OS - 병행제어

Process Synchronization

프로세스 동기화는 공유 데이터를 여럿이 동시에 접근할 때, 데이터를 읽고 수정하고 저장하는 과정이 atomic(원자적)하게 수행이 안돼서 도중에 CPU가 넘어갔을 때 생기는 문제를 해결하는 것이다.

shared data 의 concurrent access(동시접근)은 inconsistency(불일치)문제를 발생시킨다.

consistency(일관성)을 유지하기 위해선 공유데이터를 사용하는 cooperating process(협력 프로세스) 간 orderly execution(실행순서) 를 정하는 메커니즘이 필요하다.

이 메커니즘이 Process Synchronization 이다.

위 그림처럼 연산 할 때는 항상 어디선가(Memory, Disk, Virtual Memory) 데이터를 읽어 와서 연산한다.
문제는 아래그림처럼 Data를 한군데서 연산하는 것이 아닐 경우다.

count 가 증가했다 감소하면 원래 값이 돼야 정상이다,

만약 좌측 E-box 가 count++ 시키는 와중에 우측 E-box 가 count-- 할 경우
동시접근, 동기화문제로 인해 count++ 가 일어나지 않은일로 될 수 있다.

Race Condition(경쟁상태) 라고 한다.

Race Condition(경쟁조건)

이렇게 S-box 를 공유하는 E-box 가 여러 개인 경우를 Race Condition 상태라 한다.

프로세스가 Shared Memory, Multi Processor 기능을 사용 안한다면 당연히 Race Condition 이 일어나지 않을 거라 생각하지만
프로세스A 와 프로세스B 가 System Call 을 통해 OS가 접근할 수 있는 Data를 변경하고 요청한다면 Race Condition이 일어날 수 있다.

System Call 로 인한 Race Condition

프로세스가 System Call 하여 Kernel mode로 수행 중 문맥교환이 일어날 경우

프로세스A는 user mode 와 kernel mode 에서 번갈아 수행된다.

user mode 에서는 가상메모리를 사용하기 때문에 다른 프로세스와 data sharing이 없다.
하지만 kernel mode에선 kernel address space를 사용하기 때문에 다른 프로세스와의 공유가 발생할 수 있다.

프로세스A는 이미 count 를 레지스터에 저장한 상태이다,
이 상태에서 CPU를 뺏겼다 받으면 프로세스B 가 증가시킨 count 변수로 연산하는 것이 아닌 문맥교환을 통해
복원된 예전 레지스터의 count변수로 연산하기 때문에 count 를 2번 증가시켰지만 실제로는 1번 증가한다.

해결책은 kernel mode 에서 프로세스가 수행 중일 땐 CPU를 Preempt(선점)하지 않고 user mode 로 돌아갈 때 CPU를 넘기면 된다.
각 프로세스 CPU burst time이 달라질 순 있지만 융통성을 추구한다.

인터럽트 발생으로 인한 Race Condition

System Call 이 아닌 인터럽트 발생 시 Race Condition 이 생기는 경우.

kernel mode 에서 count 를 레지스터에 load 하고 증가시키려는 도중
Interrupt call 이 들어와서 현재 문맥을 저장하고 count-- 하는 인터럽트 수행코드를 실행한다.

그리고 다시 문맥에 보관해 놓았던 count를 레지스터에 복원한다,
그러면 인터럽트가 수행했던 count 감소는 반영되지 않는다.

인터럽트의 Race Condition 해결책은 더 까다롭다.
둘 다 kernel code 라 kernel address space 를 공유하고
interrupt 는 중요하기 때문에 끝날 때 까지 오래 기다려줄 수 없다.

하지만 융통성을 중요시 하는 OS는 변수가 그림의 빨간 점처럼 E-box 연산결과가 S-box 에 저장될 때 까지 interrupt 수행을 잠시 멈춘다(disable/enable)

아무리 인터럽트라 해도 연산이 끝난 후 CPU 를 Preempt 해야 Race Condition 문제가 발생하지 않는다.

Multiprocessor 에서 Shared Memory 사용시 Race Condition

CPU가 여러 개일 때 발생하는 상황이다. 마찬자기로 Kernel mode 에서 발생한다.

프로세스는 각자 별도의 주소공간이 있어 상관없지만 OS는 아니다.
CPU1 이 interrupt 때문에 count 를 접근하고
CPU2 도 interrupt 때문에 count 를 거의 동시에 접근한다면 역시 문제가 생길 수 있다.

2번의 해결책인 interrupt disable/enable 로는 해결할 수 없다.
CPU1 에서 발생한 interrupt 를 막아도 CPU2 에서 발생한 interrupt 까지 막을 순 없다.

첫 번째 해결방법은 kernel 에 동시에 하나의 CPU 만 접근하도록 하는 것이다.
하지만 비효율적인 방법이라 사용하지 않는다.

두 번째 해결방법은 kernel shared data 접근 시 lock/unlock 하는 방법이다.
CPU1이 count 연산후 unlock 해주기 전에는 CPU2는 count 에 접근하지 못한다.
물론 해당 과정에서도 중간에 CPU를 뺏기더라고 문제가 생기지 않도록 하는 기술이 필요하다.

공유 데이터를 건드리는 code 를 critical section 이라 한다.

P1 이 critical section 을 수행 중일 땐
P2 는 critical section 을 접근하지 말아야 한다,
이것이 lock과 unlock의 개념이다.

동기화문제 해결 충족 조건

아래에서 설명하는 3가지 조건들이 충족되어야 동기화 문제로부터 해방될 수 있다.

1. Mutual Exclusion (상호배제, Mutex로 줄여말함)
프로세스A 가 critical section 부분을 수행 중이면
다른 프로세스들은 critical section 동시에 접근 하면 안 된다.

2. Progress (진행)
아무도 critical section 에 있지 않은 상태일 때 프로세스가 critical section 에 들어가는 것을 요청하면 허가해 주어야 한다.

3. Bounded Waiting (유한대기)
프로세스가 critical section 에 들어가려고 요청한 후 그 요청이 허용될 때까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야 한다.
즉 특정 프로세스만 critical section 에 들어가지 못하는 starvation 이 발생하면 안 된다.

동기화 변수 사용시 발생문제

Synchronization variable(동기화 변수, 일종의 lock) 를 사용했을 때 발생할만한 동기화 문제를 알아본다.

프로세스A 의 코드

프로세스B 의 코드

critical section 에 들어가기 전 turn이란 동기화 변수를 통해 자신의 차례인지 확인한다.
작업이 다 끝나면 turn 을 상대방의 값으로 바꾸어 상대방이 들어갈 수 있게 해준다.
turn=0 일 때 프로세스A 의 차례이고 turn=1 일 때 프로세스B 의 차례이다.

위 동기화 충족조건에 Mutual Exclusion 은 충족하지만 Progress는 충족하지 못한다.

프로세스A가 연달아 critical section에서 작업을 해야 할 때 turn 이 변경되지 않다 critical section에 들어가지 못한다.

프로세스B 가 최소 한번 critical section에서 작업을 해줘야 프로세스A 가 번갈아 가면서 들어갈 수 있다.

깃발 알고리즘 발생문제

프로세스마다 flag 을 사용하는 알고리즘이다.

프로세스i, 프로세스j 가 critical section 에 들어가기 전후 항상 자신의 flag 값을 변경
항상 다른 프로세스의 flag[x]=false 인지 확인하고 critical section 에 입장하는 방식이다.

이 알고리즘 역시 Mutual Exclusion은 충족하지만 Progress 충족하지 않는다.

프로세스i 는 flag[i]=true 바꾸고 critical section 에 들어가기 위해 루프하면서 flag[j]=false 될 때까지 기다린다.

하지만 프로세스i 가 타이머나 인터럽트로 인해 프로세스j 에게 다시 CPU를 뺏길 경우.
프로세스j 역시 critical section 사용을 위해 flag[j]=true 로 바꿀 것이고
flag[i]=false 로 변할 때까지 기다릴 것이다.

프로세스i, 프로세스j 모두 깃발이 내려갈 때 까지 기다리는 것이다.
서로 깃발만 들고 끊임없이 양보하는 상황이 발생할 수 있다. (향후 이야기할 데드락 상태가 발생한다)

피터슨 알고리즘

peterson이 만든 알고리즘이다. flag, turn 을 모두 사용한다.
critical section 에 들어가기 전 깃발을 들고 turn 을 상대방의 값으로 변경한다.

프로세스i 입장의 코드이다.

상대방의 깃발이 들려있는 상태이고 상대방 차례라면 기다리고
둘 중에 하나라도 아니라면 critical section 에 들어간다.
그리고 다 쓰고 나올 땐 깃발을 내린다.

하드웨어를 사용한 동기화

동기화 문제는 항상 어떤 데이터를 변경하는 와중에 CPU를 뺏겨서 발생한다.

데이터를 읽어서 변경을 하고 저장하는 과정중 CPU를 빼앗기지 않고 한번에 atomic 하게 수행할 수 있다면
동기화 문제는 발생하지 않는다.

이 atomic한 과정을 Synchronization Hardware(하드웨어 동기화)를 통해 수행할 수 있다.

이 하드웨어를 사용하기 위한 기계어로 Test & Set, Compare & Swap 이 있다.

• Test & Set 메모리 위치의 내용을 수정하고 이전 값을 단일 원자 연산으로 반환.
• Compare & Swap
  메모리 위치의 내용을 주어진 값과 원자적으로 비교하고, 동일한 경우에만 해당 메모리 위치의 내용을 주어진 새 값으로 수정.

이 과정을 flag 같은 변수에 적용할 수 있다면 피터슨 알고리즘같이 복잡한 알고리즘은 필요 없다.

a값을 읽고 값을 true 로 설정하는 것을 atomic 하게 수행하는 그림이다.
a를 critical section 에 들어가기 위한 lock 으로 사용한다.

a값이 참이건 거짓이건 일단 true로 세팅하고 이전값을 반환한다.

Synchronization Hardware 명령을 사용할 수 있으면 코드는 매우 간단해 질 수 있다.
대략적으로 아래와 같은 코드를 가진다.

volatile bool lock = false; // global lockPtr

bool Test_and_Set(bool* lockPtr) {
    bool oldLock = *lockPtr;
    *lockPtr = true;
    return oldLock;
}

당연히 초기 Test_and_Set 은 false 를 반환함으로 쉽게 while 문을 탈출하게 되고 critical section 을 수행한다.

그리고 해당 스레드가 다시 lock=false 를 수행하기 전 까지는 어떠한 스레드도 while 문을 탈출하지 못하게 되는 것이다.

세마포어

Semaphores 는 일종의 추상 자료형이다.

추상 자료형이란 어떻게 구현되는지는 자세히 모르고 객체와 명령어로 정의되는 것이다.
정수 추상자료형을 예로들면 정수형 변수들을 포함하여 정수 덧셈이나 곱셈 같은 연산자들 까지를 추상 자료형이라 한다.

Semaphore 는 일종의 공유자료로 객체와 명령어로 구성되는지 알면 된다.
Semaphore 변수 S 가 있을 때 아래 두 가지 atomic 연산으로 어떻게 사용하는지 알아보자.

물론 Semaphore 는 atomic 연산이 있어야 하면 위에서 말한 Synchronization Hardware 같은 지원이 있거나 해야 한다.

S 는 자원의 개수이다, S=5 이면 획득할 수 있는 자원이 5개란 뜻이다.

P(S) 내용은 아래와 같다.
S<=0 이면 자원이 없기에 계속 while 문에서 기다리고
S>0 이면 자원의 여분이 있기에 S 값을 하나 내리고 자원을 사용하는 코드를 이어 실행한다.

V(S) 내용은 보면 연산은 자원을 다 쓰고 나왔을 때 자원을 반납하는 뜻이다.

만약 S=1 일 경우 P 와 V 연산은 Synchronization 에서 말한 lock, unlock의 개념으로 봐도 된다.
뮤텍스 라고 명칭을 붙여 사용한다.

공유 자원 개수가 1인 세마포어를 Binary semaphore, 뮤텍스 라 부르기도 한다.
공유 자원 개수가 여러개인 세마포어를 Counting semaphore 라 한다.

즉 공유자원들을 counting 하고 현재 남아있는 자원이 있는지 없는지 확인하고 제어하기 위해서 Semaphore 변수를 사용한다.

Semaphore 변수 mutex=1 로 초기화하고 P(mutex), V(mutex) 연산을 통해 critical section 에 들어가는 코드이다.

그림처럼 Semaphore 변수를 사용하면 critical section 의 동기화 문제를 쉽게 해결 가능하다.

busy waiting(spin lock), block & wakeup(sleep lock)

충족조건을 다 만족하지만 비효율 적인 문제가 있다.
CPU burst time 이 다할 동안 while문을 계속 루프 도는 것이다.
이 상황을 busy waiting(spin lock)이라 한다.

while 문을 빠져나올때 까지 루프돌기 보다 다른 프로세스에게 CPU를 빨리 넘기는 것이 효율적이다.

위의 코드도 while(s<=0) 을 계속 돌기보단 공유 자원이 해제될 때 까지 CPU를 넘기는 것이 효율적이다.
이를 block & wakeup(sleep lock) 방식이라 한다.

구조체로 Semaphore 를 정의한다.

value 변수와 프로세스들을 줄 세울 Linked List 구조가 하나 있다.

value 는 자원수, L 은 프로세스 wait queue 이다.

이제부턴 busy waiting 하지않고 block system call(sleep lock) 호출한다.

커널은 해당 프로세스를 suspend 하고 이 프로세스의 PCB를 위 그림처럼 Semaphore의 wait queue 에 넣는다.
그리고 다른 프로세스가 V(S) 연산을 통해 공유자원에서 나온다면 suspend 되었던 프로세스를 wakeup 시켜 PCB를 ready queue로 옮긴다.

코드로 바꾸면 아래와 같다.

block & wakeup 이 busy waiting 의 코드와 차이점은 아래와 같다.

P(S) 연산에서 S 값을 일단 1 빼고 보는 것이다.
자원여분이 없는 상황이라도 1을 빼기 때문에 음수가 될 수도 있다.
S<0 경우는 프로세스가 block 된 상태에서 공유자원 S 을 기다리고 있는 상황인 것이다.

그리고 V(S) 내용을 보면 S 값을 일단 증가시킨다.
그렇다고 S 값이 무조건 양수가 되는 것은 아니다.
Semaphore 의 wait queue 에서 프로세스 하나를 꺼내서 wakeup 시킨다(block->ready).

block & wakeup 이 busy waiting 차이를 요약하면

busy waiting 의 value 는 자원의 여분의 개수 확인하는 거라면
block & wakeup 의 value 는 공유자원을 대기하는 프로세스의 유무를 확인하는 것이다.

공유자원을 얻으려면 wait queue 에서 block(대기)하며 자원은 다쓴 프로세스가 V(S) 를 통해 자신을 wakeup 해줄때 까지 기다려야 한다.

일반적인 경우엔 busy wait 보단 block & wakeup 효율이 좋지만
critical section 의 길이가 극도로 짧을 경우 block & wakeup 과정이 overhead 가 더 큼으로
busy wait 가 더 효율적일 수 있다.

또 공유자원의 경쟁이 치열할 때는 많은 프로세스가 기다려야하기 때문에 block & wakeup 이 효율적이지만
공유자원이 한산하면 busy wait 도 크게 나쁘진 않다.

세마포어 와 데드락

뮤텍스는 단순히 critical section 에 상호배제를 구현하기 위한 방식이다.
lock 을 설정하고, 해당 lock 을 설정한 프로세스만이 lock 을 해제할 수 있다.

이런 특징때문에 뮤텍스는 priority inheritance 속성을 가지는데
lock 을 빨리 해제하도록 시키기 위해 해당 공유자원을 기다리는 가장 높은 권한을 lock 을 가진 프로세스에게 상속시키는 것이다.

세마포어는 단순히 lock 으로 구현하지 않고 block & wakeup 방식을 사용하기 때문에,
특정 프로세스를 멈췄다 다시 실행시키는 방식으로 운영할 수 있어 순서를 지정할 수 있다.
다른 프로세스가 세마포어 공유자원 해제를 할 수 있기 때문에 가능한 일이다.

Semaphore 는 민감한 알고리즘이다. 코딩 시 조금만 잘못 사용해도 문제가 생긴다.

예를 들어 Semaphore 변수 S, Q 가 있는데 P0, P1이 두 S, Q 를 동시에 필요로 할 때
아래 예제는 Deadlock 문제가 발생할 수 있다.

P0 은 P(S) 연산 후 P1 에게 CPU를 뺏기고 P1 은 P(Q) 연산을 수행한다.
P1 은 P(S) 를 수행하고 싶지만 P0 에게 자원이 있기에 CPU는 다시 P0 에게 넘어간다.
이런 상황이 계속 반복되며 이후의 연산은 영원히 수행되지 않는다.

두 프로세스다 일이 끝난 다음에 자원을 내놓는 V 연산을 수행하고 그전엔 절대 자원을 release하지 않기 때문에 이런 문제가 생긴다.

위처럼 둘 이상의 프로세스가 서도 상대방에 의해 충족되는 상황을 무한히 기다리는 상황을 Deadlock이라 한다.

Deadlock은 starvation이라 할 수도 있다.
starvation 이 각각의 입장에서 굶어 죽는 경우라면 Deadlock 은 여럿이 얽혀 굶어 죽는 경우다.

위의 예제는 다음과 같이 코딩하면 해결할 수 있다.

자원을 얻는 순서를 바꾸면 해결 가능하다.
사소한 문제로 데드락이 발생할 수 있으니 개발 시 Semaphore는 신중히 사용해야한다.

Classical Problems of Synchronization (동기화의 고전적 문제점) 들을 알아본다.

생산자 소비자 문제(Producer-Consumer-Problem)

Bounded-Buffer Problem: 유한 버퍼 문제라 부르기도 한다.

크기가 유한한 버퍼를 공유 사용할 때 생기는 문제다.

여기서 프로세스의 종류는 생산자 프로세스와 소비자 프로세스가 있다. 생산자 프로세스는 데이터를 만들어 버퍼에 집어넣고 소비자 프로세스는 버퍼에서 데이터를 꺼내가는 역할이다.

공유 버퍼를 사용할 때 소비자, 생산자 둘 다 동기화 문제가 발생할 수 있다.

생산자 프로세스A가 비어있는 버퍼에 데이터를 집어넣으려는 순간 CPU를 다른 생산자 프로세스B에게 뺏기고 B가 그 버퍼에 데이터를 입력한다, 그리고 다시 CPU를 받은 프로세스A는 데이터를 프로세스B가 저장한 버퍼에 덮어씌우면서 버퍼의 데이터가 유실될 수 있다.

동기화 문제 방지를 위해 생산자 프로세스A는 데이터 입력 전 버퍼에 Lock을 걸고 비어있는 버퍼의 위치를 다음 버퍼로 설정 후 데이터를 입력하고 Unlock해야 한다.

소비자 프로세스A는 버퍼에서 데이터를 꺼내가려는 순간 생산자 프로세스B에게 CPU를 뺏기고 B가 그 버퍼의 데이터를 꺼내간다, 그리고 다시 CPU를 받은 프로세스A는 꺼내갈 데이터가 없어지게 된다.

소비자 프로세스 또한 데이터를 꺼내가지 전 버퍼에 Lock을 걸고 채워져 있는 버퍼의 위치를 다음 버퍼로 설정 후 데이터를 꺼내가고 Unlock해야 한다.

생산자 입장에선 빈 버퍼가, 소비자 입장에선 차있는 버퍼가 자원(Shared Data)이다. Empty&Full 버퍼시작위치 같은 버퍼의 조작변수 또한 자원이다.

위처럼 버퍼의 개수를 세는 작업(resource count)할 때는 Counting semaphore, 버퍼에 Lock과 Unlock작업(mutual exclusion)할 때는 Binary semaphore가 적합하다.

생산자 프로세스와 소비자 프로세스의 코드는 아래와 같다.

P연산은 Semaphore변수를 1빼는 것, V연산은 Semaphore변수를 1증가시키는 것이다.

버퍼의 개수 n, Counting semaphore변수 full=0, empty=n(전부 비워져 있는 상황),
그리고 Binary semaphore변수 lock/unlock용 mutex가 있다.

Producer프로세스는 x라는 data를 만들고 버퍼에다 집어넣기 전 P(empty)연산을 통해 empty를 1 감소시키고 빈 버퍼를 얻어야 한다. 만약 얻지 못했다면 Consumer프로세스의 V(empty)연산이 수행될 때까지 기다려야 한다.

그리고 P(mutex)연산을 통해 1이었던 mutex를 0으로 설정, 버퍼에 Lock을 걸고 데이터를 넣은 후 V(mutex)연산을 통해 Unlock한다.
V(full)연산은 full변수를 1증가하고 Full buffer를 만드는 마무리 연산이다.

Consumer프로세스가 P(full)연산과정에서 Full buffer를 기다리고 있다면 Producer의 V(Full)연산이 block돼있는 Consumer프로세스를 깨운다.

Consumer프로세스도 마찬가지다. Full buffer를 얻고 Lock을 건 후 버퍼에서 데이터를 꺼내 y버퍼에 넣고 Unlock하고 V(empty)연산을 수행한다.

만약 Producer프로세스가 Empty buffer를 기다리고 있다면 wakeup시킨다.

읽기 쓰기 문제(Readers and Writers Problem)

공유 데이터에 접근하는 프로세스는 두 종류가 있다.

• 읽는 프로세스(Reader)
• 쓰는 프로세스(Writer)

두 종류의 프로세스가 동시에 공유 데이터에 접근하면 당연히 문제가 발생하기 때문에 막아야 한다.

lock, unlock 을 통해 간단히 해결 가능하지만 효율이 좋지 않다.
DB에서 위처럼 사용한다면 매우 느려질 것이다.

우선 Reader프로세스들은 동시에 접근해도 되고 Writer는 무조건 혼자 접근할 수 있도록 해야 한다(배타적).
Writer가 접근할 때는 모든 Reader와 Writer프로세스의 접근을 막아야 한다.

DB를 예로 들면 공유 자원으로는 DB자체와 DB접근변수인 read count(DB에 접근중인 Reader의 수)가 있다.

readcount가 1이상이라면 이미 reader가 접근중인 상황이고 DB에 lock이 걸려 있더라고 다른 reader들이 접근할 수 있도록 해줘야 한다.
만약 read count가 0인데 DB에 lock이 걸려있다면 Writer가 접근중이어서 다른 Reader와 Writer모두 막아야 한다.

Readers and Writers Problem 코드는 아래와 같다.

readcount는 공유 자원이기 때문에 동시접근을 막기 위한 semaphore변수 mutex(lock)가 필요하다. DB자체는 semaphore변수 db를 사용해 표현하고 lock/unlock한다.

Writer의 코드는 간단하다. DB에 접근 전 lock을 걸고 접근 후 unlock한다. Reader코드는 다른 Reader들도 동시에 접근할 수 있도록 하기 위해 복잡하다.

항상 readcount접근 전 mutex를 통해 lock unlock작업을 해야 한다.

readcount를 증가하고 readcount가 1인지 확인한다. 이는 Reader프로세스인 자신 외엔 DB에 접근중인 프로세스가 없다는 뜻이다.

일단 Writer의 접근을 막기 위해 P(db)연산을 통해 lock을 건다. 만약 readcount가 1보다 크다면 다른 reader가 있기 때문에 굳이 P(db)연산을 할 필요가 없다.

DB 사용 후엔 readcount를 감소하고 0인지 확인하다. 이는 자신이 DB에 접근중인 마지막 프로세스인지 확인하는 것이다.

자신 외 아무도 DB를 사용하지 않는다면 V(db)를 통해 unlock한다. 만약 다른 Reader가 있다면 Writer의 접근을 막기위해 V(db)연산을 수행하지 않는다.

이 코드의 문제는 Reader들이 계속 들어오게 된다면 Writer프로세스는 Starvation이 발생 가능한 코드다.

이를 해결하기 위해선 신호등처럼 Writer가 접근할 수 있는 시간을 만들어 줘야한다.

식사하는 철학자(Dining-Philosophers Problem)

5명의 철학자가 식탁에 둘러 앉아있다. 철학자는 앉아서 2가지 행동을 한다. 생각하는 것과 먹는 것.

철학자의 양옆에는 젓가락(공유자원)이 하나씩 있다. 한명이 식사중이라면 다른 한명은 못 먹는 상황이 발생하고 젓가락을 나눌 수 없으니 동시접근을 막아야한다.

모든 철학자들이 동시에 배고 고파져서 모두 오른쪽 젓가락을 하나씩 집는다면 왼쪽 젓가락이 없어 모두가 영원히 밥을 못 먹는 상황이 된다.

위 코드에선 5개의 mutex(5개의 lock/unlock) chopstick[5] 가 있다.

P(chopstick[i])를 통해 자신의 왼쪽 젓가락을 lock,
P(chopstick[(i+1)%5]) 를 통해 자신의 오른쪽 젓가락을 lock하고 eat() 을 실행한다.

이 경우 5개의 프로세스가 P(chopstick[i]) 만 실행 후 CPU를 뺏긴다면
위의 영원이 밥을 못 먹는 Deadlock 가능성이 발생한다.

해결방법은 3가지가 있다.

1. 4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
2. 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.(맨 위의 순서 변경과 같은 원리이다.)
3. 젓가락 두 개를 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

3번째 경우를 코드화 해서 보자.

self의 값은 이 양옆 젓가락을 잡을 수 있다면1, 아니면 0이다. 초기 값이 1이 아닌 이유는 권한을 먼저 테스트하기 때문이다. Binary semaphore self[i]는 i번째 철학자의 권한을 가리킨다.

공유자원으로는 젓가락을 잡을수 있는 권한 도 있지만 주변 철학자들의 상태 변수 state[5]가 있다.

Binary semaphore mutex는 공유변수 접근 전 lock/unlock 용이다.

코드를 보면 먹기 전 젓가락을 들어서(pickup) 밥을 먹고(eat) 먹은 후 내려놓고(putdown) 생각하는(think) 구조이다.

pickup함수 코드를 보면 공유변수state 접근 전 P(mutex)를 통해 lock을하고 상태를 지정하고 test함수를 호출한다.

test함수를 보면 i철학자의 왼쪽 철학자(state[(i+4)%5])가 밥 먹고 있지 않고 i철학자는 배고프며 오른쪽 철학자(state[(i+1)%5])도 밥 먹고 있지 않은 경우

상태를 eating으로 바꾸고 V(self[i])연산을 통해 self[i]를 1로 세팅하여 젓가락2개를 잡을 수 있는 권한을 주게 된다.

특이한건 바로 젓가락을 잡는 것이 아닌 V연산을 통해 권한을 받게 되는 것 이다. 권한을 받으면 비로소 P(self[i])연산을 실행할 수 있다.

만약 test함수에서 if문 조건에 부합하지 않아 V연산을 실행하지 못하고 test함수를 빠져나오면 당연히 P(self[i])연산에서 대기 중일 것 이다(sleep). 이 경우 주변 철학자가 putdown함수를 실행할 때 까지 기다려야 한다.

putdown함수 코드를 보면 밥을 다 먹고 상태를 thinking으로 변경하고, 자신의 양옆 철학자(state[(i+4)%5]), state[(i+1)%5])를 위해 test함수를 호출한다.

즉 양옆 자기 젓가락만 내려놓는 것이 아닌 주변 철학자들의 젓가락 잡을 수 있는 권한을 대신하여 주는 것이다.

나중에 P(self[i])연산을 못하고 있던 프로세스의 CPU차례가 돌아오면 주변의 철학자가 대신 권한을 준 상태이기 때문에 P연산을 실행가능하다.

Monitor

지금까지 세마포어를 통해 process synchronization 문제들을 해결하였다.
하지만 위의 코드들을 보면 쉽게 사용이 힘들다(복잡한 알고리즘…).

위 그림처럼 코딩실수로 공유자원에 들어가기 전 V연산을 수행하면 동시접근이 발생하고,
공유자원에서 V연산을 실행하지 않고 P연산을 실행하면 Deadlock이 발생한다.

위의 경우라도 동시접근이나 Deadlock이 발생 안할 수 있다. 즉 세마포어 검증(correctness)이 힘들기 때문에 신중히 쓰여야 한다는 뜻이다.

여러 프로세스들의 자발적 협력(voluntary cooperation)이 필요하고 한 번의 실수가 모든 시스템에 치명적 영향을 끼칠 수 있다.

세마포어 연산을 제공해 주었을 뿐 책임까지는 지지 않았고 동기화 문제는 프로그래머가 책임지었다(lock/unlock과정이 모두 프로그래머에게 있었다).

이를 완화하기 위한 것이 Monitor다.

Monitor는 프로그래밍 고급 언어차원에서 지원하는 동기화 수단이다.
Monitor에는 공유자원을 책임지는, 공유자원을 위한 연산들이 정의가 돼있다.
(아래 그림 참조)

단 공유자원을 접근할 때는 오직 Monitor의 연산을 통해서만 접근해야한다.
그러면 공유자원안에서 Monitor의 연산도 하나만 실행할 수 있도록 다 알아서 해준다.

즉 lock/unlock 과정을 생략하고 Monitor안의 연산만 써도 동기화 문제가 해결 된다는 뜻이다.

Monitor의 추상적 그림

동그란 부분 전체가 Monitor다.

맨 윗부분은 공유자원, x와 y는 공유자원안 변수들이다.
중간은 Monitor의 연산, 맨 아래는 초기화 코드이다.
entry queue 는 공유자원 접근을 기다리는 프로세스들이다.

하나의 프로세스가 공유자원 접근을 위해 Monitor의 연산을 사용 중이라면 Monitor가 알아서 동시 접근을 막기 위해 다른 프로세스들은 entry queue로 대기시킨다.

공유자원은 lock/unlock작업 외에 개수를 세는 작업도 있었다.
버퍼예제처럼 자원들을 하나씩 쓰다가 더 이상 쓸 자원이 없을 때 프로세스를 block시켰는데

block된 프로세스를 위해 Monitor에서는 Condition Variable(일종의 큐)을 사용한다.

보통 공유자원을 사용 못할 때는 queue에서 대기시킨다, 이 queue를 Condition Variable이라 한다.

시스템에 대해 배울때 보았던 그림이다. 여기서의 queue가 Condition Variable이라 할 수 있다.

그림에서 x와 y를 사용하려고 기다리는 프로세스들을 Condition Variable 에 줄 세운 것을 볼 수 있다. Condition Variable에 접근시키기 위해 wait와 signal연산을 사용한다.

1. Monitor의 Bounded-Buffer Problem (생산자 소비자 문제)

세마포어의 코드와 비교해보자.
세마포어에선 counting변수 full=0, empty=n으로 초기화하고 이 값을 기준으로 P와 V연산 실행여부를 가렸다.

Monitor의 Condition Variable은 세는 과정(더하고 빼는 과정)이 생략 돼있고 초기 값을 설정할 필요도 없다.

Monitor의 코드를 보면 semaphore보다 훨씬 자연스럽고 상식적이다.

그저 자원이 없으면 기다리고 자원이 있으면 깨우고 다음에 자원을 쓸 프로세스를 깨워주기만 하면 된다.

produce(생산자)연산의 코드를 보면 만약 empty buffer가 없다면 wait()호출, 있다면 empty buffer에 값을 넣고 full의 signal()호출한다.

이 간략한 코드는 Monitor에서 이미 entry queue를 통해 프로세스들의 동시 접근을 막고 있기 때문에 가능하다(produce와 consume은 동시에 한개 프로세스만 접근 가능).

semaphore와 유사한 측면이 있지만 프로그래머가 체감하는 것은 크다.

semaphore는 원자적 연산만 제공만 해주는 반면 Monitor는 lock/unlock, 공유자원의 개수변경 모두 신경 쓸 필요가 없다.

2. Monitor의 Dining-Philosophers Problem (식사하는 철학자)

철학자의 상태변수, 젓가락잡는 권한은 공유데이터.

젓가락을 잡는 행위(pickup), 놓는 행위(putdown), 젓가락을 모두 잡을 수 있게 테스트(test)하는 행위는 모니터의 연산이다.

putdown연산을 호출할 때 putdown안의 test연산이 양 옆의 철학자를 깨워준다. semaphore의 알고리즘과 동일하다.