# 교착상태(Deadlock)
정의
두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태
# 교착상태의 원인
- 상호 배제 : 한 프로세스가 자원을 독점하고 있으며 다른 프로세스들은 접근이 불가능합니다.
- 점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태입니다.
- 비선점 : 다른 프로세스의 자원을 강제적으로 가져올 수 없습니다.
- 환형 대기 : 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황을 말합니다.
# 교착상태의 해결 방법
- 자원을 할당할 때 애초에 조건이 성립되지 않도록 설계합니다.
- 교착 상태 가능성이 없을 때만 자원 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당 가능 여부를 파악하는 '은행원 알고리즘'을 사용합니다.
- 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지웁니다.
- 교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서 교착 상태가 발생하면 사용자가 작업을 종료합니다.
현대 운영체제가 사용하는 방법입니다. 예를 들어 프로세스를 실행시키다 '응답없음'이라고 뜨는 경우가 있는데 이는 교착 상태가 발생한 경우입니다.
# 은행원 알고리즘
총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고 안정 상태로 가도록 자원을 할당하는 알고리즘
| 변수 | 설명 |
|---|---|
| 전체 자원(Total) | 시스탬 내 전체 자원의 수 |
| 가용 자원(Available) | 시스템 내 현재 사용할 수 있는 자원의 수 (가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원) |
| 최대 자원(Max) | 각 프로세스가 선언한 최대 자원의 수 |
| 할당 자원(Allocation) | 각 프로세스에 현재 할당된 자원의 수 |
| 기대 자원(Expect) | 각 프로세스가 앞으로 사용할 자원의 수 (기대 자원 = 최대 자원 - 할당 자원) |
- 실행 방식
- 각 프로세스는 자신이 사용할 자원의 최대수(max)를 운영체제에 알려줍니다.
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당합니다. (안정상태)
- 가용 자원이 어떤 기대 자원보다 작으면 할당하지 않습니다. (불안정 상태)
- 현재 실행중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용자원을 할당 해야합니다.
# 식사하는 철학자 문제
5명의 철학자들이 한 식탁에서 함께 식사를 하는데 젓가락이 5개 밖에 존재하지 않습니다. 철학자들은 바로 옆 젓가락만 들을 수 있고, 왼쪽 젓가락과 오른쪽 젓가락을 둘 다 들어야 식사를 할 수 있습니다. 식사를 마침 다음에야 두 젓가락을 모두 내려놓을 수 있습니다.
- 철학자들이 동시에 배가 고파져 모두 자신의 오른쪽 젓가락을 잡으면 왼쪽 젓가락을 잡지 못해 교착상태가 발생합니다.
- 교착상태의 해결방법
- 젓가락 개수 늘리기
- 젓가락 개수를 6개로 늘려 최악의 경우에도 1명은 2개의 젓가락으로 식사를 마칠 수 있게 합니다.
- 철학자 위치 구분 (홀짝)
- 홀수 번 철학자, 짝수 번 철학자를 구분합니다.
- 홀수 번 철학자인 경우는 젓가락을 왼쪽, 오른쪽 순으로 집어서 밥을 먹고 젓가락을 왼쪽, 오른쪽 순으로 내려 놓습니다.
- 짝수 번 철학자인 경우는 젓가락을 오른쪽, 왼쪽 순으로 집어서 밥을 먹고 젓가락을 오른쪽, 왼쪽 순으로 내려 놓습니다.
- 각각의 철학자 상태 구분
- 철학자가 EATING 상태가 되기 위해서 자신이 HUNGRY 상태이고, 자신의 왼쪽, 오른쪽 모두 EATING 상태가 아니어야 한다는 조건을 넣습니다.
- HUNGRY : 철학자가 젓가락을 집기를 원하는 상황 (임계구역 접근을 원함)
- THINKING : 철학자가 젓가락 집기를 원치 않는 상황 (임계구역 접근을 원치 않는 상황)
- EATING : 철학자가 2개의 젓가락을 집어 밥을 먹는 상황 (임계구역에 접근한 상황)
- 철학자가 EATING 상태가 되기 위해서 자신이 HUNGRY 상태이고, 자신의 왼쪽, 오른쪽 모두 EATING 상태가 아니어야 한다는 조건을 넣습니다.
- 젓가락 개수 늘리기
# 기아상태(Starvation)
정의
프로세스가 CPU 자원의 할당을 무한히 대기하는 상태
# 교착상태 vs 기아상태
둘 다 자원의 할당을 계속해서 대기한다는 점에서 비슷합니다.
하지만 교착상태는 프로세스의 상태 중 blocked 상태에서 발생하며, 기아상태는 ready 상태에서 발생합니다.
교착상태는 절대 발생하지 않는 이벤트를 대기하고 있지만, 기아 상태는 CPU의 할당을 대기하고 있습니다.
# 참고자료
- 주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
- 숭실대학교 김영근 교수님의 운영체제 강의자료(2021)
- suyeonme.log (opens new window)
- 유쾌하게 긍정적으로 (opens new window)
- minseojo.log (opens new window)
← 공유자원과 임계영역 CPU 스케줄링 →