운영체제 - 7장 동기화 예제

7장 주제

• 동기화 문제 중 bounded-buffer(유한 버퍼), readers-writers, dining philosophers를 설명한다.

• 리눅스와 윈도우에서 동기화 문제를 해결하기 위해 사용한 도구(tool)들에 대해 설명한다.

• POSIX가 어떻게 프로세스 동기화 문제에 사용될 수 있는지 설명한다.

고전적인 동기화 문제들

유한 버퍼 문제 (The bounded buffer problem)

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

counter 변수 없이 mutex만 사용해서 문제를 해결할 수 없다. counting semaphore인 full, empty를 사용하는 것이 효율적이다.
(세마포의 값 = 리소스의 개수)

아래 코드는 생산자가 소비자를 위해 꽉 찬 버퍼를 생산해내고, 소비자는 생산자를 위해 비어 있는 버퍼를 생산해내는 코드로 해석할 수 있다.

생산자와 소비자 코드는 유사성을 띄며, 각각 별도의 뮤텍스 락을 사용하는 것이 효율적이다.

Readers-Writers 문제

하나의 DB가 다수의 병행 프로세스 간에 공유된다고 가정하자.

이들 프로세스들 중의 일부는 데이터베이스의 내용을 읽기만 하고 어떤 프로세스들은 데이터베이스를 갱신(읽고, 쓰기)를 원할 수 있다.

두 reader(읽기만 수행)가 동시에 공유 데이터 접근해도 문제가 생기지 않지만, 하나의 writer(읽기와 쓰기 수행, 데이터를 업데이드 시킨다)와 어떤 다른 스레드 (reader or writer)가 동시에 데이터베이스에 접근하면 문제가 된다.

readers-writers 문제 : 위와 같은 문제점이 발생하지 않도록 보장하기 위해, 우리는 writer가 쓰기 작업 동안에 공유 DB에 대해 배타적 접근 권한을 가지게 할 필요가 있다.

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

1. reader preference - reader가 끝날 때 까지 writer는 실행되지 못한다. - writer 기야 상태 야기
2. writer preference - writer가 끝날 때 까지 reader는 실행되지 못한다. - reader 기야 상태 야기

1번 문제 해결안

• reader 프로세스는 아래 자료구조를 공유한다.
  

• mutex와 rw_mutex 이진 세마포는 각각 1로 초기화되고 read_count는 0으로 초기화된다.

• rw_mutex 세마포는 reader와 writer가 모두 공유한다.

  • rw_mutex : reader와 writer 상호베타용 세마포
  • mutex : reader가 read_count를 업데이트하기 위해 사용하는 mutex 세마포
  • read_count : reader의 수를 count

reader-writers 문제와 그의 해결안들은 일반화 되어 몇몇 시스템에서는 read-writer 락을 제공한다.

해당 락을 획득할 때에는 읽기인지 또는 쓰기인지의 모드를 구분해야 한다.

• 프로세스가 공유 데이터를 읽기만 원한다면 읽기 모드의 reader-writer 락을 요청
• 공유 데이터의 수정을 원한다면 쓰기 모드의 read-writer 락을 요청

읽기 모드의 reader-writer 락은 여러 개의 프로세스가 동시에 획득하는 것이 가능하다.
Writer는 공유 데이터를 배타적으로 접근해야 하므로 오직 하나의 프로세스만이 쓰기 모드의 reader-writer 락을 획득할 수 있다.
=> reader 선호 알고리즘

해당 알고리즘 해석

• 자신이 유일한 reader라면 writer와 경쟁, 그렇지 않다면 다른 reader가 들어오는 것을 허용

• reader가 중복해서 들어오는 것을 허용

• 더 이상 reader 없으면 writer를 허용

  • reader가 writer 보다 많고, 읽기만 하는 프로세스와 쓰기만 하는 스레드를 식별하기 쉬울 때 유용한 방법이다.

공정한 reader-writer : 선착순으로 CS에 들어가서 reader의 중복을 최대한 허용하는 방식. 이 방식에서는 늦게 온 reader/writer가 기다리고 있는 다른 reader/writer를 앞지르지 못한다.

식사하는 철학자들 문제

식사하는 철학자들 문제 : 고전적인 동기화 문제. 많은 부류의 병행 제어 문제의 한 예이고, 교착 상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것이다.

생각하고 먹으면서 그들의 생애를 보내는 5명의 철학자를 고려해 보자. 철학자들은 원형 테이블을 공유하며, 이 테이블은 각각 한 철학자에 속하는 5개의 의자로 둘러싸여 있다.
테이블 중앙에는 한 사발의 밥이 있고, 테이블에는 다섯 개의 젓가락이 놓여 있다.
철학자가 생각할 때는 다른 동료들과 상호 작용하지 않는다. 때때로 철학자들은 배가 고파지고 자신에게 가장 가까이 있는 두 개의 젓가락（자신과 자신의 왼쪽 철학자 그리고 오른쪽 철학자 사이에 있는 젓가락）을 집으려고 시도한다.
철학자는 한 번에 한 개의 젓가락만 집을 수도 있다. 분명히 철학자는 이미 옆 사람의 손에 들어간 젓가락을 집을 수는 없다.
배고픈 철학자가 동시에 젓가락 두 개를 집으면, 젓가락을 놓지 않고 식사를 한다.
식사를 마치면, 젓가락 두 개를 모두 놓고 다시 생각하기 시작한다.

세마포 해결안

• 한 가지 간단한 해결책은 각 젓가락을 하나의 세마포로 표현하는 것이다.
• 철학자는 그 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 시도한다. 그는 또한 해당 세마포에 signal() 연산을 실행함으로써 자신의 젓가락을 놓는다.

  공유 자료를 다음과 같이 선언한다 : semaphore chopstick[5];

chopstick의 원소들은 모두 1로 초기화된다.

problem : 두 철학자가 동시에 식사하지 않는 것을 보장하지만(베타), 교착 상태를 야기할 가능성이 있기 때문에 채택할 수 없다.

교착 상태를 피하는 3가지 방법

• 테이블에 최대 4명만 앉는다.
• 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 집도록 허용한다.
• 비대칭 해결안, 짝수번 철학자는 왼쪽, 오른쪽 순서로, 홀수번 철학자는 오른쪽, 왼쪽 순서로 집는다.

모니터 해결안

교착 상태가 없는 해결안을 제시함으로써 모니터 개념을 설명한다.

이 해결안은, 철학자가 처할 수 있는 세 가지 상태들을 구분할 필요가 있다. 이러한 목적으로 다음의 자료구조를 도입한다.

철학자 $i$는 그의 양쪽 두 이웃이 식사하진 않을 때만 변수 state[i] = EATING으로 설정할 수 있다.

조건 (state[(i+4) % 5] != EATING) 그리고 (state[(i+1) % 5] != EATING) 이 성립할 때만

또한 다음을 선언할 필요가 있다.

이 해결안은 철학자는 양쪽 젓가락 모두 얻을 수 있을 때만 젓가락을 집을 수 있다는 제한을 강제한다.
self는 철학자 $i$가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 젓가락 집기를 미룰 수 있게 한다.

• pickup() 함수는 젓가락을 집는다.
• putdown() 함수에 마지막 부분에서 좌우에 누가 먹기를 기다리고 있으면 깨워준다.
• test() 함수는 $i$의 왼쪽과 오른쪽 철학자 모두가 식사 중이 아니면 i는 식사가 가능 -> $i$를 식사중으로 설정 -> $i$를 깨움
• initialization_code() 함수는 모든 철학자를 THINKING 상태로 초기화한다.

각 철학자 $i$는 pickup()와 putdown() 함수를 따른다.

이 해결안은 교착 상태는 없지만 기아 상태는 가능하다.

커널 안에서의 동기화

Windows, Linux 운영체제에서 제공되는 동기화 기법을 설명한다.

Windows 동기화

• Windows 운영체제는 실시간 응용과 다중 처리기 지원을 제공하는 다중 스레드 커널이다.

커널 레벨 동기화 메커니즘

• Windows 커널이 단일 처리기에서 전역 정보를 액세스할 때에는 동일한 전역 정보를 액세스할 가능성이 있는 인터럽트 핸들러가 실행되지 않도록, 인터럽트를 잠시 동안 못 걸리게 막는다.
• 다중 처리기 시스템에서는 Windows는 스핀락을 써서 전역 정보 액세스를 통제한다. (windows 커널은 짧은 코드에 대해서만 스핀락을 사용한다.
• 효율성을 위해서 스레드가 스핀락을 가지고 있는 동안에는 선점되지 않도록 보장한다. (spinlock을 가진 스레드가 preempt되면 deadlock이 발생할 수 있다.)

사용자 레벨 동기화 메커니즘

• 스레드는 dispatcher 객체를 사용하여 mutex 락, 세마포, event 및 타이머를 포함한 다양한 기 법에 맞추어 동기화할 수 있다.

  • event : 어떤 조건을 만족하면 기다리던 스레드에게 notify()한다. (조건 변수와 유사하다.)
  • timer : 한 개 이상에 스레드에게 시간이 초과되면 notify()한다.

• Dispatcher 객체는 signaled 상태에 있을 수도 있고 nonsignaled 상태에 있을 수도 있다.

  • Signaled: 객체가 사용 가능하고 그 객체를 얻을 때 그 스레드가 봉쇄되지 않음을 뜻 함
  • Nonsignaled 상태는 객체가 사용할 수 없고 그 객체를 얻으려고 시도하면 그 스레드가 봉쇄됨을 뜻함
    • dispatcher 객체마다 waiting queue가 있고, object가 signaled 상태로 바뀌면 queue에 대기하던 모든 스레드 또는 일부를 깨운다.

  

Linux 동기화

• 버전 2.6 이전 Linux는 비선점형 커널이었다. 즉 커널 모드에서 실행 중인 프로세스는 더 높은 우선순위의 프로세스가 실행 가능한 상태가 되더라도 선점될 수 없었다.

• 그러나 지금의 Linux 커널은 완전히 선점 가능하며, 따라서 커널 모드에서 실행 중일 때도 태스크는 선점될 수 있다.

Linux는 커널 안에서 동기화를 할 수 있는 많은 다른 기법을 제공한다.

• 세마포
• 아토믹 연산
• 스핀락
• 뮤텍스 락

Linux 커널에서 스핀락과 mutex 락은 재귀적이지 않다. 즉, 스레드가 이러한 락중 하나를 획득했다면 획득한 락을 해제하지 않고는 같은 락을 다시 획득할 수 없다. 해제하지 않으면 락을 획득하려는 두 번째 시도는 봉쇄된다.

POSIX 동기화

(복습 필요)

POSIX API는 뮤텍스 락, 세마포, 조건 변수를 제공한다.

이 API는 UNIX, Linux 및 macOS 시스템의 개발자가 스레드를 생성하고 동기화하는 데 널리 사용된다.

mutex lock

락을 생성하고 선언하는 코드

Mutex 락은 Pthreads에서 사용할 수 있는 기본적인 동기화 기법을 대표한다. Mutex 락은 코드의 임계구역을 보호하기 위해 사용된다.
즉, 스레드는 임계구역에 진입하기 전에 락을 획득하고 임계구역에서 나갈 때 락을 방출한다.
Pthreads는 mutex 락의 데이터 형으로 pthread_nmtex_t 데이터 형을 사용한다. Mutex는 pthread_mutex_init() 함수를 호출하여 생성한다.
첫 번째 매개변수는 mutex를 가리키는 포인터이다. 두 번째 매개변수로 NULL을 전달하여 속성을 디폴트 값으로 초기화한다.

락을 흭득하고 풀어준 코드

Mutex는 phtread_niutex_lock()과 pthread_mrtex_unlock() 함수를 통하여 각각 획득되고 방출된다.
Mutex 락을 획득할 수 없는 경우에 획득을 요청한 스레드는 락을 가지고 있는 스레드가 pthread_mutex_unlock() 함수를 호출할 때까지 봉쇄 된다.

모든 mutex 함수는 연산이 성공했을 경우 0 값을 반환한다. 만일 오류가 발생한 경우에는 이 함수들은 0이 아닌 오류 코드를 반환하게 된다.

semaphores

POSIX는 기명(named)과 무명(unnamed)의 두 유형의 세마포를 명기하고 있다. 기본적으로 이 두 가지는 매우 유사하지만 프로세스 간에 생성 및 공유되는 방식이 다르다.

기명 세마포는 관련 없는 프로세스들에 의해 동기화에 사용될 수 있고, 무명 세마포는 지원되지 않는다.

POSIX 기명 세마포

sem_open() 함수는 POSIX 기명 세마포를 생성하고 여는 데 사용된다.

관련 없는 프로세스 사이에서 동기화할 때 사용하기도 한다.

세마포를 생성하고 선언하는 코드

이 경우 세마포를 SEM이라고 부르고 있다. 0-CREAT 플래그는 세마포가 존재하지 않는 경우 생성될 것임을 나타낸다. 또한 세마포는 매개변수 0666을 통해 다른 프로세스에 읽기 및 쓰기 접근 권한을 부여하고, 1로 초기화된다.

세마포를 흭득하고 방출하는 코드

POSIX 무명 세마포

무명 세마포는 sem_init() 함수를 사용하여 셍성 및 초기화되며 세 개의 매개변수가 전달된다.

• 세마포를 가리키는 포인터
• 공유 수준을 나타내는 플래그
• 세마포의 초기

세마포를 생성하고 선언하는 코드

이 예제에서 플래그 0을 전달하면 세마포를 만든 프로세스에 속하는 스레드만 이 세마포를 공유할 수 있음을 나타낸다. (0이 아닌 값을 제공한 경우 세마포를 공유 메모리 영역에배치하여 서로 다른 프로세스 간에 공유할 수 있다.) 또한 세마포를 값 1로 초기화한다.

POSIX 무명 세마포는 기명 세마포와 동일한 sem_wait () 및 sem_post() 연산을 사용한다. 다음 코드 예제는 위에서 만든 무명 세마포를 사용하여 임계구역을 보호하는 방법을 보여준다.

세마포를 흭득하고 방출하는 코드

condition variable

Pthread의 조건 변수는 모니터 문맥 내에서 사용되며 모니터가 데이터 무결성을 보장하는 락 기법을 제공한다.
Pthread는 일반적으로 C 프로그램에서 사용되며 C에는 모니터가 없으므로 조건 변수에 mutex 락을 연결하여 락킹을 제공한다.

Pthread의 조건 변수는 pthread_cond_t 데이터 유형을 사용하고 pthread_cond_init() 함수를 사용하여 초기화된다. 이 코드는 조건 변수 및 관련 mutex 락을 생성하고 초기화한다.

pthread_cond_wait() 함수는 조건 변수를 기다리는 데 사용된다. 이 코드는 Pthread 조건 변수를 사용하여 스레드가 조건 a == b가 true가 될 때까지 대기하는 방법을 보여준다.

조건 변수와 연관된 mutex 락은 pthread_cond_wait () 함수가 호출되기 전에 획득되어야 한다. 이는 가능한 경쟁 조건으로부터 조건 절의 데이터를 보호하는 데 사용되기 때문이다.

대체 방안들

대체 방안들로는 트랜잭션 메모리, OpenMP, 함수형 프로그래밍 언어가 있다.

트랜잭션 메모리

메모리 트랜잭션: 메모리 읽기와 쓰기 연산의 원자적인 연속적 순서이다. 그러나 락과 세마포 같은 동기화 기법을 사용하는 것은 교착 상태와 같은 많은 잠재적인 문제를 야기할 수 있다. 또한 스레드의 개수가 증가할수록 락을 소유하기 위한 스레드의 경쟁 수준이 매우 높아지므로 전통적인 락킹 기법은 규모 적응성을 보이지 않는다.

전통적인 기법에 대한 대안으로 트랜잭션 메모리의 이점을 취할 수 있는 새로운 기능을 프로그래밍 언어에 추가할 수 있다. 새로운 구조물 atomic{S}가 추가되었다고 가정하자. 이 구조물은 S 내의 연산이 트랜잭션으로 실행된다는 것을 보장한다.

트랜잭션은 모든 연산이 올바르게 처리되어 commit(확정)되거나, 또는 취소되서 원점으로 롤백하는 두 가지만 가능하다.

OpenMP

OpenMP는 컴파일러 디렉티브와 API로 구성된 코드로 병렬구역으로 인식되어 시스템의 처리 코어 개수만큼의 스레드에 의해서 실행된다.

생략

함수형 프로그래밍 언어

• 함수형 프로그래밍 언어는 명령형 언어가 제공하는 패러다임과는 많이 다른 패러다임을 따른다. (명령형 혹은 절차형 언어는 상태에 기반을 둔 알고리즘을 구현하는 데 사용된다.)

• 근본적인 차이는 함수형 언어는 상태를 유지하지 않는다는 것이다. 즉, 변수가 정의되어 값을 배정받으면 그 값은 변경될 수 없기 때문에 변하지 않는다. 함수형 언어는 변경 가능 상태를 허용하지 않기 때문에 경쟁 조건이나 교착 상태와 같은 쟁점에 대해 신경 쓸 필요가 없다.

• 데이터 경쟁 다루는 방식에 접근법에 대해 현재 Erlang과 Scala 두 개의 언어에 대한 관심이 증가한다.