요즘 '동시성'에 대해 관심을 가지고 짬을 내서 공부를 하다보니, 학부시절 운영체제를 수강할때 배웠던 '식사하는 철학자들' 문제가 불현듯 떠올랐다. 그래서 이번에는 이 문제를 JAVA로 어떻게 구현하고 해결 하는지 포스팅해 보려고 한다.
알 만한 사람들은 다 아는 아주 고전적이고 유명한 문제라, 개념 자체에 대해서는 간단하게만 정리하고 넘어 가겠다.
다섯명의 철학자가 원형테이블 주위에 앉아있다. 스파게티 한 접시가 각 철학자에게 주어진다. 이를 먹기 위해서는 두개의 포크가 필요하다. 접시와 접시 사이에 하나의 포크가 있다. 아래는 이러한 배치를 가진 테이블의 모습이다.
이 문제의 룰을 간단히 요약해보자.
- 철학자의 삶은 식사시간과 생각하는 시간의 반복이다.
- 철학자는 배가 고프면 왼쪽 포크, 오른쪽 포크를 한번에 하나씩 잡으려고 시도한다.
- 두개의 포크를 잡게되면 철학자는 잠시동안 먹고, 포크를 테이블위에 올려놓고, 그리고 다시 생각한다.
여기서 핵심적인 질문은 아래와 같다
"각 철학자가 해야할 일을 그대로 수행하면서
절대로 중단 되지 않는 프로그램으로 작성될 수 있는가?"
만약 5명의 철학자들이 서로 사이좋게 양보하며 자신의 왼쪽, 오른쪽에 있는 두개의 포크를 잡고 골고루 식사를 할 수 있다면 그들에겐 아주 행복한 저녁이 될 것이다. 하지만 이를 소프트웨어, 특별히 멀티 스레드 기반의 어플리케이션이라고 보았을 때 이것을 '영원히' 보장 할 수 있는가? 가령, 5명의 철학자가 동시에 왼쪽 또는 오른쪽 포크를 잡는다면 어떻게 될까? 이들은 식사를 하지 못한채 망부석 마냥 한 없이 다른 한 쪽의 포크가 테이블에 올려지길 기다릴 것이다. 사실 이 '식사하는 철학자들' 문제는 교착상태(deadlock)를 다루는 아주 대표적인 예제이다. (참고 - <'운영체제론' 3rd Edition, Andrew S Tanenbaum 저>)
이 예제를 JAVA 스레드기반의 어플리케이션으로 아래와 같이 구현해 보았다.
먼저 이 예제의 'Shared Resource' 라고 할 수 있는 'Fork' 클래스 이다.
class Fork { Lock lock = new ReentrantLock(); public void useFork() { lock.lock(); } public void unUseFork() { lock.unlock(); } } class Tableware { public static final List<Fork> forks = new ArrayList<>(); static { forks.add(new Fork()); forks.add(new Fork()); forks.add(new Fork()); forks.add(new Fork()); forks.add(new Fork()); } }
각 'Fork' 객체는 소유권을 가지지 않은 스레드의 접근을 막기 위해 명시적 'lock' 필드를 가지고 있다. useFork 메서드 수행시 lock을 획득하고, unUseFork 메서드 수행시 lock을 해제 한다. 인덱스 범위는 0 ~ 4 이다.
class Philosopher implements Runnable { private String name; private int number; public Philosopher(String name, int number) { this.name = name; this.number = number; } public void think() { print(name + " thinking ..."); } public void eat() { print(name + " eating ... yum-yum-yum"); } public void takeFork(int i) { print(name + " attemp to take (" + i + ") fork ..."); Fork fork = Tableware.forks.get(i); fork.useFork(); print(name + " take (" + i + ") fork now!"); } public void putFork(int i) { print(name + " put (" + i + ") fork down ..."); Fork fork = Tableware.forks.get(i); fork.unUseFork(); } @Override public void run() { while (true) { think(); takeFork(this.number); takeFork((this.number + 1) % 5); eat(); putFork(this.number); putFork((this.number + 1) % 5); } } }
'Runnable' 인터페이스를 구현한 'Philosopher'(철학자) 클래스이다. 포크를 잡기위한 'takeFork' 메서드와 포크를 테이블에 올려놓기 위한 'putFork' 메서드가 정의되어 있고, 정적 'forks' 리스트에 접근하기 위해 Tableware(식기) 클래스를 사용하고 있다.
'run' 메서드에서는 해당 행위 메서드들을 순차적으로 나열함으로서 철학자들이 해야 하는 일을 구현하였다. 서두에 설명한대로, 생각하고(think), 왼쪽 그리고 오른쪽 포크를 잡으며(takeFork), 먹고(eat), 다시 포크를 내려 놓는다(putFork). 왼쪽, 오른쪽 포크의 인덱스를 구하기 위해 'modulo' 연산을 사용한다.
아래는 위 구현사항을 실행하기 위한 'main' 메서드이다.
public class DiningPhilosophers { public static void main(String[] args) { Philosopher a = new Philosopher("A", 0); Philosopher b = new Philosopher("B", 1); Philosopher c = new Philosopher("C", 2); Philosopher d = new Philosopher("D", 3); Philosopher e = new Philosopher("E", 4); ExecutorService exec = Executors.newCachedThreadPool(); exec.execute(a); exec.execute(b); exec.execute(c); exec.execute(d); exec.execute(e); } }
이제 이 프로그램을 실행해보면 어떤 결과가 나타날까? 일정 시간은 5명의 철학자들이 돌아가면서 식사를 잘 하는 것처럼 보이다가... 아래와 같은 현상에 봉착한다.
A, B, C, D, E 모두가 다른 한쪽 포크를 잡기 위해 (lock을 획득하기 위해) 시도 하고 있다. 하지만 안타깝게도 자신의 다른 한쪽 포크는 이미 다른 철학자가 잡고 있는 상태이다. 때문에 모든 철학자들이 영원히 식사를 하지 못하게 되는 교착상태에 빠져 버린다.
'동시성' 문제는 이처럼 '공유자원' 으로 인해 발생한다. 하지만 요즘 많이들 이야기 하고 있는 '함수형 프로그래밍' 에서는 공유 자원이라는 개념자체가 희박하여 (있어도 함수형 언어의 'Runtime' 레벨에서 알아서 해주는..?) 부수효과를 예방하는 '순수함수' 위주로 프로그램을 작성하기 때문에 이런 문제를 걱정할 필요가 없을 수도 있다.
하지만 아무리 요즘의 언어들이 저수준의 문제를 Runtime에 추상화하는 방향으로 발전하면서 개발자들에게 '비즈니스 로직'에만 집중하게 한다 하더라도, 이러한 프로그램의 본질적인 문제들을 탐구하려고 노력해야 좀 더 엔지니어로서 깊은 내공을 쌓을 수 있다는 것이 개인적인 생각이다.
흠.. 동시성 예제를 살펴보다가 갑자기 잡설로 빠진 것 같다. 아무튼 교착상태에 빠진 배고픈 철학자들을 구제해 줄만한 해결책은 당연히 있다. 제목에서 이미 보았듯이 '시작' 이므로, 해결책에 대한 코드는 다음 포스팅에 정리 해야 겠다. 오늘은 이만..
