[Operating System Concepts 10th] 7. Synchronization Examples 리뷰

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ

7. Synchronization Examples

• 6장에서 다룬 도구들은 메모리 장벽 및 compare_and_swap 연산과 같은 저수준 하드웨어 해결책에서 점점 더 높은 수준의 도구(mutex 락에서 세마포, 모니터까지)에 이르기까지 다양했다.
• 7장에서는 6장에 제시된 도구를 몇 가지 고전적인 동기화 문제에 적용한다.

• 목표
  • 유한 버퍼, readers-writer 및 식사하는 철학자 동기화 문제에 관해 설명한다.
  • 프로세스 동기화 문제를 해결하기 위해 Linux 및 WIndows에서 사용하는 특정 도구를 설명한다.
  • 프로세스 동기화 문제를 해결하기 위하여 POSIX 및 Java가 어떻게 사용될 수 있는지 설명한다.
  • POSIX 및 Java API를 사용하여 동기화 문제를 처리하는 해결책을 설계하고 개발한다.

7.1 Classic Problems of Synchronization

• 동기화 문제에 대한 해결책을 제시할 때 전통적으로 세마포를 사용해 왔기 때문에 여기서도 세마포가 사용된다.
• 그러나 이 해결책을 실제 구현할 때에는 이진 세마포 대신에 mutex 락이 사용될 수 있다.

7.1.1 The Bounded-Buffer Problem

• 우리가 해결하려는 문제에서 소비자와 생산자는 다음과 같은 자료구조를 공유한다.
  • n개의 버퍼로 구성된 풀(pool)이 있으며 각 버퍼는 한 항목(item)을 저장할 수 있다고 가정한다.
  • mutex 이진 세마포는 버퍼 풀에 접근하기 위한 상호 배제 기능을 제공하며 1로 초기화된다.
  • empty와 full 세마포들은 각각 피어 있는 버퍼의 수와 꽉 찬 버퍼의 수를 기록한다.

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

• 생산자 코드는 Figure 7.1, 소비자 코드는 Figure 7.2에 나와있다.
• 이 코드에서 생산자가 소비자를 위해 꽉 찬 버퍼를 생산해내고, 소비자는 생산자를 위해 비어 있는 버퍼를 생산해내는 것으로 해석할 수 있다.

/* Figure 7.1 The structure of the producer process */
while (true) {
    ...
    /* produce an item in next_produced */
    ...
    wait(empty);
    wait(mutex);
    ...
    /* add next_produced to the buffer */
    ...
    signal(mutex);
    signal(full);
}

/* Figure 7.2 The structure of the consumer process */
while (true) {
    wait(full);
    wait(mutex);
    ...
    /* remove an item from buffer to next consumed */
    ...
    signal(mutex);
    signal(empty);
    ...
    /* consume the item in next_consumed */
    ...
}

7.1.2 The Readers-Writers Problem

• 하나의 데이터베이스가 다수의 동시 프로세스 간에 공유된다고 가정해본다.
  • 이들 프로세스들 중 일부는 데이터베이스의 내용을 읽기만 하고(readers라 한다.) 어떤 프로세스들은 데이터베이스를 갱신(즉, 읽고 쓰기. writers라 한다.)하기를 원한다.
• 우리는 writer가 쓰기 작업 동안에 공유 데이터베이스에 대해 배타적 접근 권한을 가지게 할 필요가 있다.
  • 이 동기화 문제를 readers-writers problem이라 한다.

• readers-writers 문제에는 여러 가지 변형들이 있는데, 모두 우선순위와 연관된 변형들이다.
• 첫 번쨰(first) readers-writers 문제는 writer가 공유 객체를 사용할 수 있는 허가를 아직 얻지 못했다면, 어느 reader도 기다리게 해서는 안된다.
  • 즉, 단순히 writer가 기다리고 있기 때문에, 다른 reader들이 끝날 때까지 기다리는 reader가 있어서는 안 된다.
• 두 번째(second) readers-writers 문제는 일단 writer가 준비되면 가능한 한 빨리 쓰기를 수행할 것을 요구한다.
  • 즉, writer가 객체에 접근하려고 기다리고 있다면, 새로운 reader들은 읽기를 시작하지 못한다.
• 첫 번째 경우에는 writer가 기아 상태에 빠질 수 있으며, 두 번째 경우에는 reader가 기아 상태에 빠질 수 있다.

• 첫 번째 readers-writers 문제에 대한 해결안에서, reader 프로세스는 다음과 같은 자료구조를 공유한다.
  • rw_mutex 세마포는 reader와 writer가 모두 공유한다.
  • mutex 세마포는 read_count를 갱신할 때 상호 배제를 보장하기 위해 사용된다.
  • read_count는 현재 몇 개의 프로세스들이 객체를 읽고 있는지 알려준다.
  • rw_mutex 세마포는 writer들을 위한 상호 배제 세마포이다. 또한 임계구역으로 진입하는 첫 번째 reader와, 임계구역을 빠져나오는 마지막 reader에 의해서도 사용된다.
  • 그러나 다른 reader들이 임계구역 안에 있는 동안 임계구역을 드나드는 reader들은 이것을 사용하지 않는다.

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

• Figure 7.3은 writer 프로세스를 위한 코드를, Figure 7.4는 reader 프로세스를 보여준다.
  • writer가 임계구역에 있고 n개의 reader가 기다리고 있으면 한 개의 reader만이 rw_mutex와 관련된 큐에 삽입되고, 나머지 n-1개의 reader들은 mutex와 관련된 큐에 삽입된다.
  • 또 writer가 signal(rw_mutex)을 수행하면 대기 중인 여러 reader 혹은 대기 중인 한 개의 writer의 수행이 재개됨을 관찰할 수 있다.

/* Figure 7.3 The structure of a writer process */
while (true) {
  wait(rw_mutex);
  ...
  /* writing is performed */
  ...
  signal(rw_mutex);
}

/* Figure 7.4 The structure of a reader process */
while (true) {
  wait(mutex);
  read_count++;
  if (read_count == 1)
    wait(rw_mutex);
  signal(mutex);
    ...
  /* reading is performed */
    ...
  wait(mutex);
  read_count--;
  if (read_count == 0)
    signal(rw_mutex);
  signal(mutex);
}

• Readers-writers 문제와 그의 해결안들은 몇몇 시스템에서 read-writer 락(lock)을 제공한다.
• Reader-writer 락을 획득할 때에는 읽기(read)인지 쓰기(write)인지의 모드를 지정해야만 한다.
• 읽기 모드의 reader-writer 락은 여러 개의 프로세스가 동시에 획득하는 것이 가능하다.
• writer는 공유 데이터를 배타적으로 접근해야 하므로 오직 하나의 프로세스만이 쓰기 모드의 reader-writer 락을 획득할 수 있다.

7.1.3 The Dining-Philosophers Problem

• 식사하는 철학자들 문제(the dining-philosophers problem)는 교착 상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것이다.

7.2 Synchronization within the Kernel

7.2.1 Synchronization in Windows

• Windows 운영체제는 실시간 애플리케이션과 멀티 프로세서 지원을 제공하는 멀티 스레드 커널이다.
• Windows 커널이 싱글 프로세서에서 전역 정보를 액세스할 때에는 동일한 전역 정보를 액세스할 가능성이 있는 인터럽트 핸들러가 실행되지 않도록, 인터럽트를 잠시 동안 못 걸리게 만든다.
• 멀티 프로세서 시스템에서는 Windows는 스핀락을 써서 전역 정보 액세스를 통제한다.
  • Windows 커널은 짧은 코드에 대해서만 스핀락을 사용한다.

• 커널 외부에서 스레드를 동기화하기 위해 dispatcher 객체를 제공한다.
• 시스템은 데이터에 접근하기 위해서 스레드가 mutex의 소유권을 획득한 후, 필요한 작업이 끝난 후에는 다시 반납하게 함으로써 공동으로 사용하는 데이터를 보호한다.
• Event는 조건 변수와 유사하다. 기다리는 조건이 만족하면 기다리고 있는 스레드에 통지해 줄 수 있다.
• Timer는 지정한 시간이 만료되면 하나 이상의 스레드에 통지하는 데 사용된다.

• Dispacther 객체는 signaled 상태에 있을 수도 있고 nonsignaled 상태에 있을 수도 있다.
  • Signaled 상태 : 객체가 사용 가능하고 그 객체를 얻을 때 그 스레드가 블록되지 않음을 뜻한다.
  • Nonsignaled 상태 : 객체가 사용할 수 없고 그 객체를 얻으려고 시도하면 그 스레드가 블록됨을 뜻한다.
• Dispatcher 객체의 상태와 스레드 상태 간에는 관련성이 있다.

• Critical-section 객체는 커널의 개입 없이 획득하거나 방출할 수 있는 사용자 모드 mutex이다.
• 멀티 프로세서 시스템에서 critical-section 객체는 처음에는 스핀락을 사용하여 다른 스레드가 객체를 방출하기를 기다린다.
  • 회진이 길어지면 락을 획득하려는 프로세스는 커널 mutex를 할당하고 CPU를 양도한다.

7.2.2 Synchronization in Linux

• Linux에서 커널 안의 임계구역을 보호하기 위해 mutex 락이 제공된다.
  • 태스크는 임계구역에 들어가기 전에 mutex_lock() 함수를 호출해야 하고 나오기 전에 mutex_unlock() 함수를 호출해야 한다.
  • 만일 mutex 락을 획득할 수 없으면 mutex_lock()을 호출한 태스크는 수면 상태에 놓이고 락의 소유자가 mutex_unlock()을 호출할 때 깨어나게 된다.

• Linux 커널은 커널 안에서의 locking을 위하여 스핀락과 세마포 및 두 락의 reader-writer 버전도 제공한다.

References