[OS] 교착 상태

교착 상태 (dead lock)

• 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태
• 아사 현상과 달리, 정책상 잘못이나 오류가 없어도 자연적으로 발생

 

- 교착 상태의 발생

• 시스템 자원, 공유 변수 (또는 파일), 응용 프로그램 사용 시 발생
• 시스템 자원 : 어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우
• 공유 변수 : 한 변수를 할당받은 상태에서 다른 변수를 기다릴 경우, 모든 프로세스가 임계구역에 들어가지 못하는 교착 상태 발생 (무한 대기)
• 응용 프로그램 : 데이터베이스가 데이터 일관성을 유지하기 위해 사용하는 잠금에서 교착 상태 발생 가능

 

자원 할당 그래프 (resource allocation graph)

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

 프로세스 P1이 자원 R1을 할당받은 경우 (할당)  /  프로세스 P1이 자원 R1을 기다리는 경우 (대기)

• 다중 자원 (multiple resource) : 여러 프로세스가 하나의 자원을 동시에 사용
  • 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현

2개의 프로세스를 수용하는 자원

• 식사하는 철학자 문제 (교착 상태)
  • 철학자 4명이 둥근 식탁에서 식사를 하는데, 왼쪽의 포크를 잡은 뒤 오른쪽의 포크를 잡아야만 식사가 가능함
  • 하지만 왼쪽 포크를 잡은 뒤 오른쪽 포크를 보면 왼손에 포크를 들고 있는 다른 철학자가 있음
    = 자원 하나를 잡은 상태에서 다른 자원을 기다리는 경우

 

교착 상태 필요조건

• 교착 상태는 다음의 조건을 모두 충족해야 발생

[자원의 특징]

• 상호 배제 (mutual exclusion) : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함, 배타적인 자원은 임계구역으로 보호되므로 여러 프로세스가 동시에 사용할 수 없음
• 비선점 (non-preemption) : 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함

[프로세스의 행위]

• 점유와 대기 (hold and wait) : 프로세스가 자원을 할당받은 상태(점유)에서 다른 자원을 기다리는 상태(대기)여야 함
• 원형 대기 (circular wait) : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함

 

교착 상태 해결 방법

- 교착 상태 예방

• 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식
• 실효성이 적어 잘 사용하지 않음
  • 상호 배제/비선점의 경우 자원 보호하기 위해 예방 어려움
  • 점유와 대기/원형 대시는 프로세스의 작업 방식 제한하고 자원을 낭비

[상호 배제 예방]

• 시스템 내에 있는 상호 배타적인 모든 자원을 제거
• 시스템 내의 모든 자원을 공유할 수 있음
• 하지만 시스템 내에는 공유할 수 없는 자원이 있으므로 상호 배제 무력화는 사실상 어려움

[비선점 예방]

• 모든 자원을 빼앗을 수 있도록 만드는 방법
• 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등 결정 어려움
• 아사현상 일으킴, 에이징 기법을 사용하면 프로세스가 점유하고 있는 자원이 비선점 자원이 됨
• 사실상 비선점 조건을 무력화하기 어려움

[점유와 대기 예방]

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
• 전부 할당하거나 아니면 아예 할당하지 않는 방식 적용 (all or nothing)
• 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납
• 상호 배제/비선점 예방은 자원에 대한 제약을 푸는 것이지만 (자원에 대한 제약은 풀기 어려움) 점유와 대기 예방은 프로세스의 자원 사용 방식을 변화시킴
• 단점
  • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
  • 자원의 활용성이 떨어짐 : 한 프로세스가 앞으로 사용할 자원까지 선점하므로 그 자원을 필요로 하는 다른 프로세스의 작업이 진행되지 않음
  • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리 → 아사 현상 발생
  • 결국 일괄 작업 방식으로 동작

[원형 대기 예방]

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
• 프로세스들이 한 줄로 길게 늘어선다면 그 줄의 맨 끝에서부터 문제가 해결될 수 있음
• 자원을 한 방향으로만 사용하도록 설정, 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원 할당
• 단점
  • 프로세스 작업 진행에 유연성이 떨어짐
  • 자원의 번호 부여 방법 문제

 

- 교착 상태 회피

• 자원 할당량을 조절하여 교착 상태 해결하는 방식
• 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나눠주면 교착 상태가 발생하는지 파악 후 그 수준이하로 자원을 나누어줌, 교착 상태가 발생하는 범위에 있을 경우 프로세스를 대기시킴
• 자원의 총 수, 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)/불안정 상태(unsafe state)로 구분
  • 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘수록 불안정 상태가 커짐
  • 불안정 상태는 교착 상태가 발생할 가능성이 높아질 뿐, 항상 교착 상태가 발생하는 것은 아님
  • 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당
• 은행원 알고리즘 (banker's algorithm)
  • 은행이 대출을 해주는 방식과 유사 (대출 금액이 대출 가능한 범위 내이면 허용, 그렇지 않으면 거부)
  • [은행원 알고리즘에서 사용하는 변수]
    전체 자원 (Total) : 시스템 내 전체 자원의 수
    가용 자원 (Available) : 시스템 내 현재 사용할 수 있는 자원의 수 (전체 자원-모든 프로세스의 할당 자원)
    최대 자원 (Max) : 각 프로세스가 선언한 최대 자원의 수
    할당 자원 (Allocation) : 각 프로세스에 현재 할당된 자원의 수
    기대 자원 (Expect) : 각 프로세스가 앞으로 사용할 자원의 수 (최대 자원-할당 자원)
  • 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원 할당
    (가용 자원이 기대 자원보다 크다 = 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다 = 안정상태)
• 문제점
  • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
  • 시스템 전체 자원 수가 고정적이어야 함 (일시적인 고장, 새로운 자원 추가로 시스템 자원의 수는 유동적임)
  • 자원 낭비 : 모든 불안정 상태가 교착 상태가 되는 것은 아님에도 자원을 할당하지 않는 것은 자원 낭비

 

- 교착 상태 검출

• 자원 할당 그래프를 모니터링하며 교착 상태가 발생하는지 살펴보는 방식
• 교착 상태 해결 방법 중 가장 현실적
• 교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟음

[타임아웃을 이용한 교착 상태 검출 = 가벼운 교착 상태 검출]

• 일정 시간 동안 작업이 진행되지 않은 프로세슬르 교착 상태가 발생한 것으로 간주하여 처리
• 문제점
  • 엉뚱한 프로세스가 강제 종료될 수 있음 : 교착 상태 외의 이유로 작업 진행되지 않는 프로세스 강제 종료 가능
  • 모든 시스템에 적용 불가 : 하나의 운영 체제 내에서 동작하는 프로세스들은 운영체제가 상태 감시 가능하여 적용 가능, 데이터가 여러 시스템에 나뉘어있고 각 시스템이 네트워크로 연결된 분산 데이터베이스의 경우에는 적용하기 어려움 (프로세스의 응답이 없는 이유를 정확히 알 수 없음)
• 대부분의 데이터베이스와 운영체제에서 많이 선호
• 타임아웃으로 데이터의 일관성이 깨지는 문제 해결 위해 체크포인트와 롤백 사용
  • 체크포인트 (check point) : 현재 시스템 상태를 하드 디스크에 저장, 저장된 데이터 = 스냅숏 (snap shot)
  • 롤백 (roll back) : 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것

[자원 할당 그래프를 이용한 교착 상태 검출 = 무거운 교착 상태 검출]

• 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지, 혹은 기다리고 있는지 알 수 있음
• 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 장점
• 자원 할당 그래프를 유지, 갱신, 사이클 검사 작업으로 인해 오버헤드가 발생하는 단점

 

- 교착 상태 회복

• 교착 상태가 검출되면 교착 상태를 푸는 후속 작업 진행
• 교착 상태를 유발한 프로세스를 강제 종료
  • 교착 상태를 일으킨 프로세스를 동시에 종료 : 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태 일으킬 가능성이 큼, 따라서 강제 종료 후 순차적으로 실행해야 하며 어떤 프로세스를 먼저 실행할 지 기준 필요
  • 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료 : 순서대로 종료하며 나머지 프로세스 상태를 파악
    [프로세스 종료 기준]
    우선 순위가 낮은 프로세스 먼저, 우선 순위가 같은 경우 작업 시간이 짧은 프로세스 먼저, 두 조건이 같은 경우 자원을 많이 사용하는 프로세스 먼저
• 강제 종료된 프로세스가 다시 실행되기 전에 시스템 복구도 진행
  • 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 방식
  • 작업량이 살당하여 시스템에 부하를 주므로 체크포인트를 무분별하게 사용하지 말고 선택적으로 사용해야 함