4장 병행 프로세스 병행성의 원리를 이해한다 병행 프로세스 수행과 관련된 상호 배 제 해결방안을 알아본다

Presentation on theme: "4장 병행 프로세스 병행성의 원리를 이해한다 병행 프로세스 수행과 관련된 상호 배 제 해결방안을 알아본다"— Presentation transcript:

1 4장 병행 프로세스 병행성의 원리를 이해한다 병행 프로세스 수행과 관련된 상호 배 제 해결방안을 알아본다
병행성의 원리를  이해한다 병행 프로세스 수행과 관련된 상호 배 제 해결방안을 알아본다 프로세스간 상호작용에 대하여 살펴 본다.

2 병행 프로세스 병행 프로세스 - 프로세스들이 여럿이 동시에 수행 상태 비동기적(asynchronous)병행 프로세스
서로 관련 없이 독립적 수행 또는 다른 프로세스와 협력 필요하면서 기능 수행 비동기적(asynchronous)병행 프로세스 프로세스들 간에 교신 필요하고 그것이 동기화가 되어야 한다면 비동기적 병행 프로세스라 함. 병행 프로세스 사이에는 제한된 자원을 공유하기 위하여 자주 상호 작용 필요 하므로 상호 작용 프로세스를 그대로 두면 문제 발생한다. 따라서 순서에 맞게 실행되도록 프로세스간의 동기화 필요함. ◆ 동기화(Synchronization) - 둘 또는 그 이상의 프로세스가 시간에 따라 실행 순서가 이루어져야 할 경우, 이들 프로세스에 대한 처리 순서를 결정해야 하는 것

3 병행 프로세스 병행 프로세스 과제 결론 : 프로세서를 수행하는 과정에서 발생되는 상호 배제 보장이 필요함.
공유 자원의 상호 배타적 사용 예) 프린터, 통신망 등은 한 순간에 한 프로세스만 사용 협력 또는 동기화가 이루어져야 즉 상호배제는 동기화의 한 형태 2 프로세스 사이 자료 교환을 위한 통신이 이루어져야 함. 결정성(determinancy) 확보 동시에 수행되는 다른 프로세스들의 실행 속도와 관계없이 항상 일정한 실행 결과 보장되는 것 교착 상태 해결하여야 하며 병행 프로세스들의 병렬 처리 능력 극대화 해야 함. 올바른 실행을 검증하는 문제가 해결되어야 함. 결론 : 프로세서를 수행하는 과정에서 발생되는 상호 배제 보장이 필요함.

4 병행 프로세스 선행 그래프 [예] a := x + y; b := z + 1; c := a - b; w := c + 1;
프로세스 요소 프로세스의 집합 + 이들의 선행제약(precedence constraint;우선순위 제약) 선행제약 - 부분순서로 이행성 유지 하는 것 P1, P2....Pn의 프로세스가 있으면 선행순서는 Pi < Pj 로 표시 Pi < Pj 이고  Pj < Pk 이면 Pi < Pk 되고 두 프로세스 간에 선행관계가 없으면 – 독립적, 병행해서 실행 가능 선행 그래프(Precedence Graph)를 사용하면 제약을 규칙적(논리적) 표현 할 수 있음. [예] a := x + y; b := z + 1; c := a - b; w := c + 1;  c := a - b  a와 b가 값을 할당 받기 전에 수행 불가  w := c  c의 값이 계산되기 전 수행 불가  a := x + y, b := z + 1  서로 독립적, 동시 수행 가능. 단일 프로그램도 여러 문장 중에 선행제약 있음

5 병행 프로세스 선행 그래프 - 계속 선행 관계 선행 그래프는 각 문장에 대응되는 노드들이 비순환 그래프 구성 되어야 한다.
노드 si 노드 sj : 연결선(edge)은 문장 si가 수행된 후 문장 sj가 수행 의미 선행 관계 ① s2와 s3는 s1이 끝난 후 수행 ② s4는 s2가 끝난 후 수행 ③ s5와 s6는 s4가 끝나 후에 수행 ④ s7은 s5, s6, s3가 끝난 후에만 수행     s3는 s2, s4, s5, s6와 병행되어 수행

6 병행 프로세스 선행 그래프 - 계속 s3는 s2가 끝난 후에만 수행될 수 있고 s2는 s3가 끝난 후에만 수행되므로

7 병행 프로세스 언어적 표현과 병행 문장 1) Fork와 Join 구조
선행 그래프 - 연산 부분의 선행 제약을 정의하는데 유용 함. - 선행그래프는 2차원적 표현이기 때문에 프로그래밍 언어에서 사용 곤란. Fork문과 join문 ,병행 문장(parbegin/parend) - 여러 문장 중에서 선행 관계를 명시한 언어 구조 1) Fork와 Join 구조 콘웨이(Conway)와 데니스, 호른(Dennis & Van Horn(1966)에 의해 소개 fork L 명령은 병행을 명시하기 위한 최초의 언어적 표현 fork L 명령 - 프로그램 상에서 두 개의 병행 수행 생성 - L로 레이블이 붙여진 문장에서 수행 시작 - fork 명령은 바로 다음 문장에서부터 계속

8 병행 프로세스 언어적 표현과 병행 문장 - 계속 s1 ; fork L; s2 ; . L : s3 ;
    . L : s3 ; ▶ fork L 수행 - 새로운 연산이 s3로부터 실행 - 새로운 연산- s2로부터 시작되는 연산과 병행수행 ▶ fork 문장 - 단일 연산을 두 개의 독립적 연산으로 분할 join - 2개의 병행 연산을 하나로 재결합시키는 방법 제공. 연산 : 서로 다른 속도로 진행  하나는 다른 것보다 먼저 join 수행 먼저 join을 수행한 연산은 끝 나고, 다른 연산은 계속 수행 가능 세 개의 연산이 합쳐져야 될 경우 join을 수행한 처음 두 개가 끝이 나고, 다른 연산은 계속 수행 - 마지막 하나를 제외하고 나머지를 완료하기 위해서는 연산의 개수 알아야 함.

9 병행 프로세스 언어적 표현과 병행 문장 - 계속 : count := count - 1;
 join : 합쳐져야 할 연산의 수 명시 인자 가진다. [예] count 파라미터를 가지는 join 명령 수행 효과 count : 0이 아닌 정수 값으로 초기치 2 quit : 계산 수행을 종료시키는 명령 join : 단위적으로 수행 두 개의 join 병행 수행  두 문장이 임의의 순서로 순차 수행되는 것과 동일 : count := count - 1; if count ≠ 0 then quit;   count ;= 2;     fork L1;     :     :     S1;    go to L2; L1 : S2; L2 : join count;      S3;          선행 그래프

10 병행 프로세스 언어적 표현과 병행 문장 - 계속 [예] a := x + y; b := z + 1; c := a - b;
두 개의 read 문장을 병행 수행- fork와 join 명령 이용 작성 [예] a := x + y; b := z + 1; c := a - b; w := c +1; count := 2;      fork L1;      a := x + y;      go to L2; L1 : b := z +1; L2 : join count ;      c := a - b;      w := c + 1; [그림4-5]   산술식에 대한 선행그래프와 fork-join구조 

11 병행 프로세스 언어적 표현과 병행 문장 - 계속 S1; count := 3; fork L1; S2 ; S4; fork L2;
 fork, join 명령 이용 작성  병행 프로그램 작성 수단 어색한 제어 구조( fork : go to  문장 유사)   S1;       count := 3;       fork L1;       S2 ;       S4;       fork L2;       S5 ;       go to L3;  L2 : S6 ;       go to L3;  L1 : S3 ;  L3 : join count;       S7 ; join 노드 - (S7) 유입 정도(in-degree) 3 - 하나의 join 필요 join의 count 초기치 : 3 [그림4-1] 선행 그래프 fork, join 명령 이용한 알고리즘

12 병행 프로세스 언어적 표현과 병행 문장 - 계속 2) 병행문장
- Dijkstra(1965)가 제시한 parbegin/parend 표현방법 사용 ▶ 한 개의 프로세스가 여러 가닥의 병렬 프로세스로 실행하다가  다시 한 가닥의 프로세스로 뭉쳐지는 고급언어 구조는 parbegin/parend 형태이다.  parbegin S1; S2; ; Sn  parend    Si: 단일 문장 parbegin과 parend 사이의 모든 문장⇒ 병행 수행 Sn+1 은 모든 S (i=1, 2, .... n)가 모두 끝난 후에만 실행 [그림4-6]병행문장의 선행그래프

13 병행 프로세스 언어적 표현과 병행 문장 - 계속 [예] parbegin a := x + y; S3; b := z + 1;
      parend;     end; parend; S7; [예] a := x + y; b := z + 1; c := a - b; w := c +1; parbegin       a := x + y;       b := z + 1;  parend;    c := a - b;    w := c + 1; 선행 그래프에 대한 알고리즘 parbegin/parend 구조 표현

14 상호 배제와 동기화 02 상호배제(mutual exclusion)
- 특정한 비공유 자원 → 한 순간에 1개의 프로세스만 사용하는 것 - 하나의 프로세스가 공유 데이터 액세스할 때 다른 프로세스들의 데이터 액세스를 금지하는 것  [예] 공통 변수나 파일 - 차례대로 하나의  프로세스만이 R/W 하는 것. 프로세스들 간의 동기화 순차적으로 재사용 가능한 자원을 공유하기 위하여 상호 협력하는 프로세스 사이에서 나타남. 상호 배제가 실시되면 교착상태와 기아 상태 발생 – 5장 참고

15 상호 배제와 동기화 02 프로세스간 상호 작용 동시에 수행되는 프로세스들이 같은 자원사용 시 – 충돌 발생
[예] 입출력 장치, 메모리, 프로세서, 클럭 등 ▶ 이러한 자원 - 다른 프로세스에 의해서 영향을 받거나, 상태가 변화 시켜서는 안됨 3가지 형태 ① 서로 인식 못하는 경쟁 관계 를 유지하는 독립적인 프로세스 [예] 서로 독립적인 여러 프로세스들로 이루어진 다중프로그래밍 환경 ⇒ OS는 자원에 대한 경쟁을 고려하여 동일한 디스크나 프린터의 접근 조절이 필요함. ② 프로세스들이 간접적으로 인식하는 관계로 입출력 버퍼 등 공유 개체를 공유하는 단계 - 다른 프로세스로부터 얻은 정보에 의존 또는 프로세스의 타이밍 영향  받을 수 있음 ⇒ 프로세스들은 공동 개체를 공유하는데 따른 협력이 필요함. ③ 프로세스들이 서로 인식하고 통신할 수 있는 기본적인 함수 보유하는 경우 - 직접 통신 가능하고 서로 함께 동작되도록 설계된 프로세스이다.(협력관계) - 이러한 프로세스는 구분되는 것은 아니며 때로는 경쟁과 협력이 함께 나타날 수도 있음

16 상호 배제와 동기화 02 프로세스간 상호 작용 - 계속 ■ 경쟁관계 프로세스
■ 경쟁관계 프로세스 정보 교환이 없으나 어떤 프로세스의 수행이 나머지 프로세스들의 수행에 영향을 줄 수 있음 두 개의 프로세스가 동일 자원에 대한 접근을 시도하는 경우 - OS는 하나의 프로세스에 자원을 할당 한다. 결론 : 경쟁관계에 있는 프로세스들은 상호배제 필요 함.    

17 상호 배제와 동기화 02 임계영역 임계자원 - 둘 이상의 프로세스들이 공유할 수 없는 자원(프린터)
  임계자원 - 둘 이상의 프로세스들이 공유할 수 없는 자원(프린터) 임계영역(critical section) - 프로그램에서 이 자원을 이용하는 부분 - 두 프로세스(입력과 출력)가 공통 버퍼 사용 - 버퍼를 임계영역(CS) 임계영역 [그림4-7] 임계영역 프로세스가 공유 데이터 엑세스 - CS내에 있다고 표현 프로세스들은 공통 변수 읽고, 테이블 갱신, 파일 수정 등 수행한다. 어떤 프로세스가 CS 진입 - 다른 프로세스 CS 진입 금지 CS 내 - 빠른 속도로 수행, 보류(block) 안되며, 무한순환 등에 빠지지 않도록 작성 ⇒ 결론은 프로세스에 의한 CS의 수행은 상호 배제적이어야 한다.

18 상호 배제와 동기화 02 임계영역 - 계속 임계영역 진입을 원하는 프로세스는 – 진입 상호배제를 수행 하려고 하나
진입상호배제는 –하나의 프로세스가 CS내에 있으면 진입을 금지 시킨다. CS을 떠나는 프로세스는 출구상호배제 수행함으로써 다른 프로세스가 CS에 들어갈 수 있도록 조치 한다. 임계 영역 진입 임계 영역 나옴 B는 임계 영역 진입 시도 B는 임계 영역 나옴 B는 임계 영역 진입 [그림4-8] 임계영역을 이용한 상호배제

19 상호 배제와 동기화 02 임계영역 - 계속 임계영역 문제 - 프로세스들이 서로 협력하여 사용하도록 프로토콜을 설계한다.
각 프로세스 – CS 진입 여부 요청 필요함. 진입 코드 : 진입 요구를 구현한 코드 = 또는 진입영역 출구(exit)영역 - CS의 수행 마치고 다음에 진입할 프로세스를 선택하는 것 잔류영역 -나머지 코드로 CS을 나와서 나머지 작업 수행 [그림4-9] 병행 프로세스에서의 임계영역(cs) 과 잔류영역(rs)

20 상호 배제와 동기화 02 임계영역 - 계속 CS 문제의 해결은 아래의 3가지 요구가 만족되어야 한다. 상호 배제     프로세스 Pi 가 CS 수행 중 일때 다른 어떤 프로세스도 CS 수행 불가 진행(요구) -  CS영역을 수행하는 프로세스가 없고 여러 개의 프로세스들이 CS에 들어오려고 할 때 잔류영역에서 처리하지 않은 프로세스들 중에서 수행 대상을 빠르게 결정  제한된 대기 -  CS에 대한 요청 후부터 요청이 수락되기까지의 기간 내에 다른 프로세스가 CS을 수행하는 횟수에는 제한이 있어야 한다.

21 상호 배제와 동기화 02 생산자/소비자 프로세스 ■ 여러 프로세스들이 공통의 작업을 수행하기 위해 서로 협력하는 경우 예 이거나 또는 병행처리에서 발생되는 가장 흔한 예가 생산자/소비자, 판독자/기록자 문제이다. 생산자/소비자 문제는 상호배제와 동기화를 필요로 하며 세마포어를 이용 구현함. 생산자/소비자 프로세스는 비동기적 수행 모델로 생산자(P)프로세스는 소비자(C)프로세스에 의해 소비되는 정보를 생산한다. [그림4-10] 생산자/소비자 프로세스 관계 생산자와 소비자 프로세스 병행 실행 생산자와 소비자는 같은 버퍼 접근

22 상호 배제와 동기화 02 생산자/소비자 프로세스 ▶ 버퍼의 3 가지 상태 생산자 소비자
▶ 버퍼의 3 가지 상태  생산자 소비자 → 가득찬 버퍼 → 부분적으로 비어 있는 버퍼 → 모두 비어 있는 버퍼 [그림 4-11] 세가지 종류의 전형적인 버퍼 상태=속도가 다른 경우 프로세스통신(IPC:Interprocess Communication)의 예 - 생산자 소비자 관계에서 한 프로세스가 정보 생산 ⇒ 다른 프로세스는 그 정보를 소비 생산자는 버퍼가 가득 찼을 때 : 정보 생산 중단 - 소비자는 버퍼가 텅 비어있을 때 : 정보 소비 중단 - 버퍼가 비워있거나 꽉 차 있으면 버퍼의 접근을 배제해야 하므로 생산자와 소비자는 동기화되어야 한다.

23 상호 배제와 동기화 02 생산자/소비자 프로세스 무한 버퍼 생산자/소비자 문제 - 버퍼의 크기에 제한을 두지 않으며 항상 버퍼에 빈자리 존재 유한 버퍼 생산자/소비자 문제 - 고정된 크기를 가진 버퍼를 둔다. - 버퍼가 비면 소비자는 기다리고 버퍼 차면 : 생산자가 기다림 [그림4-12] 유한 버퍼 시나리오

24 상호 배제와 동기화 02 생산자/소비자 프로세스  유한 버퍼 문제 해결 - 공유 버퍼 저장소를 논리적 포인터 in과 out을 사용한 순환 배열로 구현 var n; type item = … ;    var buffer : arrary [0..n-1] of item ;        in, out : 0..n-1 ;         nextp, nextc : item ;         in : = 0 ;         out : = 0 ; in , out  0 (초기화) in : 다음의 비어있는 버퍼 가리키고 out : 채워진 버퍼의 맨 처음 지시 소비자는 버퍼에서 데이터를 읽기 전 in > out 확인 버퍼 a 구조  음영 부분은 점유된 지역 a[5] a[4] a[3] a[2] a[1] a[n] [그림4-13] 무한 버퍼 생산자/소비자

25 상호 배제와 동기화 02 생산자/소비자 프로세스 parbegin 생산자 : begin
                         repeat                                …                            nextp 에서 한 항목 생산                             while in + 1 mod n = out do no-op ;                             buffer[in] := nextp ;                             in := in + 1 mod n ;                          until false ;                       end ;                        소비자 : begin                            repeat                               while in = out do skip ;                               nextc := buffer[out] ;                               out := out + 1 mod n ;                                 …                               nextc 에서 한 항목 소비                            until false ;                      end ;   parend ;   유한 버퍼를 공유하는 생산자/소비자 프로세스간의 병형 프로그램 in = out : 버퍼 빈 경우 (in+1) mod n = out : 버퍼 차 있는 경우 no-op : 아무 일도 하지 않는 경우 while 조건 do no-op : 조건이 거짓이 될 때까지 반복적 조건 검사 nextp : 생산될 새로운 항목이 기억되는 지역변수 Nextc : 소비될 항목이 기억되는 지역변수 ※ 7 mod 3 = 4이다. 즉 7을 3으로 나누어 나머지 값을 구함

26 상호 배제와 동기화 02 생산자/소비자 프로세스 repeat … nextp 에서 한 항목 생산 …
결점 해결  정수 변수 counter를 추가하여 0으로 초기화 새로운 요소가 더해질 때마다 counter 1씩 증가, 빼낼 때마다 1씩 감소 생산자 프로세스를 위한 코드 소비자 프로세스를 위한 코드  repeat            …            nextp 에서 한 항목 생산             …            while counter = n do no-op ;            buffer[in] := nextp ;            in := in + 1 mod n ;            counter := counter + 1 ;  until false ;    repeat                   while counter = 0 do no-op ;                   nextc := buffer[out] ;                   out := out + 1 mod n ;                   counter := counter - 1 ;                      …                   nextc 에서 한 항목 소비    until false ; 동시 수행  기능이 다르게 동작 [예] counter = 5일 때, counter := counter+1과 counter := counter-1 동시 수행  counter 값은 4, 5, 6이 될 수 있음  정상적으로 P와 C가 각각 별도로 수행 : counter의 값은 5

27 상호 배제와 동기화 02 생산자/소비자 프로세스 register1 := counter;
register1 := register1 +1; counter := register1; Counter 값의 오류  * counter := counter +1  기계어 작성 * counter := counter -1  기계어 작성       register2 := counter; register2 := register2 -1; counter := register2; register1, register2 : 국부 레지스터 각 레지스터는 인터럽트 처리기와 디스패처 등의 프로세서 스케줄링 루틴에 의해 저장되었다가 복귀 counter := counter +1과 counter := counter -1의 동시 수행 ⇒ 위에 제시된 기계어의 임의의 순서로(겹쳐진 순서)실행

28 상호 배제와 동기화 02 생산자/소비자 프로세스 [예]
 T1 : 생산자가 register1 := counter를 수행(register1 = 5)  T2 : 생산자가  register1 := register1+1을 수행(register2 = 6)  T3 : 소비자가  register2 := counter를 수행(register2 = 5)  T4 : 소비자가  register2 := register2-1을 수행(register2 = 4)  T5 : 생산자가  counter := register1을 수행(counter = 6)  T6 : 소비자가  counter := register2을 수행(counter = 4) register1 := counter; =5 register1 := register1 +1; counter := register1; =6 실제적으로는 counter = 5 이어야 하는데 ⇒ counter = 4이다. - T5와 T6순서를 바꾸면 counter = 6 [이유] 두 프로세스가 변수 counter를 동시에 조작 오류 방지 : 공유변수 counter를 한 프로세스만이 조작  CS 문제 counter 조작 부분 : CS으로 설정하여 상호배제 단일 프로세서 시스템 : 같은 현상 발생 - register1과 register2는 서로 문맥 교환 후 복귀 될 수 있기 때문 register2 := counter; =6 register2 := register2 -1; counter := register2; =5

29 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 1) 알고리즘 1 2개의 프로세스(p1, p2) 상호 배제 해결 알고리즘
- parbegin/parend : p1과 p2가 동시 수행 CS의 진입여부 확인 : while 순환으로 구현  processnumber : 자기 프로세스의 번호와 일치할 때 까지 계속 순환 CS 나올 때는 상대방 프로세스 번호로 바꿀 수 있도록 조치  상대방 프로세스가 CS에 들어갈 수 있도록 - p1이 while do명령 수행 processnumber의 초기치 = 1  p1이 CS에 진입 p2는 CS 진입 실패  상호 배제 보장 - p1이 CS을 끝내고 processnumber = 2  p2가 CS에 진입 1개의 변수(processnumber)를 사용하여 해결 2개의 프로세스(p1, p2)가 교대로 실행

30 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 - 계속 program versionone;
       var processnumber : integer;        procedure p1;             begin                 while true do                     begin                       while processnumber = 2 do;                        criticalsectionone;                        processnumber := 2 ;                       otherstuffone                  end;            end; procedure p2;      begin           while true do                begin                   while processnumber = 1 do;                    criticalsectiontwo;                    processnumber := 1;                    otherstufftwo                 end;       end;           begin                processnumber:=1;                parbegin                      p1;                p2                parend            end 상호배제 단계 1 상호배제 보장 - p2 준비되어 있어도 p1 먼저 시작 - p1이 CS에 들어갔다가 나와야( 대기 시간 길어짐) - 프로세스들도 동일( 프로세스의 수행속도 느려짐) 교착 상태 방지 동시에 CS에 들어갈 수 없고 하나만 들어갈 수 있음 두 프로세스 중 하나 중지 : 1개의 공유변수 processnumber 사용

31 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 - 계속
대기 프로세스가 비생산적, 자원 소비하는 대기 루프에 남아있는 상태  프로세서 시간 낭비 결과 초래 소프트웨어 접근에 의한 해결 - 계속 2) 알고리즘 2 : 2개 변수(P1inside, P2inside) 사용 해결 program versiontwo var plinside, p2inside : boolean; procedure p1;        begin             while true do                 begin                     while p2inside do;                      plinside := true;                      criticalsectionone;                      plinside := false;                     otherstuffone                 end;        end;  procedure p2;       begin           while true do               begin               while p1inside do;                   p2inside := true;                   criticalsectiontwo;                   p2inside := false;                   otherstufftwo               end;       end:   begin     p1inside:=false;     p2inside:=false;     parbegin;        p1;        p2     parend  end 상호배제 단계 2 p1inside : p1이 CS에 있을 때 참 p2inside : p2가 CS에 있을 때 참 p2inside : 참  p1 바쁜 대기  p2가 CS 벗어나면 p2inside를 거짓   p1 : p1inside를 참, CS 진입 p1inside : 참인 동안 p2는 CS 진입 불가, p1과  p2는 동시 프로세스 : 동시에 while 문에 도달  p1inside는 거짓 p1 : p1inside를 참, CS 진입, p2 : p2inside를 참, CS 진입  2개의 프로세스가 동시에 CS 진입 결과 되어  상호배제가 보장되지 않음 -> 알고리즘2에서는 프로세스가 While문을 검사하기 시작하여 임계영역에 들어가는 동안에 /다른 프로세스가 더 빨리 검사를 하고 CS 진입에 들어갈 수 있기 때문에 문제가 발생함. - 해결 : 어떤 프로세스가 While검사를 시작하게 되면 다른 프로세스는 그것을 하지 못하게 해야 한다.

32 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 - 계속
문제 : 프로세스가 while 검사 시작하여 CS에 진입하는 동안 다른 프로세스가 더 빨리 테스트 하고 CS 진입하기 때문 발생 해결 방안 : 프로세스 while 검사 시작  다른 프로세스 검사 중단 3) 알고리즘 3 ⇒ while 검사 전에 자기가 while 검사 시작 사실을 플래그(문자표시)를 해줌  program versionthree;  var p1enter, p2enter : boolean;  procedure p1;       begin            while true do                  begin                     p1enter :=true;                     while p2enter do;                     criticalsectionone;                     p1enter : false;                     other stuff one                 end;       end;  procedure p2;        begin            while true do                begin                   p2enter :=true;                   while p1enter do;                   criticalsectiontwo;                   p2enter :=false;                   other stuff two               end;     end; begin    p1enter :=false;     p2enter :=false;     parbegin        p1;        p2     parend end        상호배제 단계 3 - 문제 제기 - 두 프로세스가 while 검사 전에 자신의 플러그를 동시에 바꾸면  영원히 while do - 2개 프로세스의 교착 상태 예 - 플래그 거짓(무한 연기 문제 발생)

33 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 4) 알고리즘 4 program versionfour;
var p1enter, p2enter : boolean; procedure p1;      begin         while true do             begin                p1enter := true;               while p2enter do;                  begin                    p1enter := false;                    delay(random, fewcycles);                    p1enter := true                 end;               criticalsectionone;               p1enter := false;               otherstffone            end;      end;  procedure p2;      begin         while true do            begin                p2enter := true;                while p1enter do;                    begin                       p2enter := false;                       delay(random, fewcycles);                       p2enter := true                    end;                 criticalsectiontwo;                 p2enter := false;                 otherstufftwo           end;       end; 상호배제 단계 4 begin      p1enter := false;      p2enter := false;      parbegin        p1;        p2      parend end - 가능한 순서 고려 - 각 프로세스는 나란히 진행 각 프로세스가 신호를 참으로 하고,  while 검사를 한 후 while loop 수행하여 플래그 거짓하고, 다시 참으로 하는 작업을 반복해서 검사를 계속할 수 가 있다.

34 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 - 계속
5) Dekker 알고리즘 - 2개의 프로세스의 상호배제 문제 해결    program dekkersalgorithm; var fprocess: (first, second);       p1enter, p2enter : boolean; procedure p1;    begin       while true do          begin             plenter := true;             while p2enter do;             if fprocess = second then               begin                 p1enter := false;                while fprocess = second do;                p1enter := true              end;             criticalsectionone;             fprocess := second;             p1enter := false;             otherstuffone         end;   end;  procedure p2;      begin         while true do            begin                 p2enter := true;                 while p1enter do;                     if fprocess = first then                        begin                           p2enter := false;                           while fprocess = first do;                           p2enter := true;                        end;                 criticalsectiontwo;                 fprocess := first;                 p2enter := false;                 otherstufftwo           end;      end; 상호 배제를 구현한 Dekker 알고리즘 P1에게 진입순서양보→ begin    p1enter := false;    p2enter := false;    fprocess := first;    parbegin        p1;        p2    parend end      ← P2에게 진입순서양보

35 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 - 계속 Dekker의 알고리즘
① p1 : 플래그를 참으로 설정 -> CS 진입사실 알림 후 -> while 검사 하여 -> p2의 CS 진입 여부 확인 ② p2 플래그가 거짓(false)이면 ⇒ p1은 CS로 진입 ③ p2 플래그가 참 (true)이면 ⇒ p1은 while 순환으로 대기 ④ fprocess 변수 : 2개의 프로세스가 동시에 CS 진입 시 충돌 방지 해줌 ⑤ p1이 fprocess이면  p1은 if문 영역을 수행하지 않고, p2가 플래그가 거짓이 될 때까지 while 순환에서 기다림 ⑥ p2가 fprocess이면  if 문 영역에 들어가 자기의 플래그를 거짓으로 하고, p2가 fprocess인 동안 계속 while 순환에서 기다림 ⇒ 자기의 플래그를 거짓으로 하여 p2가 CS 진입 가능케 함.

36 상호 배제와 동기화 02 소프트웨어 접근에 의한 해결 - 계속 Dekker의 알고리즘 특징 특별한 하드웨어 명령문 불필요
CS 밖에서 수행중인 프로세스가 다른 프로세스들의 CS 진입 방해 안 됨 CS 진입을 원하는 프로세서를 무한정 기다리게 해서는 안 됨  두 프로세스의 상호배제 문제 해결 n개의 프로세스에 대한 소프트웨어 해결방법 - 복잡 Dijkstra(다익스트라) - n개 프로세스의 상호배제문제를 소프트웨어로 해결 Knuth(크누스) - 무한 연기 현상의 가능성을 배제하는 해결책 제시 프로세스들이 오랫동안 기다림 Lamport(램포트) - 분산처리 시스템에 유용한 알고리즘 개발 “Lamport의 빵집 알고리즘” Brinch Hansen(브린치 핸슨) - 분산처리 프로세서 간의 동시성 제어에 대한 발표

37 상호 배제와 동기화 02 하드웨어에 의한 해결 임계 영역 문제 - 공유 변수 수정 동안 인터럽트 발생 억제하여 해결- 실행 효율 감소 - 많은 기계를 비교(test)하거나, 단어 내용 검사(수정), 내용을 바꾸는(swap) 명령어들 제공 하여 상대적으로  간단한 방식으로 CS 문제 해결한다. 따라서 알고리즘이 간단 해지고, 명령들은 하나의 기억장치 사이클에서 수행되므로 생산자/소비자 문제에서 예를 든 counter 변수 수정에서 발생하는 문제를 해소함. testandset(a, b) :  논리변수 b를 읽어서 a에다 복사하고 b를 참으로 하는 명령문

38 상호 배제와 동기화 02 하드웨어에 의한 해결-계속 procedure process2;
  var notenter2 : boolean;   begin    while true do     begin      notenter2 := true;      while notenter2 do       testandset(notenter2, active);      criticalsectiontwo;      active := false;      otherstufftwo;     end;  end; begin   active := false;  parbegin    process1;    process2;   parend end. program testandsetexample; var active : boolean; procedure process1; var notenter1 : boolean;  begin    while true do     begin      notenter1 := true;      while notenter1 do       testandset(notenter1, active);      criticalsectionone;      active := false;      otherstuffone;     end;   end testandset 이용 상호 배제 알고리즘

39 상호 배제와 동기화 02 하드웨어에 의한 해결-계속
① active(논리변수) : 프로세스가 CS 내에 있으면 참, 아니면 거짓 ② process1 : 자신의 논리변수 notenter1에 따라 CS 진입여부 결정 Notenter1 : 참, 계속해서  active를 testandset 함 Notenter2 : CS에 없으면 active는 거짓 ③ testandset : 거짓의 값을 읽어서 notenter1에 기억, active = 참 while 검사 = 거짓 ⇒ process1 : CS 진입 active = 참 ⇒ process2 : CS 진입 못함 ④ 만약 process1이 - CS 진입 때 process2가 이미 CS에 있다면 ⇒ process1 : notenter1을 참, 계속 testandset 실행 ⑤ CS에 process2가 있으므로 active는 참 testandset 할 때 마다  active가 참임을 알고 notenter1와 active를 참으로 하게 된다. ⑥ process2 가 CS을 벗어나서  active를 거짓으로 할 때 까지 process1은 바쁜 대기 ⑦ process2가 CS을 벗어나면 testandset는 active가 거짓임을 알고 process2를 들어갈 수 없도록 notenter1 = 거짓, process1은 CS에 진입 가능 단일 프로세서 또는 다중 프로세싱 환경에 관계 없이 적용되고 간단하게 적용되는 장점이 있으나 CS에 진입하려는 프로세스는 바쁜 대기가 발생함. 또한 무한 연기 가능성 발생 단, 프로세스 수가 많으면 거의 발생되지 않음

40 상호 배제와 동기화 02 세마포어 앞서 제시한 상호 배제의 해결를 좀더 복잡한 문제에서는 일반화가 어려움
이를 극복하기 위해 세마포어라고 부르는 새로운 도구가 Dijkstra에 의해서 제기됨. 세마포어(semaphore)는 플래그로 사용되는 음이 아닌 정수 값을 갖는 변수(예 : 열차 차단기) 이며 가장 잘 알려진 예가 철도에서 열차의 진행 가부를 나타내는 차단기이다. 진행 정지 [그림4-14]세마포어는 열차의 진행 여부 표현  - 차단기 올라가면 : 장애물이 있다는 표시(기다려야 함) ⇒ 운영체제의 경우는  자원이 없는 경우에 해당됨 - 차단기 내려가면 : 장애물이 없다는 표시(계속 진행 가능) ⇒ 운영체제의 경우  자원이 자유 상태(프로세스가 자원 사용 가능) ■ 프로세스의 동기화 문제 해결 방법 세마포어에 대한 2가지 동작(P, V)을 소개

41 상호 배제와 동기화 02 세마포어 - 계속 1) 정의 P(S) : while S ≤ O do no-op ; S :=S-1 ;
  P : 검사(proberen; 네덜란드어) ⇒ 프로세스를 대기시키는 Wait 동작 V: 증가(verhogen) ⇒ 대기 중인 프로세스를 깨우는 신호를 보내는 Signal 동작 S: P와 V에 의해서만 접근되는 정수 변수  P(S) : while S ≤ O do no-op ;             S :=S-1 ;  V(S) : S := S + 1 ;

42 상호 배제와 동기화 02 세마포어 - 계속 S에 대한 P 동작 : S 값 검사
양수 : 1(감소)  검사, 인출, 감소, 저장 순서로 구성 조건 : P, V 동작 종료까지 프로세스가  다른 P, V 동작 수행 않도록 조정 S에 대한 V 동작 : S ⇒1 증가 인출, 증가, 저장으로 구성 V 동작도 교착 상태를 피하기 위하여  단일 동작으로 수행 P와 V연산에 있는 세마포어의 정수 값 : 개별적 실행 프로세스가 세마포어 값 수정  동시 같은 세마포어 값 수정 불가 Wait인 경우 (2가지) S 값 검사(S ≤ 0) 수행 수정(S := S - 1)시 인터럽트 없이 실행해야 한다. P와 V 동작 세마포어를 인수로 명명한 임의의 프로세스에 의하여 요청된 시스템을 호출함으로 운영체제에의 의해 실행

43 상호 배제와 동기화 02 세마포어 - 계속 2) 사용 세마포어는 n개의 프로세스의 임계영역 문제 해결에 사용 됨.
n개의 프로세스는 1로 초기화된 공통 세마포어 mutex(mutual exclusion) 공유 함. 세마포어는 여러 가지 동기 문제 해결에 사용 된다. [예] 수행중인 2개의 프로세스 즉, 문장 S1을 가진 P1과 문장 S2를 가진 P2를 가장할 경우 S2는 S1 이 끝난 후에만 수행 되게 한다. 이는 P1과 P2가 0으로 초기화되는 공통 세마포어 ' synch' 공유하고 프로세스 P1과 P2 에는 아래 [그림]처럼 삽입하면 쉽게 구현된다.  S1 ;  V(synch) ; P(synch) ; S2 ; 프로세스 P1 프로세스 P2 - synch는 0으로 초기화되었기 때문에 P2는 P1이 V(synch)를 부르고 난 후 S2 수행 한다. 세마포어에 의한 상호 배제의 구현 ※ Synch=Synchronization;동기화

44 상호 배제와 동기화 02 세마포어 - 계속 3) 구현 세마포어는 제어된 변수로서 그 값은 P, V와 초기 작업 때에만 변화 함. 이진 세마포어는 0과 1의 값만 가진다. 상호배제 해결과 세마포어의 단점 : 바쁜 대기가 요구 됨 - 프로세스가 CS에 있으면, 진입코드에서 계속 반복 순환 해야 함(시간 낭비) 바쁜 대기 필요성 극복 방법 : 세마포어의 wait, signal 동작 수정함 - 프로세스는 wait 연산을 실행하고 세마포어의 값이 양수가 아니면 : 프로세스는 대기 함. - 다음 제어는 : 프로세서 스케줄러에게 넘기고 프로세스는 준비 큐에서 다른 프로세스 선택함. 세마포어 S에 의해 블록 또는 대기 중인 프로세스 경우 - 다른 프로세스가 signal  연산을 실행해야 재 시작 할 수 있고, 이때 wakeup 연산에 의해 재 시작되고, 대기상태에서 준비 상태로 변하면서 프로세스는 준비 큐에 놓는다.  

45 상호 배제와 동기화 02 세마포어 - 계속 ■ 세마포어를 다음의 레코드로 정의한다.
- 세마포어 : 정수 값과 프로세스의 리스트 유지, 어떤 프로세스가 세마포어에 의해 대기 중일 때 프로세스의 리스트에 추가 - V 동작 : 대기 프로세스의 리스트에서 하나 제거 하여 이를 깨운다(signal= wakeup). type semaphore = record      value : integer      L : list of process ;           end; ■ 세마포어 동작 정의  P(S):      S:= S - 1;      if S < 0         then begin             프로세스를 대기(보류)상태             프로세스번호를 wait큐에 추가         end;          else 임계영역 수행  V(S):       S := S  +1;       if 0          then begin              대기 큐에서 프로세스를 제거하고 제거한 프로세스에게  wakeup신호를 보내서 준비 큐에 추가한다.              end; P 오퍼레이션 V 오퍼레이션 ⇒ P와 V의 동작 : 세마포어 변수 S를 수정하는데 사용되지만 표시한 프로세스가 변수 S를 수정하면 다른 프로세스 수정 가능

46 상호 배제와 동기화 02 세마포어 - 계속 세마포어는 block/wakeup 동기화를 구현하는 메커니즘으로 사용 됨 ■ 하나의 프로세스가 자신을 보류시키고(S의 값이 0 일 때 P(S)를 함으로써), 사건 발생을 기다리면, 다른 프로세스가 사건의 발생을 알게 되어 보류된 프로세서를 깨워줌(V(S)) ■ 처음 p 동작 수행 프로세스 : 초기 값 s=1을 감소하여 0 이 됨. 이때 if 조건의 거짓되어 CS를 수행한다. ■ 다른 프로세스들이 CS 진입하려고 p 동작 수행할 때 마다 세마포어의 변수 값은 감소함 바쁜 대기 세마포어에서는 그 값이 절대음수가 될 수 없으나 여기에 구현된 세마포어의 값은 음수가 될 수 있음 ■ 세마포어의 값이 음수(-)일 때 wait 큐에 프로세스 번호를 삽입하고 보류되어 대기 상태가 되므로 S의 실제 값은 세마포어에서 기다리는 프로세스의 개수를 나타낸다. - 이러한 결과는 P동작의 구현에 있어 감산과 테스트의 순서를 맞바꿈으로 나타남

47 상호 배제와 동기화 02 세마포어 - 계속 프로세스 리스트
⇒ 각 프로세스 PCB의 링크 필드(link field)에 의해 쉽게 구현함. 각 세마포어 ⇒ 정수 값과 PCB 리스트의 포인터 포함 함 리스트에서 프로세스 추가, 제거시키는 가장 간단한 방법은 LIFO(stack)이다. ⇒ 이 방법은 기아상태 발생 초래 함. 세마포어의 중요 특징 : 단위적으로 수행됨 - 두 개의 프로세스가 동시에 같은 세마포어에 대하여 P와 V 조작 못 하게 하여야 함

48 상호 배제와 동기화 02 세마포어 - 계속 임계 영역 문제의 예 ① 단일 프로세서 경우 해결 방법 : P와 V조작의 수행 중에 인터럽트 금지 ② 다중 프로세서 경우 : 인터럽트 금지를 할 수 가 없다. 따라서 임계 영역 문제에 대해서 소프트웨어 해결 방법을 사용해야 한다. - 임계 영역 구성 : P와 V, 프로시저로 구성 - 여기서 P와 V 연산으로는 바쁜 대기 제거 할 수 없으므로 응용 프로그램의 진입 점에서 CS 까지 바쁜 대기 제거한다. 결국 바쁜 대기의 시기를 이동시키는 것이다. ⇒ 짧은 시간 동안  P, V 조작의 CS 내에서만 제한 가능하다. ⇒ 결론 - CS은 거의 비어 있고, 바쁜 대기가 발생하지 않는 것처럼 보임 - 어떤 애플리케이션에서는 CS 아주 길거나 거의 항상 점유 상황이 발생한다. 이 경우에는 바쁜 대기가 비효율적이다.

49 상호 배제와 동기화 02 모니터 세마포어 상호배제 및 프로세스들 사이의 조정을 위한 유연성, 강력한 도구 제공
P(wait 동작), V(signal 동작) 연산 : 프로그램 전체에 널리 퍼짐 연산이 각자의 세마포어에 미치는 영향 파악 어려움 ⇒ 프로그램 작성 어려움 결론: 세마포어의 단점을 극복하기 위해서 모니터가 개발 되었음 모니터 -Brich Hansen(브린치 핸슨)과 Hoare(호)에 의해 개발 동기화를 자동적으로 제공하기 위해 개발 프로그래밍언어에서 제공되는 프로그래머-정의 연산자들의 집합으로 구성 세마포어와 비슷한 기능을 가짐 - 제어가 쉽다 모니터 형태의 표현 - 변수들을 선언하는 것으로 구성됨 변수들의 값 : 그 형태를 정의하는 것으로 그 형태의 연산들을 구현하는 프로시저나 함수들의 몸체를 정의하는 것과 유사 함 모니터 형태의 표현 여러 가지 프로세스들에 의하여 직접 사용 불가 모니터 안에서 정의된 프로시저는 모니터 안에서 정의된 변수들과 형식적인 매개 변수들만 접근 가능 모니터의 지역 변수들은 지역 프로시저에 의해서만 접근 가능함

50 상호 배제와 동기화 02 모니터 - 계속 모니터 구조 Type monitor-name = monitor
 모니터 구조 - 한 순간에 하나의 프로세스만 모니터 안에서 활동하도록 보장 - 따라서 프로그래머는 동기화 제약 조건을 명시적 코드 할 필요가 없음 - 하나 또는 그 이상의 프로시저와 초기화 과정, 그리고 지역 데이터로 구성된 소프트웨어 모듈 Type monitor-name = monitor   변수 선언   Procedure entry P1( ... );     begin ... end;   procedure entry P2 ( ... );     .   procedure entry Pn ( ... );   begin     코드 초기화   end 진입 큐 공유 데이터 연산동작 들 모니터 문법 구조 초기화 코드 [그림4-15]모니터의 일반 구조

51 상호 배제와 동기화 02 모니터 - 계속 var x, y: condition; 모니터는 여러 측면에서 임계 구역과 유사 하다.
CS : 어떤 동기화 기법을 모델링하는데 충분하지 못해 조건 CS으로 확장 되었음 모니터 : 모니터도 동기화를 위해 부수적인 기법 필요 – 기법은 조건 구조에 의하여 제공 됨 조건 형태의 변수 정의 조건 변수에서 호출될 수 있는 유일한 연산 : wait와 signal이다. 조건 변수 : 두 연산을 제공하는 추상적인 자료 형태로 볼 수 있음 var x, y: condition; 모니터 연산 동작 1 진입 큐 연산 동작 2 [그림4-26] 조건 변수들을 가진 모니터 연산 동작 n 조건 변수 조건 큐

52 상호 배제와 동기화 02 모니터 - 계속 연산 x.wait;  어떤 프로세스가 x.signal; 을 호출할 때까지 x.wait; 을 호출한  프로세스는 연기 즉 중단 의미 x-signal 연산  중단된 프로세스 중에서 1 개만 재개 만약 중단된 프로세스가 없으면, signal(wakeup) 연산은 효과가 없으며 x의 상태는 연산이 전혀 실행되지 않는 것과 같음 - 이것은 세마포어의 P(wait)와 비교하면 V(signal 연산)는 세마포어 상태에 영향을 줌 가정 : x-signal 연산이 프로세스 P에 의하여 호출될 때 조건 x와 연관된 중단된 프로세스 Q가 있다고 가정함. - 중단된 프로세스 Q가 실행을 다시 하도록 허용된다면, signal을 보낸 프로세스 P는 대기, 아니면 P와 Q는 모니터 안에서 동시 수행 두 프로세스들은 실행을 계속 할 경우 - 두 가지 가능성이 존재 함. - P는 Q가 모니터를 떠날 때 까지, 또는 다른 조건을 위해 대기한다. - Q는 P가 모니터를 떠날 때 까지, 또는 다른 조건을 위해 대기한다. ◈ 위의 가능성 적용의 합리적 근거 : P가 모니터 안에서 실행되기 때문에 후자 선택 : 합리적이다 그러나 프로세스 P를 계속하도록 허용  Q가 대기하기 위한 논리적인 조건은 Q가 재개될 때까지 유지 못할 수도 있음

53 상호 배제와 동기화 02 모니터 - 계속 - P는 Q가 모니터를 떠날 때 까지, 또는 다른 조건을 위해 대기한다.
- Q는 P가 모니터를 떠날 때 까지, 또는 다른 조건을 위해 대기한다. 전자는 Hoare 주장 이유 - 선행하는 조건들이 더욱 간단하고 세련된 증명 법칙들로 해석 함 병행 PASCAL 언어 - 두 가지 선택 사항 절충(Brich Hansen 선택) 적용 함 프로세스 P가 signal 연산 실행 - 모니터를 떠나고, Q가 재실행 함 - 이 기법은 프로세스가 한번 프로시저를 호출하는 동안 한번 이상의 signal 신호를 보낼 수 없기 때문에 Hoare의 기법만큼 강력하지는 못함.

54 상호 배제와 동기화 02 모니터 - 계속 세마포어를 이용한 모니터 기법 구현
각 모니터마다 세마포어 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); 모니터 안에서의 상호 배제보장. ⇒ 프로세스는 1로 초기화된 공통 세마포어 = mutex(mutual exclusion)

55 상호 배제와 동기화 02 모니터 - 계속 ■ 조건 변수 구현 각 조건 x에 대해 초기치 0으로 된 세마포어 x-sem과 정수변수 x-count 도입 1) 연산 x.wait 구현  2) 연산 x.signal 구현 x-count := x-count + 1;  if next-count > 0     then V(next)     else V(mutex);     P(x-sem);  x-count := x-count - 1;  if x-count > 0            then begin                next-count := next-count + 1;                V(x-sem);                P(next);                next-count := next-count - 1;     end; next-count = next에서 중단된 프로세스들의 수/ 모니터를 떠날 때 : V(mutex) 실행 위와 같이 구현하면 Hoare와 Brinch Hansen이 제안한 모니터들의 정의에 적용 할 수 있음

56 상호 배제와 동기화 02 모니터 - 계속 모니터 안에서 프로세스-재개 순서 - 프로세스들이 조건 x에서 중단되고 x.signal 연산이 어떤 프로세스에 의하여 실행된다면 중단된 프로세스들 중에서 어느 프로세스를 재개할 것인가? - 단순 해결 방법 : 선입 선처리 기법 이용하여 가장 오래 대기한 프로세스 먼저 재개 함  이 방법은 단순한 스케줄링 기법을 적용하기 힘든 환경도 많이 있음 – 조건 대기 구조 사용 조건 대기 구조 사용  x.wait(c);  → 조건 c가 만족될 때 까지 모니터를 호출한 프로세스의 수행을 일시 정지되므로 모니터를 다른 프로세스들이 사용할 수 있음. C : 정수로 된 식으로 wait 연산이 실행될 때 평가된다. C의 값 - 우선순위 번호, 중단된 프로세스의 이름과 함께 기억 된다. - x.signal이 실행될 때 가장 값이 작은 우선순위의 수를 가진 프로세스가 다음에 재실행된다.

57 상호 배제와 동기화 02 모니터 - 계속 단일 자원을 할당하는 모니터
◈ 위 기( x.wait(c); )법 - 경쟁하는 프로세스들 사이에서 단일 지원 할당을 제어 자원 할당 요구 - 각 프로세스의 자원 사용 예정 시간을 최대로 규정하여 모니터는 가장 짧은 시간을 할당하여 요청하는 프로세스에게 자원 할당 한다.  type resource-allocation = monitor       var busy: boolean;           x: condition;     procedure entry acquire (time: integer);        begin            if busy then x.wait(time);            busy := true;        end;  procedure entry release;        begin           busy := false;           x.signal;        end;  begin       busy := false;  end - Acquire(획득)/ release(방출) 단일 자원을 할당하는 모니터

58 프로세스간 통신 03 공유 메모리 기법과 메시지 전달 시스템 프로세스간 통신- 공유 메모리 기법과 메시지 전달 시스템
공유 메모리 - 프로세스들은 공유 변수 이용하여 정보 교환 [예] 유한 버퍼 기법(고정 크기를 가진 버퍼)- 버퍼가 비면 소비자는 기다리고, 버퍼 차면 : 생산자가 기다림 응용 프로그래머 : 통신 기능을 제공하는 책임 , 운영체제 : 단순한 공유 메모리만 제공 메시지 전달 시스템 - 프로세스들이 메시지들을 교환하도록 허용하며 통신을 제공하는 책임은 운영체제 자체에 있다. - 이 두 기법은 상호 배타적이 아닌 단일 운영체제 안에서 동시에 사용된다. [그림4-17]  프로세스간 통신

59 프로세스간 통신 03 메시지 전달 시스템 프로세스간 통신 기능 : 두 가지 연산자 형태로 제공
프로세스간 통신 기능 : 두 가지 연산자 형태로 제공   send(목적지, message) = 송신 receive(발생지, message) = 수신 통신 링크(link) 설정 방법 – 여기서는 물리적 구현이 아닌 논리적인 특성과 구현에 관한 것만. 어떻게 링크를 설정하는가? 두 개 이상의 프로세스에서도 연결이 가능한가? 통신 프로세스의 쌍(pair) 사이에 얼마나 많은 링크가 있는가? 링크의 용량은? (버퍼 공간)을 갖는가?   갖는다면 어느 정도인가? 메시지의 길이는 ? 링크가 가변-길이 또는 고정-길이 메시지들  수용여부? 링크는 단 방향, 양방향인가? 즉 P와 Q사이에 링크가 있다면, 메시지들이 한 방향 (예를 들어, P에서 Q로만 가능)만 가능한가, 양 방향 모두 가능한가? 링크의 논리적인 구현(send/receive 연산) 방법 직접 또는 간접 통신 대칭 또는 비대칭 통신 자동 또는 명시적 버퍼링 복사에 의한 전송 또는 참조에 의한 전송 고정-길이 또는 가변-길이 메시지

60 프로세스간 통신 03 명칭부착  직접 통신(주소 지정) 기법 - 메시지를 전송 또는 접수하기 원하는 각 프로세스는 통신의 접수자 또는 전송자의 이름 명시해야 한다. 이 기법에서 send/receive에 필요한 원시 연산자 정의는 아래와 같다. 간접 통신 직접 통신 우편함 포트 send(P, message) - 프로세스 P로 메시지를 보낸다. receive(Q, message) - 프로세스 Q에서 메시지를 받는다. [그림4-18] 직접 통신과 간접 통신 [특성]  - 통신을 원하는 각 프로세스의 쌍들 사이에 링크가 자동적으로 이루어짐.     프로세스들은 통신하기 위하여 서로 상대방의 신원(identity)을 알아야 함.  - 링크는 두 프로세스들 사이에 명시적으로 지정되어야 함  - 통신하는 프로세스들의 각 쌍 사이에는 정확하게 하나의 링크가 존재  - 링크는 양 방향이다.

61 프로세스간 통신 03 명칭부착 생산자 - 소비자 문제 type item = .....;
명칭부착  생산자 - 소비자 문제 type item = .....;   var nexp, nextc : item ;   parbegin     producer : repeat                  ...                nextp에서 한 항목 생산                  ...                send(cunsumer,nextp);              until false;  consumer: repeat                  receive(producer,nextc);                      ...                  nextc에서 한 항목 소비                       ...                 until false;   parend; - 유한 버퍼 기법의 경우  버퍼의 크기는 통신 링크의 용량과 동일 유한 버퍼 기법은 주소 지정에서 대칭성 가짐  송신자와 수신자가 통신 하기 위해 서로 이름 부여해야 한다. 변형 기법 : 주소 지정에서 비 대칭성 사용 할 수도 있음  송신자만 수신자 이름 지명이 필요 하고 수신자는 송신자의 이름 불필요함.  send와 receive 정의  - send(P. message)  메시지를 프로세스 P에 전송한다.   - receive(id, message)  프로세스로부터 메시지를 수신  id는 통신이 발생한  프로세스의 이름으로 설정된다.  ⇒ 대칭과 비대칭의 단점 : 프로세스 정의의 모듈성 제한함. 이름을 바꾸려면 모든 다른 프로세스를 검사, 옛 이름을 모두 참조해야 새로운 이름을 수정 할 수 있음.

62 프로세스간 통신 03 명칭부착 - 계속 ■ 간접 통신(주소지정) 기법
명칭부착 - 계속 ■ 간접 통신(주소지정) 기법 메시지들을 우편함(mailbox 또는 port)으로부터 송신 또는 수신함. 우편함 - 메시지들이 프로세스들에 의하여 넣어지는 객체로, 메시지들이 제거되는 객체 - 각 우편함은 고유한 이름(id)을 갖고 프로세스는 서로 다른  우편함에 의해서 다른 프로세스들과 통신할 수 있으며 두 프로세스들이 공유 우편함을 가질 때만 통신 이 기법은 송/수신자를 분리하여 메시지의 사용에 있어 유연성 제공함. 송신자 프로세스 수신자 프로세스 우편함 송신자 프로세스 수신자 프로세스 포트 [그림4-19] 간접 통신 기법

63 프로세스간 통신 03 명칭부착 - 계속 send, receive 연산자 정의
명칭부착 - 계속  send, receive 연산자 정의 - send(A, message) : 메시지를 우편함 A로 송신 - receive(A, message) : 메시지를 우편함 A로부터 수신 통신 링크 성질  - 링크는 한 쌍의 프로세스가 공유 우편함을 가질 때만 두 프로세스들 사이에 링크가  설정  - 링크는 두 개 이상의 프로세스들과 관련될 수 있음  - 통신하고 있는 각 프로세스들 사이에는 우편함에 관계되는 여러 개의 서로 다른 링크가  존재  - 링크는 단 방향일 수도 있고 양 방향일 수도 있음

64 프로세스간 통신 03 명칭부착 - 계속 프로세스 P₁,P₂,P₃모두 우편함 A를 공유 가정
명칭부착 - 계속 프로세스 P₁,P₂,P₃모두 우편함 A를 공유 가정   P₁: 메시지를 A에 송신, P₂, P₃ : 각각 A로부터 receive 실행 ■ 어느 프로세스가 P₁이 보낸 메시지 수신하는가? [해결]   - 하나의 링크는 최대로 두 개의 프로세스와 관련하도록 허용   - 한 프로세스는 한 순간에 최대로 하나의 receive 연산을 실행하도록 허용   - 어느 프로세스가 메시지를 수신할 것인지를 임의로 선택하도록 허용하는 방법 즉, P₂, P₃중 하나 선택(모두 선택은 안됨) – 시스템은 송신자에게 수신자를  알림 우편함이 한 프로세스에 의하여 소유(우편함은 프로세스나 시스템에 소속) 될 경우 우편함의 소유자(이 우편함으로 메시지 수신 가능한 것)와 우편함의 사용자(우편함에 메시지를 송신할 수 있는 것) 구분할 수 있다. 우편함 소유자 유지 - 우편함으로 보낸 메시지 수신에 대한 혼란이 없음 우편함을 소유하고 있는 프로세스 종료 - 우편함은 사라짐 이 우편함에 메시지를 송신하는 모든 프로세스에게 우편함이 없다는 사실을 알려주어야 (예외 처리를 통하여)

65 프로세스간 통신 03 명칭부착 - 계속 ■ 특정 우편함의 소유자와 사용자 지정 방법
명칭부착 - 계속 ■ 특정 우편함의 소유자와 사용자 지정 방법 프로세스가 우편함 형태(TYPE)의 변수들을 선언할 수 있게 허용 - 우편함을 선언한 프로세스는 우편함의 소유자이다. - 우편함의 이름을 알고 있는 모든 프로세스 - 우편함 사용 가능 ■ 공유 우편함 선언하고 소유자를 외부적으로 선언하는 방법   ■ 운영체제가 소유한 우편함은 스스로 존재 – 독립적인 것으로 특정 프로세스에 예속 안됨 ■ 운영체제는 한 프로세스가 다음을 허용하는 기법을 제공한다. -  새로운 우편함의 생성   -  우편함을 이용한 송신과 수신   -  우편함의 파괴

66 프로세스간 통신 03 명칭부착 - 계속 ▶ 새로운 우편함 생성 프로세스 - 우편함의 소유자
명칭부착 - 계속 ▶ 새로운 우편함 생성 프로세스 - 우편함의 소유자 - 초기 소유자 : 우편함을 통한 메시지 수신할 수 있는 유일한 프로세스이다. - 소유권과 수신 특권 : 시스템 호출을 통하여 다른 프로세스에게 인계 가능 따라서 우편함마다 복수의 수신자들을 갖게 된다. - 프로세스들은 프로세스 생성 기능을 통하여 우편함을 공유할 수 있다. [예] ◈ 프로세스 P가 우편함 A를 생성하고 프로세스 Q를 생성  P와 Q는 우편함 A 공유 우편함에 대한 접근권한을 가진 모든 프로세스들이 종료하기 때문에 우편함은 일정시간이 지나면, 다른 프로세스에 의하여 접근되지 못함 운영체제는 우편함용으로 사용된 공간 모두 회수해야 한다. 이 작업은 쓰레기 수집(Garbage Collection)과 같은 형식을 요구하게 된다.

67 프로세스간 통신 03 버퍼링 1) 용량 링크의 논리적 구현- 용량과 메시지 특성
링크 : 임시로 저장되는 메시지들의 수를(용량) 결정하는 크기를 가진다. - 이 특성은 링크에 부착된 메시지들의 큐라고 볼 수 있다. ■ 큐를 구현 할 수 있는 3가지 방식은 무용량, 제한된 용량, 무한 용량이 있다. 무 용량(zero copacity) 큐 : 최대 길이(0) - 자체 안에 대기하는 메시지들을 가질 수 없음   - 송신자는 수신자가 메시지를 수신할 때까지 대기 - 메시지 전송을 위하여 두 프로세스들은 동기화되어야 – 랑데부(Rendezvous;만나는 지점) 제한된 용량 큐 : 유한한 길이 n -> 최대로 n개의 메시지를 가질 수 있음 - 새로운 메시지가 전송될 때 큐가 차 있지 않다면 메시지는 큐에 놓이며 (메시지가 복사되든지 또는 메시지에 대한 포인터 유지) 송신자는 대기하지 않고 실행 계속. - 링크는 유한한 용량을 가지므로 링크가 꽉 차면 송신자는 큐 안에 공간이 생길 때 까지 연기(대기)되어야 한다.

68 프로세스간 통신 03 버퍼링 - 계속 무한 용량 큐 : 잠재적으로 무한한 길이 - 메시지들이 큐 안에서 대기할 수  있으므로 송신자는 결코 지연되지 않음 - 무 용량의 경우 : 비 버퍼링 메시지 시스템이라고 하며, 다른 경우 자동 버퍼링 제공 - 무 용량이 아닌 경우 : send 연산 종료 후 - 메시지의 목적지 도달여부를 프로세스가 알 수 없음, 연산에 있어서 이러한 정보가 매우 중요하면 송신자는 수신자의 메시지 수신 여부 확인(명시적 통신 필요) [예] 프로세스 P가 프로세스 Q로 메시지를 송신하고 그 메시지가 수신된 후에만 실행을 계속할 수 있다고 가정하면 프로세스 P 실행 순서 프로세스 Q 실행순서  send(Q, message);  receive(Q, message);  receive(P, message);  send(P, "acknowledgment"); 프로세스들은 비동기적으로 통신

69 프로세스간 통신 03 버퍼링 - 계속 2) 메시지 고정 크기 : 실제적인 구현은 매우 간단, 프로그래밍의 어려움이 있고
가변 크기 : 복잡한 실질적인 구현 필요, 프로그래밍은 간단해짐 형태화 된(typed) 메시지 : 기본적으로 간접 통신에만 적용, 우편함으로부터 송수신되는 메시지는 지정된 형태로 제한된다. 제어 정보 발신지 이름(ID) 메시지 형태 목적지 이름(ID) 메시지 길이 메시지 내용 메시지 헤더 메시지 본문 [그림4-20] 형태화 된 메시지 구성

70 프로세스간 통신 03 버퍼링 - 계속 3) 특별한 경우(2가지) ▶ 메시지 송신하는 프로세스 회신을 받을 때까지 지연된다.
▶ 메시지를 송신한 프로세스는 결코 지연되지 않는다 만약 송신 프로세스가 다른 메시지를 전송하기 전에 수신자가 메시지를 수신하지 않는다면  첫 번째 메시지는 유실된다.(‘사본을 송신’ 보다 ‘참조를 송신’하는 논리적 구현 기반 ) [장점] 대형 메시지들은 한번 이상 복사될 필요가 없다는 점 [단점] 프로그래밍이 더 어려워진다는 점이다. - 메시지들의 유실 방지, 송신자와 수신자가 메시지 버퍼를 동시 조작 방지  프로세스들은 명시적으로 동기화 필요 ▶ 메시지 송신하는 프로세스 회신을 받을 때까지 지연된다. Thoth(지혜와 정의의 신) 운영 체제에서 구현 - 메시지들의 크기가 고정 길이(8 워드) 수신 프로세스가 메시지를 수신, reply(P. message)에 의해  8워드의 회신(reply)을 보내올 때까지 메시지를 송신하는 프로세스 P는 보류 회신 메시지는  원래의 메시지 버퍼에 겹쳐 쓴다 send와 reply 차이 send : 송신 프로세스를 보류 reply : 송신 프로세스와 수신 프로세스가 그들의 실행 을 즉시 계속 할 수 있다.

71 프로세스간 통신 03 버퍼링 - 계속 동기화 통신 방식  원격 프로시저 호출(RPC;Remote Procedure Call) 시스템으로 확장 가능 RPC   단일 프로세서 시스템에서의 서브루틴이나 프로시저 호출이 송신자가 회신을 수신할 때까지 보류되는 메시지 시스템과 같이 동작하도록 실현하는 것 메시지 - 서브루틴 호출 회신 메시지  서브루틴이 연산한 값 포함 병행 프로세스들이 RPC를 이용하여 서브루틴처럼 서로 호출

72 프로세스간 통신 03 예외 조건 분산 환경 - 메시지 시스템이 유용 통신(그리고 처리)하는 동안에 오류 발생 확률 – 큼
통신(그리고 처리)하는 동안에 오류 발생 확률 – 큼 단일 기계 환경 : 메시지들이 공유 메모리에서 구현 고장 발생 : 전체 시스템 중지 분산 환경 : 메시지들이 통신선 이용 처리 한 사이트(링크)의 고장  전체 시스템의 고장으로 연결되지 않음 중앙 집중 또는 분산 시스템에서 문제 발생 오류의 회복 처리(예외 처리) 실행

73 프로세스간 통신 03 예외 조건 프로세스 종료 메시지가 처리되기 전에 송신자와 수신자 종료 수신되지 않은 메시지를 기다리거나 송신되지 않을 메시지를 기다리는 프로세스들 생성 수신자 프로세스 P는 종료된 프로세스 Q로 부터 메시지 기다림 조치 없으면 P는 보류(순환 대기가 없기 때문에 교착 상태 아님) - 시스템은 P를 종료하든가 Q가 종료한 사실을 P에게 통지  프로세스 P는 종료한 프로세스 Q에게 메시지 보냄 - 자동 버퍼링 기법 : 손해 없음 - P는 실행 계속 - Q가 처리한 메시지를 P가 알아야 한다면 - 프로그램 작성 버퍼가 없는 경우 - P는 영원히 보류 - 시스템은 P를 종료, Q가 종료한 사실을 P에게 통지

74 프로세스간 통신 03 예외 조건 메시지의 상실 P  Q로 가는 메시지 : 하드웨어나 통신 고장으로 상실 가능
운영체제는 이런 사건을 탐지하고 메시지 재전송 원하는 경우 송신 프로세스가 사건을 탐지하고 메시지 재전송 운영체제가 사건 탐지 - 메시지를 상실한 송신 프로세스에게  통지  메시지 상실 탐지 - 시간제한 사용 메시지 송신  메시지의 수신(회신) 메시지가 송신 회신 메시지 도착하는 시간 간격 규정 필요 - 회신 메시지가 도착하기 전에 이 시간 간격이 지나면  운영체제 (또는 프로세스)는 메시지 상실 가정하고 메시지 재전송 - 메시지가 상실되지 않고도 시간이 예정보다 늦어지는 경우  동일한 메시지를 여러 번 네트워크에 전송 가능 - 메시지들의 이러한 다양한 형태 구분 필요

75 프로세스간 통신 03 예외 조건 훼손 메시지 메시지 : 도중에 훼손 가능 [예]
   메시지 : 도중에 훼손 가능 [예] 통신 채널의 잡음으로 발생  상실된 메시지의 경우와 유사 운영체제가 원래 메시지를 재전송 이 사건의 프로세스에게 통지 오류 탐지 기법 : 패리티 기법 사용