[8] 전통적 동기화 예제

KOCW - 양희재 교수님 강의를 기반으로 운영체제 정리

Producer and Consumer Problem

생산자-소비자 문제는 생산자가 데이터를 생산하면 소비자는 그 데이터를 소비하는 형태에서의 문제입니다. 예를 들어, 컴파일러가 소스코드를 어셈블리어로 번역하게 되고 어셈블러는 어셈블리어를 기계어로 번역합니다. 여기서 컴파일러(생산자)가 생산한 어셈블리어(데이터)를 어셈블러(소비자)가 소비하는 형태입니다.

생산자가 데이터를 생산하는 속도와 소비자가 데이터를 소비하는 속도는 일반적으로 다르기 때문에 데이터를 Buffer라는 임시 공간에 저장합니다. 현실 시스템에서 버퍼의 크기는 유한(bounded)하기 때문에 생산자는 버퍼 크기가 가득 차면 더 넣을 수 없고 소비자는 버퍼가 비면 뺄 수 없습니다.

자바 코드를 통한 생산자-소비자 환경을 구현해보면 아래와 같습니다.

class Test {
	public static void main(String[] args) {
    	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 ++;
    }
    
    void 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();
    }
}

위 코드의 결과를 예상해보면, 생산자가 10000번 생산하고 소비자가 10000번 소비하기 때문에 count 값을 0으로 기대할 수 있습니다. 하지만 실제 코드를 실행해보면 애초에 실행이 되지 않거나 count가 0이 아닌 결과를 확인할 수 있습니다.

이전 은행계좌 문제에서도 알 수 있듯이 이 문제 또한 동기화 문제입니다. 생산자와 소비자가 사용하는 공통 변수인 buf, count를 변경하는 과정(임계구역)을 동시에 접근하기 때문입니다.

이 문제를 해결하기 위해 앞에서 배웠던 세마포어를 사용하여 mutual exclusion을 보장시킬 수 있습니다.

import java.util.concurrent.Semaphore;

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) {
    	/* check if buf is full */
        while (count == size)
        
        /* buf is not full */
        try {
        	mutex.acquire();
	        buf[in] = item;
    	    in = (in + 1)%size;
        	count ++;
            mutex.release();
	    } catch (InterruptedException e) {}
    
    void remove() {
    	/* check if buf is empty */
        while (count == 0 )
        
        /* buf is not empty */
        try {
            mutex.acquire();
	        int item = buf[out]
    	    out = (out + 1) % size;
        	count --;
            mutex.release();
	        return item;            
        } catch (InterruptedException e) {}
        return -1
    }
}

Busy waiting

위의 코드는 이제 실행이 가능한 것을 확인하실 수 있습니다. 하지만 한가지 문제점이 더 있는데 바로 busy waiting 문제입니다. 코드에서 버퍼의 크기가 꽉 찼는지 아니면 비어있는지 확인하기 위해 무한 루프문을 사용하고 있습니다. 이 코드로 인해 CPU는 다른 일을 하지 못하고 계속 count 변수를 확인하며 기다리는 상태가 되는데 이 현상을 busy waiting(바쁘게 기다림)이라고 합니다.

이 낭비를 없애기 위해 무한 루프를 돌리지 말고 세마포어를 사용하여 block처리를 할 수 있습니다.

import java.util.concurrent.Semaphore;

class Buffer {
	int[] buf;
    int size;
    int count;
    int in;
    int out;
    Semaphore mutex; // 상호배제를 위한 세마포어
    Semaphore empty; // busy waiting을 위한 세마포어
    Semaphore full; // busy waiting을 위한 세마포어
    
    
    Buffer(int size) {
    	buf = new int[size];
        this.size = size;
        count = in = out = 0;
        mutex = new Semaphore(1);
        empty = new Semaphore(size);
        full = new Semaphore(0);
    }
    
    void insert(int item) {
        try {
        	mutex.acquire();
            empty.acquire();
	        buf[in] = item;
    	    in = (in + 1)%size;
        	count ++;
            mutex.release();
            full.release();
	    } catch (InterruptedException e) {}
    
    void remove() {
        try {
            mutex.acquire();
            full.acquire();
	        int item = buf[out]
    	    out = (out + 1) % size;
        	count --;
            mutex.release();
            empty.release();
	        return item;            
        } catch (InterruptedException e) {}
        return -1
    }
}

• empty : 버퍼 size로 세마포어 생성

• full : 0을 초기값으로 세마포어 생성

생산하는 경우 empty.acquire(empty 1 감소)을 하고 생산이 완료된 경우 full.release(full 1 증가)를 합니다. 반대로 소비하는 경우 full.acquire(full 1감소)을 하고 소비가 완료된 경우 empty.release(empty 1증가)를 하여 busy waiting 문제를 해결할 수 있습니다.

Readers-Writers Problem

읽기-쓰기 문제는 공통 데이터베이스를 사용하는 경우에서 발생할 수 있는 동기화 문제입니다. 데이터베이스에 접근하는 이유는 크게 데이터베이스 내용을 읽거나(Reader) 추가 및 수정(Writer)하는 경우입니다. 지금까지 겪었던 동기화 문제로 봤을때 데이터베이스 접근을 세마포어를 이용하여 상호배타로 설정하면 문제를 해결할 수 있습니다. 하지만 읽기 프로세스(DB내용 바뀌지 않음)가 접근해서 데이터베이스의 접근을 막아버린다면 또 다른 읽기 프로세스는 접근할 수 없기 때문에 매우 비효율적입니다.

따라서 효율성을 증가하기 위해 하나의 읽기 프로세스가 임계구역에 접근하게 되면 또 다른 읽기 프로세스는 임계구역 접근을 허용하게끔 구현할 수 있습니다. 하지만 아래와 같은 문제가 발생할 수 있기 때문에 현재 상황을 고려하여 설계해야 합니다.

• The first R/W problem : 읽기 프로세스에게 우선권

• The second R/W problem : 쓰기 프로세스에게 우선권

• The Third R/W problem : 아무에게도 우선권을 주지 않음

Dining Philosopher Problem

식사하는 철학자 문제를 이해하기 위해 5명의 철학자와 5개의 젓가락이 있는 상황을 가정해 보겠습니다. 식사를 하기 위해선 2개의 젓가락이 필요하며, 각각의 철학자들은 식사하고 생각하고를 반복합니다.

위의 상황을 코드로 구현하기 위해 젓가락을 세마포어를 1로 초기화(좌측과 우측 철학자 중 한명이 사용하면 다른 사람은 접근 불가)하여 만들 수 있습니다. 추가적으로 식사를 하기 위해 왼쪽 젓가락에서 오른쪽 젓가락 순서로 들고, 식사를 마치고 나서도 왼쪽 젓가락에서 오른쪽 젓가락 부터 놓는 상황으로 하겠습니다.

import java.util.concurrent.Semaphore;

class Test{
	static final int num = 5;
    
    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();
    }
}

class Philosopher extends Thread {
	int id;
    Semaphore lstick, rstick;
    
    Philosopher(int id, Semaphore lstick, Semaphore rstick) {
    	this.id = id;
        this.lstick = lstick;
        this.rstick = rstick;
    }
    
    public void run() {
    	try {
        	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");
    }
}

위의 코드는 5개의 젓가락 세마포어를 생성하고 5명의 철학자 쓰레드를 생성한 코드입니다. 이 코드를 실행시켜보면 식사와 생각을 반복하다가 어느 순간 모든 철학자 쓰레드가 블락당하는 현상이 일어납니다. 이런 현상도 동기화 문제 중 하나인 starvation 문제입니다.

만약 모든 철학자가 동시에 왼쪽 젓가락을 들었다고 생각해보겠습니다. 이런 상황이 발생한다면 오른쪽 젓가락은 다른 철학자가 사용하고 놓아주지 않기 때문에 일어나는 현상입니다. 이런 상황을 교착상태(Deadlock)이라고 합니다.

교착상태에 대한 설명을 하기 전 지금까지 배운 내용을 복습해보겠습니다.
운영체제의 다양한 역할 중 Process Management는 크게 CPU scheduling과 process synchronized 관리 였습니다. 이 중 동기화는 mutual exclusion, ordering, busy waiting, 효율성 증가와 같은 목적을 위해 꼭 필요한 기술입니다. 마지막으로 간혹 이 기술을 잘못 사용하다 보면 deadlock에 빠질 수 있습니다.

Deadlock

프로세스는 실행을 위해 다양한 자원을 필요로 합니다. 운영체제의 역할은 프로세스에 한정된 자원들을 효율적으로 제공하고 관리해줘야 합니다. 만약 운영체제가 프로세스에게 자원을 잘 나눠주지 못하면 교착상태에 빠지게 됩니다.

교착상태는 하나의 프로세스가 실행하기 위한 하나의 자원은 가지고 있으나 다른 자원은 가지지 못하는 상황입니다. 즉, 다른 프로세스가 필요한 자원을 사용하고 있기 때문에 무한 대기가 일어나는 현상입니다.

교착상태가 일어나는 필요 조건

아래의 조건들은 필요 조건이기 때문에 전부 만족해야 교착상태가 일어날 수도 있습니다. 따라서 교착상태는 잘 일어나지 않습니다.

• Mutual exclusion (상호배타) : 식사하는 철학자 문제에서의 젓가락은 상호배타적

• Hold and wait (보유 및 대기) : 왼쪽 젓가락을 보유하면서 오른쪽 젓가락을 대기하는 상태

• No Preemption (비선점) : 다른 철학자의 젓가락을 강제로 선점할 수 없다.

• Circular wait (환형대기) : 철학자들은 원형 탁자위에서 대기하고 있다.

자원 (Resources)

교착상태가 일어나는 이유는 결국 자원 때문입니다. 프로세스는 자원을 사용하기 위해 운영체제한테 요청(request)를 하고 사용(use)후 반납(release)하는 과정을 거치게 됩니다.

교착상태가 일어날 수 있는지를 가시화하는 좋은 방법으로 자원 할당도(Resource Allocation Graph)를 통해 그림을 그려보는 방법입니다. 자원 할당도에서 사각형은 자원, 자원안의 점은 동일한 자원의 개수(CPU 2개, 프린트 3개 등), 원은 프로세스, 화살표는 할당을 의미합니다.

위의 자원할당도를 해석하면 R1자원은 1개가 존재하고 P1 프로세스에 할당(assign)되어져 있는 상황입니다. 또한 P2가 R1자원을 요청(request)하고 있는 상황입니다.

한가지 다른 상황을 더 그려보겠습니다.

R2자원은 2개가 존재하고 각각 P1, P2에 할당되어 있습니다. R1자원은 P2에게 할당되어 있고, P1은 R1자원을 요청하는 상황이며 R3자원은 P3에게 할당되어 있고 P2는 R3자원을 요청하는 상황입니다.

자원할당도는 기본적으로 상호배타와 비선점이 기본적으로 적용되어 있습니다. 따라서 현재 프로세스가 Hold and wait상태인지를 판단할 수 있고 화살표 방향으로 원형을 이룬다면 환형대기인 상태를 판단할 수 있습니다.

위의 그림에서 P1과 P2는 Hold and wait인 상태입니다. 하지만 화살표로 원형을 이루고 있지 않기 때문에 P3가 끝나면 P2, P1 순서대로 처리될 수 있습니다.

마지막으로 식사하는 철학자 문제를 자원할당도로 나타내어 보겠습니다.

위와 같이 자원할당도 상에서 원형을 이루는 경우 환형대기 상태까지 만족되어 교착상태에 빠지게 됩니다.

교착상태를 일어나지 않게 하려면 교착 상태의 필요조건 중 하나라도 만족하지 않게끔 하면 됩니다. 식사하는 철학자 문제에서 환형 대기를 제거하여 교착상태를 일어나지 않게 만들어보겠습니다. 가장 쉬운 방법으로 짝수번 철학자는 왼쪽 젓가락을, 홀수번 철학자는 오른쪽 젓가락을 들도록 한다면 환형대기가 일어나지 않을 수 있습니다.

class Philosopher extends Thread {
	int id;
    Semaphore lstick, rstick;
    
    Philosopher(int id, Semaphore lstick, Semaphore rstick) {
    	this.id = id;
        this.lstick = lstick;
        this.rstick = rstick;
    }
    
    public void run() {
    	try {
        	if (id%2==0) {
            	lstick.acquire();
                rstick.acquire();
            } else {
            	rsitck.acquire();
                lstick.acquire();
            }
            eating();
            lstick.release();
            rstick.release();
            thinking();
        } catch (InterruptedException e) {}
    }
    
    void eating() {
    	System.out.println("[" + id + "] eating");
    }
    
    void thinking() {
    	System.out.println("[" + id + "] thinking");
    }
}

교착상태 처리

교착상태 방지 (Deadlock Prevention)

교착상태 방지는 교착상태의 4가지 필요조건을 한 가지라도 깨는 방법입니다.

• 상호배타 불만족 : 자원을 공유하게 해야하는데 원천적으로 불가능한 경우가 많습니다. (ex. cpu 동시 사용 불가능, 파일 동시 쓰기 불가능)

• 보유 및 대기 불만족 : 동시에 필요한 모든 자원을 할당받게하고, 만약 하나라도 못받는다면 전부 놓아주게끔 하기. 하지만 이방법은 자원 활용률이 낮고, 기아 현상이 일어날 수 있습니다.

• 비선점 불만족 : 자원을 선점 가능하게 해야하는데 원천적으로 불가능한 경우가 많습니다. (ex. 프린트 선점 불가능)

• 환형 대기 불만족 : 자원에 번호를 부여하여 자원 번호의 오름차순으로 자원 요청. 단점으로 자원 활용률이 저하 된다. 식사하는 철학자에 적용하면 마지막 철학자를 제외하고 전부 왼쪽(더 낮은 번호)에서 오른쪽(높은 번호)로 요청하지만 마지막 철학자의 경우 오른쪽(더 낮은)젓가락이 더 낮기 때문에 환형 대기를 깰 수 있습니다.

교착상태 회피 (Deadlock Avoidance)

운영체제는 다른 말로 Resource management(allocator)라고 부릅니다. 교착상태 회피에서는 애초에 운영체제가 자원을 잘못 할당해서 교착상태가 일어난 것이라고 판단합니다.

예를 들어, 우리에게 12개의 A라는 동일한 자원과 3개의 프로세스가 있다고 가정해봅시다. 이 프로세스는 실행하기 위해 A라는 자원이 필요한 상황입니다.

Process	Max needs	Current need
P1	10	5
P2	4	2
P3	9	2

• Max needs : 프로세스가 끝나기 위해 필요한 A자원의 총 개수

• Current needs : 현재 시점에서 필요한 A자원의 개수

위와 같은 상황에서 A자원을 할당할 때 P1에게 5개, P2에게 2개, P3에게 2개를 나눠주어도 3개의 A자원이 남아있기 때문에 문제가 생기지 않습니다.

• P2에게 종료하기 위한 A자원 2개 할당 : 현재 A 자원 1개

• P2가 종료되어 자원 회수 : 현재 A 자원 5개

• P1에게 종료하기 위한 A자원 5개 할당 : 현재 A 자원 0개

• P1이 종료되어 자원 회수 : 현재 A 자원 10개

• P3에게 종료하기 위한 A자원 7개 할당 : 현재 A 자원 3개

• P3이 종료되어 자원 회수 : 현재 A 자원 12개

그렇다면, 아래와 같은 상황은 어떨지 확인해보겠습니다.

Process	Max needs	Current need
P1	10	5
P2	4	2
P3	9	3

각각의 프로세스에게 현재 필요한 자원을 할당하면 현재 A자원은 2개입니다.

• P2에게 종료하기 위한 A자원 2개 할당 : 현재 A 자원 0개

• P2이 종료되어 자원 회수 : 현재 A 자원 4개

• 어떠한 방법으로 할당하더라도 P1과 P3는 종료될 수 없다.

위와 같은 상황을 운영체제의 불안정한 할당이라고 합니다. 불안정한 할당이 곧 교착상태를 일으키기 때문에 운영체제는 불안전한 할당이 일어나지 않도록 해야 합니다. 이 방법을 해결하기 위한 알고리즘으로 Banker's Algorithm 이 있으며 이 알고리즘은 현재 할당 가능한 자원을 프로세스에 투자하여 프로세스를 끝낼 수 있는지(자원 회수) 확인하는 알고리즘입니다.

교착상태 검출 및 복구

방지와 회피는 애초에 교착상태가 일어나지 않도록 하는 방법입니다. 이 방법들과 다르게 검출 및 복구는 교착상태가 일어나느 조건을 무시하고 자원을 분배합니다. 그 후 주기적으로 교착상태가 일어났는지 검사를 하고 교착상태 발생 시 복구하는 방법입니다.

이 방법은 교착상태를 주기적으로 검사하는데 필요한 계산과 메모리 사용으로 인해 오버헤드가 일어날 수 있습니다.

교착상태가 발생하여 복구하는 방법은 프로세스 일부를 강제 종료시키거나 자원을 선점하여 일부 프로세스에게 할당하는 방법을 사용합니다.

교착상태 무시

현실적으로 교착상태는 잘 일어나지 않기 때문에 교착상태를 무시하는 것도 한가지 방법으로 사용되고 있습니다.