2022. 4. 11. 10:10ㆍMajor`/운영체제
이전에 Critical Section 문제에 대한 해결책으로 "하드웨어적 프로세스 동기화"를 설명했다. 하드웨어 기반 해결책은 매우 복잡하고 응용 프로그래머가 쉽게 사용할 수가 없다.
이러한 문제를 위해 OS에서는 몇가지의 소프트웨어 도구들을 개발했다
- Mutex Lock
- Semaphore
- Monitor
1. Mutex Lock
mutex는 사실 "Mutual Exclusion"의 축약 형태이다.
"Mutual Exclusion"이란 'Critical Section에는 오직 하나의 프로세스만 들어갈 수 있고 Critical Section에 이미 프로세스가 존재한다면 나머지 프로세스들은 Critical Section에 접근할 수 없다'라는 Critical Section 해결 조건 중 하나이다
Mutex Lock은 Critical Section을 보호하고 프로세스 간 경쟁을 방지하기 위해서 사용한다
1. 프로세스가 Critical Section에 들어가려면 먼저 "Lock"을 획득해야 한다 : acquire()
2. Critical Section에서 빠져나올 때는 "Lock"을 반환해야 한다 : release()
>> acquire() & release()는 둘 다 "Atomic"하게 동작한다
이러한 방식으로 Mutual Exclusion을 만족하고, Mutex Lock은 "boolean lock"을 통해서 "Lock 가용 여부"를 표시한다
'synchronization variable'
boolean lock = false;
acquire(){
while(lock){
/*
이미 lock이 걸려져 있는 상태라면?
>> "Busy Waiting"
*/
}
lock = true;
}
release(){
lock = false;
}
-----------------------------------------------------------------------
while(true){
acquire lock
"Critical Section"
release lock
"Remainder Section"
}먼저 프로세스 A가 acquire()를 통해서 "Lock"을 획득하였다
그리고 프로세스 B, C, D가 아무리 acquire()를 통해서 "Lock"을 획득하려고 해도 "lock == true"이므로 while 무한루프에 갇히게 된다
프로세스 A가 Critical Section에서 빠져나옴으로써 "Lock"에 대한 release()를 호출하면 "lock == false"가 되면서 다른 프로세스들 중 하나가 Critical Section에 들어갈 수 있게 된다
대기 중인 프로세스들은 while 무한루프에서는 "Busy Waiting"을 통해서 lock을 기다리는데 "Busy Waiting"은 CPU & 메모리를 지속적으로 사용하면서 while 루프의 조건을 확인한다
- "Busy Waiting"의 문제점은 "Multiprogramming System"에서 다른 프로세스가 CPU를 할당받으면 생산적으로 사용할 수 있는 것을 "Busy Waiting"에서 의미없이 CPU 주기를 낭비한다
하지만 대기하는 프로세스 입장에서 계속 CPU & 메모리를 사용하면서 대기하는데 어차피 lock에 대한 조건은 "현재 Critical Section에 들어가있는 프로세스"만이 빠져나오면서 변경해줄 수 있기 때문에 대기하는 프로세스 입장에서는 "절대 만족되지 않는 조건에 대해서 자원을 사용하면서 조건을 check하고 있다"라고 볼 수 있다
"판별"만 한다고 해서 "변경"이 이루어지지는 않는다
이러한 "Busy Waiting"을 "Spin Lock"이라고도 부른다
Spin Lock
다른 thread가 lock을 소유하고 있을 때, 해당 lock이 return될 때까지 계속 조건을 check하면서 대기하는 것
Spin Lock의 개발 컨셉은 "어차피 lock - unlock 사이에 약간의 시간만 기다리면 바로 lock이 풀리는데 굳이 context switch를 해서 overhead를 발생시킬 필요가 있을까"에서 출발했다
이러한 컨셉은 "lock - unlock"과정이 아주 짧을 때 유용하다
- lock을 걸 때 단순히 어떠한 숫자에 + 1을 통해서 lock을 건다고 가정하면
- 굳이 + 1을 걸어서 lock을 해주는데 context switch overhead를 발생시킬 필요는 없다
하지만 Critical Section이 매우 크거나 프로세스의 처리 속도가 느리다면 Spin Lock은 대기하고 있는 프로세스들이 CPU에 주는 부담이 굉장히 커진다
Spin Lock 특성
1. 현재 Lock을 얻을 수 없다면 일단 CPU를 보유한 상태에서 계속 Lock을 확인하면서 기다린다
- while 루프를 CPU를 이용해서 돌면서 최대한 다른 thread에게 CPU를 양보하지 않는다
2. Lock의 주기가 굉장히 짧을 경우 context switch overhead를 줄여서 CPU의 부담을 덜어준다
3. Lock의 주기가 굉장히 길 경우, 오히려 CPU를 오랫동안 점유를 하게되어서 다른 프로세스들의 입장에서는 별로 안좋다
4. 하나의 CPU / Single Core의 경우에는 Spin Lock이 유용하지는 않다
- 보통 Lock을 기다리는 thread는 총 2번의 context switch가 필요하다
- thread를 Waiting 상태로 변환
- lock이 사용가능해지면 Waiting 상태의 thread를 restore
- 일반적으로 2번 context switch하는 시간보다 lock의 주기가 더 짧으면 Spin Lock을 사용한다
2. Semaphore
Semaphore S는 Integer 값이다
Binary Semaphore
S가 0 or 1의 값만 가질 수 있는 Semaphore를 의미한다
Mutex Lock과 거의 유사한 방식으로 Critical Section을 관리한다
1. Resource 기다리기 : wait()
2. Resource 반납 : signal()
>> signal()을 통해서 wait()중인 프로세스에게 Resource를 제공함으로써 프로세스 resume
'Synchronization variable'
Semaphore S = 1
wait(S){
while(S <= 0){
/*
"Busy Waiting"
*/
}
S--;
}
signal(S){
S++;
}
Counting Semaphore
S가 Unlimited한 Integer이다
따라서 Counting Semaphore에서의 S는 "Available한 Resource의 수"라고도 볼 수 있다
유한한 Resource에 대한 접근 제어를 위해 사용할 수 있다
1. Resource 기다리기 : wait()
2. Resource 반납 : signal()
>> signal()을 통해서 wait()중인 프로세스에게 Resource를 제공함으로써 프로세스 resume
'Synchronization variable'
Semaphore S = N // Unsigned Integer
wait(S){
while(S <= 0){
/*
"Busy Waiting"
*/
}
S--;
}
signal(S){
S++;
}
>> 하지만 여기서도 "Busy Waiting"을 통해서 여러 프로세스들이 자원을 기다리고 있다
"Busy Waiting"을 대신해서 "Block & WakeUp"으로 대기하는 프로세스들을 처리할 수 있다
보통 signal()은 wait()에 의해서 block된 프로세스를 깨워주는 역할을 수행
Block & WakeUp Semaphore
어떤 프로세스가 wait()를 통해서 resource를 대기하고 있는데 Semaphore S가 0이하이면 Resource를 얻을 수 없으므로 해당 프로세스는 계속 대기만 해야 한다
이전에 "Busy Waiting" 방식은 대기를 할 때 "루프를 계속 돌면서 조건을 check"하는 방식이였다
하지만 "Block & WakeUp" 방식은 대기를 해야하면 루프를 돌지말고 "일단 Block하고 Semaphore와 관련된 list queue에 들어간다"
이러한 방식은 대기를 하는 프로세스가 CPU를 계속 갖고 있는게 아니라 스케줄러에 의해서 다른 프로세스에게 CPU를 할당해준다
물론 list queue에 들어간 프로세스들을 다시 깨우는 연산이 필요하다. 다시 깨워줄 때는 Resource를 반납할 때 호출하는 signal()을 통해서 깨워준다
wait()
typedef struct{
int value; // Semaphore S 정수값
struct process *list; // Semaphore 대기 큐
} Semaphore
wait(Semaphore *S){
S->value--;
/*
일단 wait()를 호출하는 프로세스는 resource를 요청하고 대기한다
근데 이 때 자원을 가져가려는데 S가 음수가 되었다면 원래 S가 더이상 없다는 의미
그러면 wait()를 호출한 프로세스를 list queue에 집어넣기 : block()
*/
if (S->value < 0){
"add this process to S->list"
block();
}
}일단 프로세스 입장에서는 앞에서 누가 자원을 가져갔고 세마포어 S값이 현재 몇인지 모르니까 일단 wait()를 호출해서 자원을 가져가려고 한다
근데 만약에 자원을 가져가고 S->value를 확인해봤는데 음수라면?? 가져가기 이전부터 남는 resource가 없었다는 의미이다.
따라서 wait()를 호출한 프로세스에게 할당해줄 자원이 존재하지 않기 때문에 해당 프로세스는 대기해야 한다
대기할 때 루프를 도는 것이 아니라 "Block & WakeUp"방식으로 일단 해당 프로세스를 "세마포어 list queue"에 집어넣음으로써 Block시킨다
그리고 자원을 반납하는 프로세스가 있을 경우 signal()을 호출하게 되는데 signal() 내부에서 list queue에 존재하는 프로세스 중 "하나의 프로세스"를 깨워준다
깨워진 프로세스는 waiting queue에서 ready queue로 옮겨간다
signal()
typedef struct{
int value; // Semaphore S 정수값
struct process *list; // Semaphore 대기 큐
} Semaphore
signal(Semaphore *S){
S->value++;
/*
자원을 반납
근데 반납을 했는데도 S->value가 0 이하라면??
>> S->value = 0인 상태에서 어떤 프로세스가 wait()를 호출해서 자원을 획득하려고 했는데 block
*/
if (S->value <= 0){
"remove a process P from S->list"
wakeUp(P);
/*
waiting queue에 존재하는 프로세스 "하나" 깨워주기
*/
}
}현재 semaphore waiting queue 상태 : (rear) P3 -> P4 -> P2 (front)
자원을 반납하려는 프로세스 A
프로세스 A가 Critical Section에서 빠져나와서 Resource를 반납하려고 한다
Resource를 반납하면 당연히 S->value가 1 증가할 것이다
그런데 S->value를 1 증가했는데도 S->value가 0 이하라면??
이전에 어떤 프로세스가 wait()를 통해서 자원을 획득하려고 했는데 "자원이 없어서 Block"을 당한 상태일 것이다
따라서 반납을 했는데 S->value <= 0이라면 세마포어 list queue에 존재하는 여러 block 프로세스들 중에서 하나의 프로세스를 깨워주고 ready queue로 보내줘야 한다
"Busy Waiting" vs "Block & WakeUp"
일반적인 경우에는 Block & WakUp이 더 효율적일 것이다
- 쓸데없이 CPU를 점유하면서 기다리지 않는다
- 먼저 Resoruce 여부를 확인하고 여분이 없으면 알아서 CPU 반납하고 block
- 전체적으로 CPU 처리율이 향상된다
하지만 Block & WakeUp은 overhead이다
Block은 ready -> block 과정이고 WakeUp은 block -> ready 과정이고 이 때 당연히 overhead가 발생한다
1) Critical Section이 매우 짧은 경우
Block & WakeUp의 overhead가 "Busy Waiting"의 CPU 점유보다 훨씬 문제가 된다
2) Critical Section이 긴 경우
"Busy Waiting"은 결국 CPU를 점유하고 CPU를 생산적으로 활용하지 않기 때문에 CPU의 낭비가 심해진다
따라서 Critical Section이 긴 경우 "Block & WakeUp"을 통해서 CPU의 처리율을 향상시키는 것이 더 좋다
Semaphore 문제점
1) Deadlock
Semaphore S, Q는 현재 1로 초기화된 상태
현재 Process A, B가 존재하고 A, B 둘 다 Semaphore S, Q 모두 보유해야 본인의 작업이 가능
| Process A | wait(P) | wait(Q) | ...... | signal(Q) | signal(P) |
| Process B | wait(Q) | wait(P) | ...... | signal(P) | signal(Q) |
A는 P - Q순으로 획득하고 작업을 하다가 Q - P 순으로 반납을 한다
B는 Q - P순으로 획득하고 작업을 하다가 P - Q 순으로 반납을 한다
근데 여기서 문제가 발생한다
현재 A는 P를 얻고 B는 Q를 얻었으면 "A는 Q가 필요하고 B는 P가 필요하다"
>> 이러면 서로 보유하고 있는 자원을 탐내게 된다
"본인의 자원은 계속 가지고 있으려고 하면서 상대방의 자원을 가지고 싶어한다"
이러한 문제가 "Deadlock"이다
2) Starvation
특정 프로세스가 세마포어 list queue에 존재하는데 "자원을 끝까지 얻지 못하고 Indefinite Blocking상태"되는 현상
"Mutex Lock" vs "Semaphore"
Mutex Lock
- 동기화 대상이 오직 1개일 때 사용
- Mutex Lock을 통해서 자원을 획득한 프로세스는 "자원에 대한 소유 & 책임"이 존재
- status가 0/1뿐이라서 Lock을 가질 수 있고, 반드시 Lock을 보유한 프로세스만이 Mutex를 해제할 수 있다
- 프로세스의 범위를 가지고 프로세스가 종료될 때 자동으로 Clean Up
- 공유 자원에 대한 "보호"의 목적으로 주로 사용된다
Semaphore
- 동기화 대상이 1개 이상일 때 사용
- 자원에 대한 소유 & 책임이 존재하지 않는다
- Semaphore를 보유하지 않은 프로세스도 Semaphore를 해제할 수 있다
- 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재한다
- 복수의 공유 자원을 사용함에 있어서 "시그널"로 처리할 때 한다
- "시그널"이란 "내가 지금 사용중"이라는 뜻으로 "보호"와는 거리가 먼 개념이다
Semaphore는 Critical Section을 꽤 잘 해결하는 소프트웨어적 기법이라고 할 수 있는데 Semaphore 또한 문제점이 존재한다
- 코딩하기 힘들다
- Correctness에 대한 입증이 어려움
- 자발적 협력이 필요
- 한번의 코딩 실수로 모든 System에 치명적인 영향
// 정상적인 세마포어 구현
wait(mutex);
...
Critical Section
...
signal(mutex);
오류 1)
// 세마포어 오류
signal(mutex);
...
Critical Section
...
wait(mutex);이렇게 코딩하면 어떠한 문제가 발생할까
일반적으로 Critical Section에 들어가려면 wait()를 통해서 lock(Binary Semaphore : initialized 1)을 걸어야 본인만 들어갈 수 있다
하지만 위의 코드처럼 Critical Section 전에 lock을 풀고 들어간다면?
>> 2개 이상의 프로세스가 타이밍 좋게 동시에 lock을 걸어버리면 2개 이상의 프로세스가 동시에 Critical Section에 접근 가능
"Mutual Exclusion 위반"
오류 2)
// 세마포어 오류
wait(mutex);
...
Critical Section
...
wait(mutex);기본적으로 Critical Section에서 빠져나왔으면 signal()을 통해서 lock을 풀어줘야 다른 프로세스가 Critical Section에 접근할 수 있을 것이다
근데 위의 코드는 Critical Section에서 빠져나와도 lock을 풀어주지 않는다
물론 가장 처음으로 lock건 프로세스는 Critical Section에 들어가기라도 했을 것이다
그러나 다른 프로세스는 영원히 Critical Section에 들어갈 수 없으므로 영구적으로 Blocking이 된다
Semaphore는 프로그래머의 단순한 실수에 의해서 System에 치명적인 영향을 줄 수 있다
이러한 오류를 처리하기 위해서 "동기화 도구들을 통합해서 고급 언어 구조물로 제공"하는 방식인 Monitor가 존재한다
3. Monitor
프로세스 동기화에 대해서 굉장히 편리하고 효율적인 메커니즘을 제공해주는 ADT
- Semaphore나 Mutex Lock보다 더 높은 레벨의 동기화 형태이다
동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장한다
공유 자원/Monitor Lock(Mutex Lock)/1개 이상의 Condition Variables로 구성된다
이 때 공유 자원에 접근하려면 Monitor 내부에 선언된 프로시저(메소드)를 통해서만 접근이 가능하다
monitor <monitor-name>{
<shared variable declarations>
procedure body P1(....){
...
}
procedure body P2(...){
...
}
procedure body P3(...){
...
}
....
initialization code(...){
...
}
}shared variable은 반드시 P1 / P2 / P3 / ....를 통해서만 접근이 가능하도록 설계되어 있다
그리고 Monitor가 원천적으로 내부에 존재하는 여러 프로시저들을 동시에 수행할 수 없도록 통제한다
- 이러면 프로그래머는 공유 데이터에 대한 lock을 따로 걸어줄 필요가 없다
각 프로시저들은 다르게 말하자면 Binary Semaphore를 통해서 반드시 하나의 프로시저만 동작되도록 구현이 되어 있다
Semaphore mutex = 1
"Each Procedure P"
wait(mutex);
....
body of P
...
signal(mutex);프로시저는 한번에 하나만 실행 가능하기 때문에 내부적으로 Binary Semaphore (mutex)를 사용해서 프로시저 P가 시작되면 wait(mutex)를 통해서 lock걸고 끝나면 signal(mutex)를 통해서 lock을 풀어준다
Monitor 내부에서는 "오직 하나의 프로세스"만이 active상태가 된다
- 다른 프로세스들은 Mutual Exclusion을 위반하지 않기 위해서 entry queue에서 대기한다
Monitor Lock
thread가 Monitor 내부의 보호되고 있는 shared data에 접근하려고 하면 먼저 Monitor Lock을 얻어야 한다
- Monitor Lock을 얻으면 "in the monitor"라고 한다
"in the monitor"동안 thread는 모니터 내부에 존재하는 어떠한 데이터에도 자유롭게 접근이 가능하고 수정할 수 있다
그리고 내부에서 일을 다 끝내면 monitor lock을 반납해준다
- wait()를 통해서 block된 프로세스는 일단 "in the monitor"상태에서 block을 당했으므로 monitor에 대한 mutex lock은 이미 보유한 상태에서 block을 당하게 된다
Condition Variables
Monitor 구조 자체만으로는 동기화 수행이 부족하기 때문에 "condition variables"를 정의해서 추가적인 동기화 메커니즘을 제공해줘야 한다
프로그래머가 임의로 정의한 "condition variable"은 오직 wait() / signal()을 통해서만 접근이 가능하다
각각의 condition variable들은 "Waiting Queue"를 가지고 Waiting Queue에는 "조건이 충족되길 기다리는 thread/process들이 blocked(suspend)상태로 머무는 곳"이다
# condition x #
x.wait() : x.wait()를 호출한 프로세스는 x.signal()이 호출되기 전까지 suspend상태가 된다
- 자기 자신을 condition variable의 waiting queue에 넣고 block 상태로 전환
>> 이 때 condition x와 연관된 Queue에서 suspend상태로 대기한다
x.signal() : x.wait()를 호출해서 suspend된 프로세스 중 "하나의 프로세스"를 resume
- waiting queue에서 대기중인 하나의 프로세스를 깨운다
>> 만약 suspended 프로세스가 없다면 x.signal()은 아무런 효과도 없다
Semaphore에서의 signal()연산은 S->value++을 통해서 항상 Semaphore에 영향을 주지만,
Monitor에서의 signal()연산은 suspend된 프로세스가 있냐 없냐에 따라서 영향을 줄 수도 주지 않을 수도 있다
Example)
P1, P2는 S1, S2를 각각 실행시켜야 한다
>> S1은 S2보다 먼저 실행된다
F1: // P1 invoked
S1;
done = true;
x.signal();
F2: // P2 invoked
if (!done)
x.wait();
S2;S1이 S2보다 먼저 실행되려면 어떤 조건을 추가적으로 부여해야 할까
>> P2가 S2를 실행하기전에 어떤 조건을 check해야 한다 :: "boolean done"
done을 처음에 false로 초기화한다면, P2는 done이 false일 때 x.wait()를 호출함으로써 suspend가 된다
그러면 P1이 suspend된 P2를 resume시켜줘야 된다
따라서 P1은 S1을 실행시키고 done을 true로 바꿔주고, x.signal()을 통해서 P2를 resume시킨다
Monitor에는 반드시 하나의 프로세스만이 접근 가능하기 때문에 이미 어느 프로세스가 Monitor에 존재한다면 다른 프로세스들은 "Entry Queue (Mutual Exclusion을 위한 Queue)"에서 기다린다
Monitor 내부에 존재하는 프로세스가 어느 조건을 만족하지 못해서 "wait()"를 호출하면 해당 프로세스는 "Waiting Queue"로 들어가게 된다 (Suspend)
→ 이러면 현재 Monitor에 접근하는 프로세스가 없다. 이 때 어느 하나의 프로세스를 깨워줘야 하는데 1) entry Queue에 있는 프로세스를 들여보내줄까 2) 아니면 "signal & wait scheme"에서 signal() 후 잠시 대기하는 프로세스를 resume해줄까 :: 이러한 고민에 빠지게 된다
Monitor내부에서 새롭게 active된 프로세스가 "signal()"을 호출하면 Waiting Queue에 존재하는 suspend 프로세스들 중 하나의 프로세스를 resume하게 된다
>> 이 때 그냥 resume하게 되면 2개의 프로세스가 동시에 Monitor에 접근하므로 "Mutual Exclusion"을 위배한다
- Signal - Wait : signal()을 호출한 프로세스는 1) resume된 프로세스가 Monitor를 떠날때까지 기다리거나 2) 다른 조건을 기다린다
- Signal - Continue : signal()을 호출한 프로세스는 그냥 계속 진행된다 & resume되려는 프로세스는 1) 현재 프로세스가 Monitor를 떠날때까지 기다리거나 2) 다른 조건을 기다린다
1) Signal & Wait
// Signal & Wait
semaphore mutex; // initially = 1 & Binary Semaphore
semaphore next; // initially = 0 & Binary Semaphore
int next_count = 0;
"Each Procedure P"
wait(mutex);
...
// body of P
...
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
"Each Condition Variable x"
semaphore x_sem; // initially = 0 & Binary Semaphore
int x_count = 0;
void wait(){
x_count++;
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
wait(x_sem);
x_count--;
}
void signal(){
if(x_count > 0){
next_count++;
signal(x_sem);
wait(next);
next_count--;
}
}처음에는 "entry queue에서 여러 프로세스들이 대기하고, condition variable x의 waiting queue에서 여러 프로세스들이 대기하니까 semaphore next & semaphore x_sem은 Counting Semaphore겠지"라고 생각을 했었다
하지만 Semaphore next & Semaphore x_sem은 반드시 Binary Semaphore로 구현해줘야 한다
왜냐하면 wait()의 목적은 "wait()를 call한 프로세스를 block으로 만들겠다"인데 만약 Counting Semaphore로 구현을 하게 된다면 wait()를 call한 프로세스가 block이 아니라 내부의 wait(x_sem)을 통해서 x_sem의 자원을 받아가는 현상이 발생할 수 있다
현재 Monitor 내부에는 "Process A"가 active상태이고 나머지 Process B/C/D는 entry queue에서 대기중인 상태이다
이 때 A가 x.wait()를 호출함에 따라서 block이 된다면
void wait(){
x_count++;
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
wait(x_sem);
x_count--;
}프로세스 A의 입장에서는 wait()를 호출하였고 next_count == 0이므로 signal(mutex)를 통해서 entry queue에서 대기하고 있는 프로세스를 모니터 내부로 active시켜준다
wait(Semaphore *S){
S->value--;
if(S->value < 0){
// add this process to S->list and block()
block();
}
}Semaphore x_sem의 초기값은 0이고 wait(x_sem)을 호출하면 S->value가 음수가 됨에 따라 프로세스 A는 block이 된다
>> 이러한 이유 때문에 Semaphore x_sem은 반드시 Binary Semaphore이여야 한다
void wait(){
x_count++;
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
wait(x_sem); << Process A의 Context
x_count--;
}그리고 wait(x_sem)을 통해서 block이 되었으므로 본인의 context는 wait(x_sem)로 기억이 된다
나중에 signal()에 의해서 waiting queue에서 빠져나와서 "signal & wait"이므로 next Queue로 이동하게 된다
그 후 진행되다가 프로세스 B가 x.signal()을 호출하게 된다면
void signal(){
if(x_count > 0){
next_count++;
signal(x_sem);
wait(next);
next_count--;
}
}x_count > 0이고 "signal & wait"로 구현이 되었으므로 Semaphore next & wait(next)를 통해서 프로세스 B는 현재 x waiting queue에 존재하는 프로세스 A가 모니터를 떠나거나 다른 조건에 의해서 block이 될때까지 Next Queue에서 잠시 대기한다
- 이 때 깨어난 프로세스 A는 Mutual Exclusive하게 수행되는 함수 내에서 깨어나기 때문에 이미 mutex에 대한 lock은 보유하고 있는 상태이다
void signal(){
if(x_count > 0){
next_count++;
signal(x_sem);
wait(next); << Process B의 context
next_count--;
}
}나중에 프로세스 B가 다시 resume된다면 next Queue에서 빠져나오므로 Process B의 context 다음인 next_count--를 통해서 next_count를 감소시켜준다
Semaphore Mutex & Entry Queue : Mutual Exclusion을 만족하기 위한 Binary Semaphore & Queue
Semaphore next & Next Queue : "signal & wait"에서 signal()를 호출하고 resume되는 프로세스를 위해서 잠시 대기하는 프로세스를 위한 Binary Semaphore & Queue
Semaphore x_sem & Waiting Queue : wait()에 의해서 block되는 프로세스를 위한 세마포어 변수 & Queue
2) Signal & Continue
임시로 생각해낸 코드이고 틀린 부분이 있을 수 있음
// Signal & Continue
semaphore mutex;
semaphore next;
int next_count = 0;
"Each Procedure P"
wait(mutex);
...
// body of P
...
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
"Each Condition Variable x"
semaphore x_sem; // initially = 0 & Binary Semaphore
int x_count = 0;
void wait(){
x_count++;
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
wait(x_sem);
x_count--;
wait(next);
next_count--;
}
void signal(){
/*
x_sem Queue에 존재하는 프로세스를 "일단 현재 프로세스 계속 진행시키기 위해서"
>> next Queue로 잠시 보내기
*/
if(x_count > 0){
signal(x_sem);
}
if("현재 프로세스가 종료됨"){
signal(next);
}
}
3) Signal & Leave
1), 2)의 절충안으로 signal()을 호출한 프로세스는 즉시 모니터를 떠나는 구조이다
임시로 생각해낸 코드이고 틀린 부분이 있을 수 있음
// Signal & Leave
semaphore mutex;
semaphore next;
int next_count = 0;
"Each Procedure P"
wait(mutex);
...
// body of P
...
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
"Each Condition Variable x"
semaphore x_sem; // initially = 0 & Binary Semaphore
int x_count = 0;
void wait(){
x_count++;
if(next_count > 0){
signal(next);
}
else{
signal(mutex);
}
wait(x_sem);
x_count--;
}
void signal(){
if(x_count > 0){
signal(s_xem);
}
Terminate(this);
}
Monitor 내에서 프로세스 Resume
wait()를 통해서 Waiting Queue에서 suspend된 프로세스는 signal()을 통해서 다시 Resume될 수 있다
여기서 suspend 프로세스 중 어느 프로세스를 다시 Resume시키고 그 기준을 무엇일까?
가장 간단한 방법은 당연히 "FCFS"일 것이다
하지만 suspend 프로세스가 굉장히 많을 경우 FCFS는 효율적이지 못할 수 있다
이를 위해서 "conditional-wait construct"를 사용할 수 있다
x.wait(c)어떤 프로세스가 wait()를 호출할 때 "c : Priority Number"을 같이 파라미터로 넘겨주는 것이다
>> 이렇게 P-N을 넘겨주면 다음에 signal()이 호출되면 "가장 작은 c를 가진 프로세스"가 resume된다
"ResourceAllocator" Monitor
R.acquire(t);
...
"access the resource"
...
R.release();이 모니터는 1개의 자원을 여러 프로세스 사이에 할당해준다.
각 프로세스는 자원을 할당받기를 원하면 R.acquire(t)를 호출한다. 이 때 "t"는 해당 자원을 사용할 최대 시간이다
>> 모니터는 "t"가 가장 작은 프로세스에게 자원을 먼저 할당해준다
monitor ResourceAllocator{
boolean busy;
condition x;
void acquire(int time){
if(busy){
x.wait(time);
}
busy = true;
}
void release(){
busy = false;
x.signal();
}
initialization_code(){
busy = false;
}
}"Process A"
ResourceAllocator A_RA;
int main(void){
...
A_RA.acquire(100);
...
A_RA.release();
}
"Process B"
Resource Allocator B_RA;
int main(void){
...
B_RA.acquire(50);
...
B_RA.release();
}모니터는 당연히 time이 더 작은 Process B에게 먼저 자원을 할당해줄 것이다
Liveness
위에 설명했던 Mutex Lock / Semaphore / Monitor는 Critical Section의 "Mutual Exclusion"문제를 해결하는 방법이다
하지만 Mutual Exclusion은 해결할 수 있지만 Critical Section의 나머지 해결 조건인 Progress / Bounded Waiting은 해결되지 않을 수 있다
"Liveness"란 어느 프로세스가 실행 life cycle동안 반드시 Progress됨을 보장하기 위해서 시스템 상에서 충족해야 하는 속성을 말한다
"Liveness refers to a set of properties that a system must satisfy to ensure processes make progress."
1) Deadlock
2개 이상의 프로세스들이 "오직 대기중인 프로세스만이 발생할 수 있는 이벤트"를 무한정 기다리는 상태
- 여기서 "이벤트"란 Mutex Lock / Semaphore같이 Resource의 acquire과 release이다
P(0)가 wait(S)를 호출하고, P(1)이 wait(Q)를 호출한다고 하자
P(0)는 wait(Q)를 호출해야 하는데 이는 P(1)이 signal(Q)를 호출해야 가능한 상황이다
P(1)은 wait(S)를 호출해야 하는데 이는 P(0)가 signal(P)를 호출해야 가능한 상황이다
>> 이러면 P(0)와 P(1)은 Deadlock이 된다
2) Starvation
특정 프로세스가 세마포어 list queue에 존재하는데 "자원을 끝까지 얻지 못하고 Indefinite Blocking상태"되는 현상
3) Priority Inversion (우선순위 역전)
"높은 우선순위 프로세스"가 현재 kernel data를 읽거나 변경을 해야한다
근데 지금 "낮은 우선순위 프로세스"가 kernel에 접근해서 kernel data를 읽고 변경하고 있다
kernel에 접근하는 것은 lock에 의해 보호가 되기 때문에 "낮은 우선순위 프로세스"가 먼저 lock을 획득해서 kernel에 접근하고 있으면 아무리 높은 우선순위 프로세스가 존재하더라도 기다려야 한다
- 간단히 말하면 우선순위가 가장 높은 프로세스가 가장 늦게 완료되는 상황이다
- Critical Section / Shared Data에 대한 접근을 제어하다가 발생할 수 있는 문제이다
task1, task3는 Binary Semaphore에 의해서 접근이 제한되는 작업을 수행한다
task2는 semaphore와 관련이 없는 작업이다
1. 먼저 task3가 공유 자원의 접근을 위해서 Binary Semaphore를 획득하고 접근을 한다
2. 이 때 우선순위가 더 높은 task1이 접근을 시도했으나 Binary Semaphore에 의해서 block이 되었다
3. 계속 task3가 수행되다가 semaphore와 관련이 없고 task3보다 우선순위가 높은 task2가 도착
>> task2는 Binary Semaphore lock과 상관이 없기 때문에 즉시 "context switch"하고 task2 수행
4. task2 수행이 완료되고 다시 lock을 보유하고 있는 task3 수행
5. task3 수행이 완료되고 드디어 Binary Semaphore를 획득한 task1 수행
결국 우선순위가 가장 높은 task1은 Binary Semaphore라는 접근 제한 때문에 가장 늦게 수행이 되었다 :: Priority Inversion
Priority Inversion문제는 보통 3개 이상의 우선순위 프로세스를 보유한 시스템에서만 발생한다
이러한 문제는 어떻게 해결할까?? Priority-Inheritance Protocol
Priority-Inheritance Protocol
"낮은 우선순위 프로세스"가 현재 "높은 우선순위 프로세스가 요구하는 자원"을 보유하고 있을 경우 → 임시로 "낮은 우선순위 프로세스"를 "자원을 요구하는 프로세스의 우선순위로 높여주는 기법"
여기서 보게되면 현재 Binary Semaphore는 task3가 보유하고 있다
그런데 task1도 Binary Semaphore를 요구하고 있다
>> task3의 우선순위를 임시로 task1의 우선순위와 동일하게 만들어주기
이러한 방식으로 Priority-Inheritance를 해주면 중간에 task2가 오더라도 선점당하지 않을 수 있다
- 이 때 주의해야하는게 task1이 task3의 자원을 빼앗는게 아니다
- task3가 Binary Semaphore 자원을 얻고 있는 상태면 task1은 일단 Block이 된다
- 그리고 task3가 Binary Semaphore를 release해야 그 때 task1이 Binary Semaphore를 획득할 수 있다
