운영체제 강의노트 교재 : 운영체제 ( 개정판 ) 출판사 : 한빛미디어 (2010 년 11 월발행 ) 저자 : 구현회 소프트웨어학과원성현교수 1
4 장 병행프로세스와 상호배제 소프트웨어학과원성현교수 2
1. 병행프로세스 병행프로세스의과제 병행성 동시에 2 개이상의프로세스가실행되는성질 다중프로세싱시스템, 분산처리시스템에서주로발생 다중프로세싱시스템은프로세서의효율성을증대시킴 시스템성능을향상시키지만해결해야할과제가있음 공유자원을상호배타적으로사용할수있어야함 프린터, 네트웍등은한순간에한프로세스만사용할수있어야함 병행프로세스간에동기화가이루어져야함 동시에수행되는다른프로세스의속도와관계없이항상일정한결과가보장되는결정성 (determinacy) 이보장되어야함 교착상태를해결할수있어야함 상호배제, 즉어떤프로세스가실행중일때나머지프로세스들이그작업과관련된작업을수행할수없도록보장할수있어야함 소프트웨어학과원성현교수 3
1. 병행프로세스 선행그래프 선행그래프 (precedence graph) 란? 두프로세스간에존재하는선행관계를규칙적으로표현한것 간단한알고리즘예 S1 S2 S1 과 S2 는동시에실행될수있다. a = x + y; (S1) b = z + 1; (S2) c = a b; (S3) w = c + 1; (S4) S3 S3 는 S1 과 S2 가끝나기전에는실행될수없다. S4 S4 는 S3 이끝나기전에는실행될수없다. 소프트웨어학과원성현교수 4
1. 병행프로세스 언어적표현과병행문장 fork 단일연산을 2 개의독립적인연산으로분할 간단한알고리즘예 S1; fork L; S2;... L : S3; S1 fork fork 에의해 S2 와 S3 이별도의지시가있을때까지동시에실행 S2 S3 소프트웨어학과원성현교수 5
1. 병행프로세스 join 2 개의병행연산을하나로결합하는방법을제공 join 할명령의개수 간단한알고리즘예 a = x + y; (S1) b = z + 1; (S2) c = a b; (S3) w = c + 1; (S4) count = 2; fork L1; a = x + y; go to L2; L1 : b = z + 1; L2 : join count; c = a b; w = c + 1; S1(a=x+y) fork join S3(c=a-b) S2(b=z+1) S4(w=c+1) 소프트웨어학과원성현교수 6
1. 병행프로세스 S1 S5 S2 S4 S6 S3 S7 S1; count = 3; fork L1; S2; S4; fork L2; S5; go to L3; L2 : S6; L1 : S3; L3 : join count; S7; 간단한알고리즘예 소프트웨어학과원성현교수 7
1. 병행프로세스 병행문장 프로세스하나가여러가닥의병렬프로세스로퍼졌다가다시하나로뭉치게하는고급언어구조 par 과 parend 를사용 S0 S1 S2 Sn S0; par S1; S2; ; Sn; par Sn+1; Sn+1 병행문장의일반형태와선형그래프 소프트웨어학과원성현교수 8
1. 병행프로세스 S0 S1 S3 S2 S5 S4 S6 S0; par S1; S2; par S3; S4; par S5; S6; par S7; S7 복잡한구조의선형그래프 소프트웨어학과원성현교수 9
병행프로세스간상호작용 자원들의공유가능성 컴퓨터자원중에는 2 개이상의프로세스가동시에사용접근하는것이가능한경우 ( 메모리, 디스크등 ) 도있지만, 불가능한경우 (CPU, 프린터등 ) 도있음 상호배제 (mutual exclusion) 란? 특정공유자원을한순간에하나의프로세스만사용할수있을때어떤프로세스가공유자원을접근하는동안다른프로세스는해당공유자원을접근할수없도록하는제어 상호배제의필요성 프로세스간의충돌이없는읽기연산과같은경우는공유데이터에동시에접근할수있지만그래도여러프로세스가사용하는경우순서대로읽기연산을수행하게하는것이바람직함 동기화 공유자원을동시에사용하지못하도록실행을제어하는기법 정확한동기화를통해프로세스간의충돌을회피해야함 소프트웨어학과원성현교수 10
생산자 / 소비자프로세스 자원을생산하는프로세스와소비하는프로세스 프린터드라이버가프린트할문자를생산하면프린터는인쇄하기위해문자를소비 생산자의생산속도와소비자의소비속도가다르므로생산자와소비자가공유하는버퍼가필요함 생산자는생산된데이터를버퍼에저장하고, 소비자는버퍼에가서소비할데이터를가져와서소비함 버퍼가꽉찼을때계속생산하려하고, 버퍼가비었을때계속소비하려고할때문제가발생할수있음 그러므로버퍼의상황을정확하게파악하여각프로세스가버퍼의상태를인지하게하는것이중요함 버퍼가비었거나, 꽉찼을때버퍼에접근하는것을막기위하여동기화가필요함 동기화는원형큐를활용하여 front 와 rear 의제어를통해큐의상태를파악하는것이가장좋은방법임 소프트웨어학과원성현교수 11
유한버퍼를공유하는생산자 / 소비자프로세스간의변형프로그램 생산자 소비자 par repeat while (in+1) mod n = out do no-op; buffer[in] := nextp; in := (in + 1) mod n; until false; repeat while in = out do skip; nextc := buffer[out]; out := (out + 1) mod n; until false; par out a[2] a[3] a[1] a[4] a[n] a[5] 소프트웨어학과원성현교수 12 in in : 비어있는첫버퍼 out : 채워진첫버퍼 in = out : 버퍼가빔 (in + 1) mod n = out : 버퍼가꽉참
임계영역 용어 임계자원 프린터와같이프로세스가공유할수없는자원 임계영역 (critical section) 임계자원을사용하는상태 임계영역에있다 프로세스가공통변수를읽거나테이블을갱신하거나파일을수정하는등공유데이터에접근하고있는상태 한프로세스가임계영역에있다면다른프로세스는임계영역으로들어갈수없음 임계영역에있던프로세스가임계영역을나오게되면다른프로세스가임계영역으로들어갈수있도록임계영역점유를해제해야함 임계영역에는오래있으면안되고, 무한루푸에빠지게되는것을절대적으로경계해야함 소프트웨어학과원성현교수 13
프로세스 A 가임계영역에진입 프로세스 A 가임계영역에서나옴 프로세스 A 프로세스 B 가임계영역진입시도 프로세스 B 가임계영역에진입 프로세스 B 가임계영역에서나옴 프로세스 B T1 T2 보류 T3 T4 time flow 소프트웨어학과원성현교수 14
소프트웨어적인임계영역문제해결 알고리즘 1( 교재 164 쪽알고리즘 4-7 참조 ) procedure P1; while true do while processnumber = 2 do; criticalsectionone; processnumber := 2; otherstuffone procedure P2; while true do while processnumber = 1 do; criticalsectiontwo; processnumber := 1; otherstufftwo processnumber := 1; par P1; P2; par end. 교착상태에빠지지않음 반드시 P1 부터시작해야하기때문에 P2 가먼저준비되는경우는대기하게됨 공유변수 (processnumber) 를 1 개만사용했기때문에두프로세스중 1 개가중단되면다른프로세스도중단 소프트웨어학과원성현교수 15
알고리즘 2( 교재 166 쪽알고리즘 4-8 참조 ) procedure P1; while true do while P2_inside do; P1_inside := true; criticalsectionone; P1_inside := false; otherstuffone procedure P2; while true do while P1_inside do; P2_inside := true; criticalsectiontwo; P2_inside := false; otherstufftwo P1_inside := false; P2_inside := false; par P1; P2; par end. P1_inside 와 P2_inside 가모두참이면두프로세스가동시에임계영역에들어가게되어상호배제가보장되지않음 소프트웨어학과원성현교수 16
알고리즘 3( 교재 167 쪽알고리즘 4-9 참조 ) procedure P1; while true do P1_enter := true; while P2_enter do; criticalsectionone; P1_enter := false; otherstuffone procedure P2; while true do P2_enter := true; while P1_enter do; criticalsectiontwo; P2_enter := false; otherstufftwo P1_enter := false; P2_enter := false; par P1; P2; par end. while 문전에 P1_enter := true 와 P2_enter := true 를두어임계영역에들어가기위한조건을충족시킴 P1_enter 와 P2_enter 모두가동시에 true 로값을바꾸게되면 P1 과 P2 모두의 while 문은무한루프에빠지게되어교착상태에이르게됨 소프트웨어학과원성현교수 17
알고리즘 4( 교재 169 쪽알고리즘 4-10 참조 ) procedure P1; while true do P1_enter := true; while P2_enter do; P1_enter := false; delay(random, fewcycles); P1_enter := true criticalsectionone; P1_enter := false; otherstuffone P1 과 P2 둘모두임계영역에들어가고자한다면둘중의하나가일정시간동안임계영역진입을보류 잘못하면무한대기발생 procedure P2; while true do P2_enter := true; while P1_enter do; P2_enter := false; delay(random, fewcycles); P2_enter := true criticalsectiontwo; P2_enter := false; otherstufftwo P1_enter := false; P2_enter := false; par P1; P2; par end. 소프트웨어학과원성현교수 18
Dekker 알고리즘 ( 교재 170 쪽알고리즘 4-11 참조 ) procedure P1; while true do P1_enter := true; while P2_enter do; if fprocess = second then P1_enter := false; while fprocess = second do; P1_enter := true criticalsectionone; fprocess := second; P1_enter := false; otherstuffone procedure P2; while true do P2_enter := true; while P1_enter do; if fprocess = first then P2_enter := false; while fprocess = first do; P2_enter := true criticalsectiontwo; fprocess := first; P2_enter := false; otherstufftwo P1_enter := false; P2_enter := false; fprocess := first; par P1; P2; par end. 소프트웨어학과원성현교수 19
세마포어 세마포어 (semaphore) 란? 네덜란드의천재컴퓨터학자 Dijkstra 가제시한상호배제해결방안 세마포어변수 S 를두고연산 P 와 V 를수행 연산 P( 시도 (try) 를뜻하는네덜란드말 Proberen) 는프로세스가임계영역에진입하기위한연산으로세마포어변수 S 를 1 감소시킴 연산 V( 증가 (increment) 를뜻하는네덜란드말 Verhogen) 는프로세스가임계영역에서나오기위한연산으로세마포어변수 S 를 1 증가시킴 P(S) : S := S 1; if S < 0 then 프로세스대기상태프로세스번호를 wait 큐에추가 else 임계영역수행 V(S) : S := S + 1; if S <= 0 then wait 큐에서프로세스를제거하고제거한프로세스에 wakeup 신호를보내서 ready 큐에추가 소프트웨어학과원성현교수 20