Process Synchronization - 정의, Race condition, Critical section, Peterson Algorithm, Semaphore, Problem, Monitor

Process Synchronization

Process Synchronization

Definition : 프로세스들이 공유된 자원을 사용할 때 동시에 공유 자원 접근 시 생길 수 있는 여러 문제들을 해결하기 위한 방법 -> 동시에 공유자원에 접근 시 데이터의 비일관성을 야기시킬 수 있다.

Race Condition

Definition : 여러 프로세스가 같은 데이터를 동시에 접근 또는 조작하는 것을 의미

-> 조작 후 결과가 예상치 못한 결과를 만들어낼 수 있음(동시에 접근 시 나중에 수행된 프로세스의 결과값을 따르게 된다.

- 위와 같은 경우 Process A가 먼저 공유 변수를 불러와 수정했지만 저장되기 전에 Process B가 원래의 값을 불러와 수정해 A가 저장한 후 B가 저장해 Process A의 수행결과가 손실된 것을 볼 수 있다.

Preemptive kernel vs Nonpreemptive kernel

1) Nonpreemptive kernel

- 커널 모드에서 동작 중에는 다른 프로세스가 접근하는 것을 막음

2) Preemptive kernel

- 커널 모드에서 동작 중이더라도 다른 프로세스가 접근할 수 있음

-> 이러한 경우에 Race condition이 발생할 수 있음

Critical Section

Definition : 공유 데이터 접근이 일어나는 code segment부분을 의미

-> Race condition을 막기 위해 해결책이 필요함

Solution

1) Mutual Exclusion(상호 배제)

- 두개 이상의 프로세스가 공용 데이터에 접근하는 것을 막음

2) Progress

- 어떤 프로세스도 공유 데이터에 접근하고 있지 않을 때 프로세스가 접근 요청을 하면 접근을 허용해야 한다.

3) Bounded Waiting

- 공유 데이터 접근 요청 후 일정 시간을 기다린다면 접근할 수 있도록 해줘야한다. (일정 시간을 설정해준다는 의미)

Peterson Algorithm

- Critical Section 접근 시 발생하는 문제를 막기 위한 2개의 프로세스 사용에서 쓸 수 있는 알고리즘

1 2 3 4 5 6 7 8 9 10 11

do {                                do {             flag[i] = true;                     flag[j] = true;     turn = j ;                          turn = i;     while(flag[j] && turn == j);        while(flag[i] && turn == i);     //Critical Section//                //Critical Section//     flag[i] = false;                    flag[j] = false; } while(1);                         } while(1);     Pi Process                          Pj Prcoess   int turn = 0; bool flag[2];         Colored by Color Scripter

cs

- turn이라는 변수와 flag라는 배열 사용

- process i에서는 j의 flag가 1(true)이고 turn이 j라면 while문을 통해 process j의 작업이 끝날 때 까지 기다린다. j의 수행이 끝난 후 자신의 flag를 0(false)로 바꿔주면 process i는 while문에서 빠져나오고Critical section에 접근할 수 있게 된다.

-> 단점 : Busy waiting(while문으로 구현되어 있기 때문에 CPU를 계속 소모하며 기다림)

Synchronization Hardware

Definition : 하드웨어를 통해 Process Synchronization을 구현하는 방법

1) Uniprocessors

- Interrupt를 차단하는 방법

- preemption을 허용하지 않고 프로세스를 수행

- 단점 : Multiprocessor의 효율을 살릴 수 없다.

-> 최근에는 Atomic한 하드웨어 지시자들이 있음(TestAndSet(),Swap())

Semaphore

Definition : Critical Section 접근을 효율적으로 할 수 있게 해주는 커널에서 제공하는 메커니즘

- Semaphore는 integer형 변수로 되어있음

- wait(), P() -> wait함수를 통해 critical section에 들어갈 때 다른 프로세스가 접근하지 못하도록 함

- signal(), V() -> signal함수를 통해 critical section에서 나갈 때 다른 프로세스가 접근할 수 있도록 함

Type

1) Binary Semaphore(mutex)

- 0~1의 값만 사용하는 semaphore

2) Counting Semaphore

- Full, Empty 사용, 제한되지 않은 정수 범위 사용하는 semaphore

-> Semaphore도 마찬가지로 Busy waiting을 사용한다. 

-> Busy waiting을 없애기 위한 Semaphore사용에는 block,wakeup 함수를 사용한다. while문을 통해 기다리는 것이 아닌 sleep()함수와 같은 원리로 자원이 없으면 block을 통해 자원을 기다린다

Problem of Synchronization

1) Bounded Buffer Problem

- 버퍼의 크기가 유한하기 때문에 생길 수 있는 문제이다. 

- mutex는 1로 초기화, Counting에서는 full은 0, empty는 N으로 초기화된다.

- 생산자는 buffer에 공유 데이터를 넣고, 소비자는 buffer에서 공유 데이터를 꺼내간다.

- Buffer가 꽉찰 경우 생산자는 공유 데이터를 넣을 수 없고, 비어있을 경우 소비자는 공유 데이터를 꺼낼 수 없다.

-> 즉, 이러한 문제를 해결하기 위한 해결책이 필요.  

-> 생산자와 소비자는 buffer의 상태를 확인할 수 있어야 한다.

-> 동시에 buffer에 접근하는 것을 막아야한다.

2) Dining-Philosophers Problem(병행 제어 문제)

- 식사를 하기 위해 젓가락을 집는 것을 제어하는 문제

철학자들의 식사에서 밥을 먹으려면 젓가락이 2개 필요한데 각각 자신의 왼쪽, 오른쪽에 젓가락 1개씩이 놓아져있고 두개를 집었을 경우 식사를 할 수 있다.

- 만약 모든 철학자들이 1개의 젓가락만 집고 있다면 서로 다른 젓가락을 기다리는 상태이기 때문에deadlock(교착상태)가 일어날 수 있다.

Solution

1) 가장 간단한 방법으로 한명을 내쫓는 방법이 있다.

2) 젓가락을 집을 때 왼쪽, 오른쪽 두개가 모두 존재할 때 집게하는 방법

3) 홀수 번 철학자는 왼쪽->오른쪽 순으로 집고, 짝수 번 철학자는 오른쪽->왼쪽 순으로 집게하는 방법

Monitor

- Process synchronization을 편리하게 제공해주는 높은 레벨의 Abstration

- Semaphore의 한계를 극복하기 위해 등장한 개념

- 한번에 오로지 하나의 프로세스만 모니터에 접근 가능 -> Semaphore와 비슷한 형태

- 프로세스의 모니터 접근을 Condition value를 통해 관리한다.