OS - 동기화 예제

1. 고전적인 동기화 문제들

1.1 유한 버퍼 문제

우리가 해결하려는 문제에서 소비자와 생산자는 다음과 같은 자료구조를 공유한다.

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

우리는 n개의 버퍼로 구성된 풀이 있으며 각 버퍼는 한 항목(item)을 저장할 수 있다고 가정한다. mutex 이진 세마포는 버퍼 풀에 접근하기 위한 상호 배제 기능을 제공하며 1로 초기화된다. empty와 full 세마포들은 각각 비어 있는 버퍼의 수와 꽉 찬 버퍼의 수를 기록한다. 세마포 empty는 n값으로 초기화되고, 세마포 full은 0으로 초기화 된다.

 

다음은 생산자 코드이다.

while(true) {
  wait(empty); //버퍼가 가득 찬 경우 block
  wait(mutex); // 임계 구역을 위한 mutex
  // 버퍼에 item 저장 
  signal(mutex); 
  signal(full); //소비자를 위해 signal
}

다음은 소비자 코드이다.

while(true) {
  /* 버퍼가 비면 block */
  wait(full); //버퍼가 빈 경우 block
  wait(mutex);
  // 버퍼에서 item 가져가기 
  signal(mutex)기
  signal(empty); //생산자를 위해 signal 
}

 

1.2 Readers-Writers 문제

 

하나의 데이터베이스가 다수의 병행 프로세스 간에 공유된다고 가정하자. 이들 프로세스 들 중의 일부는 데이터베이스의 내용을 읽기만 하고 어떤 프로세스들은 데이터베이스를 갱신 하기를 원할 수 있다. 우리는 전자를 readers, 그리고 후자를 writers로 불러 이 두 가지 유형의 프로세스들을 구별한다. 

 

만약 두 reader가 동시에 공유 데이터에 접근하는건 상관없다. 그러나 하나의 writer와 어떤 다른 스레드(reader 또는 writer)가 동시에 데이터베이스에 접근하면, 혼란이 야기될 수 있다.

 

이러한 문제점이 발생하지 않도록 보장하기 위해, 우리는 writer가 쓰기 작업 동안에 공유 데이터베이스에 대해 배타적 접근 권한을 가지게 할 필요가 있다. 이 동기화 문제를 readers-writers 문제라고 한다. 

 

Readers-writers 문제에는 여러가지 변형들이 있는데, 모두 우선순위와 연관된 변형들이다.

 

[첫 번째 readers-writers문제]

writer가 공유 객체를 사용할 수 있는 허가를 아직 얻지 못했다면, 어느 reader도 기다리게 해서는 안된다. 바꿔 말하면, 단순히 writer가 기다리고 있기 때문에, 다른 reader 들이 끝날 때까지 기다리는 reader가 있어서는 안된다.

 

[두 번째 readers-writers문제]

일단 writer가 준비되면 가능한 한 빨리 쓰기를 수행할 것을 요구한다. 바꿔 말해서, writer가 객체에 접근하려고 기다리고 있다면 새로운 reader들은 읽기를 시작하지 못한다. 

 

이 두 문제에는 기아 문제가 발생할 수 있다. 첫 번째 경우에는 writer가 기아 상태에 빠질 수 있으며, 두 번째 경우에는 reader가 기아 상태에 빠질 수 있다. 이러한 이유 때문에, 이 문제의 다른 변형들이 제안되었다. 

 

첫 번째 readers-writers 문제에 대한 해결안에서, reader 프로세스는 다음과 같은 자료구조를 공유한다.

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

• mutex오 rw_mutex 이진 세마포는 각각 1로 초기화되고 read_count는 0으로 초기화된다. 
• rw_mutex 세마포는 reader와 writer가 모두 공유한다. 
• mutex 세마포는 read_count를 갱신할 때 상호 배제를 보장하기 위해 사용된다. 
• read_count는 현재 몇 개의 프로세스들이 객체를 읽고 있는지 알려준다. 
• rw_mutex 세마포는 writer들을 위한 상호 배제 세마포이다. 또한 임계구역으로 진입하는 첫 번째 reader와 임계구역을 빠져나오는 마지막 reader에 의해서도 사용된다. 

writer 코드

while(true) {
  wait(rw_mutex);
  // 쓰기
  signal(rw_mutex);
}

 

reader 코드

while(true) {
  wait(mutex);
  read_count++;
  if(read_count == 1) wait(rw_mutex);
  signal(mutex);

  // 읽기 

  wait(mutex);
  read_count--;
  if(read_count == 0) signal(rw_mutex);
  signal(mutex);
}

위 코드를 보면 데이터베이스를 읽으렴는 제일 처음 reader가 wait(rw_mutex)를 호출하여 임계구역으로 진입을 시도한다. 진입에 성공하면 writer 프로세스는 임계구역으로 진입할 수 없으며, 반면 reader 프로세스는 wait(rw_mutex) 호출 없이 자유롭게 데이터베이스를 읽을 수 있다. 또한 모든 reader 프로세스가 읽기를 끝내고 제일 마지막 reader만 남았다면 이 프로세스는 signal(rw_mutex)를 호출하여 임계구역에 대한 독점권을 내려놓고 빠져 나온다. 

 

즉, 코드를 보면 모든 reader 프로세스가 읽기를 마쳐야만 writer 프로세스가 임계구역에 들어갈 수 있다. 따라서 reader 프로세스가 많다면 writer 프로세스는 데이터베이스 사용이 매우 어려움을 알 수 있다. 

 

1.3 식사하는 철학자 문제

 

이 문제는 여러 명의 철학자들이 원탁의 식탁에 둘러 앉아 있는 상황을 나타낸 것이며, 철학자와 철학자 사이에는 각각 한 개씩의 젓가락이 놓여있다. 식사를 하려면 두 개의 젓가락이 필요하므로 철학자는 자기 좌우에 놓인 젓가락을 들고서 식사를 하며, 식사를 마치면 젓가락을 원

래의 위치에 내려놓는다. 식사 후 철학자는 생각을 하며, 생각을 마치면 다시 식사를 하는 과정이 반복된다. 

 

식사하는 철학자 문제를 프로그램으로 나타내보면 각각의 철학자는 프로세스 또는 쓰레드로 나타내면 되고, 젓가락은 한 번에 한 명의 철학자만 사용할 수 있으므로 초기 값이 1인 세마포로 나타낼 수 있다. 

 

while(true) {
  lstick.acquire(); //왼쪽 젓가락 잡기 
  rstick.acquire(); //오른쪽 젓가락 잡기
  eating()          //식사하기 
  lstick.release(); //왼쪽 젓가락 내려놓기 
  rstick.release(); //오른쪽 젓가락 내려놓기 
}

 

위 코드는 논리적으로 별 문제 없는 것 같지만, 실제로 실행해보면 얼마동안은 잘 작동하다가 결국 프로그램이 더 이상 진행하지 않고 묶여 버리는 것을 발견할 수 있다. 그 이유는 무엇일까?

 

모든 철학자가 동시에 자신의 왼쪽 젓가락을 잡으면 각 철학자는 단지 한 개의 젓가락만 갖게 되며, 나머지 젓가락을 잡기 위해 대기해야지만 다른 철학자 역시 식사를 위해 자신의 젓가락을 놓지 않기 때문에 결국은 모든 철학자가 무한 대기 상태에 들어가는 것이다.

 

이와 같이 모든 프로세스가 진행하지 못하고 무한 대기 상태에 들어가는 것을 교착상태라고 부른다. 교착상태는 프로그램이 아무 일도 못하고 무한 대기 상태로 들어가는 것이므로 올바른 상황은 아니다.