[운영체제] 동기화 예제 1) 생산자-소비자 문제

 

1. 생산자-소비자 문제 Bounded Buffer Problem

1)  생산자-소비자 문제

• 생산자 프로세스가 데이터를 생산하면 소비자 프로세스는 그것을 소비한다.
• -> 버퍼는 생산자와 소비자가 모두 접근하는 임계 구역인 셈이다.
• -> 세마포어를 사용해서 상호 배제로 문제를 해결할 수 있다.
• 예) 컴파일러(생산) > 어셈블러(소비), 파일 서버(생산) > 클라이언트(소비), 웹 서버(생산) > 웹 클라이언트(서버)

 

(1) Bounded Buffer

• 생산된 데이터는 버퍼에 저장한다.(속도 차이 등 때문에)
• 현실 시스템에서 버퍼 크기는 유한하다. (bounded : 한계가 있는)
• 생산자는 버퍼가 가득 차면 더 넣을 수 없다.
• 소비자는 버퍼가 비면 뺄 수 없다.

 

2) 예제 코드

Producer는 버퍼에 10,000개 아이템을 넣고, Cosumer는 버퍼에서 10,000 개 아이템을 찾는다.

프로그램이 종료된 후 아이템은 0개가 남아있어야한다.

 

count : buf에 생산된 데이터의 갯수

size : buf의 크기

in : buf에 데이터가 in되는 위치(index)

out : buf에 데이터가 out되는 위치(index)

(이렇게 동작하면 circural하게 동작한다.)

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 buf;
    int sz;
    Producer(Buffer buf, int sz) {
        this.buf = buf;
        this.sz = sz;
    }
    
    @Override
    public void run() {
        for(int i = 0; i < sz; i++) {
            buf.insert(i);
        }
    }
}

class Consumer extends Thread {
    Buffer buf;
    int sz;
    Consumer(Buffer buf, int sz) {
        this.buf = buf;
        this.sz = sz;
    }
    
    @Override
    public void run() {
        int item = 0;
        for(int i = 0; i < sz; i++) {
            item = buf.remove();
        }
    }
}

class Main {
    public static void main(String[] args) {
        Buffer buf = new Buffer(100);
        Producer p = new Producer(buf, 10000);
        Consumer c = new Consumer(buf, 10000);
        p.start();
        c.start();
        try {
            p.join();
            c.join();
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Number of items in the buf is " + buf.count);
    }
}

/*
Output
Number of items in the buf is 25
*/

문제점

위의 코드는 동작 안하거나 잘못된 결과나온다. (버퍼 안 아이템 수 25가 나왔다)

원인은 공통변수 업데이트 구간(= 임계구역)에 대한 동시 진입했기 때문이다. (공통변수 count, buf[] 동시에 업데이트)

해결 방법은 세마포어를 사용해 임계구역에 대한 동시 접근 방지 (상호배타)

 

수정 코드

import java.util.concurrent.Semaphore;

class Buffer {
    int[] buf;
    int size;
    int count;
    int in;
    int out;
    /* mutex : mutual exclusion */
    Semaphore mutex;
    
    
    Buffer(int size) {
        buf = new int[size];
        this.size = size;
        count = in = out = 0;
        mutex = new Semaphore(1);
    }
    
    void insert(int item) {
        /* check if buf is full */
        while(count == size) { }
        
        /* buf is not full */
        try {
            mutex.acquire();
        
        //////////// Critical Section /////////////////
        buf[in] = item;
        in = (in+1)%size;
        count++;
        ///////////////////////////////////////////////
        mutex.release(); 
        } catch (InterruptedException ex) {}
    }
    
    int remove() {
        /* check if buf is empty */
        while (count == 0) { }
        /* buf is not empty */
        try {
            mutex.acquire(); 
        //////////// Critical Section /////////////////
        int item = buf[out];
        out = (out + 1) % size;
        count--;
        mutex.release(); 
        return item;
        ///////////////////////////////////////////////
        
    
        } catch (InterruptedException ex) {}
        return -1;
    }
}


/*
Output
Number of items in the buf is 0
*/

여러번 실행 해도 0으로 맞게 나온다. 

세마포어를 사용해 임계구역 문제를 해결했다.

 

 

2) Busy Wait

(1) Busy Wait 이란?

• 생산자는 버퍼가 가득 찬 경우 빈공간이 있는지, 소비자는 버퍼가 빈 경우 데이터가 있는지 계속 확인해야해서 CPU 낭비를 초래한다.
• -> 쉬는데 바쁘다는 의미로 Busy Wait 이라고한다. 
• 이를 해결하기 위해 세마포어 2개를 추가해 해결한다. 

 

(2) 세마포어를 사용한 busy-wait 회피

세마포어 full, empty를 추가한다.

full의 permit은 0, empty의 permit 은 BUF_SIZE

import java.util.concurrent.Semaphore;

class Buffer {
    int[] buf;
    int size;
    int count;
    int in;
    int out;
    /* mutex : mutual exclusion */
    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) {
        /* buf is not full */
        try {
            empty.acquire();
            mutex.acquire(); 
        
        //////////// Critical Section /////////////////
        buf[in] = item;
        in = (in+1)%size;
        count++;
        ///////////////////////////////////////////////
        mutex.release(); 
        full.release();
        } catch (InterruptedException ex) {}
    }
    
    int remove() {
        /* buf is not empty */
        try {
            full.acquire();
            mutex.acquire(); 
        //////////// Critical Section /////////////////
        int item = buf[out];
        out = (out + 1) % size;
        count--;
        mutex.release(); 
        empty.release();
        return item;
        ///////////////////////////////////////////////
    
        } catch (InterruptedException ex) {}
        return -1;
    }
}



/*
Output
Number of items in the buf is 0
*/

생산자	소비자
empty.acquire(); PRODUCE; full.release();	full.acquire(); CONSUME; empty.release();

 

세마포어를 사용해 임계구역 문제를 해결했고, 

세마포어 2개를 추가해 busy wait 문제를 해결했다.