[운영체제] 6. Process Synchronization (=Concurrency Control) (3)

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Synchronization Hardware

하드웨어적으로 Test & Modify를 atomic하게 수행할 수 있도록 지원함으로써 not progress 문제를 해결할 수 있다.

Test & Set 명령어를 따로 수행한다면, Set 이후 context switch가 발생하여 Algorithm2와 동일한 문제가 발생할 수 있다. Test_and_Set 회로를 만들면 하나의 operation처럼 수행함으로써(atomic) 문제를 해결한다.

 

Mutual Exclusion with Test & Set

Synchronization variable : boolean lock = false;

Process Pi

 

do {
    while(Test_and_Set(lock));
    critical section;
    lock = false;
    remainder section
}

 

그러나 Busy waiting 문제가 여전히 발생

2. Semaphores

앞의 방식들을 추상화함

 

Semaphore S

- integer variable

- 아래의 두 가지 atomic 연산에 의해서만 접근 가능

공유데이터 획득, P(S) : while(S<=0) do no-op; S--;

자원의 개수가 0이거나 음수라면 양수가 될 때까지 while문을 도는 busy wait 발생. 

공유데이터 반납, V(S) : S++;

Critical Section of n Processes

Synchronization variable

semaphore mutex; 

 

Process Pi

 

do {
    P(mutex); /*if positive, dec&enter, otherwise, wait.*/
    critical section
    V(mutex);
    remainder section
} while(1);

 

busy wait (=spin lock) 방식은 효율적이지 못함. -> block & wakeup 방식(=sleep lock)으로 구현

Two types of Semaphores

- Counting semaphore: 도메인이 0 이상인 임의의 정수값. 주로 resource counting에 사용.

- Binary semaphore (=mutex): 0 또는 1 값만 가질 수 있는 semaphore. 주로 mutual exclusion(lock/unlock)에 사용. 

3. Block/Wakeup Implementation

Semaphore를 다음과 같이 정의

 

typedef struct
{
    int value; /* semaphore */
    struct process *L; /* process wait queue */
} semaphore;

 

block과 wakeup을 다음과 같이 가정

- block: 커널은 block을 호출한 프로세스를 suspend 시킴. -> CPU를 소모하지 않음!

- wakeup(P): block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김.

Block/Wakeup version of P() & V()

P(S)

 

S.value--; /* prepare to enter */
if(S.value < 0){ /* negative, cannot enter */
    add this process to S.L;
    block();
}

 

V(S)

 

S.value++;
if(S.value <= 0){ /* wait queue에 PCB 대기 중이면 */
    remove a process P from S.L;
    wakeup(P);
}

4. Busy-wait v.s. Block/Wakeup

Block/Wakeup overhead v.s. Critical section 길이

- Critical section의 길이가 긴 경우 Block/Wakeup이 적당. (while문을 계속 돌며 CPU가 소모되기 때문)

- Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음. (suspend->wakeup 시 발생하는 context switch로 인한 오버헤드)

- 일반적으로는 block/wakeup 방식이 더 좋음!

5. Deadlock and Starvation

Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 (Algorithm2에서 발생한 문제)

 

S와 Q가 1로 초기화된 semaphore

 

서로 하나씩 차지한 상태로 상대방의 것을 요구함.

해결: S->Q 순서를 정해서 자원을 잡도록 함.

 

Starvation: indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상.

6. Classical Problems of Synchronization

Bounded-Buffer Problem(=Producer-Consumer Problem)

Shared data

buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)

 

Synchronization variables

mutual exclusion -> Need binary semaphore(Shared data의 mutual exclusion을 위해. lock/unlock)

resource count -> Need integer semaphore(남은 full/empty buffer의 수 표시)

 

Synchronization variables: semaphore full = 0, empty = n, mutex = 1;

 

Producer

 

do {
    produce an item in x
    ...
    P(empty);
    P(mutex);
    ...
    add x to buffer
    ...
    V(mutex);
    V(full);
} while(1);

 

1. emtpy 버퍼가 비어 있는지 확인 (없으면 기다림) - P(empty)

2. 공유데이터에 lock을 건다. - P(mutex)

3. empty 버퍼에 데이터 입력 및 buffer 조작(가리키는 위치 이동)

4. lock을 푼다. - V(mutex)

5. full 버퍼 하나 증가 - V(full)

 

Consumer

 

do {
    P(full);
    P(mutex);
    ...
    remove an item from buffer to y
    ...
    V(mutex);
    V(empty);
    ...
    consume the item in y
    ...
} while(1);

 

1. full 버퍼가 있는지 확인 (없으면 기다림) - P(full)

2. 공유데이터에 lock을 건다. - P(mutex)

3. full 버퍼에서 데이터 꺼내고 buffer 조작(가리키는 위치 이동)

4. lock을 푼다. - V(mutex)

5. empty 버퍼 하나 증가 - V(empty)

Readers-Writers Problem

한 process가 DB에 write 중일 때 다른 process가 접근하면 안 됨. 그러나 read는 동시에 여럿이 해도 됨.

solution

- writer가 DB 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들은 다 DB에 접근하게 해준다.

- writer는 대기 중인 reader가 하나도 없을 때 DB 접근이 허용된다.

- 일단 writer가 DB에 접근 중이면 reader들은 접근이 금지된다.

- writer가 DB에서 빠져나가야만 reader들의 접근이 허용된다.

 

Shared data

DB 자체 및 readcount(현재 DB에 접근 중인 reader들의 수)

 

Synchronization variables

mutex (공유 변수 readcount를 접근하는 코드의 mutual exclusion을 보장하기 위해 사용)

db (reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할)

-> 둘 다 binary semaphore

 

Shared data: int readcount = 0; DB 자체;

Synchronization variables: semaphore mutex = 1, db = 1;

 

Writer

 

P(db);
...
writing DB is perfomred
...
V(db);

 

Reader

 

P(mutex); //readcount에 대한 semaphore
readcount++;
if(readcount==1) P(db); //첫 reader이므로 db를 획득. block writer.
V(mutex); 
...
reading DB is performed
...
P(mutex);
readcount--;
if(readcount==0) V(db); //마지막 reader이므로 db unlock. enable writer.
V(mutex);

 

Starvation 문제 발생 -> reader가 db를 획득한 상태에서, writer가 먼저 도착해도 reader가 끊임없이 도착하면 starvation이 발생함.

해결 -> 일정시간 간격을 둬서 reader를 받아들이고 writer에게 기회를 줌.

Dining-Philosophers Problem

 

상황 : 다섯 명의 철학자가 원탁에 앉아 있고, 양 옆 포크가 하나씩 있다. 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다. 만약 다섯 철학자가 동시에 왼쪽의 포크를 든다면, 오른쪽의 포크는 이미 가져가진 상태이기 때문에 다섯 명 모두가 무한정 서로를 기다리는 deadlock에 빠지게 된다. 

 

Synchronization variables: semaphore chopstick[5]; /*initailly all values are 1*/

 

Philosopher i

 

do {
    P(chopstick[i]); //왼쪽 젓가락 lock
    P(chopstick[(i+1)%5]); //오른쪽 젓가락 lock
    ...
    eat();
    ...
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
    ...
    think();
    ...
} while(1);

 

문제점

- deadlock 가능성이 있다. (ex. 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우)

 

해결 방안

- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.

- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다. (젓가락을 집는 우선순위 부여)

 

Shared data: enum {thinking, hungry, eating} state[5];

Synchronization variables: semaphore self[5] = 0; semaphore mutex = 1;

self[i]  = 1이면 양쪽 젓가락을 모두 잡을 수 있는 상태를 의미. mutex는 state[]에 대한 lock(binary semaphore).

 

Philosopher i

 

do {
    pickup(i);
    eat();
    putdown(i);
    think();
} while(1);

 

void pickup(int i){
    P(mutex); //state에 대한 lock
    state[i] = hungry;
    test(i); //젓가락을 모두 잡을 수 있는지 test
    V(mutex);
    P(self[i]); //자원이 없으면 block. 인접 철학자가 젓가락을 내려놓음으로써 test 연산이 다시 수행 가능
}

 

void putdown(int i){
    P(mutex);
    state[i] = thinking;
    test((i+4)%5); //왼쪽 철학자
    test((i+1)%5); //오른쪽 철학자
    V(mutex);
}

 

본인이 젓가락을 내려놓음으로써 나의 왼쪽, 오른쪽 철학자가 식사를 할 수 있는지 test함. 

 

void test(int i){
    if(state[(i+4)%5]!=eating && state[i]==hungry && state[(i+1)%5]!=eating){
        state[i] = eating;
        V(self[i]); //self[i] = 1로, block 상태라면 wakeup해줌.
    }
}