[운영체제] Deadlock and Starvation

Principles of Deadlock

교착상태(deadlock)이란 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태로 정의된다.

 

 

 

 

Reusable Resources(재사용 가능한 자원)

 

- 프로세스의 사용에 의해 없어지지 않는 자원

 

- 프로세스가 사용한 후 다른 프로세스가 다시 사용할 수 있도록 반납하게 된다.

 

- 처리기, 입출력 채널, 주/보조 메모리, 장치, 파일이나 데이터베이스나 세마포어와 같은 자료 구조들이 재사용 가능한 자원의 대표적인 예이다.

 

- Deadlock(교착 상태)은 자원을 가지고 있는 한 프로세스가 다른 자원을 요청할 때 발생한다. 

 

 

예시1

 

만약 수행 순서가 위와 같이 p0 -> p1 -> q0 -> q1 -> p2 -> q2 순서로 되면 교착 상태가 발생한다.

 

예시2

 

만약 200KB의 가용 메모리가 있는 상태라고 할때 두개의 프로세스가 수행된다고 가정할 때,

P1이 첫 번째 요청이 수행되고, P2이 첫 번째 요청이 수행된 뒤, 두 번째 요청이 발생하면 두 프로세스 모두 블록된다.

 

 

Consumable Resources(소모성 자원)

- 생성되었다가 사용된 이후 소멸되는 자원

 

- 소모성 자원에는 개수의 제한이 없다.

 

- 인터럽트, 시그널, 메시지, I/O 버퍼에 존재하는 정보가 소모성 자원의 대표적인 예이다.

 

- Deadlock은 다양한 조건들의 조합이 모두 만족되어야 발생하는 것도 있다.

 

 

예시1

각 프로세스는 상대 프로세스로부터 메시지 수신을 기다린다. 그리고 메시지 수신 이후 상대 프로세스에게 새로운 메시지를 전달한다.

 

두 프로세스 모두 수신을 먼저 수행하기 때문에, 만일 수신 프리미티브가 블록킹 타입이라면 (수신 프로세스가 메시지가 올 때까지 대기하는 유형) 교착상태가 발생한다.

 

 

4 Conditions for Deadlock (교착상태 조건)

1. Mutual Exclusion (상호 배제 조건)

한 순간에 한 프로세스만이 자원을 사용할 수 있다.

 

2. Hold and wait (점유대기 조건)

이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다.

 

3. No preemption (비선점 조건)

프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다.

 

 

위 세 가지 조건이 만족되면, 교착상태가 발생할 수 있다. 하지만 위 세 조건만으로는 교착상태가 실제로 발생하는 것이 아니다. (필요조건)

 

 

4. 환형 대기 (Circular wait)

프로세스들 간에 닫힌 연결(closed chain)이 존재한다. 즉 자원 할당 그래프에서 환형이 만들어 지는 것이다.

 

 

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

 

교착상태 가능	교착상태 발생
1. Mutual Exclusion 2. Hold and wait 3. No preemption	1. Mutual Exclusion 2. Hold and wait 3. No preemption 4. Circular wait

 

 

이를 해결하기 위한 다양한 접근 방법들이 제안되었다.

 

 

1. Deadlock Prevention

- 교착상태의 발생 조건 1~4 중에 하나를 시스템에서 허용하지 않는 것이다.

 

2. Deadlock Avoidance

- 현재 자원 할당의 상태에 따라 안전하게 자원 할당을 결정하는 것이다.

 

3. Deadlock Detection

- 교착상태가 발생하면 그것을 발견하고 회복하는 것이다.

 

 

 

 

Deadlock Prevention (교착상태 예방)

교착상태가 발생할 가능성을 없애는 것이다.

 

1. Mutual Exclusion (상호 배제)

상호 배제 조건을 없앨 수는 없다. 상호 배제 조건은 공유자원의 일관성을 유지하기 위해 반드시 필요하기 때문에, 자원 접근에서 상호 배제가 필요하면 운영체제가 이를 지원해 주어야 한다.

 

2. Hold and Wait (점유대기 조건)

- 프로세스는 자신이 사용할 모든 자원을 한순간에 요청한다.

 

하지만 이는 다음과 같은 비 효율성이 나타난다.

1. 모든 자원을 할당받기 위해 오래 기다릴 수 있다. 즉,  프로세스는 모든 자원의 할당이 가능할 때까지 대기해야 한다.

2.  실제로 이용되지 않으면서 점유되어 있는 경우가 있다.

3. 프로세스가 미래에 사용될 모든 자원을 미리 알기는 어렵다.

 

 

3. No Preemption (비선점)

1. 자원을 점유한 프로세스가 다른 자원을 요청했을 때 할당받을 수 없다면, 일단 자신이 점유한 자원을 반납한다.

 

2. 한 프로세스에서 다른 프로세스가 점유한 자원을 원하면, 운영체제는 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에게 할당할 수 있다.

 

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

 

 

4. Circular Wait (환형 대기)

환형대기 조건은 자원들의 할당 순서를 정하면 없앨 수 있다.

 

만일 프로세스가 자원 R을 할당받았다면, 이후 이 프로세스는 자원 R 다음 순서를 갖는 자원들을 요청할 수 있는 것이다.

 

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

 

 

 

Deadlock Avoidance (교착상태 회피)

프로세스가 자원을 요청하고 그 자원이 사용가능할 때 그대로 할당해 주지 않는다.

할당 전에 이 할당이 교착상태를 발생시킬 가능성이 있는지 동적으로 조사하고, 교착상태를 발생시킬 가능성이 있다면 자원을 할당하지 않는다.

 

현재 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고있어야 가능하다.

 

 

Deadlock Avoidance의 두 가지 접근 방법

 

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

 

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

 

 

 

Process Initiation Denial (프로세스 시작 거부)

 

 

 

 

위에 있는 사진부터 1번, 2번, 3번이라할 때

 

1. 모든 자원은 가용하거나 할당되어 있다. (이 식은 가용 자원과 할당된 자원의 합이 결국 그 자원의 전체 개수와 동일함을 의미)

 

2. 프로세스는 자원의 전체 개수보다 더 많은 개수의 자원을 요구할 수 없다.

 

3. 프로세스는 자신이 요구한 자원보다 더 많은 개수의 자원을 할당할 수 없다.

 

 

새로운 프로세스와 기존의 프로세스들이 요구하는 자원의 개수가 그 자원의 전체 개수보다 적을 경우에 수행을 허용한다.

 

 

 

Resource Allocation Denial (자원 할당 거부)

Banker's Algorithm을 통해 알아보자.

시스템의 상태를 안전한 상태(safe state), 불안전한 상태(unsafe state)로 구분한다.

 

safe state : 교착상태가 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 진행 경로가 존재함을 의미

 

unsafe state : 그러한 진행경로가 없는 상태

 

 

 

 

 

 

 

 

이므로 safe한 상태라고 볼 수 있다.

 

 

장점

교착상태 회피는 교착상태 예방에 비해 자원 할당이 더 자유롭다.

자원을 선점하고 프로세스 수행의 롤백이 필요 없다는 장점이 있다. 

 

 

단점

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

 

 

Deadlock Detection (교착상태 발견)

 

자원 할당이 가능한 상황이면 항상 할당을 해준다. 

주기적으로 운영체제는 데드락이 발생할지 발견하는 알고리즘을 수행한다.

 

 

Algorithm

Q : 요청 행렬

 

1. 할당 행렬에서 행의 값이 모두 0인 프로세스를 우선 표시한다.

 

2. 임시벡터 W를 만들고, 현재 사용 가능한 자원의 개수를 벡터 W의 초기 값으로 설정한다.

 

3. 표시되지 않은 프로세스들 중에서 요청 행렬 Q의 특정 행의 값이 모두 W보다 작은 프로세스를 찾는다.

 

4. 단계 3의 조건을 만족하는 행을 Q에서 찾으면, 할당 행렬에서 그 행에 대응되는 값으로 W를 갱신한다.

 

 

 

 

1. P4는 할당받은 자원이 없다. 따라서 P4를 표시한다.

 

2. W = (0 0 0 0 1)로 초기화 한다.

3. P3의 요청을 W가 만족할 수 있다. 따라서 P3을 표시하고, W = W + (0 0 0 1 0)를 수행한다.

즉, (0 0 0 1 1)이 된다.

 

4. 표시가 되지 않은 프로세스들 중에서 W로 요청을 만족할 수 있는 프로세스가 더 이상 없다. 따라서 알고리즘이 종료된다.

 

 

끝난 후에는 P1과 P2가 표시가 되지 않은 상태로 남아 있으며, 결국 P1과 P2가 교착상태에 있음을 발견할 수 있다.

 

 

 

Deadlock Recovery Algorithm (교착상태 회복 알고리즘)

1. 교착상태에 포함되어 있는 모든 프로세스들을 중지시킴.

 

2. 교착상태에 포함되어 있는 각 프로세스의 수행을 롤백시킴. 즉, 미리 정의된 특정 체크포인트 시점까지 되돌린 후 다시 수행한다.

 

3. 교착상태가 없어질 때 까지 교착상태에 포함되어 있는 프로세스들 하나씩 종료시킴.

 

4. 교착상태가 없어질 때 까지 교착상태에 포함되어 있는 자원을 하나씩 선점시킴.

 

 

 

Selection Criteria Deadlocked Process (프로세스 선택 기준)

 

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