6장 - 교착상태 (Dead Lock)

Dead Lock 이란?

 - 교착상태 (Dead Lock)란, 프로세스간 자원을 점유하고, 또 다른 필요한 자원을 점유하기 위해 대기하는 과정에서 무한히 대기하여 프로세스 처리를 못하는 현상을 이야기한다.

 

교착 상태의 발생?

- 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생한다.

 

자원 할당 그래프(하이퍼링크 예정)

 

Dead Lock 의 4대 필요조건

1. 상호 배제 (Mutual Exclusion)

한 자원에 대한 여러 프로세스의 동시 접근 불가

 

2. 점유와 대기 (Hold And Wait)

자원을 가지고 있는 상태에서 다른 프로세스가 사용하고 있는 자원의 반납을 기다리는 것

 

3. 비선점 (Non Preemptive)

다른 프로세스의 자원을 강제로 가져올 수 없음

 

4. 환형 대기 (Circle wait)

각 프로세스가 순환적(환형 및 사이클)으로 다음 프로세스가 요구하는 자원을 가지고 있는 것

 

 

교착 상태 해결 방법

1. 교착 상태 예방 (Prevention)

교착 상태를 유발하는 네 가지 조건을 무력화 

 

2. 교착 상태 회피 (Avoidance)

교착 상태가 발생하지 않는 수준으로 자원을 할당

 

3. 교착 상태 검출 (Detection)

자원 할당 그래프를 사용하여 교착 상태를 발견

 

4. 교착 상태 회복 (Recovery)

교착 상태를 검출 한 후 해결

 

** 예방, 회피는 서로 다른 방법이지만, 검출, 회복은 [ 검출 -> 회복 ] 으로 한 쌍의 단계로 이해하는 것이 수월함

 

 

1. 교착 상태 예방

1) 상호 배제 예방

독점적으로 사용할 수 있는 자원이라는 개념 자체를 삭제 

 

문제점 : Lock, UnLock과 같은 임계구역에서의 자원을 독점적으로 사용하지 않으면, 데이터가 처리 순서에 따라 다르게 결과를 리턴. 즉, 데이터를 신뢰할 수 없어짐

 

2) 비선점 예방

모든 자원을 빼앗을 수 있도록 하는 개념

 

문제점 : 자원을 빼앗을 수 있다면, 상호 배제 또한 보장할 수 없음. 그러므로 시스템의 모든 자원에 적용하기는 어려움

또한, 빼앗을 수 있다고 할지라도, 이전에 빼앗긴 프로세스가 바로 빼앗을지, 빼앗은 다음엔 얼마나 쓸 수 있을지. 계속 빼앗기만 하면 어떻게 될 것인지. 라는 문제가 발생함

 

3) 점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 개념

-> 한 꺼번에 동시에 점유와 반납 (동시에 할 수 있다면 처리, 못한다면 반납) 

 

문제점 

1. 프로세스가 한번에 모든 자원을 선점한 후, 추가적으로 필요한 자원이 있을때, 확보하기가 어렵다.

2. 당장 사용하지 않을 자원을 선점해놓아야하기 때문에 활용성이 떨어진다.

3. 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.

4. 일괄 작업 방식으로 처리되어 시스템 비효율성을 초래한다.

 

4) 환형 대기 예방

개념 : 점유와 대기를 환형으로 하지 못하게 하는 개념

 

문제점

1. 프로세스 작업 진행에 유연성이 떨어짐
2. 자원의 번호 부여에 고민이 필요함

 

환형 대기 예방 방식에 대한 설명

1. 시스템 자원에 숫자 등을 부여

2. 프로세스들이 자원을 사용하려 할 때, 작은 번호 자원 할당

3. 큰 번호 자원을 할당

ex) 마우스(1)를 할당 후, 하드 디스크 할당(2) :: OK

     하드디스크(2)를 할당 후, 마우스 할당(1) :: NO

[1-1. 환형 대기 예방]

ex2) 프로세스 적용

[1-2. 프로세스 적용의 예]

실선 : 프로세스가 자원을 점유한 상태

점선 : 프로세스가 자원을 대기하는 상태

 

설명

1. P1은 R1을 이미 점유 R2가 필요한 상황

2. 대기를 하면 R2를 가진 P2의 프로세스가 종료시 P1이 사용할 수 있음

3. 단 우선순위가 낮은 R1을 점유하고 R2 대기를 허용(P1 은 허용됌)

4. P2는 R2를 먼저 점유 R1이 필요한 상황

5. P2는 R1을 대기할 수 없음 자원 반납

6. P2는 R1,R2의 점유순서를 바꾸는 것이 아니라면 끝낼 수 없는 프로세스

 

2. 교착 상태 회피

프로세스에 자원을 할당할 때 어느 수준이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 이하 수준으로 자원을 나누어주는 방법

 

교착 상태 회피는 할당된 자원의 수를 기준으로 구분

1. 안정 상태 (Safe State)

2. 불안정 상태 (UnSafe State)

 

문제점 

1. 프로세스가 자신이 사용할 모든 자원을 미리 선언할 필요가 있음

2. 시스템의 전체 자원 수가 고정적이어야 함

3. 자원의 낭비

 

[이미지 2-1. 안정, 불안정 상태]

 

은행원 알고리즘

-> 교착 상태 회피 알고리즘으로 사용. 은행이 대출해주는 방식과 유사함

 

변수

1. 전체 자원(Total) 

시스템 내 전체 자원 수

 

2. 가용 자원(Available)

시스템 낸 현재 사용할 수 있는 자원의 수

(가용자원 = 전체 자원 - 모든 프로세스의 할당 자원)

 

3. 최대 자원(Max) 

각 프로세스가 선언한 최대 자원의 수

 

4. 할당 자원(Allocation)

각 프로세스에 현재 할당된 자원의 수

 

5. 기대 자원(Expect)

각 프로세스가 앞으로 사용할 자원의 수

(기대자원 = 최대 자원 - 할당 자원)

 

조건

1. 각 프로세스의 기대 자원과 비교하여 가용 자원의 하나라도 크거나 같으면 할당

-> 이 의미는 즉 끝낼 프로세스가 있다는 것

 

2. 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않음. 가용 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 없다는 의미 즉, 불안정 상태

 

 

[이미지 2-1. 은행원 알고리즘 - 안정 상태]

1. Total 시스템 자원 수 14, 가용 자원은 2 임. 즉 앞으로 남은 기대 자원이 2 일때 프로세스를 처리할 수 있음

2. P2의 기대자원이 2, 가용자원은 기대자원으로 할당하고 P2를 처리함 

3. P2가 처리되면 Allocation으로 묶고있는 자원 4와 빌려주었던 2를 반납받아 6의 가용자원이 생김

4. 가용자원 6으로 우선순위에 따라 P1 또는 P3을 처리하여 교착상태를 회피할 수 있음

 

[이미지 2-2. 은행원 알고리즘 - 불안정 상태]

1. 가용자원이 1 이하인 프로세스를 확인

2. 처리할 수 있는 프로세스가 존재하지 않음

3. 불안정 상태 -> 교착 상태로 빠짐

 

3. 교착 상태 검출

- 교착 상태인지 검사하여 검출해내고, 교착 상태시 회복 상태로 루프시키는 과정

 

방법

1. 타임아웃을 이용한 교착 상태 검출

2. 자원 할당 그래프를 이용한 교착 상태 검출

 

타임아웃을 이용한 교착상태 검출

- 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생했다고 간주하여 처리하는 방법

주로, 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것

 

문제점

1. 엉뚱한 프로세스가 강제 종료될 수 있음

단순한 시간으로 처리하기 때문에 다른 이유로 멈춘 프로세스를 교착상태로 간주하여 꺼버릴 수 있음

 

2. 모든 시스템에 적용할 수 없음

한 운영체제에서 실행되는 프로세스는 적용될 수 있겠지만, 여러 운영체제에서 실행되어 DB에 데이터를 저장하는 분산 처리시스템에는 적용하기가 어려움. 

이러한 시스템에서는 프로세스가 멈춘 원인을 정확히 파악할 수 없음.

이럼에도 불구하고 타임아웃을 이용한 교착상태 검출 방식을 사용하는데, 이는 자원할당 그래프를 이용한 방법의 작업량이 너무 많아서 그렇다고 함

 

 

데이터베이스의 교착상태 처리

- DB는 데이터의 일관성이 무엇보다도 중요함. 반드시 잠금을 얻은 후 데이터를 조작해야 함

 

체크포인트 : 잠금 상태를 얻은 그 상태의 데이터를 저장. 어떤 문제가 생길 시 돌아오기위한 표시

스냅 숏 : 체크포인트가 찍힌 상태의 데이터

롤백 : 어떠한 문제가 발생했을 때, 체크포인트로 돌아오는 과정

 

[이미지 3-1. 체크 포인트, 스냅숏, 롤백]

그림에 나와있듯, 타임 아웃 발생하면 "롤백" , 발생하지 않으면 그대로 "입력" 이 이루어지는 과정

 

자원할당 그래프를 이용한 교착상태 검출

[이미지 4-1. 교착 상태가 없는 자원 할당 그래프]

위 이미지 4-1의 구성을 살펴보면 다음과 같다.

P1 : R1 점유, R2 대기

P2 : R2 점유

P3 : R3 대기

P4 : R3 점유, R1 대기

 

이러한 구성에서 P2가 처리 -> R2를 P1이 점유 -> P1 처리 -> R1을 P4가 점유 -> P4처리 -> P3가 R3점유 -> P3 처리

순서로 교착상태가 발생하지 않고 처리가 이루어진다. 

이런 자원할당 그래프에서 교착상태를 확인하기 위해 사이클(환형)이 구성되어있는지 확인해야 한다.

아래가 사이클이 구성된 자원 할당 그래프 이다.

 

[이미지 4-2. 교착 상태가 있는 자원 할당 그래프]

위 이미지 4-2의 구성을 살펴보면 다음과 같다.

P1 : R1 점유, R2 대기

P2 : R2 점유, R3 대기

P3 : R3 대기 

P4 : R3 점유, R1 대기 

 

이런 경우, P1 - P2 - P4 간 사이클이 발생되었다. 서로의 자원을 점유하여야 처리할 수 있으므로 교착 상태가 발생했다고 할 수 있다.

 

장점 

1. 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악가능

 

문제점

1. 작업에 대한 오버헤드가 매우 큼

-> 줄이기 위해 일정 시간에 한번 검사하는 방식으로 사용하기도 함

 

4. 교착 상태 회복

교착 상태를 유발한 프로세스를 강제 종료하여 교착상태를 회복함

1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료

-> 다시 동시에 작업이 실행시 똑같은 문제가 발생할 수 있음

-> 이러한 작업이 실행되면 그 다음은 순차적으로 작업을 실행하도록 하는 작업이 필요

 

2. 교착 상태를 일으킨 프로세스 중 하나를 선택하여 종료

-> 우선 순위가 낮은 프로세스를 종료

-> 우선 순위가 같은경우 작업 시간이 짧은 프로세스를 먼저 종료

-> 위의 두 조건이 같은경우 자원을 많이 사용하는 프로세스를 먼저 종료

 

** 이러한 강제 종료 이후에는 프로세스가 원래 작업 전으로 돌아가는 행동을 취해야하는데 이는 [이미지 3-1]과 같이

체크포인트를 이용해 스냅숏을 찍은 뒤 롤백하는 형식으로 돌아가도록 한다.