process synchronization에 대해 학습하기 전에 먼저 시스템 안에서 데이터가 접근되는 패턴에 대해서 간단하게 알아보자.
위 그림처럼 연산을 위해서 연산할 데이터를 가져오고, 연산된 결과를 어딘가에 저장하는 것이 시스템 어느 곳에서나 작동하는 메커니즘이다.
데이터를 저장하는 곳을 storage box, 연산하는 곳을 execution box라고 하면
Execution Box가 'CPU'일때, Strorage Box는 '메모리',
Execution Box가 '컴퓨터 내부'일때, Strorage Box는 디스크,
Execution Box가 '프로세스'일때, Strorage Box는 '해당 프로세스의 주소 공간' 일 수 있을 것이다.
만약 데이터를 읽기만하면 누가 어디서 읽든 몇 개의 박스가 데이터를 읽든 상관이 없다. 하지만 저장된 데이터를 읽어와서 수정하고 다시 저장하는 일이 벌어지기 때문에 누가 먼저 읽어갔는지에 따라 데이터가 달라지고 문제가 생길 수 있다.
이러한 문제를 동기화 문제라고 하고 해당 포스트에서는 이러한 동기화 문제에 대해 다룰 것이다.
Race Condition
위와 같은 그림에서 왼쪽의 box가 데이터를 가져가서 +1을 하고, 오른쪽 box가 데이터를 가져가서 -1을 하면 문제가 되지 않는다. 하지만 만약 왼쪽 박스가 데이터를 가져가서 연산을 하는 사이에 오른쪽 박스가 데이터를 가져가서 -1을 한다면 왼쪽 box가 +1을 한 내용은 반영되지 않는다. 이러한 문제가 동기화 문제이다.
즉 여러 주체가 하나의 데이터에 동시에 접근하려고 할 때 문제가 발생한다.
여러 주체가 하나의 데이터에 동시에 접근하려고 할때 이것을 race condition이라고 한다.
물론 이러한 race condition에 대한 문제는 프로세스끼리는 발생하지 않는다. 대부분의 경우에 프로세스들은 서로의 주소공간을 모르고 자신들의 공간에만 접근하기 때문이다. 하지만 프로세스 본인들이 직접 실행할 수 없는 부분, 운영체제에게 요청해서 실행해야 하는 부분에 대해서는 system call을 통해 커널의 코드가 프로세스를 대신해서 수행한다. 그런데 커널의 코드가 수행된다는 것은 커널의 데이터에 접근하는 것이다. 즉 이러한 경우에 다수의 프로세스(execution boxes)들이 하나의 커널에 접근(one storage box)에 접근하는 것이기 때문에 동기화 문제. 즉 race condition이 발생하게 되는 것이다.
또한 커널의 코드가 실행 중일때 인터럽트가 들어올 수 있다. 이때 인터럽트가 들어오면 커널 코드의 수행을 멈추고 인터럽트 처리를 해줘야 하므로(요 인터럽트도 결국 커널의 코드이기 때문에) 동기화 문제가 발생할 수 있다.
OS에서 race condition은 언제 발생하는가?
1. kernal 수행 중 인터럽트 발생 시
2. Process가 system call을 하여 kernal mode로 수행 중인데 context switch가 일어나는 경우
3. Multiprocessor에서 shared memory가 일어나는 경우
아래부터는 race condition이 발생하는 예시들이다.
1. kernal 수행 중 인터럽트 발생 시
count라는 값을 증가시키는 고급언어의 코드는 CPU 내부에서는 여러개의 instruction으로 바뀌어 수행된다.
(load, Inc, Store) 근데 요 3개의 instruction이 처리되는 도중에 인터럽트가 발생하여 count값을 호출하면 count값에 race condition이 발생한다. 즉 count값을 ++하기 위해 count값을 load해두었는데, 이때 count--을 하는 인터럽트가 들어오면 이미 앞에서 count를 load한 상태이므로 count--를 한 것은 반영이 안되고 load해둔 값을 ++하므로 결과적으로 count값은 +1 만 반영되어 저장될 것이다.
(해서 이러한 문제를 막기 위해서는 인터럽트가 들어와도 현재 수행중인 커널 코드는 모두 수행한 후에 인터럽트를 처리하도록 하면 된다.)
2. Process가 system call을 하여 kernal mode로 수행 중인데 context switch가 일어나는 경우
아래 그림처럼 프로세스가 하나만 실행되는 경우에는 race condition이 발생할 여지가 없다.
하지만 아래 그림과 같은 멀티 프로세스의 경우에 race condition이 발생한다.
프로세스A가 수행되다가 커널의 코드(count++)을 수행하려고 load했는데, 프로세스A에게 할당된 시간이 끝나버렸고, 프로세스B가 CPU를 받아 count++ 시스템콜을 하였다. 그 다음 다시 프로세스A가 count++을 수행하는데, 프로세스B가 count++을 하기전에 이미 load한 count값을 대상으로 연산하므로 최종적으로 count+2가 되는 것이 아니라 count+1만 반영되어 커널에 저장될 것이다.
정리하면 두 프로세스의 address space 간에는 data sharing이 없지만 system call을 하는 동안에는 kernal address space의 data를 access하게 된다(share). 이 작업 중간에 CPU를 preempt해가면 race condition이 발생하는 것이다.
해결책 : 프로세스가 커널모드에 있을 때는 할당 시간이 끝나도 CPU를 빼앗지 않는 것이다. 즉 위와 같은 상황에서 프로세스A의 커널모드가 끝나고 난 뒤, 유저 모드가 실행될 때 CPU를 빼앗으면 된다.
3. Multiprocessor에서 shared memory가 일어나는 경우
CPU가 여러개 있는 경우에 발생하는 race condition은 위에서 살펴본 1, 2 경우의 해결책(커널의 코드 수행 중 인터럽트 막기)으로는 해결할 수 없는 방법이다.
해서 이를 위해서는 어떤 CPU가 데이터를 가져갈 때 그 데이터에 대해서는 lock을 걸어두는 것이다. 연산을 하여 저장하기 전까지는 lock을 걸어 다른 CPU가 사용하지 못하게 하면 되는 것이다.
Process Synchronization 문제를 다시 정리하면 다음과 같다.
• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
• 일관성(consistency) 유지를 위해서는 협력 프로세스(cooprerating process)간의 실행 순서를 정해주는 메커니즘이 필요.
• Race condition
-- 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황
-- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.
Critical-Section Problem
• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• Problem
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
critical section : 공유 데이터에 접근하는 코드
critical section은 공유 데이터에 접근하는 코드를 일컫는 말이다. 아래의 그림에서 처럼 X가 공유 데이터이고, P1과 P2에 각각 X = X + 1, X = X-1 과 같은 코드가 있다면 요 두 개의 코드가 critical section인 것이다.
Attempts to Solve Problem
이제 critical section으로 인해 발생하는 Race condition을 해결하기 위한 방법을 알아보자.
일단 2개의 프로세스 P0과 P1이 있다고 가정한다. 그리고 그 두개의 프로세스는 아래와 같은 코드를 가지고 있다.
do{
entry section
critical section
exit section
remainder section
} while (1);
entry section --> lock 걸기 (제가 공유 데이터에 들어가니까 아무도 들어오지 마세요~ lock걸겠습니다!)
exit section --> lock 풀기 (제가 공유 데이터 다 썻으니까 들어올 프로세스는 들어오세요~ lock 풀겠습니다!)
이와 같은 critical section을 프로그램 적으로 해결하기 위해서는 지켜야할 충족 조건이 3가지 있다.
1. Mutual Exclusion(상호 배제)
- 프로세스 Pi가 critical section부분을 수행 중이면 다른 모든 프로세스 들은 그들의 critical section에 들어가면 안된다.
2. Progress(진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해줘야 한다.
3. Bounded Waiting(유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. 즉 특정 프로세스가 공유 데이터에 접근하기 위해 무한히 기다리는 starvation 현상이 발생해서는 안된다.
이제 critical section 해결을 위한 알고리즘들을 하나씩 알아보자.
• 알고리즘 1
첫번째 방법은 각 프로세스들에 turn이라는 변수를 추가하는 것이다. 즉 turn == 0 이면 P0 프로세스가 공유 데이터에 접근할 수 있고, turn == 1이면 P1 프로세스가 공유 데이터에 접근할 수 있다. 코드는 아래와 같다.
do {
while( turn != 0); /* my turn? */
critical section
exit section; /* now its your turn */
remainder section
} while (1);
위는 P0의 코드이다. 코드를 보면 while문에서 turn == 0일때까지 대기하다가, 0이 되면 critical section을 수행하고, turn을 1로 바꿔준다. 그러면 이제 P1이 critical section 코드를 수행할 수 있을 것이다. 그런데 위 알고리즘은 Progress 조건을 만족하지 못하는 문제가 있다.
만약 P0이 turn의 값을 바꿔주지 않으면 위의 P1은 절대 critical section을 수행할 수 없다. 즉 공유 데이터에 접근하는 프로세스가 없는데도 critical section을 수행하지 못하는 것이다. 이러한 경우에는 과잉양보 문제가 발생할 수 있다. 과잉양보문제란 만약 P0이 더 빈번히 critical section을 수행해야 하고, P1은 critical section을 가끔 수행하는 경우를 생각해보면 P0은 반드시 P1이 critical section을 수행해야만 turn이 0이 되므로 그때만 critical section을 수행할 수 있는 문제가 발생하는 것이다.
• 알고리즘 2
두번째 방법은 flag 배열을 사용하는 것이다. flag[ boolean, boolea]에 flag[0]이 true라면 P0이 critical section을 수행중인 것이고, flag[1]이 true면 P1이 critical section을 수행 중인 것이다.
즉 깃발을 들어서 "나 critical section 수행할꺼!"라고 하는 것이다. 코드는 아래와 같다.
do {
flag[i] = true ; /* Pretend i am in */
while(flag[i]); /* is he also in? then wait */
critical section
flag[i] = false; /* i am out now */
remainder section
} while (1);
그런데 위와 같은 알고리즘도 과잉양보 문제가 발생한다 만약 두 프로세스 모두 flag가 true라면 서로가 끊임없이 공유 데이터를 양보하게 된다.
• 알고리즘 3
이 방법은 flag와 turn변수를 둘 다 사용하여 모든 충족 조건을 만족시키는 알고리즘이다.
do {
flag[i] = true ; /* my intention is to enter .... */
turn = j; /* set to his turn */
while(flag[i] && turn == j ); /* wait only if ... */
critical section
flag[i] = false;
remainder section
} while (1);
하지만 Busy Waiting(spin lock)문제가 발생한다. 만약 특정 프로세스가 critical section을 수행하기 위해 while에서 대기 중이라면 쉴새없이 자신에게 CPU가 할당되었을 때도 while문을 수행하게 되는 낭비가 발생한다.
critical section을 해결하기 위해 다양한 프로그램적 해결책을 알아봤는데, 만약 하드웨어적으로 read와 write를 한꺼번에 할 수 있는 명령어를 제공한다면 사실 이와 같은 문제는 진작에 해결이 가능하다.
Synchronization Hardware
• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결 가능
• Mutual Exclusion with Test & Set
Synchronization variable:
boolean lock = false;
Process Pi
do {
while (Test_and_Set(lock));
critical section
lock = false;
remainder section
}
즉 하나의 instruction에 읽기와 쓰기를 모두 가능하게 한다면 바로 읽고 수정하면 되기 때문에 문제가 발생하지 않는 것이다.
Semaphores
세마포는 위에서 살펴본 race condition을 해결하기 위한 방법으로 해결방법들을 추상화시켜둔 것이다.
Semaphores S
아래의 atomic한 두 가지 연산에 의해서만 공유 데이터 접근, 반납이 가능하다.
세마포는 공유 자원을 사용하고, 반납하는 일을 해준다. 위 식의 S는 공유 데이터에 접근가능한 수이다.
식 P를 보면 S가 양수이면 공유 데이터에 접근이 가능하여 프로세스가 사용할 수 있고, 음수라면 while문을 돌며 기다린다.
식 V는 자원을 반납하는 연산으로, 프로세스가 공유 자원을 사용했다면 반드시 S를 증가시켜주어 다른 프로세스들이 접근할 수 있도록 해주어야 한다.
그런데 이와 같은 세마포 방식은 이전에도 살펴봤듯이 busy waiting이 발생하는 치명적인 문제가 발생한다.
해서 이와 같은 문제를 해결하기 위해 현재 공유 데이터에 접근하고 싶은데 들어갈 자리가 없어 while문을 돌면서 대기중인 프로세스들을 아예 Block시켜버려서 CPU를 받지 못하도록 하는 방법을 사용한다. 이와 같은 방법을 사용하면 CPU 리소스가 낭비되지 않을 것이다.
그런데 이전에 인터럽트 시에도 이같은 방법을 사용하여 인터럽트를 발생시킨 프로세스들을 아예 IO 큐에 넣어 대기시키는 방법을 사용했다.
이제 공유 데이터에 접근하는 프로세스에도 똑같은 방법을 적용하는 것이다.
Block & Wakeup Implementation
이와 같이 공유 데이터에 접근시 공간이 없을 때 block 시키는 방법을 Block & Wakeup이라고 한다.
이때 세마포는 아래와 같이 정의된다.
value는 공유 데이터 접근할 여유가 있는지에 대한 정수이고, process 리스트 L은 block되어 대기중인 프로세스들이다.
이때 block과 wakeup(P)는 아래와 같이 정의한다.
• block : 커널은 block을 호출한 프로세스를 suspend시킴. 이 프로세스의 PCB를 세마포에 대한 wait queue에 넣음
• wakeup(P) : block된 프로세스 P를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김.
block & wakeup을 적용한 연산은 이제 아래와 같다.
하지만 block & wakeup도 단점이 있다. block을 시키고 다시 wakeup을 할 때 마다 프로세스들의 상태를 변경시켜야하는 오버헤드가 발생하는 것이다. 만약에 critical section이 매우 짧다면 단순히 공유 데이터에 lock/unlock을 하는 방법이 훨씬 효율적일 것이다.
하지만 일반적인 대부분의 경우에는 block & wakeup가 효율성이 높다고 한다.
이렇게 두가지의 세마포 방식을 정리하면 아래와 같이 정리할 수 있다.
1. Counting semaphore
- 도메인이 0 이상인 임의의 정수값
2. Binary semaphore
- 0 또는 1값만 가질 수 있는 semaphore
- 주로 mutual exclusion (lock/unlock)에 사용
-> 이 방법이 block&wakeup 방식임
하지만 세마포는 Deadlock 혹은 Starvation이 발생할 수 있어 조심해야한다.
Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
S와 Q가 1로 초기화된 semaphore라 하자.
예를 들어 P0가 하드디스크에 있는 값 S를 읽어서 Q에 쓰려고 하고, 반대로 프로세스 P1은 S를 읽어서 Q에 쓰려고 한다. 즉 두 프로세스 모두 공유 데이터 S와 Q를 동시에 필요로한다. 하여 P0은 S를, P1은 Q를 읽은 상태에서 각각 Q, S도 필요해서 Deadlock이 걸려 영원히 Q와 S를 기다리게 되는 것이다.
Starvation
- indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포 큐에서 빠져나갈 수 없는 현상
Classical Problems of Synchronization
이번에는 synchronization에서 발생하는 전형적인 3가지 문제들을 알아보자.
1. Bounded-Buffer Problem (producer-consumer problem)
버퍼의 크기가 유한한 상황에서는 프로듀서, 컨슈머 문제가 발생한다. 이는 공유 데이터를 만들어서 버퍼에 넣는 프로듀서 프로세스와 공유 데이터를 가져가서 사용하는 컨슈머로 볼 때 두 가지 문제가 발생한다.
1. 2개 이상의 프로듀서가 같은 버퍼에 도착한 경우:
이 경우에 프로듀서가 하나의 버퍼에 공유 데이터를 같이 넣으려고 하여 발생하는 문제이다. 즉 동시에 같은 버퍼에 데이터를 넣으려고 하니 두 데이터 중 하나는 유실될 수 있을 것이다.
➡️ 해서 이와 같은 문제를 막기 위해서는 하나의 버퍼에 데이터를 쓸 때 lock을 걸어 다른 프로듀서 프로세스는 접근할 수 없도록 해야한다.
2. 2개 이상의 컨슈머가 같은 버퍼에 도착하는 경우
해당 문제는 버퍼가 유한하기 때문에 발생하는 문제이다. 프로듀서들이 도착하여 버퍼를 채우기 시작하는데, 모든 버퍼가 이미 다 차버린 것이다. 즉 컨슈머들이 데이터를 가져가지 않아서 더는 공유 데이터를 넣을 수 없는 상황이 되는 것이다.
➡️ 해서 이와 같은 문제를 막기 위해서는 가용한 자원이 있는지를 확인할 수 있도록 해야 한다.
➡️ ➡️ ➡️ 정리하면 현재 프로듀서가 동시에 접근할 때 lock을 걸고, 풀기와 버퍼가 가득차거나 버퍼가 모두 비었을 때 가용 자원으로서의 카운팅 세마포가 필요한 상황이다.
세마포 : 가용 가능한 자원의 개수를 counting하는 용도로도 사용될 수 있음.
위의 문제에서 프로듀서 입장에서는 비어있는 버퍼의 개수가 세마포의 개수가 될 수 있다.
반대로 컨슈머 입장에서는 공유 데이터가 들어있는 버퍼가 세마포이다.
아래와 같이 세마포를 사용하는 프로듀서, 컨슈머는 Bounded-Buffer Problem을 해결하게 해준다.
mutex: lock을 걸기 위한 변수, 만약 mutex == 1 이라면 공유 데이터에 하나의 프로세스만 접근할 수 있다는 것이다.
full: 공유 데이터가 들어있는 버퍼의 수
empty: 비어있는 버퍼의 수
P 연산은 자원을 획득하는 연산이고, V는 자원을 반납하는 연산이다.
Producer부터 살펴보면 아래와 같다.
- P(empty) : 버어있는 버퍼가 있는지 확인. 공유 데이터에 접근할 수 있는지 확인. 0이라면 기다려야함.
- P(mutex) : 버퍼 전체에 lock을 걸기
- add x to buffer : 버퍼에 데이터 넣기
- V(mutex) : lock 풀기
- V(full) : 내용이 들어있는 버퍼의 개수를 1 증가시킴
Consumer는 아래와 같다.
- P(full) : 차있는 버퍼가 있는가?
- P(mutex) : 있다면 lock을 걸고
- remove an item from buffer to y : 데이터 가져가기
- V(mutex) : lock 풀기
- V(empty) : 비어있는 버퍼의 개수를 1 증가시킴
2. Readers and Writers Problem
• 한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨
• read는 동시에 여럿이 해도 됨
DB는 공유 데이터이다. 이때 DB에 read를 하는 프로세스들은 동시에 도착해도 상관이 없지만, DB에 write를 하는 프로세스들은 하나씩만 순서대로 도착해야한다. 즉 reader들은 동시에 공유 데이터에 접근해도 되지만 writer들은 항상 아무 프로세스가 없을 때만 베타적으로, 족점적으로 write를 해야한다. 이와 같은 문제를 세마포를 사용하여 해결해보자.
shared data :
1. DB
2. readcount : 현재 DB에 접근 중인 reader의 수
synchronization variables :
1. mutex :공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용
2. db: reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
세마포를 사용한 코드는 아래와 같다.
Writer:
- P(db) : db에 접근할 수 있는지 확인.
- writing DB is performed : db에 쓰기
- V(db) : db 반납
Reader :
- P(mutex); : 공유 데이터들에 lock을 건다.
- readcount++; : 모든 reader가 접근하는 공유 변수인 readcount를 1올린다.
- if(readcount == 1) P(db); : 만약 본인이 최초의 reader라면, 즉 어떤 reader도 DB를 읽고 있지 않아서 본인만 읽기를 한다면 해당 reader 프로세스가 db에 lock을 건다.
- V(mutex); : 공유 데이터들에 대한 lock을 푼다.
- reading DB is performed : DB를 read한다.
- P(mutex); : 다시 lock을 건다.
- readcount --; : readcount를 1 감소시킨다.
- if(readcount == 0) V(db); : 내가 마지막으로 읽고 나가는 프로세스라면 enable writer. db를 반납한다.
- V(mutex); : lock을 푼다.
위 reader의 코드를 보면 반복적으로 lock을 걸고 풀고하는 코드가 나타난다. 이는 역시 공유 변수인 readcount 값에 접근하기 때문이다.
최초의 reader(아무도 read를 하고 있지 않은 상태에서 나타난 reader)가 db에 대한 writer들의 접근을 차단시켜야하고P(db),
마지막 reader라면(아무도 DB를 읽지 않고 본인만 읽고 이제 read 작업을 마치는 reader 프로세스), writer가 접근할 수 있도록 해줘야 하기 때문이다.V(db)
위 코드들은 writer들은 모든 reader들이 빠져 나갈때까지 기다려야 하지만, reader들은 다른 reader가 readcount에 접근하는 순간에만 멈추고, 계속해서 db에 접근할 수 있다.
➡️ ➡️ ➡️ 해서 writer의 입장에서는 starvation이 발생할 수 있다. reader들이 계속해서 온다면 writer들은 reader들이 나갈 때까지 한 없이 기다려야 하기 때문이다.
3. Dining-Phiosophers Problem
위 식사하는 철학자 문제는 철학자는 5명인데, 젓가락도 5개여서 모든 철학자가 젓가락을(공유 데이터)에 동시에 사용할 수 없는 문제이다. 아래 그림과 같다. 철학자는 eat(), thinking() 두 가지 동작을 하며, 왼쪽 젓가락부터 집게된다.
P(chopstick[i]) : 왼쪽 젓가락을 잡기
P(chopstick[i+1]%5) : 오른쪽 젓가락을 잡기
V(chopstick[i]) : 왼쪽 젓가락을 잡기
V(chopstick[i+1]%5) : 왼쪽 젓가락을 잡기
그런데 위와 같은 상황에서 i번째 철학자가 양 접가락을 모두 잡으면 i번째 철학자의 왼쪽 철학자는 오른쪽 젓가락을 못잡고, i번째 철학자의 오른쪽 철학자는 왼쪽 젓가락을 못잡는 문제가 발생한다. 해서 이와 같은 상황을 냅두면
더 이상 아무것도 진행되지 못하는 Deadlock 문제가 발생할 수 있다. 즉 모든 철학자가 배고파서 왼쪽 젓가락을 집어버린 상황에서 모든 철학자들은 오른쪽 젓가락을 끊임없이 기다리게 될 것이다.
해서 이를 세마포를 사용한 코드로 해결해보자.
enum {thinking, hungry, eating} : 철학자들의 상태
self[5] : 각 철학자들이 젓가락을 잡을 수 있는지, 아닌지에 대한 공유 데이터이다. 만약 self[3] = 0 이면 3번째 철학자는 양 젓가락을 집을 수 없다는 것이고, self[5] = 1 이면 5번째 철학자는 양 젓가락을 모두 사용할 수 있다는 것이다.
mutex : 공유 변수에 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용
먼저 pickup 메서드를 살펴보자.
pickup(int i) :
• P(mutex); : 공유 데이터에 lock을 건다.
• state[i] = hungry; : 젓가락을 들어올리려고 하므로 배고픈 상태로 변경
• test(i); : 철학자 i가 젓가락 2개를 잡을 수 있는 상태인지 테스트
test(int i) :
• if문 : test함수는 i철학자의 왼쪽 철학자도 밥을 먹고 있지 않고, 오른쪽 철학자도 밥을 먹고 있지 않다면 i철학자가 밥을 먹을 수 있
고 판단.
• 그리고 V(self[i])로 i번째 철학자에게 밥을 먹을 수 있는 권한을 준다.
• V(mutex); : 0이었던 값을 1로 바꿔서 lock을 푼다. (V는 0을 1로 바꾸는 연산)
• P(self[i]); : lock 젓가락 접근에 대한 lock을 건다.
pickdown(int i):
• P(mutex) : lock을 건다.
• state[i] = thinking : 나는 밥 먹었으니까 다시 thinking 상태로 바꿔준다.
• test((i+4)%5);
test((i+1)%5); : 그리고 내양쪽에 있는 철학자들이 혹시 배가 고픈 상태인데 내가 먹느라 기다리고 있던것은 아닌지 Test해준다.
• V(mutex) : lock을 푼다.
Monitor
지금까지 다양한 문제를 세마포를 사용하여 해결했는데, 세마포에는 문제가 존재한다.
● Semaphore의 문제점
1. 코딩하기 힘들다.
2. 정확성의 입증이 어렵다.
3. 자발적 협력이 필요하다.
4. 한번의 실수가 모든 시스템에 치명적 영향.
예1) V(mutex) --> Critical Section --> P(mutex)
P와 V의 순서를 반대로 하는 실수를 할 수 있다. <-- Mutual exclusion 깨짐
예2) P(mutex) --> Critical Section --> P(mutex)
Critical section에 접근한 뒤 계속 막아두는 실수를 할 수 있다. <-- Deadlock 발생
위 두가지 예시처럼 세마포를 사용하는 방법은 프로그래머가 직접 P, V연산을 해줘야 하기 때문에 실수가 나올 수 있고, 이는 치명적인 문제로 이어질 수 있다. 해서 Monitor를 사용할 수 있다.
모니터는 프로그래밍 언어적 차원에서 동기화 문제를 해결하는 방법이다.
Monitor :
동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
즉 위와 같은 추상화를 통해 공유 데이터에 접근하기 위해서는 위의 procedure을 통해서만 접근할 수 있게 하는 것이다.
모니터는 프로그래밍 언어적 차원에서 프로그래머의 부담을 줄여준다.
위 그림처럼 공유 데이터에 접근하기 위해서는 미리 정의된 operations들을 통해서만 가능하다.
Monitor의 특징:
• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명식적으로 코딩할 필요 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용.
condition x, y :
• Condition variable은 wait와 signal 연산에 의해서만 접근 가능.
x.wait() :
• x.wait()을 Invoke한 프로세스는 다른 프로세스가 x.signal을 invoke하기 전까지 suspend된다.•
x.signal() :
• x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.
모니터를 적용하여 공유 데이터에 접근하는 producer, consumer의 코드는 각각 아래와 같다.
코드를 보면 공유 데이터에 접근하기 전에 lock을 걸고 푸는 내용이 없는 것을 볼 수 있다.
모니터를 사용하면 모니터가 하나의 프로세스만이 접근하도록 관리해주기 때문에 코드에 lock을 걸고 풀고 하는 내용이 필요없어지는 것이다. (wait연산은 세마포의 P연산, signal연산은 세마포의 V연산과 유사한 역할을 한다.)
condition 변수 : 어떤 조건을 만족하지 않아서 오래 기다려야 할 때 그 프로세스를 잠들게 하는 용도로 사용된다.
마지막으로 모니터를 사용한 식사하는 철학자 문제 코드를 보면 아래와 같다.
특히 state 공유 변수에 접근하는 코드를 보며 모니터 안에서 접근하기 때문에 lock을 걸고 푸는 내용이 없는 것을 볼 수 있다.
출처 : 이화대학교 반효경 교수님의 운영체제 강의
http://www.kocw.net/home/search/kemView.do?kemId=1046323
'EH 운영체제 강의' 카테고리의 다른 글
| Memory Management (0) | 2022.08.23 |
|---|---|
| Deadlock (0) | 2022.08.21 |
| CPU 스케쥴링 (0) | 2022.07.01 |
| 5. 프로세스 - 스레드 (0) | 2022.06.21 |
| 4. 프로세스 (0) | 2022.05.20 |
