outline
Classical Problems of Synchronization
Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem
Monitors
전통적 동기화 문제들(Classical Problems of Synchronization)
1. 유한 버퍼 문제(Bounded-Buffer Problem), 소비-생산자 문제(Producer-Consumer Problem)
- 생산자(Producer)는 데이터를 생성하고, 소비자(Consumer)는 데이터를 소비한다.
- 생산한 데이터는 중간의 버퍼(buffer)라는 저장 공간에 저장해 두고, 소비자는 버퍼에서 필요한 만큼 가져간다.
- 버퍼의 크기는 유한하다.
- 버퍼의 공간이 가득 차면 생산자는 더 이상 버퍼에 접근할 수 없고, 버퍼가 비어 있으면 소비자는 버퍼에 접근할 수 없다.
/*Producer*/
do{
//produce an item in next process
P(empty);
P(mutex);
...
add next produce to buffer
...
V(mutex);
V(full);
}while(1);
/*Consumer*/
do{
P(full);
P(mutex);
...
remove an item from buffer to next consumer
...
V(mutex);
V(empty);
...
consume the item in next comsumer
...
}while(1);- 공유된 데이터로는 카운팅 세마포 변수를 사용하는 full = 0, empty = n(n은 버퍼의 크기)로 초기 값을 설정한다. 생산자와 소비자가 동시에 버퍼의 자원에 접근할 수 없도록 mutex 값을 1로 초기화시켜준다.
- 생산자(Producer): 만약 empty 값이 0보다 작으면 해당 버퍼는 전부 가득 차 있기 때문에 생산자 자체는 waiting 상태가 된다. 만약 버퍼의 자리가 남아 있다면 소비자가 접근할 수 없도록 mutex 값을 설정해 준다. 그다음에 버퍼에 데이터를 저장하고 해당 생산자의 작업이 끝나면 mutex 값을 다시 전환시켜주고 버퍼에 데이터가 저장되었기 때문에 full을 1 증가시켜준다.
- 소비자(Consumer): 만약 full 값이 0이면 버퍼에 데이터가 하나도 없기 때문에 소비자는 접근할 수 없게 waiting 상태로 만들어 준다. 만약 버퍼에 데이터가 있을 경우 다음 작업을 시행하는데 소비자가 작업이 시행되기 때문에 동일하게 생산자는 해당 버퍼에 접근하지 못하게 mutex 값을 설정해준다. 소비자가 버퍼에 데이터를 사용했으면 mutex 값을 다시 전환시켜주고 데이터를 사용했기 때문에 empty 값을 1 감소시켜준다.
- P, V 함수 자체가 atomic 하기 때문에 생산자와 소비자가 동시에 버퍼에 접근하는 일은 원천적으로 방지된다.
2. 읽기 쓰기 문제(Readers and Writers Problem)
- Reader는 데이터를 읽기만 하는 사용자이고 Writer는 데이터를 읽고 수정할 수 있는 사용자를 의미한다.
- 유한 버퍼 문제에서 소비자(consumer)와 다르게 Reader는 데이터를 읽고 소비하지 않는다. (Reader는 읽기만 가능한다.)
- 여러 Reader들은 데이터베이스에 데이터를 읽을 때 동시에 접근이 된다. (Reader는 읽기만 가능하다 = 데이터에 대한 동기화 문제가 발생하지 않는다.)
- Reader들 중에 하나라도 데이터베이스에 접근하여 데이터를 읽고 있는 상태라면 Writer은 데이터베이스에 접근할 수 없다. 반대로 Writer가 데이터베이스의 데이터에 접근하면 어느 Reader도 데이터베이스에 접근할 수 없다.
초기 값
Semaphore mutex = 1, db = 1, int readcount = 0
- Writer 입장에서는 단순히 Reader들이 데이터베이스(db)를 이용하고 있을 때 접근할 수 없게 이진 세마포로 db 값을 설정하여 P, V 함수를 이용해 접근할 수 없게 처리한다. 모든 Reader들이 db를 이용하고 마쳤으면 db의 값이 전환되어 Writer는 db의 데이터에 접근하여 수정 또는 추가할 수 있다. 작업을 마쳤으면 작업을 마쳤다는 알림을 보내준다.
- Reader 입장에서 readcount라는 변수가 존재한다. 해당 변수는 Reader들 사이에는 동시 접근이 가능하기 때문에 데이터베이스에 접근한 Reader들의 수를 알아야 한다. 첫 번째 Reader가 데이터베이스에 접근하기 전에 readcount를 1 증가시킨다. 만약 readcount가 1이라면 해당 Reader가 P, V함수를 이용해 Writer을 접근할 수 없게 한다. 또 여러 Reader들이 들어와 readcount를 하면 Reader들 사이에서 readcount에 대한 동기화 문제가 발생하기 때문에 한 Reader가 들어오면 P, V 함수를 이용해 잠시 다른 Reader들은 접근할 수 없게 한다.(readcount 수정에 대한) Reader들이 작업을 마치고 readcount를 1을 감소시키는데 그 과정에서도 P, V함수를 이용해 Reader사이제 접근을 금지하고 오로지 마지막 Reader가 V(dv)를 할 수 있게 readcount가 0인 조건을 추가한다.
3. 식사하는 철학자 문제(Dining-Philosophers Problem)
'식사하는 철학자 문제'는 5명의 철학자가 식사를 하고 있는 상황을 가정한 문제이다. 5명의 철학자들이 원형의 테이블에 앉아 있는데 철학자들 사이에는 젓가락 한 짝만 놓여있고 철학자 앞에는 음식이 놓여있다. 철학자는 생각을 하다가 배가 고프면 양 옆에 있는 젓가락을 사용해서 식사를 하고 다시 젓가락을 원 위치에 두고 생각을 한다. 여기서 생기는 문제는 철학자 한 명이 음식을 먹고 있으면 양 옆에 있는 철학자는 배가 고파도 음식을 먹을 수 없는 상황이 온다. 따라서 젓가락에 대한 접근을 하는 것에 대한 문제 해결이 필요한 것이다.
- 식사하는 철학자는 단순히 한 철학자가 왼쪽 젓가락을 접근할 때 다른 철학자는 해당 젓가락에 접근할 수 없도록 막아 놓는다. 다음으로 오른쪽 젓가락에 접근할 때 마찬가지로 다른 철학자는 접근할 수 없도록 설정한다. 만약에 오른쪽 젓가락 또는 왼쪽 젓가락이 다른 철학자가 이용 상태라면 해당 철학자는 배고파도 다른 철학자가 이용이 마칠 때까지 대기 상태가 된다. 그럼 다음 양 젓가락이 생기면 철학자는 음식을 먹게 되고 차례대로 젓가락을 두고 다시 생각에 빠지게 된다.
- 하지만 해당 코드에는 문제점이 있다. 만약 5명의 철학자가 동시에 왼쪽 젓가락을 들면 어떻게 될까? 5명 다 오른쪽 젓가락이 없는 상태에서 5명의 철학자가 배고프지만 음식을 못 먹는 상황이 온다. 이런 문제를 교착상태(Deadlock)이라 한다.
교착상태(Deadlock)
프로세스는 실행을 위해 여러 자원을 필요로 한다. CPU, 메모리, 파일, 등등 여러 자원을 사용하여 프로세스가 실행된다. 하지만 자원은 한정되어 있고 여러 프로세스가 같이 자원에 대해 접근하게 되면 문제가 발생한다. 운영체제는 이러한 자원을 프로세스에게 할당을 잘해주어야 한다. '식사하는 철학자 문제'와 같이 모든 프로세스가 자원을 가지려고 대기하는 교착상태(Deadlock)에 빠질 수 있다. 다음은 교착상태에 대한 문제 해결 방안을 제시되어 있다.
- 양 쪽 젓가락을 동시에 들기(Pick up only both)
- Asymmetric coding : 홀수번째 철학자는 왼쪽 젓가락을 먼저 들고 짝수번째 철학자는 오른쪽 젓가락을 먼저 들기
- 처음부터 5자리는 있지만 4명의 철학자만 설정하기
세마포의 문제(Problems of Semaphore)
교착상태(Deadlock)에 대한 문제 해결방안은 여러 가지가 있지만 여전히 문제 아닌 문제가 있다. 지금까지 우리는 세마포를 이용해 서로 간의 임계 영역에 접근할 수 없게 설정하였다. "단순히 세마포를 이용하면 되는구나"가 아닌 실제로 세마포를 코드를 작성하는 것은 매우 어렵다. 그리고 우리가 지금까지 다루었던 해결 방안들을 증명하기 위한 다루었던 문제들을 재현하기 어렵다. 마지막으로 세마포를 남용할 경우 전체 시스템에 영향을 끼칠 수 있기 때문에 단순히 세마포를 이용해서 문제 해결하는 것보다 더 쉬운 해결방안을 제안했다.
모니터(Monitors)
고급 언어의 설계 구조물로써, 개발자의 코드를 상호 배제하게끔 만든 추상화된 데이터 형태이다. 공유 자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다.
위에 그림처럼 전반적인 모니터의 구조를 나타낸다. 'entry queue'는 이미 수행 중인 프로세스가 있기에 다른 프로세스는 wait queue에 저장된다. operation 영역에서는 수행되는 프로세스가 있는데 만약 해당 프로세스가 실행 도중에 조건이 충족되지 않을 시 조건이 만족이 될 때까지 waiting 상태로 되는데 해당 프로세스가 shared data 영역의 queue로 진입하게 된다. 만약 동작했던 프로세스가 조건에 안 맞아서 대기 상태가 되었다면 entry queue에서 한 프로세스가 다시 작동하고 해당 프로세스가 종료되면 entry queue에 있는 프로세스로 가는 게 아니라 먼저 shared data에서 대기하고 있는 프로세스에 signal을 보내서 조건이 충족되지 않아 대기 상태에 있는 프로세스를 먼저 확인한다. 만약 프로세스가 존재하면 해당 프로세스를 우선적으로 실행시킨다.
monitor dining_philosopher
{
enum { thinking, eating, hungry} state[5];
condition self[5]; /*shared data의 영역에서 프로세스의 대기상태를 설정하기 위한 변수*/
void pickup(int i)
{
state[i] = hungry; /*젓가락을 들면 해당 철학자의 상태는 배고픈 상태로 설정*/
test(i);
if(state[i] != eating)
self[i].wait(); /*다른 철학자가 eating하고 있어서 해당 state의 상태를 wait으로 설정*/
}
void putdown(int i)
{
state[i] = thinking; /*해당 철학자는 다시 상태를 생각하는 것으로 설정*/
test((i+4)%5); /*왼쪽 철학자에게 시그널을 보낸다.*/
test((i+1)%5); /*오른쪽 철학자에게 시그널을 보낸다.*/
}
}
void test(int i)
{
if((state[(i+4)%5] != eating) && (state[i] == hungry) && (state[(i+1)%5] != eating))
{ /*왼쪽 철학자와 오른쪽 철학자가 생각하는 상태이고 나의 상태가 배고픈 상태일때*/
state[i] = eating; /*나의 상태를 먹는 상태로 전환*/
self[i].signal(); /*해당 코드는 putdown에서 사용 가능*/
}
}
void init()
{
for(int i=0; i<5; i++)
state[i] = thinking;
}
위에 코드는 '식사하는 철학자 문제'를 모니터 방식으로 간략하게 짜인 코드이다.
코드마다 주석을 달았기 때문에 부연 설명은 pass~
조건부 대기 구성(Conditional-wait construct) : x.wait(c);
- c- 정수는 대기 상태가 실해될 때 계산된다.
- 일시 중단된 프로세스 이름과 함께 저장된 c값(우선순위 번호)이다.
- x.signal이 실행되면, 관련된 우선순위 번호가 가장 작은 프로세스가 다음으로 재개된다.
두 가지 조건을 점검하여 시스템의 정확성을 확인
- 사용자 프로세스는 항상 모니터에서 올바른 순서로 호출되어야 한다.
- 비협조 프로세스(uncooperative process)가 모니터에서 제공하는 상호 제외 게이트웨이를 무시하지 않도록 하고 접근 프로토콜을 사용하지 않고 공유 리소스에 직접 접근할 수 있도록 해야 한다.
