•
다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁할 수 있다. 한 프로세스가 자원을 요청했을 때 자원을 사용할 수 없는 상황이 발생할 수 있고 그 경우 프로세스는 대기 상태에 들어간다. 이처럼 대기 중인 프로세스들이 결코 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착상태라 부른다.
시스템 모델
•
시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다. 이들 자원은 다수의 타입으로 분할되며, 이들 각각은 동등한 다수의 인스턴스(instance)들로 구성된다. CPU 주기, 파일, 그리고 입출력 장치 등이 자원 타입들의 예이다.
◦
한 시스템이 두 개의 CPU를 가진다면 자원 타입 CPU는 두 개의 인스턴스를 가진다. 마찬가지로 프린터라는 자원 타입이 5개의 인스턴스를 가질 수 있다.
•
만일 한 프로세스가 어떤 자원 타입의 한 인스턴스를 요청하면 동일 타입 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다. 만일 그렇지 않으면 인스턴스들이 일치하지 않고 자원 타입의 클래스가 정확하게 정의되지 않은 것이다.
◦
예컨대 시스템이 두 개의 프린터를 가지고 있고, 어떤 프린터가 어떤 출력을 인쇄하는지에 대해 아무도 관심이 없다면 이들 두 프린터는 동일한 자원 클래스로 정의될 수 있다.
◦
그러나 한 프린터는 9층에 있고 다른 프린터는 지하에 있다면 9층에 있는 사람들은 두 프린터를 동등하게 간주하지 않을 것이므로 각 프린터는 별도의 자원 클래스로 정의해야 할 것이다.
•
6장에서 mutex 락과 세마포와 같은 다양한 동기화 도구들에 대해 논의하였다. 이러한 도구들은 시스템 자원으로 간주되며 교착상태의 주요 발생지이다.
◦
그러나 락은 통상 특정 자료구조를 보호하는 것과 관련이 있어서 예컨대 하나의 락은 큐에 대한 접근을 보호하고 다른 락은 연결 리스트의 접근을 보호하는 용도 등으로 사용된다.
◦
그러한 이유 때문에 각 락은 자신만의 자원 클래스를 배정받으므로 락을 정의하는 것은 문제 되지 않는다.
•
프로세스는 자원을 사용하기 전에 반드시 요청해야 하고 사용 후에는 반드시 방출해야 한다. 프로세스는 지정된 태스크(task)를 수행하기 위해 필요한 만큼의 자원을 요청할 수 있다.
◦
명백히 요청된 자원의 수는 시스템에서 사용 간으한 전체 자원의 수를 초과해서는 안된다. 바꾸어 말하면 시스템이 두 개의 프린터 밖에 없는데 세 개를 요청할 수는 없다.
•
정상적인 작동 모드 하에서 프로세스는 다음 순서로만 자원을 사용할 수 있다.
1.
요청: 프로세스는 자원을 요청한다. 요청이 즉시 허용되지 않으면 요청 프로세스는 자원을 얻을 때까지 대기해야 한다.
2.
사용: 프로세스는 자원에 대해 작업을 수행할 수 있다.
3.
방출: 프로세스가 자원을 방출한다.
•
자원의 요청과 방출은 시스템 호출이다. 그런 예들로 장치의 request()와 release(), 파일의 open()과 close(), 그리고 메모리의 allocate()와 free() 시스템 호출이 있다.
◦
마찬가지로 6장에서 본 것처럼 세마포의 획득과 방출은 세마포에 대한 wait()와 signal() 연산 또는 mutex 락의 획득과 방출을 통해 이루어질 수 있다.
◦
프로세스나 스레드가 커널이 관리하는 자원을 사용할 때마다 매번 운영체제는 프로세스가 자원을 요청했는지와 그 자원을 할당받았는지를 확인한다.
◦
시스템 테이블이 각 자원이 자유 상태인지 또는 할당되었는지를 기록하며 각 할당된 자원에 대해서는 어느 프로세스에게 할당되었는지도 기록한다.
◦
어떤 프로세스가 현재 다른 프로세스에 할당된 자원을 요청하면 그 자원을 기다리는 프로세스 큐에 입력될 수 있다.
•
한 프로세스 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스에 의해서만 발생 될 수 있는 사건을 기다린다면 그 프로세스 집합은 교착 상태에 있다. 여기서 우리가 주로 관심 갖는 사건은 자원의 획득과 방출이다.
◦
자원은 물리적인 자원(프린터, 메모리 공간, CPU 주기 등) 또는 논리적인 자원(세마포, mutex 락, 파일 등)일 수 있다. 그러나 다른 타입의 사건들 또한 교착상태를 발생시킬 수 있다.
•
교착상태를 설명하기 위해 세 개의 CD RW 드라이브를 가진 시스템을 고려해 보자. 세 개의 프로세스가 있고 각각 한 개의 CD RW 드라이브를 점유한다고 가정하자. 만약 각 프로세스가 지금 또 다른 드라이브를 요청한다면, 세 개의 프로세스는 교착상태에 놓인다.
◦
각각은 CD RW 드라이브가 방출되었다는 사건을 기다리는데 이 사건은 다른 대기 중인 프로세스들 중의 어느 하나에 의해서만 발생이 가능하다. 이 예는 동일한 자원 타입을 얻으려고 경쟁하는 프로세스의 교착상태를 설명한다.
•
교착상태는 다른 자원 타입을 포함할 수도 있다. 예컨대 하나의 프린터와 하나의 DVD 드라이브를 가진 시스템을 생각해 보자.
◦
프로세스 Pi는 DVD 드라이브를 점유하고 있으며 Pj는 프린터를 점유하고 있다고 가정하자. 만약 Pi가 프린터를 요청하고, Pj가 DVD 드라이브를 요청한다면 교착상태가 발생한다.
•
다중 스레드 응용 개발자는 반드시 교착상태의 가능성을 염두에 두어야 한다. 6장에서 선보인 락킹 도구들은 경쟁조건을 회피하도록 설계되었다. 그러나 이러한 도구를 사용할 때, 개발자는 락이 획득되고 방출되는 방식에 대해 주의를 기울여야 한다. 그렇지 않은 경우 ‘식사하는 철학자 문제’에서 설명한 것처럼 교착상태가 발생할 수 있다.
교착상태의 특징
•
교착상태에서 프로세스들은 결코 실행을 끝낼 수 없으며, 시스템 자원이 묶여 있어서 다른 작업을 시작하는 것도 불가능하다.
필요 조건들(Necessary Conditios)
•
교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.
1.
상호 배제(Mutual exclusion)
•
최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 프로세스만이 그 자원을 사용할 수 있다. 다른 프로세스가 그 자원을 요청하면 요청 프로세스는 자원이 방출될 때까지 반드시 지연되어야 한다.
2.
점유하며 대기(Hold-and-wait)
•
프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
3.
비선점(No preemption)
•
자원들을 선점할 수 없어야 한다. 즉 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있다.
4.
순환 대기(Circular wait)
•
대기하고 있는 프로세스의 집합 { P0, P1, … , Pn } 에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 .. Pn은 P0가 점유한 자원을 대기한다.
•
우리는 교착상태가 발생하려면 앞의 네 가지 조건이 성립되어야 함을 강조한다. 순환 대기 조건은 점유하며 대기 조건을 암시하므로 네 조건이 완전히 독립적인 것은 아니다. 그러나 각 조건을 별개로 간주하는 것이 유용하다.
자원 할당 그래프(Resource-Allocation Graph)
•
교착상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 보다 정확하게 기술할 수 있다. 이 그래프는 정점(vertex) V의 집합과 간선(edge) E의 집하븡로 구성된다.
◦
정점 V의 집합은 시스템 내의 모든 활성 프로세스의 집합인 P = { P1, P2, … Pn }과 시스템 내의 모든 자원 타입의 집합인 R = { R1, R2, … , Rm }의 두 가지 타입으로 구별된다.
•
프로세스 Pi로부터 자원 타입 Rj로의 방향 간선(directed edge)은 로 표현하며 이것은 프로세스 Pi가 자원 타입 Rj의 인스턴스를 하나 요청하는 것으로 현재 이 자원을 기다리는 상태이다.
◦
자원 타입 Rj로부터 프로세스 Pi로의 방향 간선은 로 표현하며, 이것은 자원 타입 Rj의 한 인스턴스가 프로세스 Pi에 할당된 것을 의미한다.
◦
방향 간선 는 요청 간선(request edge)이라 부르고 방향간선 는 할당 간선(assignment edge)이라 한다.
•
도식적으로 우리는 각 프로세스 Pi를 원으로 표현하고, 각 자원 타입 Rj는 사각형으로 표현한다. 자원 타입 Rj가 한 개 이상의 인스턴스를 가질 떄는 각 인스턴스를 사각 형 내의 하나의 점으로 표현한다.
◦
할당 간선은 또한 반드시 사각형 안의 하나의 점을 지정해야 하는 반면, 요청 간선은 사각형 Rj만을 가리킨다는 것에 유의하라
•
프로세스 Pi가 자원 타입 Rj의 한 인스턴스를 요청하면, 요청 간선이 자원 할당 그래프 안에 삽입된다. 이 요청이 만족될 수 있으면 요청 간선은 즉시 할당 간선으로 변환된다.
◦
프로세스가 더는 자원에 대한 접근을 필요하지 않으면 자원을 방출하고 그 결과 할당 간선은 삭제된다.
•
그림 7.1은 다음 상황을 묘사한다.
◦
집합 P, R, E
▪
▪
▪
◦
자원의 인스턴스
▪
자원 타입 의 인스턴스가 1개
▪
자원 타입 의 인스턴스가 2개
▪
자원 타입 의 인스턴스가 1개
▪
자원 타입 의 인스턴스가 3개
◦
프로세스 상태
▪
프로세스 은 자원타입 의 인스턴스 한 개를 점유하고, 자원 타입 의 인스턴스 한 개를 기다리며 대기한다.
▪
프로세스 는 과 의 인스턴스를 각각 한 개씩 점유하고 자원 타입 의 인스턴스 한 개를 기다린다.
▪
프로세스 는 의 인스턴스 한 개를 점유하고 있다.
