[운영체제-양희재 교수님]14-15강 교착 상태

경성대학교 양희재 교수님의 운영체제 14강

경성대학교 양희재 교수님의 운영체제 15강

교착 상태(Deadlock)

• 프로세스는 실행을 위해 여러 자원이 필요하며 자원의 사용을 기다릴 때 교착 상태 발생 가능
  • 자원: CPU, 메모리, 파일, 프린터 등
• 교착상태 필요 조건(Necessary Conditions)
  • Mutual exclusion(상호 배타)
    • 자원이 이미 사용 중이라면 다른 프로세스는 이를 사용할 수 없다.
  • Hold and wait(보유 및 대기)
    • 자원을 가지고 있는 상태에서 다른 자원을 기다리는 상태
  • No Preemption(비선점)
    • 강제로 자원을 뺏을 수 없는 경우
  • Circular wait(환형 대기)
    • 대기하는 프로세스와 자원이 원형을 이루는 경우
  • 위 네 조건을 만족하는 경우 교착 상태가 일어날 수 있다.
    • 네 조건을 만족하는 경우 무조건 교착 상태가 일어나는 건 아니다.

자원(Resources)

• 동일 형식(type) 자원이 여러 개 존재 가능
  • 이때 각 자원을 instance라 한다.
  • 예) 동일 CPU 2개, 동일 프린터 3개 등
• 자원 사용 절차
  • 요청(request) → 사용(use) → 반납(release)
• 자원 할당도(Resource Allocation Graph)

자원 할당도(Resource Allocation Graph)

• 어떤 자원이 어떤 프로세스에 할당되었는지, 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는지를 그림으로 표현한 것
  • 자원 ⇒ 사각형
  • 프로세스 ⇒ 원
  • 할당 ⇒ 화살표
• 자원 할당도를 통해 교착 상태가 발생할지를 판단할 수 있다.

• 일반적으로 상호 배타, 보유 및 대기, 비선점은 자원 할당도에 적용되어 있다.
• 따라서 자원 할당도 상에 원이 만들어지는 경우 ⇒ 교착 상태의 환형 대기 조건까지 충족 ⇒ 교착상태 발생 가능

교착 상태 처리

교착 상태 방지(Deadlock Prevention)

• 교착 상태 4가지 필요 조건 중 한 가지 이상 만족하지 않도록 만드는 방법
• 상호 배타(Mutual exclusion) ⇒ 자원을 공유할 수 있게 한다.
  • 일반적으로 불가하다.
• 보유 및 대기(Hold & Wait) ⇒ 자원을 가지고 있으면서 다른 자원을 기다리지 않게 한다.
  • 예) 자원이 없는 상태에서 모든 자원이 사용할 수 있을 때까지 대기, 일부 자원만 가용하면 아예 아무 자원을 갖지 않도록 보유 자원을 모두 놓아주기
  • 단점) 자원 활용률 저하, 기아(starvation) 발생 가능성이 커짐
  • 장점) 그나마 실행할 수 있다.
• 비선점(No preemption) ⇒ 자원을 선점할 수 있게 한다.
  • 일반적으로 불가하다.
• 환형 대기(Circular wait)
  • 예) 자원에 번호를 부여하여 오름차순으로만 자원을 요청
  • 단점) 자원 활용률 저하
  • 장점) 그나마 실행할 수 있다.

교착 상태 회피(Deadlock Avoidance)

• 교착 상태의 발생 원인을 잘못된 자원 배분이라 가정하고 이를 해결하는 방법
  • 교착상태 = 자원 요청에 대한 잘못된 승인 ≒ 은행 파산
• 할당 방법
  • 안전한 할당(Safe allocation)
    • 결과적으로 모든 프로세스에 자원을 할당할 수 있는 경우
  • 불안전한 할당(Unsafe allocation)
    • 자원을 전부 할당했는데 프로세스가 끝나지 않아 자원을 돌려받을 수 없고 결과적으로 어떤 프로세스에도 자원을 할당할 수도 없는 경우
    • 교착 상태 발생 가능
• 운영체제는 자원을 할당할 때 불안전한 할당을 하지 않도록 해야 한다.
  • 이 경우는 대출 전문 은행의 경우와 유사하다 ⇒ Banker’s Algorithm

교착 상태 검출 및 복구(Deadlock Detection & Recovery)

• 교착상태가 일어나는 것을 허용한다.
  • 교착 상태는 드물게 일어나기 때문에 발생할 때만 대처한다.
  • 주기적 검사와 교착 상태 발생 시의 복구 필요
• 검출
  • 검사에 따른 추가 부담(overhead)
    • 계산, 메모리 등
• 복구
  • 주기적으로 현재 상태를 기억해 놓아야 교착 상태 발생 시 복구 가능 ⇒ 비용 증가
  • 복구 불가 시 프로세스 일부 강제 종료 또는 자원을 선점하여(빼앗아) 일부 프로세스게 할당

교착 상태 무시(Don’t Care)

• 교착상태는 실제로 잘 일어나지 않기 때문에 무시
  • 4가지 필요조건을 모두 만족해도 교착 상태는 잘 일어나지 않는다.
  • PC 등의 경우는 교착상태 발생 시 재시동을 하면 된다.