[운영체제 Step 13] - Eventcount / Sequencer

세마포어가 Busy Waiting을 해결하는 좋은 솔루션이 된 것을 지난 포스팅에서 확인했습니다.

하지만 Waiting하고 있는 프로세스를 깨울 때 누구를 깨울지 정해진 것이 없었기 때문에 그것을 정형화하는 룰이 등장하기 시작합니다.

이번에 사용될 아이디어는 은행의 번호표와 비슷한 개념으로서, 대기번호에 따라 프로세스의 순서를 매길 수 있습니다.

그것이 바로 Eventcount / Sequencer입니다.

은행을 가면 번호표를 뽑고 자신의 순서를 기다리며 자신의 번호가 호명될 때 업무를 할 수 있습니다.

여기에선 번호 뽑는 기계를 Sequencer라고 부릅니다.

이 기계는 1씩 증가하며 번호를 매기게 되며 최초 생성시 0으로 초기화를 하고 절대 감소하지 않습니다.

그리고 이 Sequencer는 ticket()의 연산으로만 접근이 가능하다는 특징을 가집니다.

이 ticket()은 번호표를 뽑은 횟수가 되겠습니다.

따라서 이 ticket()을 세 번 실행하면, 번호표도 3번이 찍히게 되게 되겠지요.

그리고 뽑은 번호표를 가지고 기다리고 있다가 이 번호표가 띵동하고 호명이 될 때 우리 업무를 볼 수 있습니다.

이 작업을 Eventcount가 수행합니다.

마찬가지로 Eventcount의 숫자도 0으로 시작하여 감소하지 않습니다.

그러므로 지금까지 업무를 수행한 사람의 수로 측정할 수 있겠습니다.

이 Eventcount는 read, advance, await로만 접근이 가능하다는 성질을 가지고 있는데요.

한 번 살펴보겠습니다.

• read(E)
• advance(E)
• await(E,v)

가 있습니다.

read는 말 그대로 Eventcount의 현재 값을 반환하는 역할입니다.

advance는 축적된 번호를 1증가시키고 자신의 번호를 기다리고 있던 프로세스를 깨웁니다.

마지막으로 await는 이렇게 이해하시면 좋습니다.

현재 자신의 번호표가 20번이고 Eventcount가 10번이면 아직 자신의 순번은 10번이나 남았으므로 기다려야 합니다.

컴퓨터는 대기실에 자신의 번호가 되면 깨워달라고 큐에 담습니다.

자 실제 문제에 대입해서 풀어봅시다.

상호배제 문제부터 살펴보겠습니다.

ticket(S)을 먼저 실행합니다.

그럼으로 인해 v는 0이 되고 S는 1이 됩니다.

그리고 await에서 E는 0, v는 0인 상태입니다.

아무도 기다리고 있는 사람이 없으므로 E와 v가 0씩 같기 때문에 바로 CS영역에 들어갈 수 있습니다.

그렇게 P1은 업무를 수행하고 있는데, P2번이 도착합니다.

이 P2번은 번호표를 뽑으며 v는 1이 찍힐테고 S는 2가 됩니다.

아직 P1이 일하고 있기 때문에 E는 0번인 상태입니다. (E < v)

따라서 대기실에 P2는 기다리기로 마음먹습니다.

그렇게 쭉 기다리고 있으면 P1이 종료되고 E를 증가시킵니다.

그럼 마침내 E와 v가 같아지게 되어 P2도 정상적으로 CS영역에 들어가서 본인의 업무를 할 수 있게됩니다.

이 솔루션은 뒤에 여러 프로세스들이 와도 순차적으로 해결할 수 있다는 장점을 가지고 있습니다.

또한 세마포어에서의 문제점인 Starvation도 이 Eventcount/Sequencer를 해결할 수 있게 됩니다.

 

다른 문제도 해결할 수 있는지 살펴보겠습니다.

Pticket과 Cticket은 생산자 티켓, 소비자 티켓을 변수로 나타낸 값입니다.

자 프로세스가 생산을 하러 왔습니다.

Pticket은 어떤 의미일까요? 생산자를 위한 번호표. 즉, 생산자가 한 번에 한 명만 들어가게 하겠단 뜻입니다.

이 생산자가 뽑은 번호표는 t에 담깁니다.

그리고 이것을 await를 하여 자신의 차례가 되면 들어가겠다고 말하고 소비자입장에서도 Cticket을 통해 u에 자신의 소비자 티켓을 저장하며 await에게 자신의 차례를 기다리겠다고 합니다.

CS에 들어가는 녀석들은 한 번에 한 명씩만 들어가겠죠?

CS에서 작업중인 프로세스가 있어서 공간이 없는데 함부로 넣으면 안되겠지요?

그래서 await(Out, t-N+1)을 시행하여 CS에 공간이 있는지 여부를 묻습니다.

자, 공간이 있는지 여부를 판단하고 싶은데 이 공간이 1이상이면 CS에 넣을 수 있잖아요??

근데 이 공간은 N개의 공간 - t개만큼 예약됨 + out만큼 물건을 빼간 수로 표현이 됩니다.

그럼 out빼고 나머지를 이항하여 본다면 out >= t - N + 1이 되며 공간이 없다는 조건은

out < t - N + 1이 됩니다.

이렇게 보니 어떻나요?

await(out, t - N + 1)의 정의가 됩니다. (await (E,v)는 (E < v)일때 큐에 담음)

그러므로 공간이 있는 것을 확인했다면 advance에 물건을 놓고 In을 1 증가시킵니다.

 

Consumer는 어떻나요?

제일 먼저 await은 물건이 있는지를 확인해야할 것입니다.

물건수가 1개 이상이면 들어갈 수 있겠죠?

그럼 그 말은 물건 수가 1보다 적으면 기다려야 할 것입니다.

물건 수는 In만큼 있고 - u만큼 티켓 생성 수가 1보다 적어야 하겠습니다.

마찬가지로 In을 제외하고 이항시키면 In < u + 1이 되고 이것은 다른말로 await(In, u+1)로 쓸 수 있는 것입니다.

그러므로 물건이 없으면 기다리고 물건이 있으면 안으로 들어가고 물건을 놓고 나오면 되겠습니다.

 

자 이렇게 생산자도 줄을 세우고 소비자도 줄을 세웠을 때도 문제를 풀어갈 수 있음을 확인했습니다.

자 정리를 해보면, Eventcount/Sequencer은 이런 장점을 가지고 있습니다.

세마포어 보다 순서를 컨트롤하기 더 쉬웠으며 busy waiting도 없고 starvation도 없었습니다.

다음 포스팅에선 랭기지 레벨에서 서포트하는 솔루션에 대해 알아보겠습니다.

감사합니다.