[OS] 상호 배제, 한정 대기, 진행, 피터슨 알고리즘

2023.05.22 - [OS] - [OS] 생산자-소비자 문제

[OS] 생산자-소비자 문제

 

 

임계구역 해결 방법

.

 

 

임계구역 문제를 해결하는 단순한 방법은 Lock을 이용하는 것이다.

앞 내용에서 말한 임계영역 해결하는 3가지 조건에 대해 차례로 알아보자.

 

 

1. 상호 배제 문제

.

 

 

 

먼저 잠금이 걸려있나 while문을 통해 확인 후 잠겨있을 경우(true) 무한 루프를 돌며 기다린다.

다른 프로세스가 작업을 완료하여 lock 값을 false로 바꾸면

무한 루프를 빠져나와 임계구역으로 진입한다.

 

이 상황에서 문제점을 알아보자.

 

 

 

P1이 1번을 실행 후 타임아웃으로 준비 상태로 옮겨지고 문맥 교환이 발생으로 P2가 실행된다.

P1이 lock 값을 true로 바꾸기 전에 P2가 2번문을 통과하였기 때문에

두 프로세스가 동시에 임계 구역으로 진입할 수 있게 되었다.

 

이렇게 두 개 이상의 프로세스가 동시에 임계 구역으로 진입하는 것을 '상호 배제'라고 한다.

 

또한, lock 값을 확인하기 위해 while 문을 통해 무한 루프를 돌면서

시스템 자원을 낭비하여야 한다는 문제도 있다.

 

 

2. 한정 대기 문제

.

 

아래 그림은 상호 배제를 보장하지 못하는 이전 문제를 보완하여 작성된 코드이다.

 

 

 

 

위의 코드는 잠금을 2개를 사용한다.

먼저 잠금을 하고 다른 프로세스가 잠겼는지 확인하므로 두 프로세스의 상호 배제가 보장된다.

 

그럼 이 코드에서 문제는 무엇일지 알아보자.

 

 

P1, P2 모두 첫번째 문장만 실행되고 타임아웃이 발생하면,

그 다음 실행에서 두 프로세스가 무한 루프에 빠져서 임계구역에 진입하지 못한다.

 

이는 한정 대기 조건을 보장하지 못하는 상황으로 '교착 상태'라고 한다.

 

교착 상태는 프로세스가 살아 있으나 작업이 진행되지 못하는 상태를 말한다.

 

또한, 이 방법은 프로세스가 늘어나면 lock의 개수도 늘어나 비효율적이다.

 

 

3. 진행 문제

.

 

 

 

위의 코드에서 lock값은 1이면 P1의 임계구역, 2이면 P2의 임계구역을 사용한다는 뜻이다.

 

위의 코드는 상호 배제와 한정 대기를 보장한다.

그러나 서로 번갈아가며 실행되기 때문에 한 프로세스가 연속적으로 임계구역에 진입할 수 없다.

 

즉, P1은 P2가 입계구역 진입 후 다시 진입할 수 있으므로

서로가 진행을 방해하는 구조이다.

 

이는 진행 조건을 보장하지 못한다.

 

 

4. 동기화 하드웨어

.

 

 

 

하드웨어적인 방법으로도 간단히 해결할 수 있다.

1번과 2번을 분리 실행하면 타임아웃의 문제가 발생한다.

 

하드웨어적으로 두 명령어를 동시에 실행하면 이 문제를 쉽게 해결할 수 있다.

 

하드웨어적 해결 방법은 편리하지만 바쁜 대기를 사용하여 검사하기 때문에 자원 낭비가 있다.

 

 

5. 피터슨 알고리즘

.

 

 

 

피터슨 알고리즘은 한정 대기에서 설명한 코드와 비슷한데

turn이라는 공유 변수를 더 사용하였다.

 

변수 turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못 들어가는 상황에 대비하기 위한 장치이다.

즉 두 프로세스가 동시에 lock을 설정했더라도 turn을 사용하여 다른 프로세스에게 양보한다.

 

 

피터슨 알고리즘은 임계구역 세 가지 조건을 모두 만족하지만

2개의 프로세스만 사용 가능하다는 한계가 있다.