📍목차
- 교착 상태의 개요
- 교착 상태 필요조건
- 교착 상태 해결 방법
1️⃣ 교착 상태(DeadLock)의 개요
이전 포스팅에서 한정 대기 조건을 보장하지 못하면 교착 상태가 발생하는 것을 살펴본 바 있다.
교착 상태란, 다른 작업이 끝나기를 기다리느라 더 이상 작업이 진행되지 못하는 상태이다.
교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때 발생할 수 있다.
프린터, 스캐너와 같이 임계구역으로 보호되어 동시에 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우,
프로그램에서 while(lock1 == true)와 같이 잠금 여부를 확인하는 경우,
데이터베이스에서 데이터 일관성을 유지하기 위해 잠금을 사용하는 경우를 예로 들 수 있다.
✔️ 자원 할당 그래프
자원 할당 그래프란, 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 표현한 유향 그래프이다.
교착 상태를 실생활에서의 예로 표현해보면,
요리사 A가 믹서기를 사용하면서 제빵기를 달라고 하고, 요리사 B가 제빵기를 사용하며 믹서기를 달라고 하는 상황이다.
그리고 이러한 교착 상태를 자원 할당 그래프로 표현하면 아래와 같다.
추가로 자원(믹서, 제빵기) 내에 그려진 작은 점은 동시에 수용할 수 있는 프로세스의 수를 의미한다.
위의 예에서는 모두 작은 점이 두 개이므로 하나의 프로세스만 수용 가능함을 의미한다.
2️⃣ 교착 상태 필요 조건
교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기의 네 가지 조건을 모두 만족해야만 발생한다.
각 조건에 대해 알아보자.
✔️ 상호 배제
상호 배제란, 자원이 임계구역으로 보호되어 공유할 수 없는 자원이어야 한다는 것이다.
✔️ 비선점
비선점이란, 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없다는 것이다.
자원을 빼앗을 수 있다면 시간 간격을 두고 자원을 공유할 수 있다.
✔️ 점유와 대기
점유와 대기란, 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다려야 한다는 것이다.
교착 상태가 발생하려면, 다른 프로세스가 필요로하는 자원을 점유한 채로 다른 자원을 기다려야 한다.
✔️ 원형 대기
원형 대기란, 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다는 것이다.
점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것이 아니라, 프로세스가 방해하는 방향이 원을 이루는 상황에 발생한다.
이를 자원 할당 그래프로 표현하면 아래와 같다.
상호 배제와 비선점 조건은 "자원이 어떤 특징을 갖는가?" 를 나타내고,
점유와 대기와 원형 대기는 "프로세스가 어떤 행위를 하는가?"를 나타낸다.
따라서 상호 배제와 비선점 조건은 임계구역과 관련이 있다.
임계구역 보호를 위해 잠금 장치를 사용하면 비선점 조건이 보장되어 교착 상태가 발생할 수 있다.
그러나 임계구역으로 보호된다고 해서 교착 상태를 유발하는 것이 아니라,
임계구역의 자원을 사용하는 프로세스들이 점유와 대기, 원형 대기 상황에 있을 때 교착 상태가 발생한다.
3️⃣ 교착 상태 해결 방법
이러한 교착 상태를 해결하는 방법은 예방, 회피, 검출이 있으며, 이 중 검출을 통해 교착 상태를 발견하면 회복 과정을 거친다.
✔️ 교착 상태 예방
교착 상태 예방이란, 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식이다.
1. 상호 배제 예방
시스템 내의 모든 자원을 공유할 수 있게 만드는 방식이다.
즉, 임계구역으로 보호받는 자원을 없애 교착 상태를 발생하지 않도록 한다.
단점
그러나 임계구역이 없으면 작업 순서에 따라 작업 결과가 달라지는 경쟁 조건 상황이 발생할 수 있기 때문에,
상호 배제를 예방하는 것은 불가능하다.
2. 비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방식이다.
단점
그러나 임계구역 보호를 위해 잠금을 사용하면 자원을 빼앗을 수 없으며,
빼앗을 수 있다 하더라도 어떤 기준으로 빼앗을지, 빼앗은 후 얼마나 사용하게 할지 결정하기 어렵다.
설령 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스의 자원을 무조건 빼앗도록 구현하더라도,
우선순위가 높은 프로세스가 계속 진입한다면 우선순위가 낮은 프로세스가 실행되지 못하는 아사 현상이 발생한다.
3. 점유와 대기 예방
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방식이다.
즉, 전부 할당하거나 아예 할당하지 않음으로써 교착 상태를 예방한다.
단점
그러나 이는 프로세스가 자신이 사용하는 모든 자원을 미리 알기 어렵다는 점과,
당장 사용하지 않을 자원을 선점함으로써 자원의 활용성이 떨어진다는 단점이 있다.
또한 수십 개의 자원 중에 모든 프로세스가 단 하나의 자원만 공유하더라도, 모든 자원을 확보한 후 실행해야 하므로 일괄 작업 방식으로 동작하게 된다.
4. 원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 하는 방식이다.
자원을 한 방향으로만 사용하도록 설정하면 교착 상태가 발생하지 않는다.
이를 위해 모든 자원에 숫자를 부여하고, 숫자가 커지는 방향으로만 자원을 할당한다.
위 사진에서 프로세스 P2는 자원 R2를 할당받고, 자원 R1를 점유하려는 상황이다.
그러나 R2의 번호가 R1보다 크기 때문에 프로세스 P2의 요청이 거절되어 강제 종료된다.
따라서 교착 상태가 발생하지 않고 P1이 정상적으로 실행된다.
단점
위 사진의 예에 따르면, 프린터를 할당받은 후 마우스를 사용할 수 없게 된다.
이는 납득할 수 없는 방식이며, 이런 경우로 인해 어떤 기준으로 자원에 번호를 할당할지 난감하다.
네 가지 예방 방식의 결론은,
자원을 보호해야 하므로 상호 배제 예방과 비선점 예방은 사용할 수 없고,
점유와 대기 예방과 원형 대기 예방은 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.
✔️ 교착 상태 회피
교착 상태 회피란, 어느 수준 이상으로 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 나누어주는 방식이다.
교착 상태 예방은 시스템 운영 방식에 변경이 생기는 반면, 교착 상태 회피는 운영 방식에 변경이 없어 유연하다.
교착 상태 회피는 자원을 많이 할당할수록 교착 상태가 발생할 확률이 커진다는 이론에 기반한다.
자원의 총수와 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눈다.
할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 많으면 불안정 상태가 커진다.
🔑 은행원 알고리즘
교착 상태 회피의 대표적인 구현 방식으로 은행원 알고리즘이 있다.
은행이 대출해 주는 방식에서 유래한 아이디어로, 대출 금액이 가능한 범위 내에 있다면 대출을 허용하는 형태이다.
은행원 알고리즘에서는 아래와 같은 변수를 사용한다.
| 변수 | 역할 |
|---|---|
| 전체 자원 | 시스템 내 전체 자원의 수 |
| 가용 자원 | 시스템 내 현재 사용 가능한 자원의 수 = (전체 자원) - (모든 프로세스의 할당 자원) |
| 최대 자원 | 각 프로세스가 선언한 최대 자원의 수 |
| 할당 자원 | 각 프로세스에 현재 할당된 자원의 수 |
| 기대 자원 | 각 프로세스가 앞으로 사용할 자원의 수 = (최대 자원) - (할당 자원) |
위 변수들에 기반하여 안정 상태와 불안정 상태를 판단한다.
가용 자원이 기대 자원보다 크거나 같으면 안정 상태이고, 가용 자원이 기대 자원보다 작으면 불안정 상태이다.
단점
그러나 이러한 방식은 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다는 문제점이 있다.
미리 선언한 자원이 정확하지 않다면 여전히 교착 상태가 발생할 수 있다.
또한 시스템 자원의 고장이나 추가로 인한 유동적인 상황에 대비할 수 없고, 모든 불안정 상태가 교착 상태가 되는 것이 아님에도 자원을 할당하지 않아 자원이 낭비될 수 있다.
✔️ 교착 상태 검출과 회복
🔑 타임아웃
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주한다.
교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하며, 구현이 간단하다.
아래에서 설명할 자원 할당 그래프를 이용한 검출 방법은 그래프를 갱신하고 감시하는 과정을 구현하기 힘들어 무거운 교착 상태 검출이라 하고, 타임아웃을 이용한 검출 방법은 가벼운 교착 상태 검출이라 한다.
실제로 유닉스나 윈도우 등의 운영체제에서 많이 사용하는 방식으로,
"프로그램이 응답이 없어 종료합니다" 문구가 적힌 알림창이 타임아웃을 이용한 검출의 예시이다.
단점
그러나 단순히 시간만으로 판단하기 때문에, 교착 상태가 아닌 이유로 작업이 진행되지 못하는 프로세스가 강제 종료될 수 있다.
또한 하나의 운영체제 내에서 동작하지 않고, 각 시스템이 네트워크로 연결된 분산 데이터베이스같은 경우는 프로세스의 응답이 없는 것이 교착 상태 때문인지, 네트워크 문제인지 원인을 정확히 파악하기 힘들다는 문제점이 있다.
데이터베이스 교착 상태 해결
DB는 데이터의 일관성이 매우 중요한 문제다.
잠금을 얻어 작업하던 중 타임아웃으로 프로세스가 종료되면 데이터의 일관성이 깨질 수 있다.
이를 해결하기 위해 DB에서는 체크포인트와 롤백을 사용한다.
체크포인트는 문제가 발생했을 때 되돌아올 지점을 의미하고, 이 지점의 데이터를 스냅숏이라고 한다.
롤백은 문제가 발생했을 때 체크포인트로 되돌아가는 것을 말한다.
DB에서 중요한 데이터에 잠금을 요청하면 체크포인트를 만들어 스냅숏을 저장하고,
타임아웃이 발생한다면 롤백을 통해 체크포인트 시점으로 시스템을 복귀시킨다.
🔑 자원 할당 그래프 이용
자원 할당 그래프를 검사하여 사이클이 발견되는지 확인하는 방식이다.
운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신한다.
이때 사이클이 발생하면 교착 상태가 검출된 것으로 판단하고, 교착 상태를 푸는 교착 상태 회복 과정을 진행한다.
단점
위에서 언급한 바와 같이 자원 할당 그래프를 유지하고, 갱신하고, 검사하는 작업으로 인해 오버헤드가 발생한다.
이로 인해 자원이 할당될 때마다 검사하는 것이 아닌 일정 시간마다 검사하는 방법도 있다.
교착 상태 회복
교착 상태를 검출하면 교착 상태를 유발한 프로세스를 강제로 종료하며, 강제 종료 방법에는 두 가지가 있다.
1. 모든 프로세스 동시 종료
이 방법은 종료된 프로세스가 동시에 작업을 시작하면 다시 교착 상태를 일으킬 수 있다.
따라서 다시 시작할 프로세스을 순차적으로 실행해야 하며, 어떤 프로세스를 먼저 실행할지 기준을 정해야 한다.
2. 프로세스 순차 종료
이 방법은 어떤 프로세스를 먼저 종료할지에 대한 기준이 필요하다.
기준의 예시는 아래와 같다.
- 우선순위가 낮은 프로세스 먼저 종료
- 우선순위가 동일하면, 작업 시간이 짧은 프로세스 먼저 종료
- 작업 시간도 동일하면, 자원을 많이 사용하는 프로세스 먼저 종료
또한 교착 상태 회복 단계에서는 프로세스 종료 외에도 프로세스 재시작 전 시스템을 복구하는 작업도 진행된다.
이는 명령어가 실행될 때 체크포인트를 만들어두는 방식으로 진행되는데, 작업량이 커 시스템에 부하를 주므로 체크포인트를 전략적으로 생성해야 한다.
👏 마무리
프로세스가 자원을 사용하는 과정에서 발생하는 교착 상태의 개념과 발생 조건, 해결 방법까지 알아봤다.
다음 포스팅부터는 메모리 관리 방식에 대해 알아보자.
참고 자료
💕좋아요와 댓글은 큰 힘이 됩니다.💕
