[OS] DeadLock(교착상태) 란

운영체제 DEAD LOCK(교착상태) 에 대해서 알아보자

 

교착상태란? 

DEAD LOCK 즉, 교착상태란 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태 즉, 무한히 다음 자원을 기다리게 되는 상태를 말한다. 쉽게 말해 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

 

책에서는 쉬운 예로 Dining philosophers problem( 식사하는 철학자 문제)를 예로 든다.

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

간단하게 생각해, 만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.

 

교착상태가 일어나는 경우

프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정해보자

t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음

t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

 

현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

→ 이것이 바로 DeadLock!!!!!!

 

교착상태(DeadLock) 발생 조건 < 코프만 조건 >

코프만은 1971년 6월 논문에서 컴퓨터 시스템에서 교착 상태를 유발할 수 있는 4가지의 필요충분 조건을 찾아내어 증명하였다. 그의 이론은 아래 4가지 조건을 모두 허용된 컴퓨터 시스템은 언제든 교착상태가 발생할 수 있다는 것이다.

 

1. 상호 배제(Mutual exclusion)

자원은 한번에 한 프로세스만 사용할 수 있음

 

2. 점유 대기(Hold and wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함 

 

3. 비 선점(No preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

 

4. 순환 대기(Circular wait)

프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

 

교착상태(Dead Lock)의 해결법 

교착상태의 해결법에는 4가지가 있다.

 

1. 교착상태 예방(prevention)

교착상태예방은 앞에서 언급한 코프만 4가지 조건 중 하나 이상의 조건이 아예 성립되지 못하도록 시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것이다.

 

2. 교착상태 회피(avoidance)

교착상태 회치는 운영체제가 자원을 할당할 때 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당하여 미래에 교착상태로 가지 않도록 하는 방법이다.

 

3. 교착 상태 및 감지 및 복구(detection and recovery)

교착상태의 예방이나 회피전략을 가동하지 않고, 운영체제가 교착상태를 감지하는 별도의 프로그램을 구동시켜 교착상태에 빠진 스레드 그룹을 발견하면 교착상태로부터 해제하는 방법이다.

 

4. 교착 상태 무시(ignore and reboot)

교착상태 예방, 회피, 감지 및 복구 방법에는 많은 시간과 공간을 필요로 하여 컴퓨터 시스템 성능을 떨어뜨리기 때문에, 또한 범용 시스템에서는 교착상태가 발생한다고 하더라도 파국을 부를 만한 작업을 실행시키지 않기 때문에 아무런 대책없이 교착상태가 발생하도록 내려두는 방법이다. 교착상태 무시 알고리즘을 ostrich 알고리즘(타조 알고리즘) 이라고 부른다.

 

 

Banker's 알고리즘(은행원 알고리즘)

교착상태 회피 방법의 대표적인 알고리즘이다.

Edsger Dijstra에 의해 개발된 알고리즘으로 시스템을 안전한 상태와 불안전한 상태로 나누고, 자원을 할당하였을 때 안전한 상태로만 갈 때만 자원을 할당한다.

이 알고리즘을 사용하기 위해서는 각 스레드는 실행 전에 필요한 전체 자원의 수를 운영체제가 알고 있어야 하는데, 스레드의 실행 전에 필요한 자원의 개수를 아는 것은 사실상 불가능하므로 비현실적인 알고리즘이다.

 

 

Ostrich 알고리즘 (타조 알고리즘)

교착 상태 무시 방법의 대표적인 알고리즘이다.

타조 알고리즘은 교착상태에 대한 아무런 대책 없이 컴퓨터 시스템을 가동시키고, 교착상태가 발생하면 시스템을 재시작(reboot)하거나 특정 스레드를 강제 종료하는 쉬운 방법으로, 교착상태를 해결한다.

컴퓨터 시스템에서 교착상태는 얼마나 자주 발생하는가에 대한 통계치는 없다.

어떤 문헌에서는 1년에 한 번 정도 발생한다고도 하고, 멀티스레드 프로그램을 오래 작성한 개발자들 사이에서는 이보다는 자주 발생한다고도 한다. 교착상태가 발생할 가능성이 극히 적은 반면 교착상태를 피하기 위한 비용이 많이 들어간다면, 굳이 많은 시간과 비용을 소면서 까지 교착상태 예방, 회피, 혹은 감지 복구등의 방법을 사용할 필요가 있을까? 라는 의문에서 탄생한 알고리즘이다.

 

Not everything worth doing is worth doing well.

 

 

 

 

이 글은 <명품 운영체제>를 참고하여 작성하였습니다.