4 병행 프로세스와 상호배제.

Presentation on theme: "4 병행 프로세스와 상호배제."— Presentation transcript:

1 4 병행 프로세스와 상호배제

2 학습목표 내용 병행성의 원리를 이해한다. 병행 프로세스 수행과 관련해 상호배제를 해결하는 방안을 알아본다. 병행 프로세스
상호배제와 동기화

3 1. 병행 프로세스 병행 프로세스 개념 병행 프로세스의 과제 프로세스 여러 개가 동시에 실행되는 것. 비동기적 병행 프로세스
독립적으로 작업을 수행, 다른 프로세스와 협력하며 특정 기능 수행. 프로세스 간 교신이 필요. 비동기적 병행 프로세스 프로세스 간 교신 시 동기화되어야 하는 프로세스. 상호 작용 제한된 자원을 공유하기 위함이며, 상호 작용하는 프로세스는 순서에 맞게 실행되도록 동기화되어야 함. 병행 프로세스의 과제 병행성 다수의 프로세서를 이용하여 작업을 수행하며, 다중 프로세싱 시스템, 분산 처리 환경, 다 중 프로그래밍 운영체제에서 매우 중요함. 시스템의 신뢰도 향상과 처리 속도 개선을 통한 처리 능력 증대에 매우 중요함. 다중 프로세싱 시스템 - 각 프로세서가 갖는 오버헤드를 감소시키면서 프로세서의 유효성을 증대시킴. - 여러 개의 명령어를 세분화하여 동시에 처리하기 위해 프로세서들을 연결, 상호작용을 제어.

4 1. 병행 프로세스 다중 프로세싱 시스템의 성공적인 구현을 위한 해결 문제
공유 자원을 상호 배타적으로 사용해야 함. - 프린터, 통신망 등은 한 순간에 한 프로세스만 사용해야 함. 병행 프로세서들 사이는 협력 또는 동기화되어야 함. - 상호 배제도 동기화의 형태임. 두 프로세스 사이에 데이터 교환을 위한 통신이 이루어져야 함. 프로세서는 결정성(Determinacy)을 확보해야 함. - 동시에 수행되는 다른 프로세스들의 실행 속도와 관계 없이 항상 일정한 실행 결과 보장. 교착 상태를 해결하고 병행 프로세스들의 병렬 처리 능력 극대화. 실행 검증 문제 해결 병행 프로세스 수행 과정에서 발생하는 상호 배제를 보장해야 함. - 어떤 프로세스가 작업을 실행 중일 때 나머지 프로세스들이 그 작업에 관련된 작업을 수행할 수 없음. 다중 프로세싱 시스템은 프로세스 동기화 알고리즘이 필요. 프로세서들이 모든 입출력 장치와 메모리를 참조 가능. 동시에 동일한 자원에 접근할 경우 충돌이 발생하므로 이를 해결.

5 1. 병행 프로세스 선행 그래프 프로세스는 프로세스 집합과 이들의 선행 제약(Precedence Constraint)의 두 가지 요소로 정의. 선행 제약 프로세스가 순서대로 다른 상태로 옮겨감. 프로세스 ‘P1, P2, …, Pn’가 있을 때, 선행 순서는 Pi < Pj 로 표시, 상태는 Pi에서 Pj 로 옮겨감. 따라서 Pi < Pj 이고 Pj < Pk이면 Pi < Pk 두 프로세스 간에 선행 관계가 없으면 이들은 독립적이라 병행 실행이 가능함. 선행 그래프(Precedence Graph) 제약을 규칙적(논리적)으로 표현한 것. 각 문장에 대응되는 노드가 비순환 그래프를 이룸. - 노드 Si에서 노드 Sj로 가는 연걸선(Edge)은 문장 Si가 완전히 수행된 다음에 문자 Sj가 수행됨을 의미함.

6 1. 병행 프로세스 산술 연산 수행 알고리즘 (알고리즘 4-1)
병행 수행을 하기 위해 프로세서 안의 기능 단위(가산기 등)를 여러 개 두거나 프로세서를 여러 개 사용해야 함. 프로세서를 여러 개 사용 시 여러 문장이 동시에 수행되어 총 수행시간을 줄일 수 있음. [그림4-1] [알고리즘4-1]에 대한 선행 그래프 알고리즘 4-1 간단한 산술 연산을 수행하는 알고리즘 a := x + y → S1 b := z → S2 c := a – b → S3 w := c → S4 c := a – b; - a와 b가 값을 할당받기 전에 수행하면 안 된다. w := c + 1; - c 값을 계산하기 전에 수행할 수 없다. a := x + y, b := z + 1; - 서로 독립적이므로 동시에 수행할 수 없다.

7 1. 병행 프로세스 선행 그래프(그림 4-2) S2와 S3은 S1이 끝난 후에 수행된다. S4는 S2가 끝난 후에 수행된다.
S7은 S5, S6, S3이 끝난 후에만 수행된다. S3은 S2, S4, S5, S6과 병행하여 수행될 수 있다. 선행 그래프 (그림 4-3) S3은 S2가 끝난 후에만 수행할 수 있다. S2는 S3이 끝난 후에만 수행할 수 있다. - 이 제약은 동시에 만족할 수 없음. - 실행 우선 순위를 정의할 수 없어 모순이 발생. [그림4-2] 선행 그래프 [그림4-3] 순환 선행 그래프

8 1. 병행 프로세스 언어적 표현과 병행 문장 프로그램의 여러 문장의 선행 관계 명시를 위해 두 가지 언어구조 제시.
fork와 join 구조 선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하나, 2차원이므로 프로그래밍 언어에서 사용하기에 어려움. 콘웨이(Conway, 1963년)와 데니스(Dennis, 1966년), 호른(Van Horn, 1966년)이 소개. 병행을 최초로 언어적 표현으로 명시. fork L 명령 - 프로그램에서 두 개의 병행 수행을 만듦. - 단일 연산을 두 개의 독립적인 연산으로 분할. 1. 레이블이 L인 문장에서 수행을 시작. 2. fork 명령 바로 다음 문장에서 시작 join 명령 - 여러 개의 병행 연산을 하나로 결합하는 방법 제공하며, 단위적으로 수행해야 함. - 합칠 연산의 수를 명시하는 매개변수를 가짐. 1. 연산들은 서로 다른 속도로 진행되므로 둘 중 하나가 join을 먼저 수행하게 됨. 2. join 연산 수행 후 다른 연산 수행. 3. 세 개의 연산을 합칠 경우 두 개의 연산이 끝나고 join 연산을 수행한 다음 이들의 결과와 나머지 연산을 join 함.

9 1. 병행 프로세스 fork와 join 구조 설명 알고리즘(알고리즘 4-2) count를 매개변수로 가지는 join 명령 예
‘fork L’문장이 수행되면 새로운 연산이 S3에서 실행. 새로운 연산은 S2에서 시작되는 연산과 병행하여 수행됨. [그림4-4] fork 구조의 선행 그래프 알고리즘 4-2 fork와 join 구조를 설명하는 알고리즘 S1; fork L; S2 … L : S3 count를 매개변수로 가지는 join 명령 예 count는 0이 아닌 정수값, quit는 count의 계산 수행을 종료시키는 명령. - join할 연산이 2개라면 매개변수 count의 초기값은 2. … count := count - 1; if count = 0 then quit;

10 1. 병행 프로세스 임의의 순서로 순차 수행되는 것과 동일한 알고리즘(알고리즘 4-3)
두 개의 join 문장의 병행 수행은 두 문장을 임의의 순서로 순차 수행하는 것과 동일함. 알고리즘 4-3 임의의 순서로 순차 수행되는 것과 동일한 알고리즘 Count := 2; fork L1; … … S1; Go to L2; 07 L1 : S2; 08 L2 : join count; S3; [그림4-5] join 구조의 선행 그래프

11 1. 병행 프로세스 산술식에 대한 선행 그래프와 fork-join 구조 (그림 4-6)
[알고리즘 4-1] 중 두 개의 read 문장을 병행 수행하기 위한 fork-join 명령. [그림4-6] 산술식에 대한 선행 그래프와 fork-join 구조 count := 2; fork L1; a := x + y; go to L2; L1 : b := z + 1; L2 : join count; c := a – b; w := c + 1;

12 1. 병행 프로세스 [그림 4-2]의 선행 그래프에 대한 fork, join 명령을 이용한 알고리즘
[그림 4-2]에는 유일한 join 노드 S7이 있으며, 유입 정도(In-degree)는 3. 따라서 join 문장이 하나 필요하며 join에 대한 count의 초기값은 3. 알고리즘 4-4 [그림 4-2]의 선행 그래프에 대해 fork, join 명령을 이용한 알고리즘 S1; count := 3; fork L1; S2; S4; fork L2; S5; go to L3; 09 L2 : S6; go to L3; 11 L1 : S3; 12 L3 : join count; S7;

13 1. 병행 프로세스 병행 문장 프로세스 하나가 여러 가닥의 병렬 프로세스로 퍼졌다가 다시 한 가닥으로 뭉쳐지는 것을 나타내는 고급언어 구조. - 대표적인 예 : 다익스트라(Dijkstra, 1965년)가 제안한 ‘parbegin/parend’ 일반적인 형태는 아래와 같음. parbegin S1; S2; ……; Sn; parend; 각 Si는 단일 문장(명령어), parbegin과 parend 사이의 모든 문장은 병행 수행 가능. 보다 효과적인 병행 문장은 S0과 Sn+1 문장을 추가하여 아래와 같이 정의 가능. - Sn+1 은 모든 S(i=1, 2,…, n)가 끝난 후에만 실행 가능. - 모든 문장이 ‘S1; S2; …;Sn;’과 같이 실행 후 Sn+1 결과가 된다면 [그림 4-8]로 표현. S0; parbegin S1; S2; ……; Sn; parend; Sn+1; [그림4-8] 복잡한 구조의 선행 그래프 [그림4-7] 병행문장의 일반 형태와 선행 그래프

14 1. 병행 프로세스 [알고리즘 4-1]의 처음 두 문장을 동시에 수행
parbegin/parend 구조 이용, 아래 왼쪽과 같이 표기. 알고리즘 4-5 [그림 4-2]의 선행 그래프에 대한 알고리즘 S1; 02 parbegin S3; begin S3; S4; parbegin S5; S6; parend; end; 12 parend; 13 S7; parbegin a := x + y; b := z + 1; parend; c := a – b; w := c + 1;

15 2. 상호배제와 동기화 상호배제와 동기화 병행 프로세스 간 상호작용 상호배제 (Mutual Exclusion)
특정 공유 자원을 한 순간에 한 개의 프로세스만 사용할 수 있을 때, 프로세스 하나가 공유 데이터에 접근하는 동안 다른 프로세스가 해당 데이터를 접근할 수 없게 하는 것. 프로세스 간 동기화 공유자원을 동시에 사용하지 못하게 실행을 제어하는 기법. 순차적으로 재사용 가능한 자원을 공유하기 위해 상호작용하는 프로세스 사이에서 나타남. 병행 프로세스 간 상호작용 프로세스는 아래 세 가지 형태로 상호작용 함. 프로세스들이 서로 인식하지 못하는 경쟁관계 유지. - 다중 프로그래밍 환경에서 운영체제는 자원에 대한 경쟁을 고려, 동일한 디스크나 프린터로의 접근 조절. 프로세스들은 입출력 버스를 비롯한 개체를 공유하는 단계에서 간접적으로 서로의 관계를 인식함. - 프로세스들은 공동 개체를 공유하는데 따른 협력이 필요함. 프로세스들은 서로를 인식하고 프로세스끼리 통신할 수 있는 기본 함수를 가짐. - 프로세스들이 협력관계일 때, 프로세스 간 직접 통신이 가능, 병행해서 함께 동작할 수 있음.

16 2. 상호배제와 동기화 생산자/소비자 프로세스 생산자/소비자, 판독자/기록자(입력기/출력기) 문제
여러 프로세스가 공통 작업 수행을 위해 서로 협동하고, 병행 처리되는 대표적인 예. 상호배제와 동기화가 필요하며 세마포어를 이용해 구현. 운영체제에서 비동기적으로 수행하는 모델로 생산자 프로세스는 소비자 프로세스가 소비하는 정보를 생산. [그림4-9] 생산자/소비자 프로세스 관계

17 2. 상호배제와 동기화 생산자와 소비자 프로세서들을 병행 실행하기 위해 공유 버퍼가 필요함.
생산자의 데이터 생산 속도와 소비자의 데이터 소비 속도는 서로 독립적이므로 버퍼가 필 요함. - 생산자와 소비자는 같은 버퍼에 접근하므로 동시에 사용할 수 없음. 생산자가 이미 채워진 버퍼에 더 채우거나, 소비자가 빈 버퍼에서 데이터를 꺼낼 때 문제 발생. 속도가 다른 생산자와 소비자가 데이터를 일시 저장할 수 있는 버퍼 사용 시 버퍼는 [그림 4-10]의 세 가지 상태 중 하나. [그림4-10] 전형적인 버퍼의 세 가지 상태

18 2. 상호배제와 동기화 프로세스 간 통신의 예 무한 버퍼 생산자/소비자 문제
생산자/소비자 관계에서 한 프로세스가 정보를 생산하면 다른 프로세스는 그 정보를 소비 함. 버퍼가 비었거나 꽉 차 있을 때 버퍼에 접근하는 것을 막기 위해 생산자와 소비자가 동기화 되어 있어야 함. [그림4-11] 유한 버퍼 시나리오 무한 버퍼 생산자/소비자 문제 버퍼의 크기에 제한을 두지 않으며 항상 버퍼에 빈자리가 존재함.

19 2. 상호배제와 동기화 유한 버퍼 생산자/소비자 문제
크기가 고정된 버퍼를 사용, 버퍼가 비었을 시 소비자가 대기, 버퍼가 가득 차면 생산자가 대기함. 공유 버퍼의 저장소를 두 개의 논리적 포인터 in과 out을 사용한 순환 배열로 해결 가능. - in과 out은 0으로 초기화. - 변수 in은 비어있는 다음 버퍼를 가리킴. - 변수 out은 채워진 버퍼의 맨 처음을 가리킴. - 소비자는 버퍼에서 데이터를 읽기 전 생산자가 앞서 가는 지, 즉 in > out 인지 확인함. [그림 4-12] 유한 버퍼 생산자/소비자 - 버퍼 a의 구조이며 회색 부분은 점유된 지역. var n; type item = … .; var buffer : arrary[0, •, n-1] of item; in, out : 0, ..., n-1; nextp, nextc : item; in := 0; out := 0; [그림4-12] 유한 버퍼 생산자/소비자

20 2. 상호배제와 동기화 유한 버퍼를 공유하는 생산자/소비자 프로세스 간 변형 프로그램 (알고리즘4-6)
버퍼가 비어있으면 ‘in = out’, 버퍼가 꽉 차면 ‘(in+1) mod n = out’. no-op : 아무 일도 하지 않는 경우. while 조건 do no-op : 조건이 거짓이 될 때까지 반복적으로 검사. 생산자 프로세스 : 생산될 새로운 항목이 기억되는 지역변수 nextp를 가짐. 소비자 프로세스 : 소비될 항목이 기억되는 지역변수 nextc를 가짐. 알고리즘 4-6 유한 버퍼를 공유하는 생산자/소비자 프로세스 간의 변형 프로그램 01 parbegin 생산자 : begin repeat … nextp에서 항목을 하나 생산한다. … while (in + 1) mod n = out do no-op; buffer[in] := nextp; in := (in + 1) mod n; until false; end; 알고리즘 4-6 유한 버퍼를 공유하는 생산자/소비자 프로세스 간의 변형 프로그램 소비자 : begin repeat while in = out do skip; nextc := buffer[out]; out := (out + 1) mod n; … nextc에서 항목을 하나 소비한다. … until false; end; parend;

21 2. 상호배제와 동기화 유한 버퍼를 공유하는 생산자/소비자 프로세스 간 변형 프로그램 (알고리즘4-6)
이 알고리즘에서 동시에 채울 수 있는 버퍼는 최대 n-1개. 이를 해결하기 위해 정수 변수 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이 됨.

22 2. 상호배제와 동기화 유한 버퍼를 공유하는 생산자/소비자 프로세스 간 변형 프로그램 (알고리즘4-6) counter 값 확인
* counter := counter + 1을 기계어로 다음과 같이 작성한다. register1 := counter; register1 := register1 + 1; counter := register1; * counter := counter - 1을 기계어로 다음과 같이 작성한다. register2 := counter; register2 := register2 – 1; counter := register2; 국부 레지스터 : register1, register2 각각 프로세서 스케줄링 루틴에 의해 저장되었다가 복귀됨.

23 2. 상호배제와 동기화 유한 버퍼를 공유하는 생산자/소비자 프로세스 간 변형 프로그램 (알고리즘4-6) 실행 예
counter 값이 일관성 없이 나타나는 이유는 두 프로세서가 변수 counter를 동시에 조작하기 때문. T1 : 생산자가 register1 := counter를 수행 (register1 = 5) T2 : 생산자가 register1 := counter1 + 1을 수행 (register2 = 6) T3 : 소비자가 register2 := counter를 수행 (register2 = 5) T4 : 소비자가 register2 := register2 – 1을 수행 (register2 = 4) T5 : 생산자가 counter := register1을 수행 (counter = 6) T6 : 소비자가 counter := register2를 수행 (counter = 4)

24 2. 상호배제와 동기화 경쟁 상태(Race Condition) 동기화 실행 방법
공유 데이터에 최종적으로 남는 데이터의 결과를 보장할 수 없는 상황을 의미. 여러 프로세스가 공유 데이터를 동시에(병행적으로) 접근(읽기나 쓰기)할 때 공유 데이터 에 대한 접근 순서에 따라 실행 결과가 달라지는 상황. 장치나 시스템이 둘 이상의 연산을 동시에 수행하려 할 때, 어느 프로세서가 제일 마지막에 수행된 후 결과를 저장했느냐에 따라 발생하는 오류. 접근 순서화가 필요. 이를 방지하기 위해 병행 프로세서들은 반드시 동기화되어 실행되어야 함. 동기화 실행 방법 임계 영역 - 공유 변수를 어느 한 순간에 한 프로세스만 조작할 수 있도록 함. 상호 배제 - 예에서 counter를 조작하는 부분을 임계영역으로 설정, 상호 배제 함.

25 2. 상호배제와 동기화 임계 영역(Critical Section)
둘 이상의 프로세스가 공유할 수 없는 자원을 임계자원이라 하며, 프로그램에서 이를 이용하는 부분. 공유 메모리가 참조되는 프로그램의 부분(데이터나 데이터 구조)으로 다수의 프로세스가 접근 가능한 영역이면서 한 순간에 하나의 프로세스만 사용할 수 있는 영역(공유 자원의 독 점을 보장하는 코드 영역)을 의미. 프로세스들이 공유 데이터를 통해 협력 시, 한 프로세스가 임계영역에 들어가면 다른 모든 프로세스는 임계영역으로의 진입 금지. 다중 처리 시스템과 단일 처리 시스템(시분할)환경에 적용되는 하나의 실행단위, 실행 구간을 의미. - 임계영역 내에서 빠른 속도로 작업을 수행, 한 프로세스가 오랫동안 머무르면 안됨. - 프로세스가 무한 루프 등에 빠지지 않도록 관리. [그림4-13] 임계 영역

26 2. 상호배제와 동기화 진입 상호 배제 프로세스 하나가 임계 영역에 있으면 다른 프로세스가 임계 영역에 들어가지 못하게 하는 것. 임계 영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야 함. - 프로세스가 접근하지 않은 임계 영역은 잠금 상태. - 프로세스는 임계 영역에서 작업을 수행하기 전에 키를 얻어 임계 영역의 잠금 상태를 해제해야 함. - 프로세스가 키를 반환할 때까지 다른 모든 프로세스에 대해 잠김 상태 유지. 임계 영역을 떠나는 프로세스는 출구 상호배제를 수행함으로써 다른 프로세스가 임계 영역 에 들어갈 수 있도록 함. [그림4-14] 임계 영역을 이용한 상호 배제

27 2. 상호배제와 동기화 프로세스들이 서로 협력하여 자원을 사용할 수 있도록 프로토콜을 설계하여 임계영역 문제를 해결 가능.
프로세스들이 서로 협력하여 자원을 사용할 수 있도록 프로토콜을 설계하여 임계영역 문제를 해결 가능. 진입영역(진입코드) - 각 프로세스는 접근하려는 자원의 임계영역에 들어갈 수 있는지 여부를 미리 요청해야 하며, 이를 코드로 구현한 부분. 출구영역 - 임계영역에서 수행을 마치고 나갈 프로세스를 선택. 잔류영역 - 진입영역과 출구영역을 제외한 나머지 영역으로, 임계영역을 마치고 나와 수행함. [그림4-15] 병행 프로세스에서 영역 구분

28 2. 상호배제와 동기화 임계영역을 해결하기 위해 아래 세 가지 요구를 만족시켜야 함. 상호 배제 진행 제한된 대기
- 프로세스 Pi가 임계영역에서 수행 중일 때 다른 프로세스는 임계영역에서 수행할 수 없다. 진행 - 임계영역에서 수행하는 프로세스가 없고 여러 개의 프로세스가 임계영역으로 들어가려고 하면 프로세스 선정 알고리즘에 따라 다음 임계영역에서 수행할 대상을 선정한다. - 다음 임계영역으로 들어갈 프로세스 선택은 무한정 미룰 수 없다. 제한된 대기 - 한 프로세스가 임계영역을 요청한 후 요청이 수락되기까지 다른 프로세스가 임계영역에 진입할 수 있는 회수를 제한해야 한다.

29 2. 상호배제와 동기화 소프트웨어적인 임계영역 문제 해결
단일 프로세서 또는 메모리를 공유하는 다중 처리 환경의 프로세서가 존재. 알고리즘 1 (알고리즘 4-7) 두 개의 프로세스(P1, P2)에 대한 상호배제를 보장. 현재 parbegin/parend 때문에 P1과 P2가 동시에 수행되며, 임계영역의 진입여부를 확인하기 위해 while 문 구현. 구현 방식 - 한 개의 공유변수(processnumber)를 사용하여 해결. - 두 개의 프로세스(P1, P2)가 교대로 실행됨. 임계영역 진입 : processnumber 값에 따라 진입 여부(P1 = processnumber ← 1)가 결정. - 임계영역 진입을 위해 반드시 상대 프로세스의 processnumber 값 확인이 필요함. 상호배제가 보장되지만 반드시 P1이 먼저 시작해야 함. - P2가 준비되어도 P1이 먼저 들어갔다 나와야 하므로 대기 시간이 길어질 수 있음. 프로세스는 반드시 한 번씩 번갈아 들어갔다 나와야 함. - 프로세스 수행 속도가 느려질 수는 있으나 시스템은 교착상태에 빠지지 않음. 공유변수 processnumber를 한 개 사용하였으므로, 두 프로세스 중 하나가 중지되면 다른 프로세스도 중지됨.

30 2. 상호배제와 동기화 알고리즘 4-7 상호배제 단계 1 01 program versionone; // 첫 번째 버전
var processnumber : integer; // 공유 변수 procedure P1; // 프로세스 P1의 임계영역 진입 절차 begin while true do // 진입영역에서 P1의 진입 활동 begin while processnumber = 2 do; // P2의 임계영역 진입 여부 확인 criticalsectionone; // 임계영역 processnumber : = 2; // P2에게 진입 순서 양보 otherstuffone // P1의 잔류영역 수행 end; end; procedure P2; // 프로세스 P2의 임계영역 진입 절차 begin while true do // 진입영역에서 P2의 진입 활동 begin while processnumber = 1 do; // P1의 임계영역 진입여부 확인 criticalsectiontwo; // 임계영역 processnumber := 1; // P1에게 진입 순서 양보 otherstufftwo // P2의 잔류영역 수행

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

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

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

34 2. 상호배제와 동기화 알고리즘 3 (p.167 참조) 알고리즘 4 (p.169 참조)
[알고리즘 4-9]에서는 while 문을 검사하기 전에 while 문 검사를 시작함을 플래그로 알려 주어 상호배제를 해결. 두 프로세스가 교착상태에 빠질 가능성이 있음. - 두 개의 프로세스가 while 문 검사를 하기 전에 동시에 플러그를 바꾸면 서로의 플래그 상태를 확인한 두 프로세스는 영원히 while~do 구조를 수행. 알고리즘 4 (p.169 참조) [알고리즘 4-10]에서는 순환하는 각 프로세스가 플래그를 얼마 동안만 거짓으로 하여 [알 고리즘 4-9]의 문제 해결. 이 방법도 무한 연기 문제가 발생함. - 각 프로세스의 상대적인 속도를 예측 불가능함. 가능한 순서를 고려하여 무한 연기 문제 해결. - 각 프로세스가 신호를 참으로 설정하고 while 문 검사를 한 후 while 루프를 수행하여 플래그를 거짓으로 수행. - 이후 다시 참으로 설정하는 작업을 반복하여 검사를 계속 수행.

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

36 2. 상호배제와 동기화 알고리즘 4-11 상호배제를 구현한 데커 알고리즘
P1_enter := true // P1이 임계영역 재진입 시도 end; criticalsectionone; // 임계영역 fprocess := second; // P2에게 진입 순서 양보 P1_enter := false; // P1의 임계영역 사용 완료 지정 otherstuffone // P1의 잔류영역 수행 end; end; procedure P2; begin while true do begin P2_enter := true; while P1_enter do; if fprocess = first then begin P2_enter := false; while fprocess = first do; P2_enter := true; end;

37 2. 상호배제와 동기화 알고리즘 4-11 상호배제를 구현한 데커 알고리즘 34 criticalsectiontwo;
fprocess := first; P2_enter := false; otherstufftwo end; end; begin P1_enter := false; P2_enter := false; fprocess := first; parbegin P1; P2; parend; end.

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

39 2. 상호배제와 동기화 알고리즘 4-12 testandest을 이용한 상호배제 알고리즘
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; procedure process2; var notenter2 : boolean; begin while true do begin notenter2 := true;

40 2. 상호배제와 동기화 알고리즘 4-12 testandest을 이용한 상호배제 알고리즘 22 while notenter2 do
testandset(notenter2, active); criticalsectiontwo; active := false; otherstufftwo; end; end; begin active := false; parbegin process1; process2; parend; end.

41 [그림4-16] 세마포어의 예인 열차의 진행 가능 여부 표현
2. 상호배제와 동기화 세마포어 (Semaphore) 음이 아닌 정수값을 갖는 플래그 변수. 다익스트라(Dijkstra)가 상호배제의 문제를 극복하기 위해 제안함. 세마포어의 유명한 예 ‘열차의 진행 가능 여부’를 나타내는 차단기. - 차단기 올라감 : 정지/대기 (운영체제는 자원이 없어 기다리는 경우) - 차단기 내려감 : 진행 (프로세스가 해당 자원을 사용할 수 있는 자유 상태) [그림4-16] 세마포어의 예인 열차의 진행 가능 여부 표현

42 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와 V의 동작은 세마포어를 인자로 명명한 임의의 프로세스가 요청한 시스템을 호출함으로써 운영체제에 의해 실행됨. 프로세스 제어를 용이하게 하며 P 연산을 요구하는 프로세서는 그 동작이 수행 가능한 상 태가 될 때까지 대기해야 함. P와 V 연산은 세마포어 변수 S를 수정하는데 사용되나, 표시한 프로세스가 변수 S를 수정 하면 다른 프로세스를 수정할 수 있음.

43 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;

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

45 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 신호를 보내서 준비 큐에 추가

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

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

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

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

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

51 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);

52 2. 상호배제와 동기화 각 조건 x에 대해 초기값이 0인 세마포어 x-sem, 정수 변수 x-count를 도입.
x.wait 연산은 아래와 같이 구현함. 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; x.signal 연산은 아래와 같이 구현함. If x-count > 0 then begin next-count := next-count + 1; V(x-sem); P(next); next-count := next-count -1; end;

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

54 2. 상호배제와 동기화 단일 자원을 할당하는 모니터(알고리즘 4-13) 알고리즘 4-13 단일 자원을 할당하는 모니터
type resource-allocation = monitor var busy: boolean; x: condition; 04 procedure entry acquire(time: integer); begin if busy then x.wait(time); busy := true; end; 10 procedure entry release; begin busy := false; x.signal; end; 16 begin busy := false; end.