정현석

개인 저장공간입니다.
Since 2021.10

5 분 소요

본 글은 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

6장에서 동기화 도구를 만들었다면, 이번 글은 그 도구들을 실제 문제에 적용하는 장이다. 먼저 유한 버퍼, readers-writers, 식사하는 철학자라는 세 가지 고전적인 동기화 문제를 다루고, 이어서 Windows와 Linux 커널이 내부적으로 사용하는 동기화 기법을 살펴본다.

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

동기화 도구가 실제로 쓰이는 고전적인 문제 세 가지를 먼저 살펴본다 — 유한 버퍼, readers-writers, 식사하는 철학자다.

  • 동기화 문제에 대한 해결책을 제시할 때 전통적으로 세마포를 사용해 왔기 때문에 여기서도 세마포가 사용된다.
  • 그러나 이 해결책을 실제 구현할 때에는 이진 세마포 대신에 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 문제는 이름의 순서가 아니라, 우선순위를 누구에게 주는지의 차이다.

결국 우선순위를 누구에게 두느냐의 차이다.

  • 첫 번째 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);
}

정리하면, reader는 처음 진입과 마지막 이탈에서만 rw_mutex를 사용하고, 그 사이의 reader들은 read_count로만 관리된다.

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

7.1.3 The Dining-Philosophers Problem

세 번째 문제는 여러 스레드가 한정된 자원을 나눠 써야 하는 상황을 식탁에 비유한 것이다.

image

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

7.2 Synchronization within the Kernel

여기서부터는 추상적인 문제를 떠나, Windows와 Linux 커널이 실제로 어떤 동기화 도구를 제공하는지 본다.

7.2.1 Synchronization in Windows

먼저 Windows 커널이 전역 정보를 보호하고 스레드를 동기화하는 방식을 살펴본다.

  • Windows 운영체제는 실시간 애플리케이션과 멀티 프로세서 지원을 제공하는 멀티 스레드 커널이다.
  • Windows 커널이 싱글 프로세서에서 전역 정보를 액세스할 때에는 동일한 전역 정보를 액세스할 가능성이 있는 인터럽트 핸들러가 실행되지 않도록, 인터럽트를 잠시 동안 못 걸리게 만든다.
  • 멀티 프로세서 시스템에서는 Windows는 스핀락을 써서 전역 정보 액세스를 통제한다.
    • Windows 커널은 짧은 코드에 대해서만 스핀락을 사용한다.
  • 커널 외부에서 스레드를 동기화하기 위해 dispatcher 객체를 제공한다. 2
  • 시스템은 데이터에 접근하기 위해서 스레드가 mutex의 소유권을 획득한 후, 필요한 작업이 끝난 후에는 다시 반납하게 함으로써 공동으로 사용하는 데이터를 보호한다.
  • Event는 조건 변수와 유사하다. 기다리는 조건이 만족하면 기다리고 있는 스레드에 통지해 줄 수 있다.
  • Timer는 지정한 시간이 만료되면 하나 이상의 스레드에 통지하는 데 사용된다.

image

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

Windows의 이벤트(dispatcher 객체)를 기다리는 스레드가 대기 상태로 들어가고, 다른 스레드가 객체를 signaled 상태로 만들면 다시 실행을 위해 디스패치되는 흐름

출처: Defining and Using an Event Object - Microsoft Learn (https://learn.microsoft.com/en-us/windows-hardware/drivers/kernel/defining-and-using-an-event-object), CC BY 4.0 3

정리하면, dispatcher 객체의 상태가 그 객체를 얻으려는 스레드가 블록될지 여부를 결정한다.

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

7.2.2 Synchronization in Linux

Windows의 방식을 봤으니, 이제 Linux는 어떤 도구를 쓰는지 보자.

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

image

커널 안과 밖은 서로 다른 규칙으로 움직인다.

이 장의 해결책들은 모두 대가를 동반한다. 유한 버퍼 문제는 버퍼 풀의 빈자리와 찬자리 수를 세마포로 관리해야 하고, readers-writers 문제는 첫 번째 해법에서 writer가, 두 번째 해법에서 reader가 기아에 빠질 수 있다. 식사하는 철학자 문제 역시 교착 상태와 기아를 함께 피해야 한다는 점이 핵심 난제다. 커널 동기화도 마찬가지여서, Windows는 짧은 코드에만 스핀락을 사용하고 회전이 길어지면 커널 mutex로 CPU를 양도하며, Linux도 임계구역의 길이에 따라 스핀락과 세마포·mutex를 구분해 사용한다.

핵심 정리

  • 세 가지 고전 문제. 유한 버퍼, readers-writers, 식사하는 철학자는 전통적으로 세마포를 사용해 해결해 온 대표적인 동기화 문제다.
  • 우선순위의 갈림길. readers-writers 문제는 이름의 순서가 아니라 우선순위를 누구에게 주느냐에 따라 첫 번째·두 번째로 나뉘고, 그 결과 기아에 빠지는 대상이 writer냐 reader냐로 갈린다.
  • 커널이 쓰는 도구. Windows는 인터럽트 차단과 스핀락, dispatcher 객체를 사용하고, Linux는 커널 안에서 mutex 락과 스핀락·세마포를 사용한다.
  • reader-writer 락의 모드. 읽기 모드는 여러 프로세스가 동시에 획득할 수 있지만, 쓰기 모드는 오직 하나의 프로세스만 획득할 수 있다.

References

  1. pthread_rwlock_rdlock - The Open Group Base Specifications Issue 7 ↩

  2. Introduction to Kernel Dispatcher Objects - Microsoft Learn ↩

  3. Defining and Using an Event Object - Microsoft Learn ↩

  4. Generic Mutex Subsystem - Linux Kernel Documentation ↩

댓글남기기

참고