6. 프로세스 동기화 & 상호배제 (6) - Eventcount/Sequencer

강의 링크 : https://www.youtube.com/watch?v=S7l2UEXVhb0&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=17

3. Eventcount/Sequencer

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

1) 용어 및 연산

(1) Sequencer

은행에서 대기표 뽑는 기계 생각하면 됨.

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

(2) ticket(S)

은행에서 대기표 뽑는 기계에서 대기표를 뽑는 상황

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

(3) Eventcount

은행 창구에서 현재 업무 중인 번호를 보여주는 기계

• 정수형 변수
• 생성 시 0으로 초기화, 감소하지 않음
• 특정 사건의 발생 횟수를 기록
• read(E), advance(E), await(E, v)연산으로만 접근 가능

(4) read(E)

은행 창구에서 현재 업무 중인 번호를 확인하는 상황

• 현재 Eventcount 값 반환

(5) advance(E)

은행 창구에서 현재 업무를 종료하고 다음 대기자를 받기 위해 업무 가능 번호를 +1하는 상황

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

(6) await(E, v)

E는 은행 창구에서 업무볼 수 있는 번호(Eventcount), v는 현재 내가 든 번호표

• V는 정수형 변수
• if (E<v)이면 E에 연결된 Qe에 프로세스 전달(push) 및 CPU scheduler 호출

2) Mutual exclusion (상호 배제)

띵동띵동 은행으로 비유해서 생각해보쟈

1. 은행에 간다
2. v <- ticket(S) : 대기표를 뽑는다.
3. await(E, v) : 내 차례가 될 때까지 기다린다.
4. Critical Section : 업무를 본다
5. advance(E) : 내 업무를 마치고, 다음 차례를 부른다.

-> 2, 3번이 P()연산, 5번이 V()연산

-> 세마포어의 starvation 문제를 해결해줄 수 있음

3) Producer-Consumer problem

생산자-소비자 문제를 evencount/sequencer로 해결해봅시다

0. Pticket : 생성자의 번호표, Cticket : 소비자의 번호표, In : 물건을 놓는 이벤트, Out: 물건을 가져가는 이벤트, buffer : 크기가 n인 circular buffer
1. Producer
   1. t <- ticket(Pticket) : 생성자가 번호표를 뽑는다.
   2. await(In, t) : 자신의 차례가 올 때까지 기다린다.
   3. await(Out, t-N+1) : buffer를 넣을 공간이 있는지 확인한다.
      • 총 공간이 N개 인데, 현재 t번까지 대기 중이고, out번까지 진행되었다고 생각하면 -> 현재 N-t+out 만큼 대기 중이라는 말. N-t+out이 1이상이어야 buffer를 넣을 수 있음.
        • 이를 수식으로 나타내면 await(Out, t-N+1)
      • buffer[t mod N] <- M : 공간에 buffer를 넣는다.
   4. advance(In) : eventcount ++
2. Consumer
   1. u <- ticket(Cticket) : 소비자가 번호표를 뽑는다.
   2. await(Out, u) : 자신의 차례가 올 때까지 기다린다.
   3. await(In, u+1) : buffer가 있는지 확인한다.
      • 현재 총 In개 들어왔는데, 그 중 u개를 사용했으므로 In-u가 1보다 크거나 같아야 내가 가져갈 buffer가 존재하는 것
        • 이를 수식으로 나타내면 await(In, u+1)
      • m <- buffer[u mod N]
        • 정해진 위치에있는 물건(buffer)을 가지고 나온다.
   4. advance(Out) : eventcount ++

4) 특징 정리

• No busy waiting
• No starvation
  • Qe에 의한 선입선출 스케줄링
• 세마포어보다 더 low-level control이 가능하다. (==더 세세한 control이 가능하다. 왜냐하면 순서 control이 가능하기 때문)