on
운영체제 - 13
KOCW 운영체제 13강
양희재 교수님 강의를 듣고 쓴 글입니다.
Classical Synchronization Problems
-
Producer and Consumer Problem(==Bounded Buffer Problem)
생산자-소비자 문제.
-
Readers-Writers Problem
공유하는 데이터베이스 접근.
-
Dining Philosopher Problem
식사하는 철학자 문제.
이 중에서 이번 강의에서는 생산자-소비자문제에 대하여 다룰 것이다.
Producer-Consumer Problem
생산자가 데이터를 생산하면, 소비자는 그것을 소비. 그 때에 생기는 문제.
생각해보면 위 문장은 너무나 당연한 말이다. 생산자니깐 생산하고, 소비자니깐 소비하는 것이다. 그 때 발생하는 문제에 대해 말하기 전에 ‘생산자-소비자’는 어떤 관계인건지 예시를 들어보겠다.
-
Compiler - Assembler
Compiler는 high level language code 를 assembly code 로 생산해준다. 그리고 Assembler는 assembly code를 소비하여 machine code로 만들어준다.
→ Compiler 가 assembly code 를 생산하면, Assembler 는 이를 소비하는 관계인 것이다.
예시 상황
저번의 BankAccount Problem처럼 이번에도 예시 코드를 직접 작생해보면서 어떤 문제인지, 어떻게 해결할 것인지 알아볼거다.
-
Producer
데이터를 생성해서 소비자에게 넘겨준다.
-
Consumer
생산자가 데이터를 넘겨주면 소비한다.
-
Buffer
보통 이런 생산자-소비자 관계에서는 속도 차이 등등으로 인해 둘의 사이에 Buffer가 존재한다. 따라서 Buffer class 를 만들 것이고, 해당 버퍼가 가득차면 생산자는 못 넘겨주고, 버퍼가 빈 상태라면 소비자는 소비를 못한다.
Code
// Buffer class
package produce_consumer;
public class Buffer {
private int[] buffer; // int data 담을 버퍼. 배열로 선언.
private int size; // buffer[]의 크기.
private int count; // 현재 buffer[]가 가득 찼으면 count==size, 비었으면 count == 0
private int in; // buffer[]에 삽입할 때 index
private int out; // buffer[]에 삭제할 때 index
public Buffer(int size) {
buffer = new int[size];
this.size = size;
count = in = out = 0;
}
void insert(int item) throws InterruptedException {
while (count == size) ; // 버퍼가 가득 찼으면 삽입은 멈춘다.
count++; // 버퍼에 데이터 하나 더 들어간다는 뜻.
buffer[in] = item; // item이라는 데이터를 버퍼의 in번째에 삽입.
in = (in + 1) % size; // in index를 순환시킨다.
}
int remove() throws InterruptedException {
while (count == 0) ; // 버퍼가 비었으면 소비를 멈춘다.
count--; // 버퍼에 데이터 하나를 삭제할거니, 한자리 빈다는 뜻.
int item = buffer[out]; // out번째의 데이터를 제거할 것.
out = (out + 1) % size; // out index를 순환시킨다.
return item; // 삭제한 데이터 반환.
}
}
// Producer Class
package produce_consumer;
public class Producer extends Thread{
private Buffer buffer; // Consumer와 Producer 사이에 있을 버퍼 선언.
private int N; // N번 반복할 것.
public Producer(Buffer buffer, int N) {
this.buffer = buffer;
this.N = N;
}
public void run() {
for (int i = 0; i < N; i++) {
buffer.insert(i); // 삽입 연산을 N번 반복.
}
}
}
// Consumer Class
package produce_consumer;
public class Consumer extends Thread {
private Buffer buffer; // Consumer와 Producer 사이에 있을 버퍼 선언.
private int N;
public Consumer(Buffer buffer, int N) {
this.buffer = buffer;
this.N = N;
}
public void run() {
int item = 0;
for (int i = 0; i < N; i++) {
int item = buffer.remove(); // N번 삭제 반복.
}
}
}
이제 Main만 만들면 된다.
package produce_consumer;
public class Main {
public static void main(String[] args) throws InterruptedException {
int HOW_MANY = 10000; // 10000번 반복시킬 것이다.
Buffer buffer = new Buffer(50); // 버퍼의 크기는 50
Producer p = new Producer(buffer, HOW_MANY);
Consumer c = new Consumer(buffer, HOW_MANY);
p.start();
c.start();
p.join();
c.join();
System.out.println("=== END Process! ===");
}
}
설명은 각 주석을 참고하길 바란다.
문제점
위의 코드들로 실행을 시키면 Main의 가장 마지막 줄인 "=== END Process! ==="가 보이지 않는다. 그저 아무것도 안나오는 채로 계속 실행만 되고 있다. 어딘가에 문제가 있다는 뜻.
공통 변수 count, buffer[]에 대한 동시 업데이트가 발생.
결국 저번 시간에 배웠던대로 Critical-Section 에 관한 문제였다. 따라서 mutual exclusion 을 보장해주기 위해서 이번에도 Semaphore를 사용하여 해결할 것이다.
Semaphore code
// Buffer Class with Semaphore
package produce_consumer;
import java.util.concurrent.Semaphore;
public class Buffer {
private int[] buffer;
private int size;
private int count;
private int in;
private int out;
private Semaphore mutex; // mutex 라는 이름의 semphore 객체 선언.
public Buffer(int size) {
buffer = new int[size];
this.size = size;
count = in = out = 0;
mutex = new Semaphore(1); // 한번에 1개의 thread만 접근 가능하게 하기 위해 number of permit=1
}
void insert(int item) throws InterruptedException {
while (count == size) ;
mutex.acquire();
// Critical Section ...
count++;
buffer[in] = item;
in = (in + 1) % size;
// ... Critical Section
mutex.release();
}
int remove() throws InterruptedException {
while (count == 0) ;
mutex.acquire();
// Critical Section ...
count--;
int item = buffer[out];
out = (out + 1) % size;
// ... Critical Section
mutex.release();
return item;
}
}
Critical-Section인 부분에서 간섭이 안 일어나도록 Semaphore를 사용하여 mutual exclusion을 보장해줬다.
Busy-Wait
이렇게 강의가 저번과 비슷한 내용으로 끝나는 줄 알았지만 아니었다. 위의 코드에서 더 효율적으로 개선할 수 있는 방향을 알려주셨기 때문이다.
while (count == size) ; // in insert method. 버퍼가 가득차면 생산을 대기하라는 코드.
while (count == 0) ; // in remove method. 버퍼가 비어있으면 소비를 대기하라는 코드.
위 2줄의 코드를 보도록 하자. CPU는 while안의 조건이 false가 될 때까지 계속 실행시킨다. 여기서 ‘대기’의 개념은 CPU가 해당 thread를 잠시 두고 다른 일을 하러 가는 것이 아니다. CPU는 다른 것을 못하는 상태로 해당 whileloop를 실행시켜야 하는 것이다. 이를 Busy-wait라고 한다.
따라서 Semaphore를 사용하여 CPU의 자원을 더욱 효율적으로 사용할 수 있는 방법을 배우게 됐다.
Producer : empty.acquire() // buffer에 빈 곳이 없으면 block
Consumer : full.acquire() // buffer에 소비할게 없으면 block
위 2개의 Semaphore를 사용하여 구현해볼 것이다.
// Buffer Class with mutex, empty, full Semaphore
package produce_consumer;
import java.util.concurrent.Semaphore;
public class Buffer {
private int[] buffer;
private int size;
private int count;
private int in;
private int out;
private Semaphore mutex, full, empty;
public Buffer(int size) {
buffer = new int[size];
this.size = size;
count = in = out = 0;
mutex = new Semaphore(1);
full = new Semaphore(0); // 소비할 수 있는 것의 개수 == number of permit
empty = new Semaphore(size); // 생산할 수 있는 것의 개수 == number of permit
}
void insert(int item) throws InterruptedException {
// while (count == size) ; // BUSY WAIT ← 비효율적
empty.acquire(); // 만약 빈 곳이 없다면 block해라.
mutex.acquire();
// Critical Section ...
count++;
buffer[in] = item;
in = (in + 1) % size;
// ... Critical Section
mutex.release();
full.release(); // 소비할게 생겼다는 의미.
}
int remove() throws InterruptedException {
// while (count == 0) ; // BUSY WAIT ← 비효율적
full.acquire(); // 내부효율을 위해서 semaphore 사용. 소비할게 없다면 block
mutex.acquire();
// Critical Section ...
count--;
int item = buffer[out];
out = (out + 1) % size;
// ... Critical Section
mutex.release();
empty.release(); // 빈 공간이 생겼다는 의미.
return item;
}
}
-
더 효율적인 이유
Semaphore는 CPU가 계속 기다리는게(Busy wait) 아닌,Semaphore내부의 Queue에 보내서 Block을 시킨 뒤 CPU는 다른 일을 할 수 있기 때문이다.