1. 교착상태 원리

교착상태(deadlock)란 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태로 정의된다. 교착상태는 시스템 자원에 대한 경쟁 도중에 발생할 수도 있고 프로세스 간 통신 도중에 발생할 수도 있다. 집합 내의 한 프로세스가 특정 사건의 발생을 기다리며 대기하고 있고, 이 사건이 집합 내의 다른 블록된 프로세스에 의해 발생될 수 있을 때 이 프로세스의 집합은 교착상태가 된다. 교착상태가 영구적인 이유는 기다리던 사건이 결코 발생하지 않기 때문이다.

교착상태는 두 개 이상의 프로세스들이 서로 충돌되는 자원 요구를 할 때 발생한다. 아래 그림은 교착상태의 대표적인 예로, 교통 교착상태이다. 교차로의 네 구역(a,b,c,d)은 제어가 필요한 공유 자원이 된다. 사거리 교차로에서 각 차들이 원하는 자원은 다음과 같다.

1번 차: 구역 a, b가 필요
2번 차: 구역 b, c가 필요
3번 차: 구역 c, d가 필요
4번 차: 구역 a, d가 필요

차들이 거의 동시에 직진하게 되면 그림의 (b)처럼 각 차들이 자원을 가지고 다른 자원(a,b,c,d)을 필요로 하기 때문에 교착상태에 빠지는 것이다.

2. 교착상태 조건

1. 상호 배제(mutual exclusion) 조건
   한 순간에 한 프로세스만이 자원을 사용할 수 있다. 즉 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수는 없다.
2. 점유대기(hold and wait) 조건
   이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다.
3. 비선점(no preemption) 조건
   프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다.
4. 환형 대기(circular wait) 조건
   프로세스들 간에 닫힌 연결(closed chain)이 존재한다. 즉 자원 할당 그래프에서 환형이 만들어 지는 것이다. 닫힌 연결에서 블록된 프로세스가 자원을 점유하고 있는데, 이 자원을 체인 내부의 다른 프로세스가 원하며 대기하고 있다.

여러 가지 면에서 고려해 볼 때 위 조건들은 바람직한 조건들이다. 예를 들어, 상호 배제는 수행 결과의 일관성과 데이터베이스의 무결성을 보장하기 위해 반드시 필요하다. 또한 선점도 임의대로 수행되어서는 안 된다. 예를 들어, 특히 데이터 자원이 연관되어 있는 경우, 선점은 롤백(rollback) 복구 기법의 지원이 있어야만 가능하다. 즉, 프로세스가 다시 재수행될 수 있도록 프로세스의 상태와 사용하던 자원의 상태를 안정적인 이전의 상태로 복원할 수 있어야 선점이 가능한 것이다.

조건 4는 조건 1~3의 결과에 의해 발생한다. 즉, 조건 1~3의 복잡한 상호작용의 결과 해결할 수 없는 환경 대기 상태가 발생하게 되는 것이다. 교착상태의 정의가 바로 해결할 수 없는 환형 대기 상태이다. 환형 대기 상태가 해결될 수 없는 이유는 조건 1~3이 지켜지기 때문이다. 결국 위 네 가지 조건이 교착상태가 발생할 수 있는 필요충분조건이다.

교착상태를 해결하기 위한 다양한 접근 방법들 중 대표적인 것은 3가지가 있다.
첫 번째 접근 방법은 예방(prevent) 으로 교착상태의 발생 조건 1~4 중에 하나를 시스템에서 허용하지 않는 것이다.
두 번째 접근 방법은 교착상태 회피(avoid) 로 현재 자원 할당의 상태에 따라 안전하게 자원 할당을 결정하는 것이다.
세 번째 접근 방법은 교착상태 발견(detect) 으로, 교착상태가 발생하면 그것을 발견하고 회복하는 것이다. 이제부터 각 방법을 살펴보자.

3. 교착상태 예방

교착상태 예방 전략은 운영체제를 설계할 때 교착상태가 발생할 가능성을 없애는 것이다. 구체적으로 이전에 설명했던 교착상태가 발생하기 위한 네 가지 필요충분조건 중에 하나를 설계 단계에서 배제하는 것이다.

3.1 상호 배제

시스템을 설계할 때 상호 배제 조건을 없앨 수는 없다. 상호 배제 조건은 공유 자원의 일관성을 유지하기 위해 반드시 필요하기 때문에, 자원 접근에서 상호 배제가 필요하면 운영체제가 이를 지원해 주어야 한다. 예를 들어, 파일 같은 자원의 경우, 다수의 읽기 접근은 허용되지만 쓰기 접근은 한 시점에 하나만 배타적으로 허용되어야 한다. 다수의 프로세스들이 쓰기 권한을 얻으려고 할 때 교착상태가 발생할 수도 있다.

3.2 점유대기

점유대기 조건은 다음과 같은 방법으로 없앨 수 있다. 프로세스는 자신이 사용할 모든 자원을 한순간에 요청한다. 만일 모든 자원을 할당받을 수 있으면 계속 수행한다. 반면 하나의 자원이라도 할당받을 수 없으면, 어떠한 자원도 할당받지 않은 채 대기한다. 이 방법은 가능하기는 하지만 다음과 같은 비효율성이 나타난다.

1. 프로세스는 모든 자원을 할당받기 위해 오랜 기간 기다릴 수 있다.
실제로는 프로세스가 일부 자원만 할당받고 수행을 시작할 수 있으며, 이후 다른 자원은 수행 중에 할당받아도 되는 경우가 있다.
하지만 이 방법을 적용하면 프로세스는 모든 자원의 할당이 가능해질 때까지 대기해야 한다.
2. 한꺼번에 할당받은 자원 중 일부는 실제 수행이 끝날 때쯤에 사용될 수 있다. 그렇다면 그 자원들은 프로세스의 시작 시점과 실제 사용 시점 사이에서 실제로 이용되지 않으면서 점유되어 있다는 의미가 된다. 그 동안 다른 프로세스들은 그 자원을 사용할 수 없다.
3. 프로세스가 미래에 사용될 모든 자원을 미리 알기는 상당히 어렵다.

3.3 비선점

비선점 조건은 다음과 같은 두 가지 방법으로 없앨 수 있다.
첫째, 자원을 점유한 프로세스가 다른 자원을 요청했을 때 할당받을 수 없다면, 일단 자신이 점유한 자원을 반납한다. 이후 프로세스는 원래 자원과 새로 원하는 자원을 함께 요청한다.
둘째, 한 프로세스에서 다른 프로세스가 점유한 자원을 원하면, 운영체제는 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에게 할당할 수 있다. 두 번째 방법은 프로세스들이 서로 다른 우선순위를 갖고 있을 때 교착상태를 예방할 수 있다.

이 방법은 자원의 상태를 저장하고 복구하기 쉬운 자원에 적용할 수 있다. 이러한 자원의 대표적인 예는 프로세서이다.

3.4 환형대기

환형대기 조건은 자원들의 할당 순서를 정하면 없앨 수 있다. 만일 프로세스가 자원 R을 할당받았다면, 이후 이 프로세스는 자원 R 다음 순서를 갖는 자원들을 요청할 수 있는 것이다.

예를 들어 두 자원 Ri와 Rj가 있으며, 운영체제가 i<j인 할당 순서를 정했다고 하자. 이때 i<j는 Ri가 먼저 할당되어야 하며 그 이후에 Rj가 할당될 수 있다는 것을 의미한다. 프로세스 P가 Ri를 할당하고 Rj를 요청하였다고 하자. 이 상황에서 교착상태가 발생하려면 다른 프로세스 Q는 Rj를 할당하고 Ri를 요청하여야 한다. 하지만 이것은 운영체제의 자원 할당 순서에 위배되기 때문에 나타날 수 없다. 결국 자원들의 할당 순서를 정하면 교착상태가 발생하지 않는 것이다.

점유대기의 경우처럼, 환형대기 조건을 없애는 것은 프로세스의 수행 지연과 불필요한 자원 할당 거부를 야기할 수 있다.

4. 교착상태 회피

교착상태를 해결할 수 있는 또 다른 방법은 회피이다. 회피는 예방과 약간 다른 접근 방법을 사용한다. 교착상태 예방은 교착상태 발생을 위해 필요한 네 가지 조건 중에 하나를 예방하는 방법이다. 예방은 자원 사용과 프로세스 수행에 비효율성을 야기할 수 있다. 반면에, 교착상태 회피는 교착상태 발생 조건 중 1~3은 허용한다. 또한 예방처럼 자원 할당 순서를 미리 정하지도 않는다. 그 대신 자원을 할당할 때 교착상태가 발생 가능한 상황으로 진행하지 않도록 고려한다. 따라서 회피 방법은 예방 방법에 비해 더 많은 병행성을 제공한다(자원 사용의 효율성이 높다). 교착상태 회피는 프로세스가 자원을 요청하고 그 자원이 사용 가능할 때 그대로 할당해 주지 않는다. 할당 전에 이 할당이 교착상태를 발생시킬 가능성이 있는지 동적으로 조사한다. 만일 교착상태를 발생시킬 가능성이 있다면 자원을 할당하지 않는다. 사실 회피 방법은 현재 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고 있어야 가능하다.

교착상태 회피를 위한 2가지 기법

• 프로세스가 시작하려 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면, 프로세스를 시작시키지 않는다.
• 수행 중인 프로세스가 요구하는 추가적인 자원 할당이 교착상태 발생의 가능성이 있으면, 자원을 할당하지 않는다.

4.1 프로세스 시작 거부

새로운 프로세스와 기존의 프로세스들이 요구하는 자원의 개수가 그 자원의 전체 개수보다 적을 경우에 수행을 허용하는 것이다. 이 정책은 최악의 경우, 즉 모든 프로세스들이 동시에 최대 자원을 요구하여 사용함을 가정하고 있으며, 따라서 효율적이지는 않다.

4.2 자원 할당 거부

교착상태 회피를 위한 자원 할당 거부 방법은 은행원 알고리즘이라 불린다. 은행원 알고리즘 자세히 알아보기
은행원 알고리즘의 정의는 다음과 같다.

• 운영체제는 자원의 상태를 감시하고, 사용자 프로세스는 사전에 자신의 작업에서 필요한 자원의 수를 제시하는 교착상태 회피 알고리즘
• 운영체제는 안정상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 교착상태 회피 알고리즘

안전한 상태란 교착상태가 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 진행 경로가 존재함을 의미한다(결국 모든 프로세스가 자신의 자원 요구량을 모두 만족하여 수행을 마칠 수 있음을 의미).
불안전한 상태란 그러한 진행 경로가 없는 상태이다.

간단한 예시를 보자.

프로세스	Max	Allocation
P0	3	1
P1	12	5
P2	4	1

초기에 10이라는 자원이 있었다.
프로세스 P0는 최대 3이 필요하고, 현재 1의 리소스를 사용하고 있다. 프로세스 P1은 최대 10이 필요하고 현재 5를 할당받고, P2는 최대 4가 필요하며 현재 1을 할당 받았다.
따라서 현재 P0은 2, P1은 5, P2는 3이 필요하다.

그럼 이것이 안전한 상태일까?
현재 남은 자원은 10(초기) - 7(Allocation합) = 3 이다.

P0 -> P2 -> P1
P2 -> P0 -> P1
이라는 진행 경로가 존재하므로 안전한 상태이다.

장점

교착상태 회피는 교착상태 예방에 비해 자원 할당이 더 자유롭다. 따라서 시스템에서 자원 효율이 높아진다. 또한 후에 논의될 교착상태 발견에 비해 자원을 선점하고 프로세스 수행의 롤백(rollback)이 필요 없다는 장점이 있다.

단점

• 각 프로세스들이 사용할 최대 자원 요구량을 미리 운영체제에 알려주어야 한다.
• 프로세스들은 서로 독립적이어야 한다. 즉 프로세스들 중에 한 프로세스는 다른 프로세스에 비해 먼저 수행되어야 한다는 것과 같은 수행 순서 종속 관계가 없어야 한다.
• 자원 개수가 고정되어 있어야 한다.
• 자원을 선점한 채 종료되는 프로세스는 없어야 한다.

5. 교착상태 발견

교착상태 예방 전략은 교착상태가 발생하지 않도록 하기 위해 자원 접근에 대한 제한과 프로세스의 수행에 제한을 둔다. 반면, 교착상태 발견 전략은 자원 접근에 대한 제한이나 프로세스의 행위에 제한을 두지 않는다. 즉 자원 할당이 가능한 상황이면 항상 할당을 해 준다. 단 교착상태 발견 방법은 주기적으로 시스템에 환형 대기조건이 발생하였는지 검사하고, 만일 발생하였으면 그것을 해결해 준다.

5.1 교착상태 발견 알고리즘

교착상태 발견은 자원 할당이 요구될 때마다 매번 수행될 수도 있고, 주기적으로 가끔 수행될 수도 있다. 자원 할당이 요구될 때마다 매번 수행되면 교착상태를 빠른 시점에 발견할 수 있으며, 또한 시스템의 상태가 점진적으로 변하기 때문에 발견 알고리즘도 간단해 진다는 장점이 있다.
반면, 매번 시도될 때마다 발생하는 처리 비용이 커진다는 단점이 있다.

5.2 교착상태 회복 알고리즘

교착상태가 발견되면 이를 해결하기 위한 기법이 필요하다. 교착상태 회복 방법에는 다음과 같은 것이 있다.

1. 교착상태에 포함되어 있는 모든 프로세스들을 중지시킴. (실제로 많은 운영체제에서 사용하고 있는 방법 중에 하나)
2. 교착상태에 포함되어 있는 각 프로세스의 수행을 롤백시킴. 즉, 미리 정의된 특정 체크포인트 시점까지 되돌린 후 다시 수행시킨다. 이 방법의 단점은 다시 수행시켰을 때 다시 교착상태에 빠질 수 있다는 것이다. 하지만 병행 처리의 비결정 특성은 이 가능성을 적게 한다.
3. 교착상태가 없어질 때까지 교착상태에 포함되어 있는 프로세스들 하나씩 종료시킴. 종료시킬 프로세스의 선택은 비용이 가장 적은 것으로 한다. 하나씩 종료시킨 후 교착상태 발견 알고리즘을 다시 수행시켜보면 아직 교착상태가 존재하는지 여부를 알 수 있다.
4. 교착상태가 없어질 때까지 교착상태에 포함되어 있는 자원을 하나씩 선점시킴. 자원 선택은 3에서와 같이 비용이 가장 적은 자원부터 선택한다. 그리고 하나씩 선점한 후 교착상태 발견 알고리즘을 수행시켜 아직 교착상태가 존재하는지 파악한다. 이때 자원을 선점 당한 프로세스는 자원을 할당 받기 전 시점으로 롤백하고, 그 시점부터 다시 수행한다.

방법 3에서 프로세스의 선택은 다음과 같은 기준을 적용할 수 있다.

• 지금까지 사용한 처리기 시간이 적은 프로세스부터
• 지금까지 생산한 출력량이 적은 프로세스부터
• 이후 남은 수행시간이 가장 긴 프로세스부터
• 할당받은 자원이 가장 적은 프로세스부터
• 우선순위가 낮은 프로세스부터