서론

몇가지 종류의 교착 상태 (DeadLock) 에 대해 알아보고, 이들이 어떻게 발생하는지, 예방하거나 회피하는 방법은 무엇이 있는지에 대해 알아보겠다.

자원

자원은 하드웨어 장치일 수도, 정보의 일부분일 수도 있다.

컴퓨터는 서로 다른 획득 가능한 많은 자원들을 가진다.

시간이 지나면서 자원은 획득되고 사용되고 반환된다.

데드락은 프로세스가 자원들에 대해 배타적인 접근을 승인 받았을 때 발생한다.

선점형과 비 선점형 자원들

선점 가능한 리소스 (Preemptable resources)

프로세스로부터 가져와도 문제가 발생하지 않는다.
예) 메모리

선점 불가능한 리소스 (Nonpreemptable resources)

프로세스로부터 가져오면 프로세스가 작업에 실패한다.
예) CD-ROM : CD를 복사하는 와중에 CD 기록장치를 다른 프로세스에게 주면 미완성된 CD가 완성될 것이다.

데드락은 일반적으로 선점 불가능한 리소스 와 관련이 있다.

DeadLock 소개

데드락 정의

한 프로세스들의 집합 내에서 각각의 프로세스가 그 집합 내의 다른 프로세스만이 발생시킬 수 있는 이벤트를 기다리고 있다면
그 집합의 프로세스들은 데드락에 걸려 있는 것이다.
즉, 모든 프로세스들이 기다리고 있기 때문에 그들 중 아무도 집합 내의 다른 프로세스들을 깨울 수 없다.

데드락 발생의 예:

1. 프로세스 A가 리소스 R1을 점유하고 R2를 요청.

2. 동시에 프로세스 B가 R2를 점유하고 R1을 요청.

3. 두 프로세스가 서로의 리소스를 대기하면서 데드락 상태에 빠짐.

대부분의 경우 각 프로세스가 기다리고 있는 이벤트는 현재 그 집합의 다른 프로세스가 소유하고 있는 어떤 자원 이 반환되는 것이다.

이러한 교착 상태를 자원 교착상태 (Resource deadlock) 이라고 한다.

자원 교착상태의 조건

다음 조건이 모두 충족되어야 한다.
하나라도 충족되지 않으면 데드락이 생기지 않는다.

1. 상호 배제 (Mutual Exclusion):

   • 리소스는 한 번에 하나의 프로세스에만 할당될 수 있다.

2. 점유 및 대기 (Hold and Wait):

   • 이미 리소스를 점유한 프로세스가 추가 리소스를 요청할 수 있다.

3. 비선점 (No Preemption):

   • 이미 할당된 리소스를 강제로 가져올 수 없다.

4. 순환 대기 (Circular Wait):

   • 프로세스 간 순환적인 리소스 대기 상태 존재.

DeadLock 모델링

DeadLock 발생하는 경우

DeadLock 발생하지 않는 경우

타조 알고리즘

가장 단순한 접근 방법으로 DeadLock이 발생을 거의 안하니까 그냥 받아들이는 것

타조가 위기를 맞이하면 머리를 모래에 박고 아무런 문제가 없는 척 하는데서 유래되어 '타조 알고리즘' 이라 한다고 한다.

근데 이건 꿩 아닌가?

DeadLock의 탐지 및 회복

DeadLock의 탐지와 회복에 대한 기술이 사용될 때 시스템은 DeadLock의 발생을 예방하려고 노력하지 않는다.

시스템은 DeadLock이 발생할 때 이를 검출하려고 시도하며, DeadLock으로부터 회복하기 위한 조치를 취한다.

여기선 DeadLock을 탐지할 수 있는 방법들과 DeadLock으로부터 회복할 수 있는 방법들에 대해 알아보겠다.

타입마다 자원이 하나인 경우의 DeadLock 탐지

가장 단순한 경우이다.
이러한 시스템은 하나의 스캐너, 프린터, CD 드라이버 등등 각 타입마다 하나의 자원만을 가진다.
(두개 이상의 자원인 경우는 다루지 않겠다)

이런 시스템에서 DeadLock을 탐지하는 방법은 앞에서 본 자원 그래프 를 그리는 것이다.

자원 그래프에서 Cycle 이 발생하면 DeadLock이 생긴 것이다.

DeadLock을 탐지하는 알고리즘

그래프의 각 노드를 차례대로 트리의 루트로 간주하여 DFS(Depth First Search) 를 하는 것이다.

만일 이미 방문했던 노드로 돌아오면 Cycle 이 발견된 것이다.
Cycle 을 만나면 알고리즘은 즉시 멈춘다.

DeadLock 으로부터의 회복

알고리즘이 DeadLock 을 성공적으로 탐지했다고 가정했을 때, 회복하는 방법에 대해 알아보겠다.

1. 리소스 선점 (Recovery through Preemption)

다른 프로세스에서 리소스를 강제로 가져와 데드락을 해소한다.

• 주의점:
  • 리소스의 특성(속성)에 따라 선점이 가능하거나 불가능할 수 있다.

2. 롤백을 통한 복구 (Recovery through Rollback)

• 설명:

  • 프로세스 상태를 주기적으로 체크포인트에 저장한다.

  • DeadLock이 발견되면 저장된 상태로 돌아가 다시 실행한다.

• 세부 절차:

  1. 체크포인트 저장: 프로세스 상태를 주기적으로 저장.

  2. 롤백: 필요한 리소스를 소유한 프로세스를 이전 상태로 복구.

  3. 재시작: 복구된 상태에서 프로세스를 재시작.

• 예:
  필요한 리소스를 소유한 프로세스가 롤백됨으로써 데드락 해소.

3. 프로세스 종료를 통한 복구 (Recovery through Killing Processes)

• 설명:

  DeadLock 을 해결하기 위해 DeadLock 사이클에 포함된 프로세스를 하나씩 종료한다.
  

• 특징:

  • 가장 단순하고 거친 해결 방법.

  • DeadLock 해소를 위해 희생되는 프로세스가 발생.

2. 복구 절차

1. DeadLock 프로세스 종료:

   • 데드락에 연루된 프로세스 중 하나를 선택하여 종료한다.

   • 선택된 프로세스의 리소스는 해제되어 다른 프로세스가 사용할 수 있게 된다.

2. 프로세스 선택 기준:

   • 다시 실행 가능한 프로세스를 선택한다.

   • 종료된 프로세스는 처음부터 다시 실행할 수 있어야 함.

3. 반복:

   • 데드락 사이클이 해결되지 않으면 다른 프로세스를 종료.

   • 사이클이 완전히 깨질 때까지 반복.

장단점

• 장점:

  • 구현이 간단하며 즉각적인 해결책 제공.

• 단점:

  • 종료된 프로세스의 데이터 손실 및 작업 중단 가능성.
  • 시스템 안정성에 영향을 줄 수 있음.

DeadLock 회피

대부분의 시스템에서는 프로세스는 한번에 하나의 자원을 요구한다.

여기서는 항상 올바른 선택을 함으로써 DeadLock을 회피할 수 있는 알고리즘에 대해 알아보겠다.
(이 알고리즘은 어떤 정보를 미리 사용할 수 있는 경우에만 적용가능하다)

자원 궤도

• 가로축은 프로세스 A 에 의해 실행되는 명령어의 수를 나타낸다

  • 가로로 가면 A 실행한다는 뜻

• 세로축은 프로세스 B 에 의해 실행되는 명령어의 수를 나타낸다

  • 세로로 가면 B 실행한다는 뜻

• 모든 점은 두 프로세스의 만남 상태를 나타낸다.

초록색 구역에 진입하는 순간 DeadLock 은 필연적으로 발생한다.
(다시 빠져나갈 수 없고 결국 두개의 자원을 서로 동시에 사용하려고 하므로)

따라서 T 지점에서는 그냥 프로세스 A가 I4 까지 도달할 때 까지 실행하는 것이다.

이때 T 지점에서 B는 플로터를 요청하고 있다. (I5 ~ I7)
시스템은 이걸 승인할지 말지 결정해야 하는데 승인하면 결국 겹치는 구역으로 들어가 DeadLock 이 발생할 것이다.

위의 그림을 자원 그래프로 그려보면 사이클이 생겨서 왜 DeadLock 이 발생하는지 한눈에 알 수 있다.

안전과 불안정 상태

모든 프로세스가 모두 자신이 필요로 하는 최대 수의 자원들을 즉시 요청할지라도 이들이 모두 완료할 때 까지 실행할 수 있는 어떤 프로세스 스케줄링 순서가 존재하면 안전한 상태 라고 말한다.

주의할 점은 불안전한 상태라고 DeadLock인 것은 아니다.

안전한 시스템은 모든 프로세스들이 완료하는 것을 보장할 수 있다는 뜻이며
불안전한 상태에서는 그런 보장을 할 수 없다는 것이다.

단일 자원에 대한 은행원 알고리즘

각 단계마다 할당을 했을 때 안전한 상태가 되면 할당을 승인하고

불안정한 상태가 되면 할당을 거부하는 알고리즘이다.

DeadLock 회피 알고리즘이 비효율적인 이유

• 프로세스의 최대 자원 요구량을 사전에 알 수 없는 경우가 많다.

  대부분의 프로세스는 실행 전에 필요한 자원의 최대치를 미리 정의하지 않는다.

• 프로세스의 개수가 고정되어 있지 않고 동적으로 변한다.

  시스템에서 실행되는 프로세스는 동적으로 생성되거나 종료되므로 고정된 환경을 가정할 수 없다.

• 리소스가 갑자기 사용할 수 없게 될 수 있다.

  하드웨어 오류나 시스템 장애로 인해 리소스가 갑자기 사라지는 상황이 발생할 수 있다.

DeadLock 예방

데드락 예방: 상호 배제 조건 제거

1. 방법: 일부 장치를 스풀링 (Spooling)

스풀링(Spooling)은 "Simultaneous Peripheral Operations On-Line"의 약자로, 입출력 작업을 효율적으로 처리하기 위해 사용하는 버퍼링 기법 을 의미

• 설명:

  • 일부 장치(예: 프린터)는 스풀링 을 통해 관리될 수 있다.

  • 프린터 데몬만 프린터 리소스를 직접 사용하도록 설정.

  • 이를 통해 프린터에 대한 데드락을 방지할 수 있다.

• 제한 사항:

  • 모든 장치가 스풀링될 수 있는 것은 아니다.

2. 원칙 (Principle)

• 불필요할 경우 리소스를 할당하지 않는다.

  • 꼭 필요하지 않은 경우 리소스 사용을 피한다.

• 최소한의 프로세스만 리소스를 요청하도록 한다.

  • 실제로 리소스를 사용해야 하는 프로세스만 자원을 요청하게 하여 데드락 가능성을 줄인다.

데드락 예방: 점유 및 대기 조건 제거

1. 방법: 모든 리소스를 시작 전에 요청 (Request All Resources Before Starting)

• 설명:

  • 프로세스가 시작되기 전에 필요한 모든 리소스를 한 번에 요청하도록 강제.

  • 이를 통해 실행 중에 추가 리소스를 기다릴 필요가 없게 된다.

2. 문제점

• 필요한 리소스를 미리 알 수 없는 경우가 많다.

  • 실행 초기에 필요한 모든 자원을 정확히 예측하기 어려움.

• 리소스를 다른 프로세스가 사용할 수 없게 한다.

  • 프로세스가 사용하지 않는 리소스를 점유하여 다른 프로세스의 실행을 방해할 수 있다.

3. 변형 방법: 모든 리소스를 반환한 뒤 다시 요청 (Release and Re-request All Resources)

• 설명:

  • 프로세스는 현재 점유 중인 모든 리소스를 반환하고, 즉시 필요한 모든 리소스를 한 번에 다시 요청한다.

  • 이를 통해 점유 상태에서 대기하는 상황을 방지한다.

데드락 예방: 비선점 조건 공략

뭐 딱히 방법은 없다

프린터를 쓰던 프로세스로부터 프린터를 강제로 뺐을 수는 있지만
프린터를 쓰던 중이었으므로 이걸 도중에 뺐는다고 사용할 수가 없다.

데드락 예방: Circular Wait Condition 공략

조건1

프로세스는 어떤 순간에 하나의 자원만 보유할 권리가 있다고 규칙을 정하면 된다.

두번째 자원이 필요하다면 첫번째 것을 반환해야만 한다.

조건 2

이렇게 자원에 번호를 할당하고 순차적으로 요청을 하면 된다.

그림 b에서 i, j 는 서로 다른 자원이므로 번호가 다를 것이고.

만약 i>j 라면 A가 j를 요청하지 못한다. (j 번호가 낮으므로)

마찬가지로 i<j 라면 B가 i를 요청하지 못한다.