[OS] 프로세스 동기화 2

1. 전통적 동기화 예제(Classical Synchronization Problems)

1.1 Producer-Consumer Promblem

생산자-소비자 문제는 생산자가 데이터를 생산하면 소비자는 그 데이터를 소비하는 형태의 문제이다. 컴퓨터 환경에서 예를 보면, 컴파일러 -> 어셈블러, 웹서버 -> 웹 클라이언트 등이 있다. 컴파일러에서 생성한 어셈블리어는 어셈블러에서 이를 소비하여 기계어를 만든다.

생산자-소비자 관계를 간단히 그림으로 나타내면 위와 같다. 이 관계의 대부분은 생산자에서 생산한 데이터 양을 소비자가 한 번에 소비하는 경우는 드물다. 생산한 데이터는 중간의 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) {
		/* 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 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();
	}
}

 

Buffer 클래스의 멤버 변수를 보면

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

만약 생성자가 데이터를 계속 생성해서 버퍼의 마지막 인덱스로 가면 그 다음으로는 처음으로 돌아간다. 소비자 또한 마찬가지이다.

main 메소드를 보면 100 크기의 버퍼를 생성하고 Producer, Consumer 두 개의 쓰레드가 각각 10000번씩 생성하고 소비한다. 정상적으로라면 0이 출력되어야 할 것이다.

 

하지만 위 코드를 실행시키면 무한루프에 빠지거나 count 값에 전혀 예상하지 않은 값이 출력된다. 이 문제 역시 동기화 문제이다. 두 가지 문제가 존재한다. 생산자와 소비자가 동시에 접근하는 공통 변수 buf, count를 두 프로세스가 동시에 업데이트 하고 있다. 임계구역에 동시에 접근한 것이다.

 

또 busy waiting 문제가 있다. 생산과 소비를 하기 전에 버퍼가 가득 찼는지, 비었는지 확인하는 무한 반복문에서 발생한다. 이는 아무일도 하지 않으면서 무한으로 반복하여 CPU를 계속 점유하고 있어 비효율 적이다. 이 문제들을 세마포를 활용하여 해결할 수 있다.

 

class Buffer {
    int[] buf;
    int size, count, in, 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();        // 버퍼의 비어있는 공간을 1 감소 시킨다. (비어있는 공간이 없다면 block)
            mutex.acquire();        // 임계구역 진입 요청
            buf[in] = item;
            in = (in + 1) % size;
            count++;
            mutex.release();        // 임계구역 나가기
            full.release();         // 버퍼의 찬 공간을 1 증가 시킨다.
        } catch (InterruptedException e) {}
    }

    int remove() {
        try {
            full.acquire();         // 버퍼의 찬 공간을 1 감소 시킨다. (버퍼가 모두 비어있으면 block)
            mutex.acquire();
            int item = buf[out];
            out = (out + 1) % size;
            count--;
            mutex.release();
            empty.release();        // 버퍼의 비어있는 공간을 1 증가시킨다.
            return item;
        } catch (InterruptedException e) {}
        return -1;
    }
}

 

 

위 코드에서 Semaphore 변수가 mutex인 이유?

세마포는 여러 프로세스가 데이터를 공유하면서 실행될 때, 공유 데이터에 한번에 하나의 프로세스만 접근하도록 제한하는 기술이다. 세마포는 임계구역에 접근하기 전에 프로세스 진입 여부를 자원의 개수를 통해 결정하게 되는데 위 코드에서 생산자, 소비자 두 스레드가 공유 자원인 buf, count에 접근하고 있다. 즉, 두 개의 진입 여부로 판단하게 된다. 이를 0, 1 이진법으로 표현하는데 이진 세마포, 뮤텍스(Mutex)라고 한다.

 

 

 

mutex 세마포 변수로 임계구역에 접근하기 전에 full, empty 세마포를 통해 버퍼가 가득 찼는지 비어있는지 여부를 먼저 확인한다. 없다면 empty 세마포의 값이 -1이 되므로 block 되고 있다면 임계구역 내부로 진입하여 데이터를 생성한다. 생성이 완료되면 full 세마포의 값을 1 증가시킨다. 이 코드를 실행하면 정상적으로 0이 출력됨을 알 수 있다.

 

1.2 Readers-Writers Promblem

Readers-Writers 문제는 대표적으로 공통 데이터베이스에 접근하는 경우가 있다. 하나의 데이터베이스에 여러 프로세스(readers, writers)가 접근하므로 데이터베이스를 임계구역으로 설정해야한다. 즉, 한번에 하나의 프로세스만 접근가능하도록 해야하는데 이는 매우 비효율적이다.

 

비효율을 해결하기 위해 데이터베이스에 접근하는 프로세스 종류를 reader와 writer로 나눈다. 그리고 reader는 데이터베이스 내의 정보를 바꾸지 않고 읽기만 하는 프로세스로 여러 reader 프로세스가 동시에 데이터베이스를 접근하는 것을 허용한다.

 

writer는 내용을 바꾸는 프로세스이므로 당연히 mutual exclusion을 보장해야한다.

Reader-Writers 문제는 우선순위에 따라 여러 경우로 나뉠 수 있다.

• The first R/W problem (readers-preference) : 이 방법은 reader 프로세스에 우선권을 주는 것이다. 만약, 한 reader 프로세스가 데이터베이스를 읽고 있는 동안 writer 프로세스가 오면 당연히 접근하지 못하고 기다린다. 이 상황에서 다른 reader 프로세스가 들어온다면, writer 프로세스가 기다리는 것을 무시하고 데이터베이스에 접근하여 읽는다. 그 결과 두 reader가 동시에 데이터베이스를 읽는 상황이 된다.
• The second R/W problem (writers-preference) : 위 방법과 반대로 writer 프로세스가 기다리는 상황에서 다른 reader 프로세스가 들어온다면, 기존의 writer 프로세스 다음 순서로 기다려야한다.
• The third R/W problem : 아무에게도 우선순위를 주지 않는다.

1.3 Dining Philosopher Problem

배고픈 철학자 문제라 불리는 대표적인 데드락에 관련된 문제이다. 원형 테이블에 5명의 철학자와 5개의 젓가락이 있는 상황이 있다고 하자. 각 철학자는 생각하고 식사하고를 반복한다. 단 식사를 하기 위해서는 2개의 젓가락이 필요하다.

 

 

젓가락은 한 철학자가 가져가면 다른 철학자는 이 젓가락을 사용할 수 없다. 즉, 한 젓가락에 동시에 접근할 수 있는 철학자는 한명뿐이므로 젓가락은 세마포로 만들 수 있다. (number of permit = 1) 한 철학자가 식사하려고 하면, 왼쪽 젓가락과 오른쪽 젓가락을 순서로 가져가고 식사가 끝나면 동일하게 둘다 순서대로 내려놓는다.

 

import java.util.concurrent.Semaphore;

public class Test {

    static final int num = 5;

    public static void main(String[] args) {
        Semaphore[] sticks = new Semaphore[num];

        for (int i = 0; i < num; i++) {
            sticks[i] = new Semaphore(1);
        }

        Philosopher[] philosophers = new Philosopher[num];
        for (int i = 0; i < num; i++) {
            philosophers[i] = new Philosopher(i, sticks[i], sticks[(i + 1) % num]);
        }

        for (int i = 0; i < num; i++) {
            philosophers[i].start();
        }
    }
}

class Philosopher extends Thread {
    int id;         // 철학자 ID
    Semaphore l_stick, r_stick;     // 왼쪽, 오른쪽 젓가락

    Philosopher(int id, Semaphore l_stick, Semaphore r_stick) {
        this.id = id;
        this.l_stick = l_stick;
        this.r_stick = r_stick;
    }

    public void run() {
        try {
            while (true) {
                l_stick.acquire();
                r_stick.acquire();

                eating();

                l_stick.release();
                r_stick.release();

                thinking();
            }
        } catch (InterruptedException e) {}
    }

    void eating() {
        System.out.println("[" + id + "] : eating");
    }

    void thinking() {
        System.out.println("[" + id + "] : thinking");
    }
}

 

5개의 젓가락 세마포와 5명의 철학자 스레드를 생성한다. 각 철학자 스레드는 무한 반복으로 왼쪽, 오른쪽을 순서대로 집어 식사를 하고 다시 왼, 오 순서대로 내려놓고 생각을 한다.

 

단순히 코드는 문제가 없어보이지만 코드를 실행하면 중간에 멈추고 더이상 실행되지 않는다. 이것은 대표적인 starvation(기아) 문제 중 하나이다. 모든 철학자가 식사를 하지 못하고 굶어죽는 상황이라고 할 수 있다.

 

이는 매우 드문 상황으로 모든 철학자가 동시에 식사를 하려고 왼쪽 젓가락을 집었다고 하자. 그러면 5명 모두 5개 젓가락을 모두 집어든 상황이다. 그렇다면 남아있는 젓가락은 더 이상 없고 모든 철학자가 반대편 젓가락을 들기 위해 기다리게 된다. 하지만 식사할 수 있는 철학자는 없으므로 아무도 젓가락을 내려놓지 않고 하염없이 기다리게 되는 것이다. 이러한 상황을 교착상태(deadlock)라고 한다.