[운영체제] 동기화와 교착상태 - 4. 교착상태와 해결 방법

교착 상태

교착 상태는 시스템 내에서 두 개 이상의 프로세스가 서로의 작업을 완료하기 위해 상대방이 점유하고 있는 자원을 기다리며 무한정 대기하는 상황을 말한다. 즉, 교착 상태(deadlock)는 일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰 버리는 현상을 의미한다. 

 

교착 상태 발생 조건 

교착상태가 발생하기 위한 네 가지 조건은 상호 배제, 점유와 대기, 비선점, 원형 대기이다. 이 중 하나라도 만족하지 않는다면 교착 상태는 발생하지 않고, 네 가지 조건이 모두 만족할 때 교착 상태가 발생할 가능성이 생긴다. 

• 상호배제
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상호 배제의 상황에서 교착 상태가 발생한다.
• 점유와 대기
  • 한 프로세스가 어떤 자원을 할당받은 상황(점유)에서 다른 자원을 할당받기를 기다린다면(대기) 교착 상태가 발생할 수 있다. 즉, 점유와 대기의 상황인 것이다.
• 비선점
  • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우(비선점) 교착 상태가 발샐할 수 있다.
• 원형 대기 
  • 프로세스와 프로세스가 요청한 자원이 원의 형태를 이루는 경우이다. 다음 처럼 원의 형태로 점유한 자원을 대기할 경우 교착 상태가 발생할 수 있다.

 

 

교착 상태 해결 방법

 

1. 교착 상태 예방 

교착 상태 예방은 앞서 설명한 "교착 상태를 발생하기 위해선 4가지 필요 조건를 모두 만족해야 한다."에서 하나를 충족 못 시키게 하는 것이다. 즉, 하나라도 충족을 못 시키게 만들어 애초에 교착 상태가 발생하지 않도록 하는 방법이다.

• 상호 배제 : 모든 자원을 프로세스들이 공유(전역)하게 만들 순 없다. 그렇기 때문에 현실적으로 모두 없애는 것이 불가능하다.
• 점유와 대기 : 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. 자원의 활용도가 낮아지는 단점을 가지고 있다. ex) 철학자 게임에서 먹을 수 있는 가능성이 있는 경우에만 모든 포크를 들게 하고, 기다려야 한다면 한 개의 포크도 들지 않게 한다.
• 비선점 : 선점이 가능한 자원에 한해 효과적이나 모든 자원이 선점 가능한 것은 아니다.
  ex) 프린터나 데이터베이스 락의 경우 독점하여 작업하고 있다면, 다른 프로세스가 선점할 수 없다.
• 원형 대기 : 자원에 번호를 매기고 오름차순으로 자원을 할당 받게 한다.
  • 1번 포크 → 2번 포크 → 3번 포크..... → 5번 포크에서 다시 1번 포크는 잡지 못한다. (원형 대기를 없앤다.)
  • 위 3가지 방식에 비해 현실적인 방식이지만  어떤 자원에 어떤 번호를 붙이느냐에 따라 자원 활용률이 달라지게 된다.(비효율성이 높아질 수도 있다.)
  
  

  

교착 상태 조건을 만족시키지 못하게 함으로 교착 상태를 방지할 순 있지만 자원 낭비가 가장 심한 기법이다.

 

2. 교착 상태 회피

교착 상태 회피는 한정된 자원에서 "무분별한 할당이 진행될 경우 교착 상태가 발생할 수 있다"는 전제를 바탕으로 한다. 그렇기 때문에 교착 상태가 발생하지 않도록 자원 할당을 신중히 관리하는 기법이다.

 

교착 상태 회피를 알기 위해선 다음 용어를 알고 있어야 한다.

• 안전 상태(Safe State):
  • 시스템이 모든 프로세스가 교착 상태에 빠지지 않고 완료될 수 있는 자원 할당 상태
• 비안전 상태(Unsafe State):
  • 교착 상태가 발생할 가능성이 있는 자원 할당 상태

교착 상태 회피 기법은 자원을 할당하기 전에 시스템이 안전 상태를 유지할 수 있을지 판단한다. 안전 상태를 유지할 수 없다면 자원을 할당하지 않는다. 

 

대표적인 교착 상태 회피 알고리즘에는 은행원 알고리즘(Banker's Algorithm)이 있다. 

은행원 알고리즘
- 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
- 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태는 `안전상태`, 교착상태가 발생할 수 있는 상태는 `불안전 상태`라고 한다.
- 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
- 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.

 

 

3. 교착 상태 검출 후 회복

이전에 나온 예방과 회피 방법이 사전에 교착 상태를 막기위한 예방이었으면, 교착 상태 검출 후 회복은 교착 상태가 발생을 인정하고 사후 조치에 해당한다. 

 

그렇기 때문에 프로세스가 자원을 요구하면 일단 할당 후 교착 상태가 발생(검출)하면 회복하는 방식으로 처리가 된다.

 

교착상태를 회복하는 방법은 두 가지가 있다. 

• 선점을 통한 회복
  교착상태가 해결이 될 때까지, 다른 프로세스로부터 강제로 자원을 빼앗아 한 프로세스에 몰아서 할당하는 방식이다.
• 프로세스 강제 종료를 통한 회복
  교착 상태에 놓인 프로세스 모두를 강제로 종료하는 방식이 있고 작업 내역을 잃을 위험성이 존재한다. 또 다른 방법으론 해결될 때까지 한 프로세스씩 강제 종료하는 방식이 있다. 이 방식은 한 프로세스 종료하고 교착 상태가 해결되었는지 확인하는 작업이 추가적으로 필요해 오버헤드가 발생할 수 있다.

 

참조

https://fastcampus.co.kr/dev_online_newcomputer

초격차 패키지 : 현실 세상의 컴퓨터공학 지식 with 30가지 실무 시나리오 | 패스트캠퍼스