[쉽게 배우는 운영체제] 6. 교착 상태

쉽게 배우는 운영체제

교착 상태의 개요

교착 상태의 정의

교착 상태(deadlock)
2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태

 

교착 상태(deadlock) vs 아사 현상(starvation)
아사 현상 : 잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제
교착 상태 : 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상

컴퓨터 시스템에서 교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때 발생할 수 있다.

 

시스템 자원

• 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생

잠금

• 교착 상태는 잠금을 사용할 때 발생

교착 상태를 발생시키는 임계구역 코드

• 예시 코드 - 무한 대기를 막지 못해 교착 상태가 발생한 경우
  • p1이 lock1을 true로 만든 다음 p2가 lock2를 true로 만들었다고 가정
  • 이후 p1은 while(lock2==true)가 실행되어 무한 반복
  • p2도 while(lock1==true)가 실행되어 무한 반복
  • 이 경우 p1, p2 모두 임계구역에 들어가지 못하는 교착 상태 발생

이처럼 한 변수를 할당받은 상태에서 다른 변수를 기다리면 교착 상태가 발생

응용 프로그램

• 데이터베이스 같은 응용 프로그램에서도 교착 상태 발생
• 여러 프로세스가 데이터베이스에 저장된 데이터를 사용할 때는 일관성을 유지해야 함
• 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데 이때 교착 상태 발생할 수 있음

 

자원 할당 그래프

• 자원 할당 그래프(resource allocation graph)는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프(directional graph)로 표현한 것
• 어떤 프로세스에 자원이 할당되어 있고 어떤 프로세스가 자원을 기다리고 있는지를 한눈에 파악 가능

자원 할당 그래프 표현 방식
원 : 프로세스
사각형 : 자원
자원에서 프로세스로 향하는 화살표 : 자원을 사용하는 경우(할당된 경우)
프로세스에서 자원으로 향하는 화살표 : 프로세스가 자원을 기다리는 경우(대기하는 경우)

자원 할당 그래프

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

식사하는 철학자 문제

원형 테이블

1. 철학자들은 포크 공유 불가
   → 자원을 공유하지 못하는 교착 상태 발생
2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없음
   → 자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태 발생
3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림
   → 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태 발생
4. 자원 할당 그래프가 원형
   → 자원을 요구하는 방향이 원을 이루면 양보하지 x → 교착 상태 발생

 

교착 상태 필요조건

1. 상호 배제
   • 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함
   • 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용 불가
   • 배타적인 자원을 사용하면 교착 상태 발생
2. 비선점
   • 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함 
3. 점유와 대기
   • 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함
4. 원형 대기
   • 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함

 

교착 상태 해결 방법

교착 상태 해결

• 교착 상태 예방
  • 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식
  • 상호 배제, 비선점, 점유와 대기, 원형 대기 중 하나라도 막으면 교착 상태 발생 x
  • 실효성이 적어 잘 사용되지 않는 방법
• 교착 상태 회피
  • 자원 할당량을 조절하여 교착 상태를 해결하는 방식
  • 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장 x → 실효성 적음
• 교착 상태 검출과 회복
  • 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식
  • 교착 상태 발생시 교착 상태 회복 단계가 진행됨
  • 교착 상태를 해결하는 현실적인 접근 방법

 

교착 상태 예방

상호 배제 예방

• 시스템 내에 있는 상호 배타적인 모든 자원(독점적으로 사용할 수 있는 자원)을 없애버리는 방법
• 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않음

비선점 예방

• 모든 자원을 빼앗을 수 있도록 만드는 방법
• 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등 결정하기 어렵고 아사 현상을 일으킬 수 있음

점유와 대기 예방

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
• 전부 할당하거나 아예 할당하지 않는 방식을 적용하는 것
• 단점
  1. 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
  2. 자원의 활용성 떨어짐
  3. 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리
  4. 결국 일괄 작업 방식으로 동작

전부 할당 또는 할당 x

원형 대기 예방

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
• 프로세스들이 한줄로 늘어선다면 그 줄의 맨 끝에서부터 문제가 해결됨
• 단점
  1. 프로세스 작업 진행에 유연성이 떨어짐
  2. 자원에 번호를 어떻게 부여할지가 문제

자원 번호

 

교착 상태 회피

교착 상태 회피의 개념

• 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
• 할당되는 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당

안정 / 불안정 상태

 

은행원 알고리즘

• 에츠허르 데이크스트라가 제안
• 은행이 대출해주는 방식
  • 대출 금액이 가능한 범위 내(안정상태) → 대출 허용
  • 그렇지 않으면 거부

 

• 은행원 알고리즘의 변수

변수	설명
전체 자원(Total)	시스템 내 전체 자원의 수
가용 자원(Available)	시스템 내 현재 사용할 수 있는 자원의 수 가용 자원 = 전체 자원  - 모든 프로세스의 할당 자원
최대 자원(Max)	각 프로세스가 선언한 최대 자원의 수
할당 자원(Application)	각 프로세스에 현재 할당된 자원의 수
기대 자원(Expect)	각 프로세스가 앞으로 사용할 자원의 수 기대 자원 = 최대 자원 - 할당 자원

• 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원 할당
• 가용 자원이 기대 자원보다 크다는 것
  = 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미 → 안정 상태
• 가용 자원이 어떤 기대 자원보다도 크지 않으면 자원 할당 x
  = 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미 → 불안정 상태

안정 상태
각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우

은행원 알고리즘 예시

[6-17]

• 가용 자원: 최대 자원 수(14) - 할당된 자원 수(2 + 4 + 6 = 12) = 2
• 기대 자원: 최대 자원 수 (5, 6, 10) - 현재 할당된 자원의 수(2, 4, 6) = 3, 2, 4
  • P2가 필요로 하는 자원 수(2)와 가용 자원(2)가 같으므로 안정자원이다.
  • 2를 P2에 할당시켜 실행하고 반환하면(6) 전체 작업 무사 완료 가능

[6-18]

• 가용 자원: 최대 자원 수(14) - 할당된 자원(3 + 4 + 6 = 13) = 1
• 기대 자원: 최대 자원 수(7, 6, 10) - 현재 할당된 자원 수(3, 4, 6) = 4, 2, 4
  • 1과 같거나 큰 기대 자원이 없으므로 어떠한 프로세스에도 주지 못하는 불안정 자원이다.
• 문제점(원칙 : 교착 상태가 발생하지 않을 수준까지만 자원을 나누어주는 것)
  1. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
  2. 시스템의 전체 자원 수가 고정적이어야 함
  3. 자원이 낭비됨

 

교착 상태 검출

타임아웃

• 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법
• 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 방법
• 가벼운 교착 상태 검출이라 부름

타임아웃 예시

• 문제점
  1. 엉뚱한 프로세스가 강제 종료될 수 있음
     • 교착 상태 외 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료될 수 있음
  2. 모든 시스템에 적용할 수 없음
     • 분산 데이터베이스와 같이 데이터가 여러 시스템에 나뉘어 있으면 타임아웃 방법 적용 불가
• 데이터베이스의 교착 상태 처리는 운영체제보다 복잡하다
  • 데이터베이스에서는 데이터의 일관성이 깨지면 안된다 → 데이터를 조작할 때 반드시 잠금을 얻은 후 작업을 시작해야 함
  • 여러 개의 잠금을 얻어 작업하던 중 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있음
  • 체크포인트(check point)와 롤백(roll back)을 사용
  • 체크포인트
    1. 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시
    2. 현재 시스템 상태가 하드디스크에 저장된다.(스냅숏(snap shot))
  • 롤백: 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것

check point / rollback

 

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

• 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있음

자원 할당 그래프와 교착 상태

(a) 교착 상태가 없는 자원 할당 그래프

• 프로세스 P1은 프로세스 P2가 자원 R2를 다 사용하고 반환하기를 기다림
• 프로세스 P4는 프로세스 P1의 자원 반환을, 프로세스 P3은 프로세스 P4의 자원 반환을 기다리고 있음
• 이 자원 할당 그래프에는 사이클이 존재하지 않으므로 프로세스 P2가 작업을 마치고 자원 R2를 반환하면 나머지 프로세스의 작업이 계속 진행되어 결국 교착 상태가 발생하지 않음

(b) 교착 상태가 있는 자원 할당 그래프

• 운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신
• 이때 사이클이 발생하면 교착 상태가 검출된 것으로 판단
• 프로세스 P2가 추가로 자원 R3를 요구하는 경우, P1 → P2 → P4 → P1로 이어지는 사이클이 존재하기 때문에 운영체제는 교착 상태가 발생한 것으로 판단

자원 할당 그래프 장단점

• 장점: 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있음
• 단점: 자원 할당 그래프를 유지, 갱신, 사이클 검사 등 추가 작업으로 인해 오버헤드 발생
  → 추가 작업 줄이기 위해 자원이 할당될 때마다 사이클 검사를 하는 것이 아닌 일정시간마다 하는 방법도 존재

 

교착 상태 회복

• 교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 교착 상태 회복이라 함
• 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제 종료

프로세스 강제 종료 방법

1. 교착 상태를 일으킨 모든 프로세스를 동시 종료
   • 종료된 프로세스들이 동시에 작업을 다시 시작하면 다시 교착 상태를 일으킬 가능성이 큼
   • 모든 프로세스를  강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야 함
   • 이때 어떤 프로세스를 먼저 실행할 것인지 기준을 정해야 함
2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
   • 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법
   • 프로세스 종료 순서를 정할 때는 다음과 같은 기준 필요
     1) 우선순위가 낮은 프로세스 먼저
     2) 우선순위가 같으면 작업 시간이 짧은 프로세스 먼저
     3) 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스 먼저