Bounded-Buffer Problem(Producer-Consumer Problem)
임시로 데이터를 저장하는 버퍼의 크기가 유한하게 주어진다고 가정한다.
2종류의 프로세스가 여러개 존재한다.(Producer, Consumer)
Producer는 공유 버퍼에 데이터를 하나 만들어서 집어넣는다.
Consumer는 공유 버퍼에 존재하는 데이터를 꺼낸다.
문제점:
두 Producer가 동시에 같은 빈 버퍼에 데이터를 넣으려고 하는 경우
-> 공유 버퍼에 lock을 걸어서 다른 프로세스들의 접근을 막은 후 비어있는 버퍼에 데이터를 집어넣고 lock을 푼다.
두 Consumer가 동시에 같은 버퍼의 데이터에 접근하는 경우
-> 공유 버퍼에 lock을 걸어서 다른 프로세스들의 접근을 막은 후 데이터를 꺼내가고 lock을 푼다.
둘이 동시에 공유 버퍼를 접근하는 것을 막기 위해 공유 버퍼 전체에 lock을 거는 binary semaphore 필요
공유 버퍼가 가득 찬 상태에서 producer가 데이터를 집어넣으려고 하는 경우
-> producer 입장에서는 사용할 수 있는 자원(비어있는 버퍼의 수)이 없는 경우이다. 비어 있는 버퍼가 생길 때 까지 기다려야 한다.(consumer가 꺼내갈 때 까지)
공유 버퍼가 모두 빈 상태에서 consumer가 데이터를 꺼내려는 경우
-> consumer 입장에서는 사용할 수 있는 자원(차 있는 버퍼의 수)이 없는 경우이다. 차 있는 버퍼가 생길 때 까지 기다려야 한다.(producer가 데이터를 채울 때 까지)
버퍼가 가득 차거나 버퍼가 비었을 때 가용 자원의 갯수를 세는 counting semaphore 필요
synchronization variables
semaphore full = 0, empty = n, mutex = 1
producer
do {
...
produce an item in x
...
P(empty); - producer 입장에서는 빈 곳의 수가 자원의 수이므로 P연산으로 확인한다.
P(mutex); - lock을 걸어준다.
...
add x to buffer
...
V(mutex); - lock을 풀어준다.
V(full); - 가득 찬 버퍼가 하나 생긴 것이므로 V연산을 통해 full을 올려준다.
} while(1);consumer
do {
P(full); - consumer 입장에서는 가득 차 있는 버퍼 수가 자원의 수이므로 P연산으로 확인한다.
P(mutex); - lock을 걸어준다.
...
remove an item from buffer to y
...
V(mutex); - lock을 풀어준다.
V(empty); - 빈 버퍼가 하나 생긴 것이므로 V연산을 통해 empty를 올려준다.
...
consume the item in y
...
} while(1);Readers and Writers Problem
2종류의 프로세스(Reader, Writer)와 공유 데이터(DB)가 존재한다.
Reader는 DB에서 데이터를 읽어오고, Writer는 DB에 데이터를 쓴다.
Reader & Writer는 데이터를 쓸 때는 한 번에 하나의 프로세스만이 행동해야하지만(lock을 건다) Producer-Consumer와 다르게 데이터를 읽어올 때는 동시에 여러 프로세스가 행동해도 상관없다.
즉 누군가가 데이터를 읽고 있을 때 Reader가 들어오면 동시에 행동할 수 있게 하고, Writer가 들어오면 기다리게 해야한다.
shared data
int readcount = 0; - 현재 몇명이 데이터를 읽고 있는가를 나타냄
DBSynchronization variables
semaphore mutex = 1; - readcount를 위한 세마포 변수
semaphore db = 1; - DB의 lock에 해당하는 세마포 변수Writer
P(db); - DB에 접근하기 위해 lock을 건다.
...
writing DB is performed
...
V(db); - lock을 풀어준다.Reader
P(mutex); - readcount도 공유 변수이므로 이 값을 변경하기 위해서는 lock을 걸어줘야한다.
readcount++;
if(readcount == 1) - 제일 처음 읽으러 왔다면
P(db); - DB에 lock을 건다(최초가 아니라면 이미 lock이 걸려있기 때문에 lock을 걸 필요가 없다)
V(mutex);
...
reading DB is performed
...
P(mutex);
readcount--;
if(readcount == 0) - 마지막으로 읽고 나가는 프로세스라면
V(db); - DB lock을 풀어준다.(writer가 행동할 수 있도록)
V(mutex);Q. reader가 데이터를 읽고 있을 때 writer, reader 순으로 프로세스가 도착한다면?
-> writer는 기다리지만 reader는 뒤에왔더라도 데이터를 읽을 수 있다. 따라서 모든 reader가 지나고나야지 writer가 행동할 수 있다.(starvation 문제) -> 어느 정도 reader가 지나가면 writer가 진행할 수 있도록 하는 식으로 개선할 수 있다.
Dining-Philosophers Problem
철학자가 원탁에 둘러 앉아있고, 각 철학자들은 생각하는 행동, 밥 먹는 행동 두가지 행동을 할 수 있다.
배가 고파지면 철학자들은 자신의 왼쪽, 오른쪽의 젓가락을 모두 집어서 밥을 먹는다.
배가 불러지면 생각을 하게 된다.
Synchronization variables
semaphore chopstick[5]; - 1로 초기화 되어있다.(동시에 두 명이 잡을 수는 없기 때문)
Philosopher i
do {
P(chopstick[i]); - 왼쪽 젓가락을 잡는 행동(없다면 wait)
P(chopstick[(i + 1) % 5]); - 오른쪽 젓가락을 잡는 행동(없다면 wait)
...
eat(); - 밥먹기
...
V(chopstick[i]); - 왼쪽 젓가락 반납
V(chopstick[(i + 1) % 5]); - 오른쪽 젓가락 반납
...
think(); - 생각
...
} while(1);위의 코드 문제점
- Deadlock 가능성
-> 아무것도 진행되지 못하고 막혀있는 상황(ex. 모든 철학자가 모두 배가고파서 왼쪽 젓가락을 잡아버리면 아무도 오른쪽 젓가락을 잡을 수 없어서 아무도 밥을 먹을 수 없다)
해결 방법
- n-1 명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 젓가락을 두 개 모두 잡을 수 있을 때만 젓가락을 잡을 수 있게 한다.
- 비대칭 방법(짝수 철학자는 왼쪽 젓가락부터 잡도록하고, 홀수 철학자는 오른쪽 젓가락부터 잡도록한다.)
