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

출처 : https://www.youtube.com/watch?v=S7l2UEXVhb0&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=17

 

 

 

Eventcount / Sequencer

 

이전 강의에서 배운 semaphore에서 busy waiting 문제는 해결하였다. 하지만 wakeup에서 대기하고 있는 프로세스 중 하나를 랜덤으로 고르기 때문에 끝까지 선택되지 않을 수 있는 프로세스가 존재(starvation problem)할 수 있다.

 

이 starvation problem을 해결하고자 어떤 순서를 만들어서 깨워주기 위해서 Eventcount / Sequencer가 등장한다.

 

• 은행의 번호표와 비슷한 개념
• Sequencer : 번호표를 뽑는 기계
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음. 즉, 0부터 시작해서 계속 증가
  • 발생 사건들의 순서 유지
  • ticket() 연산으로만 접근 가능
• ticket(S) : 기계에서 번호표를 뽑는 행 
  • 현재까지 ticket() 연산이 호출 된 횟수를 반환
  • Indivisible operation

 

 

• Eventcount : 은행원이 특정 번호를 가진 고객을 부르는 것
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 특정 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E, v) 연산으로만 접근 가능
• read(E) : 현재 번호를 읽는 것
  • 현재 Eventcount 값 반환
• advance(E) : 은행원이 다음 고객을 부르면 번호가 1 증가시키고, 해당 번호의 고객을 부름
  • E <- E + 1
  • E를 기다리고 있는 프로세스를 깨움(wake-up)
• await(E, v) :  E = 은행원이 부른 번호, v = 내 번호
  • v는 정수형 변수
  • if (E < v) 이면 E에 연결된 Qe에 프로세스 전달(push) 및 CPU 스케줄러 호출. 즉, 내 번호(v)가 현재 번호(E)보다 크다면 대기실(Qe)에서 기다리고, 내 번호가 되면 깨워달라고 스케줄러에게 부탁하는 것.

 

Mutual Exclusion

 

P(S) 연산

맨 처음 번호표를 뽑으면 S = 0인 상태일테니, v = 0이 된다. 그리고 S = S + 1 = 1이 된다.

 

그 다음 await(E, v)에서 if E < v면 기달려야 하는데 E = 0, v = 0이므로 바로 CS에 입장한다. 그 뒤에, 프로세스들이 차례대로 도착하면 v = 1 S = 2, v = 2 S = 3, ... 으로 증가한다. 이때 v = 1, 2, ... 들은 if E < v 조건을 만족하므로 대기실 Qe에서 기다린다.

 

V(S) 연산

CS에 들어갔던 v = 0이 일을 마치고 나오면 advance(E) 연산으로 인해 E = E + 1 = 1 이 되고, 대기실 Qe에서 기다리는 v = 1을 호출한다.

 

우리가 은행에서 번호표를 뽑아서 업무를 보는 것과 매우 유사하다.

 

이를 통해 semaphore에서 있었던 starvation problem이 해결되었다.

 

 

사이즈가 N인 Producer-Consumer problem

 

변수

Pticket : Producer의 티켓

Cticket : Consumer의 티켓

In : 물건을 놓는 이벤트

Out : 물건을 꺼내는 이벤트

buffer : 물건을 넣는 공간 circular buffer

 

Producer Pi

 

P()연산 : CS에 하나의 프로세스만 들어갈 수 있도록 만듬

t <- ticket(Pticket) : Producer가 번호표를 뽑음

await(In, t) : 내 차례가 되면 CS에 들어감. 아니면 기다림

 

CS

await(Out, t - N + 1) : 남아있는 공간이 있는지 확인

buffet[t mod N] <- M

 

V()연산

advance(In)

 

 

Consumer Cj

 

P() 연산 : CS에 하나의 프로세스만 들어갈 수 있도록 만

u <- ticket(Cticket) : Consumer가 번호표를 뽑음

await(Out, u) : 내 차례가 되면 CS에 들어감. 아니면 기다림

 

CS

await(In, u + 1) : 물건이 있는지 확인

m <- buffer[u mod N]

 

V() 연산

advance(Out)

Consume the message m

 

 

Eventcount / Sequencer

 

• No busy waiting
• No starvation
  • FIFO scheduling for Qe
• Semaphore 보다 더 low-level control 이 가능. 즉, 순서를 컨트롤할 수 있음.