목표
- Classical Problems of Syncronization
- Bounded-Buffer Problem
- Readers-Writers Problem
- Dining-Philosophers Problem
- Monitor
Classical Problems of Syncronization
01. Bounded-Buffer Problem
Buffer: 데이터를 임시로 저장하는 공간.
Bounded-Buffer: 버퍼의 크기가 유한함.
Producer-Consumer 문제
process 두가지 종류
이 문제에는 process가 두가지 종류가 있음.
- Producer 프로세스
- 여러개 있음
- 역할: 버퍼에다가 공유 데이터를 만들어서 집어 넣음
- 주황색 : producer가 데이터를 만들어서 집어넣은 상태
- Consumer 프로세스
- 여러개 있음
- 역할: 버퍼에 있는 데이터 빼가서 사용
- 비어있음: 애초에 비어있든지, cousumer가 데이터를 꺼낸 상태
Synchronization 문제 3가지
이 곳에서 Synchronization 관련한 어떤 문제가 발생할 수 있을까?
- 공유 버퍼이기 때문에 producer가 동시에 도착해서 비어있는 하나의 버퍼에 동시에 데이터를 만들어 집어넣는 문제
=> producer가 비어있는 buffer를 확인하고, 데이터를 집어넣는걸 그냥 하지않고,
buffer에다가 lock을 걸어서 다른 process들의 접근을 막은 다음에
buffer에다가 데이터를 넣고
그 작업이 끝나면
lock 풀고 다른 producer나 consumer가 버퍼에 접근하게 한다.
- consumer가 동시에 같은 데이터를 꺼내가려고 할 때
=> buffer에다가 lock을 걸어서
데이터를 꺼내가고,
lock을 풀고
- buffer가 유한하기 때문에 생기는 문제
buffer에 data가 다 찼을 때, consumer는 안오고 producer가 또 올 때
=> producer 입장에선 더이상 생산할 수 있는 자원이 없는 상태임/
- producer 입장에선 비어있는 자원의 개수가 counting 해야하는 자원이다.
- consumer 입장에서 자원은 내용이 들어있는 buffer다.
semaphore가 역할 2가지
- 공유 버퍼에 접근하는 것을 막기 위해서 버퍼 전체에다가 lock을 걸어서 나 혼자 접근 가능하게 lock을 걸고, 접근이 끝났으면 lock을 풀어줘야 한다.
- 버퍼가 가득 차거나 비었을 때 가용자원의 개수를 세는 counting semaphore 용도
semaphore 변수
semaphore 변수 3가지
- full : 내용이 들어있는 개수를 세기위한 변수
- 처음에 full은 0개야. 채워져있는게 없다는 뜻임.
- empty : 비어있는 buffer를 세기위한 변수
- 처음에 empty는 n개야. 모두다 비어있다는 뜻임.
- mutex : lock을 걸고 풀기 위한 변수
생산자 process들은 어떤 절차를 거치는지
item x를 만든 다음 이걸 공유 버퍼에 넣고 싶은데, 그 전에 ~~
빈 버퍼가 있는지 확인부터 한다.
버퍼에다가 데이터를 집어넣기 위해서 lock을 건다.
버퍼에다가 데이터를 집어넣는다.
버퍼에 걸었던 lock을 푼다.
내용 들어있는 버퍼 개수 1증가 시키는게 full에 대한 V연산
소비자는 반대로 ~! ...아래 사진 참고 !
02. Readers-Writers Problem
Readers-Writer 문제는 process가 2문제가 있음.
- 읽는 process
- 쓰는 process
여기서는 공유 data를 DB로 명명. (읽고 쓰는 문제는 보통 DB에서 일어나기 때문)
그런데 DB에서는,
- 쓰는 작업은 여러 Process가 접근하면 안되지만,
- 읽는 작업은 여러 Process가 접근해도 괜찮다.
Writer
- DB는 공유데이터를 뜻함. : 데이터에 접근하려면 lock을 걸어야함.
- db: DB에 대한 lock에해당하는 semaphore 변수 : 공유 데이터 DB에 접근하기 위해 P연산 lock을 건 것임.
Reader
- 읽는 작업은 여러명이 해도 되는데 lock을 걸어버리면 비효율적
- readcount: reader 몇명이 읽고 있는지 세는 변수 , 이것도 공유변수라서 이에 대한 lock을 거는
mutex
라는 semaphore 변수가 있는거야. (이 변수를 lock 걸지 않으면 여러 reader가 와서 혼잡해질 때 readcount를 제대로 세지 않는 경우가 생길 수 있음.) , 내가 만약 readcount를 최초로 올린 reader라면 DB에다가 lock을 거는 P(db)연산을 해야함.
- 빠져나갈 때, 내가 만약 마지막으로 읽었던 process라면 readcount가 0이 되고 DB에 걸었던 lock을 푸는 V(db) 연산을 한다.
Starvation 문제
- Reader가 DB에서 읽고 있는데, 또 다른 Reader와 Writer가 왔다. 이미 Reader가 읽고 있다면 Reader가 들어오고, Writer는 기다려야 한다. 그런식이면 마지막Reader가 나가려고 하는데 또 Reader 1000개가 들어오면, Writer의 starvation 문제가 있음.
=> 어느정도 많이 기다리면 이제 Writer가 접근할 수 있게 한다.
03. Dining-Philosophers Problem
철학자들은 밥을 먹거나 생각하거나
밥 먹기 전에 왼쪽 젓가락, 오른쪽 젓가락 잡는 연산
밥 먹고 나면, 왼쪽 젓가락이랑, 오른쪽 젓가락을 놓는 연산
- 철학자들은 일단 왼쪽 젓가락 잡았으면 밥 먹을 때까지. 절대 놓지 않아요
=> 모두가 왼쪽 젓가락 잡고 안놔
=> Deadlock
해결 방안
- 4명만 동시에 앉아라.
- 젓가락 양쪽 잡을 수 있을 때만 권한을 준다.
- 각 철학자마다 우선순위의 젓가락을 잡아야만 다음 젓가락 잡을 수 있게 권한을 준다.
철학자는 젓가락을 잡고pickup
, 먹고eat
, 젓가락 내려놓고pickdown
, 생각한다think
-
semaphore self[i] = 1
: 철학자 i번째 사람이 젓가락 잡을 권한 있다는 뜻 .
ex) semaphore self[i] = 0;
: 젓가락 잡을 권한 없다는 뜻.
-
enum (thinking, hungry, eating) state[5]
: 다섯명의 철학자 상태를 나타내는 공유 변수
-
semaphore mutex = 1
: i번째 철학자의 상태를 바꾸는 건 본인 뿐 아니라, 옆 철학자(i-1, i+1)도 가능함.
- 따라서, state는 공유변수이고,
- 공유변수에 대한 동시접근을 막기 위해서
mutex
가 있음.
mutex
는 lock을 나타냄
Monitor
예) 프로그래머의 한번의 실수가 모든 시스템에 치명적
- V연산과 P연산 순서를 바꿨을 때 => 둘이 동시에 들어가는 문제 발생.
예2) P연산만 두번했을 때 => 영원히 어느 프로세스도 Critical section에 못들어감.
이런 문제 때문에 Monitor
제공
monitor는 프로그래밍 언어 차원에서 synchronization 문제
를 해결하는 high-level synchronization construct
객체지향 프로그래밍 언어들을 보면 객체를 중심으로 operation 들이 정의가 됨. 그런거에 기반해서 monitor는 이런식으로 공유 data
에 접근하기 위해서는 이 monitor라고 정의된 내부의 procedure
를 통해서만 가능하다.
예를들어, 이 공유데이터가 안에 있으면 밖에서 아무나 접근할 수 있는게 아니라 monitor 안에다가 shared data
와 그것에 접근할 수 있는 procedure 즉, operations
를 정의해놓는다.
monitor는 원천적으로 내부에 있는 procedure는 동시에 여러개 실행이 안되도록 통제를 한다. => 프로그래머 입장에선 lock을 걸 필요가 사라짐
semaphore처럼 lock을 걸 필요는 없어졌지만, 여전히 자원의 개수를 세는건 필요하다. 왜냐하면 자원이 없으면 프로세스를 기다리게 함. condition variable
- 자원의 개수를 세는
condition x
;
- 자원이 없으면 기다리는 함수
x.wait()
- 접근 다하고 빠져나가면서 기다리는 프로세스 있으면 깨우는? 함수
x.signal()
생산자-소비자 문제의 semaphore 코드를 monitor 코드로 conversion
아까 여기선 lock을 걸고 푼다.
하지만, monitor는 lock을 걸고 풀 필요 없음.
공유 buffer가 monitor 안에 정의되어 있음.
생산하거나 소비하는 작업을 하기 위해서는 monitor 내부 코드를 실행해야함.
그러면 생산자든, 소비자들 하나의 코드만 monitor 안에서 활성화되기 때문에 굳이 lock을 걸지 않아도 또 다른 생산자나, 소비자가 접근해서 생기는 문제를 고려할 필요 없다.
만약에 비어있는 버퍼가 없다면, 버퍼 기다리는 줄에 줄서게 blocked 상태로 보냄
비어있는 버퍼가 있다면, 그냥 버퍼에다가 내용을 하나 넣어주면 됨.
그 작업이 끝났으면 버퍼 없어서 잠들어있던 프로세스를 깨워주는 코드
- 프로그래머한테 semaphore보다 monitor가 더 쉽다.