06. Process Synchronization (2/5), (3/5)

1. 충족 조건

가. Mutual Exclusion(상호 배제): 어떤 프로세스가 critical section에 있으면 다른 모든 프로세스들은 들어가면 안 된다.

나. Progress(진행): Critical section에 아무도 업을 때, 프로세스가 들어가고 싶으면 들어갈 수 있어야 한다.

다. Bounded Waiting(유한 대기):Critical section에 들어가려고 요청한 후 허용되기 전까지 너무 기다리면 안 됨(횟수 제한)

2. 알고리즘

가.

int turn;

initially turn = 0            //들어갈 차례

do{

while (turn != 0);        //my turn?

critical section

turn = 1                    // Now it's your turn

remainder section

} while(1);

Mutual Exclusion은 가능, Progress는 만족 못 함(무조건 번갈아 들어가야 하므로)

나.

boolean flag[2]                //들어가겠다는 의미

flag[모두] = false

do{

flag[i] = true;            //pretend I am in

while(flag[j]);            // Is he also in? then wait

critical section

flag[i] = false            //I am out now

remainder section

} while(1)

Mutual Exclusion은 가능, Progress는 만족 못 함(동시에 들어가면 아무도 못 들어감)

다. Peterson's Algorithm

do{

flag[i] = true

turn = j

while(flag[j] && turn == j);

critical section

flag[i] = false

remainder section

} while(1)

3개 모두 만족한다.

단점: Busy Waiting(=spin lock), 계속 CPU와 memory를 쓰면서 wait한다.

라. Synchronization Hardware: 하드웨어 적으로 Test와 Modify를 atomic하게 수행하면 간단히 해결

Test_and_Set : 원래의 값을 읽고 그 값을 1(True)로 세팅하는 것을 하나의 instruction으로 만듦

do{

while(Test_and_Set(lock))

critical section

lock= false

remainder section

}

3. Semaphores: 앞의 방식들을 추상화 시킴

가. P(S): while (S<=0) do no-op; S--; 변수를 획득하는 과정

나. V(S): S++                                자원을 내어놓는 것

-> 위 2개가 atomic 하다고 가정

다. typedef struct{

int value                //semaphore

struct process* L    //process wait queue

} semaphore

라. P(S):    S.value--

                   if(S.value < 0){

add this process to S.L

block()

}

마. V(S):    S.value++

   if(S.value <= 0){

remove a process P from S.L

wakeup(P)

}

4. Counting semaphore: 자원의 개수가 여러개

5. Binary semaphore: 자원의 개수가 2개(mutex)

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

가. 하나의 프로세스가 특정한 자원을 가진 채로 block되었을 때, 다른 프로세스가 그 자원을 요구할 때 발생

-> 서로 상대방의 것을 원하고, 내어놓지 않아서 생기는 문제

-> 자원을 얻는 순서를 정해주면 해결됨

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

-> 특정 프로세스만 자원을 가져서 다른 프로세스는 영원히 가질 수 없는 현상

8.