[운영체제] 교착상태

교착상태 문제 제기

1) 실생활에서 발생하는 교착상태

• 밥을 먹기 위해 숟가락, 젓가락 모두 필요한 상황에서 한 사람은 숟가락을 다른 한 사람은 젓가락을 소유할 경우 숟가락이나 젓가락을 사용할 수 있을 때까지 대기 → 무한 대기 발생
• 교착 상태 : 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기

2) 식사하는 철학자 문제

• 5명의 철학자가 원탁에서 식사, 식사 시간은 서로 다름
• 자리마다 스파게티 1개와 양 옆에 포크가 있으며
• 각 철학자는 옆 철학자와 대화 불가능
• 식사를 하기 위해서는 양 손에 포크가 동시에 들려 있어야하며
• 왼쪽 포크를들고 다음 오른쪽 포크를 드는 순서
• 포크가 사용 중일 경우 대기

→ 모든 철학자가 동시에 같이 자리에 앉아 식사를 할 경우 모두 왼쪽에 포크를 들어 무한 대기 발생

3) 철학자들의 교착상태 원인과 해결

• 교착상태 원인 - 환형 대기 / 요청 5명 모두 자원을 소유하면서 다른 자원을 요청
• 교착상태 해결 - 환형 대기가 생기지 않도록 ex) 마지막 철학자만 오른쪽 포크를 먼저 잡고 왼쪽을 잡도록 규칙

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

• 식사하는 철학자 문제는 컴퓨터 교착상태를 비유하여 나타낸 것
• 철학자 : 프로세스 포크 : 자원 스파게티 : 프로세스가 처리할 작업

교착상태

1) 교착상태의 정의

• Deadlock(교착상태) : 자원을 소유한 스레드들 사이에서, 각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하고 있는 현상
• 교착상태 발생 위치
• 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생 (정교하지 못한 코딩)
• 커널 내에서도 발생 가능 (거의 발생 X)
• 교착상태를 막도록 운영하는 컴퓨터 시스템은 많지않음 (막는데 많은 시간과 비용 소모)

2) 전형적인 멀티 스레드 교착상태

• 2개의 스레드가 각각 락 소유, 다른 상대가 가진 락을 요청하고 기다릴 때 발생
• 락과 자원에 대한 경쟁이 있을 경우 교착상태는 언제든 발생 가능

3) 잠재적인 교착상태 발생 요인

1. 자원

• 교착상태의 발생 원인
• 컴퓨터 시스템에는 많은 자원 존재 (락 자원, 파일, 데이터 베이스 등의 소프트웨어 자원과 프린터, 메모리, 프로세서 등의 하드웨어 자원)

1. 자원과 스레드

• 한 스레드가 여러 자원을 동시에 필요로 하는 상황

1. 자원과 운영체제

• 한 번에 하나씩 자원을 할당하는 운영체제 정책

1. 자원 비선점

• 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못하는 정책

4) 교착상태 모델링

• 자원 할당 그래프
• 그래프의 요소
• 꼭지점 : 스레드(원), 자원(사각형)
• 간선 : 소유/요청 관계, 할당 간선과 요청 간선
• 자원에 대한 시스템의 상태를 나타내는 방향성 그래프
• 해당 그래프를 통해 교착상태 판단
• 교착상태 예방, 회피, 감지를 위한 알고리즘 개발에 필요

교착상태 해결

1) 교착상태가 발생하는 4가지 조건

• 코프만 조건 : 교착상태가 발생하는 4가지 필요조건
• 상호 배제
• 소유하면서 대기
• 강제 자원 반환 불가
• 환형 대기
• 4가지 조건 중 한 가지라도 성립되지 않으면 교착상태가 발생하지 않음

2) 교착상태 해결 방법

1. 교착상태 예방

• 교착상태 발생 여지를 차단
• 4가지 조건 중 하나 이상의 조건이 성립되지 않도록 시스템 구성

1. 교착상태 회피

• 교착상태에 가지 않도록 회피
• 자원 할당 시마다 교착상태 가능성을 파악하여 교착상태가 일어나지 않으면 자원 할당
• banker’s algorithm

1. 교착상태 감지 및 복구

• 교착상태를 감지하는 프로그램 구동, 발견 후 교착상태 해제

1. 교착상태 무시

• 교착상태는 없다고 단정하여 사용
• 사용자가 이상을 느끼면 재실행할 것이라고 믿는 방법
• 현재 대부분의 운영체제에서 사용하는 가장 일반적인 방법

3) 교착상태 예방

1. 상호배제 없애기

• 2개 이상의 스레드가 자원을 활용할 수 있도록
• 근본적으로 컴퓨터 시스템에 적용 불가능

1. 대기하지 않게 만들기

• 방법 1 : 스레드 실행 전 필요한 모든 자원을 파악 후 모든 자원을 할당
• 방법 2 : 스레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고 한꺼번에 요청하여 할당

1. 선점 허용

• 자원을 강제로 반환하게 된 스레드가 자원을 다시 사용하게 될 때 이전 상태로 되돌아갈 수 있도록 상태 관리
• 간단하지 않으며 오버헤드가 매우 큼

1. 환형 대기 제거

• 모든 자원에게 번호를 매기고, 번호 순으로 자원 할당

4) 교착상태 회피

• 자원할당 시 미래에 환형 대기가 발생할 것으로 판단되면 자원 할당하지 않는 정책
• banker’s Algorithm
• 해당 내용은 따로 포스트 할 예정

5) 교착상태 감지 및 복구

• 교착상태를 감지하는 프로그램을 통해 형성된 교착상태 해제
• 교착상태를 감지하였을 때 복구 방법
  • 자원 강제 선점
  • 롤백 (시간과 메모리에 대한 부담이 커 잘 사용하지 않음)
  • 스레드 강제 종료

6) 교착상태 무시

• 교착상태를 해결할 필요성 : 교착상태는 발생하긴하나 발생 가능성이 극히 적고 교착상태를 피하기 위한 비용이 많이 듦
• 타조 알고리즘 (ostrich)
• put your head in the sand (무시)
• 현재 대부분의 운영체제에서 사용
• hard real-time 시스템이나 환자 감시 시스템에서는 적합하지 않음