운영체제 6 : Process Synchronization and Mutual Exclusion (3)

Busy waiting 문제를 해결하기 위해서 OS가 지원하는 Solution을 살펴보자.

• Spinlock
• Semaphore
• Evencount/sequencer

---

 

Spinlock

: 정수 변수로, 초기화, P( ), V( ) 연산으로만 접근 가능하다.

 

P( ), V( )는 atomic 연산을 하도록 OS 가 보장해준다. 즉, 중간에 preemption되지 않는다.

 

- P는 물건을 꺼내고, V는 물건을 넣는 것으로 볼 수 있다.

- S는 물건의 개수로 보면 된다.

- P는 자물쇠를 잠그고, S는 자물쇠를 푼다고 생각할 수도 있다.

P(S) {
    while (S <=0) do
    endwhile;
    S <- S-1;
}

물건이 없다면, 물건이 생길 때까지 기다린다.

물건이 생기면 물건을 가져가고 빠져나간다.

 

V(S) {
    S <- S+1;
}

물건을 넣는다.

 

Spinlock

P가 진행 중에 preemption되지 않으므로, 동시에 들어가거나 아무도 들어가지 않는 상황을 방지할 수 있다.

 

문제점

- P(S)에서 오랫동안 기다리는 것을 멈출 수 없으므로, 프로세스가 CPU에서 불필요하게 너무 오래 기다린다.

- busy waiting을 여전히 해결하지 못했다.

---

Semaphore

: 음이 아닌 정수형 변수(S)로, 초기화 연산, P( ), V( )로만 접근 가능하다.

 

- Spinlock과 유사하다.

- 임의의 S 변수 하나에 ready queue 하나가 할당된다. (spinlock 과의 차이점)

- 모두 indivisible 연산이 되도록 OS가 보장한다.

- 기다려야 하는 프로세스는 block(asleep) 상태가 되어, busy waiting 을 해결한다.

- Semaphore queue에 대한 wake-up 순서는 아직 정해지지 않았다.

 

Semaphore를 2가지로 분류할 수 있다.

 

Binary semaphore

- S가 0과 1 두 종류의 값만 갖는다.

- 상호배제나 프로세스 동기화의 목적으로 사용된다.

 

Counting semaphore

- S가 0 이상의 정수값으 가질 수 있다.

- 생산자-소비자 문제 (Producer-Consumer) 문제 등을 해결할 수 있다.

 

 

전략

P(S)에서 S가 0이면 queue 에 들어가서 기다린다.

V(S)에서 작업이 끝나면 queue 에 기다리고 있는 프로세스를 깨우고, queue가 비었으면 S를 늘린다.

 

spinlock과의 차이점

계속 while문을 도는 것이 아니라 queue에 들어가 있다가 V(S)가 신호를 보내면 CS에 들어간다.

---

Semaphore로 해결 가능한 동기화 문제들

- 상호배제 문제 (Mutual exclusion)

- 프로세스 동기화 문제 (process synchronization problem)

- 생산자-소비자 문제 (producer-consumer problem)

- Reader-writer 문제

- Dining philosopher 문제

---

1. Mutual exclusion

Spinlock과 다르게 P( )에서 직접 active 값을 확인하며 기다리는 것이 아니라, V( )가 깨워줄 때까지 기다린다는 점이다.

그렇게 busy-waiting 문제를 해결하였다.

 

2. Process synchronization

프로세스 Pi 는 프로세스 Pj 가 Lj 지점을 통과할 때까지 Li 지점에서 대기한다.

프로세스 Pj 가 Lj 를 통과하기 전이라면 Pi 는 Li 에서 queue로 들어가게 된다.

Pj 가 Lj 를 통과하게 되면 queue의 Pi 를 깨워준다.

 

3. Producer-Consumer problem

메시지를 생산하는 도중에 다른 메시지가 쌓이면 안된다.

메시지를 생산하는 도중에 소비가 시작되면 안된다.

 

 

 

버퍼가 하나일 때와 여러 개일 때를 살펴보자.

 

Producer-Consumer problem with single buffer

물건을 놓을 때 가져가면 안되고, 물건을 가져갈 때는 놓을 수 없다.

즉, 버퍼에는 한 번에 한 프로세스만 접근해야한다.

버퍼가 CS 영역과 비슷하다.

 

consumed 변수

: 소비되었는 지를 나타내는 지표. 1이면 소비되어서 버퍼가 비어있음을 의미한다.

 

produced 변수

: 생산되었는 지를 나타내는 지표. 1이면 생산되어서 버퍼가 채워져있음을 의미한다.

 

두 변수는 항상 반대 값을 가진다.

 

전략 Pi

- buffer에 접근하기 전에 consumed 변수를 보고 소비했는지를 파악한다.

- 소비되었으면 consumed를 감소시키고, buffer에 메시지를 놓고

- consumed가 0으로 소비되지 않았다면, queue에 들어가 기다린다.

- 버퍼에 나오고 난 후에는 produced를 증가시키고, queue에 기다리고 있는 프로세스가 있다면 깨운다.

 

전략 Pj

- buffer에 접근하기 전에 produced 변수를 보고 메시지가 있는지 파악한다.

- 메시지가 있다면 produced를 감소시키고, buffer에서 메시지를 가져온다.

- produced가 0으로 메시지가 없다면, queue에 들어가 기다린다.

- 버퍼에 나오고 난 후에는 cosumed를 증가시키고, queue에 기다리고 있는 프로세스가 있다면 깨운다.

 

Producer-Consumer problem with N-buffers

 

버퍼 사이즈가 n일 때의 경우를 살펴보자.

 

- in : 메시지를 넣어가는 지점을 가리키는 포인터

- out : 메시지를 가져갈 지점을 가리키는 포인터

- nrfull + nrempty = N

- mutexP : 한 번에 한 프로세스만 버퍼에 메시지를 입력하도록 한다.

- mutexC : 한 번에 한 프로세스만 버퍼에서 메시지를 가져오도록 한다.

 

전략 Pi

- 위 1번의 Mutual Exclusion을 해결할 때처럼 버퍼에 입력하려는 프로세스가 겹치지 않도록 mutextP를 사용한다.

- P(nrempyt) 에서 버퍼에 빈 자리가 있는 지 확인한다.

- 빈 자리가 있으면 통과하고, 없으면 queue에 들어간다.

- 버퍼에 메시지를 넣고 버퍼를 가리키는 포인터 in 을 증가시킨다.

- V(nrfull) 에서 queue에서 기다리고 있는 Pj가 있는 지 확인한다.

- 있으면 깨우고 통과하고, 없으면 nrfull을 증가시킨다.

 

전략 Cj

- mutexC를 검사하여 여러 프로세스가 버퍼에서 메시지를 동시에 가져오지 않도록 한다.

- P(nrfull) 에서 버퍼에 메시지가 있는지 확인한다.

- 메시지가 있으면 통과하고, 없으면 queue에 들어간다.

- 메시지를 가져오고, 버퍼를 가리키는 포인터 out 을 증가시킨다.

- V(nrempty) 에서 queue에서 기다리고 있는 Pi가 있는 지 확인한다.

- 있으면 깨우고 통과하고, 없으면 nrempty를 증가시킨다.

 

4. Reader-Writer problem

Reader

: 데이터에 대해 읽기 연산만 수행하기 때문에, 여러 프로세스가 동작해도 상관 없다.

- 하지만 읽는 중에 writer가 동작하면 안된다.

 

Writer

: 데이터에 대해 갱신 연산을 수행하여, 하나의 프로세스만 동작해야 한다.

- 우선권을 reader 혹은 writer 에게 주는 두 방법이 있다.

 

Reader-Writer problem (reader preference solution)

Reader가 우선권을 가진다.

 

전략 Ri

- 읽기 전과 후의 작업은 한 프로세스만 동작한다.

- 읽기 전에 writer 가 동작하지 못하도록 wmutex를 수정한다. 만약 다른 reader가 이미 수정했으면 넘어간다.

- reader 의 수를 증가시킨다.

- 읽은 후에 reader를 감소시키고, 자신이 마지막 reader라면 wmutex를 수정하여 writer가 동작 가능하도록 한다.

 

전략 Wj

- P(wmutex) 와 V(wmutex) 를 이용하여 한 번에 한 프로세스만 동작하도록 한다.

 

---

 

Eventcount / Seuquencer

- busy waiting 이 없다.

- 먼저 온 프로세스가 먼저 동작하는 FIFO 방식이므로, starvation 이 없다.

- Semaphore 보다 더 세부적 (low-level) 으로 조작이 가능하다.

 

Sequencer

: 정수형 변수로 발생 사건들의 순서를 가진다.

 

- 생성시 0으로 초기화되고 감소하지 않는다.

- ticket( ) 연산으로만 접근이 가능하다.

- 은행 번호표라고 생각하면 쉽다.

 

ticket(S)

: 현재까지 ticket( ) 연산이 호출된 횟수를 반환한다.

 

 

---

Eventcount

: 정수형 변수로 특정 사건의 발생 횟수로 기록한다.

 

- 생성시 0으로 초기화되고 감소하지 않는다.

- read(E), advance(E), await(E, v) 연산으로만 접근 가능하다.

 

read(E)

: 현재 Eventcount 값을 반환한다.

 

advance(E)

: E를 증가시키고, 증가된 번호를 가진 프로세스를 깨운다. (wake-up)

 

await(E, v)

: 받은 sequencer이 현재 처리중인 E보다 크면 E에 연결된 queue에 프로세스를 전달하고, CPU 스케줄러를 호출한다.

 

---

1. Mutual Exclusion

 

전략

- 프로세스가 ticket(S)으로 자신만의 수를 받는다.

- await(E, v) 로 현재 CS에 들어갈 수 있는 수를 가리키는 E를 보고, 자신이면 CS로 들어간다.

- 새로운 프로세스가 수를 받고 E보다 자신의 수 v가 더 크다면 queue에서 기다린다.

- CS 에서 나온 프로세스는 advance(E)로 E를 증가시키고, queue 안의 프로세스를 깨운다.

 

2. Producer-Consumer problem

전략 Pi

- 프로세스는 메시지를 생성하고 자신만의 수 t 를 받는다.

- CS에 들어가기 전에 현재 들어가도 되는 번호 In 보다 자신의 t 가 크면 queue에 들어가서 기다린다.

- 메시지를 넣을 공간이 버퍼에 있는지 체크한다.

- 공간 ( N - t + OUT ) >= 1 이어야 버퍼에 자리가 있는 것이다. OUT은 메시지를 가져간 횟수이다.

- 정리하면 OUT >= t - N + 1

- 공간이 있으면 메시지를 넣고 In을 증가시킨다.

 

전략 Cj

- 프로세스는 자신만의 수 u를 받고 Out보다 크면 queue에서 일단 기다린다.

- 자신의 차례가 되면 queue에 메시지가 있는지 확인한다.

- 메시지의 갯수 ( In - u ) >= 1 이어야 메시지를 가져갈 수 있다.

- 정리하면 In >= u + 1

- 메시지가 있으면 가져가고 Out을 증가시킨다.

 

다음 글에서는 마지막으로 Language-Level 에서의 solution을 살펴볼 것이다.

---

본 글은 HPC Lab. KOREAHECH YOUTUBE 채널의 김덕수 교수님 강의를 보고 작성되었습니다.

[Course] Operating System (CPA310) - 운영체제 강의