운영체제) 고전적인 프로세스간 통신 문제들

▣ 식사하는 철학자 문제 (Dining Philosophers)

- 철학자들이 원탁에 모여 식사함

- 먹는데는 양쪽의 두개의 포크가 필요하다

- 하나씩 포크를 들면, 다른 하나의 포크를 얻기 위해 기다리게 됨 (기아상태)

- 어떻게 이러한 데드락을 피할 수 있는가

#define TRUE		1
#define FALSE		0

#define N			5
#define LEFT		(i+N-1)%N
#define RIGHT		(i+1)%N
#define THINKING	0
#define HUNGRY		1
#define	EATING		2

typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

void philosophere(int i) {
	while (TRUE) {
		think();
		take_forks(i);
		eat();
		put_forks(i);
	}
}

void take_forks(int i) {
	down(&mutex);
	state[i] = HUNGRY;
	test(i);
	up(&mutex);
	down(&s[i]);
	//	포크를 사용하였다면 : 1->0
	//	포크를 사용하지 않았다면 : 0->sleep

}

void put_forks(int i) {
	down(&mutex);
	state[i] = THINKING;
	test(LEFT);
	test(RIGHT);
	//	블락된 양 옆 사람 시그널을 주는 과정
	up(&mutex);
}

void test(int i) {
	if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
		state[i] = EATING;
		up(&s[i]);
	}
}

- state : 철학자가 식사중인지, 생각중인지, 배고파하는지 결정

- 필요한 포크가 사용중이라면, 배고픈 철학자라도 블락된다

▣ 읽는자 쓰는자 (The Readers and Writers Problem)

- 식사하는 철학자 문제가 I/O와 같이 제한된 수의 자원에 접근하는 문제라면

- 읽는자 쓰는자는 데이터베이스에 접근하는 모델

- 여러 리더가 존재 가능

- Reader 와 Writer의 배타적 접근

#define TRUE		1
#define FALSE		0

typedef int semaphore;
semaphore mutex = 1;
semaphore db = 1;
int rc = 0;					// reader counter


void reader(void)
{
	while (TRUE) {
		down(&mutex);
		rc = rc + 1;
		if (rc == 1) down(&db);		// 첫 Reader라면
		up(&mutex);
		read_data_base();
		down(&mutex);
		rc = rc - 1;
		if (rc == 0) up(&db);		// 마지막 Reader라면
		up(&mutex);
		use_data_read();
	}
}

void writer(void)
{
	while (TRUE) {
		think_up_data();
		down(&db);
		write_data_base();
		up(&db);
	}
}

- mutex : read간 rc의 배제

- db : reader- writer 간

▣ 잠자는 이발사 (The Sleeping Barber)

- 한명의 이발사, 하나의 이발용 의자, 기다리는 손님을 위한 n개의 의자

- 손님이 없으면 이발사는 sleep

- 손님이 오면 이발사는 wakeup

- 이발 중 손님이 오면 대기용 의자에서 기다림

- 대기용 의자도 만석이면 손님은 그냥 이발소를 떠남

==> 이발사와 손님이 경쟁조건에 빠지지 않도록 하는 것

#define TRUE		1
#define FALSE		0

#define CHAIRS		5

typedef int semaphore;
semaphore customers = 0;
semaphore barbers = 0;
semaphore mutex = 1;
int waiting = 0;

void barber(void)
{
	while (TRUE) {
		down(&customers);
		down(&mutex);
		waiting = waiting - 1;
		up(&barbers);
		up(&mutex);
		cut_hair();
	}
}

void customer(void) {
	down(&mutex);
	if (waiting < CHAIRS) {
		waiting = waiting + 1;
		up(&customer);
		up(&mutex);
		down(&barbers);
		get_haircut();
	}
	else {
		up(&mutex);
	}
}

- 경쟁조건에 빠지지 않도록 --> 3개의 semaphore

a. customers : 기다리는 손님의 수

b. barbers : 이발사 수 (0 or 1 )

c. mutex : 상호배제