스핀락(Spinlock) 뮤텍스(Mutex) 세마포어(Semaphore)

0. 기본 개념

경쟁 조건 (Race Condition)

여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황

동기화(Synchronization)

여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것

임계 영역(Critical Section)

공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행 가능한 영역

상호 배제(Mutual Exclusion)

위의 임계 영역에서 설명한, 하나의 프로세스/스레드만 진입해서 실행한다는 것 또는 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘

그렇다면, 어떻게 이 상호 배제를 달성할 수 있을까요? 락(Lock)을 사용해서 이를 달성할 수 있습니다.

 

do {
    acquire lock // 여러 프로세스/스레드가 lock을 획득하기 위해 경합
    	[critical section] // lock을 획득한 프로세스/스레드만 임계 영역에서 실행함
    release lock // 작업을 끝내고, lock을 반환함
    	remainder section
} while(true)

 

1. Spinlock

위의 예제를, 스레드 예제로 다시한번 보겠습니다.

volatile int lock = 0; // global

void critical() {
  while(test_and_set(&lock) == 1); // lock을 획득하려는 시도를 함
  [... critical section] // lock을 얻었다면, 임계 영역으로 진입
  lock = 0; // 작업이 끝난 후, lock을 반환
}

int TestAndSet(int* lockPtr) {
    int oldLock = *lockPtr;
    *lockPtr = 1; // 반환하기 직전에 lock의 값을 1로 바꿔줌
    return oldLock;
}

2개의 스레드(T1, T2)인 상황을 가정해 보겠습니다. 

1. T1이 실행되면서 while문 조건을 검사함
2. 현재 lock은 0이기 때문에, test_and_set(&lock)은 0을 반환하고 이는 1이 아니므로 test_and_set(&lock) == 1은 false가 되어 while문을 빠져나옴
3. while문을 빠져나오기 직전에, lock을 1로 바꿔줌
4. 임계 영역으로 진입하여 작업함
5. 이 때, T2가 시작하면서 while문 조건을 검사함
6. 현재 lock값은 1이기 때문에, test_and_set(&lock) == 1은 true가 되어 while문을 빠져나오지 못함
7. 어느 정도 시간이 지난 후, T1이 작업을 마치고 lock을 반환함. (lock = 0)
8. 계속해서 조건을 확인하고 있던 T2가 lock을 획득하여 임계 영역으로 진입함.

이러한 Flow로 진행이 되게 됩니다. test_and_set(&lock)을 통해 임계 영역에서의 동시 작업을 방어하고 있습니다.

 

그런데, 동시에 T1와 T2가 작업을 시작하여 while문으로 진입하면 둘다 test_and_set을 통해 lock을 획득하여 임계 영역에 도달할 수 있지 않을까요?

 

그렇게 생각하실 수도 있지만, 사실 TestAndSet은 CPU의 atomic 명령어입니다.

TestAndSet 명령어는 동시성을 제어하기 위한 동기화 명령어 중 하나로서, 하드웨어의 도움을 받아 수행됩니다. 이것을 활용하면 상호 배제 등을 편리하게 구현할 수 있습니다.

Atomic 명령어의 특징
- 실행 중간에 간섭받거나 중단되지 않습니다
- 같은 메모리 영역에 대해 동시에 실행되지 않습니다, 즉 동시에 호출이 일어나도 CPU level에서 이를 방어합니다

따라서 앞의 예제에서 test_and_set(&lock)은 T1이 실행하고 있다가 문맥 교환으로 인해 T2가 실행될 일이 없습니다. 또 멀티 코어 환경에서 2개의 스레드가 이 명령어를 동시에 실행시켰다 하더라도 CPU level에서 동기화를 시켜서 동시에 실행시키지 않습니다.(뭐가 우선적으로 실행될지는 알 수 없음)

 

위의 예제에서 봤던, while loop를 빠져나가기 위해 계속해서 lock을 확인하여 획득하는 방식을 Spinlock(스핀락) 이라고 합니다. 이해하기 쉽게 정리하면 '락을 가질 수 있을 때 까지 반복해서 시도하는 방식' 입니다.

 

이 방식은 쉽게 Mutual Exclusion을 구현할 수 있다는 장점이 존재하지만, 락이 존재하는지를 계속해서 확인해야 하므로 CPU를 낭비한다는 단점이 있습니다. 

 

단점에 대해서 조금 자세히 설명해보자면, 이런 방식은 락이 금방 해제되는 상황에서는 크게 문제가 되지 않을수도 있지만 락을 획득하는데 오랜 시간이 걸리는 경우에는 많은 CPU 자원을 불필요하게 소모하게 됩니다. 특히, 디스크 I/O나 네트워크 통신과 같은 상대적으로 느린 작업을 수행하는 임계 영역이 존재한다면 그 동안 다른 스레드는 락을 획득하려고 계속해서 CPU를 점유하게 되겠죠? 이렇게 되면, 전체 시스템의 성능이 저하될 수 있습니다.

 

그래서, Lock이 준비될 때 까지 기다리고 있는 Mutex가 등장합니다.

 

** 위에서의 TestAndSet은 이해를 위해 작성된 코드이며, 실제와 다르게 작성되어 있습니다!

 

2. Mutex

이번에도 코드를 먼저 보고 가겠습니다.

mutex->lock(); // mutex의 lock을 가지기 위해서 경합
[critical section] // lock을 획득했다면, 임계 영역에 진입
mutex->unlock(); // 작업이 끝났다면, lock을 반환

임계 영역에 진입하기 위해 Lock을 획득하고, 작업이 끝난 후 Lock을 반환해야 하는 Flow는 동일합니다.

class Mutex{
    int value = 1; // 임계 영역에 진입하기 위해 이 value를 취득해야 함
    int guard = 0;
}

임계 영역에 진입하기 위해, 각 프로세스나 스레드들은 이 Mutex의 value를 획득해야 합니다.

Mutex::lock() {
    while(test_and_set(&guard));
    if(value == 0) { // 이미 누가 value를 취득한 상태라면 (lock을 획득할 수 없음)
        ... 현재 스레드를 큐에 넣음; // lock을 획득할 수 있을 때 깨워주기 위해 선입선출 구조인 Queue에 넣음
        guard = 0; & go to sleep
    } else { // lock을 획득할 수 있다면
        value = 0; // lock을 취득함
        guard = 0;
    }
}

Mutex::unlock() {
    while(test_and_set(&guard));
    if(큐에 하나라도 대기중이라면) { // ex) queue.isNotEmpty()
    	그 중에 하나를 깨운다; // ex) queue.poll()
    } else {
    	value = 1;
    }
    guard = 0;
}

위에서의 의사코드와 주석으로 어느정도 이해가 되셨으리라 생각합니다. 그래도 짧게나마 다시 한번 설명해보겠습니다.

 

lock에서는 당장 lock을 획득할 수 없다면, FIFO구조의 queue에 현재 스레드를 넣고, 쉬러갑니다(sleep).

unlock에서는 queue에 대기중인 스레드가 존재한다면, 스레드를 깨워서 lock을 부여합니다.

 

그렇다면, guard는 뭘까요? 위에서 Mutex의 value라는 값도 결국은 여러 프로세스/스레드가 서로 취득하기 위해 경쟁하는 공유 데이터입니다. 그렇다면, value라는 값 자체도 그 값을 바꿔줄 때 마다 임계 영역에서 안전하게 바꿔주어야 합니다. 그렇지 않으면, 경쟁 상태가 발생할 수 있기 때문입니다. 그래서, 이 value값을 임계 영역에서 안전하게 바꿔주기 위한 장치가 필요한데 그것이 바로 guard입니다.

 

위에서 test_and_set의 인자부분이 value(lock)가 아니라 guard인 것을 혹시 눈치채셨나요? value 값을 바꿔주는 로직을 보호하기 위해 guard라는 장치를 통해 보호하고 있습니다.

 

이러한 Mutual Exclusion 방식을 Mutex라고 부르며, 락을 가질 수 있을 때 까지 휴식하는 방식입니다.

 

1번에서 보았던 Spinlock과 다르게 Mutex는 lock을 획득할 수 없으면 스레드가 sleep 상태가 되는데요, 이로 인해 Cpu Cycle이 낭비되는 것을 최소화할 수 있습니다.

 

이러한 이유로 '보통' 의 경우에는 Spinlock보다 Mutex Lock이 사용됩니다.

 

** 위에서의 의사코드는 Queue로 구현되어 있는데, 실제 구현은 다를 수 있습니다.(반드시 Queue만 사용되는 것은 아닙니다)

3. Mutex vs Spinlock

위에서 제가 언급한 내용들을 종합하면, Mutex가 항상 Spinlock보다 좋은 것 처럼 느껴지는데 진짜 그럴까요? 대부분에 상황에서는 어느 정도 맞는 말이지만, 꼭 그렇지만은 않습니다.

멀티 코어 환경이고, 임계 영역에서의 작업이 문맥 교환보다 더 빨리 끝난다면 Spinlock이 Mutex보다 더 이점이 있습니다.

앞선 Mutex는 lock을 획득할 수 없다면 스레드들이 sleep 상태로 대기하다가 lock을 획득할 수 있다면 깨어나서 lock을 획득하여 작업을 이어가는 방식이었습니다. 반대로 Spinlock은 계속해서 lock을 획득할 수 있는지 확인하는 작업이었죠? 임계 영역에서의 작업이 이러한 잠들고 깨는(문맥교환) 시간보다 짧다면 Spinlock이 더 우세할 수 있습니다.

 

그러면 왜 멀티 코어라는 조건이 붙는걸까요? 싱글 코어 환경에서는 Spinlock을 사용한다고 하더라도, lock을 취득하려면 누군가가 쥐고있는 lock을 해제해야 하는데 이러한 과정이 결국 문맥교환을 필요로 하기 때문입니다. 반면 다른 코어에서 다른 코어의 락을 획득하기 위해 Spinlock 방식으로 확인하고 있다면, lock을 획득하는 과정에서 문맥교환이 발생하지 않기 때문에 이러한 상황에서는 성능 상 이점이 존재하게 되겠습니다.

 

4. Semaphore

Signal Mechanism을 가진, 하나 이상의 프로세스/스레드가 임계 영역에 접근하도록 하는 장치

간단한 정의는 이러한데요, 이번에도 코드로 확인해 보겠습니다.

semaphore -> wait(); // mutex에서의 lock
[critical section]
semaphore -> signal(); // mutex에서의 unlock

class Semaphore {
    int value = 1; // mutex와 달리 0, 1, 2... 의 값을 가질 수 있음
    int guard = 0;
}

Semaphore::wait() {
    while(test_and_set(&guard));
    if(value == 0) { 
        ... 현재 스레드를 큐에 넣음;
        guard = 0; & go to sleep
    } else {
        value -= 1; // mutex에서는 0으로 바꾸었지만, semaphore에서는 1씩 차감하는 형태
        guard = 0;
    }
}

Semaphore::signal() {
    while(test_and_set(&guard));
    if(큐에 하나라도 대기중이라면) { 
    	그 중에 하나를 깨운다;
    } else {
    	value += 1; // mutex에서는 1로 바꾸었지만, semaphore에서는 1씩 증가하는 형태
    }
    guard = 0;
}

전체적으로 Mutex의 코드와 비슷합니다.

차이점으로는 value(lock)을 Semaphore는 1 이상 가질 수 있는 부분과 락을 획득했을 때, 해제했을 때 단순히 value를 0, 1로 바꾸는 것이 아니라 현재 값에서 차감하고 증가하는 형태로 바뀐 부분입니다.

 

왜 이러한 형태로 값을 변경하냐면, Semaphore는 임계 영역에 프로세스/스레드가 하나 이상 들어가게 하기 위함입니다. 예를 들어서, 3개의 좌석이 있는 식당이라면 이런 경우에 3개까지 사용할 수 있겠죠? 이러한 상황에 사용할 수 있습니다.

물론, value 값을 1로 지정하여 Mutex와 같이 Semaphore도 하나의 프로세스/스레드만 임계 영역에 진입하게 할 수도 있습니다. Semaphore 클래스의 value가 1로 설정되어 있다면, 누군가 lock을 획득하는 순간 value가 0이 될 것이고, 그렇다면 if문 조건에 걸려서 다른 프로세스/스레드는 lock을 획득할 수 없게 될테니까요.

 

이렇게 value값으로 1을 가지는 Semaphore를 binary Semaphore, 혹은 이진 세마포어라고 하고, value값으로 1이 아닌 값을 가지는 Semaphore를 Counting Semaphore라고 합니다.

 

위에서 Semaphore 정의에 Signal mechanism라는 말을 했었는데요, 이 말은 Semaphore의 값이 변경될 때 다른 프로세스/스레드에 그 사실을 알리는 방법을 의미합니다.

1. 2개의 프로세스가 있다(P1, P2)
2. 각 프로세스가 공유 자원을 사용하려고 함
3. P1이 먼저 자원을 사용하기 위해 세마포어를 획득함(lock)
4. P2는 lock을 얻을 때 까지 기다림
5. P1이 작업을 마치면, Lock을 해제함(Signal Mechanism)
6. P2가 그 신호를 받고 자원을 사용함

  P1      --->  Lock  --->  Work  --->  Unlock  --->
          
  P2                  --->  Wait  ------------>  Work

 

이러한 Signal Mechanism을 통해 실행 순서도 정해줄 수 있게 됩니다.

 

그런데, 생각해보면 조금 이상한 부분이 있습니다. 위에서의 Mutex 예시는 Queue로 구현되었고, 이도 결국 순서를 정해줄 수 있는 것이 아닌가? 라는 생각인데요. 그렇다면 Mutex와 Binary Semaphore는 같은게 아닐까요?

 

5. Binary Semaphore 와 Mutex는 같은것일까?

결론부터 말하자면 똑같지 않습니다. 몇 가지 차이점을 얘기해보겠습니다.

 

1. Mutex는 lock을 가진 자만 lock을 해제 할 수 있지만, Semaphore는 그렇지 않다.

앞의 Semaphore 예제에서 보면, Semaphore는 wait를 호출하는 존재와 signal을 호출하는 존재가 다를 수 있습니다. 하지만 Mutex는 lock을 가진 프로세스/스레드만이 lock을 해제할 수 있기 때문에, 누가 lock을 해제할지 어느정도 예상할 수 있습니다.

 

2. Mutex는 Priority Inheritance 속성을 가지지만, Semaphore는 그렇지 않다.

우선, Priority Inheritance를 간단하게 설명해보겠습니다.

여러 프로세스/스레드가 동시에 실행을 하게 되면 CPU에서 문맥교환이 발생해서 누구를 먼저 실행시킬지 정해야 하는데, 이를 스케줄링(Scheduling)이라 합니다. 이 스케줄링 방식에는 여러가지가 있는데, 그 중 하나가 프로세스/스레드 우선순위에 따라서 우선순위가 높은 프로세스/스레드를 먼저 실행시키는 방식입니다.

 

간단한 기본 개념을 말씀드렸으니, 이 스케줄링 방식 이해를 위해 상황을 통해 설명해보겠습니다.

2개의 프로세스 P1(High Priority), P2(Low Priority)가 있는데 P1의 우선순위가 더 높은 상황을 가정해 보겠습니다. 

1. P2가 먼저 lock을 획득하여 임계 영역에서 작업하고 있습니다.
2. 스케줄링이 진행되어서, P1이 lock을 획득하려 하고 있지만 P2가 점유하고 있어 작업을 진행하지 못합니다. (P1은 P2가 lock을 반환하기 전까지 작업을 할 수 없게 됨, P1이 P2에 의존함)
3. 이 때, P2는 우선순위가 낮은 작업이므로 이 스케줄링 방식에서 언제 작업이 끝날지 모름(임계 영역 점유가 길어질 수 있음)
4. 따라서, P1은 우선순위가 높음에도 불구하고 아무 작업도 못하고 기다리고 있음

이러한 우선순위가 높은 작업이, 우선순위가 낮은 작업에 의해 실행되지 못하는 상황을 Mutex에서는 이렇게 해결합니다.

1. P1이 P2에 의존하고 있는 이 상황에서, P2의 우선순위를 P1만큼 올려버립니다.
2. 따라서, P2의 우선순위가 올라갔으므로 스케줄러가 P2를 실행시킵니다.
3. 이에 P2가 빠르게 임계 영역을 빠져나올 수 있게 됩니다.

이렇게 P2의 우선순위를 P1만큼 올려주는 이것을 Priority Inheritance라고 부릅니다.Semaphore는 누가 lock을 해제할지(signal)알 수 없기 때문에 이러한 속성이 존재하지 않습니다. 따라서,

Mutual Exclusion(상호 배제)만 필요하다면 Mutex를, 작업 간의 실행 순서 동기화가 필요하다면 Semaphore가 권장됩니다.

 

---

오늘 다뤘던 Spinlock, Mutex, Semaphore의 구체적인 동작 방식은 OS와 프로그래밍 언어에 따라 조금씩 다를 수 있습니다.