3장 운영체제 2C200512116 김주성.

Presentation on theme: "3장 운영체제 2C200512116 김주성."— Presentation transcript:

1 3장 운영체제 2C 김주성

2 병행 프로세스 정의 병행 프로세스 개요 병행 프로세스란 여러 프로세스들이 동시에 수행상태에 있는 것을 말하며 독립적 또는 다른 프로세스와 협력하면서 기능을 수행한다. 비동기성(Asynchronous)란 프로세스간의 상호협력 하는 것 병행 프로세스의 비동기성으로 인해 발생하는 문제점 상호배제(Mutual Exclusion) 동기화(synchronization) 결정적인(Determinacy) 문제 통신(Communication) 문제 교착상태(Dead Lock)

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

4 선형 그래프 S1 S2 S3 S4 S6 S5 S7

5 상호배제(Mutual Exclusion)
상호배제란 여러 프로세스가 하나의 공유 데이터를 액세스 하면서 작업이 수행될 때 한 프로세스가 그 데이터를 액세스 할 때 다른 프로세스는 그 데이터를 액세스하지 못하도록 하는 기법. 임계 영역(Critical Section) 임계 영역이란 공유메모리가 참조하는 프로그램의 부분을 말한다. 즉, 어떤 프로세스가 공유 데이터를 액세스 할 때 그 프로세스는 임계영역 내에 있다고 말한다. 상호배제 기법 소프트 웨어 적인 상호배제 기법 2개 프로세스 대상: Dekker 알고리즘, Peterson 알고리즘 n개 프로세스 대상: Dijstra 알고리즘, Knuth 알고리즘 & Mcguire 알고리즘, Lamport 알고리즘

6 순환 반복대기(Busy Waiting) 기법
하드웨어적인 상호배제 기법 Test and Set 명령어 Swap 명령어 순환 반복대기(Busy Waiting) 기법 세마포어(Semaphore) Eventcount/Sequencer(시크 벤저) 상호배제 기법(Dekker의 알고리즘) 2개의 프로세스가 모두 자신의 flag[]값을 true로 설정하고 임계영역에 진입하는 경우 그 당시의 turn 값에 따라 진입순서를 결정한다.(P0=turn ←1;, P1=turn←0;) 그리고 한 프로세서가 임계 영역에 진입하기 위해서는 반드시 상대방 프로세스의 flag[]값이false 인지 확인 요

7 상호배제 기법(Peterson의 알고리즘)
Dekker 알고리즘을 보완하여 1981년에 피터슨에 의해 제안 프로세스 P0는 turn의 값을 1로, P1은 turn 값을 0으로 설정 한다. 그 뒤에 while 루프에 진입하여 상대 프로세스가 진입을 시도하는지 여부를 검사하여, 이 때 2개의 프로세스가 모두 진입을 시도한다면 flag[0]와 flag[1]의 값이 모두 true이면 true 값에 따라 turn이 가리키는 순서의 프로세스가 임계영역에 진입 한다. 즉, turn의 값을 먼저 설정한 프로세서가 임계영역에 진입.

8 상호배제 프리미티브 1 프로세스가 상호배제를 수행하는 것을 해결 하려한 첫 번째 예.
parbegin/parend 때문에 pone과 ptwo가 동시에 수행됨. 두 프로세스들은 무한순환을 하는데 계속해서 임계영역을 들어갔다 나왔다 하는 일을 반복함. while loop이 상호배제로 들어가는 것으로 구현되었는데, pnumbe r라는 변수가 자기 프로세스의 번호와 같아 지기 까지 계속 loop을 돌며 기다림. 상호배제 탈출은 pnumber라는 변수를 상대방 프로세스의 번호로치환시키게 끔 구현되었음. pone이 while do문을 수행하게 되면 pnumber의 초기치가 1이므로 pone이 임계영역에 진입한다. ptwo는 pnumber가 1인 것을 확인하고는 while do 순환을 계속한다. ptwo가 CPU에 돌아갈 때는 pnumber가 2로 되는 것을 기다리며 loop을 반복하게 된다. 따라서 ptwo는 임계영역에 들어가지 못하고 상호배제는 보장됨.

9 상호배제 프리미티브 2 2개의 변수 사용 예. p1변수는 pone이 임계영역에 있을 때 참(True)이 되고, p2변수는 ptwo가 임계영역에 있을 때 참(True)이 됨. p2가 참(True)일 동안 pone은 busy wait를 하게 됨. 언젠가는 ptwo가 임계영역을 벗어나게 되고 그때 p2를 거짓(False)으로 한다. 그때에 pone은 p1을 참(True)으로 하고 임계영역으로 들어간다. p1이 참(True)일 동안 ptwo는 임계영역에 들어갈 수 없음 . p1과 p2의 초기치가 모두 거짓(false)으로 되어있음. 따라서 2개의 프로세스가 동시에 임계영역에 들어가게 되어 상호배제가 보장되지 않음.

10 다익스트라 (Dijkstra) Flag[] 변수 값.
이 알고리즘의 임계영역 진입시도 1단계에서는해당 프로세스 flag[] 값을 want-in으로 설정하고turn의 값이 i와 같을 때 제2단계로 진입한다. 2단계에서 이와 같이 제 1 단계를 통과한 프로세스 들의 수를 파악하여 그 수가 2 이상이면 임계영역 진입시도를 처음부터 다시 한다. 즉, 자신외도 제 1단계를 통과한 프로세서들이 있으면 임계영역 진입시도를 처음부터 다시 시작한다.

11 다익스트라 (Dijkstra) Flag[] 변수 값.
이 알고리즘의 임계영역 진입시도 1단계에서는해당 프로세스 flag[] 값을 want-in으로 설정하고turn의 값이 i와 같을 때 제2단계로 진입한다. 2단계에서 이와 같이 제 1 단계를 통과한 프로세스 들의 수를 파악하여 그 수가 2 이상이면 임계영역 진입시도를 처음부터 다시 한다. 즉, 자신외도 제 1단계를 통과한 프로세서들이 있으면 임계영역 진입시도를 처음부터 다시 시작한다.

12 하드 웨어 적인 상호배제 기법 Test and set 알고리즘의 방법
Dekker, Peterson, Dijstra 알고리즘은 소프트웨어적인 상호배제 해결방법으로 실행시간이 길며, 프리미티브(Primitives)의 실행 중 블록 될 가능성이 있는 문제점이 있다. 이를 해결하기 위해 하드웨어적인 상호배제 해결 방법으로 IBM에서 제안한 Test and set 명령어가 있다. Test and set 알고리즘의 방법 먼저 변수를 읽고 그것의 값을 저장 영역(Save Area)에 기억시킨 후 그 변수에 다른 값을 Set시키는 방법이다. 임계구역 진입, 해제 전후에 다른 프로세스가 개입할 수 없게 만든다. 즉 아예 인터럽트를 걸지 못하게 한다. 다른 프로세스 개입 불가.

13 모니터 Dekker, Perterson, Dijkstra, Test and set 명령어, 세마포어 등에 의한 기법들은 저 수준의 기법들로 너무 기초적이고, 복잡한 병행성문제에 대한 해답을 표현하기 어렵다. 또한 코딩이 어려워질 수 있고, 디버깅이나 정확성 증명에 어려움 단점이 있다. 이러한 단점을 보완한 것이 수준 병 행성 제어 구조인 모니터 가 제안 되었다. 모니터란 여러 프로세스 사이에 공유 데이터와 이 공유 데이터에 접근하는 여러 프로시져(Procedure)이다. 즉, 임계영역 코드들의 집합으로 정의 한다. 프로시져(Procedure)란 자주 실행해야 하는 업무 흐름을 이 문법에 미리 작성하여 데이터베이스 내에 저장해 두었다가 필요할 때마다 호출하여 실행할 수 있는 PL/SQL 블록. PL/SQL 은 APPLICATION LOGIC 을 추가하여 SQL 을 확장한 ORACLE의 절차 적인 언어.

14 프로세스 동기화 Critical Section(임계 영역)에 대해서 프로세스들이 어떠한 순서로 작업을 수행하더라도 올바른 결과를 기대할 수 있도록 하는 데이터의 정확성(correctness)과 데이터의 일관성(consistency)을 보장. 메시지 송신 측 프로세스와 수신 측 프로세스간에 교환될 수 있는 정보의 집합으로써 둘 or 그 이상의 프로세스 간에 전송될 데이터 또는 실행명령 등을 의미.