스핀락(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을 사용해 락을 해제할 수 있습니다.

 

세마포어는 자원의 개수를 의미하기도 합니다.

세마포어는 사용할 수 있는 자원의 개수에 따라 두 가지 유형이 있습니다.

구현

---

세마포어(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로 옮깁니다.
  
  
  
  

스핀 락(SPIN LOCK)과 뮤텍스(MUTEX)의 차이

둘 모두 자원에 대해 락을 걸고 사용하려고 할 시에 락이 풀릴 때까지 기다려야 한다는 점은 같지만, 둘은 내부적으로 로우레벨에서 차이점이 있다.

 

 우선 뮤텍스의 경우, 자원에 이미 락이 걸려 있을 경우 락이 풀릴 때까지 기다리며 컨텍스트 스위칭을 실행한다. 

즉, 다른 병렬적인 태스크를 처리하기 위해 CPU를 양보할 수 있다는 것이며 이는 자원을 얻기 위해 오랜 시간을 기다려야 할 것이 예상될 때 다른 작업을 동시에 진행할 수 있다는 것이다. 하지만 이는 자원이 단시간 내로 얻을 수 있게 될 경우 컨텍스트 스위칭에 더 큰 자원을 낭비하게 될 수 있다는 문제가 있다.

 스핀 락의 경우에는 이름에서부터 알 수 있듯이, 자원에 락이 걸려 있을 경우 이를 얻을 때까지 무한 루프를 돌면서 다른 태스크에 CPU를 양보하지 않는 것이다. 자원이 단시간 내로 얻을 수 있게 된다면 컨텍스트 스위칭 비용이 들지 않으므로 효율을 높일 수 있지만, 그 반대의 경우 다른 태스크에 CPU를 양보하지 않으므로 오히려 CPU 효율을 떨어뜨릴 수 있는 문제가 있다.