[Server] Spin lock & Mutex & Semaphore

 

기본 개념

Spin lock, Mutex, Semaphore를 이해하기 전 기본적으로 알아야 하는 개념들이 존재한다.

이에 대해 먼저 살펴보면 다음과 같다.

Race Condition ( 경쟁 조건 )

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

Synchronization ( 동기화 )

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

Critical Section ( 임계 영역 )

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

Mutual Exclusion ( 상호 배제 )

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

 

여러 개의 프로세스 /  스레드가 존재할 때, 

Race Condition인 상황을 극복하기 위해서는 상호 배제가 이루어져야 한다.

이 상호 배제는 Lock을 통해 구현할 수 있다.

이 Lock의 종류로 크게 Spin lock / Mutex / Semaphore 가 존재하는 것이다.

 

Spin lock

스핀 락(Spin lock)은 임계 구역에 진입이 불가능할 때

진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된다.

임계 구역 진입 전까진 루프를 계속 돌고 있기 때문에 busy waiting이 발생하게 된다.

다음은 spin lock을 사용하는 코드의 예시이다.

volatile boolean lock = false; // global

boolean test_and_set (boolean *target)
{
    boolean rv = *target;
    *target = true; // 반환 직전 Lock을 True로 변경
    return rv:
}

do {
    while(test_and_set(&lock)); // Lock을 획득하기 위한 시도
    [ This is Critical Section ] // Lock을 얻었다면 임계 영역으로 접근 
    lock = false; // 작업이 끝난 후 Lock을 반환
    [ This is Remainder Section ]
    
} while (true);

 

2개의 스레드(T1, T2)인 상황을 가정하여 흐름을 살펴보면 다음과 같다.

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

예시 코드는 위와 같은 흐름으로 진행되고,

test_and_set(&lock)을 통해 임계 영역에서의 동시 작업을 방어하게 된다.

 

그런데, 동시에 T1와 T2가 작업을 시작하여 while문으로 진입하면,

둘 다 test_and_set을 통해 lock을 획득하여 임계 영역에 도달할 수 있지 않을까?

사실 test_and_set은 CPU의 Atomic 명령어이다.

Atomic 명령어는 같은 메모리 영역에 대해 동시에 실행되지 않는다,

즉 동시에 호출이 일어나도 CPU level에서 이를 방어해 주는 것이다.

 

따라서 앞의 예제에서 test_and_set(&lock)은

T1이 실행하고 있다가 문맥 교환으로 인해 T2가 실행될 일이 없다.

또 멀티 코어 환경에서 2개의 스레드가 이 명령어를 동시에 실행시켰다 하더라도

CPU level에서 동기화를 시켜서 동시에 실행시키지 않는다.

 

test_and_set 명령어는 동시성을 제어하기 위한 동기화 명령어 중 하나로서,

하드웨어의 도움을 받아 수행된다. 이것을 활용하면 상호 배제 등을 편리하게 구현 가능하다.
하지만 test_and_set은 CPU 명령어이므로 

임계 영역 문제를 해결하기 위해 어셈블리 수준의 코딩이 필요하다.

따라서 위의 예시는 Spin lock의 흐름을 나타내기 위해 제시한 코드로

실제로는 세마포어와 함께 Spin lock 방식을 많이 구현한다.

 

위의 예제 코드처럼, while loop를 빠져나가기 위해

계속해서 lock을 확인하여 획득하는 방식이 Spin lock 방식이다.

이 방식은 쉽게 Mutual Exclusion을 구현할 수 있다는 장점이 존재하지만,

락이 존재하는지를 계속해서 확인해야 하므로 CPU를 낭비한다는 단점이 있다. 

 

이런 방식은 락이 금방 해제되는 상황에서는 크게 문제가 되지 않을 수도 있지만

락을 획득하는데 오랜 시간이 걸리는 경우에는 많은 CPU 자원을 불필요하게 소모한다.

특히, 디스크 I/O나 네트워크 통신과 같은 상대적으로 느린 작업을 수행하는

임계 영역이 존재한다면 그동안 다른 스레드는 락을 획득하려고

계속해서 CPU를 점유하게 되고, 이렇게 되면, 전체 시스템의 성능이 저하될 수 있다.

 

Mutex

Mutex는 잠금이 걸려 있을 때 스레드를 대기 상태로 전환시켜

CPU를 다른 스레드에게 할당하고, 잠금이 해제되면 해당 스레드는 다시 깨어나는 구조이다.

Mutex는 자원에 대한 접근을 동기화하기 위해 사용되는 상호 배제 기술로,

Locking 메커니즘으로 락을 걸은 스레드만이 임계 영역을 나갈 때 락을 해제할 수 있다.

다음은 Mutex를 사용하는 예시 코드이다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; // 전역 Mutex 초기화

void* thread_function(void* arg) {
    do {
        pthread_mutex_lock(&lock); // Mutex 잠금 시도
        // [ This is Critical Section ]
        pthread_mutex_unlock(&lock); // 임계 영역 작업 후 Mutex 잠금 해제
        // [ This is Remainder Section ]
    } while (true);
}

 

잠금 메커니즘이라는 점은 스핀 락과 동일하나

권한을 획득할 때까지 busy waiting 상태에 머무르지 않고,

sleep 상태로 들어가고 wakeup 되면 다시 권한 획득을 시도하는 sleep lock을 사용한다.

 

lock에서는 당장 lock을 획득할 수 없다면, FIFO구조의 queue에 현재 스레드를 넣고, 

Sleep 상태에 들어간다. unlock에서는 queue에 대기 중인 스레드가 존재한다면,

스레드를 깨워서 lock을 부여한다. 이 과정은 pthread_mutex_lock()에 포함되어 있는데,

pthread_mutex_lock()의 처리과정을 살펴보면 다음과 같다.

 

Mutex가 사용 중일 때

스레드가 pthread_mutex_lock()을 호출하면, 대기 상태로 전환된다.

이 스레드는 자동으로 내부 대기 큐(FIFO 큐)에 추가된다.

FIFO(선입선출) 방식으로 관리되므로, 대기 중인 스레드는 Mutex가 해제되면 순서대로 깨어난다.

 

Mutex가 해제될 때

다른 스레드가 pthread_mutex_unlock()을 호출하면,

대기 중인 첫 번째 스레드가 깨어나 Mutex를 얻고 임계 구역에 진입한다.

이 과정은 OS 내부에서 처리되며, 개발자가 직접 대기 큐를 관리할 필요는 없다.

 

 

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

Spinlock과 다르게 Mutex는 lock을 획득할 수 없으면 스레드가 sleep 상태가 되는데,

이로 인해 Cpu Cycle이 낭비되는 것을 최소화할 수 있다.

다음과 같은 이유 때문에 Mutex를 SpinLock보다 많이 사용한다.

하지만 항상 Mutex가 좋은 방법일까?

 

Spin lock vs Mutex

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

 

앞선 Mutex는 lock을 획득할 수 없다면 스레드들이 Sleep 상태로 대기하다가

lock을 획득할 수 있다면 깨어나서 lock을 획득하여 작업을 이어가는 방식이다.

반대로 Spin lock은 계속해서 lock을 획득할 수 있는지 확인하는 작업이다.

임계 영역에서의 작업이 잠들고 깨는(문맥교환) 시간보다 짧다면 Spin lock이 더 우세할 수 있다.

 

멀티 코어라는 조건을 붙는 이유는 다음과 같다.

싱글 코어 환경에서는 Spin lock을 사용한다고 하더라도

lock을 취득하려면 누군가가 쥐고 있는 lock을 해제해야 하는데,

이러한 과정이 결국 문맥교환을 필요로 하기 때문이다.

반면 다른 코어에서 다른 코어의 락을 획득하기 위해 Spin lock 방식으로 확인하고 있다면,

lock을 획득하는 과정에서 문맥교환이 발생하지 않기 때문에 성능 상 이점이 존재한다.

이에 대해 좀 더 자세히 설명하면 다음과 같다.

 

싱글 코어 환경에서 Spin lock과 Mutex의 동작 방식

Spin lock

바쁜 대기(Busy Waiting) 방식으로, 스레드가 락을 얻으려고 끊임없이 루프를 돈다.

스레드가 락을 얻지 못하면 계속 CPU를 점유하며 락이 해제될 때까지 기다린다.

문제는 싱글 코어 환경에서는 하나의 스레드만 CPU를 사용할 수 있다.

현재 락을 쥐고 있는 스레드가 임계 영역에서 작업을 끝내야 다른 스레드가 락을 얻을 수 있는데,

Spin lock이 걸려 있는 스레드는 CPU를 점유하면서 계속 대기하기 때문에

락을 쥐고 있는 스레드가 CPU에 접근할 기회를 얻지 못하게 된다.

결국, 락을 쥐고 있는 스레드가 CPU를 쓰려면 Spin lock을 걸고 있는 스레드를

강제로 문맥 교환(Context Switch) 해야 한다. 이렇게 되면 Spin lock이 문맥 교환 오버헤드를

줄이기 위해 설계되었지만, 문맥 교환이 필수적으로 발생하게 되어 Spin lock의 이점을 잃는다.

 

Mutex

반면, Mutex는 스레드가 락을 얻지 못하면 즉시 대기 상태로 전환되며, CPU를 양보한다.

즉, 락을 쥐고 있는 스레드가 CPU를 사용할 수 있게 되어, 빠르게 임계 구역을 끝내고 락을 해제한다.

그래서 싱글 코어 환경에서는 Spin lock보다는 Mutex가 더 적합하다.

Mutex는 락을 기다리는 동안 CPU 자원을 낭비하지 않고,

필요시 문맥 교환을 통해 락을 쥐고 있는 스레드에게 CPU를 넘기기 때문이다.

 

멀티 코어 환경에서 Spin lock과 Mutex의 동작 방식

Spin lock

멀티 코어 환경에서는 여러 코어가 동시에 작업을 처리할 수 있다.

즉, 한 코어가 임계 구역에서 작업을 진행하면서 락을 쥐고 있는 동안,

다른 코어는 계속해서 락이 해제되는지를 확인하는 Spin lock을 실행할 수 있다.

이 경우 문맥 교환이 필요하지 않다. 락을 쥐고 있는 스레드는 다른 코어에서 실행되고 있으며,

Spin lock을 기다리는 스레드는 다른 코어에서 계속 CPU를 점유하고 있기 때문에

문맥 교환이 발생하지 않고, 락이 해제되자마자 바로 락을 획득할 수 있다.

즉, 멀티 코어 환경에서는 Spin lock이 락을 기다리는 동안

CPU 자원을 효율적으로 사용할 수 있어 성능 상의 이점이 생긴다.

 

Mutex

멀티 코어 환경에서도 Mutex는 스레드가 락을 얻지 못할 경우 

즉시 대기 상태로 전환되며 CPU를 양보한다.

그러나 Spin lock의 경우와 달리, 대기 상태로 들어가면서 문맥 교환이 발생하게 되고,

대기 시간이 짧은 경우에는 이 문맥 교환이 오히려 성능 저하를 초래할 수 있다.

왜냐하면, 락이 짧은 시간 내에 해제될 상황에서도 스레드가 대기 상태로 전환되고,

이후 다시 깨워지는 오버헤드가 발생하기 때문이다.

 

결론적으로, 멀티 코어 환경에서는 락을 획득하기 위해 Spin lock을 사용할 때,

다른 코어에서 작업이 동시에 이루어지기 때문에

문맥 교환이 발생하지 않아서 성능 상의 이점이 생긴다.

 

 

Semaphore

세마포어의 정의는 다음과 같다.

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

 

운영체제는 소프트웨어상에서 Critical Section 문제를 해결하기 위한 

동기화 도구로써 Semaphore을 제공하고 있다.

세마포어는 음수가 아닌 정수 값을 가지고 스레드 간에 공유되는 변수로,

이 변수는 임계 구역 문제를 해결하고 동기화를 구현하는 데 사용된다.

세마포어는 자원의 개수를 의미하기도 하는데,

사용할 수 있는 자원의 개수에 따라 두 가지 유형이 존재한다.

이진 세마포어 (Binary semaphore)

• 0 또는 1 값만 가질 수 있는 세마포어
• 임계 구역 문제를 해결하는 데 사용하며 자원이 하나이기 때문에 뮤텍스로도 사용 가능

개수 세마포어 (Counting semaphore)

• 도메인이 0 이상인 임의의 정수값인 세마포어
• 여러 개의 자원을 가질 수 있으며 제한된 자원을 가지고 액세스 작업을 할 때 사용 가능

이 세마포어를 이용하여 Spin lock 방식과 Mutex 방식으로 둘 다 구현할 수 있다.

volatile boolean S = 1;

wait(S) {
  while (S <= 0);  // 자원이 없다면 while 루프를 돌며 대기
  S--;  // 자원을 획득함.
}

signal(S) {
  S++;  // 자원을 해제함.
}

void doSomething(){
    wait(S);
    // [ This is Critical Section ]
    signal(S);
    // [ This is Remainder Section ]
}

volatile boolean S = 1;

wait (S) {
    S--;
    if (S < 0)
        // 해당 프로세스를 wait queue에 추가 (Block)
}

signal (S) {
    S++;
    if (S <= 0)
        // wait queue에서 프로세스를 제거 (WakeUp)
}

void doSomething(){
    wait(S);
    // [ This is Critical Section ]
    signal(S);
    // [ This is Remainder Section ]
}

 

세마포어를 사용하였을 때의 차이점으로는

Semaphore는 1 이상 가질 수 있는 부분과 락을 획득하고,

해제했을 때 현재 값에서 차감하고 증가하는 형태로 바뀐 부분이다.

 

왜 이러한 형태로 값을 변경하냐면,

Semaphore는 임계 영역에 프로세스/스레드가 하나 이상 들어가게 하기 위함이다.

예를 들어서, 3개의 좌석이 있는 식당이라면 좌석을 3개까지 사용하는 상황과 유사하다.

물론, S의 초기값을 1로 지정하여 Mutex와 같이 Semaphore도

하나의 프로세스/스레드만 임계 영역에 진입하게 할 수도 있다.

 

이렇게 초기 세마포어 값이 1인 Semaphore를 위에서 설명한 binary Semaphore,

혹은 이진 세마포어라고 하고, 1이 아닌 값을 가지는 Semaphore를 Counting Semaphore라고 한다.

 

위에서 Semaphore 정의에 Signal mechanism라는 구문이 나온다.

이 구문은 Semaphore의 값이 변경될 때 다른 프로세스/스레드에 그 사실을 알리는 방법을 의미한다.

아래 예시를 통해 이해를 높일 수 있다.

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

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

 

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

하지만 Mutex 예시는 Queue로 구현되었고, 이도 결국 순서를 정할 수 있는 것처럼 보인다.

그렇다면 Mutex와 Binary Semaphore는 같아 보이는데 차이점이 존재한다.

 

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

앞의 Semaphore 예제에서 보면,

Semaphore는 wait를 호출하는 존재와 signal을 호출하는 존재가 다를 수 있다.

하지만, Mutex는 lock을 가진 프로세스 / 스레드만이 lock을 해제할 수 있다.

위의 Mutex 설명에서 Mutex는 Locking 메커니즘으로

락을 걸은 스레드만이 임계 영역을 나갈 때 락을 해제할 수 있다고 설명하였다.

하지만 세마포어는 Signaling 메커니즘으로 락을 걸지 않은 스레드도 signal을 통해 락을 해제할 수 있다.

따라서 세마포어의 카운트를 1로 설정하면 뮤텍스처럼 활용할 수 있지만,

Mutex는 절대 세마포어처럼 사용될 수 없다.

마지막으로 Spin lock과 Mutex의 특징, 차이점과 적용 상황에 대해 정리하면 다음과 같다.

 

Spin lock Summary

동작 원리

Spin lock은 잠금이 걸려 있을 때,

스레드가 잠금이 해제될 때까지 계속해서 CPU를 점유하며 루프를 돌면서 확인.

 

장점

• 짧은 대기 시간
  잠금이 짧은 시간 안에 해제될 것이 확실한 경우,
  문맥 전환(Context Switch) 없이 대기할 수 있어 빠른 반응이 가능하다.
• 스레드 전환 비용 없음
  CPU 자원을 계속 사용하므로 문맥 전환을 하지 않아 스레드 전환 비용이 없다.

단점

• CPU 낭비
  잠금을 기다리는 동안에도 CPU를 계속 사용하므로, 잠금이 오래 걸리면 효율성이 떨어진다.

Spin lock이 적합한 상황

• 잠금 유지 시간이 매우 짧을 때
  자원에 대한 접근이 빠르게 이루어지고, 잠금 대기 시간이 짧을 것으로 예상될 때
• 멀티코어 시스템
  여러 코어에서 동시에 실행되는 상황에서 문맥 전환을 피하고
  잠금을 빠르게 얻는 것이 유리할 때
• 커널 수준의 코드에서 자주 사용
  문맥 전환 비용을 줄이기 위해 커널 코드에서 Spin lock을 사용하는 경우가 많다.

 

Mutex Summary

동작 원리

Mutex는 잠금이 걸려 있을 때 스레드를 대기 상태로 전환시켜

CPU를 다른 스레드에게 양보한다. 잠금이 해제되면 해당 스레드는 다시 깨어난다.

 

장점

• CPU 낭비 없음
  잠금을 기다리는 동안 스레드가 CPU를 사용하지 않기 때문에 자원이 낭비되지 않는다.
• 긴 대기 시간에도 유리
  잠금이 오랫동안 지속될 때 효율적으로 대기할 수 있다.

단점

• 문맥 전환 비용
  잠금을 기다리면서 스레드를 대기 상태로 전환하는 과정에서
  문맥 전환이 발생하여 약간의 오버헤드가 존재한다.

Mutex가 적합한 상황

• 잠금 유지 시간이 길 때
  자원을 오랜 시간 잠그고 사용하는 경우에
  스레드를 대기 상태로 만들어 CPU 낭비를 줄일 수 있다.
• 단일 프로세서 시스템
  여러 코어가 없고 문맥 전환이 빈번하게 일어나지 않는 환경에 적합.
• 복잡한 동기화 요구
  Mutex는 더 복잡한 동기화 요구 사항
  (재진입, 우선순위 상속 등)에 대응할 수 있는 다양한 기능을 제공.

 

즉 Spin lock은 짧은 시간 안에 자원을 잠그고 해제할 때,
또는 멀티코어 시스템에서 사용하기 적합하고 Mutex는 긴 시간 동안 잠금을 유지할 때,

또는 단일 코어 시스템에서 CPU 자원을 절약하기 적합하다.

상황에 따라 이러한 동기화 기법을 적절하게 선택하는 것이 성능과 효율성에 큰 영향을 미친다.

 

 

참고자료

https://s7won.tistory.com/12

https://yoongrammer.tistory.com/63

https://jwprogramming.tistory.com/13

 https://mangkyu.tistory.com/104