Consumer-Producer
while (true) {
/* produce an item in next produced */
while (counter == BUFFER_SIZE);
/* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
while (true) {
while (counter == 0);
/* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in next consumed */
}
// 카운터 변수의 추가적인 도입으로 버퍼의 마지막 칸을 채우지 못했던 문제를 해결할 수 있다
Race Condition
둘 이상의 스레드(프로세스)가 동일한 데이터에 동시에 접근할 때 실행 순서에 따라서 결과가 달라지는 오류 상황
여러 프로세스가 동시에 동일한 데이터를 접근하고 조작할 때, 실행 결과가 접근이 일어나는 특정 순서에 따라 달라지는 경우
Race Condition을 방지하려면 상호 배제와 프로세스 간 동기화가 보장되어야 한다.
Critical Section은 둘 이상의 스레드가 동시에 접근하면 안 되는 코드 영역
Critical Section Problem
둘 이상의 프로세스가 공유 자원에 접근할 때 동시 접근으로 인한 충돌 없이 올바르게 동작하도록하는 방법을 정의하는 문제
두 개 이상의 프로세스가 동시에 Critical Section을 실행해서는 안 됨
프로세스들이 데이터를 협력적으로 공유할 수 있도록, 활동을 동기화하기 위한 프로토콜을 설계하는 것이 목적
Entry Section
프로세스나 스레드가 Critical Section에 진입하기 전에 동기화 조건을 확인하고 진입을 시도하는 코드 영역
Exit Section
프로세스나 스레드가 Critical Section 실행을 마친 후 공유 자원에 대한 접근 권한을 해제하는 코드 영역
나머지 코드는 Remainder section
Solution to Critical-Section Problem → three requirements:
Mutual Exclusion는
둘 이상의 프로세스나 스레드가 동시에 Critical Section에 접근하지 못하도록 하는 상호 배제 원칙
(프로세스 Pi가 자신의 Critical Section을 실행 중이라면, 다른 어떤 프로세스도 Critical Section을 실행할 수 없음)
Progress는
어떤 프로세스도 Critical Section에 있지 않고, 특정 프로세스가 Critical Section에 들어가기를 원할 때
적절한 시간 내에 Critical Section에 진입할 수 있도록 보장하는 조건
Bounded Waiting는
한 프로세스가 Critical Section에 들어가기를 요청한 후, 그 요청이 승인되기 전까지
다른 프로세스들이 Critical Section에 들어갈 수 있는 횟수에는 상한이 있어야 한다는 조건
P0와 P1이 fork() 시스템 호출을 사용하여 자식 프로세스를 생성하고 있음
Mutual Exclusion이 없다면 동일한 pid가 서로 다른 두 프로세스에 할당될 수 있음
싱글코어 코어 환경에서는 공유 변수가 수정되는 동안 인터럽트가 발생하지 않도록 막을 수 있다면 해결 가능
현재 명령어 시퀀스가 선점 없이 순서대로 실행될 수 있고,
다른 명령어가 실행되지 않기 때문에 공유 변수에 예기치 않은 수정이 발생하지 않는다.
멀티 코어 환경에서는 다른 코어에서 접근이 가능하므로 이 방법이 소용이 없다
Non-preemptive kernel
커널 모드가 블락되거나, 자발적으로 CPU를 양보할 때까지 실행
본질적으로 Race Condition이 발생하지 않음
Preemptive kernel
커널 모드가 실행 중일 때 프로세스가 선점이 가능
설계가 특히 어렵고 복잡하지만, 더 높은 응답성을 가질 수 있음
하지만 Race Conditon을 막을 방법이 필요하다
Peterson’s Solution
Critical Section 문제에 대한 고전적인 소프트웨어 기반 해결책
Peterson의 해결책이 항상 올바르게 작동한다는 보장은 없음
현대 컴퓨터 아키텍처가 load와 store 같은 기본 기계어 명령어를 수행하는 방식 때문
하지만 Critical Section 문제를 해결하는 알고리즘적 설명으로는 훌륭
Peterson's Solution은 문제 상황을
두 프로세스가 임계 구역과 나머지 구역을 번갈아가며 실행하는 경우로 제한
두 프로세스는 두 변수를 공유
int turn; // 누가 임계 구역에 들어갈 차례인지
boolean flag[2] // 각 프로세스가 임계 구역에 들어갈 준비가 되었는지
(flag[0] = true이면 프로세스 P0가 준비된 상태임을 의미)
Algorithm with turn
각 프로세스가 다음 프로세스에게 차례를 넘겨줌
Mutual Exclusion은 보장되지만 Progress는 보장되지 않음
while();
() 내부가 false가 되면 무한 루프를 탈출하고 다음으로 넘어간다
(가령, P0의 cs가 실행되는 데 1분 걸리고, P1의 cs가 실행되는 데 1시간이 걸린다고 하면)
(어떤 프로세스도 Critical Section에 있지 않고, 특정 프로세스가 Critical Section에 들어가기를 원할 때
적절한 시간 내에 Critical Section에 진입할 수 있도록 보장하는 조건)
Algorithm with flag
Mutual Exclusion은 보장되지만 Progress은 보장되지 않음
flag[0] = flag[1] = true인 경우 교착 상태(Deadlock)가 발생할 수 있음
(0번 깃발을 들고, 1번 깃발이 내려와 있는 것을 확인 후 진입 허용)
=> (0번 깃발도 들고 있고, 1번 깃발도 들고 있는 경우에는 둘 다 진입할 수 없으므로 진행 보장 x)
Peterson’s Solution
flag, turn 둘 다 쓰면 해결 가능
(1) Mutual Exclusion이 보장됨
P0는 flag[1] = false 이거나 turn = 0인 경우에만 Critical Section 진입
(0번 차례이거나, 1번 차례이더라도 1번이 들어가지 않는 경우)
(2) Progress 충족됨
(3) Bounded-waiting 충족됨
(0번 프로세스에서 flag[0] 깃발을 true로 든 다음에, turn은 1번 프로세스로 넘겨줌)
Peterson's solution이 현대 아키텍처에서 항상 작동한다는 보장은 없다
성능 향상을 위해 컴파일러가 의존성이 없는 연산의 순서를 변경할 수 있다 (reorder operations)
싱글스레드에서는 결과가 항상 같기 때문에 문제가 없음, 멀티스레드에서는 순서 변경이 예상치 못한 결과를 초래할 수 있음
Peterson’s Solution
boolean flag = false;
int x = 0;
스레드 1
while (!flag);
print x;
스레드 2
x = 100;
flag = true;
예상 출력은 무엇인가?
예상 출력은 100
하지만 스레드 2의 연산이 다음과 같이 재배열되는 경우,
flag = true;
x = 100;
이 경우 출력이 0이 될 수 있음
This allows both processes to be in their critical section at the same time!
(둘 이상의 프로세스가 동시에 Critical Sectioin에 진입할 수 있다)
컴파일러의 명령어 재배열로, turn과 flag의 명령어 순서가 바뀌면, critical section에 두 프로세스가 진입하는 것을 허용하게 됨
(P0의 turn=1;과 flag[0]=true; 사이에서 Context Swithcing이 발생하면)
(P1은 flag[0]=false 때문에 cs에 진입할 수 있게 되고)
(P0는 trun=0 때문에 cs에 진입할 수 있게 되어 Mutual Exclusio이 깨지게 된다)
Hardware Support for Synchronization
하드웨어 명령어는
critical-section problem 해결을 지원,
직접 동기화 도구로 사용될 수 있고, 더 추상적인 동기화 메커니즘을 형성하는 데도 사용
(1) Memory Barriers
메모리의 모든 변경 사항이 다른 모든 프로세서에 visible되도록하여
컴파일러 리오더링을 방지하는 하드웨어 명령어이다
전체 코어 정보를 메모리에 전부 적재 시키는 cpu 제공 operation
(flag → memory_barrier() → turn 으로, 컴파일러 리오더링을 방지)
(2) Hardware Instructions
많은 현대 컴퓨터 시스템은 원자적으로 실행되는 특별한 하드웨어 명령어를 제공
atomic operation은 하드웨어적으로 지원되는 중단 불가능한 하나의 연산 단위
Test-and-Set
Definition:
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = true;
return rv;
}
1. Executed atomically
2. Returns the original passed parameter value
3. Set the new value of passed parameter to true
Solution using test_and_set()
Shared boolean variable lock, initialized to false
do {
while (test_and_set(&lock)); /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
처음 진입하는 프로세스는 lock이 false이므로
tas(&lock)은 false를 리턴하고(따라서 critical section 진입), 동시에 lock을 true로 바꿔준다(atomic 하게 동작)
lock이 true로 되어있으므로, c.s.에 들어와 있는 프로세스가 공유 자원 작업을 마치고 lock을 false로 바꿔줄 때까지
다른 프로세스는 임계영역에 진입할 수 없다 (while-loop에 걸린다)
tas는 하드웨어적으로 동시 수행을 막는다 (조금이라도 더 빠른 애를 먼저 수행시킴)
Compare-and-Swap
Definition:
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
1. Executed atomically
2. Returns the original value of passed parameter value
3. Set the variable valuethe value of the passed parameter new_value
but only if *value == expected is true. That is, the swap takes place
only under this condition.
Solution using compare_and_swap
Shared integer lock initialized to 0;
while (true){
while (compare_and_swap(&lock, 0, 1) != 0); /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
(lock == 0이면 0을 뱉고 1로 바꿈)
(lock == 1이면 1을 뱉고 바꾸지 아니함)
Bounded-waiting Mutual Exclusion with compare-and-swap
while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = compare_and_swap(&lock,0,1);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = 0;
else
waiting[j] = false;
/* remainder section */
}
Atomic Variable은 동시에 여러 스레드가 접근해도 중단 없이 일관된 연산이 보장되는 변수로,
내부적으로 원자적(atomic) 연산을 수행한다.
Atomic Variables
compare and swap() 명령어는 atomic variable 구성하는 데에도 사용
Atomic Variable은 기본 데이터 타입에 대해 원자적 연산을 제공하여,
Race Condition이 발생할 수 있는 단일 변수에 대해 Mutual Exclusion을 보장하는 데 사용할 수 있다
예를 들어, atomic 변수인 sequence에 대해
increment(&sequence); 연산을 수행하면 sequence가 중단 없이 증가함이 보장됨
The increment()function can be implemented as follows:
void increment(atomic_int *v)
{
int temp;
do {
temp = *v;
}
while (temp != (compare_and_swap(v,temp,temp+1));
}
temp랑 v 값이 다르면 CAS는 값 업데이트 하지 않음, 다시 while-loop 반복
temp랑 v 값이 같으면, CAS는 temp+1로 값을 업데이트하고, while-loop는 종료됨
Mutex Lock
critical section에 들어가기 전에 acquire()로 락을 획득하고 나올 때 release()로 해제하여
한 번에 하나의 프로세스만 Critical Section에 들어갈 수 있도록 하여 상호 배제를 구현하는 동기화 기법
임계 구역을 보호하고 레이스 컨디션을 방지하기 위해 사용됨
Mutex Lock을 위한 두 개의 함수와 하나의 변수:
acquire()와 release()
락의 사용 가능 여부를 나타내는 불리언 변수 available
acquire()와 release()는 원자적으로 구현되어야 함
test-and-set과 compare-and-swap 명령어 모두
이 함수들을 구현하는 데 사용할 수 있음
acquire() {
while (!available)
; /* busy wait */
available = false;
}
release() {
available = true;
}
acuire()은 available이 false이면 무한 루프에 가두어 놓는 역할
Busy waiting
한 프로세스가 critical section에 있고 다른 프로세스가 acquire()로 진입 시도 시
무의미한 반복 루프를 돌며 CPU 사이클을 낭비하는 문제
Busy waiting은 실제 다중 프로그래밍 시스템에서 명백한 문제임
하나의 CPU 코어가 여러 프로세스에 의해 공유되는 환경에서 다른 프로세스가 생산적으로 사용할 수 있었던 CPU 사이클을 낭비하게 된다
Spinlock
busy waiting을 사용하는 mutex lock으로,
락이 해제될 때까지 프로세스가 반복 루프를 돌며 대기하는 방식이다
장점
컨텍스트 스위치 없이 빠르게 락을 획득할 수 있어 멀티코어 환경에서 효율적으로 작동한다
Semaphore
정수형 변수로, wait와 signal이라는 원자적 연산으로
여러 프로세스 간 사용 가능한 공유 자원의 개수를 관리하는 동기화 도구
wait() 또는 P(): proberen – 테스트한다는 의미
signal() 또는 V(): verhogen – 증가시킨다는 의미
wait(S) {
while (S <= 0); // busy wait
S--;
}
signal(S) {
S++;
}
Binary semaphore
0 또는 1의 값을 가져서 뮤텍스 락과 동일하게 동작
Counting semaphore
1 이상의 값을 가질 수 있어서 여러 개의 공유 자원을 관리하는 데 사용될 수 있다
Counting semaphore 사용 방법
세마포어는 사용 가능한 자원의 개수로 초기화됨
프로세스가 자원을 사용할 때 세마포어에 대해 wait() 연산을 수행하여 값을 감소시킴
프로세스가 자원을 반납할 때 세마포어에 대해 signal() 연산을 수행하여 값을 증가시킴
카운트가 0이 되면 모든 자원이 사용 중인 상태임
그 이후로 자원을 사용하고자 하는 프로세스는 카운트가 0보다 커질 때까지 차단됨
세마포어는 다양한 동기화 문제를 해결할 수 있음
P1과 P2가 있고, S1이 S2보다 먼저 실행되어야 할 때
“synch”라는 세마포어를 0으로 초기화하여 생성
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
세마포어 연산은 busy waiting 문제를 가짐
=> wait()와 signal() 연산의 정의 수정
프로세스가 wait() 연산을 실행할 때
세마포어 값 <= 0이면, busy waiting 대신 suspend 상태로 전환
=> suspend operation은 프로세스를 waiting queue에 넣음
다른 프로세스가 signal() 연산을 실행할 때
대기 중인 프로세스는 wakeup() 연산에 의해 재시작됨 그리고 ready queue에 배치됨
Semaphore Implementation with no Busy waiting
typedef struct {
int value;
struct process *list;
} semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
sleep();
}
}
signal(semaphore *S) {
S->value++;
// value를 1만큼 더했을 때에도 0이거나 0보다 작다는 것은
// waiting queue에 프로세스가 있었다는 뜻
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
세마포어를 잘못 사용하면 탐지하기 어려운 타이밍 오류가 발생할 수 있음
mutex를 공유하며, 이 변수는 1로 초기화
각 프로세스는 critical section에 들어가기 전에 wait(mutex)를 실행
critical section을 나올 때 signal(mutex)를 실행
이 순서가 지켜지지 않으면, 두 프로세스가 동시에 critical section에 있을 수 있음
(wait와 signal의 호출 순서가 지켜지지 않는 타이밍 오류가 발생하면)
(두 프로세스가 동시에 critical section에 있을 수 있다)
(1) signal (mutex) … CS … wait (mutex): Mutual Exclusion 위반 (=> Race Condition 발생 가능)
(2) wait (mutex) … CS … wait (mutex): Deadlock 발생
(3) Omitting of wait (mutex) and/or signal (mutex):
- wait를 빠트리면, Mutual Exclusion 위반
- signal을 빠트리면, Deadlock 발생
semSignal(delay)는 producer, semWait(delay)는 consumer
Monitor
한 번에 하나의 프로세스만 내부에서 실행할 수 있도록 하며,
wait()과 signal()을 통해 프로세스 간 동기화 제공하는 고수준 동기화 구조.
세마포어와 동일한 기능을 제공하면서 제어가 더 쉬움
하나 이상의 프로시저, 초기화 시퀀스, 그리고 지역 데이터를 포함하는 소프트웨어 모듈
지역 데이터(내부 변수)는 모니터 내부 프로시저만 접근 가능하며 외부 프로시저는 접근 불가
프로세스는 모니터 내부 프로시저 중 하나를 호출하여 진입함
한 번에 오직 하나의 프로세스만 모니터 내부에서 실행될 수 있음
Condition variable
cwait와 csignal 연산을 통해 프로세스 동기화를 지원하는 모니터 내에서만 접근 가능한 특별한 데이터 타입
조건 변수는 모니터 내에 포함되어 있으며 모니터 내에서만 접근 가능함
cwait(x) 또는 x.wait():
조건 x에서 호출 프로세스를 suspend 시키고 해당 조건 큐으로 들어감
csignal(x) 또는 x.signal():
조건 x에서 cwait()로 대기 중인 프로세스 중 하나를 재개하고,
대기 중인 프로세스가 없으면 아무 작업도 하지 않음 (그 조건으로 wait하는 애 없으면 그냥 종료, semaphore과 차이점)
(urgent queue는 csignal을 호출한 스레드가 잠시 대기하는 공간)
Mutual Exclusion은 모니터 구조 자체가 담당
Synchronization은 조건 변수가 담당
Semaphore는 두 가지 모두 프로그래머가 직접 책임
장점
모니터 구조에 의해서 상호 배제가 보장되기 때문에 동기화만 고려하면 되는데,
모니터 내부에서만 동기화가 올바르게 이루어졌는지 확인하면 되기 때문에 버그 디텍션에 용이하다
(세마 포어는 동기화, 상호 배제 모두를 critical section에 진입할 수 있는 여러 부분에서 고려하여야 한다)
Condition Variables Choices
프로세스 P가 csignal(x)를 호출하고 프로세스 Q가 cwait(x)에서 대기 중일 때, 이후 어떻게 해야 하는가?
P와 Q는 동시에 실행할 수 없음, Q가 재개되면 P는 대기해야 함
(1) Signal and wait
- P는 Q가 모니터를 나가거나 다른 조건을 기다릴 때까지 대기함
- Q(cwait(x)에서 대기 중이던 프로세스) => P(csignal(x)를 호출한 프로세스)
(2) Signal and continue
- Q는 P가 모니터를 나가거나 다른 조건을 기다릴 때까지 대기함
- P(csignal(x)를 호출한 프로세스) => Q(cwait(x)에서 대기 중이던 프로세스)
Concurrent Pascal에서 구현된 모니터
P가 signal을 실행하면 즉시 모니터를 떠나고, Q가 재개됨
(cwait에서 대기 중이던 프로세스를 바로 실행하고, csignal을 호출한 프로세스는 즉시 모니터를 떠난다)
Concurrent Pascal은 csignal()이 모니터 프로시저에서 실행되는 마지막 연산이어야 함을 요구
Liveness
프로세스가 언젠가는 반드시 자신의 작업을 진행하거나 완료할 수 있음을 보장하는 속성
Infinite waiting은 Progress와 Bounded-waiting을 위반
liveness 실패로 이어질 수 있는, 두 가지 상황
– 데드락(Deadlock)
– 우선순위 역전(Priority Inversion)
Deadlock
둘 이상의 프로세스가 서로 자원을 점유한 채 상대방의 자원을 기다리면서 무한히 대기하는 상태
S와 Q를 각각 1로 초기화한 두 개의 세마포어
P0가 wait(S)를 실행하고 P1이 wait(Q)를 실행한다고 가정
P0가 wait(Q)를 실행할 때, P1이 signal(Q)를 실행할 때까지 기다려야 하는데,
P1은 P0가 signal(S)를 실행할 때까지 기다리고 있다
=> P0와 P1은 deadlock에 빠짐
Priority Inversion
낮은 우선순위 프로세스가 자원을 점유한 상태에서 높은 우선순위 프로세스가 그 자원을 기다리며 차단되는 현상
priority: P1 > P2 > P3
자원 R이 P3에게 할당, P1이 이를 원함 => P1은 P3가 자원 사용을 끝낼 때까지 기다려야 함
하지만 P2가 실행 가능해져 P3를 선점 => P3는 P2가 종료될 때까지 기다려야 함
결과적으로 우선순위가 P1보다 낮은 P2가, 간접적으로 P1이 자원에 접근하는 것을 막음
해결법: priority-inheritance 프로토콜
높은 우선순위 프로세스가 필요한 자원에 접근하는 모든 프로세스가,
자원 사용이 끝날 때까지 그 높은 우선순위를 상속받음
즉, 현재 자원 소유자는 그 자원을 얻으려는 가장 높은 우선순위 프로세스의 우선순위를 부여받음
Bounded-Buffer Problem
Bounded-Buffer를 공유하는 생산자와 소비자 간의 동기화를 다루는 상호 배제 문제
int n; // 메세지 수
semaphore mutex = 1; // C.S. 진입 시 사용
semaphore empty = n; // 비어 있는 버퍼의 개수를 셈
semaphore full = 0; // 가득 찬 버퍼의 개수를 셈
n개의 버퍼가 있으며, 각 버퍼는 하나의 아이템을 저장할 수 있음
// The structure of the producer process
while (true) {
...
/* produce an item in
next_produced */
...
wait(empty); // empty를 소비, empty가 1개도 없으면 대기
wait(mutex); // c.s. 진입
...
/* add next produced to the
buffer */
...
signal(mutex); // c.s.에서 나옴
signal(full); // full을 하나 올려줌
}
// The structure of the consumer process
while (true) {
wait(full); // full을 소비, full이 1개도 없으면 대기
wait(mutex); // c.s. 진입
...
/* remove an item from buffer to
next_consumed */
...
signal(mutex); // c.s.에서 나옴
signal(empty); // empty를 하나 올려줌
...
/* consume the item in next
consumed */
...
}
Readers-Writers Problem
읽기는 동시에 허용하되 쓰기는 배타적으로 수행되도록 동기화를 요구하는 문제
Readers: 데이터 집합을 읽기만 하며 업데이트하지 않음
Writers: 읽기와 쓰기 모두 가능함여러 리더가 동시에 읽는 것은 허용해야 함 (동기화 문제 x)
만약 writer와 다른 프로세스(reader or writer)가 동시에 데이터베이스에 접근하면 혼란이 발생할 수 있음
첫 번째 경우
– writer가 기다리고 있다고 하더라도, read 먼저 다 처리하고 read 사라지면 write를 처리해준다
두 번째 경우
– writer가 하나라도 들어오면, read 전부 멈추고, write 끝나면 reader들이 읽게끔 한다
두 경우 모두 기아를 초래할 수 있음
– 첫 번째 경우에는, writer가 기아 상태에 빠질 수 있음
– 두 번째 경우에는, reader가 기아 상태에 빠질 수 있음
첫 번째 경우 해결책
Semaphore rw_mutex는 1로 초기화 (한 쪽이 쓰고 있으면, 다른 쪽이 read든 write든 막겠다)
– rw_mutex는 reader와 writer에 공통
– rw_mutex는 writer를 위한 mutual exclusion semaphore로 작동
– 첫 번째 또는 마지막 리더가 c.s.에 들어가거나 나올 때 사용
– 다른 reader가 c.s.에 있는 동안, 들어가거나 나오는 리더들은 사용하지 않음
Semaphore mutex는 1로 초기화
– mutex는 read_count 변수를 업데이트할 때 상호 배제를 보장하기 위해 사용
Integer read_count는 0으로 초기화
– read_count 변수는 현재 객체를 읽고 있는 프로세스 수를 추적
=> read 수행 중이면 read 끝날 때까지 대기하고 write를 수행한다
// The structure of a writer process
while (true) {
wait(rw_mutex);
...
/* writing is performed */
...
signal(rw_mutex);
}
// The structure of a reader process
while (true){
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex); // 첫 번째 reader가 들어온 경우, 읽기 모드 켜겠다
signal(mutex);
...
/* reading is performed */
...
wait(mutex);
read count--;
if (read_count == 0)
signal(rw_mutex); // 마지막 reader가 나간 경우, 읽게 모드 끄겠다
signal(mutex);
}
writer가 임계 구역에 있고 n명의 reader가 대기 중이라면
한 명의 reader는 rw_mutex에 대기열에 있고
나머지 n − 1명의 reader는 mutex에 대기열에 있다
또한 writer가 signal(rw_mutex)를 실행할 때
대기 중인 reader나 writer 중 하나의 실행이 스케줄러에 의해 선택된다
Reader–Writer Lock
읽기 모드로는 여러 프로세스가 동시에 락을 획득할 수 있지만, 쓰기 모드로는 하나의 프로세스만 락을 획득할 수 있는 동기화 도구
Dining-Philosophers Problem
철학자가 배가 고파지면, 가장 가까운 두 개의 젓가락을 집으려 한다, 젓가락 2개를 집으면 밥을 먹는다
1. Semaphore Solution
각 젓가락 = 세마포어
wait() 연산을 실행하여 젓가락을 잡으려고 시도
signal() 연산을 실행하여 젓가락을 놓는다
while (true){
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );
/* eat for a while */
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
/* think for a while */
}
다섯명 모두 동시에 왼쪽 젓가락을 잡는다면, 모든 젓가락 세마포어 값은 0이 되어
오른쪽 젓가락을 잡으려 할 때 모두 영원히 대기하게 된다(데드락에 빠지게 된다)
해결책:
(1) 테이블에 동시에 앉을 수 있는 철학자의 수를 최대 네 명으로 제한
(2) 두 젓가락 모두 사용 가능할 때만, 젓가락을 잡도록 허용
(3) 홀수 철학자는 먼저 왼쪽을 집고 그다음 오른쪽을 집는다, 짝수 철학자는 먼저 오른쪽 을 집고 그다음 왼쪽을 집는다
=> 데드락은 해결할 수 있지만, 기아를 해결해 주지는 않는다
최대 네 명으로 제한
counting semphore인 room을 4로 초기화하여 시작
2. Monitor Solution
모니터를 이용하여, 두 젓가락이 모두 사용 가능할 때만 젓가락을 집을 수 있다
상태 구분: THINKING, HUNGRY, EATING
철학자 i는 변수 state[i]를 EATING으로 설정할 수 있다
단 두 이웃 철학자가 먹고 있지 않은 경우에만 (양쪽이 EATING이 아니어야 EATING이 될 수 있다)
state[(i+4) % 5] != EATING
state[(i+1) % 5] != EATING
또한 조건 변수 self[5]를 선언
이것은 철학자 i가 배고프지만 필요한 젓가락을 얻지 못할 때 기다리도록 허용
(못먹을 때 -> waiting, 먹을 수 있을 때 -> signal)
젓가락의 분배는 모니터 DiningPhilosophers에 의해 제어됨
각 철학자는 먹기 시작하기 전에 pickup() 연산을 호출 (이 동작은 철학자 프로세스의 suspend를 초래할 수 있다)
연산이 성공적으로 완료된 후 철학자는 먹을 수 있다
철학자는 putdown() 연산을 호출한다
DiningPhilosophers.pickup(i)
/** EAT **/
DiningPhilosophers.putdown(i)
모니터를 쓰기 때문에 상호 배제는 보장되며 교착 상태는 발생하지 않는다
그러나 기아는 발생할 수 있다
monitor DiningPhilosophers
{
enum {THINKING; HUNGRY, EATING}
state[5];
condition self[5];
void pickup (int i) {
state[i] = HUNGRY;
test(i); // 조건 만족하면 나와서 먹어라
if (state[i] != EATING) // 조건 만족하지 않는다면 기다려라
self[i].wait;
}
void putdown (int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5); // 나때매 못먹은 애들 있으면
test((i + 1) % 5); // 내려놓으면서 먹게 해준다
}
void test (int i) {
if ((state[(i+4)%5] !=
EATING) && (state[i] ==
HUNGRY) && (state[(i+1)%5]
!= EATING) ) {
state[i] = EATING ;
self[i].signal() ;
}
}
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}