Written by xi-jjun
on May 10, 2021

운영체제 - 14

KOCW 운영체제 14강

양희재 교수님 강의를 듣고 쓴 글입니다.

Classical Synchronization Problems

Producer and Consumer Problem(==Bounded Buffer Problem)

생산자-소비자 문제.
Readers-Writers Problem

공유하는 데이터베이스 접근.
Dining Philosopher Problem

식사하는 철학자 문제.

이 중에서 이번 강의에서는 Readers-Writers, Dining Philosopher문제에 대하여 다룰 것이다.

Readers-Writers Problem

여러 명의 독자와 저자들이 하나의 저장 공간(버퍼)을 공유하며 이를 접근할 때 발생하는 문제. - 출처

readers : read data, never modify it.
writers : write data, modify it.
mutual exclusion 한번에 하나의 프로세스만 접근 → 비효율적.

효율성 재고

read 와 write 행위는 critical section에서 무조건 발생.

writers에게 mutual exclusion 보장. 동시에 여러명이 데이터의 수정을 하면 안되기 때문.
readers에게는 여러명이 같은 data에 접근하도록 허용.

Dining Philosopher Problem

os14_1

5명의 철학자가 원형으로 둘러 앉는다. 각각의 철학자 사이에는 젓가락이 낱개로 1개 있다. 철학자는 생각을 주로 하며, 배가 고프면 젓가락으로 식탁 중앙의 밥을 먹는다. 이 과정을 코드로 표현해보겠다.

Code

/* 철학자 class */
public class Philosopher extends Thread {
	private final Semaphore leftChopstick;
	private final Semaphore rightChopstick;
	private final int id;

	public Philosopher(int id, Semaphore leftChopstick, Semaphore rightChopstick) {
		this.id = id;
		this.leftChopstick = leftChopstick;
		this.rightChopstick = rightChopstick;
	}

	@Override
	public void run() {
		while (true) {
			eatAndThinking();
		}
	}

	private void eatAndThinking() {
		try {
			leftChopstick.acquire(); // 왼쪽 젓가락 획득
			rightChopstick.acquire(); // 오른쪽 젓가락 획득
			eating(); // 온전한 젓가락으로 밥 먹음

      // 밥 다 먹었으니 젓가락 모두 반납 후 생각하기
			leftChopstick.release(); 
			rightChopstick.release();
			thinking();
      
		} catch (InterruptedException e) {
			System.out.println(e.getMessage());
		}
	}

	private void thinking() {
		System.out.println(id + " philosopher thinking...");
	}

	private void eating() {
		System.out.println(id + " philosopher eating...");
	}
}

철학자는 위에서 얘기한대로 먹거나 생각하는 행위만을 반복한다. 하지만 먹기위해서는 젓가락 2개가 있어야 한다는 점이다.

/* 테스트를 진행할 Main class*/
public class Main {
	static final int CHOPSTICK_NUM = 1; // 젓가락 낱개로 1개
	static final int PHILOSOPHER_NUM = 5; // 철학자는 총 5명으로 설정.

	public static void main(String[] args) {
		Philosopher[] philosophers = new Philosopher[PHILOSOPHER_NUM];
		Semaphore[] chopsticks = new Semaphore[PHILOSOPHER_NUM];

		init(philosophers, chopsticks); // 초기설정

		start(philosophers); // 철학자들이 행동하기 시작
	}

	private static void start(Philosopher[] philosophers) {
		for (Philosopher philosopher : philosophers) {
			philosopher.start();
		}
	}

	private static void init(Philosopher[] philosophers, Semaphore[] chopsticks) {
		setChopsticks(chopsticks);
		setPhilosophers(philosophers, chopsticks);
	}

	private static void setPhilosophers(Philosopher[] philosophers, Semaphore[] chopsticks) {
		for (int i = 0; i < PHILOSOPHER_NUM; i++) {
			philosophers[i] = new Philosopher(i, chopsticks[i], chopsticks[(i + 1) % PHILOSOPHER_NUM]);
		}
	}

	private static void setChopsticks(Semaphore[] chopsticks) {
		for (int i = 0; i < PHILOSOPHER_NUM; i++) {
			chopsticks[i] = new Semaphore(CHOPSTICK_NUM);
		}
	}
}

위 Main 코드를 실행시키면…

philosopher eating...
philosopher eating...
philosopher eating...
philosopher eating...
....(생략)...
philosopher thinking...
philosopher thinking...
philosopher eating...
philosopher thinking...
philosopher eating...
philosopher thinking...
philosopher eating...
philosopher thinking...

진행이 잘 되다가 어느순간 멈춰서 아무것도 못하게 된다.

Why?? 왜 갑자기 멈추는 걸까?

만약 낮은 확률로 동시에 모든 철학자가 젓가락을 든다면? 어떻게 될지 생각해보자.

0번 철학자는 0번 젓가락을 든다. (코드에서 leftChopstick먼저 들도록 설정했기 때문이다)
동시에 1번 철학자는 1번 젓가락을 든다.
동시에 2번 철학자는 2번 젓가락을 든다.
동시에 3번 철학자는 3번 젓가락을 든다.
동시에 4번 철학자는 4번 젓가락을 든다.

동시에 1번 철학자는 2번 젓가락을 든다...? 근데 없다... 기다린다 (코드에서 left 다음에 rightChopstick을 들도록 설정했기 때문이다)
동시에 2번 철학자는 3번 젓가락을 든다...? 근데 없다... 기다린다 
동시에 3번 철학자는 4번 젓가락을 든다...? 근데 없다... 기다린다 
동시에 4번 철학자는 0번 젓가락을 든다...? 근데 없다... 기다린다 

아까 console에 출력된 코드를 순서에 따라 왜 멈췄는지 풀어서 적어내봤다. 모든 철학자들이 젓가락 2개를 모아서 밥을 먹어야 젓가락 반납하고 생각을 할 수 있는데, 현재 그 어떠한 철학자도 온전한 2개의 젓가락을 갖지 못했다. 따라서 다른 철학자가 반납을 할 때 까지 모두 기다리는 중이다. 이도저도 못하는 상황이 돼버린 것이다.

Deadlock(교착 상태)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. - 출처

위 상황처럼 이도저도 못하게 된 상태를 deadlock 이라고 한다. 더 정확한 deadlock의 조건을 알아보도록 하겠다.

필요조건

Mutual Exclusion

Process 1 가 resource 1을 쓰고 있다면, 다른 process들은 resource 1에 접근을 할 수 없을 때.
Hold and Wait

한 process가 resource 1을 가진 상태로 resource 2를 가질려고 계속 기다릴 때.
No Preemption

다른 process가 이미 쓰고 있는 자원을 뺏을 수 없다는 상황일 때.
Circular Wait

Dining Philosopher Problem 처럼 순환적으로 자원을 기다리고 있는 형태일 때.

위 4가지 상황이 모두 만족되어야 deadlock이 발생할 수 있다.

위 상황에 맞춰서 다시 조건에 대한 설명을 해보자면,

Mutual Exclusion : 한 철학자가 젓가락을 잡으면 놓을 때 까지 아무도 못쓴다.
Hold and Wait : 철학자가 1개의 젓가락을 잡은 상태에서 다른 젓가락이 없다면 있을 때 까지 무한히 기다리게 된다.
No Preemption : 철학자가 다른 철학자가 들고 있는 젓가락을 뺏을 수 없다.
Circular Wait : 각 철학자가 순환적인 구조로 젓가락의 사용을 기다리고 있다.

이렇게 정리할 수 있다. 따라서 deadlock이 발생한 것이다.

다음 시간에 deadlock을 예방하고 해결하는 방법에 대해 알아보도록 하자.

← → Top