[OS] 프로세스 동기화

* 프로세스 동기화 배경

프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성이 유지되어야 한다.

병행 프로세스는 다중 처리 시스템이나 분산 처리 시스템에서 중요 개념으로 사용

* 임계 구역

한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다

임계구역 안에서는 공유 변수를 변경, 테이블 갱신, 파일 쓰기 등의 작업을 수행한다.

임계구역에는 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납해야 다른 프로세스가 자원 및 데이터를 사용할 수 있다

* 임계구역 문제 해결 방법

1. 상호 배제 기법

특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법

두 개의 프로세스 기준 : 피터슨 알고리즘(두 프로세스가 두 개의 데이터 항목을 공유하여 자원을 사용하는 방법)

여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘(각 프로세스에 번호를 부여하여 자원을 사용하도록 하는 방볍)

2. 진행

자신의 임계구역에서 실행되는 프로세스가 없고 자신의 임계구역으로 진입하려는 프로세스가 있다면, 

잔류 구역에서 실행 중이지 않은 프로세스들만 임계영역에 진입 대상이 되고, 이 선택은 무한정 연기되지 않음!

3. 한계 대기

프로세스가 자기의 임계구역에 진입하려는 요청을 한 후로부터 요청이 허용될 때까지 다른 프로세스들이 임계영역에 그들 자신의 임계구역에 진입을 허용하는 횟수의 한계가 필요

* Mutex Lock

>> Mutex가 지켜주는 덕에 화장실을 한명만 사용할 수 있다.

즉, Mutex는 임계구역을 보호하고 프로세스간 경쟁을 방지하기 위해 사용

boolean available 변수를 사용 => 락의 가용 여부 표시

do {
    //Lock 획득
    임계구역
    //Lock 반환
    나머지 구역
} while(true);

* 세마포어(Semaphore)

Mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화 할 수 있는 방법 제공

각 프로세스에 제어신호를 전달하여 순차적으로 진행하기 위한 동기화 구현

세마포 S = 정수 변수, wait(s)와 signal(s)로만 접근이 가능하다. S = 0인 경우 모든 자원이 사용 중을 의미

//wait(S)
//임계구역에 진입하기 전에 확인
if (S <= 0) //누군가 사용하고 있다면
    S가 양수가 될 때까지 현재 프로세스를 list에서 기다림
else    //임계 구역에 진입이 가능하다면
    S = S - 1;

//Signal(S)
//임계구역을 떠날 때 실행
if (자원 반환전에 list에서 기다리는 프로세스가 있다면)
    그 중 한개 프로세스를 임계 구역 진입
else     //list에서 기다리는 프로세스가 없다면
    S = S + 1;

=> 진행 보장

* 고전적인 동기화 문제

1. 생산자-소비자 문제

생산자가 데이터를 생산하여 입력된 경우에만 접근하도록 구성하는 방식

생산자는 꽉찬 버퍼를 생산하고 소비자는 비어있는 버퍼를 생산한다.

2. 읽기-쓰기 문제

두 Reader가 동시에 공유 데이터를 접근하는 것은 허용하나, 동시에 Writer를 허용하지 않는 방식

Writer보다 Reader 요청이 많은 경우 병행성을 높일 수 있다.

3. 식사하는 철학자 문제

5명의 철학자들은 생각하고 먹는 일을 수행(철학자 : 프로세스, 젓가락 : 자원)

1. 철학자는 양쪽의 젓가락을 사용하여 식사를 하고, 식사를 마친 철학자는 젓가락을 내려놓고 다시 생각한다.
2. 철학자는 2개의 젓가락을 손에 쥐어야 식사를 할 수 있고, 한 번에 하나씩 잡을 수 있다.
3. 옆 사람이 식사중이면 젓가락 잡는 것을 대기한다.

5명의 철학자가 동시에 식사를 하게 되면 모두 왼쪽 포크만을 가지게 되고 오른쪽 포크를 대기하는 교착 상태(Deadlock)이 발생한다.

이를 방자힉 위한 방법은 대표적으로 3가지이다.

1. 최대 4명의 철학자들만이 테이블에 앉을 수 있도록 한다. => 젓가락이 하나 남기 때문에 어떤 철학자는 식사가 가능하다.
2. 한 철학자가 동시에 두개의 젓가락을 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.(즉, 임계구역 안에서만 젓가락을 집어야 한다)
3. 비대칭 해결안을 사용한다.(홀수 번 철학자는 왼쪽, 짝수 번 철학자는 오른쪽 젓가락부터 집는다)