[OS] Critical Section Problem, 쓰레드간 협력

하나의 일을 효율적으로 처리하기 위해서는 쓰레드간 협력이 필요하다. 이러한 협력을 보장하기 위해 서로 개별적인(automic)한 연산을 수행해야한다. 예를 들어 Producer-Consumer Problem을 살펴보자. 한 쓰레드(A)는 cnt 변수를 하나 증가시키고 다른 한 쓰레드(B)는 cnt 변수를 하나 감소시켜야한다. 처음 목표는 A가 cnt를 하나 증가시키고 B가 하나를 감소하는거라 기존값과 같은 결과가 나와야하지만 A가 증가시키는 도중에 B가 cnt 변수를 읽어 하나를 감소시켜 덮어쓴다면 기존값보다 하나 더 작게 나오는 결과가 나온다. 이러한 상황을 동시성 문제, Race Condition(두 프로세스가 동시에 같은 변수를 조작해 결과가 예측 불가능하게 되는 상황)이라 한다. 이 문제를 방지하여 개별적인 연산을 수행하는 것을 Synchornization이라하고 공유 변수를 조작하는 구문은 한번에 하나의 프로세스만 실행하도록하여 임계구역을 정한다. 

 

임계구역에 대해서는 위 사진을 보면 더 쉽게 이해할 수 있다. critical section을 임계구역이라 하는데 공유자원(위에서 말한 cnt)을 사용하는 구역을 말한다. 한번에 한 쓰레드만 code영역에 접근하는 single write 성질을 띈다. 그리고 entry section은 임계구역에 들어가기 위해 준비하는 구역으로 임계구역에 있던 쓰레드가 exit되면 entry section에 있던 쓰레드 중 하나가 critical section으로 들어가게 된다. remainder section은 임계구역과 상관 없는 나머지 일반 작업을 하는 영역이다. 

 

공유 데이터 무결성을 지키면서 여러 프로세스가 협력하여 자원을 사용할 수 있도록(Critical Section Problem)하는 3가지 조건은 아래와 같다.

1. Mutual exclusion

상호 배제란 동시에 두 쓰레드가 임계구역에 진입하지 안고 한 쓰레드만 임계구역에 들어와 일할 수 있게 하는것이다. Mutual Exclustion을 강화하게 된다면 starvation과 deadlock을 방지할 수 있다. starvation 방지란 어떤 쓰레드도 무한히 기다리지 않도록하는 것이다. 임계구역 진입을 원하면 반드시 언제가는 진입할 수 있어야한다. deadlock 방지는 교착상태로 모든 쓰레드가 서로 임계구역을 대기하는 상황을 말한다. 

2. Progress

critical section 수요 쓰레드가 1개밖에 없으면 바로 들어갈 수 있게 들어가고 싶어하는 쓰레드 중에서 결정하는 것이다. 아무도 ritical section에 없고, 여러 프로세스가 진입을 기다리고 있다면 기다리는 프로세스 중에서 하나는 반드시 들어가야 한다. 

3. Bounded wating

어떤 쓰레드가 임계 구역 진입을 요청한 후 정해진 횟수 이내에 반드시 진입할 수 있어야한다(starvation 방지) 즉 critical section 대기시간은 무한이면 안되며 반드시 자신 차례가 와야한다.

이때 Progress를 충족하지 않으면 자연스레 Bounded wating도 만족하지 않는다(기다리는 프로세스 중 하나가 반드시 들어가야하는데 이게 만족하지 않으면 wating 시간이 무한..)

 

이를 구현하는 4가지 알고리즘에 대해 알아보자

 

Algorithm1: turn 설정

처음엔 turn을 0이나 1로 초기화하고 trun이 i라면 Pi가 임계구역 진입, turn이 j라면 Pj 임계구역 진입

 

이는 Mutual exclusion하지만 progress는 충족하지 않는다. 자신의 turn으로 설정되야 임계 구역에 진입할 수 있기에 섹션에 하나의 쓰레드만 존재하는 것은 자명하다. 그러나 trun이 상대에 의해 바뀌기 때문에 turn이 0이고 P0가 remainder section(임계구역 접근X) 상태라면 P1은 임계 구역에 들어가고 싶어도 P0가 critical section에 들어왔다가 turn을 바꿔야하는 순간을 기다려야한다.이는 각 프로세스의 상태를 기억하지 못하고 어떤 프로세스가 임계 구역에 접근 가능한지만 기억해서 발생하는 현상이다.

 

Algorithm2: flag 설정 (상태값)

flag 배열로 상태값 확인, 만약 flag[i]가 true라면 Pi가 임계구역에 진입한다.

하지만 이는 Mutual exclusion에 위배된다. 만약 Pj가 flag를 확인하고 반복문을 탈출했는데 flag 상태를 변경하는 사이 Pi가 변경되지 않은 flag를 확인하면 두 쓰레드가 임계영역에 들어가게 된다. 이는 flag를 변경하기 전에 반복문을 탈출하기 때문에 발생하는 문제이다.

 

Algorithm3: flag를 바꾸고 확인

앞선 2번 알고리즘의 상호배제 문제를 해결하기 위해 flag를 변경하고 상태 flag를 확인하는 알고리즘이다. 이는 Mutual exclusion은 만족하지만 progress하지 않다. 왜냐 P[0]과 P[1] 둘다 임계구역에 들어가고 싶은 경우 무한 대기현상이 발생한다(deadlock)

진입의사가 있는 두 쓰레드가 서로 방해하여 아무도 진입하지 못하는 상황이 발생하는 것이다. 

 

Algorithm4: Peterson Algorithm(flag와 turn 사용)

마지막 상태값과 turn 모두 사용하는 알고리즘이다. 이는 Mutual exclusion, progress, bounded waiting 모두 만족한다.

하나씩 살펴보자

 

Mutual exclusion

각 프로세스는 두 가지 경우에 임계구역 진입 가능 (상대방이 진입 의사가 없는 경우 or 상대방에게 양보 받는 경우)

만약 P0와 P1이 동시에 진입하려 한다면 flag는 둘다 true지만 turn은 한쪽에게만 설정되므로 둘중 한명만 통과할 수 있다

 

Progress

flag가 true이고 상대 turn일때만 임계구역에 진입할 수 없다. 상대가 진입할 의사가 없다면 바로 진입 가능하고 상대와 순서가 겹쳐도 둘중에 하나만 들어가고 작업이 끝나면 flag가 false되므로 남은 쓰레드도 뒤이어 작업할 수 있다

 

Bounded waiting

Pi가 계속 대기중이 상태는 flag가 true이고 상대 turn일때만이다. 상대는 임계구역 작업이 끝나고 반드시 flag를 false로 설정하기 때문에 그 이후에 Pi가 반드시 진입 가능하다

 

다음 블로그에서는 Critical Section Problem을 해결하기 위한 쎄마포어에 대해 알아보자