병행 프로세스 병행처리는 프로세스들이 서로 관계없이 독립적으 로 수행 가능하고 다른 프로세스들과 협력을 필요로 하면서 기능 수행 3.1 개요 parbegin/parend 제어문 : 순차적인 수행으로부터 여러 개의 동시 수행으로 갈라짐을 지시하는 명령어와 여러 개의 동시.

Presentation on theme: "병행 프로세스 병행처리는 프로세스들이 서로 관계없이 독립적으 로 수행 가능하고 다른 프로세스들과 협력을 필요로 하면서 기능 수행 3.1 개요 parbegin/parend 제어문 : 순차적인 수행으로부터 여러 개의 동시 수행으로 갈라짐을 지시하는 명령어와 여러 개의 동시."— Presentation transcript:

1

2 병행 프로세스 병행처리는 프로세스들이 서로 관계없이 독립적으 로 수행 가능하고 다른 프로세스들과 협력을 필요로 하면서 기능 수행 3.1 개요 parbegin/parend 제어문 : 순차적인 수행으로부터 여러 개의 동시 수행으로 갈라짐을 지시하는 명령어와 여러 개의 동시 수행되는 것들이 하나로 모여서 순차적 수행으로 돌아가도록 지시하는 명령어 parbegin statement 1 ; statement 2 ; statement n ; parend

3 수업 필기 병행 프로세스의 비동기성으로 인해 발생하는 문제 점 소프트웨어적인 상호배제 기법 상호배제 동기화 결정적인 문제
통신문제 교착상태 소프트웨어적인 상호배제 기법 2개 프로세스 대상:Dekker 알고리즘, Peterson 알고리즘 n개 프로세스 대상:Dijstra 알고리즘, Knuth 알고리즘 & Mcguire 알고리즘, Lamport알고리즘

4 선형그래프 순환 선형 그래프 S2와 S3은 S1이 끝난 후 수행된다. S4는 S2가 끝난 후 수행 된다.
R(Si) = {a1, a2, …, am} (Si의 판독 집합) 문장 Si가 수행되는 도중에 Si에 의해 값이 참조되는 모든 변수들의 집합 W(Si) = {b1, b2, …, bn} (Si의 기록 집합) 문장 Si의 수행에 의해 값이 변하게 되는 모든 변수들의 집합 S2와 S3은 S1이 끝난 후 수행된다. S4는 S2가 끝난 후 수행 된다. S5와 S6은 S4가 끝난 후 수행된다. S7은 S5, S6, S3가 끝난 후 수행된다.

5 3.2 상호배제와 임계영역 상호배제란? 임계영역이란?
공용변수를 액세스하고 있는 하나의 프로세스 이외에는 다른 모든 프로세스들이 공용변수를 액세스하지 못하도록 제어하는 기법 병행 프로그래밍에 있어서 중요 임계영역이란? 어떤 프로세스가 공용데이터를 액세스하고 있을 때를 의미 보류되거나 무한루프에 빠지지 않도록 주의

6 상호배제 프리미티브 1 var pnumber : integer ; procedure pone ; begin while true do while pnumber = 2 do ; CSone ; pnumber := 2 ; end end ; procedure ptwo ; begin while pnumber = 1 do ; CStwo ; pnumber := 1 ; end end ; parbegin pone ; ptwo ; parend

7 상호배제 프리미티브 2 var p1, p2 : boolean ; procedure pone ; begin while true do while p2 do p1 := true ; CSone ; p1 := false ; end procedure ptwo ; begin while p1 do ; p2 := true ; CStwo ; p2 := palse; end p1 := false ; p2 := false ; parbegin pone ; ptwo ; parend

8 상호배제 프리미티브 3 var p1, p2 : boolean ; procedure pone ; begin while true do p1 := true ; while p2 do CSone ; p1 := false ; end procedure ptwo ; begin p2 := true ; while p1 do ; CStwo ; p2 := palse; end p1 := false ; p2 := false ; parbegin pone ; ptwo ; parend

9 상호배제 프리미티브 4 var p1, p2 : boolean ; procedure pone ; begin while true do p1 := true ; while p2 do p1 := false ; delay (random, fewcycles) ; end CSone ; procedure ptwo ; begin p2 := true ; while p1 do ; p2 := false ; delay (random, fewcycles) ; end CStwo ; p1 := false ; parbegin pone ; ptwo ; parend

10 상호배제 프리미티브 Dekker 알고리즘 var pavorP (first, second); p1, p2 ; boolean; procedure pone ; begin while true do p1 := true ; while p2 do if favorP = second then p1 := false ; while favorP = second do end CSone ; favorP := second; procedure ptwo ; begin p2 := true ; while p1 do ; if favorP = first then p2 := false ; while favorP = first do ; end CStwo ; favorP := first ; p1 := false ; favorP := first; parbegin pone ; ptwo ; parend

11 세마포어 상호배제의 해결은 복잡한 문제에서 일반화하기 어려움
이를 극복하기 위해 세마포어라 불리는 새로운 동기 도 구가 다익스트라에 의해 도입 세마포어란 P와 V, 그리고 세마포어 초기치를 설정해 주 는 오퍼레이션에 의해서만 액세스될 수 있는 통제된 변 수이다. 이진 세마포어는 0과 1의 두 가지 값만을 가질 수 있고, 산술 세마포어는 0과 양의 정수를 값으로 가질 수 있다. P(S) if(S > 0) then S := S-1 else (wait on S) V(S) if (1개 이상의 프로세스가 S에 대기 중) then (그중 1개의 프로세스만 진행) else S := S+1

12 3.3.1 사용(1) 세마포어는 n개의 프로세스의 임계영역 문제를 다 루는데 사용
n개의 프로세스는 1로 초기화된 공통 세마포어인 mutex를 공유 Pi repeat P(mutex) ; 임계영역 V(mutex) ; 나머지영역 until false ;

13 3.3.1 사용(2) 세마포어는 여러 가지 동기 문제를 해결하는데 사용
세마포어S에 대한 상호배제는 P(S)와 V(S)사이에 서 보장 세마포어와 그에 대한 오퍼레이션들은 소프트웨어 나 하드웨어에 의해 구현 운영체제의 핵에 속하여 구현 CPU를 한 프로세스로부터 다른 프로세스에게로 넘 겨줌 P1 S1; V(synch); P2 p(synch); S2;

14 3.3.2 구현 세마포어의 가장 큰 단점은 바쁜대기를 요구하는 것
이는 다른 프로세스가 생산적으로 사용할 수 있는 CPU시간을 낭비하는 것 바쁜 대기의 필요성을 극복하기 위하여 세마포어의 P, V 조작을 수정 type semaphore = record value : integer ; L : list of process; end

15 세마포어 조작 P(S) : S.value := S.value -1 ; add this process to S.L ;
if (S.value < 0) then begin add this process to S.L ; block ; end; V(S) : S.value := S.value + 1 ; if (S.value <= 0) remove a process P from S.L ; wakeup(P);

16 3.4 요약정리 (1) 임계구역 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 자원(영역) 임계 구역에는 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납한 후에만 다른 프로세스가 자원이나 데이터를 사용할 수 있음 상호배제 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법 여러 프로세스가 동시에 공유 자원을 사용하려 할 때 각 프로세스가 번갈아가며 공유 자원을 사용하도록 하는 것으로 임계 구역을 유지하는 기법

17 3.4 요약정리 (2) 세마포어 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법
E.J.Dijkstra가 제안하였으며, P와 V라는 2개의 연산에 의해서 동기화를 유지시키고, 상호배제의 원리를 보장함 S는 P와 V 연산으로만 접근 가능한 세마포어 변수로, 공유 자원의 개수를 나타내며 0과 1 혹은 0과 양의 값을 가질 수 있음 P 연산 : 자원을 사용하려는 프로세스들의 진입 여부를 자원의 개수(S)를 통해 결정하는 것으로, wait 동작이라 함 V 연산 : 대기 중인 프로세스를 깨우는 신호(Wake Up)로서, signal 동작이라 함

18 3.4 요약정리 (3) 모니터 모니터란 여러 프로세스 사이에 공유 데이터와 이 공유 데이터에 접근하는 여러 프로시저이다
동기화를 구현하기 위한 특수 프로그램 기법으로 특정 공유 자원을 프로세스에게 할당하는데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성됨 자료 추상화와 정보 은폐 개념을 기초로 하며 공유 자원을 할당하기 위한 병행성 구조로 이루어져 있음 모니터 내의 공유 자원을 사용하려면 프로세스는 반드시 모니터의 진입부를 호출해야 함 외부의 프로시저는 직접 액세스할 수 없으며, 모니터의 경계에서 상호 배제가 시행됨 한순간에 하나의 프로세스만 진입하여 자원을 사용할 수 있음