[운영체제- 김덕수 교수님] 프로세스 상호배제, 동기화(6/7) - Eventcount/Sequencer

세마포어는 누구를 깨울지 순서가 부정확하다.

그래서 나온 것이 이벤트 카운트

• 은행의 번호표와 비슷한 개념
• Sequencer
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 발생 사건들의 순서 유지
  • ticket() 연산으로만 접근 가능
• ticket(s)
  • 현재까지 ticket() 연산이 호출된 횟수에 하나를 더해서 반환
  • indivisible operation
  • t <- ticket() + 1
• Eventcount
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 특정 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E,v) 연산으로만 접근 가능
• read(E)
  • 현재 Eventcount 값 반환
• advance(E)
  • E <- E + 1
  • E를 기다리고 있는 프로세스를 깨움(wake - up)
  • 다음 이벤트 카운터를 진행시키는 것이 V() 연산과 유사(풀기)
• await(E, v)
  • v는 정수형 변수
  • if (E < v) 이면, E에 연결된 Qe 에 프로세스 전달(push) 및 CPU scheduler 호출
  • 은행 번호표 생각하면 쉬운데, E가 10 이고 v가 15면
  • E가 15가 될때 까지 기다리고, v가 10 인 애를 일시킴
  • 티켓 배분하고 기다리는 것이 P() 연산과 유사(잠그기)

복잡해 보이니까 공유 변수 부분부터 확인을 하고 넘어가겠습니다.

• Pticket, Cticket
  • 각각 프로듀서가 호출한 티켓과 컨슈머가 호출한 티켓
• In, Out
  • 이것은 환형 큐이니까 물건을 놓는 부분과 가져가는 부분을 가르키는 포인터
• buffer
  • 메시지를 담을 수 있는 컨테이너(메모리)입니다.

‏‏‎ ‎

자 인제 늘 그렇듯, Producer Pi 부분부터 확인 하도록 해보죠.

1. create new message
   1. 메세지를 생성합니다. 이제 어떻게 버퍼에 담는지 보도록하죠.
2. t <- ticket(Pticket), await(In, t)
   1. t 가 의미하는 것은 현재 생산자의 번호표를 의미합니다.
   2. "지금 In이 t까지 올 때 까지 기다리겠다" 라는 것을 의미합니다.
   3. 이 두 명령이 사실상 P()와 같다고 보시면 됩니다.
      1. P() - 잠그는 것
3. 잠그는 것이 있다면 푸는 것도 있겠네요~ 밑에부터 보시죠.
   1. advance(In) 이 그 역할을 합니다.
   2. V()랑 같은 것이지요.
4. 자 그 다음에 await(Out, t - N + 1) 이라는 await가 또 나왔습니다.
   1. 이 말은 무엇일까요? 이것은 프로듀서가 생산할 때 공간이 있는지 체크하는 명령입니다.
   2. Out은 물건을 내보낼 자리를 확인하는 것입니다.
   3. 공간은 어떻게 확인 할 수 있을까요?
   4. 공간 >= 1 이 참이면 공간이 있다는 말이겠군요.
   5. 아무것도 없을 때 N개의 공간이 있고, 생산자의 티켓인 t만큼 있다면 현재 남은 공간은 N - t 이라고 할 수 있습니다.
   6. 여기서 out 은 물건을 빼간 자리를 뜻하므로, 총 공간의 공식은
   7. N-t + out 입니다. 그럼 위의 식에 대입해서 본다면
   8. Out >= t - N + 1 이 성립하겠네요!
   9. 이렇게 한 이유는 out이 이벤트 카운터이기 때문입니다.
   10. "이벤트 카운터가 t - n + 1 이 될때 까지 기다리겠다"는 뜻입니다.
5. buffer[t mod N] <- M 은 물건을 놓으라는 뜻입니다.

‏‏‎ ‎

자 얼마 안남았습니다. 소비자 부분을 보겠습니다.

1. u <- ticket(Cticket), await(Out, u)
   1. 생산자와 마찬가지로 P() 역할을 하는 명령입니다.
   2. 소비자의 티켓을 발행해서 u에 저장하고,
   3. 물건이 나오는 이벤트 카운터(Out)가 u보다 작다면 기다리고, 같으면 물건을 가져갑니다.
2. await(in, u+1)
   1. 이것은 무엇일까요?
   2. 물건 수 >= 1
   3. 이면 들어갈 수 있다는 말입니다.
   4. 물건 수는 == In(전체 물건의 수) - u(소비자의 수)입니다.
   5. 이벤트 카운터 In을 기준으로 정리하면
   6. In >= 1 + u 가 될 때 까지 기다려라(await)라는 뜻입니다.
3. m <- buffer[u mod N]
   1. 버퍼에 놓인 물건을 가져가고요
4. advance(Out)
   1. 하면서 꺼내간 수를 더합니다.

‏‏‎ ‎

복잡한 듯 이해도 가네요.

---

정리

‏‏‎ ‎

• No busy waiting
• No starvation
  • FIFO scheduling for Qe
• Semaphore 보다 더 low-level control 이 가능

‏‏‎ ‎