3장 – 병행 프로세스 205012002 2A 김정문.

Presentation on theme: "3장 – 병행 프로세스 205012002 2A 김정문."— Presentation transcript:

1 3장 – 병행 프로세스 2A 김정문

2 병행 프로세스 프로세스들이 동시에 수행하는 것. 서로 관련 없이 독립적 수행하거나 다른 프로세스 와 상호 작용하기도 한다.
제한된 자원 공유하기 위해 상호 작용 필요하다. 프로세스간의 동기화 필요하다. 비동기성 - 프로세스간의 상호협력 하는 것

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

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

5 상호배제 임계 구역(공유 자원)을 어느 시점에서 단지 한 개 의 프로세스만이 사용할 수 있도록 하며, 다른 프로 세스가 현재 사용중인 임계 구역(공유 자원)에 대하 여 접근하려고 할때 이를 금지하는 행위를 상호배 제라고 한다.   Pdata pdata+1; pdata 주기억장치 프로세스 P1 프로세스 P2 프로세스 P1이 공유 데이터 pdata를 액세스 하면 P2는 액세스 하지 못하게 해야 한다.

6 임계영역 (Critical Section)
동시에 둘 이상의 스레드가 동시에 접근해서는 안되 는 공유 자원(자료 구조 또는 장치)을 접근하는 코드의 일부를 말한다. 임계 영역은 주로 지정된 시간이 지난 후 사라진다. 그래서 어떤 스레드(작업 또는 프로세스)가 임계 구역에 들어가려면 지정된 시간을 기다려야 한다. 세마포어와 같이, 배타적인 사용을 보장하기 위해서는 임계영역의 입장과 퇴장에는 어떤 동기화 동작이 필요하다. 공유메모리가 참조하는 프로그램의 부분을 말한다. 즉, 어떤 프로세스가 공유 데이터를 액세스 할 때 그 프로세스는 임계 영역 내에 있다고 말한다.

7 상호배제 기법 소프트 웨어적인 상호배제 기법 프로그래밍 언어 또는 운영체제의 특별한 지원 없이, 프로세스 간 협력을 통해 직접 상호배제를 보장하는 것이다. - 2개 프로세스 대상: Dekker 알고리즘-, Peterson 알고리즘 - n개 프로세스 대상: Dijstra 알고리즘, Knuth 알고리즘 & Mcguire 알고리즘, Lamport 알고리즘 하드웨어적인 상호배제 기법 특별히 설계된 기계어 명령어를 이용하는 방법이다. - Test and Set 명령어 - Swap 명령어 순환 반복대기(Busy Waiting) 기법 - 세마포어(Semaphore) - Eventcount/Sequencer(시크벤저)

8 데커[Dekker] 알고리즘 이 알고리즘은 두 프로세스가 동시에 임계 영역에 들어 가려고 할 때 하나만 들어가도록 한다. 한 프로세스가 이미 임계 영역에 있다면, 다른 프로세스는 전 프로세스 가 끝나기를 기다려야 한다. f0과 f1 두 개의 플래그(각각 임계영역에 들어갈 의향, 두 프로세스 사이의 우선권을 나타낸다.)를 사용하여 구현 할 수 있다.

9 N개 프로세스 상호 배제 기법 데이크스트라(Dijkstra) 단점 : 무기한 연기의 가능성이 있다. 쿤즈(Knuth)
단점 : 무기한 연기의 가능성을 제거 하였지만 지 연 시간이 매우 크다 아이젠버그(Eisenberg) 유한 시간내의 시도 후 임계영역 진입을 보장 한다. 람포트(Lamport) 분산 시스템 환경을 위한 상호 배제 기법이다.

10 세마포어 에츠허르 데이크스트라가 고안한, 두 개의 원자적 함수로 조작되는 정수 변수로서, 멀티프로그 래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용된다. 이는 철학자들의 만찬 문 제의 고전적인 해법이지만 모든 교착 상태를 해결하지는 못한다. P는 임계 구역에 들어가기 전에 수행되고, V는 임계 구역에서 나올 때 수행된다. 이 때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다. 다시 말해, 한 프로세스(또는 스레드)에서 세마 포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다. 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법. S는 P와 V 연산으로만 접근 가능한 세마포어 변수로, 공유 자원의 개수를 나타내며 0과 1 혹은 0 과 양의 값을 가질 수 있다. P 연산 : 자원을 사용하려는 프로세스들의 진입 여부를 자원의 개수(S)를 통해 결정하는 것으로, wait 동작이라 한다. V 연산 : 대기 중인 프로세스를 깨우는 신호(Wake Up)로서, signal 동작이라 함. 계수 세마포어(counting semaphore)에서는 초기값은 가능한 자원의 수로 정해지며, 세마포어 값의 범위는 정해져 있지 않다. 이진 세마포어(binary semaphore)에서는 세마포어 값으로 0 또는 1을 가진다. 계수 세마포어보다 간단히 구현할 수 있으며, Test and Set 등 하드웨어가 지원하는 기능을 이용하여 구현하기도 한다. 또한, 이진 세마포어를 이용하여 계수 세마포어를 구현할 수도 있다.

11 세마포어(2) 약점> P함수와 V함수의 동작은 독립적이기 때문에 잘못 사용하는 경우, 문제가 발생한다.
P - 임계 구역 - P : 현재 프로세스가 임계 구역에서 빠져나갈 수 없 게 된다. 또한 다른 프로세스들은 임계 구역에 들어갈 수 없으므로 교착 상태(Deadlock)가 발생한다. V - 임계 구역 - P : 2개 이상의 프로세스가 동시에 임계구역에 들어 갈 수 있으므로 상호 배제(Mutual Exclusion)를 보장할 수 없게 된다. 고급 언어에서 동기화를 제공해야 한다.

12 세마포어(3) 작동원리는 매우 간단하다. 차단을 원하는 자원에대해서 세마포어를 생성하면 해 당자원을 가리키는 세마포어 값이 할당된다. 이 세마포어 값에는 현재 세마포어를 적용하고 있는 자원에 접근할수 있는 프로세스의 숫자를 나타낸다. 이 값이 0이면 이 자원에 접근할수 있는 프로세스의 숫자가 0이라는 뜻이며, 자원), 0 보다 큰 정수면 해당 정수의 크기만큼의 프로세스가 자원에 접근할수 있다라는 뜻 이 된다. 그러므로 우리는 접근제어를 해야하는 자원에 접근하기 전에 세마포어 값 을 검사해서 값이 0이면 자원을 사용할수 있을때까지 기다리고, 0보다 더크면(1이라 고 가정하자) 자원에 접근해서 세마포어 값을 1 감소 시켜서, 세마포어 값을 0으로 만들어서, 다른 프로세스가 자원에 접근할수 없도록 하고, 자원의 사용이 끝나면 세 마포어 값을 다시 1증가시켜서 다른 프로세스가 자원을 사용할수 있도록 만들어주 면 된다. 만약 세마포어 값을 검사했는데 세마포어 값이 0이라면 사용할수 있게 될때까지 (1 이 될때까지) 기다리면 (block) 될것이다.

13 모니터 여러 프로세스 사이에 공유 데이터와 이 공유 데이터에 접근하는 여러 프로시져. 임계영역 코드들의 집합으로 정의.
여러 프로세스 사이에 공유 데이터와 이 공유 데이터에 접근하는 여러 프로시져. 임계영역 코드들의 집합으로 정의. 모니터에 프로시져가 몇 개 있는지에 따라 그 개수만큼 모니터 진 입 큐 (entry queue)가 존재한다. 모니터 내의 프로시져를 호출하는 프로세스는 해당 프로시져에 대 한 진입 큐를 통해 모니터 내로 진입하며 그 과정에서 이미 모니터 내에 진입해 있는 프로세스가 존재하는 경우 진입 큐에 대기한다. 즉, 모니터 내에는 항상 하나 이하의 프로세스만이 진입하도록 상 호 배제 메커니즘이 자동으로 보장한다.