경쟁상태(Race condition) 3
세마포어
다익스트라가 제안한 방식으로 busy waiting의 문제를 해결할 수 있으며 앞서 언급했던 세가지 조건(상호 배제, 진행, 제한된 대기)를 모두 만족하는 방법이다.
뿐만아니라 다수의 스레드의 경우에도 사용할 수 있는 방법이다. 때문에 멀티 스레드를 구현할 때 API로써 언어에 제공이 많이 되는 편이다.
세마포어에 대해서 알기 위해선 먼저 함수 두개를 알아야한다. 이 두 함수는 하드웨어적으로 원자적 실행이 보장된 함수이다. 각각 함수마다 busy wait이 있는 버전이 있고, 없는 버전이 있다. 왜 이런 버전이 있는지에 대한 이유는 추가로 설명하겠다.
busy wait
wait 함수
1
2
3
4
void wait(S) {
while S <= 0;
S --;
}
signal 함수
1
2
3
void signal(S) {
S ++;
}
Non-busy wait
Non-busy wait에서 쓰이는 함수의 경우 구조체를 받아서 작업하며 구조체의 형태는 다음과 같다.
1
2
3
4
typedef struct{
int value;
struct process * list; // 스레드의 주소를 담고 있는 리스트
} Semaphore;
또한 block과 wakeup이라는 함수도 나오는데 두 함수가 호출되면 context switching이 일어난다. 각각 함수의 역할은 다음과 같다.
block
스레드를 대기 큐에 넣음 (Sleep)
wakeup
스레드를 대기 큐에서 빼서 준비 큐에 넣음 (실행)
wait 함수
1
2
3
4
5
6
7
void wait(S) {
S -> value--;
if (S -> value < 0) {
//add this process to waiting queue
block();
}
}
signal 함수
1
2
3
4
5
6
7
void signal(S) {
S -> value++;
if (S -> value <= 0) {
//remove a process P from the waiting queue
wakeup(P);
}
}
사용 예시
busy wait vs Non-busy wait
Non-busy wait 형태의 함수의 경우 context switching이 일어난다. 그러면 필연적으로 오버헤드가 발생하게 된다.
만약 Critical Section의 실행 시간이 context switching의 오버헤드 보다 짧다면 busy wait 형태로 구현하는게 오히려 성능상 이득이다. 반대로 만약 Critical Section의 실행 시간이 context switching의 오버헤드 보다 길다면 Non-busy wait 형태로 구현하는게 성능상 이득이다.
동기화 vs 상호 배제
세마포어의 S값, Non-busy wait버전에서는 S->value값이 어떤 값으로 초기화 되느냐에 따라 사용 방법이 달라질 수 있다.
0으로 초기화
동기화 툴로써 사용 될 수 있다. 다음의 예시를 보자
1
2
3
//thread 0
// do something
signal(synch)
1
2
3
//thread 1
wait(synch)
// do something
위와 같은 경우 thread 0이 먼저 작동되고 thread 1이 작동되는게 보장된다. 이런식으로 0으로 초기화 할 경우 동기화 툴로써 사용 될 수 있다.
1로 초기화
한 개의 임계 영역에 대해서 제어할 수 있다.
1
2
3
4
wait (mutex);
Critical Section
signal (mutex);
Remainder Section
어떤 스레드가 임계 영역에 들어가게되면 다른 스레드 한 개는 임계영역 안으로 들어갈 수 없다. 이를 Binary Semaphore 혹은 Mutex라고 부른다.
2이상으로 초기화
여러 개의 스레드에 한정된 자원을 분배해야할 때 사용할 수 있다. 사용 가능한 자원만큼 임계 영역에 접근 가능하다. 이를 Counting Semaphore라고 한다.
단점
교착 상태 발생 위험성
value가 1로 초기화 되었고 Thread 0과 Thread 1가 다음과 같은 상황이라 가정해보자
Thread 0은 S를 Thread 1은 Q를 실행하고 있다. Thread 0은 그 다음에 Q를 Thread 1은 그 다음에 S를 실행해야하는데 서로 Q와 S를 잡고 있어서 무한한 대기 상태, 즉 교착 상태에 빠지게 된다. 무한한 대기 상태이니 당연히 기아 현상도 발생하게 된다.
교착 상태의 예방, 회피, 탐지, 복구에 대해 알고 싶다면 이전 포스팅인 교착 상태를 확인하면 된다.
우선 순위 역전 현상
우선 순위가 높은 프로세스가 block 되었을 때 우선 순위 낮은 프로세스가 자원을 점유하고 있어서 우선 순위가 낮은 프로세스가 먼저 실행될 수 있다.
프로세스 a,b,c가 있을 때 (단, 우선순위는 a>b>c) 다음과 같은 상황이 발생 할 수 있다.
- 프로세스 c가 wait(S) 후 사용중이라 a는 block에 빠짐
- 프로세스 b는 c보다 우선순위가 높으므로 선점하여 실행
- 프로세스 b 실행 이후 c가 돌아와 자원 S로 작업 완료 후 signal(S)
- a가 돌아와 wait(S) 후 실행
원래 순서대로 라면 c가 먼저 실행되었으므로 c부터 실행되어 그 다음 우선순위가 높은 a가 실행되어 c -> a -> b 순서대로 실행되어야하지만 위의 경우 c -> b -> a 순서대로 실행된다. 이런 우선 순위에 위배되어 프로세스가 실행되는 현상을 우선 순위 역전 문제라고하며 해결책은 간단하다.
PIP(Priority Inheritance Protocol)이라고 불리는 것으로 우선 순위 낮은 프로세스의 실행으로 인해 우선 순위 높은 프로세스가 block 될 때 우선 순위가 낮은 프로세스에게 순위를 상속해주면된다. 그렇게되면 위의 경우 b가 선점되지 않으므로 자연스럽게 c -> a -> b 순서대로 프로세스가 실행되게 된다.
참고 자료
- Operating System Concept (written by Silberschatz, Galvin and Gagne)
- 동기화 방법 3 : 세마포어 - 운동개발좋아