교착 상태의 개요

1. 교착 상태의 정의

: 2개 이상의 작업이 동시에 이루어질 때, 서로 다른 작업이 끝나기만 기다리는 경우

rf. 아사 현상과의 차이점

• 아사 현상 : 잘못된 정책으로 특정 프로세스의 작업이 지연됨 ㄴ 아사 현상의 해결 : 프로세스가 양보할 수 있는 상한선(에이징)을 정하면 해결된다.

• 교착 상태 : 여러 프로세스가 작업을 진행하다 보면 나타나는 자연적인 현상

  (1) 시스템 자원 : 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다.

  ㄴ P1이 프린터를 할당 받고 스캐너를 기다림 ㄴ P2가 스캐너를 할당 받고 프린터를 기다림

  (2) 잠금 : 잠금을 사용할 때 발생한다.

  (3) 응용 프로그램 : 예를 들어 데이터베이스는 일관성의 유지를 위해 락을 사용하는데 이때 교착상태가 발생할 수 있다.

2. 자원 할당 그래프

: 프로세스가 어떤 자원을 사용중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것

교착 상태 필요조건

1. 교착 상태 필요조건

• 상호 배제 : 한 프로세스가 사용중인 자원은 다른 프로세스가 공유할 수 없음
• 비선점 : 한 프로세스가 사용중인 경우 다른 프로세스가 빼앗을 수 없음
• 점유와 대기 : 프로세스가 어떤 자원을 할당 받고 다른 자원을 대기하는 상태
• 원형 대기 : 점유와 대기를 하는 프로세스 간의 관계가 원형 상태

2. 식사하는 철학자 문제와 교착 상태 필요조건

: 4명의 철학자. 4개의 포크. 두 개의 포크를 집어야만 밥을 먹을 수 있다.

• 서로 포크를 공유할 수 없다
• 다른 사람이 포크를 들면 뺏을 수 없다
• 왼쪽 포크를 들고 오른쪽에서 왼쪽 포크를 놓을 때까지 기다린다.
• 이러한 상태가 원형으로 이러나고 있다.

교착 상태 해결 방법

1. 교착 상태 해결

• 교착 상태 예방 : 네 가지 조건의 무력화
• 교착 상태 회피 : 자원 할당량을 조절해 교착 상태를 해결
• 교착 상태 검출과 회복 : 자원 할당 그래프를 모니터링해 교착 상태가 발생하는지 살펴보고, 교착 상태가 발생하면 교착 상태 회복 단계를 거침

2. 교착 상태 예방

교착 상태 예방은 프로세스 작업 방식을 제약하기에 사용하기 어렵다.

• 상호 배제 예방 : 독점 자원을 없애버리는 것 → 현실적으로 자원 보호가 필요한 경우 있음
• 비선점 예방 : 모든 자원을 빼앗을 수 있게 만다는 것 → 임계구역 잠금하면 불가능
  • rf. 우선순위 높은 프로세스가 낮은 프로세스를 계속 빼앗으면 → 아사 현상 발생
  • 아사 현상은 에이징을 통해 해결할 수 있는데, 우선순위를 낮추고 낮추다 보면 결국 비선점 스케줄링(FCFS)을 쓸 수 밖에 없다. → 결국 비선점 조건의 무력화가 어렵다.
• 점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하기
  • 전부 할당하거나 또는 아예 할당하지 않는 (all or nothing) 방식
  • rf. 왼쪽 포크를 잡은 상태에서 오른쪽 포크를 잡지 못하게 하는 방식 철학자는 결국 모든 왼쪽 포크를 잡거나 전부 다 내려놓아야만 한다.
  • 단점
    • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
    • 자원의 활용성이 떨어진다. ( 당장 사용하지도 않는 자원 - 오른쪽 포크- 을 선점 )
    • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스 보다 불리하다.
    • 결국 일괄 작업 방식으로 동작한다.
• 원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 막는 방법
  • rf. 모든 자원에 번호를 부여하고 숫자가 큰 방향으로만 자원을 할당
    • 마우스 1, 하드디스크 2, 프린터 3
  • 단점
    • 프로세스 작업 진행에 유연성이 떨어진다.
    • 자원에 번호를 어떻게 부여할 지가 문제다.

3. 교착 상태 회피

교착 상태 회피는, 시스템 운영 방식에 변경을 가하지 않아 교착 상태 예방 보다 유연하다.

• 교착 상태 회피의 개념 : 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악해서, 그 수준 이하로 자원을 나누어 주는 방법
  • 자원을 많이 할당할 수록 교착 상태가 발생할 확률이 커진다.
  • 자원 수의 조절 → 교착 상태 회피
  • 자원 수를 기준으로 교착 상태 가능성이 높은 경우, 불안정 상태라고 한다.
    • 안정 상태
    • 불안정 상태
• 은행원 알고리즘
  • 보유 금액이 대출 가능한 범위 (안정 상태) 일 때 대출 허용
  • ex. 음식점 재료 보유 (우동 10인분, 라면 20인분) → 최대 예약 10명까지만 받는다.
  • 은행원 알고리즘에서 각 프로세스는 자신이 사용할 자원의 최대 수(MAX)를 OS에 알림
    • 전체 자원 : 시스템 전체 자원
    • 가용 자원 : 사용 가능한 자원
    • 최대 자원 : 프로세스에서 사용할 최대 자원
    • 할당 자원 : 혈재 할당 자원
    • 기대 자원 : 앞으로 할당될 자원
  • 안정 상태 : 각 프로세스의 기대 자원과 비교해 가용 자원이 크거나 같은 경우가 한 번 이상인 경우
  • 은행원 알고리즘에서는 현재 실행 중인 프로세스 가운데 하나라도 끝낼 수 있을 때, 가용 자원을 할당해야 한다.
• 교착 상태 회피의 문제점
  • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
  • 시스템의 전체 자원 수가 고정적이어야 한다.
  • 자원이 낭비된다.

4. 교착 상태 검출

• 타임 아웃 : 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태 발생되었다 간주해 처리하는 방법
  • 윈도우에서 [XXX 가 응답하지 않습니다.] confirm 창이 나타나는 것
  • 단점
    • 엉뚱한 프로세스가 강제 종료될 수 있다.
    • 모든 시스템에 적용할 수 없다.
      • 데이터베이스 :
        • 데이터베이스는 일관성이 깨지면 안된다. (타임아웃 쓰면 일관성 사라짐)
        • 체크 포인트와 롤백, 체크 포인트를 설정하면 현재 시스템 상태가 하드 디스크에 저장되며 이러한 데이터를 스냅숏이라 한다.
        • 롤백이 발생하면 체크 포인트로 돌아가며, 스냅숏을 복원한다.
• 자원 할당 그래프를 이용한 교착 상태 검출
  • 교착 상태가 없는 자원 할당 그래프
  • 교착 상태가 있는 자원 할당 그래프
  • 장점
    • 프로세스 작업 방식을 제한하지 않으면서 교착 상태를 정확히 파악할 수 있다.
  • 단점
    • 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 오버헤드가 발생한다.

5. 교착 상태 회복

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료한다.
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다.
  • 기준 예시
    • 우선순위가 낮은 프로세스를 먼저 종료
    • 우선순위가 같으면 작업 시간이 짧은 프로세스 먼저 종료
    • 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스 먼저 종료