목차
이전 글에서는 프로세스 동기화의 문제점과 이 문제를 해결하기 위한 초기 알고리즘 3가지를 알아보았다.
Synchronization Hardware는 앞서 나온 알고리즘들의 한계점을 보안해 준다.
이제는 좀 더 추상적인 동기화 문제 해결 방안 두 가지를 알아본다.
바로 세마포어 (Semaphore)와 모니터 (Monitor)이다.
이 방안들은 프로그래머로 하여금 더욱 쉽고 효율적으로 문제를 해결할 수 있도록 도와준다.
Semaphore
➳ 이전 글에서 나온 방식들을 추상화시킨다.
➳ Semaphore S
• integer variable
• 아래 두 가지 atomic 연산에 의해서만 접근이 가능하다.
P 연산은 자원을 획득하는 과정이고, V 연산은 자원을 반납하는 과정이다.
예를 들어 Semaphore 5라면 자원이 5라는 의미이다. 만약 프로세스 5개가 동시에 P 연산을 하면 모든 자원을 쓰고 있게 된다. 다른 프로세스가 자원을 획득하고 싶어도 자원의 여분이 없다면 기다려야 한다. 자원의 사용은 P 연산과 V 연산 사이에서 이루어진다. 자원을 다 사용했다면 V 연산을 통해 자원을 내놓게 된다. S는 자원을 count 한다고 볼 수도 있다.
Critical Section of n Processes
mutex : mutual exclusion의 줄임말
여기에서도 쓸데없이 while문을 도는 busy-wait 문제가 있다. 이는 어떻게 해결하면 좋을까 ?
Block / Wakeup Implementation
value 값과 줄을 세우는 list 구조를 둔다. 만약 Semaphore 여분이 없어 기다려야 한다면 변수 L에 대해서 프로세스를 block 시키고, 줄을 세워서 기다리게 한다. 이는 busy-wait 문제를 해결해 준다. busy-wait는 spin lock이라고도 부른다. 따라서 block/wakeup 방식을 sleep lock이라고 부르기도 한다.
이제 Block/Wakeup 방식으로 Semaphore 연산을 정의해 보자 !
P 연산은 자원을 획득하므로 value 값에 1을 빼준다.
S.value가 음수라면 S.L (Semaphore list)에 Block 시킨다.
V 연산은 자원을 내놓으므로 value 값에 1을 더한다.
S.value가 0 이하라면 S.L에서 하나를 꺼내 깨워준다.
Which is better ?
" busy-wait VS block/wakeup "
일반적으로는 block/wakeup이 훨씬 낫다. 하지만 block 하고 wakeup 하는 것도 어떻게 보면 overhead라고 볼 수도 있다.
➳ block/wakeup overhead VS critical section 길이로 판단한다.
• critical section의 길이가 긴 경우 block/wakeup이 적당하다.
• critical section의 길이가 매우 짧은 경우 block/wakeup overhead가 busy-wait overhead보다 더 커질 수가 있다.
• 일반적으로는 block/wakeup 방식이 더 좋다.
💡
사실 길이보다는 얼마나 경쟁이 치열한가로 이해하는 것이 올바르다.
경쟁이 치열하다면 block/wakeup이, 별로 치열하지 않다면 busy-wait이 더 좋을 수가 있다는 것이다.
Two Types of Semaphores
Counting semaphore
➳ 도메인이 0 이상인 임의의 정수값
➳ 주로 resource counting에 사용
Binary semaphore (= mutex)
➳ 0 또는 1 값만 가질 수 있는 semaphore
➳ 주로 mutual exclusion (lock / unlock)에 사용
Semaphore는 프로그래밍을 조금만 잘 못 해도 큰 문제가 생길 수가 있다.
바로 Deadlock과 Starvation이다.
다음은 이러한 Semaphore의 문제점에 대해서 알아보자 !
Deadlock and Starvation
Deadlock
" 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다. "
e.g. S와 Q가 1로 초기화된 semaphore라고 하자.
세마포어 변수 S와 Q, 두 자원 모두 있어야만 작업이 가능한 경우를 생각해 보자. S와 Q를 동시에 얻어서 작업을 하고, 동시에 반납해야 한다. P0가 S를 얻은 상태에서 P1에게 CPU를 빼앗겼다고 해보자. 그리고 P1은 Q를 획득했다. P0은 S를 획득하였고, P1은 Q를 획득한 것이다. 이 상태에서 P1은 S가 없으므로 계속 실행할 수가 없다. P0으로 넘어가도 S는 있지만 Q가 없으므로 실행이 불가하다. 이처럼 각각 프로세스가 자원을 하나씩만 가져서 영원히 그 아래로는 수행이 안 되는 문제점이 발생할 수 있다.
프로세스는 자원을 획득하면 무조건 일을 다 끝난 다음에서야 자원을 내놓는다는 점이 바로 이 문제의 근본적인 이유이다. 다른 프로세스가 또 다른 자원을 가지고 있으니 어차피 자원을 가지고 있어 봐야 소용이 없다고 생각해 자원을 내어준다면 애초에 이런 문제가 안 생길 것이다.
Starvation
" indefinite blocking이다. 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상이다. "
만약 아래 그림처럼 획득하는 자원의 순서를 동일하게 정해준다면 위와 같은 문제가 발생하지 않을 것이다 !
Classical Problems of Synchronization
공유 데이터에 접근 시 발생하는 전통적인 동기화의 문제점 세 가지에 대해서 알아보자.
해결하는 방안은 Semaphore를 이용한다.
➳ Bounded-Buffer Problem (Producer-Consumer Problem)
➳ Readers-Writers Problem
➳ Dining-Philosophers Problem
1. Bounded-Buffer Problem (Producer-Consumer Problem)
Bounded-Buffer는 크기가 유한한 공유 buffer이다. 즉, 여러 프로세스가 동시에 접근할 수 있다. 여기서 프로세스는 producer(생산자) process와 consumer(소비자) process, 두 가지로 나뉜다. 이 프로세스들이 공유 buffer에서 하는 일은 무엇일까 ? producer process는 데이터를 만들어서 buffer에 넣어주는 역할을 한다. consumer process는 데이터를 꺼내가는 역할을 한다.
producer process는 빈 버퍼를 발견하고, '여기에다 데이터를 넣어야지 !' 생각하는 찰나 CPU를 빼앗겼다고 해보자. 다른 producer process도 똑같이 빈 버퍼를 발견하고 똑같은 생각을 한다면 데이터 유실의 문제가 생긴다.
이 문제를 해결하기 위해서는 공유 buffer를 접근할 때 lock을 걸고, 작업이 끝나면 lock을 풀어주는 방법을 사용한다. 이는 consumer process도 마찬가지이다.
✨ Shared data
- buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
✨ Synchronization variables
- mutual exclusion ➳ Need binary semaphore (shared data의 mutual exclusion을 위해)
- resource count ➳ Need integer semaphore (남은 full/empty buffer의 수 표시)
코드로 보면 다음과 같다.
mutex는 lock을 거는 세마포어 변수이다.
2. Readers-Writers Problem
➳ 한 process가 DB에 write 중일 때 다른 process가 접근하면 안 된다.
➳ read는 동시에 여럿이 해도 된다.
➳ solution
• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해 준다.
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
• Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
✨ Shared data
- DB 자체
- readcount ➳ 현재 DB에 접근 중인 Reader의 수
✨ Synchronization variables
- mutex ➳ 공유 변수 readcount를 접근하는 코드 (critical section)의 mutual exclusion 보장을 위해 사용한다.
- db ➳ Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할이다. (역시 lock을 걸고 푼다.)
코드는 다음 그림과 같다.
이는 starvation이 발생할 수 있다는 문제가 있다. Reader가 계속 들어온다면 아무리 Writer가 먼저 도착했어도 영영 기다려야 할 수가 있다. 어떻게 하면 이 문제를 해결할 수 있을까 ? 일정 시간 내 접근한 Reader만 접근이 가능하도록 하고, 일정 시간 후에는 기다리고 있는 Writer에게도 접근 기회를 주는 방식으로 starvation 문제를 해결할 수 있다.
3. Dining-Philosophers Problem
젓가락 다섯 짝이 공유 데이터이고, 다섯 명의 철학자는 굶어 죽으면 안 된다. 철학자는 생각을 할 수도 있고, 밥을 먹을 수도 있다. 만약 모든 철학자가 동시에 배고파서 동시에 왼쪽에 있는 젓가락 한 짝을 집었다면 오른쪽에 있는 나머지 한 짝을 모두 집을 수 없으므로 모두 밥을 먹을 수 없는 사태가 발생한다.
❓ 문제점
➳ 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락 한 짝을 집어버린 경우 Deadlock 가능성이 있다.
❗ 해결 방안
➳ 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
➳ 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
➳ 비대칭 : 짝수 (홀수) 철학자는 왼쪽 (오른쪽) 젓가락부터 집도록 한다. 획득하는 자원의 순서를 정해주는 것이다.
두 번째 해결 방안을 코드로 살펴보면 다음과 같다.
Monitor 방안으로 Dining-Philosophers Problem를 해결한 코드를 semaphore 방안으로 고스란히 옮긴 것이다.
Semaphore의 문제점
➳ 코딩하기 힘들다.
➳ 정확성 (correctness)의 입증이 어렵다.
➳ 자발적 협력 (voluntary cooperation)이 필요하다.
➳ 한 번의 실수가 모든 시스템에 치명적인 영향을 준다.
그렇다면 좀 더 쉽게 프로세스 동기화를 할 수는 없을까 ?
이 생각으로부터 나온 방안이 바로 Monitor이다.
Monitor
동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
Monitor는 공유 데이터 동시 접근에 대한 모든 책임을 진다. 하지만 Semaphore는 그렇지 않다. Semaphore는 P 연산이나 V 연산을 통해 원자적으로 자원의 남은 개수를 count 하는 연산을 제공한다. 실제 동기화 문제는 프로그래머의 몫이다. 공유 데이터에 접근하기 전에 프로그래머가 lock을 걸고, 접근이 끝나면 프로그래머가 lock을 풀어주어야 한다.
Monitor는 공유 데이터에 대한 접근은 오직 Monitor 안에 정의된 함수를 통해서만 접근이 가능하도록 하고, Monitor 안에서 active 하게 실행되는 프로세스는 하나로 제한한다. 따라서 프로그래머는 lock을 걸 필요 없이 Monitor 안에 있는 코드로 데이터에 접근하도록 하면 알아서 동기화가 된다.
아래는 Monitor를 추상적으로 그린 것이다.
하나의 프로세스가 이미 Monitor 안에서 작업을 수행 중이라면 접근을 하고 싶어 하는 또 다른 프로세스는 Queue에 줄을 서서 기다리도록 한다.
Monitor의 특징
➳ 모니터 내에서는 한 번에 하나의 프로세스만이 활동이 가능하다.
➳ 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.
➳ 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용한다. ( condition x, y; )
➳ condition variable은 wait와 signal 연산에 의해서만 접근이 가능하다.
x.wait();
➳ x.wait()를 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
x.signal();
➳ x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다. suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.
condition variable은 semaphore 변수와 비슷한 역할을 한다. 자원의 여분이 있을 때에는 그냥 수행을 하도록 하고, 없을 때에는 잠들도록 한다. 잠들도록 한다는 것은 queue에 줄을 세워 blocked 상태로 만든다는 의미이다. x라는 자원이 없다면 x.wait()를 호출하고, condition variable은 x라는 queue에 줄을 서서 잠들도록 하는 역할을 담당한다. 만약 x라는 자원을 다 사용하고 반환하는 프로세스가 있다면 x.signal()을 호출해 혹시 x 자원의 여분이 없어 잠들어있는 프로세스가 있다면 깨우도록 한다.
이제 Monitor를 사용해 동기화 문제를 해결하는 예를 살펴보자 !
앞서 나온 Semaphore를 사용한 예와 비교하면 이해하는데 도움이 된다.
1. Bounded-Buffer Problem (Producer-Consumer Problem)
full.signal()을 호출했을 때, 만약 줄 서서 기다리고 있는 프로세스가 없다면 그냥 아무 일도 안 일어난다.
2. Dining-Philosophers Problem
공유 데이터인 다섯 짝의 젓가락과 다섯 명의 철학자 상태 변수가 monitor 함수 안에 있다. condition variable은 철학자가 밥을 먹고자 할 때 젓가락 두 짝을 모두 잡을 수 있는 상태라면 밥을 먹도록 하고, 그렇지 않은 상태라면 큐에 잠들어서 기다리도록 한다.
'CS > OS' 카테고리의 다른 글
| 데드락 (Deadlock) (0) | 2022.12.30 |
|---|---|
| 프로세스 동기화 (Process Synchronization) (0) | 2022.12.28 |
| CPU 스케줄링 (1) | 2022.12.26 |
| 프로세스의 생성과 종료 with System Call (0) | 2022.12.19 |
| 프로세스 (Process)와 스레드 (Thread) (0) | 2022.12.14 |