[운영체제] 교착 상태(정의, 필요조건, 예방, 회피, 탐지-복구)

본 게시글은 대학 전공수업을 들으며 노션에 정리한 내용을 블로그로 옮긴 게시글 입니다.

교착상태 정의 및 특성, 예방, 회피, 복구

교착상태

프로세스의 자원 사용 절차

자원 사용 요구 → 사용 → 해제

요구과정에서 가용한 자원이 없으면 → 자원을 획득할 떄 까지 대기

⇒ 교착상태(deadlock) 발생

정의

여러개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느쪽도 영원히 진행되지 못하는 상태

https://www.boardinfinity.com/blog/deadlock-in-operating-system/

기아상태와의 비교

기아상태는 꼬리물기라고 했다. 꼬리물기가 끊기면 진행할 수 있다. 즉, 희망이 있다!

하지만 교착상태는 A가 B를 기다리고, B는 A를 기다리기 때문에 무한으로 기다려야한다. 즉, 희망이 없다.

교착상태의 특성

교착상태의 필요조건

아래 4가지 조건이 ‘동시에’ 만족될 때 교착상태가 발생될 수 있다.

(’필요조건’이니, ‘발생 가능’상태)

• 상호배제
• 점유대기
• 비선점
• 환형대기

상호배제(mutual exclusion)

• 프로세스가 자원에 대한 배타적인 통제권을 요구
• 적어도 하나 이상의 자원은 여러 프로세스에 의해 동시에 사용될 수 없음
• 다른 프로세스가 점유한 자원이 필요하면 반드시 대기

점유대기(hold and wait)

프로세스가 이미 한 자원을 할당받아 점유하고 있는 상황에서, 다른 프로세스가 점유하고 있는 또 다른 자원을 요구하여 해제되기를 바라는 상황

비선점(no preemption)

프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에는 해제되지 않음

할당된 자원은 타의에 의해서는 해제되지 않음

환형대기(circular wait)

프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기하는 상황

즉, 서로가 서로의 자원만을 원하고 사용하지 못하는 환형 모양의 대기상태

자원 할당 그래프

자원할당 그래프 G=(V,E)

V: 정점의 집합 V = P + R (P와 R은 각각 프로세스 p 와 자원 r의 집합)

E: 방향있는 간선의 집합 E = Q + S

• Q는 프로세스 p가 요구하는 자원 r의 관계 (p,r)의 집합
• S는 자원 r이 할당된 프로세스 p의 관계(r,p) 의 집합

파랑색: 할당, 빨간색: 요구

이 사진에서, p2가 r3를 요구 → 요구간선 (p2, r3) 추가

→ r3 가용시 할당간선 (r3, p2) ‘추가’ : 상호배제(x)

→ r3가 끝나면 할당간선을 (r3 p3)에서 (r3,p2)로 ‘변경’ : 상호배제o

만약 p2가 r1을 요구하였으나, p1이 상호배제라면 ? 사이클이 생김

사이클이 없음 → 교착상태x

사이클 있음 → 교착상태 발생 가능.

위 사진에서 r1 r2, p1,p2는

• 상호배제O (하나의 할당간선)
• 점유 대기O (한 프로세스에 할당간선과 요구간선이 연결됨)
• 비선점O (요구간선)
• 환형대기 : 사이클

교착상태 처리 기법

예방

네가지 필요조건이 동시에 만족되는 것을 피하여 교착상태의 발생을 예방하는 방법

회피

프로세스에 필요한 자원의 최대량에 대한 정보를 이용해 발생하지 않도록 하는 방법

탐지 및 복구

교착상태의 발생 여부를 조사해, 발생한 경우 적절한 조치를 취해 복구 하는 방법

교착상태 예방

상호배제 조건 제거(❌)

공유할 수 있는 자원 : 상호배제 필요 없음

예 : 읽기 전용 파일

공유할 수 없는 자원 : ‘반드시’ 상호 배제 필요

예 : 프린터

⇒ 상호배제 조건 제거하는 방법으로 예방 불가

점유대기 조건 제거(🤔)

• 점유했을 때 대기하지 않아야 함 (’대기’를 제거)
  • 프로세스가 앞으로 필요한 모든 자원을 처음에 한꺼번에 요구하여 할당받음: 공유주방에서 “나는 화구 3개쓰고 오븐도 쓸거니까 모두 쓰지마” 하는 셈
  • ⇒ 자원이용률 낮아짐, 기아상태 가능
• 대기할 때 자원을 점유하고 있지 않아야 함 (’점유’를 제거)
  • 새로운 자원을 요구할 때 할당받았던 자원을 모두 해제
  • ⇒ 점유 도중 해제할 수 없는 자원에는 적용 불가

비선점 조건 제거(❌)

• 선점이 가능 하도록 한다면?
  • 자원의 특성에 따라 불가능한 경우 존재 (예: 프린터)
• 다른 프로세스가 대기할 가능성 줄인다면?
  • 점유대기 상황이 발생하면, 할당받았던 자원을 모두 해제
  • : but, 프린터 같은 자원에는 적용 불가능

환형대기 조건 제거(🤔)

• 모든 자원에 일련번호를 지정
• 함수 f:R → N (R:자원집합, N:자연수 집합)
  • 방법1
    • 프로세스는 자원을 요구할 떄 일련번호 기준으로 항상 오름차순이 되도록 요구.( ri < rj ⇒ f(ri) < f(rj) )
    • ex) 디스크 r1, 프린트 r2가 있다고 할 때, 함수를 통해 부여되는 일련번호도 r1 < r2가 되도록 만듬
  • 방법2
    • 프로세스가 자원을 요구할 때, 그 보다 일련번호가 작은 자원만 점유하도록 함
    • 즉, 자원 rj를 요구하려면 점유중인 자원 중 f(ri) ≤ f(rj)인 자원 rj는 모두 해제함)
      • 단., 점유대기에서 봤듯 점유 도중 해제할 수 없는 자원에는 적용이 불가능 함.

이렇게 만들면, 점유 대기중인 프로세스는 (점유중인 자원의 일련번호 보다) 대기중인 자원의 일련번호가 큼.

⇒ 환형대기 발생 불가능

But! 프로세스마다 요구 순서가 다를 수 있어 자원의 일련번호 설정이 어려움

💡 위 4가지 모두를 살펴봤듯, 교착상태 예방은 가능하나, 예방하지 못하는 경우가 일부 있다!

교착상태 회피

프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태(=안전상태)로 머물도록 하는 방법

사전정보❓

• 현재 할당된 자원
• 가용상태의 자원
• 프로세스들의 최대 요구량

안전상태❓

• 교착 상태를 회피하면서, 각 프로세스에 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태
• 안전 순서열이 존재하는 경우(↔불안전상태 : 안전순서열이 존재하지 않는 경우)

안전순서열❓

순서 있는 프로세스의 집합 P<p1, p2, p3 … pn>이 있을 때,

(1) 임의의 pi가 추가로 요구할 수 있는 자원의 양이 현재 가용상태 자원으로 충당 되거나

(2) pj에 할당된 자원까지 포함하여 충당 가능한 경우

신용카드로 비유하자면, 예정된 신용카드 카드 값이, 현재 가진 돈으로 충당 되거나 예정된 수익까지 포함해서 충당되는 경우 == 안전하다!

따라서, 가용상태의 자원을 요구하더라도 불안전 상태가 예상이 된다면 자원을 주지 않고(=회피한다!)

다른 프로세스에게 자원을 주어 자원이 해제되어 전체 요구량을 줄어들면 그 때 자원을 주면 된다.

안전 알고리즘

• 각 자원의 단위자원이 하나밖에 없는 경우
  • 변형된 자원할당 그래프 이용
• 각 자원의 단위자원이 여러개일 수 있는 경우
  • 은행원 알고리즘 이용

변형된 자원할당 그래프 이용

• 자원할당 그래프에 요구가 예정된 선언간선(점선) 추가
• 자원을 요구 받으면 선언간선을 요구간선으로 변경
  • 요구간선을 할당간선으로 변환해도 사이클이 생기지 않을 때에만 자원을 할당하고 할당 간선으로 변환한다.
  •  
  • 

은행원 알고리즘

• 자원을 요구받으면 그 자원을 할당해주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인
• 안전상태가 보장되는 경우에만 자원을 할당

$MAX_i : p_i의 최대요구 \ ALLOC_i : P_i의 할당자원 \ NEED_i : p_i의 추가요구 \ AVAIL: 가용자원$ 이라고 하면,

자원을 요구 받았을 때 AVAIL - NEED를 뺀 상태값을 계산해보고 안전상태인지 확인하는 방식.

교착상태 탐지 및 복구

• 교착상태 발생 후 처리하는 방법
• 교착상태 탐지
  • 시스템의 교착상태 여부를 조사하기 위해. ㅜ기적으로 상태조사 알고리즘 수행
• 교착상태 복구
  • 교착상태가 탐지된 경우, 적절한 조치를 취해 정상 상태로 복구

탐지

• Shosshani와 Coffman 알고리즘

Work에서, p2를 해결한 후, p1 p2 아무것도 해결할 수 없는 상황 ⇒ 교착상태 탐지

시간복잡도 : O(mn^2)

• 수행 시점
  • 즉시 받아들일 수 없는 자원 요구가 있을 때
  • 정해진 시간간격
  • CPU효율이일정수준 이하로 떨어질 때

복구

: 교착상태가 탐지되면 복구조치

복구의 주체

• 오퍼레이터: 수작업으로 복구
• 운영체제: 자동으로 복구

복구 방법

교착상태 프로세스를 종료

• 모든 교착상태 프로세스를 종료
• ⇒ 진행했던 내용에 대한 복원비용이 큼
• 사이클이 제거될 때까지 교착상태 프로세스를 하나씩 종료
• ⇒ 종료 대상을 선택하기 위한 비용 (매 프로세스 종료 후 교착상태 재확인을 위한 비용)

교착상태 프로세스가 할당받은 자원을 해제

사이클이 제거될 때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에 할당

• 프로세스와 자원 선택 기준은?
  • 프로세스 진척도,사용중인 자원의 수 등
• 프로세스의 복귀 시점도 제반 요소를 고려하여 결정
• 프로세스 선택 시 복구 횟수 고려(기아상태에 빠지지 않도록)