스핀락(Spin lock), 뮤텍스(Mutex), 세마포어(Semaphore) 알아보기
스핀 락(Spin lock)
스핀 락(Spin lock)은 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락을 가리킵니다.
임계 구역 진입 전까진 루프를 계속 돌고 있기 때문에 busy waiting이 발생하게 됩니다.
다음은 spin lock을 사용하고 있는 세마포어 함수의 예입니다.
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}스핀 락은 운영체제의 스케줄링 지원을 받지 않기 때문에, 해당 스레드에 대한 문맥 교환(context switch)이 일어나지 않습니다.
짧은 시간 안에 진입할 수 있는 경우 문맥 교환 비용이 들지 않으므로 효율을 높일 수 있지만 그 반대의 경우에는 다른 스레드에 cpu를 양보하지 않기 때문에 오히려 cpu 효율을 떨어뜨리게 됩니다.
스핀 락은 문맥 교환이 일어나지 않기 때문에 멀티 프로세서 시스템에서만 사용할 수 있습니다.
뮤텍스(Mutex)
뮤텍스는 자원에 대한 접근을 동기화하기 위해 사용되는 상호 배제 기술입니다.
뮤텍스는 Locking 메커니즘으로 락을 걸은 스레드만이 임계 영역을 나갈 때 락을 해제할 수 있습니다.
뮤텍스는 wait와 signal이라는 원자적 연산을 사용합니다.
다음은 뮤텍스를 사용하여 상호 배제를 구현한 예입니다.
do {
wait (mutex);
// Critical section
signal (mutex);
// Remainder section
} while (TRUE);잠금 메커니즘이라는 점은 스핀 락과 동일하나 권한을 획득할 때까지 busy waiting 상태에 머무르지 않고
sleep 상태로 들어가고 wakeup 되면 다시 권한 획득을 시도하는 sleep lock을 사용합니다.
세마포어(Semaphore)
세마포어는 음수가 아닌 정수 값을 가지고 스레드 간에 공유되는 변수입니다.
이 변수는 임계 구역 문제를 해결하고 동기화를 구현하는 데 사용됩니다.
세마포어는 signaling 메커니즘으로 락을 걸지 않은 스레드도 signal을 사용해 락을 해제할 수 있습니다.
세마포어는 자원의 개수를 의미하기도 합니다.
세마포어는 사용할 수 있는 자원의 개수에 따라 두 가지 유형이 있습니다.
종류
이진 세마포어 (Binary semaphore)
- 0또는 1 값만 가질 수 있는 세마포어입니다.
- 임계 구역 문제를 해결하는데 사용하며 자원이 하나이기 때문에 뮤텍스로도 사용할 수 있습니다.
개수 세마포어 (Counting semaphore)
- 도메인이 0이상인 임의의 정수값인 세마포어입니다.
- 여러개의 자원을 가질 수 있으며 제한된 자원을 가지고 액세스 작업을 할때 사용합니다.
구현
세마포어(S)는 wait 연산과 signal 연산을 가지고 있습니다.
이 두 연산은 atomic 하게 동작합니다.
wait(S) 연산
- 자원을 획득하는 연산
signal(S) 연산
- 자원을 해제하는 연산
세마포어는 시스템에서 사용할 수 있는 리소스의 수로 초기화되며, wait() 함수를 호출하여 세마포어가 0보다 클 때마다 프로세스는 세마포어를 감소시키고 임계 구역에 들어갈 수 있게 됩니다.
세마포어가 0에 도달하면 다른 프로세스가 리소스를 해제하고 signal() 함수 호출로 세마포어를 증가시킬 때까지 프로세스가 차단됩니다.
구현 방식에는 busy-wating과 block-wakeup 두 가지가 있습니다.
busy-waiting 방식
자원이 없다면 while 루프 돌면서 기다리는 방식입니다. (= spin lock)
while 루프를 돌며 대기하기 때문에 busy-waiting이 발생합니다.
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}block-wakeup 방식
자원이 없다면 blocked 상태에서 기다리는 방법입니다. (= sleep lock)
자원이 생기면 wakeup으로 block 상태인 프로세스를 깨우는 작업을 합니다.
typedef struct
{
int value; /* semaphore */
struct process *list; /* process wait queue */
} semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0 ) { // 자원이 없다면
add this process to S->list; // 프로세스를 큐에 넣고
block(); // block 시킴
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) { // 자원이 0이하라면 block중인 프로세스가 있다는 의미임.
remove a process P from S->list; // 대기하고 있는 프로세스를 가져옴.
wakeup(P); // 가져온 프로세스를 깨움.
}
}block과 wakeup은 다음과 같이 동작합니다.
- block() : 커널은 block을 호출한 프로세스를 suspend 시키고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣습니다.
- wakeup(P) : block된 프로세스 P를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮깁니다.
세마포어 사용
상호 배제
세마포어를 사용하여 상호 배제를 구현할 수 있습니다.
다음은 세마포어를 사용하여 상호 배제를 구현한 예입니다.
do {
wait(S);
// Critical section
signal(S);
// Remainder section
}while (TRUE);동기화 (synchronization)
세마포어는 상호 배제뿐만 아니라 동기화에도 사용할 수 있습니다.
예를 들어 프로세스 P2가 명령문 S2를 실행하기 전에 프로세스 P1이 명령문 S1을 실행해야 한다면 다음과 같이 사용할 수 있습니다.
S = 0;
P1:
S1;
signal(S);
P2:
wait(S);
S2;S가 0으로 초기화되었기 때문에 프로세스 P2는 P1이 signal(S) 호출을 할 때까지 대기하게 됩니다.
세마포어 vs 뮤텍스 차이
뮤텍스는 Locking 메커니즘으로 락을 걸은 스레드만이 임계 구역을 나갈 때 락을 해제할 수 있지만 세마포어는 Signaling 메커니즘으로 락을 걸지 않은 스레드도 signal을 사용해 락을 해제할 수 있습니다.
이러한 차이 때문에 이진 세마포어는 뮤텍스로 사용할 수 있지만 뮤텍스는 세마포어로 사용할 수 없습니다.
