[OS] 데드락(DeadLock)이 발생하는 상황 //pico kernel

 

식사 중인 철학자 문제

 

설명

Dining philosopher 문제는 프로세스들 간의 동기화 문제에 대한 대표적인 예로서, 실용성보다는 동기화 문제 자체의 이해를 돕기 위한 가상적인 문제입니다. 5명의 철학자들이 원탁에 둘러앉아서 배가 고프면 스파게티를 먹고 배가 부르면 생각에 잠기는 작업을 반복한다. 스파게티를 먹기 위해서는 젓가락 두 개가 필요한데 원탁에는 철학 사이마다 한 개씩만 놓여 있으므로 젓가락은 양 옆의 철학자와 공유하여 사용해야 한다. 여기서 각 철학자를 하나의 프로세스로 각 젓가락을 하나의 공유자원 혹은 공유 변수로 생각하면 그대로 프로그래밍 문제로 바뀐다.

 

데드락이란

Deadlock이란, 죽어 있는 잠김 상태 즉 전혀 풀릴 가능성이 없는 잠김 상태를 지칭한다. 보다 간단한 예로서 금고가 잠겨있는데 열쇠가 그 금고 속에 들어 있는 경우도 마찬가지다. 컴퓨터 시스템에서 데드락 상태를 보다 정확하게 정의하면, 하나의 프로세스 집합이 데드락 상태라는 것은 이 모든 집합의 프로세스가 대기상태이고 이들이 기다리는 이벤트는  이 집합 속의 다른 프로세스에 의해서 발생해야 하는 경우로 정의된다.

 

코드

#include <stdio.h>
#include <stdlib.h>

int mutexChopstick[5];

int userMain(void) {
	int philosopher(int);
	int i;
	for (i = 0; i < 5; i++) {
		mutexChopstick[i] = mutexCreate();
	}
	for (i = 0;i < 5;i++) {
		threadCreate(20, philosopher, i);
	}
}

int philosopher(int i) {
	int left = i;
	int right = (i + 1) % 5;
	while (1) {
		mutexLock(mutexChopstick[left]);
		printf("pickup %d philosopher left %d chopstick \n", i, left);
		threadYield();
		mutexLock(mutexChopstick[right]);
		printf("pickup %d philosopher right %d chopstick  \n", i, right);

		printf("eat the spaghetti\n");

		printf("putdown %d philosopher left %d chopstick \n", i);
		mutexUnlock(mutexChopstick[left]);
		printf("putdown %d philosopher right %d chopstick \n", i);
		mutexUnlock(mutexChopstick[right]);

		printf("think about the method to eat spaghetti without chopsticks\n");
	}
}

위의 코드에서는 모든 철학자가 왼쪽의 젓가락 1개만 들었고 2개의 젓가락을 확보할 수 없기 때문에 교착상태에 빠지게 되는 데드락의 예시로 볼 수 있다.

 

---

Cygwin terminal picokernel을 통한 프로그램 실행

 

참고문헌

[1] 김용석, 운영체제의 이해, 홍릉과학출판사, 2018