1. Semaphores (세마포어)
세마포어는 일종의 추상 자료형입니다. 여기서 추상 자료형이란, Object와 Operation으로 구성된 개념적인 모델을 말합니다. 만약 정수 추상 자료형이라고 한다면 덧셈, 뺄셈 등의 연산을 할 수 있는걸 알듯이 어떤 자료를 어떤 방식으로 다룰지에 대한 논리적인 정의, 즉 어떤 연산을 수행할 수 있는지만 알면 되는 것입니다.
여기서의 세마포어도 마찬가지입니다. Semaphore S라는 세마포어 변수 S가 있다고 하면 S에는 정수 값을 가질 수 있고, 연산은 P연산과 V연산 두 가지가 정의됩니다. P 연산은 공유 데이터를 획득하는 과정이고 V 연산은 자원을 다 사용하고 반납하는 과정입니다. 세마포어의 변수는 자원의 갯수를 나타냅니다. 만약 세마포어 변수 값이 5라면 자원의 개수가 5개라는 뜻이고, P연산을 한번 하면 4가 되고 한번 더 해주면 3이되는 방식입니다. 만약 여기서 V연산을 하면 4가 되고 다시 한번 V연산을 하면 5개가 됩니다.
Lock을 걸고 푸는 과정은 세마포어 변수 값이 1인 경우일 때를 생각해보면 되는데, P 연산을 하면 Lock을 거는 것이고 V 연산을 하면 Lock을 푸는 과정입니다. 구체적으로 P 연산과 V 연산이 어떻게 정의되는지 살펴보겠습니다.
변수 S에 대해 P 연산을 하게 되면 변수 값이 0 이하인 동안에는 기다리게 됩니다. 즉 자원이 없어 기다리는 상태입니다. 기다리다가 S 값이 양수가 되면, 즉 누군가가 자원을 내어놓으면 그때 S값을 -1 빼고 자원을 획득하는 것입니다. 이후 자원을 다 사용하면 V 연산을 통해 +1 증가시켜서 자원을 반납하는 것입니다.
어차피 세마포어라는 것은 구체적인 구현을 나타내는 것이 아닌 추상적으로 정의를 한 것이기 때문에, 여기서 P 연산과 V연산은 atomic하게 수행된다는 것을 가정한 것입니다.
위 사진은 앞 포스팅에서 언급했던 Critical Section 문제에 세마포어를 적용한것을 보여줍니다. Sychronization 변수로 세마포어 변수가 mutex(mutual exclusion) 변수가 할당된 것을 볼 수 있습니다. 이 mutex 변수를 1로 초기화하고 Critical Section에 들어갈 때는 P 연산, Critical Section에서 빠져나올 때는 V 연산을 해주면 Critical Section 문제가 자연스럽게 해결됩니다.
그래서 개발자는 세마포어를 이용해 P 연산과 V 연산을 해주면 되고 어떻게 구체적으로 P 연산과 V 연산을 구현할지는 구현해야할 시스템에 따라 결정되는 것입니다. 이전 포스팅에서처럼 알고리즘을 일일이 코딩하는 것이 아니라 세마포어를 통해 훨씬 간단한 코드를 작성할 수 있습니다.
하지만 여기서도 Busy-waiting(혹은 Spin lock) 문제는 생깁니다. 만약 자원이 없을 때 P 연산을 하게 되면 while 문을 돌아봤자 mutex값이 여전히 양수이기 때문에, CPU 할당 시간이 끝날 때까지 무의미하게 CPU를 낭비하게 됩니다.
이러한 단점을 보완하기 위해 Block & Wake-up 또는 Sleep lock이라고 부르는 방식이 있습니다. 이전 포스팅에서 프로세스의 상태를 설명할 때, 어떤 프로세스가 CPU를 사용하다가 I/O와 같은 오래 걸리는 작업을 하러가면 그 프로세스의 상태는 Blocked가 되고 CPU를 얻는 권한이 없어진다고 설명드렸습니다.
여기서도 마찬가지로 공유 데이터에 접근하려고 할 때, 다른 프로세스가 공유 데이터을 사용하고 있다면 그 프로세스가 공유 데이터를 내어주기 전까지는 사용할 수 없는 것입니다. 다시 말해, 프로세스가 while 문을 돌고 있는 것이 아니라 blocked 상태로 잠들어있다가 공유 데이터 사용이 끝나면, 그 때 다시 깨어나 Ready Queue에 들어오는 것입니다.
2. Block & Wake-up
세마포어를 다음과 같이 정의를 해보겠습니다.
여기서 int value; 는 세마포어 변수, struct process *list; 는 프로세스의 wait queue입니다. wait queue는 세마포어 때문에 잠들어있는 프로세스들을 연결하기 위한 큐 형태로 만들어집니다.
그리고 block과 wake up을 다음과 같이 가정해보겠습니다.
- Block : 커널은 block을 호출한 프로세스를 suspend 시킨다. 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣는다.
- wake-up(P) : blocked된 프로세스 P를 wake up 시키고, 이 프로세스의 PCB를 Ready Queue에 옮긴다.
만약 세마포어를 획득할 수 없으면 그 프로세스를 Blocked 시키게 되고, 누군가 세마포어를 쓰고 나서 반납하게 되면 Blocked 된 프로세스들 중에서 하나의 프로세스를 wake-up 시킵니다. 세마포어 변수, 즉 자원을 획득하지 못한 프로세스들의 PCB는 세마포어 변수에 연결해줍니다.
(1) Block / Wakeup Implementation
P 연산
우선, 세마포어 값을 1 빼주고 자원의 여분이 있다면 자원을 획득하고, 자원의 여분이 없으면 리스트에다가 프로세스를 연결시킨 후 Blocked(sleep) 상태가 됩니다.
V 연산
자원을 다 쓰고 반납하는 과정입니다. 세마포어 값을 1 더해주고 만약 자원을 내놓았는데도 불구하고, 값이 0 이하라면 프로세스를 기다리며 잠들어있는 다른 프로세스가 있다는 것입니다. P 연산을 다시 보면 세마포어를 먼저 감소시킨 후에 리스트에 연결을 하는 것을 볼 수 있는데, 먼저 감소를 시켰기 때문에 그 값이 반영된 것이라 생각하면 이해가 편할 것입니다. 그래서 세마포어 값이 0 이하라면 자원을 반납하고 끝인게 아니라 잠든 프로세스를 깨우는 작업이 함께 있습니다.
그래서 여기서의 세마포어 값은 단순히 자원의 개수만을 나타내는 것이 아니라, 음수라면 기다리며 잠들어 있는 다른 프로세스가 있다는 상태도 나타냅니다.
(2) Busy-wait과 Block / Wakeup 방식 중 무엇이 더 나을까?
그러면 Busy wait 과 Block/wake up 방식 중 무엇이 더 나은 방식인지를 고민을 해본다면, 보통은 Block/wake up 방식이 더 효율적입니다. 쓸데없이 CPU를 쓰면서 기다릴 필요없이 자원을 누군가가 쓰면서 기다리는 것이 CPU의 이용률이 높을 것입니다.
그렇지만 한 가지 고려를 해본다면, Block/wake up overhead의 문제가 있습니다. 프로세스의 상태를 Ready 상태에서 blocked 상태로 바꾸어야하고, 자원의 반납시에는 반대로 blocked를 Ready 상태로 바꿔주어야하는 오버헤드가 생깁니다, 그래서 만약 Critical Section의 길이가 매우 짧다면, Busy-wait을 하는게 효율적일 수는 있습니다. 하지만 Critical Section이 길다면 Block/wake up overhead이 훨씬 효율적입니다.
3. Deadlock and Starvation
세마포어를 사용할 때, 주의해야할 점이 있습니다.
(1) Deadlock
위처럼 만약 프로세스가 두 개 있고, 세마포어는 S와 Q가 있는데 어떤 일을 하기 위해 S와 Q 두 개 다 획득해야 일을 할 수 있는 환경이 있다고 가정해보겠습니다. 프로세스 0은 S와 Q를 모두 얻어서 반환을 해야하고 이 작업은 프로세스 1에서도 마찬가지입니다.
프로세스 0이 CPU를 얻어 세마포어 S를 획득한 다음 CPU 제어권을 빼앗겨 프로세스 1에게 넘어갔는데, 프로세스 1이 세마포어 Q를 획득하고 프로세스 S를 획득할려고 했더니 이미 프로세스 0이 획득한 상태입니다. 이렇게 되면 프로세스 0이 S를 내놓아야하는데 프로세스 0은 자원 Q를 얻고 작업을 끝내야 S를 반환하기 때문에 영원히 기다려야하는 문제가 발생하는 것입니다.
이렇게 자원이 여러 개일때, 프로세스들이 서로 자원을 놓지 않아 조건을 영원히 충족하지 못할 때를 DeadLock(교착 상태)라고 합니다. 데드락의 해결 방법은 자원을 획득하는 순서를 똑같이 맞춰주는 것입니다.
프로세스 0는 S를 얻고 Q를 얻는 순서로 작업이 진행되는데 이를 프로세스 1도 똑같이 맞춰주면 데드락 문제는 발생하지 않습니다.
(2) Starvation
Starvation은 자원을 얻지 못해 무한히 기다리는 상황을 말합니다. 그래서 위의 Deadlock도 Starvation의 한 종류라고도 볼 수 있습니다. 하지만 여기서의 Starvation은 특정 프로세스들만 자원을 공유하며 다른 프로세스들은 공유를 해주지 않는 것입니다. 이 문제에 대해서는 이후 포스팅에서 등장할 "식사하는 철학자 문제"에서 구체적으로 다시 설명드리겠습니다.
참고자료
[KOCW 이화여대 반효경 교수님 - Process Synchronization 2]
https://core.ewha.ac.kr/publicview/C0101020140404151340260748?vmode=f
반효경 [운영체제] 13. Process Synchronization 2
설명이 없습니다.
core.ewha.ac.kr
[ Chapter5 Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
