[운영체제] DeadLock(데드락)

안녕하세요 취업길잡이 Coy입니다!

오늘은 DeadLock(데드락)에 대해 알아보도록 하겠습니다

DeadLock(데드락)이란?

프로세스가 자원을 얻지 못하는 상태로, 교착 상태라고도 하며, 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

둘 이상의 프로세스가 각각 자원을 점유하고 있으면서 서로 자원을 기다리고 있을 때 무한 대기에 빠지는 상태를 뜻합니다

DeadLock(데드락) 발생조건 4가지

Case 1) 상호 배제(Mutual exclusion)

최소한 하나의 자원이 한 번에 하나의 프로세스에 점유되어야 합니다. 다른 프로세스가 그 자원을 요청하면 자원이 해제될 때까지 기다려야합니다

 

Case 2) 점유 대기(Holod and wait)

프로세스는 최소한 하나의 자원을 점유한 채, 다른 프로세스에 점유된 자원을 추가로 얻기 위해 대기를 해야합니다

 

Case 3) 비 선점(No preemption)

자원들을 선점할 수 없어야하고 이미 할당 된 자원을 뺏을 수 없습니다

 

Case 4) 순환 대기(Mutual exclusion)

대기하고 있는 프로세스 집합이 순환 형태로 자원을 대기하고 있어야 합니다

DeadLock(데드락) 예방(Prevention) 방법

예방 방법은 발생조건 4가지 중에 하나라도 발생하지 않게 하는 것입니다.

각각의 조건을 방지하는 것으로 예방을 할 수 있습니다

 

Case 1) 상호 배제 방지

여러 프로세스가 공유 자원을 사용할 수 있게 만들어서 프로세스가 공유 가능한 자원을 위해 대기할 필요가 없게 만들면 됩니다.

 

Case 2) 점유 대기 방지

또 다른 자원을 점유하기 위해 대기 조건을 성립하지 않기 위해선 프로세스 실행에 필요한 모든 자원을 한번에 요청하고 할당하도록 해야합니다. 필요한 모든 자원이 있을때까지 프로세스를 실행할 수 없기 때문에 이 방법은 대부분의 프로그램에서 실용적이진 않습니다.

 

Case 3) 비 선점 방지

비선점을 방지하기 위해서는 높은 우선순위의 프로세스에 자원을 우선적으로 선점하게 해주면 됩니다.

 

Case 4) 순환 대기 방지

순환 대기 방지를 위해선 모든 자원 유형에 전체적인 순서를 부여하여 각 프로세스가 순서대로 자원을 요청하도록 하면 됩니다.

위에 적어놓았다시피 예방 방법은 시스템 효율성을 떨어트릴 수 있습니다.

 

DeadLock(데드락) 회피 방법

안전 상태(Safe State)

시스템 상태가 안전(safe)하다는 말은 시스템이 어떤 순서로든 방식이든 프로세스가 요청하는 모든 자원을 데드 락을 야기시키지 않고 모두 할당해줄 수 있다는 것을 뜻합니다.

회피 알고리즘을 통해 자원을 할당한 후에도 시스템을 항상 안전 상태(Safe State)에 있을 수 있도록 하는 것이 기본 원리입니다.

회피 알고리즘으로 대표적인 은행원 알고리즘에 대해 알아보도록 하겠습니다

 

은행원 알고리즘

다익스트라가 고안한 방법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데에서 유래되었습니다

프로세스가 자원을 할당 받고 나서 시스템이 안전 상태(Safe State)에 있는지 미리 검사하는 알고리즘 입니다.

 

DeadLock(데드락) 탐지 및 회복 방법

시스템이 DeadLock(데드락)에 빠졌을 때 탐지하고 회복 알고리즘을 통해 회복합니다.

 

탐지 방법

• 자원할당 그래프를 통해 교착상태를 탐지합니다
• Available, Allocation, Request를 가지고 교착 상태를 탐지할 수 있습니다. 현재 시스템의 자원 상태를 가지고 파악하는 방법으로 은행원 알고리즘과 비슷합니다.

회복 방법

• 프로세스와 스레드 종료 시키기
  • 교착 상태 프로세스를 모두 중지하는 방법
    • 이 방법은 확실하게 교착상태를 없앨 수 있지만 비용이 큽니다. 프로세스가 그 동안 계산했던 데이터들을 다 날리고 다시 시작해야 하기 때문입니다
  • 교착 상태가 제거될 때까지 한 프로세스씩 중지
    • 이 방법은 계속 한 프로세스씩 죽이면서 탐지 알고리즘을 통해 교착상태에서 빠져나왔는지 체크를 해야하므로 오버헤드가 상당히 많이 발생할 수 있습니다.
• 자원 선점하기
  • 희생자 선택(Selection of a Victim)
    • 어느 자원과 어느 프로세스가 선점될지 정하는 방법입니다. 비용을 최소화 하기 위해서 선점의 순서를 결정해야합니다
  • 롤백(Rollback)
    • 프로세스로부터 자원을 선점하면 그 프로세스는 정상적으로 실행할 수 없습니다. 따라서 그 프로세스를 아예 안전한 상태로 롤백시키고 다시 시작하는 방법입니다

요약

• 교착 상태에는 필요한 조건이 상호배제, 점유 대기, 비선점, 순환대기 4가지가 있습니다. 교착 상태는 4 가지 조건이 모두 충족되어야 발생합니다
• 교착 상태에 필요한 4 가지 조건 중 하나가 발생하지 않도록 하여 교착 상태를 예방할 수 있습니다. 그 중가장 현실적인 방법은 순환대기를 제거하는 방법입니다.
• 은행원 알고리즘을 통해 교착 상태를 회피 할 수 있습니다. 이 알고리즘은 자원상태를 체크하여 교착 상태가 발생할 수 있는 자원 할당은 허용하지 않습니다
• 교착상태 탐지 알고리즘은 은행원 알고리즘과 비슷하게 자원 상태를 보고 현재 시스템이 교착 상태인지 탐지합니다
• 교착 상태가 발생하면 시스템은 프로세스를 중단하거나, 자원 선점을 통해 교착 상태에서 회복할 수 있습니다

 

2단계 개념 모음집 목적과 활용법은 아래 글을 읽어보시면 좋습니다

 

2단계 면접 요약정리 카테고리 설명글

 

도움이 필요하시면 사연을 메일로 보내주세요

 

jek300300@gmail.com

 

도움이 되셨다면 공감과 구독 부탁드립니다

 

읽어주셔서 감사합니다

 

당신의 취업이 성공할 때까지 같이 하겠습니다! by 취업길잡이 Coy