TIL 정리_85

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323

운영체제 강의를 듣고 정리한 내용입니다

 

*문제점

하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다

 

해결을 위한 알고리즘

두 개의 프로세스  P0, P1가 있다고 가정한다

 

프로세스들의 일반적인 구조

do {

entry section

critical section

exit section

remainder section

} while(1);

프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다

-> synchronization variable

 

 

프로그램적 해결법의 충족 조건

가정

모든 프로세스의 수행속도는 0보다 크다

프로세스들 간의 상대적인 수행 속도는 가정하지 않는다

 

Mutual Exclusion

프로세스 Pi가 critical section 부분을 수행중이면 다른 모든 프로세스들은

그들의 critical section에 들어가면 안된다

-> 상호 배제

 

Progress

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는

프로세스가 있으면 critical section에 들어가게 해주어야 한다

-> 진행

 

Bounded Waiting

프로세스가 critical section에 들어가려고 요청한 후부터 요청이 허용될 때까지

다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

-> 횟수 제한, 유한 대기

 

Algorithm1

 

Synchronization variables
int turn;
initially turn = 0; ->
Process P0 //숫자 0은 프로세스를 의미한다
do { //체크
while(turn != 0)
critical section
turn = 1;
remainder section
} while(1);

-> 문제점 : 반드시 한 번씩 교대로 들어가야 한다

 

 

Algorithm2

 

Synchronization variables
boolean flag[2];
initially flag[all] = false;
if (flag[i] == true) //Pi를 critical section에 할당한다
Process Pi
do {
flag[i] = true;
while(flag[i])
critical section
flag[i] = false;
remainder section
} while(1);

-> 문제점 : 둘 다 2행까지 수행 후 끊임없이 양보하는 상황이 발생할 수 있다.

 

 

 

Algorithm3 (Peterson’s Algorithm)

 

Process Pi
do {
flag[i] = true;
turn = j;
while(flag[j] && turn == j)
critical section
flag[i] = false;
remainder section
} while(1);

->> 해결법의 충족조건을 다 따른다

-> 문제점 : 계속 CPU와 메모리를 쓰면서 기다린다 (Busy Waiting)

 

 

 

하드웨어적으로 지원하는 경우 이러한 문제는 간단히 해결된다

Mutual Exclusion with Test & Set

• 간결하게 해결하는 방법

boolean lock = false;
Process Pi
do {
while(Test_and_Set(lock));
critical section
lock = false;
remainder section
}