이번시간 부터는 Process Synchronization에대해서 설명해보도로 하겠다.
Race Condition
하나의 동일한 데이터를 동시에 접근하려고 할때, 어떤 하나의 주체가 데이터를 이미 읽어갔는데, 또 다른 하나의 주체가 이 동일한 데이터를 읽어갔다면, 원하는 결과가 안나올 수 있다.
어떤경우가 있을까?
-
프로세스같은 경우에는 일반적으로 독자적인 자신의 주소공간만 접근하기 때문에 이런 Process Sychronization이 잘 발생하지 않는다.
그러나 Process들이 본인이 직접 수행할 수 없는 운영체제한테 대신 부탁하기 위해 System call을 날리는데,
이때, 커널의 코드가 그 프로세스 대신에 실행되고, 커널의 코드가 실행된다는것은 커널에 있는 어떤 data값을 바꾸기 위해서 읽어들이고 있는데, 갑자기 여기서 cpu를 뺏기고 또 다른 프로세스에게 cpu를 줬는데 또 systemcall을 하고 커널의 코드를 실행하면서, 커널의 data를 접근하는 이런경우에서 발생한다. -
고로 userLevel에서는 문제들이 잘 안생기던 것들이 커널로 들어가면, 운영체제 커널에 있는 data는 여러 프로세스들이 동시에 사용할 수 있는 공유 데이터 이므로, 문제가 생길 수 있다.
문제 3가지
Interrupt Handler vs kernel
운영체제 커널이 cpu를 잡아서 쓰고 있다고 치자, count를 증가시키려고 하는데 count는 커널의 data영역에 있다고 치자.
count++는 3가지의 방식으로 구현된다.
- 메모리에 있는 변수 count를 cpu 레지스터로 불러들이고
- 증가시키고
- register값을 다시 해당 메모리에 적재하기
그런데 1번에서 읽어온 사이에 interrupt가 들어왔다면, 이 count++ 작업을 멈추고, interrupt handler가 실행된다.
즉 count가 커널에 있는 data이므로, count라는 변수 1을 뺀다.
결과적으로 우리는 -1 감소시키고 +1 해서 0이 되길 바라는데, 이미 count++에서 count값을 불러들인다음에 count--가 실행되었으므로 반영이 되지않고 1증가한것만 반영이 된다는것이다.
- 해결방법
일단 인터럽트가 들어왔더라도, 인터럽트 처리 루틴으로 넘기는 것이 아니라, count++ 작업이 끝날때 까지 인터럽트를 disable시키고, 그 다음에 count++작업이 끝나면 다시 enable하는 방식이다.
preempt a process running in kernel
Pa가 usermode에서 쓰다가 system call을 갈기고 kernel mode로 쓰고있는데 갑자기 타이머 인터럽트가 걸렸다고 치자,
그런데 문제가 이 User mode에서 실행하다 걸린게 아니라, 커널에다가 system call을 갈겨서 kernel의 code를 실행시키면서, 커널의 data인 count를 증가시키는 중이었다.
그런데 그상황에서, 할당시간이 지나서 B한테 넘어가고 B에서 count를 증가시키는 작업을 하고
다시 할당시간이 끝나서 Pa한테 cpu를 돌려줬다면,
우리가 생각하기에는 kernel에 data영역에 있는 공유변수 count는 2가 되야할것 같지만,
Pb에서 증가시킨 값은 반영이 되지 않는다.
왜냐하면, 증가되기 전에 count값을 불러들이고 그 context로 증가시키고 저장한것이기 때문에, Pa에서 count++을 하더라도 처음에 불러들인 값 count는 0이기 때문에 1만증가하여 1인것이다.
- 해결방법
커널 모드에서 수행 중일때는 CPU를 preempt하지 않는다.
커널 모드에서 수행중일때는 시간을 다써도 뺏지 않고, 커널 모드가 끝나고 userMode로 빠져나왔을때 뺏는다.
Multiprocess
마지막 문제는 CPU가 여러개 있는 환경이다. 앞에서 이야기한 해결방법 2가지로도 해결을 안된다. 왜냐하면 cpu 1번이 커널의 data에 접근하더라도, cpu2번이 커널의 data에 접근가능하기 때문이다.
그래서 lock과 unlock을 사용해야한다.
-
해결방법1
이문제가 결국 운영체제 커널을 여러 cpu가 동시에 접근해서 문제이므로, 매순간 한번에 하나의 cpu만 커널에 들어갈 수 있게 하면된다.
커널전체를 하나의 lock으로 막고, 다른 cpu가 커널에 못들어오게 한뒤에, 커널을 빠져나올때 lock을 풀어주는 방법을 쓴다.
근데, cpu가 여러개 있더라도 커널에 접근할 수 있는 cpu는 매순간 1개 이기 때문에 매우 비효율적이다. 고로, 커널 전체에 lock을 거는건 별로다. -
해결방법2
커널 내부에 있는 각 공유데이터에 접근하려고 할 때마다, 그 데이터에 대한 lock/unlock을 하는방법이다.
Critical-Section
공유데이터를 접근하는 code
이 그림과 같이 P1과 P2가 공유 데이터 x에 접근하려한다.
이때 Shared Data인 X=2가 critical-section이 아니고, 박스 표 쳐놓은 x=x+1, x=x-1이 critical Section이 된다.
그래서 한 프로세스가 크리티컬 섹션안에 들어가 있으면, 즉 공유데이터에 접근하는 code를 실행하고 있으면, 다른 프로세스한테 cpu를 뺏기더라도, 그 다른 프로세스가 크리티컬 섹션에 들어가지 못하게 하는 방식을 말한다.
Critical-section vs Remainder-section
앞에서 공유데이터에 접근하는 코드를 critical section이라하면, 그렇지 않은것들을 remainder-section이라 한다.
이것이 반복되는것이 일반적인 프로세스들의 구조이다.
프로그램적 해결법의 충족 조건
-
Mutual Exclusion: 상호배제
어떤 프로세스가 critical section에 들어가 있으면, 다른 프로세스들은 그들의 critical section에 들어가선 안된다. -
Progress
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면, critical section에 들어가게 해줘야한다. -
Bounded waiting: 유한 대기
프로세스가 critical section에 들어가려고 요청한 후에 못 들어가고 지나치게 오래 기다리는 starvation이 없어야한다.
만약 프로세스가 3개가 있는데 두개가 critical section에 번갈아서 들어가면, 나머지 하나는 Starvation이 발생한다.
Algorithm 1
P0
do{
//내가 critical section에 들어가려면 turn이 0이어야함
while(turn !=0);
critical section
turn =1;
remainder section
}while(1);P1
do{
//내가 critical section에 들어가려면 turn이 1이어야함
while(turn !=1);
critical section
turn =1;
remainder section
}while(0);각 P0와 P1이 critical area에 들어가기 위해서는 turn이 각각 0과 1이어야한다.
while문을 돌면서 turn이 0이 아니면, 1인 P1의 차례를 기다리니까 계속 while문을 뺑뻉 돌면서 기다린다.
만약 Process1이 turn을 0으로 바꿔준다면,
그때 while문을 나와서 critical section에 들어가고 작업을 완료하면, 다시 turn을 1로 되돌려서 P1이 사용하게 해준다.
=> 즉, 본인의 차례가 아니면 while문에서 대기한다.
- 문제점
Mutual Exclusion은 만족하더라도, Progress를 만족하지 못한다.
왜냐면, Algorithm1은 critical section에 교대로 들어가게 설계를 해놨다.
만약, P0가 빈번하게 critical section에 들어가고 싶고, P1이 한참 있다가 critical section에 들어간다 치면,
P0가 critical section에 들어가기 위해서는 반드시 P1이 critical Section에 들어갔다가 turn을 0으로 바꿔줘야만한다.
고로, P0가 100번 critical section에 접근하고자 하고, P1이 1번만 critical Section에 접근했다 치면, P0는 99번 critical section에 접근하지 못한다.
Algorithm2
do{
flag[i]=ture;
while(flag[j]);
critical section
flag[i]=false;
remainder section
}while(1);flag를 사용한다.
프로세스 각각 자신의 flag를 가지고 있다.
P0가 critical section에 들어가고자 한다면, 자신의 flag를 true로 바꾼다.
그다음 while문을 돌면서 상대방 flag를 체크하는것이다. while문을 돌면서 상대방도 들어가고싶은 flag가 true인것을 확인하는데, 아무도 true가 없고 나만 있으면, critical section에 들어갔다가, flag를 다시 false로 바꾼다.->상대방이 기다리고 있다가 들어갈 수 있게,
- 문제점
Progress를 만족하지 않는다.
만약에 P0가 flag를 true로 만들고 cpu를 뺏겨서 P1으로 넘어갔다면, P1도 flag로 true로 만들시에 while문에서 서로 끝없이 양보하는 상황이 발생한다.
Algorithm 3 피터슨알고리즘
do{
flag[i]=ture; //나 들어가고싶어
turn = j; //상대를 확인하기위해
while(flag[j] && turn ==j); //상대를 확인
critical section
flag[i]=false;
remainder section
}while(1);피터슨 알고리즘부터는 flag와 turn을 모두 사용한다.
process i번째가 critical Section에 들어가고자 한다면, 깃발을 세워서 true로 만들고,
그다음에 상대방을 확인하기 위해 turn을 상대로 바꾼다.
그다음에, 섹션에 들어가기 전에 while문에서 체크를 하는데, 상대방인 flag[j]가 깃발을 들고 있고, turn이 상대방 차례인지 확인해서 맞으면 while문에서 대기한다.(상대가 쓰고 있음)
상대방이 critical section에 들어가려고 하는지를 먼저 파악하고, 실제로 상대방이 critical section에 들어가도되는 차례가 맞는지 확인한다.
- 문제점
세가지 조건을 모두 만족한다.
그러나 Busy waiting(=spin lock)문제가 발생한다. cpu와 메모리를 계속 쓰면서 wait하는 것이다.
만약에 내가 critical section에 들어가고 싶다 하더라도, 상대방이 critical section에서 나와서 자신의 flag를 false로 내리지 않는이상, 내 프로세스를 사용할 수 있게 cpu를 받더라도, 계속 상대방이 critical section에서 나올때까지 while문을 뺑뺑돌고있다는 말이다.
Synchronization Hardware
Race Condition을 사실 하드웨어로 쉽게 해결할 수 있다.
일단 이 문제가 발생한 이유가 읽기와 쓰기가 동시에 이루어지지 않기 때문인데, 결국
read instruction
cpu interrupt
write instruction
이런방식이라 문제가 발생하는것이고
하나의 instruction도중에 cpu를 뺏기는 경우는 없기 때문에,
read instruction, write instruction 하나의 instruction으로 수행
cpu interrupt
이런방식이면 문제가 발생하지 않는다.
그래서 그림과 같이 Test_and_set(a)라면
- a를 읽는다.
- a값을 True로 바꾼다.
이게 한번의 instruction으로 처리가 된다.
예를 들어, a가 0이었다면 0을 읽고, 그다음에 a가 1로 바뀌는 것이고,
만약 a가 1이었다면 1을 읽고, 또 1로 세팅하는것이다.
코드를 봐보자.
만약에 내가 criticalArea로 들어가고싶다면, 0인 상태에서 while문을 돌면서 1인 즉 critical Area에 있는지 확인한다. 만약 아무도 없으면, 일단 0을 읽었으니까 1로 바꾸고 그다음에 critical Area에 들어간다.
이상태에서 다른 놈이 접근하고 싶어도 1이기 때문에 들어오지 못하고 while문에서 기다리게 된다.
내가 criticalArea 다쓰고 나오면 0으로 바뀌기 때문에 그제서야 다른놈이 들어가는 과정을 만들 수 있다.
Semaphores
추상자료형
Semaphore S가 있다면, Integer를 가질 수 있고
S에 대해서 두가지 연산이 가능하다.
P와 V라는 연산이 있다.
P연산은 공유데이터를 획득하는 과정이고, V연산은 공유데이터를 다 쓰고 반납하는 과정이라고
생각하면 된다.
S에 해당하는 Integer는 자원의 갯수이다.
만약에 S가 5인데 P연산을 한번하면 자원을 하나 가져가니까 4가 된다.
V는 내어 놓는것이니까 자원의 갯수가 4개인 상태에서 V연산을 하면 5가 된다.
P연산에서 보면, S가 0이면 자원이 없는 상태니까 while문을 돌면서 기다리는것이고, 그게 아니면 자원을 가져가야하니까 S--를 해준다.
V연산은 당연히 자원을 반납하는 것이니까 S++해준다.
그래서 이 Semaphore를 Critical Section에 표현을 해보면,
애초에 Critical Section에 들어갈 수 있는 프로세스는 1개여야하니까 mutex를 1로 설정한다.
들어가기 전에는 P연산을 통해 0 으로 만들고 나오면 V연산으로 되돌리는 것이다.
mutex가 양수면 들어가게 해주고 0이면 못들어가게 한다.
그런데 문제가, 여기서도 어차피 누가 들어가 있으면, while문 뺑뺑이 도는것 마냥 기다려야하므로, CPU를 얻더라도 할 수 있는게 없으니까 효율적이지 못하다.
그러므로, Block & Wake up 방식으로 구현해야한다.
이전에 배웠던 프로세스 상태에서도
내가 CPU를 쓰고 있다가 IO같은 오래걸리는 작업을 하기 위해서 Disk I/O Queue에 들어가면 그 프로세스 상태가 BLocked가 된다. 그래서 CPU를 얻을 수 있는 권한 자체가 사라지는 것이다.
그래서 이 DIsk IO가 끝나면 그제서야 ready Queue로 돌아와서 cpu를 얻으면 다시 프로세스를 수행하는 구조인데,
공유데이터도 마찬가지 이다. 누군가 공유데이터를 쓰고 있으면, 걔가 내어 놓을 때까지 내차례가 안오니까, 쓸때업이 while문을 돌면서 기다리는 것이 아니라, 그 프로세스 자체를 Blocked 시켜서 잠들게 하다가 공유데이터를 내놓으면, 그때 꺠어나서 ReadyQueue에 들어가서 CPU를 얻으면 공유데이터에 접근하는 방식이다.
세마 포어를 다음과 같이 정의하자.
value는 세마포어 값, 그리고 L은 Blocked 되어서 기다리고있는 queue이다.
Blocked/wake up 방식의 P와 V연산
- P연산
P연산은 자원을 얻어야하니까 S를 감소시킨다, 만약에 자원이 0보다 작다면, 자원이 없는상태 0에서 -1을 하니까 음수가 된것이므로, Blocked 시키고 L에 해당 프로세스를 넣는다.
V연산은 자원을 다 쓴 친구가 ++로 자원을 증가시키고, 그 다음에 자원이 0 이하라면, 현재 L에서 기다리고 있는 Process P가 있다는 말이므로 그걸 꺼내서 WakeUp시켜준다.
Which is better, Busy-wait vs Block/wake up
일반적으로 Block/wake up 방식이 좋다.
Critical Section의 길이가 긴 경우는 Block/wake up 방식이 필수적이 겠고,
만약, Critical Section 길이가 짧은 경우는 busy-wait 방식이 나을 수 있다.
Two types of Semaphores
- Counting semaphore
도메인이 0이상인 임의의 정수값
주로 resource Counting에 사용 - Binary Semaphore(=mutex)
0 또는 1 값만 가질 수 있는 semaphore
주로 mutual exclusion (lock/unlock)에 사용된다.
DeadLock and Starvation
DeadLock
맛보기 설명--다음장에서 자세히 설명한다.
둘 이상의 프로세스가 서로 상대방에 의해 충족 될 수 있는 event를 무한히 기다리는 현상
S와 Q가 1로 초기화된 Semaphore라고 가정해보자.
P0가 S를 얻고, CPU를 뺏겼다고 가정하면,
P1이 Q를 얻고, 또 CPU를 뺏겼다고 가정
그러면 P0가 Q를 얻으로겨하지만, 이미 P1이 가져가버린상태, 다시 CPU를 뺏기고, P1이 S를 얻으려고 하지만, 이미 P0가 가져가버린 상태, 즉 서로 내놓지 않으므로, 서로 무한히 내놓기를 기다리는 상태,
그러면 어떻게 해결하면 되냐?
프로그래머가 유의해서 코드를 짜면서
S와Q를 얻어야하면, 순서를 맞춰주는것이다.
그러면 P1한테 CPU를 뺏겨도 내가 이미 S를 쥐고있으니까 DeadLock이 발생하지 않는다.
Starvation
3가지 프로세스가 있다면, 1,2끼리만 자원을 공유하고 3번째 프로세스는 자원을 얻지못해 굶어죽는 상황
Synchronization의 문제 3가지
- Bounded-Buffer Problem
- Read-write Problem
- Dining-philosophere problem
Bounded-Buffer Problem
리볼버의 탄창 같이 생긴것을 공유 버퍼라고 가정해보자.
결국 문제는 공유 버퍼의 갯수가 유한한 환경이기 때문에 발생하는데,
생산자는 데이터를 만들어서 공유 버퍼 에 집어넣는 역할을 한다.
생산자가 데이터를 넣고싶으면 그냥 넣는게 아니라,
- 버퍼가 비어있는지 확인, 없으면 기다림,
- 비어있는 버퍼 자리에 Lock을 걸고
- EmptyBuffer에 데이터 입력 및 buffer조작
- Lock을 풀고
- Full buffer 하나 증가.
소비자도 마찬가지이다.
- 가져갈 버퍼가 있는지 확인하고, 없으면 기다림, 가져가고 싶어도 가져갈게 없으면 안되니까.
- 공유 데이터에 lock을 건다.
- 버퍼에서 데이터 꺼내고 buffer조작
- lock풀고
- empty buffer증가시키기
고로, 생산자 입장에서는 버퍼의 비어있는 갯수가 자원의 갯수가 되는것이고,
소비자 입장에서는 내용이 들어있는 버퍼의 갯수가 자원의 갯수가 된다.
semaphore full이 0, empty 가 N-> 처음에 다 비어져 있으니까, mutex=1 -> mutex가 1이라는 이야기는 결국 하나의 프로세스만 접근가능하게 lock을 걸겠다는말이다.
생산자는 P(empty)로 빈버퍼가 있는지 확인한다, 빈게 없으면 기다려야한다.
P(mutex)로 락을 걸고, 걸었던 버퍼에서 data를 추가하고, 그다음에 lock을 풀고, 그다음에 data버퍼의 갯수를 증가시킨다.
소비자는
P(full)을 통해 내용이 들어있는 버퍼가 있는지 확인한다.
있으면 가져가야하니까 버퍼 전체에 lock을 걸고, buffer로 부터 data를 꺼내간 다음에 버퍼를 다시 unlock하고, 그 다음에 하나 가져갔으니까 비어있는 버퍼를 1 증가 시킨다.
Reader-writer Problem
공유데이터를 DB라고 생각하자.
공유데이터에 대한 DB를 여러 프로세스가 접근하면 안된다.
그러나 Read는 동시에 해도 된다.
그냥 읽는거니까.
그러나 한 프로세스가 DB에서 write할때는 다른 process가 접근하지 못하게 해야한다.
Shared data
DB 자체
readcount 현재 DB에 접근중인 Reader의 수
Synchronization Variables
mutex: 공유변수 readcount를 접근하기 위해서 lock걸때 사용
db: Reader와 writer가 공유 DB자체를 올바르게 접근하게 하는역할
Writer입장에서 P(db)로 DB에다가 lock을 걸고 만약 누가 DB에서 들어가서 쓰고 있으면, P연산을 통과하지 못하고 계속 대기하고,
P(db)로 lock을 걸었으면 write를 하고,
V(db)를 통해서 lock을 푸는 과정을 거친다.
그런데 오른쪽의 복잡한 코드 없이 상식적으로
Reader도 그냥 P(db)로 DB를 lock걸고, DB읽고 V(db)로 lock풀고
이러면, 문제가 아주 쉽게 해결되지만 비효울 적이다.
왜? 읽는 과정은 동시에 여러명이 해도 되는데 lock을 걸어버리면 한명만 접근이
가능하기 때문이다.
근데 어쨋든, lock을 걸기는 걸어야한다. 왜냐하면 Reader가 DB에 lock자체를 안걸면, writer 쪽에서 P(db)를 수행할때 어? lock 안걸려있네? 하면서 reader들이 읽는 과정에서도 그냥 write해버리기 때문이다.
그래서 readCount라는 공유변수를 만들고, 모든 reader들이 모두 이 count값을 변경 할 수 있게 한다.
내가 만약 최초의 reader이면 readcount가 1이되고, 그러면 db에다가 lock을 걸어야한다. 그다음 사람이 어쨋든 readcount++하면 1 이아니니까 db에다가 lock을 걸 필요가 없다.
어쨋든 readcount도 결국 공유변수가 되고, 이 공유변수의 값을 증가시키기 위해서는 lock이 필요하니까 mutex라는 세마포어로 lock을 걸어야한다.
그리고 만약 내가 마지막으로 읽고 나가는 놈이라면, readcount가 0일것이고 V(db)를 통해서 DB를 unlock해줘야한다.
Starvation가능
만약에 10명이 들어와서 읽고 있어서 writer는 P(db)에서 lock이 걸려서 뺑뺑이 돌고 있는데 9명이 나가고 1명이 read하려고 하는 찰나 100명의 reader들이 또 들어와버리면 writer는 이 101명의 reader가 나갈때까지 계속 기다려야하므로 writer가 starvation될 수 있다.
Dining-Philosophers Problem
이문제는 철학자 5명이 의자에 앉아 식사를 하려는데 젓가락이 5개 밖에 없을 때 생기는 문제를 나타내고있다.
젓가락에 해당하는 세마포어를 1로 두자,
그래서
chopstick[i]를 통해서 내 왼쪽 젓가락을 집고
chopstick[(i+1) % 5]를 통해서 내 오른쪽 젓가락을 집게 되면
eat을 하고 V연산을 통해서 젓가락을 내려놓는 느낌이다.
그런데 이경우 DeadLock가능성이있다.
모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 집는경우 영원히 오른쪽 젓가락을 집을 수 없다. 왜냐하면, eat()을 한뒤에 V로 젓가락을 내려놓는것이니까.
해결방안
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 젓가락을 두개 모두 집을 수 있을때에만 젓가락을 잡을 수 있게, 하나만 집을수 있으면 젓가락을 집는 권하는을 부여하지 않는다.
- 비대칭 - 짝수 철학자는 왼쪽 젓가락부터 집고, 홀수 철학자는 오른쪽 젓가락부터 집는것이다.
2번 해결방안 설명
우선 철학자의 상태는 3가지 생각하기, 배고프기, 먹기 상태가 있다.
그다음에 살작 헷갈리는 것이 있는데 원래 semaphore는 자원의 갯수를 세는것이고, 초기값을 얼마냐를 두고 이야기를 하는데 여기서는 self를 통해서 젓가락을 얻을 수 있는 권한 자체를 0 으로 두고, test메서드를 통과해야 젓가락을 얻을 수 있는 1 로 바꾸는 상태이다.
그다음에 이 3가지 상태는 공유변수이기 때문에 공유변수에 안전하게 접근하기 위해서는 우리는 mutex를 사용해서 접근해야한다.
철학자의 활동내용
철학자는 위 코드와 같이 젓가락을 집고, 밥을 먹고, 젓가락을 내려놓고, 생각하는 일련의 과정을 반복한다.
pickup을 봐보자, P(mutex)를 통해서 상태를 hungry로 바꿔준다. 그다음에 test메서드로 이동하는데
여기서 보면, if문을 통과해야지만, 상태를 eating으로 바꾸고, V연산을 통해서 젓가락을 집을 수 있는 권한인 self를 1로 바꾼다.
if문 내용은 왼쪽 철학자와 오른쪽 철학자가 eating상태가 아니고 내가 배가 고파야한다. 즉 왼쪽 오른쪽 젓가락을 모두 얻을 수 있는 상태에서 내가 배가 고프지 않아야한다.
이러면, V(self)를 통해서 1로 상태를 바꿔준다.-> 젓가락 얻을 수 있음
그래서 P(self[i])로 가면 만약 내가 test를 통과해서 젓가락을 얻었으면, 넘어갈 것이고, 만약에 통과를 하지 못한다면 P(self[i])에서 뺑뺑이돌면서 기다린다. 그럼
P에서 self를 1로 누가 바꿔줘서 이 무한 루프를 나오냐면 인접한 철학자가 밥을 다 먹고 젓가락을 내어놓으면 1로 바꿔준다.
P(mutex)로 state를 thinking으로 바꾸고, 그 다음에 자신의 왼쪽과 오른쪽 을 test해서 V연산을 통해서 다시 self[i]=1이던걸 0으로 바꿔준다.
Monitor
세마포어는 공유변수를 접근하기 위해서 항상 프로그래머가 Lock을 걸고 그다음에 Lock을 풀고 하는 과정을 거치지만, 이건 너무 불편하기도 하고 까먹고 Lock을 안걸거나, Lock을 안푸는 경우도 있을 수 있다.
그러므로, Moitor에서는
그림과 같이 모니터 내부에 공유변수와 공유변수에 접근할 수 있는 operation을 둔다.
이 operation은 동시에 수행이 안되게 만들어 놨는데 이러면 좋은점이 우리는 이제 프로그래머가 직접 Lock을 걸지 않아도 된다.
그림 코드와 같이 monitor구조체에 shared variable을 놓고 이 variable에 접근하기 위해서 P1,P2,,,Pn까지 함수를 구현해 놓은것이다.
모니터에서는 Conditionvariable이 있다.
세마포어처럼 자원의 갯수를 Count하거나, 값을 가지고 있는것이 아니라, wait연산, signal 연산이 있다.
condition variable을 그럼 언제 쓰냐면, 어떤 조건을 만족하지 않아서 오래 기다려야할때 그 프로세스를 잠들게 하기 위해서 쓴다.
x.wait()을 호출하면, x라는 condition variable에 가서 줄을 서게 된다.
x.signal()을 호출하면, 누군가가 x를 다쓰고 빠져나가서 x라는 condition variable을 기다리면서 줄을 서고 있다면, 그중 하나를 깨워주라는 것이다.
그래서 Bounded-Buffer Problem을 모니터로 구현을 해보면
- 생산자 프로세스 buffer에다가 data를 만들어서 넣는 프로세스
- 소비자 프로세스 buffer에다가 data를 꺼내가려는 프로세스
생산자가 버퍼에다가 data를 넣기 위해서는 다른 생산자나 소비자가 접근을 하지 못하게 buffer에다가 Lock을 걸고 data를 넣고 이런걸 해야하는데,
모니터에서는 생산자던 소비자던 프로세스를 실행하는 과정에서 CPU를 빼앗기더라도 다른 프로세스의 접근을 모니터가 막기 때문에 모니터가 Lock을 걸 필요가 없다.
생산 -> buffer가 꽉차면, empty.wait() empty가 되도록 기다리는 줄에 가서 기다리라는 것이다. 그래서 만약 줄에가서 기다리면, 모니터 내부에 active한게 없으니까 다른 프로세스가 와서 생산이던 소비던 한다.
그리고 빈 버퍼가 있으면 잠들필요 없이 빈 버퍼에 data를 넣고, full.signal()을 호출해서 혹시 내용이 들어있는 버퍼를 기다리면서 잠들어 있는 프로세스가 있다면 꺠워줘라는 말이다.
소비자 -> 버퍼가 차있는게 없으면 full.wait() 버퍼 차있는게 있으면 꺼내고, empty.signal()로 호출해서 빈 버퍼를 기다리면서 잠들어 있는 프로세스가 있다면 깨워주라는 것이다.
Dining Philosophers Example
state가 공유변수이다. 자신만 상태를 바꾸는건 아니니까, 그런데 모니터 내부 구현이라서 Lock을 걸필요가없다.
그래서 pickup부터 실행을하면, state를 바꾸고 test로 간다.
test에서 자신이 일단 hungry한지 확인한 후에, 왼쪽 오른쪽 젓가락을 집을 수 있는지 확인한다.
그다음에 if문을 통과하면 eating으로 state를 바꿔주고
self[i].signal()을 호출해준다.
혹시 i번쨰 철학자가 잠들어있으면 signal메서드로 꺠워주라는 말이다.
그런데 조금 이상한게 처음부터 젓가락 집으러 test함수에 들어왔는데 잠들어 있을리가 없기때문에 일단 그냥 지나치게 된다.
test가 끝나서 eating상태니까 if문에 들어가지 않는다.
근데 만약에 test를 통과하지 못했다면, 그철학자를 wait상태로 바꿔서 기다리게 한다.
어쨋든 밥을 먹었다고 치고
eat()이 끝나면 젓가락을 내려놓아야하는데
state를 thinking으로 바꾸고
test메서드에 내 양 옆의 철학자를 실행하는데, 내가 젓가락을 내려놓는것이기 때문에 혹시 내 인접철학자가 내가 밥먹느라 기다리고있으면 안되니까 깨워주기 위함이다.
그러면, test메서드에서는 그 철학자가 배고픈지 왼쪽 오른쪽이 eating이 아니라 젓가락을 집을 수 있는지 판단하고, 그다음에 state[i] = eating을 통해서, 밥을 먹는 상태로 바꿔주고, 밥을 먹으니까 여기서는 self[i].siganl을 통해서 잠들었다가 밥먹는 상태로 바뀐 철학자를 깨워줘야한다.
