[ 운영체제 ] 동기화 방법1 - Peterson's Solution

C.S Algorithm의 문제점

임계구역의 일반적인 형태는 아래와 같다. 

 

do{
    wants[i] = true; // i 프로세스가 공유 자원을 사용하겠다고 선언
    while(wants[j]) {;} // j 프로세스가 공유 자원을 사용중이면 진입 불가(진입구역)
    	CRITICAL SECTION
    wants[i] = false; // i 프로세스가 공유 자원 사용 완료 후 반납(퇴출구역)
    	REMAINDER SECTION
} while(TRUE)

 

기본적인 구조는 잘 갖춰져 있다. 그렇다면 저번 시간에 살펴본 임계구역의 세 가지 요구사항을 만족하는지 살펴보자. 기본적으로 상호배타적 접근은 전제로 깔고 가기 때문에 진행과 한계 대기만 확인하면 된다. 상호 배타도 뒤에서 따져보기 때문에 천천히 보시기를... 이게 무슨 말인지 모르겠다면 바로 이전 글을 보고 오는 것을 추천한다. 

wants[1] = true, wants[2] = true 인 경우

프로세스 P1, P2가 있고 각각 자원을 사용하겠다고 선언한 경우다. 아래의 순서로 진행될 경우 문제 없이 잘 수행될 것이다. 그런데 그 전에 wants[i]의 의미에 대해 한번만 더 짚고 넘어가자. wants[i]란 프로세스 i가 임계구역에 진입하겠다는 뜻이다. 아래 그림의 P1 코드에서 wants[1] = true 로 갱신하면 P2는 while문에서 무한 대기하고 있기 때문에 임계구역에 진입할 수 없다. 

 

문제 없이 잘 실행됨

 

그런데 순서가 약간 바뀌면 문제가 발생하게 된다. 아래의 상황을 보자. 

 

문제 발생

 

wants[1], wants[2]가 모두 true이기 때문에 while문에서 무한 대기하게 된다. 이를 '데드락(deadlock)'이라고 한다. 임계구역이 비어 있는데 아무도 사용할 수 없으므로 Progress 위반이고, 무한대기 상태에 빠져서 Bounded Wait 위반이다. 요구사항을 만족하지 않으므로 유효하지 않은 알고리즘이라고 할 수 있다. 이에 대한 해결책이 바로 Peterson's Solution이다. 위 코드에서 not_turn이라는 하나의 변수만 추가해주면 된다. 어떻게 가능한지 천천히 살펴보자.

not_turn 변수

not_turn 변수는 이름처럼 '아직 내 차례가 아니다'를 나타내는 변수다. not_turn에 대응되는 프로세스는 임계구역에 진입하지 못한다. not_turn도 전역변수다.

 

for(;;){ // i는 프로세스 번호
    wants[i] = true; // i 프로세스가 공유 자원 사용하겠다고 선언
    not_turn = i; // 아직 i 프로세스 차례 아님
    
    // j 프로세스가 공유 자원 사용중이고 i 차례가 아니면 진입 못함
    while(wants[j] && not_turn == i); 
    
    	CRITICAL SECTION
    wants[i] = false; // i 프로세스 공유 자원 반납
    	REMAINDER SECTION
}

 

코드의 흐름을 잘 보자. 프로세스 i가 자원을 사용하겠다고 선언하고 바로 다음에 i를 lock 시켜버린다. not_turn 변수는 전역변수이기 때문에 무조건 하나의 프로세스만 lock 된다(상호 배제 해결). 진입 구역 직전에 not_turn 변수를 갱신하기 때문에 임계구역에 진입하지 못하는 상황은 발생하지 않는다(진행, 한계 대기 해결). 아까 위에서 문제가 발생한 상황을 그대로 다시 살펴보자. 

 

 

not_turn 변수가 전역변수이기 때문에 무조건 하나의 프로세스만 lock 되는 것이 핵심이다. while문 안에 not_turn 변수가 조건으로 들어가고, not_turn에 대응하는 프로세스는 오직 하나이므로 임계구역이 비어있으면 항상 들어갈 수 있음을 보장할 수 있다. 

 

그렇다면 피터슨 방법은 C.S의 세 가지 조건(상호 배제, 진행, 한계 대기)을 모두 만족할까? 

1. Mutual Exclusive (상호 배제)

위에서 true, true인 경우는 살펴봤기 때문에 flase, true인 경우와 false, false인 경우를 살펴보자. 

 

Case1 : wants[1] = true, wants[0] = flase, not_turn = 1
while(wants[0] && not_turn == 1)   // 거짓이므로 임계구역 진입
while(wants[1] && not_turn == 0)   이 조건은 생각할 필요가 없다. 왜냐하면 이 코드에 도달하기 위해서는 wants[0] = true, not_turn = 0 과정을 거쳐야 하기 때문이다. wants[0] = false라는 것은 프로세스 0은 아직 공유 자원에 접근하지도 않았다는 의미다. 


Case2 : wants[1] = true, wants[0] = false, not_turn = 0
while(wants[0] && not_turn == 1)   // 거짓이므로 임계구역 진입
wants[0] = false이기 때문에 not_turn의 값에 상관없이 항상 임계구역에 진입할 수 있다. Case1과 동일한 이유에서 다른 while문은 고려할 필요가 없다. 


Case3 : wants[1] = false, wants[0] = false
프로세스 1, 프로세스 0 모두 공유 자원을 사용하겠다고 선언하지 않은 상태다. 이 중 하나가 공유 자원을 사용하겠다고 선언하면 Case1, Case2와 같은 상황이 되는 것이고, 둘 다 사용하겠다고 선언하면 true, true인 상황이 되는 것이다.

 

Case1 ~ Case3 모두 하나의 프로세스만 임계구역에 진입 가능하기 때문에 상호배제 조건을 만족한다.

2. Progress (진행), Bounded Wait (한계 대기)

not_turn 변수는 전역변수이고, 진입 구역 직전에 not_turn 변수를 갱신하기 때문에 임계구역에 진입하지 못하는 상황은 발생하지 않는다. not_turn 변수 파트의 설명과 중복되기 때문에 생략한다. 

 

 

피터슨 방법의 단점과 문제점

피터슨 방법은 소프트웨어적 방법이다. 처음에 이 '소프트웨어적 방법'이 와닿지 않았다. 쉽게 말해서 짜여진 code에 의해 수행된다는 의미다. 반면에 '하드웨어적 방법'은 전기 회로에 의해 수행된다는 의미다. 똑같은 작업을 소프트웨어적 방법과 하드웨어적 방법으로 수행하면 어떤 차이가 있을까? 소프트웨어적 방법은 도중에 context switch가 발생할 수 있다. 그런데 하드웨어적 방법은 해당 작업이 '실행 단위'가 돼버리기 때문에 도중에 context switch가 발생할 수 없다. 속도도 하드웨어적 방법이 훨씬 빠르다. 내가 이해한 게 맞는지 모르겠다ㅎㅎ 틀린 내용에 대해서는 언제든 지적 환영입니다.

 

도중에 눈채 챘을지 모르겠지만, 피터슨 방법은 프로세스가 2개인 경우에만 적용 가능하다. 그래서 사실상 실용성이 없다. 그냥 이런 이론이 있구나~ 하고 넘어가면 될 것 같다. 또한 두 개의 프로세스가 공유 자원에 접근하려고 할 때, 한 프로세스가 임계구역에 진입하면 다른 프로세스는 계속 기다려야 한다. 임계 영역에 들어가기 위해 기다리고 있는 프로세스는 무한 루프를 돌며 임계 영역 직전에 계속 머무리게 되는데, 이때 CPU를 계속 쓴다. 이러한 문제를 Busy Waiting이라고 한다. 싱글 코어라고 하더라도 공유 자원을 사용 중인 프로세스의 작업이 끝나야 비로소 임계 구역에 진입할 수 있다. 만약에 싱글코어인데 공유 자원 사용 중인 프로세스가 임계 구역 안에서 context switch가 일어났다면 다른 프로세스는 context switch까지 무한루프만 돈다는 뜻이다. 

 

또한 피터슨 방법은 현대 컴퓨터에서는 정상 작동하지 않는 문제가 있다. 컴파일러는 메모리 접근을 위해 컴파일 도중에 필요에 따라 코드의 위치를 조금씩 조정한다. 만약 wants[i] = true와 while문의 위치가 바뀌게 되면 제대로 동작하지 않게 된다. 이러한 문제점 때문에 하드웨어적으로 구현하는 방법이 있는데, 이는 다음 시간에 알아보도록 한다.