[OS] Process Synchronization

1. Process Synchronization

 

동기화를 기준으로 프로세스들은 다음 두가지 종류로 구분된다.

 

- Independent Process: 한 프로세스의 실행이 다른 프로세스의 실행에 영향을 주지 않는 프로세스

- Cooperative Process: 한 프로세스의 실행이 다른 프로세스의 실행에 영향을 주는 프로세스

 

Cooperative process의 경우 프로세스들이 서로의 작업을 수행할 때 영향을 주기 때문에 하나의 공유 메모리나 다른 프로세스에 접근하는 경우 매우 조심해야 한다. 이러한 프로세스 사이에 동기화를 하는 것을 프로세스 동기화 (Process Synchronization) 이라고 한다. 현재는 대부분 스레드 기준으로 스위칭이 일어나기 때문에 Thread synchronization으로도 많이 불린다.

 

 

2. Ciritical Section (임계영역)

 

임계영역이란 멀티 스레딩 상황에서 서로 다른 프로세스가 동일한 자원에 동시에 접근하는 작업(공유하는 변수 사용, 동일 파일에 접근 하는 등의 작업)을 실행하는 코드 영역을 critical section 이라고 칭한다. 만약 여러 프로세스가 하나의 공유된 자원에 접근하는 경우 어떤 프로세스가 먼저 작업을 수행하는 가에 따라 결과가 달라지는데, 이를 race condition (경쟁조건) 이라고 한다.

 

이러한 임계영역 문제를 해결하기 위해서는 다음 3가지 조건을 만족하는 방식으로 로직을 설계해야 한다.

 

- mutual exclusion (상호배제): 오직 하나의 프로세스만 임계영역에 접근할 수 있도록 한다. 만약 어떤 프로세스가 임계영역에서 실행중이라면 다른 프로세스는 해당 임계영역에서 실행될 수 없다.

 

- progress (진행): 어떠한 프로세스가 임계영역 진입 후보가 되기 위해서는 임계영역에서 실행중인 프로세스가 없고, 아무 작업도 하지 않고 있어야 한다. 이러한 후보들 중에서 다음 임계영역에 접근할 프로세스를 선택하는 과정은 유한한 시간 내에 이루어져야 한다.

 

- bounded waiting (한정된 대기): 프로세스가 임계영역에 접근을 요청하고 요청이 허용되기 까지의 대기시간은 유한하게 제한되어 있어서 해당 시간 안에 임계구역으로 접근할 수 있어야 한다.

 

 

3. Lock

 

하드웨어 기반 해결책으로 동시에 공유 자원에 접근하는 것을 막기 위해 임계영역에 진입하는 프로세스가 lock을 획득하고 임계영역을 빠져나올 때 lock을 방출함으로써 동시에 접근을 할 수 없도록 한다.

 

 

4. Semaphores (세마포)

 

세마포는 프로세스의 동시성 문제를 해결하기 위한 정수 값으로 스레드 들이 공유하는 양수 값의 변수이다. 이 변수는 임계영역 문제를 해결하여 프로세스 동기화를 달성하기 위해 멀치 프로세스 환경에서 사용된다.

 

- binary semaphore: mutex lock 이라고도 불린다. 0과 1 두가지 값만 가질 수 있다. 다중 프로세스에서 임계영역 문제를 해결하기 위해

사용된다.

 

※ Mutex

뮤텍스는 멀티스레드, 멀티프로세스 환경에서 공유 자원에 대한 접속을 제어하기 위해 사용된다. 하나의 스레드만 뮤텍스 객체를 소유할 수 있으므로 공유 자원에 대한 접근이 있는 critical section 앞에 mutex에 대한 요청을 추가한다면 오직 한 스레드만 해당 섹션에서 작동할 수 있다.

 

- counting semaphore: 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용하며, 세마포는 그 가용한 자원의 개수로 초기화된다. 자원을 사용하면 세마포가 감소, 방출하면 증가한다. 다중 인스턴스를 가지고 있는 자원에 대한 접근을 다룰 때 사용된다.

 

세마포는 내부적으로 프로세스가 대기하는 큐를 포함하는 구조로 구현되어 있다. acquire 시에 세마포의 값을 감소기키고 값이 0보다 작은 경우 큐에 집어넣어 대기시킨다. release 되는 경우 세마포의 값을 증가시키고 세마포의 값이 0보다 같거나 작은 경우 큐에서 대기하고 있는 프로세스가 있다는 의미 이기 때문에 큐에서 프로세스 하나를 꺼내어 임계구역을 수행할 수 있도록 해준다.

 

일반적으로 세마포를 사용하여 mutual exclusion 문제를 해결한다. 이외에도 release() 와 acquire() 를 호출하여 실행 순서도 조정할 수 있다.

 

 

5. 동기화 예제

 

- producer - consumer problem

 

생산자 - 소비자 문제는 생산자가 생산한 데이터를 버퍼에 저장하고 이를 소비자가 사용할 때 발생하는 문제이다. 버퍼의 크기는 유한하기 때문에 버퍼와 저장하고 있는 데이터의 카운트를 확인하여서 접근해야 한다. 이때 생산자와 소비자가 임계구역인 버퍼와 카운트에 동시에 접근하는 경우 문제가 발생하여 잘못된 값을 가지게 되거나 무한루프에 빠지게 될 수 있다.

 

이때 세마포를 사용하여 임계구역에 하나의 프로세스만 접근을 허용하여 문제를 해결할 수 있다. 하지만 이 방법 또한 문제가 있다. 생산과 소비를 하기에 앞서 버퍼가 가득 찼는지, 비어있는지를 확인하는 무한 반복문을 매번 실행해야 한다. 특별한 작업을 수행하지 않으면서 무한으로 반복하여 CPU를 점유하게 되는데, 이러한 문제를 busy waiting이라고 한다. 이러한 문제는 세마포를 추가하여 해결할 수 있다. 한 세마포는 버퍼의 비어있는 공간을, 다른 하나는 버퍼에 차 있는 공간의 개수를 카운트하도록 하여 각각 생성자와 소비자의 접근을 제어하도록 하면 반복적인 확인없이 세마포를 통한 접근 조건 확인으로 busy waiting을 해결할 수 있다.

 

- readers - writers problem

 

readers - writers 문제는 공통 데이터베이스를에 접근하는 경우에 발생하는 문제이다. 하나의 데이터베이스에 여러 프로세스가 접근하는데, 이를 임계구역으로 설정하는 경우 매우 비효율적이 된다.

 

이러한 문제를 해결하기 위해 프로세스를 readers와 writers로 나누는데, readers는 데이터를 수정하지 않고 읽기만 하는 프로세스로 writers는 데이터를 읽고 수정도 하는 프로세스들로 나눈다. 이때 readers는 동시에 접근하는 것을 허용하고 writers는 mutual exclusion을 보장해야 한다.

 

- dining philosopher problem

 

5인의 철학자 문제는 5명의 철학자가 5개의 젓가락을 가지고 식사를 할 때 음식을 먹는 경우 젓가락을 들고 그렇지 않고있는 동안에는 젓가락을 내려놓는 방식으로 식사를 한다. 이때 음식을 먹기 위해서는 젓가락이 2개 필요하기 때문에 철학자는 양쪽의 젓가락이 모두 사용중이지 않는 경우에만 음식을 먹을 수 있다. 즉 젓가락은 mutual exclusion 하게 동작해야한다.

 

세마포를 사용하여 mutual exclusion 하게 젓가락을 사용하도록 하는 경우 문제가 해결될 수 있다고 생각할 수 있지만, 이렇게 하는 경우에도 문제가 발생한다. 만약 모든 철학자가 같은 방향의 젓가락을 집어들게 되면 각자가 하나씩만의 젓가락을 가지게 되어 아무도 음식을 먹을 수 없는 상황이 된다. 이와 같이 공유된 자원에 대해서 모두가 자신의 작업을 수행하기 위해 자원을 요청한 상태에서 대기하는 상황을 deadlock, 교착상황이라고 한다.

 

Deadlock이 발생하기 위한 필요조건은 다음 네가지가 존재한다.

 

• mutual exclusion: 한 번에 한 스레드만 공유 자원을 사용할 수 있다.
• hold and wait: 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가 해당 권한을 양보하지 않은 상태에서 또 다른 자원에 대한 권한을 요구한다.
• no preemption: 한 스레드가 다른 스레드의 자원을 강제로 뺏어갈 수 없다.
• circular wait: 해당 자원의 접근 관계에 순환이 존재한다.

교착상태를 해결하기 위해서는 위의 4가지 조건 중 하나 이상을 만족시키지 않도록 해야한다.

 

• mutual exclusion: 자원을 공유가능하도록 하는 것은 실제적으로 불가능하다.
• hold and wait: 동시에 작업 수행에 필요한 모든 자원을 요청하도록 한다. 만약 요청한 자원을 동시에 가질 수 없는 경우 현재 가지고 있는 자원을 모두 내려놓고 다시 요청을 한다. 자원 활용률 저하 및 starvation이 발생할 수 있다.
• no preemptive: preemptive 하게 변경하면 해결할 수 있지만 현실적으로 불가능 한 경우가 많다.
• circular wait: 모든 자원에 번호를 부여하여 이 번호에 대한 오름차순으로만 자원을 요청하도록 한다. 자원의 활용률을 저하시키는 문제가 있다.

 

 

6. Monitor

 

세마포보다 고수준의 동기화 기능을 제공하는 도구이다. 공유 자원과 공유 자원 접근함수로 이루어져있고, 2개의 큐 (mutual exclusion queue, conditional synchronization queue)를 가지고 있다.

 

mutual exclusion queue를 사용하여 한번에 하나의 프로세스만 접근 가능하도록 한다. conditional synchronization queue는 wait()이 호출 되는 순간, 이미 공유 자원을 사용하고 있는 프로세스가 큐에 들어가게 된다. 이후 notify() 호출을 통해서 프로세스가 깨어나게 되는데, 깨어나더라도 이미 공유자원을 사용하고 있는 프로세스가 있는 경우 해당 프로세스가 자원 점유를 해제해야지 실행될 수 있다.