임계구역 해결 알고리즘은 바쁜 대기를 사용하여 자원 낭비하고, 알고리즘이 너무 복잡하다.
이를 해결하기 위해 뮤텍스와 세마포어라는 알고리즘이 있다.
뮤텍스
여러 쓰레드(Thread)를 실행하는 환경에서 자원에 대한 접근 제한을 위한 동기화 메커니즘 중 하나
공유되는 자원에 Lock 메커니즘을 이용하여 한개의 스레드가 접근하도록 하는 장치
다른 스레드가 Lock을 소유하고 있다면 큐에 들어가 대기한다.
임계구역에 접근할 때 임계구역에 한명만 접근할 수 있는 Lock을 획득하고, 나올 때는 Unlock 하여 큐에 있는 스레드를 깨워 lock을 획득하고, 반복한다.
세마포어
에츠허르 데이크스트라(Edsger Dijkstra)는 세마포어라는 알고리즘을 제안
공유되는 자원에 제한된 개수의 프로세스(Process), 또는 스레드(Thread)만 접근할 수 있도록 한다.
- 세마포어는 임계구역에 진입하기 전, 스위치를 사용중으로 놓고 임계구역에 들어간다.
- 이후 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때 까지 기다린다.
- 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.
공유 가능한 자원의 수를 설정하여, 카운터로 사용하여 그 값에 따라(보통 0을 기준) 쓰레드나 프로세스가 임계구역에 접근하도록 허용하거나 아니면 큐에 넣어 대기하도록 하는 것
세마포어는 다른 알고리즘과 달리 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.
// 전역 변수 RS를 n으로 초기화한다. RS에는 현재 사용 가능한 자원의 수가 저장된다.
Semaphore(n); // RS = n;
// 잠금을 수행하는 코드,
// 만약 RS가 0보다 크면 (사용가능한 자원이 있으면) 1만큼 감소하고 임계구역에 진입
// 만약 RS가 0보다 작으면 (사용가능한 자원이 없으면) 0보다 커질 때 까지 기다린다. (큐에 삽입)
P(); // if RS > 0 then RS = RS -1;
// else block();
// 잠금 해제와 동기화를 같이 수행하는 코드, RS 값을 1 증가시키고, 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake_up 신호를 보낸다.
V(); // RS = RS + 1;
// wake_up();
세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up 신호를 받으면 큐에서 나와 임계구역에 진입한다.
따라서 바쁜 대기를 하는 프로세스가 없다.
허나 세마포어의 P()나 V()가 내부 코드가 실행되는 도중에 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못하므로 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고, 완전히 실행되게 해야 한다.
또한 잘못된 사용으로 인해, 임계구역이 보호받지 못할 수 있는데
P()를 두번 사용하여 세마포어 큐에서 대기하고 있는 프로세스들이 무한 대기에 빠지거나
P()와 V()를 반대로 사용하여, 상호 배제가 보장되지 않은 경우 임계구역을 보호할 수 없다.
뮤텍스와 세마포어의 차이점?
- 뮤텍스는 동기화 대상이 1개, 세마포어는 1개 이상 일 때도 사용할 수 있다.
- 뮤텍스는 Lock을 가진 프로세스가 직접 Unlock 해야 하는 반면에 세마포어는 다른 프로세스나 스레드가 wake_up 신호를 날릴 수 있다.
즉, 이진 세마포어는 뮤텍스와 동일하지 않다.
상호배제만 필요하다면 뮤텍스를, 작업 간의 순서를 동기화할 필요가 있을 경우에는 세마포어를 사용하는 것이 좋다.
