운영체제: 프로세스 동기화 - 생성자 ↔ 소비자

Producer - Consumer Problem

 특정 프로세스는 데이터를 생산하고, 특정 프로세스는 생산된 데이터를 통해 처리하는 작업과 같이 생성자-소비자가 있는 프로그램에서 발생할 수 있는 문제이다. 만약 생산되지 않은 경우에 데이터를 사용하는 소비자가 데이터를 가져가게 된다면 원치 않는 데이터 (쓰레기 값)을 가져가게 될 가능성이 크다. 따라서 각각의 프로세스(쓰레드)로 부터 생성자 - 소비자가 존재한다면 생성, 소비 순으로 진행될 수 있도록 동기화가 필요하다.

 

import java.util.concurrent.Semaphore;

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) {}
    }
    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) {}

        return -1;
    }
}


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();
    }
}

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);
    }
}

 위의 자바 코드와 같이 생성자(Producer), 소비자(Consmer)는 버퍼라는 객체를 공유하여 값을 추가하거나 삭제한다. 단순히 세모포어를 적용할 경우 세모포어 획득이 필요한 경우 Busy Wating을 하게 되며 이는 비효율적이다. 따라서 2개의 세마포어를 추가하여 Busy Wating을 방지하며 생성자, 소비자 문제를 해결할 수 있다.

• empty : 버퍼 크기 만큼 초기화 하고, 새로운 값이 추가 될 경우 1 감소 시킨고, 값이 삭제 될 경우 1 증가 시킨다.
• full : empty와 반대되는 역할을 수행한다.

 

Dining Philosopher Problem

 원형 테이블에 5명의 철학자가 있고, 젓가락은 5개만 있는 상황이 있다. 각 철학자는 생각하고 식사하는 과정을 반복하며, 식사를 하기 위해서는 2개의 젓가락이 있어야 한다. 원형 테이블에 앉은 철학자들은 자신의 왼쪽의 젓가락을 획득하고, 오른쪽 젓가락이 획득가능한 경우 식사를 시작한다. 식사가 끝이나면 왼쪽 젓가락을 내려두고, 오른쪽 젓가락을 내려둔다.

 

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();
    }
}

 위의 코드는 식사하는 철학자 문제가 발생할 수 있는 자바 코드이다. 하지만 이 코드는 deadlock에 빠질 수 있다. 예를 들어 모든 철학자가 동시에 왼쪽 젓가락을 집어들면 (세마포어를 획득하면) 모든 철학자들은 오른쪽 젓가락을 집어들 수 없어 starvation에 빠지게 된다. 이는 잘못된 세마포어 설정으로 프로세스의 작업이 진행되지 않는 대표적인 상황이며, 만약 운영체제에서 deadlock이 발생한다면 이는 컴퓨터를 사용할 수 없는 상황이 될 수도 있다.