6. Process Synchronization, 프로세스 동기화

1. 유한 버퍼 문제

- 유한 버퍼 문제는 동기화 문제의 대표적인 예로서 

생산자는 데이터를 만들어서 버퍼에 저장하는 프로세스를 뜻하고,

소비자는 버퍼에 있는 데이터를 꺼내서 소비하는 프로세스를 뜻한다.

버퍼는 공유자원이기 때문에 생산하고 소비하는 작업이 서로 상호배제 되어야 하는데, 

이 두개를 병행하게 실행시킬 경우 올바르게 동작하지 않는다.

왜냐하면 두 개의 프로세스가 동시에 변수 counter를 조작하도록 허용하였기 때문인데, 이를 race condition 이라고 한다.

따라서 하나의 프로세스만이 변수를 조작할수 있도록 프로세스를 동기화 시켜야 한다.

( 동기화 : 순서에 있어 질서가 잘 맞게 하는것 )

2. 임계 영역

프로세스는 코드, 데이터, 스택 영역으로 이루어져 있다.

각각의 프로세스는 임계 영역 ( Critical Section ) 이라는 코드 부분을 포함하고 있다.

임계영역의 중요한 점은 "한 프로세스가 자신의 임계영역에서 실행하는 동안엔 다른 프로세스는 그임계영역에 들어갈 수 없다" 는 것이다.

임계영역을 구성하는 코드는 진입영역, 퇴출영역, 나머지 영역으로 구성되며

아래와 같은 3가지 요구조건을 충족해야 한다.

---

1. 상호 배제 ( Mutual exclustion ) -> Mutex

- 하나의 프로세스가 임계영역에서 실행중이라면, 다른 프로세스들은 그 임계영역으로 진입 할 수 없다.

2. 진행 ( Progress )

- 임계영역에서 실행중인 프로세스가 끝났을때 ( 없을 때 ) 임계영역으로 진입하려 하는 프로세스가 있다면,  임계 영역으로 진입하려는 프로세스 중 하나는 유한한 시간 내에 진입할 수 있어야 한다.

3. 한정된 대기 ( Bounded waiting )

- 어떤 프로세스가 임계 영역에 대한 진입을 요청한 뒤엔 다른 프로세스의 임계 영역 진입이 유한한 횟수로 제한돼야한다. 즉, 임계 영역에 대한 진입 요청후 무한히 기다리지 않는다는 것이다.

---

3. 피터슨의 해결안

현대 컴퓨터 구조에서는 올바르게 실행된다고 보장되지는 않지만, 임계 영역 문제를 해결하기 위한 좋은 알고리즘적 설명이다.

2개의 프로세스 ( Pi, Pj ) 가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

int turn;

boolean flag[2];

변수 turn은 임계영역으로 진입할 순번을 나타내며

flag 배열은 프로세스가 임계 영역으로 진입할 준비가 됐다는 것을 나타낸다.

임계영역으로 진입하기 위해선 Pi는 flag[i]를 TRUE로 만들고 turn 변수를 j로 지정한다.

이렇게 함으로써 Pj가 임계영역으로 진입하길 원한다면 진입 가능하다는 것을 보장하고

3가지 요구조건을 충족시킨다는것을 알 수 있다.

4. 동기화 하드웨어

피터슨 해결안이 올바르게 동작한다는 것을 보장하지 않으므로, 임의의 해결책 lock 도구가 있는데 이는 Mutex라고도 한다.

임계영역을 가진 쓰레드들의 러닝타임이 겹치지 않도록 , 단독으로 실행되게 하는 기술로

임계영역에 진입하기 전 Lock을 획득하고 임계영역을 나오면서 Lock을 방출하는 기법이다.

많은 현대 기계들은 특별한 하드웨어 명령어들을 제공하는데. 그 중에는 TestAndSet()과 Swap()이 있다.

1) TestAndSet() 명령어의 정의

- 변수 rv에 인자로 받은 target의 참,거짓 값을 삽입하고 true 로 바꾼다.

2) TestAndSet()을 사용한 Mutex Implementation

- lock을 TestAndSet에 넣고 그것이 참인동안은 임계영역에서 수행을 하고 수행을 마치면 키를 반환해주어야 하므로 lock 값을 False로 바꿔준다.

3) TestAndSet() 을 사용한 한정 대기조건 만족하는 Mutex

- 전역변수 waiting 과 key 배열이 있고 , n개의 프로세스가 있다고 하면

i번째 프로세스의 두 배열값을 TRUE로 바꿔줌으로써 임계영역에 들어갈 준비를 한다.

5. 세마포

4번째에서 설명한 동기화 하드웨어 기법은 복잡하므로 "세마포" 라는 도구를 사용한다.

세마포는 간단히 말해서 신호등 같은 역할이라고 생각하면 되는데, 예를들면 한 쓰레드가 임계영역에 접근할때 그 쓰레드는 세마포의 카운트를 감소시키고 수행이 종료되면 세마포의 카운트를 원래대로 증가시킨다.

현재 실행중인 쓰레드가 있으면 빨간불의 역할을 하여 다른 쓰레드의 진입을 막는것이다.

세마포는 wait() 와 signal() 두개로 접근이 가능한데,

6. 동기화 문제들

1) 유한버퍼 문제

2) Readers - Writers 문제

3) 식사하는 철학자 문제