[OS] Critical Section Problem S/W Solution - Peterson's Solution

앞의 Synchronization과 Critical-Section Problem에서 설명했던 critical section problem의 solution에 대해 알아보자!

Critical section의 기본 조건

1. Mutual Exclusion

어떤 프로세스가 Critical section을 실행 중이라면, 다른 프로세스는 Critical section을 실행할 수 없다!

2. Progress

어떠한 프로세스도 critical section을 실행하지 않고, critical section을 실행하려는 프로세스가 있다면, 다음 critical section을 실행하는 프로세스가 무기한 연기되어선 안 된다!

👉 deadlock 방지

3. Bounded Waiting

각 프로세스는 유한한 횟수의 시도 후에 critical section에 들어갈 수 있어야 한다.

👉 starvation 방지

🔍 Software basedCritical Section Solution

Critical Section Algorithm 1

공유 변수로 boolean 타입의 wants 배열을 사용해보자.

wants[i]는 i번째 Process가 critical section을 실행하길 원한다는 의미

아래와 같은 코드를 가진다.

2개의 프로세스가 C.S.에 접근하길 원하고, 다음과 같이 interrupt가 발생하는 상황을 생각해보자.

wants[i] = true;

 

이 라인을 실행하는 과정에서 interrupt가 발생하게 된다면, wants[1], wants[2] 모두 true가 되어 어느 프로세스도 critical section에 접근하지 못하게 된다.

👉 Critical Section의 기본 조건인 Progress를 충족하지 못한다.

 

Critical Section Algorithm 2

이번엔 공유 변수로 integer 타입의 not_turn 변수를 사용해보자.

not_turn이 i일 경우 i번째 Process가 critical section의 실행을 마쳤다는 의미

해당 C.S.를 가지는 프로세스가 2개 있고, 하나의 프로세스만 C.S.에 접근하길 원한다고 가정해보자.

P1이 C.S.을 나오면 not_turn 변수는 1이 된다. 이후 P2가 C.S.를 사용하지 않고 P1이 C.S를 사용하고자 한다면 P1은 C.S에 접근하지 못하게 된다.

👉 Critical Section의 기본 조건인 Progress를 충족하지 못한다.

 

Peterson's Solution

Peterson's solution은 H/W 도움없이 S/W기반 솔루션이다.

앞서 두 알고리즘에서 나온 boolean 타입의 wants 배열과 integer 타입의 not_turn 변수를 공유 변수로 사용한다.

Mutual Exclusion이 보장되는가?

앞의 두 알고리즘에서 확인해본 것과 같이 wants 배열이나 not_turn 변수를 사용하면 하나의 프로세스만 C.S.에 접근하는 것을 보장할 수 있다.

 

Progress가 보장되는가?

앞의 두 알고리즘에서 발생한 문제점을 확인해보자.

Case 1 - wants 배열 사용

알고리즘 1에서는 interrupt로 인해 두 프로세스의 wants 배열의 값이 모두 true가 되는 상황으로 두 프로세스 모두 C.S.에 접근하지 못하는 문제가 발생한다.

👉 Peterson's Solution에서는 not_turn 변수 또한 같이 사용하기 때문에 반드시 하나의 프로세스가 C.S.에 접근하는 것을 보장할 수 있다.

Case 2 - not_turn 변수 사용

알고리즘 2에서는 두 프로세스 모두 C.S.를 가지고 있지만 하나의 프로세스만 C.S.에 접근하길 원할 때 해당 프로세스는 다시 C.S.에 접근하지 못하는 문제가 발생한다.

👉 Peterson's Solution에서는 wants 배열을 사용하여 C.S.에 접근하길 원하지 않을 경우 false가 되기 때문에 이 문제를 해결할 수 있다.

 

❕❕❕ 하지만 현대 아키텍쳐에서는 원활한 작동을 보장하지 못한다...... ❕❕❕

Interrupt는 언제든지 일어날 수 있기 때문에 다시 race condition을 야기할 수 있다..

Peterson's solution은 온리 2개의 프로세스에서만 작동한다........

 

그래서 Peterson's solution은 어디서 쓰냐고 ❔❔❔

알고리즘을 검증하는 데에 유용하다고 한다~

---

다음 포스팅에서는 현대 OS에서 사용할 수 있는! Hardware Solution에 대해 알아보겠습니다 😁