I. Synchronization Problem
Synchronization Problem이란 두개 이상의 프로세스 혹은 두개 이상의 스레드가 공유자원에 접근하는 경우 발생할 수 있다. 이렇게 여러 작업 주체가 공유자원에 접근하거나, 실행 순서의 시간적인 보장이 필요한 경우 Synchronization(동기화)가 필요하다. 예를 들어 동기화 문제가 발생하는 코드 영역인 Critical Section을 A라는 프로세스가 수행하다가 Context Switching이 발생하여 B라는 프로세스가 Critical Section을 수행하게 된다면 공유자원의 오염이 발생할 수 있게 된다.
II. Bounded Buffer Problem (Producer Consumer Problem)
버퍼가 꽉 차지 않았다면 버퍼에 데이터를 넣는 Producer와 버퍼가 비어 있지 않으면 데이터를 넣는 Consumer가 번갈아 가면서 실행 되는 상황에서 발생할 수 있는 문제가 Bounded Buffer Problem이다. 이 상황에서는 가장 중요한 공유자원(Shared Resource)인 count가 보호가 되지 않는 Race Condition이 존재하기 때문에 Synchronization Problem이 발생한다. 또한 CPU가 돌아가면서 바쁘게 쉬게 되는 Busy Waiting이 발생할 수 있기 때문에 하드웨어 자원의 낭비가 커지는 문제가 존재한다.
III. Synchronization Problem을 해결하기 위한 조건
A. Mutual Exclusion(상호 배제)
Synchronization Problem이 발생할 수 있는 코드 영역인 Critical Section을 한 번에 한 프로세스만 접근할 수 있게하는 조건을 의미한다.
B. Progress
현재 Critical Section에 접근하는 다른 프로세스 혹은 스레드가 없고, Critical Section에 지금 접근 해야 하는 프로세스가 하나만 존재한다면 그 프로세스가 Critical Section에 무조건 먼저 진입하는 조건을 의미한다.
C. Bounded Waiting
다른 프로세스 혹은 스레드가 Critical Section에 접근하여 작업을 수행 중이라면 일단 기다리지만, 언젠가는 본인의 수행 차례가 올 것이라는 조건을 의미한다.
IV. Synchronization Tools
Synchronization Tool이란 Synchronization Problem을 해결 하기 위한 기법을 의미한다. Synchronization Tools의 예시는 다음과 같다.
A. Lock
특정 프로세스 혹은 스레드가 Critical Section에 진입 할 때 Lock을 걸어서 다른 프로세스 혹은 스레드가 접근하지 못하게 하고 Critical Section에서의 작업이 다 끝난 경우 Unlock을 하는 운영체제 레벨의 Primitive한 기법이다. 하지만 이 기법을 이용하더라도 Lock과 Unlock을 구분하는 구조체 내의 변수인 held(Shared Data)가 보호되지 않으며(이로 인해 Mutual Exclusion 조건이 만족되지 않는다), CPU가 동작하면서 바쁘게 쉬는 Busy Waiting이 발생하여 효율성이 떨어진다는 단점이 존재한다.
B. Hardware Atomic Instructions (Test-and-Set, Compare-and-Swap)
CPU가 딱 하나의 Atomic한 Instruction을 수행하는 중이라면 Interrupt가 걸리지 않는다. Instruction과 Instruction 사이에서 Interrupt가 걸릴 수 있기 때문에 이러한 특성을 이용하여 Lock과 Unlock 동작을 하나의 Instruction으로 만들면 Interrupt가 걸리지 않게 할 수 있다. 하지만 이러한 기법을 이용하기 위해서는 CPU 제조사의 지원이 필요하기 때문에 Hardware Dependency가 높다는 특징을 가진다. 또한 이러한 기법을 이용 한다 해도 Busy Waiting이 발생한다는 단점을 그대로 가지게 된다.
C. Disable/Enable Interrupt
특정 프로세스 혹은 스레드가 Critical Section에 진입할 때 cli() 시스템 콜을 통해 Interrupt 기능을 중지하면 Context Switching이 발생하지 않아 Spin Lock을 구현하지 않아도 Mutual Exclusion 조건을 만족시킬 수 있다. Critical Section에 대한 작업이 끝나면 sti() 시스템 콜을 통해 interrupt 기능을 다시 enable 시킬 수 있다. 하지만 유저 프로세스가 interrupt 기능을 마음대로 중단 시켰다가 재개할 수 있게 된다면 프로세스 간의 Fairness가 보장되지 않기 때문에 OS만 이러한 기능을 사용할 수 있게 해야 한다. 또한 Critical Section의 길이가 길 경우 Timer나 I/O Event를 놓칠 수 있다는 단점이 존재한다.
D. Semaphore (High Level Synchronization Tool)
Semaphore란 Shared Resource에 접근할 수 있게 하는 티켓의 수(정수형 변수)를 의미 한다고 생각하면 된다.
Wait과 Signal이라는 Operation을 사용할 수 있는데, 특정 프로세스 혹은 스레드가 Shared Resource에 접근하기
위해 Wait Operation을 수행하면 Semaphore의 값이 1 감소하게 되고, 작업이 끝나 Signal Operation을 수행하게
된다면 Semaphore의 값이 1증가하게 된다. Semaphore값이 0이 된다면 다른 프로세스나 스레드는 Wait
Operation을 실행하더라도 Shared Resource에 접근하지 못하고 대기 하게 되며 다른 프로세스 혹은 스레드의
Signal Operation을 통해 Semaphore값이 증가하여야 접근할 수 있다. 또한 0 혹은 1의 값만 가질 수 있는
Semaphore를 Binary Semaphore라고 하며, 티켓이 2장 이상인 Semaphore는 Counting Semaphore라고 한다.
이에 더불어 Semaphore는 Busy Waiting이 없다는 장점이 존재하지만 사용하기 어렵고 버그가 많다는 단점이 존재 한다.
또한 Semaphore는 두 프로세스간 작업 수행의 시간적인 동기화를 맞출 때도 이용될 수 있고 예시는 아래와 같다.
만약 A라는 작업이 Process1에서 끝나야 Process2가 작업 B를 수행할 수 있게 하기 위해서는 우선 Binary
Semaphore를 0으로 초기화 해 둔 다음 Process2에서 B라는 작업을 수행하기전에 Wait Operation을 수행하게 한
다. Binary Semaphore가 0이기 때문에 Process2가 B라는 작업을 수행하지 못하고 대기를 하게 되고 시간이 지나
Process1에서 A라는 작업을 끝내고 Signal Operation을 수행한다면 Binary Semaphore의 값이 1이 되기 때문에
Process2는 대기상태에서 벗어나 티켓을 1 감소시키고 B라는 작업을 수행할 수 있게 된다.
Critical Section을 보호하는 동기화를 위한 Semaphore 활용 코드 예시는 다음과 같다.
위 코드에서 Binary Semaphore를 이용하였기 때문에 한 번에 한 프로세스 혹은 스레드만이 계좌의 잔액을 얻어
오고, 변경하고, 저장하는 Critical Section에 접근 가능하다. wait operation을 통해 1로 초기화된 mutex 변수가 0
이 되고 다른 프로세스 혹은 스레드가 withdraw 함수를 호출하면 wait operation을 수행하는 라인에서 대기를 하
게 된다. 이후 Critical Section에 대한 작업을 마친 프로세스가 signal operation을 수행하면 다시 mutex 변수가 1
로 증가하고 대기중인 다른 프로세스 혹은 스레드 1개가 Critical Section에 진입할 수 있게 된다. (Mutual
Exclusion을 만족하게 된다)
E. Monitor (High Level Synchronization Tool)
라이브러리 단에서 제공하는 Monitor는 Shared Variable에 대한 Procedure들중 하나를 특정 프로세스 혹은 스레
드가 이용중일 때 다른 프로세스 혹은 스레드는 Shared Variable에 대한 Procedure를 수행하지 못하게 하는
Synchronization Tool이다.
동기화를 위한 Monitor 활용 코드 예시는 다음과 같다.
위코드에서 예를 들어 process1이 먼저 shared resource에 접근하고 다룰 수 있는 Procedure p1, p2, p3 중 하나
를 수행한다고 했을 때 다른 프로세스들은 shared resource에 접근하고 다룰 수 있는 Procedure p1, p2, p3중 아
무 하나도 수행을 하지 못하고 대기해야 한다. (Mutal Exclusion을 만족하게 된다)
F. Condition Variable
Monitor를 이용할 때 특정 프로세스가 특정 Procedure를 실행 중이고 특정 이벤트를 길게 기다리는 상황이라면
다른 프로세스는 오랜 시간 기다려야 한다는 단점이 존재한다. 이로 인해 Condition Variable이 등장하게 되었고
History가 존재하는 Semaphore와 달리 Condition Variable은 History가 없다는 특징을 가진다. 즉 아무 프로세스
혹은 스레드가 대기중인 상황이 아닐 때 Signal()이 수행되게 된다면 Semaphore는 티켓이 1 증가하게 되지만
Condition Variable의 경우 티켓이 증가하지 않는다.
