목차
📁 Critical Secltion Problem
n개의 프로세스들이 각자 자신의 critical section을 가지고 있다.
critical section의 코드를 실행하며 서로 경쟁적으로 접근하는 상황에서 어떤 한 프로세스가 critical section을 실행하고 있으면 다른 프로세스들은 자신의 critical section을 실행하면 안된다, 즉 같은 데이터는 동시에 접근하지 못하도록 하라는 문제가 critical section problem이다.
📁 Critical Section Problem 해결책
다음 세가지 요구사항을 모두 만족해야 한다.
1. mutual exclusion
어느 순간에 하나의 프로세스만이 자원에 접근할 수 있고, 그동안에는 다른 프로세스들이 접근하지 못하도록 하는 성질.
2. progress
어느 프로세스가 자신의 critical section에 들어가 실행하려고 하고 다른 프로세스들은 자신의 critical section을 실행하고 있지 않을 때, 실행하려는 프로세스가 critical section을 실행할 수 있어야한다는, 공유 데이터에 접근할 수 있어야 한다는 성질.
3. bounded waiting
어느 프로세스가 critical section에 들어가려고 하는데 이미 다른 프로세스가 들어가있는 상황일 때, 기다리는 시간이 한계가 있다는 성질. 즉 무한정 기다리지 않아야 한다.
예를 들어, 프로세스 p1, p2, p3가 있다고 하자. p1이 자신의 critical section을 실행하기 위해 담장에 왔는데, 이미 p2가 들어있는 상황이다. 이때 p1는 담장에 들어갈 수 없다.
=> mutual exclusion
현재 p1이 실행중이기 때문에 cpu는 p1에게 있고, p1이 running 상태이며 p2는 ready상태이다.
p1이 담장에 들어가지 못하고 기다리다가 cpu의 타임슬라이스가 끝나면 다음으로 cpu는 언젠가 p2에게 주어지고, p2는 critical section을 마저 실행 후 나올 것이다. 이후 instruction을 이어서 수행하다가 타임슬라이스가 끝나 p3에게 cpu가 주어졌다고 가정하자. 이때 p3이 critical section을 수행하고 싶다면 담장 안으로 들어갈 수 있다.
=> progress
이때 p3도 critical section을 다 실행하지 못한 채로 타임슬라이스가 끝나고, 다시 cpu가 p1에게 주어졌다. p1도 critical section에 들어가고 싶지만, mutual exclusion 성질때문에 기다려야한다. 이후 p1의 cpu 타임슬라이스가 끝나고, 이번엔 cpu가 p3에게 주어져 critical section을 끝내고, 다시 p2에게 주어져 critical seciton에 들어가는 것과 같이 공교롭게 스케줄링이 p1을 critical section수행을 못하게 막는다면, 이론적으로 p1은 무한정 기다릴수도 있게 되는 것이다.
=> bounded waiting
📁 해결책 구현방법
소프트웨어로 담장을 치는 방법 = Software solution이라고 함.
위 그림처럼 critical section 위에 entry section, 아래에 exit section을 배치한다. 중요한 critical section을 앞뒤로 둘러싸게 만드는 것이다.
이 과정을 통해 entry section과 exit section으로 critical section에 담장을 씌운 효과가 난다.
entry section에서 담장을 열고 닫는 등 통제 역할을 하고, exit section에서 안에 있던 프로세스를 밖으로 나오게 하고, 밖에서 어떤 프로세스가 기다리고 있었다면 들어가도 된다는 것을 알려주는 역할을 한다.
📝 Software solution1
공유데이터로서 shared variable로 turn이라는 변수를 사용하고, 초기값은 0이다.
turn은 담장 안에 들어갈 순서를 의미한다.
때문에 turn은 0 혹은 i가 될 수 있는데, 0이면 P0, i면 Pi가 들어갈 수 있다는 것을 나타낸다.
아래는 구현 코드이다.
먼저 while문에서 turn이 i가 아니라면 이라는 조건을 체크한다. 해당 코드가 entry section이다.
turn을 j로 설정하는 코드가 exit seciton이다.
위 코드는 mutual exclusion 요구사항은 만족하지만 progress 성질은 만족하지 않는다.
만약 p0가 cpu를 먼저 받을 경우에는 문제 없지만, p1이 먼저 받았다고 가정하자. 이때 p0는 실행하지 않은 상태이지만, p1이 entry section 코드를 수행할 때 turn이 0이기 때문에 p1이 들어갈 수 없다.
📝 Software solution2
일명 Peterson's Algorithm.
위 코드에서 critical section 앞의 세 줄의 entry section, critical section 뒤의 코드 한줄을 exit section이 된다.
이 방법은 요구사항 3개를 모두 만족한다.
하지만 이 솔루션은 프로세스가 두 개일 때만 mutual exclusion이나 progress 문제들을 해결해준다.
