프로세스 동기화의 프로그램적 해결법의 충족 조건
-
Mutual Exclusion (상호배제)
프로세스 Pi가 Critical Section부분을 수행 중이면 다른 모든 프로세스들은 그들의 Critical Section에 들어가면 안된다. -
Progress(진행)
아무도 Critical Section에 있지 않은 상태에서 Critical Section에 들어가고자 하는 프로세스가 있으면 Critical Section에 들어가게 해주어야한다. -
Bounded Waiting(유한 대기)
프로세스가 Critical Section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다.
가정
- 모든 프로세스의 수행 속도는 0보다 크다.
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
🎢 Algorithm 1
Mutual Exclusion(상호배제) 조건을 만족하지만 Progress / Bounded Waiting 조건을 만족하지 못할 수 있음.
🎢 Algorithm 2
flag 변수를 사용해 Critical Section에 들어가고 싶은지 의사표현을 한다. 이 알고리즘의 문제는 Critical Section에 들어가기 전에 눈치게임으로 아무도 못들어 갈 수 있음
🎢 Algorithm 3
알고리즘 1, 2에서 봤던 turn, flag 변수를 모두 사용한다.
Mutual Exlusion / Progress / Bounded Waiting 3조건을 모두 만족한다.
하지만 Busy Waiting(= Spin Lock) 문제가 발생할 수 있음
while문 조건을 만족하지 못할 때는 쓸데 없이 계속 while문을 돌게 됨
Synchronization Hardware
I/O가 하나의 instruction으로 해결 가능하다면 프로세스의 동기화 문제가 발생할 가능성이 적음. 왜냐하면 cpu에서 instruction을 실행하는 동안 다른 프로세스한테 cpu를 뺏길 일이 없기 때문에 하지만 하나의 instruction으로 I/O를 해결할 수 없기 때문에 문제 발생!
하드웨어적으로 하나의 instruction만 주어지면 문제는 간다하게 해결된다.
실제 하드웨어에서는 Test_and_Set이라는 자체 instruction을 제공한다.
Semaphores
추상 자료형 :
여기에서 P 연산은 세마포어를 획득하는 과정(공유 데이터를 획득) -lock
V연산은 공유 데이터를 다 사용하고 반납하는 연산 - unlock
프로세스가 잠들기 전에(Block) S.value-- 를 얻고 잠들기 때문에 내가 S.value++ 자원을 내놓고도 S.value <=0 일 경우 기다리면서 잠들어 있는 프로세스가 있다는 의미
Busy-Wait vs Block / Wakeup
- Blcok / Wake up over head vs Critical Section 길이
- Critical Section의 길이가 긴 경우 Block / Wake up이 적 당
- Critical Section의 길이가 매우 짧은 경우 Block / Wake up overhead가 Busy-Wait overhead보다 더 커질 수 있음
- 일반적으로는 Block / Wake up 방식이 더 좋음
Two Types of Semaphores
- Counting Semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting에 사용
- 자원의 개수가 여러개 있어서 여분이 있으면 가져다 쓸 수 있음. 여분의 자원은 카운팅하는 용도로 사용
- Binary Semaphore(=mutex)
- 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion(lock / unlock)에 사용
Deadlock and Starvation 문제
여기서 두 프로세스가 얻는 자원의 순서를 동일하게 하면 Deadlock 문제를 해결할 수 있음
Classical Problems of Synchronization
- Bounded-Buffer Problem(Producer-Consumer Problem)
- Readers and Writers Problem
- Dining-Philosophers Problem
Bounded-Buffer Problem
buffer : 임시로 데이터를 저장하는 공간. 버퍼의 크기는 유한함.
주황색 버퍼는 프로듀서(생산자)가 데이터를 만들어 넣어놓은 것
여기서 어떤 동기화 문제가 일어날 수 있을까?
한가지 문제는 공유 버퍼이다보니까
두 개의 생산자가 동시에 도착해서 같은 버퍼 공간에 작업할 경우 문제 발생
소비자 둘이 동시에 도착해서 같은 버퍼 공간에 있는 데이터를 꺼내려 할 때
이런 문제 발생을 방지하기 위해서는 생산자와 소비자가 작업하기 전에 lock을 걸어서 작업
버퍼가 다 차있는데 생산자가 데이터를 만들어 넣고자 할 때
소비자가 데이터를 가져가려 하는데 모든 공유버퍼가 비었을 때
생산자는 버퍼에 데이터를 채워 넣었을 때 Full buffer 수 하나 증가
소비자는 버퍼에서 데이터를 빼갔을 때 empty buffer 수를 하나 증가
위 내용을 의사코드(sudo code)로 표현한 것은 위와 같음
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 자체를 올바르게 접근하게 하는 역할
Read를 할 때 lock을 걸고 다른 Reader들이 접근을 못하게 하는 것은 너무 비효율적이다. Read는 동시에 여럿이 해도 된다. 하지만 lock을 걸지 않을 경우 Write 작업이 발생할 수 있음으로 lock을 걸기는 해야한다. 하지만 Reader의 접근은 허용해주어야 한다. Reader는 접근했을 때 readcount라는 변수를 변경한다.
최초로 진입하는 Reader가 lock을 건다. 그 이후 도착하는 Reader들은
뮤텍스와 스몰디비는 lock을 걸기 위한 바이너리 세마포어
뮤텍스는 readcount 공유데이터에 lock을 걸기 위한 세마 포어
Starvation이 발생할 수 있음
모든 Reader가 빠져나가야 Writer가 진입할 수 있는데 만약 마지막 Reader 하나를 남기고 또 100개의 Reader가 들어오면 Writer는 계속 기다릴 수밖에 없음
Dining-Philosophers Problem
배가 고파지면 왼쪽과 오른쪽 젓가락을 집어 식사를 한다.
- solution의 문제점
- Deadlock 가능성이 있다.
- 예를 들어 모든 철학자가 동시에 배가 고파져서 모두 왼쪽 젓가락을 집어버린 경우
- 해결 방안
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
- 비대칭
짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 설계
위 코드는 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 설계한 것이다.
왼쪽 철학자도 배고프지 않고 오른쪽 철학자도 배고프지 않고 내가 배고픈 상태일 때 젓가락을 집을 수 있게 한다.
