Producer and Consumer Problem
- 생산자-소비자 문제
- 유한버퍼 문제 (Bounded Buffer Problem)
Readers-Writers Problem - 공유 데이터 베이스 접근 ex) 기차표예약
Dining Philosopher Problem - 식사하는 철학자 문제
생산자-소비자 문제 Producer and Consumer Problem
- 생산자가 데이터를 생산하면 소비자는 그것을 소비
- 예) 컴파일러 > 어셈블러, 파일서버> 클라이언트, 웹서버>웹클라이언트
Bounded Buffer (유한한 버퍼 크기)
- 생산된 데이터는 버퍼에 일단 저장
- 현실 시스템에서 버퍼 크기는 유한
- 생산자는 버퍼가 가득 차면 더 넣을 수 없고, 소비자는 버퍼가 비면 뺄 수 없음
-> 생산자:농부, 버퍼:창고, 농부가 창고에 곡물을 계속 쌓다가 창고가 다 차면 곡물을 넣을 수 없는 것처럼 버퍼도 유한하기 때문에 다 차면 넣지 못함.
코드를 통한 이해
class Test {
public static void main(String[] arg) {
Buffer b = new Buffer(100);
Producer p = new Producer(b, 10000);
Consumer c = new Consumer(b, 10000);
p.start();
c.start();
try {
p.join();
c.join();
} catch (InterruptedException e) {}
System.out.println("Number of items in the buf is " + b.count);
}
}
class Buffer {
int[] buf;
int size;
int count;
int in;
int out;
Buffer(int size) {
buf = new int[size];
this.size = size;
count = in = out = 0;
}
void insert(int item) {
/* check if buf is full */
while (count == size)
;
/* buf is not full */
buf[in] = item;
in = (in+1)%size;
count++;
}
int remove() {
/* check if buf is empty */
while (count == 0)
;
/* buf is not empty */
int item = buf[out];
out = (out+1)%size;
count--;
return item;
}
}
/****** 생산자 ******/
class Producer extends Thread {
Buffer b;
int N;
Producer(Buffer b, int N) {
this.b = b; this.N = N;
}
public void run() {
for (int i=0; i<N; i++)
b.insert(i);
}
}
/****** 소비자 ******/
class Consumer extends Thread {
Buffer b;
int N;
Consumer(Buffer b, int N) {
this.b = b; this.N = N;
}
public void run() {
int item;
for (int i=0; i<N; i++)
item = b.remove();
}
}‼️ 문제 발생
실제 코드 수행 시, 잘못된 결과가 나옴
-> 무한루프 또는
-> count != 0
❓이유
동기화 문제
공통 변수 count, buf[] 에 대한 동시 업데이트
임계구역에 대한 동시 접근 때문
💡해결방법
- 이전에 배웠던 세마포를 활용하여 동시 접근을 방지하고, 하나의 프로세스만 활용해야 함.
- 1의 방법을 사용하면 busy wait 이라는 문제가 또 발생
생산과 서비를 하기 전, 버퍼가 가득 찼는 지 비웠는 지 무한 반복문을 돌며 확인하기 때문에 매우 비효율적 => 세마포를 활용하여 해결
2-1. 반복문 대신, empty , full 세마포 생성
초기값
- empty는 초기화할 때 버퍼는 모두 비어있으므로 버퍼의 크기로 초기화
- full은 초기 버퍼에는 아무런 데이터가 없으므로 0으로 초기화
방법
- 데이터를 생성하기 전에 비어있는 공간이 있는지 확인
- 없다면 empty세마포의 value값이 -1이 되므로 block이 되고, 있다면 임계구역 내부로 진입하여 데이터를 생성
- 생성이 완료되면 full세마포의 value값을 1 증가
코드
class Buffer {
int[] buf;
int size;
int count;
int in;
int out;
Semaphore mutex, full, empty;
Buffer(int size) {
buf = new int[size];
this.size = size;
count = in = out = 0;
mutex = new Semaphore(1);
full = new Semaphore(0);
empty = new Semaphore(size);
}
void insert(int item) {
try {
empty.acquire(); // 버퍼의 비어있는 공간을 1 감소시킨다.(비어있는 공간이 없으면 block)
mutex.acquire();
buf[in] = item;
in = (in+1)%size;
count++;
mutex.release();
full.release(); // 버퍼의 찬 공간을 1 증가시킨다.
} catch(InterruptedException e) {}
}
int remove() {
try {
full.acquire(); // 버퍼의 찬 공간을 1 감소시킨다.(버퍼가 모두 비어있으면 block)
mutex.acquire();
int item = buf[out];
out = (out+1)%size;
count--;
mutex.release();
empty.release(); // 버퍼의 비어있는 공간을 1 증가시킨다.
return item;
} catch(InterruptedException e) {}
return -1;
}
}이 코드를 실행시켜보면 정상적으로 결과값이 0이 출력되는 것을 확인할 수 있다.
Readers-Writers Problem
- 공통 데이터베이스에 접근하는 경우 발생하는 문제
- 하나의 DB에 여러 프로세스(reader, writer)접근 가능
- 데이터베이스는 임계구역으로 설정
-> 한 번에 한 개의 프로세스만 접근가능하도록 설정, 하지만 이 방법은 비효율적
-> reader는 읽기만 하는 프로세스이므로, 여러 reader프로세스가 동시에 접근하는 것을 허용
-> writer는 내용을 바꾸는 프로세스이므로, mutual exclusion 보장
- The first R/W problem (readers-preference)
: Reader 우선권, reader1이 읽고 있을 때 writer1 접근X 하지만 다른 reader2 접근 가능 - The second R/W problem (writers-preference)
: Writer 우선권 - The Third R/W problem
: 우선권 X
Dining Philosopher Problem
식사하는 철학자 문제
- 5명의 철학자, 5개의 젓가락, 생각 → 식사 → 생각 → 식사 ...
- 식사하려면 2개의 젓가락 필요
- 젓가락은 한 철학자가 가져가면 다른 철학자는 이 젓가락을 사용할 수 없음
-> 한 젓가락에 동시에 접근할 수 있는 철학자는 한 명뿐이므로 젓가락은 세마포로 만들 수 있다(number of permit = 1) - 한 철학자가 식사를 하려고 하면, 왼쪽 젓가락과 오른쪽 젓가락 순서로 가져가고, 식사가 끝나면 동일하게 왼쪽 젓가락, 오른쪽 젓가락 순서로 내려놓는다.
코드
import java.util.concurrent.Semaphore;
class Philosopher extends Thread {
int id; // philosopher id
Semaphore lstick, rstick; // left, right chopsticks
Philosopher(int id, Semaphore lstick, Semaphore rstick) {
this.id = id;
this.lstick = lstick;
this.rstick = rstick;
}
public void run() {
try {
while (true) {
lstick.acquire();
rstick.acquire();
eating();
lstick.release();
rstick.release();
thinking();
}
}catch (InterruptedException e) { }
}
void eating() {
System.out.println("[" + id + "] eating");
}
void thinking() {
System.out.println("[" + id + "] thinking");
}
}
class Test {
static final int num = 5; // number of philosphers & chopsticks
public static void main(String[] args) {
int i;
/* chopsticks */
Semaphore[] stick = new Semaphore[num];
for (i=0; i<num; i++)
stick[i] = new Semaphore(1);
/* philosophers */
Philosopher[] phil = new Philosopher[num];
for (i=0; i<num; i++)
phil[i] = new Philosopher(i, stick[i], stick[(i+1)%num]);
/* let philosophers eat and think */
for (i=0; i<num; i++)
phil[i].start();
}
}5개의 젓가락 세마포와 5명의 철학자 쓰레드를 생성
각 철학자 쓰레드에는 무한 반복문으로 왼쪽 젓가락과 오른쪽 젓가락을 순서대로 집은 후 식사를 하고(몇 번 철학자가 식사했다는 것을 화면에 출력), 다시 왼쪽 젓가락, 오른쪽 젓가락 순으로 내려놓고 생각을 한다.
‼️ 하지만 여기서 모든 철학자가 동시에 식사를 하려고 왼쪽 젓가락을 들면, 남아있는 젓가락은 더 이상없고 모든 철학자가 반대편 젓가락을 들기 위해 기다리고 있다. 하지만 식사할 수 있는 철학자는 없으므로 아무도 젓가락은 내려놓지 않고 하염없이 기다리고 있다.
이러한 상황을 교착상태(deadlock) 라고 함.
참고
강의 http://www.kocw.net/home/search/kemView.do?kemId=978503
정리 https://velog.io/@codemcd/운영체제OS-9.-프로세스-동기화-2
