[운영체제] Process Synchronization (3) - Mutex Lock, Semaphore

오늘은 프로세스 동기화의 마지막 남은 부분들에 대해서 알아보겠습니다. 구체적으로는 Mutex Lock과 Semaphore에 대해 중점적으로 알아보고자 합니다.

 

1. Mutex Locks

바로 전의 글에서 하드웨어를 통한 동기화 기법인 test_and_set이나 compare_and_swap의 경우에도 문제점이 있다는 점에 대해서 공부했었습니다. 그래서 운영체제의 설계자들은 이러한 문제를 해결하기 위해 다시 소프트웨어 툴을 개발합니다. 그리고 이 중에 가장 간단한 도구가 바로 Mutex Lock입니다. 아마 리눅스에서 쓰레드를 공부해 보았다면 한번쯤은 사용해 보았을 것이라 생각됩니다.

 

Mutex는 Mutual Exclusion을 뜻하고, 모든 프로세스는 Critical section에 들어가기 위해 lock을 획득해야만 하며, 빠져나올 때 반환해야 합니다. 실제로 acquire() 함수를 통해 lock을 획득하고, release() 함수를 통해 lock을 반납하게 됩니다. acquire과 release 함수는 다음과 같이 정의됩니다.  

 

여기서 available이라는 변수를 통해 현재 Lock이 사용 가능한지 아닌지를 표시합니다. Mutex Lock도 앞에서 설명한 test_and_set이나 compare_and_swap과 같이 원자적으로 수행됩니다. Mutex Lock의 사용 예시는 다음과 같습니다.

 

Mutex Lock의 약점은 바쁜 대기 (Busy Waiting)를 해야 한다는 점입니다. 즉, lock을 얻지 못하여 Critical section에 들어가지 못하는 동안 acquire 함수 내에서 while문을 돌고 있어야 한다는 단점이 있습니다. 다시 말해 현재 Critical section에 들어가지 못하여 어차피 프로세스는 할 일이 없음에도 불구하고 계속 while문을 통해 available 변수의 상태를 확인해야 합니다. 이것을 보고 프로세스가 Lock을 기다리면서 계속 회전하고 있다고 해서 Mutex Lock을 Spinlock이라고도 부릅니다.

 

하지만 프로세스가 계속 일을 하고 있기 때문에 Context Switching을 할 필요가 없다는 것은 오히려 장점으로 작용하기도 합니다. 그래서 프로세스들이 짧은 시간 동안 Lock을 소유하는 경우라면 Mutex가 유용하게 사용될 수 있습니다.

 

2. Semaphore

Mutex에서의 Lock은 boolean 값으로써 true나 false의 값만 가집니다. 하지만 Semaphore에서는 boolean 대신 integer 값의 변수를 이용합니다. Semaphore에서는 wait() 함수와 signal()함수를 이용합니다. 두 함수의 정의는 다음과 같습니다.

 

물론 wait와 signal도 원자적으로 실행이 되며, busy waiting 방식을 사용합니다. S 값을 이용하여 현재 Critical section에 들어갈 수 있는지 없는지 판단을 하게 됩니다. 

 

Semaphore에는 두 가지 방식이 존재합니다. 바로 Counting Semaphore와 Binary Semaphore입니다. Binary Semaphore는 0과 1만을 사용하기 때문에 Mutex Lock과 거의 동일한 기능을 합니다. 하지만 Counting Semaphore는 integer 값을 모두 사용하기 때문에 여러 프로세스에 제한된 양의 resource를 할당해 줄 때 유용하게 사용할 수 있습니다. 처음에 S의 값을 resource의 개수로 초기화해주고 사용할 때는 wait를, 반납할 때는 signal을 호출해주면 됩니다. 그리고 S의 값이 0이 되었을 때는 현재 사용 가능한 resource가 없으므로 누군가 반납할 때까지 기다려야 합니다.

 

3. Semaphore의 구현

Semaphore와 Mutex Lock 모두 busy waiting이라는 단점을 가지고 있습니다. 그래서 이를 극복하기 위해 Linked list를 이용하면서, wait와 signal 함수를 다음과 같이 조금 변경시킬 수 있습니다. 

우선 구조체를 하나 만들어줍니다. value는 위에서의 S의 값과 똑같은 역할을 하고 *list는 waiting queue의 head를 가리키게 됩니다.

 

wait()가 실행되면, 물론 Critical section에 들어갈 수 있는 상황이면 그냥 들어가면 되고, S의 값을 줄여주면 됩니다. 하지만 S의 값이 0이거나 0보다 작은 경우 해당 프로세스를 linked list로 구현된 waiting queue에 추가해주고 block 시켜 버립니다. 그럼 해당 프로세스는 running 상태에서 waiting 상태로 바뀌게 되고, CPU 스케쥴러는 새로운 프로세스를 선택하여 실행시킵니다. 

 

signal()이 실행되면, 프로세스가 wakeup()을 통해 재시작됩니다. Wait 상태에 있던 프로세스는 깨어나서 Ready 상태가 되어 Ready queue로 들어가게 되고 스케쥴러에게 선택받기를 기다리게 됩니다.

 

S의 값이 0 이하로도 계속 내려가게 구현을 하는 이유는 현재 waiting 상태로 대기 중인 프로세스의 수를 파악하기 위해서 입니다. S의 값이 -2라면 현재 2개의 프로세스가 대기 중이라는 뜻이 되기 때문입니다. 이를 위해서 기존의 wait 함수에서 S의 값의 감소시키는 부분과 S 값을 검사하는 부분의 순서를 바꾼 것입니다.

 

4. Deadlock and Starvation on semaphore

Waiting queue를 이용한 Semaphore 구현에서는 둘 이상의 프로세스가 서로의 signal 함수를 기다리면서 서로 더 이상 무한정 실행이 되지 못하는 상황이 발생할 수도 있습니다. 이러한 상황을 Deadlock (교착상태)이라고 합니다. Deadlock에 대해서는 다음 글에서부터 상세히 다룰 예정이니 지금은 그냥 넘어가도록 하겠습니다.

 

만약 Wait queue가 후입선출 (Last-In-First-Out)의 방법으로 구현된다면 여기서도 starvation 문제가 발생할 수 있습니다. 따라서 이러한 점들을 고려하여 알고리즘을 설계해야 합니다.

 

 

 

 

 

여기까지 프로세스의 동기화에 대해서 공부해보았습니다. 동기화 문제에 대한 대부분의 이슈들은 semaphore를 이용하여 해결하곤 하지만 상황에 따라서 구현에는 mutex lock이 사용될 수도 있습니다. 다음 글에서부터는 위에서 잠깐 언급했듯이 Deadlock에 대해서 공부해 보도록 하겠습니다. 읽어주셔서 감사합니다.