[운영체제] 프로세스 동기화 문제 & 해결방법

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

do{
    entry section
    critical section
    exit section
    remainder section
} while(1);

entry로 lock을 걸어서 critical section 접근을 막고 exit를통해 다른 프로세스가 critical section에 진입할 수 있게한다

 

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

1. Mutual Exclusion(상호 배제)

  - 프로세스가 critical section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다

2. Progress

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

3. Bounded Waiting(유한 대기)

  - 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

 

동기화문제를 해결할 수 있는 여러 알고리즘이 있다.

알고리즘1

int turn=0;

do{
    while(turn!=0);
    critical section
    turn=1
    remainder section
} while(1);

turn 변수를 통해 차례를 설정한다. while문을 돌면서 상대방이 빠져나오면 while문이 충족돼서 critical section에 들어간다

누가 나와야 다른 누군가 들어가는 방식이여서 progress 조건을 만족 못한다.

 

알고리즘2

do{
    flag[i]=true; # critical section 들어가려는 마음을 표시
    while(flag[j]);
    critical section
    flag[i]=false
    remainder section
} while (1);

critical section에 들어가고싶을때는 flag를 든다. 다른 flag를 체크해서 참인 flog가 있으면 기다린다. critical section에 들어갔다면 빠져나올때는 깃발을 내린다. 여기서 둘다 깃발을 들고 끊임 없이 양보하는 상황이 발생한다.

알고리즘 1과 마찬가지로 progress 조건을 만족 못한다

 

알고리즘3(peterson)

do{
    flag[i]=true; # critical 들어가려는 마음을 표시
    turn=j;
    while(flag[j]&&turn==j);
    critical section
    flag[i]=false
    remainder section
} while (1);

둘다 critical section에 들어가고싶으면 자기 차례인지를 따져본다. 아무도 안들어가있으면 바로 들어간다.

상대방이 깃발을 들고있고 상대방 차례이면 자기 차례를 기다린다. 두 조건 다 만족못하면 본인이 들어가고 나올때는 깃발을 내린다. 세 가지 조건을 만족하지만 Busy Waiting(=spin lock, 계속 CPU와 momory를 사용하면서 wait한다) 문제 있을 수 있음. 

 

하드웨어적으로 Test and set 지시만 내려지면 동기화 문제를 쉽게 해결할 수 있다

 

a가 원래 0이였다면 읽고 1로 바꿔준다 1이였으면 읽고 1로 세팅한다.

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

lock이 걸려있는지 체크하고 안걸려있으면 내가 lock을 걸고 critical section에 들어간다. lock이 걸려있으면 while문을 돌면서 기다린다. 

 

 

자료출처

BRAHAM SILBERSCHATZ ET AL., OPERATING SYSTEM CONCEPTS, NINTH EDITION, WILEY, 2013

반효경, 운영체제와 정보기술의 원리, 이화여자대학교 출판부, 2008