3장 병행 프로세스 2A200512097박훈
1.병행 프로세스 개요 병행 프로세스란 ? 여러 프로세스들이 동시에 수행상태에 있는 것을 말함 다른 프로세스와 협력하여 기능 수행 parbegin/parend 제어문 순차적인 수행에서 동시수행으로 나누어 수행하다가 다시 하나로 모여 순차적 수행으로 돌아가도록 지시하는 명령어 parbegin statement 1; statement 2; statement n; parend
병행성의 개념 단일, 다중, 분산처리 상에서 프로세스들을 병렬 수행하는 것. 병행시 고려 사항 발생 병행시 관계정의의 필요 상호관계, 임계영역, 교착상태, 라이브락, 상호배제, 기아, 결정성, 동기화, 통신 등 병행시 관계정의의 필요 협조관계 : 공유객체 사용시 필요 경쟁관계 : 한정된 자원을 병행작업으로 사용하기 위해 필요 프로세스들이 서로차지 하려 하기 때문에 상호 간섭 문제 발생
병행 프로세스 문제 해결 선행 그래프 선형 그래프 선행 그래프 조건 S1 선행관계 S1이 끝나야 S2, S3가 수행 방향성이 있는 유향 비순환 그래프 순환이 없어야 함. S6 S5 S7
병행 프로세스 문제 해결 선행 그래프 순환 선형 그래프 S1 S2와 S3과의 순환(cycle)이 있기 때문에 선행 제약 조건에 부합하지 않음 S2 S3
판독 세트와 기록 세트 프로세스 내에서 여러 명령문들 중에 어떤 명령문들을 병행해서 수행할 수 있고 어떤 명령문들이 선행해야 할 조건이 있는지를 알아내는 병행 조건 정의이다. 판독 세트 : R(Si) = {a1, a2, a3, …, an} : 문장Si의 수행 중, 판독(read) 되는 모든 변수의 집합으로 ai의 값은 참조만 되며, 그 값은 변하지 않음. 기록 세트 : W(Si) = {b1, b2, b3, …, bm} : 문장 Si의 수행 중, 기록 (write)되는 모든 변수의 집합으로 bi의 값은 변화할 수 있음.
판독 세트와 기록 세트 read(a, b); --------------------S1 프로그램 어떤 값을 읽어온 후, a,b,c,d에 기록하는 의미 read(a, b); --------------------S1 read(c, d); --------------------S2 x := a + b + c + d; --------------S3 write(x); ----------------------S4 a,b,c,d를 판독(참조)하여 x에 기록 x를 판독(참조)하여 출력 문장 S1 : 판독 세트 R(S1) = {} 기록 세트 W(S1) = {a, b} 문장 S2 : 판독 세트 R(S2) = {} 기록 세트 W(S2) = {c, d} 문장 S3 : 판독 세트 R(S3) = {a, b, c, d} 기록 세트 W(S3) ={x} 문장 S4 : 판독 세트 R(S4) = {x} 기록 세트 W(S4) = {} 프로그램 에 대한 판독/기록 세트
상호배제(Mutual Exclusion)와 임계영역(Critical Section) 상호배제 : 프로세스가 어떤 공용변수를 액세스 하는 도중 다른 프로세스들이 동일한 공용변수를 액세스 할 때에 늦게 액세스를 요청한 프로세스들을 기다리도록 하게 하는 것. 임계영역 : 공용변수를 사용할 수 있는 영역 프로세스가 공용 데이터를 액세스 하고 있을때 그 프로세스는 임계영역 내에 있다고 말 한다.
상호배제(Mutual Exclusion)와 임계영역(Critical Section) 상호배제 Dekker의 알고리즘 2개의 프로세스의 병행 작업들이 일으키는 여러 문제점들을 최초로 정확한 해결 방법을 제시한 알고리즘 한 프로세스가 두 번 연속해서 임계영역에 진입 할 수 있으나 세 번째는 다른 프로세스가 진입
세마포어(Semaphore) 상호배제의 좀 더 복잡한 문제를 극복하기 위해 다익스트라가 도입한 해결방법 P와 V라는 연산에 의해서만 접근되어지는 정수형 변수 P는 임계구역에 들어가기 전에 수행 V는 임계구역에서 나올 때 수행 단점: P와 V는 독립적이기 때문에 잘못 사용하는 경우 문제 발생
모니터(Monitor) 병행 다중 프로그래밍에서 상호배제를 구현하기 위한 특수 프로그램 기법, 하나의 공유 자료의 구조와 병행 프로세스들 간에 공유 자료의 접근을 하기 위한 기능들의 집합을 의미한다. 모니터 진입부 공유자원 공유 데이터 프로시저1 프로시저 집합 프로시저2 프로그램 실행 부분 수행루틴 초기화 코드 모니터의 구조