Semaphore (세마포)
세마포는 네덜란드 수학자 Dijkstra가 만든 동기화를 위한 도구로, Semaphore S는 정수형 변수로 취급됩니다.
단, S는 wait 연산과 signal 연산으로만 접근이 가능합니다. 여기서 wait 연산과 signal 연산은 단위 연산이므로, 원자성이 보장됩니다.
EX)
wait(S) {
while(S <= 0);
S--;
}
signal(S) { S++ };
세마포는 위 두 연산으로 접근가능하지만, 초기값의 경우는 wait, signal 없이 세팅이 가능합니다.
EX) Semaphore S = 1;
S의 값은 임계 구역에 들어갈 수 있는 프로세스의 수를 나타냅니다.
즉 Semaphore S = x 라면, 임계 구역에 x개의 프로세스가 접근가능합니다.
세마포를 사용하는 예로 Bounded Buffer Problem과 Readers - Writers Problem이 있습니다.
먼저 Bounded Buffer Problem(유한 버퍼 문제) 입니다.
While(count == N);
buffer[in] = next_produced;
in = (in + 1) % N;
count++;
(Producer)
While(count == 0);
next_consumed = buffer[out];
out = (out + 1) % N;
count--;
(Consumer)
Producer와 Consumer는 count를 공유 변수로 사용합니다. 하지만, 공유변수인 count를 Producer에서는 count++; Consumer에서는 count--; 를 실행하는데, 이는 어셈블리로 치환 시 원자성 보장이 되지않으므로 동기화 문제가 해결 되지 않습니다. 따라서 이를 해결하기 위해 Count Based Circular Queue 대신 일반적인 Circular Queue 사용으로 해결합니다. 하지만, 이 경우 Empty와 Full의 구별을 위해 N개의 공간 중 N - 1개 까지만 사용가능하다는 단점이 있습니다. 그래서 세마포를 사용하여 문제를 해결합니다.
EX)
Semaphore mutex = 1, full = 0, empty = n; // mutex = 임계 구역 내 프로세스 수, full = 사용중인 버퍼, empty = 비어있는 버퍼
wait(empty);
wait(mutex);
buffer[in] = next_produced;
in = (in + 1) % N;
signal(mutex);
signal(full);
(Producer)
wait(full);
wait(mutex);
next_consumed = buffer[out];
out = (out + 1) % N;
signal(mutex);
signal(empty);
(Consumer)
wait 연산과 signal 연산은 atomic operation이므로, 동기화 문제가 해결됩니다.
다음으로 Readers - Writers Problem 입니다. 해당 문제에서는 공유 데이터가 있을 때, 여러 프로세스가 Read/Write를 시도하게 되면, Read는 여러 프로세스가 사용해도 문제가 되지 않지만, Write의 경우 Read하는 프로세스 혹은 Write 하는 프로세스가 있을 때 대기하게 됩니다. Read 또한 앞서서 Write하는 프로세스가 있을 경우 대기하게 됩니다. 따라서 동기화 문제가 발생하는데 이를 해결하기 위해 세마포를 사용하는 전략 중 다음 두가지를 선택합니다.
- Reader Preference Algorithm (Read를 우선으로 실행)
- Writer Preference Algorithm (Read가 대기)
EX)
Semaphore rw_mutex = 1, mutex = 1, int read_count = 0;
wait(rw_mutex);
Write
signal(rw_mutex);
(Writer Process)
wait(mutex);
read_count++;
if(read_count == 1) wait(rw_mutex);
signal(mutex);
Read
wait(mutex);
read_count--;
if(read_count == 0) signal(rw_mutex);
signal(mutex);
(Reader Process)
Writer Process에서 Semaphore 연산을 통해 쓰기 작업을 하고, Reader Process에서는 공유 변수인 read_count의 동기화 문제 해결을 위해 Semaphore 연산을 통해 접근하게끔 작성되어 있습니다. mutex의 값이 1로 초기화 되어있기 때문에 Mutual Exclusion 조건이 만족하여 문제가 발생하지 않습니다.