Note생산자가 데이터를 생산하면 소비자가 그것을 소비하는 문제
예를 들어
하는 등의 케이스가 있다.
생산자가 생산한 데이터를 소비자가 한 번에 전부 소비하는 경우는 거의 없다. 따라서 생산된 데이터는 버퍼 (Buffer)라는 메모리 저장 공간에 저장되고 소비자가 필요에 따라 꺼내 쓴다.
하지만 현실의 시스템에서 버퍼의 크기는 무한하지 않다. 따라서 버퍼가 가득차게 되면 생산자는 더이상 데이터를 넣을 수 없다. 또한 버퍼가 비어있으면 소비자는 데이터를 꺼내 쓸 수 없다. 이렇듯 유한한 크기의 버퍼를 Bounded Buffer라고 한다.
class Test {
{
();
(b, );
(b, );
p.start();
c.start();
{
p.join();
c.join();
} (InterruptedException e) {
Thread.currentThread().interrupt();
}
System.out.println( + b.count);
}
}
{
[] buf;
size;
count;
in;
out;
Buffer( size) {
buf = [size];
.size = size;
count = in = out = ;
}
{
(count == size);
buf[in] = item;
in = (in+)%size;
count++;
}
{
(count == );
buf[out];
out = (out+)%size;
count--;
item;
}
}
{
Buffer b;
N;
Producer(Buffer b, N) {
.b = b; .N = N;
}
{
( i=; i<N; i++)
b.insert(i);
}
}
{
Buffer b;
N;
Consumer(Buffer b, N) {
.b = b; .N = N;
}
{
item;
( i=; i<N; i++)
item = b.remove();
}
}
크기가 100인 버퍼를 생성하고, 생산자와 소비자 역할을 맡은 2개의 스레드를 선언한다. 이후 각각 10000번씩 데이터를 생산하고 소비한다. 정상적으로 동작한다면 결과값 count는 0이 되어야 한다.
하지만 기대와 달리 결과값은 무한 루프에 빠지거나 count가 이상한 값으로 출력된다.
그 이유는 역시 임계 구역 문제 때문이다. 생산자와 소비자 스레드 모두가 공통 변수인 count와 buf[]를 동시에 업데이트 하기 때문이다.
이 역시 세마포어를 통한 상호 배타 (Mutual Exclusion)을 통해 해결할 수 있다. 세마포어를 통해 2개의 스레드가 임계 구역에 동시에 접근하는 것을 방지하도록 한다.
class Buffer {
int[] buf;
int size;
int count;
int in;
int out;
Semaphore mutex;
Buffer(int size) {
buf = new int[size];
this.size = size;
count = in = out = 0;
mutex = new Semaphore(1);
}
void insert(int item) {
while (count == size);
try {
mutex.acquire();
buf[in] = item;
in = (in+1)%size;
count++;
mutex.release();
} catch(InterruptedException e) {
// 학습용 예제: 실제 코드에서는 적절한 인터럽트 처리 필요
Thread.currentThread().interrupt();
}
}
int remove() {
while (count == 0);
try {
mutex.acquire();
int item = buf[out];
out = (out+1)%size;
count--;
mutex.release();
return item;
} catch(InterruptedException e) {
// 학습용 예제: 실제 코드에서는 적절한 인터럽트 처리 필요
Thread.currentThread().interrupt();
}
return -1;
}
}
다음과 같이 임계구역에 접근하는 insert(), remove()에 세마포어를 추가하여 상호 배제를 구현한다.
하지만 여기서 문제가 하나 더 생긴다.
생산자는 만약 버퍼가 가득 차면 기다려야하고 버퍼에 빈 공간이 있어야 데이터를 추가할 수 있다. 반면 소비자는 버퍼가 비어있으면 기다려야하고 버퍼에 데이터가 들어있어야 소비할 수 있다. 따라서 이러한 조건을 검사하는 코드가 추가되어야 한다.
지금같은 경우 이러한 조건을 검사하는 코드가 없어 무한 반복이 발생할 수 있고, 이러한 문제를 busy-wait 문제라고 한다.
이 역시 세마포어를 통해 회피할 수 있다.
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();
mutex.acquire();
buf[in] = item;
in = (in+1)%size;
count++;
mutex.release();
full.release();
} catch(InterruptedException e) {
// 학습용 예제: 실제 코드에서는 적절한 인터럽트 처리 필요
Thread.currentThread().interrupt();
}
}
int remove() {
try {
full.acquire();
mutex.acquire();
int item = buf[out];
out = (out+1)%size;
count--;
mutex.release();
empty.release();
return item;
} catch(InterruptedException e) {
// 학습용 예제: 실제 코드에서는 적절한 인터럽트 처리 필요
Thread.currentThread().interrupt();
}
return -1;
}
}
busy-wait 문제에 대응하기 위해 다음의 변수를 추가로 선언한다.
또한
이와 같이 세마포어를 활용하여 busy-wait 문제에 대응할 수 있다.
공통 데이터베이스에 다수의 프로세스가 접근할 때 역시 임계구역 문제로 인해 독자-저자 문제가 발생할 수 있다. 예를 들어 독자가 데이터베이스의 데이터를 읽고 있는 도중에 저자가 그 데이터를 수정할 경우 문제가 발생할 수 있다.
보통 독자는 데이터를 읽기만 하고 수정하지는 않으므로 여러 명의 독자가 임계 구역에 진입해도 상관이 없다. 하지만 저자는 데이터를 수정(쓰기)할 수 있으므로 상호 배제 (Mutual Exclusion)를 확립해야한다.
독자-저자 문제는 다음과 같은 방법으로 접근할 수 있다.
독자 프로세스에게 우선권을 부여한다. 만약 독자 A가 데이터 A를 읽고 있으면 저자는 데이터 A에 접근할 수 없다. 이 상황에서 또 다른 독자 B가 데이터 A에 접근하려고 하면 이 역시 접근할 수 있도록 한다. 저자는 모든 독자가 데이터 A를 다 읽기 전까지는 이 데이터에 접근할 수 없다.
이처럼 여러 명의 독자는 하나의 공유된 데이터에 접근할 수 있지만 동시에 저자는 접근할 수 없으므로 상호 배제가 확립된다.
The First R/W Problem에서 독자와 저자가 뒤바뀐 경우다. 즉, 저자가 데이터를 수정하고 있으면 새로 진입하려는 독자와 다른 저자 모두 수정이 끝나기 전까지 접근할 수 없다. 대기 중인 저자가 있으면 독자보다 먼저 권한을 얻는다.
독자와 저자 누구에게도 우선권을 부여하지 않는 방법이다.
원형 테이블에 5명의 철학자가 빙 둘러 앉아있고, 테이블에는 5개의 젓가락이 있다고 하자.
철학자 답게 이 사람들은 밥 먹을 때도 생각에 푹 잠겨있다. 따라서 생각하다가 식사하고 또 생각하다가 식사하고를 반복한다고 하자. (생각 -> 식사 -> 생각 -> 식사 ...)
이 상황을 코드로 표현해보면 다음과 같이 나타내볼 수 있다.
이를 코드로 나타내보면 다음과 같다.
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 philosophers & 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();
}
}
문제가 없어 보이지만 이는 교착 상태 (Deadlock) 문제로 이어져 중간에 멈춰버린다.
그 이유는 다음과 같다.
만약 모든 철학자가 동시에 식사를 하려고 왼쪽 젓가락을 들었다고 하자. 모든 젓가락이 다 들려있는 상태이다. 문제는 식사를 하려면 젓가락이 하나가 더 필요한데, 오른쪽 젓가락을 들려고 보니까 이미 다른 철학자 손에 들려있는 것이다.
이처럼 모든 철학자가 젓가락을 하나씩 들고 있고 서로가 젓가락을 내려놓기를 기다리고만 있는 상황이 펼쳐질 수 있다. 하지만 아무도 젓가락을 내려놓지 않기 때문에 무한정으로 기다리게 된다.
이러한 상황을 교착 상태 (Deadlock) 이라고 한다.
Deadlock을 해결하기 위한 다양한 기법(예: 자원 순서 부여, 비대칭 접근, 타임아웃 등)은 다음 편에서 다룬다.