본 자료 정리는 'Operating System Concepts'(Tenth Edition) - Abraham Silberschatz 원서에 출처합니다.
Copyright © 2020 John Wiley & Sons, Inc.
Chapter 7: Synchronization Examples
- Classic Problems of Synchronization
-> 이번 챕터에서는 Classic Problems of Synchronization 절만 정리합니다.
Objectives
- bounded-buffer, readers-writers 및 dining-philosophers(식사-철학자) 동기화 문제를 설명
Classical Problems of Synchronization
-
새로 제안된 동기화 체계를 테스트하는 데 사용되는 고전적인 문제
-
Bounded-Buffer Problem (sempaphore 이용)
-
Readers and Writers Problem (sempaphore 이용)
-
Dining-Philosophers Problem
-
Bounded-Buffer Problem
생산자와 소비자 프로세스 공유
-
n개의 buffer, 각각은 item을 가질 수 있다.
-
이진 세마포어 mutex는 1로 초기화된다.
-
카운팅 세마포어 full은 0으로 초기화된다.
(소비자가 필요한 자원) -
카운팅 세마포어 empty는 n의 값으로 초기화된다.
(생성자가 필요로 하는 자원)
Bounded Buffer Problem 2
- producer process의 구조
- consumer process의 구조
Readers-Writers Problem
데이터 세트는 여러 동시 프로세스 간에 공유된다.
-
Readers: 데이터 세트를 읽기만 한다. 업데이트를 수행하지 않음
-
Writers: 둘 다 읽고 쓸 수 있다. 업데이트를 수행
문제
-
여러 독자가 동시에 읽을 수 있도록 허용
-
오직 한 명의 작성자만 동시에 공유 데이터에 액세스할 수 있다.
-
독자랑 작가가 동시에 읽고 쓰면 문제가 발생한다.
-> 작가가 데이터베이스에 상호배제적인 접근권한이 있으면 해결된다. 이걸 독자-작가 문제 readers-writers problem 이라 부른다. 이걸로 거의 모든 새로운 동기화 프리미티브를 테스트한다.
여러 변형이 있는데, 모두 우선 순위 포함한다.
- 첫 번째 변형 - 작성자가 공유 객체를 사용할 수 있는 권한이 없으면 독자도 대기해서는 안된다.
-> 즉, 작가가 대기 중일 때 A 독자가 읽고 있다고 해서 다른 B 독자가 대기해서는 안된다는 것이다.
- 두 번째 변형 - 작성자가 준비되면 최대한 빨리 쓰기를 수행한다.
-> 작가가 공유 객체에 접근하려고 대기 중이면, 그 어떠한 독자도 읽기를 시작할 수 없다.
- 둘 다 starvation(기아)으로 인해 더 많은 변형이 발생할 수 있다.
- reader-writer lock을 제공하는 커널에 의해 일부 시스템에서 문제가 해결된다.
Readers-Writers Problem 2
세마포어 rw_mutex로 작가의 상호배제 보장. 첫번째 혹은 마지막 독자가 임계 구역을 입장하거나 퇴장할 때 사용하기도 함. 그 중간에 입장/퇴장하는 독자들은 사용하지 않음.
공유 데이터
-
이진 세마포어 rw_mutex 는 1로 초기화
-> 작가와 독자가 공동 사용, 작가의 상호배제 보장 -
이진 세마포어 mutex는 1로 초기화
-> read_count 변수가 갱신될 떄 상호배제를 보장하기 위해 사용 -
카운팅 세마포어 read_count는 0으로 초기화
-> 현재 객체를 자고 있는 프로세스가 몇 개인지를 의미
writer(작가) process 의 구조
reader(독자) process의 구조
이때 작가가 임계 구역에 있고, n 명의 독자가 대기 중이면, 한 독자는 rw_mutex에서 대기하고, 나머지 n - 1 명의 독자는 mutex에 대해 대기 중.
작가가 signal(rw_mutex)를 호출하면 대기 중인 독자나 대기 중인 한 작가의 실행을 재개해줄 수 있다. (스케줄러가 두 경우 중 하나를 고른다.)
Dining-Philosophers Problem
5 명의 철학자는 생각과 식사를 번갈아하면서 일생을 보낸다.
철학자가 사색에 잠기면 다른 철학자랑 대화를 안 한다. 중간에 배고파지면 양쪽에 있는 젓가락 가져가서 한 쌍을 만들어서 밥을 먹는다. 한 번에 한 젓가락 낱 개만 가져갈 수 있다. 먹을 땐 꼭 젓가락 한 쌍을 동시에 들고 먹고 다 먹으면 젓가락 각각 돌려 놓고 다시 사색에 잠긴다.
식사하는 철학자 문제 dining-philosophers problem는 전형적인 동기화 문제이다. 동시성 제어 문제에서 가장 큰 부류의 대표적인 예시이다. 여러 프로세스에게 여러 자원을 할당해주면서 데드락이나 기아 상태를 방지해야하는 경우를 매우 단순화한 예시이다.
Semaphore Solution to Dining Philosophers
각 젓가락을 세마포어로 두면 된다. 각 철학자는 가져갈 젓가락의 세마포어에 대한 wait() 연산으로 젓가락을 가져간다. 나중에 돌려 놓을 땐 signal() 연산을 한다.
공유 데이터
- Semaphore chopstick[5] 은 1로 초기화
이러면 동시에 두 이웃이 먹는 경우는 없음을 보장할 수 있지만, 데드락이 발생할 수 있다는 단점이 있다.
모든 철학자가 전부 동시에 배고파져서 자기 왼쪽에 있는 젓가락 집었다고 가정해보자. 모든 chopstick 원소의 값은 이제 0이니까 오른쪽 젓가락 집을 수 있을 때까지, 즉 영원히 대기해야한다. -> 데드락이 걸린다.
데드락 해결하려면 다음과 같이 하면된다.
-
두 젓가락을 다 확보할 때만 먹을 수 있다.
(양쪽 젓가락이 둘 다 사용가능할 때 집을 수 있다.) -
동시에 4명만 먹을 수있다.
-
짝수 철학자는 짝수 젓가락부터 잡고 홀수 철학자는 홀수 젓가락부터 잡는다.
이후 데드락 없도록 보장하는 식사하는 철학자 문제 해법을 제공한다. 하지만 이러한 대부분의 해법은 철학자 중 한 명이 굶다 죽을 수도 있다는 가능성이 있다. 데드락 해결했다고 해서 기아 상태를 방지해주지는 않기 때문이다.
Monitor Solution to Dining Philosophers
철학자는 오로지 양쪽 젓가락 둘 다 있을 때만 젓가락 들 수 있다는 제약 조건을 추가한다.
우선 철학자의 상태를 정의해야한다.
enum {THINKING, HUNGRY, EATING} state[5];
i 번째 철학자는 오로지 이웃들이 식사 중이 아닐 때만(state[(i+4)%5 != EATING && state[(i+1) % 5] != EATING) 식사할 수 있다(state[i] = EATING]).
추가적으로 i 번째 철학자가 배고프지만 젓가락을 못 얻었을 때 잠깐 대기할 수 있게(잠들게) 해줄 변수를 추가한다.
condition self[5];
젓가락 분배는 DiningPhilosophers 모니터가 관활한다.
각 철학자는 먹기 전에 먼저 pickup() 연산을 호출해야한다. 이때, 철학자 프로세스가 잠깐 중단될 수도 있다. 연산이 다 끝나면 철학자는 먹어도 된다. 그 다음 철학자는 putdown() 연산을 호출한다.
- 데드락은 없지만, Starvation(기아)가 발생할 수 있다.
수정할 부분이 있으면 댓글로 알려주세요 :)
