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