7. Synchronization Examples

이 장에선 앞 장에서 다루었던 동기화 도구들을 여러 고전적 동기화 문제들에 적용해 본다. 또한, 여러 운영 체제에서의 동기화 메커니즘을 알아보고 Java와 POSIX의 세부 API를 알아본다.

7.1. Classic Problems for Synchronization

이 절에서는 여러 기본적 동기화 문제들을 알아본다. 이들은 새로 제안된 동기화 방법을 시험할 때 항상 쓰인다.

7.1. The Bounded-Buffer Problem

제한된 버퍼 문제는 가장 기본적인 문제이다. 1로 초기화된 세마포어 mutex, n으로 초기화된 세마포어 empty, 0으로 초기화된 세마포어 full을 써서 이를 해결한다. 생산자 프로세스의 코드는 다음과 같다.

while (true) {
    wait(empty);
    wait(mutex);
    // ...
    signal(mutex);
    signal(full);
}

소비자 프로세스의 코드는 다음과 같다.

while (true) {
    wait(full);
    wait(mutex);
    // ...
    signal(mutex);
    signal(empty);
}

7.2. The Readers-Writers Problem

데이터베이스가 공유될 때 데이터베이스에 쓰는 프로세스간에는 상호 배타적 접근이 이루어져야 한다. 이를 독자-필자 문제라 한다. 이는 여러 변종이 있는데 첫째는 독자의 기다림을 허용치 않는 문제이고 둘째는 필자가 준비되는 즉시 쓰기를 시작해야 하는 문제이다. 두 문제의 해법 모두 첫 번째 문제에서는 필자가, 두 번째 문제에서는 독자가 빈곤을 겪을 수 있다. 첫 번째 문제에 대해서는 독자 프로세스들은 다음의 자료 구조를 공유한다: 1로 초기화된 세마포어 rw_mutex, 1로 초기화된 세마포어 mutex, 카운팅 세마포어 read_count. 필자 프로세스의 코드는 다음과 같다.

while (true) {
    wait(rw_mutex);
    // ...
    signal (rw_mutex);
}

독자 프로세스의 코드는 다음과 같다.

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);
}

필자가 임계 영역에 진입해 n개의 독자가 대기하고 있으면 하나의 독자만 rw_mutex 큐에 추가되고 나머지 n – 1개의 독자는 mutex에 추가된다. 또한, 필자가 signal(rw_mutex)를 수행하면 다른 필자가 실행될 수도 있고 독자가 실행될 수도 있다. 이는 독자-필자 락으로 일반화된다. 이는 다음 상황에 유용하다.

  • 어떤 프로세스가 공유 데이터를 읽고 어떤 프로세스가 공유 데이터를 쓰는지 명확히 구별 가능한 애플리케이션.
  • 읽는 프로세스가 쓰는 프로세스보다 많은 애플리케이션.

7.1.3. The Dining-Philosophers Problem

식사하는 철학자들 문제에서는 다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 밥이 있고 양옆에 젓가락을 하나씩 있다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 이때 철학자가 밥을 먹기 위해서는 양 옆의 젓가락을 동시에 들어야 한다.

7.1.3.1. Semaphore Solution

간단한 해는 각 젓가락을 세마포어로 나타내는 것이지만, 모든 철학자가 왼쪽의 젓가락을 들면 교착 상태에 빠지게 된다. 해결책은 다음 방법이 있다.

  • 테이블에 최대 4명의 철학자들만 앉을 수 있게 한다.
  • 양 옆의 젓가락이 사용 가능한 상태에서만 젓가락을 들 수 있게 한다.
  • 홀수 번호 철학자는 왼쪽 젓가락을 들고 오른쪽 젓가락을 들게 하고, 짝수 번호 철학자는 오른쪽 젓가락을 들고 왼쪽 젓가락을 들게 한다.

이 해법을 써도 한 철학자가 기아에 빠지지 않는다는 보장은 없다.

7.1.3.2. Monitor Solution

모니터를 통한 해법을 통해 양 옆의 젓가락이 사용 가능한 상태에서만 젓가락을 들 수 있게 할 수 있다. 하지만, 역시 이 해법을 써도 한 철학자가 기아에 빠지지 않는다는 보장은 없다.

7.2. Synchronization within the Kernel

이제 운영 체제에서 제공하는 동기화 방법을 알아보자.

7.2.1. Synchronization in Windows

윈도우 커널은 싱글 프로세서 시스템에서는 전역 자원에 접근할 수 있는 모든 인터럽트 핸들러의 인터럽트를 마스킹한다. 멀티프로세서 시스템에서는 스핀락을 이용해 전역 자원을 보호하며, 이 스핀락을 들고 있는 스레드는 점유되지 않도록 한다.

커널 밖에서의 스레드 동기화를 위해서는 윈도우는 디스패쳐 오브젝트를 제공하며 이는 뮤텍스 락, 세마포어, 이벤트, 타이머 등의 방법으로 스레드 동기화를 제공한다. 디스패쳐 오브젝트는 사용 가능한 시그널 상태와 사용 불가능한 논시그널 상태일 수 있다. 스레드가 논시그널 디스패쳐 오브젝트를 막고 있으면 이는 준비 상태에서 대기 상태로 바뀌고, 디스패쳐 오브젝트가 시그널 상태로 바뀔 때 다시 준비 상태로 돌아간다. 한 번에 준비 상태로 돌아가는 스레드의 수는 디스패쳐 오브젝트의 유형에 따라 다르다.

임계 영역 오브젝트는 커널 간섭 없이 획득/해제될 수 있는 사용자 모드 뮤텍스이다. 커널 뮤텍스는 대개 오브젝트에 대한 경합이 있을 때에만 할당되기 때문에 임계 영역 오브젝트는 유용하다.

7.2.2. Synchronization in Linux

리눅스 커널은 2.6 이후부터는 선점적이며, 커널에서 여러 다른 동기화 메커니즘을 제공한다. 가장 간단한 동기화 방법은 원자적 정수지만, 쓰임새가 제한되어 있다는 단점이 있다. 뮤텍스 락은 mutex_lock(), mutex_unlock()으로 제공된다. 스핀락과 세마포어도 제공한다. 싱글 프로세서에서는 커널 선점을 preempt_disable(), preempt_enable()을 통해 활성화/비활성화하는 방식으로, 멀티 프로세서에서는 스핀락을 획득/해제하는 방식으로 동기화 메커니즘을 제공한다. 리눅스 커널에서 스핀락과 뮤텍스 락은 비재귀적이다. 스핀락은 락이 짧은 시간동안만 작동할 때 쓰이며, 긴 시간 작동할 때에는 세마포어나 뮤텍스 락이 쓰인다.

7.3. POSIX Synchronization

POSIX 동기화 API를 알아보자.

7.3.1. POSIX Mutex Locks

POSIX 뮤텍스 락은 pthread_mutex_t 자료형으로 제공된다. 이는 pthread_mutex_init()으로 초기화되고, pthread_mutex_lock, pthread_mutex_unlock으로 할당/해제된다.

7.3.2. POSIX Semaphores

POSIX는 기명 세마포어와 무명 세마포어를 제공한다.

7.3.2.1. POSIX Named Semaphores

기명 세마포어는 sem_open, sem_wait, sem_post로 제어된다.

7.3.2.2. POSIX Unnamed Semaphores

무기명 세마포어는 sem_init, sem_wait, sem_post로 제어된다.

7.3.3. POSIX Condition Variables

조건 변수는 pthread_cond_t 자료형으로 제공되며, pthread_cond_init, pthread_cond_wait, pthread_cond_signal로 제어된다.

7.4. Synchronization in Java

Java의 동기화 API를 알아보자.

7.4.1. Java Monitors

Java에서 메소드가 synchronized로 선언되면 그 메소드를 호출하기 위해서는 오브젝트에 대한 락을 소유해야 한다. 이 락을 다른 스레드가 점유하고 있다면 synchronized를 호출하는 메소드는 블락되고 오브젝트 락에 대한 진입 집합에 추가된다. 락이 해제되면 호출 스레드가 그 락의 소유자가 되고 메소드에 진입할 수 있게 된다. 스레드가 메소드에서 나갈 때 락이 해제된다. 모든 오브젝트는 진입 집합뿐만 아니라 대기 집합도 갖고 있다. 이는 wait(), notify()로 제어된다. 이들은 Java의 시작부터 있던 메커니즘이나, Java에선 다른 메커니즘도 제공한다.

7.4.2. Reentrant Locks

Java에서는 ReentrantLock을 제공하며, 다음과 같이 쓰인다.

Lock key = new ReentrantLock();
key.lock();
try {
    // ...
} finally {
    key.unlock();
}

7.4.3. Semaphores

Java에서는 Semaphore를 제공하며, 다음과 같이 쓰인다.

Semaphore sem = new Semaphore();
try {
    sem.acquire();
    // ...
} catch (InterruptedException ie) { }
finally {
    sem.release();
}

7.4.4. Condition Variables

Java에서는 조건 변수도 제공하며, Condition 클래스이다. .await(), .signal()로 제어된다.

7.5. Alternative Approaches

앞서 이야기한 동기화 방법들 외에도 다른 접근법들이 있다.

7.5.1. Transactional Memory

트랜잭셔널 메모리는 DB에서 제공하는 프로세스 동기화 전략의 아이디어이다. 메모리 트랜잭션은 원자적인 메모리 읽기-쓰기 동작들의 나열이다. 이 동작들이 도중에 중단된다면 그 때까지 이뤄졌던 동작들이 롤백되어야 한다. 뮤텍스와 세마포어 등을 일일히 거는 것은 비효율적이기 때문에 트랜잭셔널 메모리를 구현해 쓰기도 한다. 소프트웨어 트랜잭셔널 메모리(STM)은 트랜잭션 블록 내에 명령문을 삽입해서 구현한다. 하드웨어 트랜잭셔널 메모리(HTM)은 하드웨어 캐시 계층과 캐시 일관성을 통해 공유 데이터에 대한 충돌을 해결한다. 이는 특별한 명령문을 필요로 하지 않기에 오버헤드가 더 적지만 캐시 계층과 캐시 일관성이 이에 맞춰 수정되어야 한다는 것이 다르다. 트랜잭셔널 메모리는 최근에 많은 관심을 받고 있다.

7.5.2. OpenMP

OpenMP는 #pragma omp critical로 임계 영역임을 표시할 수 있게 한다. 이는 일반적인 뮤텍스 락보다 쓰기 쉽지만, 애플리케이션 제작자가 가능한 레이스 컨디션을 알고 컴파일러 명령어를 이용해 공유 데이터를 보호해야 한다는 단점이 있다. 또한, 데드락도 여전히 가능하다.

7.5.3. Functional Programming Languages

대다수 프로그래밍 언어는 명령적(절차적) 언어이지만, 함수형 프로그래밍 언어에서는 변수의 값을 불변으로 둠으로써 레이스 컨디션과 데드락으로부터 자유롭다.

7.6. Summary

  • 프로세스 동기화 관련 고전적 문제들에는 제한된 버퍼, 독자-필자, 식사하는 철학자들 문제들 등이 있다. 이 문제에 대한 해법은 뮤텍스 락, 세마포어, 모니터, 조건 변수 등이 있다.
  • Windows는 디스패쳐 오브젝트와 이벤트를 이용해 프로세스 동기화를 수행한다.
  • Linux는 원자적 변수, 스핀락, 뮤텍스 락 등을 이용해 레이스 컨디션을 방지한다.
  • POSIX API는 뮤텍스 락, 세마포어, 조건 변수를 제공한다. 세마포어에는 기명 세마포어와 무기명 세마포어가 있다. 기명 세마포어는 여러 관련 없는 프로세스간 공유가 쉽다. 무기명 세마포어는 공유가 쉽지 않고, 공유 메모리 지역에 세마포어를 놓아야 한다.
  • Java는 동기화를 위한 라이브러리와 API가 풍부하다. 모니터, 오목 락, 세마포어, 조건 변수 등이 있다.
  • 임계 영역 문제를 푸는 또 다른 접근 방식은 트랜잭셔널 메모리, OpenMP, 함수형 언어들 등이 있다. 함수형 언어들은 흥미로운데, 절차적 언어들과 패러다임 면에서 다르기 때문이다. 절차적 언어들과 다르게, 함수형 언어들은 상태를 저장하지 않으므로 레이스 컨디션과 임계 영역 문제로부터 자유롭다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중