운영체제 (5) - Concurrency: Mutual Exclusion and Synchronization
2024년 1학기 운영체제 수업을 듣고 정리한 내용입니다. 수업 교재는 운영체제 - 내부구조 및 설계원리 8 판입니다.
Example
현대 운영체제의 중요한 특징은 여러 프로세스가 동시에 실행된다는 것이다. 메모리 속 여러 프로그램을 동시에 실행하면 같은 메모리 영역에 두 개 이상의 프로세스가 동시에 접근하는 경우가 생긴다.
Process 1 Process 2
read x;
... read x;
... x=x+200;
x=x+100; ...
write x; ...
... write x;
각 프로세스는 x를 읽은 다음 Process 1은 x에 100을, Process 2는 x에 200을 더한 다음 다시 x에 쓰기 작업을 했다. 그런데 x가 0일 때 결과값은 300이 아니라 200이다. 같은 메모리 영역에 동시에 접근을 함으로 문제가 발생하게 되었다. 이것이 동시성 문제의 간단한 예시이다. 이렇게 동시성 문제가 발생하는 코드 블럭들을 Critical Section으로 부른다.
Race Condition
위 상태를 Race Condition(경합 상태 또는 경쟁 상태)라고 한다. 여러개의 프로세스 또는 스레드가 동시에 읽기/쓰기 작업을 할 때 예측 불가능한 결과를 내는 것을 말한다. 운영체제는 항상 신뢰할 수 있어야 하므로 이런 경합 상태가 없는 코드를 제공해야한다.
Software Approach
경합 상태를 해결할 수 있는 방법 중 유저 레벨에서 가능한 방법을 살펴보자. 간단하게 두 개의 프로세스에서 경합 상태가 발생한다고 가정하자.
Solution 1
turn
은 두 프로세스 사이에 공유된 변수다. turn
은 항상 0 또는 1의 값만 갖기 때문에, 두 프로세스가 while을 돌더라도 한 프로세스는 항상 while을 탈출해 critical section에 진입한다. 한 프로세스가 ciritical section을 빠져 나왔다면, turn
값을 변경하여 다른 프로세스에게 차례를 넘긴다.
문제는 성능이 좋지 않다는 것이다. 만약 P0이 작업을 처리하는데 걸리는 시간이 0.001초이고 P1은 1초라고 가정하자. P0이 매우 짧은 시간에 작업을 처리하였지만 P1에게 차례가 넘어갔으므로 P1이 처리를 끝낼 때까지 기다리게 되므로 실제로는 P0도 1초마다 1번씩 실행되는 셈이다. 이런 문제를 Busy Waiting이라고 부른다. 상대방이 처리를 끝낼 때까지 무한히 기다리는 문제다.
그리고 한 프로세스가 종료되었다면, 다른 프로세스는 while에 갖혀 끝나지 않는 문제도 있다.
Solution 2
flag
변수 역시 두 프로세스 사이에 공유된 변수다. critical section으로 진입하고 싶다는 의사를 나타내는 변수로 사용되고 있다. 의사를 표현함으로 상대가 critical section를 실행하고 있지 않다면 내가 진입할 수 있게 되어 무조건 번갈아 진입하는 문제를 해결했다.
먼저 while(flag[])
을 통해 상대가 critical section으로 진입하고자 하는지 확인한다. 상대가 그럴 마음이 없다면, 내 flag
값을 true로 설정하여 critical section으로 진입할 것이라고 알린다. 처리가 끝났다면 다시 flag
값을 false로 만들어 빠져나왔음을 알린다.
하지만 한 쪽이 while을 탈출한 후 flag
값을 true로 설정하기 전에 Timeout이 걸린다면, 아직 flag
값이 false인 상태이므로 다른 프로세스가 critical section에 진입할 수 있다. 무조건 번갈아 실행하는 문제는 해결했지만, critical section에 두 프로세스 모두 진입하는 문제가 생겼다.
Solution 3
while을 탈출하고 나서 flag
값을 바꿀 때 Timeout이 발생하면 두 프로세스 모두 critical section에 진입할 수 있으므로, while문 이전에 flag
값을 변경하여 먼저 의사를 표현하도록 변경했다.
이 방법은 critical section에 한 프로세스만 진입이 가능하므로 Mutual Exclusion(상호 배제)이 성립한다. critical section에 진입했다는 것은 다른 프로세스가 진입 의사를 갖지 않는다는 것을 확인했다는 말이 된다. 그러니까 내가 critical section에 진입하려할 때 상대의 의사를 확인해야 한다. 즉 이미 누가 critical section에 진입했다면 나는 상대의 의사를 확인할 때 기다려야 함을 알게 되는 것이다.
하지만 한 쪽이 flag
값을 true로 변경하고 Timeout이 된다면 다른 프로세스가 자신의 flag
값을 true로 설정한 뒤 while에 갇히게 되므로 모두 critical section으로 진입하지 못하는 문제가 생긴다. 이런 상황을 Deadlock이라고 부른다. 서로 critical section에 진입하려고 의사를 표현하고 상대가 순서를 양보할 때까지 기다리는 것이다.
솔루션 1과 2는 쓸 수 없는 코드이지만 3번 코드는 Timeout이 잘못 걸리는 데드락 문제만 없다면 사용이 가능하다.
Solution 4
솔루션 3처럼 내 의사를 표현하고 상대방의 의사를 확인하기 때문에 상호 배제는 성립한다. 대신 달라진 것은 내 의사를 표현한 후 상대가 critical section으로 진입하려고 할 때 일정 시간동안 양보를 해보는 것이다.
양보를 함으로써 데드락에 빠졌을 경우 언젠가는 데드락이 해제될 것이라 예상할 수 있다. 그러나 매 명령어 실행 후에 Timeout이 걸린다고 가정하면 서로 양보하기만 하는 문제인 Livelock이 발생한다.
- Process 0이
flag[0]
을 true로 설정한다. - Process 1이
flag[1]
을 true로 설정한다. - Process 0이
while(flag[1])
를 확인하고 while 내부로 들어간다. - Process 1이
while(flag[0])
를 확인하고 while 내부로 들어간다. - Process 0이
flag[0]
을 false로 설정한다. - Process 1이
flag[1]
을 false로 설정한다. - 일정 시간이 지나고, Process 0이
flag[0]
을 true로 설정한다. - 일정 시간이 지나고, Process 1이
flag[1]
을 true로 설정한다. - Process 0이
while(flag[1])
를 확인하고 while 내부로 들어간다. - Process 1이
while(flag[0])
를 확인하고 while 내부로 들어간다.
...
서로 상대방이 critical section에 진입하기를 기다리기 때문에, 서로 critical section에 진입을 못하는 상황이 발생한다. 프로세스마다 딜레이를 다르게 준다고 하더라도, 실제로 프로세스가 실행되는 것은 스케쥴러에 의해 결정되기 때문에 완벽한 해결은 되지 못한다.
솔루션 4는 데드락을 피하고 라이브락 또한 발생 가능성이 낮지만, 완전한 해결책은 되지 못하는 문제를 갖는다.
Dekker's Algorithm
Dekker의 알고리즘은 동시성 문제에 대한 소프트웨어적 해결책이다.
flag
와 turn
이 공유변수로 사용되었다. 그러나 위의 솔루션들에서 turn
의 의미와는 다른데, 상대가 진입 의사를 가질 때 의미를 갖는 변수다.
빨간 형광펜으로 칠한 부분은 솔루션 4와 동일한 코드이다. 먼저 내 의사를 표현하고 상대방의 의사를 확인한 다음, while 내부로 진입한다. while 내부에는 turn
변수가 등장하는데, 상대가 진입 의사를 가질 때 의미를 갖는다.
- P0과 P1 모두 진입 의사를 가지는 상황에서 P0이 while 내부로 진입하게 된다.
- P0은
turn
이 1이면 상대에게 양보를 해야한다.flag[0]
을 false로 설정하고turn==1
이 아닐 때까지 기다린다.turn==1
의 의미는 이렇다. P0의 코드 밑부분에 critical section을 빠져나오고 turn을 1으로 설정하는 코드가 등장한다. 즉,turn
을 확인하는 것은 내가 critical section을 탈출했기 때문에 상대에게 양보를 해야하는가를 의미한다. turn==1
이면, 양보를 해야하므로flag[0]
을 true로 설정하고while(turn==1)
을 실행하여 P1이turn
을 0으로 바꿀 때까지 기다린다. 이 때의turn
은 상대가 critical section을 탈출했는지를 의미한다.- P1 또한
flag[1]
을 true로 설정하고 while의 조건을 검사한다. 앞서 P0이 양보했기 때문에 정상적으로 critical section에 진입한다. critical section을 탈출하면서turn
을 0으로 설정하게 되고, P0은 상대가 critical section을 탈출했는지 알게 되었으므로 while를 탈출한 후 자신의 의사를 표현한다. - 만약 P1이 의사를 표현했다고 하더라도,
turn
값이 0이기 때문에 P1은 상대에게 양보를 해야한다. 그러므로 P1은 자신의flag[1]
을 false로 설정하게 되고, P0이 바깔 while을 탈출하면서 critical section에 진입하게 된다.
무조건 critical section에 번갈아 진입하지 않는다. 만약 한 프로세스라도 flag
값이 false라면 다른 프로세스는 while 내부를 실행하지 않고 곧바로 critical section에 진입하게 된다.
먼저 자신이 의사를 표현하고 상대의 의사를 확인하기 때문에 솔루션 4처럼 상호 배제는 여전히 성립한다.
turn
변수에 의해 데드락은 발생하지 않는다. 어느 한쪽에게만 무조건 양보를 하도록 만들기 때문에 라이브락도 발생하지 않는다.
Q. P0이 critical section에, P1은 기다리는 상황에서 P0이 다시 critical section으로 들어갈 수 있나?
P1이
while(flag[0])
에서 기다린다면turn
이 1임을 의미한다. 즉, P0이 양보를 해야함이 강제되어 재진입이 불가능하다.P1이
while(turn==0)
에서 기다린다면 P1이 양보를 하는 상황이지만 P0이 critical section을 탈출하면서turn
을 1로 설정한다. 그 순간 P1은 다시 양보를 그만두고 의사 표현을 하게 된다. 결국 P0은while(turn==1)
에서 기다리게 되고 재진입이 불가능하다.
Q. while(turn==0)이 실행되다가 while(flag[0])이 실행되는 경우가 있을까?
P1이
while(turn==0)
에서 기다리고 있다고 가정하자. P0이 critical section을 탈출하면서turn
을 1로 설정한다. 이 때 P1은 안쪽 while을 탈출하게 되나 P0이flag[0]=false
를 실행하기 전에 Timeout된다면while(flag[0])
에서 기다리게 된다.P1이 다시 Timeout되어 P0이 실행된다면
turn
이 1이기 때문에 P0의flag[0]
가 false로 바뀌고, P1은 critical section에 진입한다.
Q. while(flag[0])이 실행되다가 while(turn==0)이 실행되는 경우가 있을까?
P1이
while(flag[0])
을 실행하고 있다는 것은,turn
이 1임을 의미한다.turn
이 1에서 0으로 바뀐다면 while(turn==0)이 실행되지만, 그런 상황은 P1이 critical section을 탈출할 때 발생한다. 즉 바깔 while에서 안쪽 while로 가는 경우는 없다.
Peterson's Algorithm
Dekker의 알고리즘은 while이 두 개나 쓰여서 꽤 복잡하지만 Peterson의 알고리즘은 간소화되어 있다. Dekker 알고리즘에서는 ritical section을 탈출하고 나서 차례를 넘겼지만 Peterson 알고리즘은 critical section 진입 전에 차례를 넘긴다.
while(flag[1] && turn==1)
의 코드는 상대가 의사를 가지면서 critical section을 탈출하기 전까지 기다린다는 의미다. turn
이 0 또는 1이기 때문에 두 프로세스중 하나는 while을 탈출하게 되고 critical section에 진입한다. critical section을 탈출하는 프로세스는 자신의 flag
를 false로 설정한다. flag
값이 바뀌었으므로 기다리던 프로세스는 critical section에 진입하게 된다.
- P0은 기다리고, P1이 critical section 안에 있는 상황이라면?
상대flag
는 true,turn
은 1이다. 상대가 critical section을 탈출한다면 상대flag
가 false로 바뀌어 P0이 critical sectino에 진입한다. - 서로가 critical section으로 진입 의사를 가지는 상황이라면?
둘 다flag
가 true여도,turn
때문에 어느 한 프로세스는 무조건 critical section에 진입하게 된다.
만약 서로flag
를 true를 만든 상태에서 내가 먼저turn
을 수정하여 양보한다면, 상대가 나중에turn
을 수정하여 양보하게 되므로 먼저 양보하는 프로세스가 먼저 critical section에 진입하게 된다.
상호 배제임을 증명
P0이 critical section에 진입했는데 P1이 critical section에 진입하여 상호 배제가 깨진다고 가정한다.
P0이 critical section에 진입한다고 가정한 후 P1이 flag[0]=true
와 turn=1
사이에서 critical section에 진입한다고 생각해볼 때, flag
값과 turn
값에 의해 두 프로세스가 모두 critical section에 들어가지 못함을 알 수 있다.
Peterson 알고리즘은 상호 배제를 지키면서 flag
변수에 의해 교대로 진입하지 않게 되었고 데드락도 일어나지 않는다. 또한 라이브락 가능성도 없는데, 일단 기다리기 시작하면 아무것도 하지 않기 때문이다.
하지만 다른 프로세스가 critical section을 나올 때까지 기다리는 상황이 분명히 존재하기 때문에 Busy Waiting 상황이 발생한다. 또한 위의 소프트웨어적 해결책들은 전부 두 프로세스에서만 적용 가능하다는 한계점이 존재한다.
Q. Dekker/Peterson 알고리즘은 Starvation이 발생하나?
Starvation은 다른 프로세스가 계속 critical section에 진입하게 되어 자신이 진입할 수 있는 기회를 못 얻는 상황을 말한다.
Dekker/Peterson 알고리즘에선, critical section에서 탈출한 프로세스가 다시 critical section으로 진입하는 경우는 언젠가 발생한다. 하지만 다른 프로세스가 while안에서 기다리고 있다면 무조건 차례를 바꾸게 되므로 Starvation이 발생하지 않는다.
Requirements for Mutual Exclusion
상호 배제는 다음과 같은 전제 조건을 갖는다.
- 한 번에 한 프로세스만 critical section에 진입해야 한다.
- 내가 critical section 코드를 실행하지 않아도 다른 프로세스의 실행에 영향을 주어선 안된다.
- Deadlock이나 Starvation이 없어야 한다.
- critical section에 진입할 수 있는데, 다른 이유에 의해 즉시 진입하지 못하는 경우는 없어야 한다.
- CPU의 속도 및 개수에 관계없어야 한다.
- 일단 critical section에 진입을 했다면, 탈출할 것으로 가정한다.
Hardware Instruction
소프트웨어적 접근은 두 개의 프로세스에서만 적용 가능하고, 복잡하다는 문제가 있다. 하드웨어적 접근은 다수의 프로세스에 적용할 수 있다. 그러나 여전히 Busy Waiting 문제를 해결하지 못하고, Starvation이 발생할 수 있다.
Compare & Swap Instruction
compare_and_swap
명령어는 원자성을 갖는 명령어다. 다시 말해, 한 번에 한 프로세스만 실행가능한 명령어다. 다른 프로세스가 명령어를 실행중이라면 동시에 실행할 수 없다. 명령어의 동작을 코드로 표현하면 이렇다.
int compare_and_swap(int *word, int testval, int newval) {
int oldval;
oldval = *word;
if (oldval==testval) *word = newval;
return oldval;
}
*word
는 메모리 공간의 주소, testval
은 비교 대상, newval
은 교환할 값이다. 포인터의 값과 testval
의 값이 같으면 메모리와 newval
을 교환하고 메모리의 값을 반환하는 명령어다. 이 명령어를 사용하여 critical section을 구현한다면 아래의 코드처럼 된다.
const int n = /* number of processes */;
int bolt;
void P(int i) {
while (true) {
while(compare_and_swap(*bolt, 0, 1) /* do nothing */ ;
/* critical section */
bolt = 0;
/* remainder */
}
}
void main() {
bolt = 0;
parbegin(P(1), P(2), ... );
}
main함수는 그냥 여러 프로세스를 동시에 실행시키는 코드이다. bolt
변수가 등장하는데, 이 변수는 공유변수로 critical section에 누가 들어갔음을 의미한다. 각 프로세스는 실행중에 compare_and_swap
함수로 bolt
가 0이라면 1을 넣어 내가 critical section에 진입했음을 알린다. critical section에서 나왔다면 bolt
값을 다시 0으로 바꾸어 다른 프로세스에게 내가 critical section을 탈출했음을 알린다.
bolt
가 0이라면 compare_and_swap
이 bolt
에 1을 저장한 후 0을 반환할 것이고, 1이라면 compare_and_swap
이 1을 반환할 것이다. 그러므로 한 프로세스가 bolt
를 1로 바꾸고 critical section에 진입한다면 다른 프로세스들은 모두 기다리기만 하는 Busy Waiting 문제가 발생한다.
while에서 기다리기만 한다면 Timeout이 걸려서 Starvation이 발생할 가능성도 있다. 그러나 코드가 매우 간단한 장점을 갖는다.
Exchange Instruction
exchange
명령어도 compare_and_swap
처럼 원자성을 갖는 명령어다. 익히 사용하던 swap함수와 똑같이 동작한다.
void exchange(int *register, int *memory) {
int temp;
temp = *memory;
*memory = *register;
*register = temp;
}
const int n = /* number of processes */;
int bolt;
void P(int i) {
while (true) {
int keyi = 1;
do exchange (&keyi, &bolt)
while (keyi != 0);
/* critical section */
bolt = 0;
/* remainder */
}
}
void main() {
bolt = 0;
parbegin(P(1), P(2), ... );
}
로컬 변수인 keyi
가 등장한다. 모든 프로세스는 keyi
가 1인 상태로 시작한다. bolt
값과 교체하는 명령어가 원자성을 가지므로 한 프로세스가 bolt
값 0과 1을 교환해갔다면 다른 프로세스는 1과 1을 교환하게 된다. 그러므로 한 프로세스만 do-while을 탈출하고 critical section으로 진입하게 된다.
여전히 do-while안에서 무한히 대기할 수 있는 가능성이 있으므로 Starvation이 발생할 수 있다.
Pros and cons
소프트웨어적 접근법과 다르게 다수의 프로세스에서도 적용이 가능하다.
코드가 간단해서 많은 수의 critical section을 쉽게 만들 수 있다.
Busy Waiting 문제는 똑같이 발생한다.
Starvation 문제도 똑같이 발생한다.
Deadlock이 발생할 수 있다. 코드 자체는 문제가 없지만 여러 critical section을 구현하다가 발생할 수 있다.
Semaphore
세마포어는 정수 하나와 큐가 함께 연결된 일종의 구조체 변수이다. 운영체제가 제공하는 도구이고, Starvation과 Busy Waiting 문제를 해결한다.
세마포어를 사용하는 명령들은 이렇다.
함수 | 설명 |
---|---|
initialize |
세마포어의 초기 정수값을 정한다. 이 때 0 또는 양수값만 설정가능하다. |
semWait |
세마포어의 값을 -1만큼 바꾼다. 만약 값이 음수라면 호출한 프로세스가 세마포어의 큐에 삽입된다. |
semSignal |
세마포어의 값을 1만큼 바꾼다. 만약 값이 0 또는 음수라면 큐에서 프로세스를 하나 꺼내고 Ready 큐에 넣는다. |
간단한 코드로 표현하면 이렇다.
struct semaphore {
int count;
queueType queue;
};
void semWait(semaphore s) {
s.count--;
if (s.count < 0) {
/* 현재 프로세스를 s.queue에 삽입 */
/* 현재 프로세스를 block시킴 */
}
}
void semSignal(semaphore s) {
s.count++;
if (s.count <= 0) {
/* 큐에서 프로세스를 꺼내 Ready 큐에 넣는다. */
}
}
세마포어를 사용하여 critical section을 구현한다면 critical section의 시작부분에는 semWait
를, 종료부분에는 semSignal
을 호출한다. 이렇게 할 때, 세마포어의 값이 음수가 아니라면 critical section에 진입하게 되고, critical section을 탈출할 때 세마포어 큐에서 대기중인 프로세스를 실행될 수 있도록 만든다.
Example
A,B,C,D 프로세스가 실행 중에 semWait(s)
를 호출한다고 가정하고 시뮬레이션해보자. A가 실행중에 semWait(s)
를 호출한다. s.count
가 1에서 0으로 바뀌지만 음수가 아니므로 A는 critical section에 진입하게 된다. 이후 timeout되어 다시 Ready 큐로 들어간다.
다음으로 B가 실행되는데, semWait(s)
를 호출하고 s.count
를 0에서 -1로 바꾼다. 값이 음수이기 때문에, critical section으로 진입하지 못하고 s.queue에 삽입된 후 blocked 상태가 된다.
다음으로 C가 실행되는데, C 역시 semWait(s)
를 호출하고 s.count
를 -1에서 -2로 만들고 s.queue에 삽입된 후 blocked 상태가 된다. D 또한 동일하게 s.queue로 들어가면 아래의 사진처럼 바뀐다.
다시 A가 실행되는데, A가 critical section을 탈출하면서 semSignal(s)
를 호출하게 된다. A는 critical section을 탈출하면서 s.count
값을 -3에서 -2로 만드는데 값이 0이하의 음수이기때문에 s.queue에서 대기중인 프로세스를 다시 Ready 큐에 넣게 된다.
B는 critical section에 진입할 수 있게 되었다. 이번에는 실행중에 critical section을 탈출한다고 가정하면 s.count
를 -2에서 -1로 바꾸고 C는 Ready 큐에 들어가게 된다.
이번에는 A가 다시 critical section에 진입한다고 가정하자. s.count
값을 -1에서 -2로 바꾸게 되는데 음수이므로, 이번엔 A가 s.queue에 삽입되고 Blocked 상태가 된다.
이런식으로 프로세스가 critical section에 진입할 때 s.count값에 따라 Blocked되거나 진입에 성공한다.
Binary semaphore
이진 세마포어는 정수값이 아니라 boolean값을 갖는 세마포어다.
struct binary_semaphore {
enum { zero, one } value;
queueType queue;
}
void semWaitB(binary_semaphore s) {
if (s.value == one)
s.value = zero;
else {
/* 현재 프로세스를 s.queue에 삽입 */
/* 현재 프로세스를 block시킴 */
}
}
void semSignalB(binary_semaphore s) {
if(is_queue_empty(s.queue))
s.value = one;
else {
/* 큐에서 프로세스를 꺼내 Ready 큐에 넣는다. */
}
}
정수값이 0 또는 1이기 때문에, 한 번에 한 프로세스만 critical section에 진입하도록 강제한 세마포어다.
Producer and Consumer problem
Producer는 버퍼에 값을 넣기만 하는 프로세스다. Consumer는 버퍼에서 값을 꺼내가기만 하는 프로세스다. 한 번에 한 프로세스만 버퍼에 접근 가능하다. 문제는 버퍼가 꽉 찼다면 Producer는 추가를 하지 못하고, 버퍼가 비었다면 Consumer는 삭제를 하지 못한다. 하지만 버퍼의 상태는 어떻게 알아야 할까?
Bounded Buffer
원형 큐 자료구조를 사용해서 버퍼를 구현한다. 원형 큐 구조는 이렇다.
in
과 out
이 각각 인덱스로 사용된다.
// Producer
while(true) {
/* produce item v */
while((in + 1) % n == out)
/* 버퍼에 자리가 생길 때까지 기다림 */;
b[in] = v;
in = (in + 1) % n;
}
// Consumer
while(true) {
while(in == out)
/* 버퍼에 아이템이 있을 때까지 기다림 */;
w = b[out];
out = (out + 1) % n;
/* consume item w */
}
Producer는 버퍼에 자리가 없으면 while에서 기다리고, 한 자리라도 있으면 while을 탈출하여 버퍼에 값을 넣는다. Consumer는 버퍼에 아이템이 없다면 while에서 기다리다가 하나라도 생길 경우 while을 탈출하여 버퍼에서 값을 꺼내간다. 이 방법은 두 프로세스 모두 while에서 기다리는 것 때문에 Busy Waiting 문제가 생긴다.
Semaphore Solution for Bounded Buffer
세마포어를 사용해서 Busy Waiting문제를 해결할 수 있다.
const int sizeOfBuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofBuffer;
void producer() {
while(true) {
produce();
semWait(e);
semWait(s); //
append(); // critical section
semSignal(s); //
semSignal(n);
}
}
void consumer() {
while(true) {
semWait(n);
semWait(s); //
take(); // critical section
semSignal(s); //
semSignal(e);
consume();
}
}
void main() {
parbegin(producer, consumer());
}
append()
는 데이터를 버퍼에 넣는 것이고, take()
는 버퍼에서 데이터를 꺼내오는 함수다. 두 함수를 호출하는 코드가 모두 세마포어 s
로 둘러 쌓여있다. 즉 버퍼에 접근하는 코드부분은 critical section이다.
critical section에 접근하기 위해 무한정 기다리는 Busy Waiting문제를 해결하기 위해서, 세마포어 n
과 e
가 사용되었다.
semaphore e
e
는 버퍼에 자리가 있는지 확인하기 위해 사용하는 세마포어다.e
가 갖는 정수값은 버퍼의 빈 자리 수를 의미한다. 또한e
의 큐는 버퍼가 꽉 찼을 때 기다릴 producer의 대기열 역할을 한다.semaphore n
반대로n
은 버퍼가 비었는지 확인하기 위해 사용하는 세마포어다.n
이 갖는 정수값은 버퍼 속 데이터의 수를,n
의 큐는 버퍼가 비었을 때 기다릴 consumer의 대기열 역할을 한다.
먼저 초기 상태에서는 버퍼에 아무것도 없기 때문에 n.count
는 0으로, e.count
는 버퍼의 크기값을 갖는다.
producer
producer는 semWait(e)
를 호출하는데 초기 상태에는 e.count
값이 음수가 아니기 때문에 Blocked되지 않고 semWait(s)
를 호출하게 되고 critical section에 접근해서 데이터를 삽입한 후 빠져나오게 된다. critical section을 빠져나오면 semSignal(n)
을 호출하여 n의 queue에서 기다리는 consumer들에게 버퍼에 데이터가 삽입되었음을 알린다. producer가 반복해서 데이터를 버퍼에 넣게되면 어느 순간엔 e.count
가 -1이 되는 순간이 온다. 그래서 semWait(e)
를 호출하는 순간 Blocked되어 e의 큐에서 대기하게 된다. e.count
가 -1이라는 것은 버퍼가 꽉 차서 더 이상 데이터를 넣을 수 없다는 것을 의미한다.
consumer
consumer는 semWait(n)
을 호출하는데 초기 상태에는 n.count
값이 음수이므로(0이었다가 호출하는 순간 -1이 되므로) Blocked되어 n의 큐에서 대기하게 된다. producer가 critical section에 진입하여 데이터를 버퍼에 넣고 탈출한 후 semSignal(n)
을 호출하게 되는데, 앞서 consumer가 n의 큐에서 대기하고 있었으므로 n의 큐에서 빠져나와 실행 가능한 상태로 변한다. 결과적으로 consumer는 critical section에 접근해서 producer가 삽입해놓은 데이터를 꺼내게 된다.
꺼낸 후에 critical section을 탈출하면서 semSignal(e)
를 호출한다. consumer가 데이터를 꺼내기 전에 버퍼가 꽉찬 상태였다면, producer는 semWait(e)
에서 Blocked되고 e의 큐에서 버퍼에 한 자리라도 빌 때까지 기다리고 있었을 것이다. consumer가 데이터를 꺼냈으므로 이 시점부터 버퍼에 한 자리가 비게 된다. 그래서 semSignal(e)
를 호출하여 기다리고 있던 producer에게 버퍼에서 데이터를 꺼내갔음을 알리는 것이다.
호출 순서를 뒤집는다면?
// producer
semWait(s);
semWait(e);
append();
semSignal(s);
semSignal(n);
// consumer
semWait(s);
semWait(n);
take();
semSignal(s);
semSignal(e);
semWait(s)
의 위치를 한 줄 위로 올려버리면 어떻게 될까?
critical section에는 한 프로세스만 진입할 수 있다. 만약 producer가 critical section에 진입하여 데이터를 넣으려 했다가 버퍼가 꽉 차서 Blocked되었다고 가정하자. 이 때 consumer가 critical section에 진입하려고 하니 이미 producer가 critical section에 진입해있는 상태라서 consumer는 s의 큐에서 기다리게 된다. producer는 버퍼가 한 자리라도 비어야지만 semWait(e)
밑의 코드를 실행할 수 있는데, 버퍼에서 데이터를 꺼내가기 위해서는 consumer 코드가 실행되어야 한다. 하지만 consumer는 critical section에 진입하기 위해 기다리는 상태이므로 데이터를 꺼내갈 수 없다. 즉, producer와 consumer 모두 Blocked되어버리는 상황이 발생한다.
반대로 semWait
대신 semSignal
의 호출 순서를 뒤집는다면 어떻게 될까? 결과는 semSignal
의 순서가 바뀌어도 달라지지 않는다.
// producer
semWait(e);
semWait(s);
append();
semSignal(n);
semSignal(s);
// consumer
semWait(n);
semWait(s);
take();
semSignal(e);
semSignal(s);
빈 버퍼에 consumer가 데이터를 꺼내려고 접근했다고 가정하자. consumer는 semWait(n)
에서 Blocked된 상태로 n의 큐에서 기다리고 있다. 이 때 producer가 버퍼에 데이터를 쓴 후 critical section을 탈출하기 직전에 semSignal(n)
를 호출한 후 timeout되었다고 생각해보자.
producer가 semSignal(n)
을 호출했으므로 consumer는 n의 큐에서 빠져나와 실행가능한 상태가 된다. 하지만 아직 producer가 semWait(s)
를 호출하기 전이어서 critical section에 남아있는 상태이므로 consumer는 critical section으로 진입하지 못하고 다시 s의 큐에서 기다리게 된다. 결국 producer가 critical section을 탈출해야만 데이터를 꺼내갈 수 있게 된다.
Monitor
세마포어를 사용하면서 발생하는 문제는 어디에서 Blocked이 걸리는지 코드만 보아서는 명확히 드러나지 않는다는 점이다. 모니터는 세마포어를 사용한 라이브러리로 로컬 데이터, 프로시저, 그리고 초기화 단계로 구성되어 있다.
모니터의 특징은 이렇다.
- 로컬 변수는 모니터 내부에서만 접근이 가능하다.
- 프로세스는 모니터 내부의 프로시저를 호출함으로 모니터 내부로 진입하게 된다.
- 한 번에 한 프로세스만 모니터 내부에 있을 수 있다.
모니터는 세마포어와 달리 정수값이 존재하지 않고 큐만 존재한다. 모니터 내부에서는 cwait
그리고 csignal
함수를 호출하여 프로세스를 대기 큐에 진입시키거나 대기 큐에서 탈출시킨다.
cwait
호출한 프로세스를 condition variable이 true로 바뀔 때까지(조건이 만족될 때까지) 일시중지시킨다. 이 때에는 모니터를 빠져나와 모니터 왼쪽의 대기 영역에서 기다리되, 각 condition variable마다 연결된 큐에서 대기한다.
csignal
cwait
에 중지되었던 프로세스를 재개시킨다. 만약 그러한 프로세스가 아예 없다면, 아무것도 하지 않는다.
모니터에 진입하려는 프로세스는 진입 큐에서 기다린다. 모니터 내부에 프로세스가 없다면 진입할 수 있게 된다.
프로세스가 모니터 내부에서 작업을 진행하다가 csignal
을 호출한다면 모니터를 나간다는 뜻이다. 하지만 csignal
을 호출한 뒤에도 아직 해야할 작업이 남아있다면 csignal
을 호출한 프로세스 그리고 신호를 받은 프로세스 두 개가 모니터 내부에 존재하게 된다. 그런 경우에는 csignal
을 호출한 프로세스가 urgent queue로 이동하게 된다. 신호를 받은 프로세스가 작업을 마치고 나가게 되면 urgent queue에 있는 프로세스가 진입 큐에 있는 프로세스보다 우선권을 갖고 처리된다.
Monitor solution for Bounded Buffer
모니터를 사용한다면 세마포어를 사용했을 때보다 더 간단하게 Bounded Buffer를 구현할 수 있다.
// 모니터 안
monitor boundedBuffer;
char buffer[N];
int nextIn, nextOut;
int count;
cond notFull, notEmpty;
void append(char x) {
if (count == N) cwait(notFull);
buffer[nextIn] = x;
nextIn = (nextIn + 1) * N;
count++;
/* one more item in buffer */
csignal(notEmpty);
}
void take(char x) {
if (count == 0) cwait(notEmpty);
x = buffer[nextOut];
nextOut = (nextOut + 1) * N;
count--;
csignal(notFull);
}
{
nextIn = 0; nextOut = 0; count = 0;
}
// 모니터 밖
void producer() {
char x;
while (true) {
produce(x);
append(x);
}
}
void consumer() {
char x;
while (true) {
take(x);
consume(x);
}
}
void main() {
parbegin(producer, consumer);
}
위 코드는 Producer/Consumer 문제를 모니터로 해결한 코드로, append()
와 take()
는 모니터 속 프로시저이다. nextIn
과 nextOut
은 원형 큐의 인덱스이고, count
는 버퍼에 들어있는 데이터의 수이다.
Producer 프로세스는 append()
함수를 호출함으로 모니터에 진입한다. 만약 버퍼가 꽉 차서 count
가 N
값과 같아진다면 Producer 프로세스는 notFull
에서 대기하게 된다. 그렇지 않다면 곧바로 버퍼에 데이터를 저장하고 count
값을 늘린 후 csignal
을 호출하여 조건 notEmpty
에서 대기중인 프로세스에게 신호를 보내고 모니터를 빠져나온다. 만약 이전에 버퍼가 비어서 notEmpty
의 큐에서 기다리고 있던 프로세스가 있다면 이 신호를 받고 모니터로 진입하게 된다.
Consumer 프로세스는 take()
함수를 호출함으로 모니터에 진입한다. 만약 버퍼가 비어서 count
가 0일 경우 조건 notEmpty
에서 대기하게 된다. Producer가 csignal(notEmpty)
를 호출하고 모니터를 나오게 된다면 그 때 다시 모니터에 진입하게 되고 버퍼에서 데이터를 꺼내가게 된다. 만약 버퍼가 꽉 찬 상태에서 Producer가 notFull
의 큐에서 대기중이라면 Consumer가 보내는 신호인 csignal(notFull)
에 의해 Producer는 모니터에 다시 진입하게 된다.
Q. 세마포어는 순서가 꼬였을 경우 데드락이 발생하는데, 모니터는 그렇지 않은 이유는?
세마포어에서 데드락이 발생했던 이유는 critical section에 진입한 후에 Blocked되었는데 다른 프로세스가 그 상태를 해제시켜주지 못해서였다. 모니터는 프로세스가 실행되는 중간에 wait된다면 condition으로 이동하게 되고 다른 프로세스가 모니터 내부로 진입한다. 즉, 항상 다른 프로세스가 모니터에 진입할 수 있으므로 다른 프로세스를 기다리지 않고 critical section의 코드가 실행될 수 있다.
Readers and Writers Problem
모든 프로세스가 읽는 작업만 하거나 쓰는 작업만 하진 않는다. 대신 읽는 작업만 하는 프로세스가 있을 수 있고, 읽기/쓰기를 모두 하는 프로세스가 있을 수 있다. 읽는 작업만 하는 프로세스를 Reader, 읽기와 쓰기를 하는 프로세스를 Writer라고 하자.
다수의 Reader는 동시에 critical section에 접근해도 상관이 없다. 데이터를 읽기만 하지 쓰지 않으므로 문제가 발생하지 않는다. 그러나 Writer는 다른 프로세스들과 동시에 critical section에 접근할 수 없다. 쓰는 작업을 하는 순간 값이 바뀌기 때문에 동시성 문제가 분명히 발생할 것이기 때문이다.
Solution
Reader끼리는 동시에 접근가능하게, 그러나 Writer는 한 번에 한 프로세스만 접근가능하도록 만들어야 한다.
int readCount;
semaphore x = 1, wsem = 1;
void reader() {
while (true) {
semWait(x);
readCount++;
if (readCount == 1) semWait(wsem);
semSignal(x);
READUNIT();
semWait(x);
readCount--;
if (readCount == 0) semSignal(wsem);
semSignal(x);
}
}
void writer() {
while (true) {
semWait(wsem);
WRITEUNIT();
semSignal(wsem);
}
}
void main() {
readCount = 0;
parbegin(reader, writer);
}
writer코드는 간단하다. wsem
만 사용하여 간단하게 critical section을 만들었다. 그러나 그에 비해 reader코드는 복잡하다.
사진에 나온 순서대로 W1,W2,R1 ... W3 프로세스들이 데이터를 읽고 쓰기 위해 진입하려고 한다고 가정하자. (W는 writer, R은 reader이다)
먼저 W1은 wsem.count
의 초기값이 1이기 때문에 데이터에 접근가능하다. W1이 데이터를 읽는 동안 W2는 대기하게 되고, R1도 reader 코드를 실행한다. x.count
의 초기값이 1이기 때문에 readCount++
를 수행한다. 그 결과로 readCount
가 1이 되었으므로 아랫줄의 조건식을 만족하여 wsem의 큐에서 대기하게 된다. 여기까지 진행되었다면 다음과 같은 모습이 된다.
다음으로 R2부터 R4 프로세스가 실행된다. R2는 semWait(x)
를 호출한다. 앞서 R1이 semWait(x)
를 호출하여 x.count
를 1에서 0으로 바꿨기 때문에 R2는 여기서 중단되고 x의 큐로 가서 대기하게 된다. R3, R4도 마찬가지이다. 여기까지 진행되었다면 다음과 같은 모습이 된다.
W3 또한 semWait(wsem)
에 의해 wsem의 큐로 가서 대기하게 되고, R5역시 semWait(x)
에 의해 x의 큐로 가게 된다. 여기까지 진행되었다면 다음과 같은 모습이 된다.
W1이 데이터를 다 쓰고 critical section을 빠져나오면 semSignal(wsem)
에 의해 W2가 critical section에 들어가게 된다. W2 또한 할 일을 다 하고 critical section을 빠져나오면 다음과 같은 모습이 된다.
Reader인 R1이 critical section에 접근하게 된다. 이 때 R1은 if (readCount == 1) semWait(wsem);
의 다음 줄부터 실행하게 된다. 다음 줄이 semSignal(x)
이므로 x의 큐에서 R2를 다시 실행가능한 상태로 바꾸고 바로 다음 줄의 READUNIT()
함수를 실행한다(데이터를 읽는다). R2는 제일 윗줄의 semWait(x)
의 다음 줄부터 실행하는데, readCount++
를 실행하고 조건문을 평가한다. readCount
가 1에서 2로 바뀌었으므로 조건문을 건너 뛰고 semSignal(x)
를 호출하여 R3를 깨우고 READUNIT()
함수를 실행한다. R3역시 readCount
를 증가시키고 semSignal(x)
를 호출하여 연쇄적으로 R4, R5를 깨우게 된다. 결과적으로 다음과 같은 모습이 된다.
reader들이 동시에 critical section에 접근한 모습이 된다.
어느 reader가 읽는 작업을 다 마쳤다. semWait(x)
를 호출하는데 값이 1에서 0으로 바뀌므로 readCount--
를 호출하게 된다. 이 때에는 readCount
이 4이므로 조건식을 건너 뛰게되고, semSignal(x)
를 호출하여 x의 큐에서 기다리는 프로세스를 깨운다. 모든 reader들이 읽는 작업을 마치고 나면 이렇게 readCount
를 감소시키게 되는데 마지막 reader는 readCount
를 감소하여 0이 되게 만든다. 조건식을 만족하기 때문에 semSignal(wsem)
를 호출하여 wsem에 대기중인 프로세스를 깨운다. 여기서는 W3를 깨우게 된다.
만약 첫 reader가 readCount--
를 호출한 다음에 Timeout에 걸렸다면 다음 reader들은 semWait(x)
때문에 x의 큐에서 대기하게 된다. 그리고 첫 reader가 다시 실행된다면 다시 연쇄적으로 semSignal(x)
를 호출하여 대기하던 reader들을 모두 critical section에서 빠져나가게 한다. 결과는 다음과 같다.
특징
이 솔루션은 writer보다 reader들이 우선순위를 갖는다. 위 시뮬레이션 중반부를 보면 R2,R3,R4,W3,R5순으로 진입하였지만 실행 순서는 R2,R3,R4,R5,W3 순으로 진행되었다. 즉, 대기열에 여러 reader들과 writer들이 섞여있다면, 첫 reader가 critical section에 진입하였을 때 그 뒤에 대기하던 writer들은 진입할 수 없지만, reader들은 진입할 수 있음을 의미한다.
Q. 왜 Reader 우선순위인가?
R1 -> W1 -> R2 -> W2
순으로 진입한다고 가정하자. R1은wsem.count
를 0으로 만들고readCount
를 1로 만든 후 critical section에 들어가게 된다. 다음으로 W1이 critical section에 접근하려고 하지만 R1이 이미 들어가 있기 때문에 wsem의 큐에서 대기한다. 다음으로 R2가 실행되는데, R2는readCount
를 2로 증가시키기 때문에 wsem의 큐에서 기다리지 않고 바로 critical section에 들어간다. 그 다음으로 W2가 실행되지만 역시 wsem의 큐에서 기다리게 된다.진입 순서는
R1 -> W1 -> R2 -> W2
이지만 critical section에 실제로 들어가는 순서는R1 -> R2 -> W1 -> W2
이 된다.