2. 상호배제와 동기화 01 program versionone; // 첫 번째 버전 알고리즘 4-7 상호배제 단계 1 01 program versionone; // 첫 번째 버전 02 var processnumber : integer; // 공유 변수 03 procedure P1; // 프로세스 P1의 임계영역 진입 절차 04 begin 05 while true do // 진입영역에서 P1의 진입 활동 06 begin 07 while processnumber = 2 do; // P2의 임계영역 진입 여부 확인 08 criticalsectionone; // 임계영역 09 processnumber : = 2; // P2에게 진입 순서 양보 10 otherstuffone // P1의 잔류영역 수행 11 end; 12 end; 13 procedure P2; // 프로세스 P2의 임계영역 진입 절차 14 begin 15 while true do // 진입영역에서 P2의 진입 활동 16 begin 17 while processnumber = 1 do; // P1의 임계영역 진입여부 확인 18 criticalsectiontwo; // 임계영역 19 processnumber := 1; // P1에게 진입 순서 양보 20 otherstufftwo // P2의 잔류영역 수행

2. 상호배제와 동기화 21 end; 22 end; 23 24 begin 알고리즘 4-7 상호배제 단계 1 21 end; 22 end; 23 24 begin 25 processnumber := 1; // P1의 우선 진입 순서로 초기화 26 parbegin 27 P1; // 동시 수행(P1, P2) 28 P2; 29 parend; 30 end.

2. 상호배제와 동기화 알고리즘 2 (알고리즘 4-8) 두 개의 변수(P1_inside, P2_inside)를 사용해 상호배제를 해결. 알고리즘 4-8 상호배제 단계 2 01 program versiontwo // 두 번째 버전 02 var P1_inside, P2_inside : boolean; // 논리변수 선언 03 04 procedure P1; // 프로세스 P1의 임계영역 진입 절차 05 begin 06 while true do // 진입영역에서 P1의 진입 활동 07 begin 08 while P2_inside do; // P2의 임계영역 진입 여부 확인 09 P1_inside := true; // P1이 임계영역 진입 시도 10 criticalsectionone; // 임계영역 11 P1_inside := false; // P2에게 진입 순서 양보 12 otherstuffone // P1의 잔류영역 수행 13 end; 14 end; 15 16 procedure P2; // 프로세스 P2의 임계영역 진입 절차 17 begin 18 while true do // 진입영역에서 P2의 진입 활동 19 begin

2. 상호배제와 동기화 바쁜 대기가 발생하므로, 프로세서 시간 낭비를 초래함. 알고리즘 4-8 상호배제 단계 2 20 while P1_inside do; // P1의 임계영역 진입 여부 확인 21 P2_inside := true; // P2가 임계영역 진입 시도 22 criticalsectiontwo; // 임계영역 23 P2_inside := false; // P1에게 진입 순서 양보 24 otherstufftwo // P2의 잔류영역 수행 25 end; 26 end; 27 28 begin 29 P1_inside := false; // P1의 초기화(거짓) 30 P2_inside := false; // P2의 초기화(거짓) 31 parbegin 32 P1; 33 P2; 34 parend; 35 end. 바쁜 대기가 발생하므로, 프로세서 시간 낭비를 초래함. - 바쁜 대기: 대기 프로세스들이 비생산적이고, 자원을 소비하는 대기 루프에 남아있는 상태. 두 프로세스가 동시에 임계영역으로 들어가면 상호배제가 보장되지 않음. - P1과 P2가 동시에 criticalsectionone;와 criticalsectiontwo; 진입

2. 상호배제와 동기화 알고리즘 3 (알고리즘 4-9) [알고리즘 4-9]에서는 while 문을 검사하기 전에 while 문 검사를 시작함을 플래그로 알려 주어 상호배제를 해결. 두 프로세스가 교착상태에 빠질 가능성이 있음. - 두 개의 프로세스가 while 문 검사를 하기 전에 동시에 플러그를 바꾸면 서로의 플래그 상태를 확인한 두 프로세스는 영원히 while~do 구조를 수행. 알고리즘 4-9 상호배제 단계 3 01 program versionthree // 세 번째 버전 02 var P1_enter, P2_enter : boolean; // 논리변수 선언 03 procedure P1; 04 begin 05 while true do 06 begin 07 P1_enter := true; // P1의 임계영역 진입 시도 08 while P2_enter do; // P2의 임계영역 진입 여부 확인 09 criticalsectionone; // 임계영역 10 P1_enter := false; // P2에게 진입 순서 양보 11 otherstuffone // P1의 잔류영역 수행 12 end; 13 end;

2. 상호배제와 동기화 6 알고리즘 4-9 상호배제 단계 3 14 procedure P2; 15 begin 16 while true do 17 begin 18 P2_enter := true; // P2의 임계영역 진입 시도 19 while P1_enter do; // P1의 임계영역 진입 여부 확인 20 criticalsectiontwo; // 임계영역 21 P2_enter := false; // P1에게 진입 순서 양보 22 otherstufftwo // P2의 잔류영역 수행 23 end; 24 end; 25 begin 26 P1_enter := false; // P1의 초기화(거짓) 27 P2_enter := false; // P2의 초기화(거짓) 28 parbegin 29 P1; 30 P2; 31 parend; 32 end. 6

2. 상호배제와 동기화 알고리즘 4 (알고리즘 4-10) [알고리즘 4-10]에서는 순환하는 각 프로세스가 플래그를 얼마 동안만 거짓으로 하여 [알 고리즘 4-9]의 문제 해결. 이 방법도 무한 연기 문제가 발생함. - 각 프로세스의 상대적인 속도를 예측 불가능함. 가능한 순서를 고려하여 무한 연기 문제 해결. - 각 프로세스가 신호를 참으로 설정하고 while 문 검사를 한 후 while 루프를 수행하여 플래그를 거짓으로 수행. - 이후 다시 참으로 설정하는 작업을 반복하여 검사를 계속 수행. 7

2. 상호배제와 동기화 delay(random, fewcycles); // 순간 연기 8 알고리즘 4-10 상호배제 단계 4 01 program versionfour // 네 번째 버전 02 var P1_enter, P2_enter : boolean; // 논리변수 선언 03 procedure P1; 04 begin 05 while true do 06 begin 07 P1_enter := true; // P1의 임계영역 진입 시도 08 while P2_enter do; // P2의 임계영역 진입 여부 확인 09 begin 10 P1_enter := false; // P2에게 진입 순서 양보 delay(random, fewcycles); // 순간 연기 P1_enter := true; // P1이 임계영역 재진입 시도 end; 14 criticalsectionone; // 임계영역 15 P1_enter := false; // P2에게 진입 순서 양보 16 otherstuffone // P1의 잔류영역 수행 17 end; 8

2. 상호배제와 동기화 9 알고리즘 4-10 상호배제 단계 4 Procedure P2; 20 begin 21 While true do 22 begin 23 P2_enter : = true; // P2가 임계영역 진입 시도 24 While P1_enter do; // P1이 임계영역 진입 여부 확인 25 begin 26 P2_enter : = false; // P1에게 진입 순서 양보 27 delay(random, fewcycles); // 순간 연기 28 P2_enter := true; // P2가 임계영역 재진입 시도 29 end; 30 criticalsectiontwo; // 임계영역 31 P2_enter := false; // P1에게 진입 순서 양보 32 otherstufftwo // P2의 잔류영역 수행 end; begin P1_enter := false; P2_enter : = false; parbegin P1; P2; parend; end. 9

2. 상호배제와 동기화 데커 알고리즘 하드웨어의 도움 없이 프로세스 두 개의 상호배제 문제를 해결. 아래와 같은 특징을 가짐 - 특별한 하드웨어 명령문을 필요로 하지 않는다. - 임계영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계영역에 들어가려는 것을 막아서는 안 된다. - 임계영역에 들어가기를 원하는 프로세서로 하여금 무한정 기다리게 해서는 안 된다. 알고리즘 4-11 상호배제를 구현한 데커 알고리즘 01 program dekkersalgorithm; 02 var fprocess: (first, second); // 공유 변수 03 P1_enter, P2_enter : boolean; 04 procedure P1; // 프로세스 P1의 임계영역 진입 절차 05 begin 06 while true do 07 begin 08 P1_enter := true; // P1이 임계영역 진입 시도 09 while P2_enter do; // P2의 임계영역 진입 여부 확인 10 if fprocess = second then // P2의 진입 차례(기회)라면 11 begin 12 P1_enter := false; // P2에게 진입 순서 양보 13 while fprocess = second do; // 순서 기다림(P2 완료) 14 P1_enter := true; // P1이 임계영역 재진입 시도 15 end;

2. 상호배제와 동기화 11 알고리즘 4-11 상호배제를 구현한 데커 알고리즘 16 criticalsectionone; // 임계영역 17 fprocess := second; // P2에게 진입 순서 양보 18 P1_enter := false; // P1의 임계영역 사용 완료 지정 19 otherstuffone // P1의 잔류영역 수행 20 end; 21 end; 22 procedure P2; 23 begin 24 while true do 25 begin 26 P2_enter := true; 27 while P1_enter do; 28 if fprocess = first then 29 begin 30 P2_enter := false; 31 while fprocess = first do; 32 P2_enter := true; 33 end; 34 criticalsectiontwo; 35 fprocess := first; 36 P2_enter := false; 37 otherstufftwo 38 end; 39 end; 40 begin 41 P1_enter := false; 42 P2_enter := false; 43 fprocess := first; 44 parbegin 45 P1; 46 P2; 47 parend; 48 end. 11

2. 상호배제와 동기화 하드웨어적인 임계영역 문제 해결 특별한 하드웨어 명령을 사용하여 임계영역 문제를 해결 가능. 기계를 비교하거나 단어 내용을 검사 및 수정 또는 내용을 바꾸는(Swap) 명령을 사용하여 임계영역 문제 해결. 하나의 기억장치 사이클에서 수행되므로 생산자/소비자 문제에서 예로 든 counter 변수 수 정에 발생하는 문제 해결 가능. testandset을 이용한 상호배제 알고리즘 (알고리즘 4-12) testandset(a, b);는 논리변수 b를 읽어 a에 복사하고 b를 참으로 하는 명령. 단일 프로세서 또는 메모리를 공유하는 다중 처리 환경과 관계없이 적용되며, 간단하여 쉽 게 적용된다는 장점을 가짐. 임계영역에 진입하려는 프로세스에 바쁜 대기가 발생. 무한 연기 가능성이 발생할 수는 있지만 프로세스 수가 많으면 거의 발생하지 않음.

2. 상호배제와 동기화 알고리즘 4-12 testandest을 이용한 상호배제 알고리즘 01 program testandsetexample; 02 var active : boolean; // 공유변수(논리변수) 선언 03 procedure process1; 04 var notenter1 : boolean; 05 begin 06 while true do 07 begin 08 notenter1 := true; 09 while notenter1 do 10 testandset(notenter1, active); 11 criticalsectionone; active := false; 13 otherstuffone; 14 end; 15 end; 16 procedure process2; 17 var notenter2 : boolean; 18 begin 19 while true do 20 begin 21 notenter2 := true; 알고리즘 4-12 testandest을 이용한 상호배제 알고리즘 22 while notenter2 do 23 testandset(notenter2, active); 24 criticalsectiontwo; 25 active := false; 26 otherstufftwo; 27 end; 28 end; 29 begin 30 active := false; 31 parbegin 32 process1; 33 process2; 34 parend; 35 end.

[그림4-16] 세마포어의 예인 열차의 진행 가능 여부 표현 2. 상호배제와 동기화 세마포어 (Semaphore) 음이 아닌 정수값을 갖는 플래그 변수. 다익스트라(Dijkstra)가 상호배제의 문제를 극복하기 위해 제안함. - P와 V라는 2개의 연산에 의해서 동기화를 유지하며 상호 배제의 원리를 보장. - S는 P와 V 연산으로만 접근 가능한 세마포어 변수로, 공유자원의 개수를 나타내며, 0과 1혹은 0과 양 의 값을 가질 수 있음. 세마포어의 유명한 예 ‘열차의 진행 가능 여부’를 나타내는 차단기. - 차단기 올라감 : 정지/대기 (운영체제는 자원이 없어 기다리는 경우) - 차단기 내려감 : 진행 (프로세스가 해당 자원을 사용할 수 있는 자유 상태) [그림4-16] 세마포어의 예인 열차의 진행 가능 여부 표현 동기화 기법 두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처 리 순서를 결정하는 것으로 상호배제의 한 형태. 동기화 구현 방법에는 세마포어와 모니터 기법이 있음.

2. 상호배제와 동기화 세마포어 정의 프로세스 동기화 문제 해결을 위한 두 가지 연산(P, V). - P : 네덜란드어로 검사(Proberen)를 나타내며, 프로세스를 대기시키는 wait 동작으로 임계 영역에 진 입하기 위한 연산. - V : 네덜란드어로 증가(Verhogen)를 나타내며, 대기 중인 프로세스를 깨우는 신호를 보내는 signal 동 작으로 임계 영역에서 나오기 위한 연산. - S : 세마포어를 나타내며, 표준 단위 연산 P와 V에 의해서만 접근되는 정수 변수. P와 V 연산은 다음과 같이 정의함. P(S) : while S ≤ 0 do no-op; S := S – 1; V(S) : S := S + 1; - P와 V 연산에 있는 세마포어 정수값은 개별적으로 실행됨. (프로세스 하나가 세마포어 값을 수정할 때 다른 프로세스가 같은 세마포어 값 동시 수정 불가) - wait 인 경우 S 값 검사하고(S<=0), 가능한 수정(S:=S-1)은 인터럽트 없이 실행해야 함. - P와 V의 동작은 세마포어를 인자로 명명한 임의의 프로세스가 요청한 시스템을 호출함으로써 운영체제에 의해 실행됨. 프로세스 제어를 용이하게 하며 P 연산을 요구하는 프로세서는 그 동작이 수행 가능한 상 태(S>0)가 될 때까지 대기해야 함.

2. 상호배제와 동기화 세마포어 사용 세마포어는 프로세스 n개의 임계 영역 문제를 다루는 데 사용. - 세마포어 S에 적용된 두 연산 P, V는 동시에 두 가지 동작이 실행되는 것을 예방하는 상호 배제를 의미함. - n개의 프로세스는 1로 초기화된 공통 세마포어인 mutex(Mutual Exclusion)를 공유. - 각 프로세스 Pi의 구조는 아래와 같음. repeat P (mutex); 임계영역 V (mutex); 잔류영역 until false; 세마포어는 여러 가지 동기화 문제를 다루는 데 사용. ex: 수행 중인 두 개의 프로세스, 문장 S1을 가진 P1과 문장 S2를 가진 P2의 경우. - 조건 : S2는 S1이 끝난 후에만 수행되도록 구현함. - 구현 방법 : P1과 P2가 0으로 초기화되는 공통 세마포어 synch를 공유하며, P1에는 ① 명령을 삽입, P2에는 ② 명령을 삽입하여 구현 가능. ① S1 ; ② P(synch); V(synch); S2;

2. 상호배제와 동기화 세마포어 구현 이진 세마포어는 0, 1 값만 가짐. 상호 배제의 해결과 세마포어의 단점 : 한 프로세스가 임계 영역에 있을 때, 임계영역에 들 어가기를 원하는 다른 프로세스가 진입코드를 계속 순환하여 프로세서 시간을 낭비. 바쁜 대기 요구를 극복하기 위해 세마포어의 wait, signal 동작을 수정. - 프로세스가 wait 동작을 실행하고 세마포어의 값이 양수가 아닐 경우 프로세스는 대기함. - 다음 제어는 프로세서 스케줄러에 넘기고 프로세서는 준비 큐에서 다른 프로세스를 선택. - 세마포어 S에 의해 블록/대기 중인 프로세스는 다른 프로세스가 signal 동작을 실행해야 재시작 가능. - 프로세스는 wakeup 동작에 의해 재시작되고, 대기상태에서 준비 상태로 변하면서 준비 큐에 놓임. - 이를 바탕으로 아래와 같은 레코드로 정의 가능. * 정수값과 프로세스 리스트로 구성. * 세마포어에 의해 대기중인 프로세스는 프로세스 리스트에 추가. * V연산은 대기 프로세스 리스트에서 하나를 꺼내 이를 깨움. type semaphore = record value : integer L : list of process; end; 세마포어는 block/wakeup 동기화를 구현하는 메커니즘으로도 사용됨. - 하나의 프로세스가 자신을 보류시켜(S=0일때 P(S)를 함으로써) 사건이 발생할 때까지 기다리면 다른 프로세스가 사건 발생 때 보류된 프로세스를 깨움(V(S)로).

2. 상호배제와 동기화 세마포어 동작의 정의. ① 세마포어 S에 대한 P 연산을 P(S)라 쓰고 다음과 같이 실행한다. S := S – 1; if S < 0 then begin 프로세스 대기(보류)상태 프로세스 번호를 wait 큐에 추가 end; else 임계영역 수행 ② V 연산은 V(S)라 쓰고 다음과 같이 실행한다. V(S) : S := S + 1; if S <= 0 대기 큐에서 프로세스를 제거하고 제거한 프로세스에 wakeup 신호를 보내서 준비 큐에 추가

2. 상호배제와 동기화 프로세스 리스트는 각 프로세스 제어 블록(PCB)의 링크 필드(Link Field)의 정보를 이용해 구현 가능 - 각 세마포어는 정수값과 PCB 리스트의 포인터를 포함. - 리스트에서 LIFO(Stack)을 이용하여 프로세스를 추가, 제거 가능하나 기아상태를 발생시킬 수 있음. 세마포어의 특징. 단위적 수행은 세마포어의 중요 특징이며, 임계영역 문제의 한 예임. - 두 프로세스가 동시에 같은 세마포어에 대해 P와 V연산을 할 수 없도록 하는 것. 단일 프로세서인 경우 P와 V 연산을 수행하는 중에 인터럽트를 금지함으로 해결 가능. - 인터럽트를 금지하면 다른 프로세서의 명령어 실행이 중간에 끼어들지 않음. 다중 프로세서인 경우 인터럽트 금지가 허용 불가능. - 하드웨어가 특별한 명령을 제공하지 않으면, 소프트웨어적 해결 방법을 사용해야 함. - 임계 영역은 P와 V 프로시저로 구성됨. P, V 연산은 짧은 시간 동안만 임계영역을 제한할 수 있음. - P, V 연산으로 바쁜 대기를 완전히 제거 불가능하므로 응용 프로그램의 진입점에서 임계영역까지 바 쁜 대기를 제거하여 바쁜 대기의 시기를 이동시킴. - 임계영역이 길거나 항상 점유된 상황 시 비효율적임. P연산을 생략하거나 V연산이 생략되면 상호배제 문제와 P 연산 때문에 대기하고 있는 프 로세스들이 교착 상태에 빠질 수 있음. - P 연산이 시작되면 프로세스는 다른 경로를 선택할 수 없음. - 프로세스는 한 번에 한 세마포어만 대기 가능해 자원을 할당하는 상황에서 교착 상태 발생 가능. (두 프로세스가 각각 한 자원을 보유하고 다른 프로세스가 상대방의 자원을 사용하려고 대기하는 경우)

2. 상호배제와 동기화 모니터 (Monitor) 프로그래밍 언어에서 제공되는 프로그래머 정의 연산자들의 집합으로 구성. 세마포어의 P, V 연산이 프로그램 전체에 퍼져 있으며, 이들 연산이 미치는 영향을 전체적 으로 파악하기 쉽지 않아 프로그램 작성이 어려운 단점을 극복하기 위함. 핸슨(Brich Hansen)과 호(Hoare)가 개발. 모니터의 형태 표현은 변수 선언으로 구성, 변수 값이 형태를 정의함. 모니터의 문법 구조는 아래와 같음. Type monitor-name = monitor 변수 선언 procedure entry P1(…); begin … end; procedure entry P2(…); … procedure entry Pn(…); begin 코드 초기화 end.

2. 상호배제와 동기화 모니터의 구조 하나 이상의 프로시저(연산 동작들)와 초기화 코드, 공유 데이터로 구성된 소프트웨어 모듈 로 이루어진 객체. 모니터 안에 정의된 프로시저는 모니터 내에서 지역적으로 정의된 변수와 형식 매개변수들 만 접근 가능. 또한 모니터의 지역 변수들은 지역 프로시저만 접근 가능. - 모니터 밖에 있는 프로세스는 모니터에 있는 데이터에 접근 불가능. (모니터 외부의 프로세스는 모니터 내부의 데이터를 직접 액세스 할 수 없음) 모니터 경계에서 한 번에 한 프로세스만 진입하도록 제어되므로 상호 배제 원칙을 지킴. - 자원을 대기하는 프로세스 또는 모니터가 사용 중이면 진입을 원하는 프로세스는 대기해야 함. - 프로그래머는 동기화 제약 조건을 명시적으로 코드화할 필요 없음. (한 순간에 하나의 프로세스만 모니터 안에서 활동을 보장 받기 때문) 자원 반납 시 모니터 진입 루틴 호출. - 호출된 루틴은 대기 중인 프로세스 중 하나가 모니터에 들어가 지원을 얻을 수 있도록 신호를 보내고, 모니터는 대기 중인 프로세스에 자원 할당. - 대기가 무기한 연기되는 것을 막기 위해 새로 도착한 프로세스보다 이미 대기 중인 프로세스에 더 높 은 우선순위를 부여함. [그림4-17] 모니터의 일반 구조

2. 상호배제와 동기화 모니터의 조건 변수 임계영역과 유사하며, 프로세스가 실행되는 동안 상호배제와 동기화를 제공. 임계영역은 조건 임계영역으로 확장되었으며, 모니터에도 동기화를 위한 부수 기법이 필요. 모니터 밖의 프로세스가 대기 시 조건 변수에 의해 수행 재개가 결정됨. - 아래와 같이 한 개 이상, 조건 형태의 변수 정의 가능. 조건 변수에서는 wait와 signal 연산만이 호출 가능. - 조건 변수는 두 가지 연산을 제공하는 추상적인 데이터 형태로 볼 수 있음. 모든 조건 변수는 관련된 큐가 있기 때문에 wait를 호출하는 프로세스는 해당 조건 변수와 연관된 큐에 놓임. var x, y: condition; [그림4-18] 조건 변수들을 가진 모니터

2. 상호배제와 동기화 x.wait 연산 x.signal 연산 - 어떤 프로세스가 x.signal을 호출할 때까지 x.wait를 호출한 프로세스는 연기/중단된다는 의미. x.signal 연산 - 중단된 프로세스 중에서 한 개만 재개하며, 호출 시 해당 조건 변수와 연관된 큐에서 대기 중인 프로세스 하나를 큐에서 꺼내 모니터로 진입할 수 있도록 함. - 중단된 프로세스가 없으면 효과가 없으며, x의 상태는 연산이 전혀 실행되지 않는 것과 같음. 프로세스 P가 x-signal 연산 호출 시, 조건 x와 연관되고 중단된 프로세스 Q가 있다고 가정 시 두 가지 가능성이 존재함. - P는 Q가 모니터를 떠날 때까지, 또는 다른 조건을 위해 대기한다. - Q는 P가 모니터를 떠날 때까지, 또는 다른 조건을 위해 대기한다. P가 이미 모니터 안에서 실행되기 때문에 후자를 선택하는 것이 합리적이라 주장. - 프로세스 P를 계속 실행되도록 허용한다면 Q는 계속 대기. 호(Hoare)는 전자를 선택하는 것이 합리적이라 주장. - 주로 선행하는 조건들이 더욱 간단하고 세련된 증명 법칙들로 해석되었기 때문. 핸슨(Hansen)은 병행 파스칼 언어에서 이 두 가지 선택 사항을 절충하여 적용. - 프로세스 P가 signal 연산을 실행하면 즉시 모니터를 떠나고 Q가 즉시 재실행됨(신호 후 종료 기법). - 프로세스가 프로시저를 한 번 호출하는 동안 한 번 이상의 signal 신호를 보낼 수 없음.

2. 상호배제와 동기화 모니터 구현 각 모니터마다 세마포어 mutex(1로 초기화됨)를 제공. 프로세스는 모니터에 진입 전 P(Mutex)를 실행해야 하며 모니터를 떠날 때는 V(Mutex)를 실행해야 함. V(signal)를 보내는 프로세스는 재개된 프로세스가 떠나거나 대기할 때까지 대기. - 초기값이 0인 세마포어 next를 도입, next에서 signal을 보내는 프로세스는 자기 자신을 연기(중단)함. - 정수형 변수 next-count는 next에서 중단된 프로세스들의 수를 계산. 각 외부 프로시저 F는 다음 루틴으로 치환됨. P(mutex); … body of F; If next-count > 0 then V(next) else V(mutex);

2. 상호배제와 동기화 여러 개의 프로세스가 조건 x에서 중단되고 x.signal 연산이 어떤 프로세스에 의해 실행된다면, 어느 프로세스를 다음에 재개할 것인가? 단순한 해결 방법으로 선입 선처리 기법(FIFO)을 이용하여 가장 오래 대기한 프로세스를 먼저 재개시킴. 단순 스케줄링 기법 적용이 어려울 시 아래 형식의 조건 대기 구조 사용. - 조건 c가 만족될 때까지 모니터를 호출한 프로세스의 수행이 일시 정지되므로, 모니터를 다른 프로세 스들이 사용 가능. - c는 정수 식으로, wait 연산이 실행될 때 평가됨. - c 값은 우선순위 번호로 중단된 프로세스의 이름과 같이 기억. - x.signal이 실행될 때 c값이 가장 작은 우선순위를 가진 프로세스가 다음으로 실행됨. x.wait(c);

2. 상호배제와 동기화 단일 자원을 할당하는 모니터(알고리즘 4-13) 알고리즘 4-13 단일 자원을 할당하는 모니터 01 type resource-allocation = monitor 02 var busy: boolean; 03 x: condition; 04 05 procedure entry acquire(time: integer); 06 begin 07 if busy then x.wait(time); 08 busy := true; 09 end; 10 11 procedure entry release; 12 begin 13 busy := false; 14 x.signal; 15 end; 16 17 begin 18 busy := false; 19 end.

SUMMARY 병행 프로세스 선행 제약 상호배제 프로세스 여러 개가 동시에 실행. 독립적으로 수행 가능하며, 다른 프로세스와 협력하면서 기능을 수행하기도 함. 선행 제약 프로세스가 순서대로 다른 상태로 옮겨가는 것. 선행 그래프는 이러한 제약을 형식적으로 표현하는데 사용됨. 프로그래머는 순차 프로세스의 개념을 이용하여 프로그램에서 여러 명령문 사이의 선행 관계를 기술 가능. 상호배제 어떤 프로세스가 작업을 실행 중일 때 나머지 프로세스들이 그 작업에 관련된 작업을 수행할 수 없도록 함. 어떤 데이터를 공유하면서 협조 관계에 있는 순차 프로세스 집합체에서 상호배제는 필수적임.

SUMMARY 병행 명령 동기화 문제점 세마포어 임계영역과 모니터 선행 제약을 위해 fork와 병행명령(parbegin/parend)이라는 언어 구조 두 개가 제안됨. 병행 실행의 개념은 순차 프로세스 개념과 선행 그래프를 이용, 형식화됨. 동기화 문제점 상이한 동기화 문제점들(유한 버퍼문제, 생산자/소비자 문제)은 병행 제어 문제들의 실례들이므로 중요함. 새롭게 제안된 거의 모든 동기화 기법들은 검사를 위해 이 문제를 이용. 세마포어 상호배제의 해결책에 대한 주요 단점으로 이들은 모두 바쁜 대기를 요구한다는 점임. 다양한 동기화 문제들을 해결하기 위해 사용 가능하며 효과적으로 구현됨. 임계영역과 모니터 운영체제는 타이밍 오류에 대처할 수 있는 수단을 제공해야 함. 임계영역은 상호배제와 임의의 동기화 문제들을 안전하고 효과적으로 구현하기 위해 사 용. 모니터는 추상 데이터 형태를 공유하기 위한 동기화 메커니즘을 제공.