[OS] 6. 프로세스 동기화 - Mutual Exclusion OS supported SW Solution (EventCount/ seqiencer)

어떻게 하면 상호배제가 잘 작동하는 알고리즘을 만들 수 있을까? 

Mutual Exclusion Solutions

• SW solutions
  
  • Dekker’s algorithm (Peterson’s algorithm)
  • Dijkstra’s algorithm , Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm
• HW solution
  
  • TestAndSet (TAS) instruction
• OS supported SW solution
  
  • Spinlock
  • Semaphore
  • Eventcount /sequencer
• Language Level solution
  
  • Monitor

 

Eventcount / Sequencer

은행의 번호표와 비슷한 개념

앞서 semaphore에서는 wake up one of them이라는 특징이 있어 한 프로세서가 계속 대기할 수 있는 문제가 있다.

먼저 대기한 프로세서에게 우선권을 주는 알고리즘이 필요함.

 

Sequencer

• 정수형 변수
• 생성시 0 으로 초기화 , 감소하지 않음
• 발생 사건들의 순서 유지
• ticket() 연산으로만 접근 가능 (티켓을 뽑는 행위..)

 

ticket(S) (현재 기다리고 있는 티켓 수)

• 현재까지 ticket() 연산이 호출 된 횟수를 반환
• Indivisible operation

 

Eventcount (은행원이 버튼을 눌러 번호에 있는 사람을 부를 때)

• 정수형 변수
• 생성시 0 으로 초기화 , 감소하지 않음
• 특정 사건의 발생 횟수를 기록 (현재까지 은행업무를 처리한 사람 수)
• read(E), advance(E), await(E, v) 연산으로만 접근 가능 (특별한 연산자로 접근 가능함)

 

read(E)

• 현재 Eventcount 값 반환

 

advance (E) (번호를 증가시키고 기다리고 있는 번호의 프로세스를 깨운다)

• E <- E + 1 (호출번호가 1증가)
• E 를 기다리고 있는 프로세스를 깨움 (wake up)

 

await(E, v)

• V 는 정수형 변수
• if (E < v)(현재번호<내 번호표) 이면 E 에 연결된 QE 에 프로세스 전달 (push) 및 CPU scheduler 호출
• 내 번호가 호출된 번호보다 높으면 QE에 내 번호가 오면 깨워달라고 전달함

 

Mutual exclusion

1. 첫번째 프로세스가 ticket(S)를 통해 번호표를 뽑음, 내 번호표는 0이 되고 S->1이 됨, 은행원이 부르는 E: 0
2. await(E,V)를 보고 E, V가  같으므로 CS에 진입
3. 두번째 프로세스가 ticket(S)를 통해 번호표를 뽑음, S->2로 만들고 자신의 번호는 1이 됨
4. 은행원 E가 아직 0번을 부르고 있으므로 1이 될때까지 QE에서 await함.
5. 첫번째 프로세스가 CS에 나온 후 advance(E)가 실행되어 E가 1증가함 E->1 (이전에는 E->0)

세마포어의 starvation이 해결됨.

 

Producer Consumer problem (queue size(buffer size): n)

변수들

• P, C sequencer
• In(물건을 놓는이벤트)
• out(물건을 꺼내는 이벤트)
• buffer(물건이 들어가는 크기)

위의 코드를 살펴보면

• Producer, Consumer의 T<-ticker(Pticket)과 awit(In,t)연산은 ME에서 다뤘던 P(S)연산과 같음
• advance(In); 은 V(S)연산과 같음
• await(Out, t-N+1); buffer[t mod N] <-M; 은 CS와 같음
• 즉 한번에 한명만 CS에 진입하게 만들었다.

 

Producer의 과정

1. Producer가 ticket연산을 통해 번호표를 생성한다. (한번에 한명씩 들어옴)
2. Producer는 await(Out, t -N + 1); 를 통해 공간이 있는지 확인한다.
3. (공간이 있다 = 공간>=1 , 공간 = N-t+Out, Out>=t-N+1 (공간이 있다는 조건))
4. 공간이 있다면 Buffer를 통해 물건을 놓고 나온다.

Consumer의 과정

1. 물건수가 1개 이상일 때 들어갈 수 있음.
2. 물건수가 1개보다 작으면 기다림 (In: 물건을 놓은 이벤트)
3. 물건을 아무도 안가져갔다면 물건은 In 개수만큼 있음
4. 물건을 가져가기로 예약한다면 In-u가 된다. (In-u<1 , In<= u+1)
5. 이는 await연산과 같음 (await(In,u+1))

 

Eventcount/Sequencer 특징

• No busy waiting
• No starvation
  
  • FIFO scheduling for QE (순서를 컨트롤 할 수 있다!)
• Semaphore 보다 더 low level control 이 가능

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---