Chapter 05. 병행 프로세스와 동기화
누워서 보는 운영체제 이야기 - 김주균 교수님
▶ 병행(Concurrent)
- 같이 (메모리에) 존재하고 있다는 뜻
- 메모리에 다수의 프로세스가 같이 존재한다는 것과 같은 의미
- CPU 하나가 있는 단일처리 시스템에서는 병행 프로세스 중 한 개만이 실제로 실행되지만, CPU 처리 시간을 효과적으로 나눔으로써 겉으로는 병행 프로세스들이 동시에 처리되는 것
▶ 병렬(Parallel)
- 다중처리 시스템의 경우는 여러 개의 프로세스가 동시에 실행
▶ 비동기적(Asynchronous)
- 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 등에 대해 모른 체 실행되고 있음을 의미
# 5.1 병행 프로세스(Concurrent Proccess)
ex1 ) 사람들이 옹기종기 모여 사는 작은 산골 마을이 있었는데 땔감을 팔고 생필품을 사기 위해서는 아랫마을에 가야 했다. 오가는 길 중간에 혼자 간신히 지나갈 수 있는 낡은 나무다리가 있었는데 숲이 우겨져 다리 위에 사람이 있어도 잘 보이지 않았다. 두 사람이 동시에 올라가면서 다리가 부서질 것을 대비해 장치를 하였는데, 양쪽 끝에 팻말을 두고 줄을 연결한 다음 팻말이 내려가 있으면 다리에 사람이 없다고 판단하고 줄을 당겨 팻말을 올린 뒤 다리를 건넌 후 다시 줄을 당겨 팻말을 내려놓기로 약속하였다. 다리를 건너기 위해 온 사람은 팻말이 올라가 있을 경우, 다리 위에 있는 사람이 다 건넌 다음 팻말을 내려줄 때까지 기다려야 함은 당연하며 이 약속을 잘 지킨 덕분에 모두 행복하게 살았다고 한다.
- 산골마을에서 함께 살고 있는 사람들은 병행 프로세스
- 누가 언제 다리를 건널 것인지에 대해서는 서로 모르므로 비동기적인 관계
- 공유된 자원이나 데이터에 대해 병행 프로세스들이 따라야 하는 룰이란 "한 번에 한 프로세스만이 접근하도록 하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장한다"는 것을 의미
ex2) <병팔이의 무모한 도전>
통장에 만원이 있는 병팔이가 이만 원을 만들기 위해 궁리를 하였다. 자신은 통장과 도장을 챙기고 동생에게는 카드를 주고서 같이 은행을 갔다. 물론 동생에게는 "형이 돈을 인출하는 순간 너는 현금지급기에서 동시에 만원을 인출해"라고 말해두고, 나름대로는 자신이 돈을 인출한 후 잔고가 0으로 처리되기 전에 동생이 인출을 시도하면 아직 잔고가 남아있는 상황으로 인식한 기계가 운 좋게 만원을 주지 않을까라고 생각한 것이다. 만약 병팔이의 뜻대로 된다면 은행들은 모두 문을 닫아야겠지만 실제로 그런 일은 생길 리가 없다. 병팔이와 동생의 인출 시도는 두 개의 병행 프로세스이며, 계좌는 공유 데이터이므로 은행은 누구를 먼저 처리해주든 만원을 주고 잔고를 0으로 만드는 작업을 완료한 후 다음 작업을 처리하도록 함으로써 잔고의 오류를 방지하는 것이다. 여기서도 잔고에 대해 "한 번에 한 프로세스가 잔고를 0으로 만드는 때까지는 다른 프로세스가 잔고에 접근하지 못하도록"하는 단순하지만 엄격한 룰을 지키고 있음을 병팔이도 알았다면 동생을 귀찮게 하지 않았을 것이다.
- 병행 프로세스: 병팔이와 동생의 인출 시도
- 공유 데이터: 계좌
- 한 번에 한 프로세스가 잔고를 0으로 만드는 때까지는 다른 프로세스가 잔고에 접근하지 못한다는 룰 존재
ex3-1) 메모리에 있는 변수 count는 현재 값이 10이며, 프로세스 A는 이 값을 하나 증가시키는 일을, 프로세스 B는 하나 감소시키는 일을 한다고 하자. 두 프로세스가 한 번씩 실행되었을 때의 결과값은 누가 먼저 실행되든 여전히 10이어야 할 것이다.
- A의 경우 먼저 메모리에서 count 값을 읽어 처리기 레지스터로 넣은 다음 1을 더하고 난 후, 처리기 레지스터에 들어 있는 결과 값 11을 메모리의 count 변수에 저장함으로써 실행을 완료함
- 여기서 중요한 점은 결과 값이 11이 저장되기 전까지는 메모리의 count 값이 10인 것을 명심해야 함
- B 역시 1을 뺀다는 것 외에는 A와 동일한 절차를 밟게 될 것임
- 정상적으로 실행됨을 가정하고 A가 먼저 실행되었을 경우 count는 11이 된 후 B에 의해 다시 10이 될 것이며, 반대로 B가 먼저 실행되었다면 9가 된 후 A에 의해 10이 될 것이므로 두 경우 모두 정확한 결과를 낳는다는 것을 알 수 있음
ex3-2) 공유 변수 count에 대해 A와 B가 아무 제약 없이 실행되도록 했을 경우를 떠올려 보자
- 먼저 A가 count 값을 레지스터로 옮기고 1을 더하면 레지스터의 값이 11로 증가됨. 레지스터의 값을 메모리에 저장하기 전에 CPU의 사용권이 B에게 넘겨진 후 B의 count에 대한 접근이 허용되면 B는 1을 빼기 위해 먼저 메모리에 있는 count 값을 읽어오게 될 텐데 이때의 값은 여전히 10일 것임
- B에 의해 9가 저장된 후 다시 A가 실행되면 이전에 CPU를 뺏긴 시점부터 시작할 것이고, 결과적으로 처리기 레지스터에 있는 값 11을 저장하게 되어 count의 최종 값은 11이 될 것이며, 반대로 A와 B의 순서를 바꾸면 9가 저장될 것임
- 다중처리 시스템의 경우에는 두 프로세스가 동시에 실행될 수 있으므로 둘 다 10을 읽고 각자의 실행 결과를 저장하게 될 것이고, 결국 count의 최종 값은 조금이라도 늦게 저장하는 프로세스의 결과 값과 같이 11 또는 9가 될 것임
- 즉, 한 프로세스의 공유 변수 count에 대한 조작 도중 다른 프로세스에게도 count에 대한 조작이 허용되면 부정확한 결과 값을 초래하게 됨
- 다시 말해, 단일 처리 시스템의 경우 정확한 결과 값을 위해서는 A의 count에 대한 조작 도중 CPU가 B로 넘겨지더라도 B의 count에 대한 조작은 허용되어서는 안 된다는 점
# 5.2 상호 배제(Mutual Exclusion)
- 경쟁 상태(Race Condition): 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황
- 경쟁관계에 있는 프로세스들로 인해 상호 배제, 교착 상태(Deadlock), 기아(Starvation)와 같은 문제 발생
- 임계 영역(Critical Section): 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원(임계 자원/critical resource)에 대해 접근하고 실행하는 프로그램 내의 코드 부분
- 상호 배제: 한 번에 하나의 프로세스 만이 임계 영역에 들어가야 함(임계 영역을 실행해야 함)을 의미
- critical section에 대한 action은 mutual exclusion을 해주어야 함
▶ 임계 영역 진입 순서
- 임계 영역에 들어가고자 하는 프로세스는 먼저 임계영역 내 다른 프로세스가 있는지를 확인
- 확인한 후 있다면 기다리고, 없다면 들어가면서 자신이 나올 때까지 다른 프로세스가 들어오지 못하도록 함
- 임계 영역을 벗어날 때는 자신이 나오는 사실을 알려 다른 프로세스가 들어올 수 있도록 함
- ex) 산골마을의 예에서 다리에 도착한 사람은 팻말이 내려가 있을 때 다리 위에 아무도 없음을 알고 줄을 당겨 팻말을 올리고 건너간 후, 다리에서 내려올 때는 다시 줄을 당겨 팻말을 내려놓음으로써 다른 사람이 다리를 건널 수 있도록 하는 것과 비교 가능
▶ 상호 배제를 실현하기 위한 필요조건(원칙)
- 상호 배제
- 임계 영역이 있지 않는 프로세스가 다른 프로세스의 임계 영역 진입을 막아서는 안됨
- 비어 있는(아무도 실행하고 있지 않는) 임계영역에 대한 진입은 바로 허용해야 됨
- 특정 프로세스의 진입 시도가 계속 무산되어 기아를 겪지 않아야 함
▶ 상호 배제를 실현하기 위해서는 임계 영역을 진입할 때와 나올 때 꼭 해야 할 일들을 어떻게 잘 구현하느냐가 성공 여부를 결정
임계 영역 진입할 때 해야 할 일: enter primitive
임계 영역을 나올 때 해야 할 일: exit primitive
▶ 운영 체제가 다양한 경우 구체적인 모든 내역을 파악하여 알아서 상호 배제를 해 주기가 어려움
- 공유 자원에 대한 상호 배제의 의무는 일반적으로 프로그래머 책임
- 운영체제는 사용자의 상호 배제 구현을 지원하기 위한 도구를 제공 ex) 세마포어, 모니터
# 5.3 상호 배제를 위한 소프트웨어 기법들
▶ 소프트웨어 기법들은 병행하는 프로세스들에게 상호배제를 책임지도록 한 것
▶ 운영체제의 지원 없이 ㅍ로세스들 간에 자신의 프로그램에서 임계 영역 앞뒤로 적절한 코딩을 해줌으로써 상호배제를 해결하는 방식
▶ 프로그램들을 이해하기 위해서는 parbegin/parend 구조를 알아야 함
- 첫 부분과 마지막 부분에서 parbegin 및 parend로 표현된 두 개의 키워드들을 볼 수 있고 그 키워드들 사이에 statement_1, statement_2 등과 같은 n개의 문장들이 들어있음
- 이러한 표현은 parbegin과 parend 사이에 존재하는 n개의 문장들이 동시에 수행될 수 있음을 뜻함
- 단일 처리기 시스템의 경우라면 각 문장의 수행 순서를 임의로 진행해도 좋다는 뜻으로, 다중 처리기의 경우에는 각 문장을 병렬로 실행하겠다는 뜻으로 이해하면 되고 따라서 이 구조에서 n개의 문장들의 나열 순서는 아무 의미가 없음
1) 몇 가지 미완성 시도들
▶ 첫 번째 시도
- 병행 프로세스 간의 실행 속도와 임계 영역을 들어가고자 하는 횟수의 차이는 얼마든지 날 수 있음
- 병행하는 두 프로세스는 P0와 P1이며, 각각이 하는 일(컴퓨터에서 일이란 프로그램으로 표현된다는 것)은 아래와 같음
- 문제점 2가지
- turn의 초기 값이 0으로 되어 있으므로 임계 영역의 첫 번째 진입은 P0 만이 할 수 있음. 물론 초기 값을 1로 바꾸면 P1이 처음으로 진입할 수 있지만, 문제는 두 프로세스에서 임계 영역의 첫 번째 진입이 고정되어 있다는 사실이고 이것은 임계 영역이 비어있을 경우 진입을 원하는 프로세스를 방해해서는 안 된다는 원칙에 위배됨
- 임계 영역의 진입이 turn 값을 바꾸어줌으로써 가능하므로 P0와 P1은 정확하게 한 번씩 번갈아가며 진입이 가능하고 누구든 연속해서 두 번 이상 진입할 수 없음. 즉, P0가 할 일이 끝나 시스템을 떠나게 되면 P1은 연속으로 진입할 수 없기 때문에 프로세스를 완료하지 못하게 됨
▶ 두 번째 시도
- flag 두 개를 사용하여 정상적으로 진행될 경우 첫 번째와는 달리 임계 영역의 최초 진입에 제한이 없어졌으며, 상대적으로 많은 횟수의 진입이나 상대 프로세스가 먼저 종료되어도 진입이 가능
- 단점: 상호 배제가 지켜지지 않음
▶ 세 번째 시도
- 두 번째 시도의 문제는 각자의 flag를 true로 만드는 작업이 while문 다음에 있었기 때문이었다는 것에 착안하여, 이번에는 이 작업을 while문 앞으로 옮겨본 것이 세 번째 시도임
- 문제점: 두 프로세스 모두 임계 영역에 들어갈 수 없는 상황이 발생
boolean flag[0], flag[1];
void P0(){
while(true){
...
...
flag[0] = true; /* 이후에 바로 CPU를 P1에게 뺏길 경우 P1에서 flag[1]=true 이후,
while문만 돌게되며 어느 프로세스도 임계 영역에 접근하지 못하는 경우 발생 */
while(flag[1]); /* do nothing */
<critical section>;
flag[0] = false;
...
...
}
}
void P1(){
while(true){
...
...
flag[1] = true;
while(flag[0]); /* do nothing */
<critical section>;
flag[1] = false;
...
...
}
}
void main(){
flag[0] = false;
flag[1] = false;
parbegin
P0;
P1;
parend
}
2) 성공적인 기법들
▶ Dekker의 알고리즘
- 앞선 시도들의 경험을 바탕으로 flag와 turn 변수를 적절히 사용하여 두 프로세스 사이의 상호 배제를 제대로 구현한 것
- 이해하기가 어렵고 정확성을 증명하기가 까다로움
▶ Peterson의 알고리즘
- 전역 변수 flag [0]와 flag [1]은 초기 값이 false이며, turn은 0 또는 1 값을 갖는 상황에서 P0의 프로그램을 보였는데, P1은 P0에서 0은 1로 1은 0으로 바꾸면 됨
boolean flag[0], flag[1], turn;
void P0(){
while(true){
flag[0] = true;
turn = 1;
while(flag[1]&&turn==1); /* do nothing */
<critical section>;
flag[0] = false;
<remainder>;
}
}
void P1(){
while(true){
flag[1] = true;
turn = 0;
while(flag[0]&&turn==0); /* do nothing */
<critical section>;
flag[1] = false;
<remainder>;
}
}
void main(){
flag[0] = false;
flag[1] = false;
parbegin
P0;
P1;
parend
}두 프로세스가 while문을 돌면서 진행이 안 되는 것 같은 경우 CPU 할당 시간이 끝나서 CPU 점유권이 넘어가게 되면 해결됨
3) n 프로세스 간의 상호 배제를 위한 소프트웨어 기법들
- n개의 프로세스들을 대상으로 하는 상호배제 기법으로는 Dijkstra의 알고리즘이 있는데 앞 장에서 설명했던 무한 대기가 발생 가능
- Knuth의 알고리즘은 지연 시간이 커지는 단점
- Eisenberg와 Mcguire의 알고리즘은 유한 시간 내에 임계 영역으로의 진입이 보장
▶ 베이커리(Bakery) 알고리즘으로 알려져 있는 Lamport의 알고리즘은 원래 분산 시스템용으로 소개되었으나 n개의 프로세스들을 대상으로 하는 상호 배제 기법으로도 유용
- 상호 배제가 요구되는 n개의 프로세스에서 임의의 프로세스 i를 위한 프로그램
- 모든 number 값과 choosing 값은 0과 false로 초기화되어 있고, 임계 영역의 진입을 원하는 프로세스 i는 먼저 number 값이 주어지는데 다른 프로세스들이 이미 받은 값보다 더 큰 값을 받게 됨
- number [i] = max~에서 max계산은 하고 할당되는 부분 전에 CPU를 뺏기게 된다면 같은 값을 할당받는 경우가 생길 수 있음
- number 값이 0이면 critical section에 들어가려는 시도조차 안 해본 프로세스
- for문 안에서 첫 번째 while문은 번호 값을 받는 중인 프로세스가 있다면 그 값도 비교해야 하기 때문에 기다리는 것이며, 두 번째 while문에서 자신의 값이 가장 작을 때 임계 영역의 진입이 허가되는 것
- 임계 영역을 벗어난 후 자신의 값을 0으로 해줌으로써 차례를 기다리는 다른 프로세스들에게 임계 영역의 진입 기회를 주게 되는데, 번호 값에 의해 차례가 정해 지므로 특정 프로세스의 무한 대기는 걱정하지 않아도 됨
# 5.4 상호 배제를 위한 하드웨어 기법들
1) 인터럽트 금지를 사용한 기법
- 단일처리 시스템의 경우는 병행 프로세스들이 실제로는 CPU를 번갈아 사용하는 것이므로 한 프로세스가 임계 영역에서 실행 중일 때 CPU를 뺏기지 않도록 하면 간단하게 상호 배제를 지켜줄 수 있을 것임
- 다시 말해, 시간 종료나 우선순위 등에 의해 CPU를 뺏길 수 있는 인터럽트를 임계 영역의 실행을 완료할 때까지 발생하지 않도록 하면 됨
- 임계 영역의 처리 동안 모든 종류의 인터럽트를 금지시킴으로써 시스템의 효율적인 운영을 방해하기 쉬움
- 다중 처리기 시스템에서는 사용하기 힘듦 → CPU가 여러 개일 때 해당 CPU만 disable 되기 때문
2) 하드웨어 명령어를 사용한 기법
- 기계 명령어로 알려져 있는 testandset과 exchange 명령어가 어떤 일을 하는지 아래 그림에서 알 수 있는데, 이해를 돕기 위해 함수 또는 프로시저의 형식으로 표현되어 있으나 실제로는 기계 명령어로서 원자적(Atomic) 실행됨(즉, 실행 도중 끊김 없이 완료되는 연산 = indivisible)
- 책들에 따라 exchange 명령어를 swap이라고 부르기도 함
▶ 장단점
- 다중 처리 시스템에서도 쉽게 사용 가능
- 한 프로그램 내에서 서로 다른 변수를 사용하여 여러 개의 임계 영역도 지원 가능
- 바쁜 대기(busy wait: while 문을 계속 맴돌게 됨으로써 CPU의 낭비 초래) 발생 가능
- 임계 영역 실행 중 높은 우선순위를 가지는 프로세스에게 CPU를 뺏길 경우 교착 상태 발생 가능
- 즉, 높은 프로세스는 while에서 돌고(우선순위가 높아 CPU를 받았지만 임계 영역에 이미 프로세스가 있어 접근하지 못하는 것) 낮은 프로세스는 CPU를 뺏겨서 일을 다 하지 못한 채로 임계 영역에 갇힌 것 → 임계영역에 있는 낮은 우선순위의 프로세스의 우선순위를 일시적으로 올리는 작업 필요(priority 역전 ceiling)
# 5.5 세마포어(Semaphore)
▶ Dijkstra가 1956년에 제안한 개념인 세마포어는 세 개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수로서, 앞서 다루었던 것들보다 더 높은 수준에서 상호 배제를 구현 가능
▶ 세마포어는 그 변수가 가질 수 있는 값의 범위에 따라,
- 세마포어가 0 아니면 1의 이진 값만을 가진다면, 그 세마포어를 이진(Binary) 세마포어라고 함
- 세마포어 값이 음이 아닌 모든 정수가 될 수 있으면, 계수(Counting) 혹은 정수(Integer) 세마포어
▶ 세마포어를 위한 특수한 명령들을 비분리(Indivisible) 명령들로서, 세마포어 값을 초기화하는 명령, P 명령, V 명령
- P 명령: wait, 또는 down이라는 이름을 사용하기도 함
- V 명령: signal 또는 up이라는 이름을 사용하기도 함
- block-wait & busy-wait
| 방식 | 장점 | 단점 |
| block-wake up | CPU 낭비가 없어 효율이 좋음 | 1. 상황이 만족되면 ready로 프로세스를 이동시키고, 이동된 프로세스는 ready에 있던 프로세스들과 경쟁하여 CPU를 받게 됨. 따라서 바로 CPU를 할당받지 못하기 때문에 즉각적인 반응이 늦어짐 2. 커널의 개입으로 인해 CPU 타임을 OS가 사용 |
| busy-wait | wait 하던 상황이 만족되었을 때는 busy-wait 하던 프로세스는 바로 다음 while을 통과하면 critical section에 진입 가능 | CPU를 wait 용도로 계속 사용하기 때문에 실제로 유용한 곳에 사용하지 못함. 다른 프로세스에게 넘겨도 될 상황임에도 wait된 프로세스에게 매여있으면서 CPU 낭비 발생 |
| enter primitive에서 while을 사용하면 busy-wait, 그렇지 않으면 block-wakeup 방식 | ||
- P 명령은 S 값이 0보다 크면 단순히 S 값을 1 감소시키는 작업을 하지만, 그렇지 않으면 S 값이 0보다 크게 되기를 기다리게 됨(큐에서 대기하게 되는데 이때 O/S의 개입이 필요함)
- V 명령에서는 S가 0보다 크게 되기를 기다리는 프로세스가 있으면, 그들 중 하나의 프로세스가 수행되고, 만약 그러한 프로세스가 존재하지 않는다면 단순히 S의 값을 1만큼 증가시키는 작업만 함
- 세마포어에 대한 명령들은 각각 분리되지 않고 수행될 수 있도록 구현해야 하며, 같은 세마포어에 대해서는 동시에 실행될 수 없음
▶ 세마포어를 이용한 상호 배제
- 세마포어 변수 S가 1로 초기화되어 있으므로 최초로 시도하는 프로세스는 S를 0으로 바꾸고 임계 영역으로 진입하게 될 것임. 이후 진입을 시도하는 프로세스들은 대기 상태가 됨
- 임계 영역을 빠져나오는 프로세스에 의해 대기 상태의 프로세스들 중 하나가 실행 가능한 상태가 되어 임계 영역으로 진입하게 됨. 대기 상태의 프로세스들이 없으면 S를 1 증가
- P와 V 명령의 정의에 따라 한 번에 하나의 프로세스만이 임계 영역에 들어갈 수 있음을 알 수 있음
▶ 계수(정수) 세마포어 활용
- ex) 프린터가 10개 있는 실습실에서, 비어있는 프린터가 있다면 누구나 출력 작업을 할 수 있도록 해놓고 싶다고 함. 이때 프린터는 공유 자원으로서 풀(Pool)로 관리되고 있다고 하며, 최대 10명이 동시에 작업을 할 수 있음
const int n = (프로세스의 수)
semaphore s = 10; // 10명이기 때문에 + integer 세마포어
void p(int i){
while(true){
P(s);
<critical section>; // 예시에는 print하는 행위
V(s);
<remainder>;
}
}
void main(){
parbegin
p(1), p(2), p(3), ...;
parend
}- 이럴 경우 S 값이 10보다 작은 양수 값일 때는 작업이 가능한 프린터 대수(임계 영역의 진입이 허용되는 프로세스 수)를 나타내게 됨
- 정수 세마포어는 자원 관리에 관한 것이며 여기서는 상호 배제에 관련된 것이 아님
▶ 세마포어 동기화
- 세마포어 - 동기화(Sync), 상호 배제(Mutual Exclusion), 자원관리(Resource Management) 3가지 영역에서 사용될 수 있음
- 동기화의 의미는 "서로를 의식하고 실행의 보조를 맞추다"는 뜻
- P0는 P1이 데이터를 생성하여 주면 받아 계속 실행을 하는 경우
# 5.6 생산자 - 소비자 문제 (Producer-Consumer Problem)
- 생산자는 데이터를 만들어 버퍼에 저장하고(채워나가고), 소비자는 버퍼에 있는 데이터를 꺼내 소비하는(비우는) 프로세스
- 버퍼는 공유 자원이므로 버퍼에 대한 접근 즉, 저장하고 꺼내는 일들이 상호 배제되어야 함
- 버퍼가 비어 있을 때는 소비 가자, 버퍼가 꽉 차 있을 때는 생산자가 기다려야 하는(더 이상 저장할 공간이 없으므로) 동기화도 자연스럽게 포함되어 있음
- 버퍼의 크기는 저장 공간이 하나인 것부터 무한개까지 설정 가능하며, 여기서는 n개의 공간을 가지는 유한 크기의 원형(Circular) 버퍼를 가정한 알고리즘을 보도록 할 것
- 버퍼를 선형(Linear)으로 할 경우에는 채우고 비워 나가는 작업이 버퍼의 끝에 다다랐을 때 문제가 생기므로 알고리즘의 효율성을 고려하여 원형으로 설정
- 공간의 개수를 제한하지 않은 무한 버퍼를 가정한 알고리즘이 필요하다면 위의 그림에서 e에 대한 선언과 명령어 부분만을 빼버리면 됨
(세마포어 e에 대한 선언부, producer()에서의 P(e), consumer()에서의 V(e))
- 무한 버퍼용 알고리즘의 경우 소비자 프로그램 부분에서 P(f)와 P(s)의 순서를 바꾸게 되면 P(s)를 통과해 버퍼에 대한 배타적 접근 권리를 가진 소비자가 버퍼가 비어 있음을 발견하게 될 경우 P(f)에서 대기 상태가 될 수 있을 것임. 이렇게 되면 버퍼를 채워줄 생산자는 P(s)에서 역시 대기하게 되어 교착 상태를 만들게 되므로 알고리즘은 실패하게 됨
# 5.7 Eventcount와 Sequencer를 사용한 기법
- Eventcount와 Sequencer 역시 특별한 명령들에 의해서만 접근이 가능한 정수형 변수들이며 초기 값은 0으로 시작하고 그 값이 감소하지 않음
- ticket(s) 명령은 비분리로 실행되며 sequencer 변수인 s 값을 반환해 주고 ticket(s) 명령이 실행될 때마다 s 값은 1 증가함
- Eventcount 변수인 E에 대한 명령은 현재의 E 값을 반환해주는 read(E), 1 증가시키는 advance(E) 그리고 E가 V 값보다 작으면 기다리도록 하는 await(E, v) 명령들이 있는데, 이 세 명령은 비분리로 실행되지 않아도 됨
- 임계 영역의 진입을 시도하는 프로세스들에게 순번 표를 부여함으로써 기다린 순서대로 처리되게 하여 기아 방지
- 실생활에서 응용하고 있는 좋은 예: 은행 - 도착해서 제일 먼저 하는 일이 번호표를 뽑는 것인데 이것이 ticket(s)로, 내 차례를 위해 작은 전광판에 적힌 숫자를 보는 것이 read(E), 한 명이 서비스될 때마다 창구 직원에 의해 그 숫자가 증가되는 advance(E) 그리고 그 값이 내 번호표의 값이 될 때까지 기다리는 await(E, v)가 잘 지켜져 고객 서비스가 이루어지는 것을 경험해보았을 것임
# 5.8 모니터
- 공유 데이터들과 이들에 대한 임계 영역들을 관리하는 소프트웨어 구성체
- 모니터는 프로그래밍 언어 수준에서 제공되는 - Java에서도 제공되는 구조임을 참고 - 모듈로서 공유 데이터를 위한 변수들과 초기화 루틴, 임계 영역을 코딩한 프로시저들로 이루어진 일종의 함(box)으로 이해
- 모니터 내의 변수들은 프로시저를 호출하여 모니터 안으로 진입한 후, 원하는 공유 데이터에 대한 접근을 하게 됨
- 중요한 점은 언제나 모니터의 진입을 한 프로세스로 제한함으로써 즉, 한 번에 하나 이하의 프로세스만이 모니터 내에 있게 함으로써 상호 배제를 자연스럽게 실현한다는 것
- 모니터로의 진입은 프로시저의 호출로 가능하고, 한 프로세스만이 들어갈 수 있으므로 이미 한 프로세스가 들어가 있을 때를 대비해 대기 큐가 있음
- 모니터에서는 조건변수(Condition Variable)를 선언하고, 조건의 대기를 위해 cwait()를, 대기에서 깨어나기 위해 csignal()을 제공함. 조건 변수는 모니터에서만 선언하고 사용하는 것으로 cwait()과 csignal()에 의해서만 접근됨
- cwait(c)는 이 연산을 호출한 프로세스를 조건 c의 큐에 대기시키고 다른 프로세스의 모니터 진입을 가능하게 함. csignal(c)는 cwait(c)에 의해 대기되었던 프로세스를 재개시키고, 자신은 신호자 대기 큐로 비켜줌. 만일 cwait(c)로 대기 중인 프로세스가 많다면 그중에 하나를 고를 것이고, 없다면 단순히 다음 문의 실행을 계속하면 됨
- 신호자 대기 큐: csignal()에 의해 대기하고 있던 프로세스를 실행시킬 때, csignal()을 호출한 프로세스는 신호자 대기 큐에서 대기하였다가 모니터가 비면 모니터에 들어가 남은 작업을 수행함
▶ 유한 버퍼에서 모니터를 사용한 생산자-소비자 알고리즘
monitor boundbuffer; // 모니터의 선언 -> 모니터 구조는 시스템이 만들지만, 모니터에서 필요한 코딩 내용은 사용자가 구성해야 함
char buffer [n];
int nextin, nextout, count;
cond notfull, notempty;
void append(char x){
if(count==n) // buffer full?
cwait(notfull);
buffer[nextin] = x;
nextin = (nextin + 1) % n ;
count++;
csignal(notempty); // process wakeup in notempty queue
}
void take(char x){
if(count==0) // buffer empty?
cwait(notempty);
x = buffer[nextout];
nextout = (nextout + 1) % n;
count--;
csignal(notfull); // process wakeup in notfull queue
}
{// monitor body
nextin = 0; nextout = 0; count = 0; // initialization
}
void producer(){
char x;
while(true){
create data x;
append(x);
}
}
void consumer(){
char x;
while(true){
take(x)
consume data x;
}
}
void main(){
parbegin
producer(), consumer();
parend
}- 생산자는 데이터를 만든 후 append(x)를 호출하여 모니터의 진입을 요청함. 내부에 이미 프로세스가 있다면 append 진입 큐에서 기다리게 될 것이며, 아닐 경우 프로시저 내의 if 문을 실행하게 될 것
- 버퍼가 차있다면 cwait(notfull)에 의해 notfull 조건 큐로 이동하게 될 것 - 모니터를 비우게 될 것 -이며, 아닐 경우 데이터를 저장한 후 notempty 조건 큐에서 기다리는 프로세스를 재개시켜 모니터로 진입하게 하고 자신은 신호자 대기 큐로 이동
- notempty 조건 큐에 아무도 없다면 다음 명령으로 실행을 옮기는데 여기서는 더 이상 실행할 것이 없으므로 append의 호출이 끝나고 모니터를 벗어나게 됨
- 소비자도 비슷한 방법으로 진행
- 시스템 내에 모니터는 하나 이상 가능. but 이름은 달라야 하며 모니터 내의 함수 이름은 같아도 됨. 단, 프로시저 호출 시 어느 모니터의 프로시저를 호출하는지 명시해야 함 ex) A.append()
▶ 원형 버퍼를 활용한 예: 스풀링(Spooling)
- 스풀러 프로세스: 디스크와 같은 보조 기억장치에 빠른 속도로 출력을 하는 프로세스
- 디스 플러 프로세스: 디스크에 임시로 출력된 내용을 실제로 프린터로 출력하는 프로세스
- 상대적으로 속도가 느린 프린터와 직접적으로 관련된 작업을 하는 디스 플러 프로세스는 스풀러 프로세스에 비하여 처리 속도가 느림. 이러한 두 프로세스 간의 속도 차이를 완화해주기 위해 원형 버퍼를 사용할 수 있음
- 스풀러 프로세스: 생산자(ex. 실 생산 공장), 디스플러 프로세스: 소비자(ex. 뜨개질하는 할머니)
- 병행 프로세스의 제어를 위해 제공: 고수준의 모니터, path expression, critical region, conditional critical region
- 모니터만 제대로 구성되고 나면 사용자는 프로그램의 적당한 위치에 모니터의 프로시저를 호출하여 사용하기만 하면 되므로 병행 프로세스 문제(상호 배제와 동기화 문제)를 해결할 수 있음
▶ 식사하는 철학자들
- 5명의 철학자가 앉아있고, 식탁에는 5 접시의 스파게티와 5개의 포크가 놓여 있다. 철학자들은 비동기적으로 먹거나 생각하는 일을 반복하는데, 스파게티를 먹기 위해서는 자신의 왼쪽과 오른쪽에 있는 포크 두 개가 있어야 한다. 결국 포크가 공유 자원이 되며 철학자들의 정상적인 식사를 보장하는 것이 이 문제의 핵심
- think: 컴퓨터 시스템이 다음 할 일을 생각하는 것, eat: 컴퓨터 시스템이 할 일을 실행하는 것
- 포크에 대한 상호 배제를 위해 세마포어를 사용하고, 각 철학자는 다음과 같이 행동하도록 해 봄 - 세마포어 fork [0.. 4]의 초기치는 1
왼쪽 포크 집은 후 오른쪽 포크 집고 먹은 후 왼쪽 포크 내려놓고 오른쪽 포크 내려놓음
- 모든 철학자가 동시에 자신의 왼쪽 포크를 집고 난 후, 오른쪽 포크를 집지 못해 먹지 못하는 이른바 교착 상태에 빠지는 경우가 발생할 수 있음. 이 문제를 해결하기 위해 아래와 같이 고칠 수 있음
오른쪽과 왼쪽 포크를 동시에 집게 함(all or none)
- 즉, 한 번에 포크 두 개를 모두 집도록 하여 교착 상태가 생기지 않도록 하겠다는 의도. 이 경우 두 개의 모두 집은 철학자는 식사가 가능하나, 하나도 못 집은 철학자는 굶게 될 텐데 동작이 매우 빠른 철학자 때문에 오랜 시간 굶게 되는 즉, 기아를 겪게 되는 철학자가 생길 수 있음
- 식탁에 한 번에 4명만 앉도록 하거나, 또는 홀수 번호의 철학자는 왼쪽 포크부터 집고 난 다음 오른쪽 포크를 집도록 하고, 짝수 번호의 철학자는 반대 순서로 집게 하면 교착 상태나 기아 없이 식사가 가능함. 교착 상태를 일으키는 위의 첫 번째 예를 모니터를 이용해 구현하면 교착 상태를 방지할 수 있는데, 그 이유는 한 명의 철학자만이 모니터 내에 있을 수 있으므로 왼쪽 포크를 집는 동안 다른 철학자가 오른쪽 포크를 집어갈 가능성을 배제할 수 있기 때문
'Study > Computer&Operating System' 카테고리의 다른 글
| [OS] Chapter 07. 메모리 관리 (0) | 2022.06.02 |
|---|---|
| [OS] Chapter 06. 교착 상태(Deadlock) (0) | 2022.05.07 |
| [OS] Chapter 04. CPU 스케줄링 (0) | 2022.04.15 |
| [OS] Chapter 03. 프로세스와 스레드 (0) | 2022.04.14 |
| [OS] Chapter 02. 들어가기 전에 (0) | 2022.04.14 |
