[운영체제] 6. Process Synchronization

공유데이터 접근

do {
	entry section
    critical section
    exit section
    remainder section
} while (1)

 

프로그램적 해결법의 충족 조건

1) Mutual Exclusion(상호 배제)

특정 프로세스가 critical section을 수행 중이면 다른 모든 프로세스들은 critical section에 들어가면 안 된다

2) Progress

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 critical section에 들어가게 해주어야 한다.

3) Bounded Waiting(유한 대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

 

Peterson's Algorithm

1) sync var 

- int turn, initially turn = 0; / turn == 1이면 ready

- boolean flag[2] = false; / flag[i] == true이면 ready

 

2) algorithm

3) result

- 세 가지 조건을 모두 만족한다

- 문제 : 계속 CPU와 Memory를 쓰면서 기다리기 때문에 Busy Waiting(while문을 돌면서 막는 Spin Lock) 발생한다

 

Test and Set

하드웨어적으로 test & modify를 atomic하게 수행할 수 있도록 하는 instruction

 

지금까지의 문제는 read & write를 동시에 실행할 수 없기 때문에 발생했음.

> read, write를 하나의 instruction으로 수행하도록 변경하면 소프트웨어적으로 복잡한 코드를 짤 필요가 없어짐

> 데이터의 현재 값을 읽고 / 값을 1로 바꾸어줌

1) 현재 lock을 사용하지 않으면, lock = 1로 변경하고 critical section에 들어감

2) 현재 lock을 사용하고 있으면, while문을 돌다가 lock 풀린 후에 critical section에 들어감

Semaphores

개발자의 편의를 위해 앞의 방식들을 추상화시킴

 

- integer variable S : 공유 자원의 개수

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

1) P연산 : 공유 자원을 획득하는 과정 (lock을 거는 과정) -> busy-waiting 문제가 발생!

2) V연산 : 공유 자원을 반납하는 과정 (lock을 푸는 과정)

1) Critical Section Implementation

- 단점 : busy-waiting

2) Block & Wakeup Implementation(Sleep)

1) semaphore

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

 

2) block & wakeup

- block : block을 호출한 프로세스를 suspend 시킴 / 해당 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

S < 0이면 누군가가 자원을 기다리고 있음(깨워야 할 것이 있음)

- wakeup(P) : block된 프로세스를 wakeup 시킴 / 해당 프로세스의 PCB를 ready queue에 넣음

 

3) 둘의 비교

- 일반적으로는 block & wakeup을 쓰는 것이 더 효율적임

- 그러나 critical section의 길이가 매우 짧은 경우에는 block & wakeup의 오버헤드가 busy-wait 오버헤드보다 커질 수 있음

 

Two types of Semaphores

1) counting semaphores : 자원의 개수가 여러 개 있는 경우

2) binary semaphore(mutex) : 자원의 개수가 1개밖에 없는 경우

 

Deadlock and Starvation

1) Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는 현상

-> 자원을 얻는 순서를 정해주면 해결(ex. P를 얻고 나서 Q를 얻어라)

2) Starvation : 프로세스가 suspend된 이유에 해당하는 semaphore 큐에서 빠져나갈 수 없는 현상(infinite locking)

ex) dining-philisophers problem : 특정 프로세스가 자원을 독점하고 있어서 다른 프로세스가 사용할 수 없다

 

Classical Problems of Synchronization

1) Bounded-Buffer Problem(Producer-Consumer Problem)

유한한 버퍼. producer가 데이터를 생성하고, consumer가 데이터를 꺼낸다.

1) shared data : buffer 자체 및 buffer 조작 변수(emtpy/full buffer의 시작 위치)

- 동일한 위치에 producer끼리 접근하거나 consumer끼리 접근하면 문제 발생 가능

2) synchronization var

- mutual exclusion : shared data의 mutual exclusion(binary semaphore 필요)

- resource count : 남은 full/emtpy buffer의 수(integer semaphore 필요)

 semaphore full = 0, empty = n, mutex = 1

 

2) Readers-Writers Problem

1) write & read

- write : 한 process가 DB에 write 중일 때 다른 process가 접근하면 안 됨

- read : 동시에 여럿이 해도 됨

 

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

- wirter가 DB에서 빠져나가야만 reader의 접근이 허용

 

2) shared data

int readcount = 0;
DB 자체;

 

3) sync var

semaphore mutex = 1, db = 1;

- 최초의 reader : writer로 인해 내용 변경되는 것을 막기 위해 DB에 lock을 걸고 읽는다

- 2번째~ reader : 이미 DB에 lock이 걸려 있기 때문에 아무런 조치 없이 그냥 읽는다

 

3) Dining-Philosopher Problem

1) 문제 : deadlock 가능성이 있음

2) 해결 방안

- 4명의 철학자만이 테이블에 동시에 앉을 수 있게 함

- 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 함

- 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 함

 

semaphore 버전의 해결법

test함수에서 젓가락 2개를 모두 집을 수 있는지 확인

1) 왼쪽과 오른쪽 사람이 젓가락을 사용하고 있지 않은 경우

2) 내가 배가 고픈 경우

 

Monitor

* semaphore의 문제점을 해결하기 위해 도입

- 정확하게 코딩하기 힘들다

- 정확성 correctness의 입증이 어렵다

- 자발적 협력 voluntary cooperation이 필요하다

- 한 번의 실수가 모든 시스템에 치명적인 영향

 

* 모니터 내부 procedure를 통해서만 shared data에 접근할 수 있도록 함

자동적으로 내부 procedure의 동시 실행을 막기 때문에(하나만 활성화) 개발자가 lock을 따로 걸 필요가 없음

 

* condition variable : wait(), signal() 연산

1) x.wait() : 다른 프로세스가 x.signal()을 호출하기 전까지 suspend된다

2) x.signal() : 하나의 suspen된 프로세스를 resume한다

 

1) Bounded-Buffer Problem(Producer-Consumer Problem)

semaphore에서는 변수가 값을 가지지만, monitor에서는 변수가 값을 가지지 않는 대신 조건 만족 여부를 개발자가 체크한다

 

2) Dining-Philosopher Problem

젓가락을 잡은 후의 코드는 모니터 내부에 존재