Process Synchronization 1

공유 데이터에 접근하는 코드를 critical section이라고 한다.

 

critical section 문제를 해결하기 위한 해결법의 충족 조건

• mutual exclusion(상호 배제) - 프로세스 p1가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다. 

 

• progress(진행) - 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다. 

 

• Bounded Waiting(유한 대기) - 특정 프로세스 입장에서 critical section에 못 들어가고 지나치게 오래 기다리는 starvation이 생기지 않도록 해야한다는 말. 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. 

turn으로 어떤 프로세스의 차례인지 알 수 있다.

아래의 코드는 P0에 해당하는 코드. 

do{
    while(turn!=0)
    critical section	//turn=0일때 c.t에 들어가게 된다. 
    turn=1				//상대방 차례로 만들어줌
    remainder section
}while(1)

위의 코드는 상호배제는 만족을 하지만 progress는 만족하지 않는다. critical section이 반드시 교대로 들어가도록 위의 코드가 설계가 되어있는데 process 0과 1의 사용 빈도가 다를 수 있는데 교대로 들어가지 않으면 진행이 되지 않는다. 따라서 critical section에 아무도 들어가지 않아 progress를 만족할 수 없게 된다. 

 

turn을 교대로 활용하는 대신 생각한 방법이 다음 방법이다. 

 

flag 사용. critical section에 들어가고자 한다면 flag를 true로 만든다. 그렇게 하고 상대방 flag를 체크한다. 만약 상대방도 true면 기다린다. 그렇지 않으면 c.t에 들어가고 나오면서 flag값을 false로 만들어준다.

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

위의 코드는 만약 i와 j가 모두 true면 둘 다 while문만 돌고 정작 critical section에는 들어가지 않을 수 있다. 따라서 이 방법도 critical section에 아무도 들어가지 않아 progress를 만족하지 않을 수도 있다. 

 

세번째 알고리즘

Peterson's Algorithm

상대방이 깃발을 들고 있더라도 내 차례면 critical section에 들어갈 수 있다. 

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

위에 나온 3가지 조건을 모두 만족하는 알고리즘이다. 

이 코드의 문제점은 Busy waiting(=spin lock)이다. 계속 회전을 하면서 lock을 걸어서 상대가 못 들어가게 막는다는 것이다. 만약 j가 cpu를 잡고 있어서 while문을 계속 돌고 있으면 계속 CPU와 메모리를 쓰면서 wait하게 된다. 

 

하드웨어 명령어 Test_and_Set(a)은 a라는 값을 읽어오고 true로 바꿔주는 작업을 한번에 한다. 만약에 a라는 값이 0이었으면 1로 세팅. a가 1이었으면 1로 다시 세팅. 

만약 이것이 지원이 된다면 Test_and_set() instruction을 이용해서 critical section에 들어가기 전에 lock을 걸고 나오면서 lock을 풀어 다른 프로세스가 critical section에 들어가게 해주는 코드를 간단히 작성할 수 있게 된다. 

boolean lock=false;

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