Mutex, Semaphore가 생긴 이유
- Critical Section(임계 영역)
코드상에서 경쟁조건이 발생할 수 있는 특정 부분(각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분) - 다수의 프로세스(스레드)가 공용 자원에 동시에 접근할 때, 접근 순서에 따라 결과값이 달라질 수 있음!(Race Condition)
-> 따라서 Critical Section에 대한 Race Condition을 없애기 위해 Mutex와 Semaphore라는 동기화 메커니즘을 통해 문제 해결!!
Mutex(Mutual Exclution)
- 오직 하나의 스레드만이 동일한 시점에 뮤텍스(자원에 대한 접근을 동기화하기 위해 사용되는 상호배제 기술)를 얻어 임계영역에 들어올 수 있는 Locking 메커니즘.
- lock : 현재 임계영역에 들어갈 권한을 얻어옴
- unlock : 현재 임계구역을 모두 사용했음을 알림
- 오직 임계영역에 있는 스레드만이 임계영역에서 나갈 때 뮤텍스를 해제할 수 있다.
- 뮤텍스 알고리즘은 데커 알고리즘, 피터슨 알고리즘, 베이커리 알고리즘 등 여러가지가 존재. (하지만 최근에는 이런 소프트웨어에 의한 해결책은 느리기 때문에 사용하고 있지 않다.)
Peterson's Algorithm
-
두개의 프로세스에 대한 Mutex Algorithm(현재는 일반화되어서 2개 이상의 프로세스 사이에서도 사용 가능)
-
Peterson's Algorithm Code
do {
flag[i] = true; //프로세스 i가 임계영역에 진입시도
turn = j; // 다른 프로세스에게 진입 양보
while (flag[j] && turn == j); // 다른 프로세스가 진입시도하면 대기
// Critical section
flag[i] = false; //
// Remainder section
} while(true);- Critical Section 문제를 해결하기 위한 3가지 조건을 충족하는 알고리즘
-
"while (flag[j] && turn == j);"
이부분을 통해 Mutual Exclution과 Progress를 만족한다.
-> 여러 프로세스가 대기중일 때 내 순서가 아니면 접근 X, 내 순서가 아니더라도 대기중인 프로세스가 없을 경우 내가 사용 가능. -
"turn = j;"
이부분을 통해 Bounded Waiting을 만족한다.
-> 순서를 양보함으로써 내가 계속 사용할 수 없게 제한을 걸어둔다.Semaphore
- 여러개의 프로세스(스레드)가 Critical Section에 진입할 수 있는 Locking 알고리즘.
카운터를 이용해 동시에 리소스에 접근할 수 있는 프로세스를 제한한다. - 세마포어는 P와 V라는 명령으로 접근할 수 있다.
- P : 임계 구역에 들어가기 전에 수행
- V : 임계 구역에서 나올 때 수행
- 세마포어의 카운터가 1개인 경우 Binary Semaphore라 하며 사실상 mutex와 같다.
- "Busy - Wait" 방식과 "Block - WakeUp" 방식이 있다.
- "Busy - Wait" 방식
프로세스 P가 자원이 모두 사용 중이라면 Wait 하는 방식. 자원의 여유가 생기면 s--를 통해 자원을 획득. 자원을 모두 사용했다면 s++를 통해 자원을 반납.
"Busy - Wait" 코드
P(s){
while(s <= 0) do wait
s--;
}
///임계영역///
V(s){
s++;
}s(자원)가 없을 때는 대기상태, s가 있을 때는 임계영역 진입, 임계영역을 빠져나올 때 s반납.
- "Block - Wakeup" 방식
임계영역에 진입할 때 s를 감소시키는 것이 아니라 먼저 자원의 값을 감소 시킨 후 만약 자원의 갯수가 부족해 사용할 수 없다면 프로세스를 Wait Queue에 추가시키는 방법. 자원이 생기면 Wait Queue에서 프로세스를 꺼내 와 wakeup()을 통해 프로세스를 수행시킴.
"Block - Wakeup" 방식 코드
P(S){
S.value--;
if(S.value < 0){
// add this precess to S.queue;
block();
}
}
V(S){
S.value++;
if(S.value <= 0){
// remove a process P from S.queue;
wakeup(P);
}
}s가 0보다 작은 경우 : 현재 자원을 기다리는 프로세스가 존재한다는 뜻. 따라서 Queue에서 프로세스를 꺼내 실행시킨다.
