[OS] Synchronization III (Spin Lock, Semaphore, Example with Codes)

Spin Lock

우리는 Busy Waiting하는 것을 Spin Lock이라고 한다. 이는 당연하게 Mutual Exclusion을 제공해준다. 그러나 Busy Waiting을 할때는 CPU의 낭비는 필연적이게 된다. 그러나 CPU 자원을 소모한다고 해서 Spin Lock 자체가 비효울적이라고는 할 수 없다. 이 시점에서 우리는 Context Switch의 비용과 Busy Waiting의 비용을 비교해야한다. 계속 Context Switching을 한다면 계속 Thread/Process를 바꾸는 비용이 기하급수적으로 증가할 수도 있다. 그러나 Spin Lock 자체는 fair한 것은 아니다. 결국 대기하면서 Thread/Process가 계속해서 Progress를 하지 못해 Starvation이 발생할 수 있기 때문이다. 

Semaphore

이 전에 동기화 기법은 크게 상호 배제와 조건 동기화 두 가지의 측면으로 나뉜다고 언급을 했었다. 이 두 동기화 기법을 구현할 수 있는 Concurrent System 내에서 Generalized된, 일반적인 동기화 기법이 Semaphore이다. Semaphore를 이해하기 위해서는 Semaphore Variable S가 필요하다. 이는 하나의 Integer Value라고 이해하면 된다. 특히 설명을 할때는 자원의 개수라고 이해하면 된다. 따라서 Semaphore 변수 S가 0이라면 CS를 사용중인 것이고, 1이라면 사용전인 상태로 바라볼 수 있다. Semaphore변수를 특정 Operation들을 통해 Control 할 수 있다. sem_init()을 통해 S의 초기값을 설정해줄 수 있고, sem_wait()을 통해 S를 감소시켜 CS를 사용중이라는 표식을 남긴다. sem_signal()을 통해 CS를 다 쓰고 나서 S의 상태롤 복구시킨다. Semaphore을 처음에 고안한 Dijikstra는 sem_wait을 Proberen(독일어이다), sem_signal을 Verhogen이라고 명명했다. 따라서 Mutex, Cond, Semaphore에서 사용하는 API의 이름을 아래의 표 처럼 정리할 수 있다. 

	Mutual Exclusion	Conditional	Semaphore
P: Proberen (try)	lock	wait	wait
V: Verhogen (increase)	unlock	signal	post

따라서 본 포스팅에서 Lock이라고 한다면 P Operation을 , Unlock이라고 하면 V Operation의 총칭을 의미한다고 보면 되겠다. 

 

먼저 Mutex를 살펴보자. Mutex에서는 항상 CS에 들어갈때 T1이 CS를 Lock을 잡고 해당 영역을 수행한 후에 다시 Unlock해주는 쌍을 이루는 구조를 가지고 있다. 어느 Thread든 CS를 잡고, 풀고 하는 Operation이 필연적으로 쌍으로 존재한다. 따라서 lock이 잡혔는지 안잡혀있는지 보고 Busy Waiting하는 구조를 가지고 있다. 

반면에 Semaphore는 Busy Waiting 없이 구현이 된다. 이는 CPU를 Consume하고 있는 비효율성을 줄이기 위함이다. 자원을 사용하고 싶다면 Blocked 상태로 만들어서 wait queue에 넣는다. 당연하게도 Semaphore는 Mutex 기법을 사용하면서 조건 동기화를 위해 사용될 수 있다. 즉, Semaphore는 중의적으로 사용이 가능하다. Semaphore를 굳이 분류하자면 Binary Semaphore와 Counting Semaphore로 나눌 수 있다. Binary Semaphore는 Semaphore Variable을 0, 1의 값만 가지게 설정하는 것이다. 따라서 그냥 Mutex처럼 동작시킬 수 있다. 반면 Counting Semaphore는 Semaphore Variable의 범주의 제약이 없다. 이를 General Semaphore이라고 부르기도 하는데 이는 조건동기화에서 자주 사용이 된다. 

 

Mutex에서는 P, V Operation이 쌍으로 함께 가야하는 반면에 Semaphore에서는 굳이 쌍으로 이루어지지 않아도 된다. 만약 같은 Semaphore를 사용하고 있더라도 누군가 깨워주기만 하면 되기 때문에 Unstructed Construct 형태로 구현이 가능하다. 이 부분에 대해서는 Conditional Sync에서 자세히 다루어 보겠다. 

 

세마포어의 구현은 아래의 그림처럼 구현할 수 있다. Wait을 하는 것은 자원을 소모하는 것이기 때문에 세마포어 변수를 감소시켜준다. 만약 세마포어 변수가 음수가 된다면 현재 자원이 사용중이기 때문에 wait queue에 넣어준다. Signal은 다시 자원을 복구하는 것이기 때문에 세마포어 변수를 증가시켜준다. 만약 세마포어 변수가 0 이하라면 wait queue에 있는 Thread를 pop해서 실행시켜준다. 만약 세마포어 변수가 양수가 된다고 하더라도 상관이 없는 것이 아무것도 안해주면 된다. 물론 이렇게 구현하는 것은 정말 간단한 방법이기때문에 완벽한 Semaphore의 구현이라고는 할 수 없다. 이는 뒤에서 자세히 다뤄보겠다. 이진 세마포어는 Enum같은 자료형을 활용해서 구현할 수도 있다. 어차피 0, 1 두 가지의 상태만 가지기 때문이다. 

위와 같은 세마포어가 그림으로 이제 어떻게 동작하는지 알아보자. 이진 세마포어로 살펴볼 것이다. 우선 T1, T2, T3 세개의 Thread가 있다고 가정하자. 순차적으로 lock을 수행하고 unlock을 수행하면 Queue와 Semaphore Variable은 아래와 같이 바뀌게 된다. wait을 하면서 Sem Var을 상태에 따라 Queue에 넣고 pop을 하는 관계를 살펴볼 수 있다. 

Deadlock

컴퓨터공학도라면 OS를 배우지 않더라도 한번쯤 들어봤을 단어이다. Semaphore로 waiting queue를 구현하면 교착상태에 이를 수 있다. 교착상태란 두개 이상의 Process들이 서로 waiting하는 것을 기다리기 때문에 진행을 못하는 상황을 의미한다. Deadlock에 대해서는 뒤에서 더 자세하게 다뤄보겠다. 

Correct Synchronization Example

이제 Semaphore까지 다루어보았다. 이전 포스팅에서 쓰레드 두개를 활용해서 전역변수를 증가시키고, 감소시키는 예시를 기억하는가? 이제는 정확한 API들을 활용해서 이를 고쳐볼 것이다. 이는 당연하게도 Mutex와 Semaphore 두 가지의 방식으로 구현이 가능하다. 먼저 Mutex를 살펴보자. 먼저 pthread.h 헤더파일을 include시키고 lock변수 m을 위해 pthread_mutex_t m;을 전역변수로 선언한다. 다음은 이 변수를 초기화해야하는데 이는 pthread_mutex_init(&m, NULL);로 가능하다. 각각의 함수에서는 전역변수 x를 다루기 전 pthread_mutex_lock(&m); pthread_mutex_unlock(&m);으로 lock, unlock해준다. 우리는 항상 mutex lock변수를 매개변수로 주어서 세마포어변수가 어떤 상태인지 파악할 수 있게 해줘야한다. lock변수는 pthread_mutex_destroy(&m);으로 마지막에 해제해준다. 

다음으로는 Semaphore를 살펴보자. 흐름자체는 Mutex와 똑같지만 활용하는 API의 이름이 다르다. semaphore.h를 include해준 다음 semaphore 변수의 선언은 sem_t s;로, 초기화는 sem_init(&s, 0, 1);로 해준다. lock과 unlock은 sem_wait(&s); sem_post(&s);로 해준다. semaphore 변수의 해제는 sem_destroy(&s);로 해주면 된다. 

Reference

William Stallings. (2018). Operating Systems: Internals and Design Principles (8th Edition): Pearson.