[운영체제] 7장 교착상태

교착상태 (DeadLock)

1. 교착상태 문제 제기

1.1 무한대기와 교착상태

교착상태 : 상대가 가진 것을 확보할 때까지 무한정 대기하는 상황

1.2 식사하는 철학자 문제(Dining Philosophers Problem)

| | - 5명의 철학자가 원탁에서 식사. 식사 시간은 서로 다를 수 있음
- 자리마다 스파게티 그릇이 하나 있고 5개의 포크가 그릇 사이에 있음
- 철학자는 다른 철학자와 대화할 수 없음
- 식사를 위해서는 양 옆의 포크를 함께 들어야 함
- 왼쪽 포크를 먼저 든 다음 오른쪽 포크를 드는 순서이며 포크가 사용 중이면 대기해야 함 왼쪽 포크를 옆 철학자가 사용하고 있다면 오른쪽 포크도 잡을 수 없음 | | ———————————————————— | ———————————————————— |

• 철학자들의 교착상태 원인 — 혼형 요청/대기 (circular request/wait)
  • 5명 모두 왼쪽 포크를 가진 상태에서 동시에 자신의 오른쪽 철학자가 가진 포크를 요청하여, 대기가 환형 고리를 형성
• 철학자들의 교착상태 해결 - 환형 요청/대기가 생기지 않게 규칙 변경
  • 1~4번의 포크 집는 순서 (왼 → 오)
  • 5번의 포커 집는 순서 (오 → 왼)

※ Concurrent Programming 동기화

1.3 식사하는 철학자와 컴퓨터 시스템

• 철학자 - 스레드
• 포크 - 자원
• 스파게티 - 스레드가 처리할 작업

2. 교착상태

2.1 교착상태 정의

교착상태는 자원을 소유한 스레드들 사이에서 각 스레드는 다른 스레드가 소유한 자원을 요청하 여 모든 스레드가 무한정 대기하는 현상이다.

2.2 컴퓨터 시스템에 잠재된 교착상태 유발 요인

• 자원 - 교착 상태의 발생지
  • 소프트웨어/데이터 자원 - 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일락등 하드웨어 자원 - 프린터, 메모리, 프로세서 등
• 자원과 스레드 - 한 스레드가 여러 자원 필요로 하는 경우
• 자원과 운영체제 - 운영체제는 한 번에 하나씩 자원을 할당한다.
• 자원 비선점 - 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못한다.

2.3 교착상태 모델링

자원 할당 그래프

컴퓨터 시스템에서 자원 할당 그래프(RAG, resource allocation graph)를 이용하여 교착 상태를 표현한다

• 꼭짓점 - 스레드는 원으로, 자원은 사각형으로 나타낸다.
• 간선 - 간선은 할당 간선(allocation edge)과 요청 간선(request edge)의 두 종류로 나뉜다. 할당 간선은 자원에서 스레드로 향하는 화살표로서 스레드가 자원을 소유하고 있음을 나타내며, 요청 간선은 스레드에서 자원으로 향하는 화살표로서 스레드가 자원을 기다리고 있음을 나타낸다.

| | • 컴퓨터 시스템에 실행 중인 전체 스레드와 자원
• 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
• 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
• 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수• 컴퓨터 시스템에 실행 중인 전체 스레드와 자원 • 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수 • 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수 • 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수 | | ———————————————————— | ———————————————————— |

교착상태가 발생한 자원 할당 그래프 모양

스레드들이 교착상태에 있게 되면, 자원 할당 그래프에 스레드와 자원들을 연결하는 간선들의 환형 고리가 나타난다.

2.4 교착상태에 빠진 응용프로그램 사례

6장 생산자 소비자를 다룬 코드에서 lock 변수를 같은 변수 사용하지 않는 이유를 알 수 있음

3. 교착상태 해결

3.1 코프만 조건(Coffman condition)

다음 4가지의 필요충분조건을 모두 가진 시스템은 교착상태 발생 가능

• 상호배제(Mutual Exclusion) - 자원은 한 번에 한 스레드에게만 할당
• 소유하면서 대기(Hold & Wait) - 스레드가 자원을 소유하면서 다른 자원대기
• 강제 자원 반환 불가(No Pr은은mption) - 스레드에게 할당된 자원을 강제로 빼앗지 못함
• 환형 대기(Circular Wait) — 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 소유한 자원을 요청하는 환형 고리 형성

3.2 교착상태 해결 방법

• 교착상태 예방(prevention)
• 교착상태 회피(avoidance)
• 교착상태 감지 및 복구(detection and recovery)
• 교착상태 무시(ignore and reboot) - ostrich 알고리즘(타조 알고리즘)

3.3 교착상태예방

• 상호배제(Mutual Exclusion) → 상호배제 없애기
  • 실현 가능성 없음
• 소유하면서 대기(Hold & Wait) → 기다리지 않게
  • 스레드가 필요한 자원을 모두 할당받을 수 없는 경우, 운영체제는 모든 자원이 준비될 때까지 아예 스레드의 실 행 자체를 대기시킨다. → 실행시간의 증가
• 자원 강제 반환 불가(No Preemption) → 자원의 선점 허용
  • 우선순위 낮으면 자원 뺏길 수 있음 → 단순하지 않은 방법
• 환형 대기(Circular Wait) → 환형 대기 제거
  • 모든 자원에 번호를 매기고, 스레드에게 반드 시 번호 순으로 자원을 할당받게 하는 방법이다.

3.4 교착 상태 회피

자원할당 알고리즘을 이용하여 교착상태를 방지하는 방법이다.

• 환형 대기가 발생하지 않는다는 확신이 서는 경우에만 자원을 할당함
• 이 방법은 자원을 할당할 때마다 환형 대기가 발생할 것인지 판단하는 작업이 실행되어 큰 단점

※ banker’s 알고리즘

3.5 교착 상태 감지 및 복구

• 자원 강제 선점(preemption)
  • 운영체제는 교착상태에 빠진 스레드 중 하나를 선택하고 이 스레드가 소유한 자워을 강제로 빼앗아 이 자원을 기다리는 다른 스레드에게 할당하는 방법
• 롤백 (rollback)
  • 교착상태가 발생하면 가장 최근에 저장해둔 상태로 복구시켜 가장 최근에 실행하던 상태로 돌아가도록
• 스레드 강제 종료(kill process)
  • 교착상태에 빠진 스레드 중 하나를 강제로 종료시키는 방법이다

※ 교착상태가 있는지 판단하는 것은 시스템에 부담을 주며 교착상태를 해제하는 방법들도 시스템에 많이 부담스럽다

※ 교착상태는 대체로 개발자의 실수로 인해 응용 프로그램에서 발생 (커널에서는 거의 X)

※ 교착상태에 빠지면 스레드 중 하나를 종료하 거나 시스템을 재시작하는 방법 외에 다른 해결책이 없다.

3.6 교착상태 무시 : 타조(ostrich) 알고리즘

교착상태의 발생 빈도가 적기 때문에 굳이 많은 시간과 비용을 지불할 필요가 없다고 느낀 경우

타조 알고리즘

• 교착상태에 대한 대비 X
• 교착상태가 의심되면 시스템 재시작 or 의심가는 스레드 강제 종료

→ 실시간 및 중요한 임베디드 시스템에서 사용하지 않음