교착상태 해결

※ 전남대학교 박태준 교수님의 운영체제 강의를 듣고, 정리한 내용입니다.

교착상태 발생 필요충분조건

다음 4가지 상황이 모두 허용되는 시스템은 언제든지 교착상태가 발생할 수 있습니다 ( Coffman Condition )

• 상호 배제 ( Mutual Exclusion )

  • 각 자원은 한번에 하나의 프로세스 / 쓰레드에게만 할당
  • 자원이 한 쓰레드에게 할당되면 다른 쓰레드에게는 할당될 수 없음

• 비선점 ( No Preemption )

  • 프로세스 / 쓰레드에게 할당된 자원을 강제로 빼앗지 못함

• 점유와 대기 ( Hold & Wait )

  • 쓰레드가 한 자원을 소유 ( Lock ) 하면서 다른 자원을 기다림

• 환형 대기 ( Circular Wait )

  • 한 그룹의 쓰레드들에 대해, 각 쓰레드는 다른 쓰레드가 요청하는 자원을 소유하는 원형 고리 형성

이 4가지 조건 중 한 가지라도 성립되지 않으면, 교착상태는 발생하지 않습니다.

교착상태 해결

• 교착상태 예방 ( Prevention )

  • 교착상태가 발생할 여지를 차단하여 예방함
  • 교착상태에 빠지는 4가지 조건 중 하나 이상의 조건이 성립되지 못하도록 시스템 구성

• 교착상태 회피 ( Avoidance )

  • 미래에 교착상태로 가지 않도록 회피
  • 자원 할당 시 마다 미래의 교착 상태 가능성 검사
    • 교착 상태가 발생하지 않을 것이라고 확신하는 경우에만 자원 할당
  • 안정한 상태와 불안정한 상태로 시스템 상태 분류
    • 안정한 상태인 경우에만 자원 할당
  • 자원 할당 시 마다 교착 상태 가능성을 검사하므로 시스템 성능 저하

• 교착상태 감지 및 복구 ( Detection and Recovery )

  • 교착상태를 감지하는 프로그램 구동
    • 발견 후 교착상태 해제
  • 백그라운드에서 교착 상태를 감지하는 프로세스가 늘 실행되어야 하는 부담이 존재

• 교착상태 무시

  • 현재 대부분의 운영체제에서 사용하는 가장 일반적인 방법
    • 교착상태 예방 / 회피 / 감지 및 복구 등의 경우 시스템 성능을 떨어뜨리기 때문
  • 심각하지 않은 작업들에 대해서는 교착상태 무시

교착상태 예방

• 상호 배제 없애기

  • 동시에 2개 이상의 쓰레드가 자원을 활용할 수 있도록 함
  • 하지만 컴퓨터시스템에서 근본적으로 적용 불가능한 방법

• 비선점 조건 없애기

  • 모든 자원을 빼앗을 수 있도록 만드는 방법 ( 선점 )
  • 기아현상이 발생할 수도 있음
  • 간단하지 않고 오버헤드가 큼

• 점유와 대기 조건 없애기

  • 1번 방법
    • 운영체제가 쓰레드 실행 전 필요한 모든 자원을 파악하고 실행 시 한 번에 할당하는 방법
  • 2번 방법
    • 쓰레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고 다시 한꺼번에 요청하여 할당
  • 문제점
    • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
    • 당장 사용하지 않는 자원을 쓰레드에 묶어둠 → 자원 활용률 감소

• 환형 대기 조건 없애기

  • 모든 자원에 숫자를 부여하고, 숫자가 큰 방향으로만 자원을 할당 ( 한쪽 방향으로만 이동 )
  • 문제점
    • 프로세스 작업 진행 간 유연성이 떨어짐
    • 자원의 번호는 어떻게 부여할 것인지?

교착상태 회피

• 자원 할당 시, 미래에 환형 대기가 발생할 것으로 판단되면 자원을 할당하지 않는 정책

• 교착 상태가 발생하지 않는 범위 내에서만 자원 할당

  • 안정한 상태 ( Safe State )
    • 현재 프로세스들을 어떤 순서로 실행시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있다면 안정한 상태
  • 불안정한 상태 ( Unsafe State )
    • 환형 대기에 빠질 수 있다면 불안정한 상태
    • 불안정하다고 해서 교착상태인 것은 아님 ( 역은 성립 )

banker’s 알고리즘

• 자원 할당 전, 미래에 교착 상태가 발생할 것인지 판단 후 자원 할당

• 알고리즘

  • 각 프로세스가 실행 시작 전, 필요한 전체 자원의 수를 운영체제에게 알림
  • 자원 할당 시, 교착상태가 발생하지 않을 만큼 안정한 상태인지 판단 후 자원 할당

• 하지만, 각 프로세스가 실행 전 필요한 자원의 갯수를 아는 것은 불가능

• 프로세스의 갯수도 동적으로 변하기 때문에, 미리 프로세스의 갯수를 정적으로 고정시키는 것 또한 불가능함

교착상태 감지 및 복구

백그라운드에서 교착상태를 감지하는 프로그램이 항상 실행되도록 하여, 교착상태 발생시 이를 풀어주는 방법도 고려해볼 수 있습니다.

교착 상태가 형성되었는지 확인하는 방법은 2가지 방법이 있습니다.

• 자원 할당 그래프를 이용한 교착 상태 검출

• 타임아웃을 이용한 교착 상태 검출

  • 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
  • 교착 상태가 자주 발생하지 않을 것 이란 가정하에 사용
  • 타임아웃이 되면 프로세스 종료

교착상태를 감지하였을 때의 복구 방법

• 자원 강제 선점 ( Preemption )

  • 교착 상태에 빠진 쓰레드 중 하나의 자원을 강제로 빼앗아 다른 쓰레드에게 할당

• 롤백 ( Rollback )

• 프로세스 / 쓰레드 강제 종료 ( Kill Process )

  • 교착상태에 빠진 쓰레드 중 하나 강제 종료

교착상태 무시 ( Ostrich Algorithm )

교착상태의 발생횟수와, 발생할 확률에 비해 이를 해결하기엔 상대적으로 비용이 많이 발생합니다.

그래서 교착상태가 발생하지 않을 것 이라 여기고, 말 그래도 무시하는 방법도 고려해볼 수 있습니다.

• 의심 가는 쓰레드를 종료시키거나 시스템 재시작

이 경우, 다음과 같은 문제점이 발생할 수 있습니다.

• 교착상태 발생시 시스템 재시작 혹은 특정 프로세스 / 쓰레드를 강제 종료
  • 관련된 데이터를 잃어버릴 수 있음
  • 그래서 데이터베이스의 경우 문제가 될 수 있기에, 체크포인트와 롤백 사용