[운영체제] 교착상태, 기아상태 그리고 우선순위역전(Deadlocks, Starvation and Priority Inversion)

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

마치 세마포어가 임계구역 문제를 해결하는 만능열쇠처럼 보였지만 실상은 그렇지 않다. 다음 예시를 한번 보자.

교착상태(Deadlock)

P0

wait(S);
wait(Q);
.
.
.
signal(S);
signal(Q);

P1

wait(Q);
wait(S);
.
.
.
signal(Q);
signal(S);

프로세스 P1 과 P2가 임계구역 진입을 시도하려고 하는 것을 생각해보자. 그리고 세마포어는 1로 초기화 되어 있다고 가정하자. 위와 같은 상황에서 아래와 같은 상황이 발생한다. 편의상 P1과 P2 번갈아가며 실행한다고 생각해보자.

1. P0가 wait(S) 실행, S 세마포어의 값은 0이 된다. 아직 음수가 되지 않았기 때문에 임계구역 진입을 위해 계속 진행한다. 현재 S는 P0가 점유한 상황이다.
2. P1이 wait(Q) 실행, Q 세마포어의 값이 0이 된다. 아직 음수가 되지 않았기 때문에 임계구역 진입을 위해 계속 진행한다. 현재 Q는 P1이 점유한 상황이다.
3. P0가 wait(Q) 실행, Q 세마포어의 값이 -1이 된다. 세마포어 값이 음수가 되었으므로 P0는 Q의 대기 큐에 들어간다.
4. P1이 wait(S) 실행, S 세마포어의 값이 -1이 된다. 세마포어 값이 음수가 되었으므로 P1는 S의 대기 큐에 들어간다.
5. P0가 임계구역에 진입하기 위해서는 P1의 signal(Q)를 받아야한다.
6. P1이 임계구역에 진입하기 위해서는 P0의 signal(S)를 받아야한다.
7. 두 프로세스 모두 대기 큐에 들어가 있으므로 signal() 연산은 절대 일어나지 않는다. 따라서 두 프로세스가 무한히 대기하는 상태가 된다.

위 예시처럼 두 프로세스가 서로의 자원을 필요로 하게 되면, 서로 대기큐에 들어가 무한정하게 기다리는 상태가 되고 이런 문제를 우리는 deadlock 이라고 부른다.

Solution

교착 상태에 대한 더 자세한 이야기는 책을 더 정리하면서 추가하도록 하자.

기아상태(Starvation)

교착상태와 비슷한 문제가 하나 더 있다. 세마포어의 대기 큐에서 대기하던 프로세스는 signal() 연산을 통해 대기 큐에서 제거되면 상태가 ready 상태로 바뀌고, 준비 큐로 들어가 디스패쳐의 스케줄링을 기다리게 된다. 이때 선입선출로 스케줄링 되는 것이 아니라 우선순위에 의해 스케줄링 되는 방식이라면(Priority Scheduling), 해당 프로세스가 우선순위가 낮을 경우 준비 큐에서 디스패처의 선택을 받지 못하고 계속 대기중인 상태가 될 여지가 있다. 이렇게 우선순위에서 계속 밀려서 스케줄링되지 못하고 계속 준비 큐에 남아있는 프로세스를 기아상태에 있다고 한다.

Solution

일반적으로 스케줄링 알고리즘을 수정해서 Round Robin 알고리즘을 Priority Scheduling 과 함께 사용하거나, aging 을 적용해서 대기시간에 따라 프로세스의 우선순위를 단계적으로 높이는 기법이 사용된다.

우선순위역전(Priority Inversion)

우선순위역전 문제는 기아상태 문제와 비슷한 맥락이다. 이 문제는 스케줄링이 가능한 프로세스가 3개 이상 존재할 때 발생한다. 다음과 같은 상황을 상상해보자.

1. 우선순위가 가장 낮은 프로세스 Plow 가 세마포어 S를 점유하고 실행중이다.
2. 우선순위가 가장 높은 프로세스 Phigh 가 시스템의 준비 큐에 들어왔고, 스케줄러에 의해 곧바로 CPU를 선점한다. 이때 Plow 는 다시 준비큐로 돌아간다.
3. 그런데 Phigh 가 작업하는 중에 세마포어 S를 사용해야하는 작업이 있다. 하지만 현재 세마포어는 Plow가 가지고 있기 때문에 wait에 의해 Phigh 는 세마포어의 대기 큐에 들어가서 대기한다.
4. CPU가 비었기 때문에 중간 우선순위를 가지고 있는 프로세스 Pmiddle 이 등장하고 스케줄링된다.
5. 이제 Phigh는 Pmiddle이 모두 종료되고, Plow가 다시 실행되어서 signal()을 실행할 때까지 기다려야 하는 상황이 되었다. 우선순위가 역전된 것이다.

우선순위는 존재하지만 세마포어 때문에 우선순위가 의미가 없어지는 역설적인 상황이다. 여기서 만약 기아상태 문제까지 발생해서 Plow 의 실행이 점점 더 늦춰진다면, Phigh의 우선순위는 정말로 의미가 없진다.

Soulution

우선순위 역전 문제의 해결을 위해서 우선순위 상속 프로토콜(Priority-Inheritance Protocol) 을 사용할 수 있다. 우선순위 상속은 만약 어떤 프로세스가 자기자신보다 높은 우선순위를 가진 프로세스로 부터 자원을 요청받는다면, 해당 자원을 넘겨줄 때까지 프로세스의 우선순위를 상속받아 높이는 것이다. 이 방법을 사용하면 위 예시에서도 Plow가 Phigh의 요청을 받는 순간 우선순위를 최고순위로 높이면서 중간 우선순위 프로세스를 제치고 먼저 실행될 수 있도록 할 수 있다.