병행 프로세스(Parallel Process)

Presentation on theme: "병행 프로세스(Parallel Process)"— Presentation transcript:

1 병행 프로세스(Parallel Process)
2-C 박상수

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

3 병행 프로세스 개요 <선형 그래프>
각문장에 대응되는 노드들이 유향 비순환 그래프를 이루는 것으로 노드 si에서 sj로 가는 에지(Edge)는 문장 si가 완전히 수행된 다음에 문장sj가 수행됨을 의미한다. <순환 선형 그래프> R (Si)={a1, a2, ···, am} (Si의 판독 집합) 문장 Si가 수행되는 도중에 Si에 의해 값이 참조되는 모든 변수들의 집합 W (Si)={b1, b2, ···, bn} (Si의 기록 집합) 문장 Si의 수행에 의해 값이 변하게 되는 모든 변수들의 집합 s3 s1 s2 s4 s6 s7 s5 s1 s2 s3

4 병행 프로세스 비동기성으로 인한 문제점 상호배제 - 프로세스 2개가 동시에 임계 지역에 진입하지 못하도록 하는 것. 동기화
- 임계 영역에서 프로세스가  작업을 수행하더라도 올바른 결과를 기대할 수 있도록 하는 데이터의 정확성과 데이터의 일관성을  보장하는 것. 결정적인 문제 - 여러 프로세서가 실행순서와 관계 없이 언제나 일정한 결과를 얻어야 한다. 통신문제 -상호배제와 동기화 문제 해결을 위해 데이터 교환 방법이 필요. 일반적으로 메시지 교환 방법 사용. 교착상태 -무한정 기다리는 상태를 말 한다.

5 상호배제와 기법 상호배제란 여러 프로세스가 하나의 공유 데이터를 액세스 하면서 작업이 수행될 때 한 프로세스가 그 데이터를 액세스 할 때 다른 프로세스는 그 데이터를 액세스하지 못하도록 하는 기법. ○ 소프트 웨어적인 상호배제 기법 - 2개 프로세스 대상: Dekker 알고리즘, Peterson 알고리즘 - n개 프로세스 대상: Dijstra 알고리즘, Knuth 알고리즘 & Mcguire 알고리즘, Lamport 알고리즘 ○ 하드웨어적인 상호배제 기법 - Test and Set 명령어 - Swap 명령어 ○ 순환 반복대기(Busy Waiting) 기법 - 세마포어(Semaphore) - Eventcount/Sequencer(시크벤저)

6 임계영역(critical section)
임계 영역이란 공유메모리가 참조하는 프로그램의 부분을 말한다. 어떤 프로세스가 공유 데이터를 액세스 할 때 그 프로세스는 임계영역 내에 있다고 말한다. 프로세스 P1 프로세스 P2 . pdata . Pdata <= Pdata + 1; Pdata <= Pdata + 1; X 주기억장치

7 임계영역(critical section)
상호배제 기법 dekker p0 p1 2개의 프로세스가 모두 자신의 flag[]값을 true로 설정 임계영역에 진입하는 경우 그 당시의 turn 값에 따라 진입 순서를 결정한다. (P0=turn ←1;, P1=turn←0;) 그리고 한 프로세서가 임계 영역에 진입하기 위해서는 반드시 상대방 프로세스의 flag[]값이 false 인지 확인 Repeat … Repeat … Frag[0]<-true; While (frag[1]) do If (turn =1) then Begin Frag[0]<-false; While (turn=1)do Endwhile; Flag[0]<-true; End; Turn<-1; Flag[0]<-false; Frag[1]<-true; While (frag[0]) do If (turn =0) then Begin Frag[1]<-false; While (turn=0)do Endwhile; Flag[1]<-true; End; Turn<-0; Flag[1]<-false; Flag[0] Flag[1] turn 임계영역(critical section) … Until (false); … Until (false);

8 임계영역(critical section)
상호배제 기법 peterson p0 p1 프로세스 P0는 turn의 값을 1로, P1은 t urn 값을 0으로 설정 한다. 그 뒤에 while 루프에 진입하여 상대 프로세스가 진입을 시도하는지 여부를 검사하여 이 때 2개의 프로세스가 모두 진입을 시도한다면 flag[0]와 flag[1]의 값이 모두 true이면 true 값에 따라 turn이 가리키는 순서의 프로세스가 임계영역에 진입 한다. turn의 값을 먼저 설정한 프로세서가 임계영역에 진입. Repeat … Repeat … Flag[0] Flag[1] Frag[0]<-true; turn =1; While(flag[1]and turn=1)do Endwhile; Flag[0]<-false; Frag[1]<-true; turn =0; While(flag[0]and turn=0)do Endwhile; Flag[1]<-false; turn 임계영역(critical section) … Until (false); … Until (false);

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

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

11 프로세스간 통신방법 -공유메모리 변수 시스템 송수신 프로세스가 공동으로 접근 가능한 메모리 공간을 할당 하며 공유변수를 이용하여 정보를 교환 한다 (운영체제는 메모리만 제공하고 통신기능은 응용프로그래머에게 주어진다.) - 메시지 시스템 프로세스들이 메시지를 이용하여 정보를 교환하며, 통신 기능을 제공하는 책임이 운영체제에게 주어 진다 (큐(Queue)의 기본원리를 이용하여 송수신 프로세스가 정보를 메시지 큐를 통해 전달.) 통신방법 사용 예) 중앙 집중식 시스템 공유변수를 이용하여 통신하며, 세마포오어 같은 메커니즘을 이용하여 동기화 및 상호배제의 문제를 해결 분산 처리 시스템 통신 네트워크를 통한 메시지 전달을 이용하여 동기화를 할 수 있다.