전통적 동기화 예제

생산자-소비자 문제 (Producer-Consumer Problem)

생산자가 데이터를 생산하면 소비자가 그것을 소비하는 문제

예를 들어

• 컴파일러가 데이터를 생산하면 어셈블러가 그 데이터를 소비
• 파일 서버가 데이터를 생산하면 클라이언트가 그 데이터를 소비
• 웹 서버가 데이터를 생산하면 웹 클라이언트가 그 데이터를 소비

하는 등의 케이스가 있다.

생산자가 생산한 데이터를 소비자가 한 번에 전부 소비하는 경우는 거의 없다. 따라서 생산된 데이터는 버퍼 (Buffer)라는 메모리 저장 공간에 저장되고 소비자가 필요에 따라 꺼내 쓴다.

Bounded Buffer

하지만 현실의 시스템에서 버퍼의 크기는 무한적이지 않다. 따라서 버퍼가 가득차게 되면 생산자는 더이상 데이터를 넣을 수 없다. 또한 버퍼가 비어있으면 소비자는 데이터를 꺼내 쓸 수 없다. 이렇듯 유한한 크기의 버퍼를 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) {
		while (count == size);
		buf[in] = item;
		in = (in+1)%size;
		count++;
	}
    
	int remove() {
		while (count == 0);
		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();
	}
}

• buf: Bounded buffer
• size: 버퍼의 크기
• count: 버퍼에 저장된 데이터의 개수
• in: 생산한 데이터를 담을 버퍼의 인덱스
• out: 소비할 데이터를 가리키는 버퍼의 인덱스

크기가 100인 버퍼를 생성하고, 생산자와 소비자 역할을 맡은 2개의 쓰레드를 선언한다. 이후 각각 10000번씩 데이터를 생산하고 소비한다. 정상적으로 동작한다면 결과값 count는 0이 되어야 한다.

Busy-Wait

하지만 기대와 달리 결과값은 무한 루프에 빠지거나 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) {}
	}

	int remove() {
		while (count == 0);
		try {
			mutex.acquire();
			int item = buf[out];
			out = (out+1)%size;
			count--;
			mutex.release();
			return item;
		} catch(InterruptedException e) {}
      
		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) {}
	}

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

busy-wait 문제에 대응하기 위해 다음의 변수를 추가로 선언한다.

• empty : 버퍼에서 비어있는 공간의 개수 (초기값 : 버퍼의 현재 크기)
• full: 버퍼에서 차있는 공간의 개수 (초기값 : 0)

1. 생산자는 데이터를 생산하기 전에 버퍼에 비어있는 공간이 있는지 확인한다.
2. 빈 공간이 없다면 empty 세마포의 value가 -1이 되므로 block이 되고, 빈 공간이 있다면 임계구역으로 진입하여 데이터를 생성한다.
3. 데이터가 생성되면 full 세마포의 value값이 1 증가된다.

또한

1. 소비자는 데이터를 소비하기 전에 버퍼에 데이터가 들어있는지 확인한다.
2. 버퍼가 비어있다면 full 세마포의 value가 -1이 되므로 block이 되고, 버퍼에 데이터가 있다면 임계구역으로 진입하여 데이터를 소비한다.
3. 데이터가 소비되면 empty 세마포의 value값이 1 증가된다.

이와 같이 세마포를 활용하여 busy-wait 문제에 대응할 수 있다.

독자-저자 문제 (Readers-Writers Problem)

공통 데이터베이스에 다수의 프로세스가 접근할 때 역시 임계구역 문제로 인해 독자-저자 문제가 발생할 수 있다. 예를 들어 독자가 데이터베이스의 데이터를 읽고 있는 도중에 저자가 그 데이터를 수정할 경우 문제가 발생할 수 있다.

보통 독자는 데이터를 읽기만 하고 수정하지는 않으므로 여러 명의 독자가 임계 구역에 진입해도 상관이 없다. 하지만 저자는 데이터를 읽을 뿐만 아니라 수정도 할 수 있으므로 상호 배제 (Mutual Exclusion)를 확립해야한다.

독자-저자 문제는 다음과 같은 방법으로 접근할 수 있다.

The First R/W Problem

독자 프로세스에게 우선권을 부여한다. 만약 독자 A가 데이터 A를 읽고 있으면 저자는 데이터 A에 접근할 수 없다. 이 상황에서 또 다른 독자 B가 데이터 A에 접근하려고 하면 이 역시 접근할 수 있도록 한다. 저자는 모든 독자가 데이터 A를 다 읽기 전까지는 이 데이터에 접근할 수 없다.

이처럼 여러 명의 독자는 하나의 공유된 데이터에 접근할 수 있지만 동시에 저자는 접근할 수 없으므로 상호 배제가 확립된다.

The Second R/W Problem

The First R/W Problem에서 독자와 저자가 뒤바뀐 경우다. 즉, 저자가 데이터를 수정하고 있으면 모든 저자는 수정이 끝나기 전까지 이 데이터에 접근할 수 없다.

The Third R/W Problem

독자와 저자 누구에게도 우선권을 부여하지 않는 방법이다.

식사하는 철학자 문제 (Dining Philosopher Problem)

원형 테이블에 5명의 철학자가 빙 둘러 앉아있고, 테이블에는 5개의 젓가락이 있다고 하자.

철학자 답게 이 사람들은 밥 먹을 때도 생각에 푹 잠겨있다. 따라서 생각하다가 식사하고 또 생각하다가 식사하고를 반복한다고 하자. (생각 -> 식사 -> 생각 -> 식사 ...)

이 상황을 코드로 표현해보면 다음과 같이 나타내볼 수 있다.

• 한 철학자가 젓가락 A를 사용하면 다른 철학자들은 이 젓가락 A를 사용할 수 없다. 즉, 젓가락 하나에 접근할 수 있는 철학자는 단 한 명 뿐이므로 젓가락을 세마포로 만들 수 있다. (number of permit = 1)
• 식사를 하기 위해서는 젓가락을 2개 사용해야만 한다. (한 쌍) 따라서 모든 철학자는 자기 왼쪽에 있는 젓가락을 먼저 들고, 그 다음 자기 오른쪽에 있는 젓가락을 들어서 한 쌍을 만든다.
• 식사를 끝마치면 마찬가지로 왼쪽 젓가락을 먼저 내려놓고, 그 다음 오른쪽 젓가락을 내려놓는다.
• 각 젓가락과 세마포는 식별을 위해 0, 1, 2, 3, 4 의 일련 변호를 갖는다.

이를 코드로 나타내보면 다음과 같다.

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

1. 5개의 젓가락 세마포와 5명의 철학자 쓰레드를 생성한다.
2. 각 철학자 쓰레드는 무한 반복문을 통해 왼쪽 젓가락과 오른쪽 젓가락을 순서대로 집은 후 식사를 한다.
3. 몇 번 철학자가 식사했는지를 화면에 출력한다.
4. 식사가 끝나면 왼쪽 젓가락, 오른쪽 젓가락 순으로 내려놓고 생각을 한다.

문제가 없어 보이지만 이는 기아 (Starvation) 문제가 발생하여 중간에 멈춰버린다.

그 이유는 다음과 같다.

만약 모든 철학자가 동시에 식사를 하려고 왼쪽 젓가락을 들었다고 하자. 모든 젓가락이 다 들려있는 상태이다. 문제는 식사를 하려면 젓가락이 하나가 더 필요한데, 오른쪽 젓가락을 들려고 보니까 이미 다른 철학자 손에 들려있는 것이다.

이처럼 모든 철학자가 젓가락을 하나씩 들고 있고 서로가 젓가락을 내려놓기를 기다리고만 있는 상황이 펼쳐질 수 있다. 하지만 아무도 젓가락을 내려놓지 않기 때문에 무한정으로 기다리게 된다.

이러한 상황을 교착 상태 (Deadlock)이라고 한다.