안녕하딤니카?
추워서 멸종되기 직전인 재빵입니다.
너무 추우니까 이번 글에서는 교착 상태에 대해서 정리해보겠습니따.
읏추 읏추
그럼 시~~~작
1. 교착 상태 (데드 락, Dead Lock)
프로세스가 실행이 제대로 되려면 자원이 필요한데, 두 개 이상의 프로세스가 각자 갖고 있는 각각의 자원들을 그저 기다리기만 한다면, 그 어떤 프로세스도 실행되지 못하고 꽉 막힌 도심 속의 차처럼 멈춰버리는 상태가 발생합니다. 이걸 우리는 교착 상태(데드 락, Dead Lock)이라고 합니다.
교착 상태를 이해하기 좋은 사례가 있는데, 이거를 식사하는 철학자 문제(Dining Philosopher's Problem)를 먼저 이해해 보겠습니다. 이 문제를 이해하면 교착 상태가 왜 발생하는지, 그리고 교착 상태를 어떻게 해결하면 좋은지를 알 수 있습니다.
위의 그림처럼 동그란 테이블에 다섯 명의 철학자가 식사를 한다고 가정하겠습니다. 식사를 하기 위해서는 두 개의 포크를 사용해야 합니다. 그래서 두 개의 포크를 사용해서 식사를 하는 과정인 1~5번을 반복해서 식사를 한다고 가정하겠습니다.
이렇게 1~5번 과정을 반복한다면 모든 철학자가 식사를 무사히 마칠 수 있을까요? (포크 쉐어 이슈다 이거 으 드러) 아닙니다... 이러면 어떤 철학자도 식사를 끝마칠 수 없습니다. 왜냐면 1번을 실행하고 오른쪽 포크를 집어 들어야 하는데, 모든 철학자가 왼쪽 포크를 집어 들면 2번으로 넘어갈 수 없습니다. 모든 철학자가 자신의 왼쪽 포크를 들고 오른쪽 포크를 하염없이 기다릴 테니까요.
이처럼 일어나지 않을 사건(오른쪽 포크가 나온다 라는 사건)을 하염없이 기다리며 진행이 멈춰버린 현상을 교착 상태라고 합니다.
식사하는 철학자 문제에서 철학자는 프로세스 혹은 스레드라고 생각할 수 있고, 포크는 실행에 꼭 필요한 자원이라고 생각할 수 있습니다. 그리고 식사를 하는 것은 자원을 이용하는 것 그니까 실행하는 것이라고 볼 수 있습니다. 그렇기 때문에 식사하는 철학자 문제는 서로가 점거하고 있는 자원을 서로가 기다릴 때, 결국 그 어떤 프로세스도 끝까지 실행될 수 없다는 것을 보여주는 사례입니다.
식사하는 철학자 문제를 컴퓨터에 빗대서 설명해 보자면, 위의 그림처럼 게임 프로세스와 웹 브라우저 프로세스가 서로가 필요한 자원 A, B가 해제되어 사용할 수 있을 때까지 하염없이 기다리고 있습니다. 이러면 게임 프로세스도, 웹 브라우저 프로세스도 두 개의 자원을 할당받기 위해서 계속 기다리며 결국에는 실행되지 못합니다.
2. 교착 상태를 해결하려면?
교착 상태를 이해했으니까, 교착 상태를 해결하기 위해서 어떤 것이 필요한 지 알아야겠죠?
- 교착 상태가 발생했을 때의 상황을 정확히 표현해 보기
- 교착 상태가 일어나는 근본적인 이유 이해하기
이렇게 두 가지로 나눠서 두 개의 문제를 정확히 표현하고, 이해해야 교착 상태를 해결할 수 있습니다.
먼저 첫 번째 "교착 상태가 발생했을 때의 상황을 정확히 표현해 보기"를 하기 위해서는 자원 할당 그래프를 확인해야 합니다. 자원 할당 그래프를 그려보면 교착 상태가 어떤 조건에서 발생하는지 대략적으로 확인 가능합니다. 그리고 어떤 프로세스가 어떤 자원을 할당받아 사용 중인지 확인 가능하고, 어떤 프로세스가 어떤 자원을 기다리고 있는지 총 세 가지의 문제를 확인 가능합니다.
이 자원 할당 그래프를 그리는 순서는 아래와 같습니다.
- 프로세스는 원으로, 자원의 종류는 사각형으로 표현
- 사용할 수 있는 자원의 개수는 자원 사각형 내에서 점으로 표현
- 어떤 프로세스가 어떤 자원을 할당 받아 사용 중이라면, 자원 ➡️ 프로세스 방향으로 화살표를 표시
- 프로세스가 어떤 자원을 기다리고 있다면, 프로세스 ➡️ 자원 방향으로 화살표를 표시
이렇게 그림을 그려보면, 교착 상태가 일어나는 자원 할당 그래프의 특징을 확인할 수 있습니다. 바로 그래프가 원의 형태를 띠고 있다는 점입니다.
이렇게 자원 할당 그래프를 확인하고 다음 단계에서는 "교착 상태가 일어나는 근본적인 이유 이해하기"로 넘어갑니다.
교착 상태가 일어나는 근본적인 이유를 이해하기 전에, 교착 상태가 발생할 조건을 먼저 확인해 보겠습니다. 아래 네 가지 발생 조건이 있습니다.
- 상호 배제 (Mutual Exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
- 점유와 대기 (Hold and Wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
- 비선점 (Non-Preemption) : 어떤 프로세스도 자원 프로세스의 자원을 강제로 빼앗지 못하는 상태
- 원형 대기 (Circular Wait) : 프로세스들이 원의 형태로 자원을 대기하는 상태
위 네 가지 조건 중 하나라도 만족하지 않으면 교착상태가 발생하지 않습니다.
위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있습니다.
만약 식사하는 철학자 문제에서, 근육 철학자가 있어서 무력을 행사해서 다른 철학자의 포크를 뺏어서 식사를 했다면? 교착 상태가 일어나지 않았을 것입니다. (비선점 조건에 해당하지 않음)
이런 식으로 하나라도 만족하지 않으면 교착 상태가 발생하지 않고, 네 가지 조건을 모두 만족한다면 교착 상태가 발생할 수 있습니다.
3. 교착 상태를 해결하는 방법
그럼 이제 교착 상태를 어떤 방법을 써서 해결하는지 그 방법에 대해서 설명하겠습니다! 이번 글에서는 예방, 회치, 검출 후 회복 이렇게 세 가지 방법으로 교착 상태를 해결하는 것을 설명합니다.
3-1. 교착 상태 예방
교착 상태 예방 방법은 애초에 교착 상태가 발생하지 않도록 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리는 방법입니다.
- 상호 배제를 없애기 : 모든 자원을 공유 가능하게 만든다. ➡️ 이론적으로는 가능하지만, 현실적인 방법은 아닙니다.
- 점유와 대기를 없애기 : 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분 ➡️ 자원의 활용률을 낮출 수 있는 부작용이 발생할 수 있습니다.
- 비선점 조건을 없애기 : 선점이 가능한 자원(ex. CPU)에 한해 효과적인 방법 ➡️ 그러나 모든 자원이 선점 가능한 것은 아닙니다. (ex. 프린터, 한 프로세스가 프린터를 써서 열심히 출력을 하고 있는데 다른 프로세스가 그 프린트를 뺏을 수는 없습니다.)
- 원형 대기 조건을 없애기 : 모든 자원에 번호를 붙이고, 그 붙인 번호의 오름차순대로 자원을 할당하면 원형 대기 조건을 없앨 수 있습니다.
원형 대기 조건을 없애면, 동그란 테이블에서 식사하는 것에서 일렬로 된 식탁에서 식사를 하는 것으로 그래프가 바뀝니다. 그래서 자원에게 붙여진 번호에 맞춰서 자원이 프로세스에 할당되니까 순차적으로 프로세스가 실행되도록 순서를 조정해서 교착 상태를 해결할 수 있습니다.
그러나 원형 대기 조건을 없애는 식으로 교착 상태를 예방, 그니까 자원에 번호를 붙이는 것은 어려운 작업입니다. 어떤 자원에 어떤 번호를 붙이느냐에 따라 자원의 활용률이 달라집니다. 그래서 원형 대기 조건을 없애는 방법은 나머지 세 가지 방법에 비해서 가장 현실적이고 실용적인 방법이지만, 단점도 존재하는 방법입니다.
3-2. 교착 상태 회피
교착 상태를 회피하는 방법은 교착 상태를 "무분별한 자원 할당으로 인해 발생" 했다고 간주합니다. 그래서 교착 상태가 발생하지 않을 만큼만 조심조심 할당하는 방법이 교착 상태 회피 방법입니다. 이 방법은 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분합니다.
교착 상태 회피 방법을 사용하기 위해서는 아래의 세 가지 용어를 이해해야 합니다.
- 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서
- 안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태 (안전 순서열이 있는 상태)
- 불안전 상태 : 교착 상태가 발생할 수도 있는 상태 (안전 순서열이 없는 상태)
안전 순서열, 안전 상태, 불안전 상태를 예시로 설명해 보겠습니다. 컴퓨터 시스템에 총 12개의 자원이 있다고 가정하겠습니다.
프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받아 실행 중이고 (운영체제가 배분할 수 있는 남은 자원의 수는 3개), 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정하겠습니다.
위의 가정대로 프로세스가 실행된다면, P2 ➡️ P1 ➡️ P3 순서대로 자원을 할당한다면 안전하게 모든 프로세스를 정상적으로 실행할 수 있습니다. 만약 위의 예시에서 최악의 상황으로 바꿔서, 최대 요구량대로 각 프로세스가 자원을 요구한다고 해도 안전 순서열(P2 ➡️ P1 ➡️ P3)에 맞춰서 프로세스를 실행한다면 교착 상태 없이 프로세스를 실행할 수 있습니다.
만약 가정을 바꿔서, 아래의 상황에서 운영체제가 P3에게 선뜻 자원 하나를 내줬다면 어떻게 될까요?
이러면 남은 자원이 2개로 줄어들어, 안전 순서열이 없어 교착 상태가 발생할 수 있습니다. 이번에도 P1, P2, P3 프로세스가 모두 최대로 자원을 요구한 최악의 상황을 가정해 보겠습니다. 그러면 P1은 5개, P2는 2개, P3는 6개를 요구하는 상황입니다.
이러면 P3는 6개를 요구했는데 남은 자원은 2개뿐이니 P3에게는 자원을 할당할 수 없습니다. 그러면 P2에게 남은 자원 2개를 할당해서 0개를 만들고, P2 프로세스를 실행한다고 하겠습니다. 그러면 P2 실행 종료 후 반환받은 자원은 4갠데, 자원 4개 가지고 P1이나 P2 그 어떤 프로세스에도 자원을 할당할 수 없는 상태입니다. 왜냐면 P1은 5개를 요구하고, P3은 6개를 요구하는 상황인데, 할당 가능한 남은 자원은 4개뿐이니까요. 이러면 교착 상태가 발생할 위험이 있습니다. (안전 순서열이 없는 상태)
정리하자면, 교착 상태 회피는 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식입니다. 항시 안전 상태를 유지하도록 자원을 할당합니다. 교착 상태 회피를 하는 대표적인 알고리즘으로는 은행원 알고리즘(Banker's algorithm) 이 있습니다.
3-3. 교착 상태 검출 후 회복
교착 상태 검출 후 회복 방법은 교착 상태의 발생을 인정하고, 사후에 조치하는 방식입니다. 프로세스가 자원을 요구하면 일단 할당하고, 교착 상태가 검출되면 회복합니다.
교착 상태 검출 후 회복 방법에는 두 가지가 있습니다. (선점을 통한 회복, 프로세스 강제 종료를 통한 회복)
- 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
- 프로세스 강제 종료를 통한 회복 : 교착 상태에 놓인 프로세스를 모두 강제 종료(➡️ 작업 내역을 잃을 위험), 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(➡️ 오버헤드)
3-4. 교착 상태 무시
교착 상태가 드물게 발생한다면, 이 잠재적인 문제는 그냥 무시하고 진행한다 라는 방법도 있습니다. (타조 알고리즘, Orstrich algorithm)
황당한 방법일 수는 있지만, 문제의 발생 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 이 방법이 적합할 때도 있습니다.
4. 정리
이번 글에서는 교착 상태란 어떤 건지, 교착 상태가 발생하는 원인과 교착 상태를 파악하는 방법, 교착 상태를 해결하는 방법에 대해서 정리해 봤습니다. 다음 글에서는 가상 메모리를 정리할 건데... 정리가 되는대로 돌아오겠습니다. (그전에 은행원 알고리즘을 정리할 수도 있구요 네넹)
그럼 20000!
[자료 출처]
강민철, 《혼자 공부하는 컴퓨터 구조+운영체제》, 한빛미디어, 2022
인프런 - 개발자를 위한 컴퓨터공학 1 : 혼자 공부하는 컴퓨터구조 + 운영체제
🍀
좋아하는 것을 계속 좋아하세요!
반드시 행복해집니다
백엔드 개발자가 되고 싶어서 열심히 헤딩 중인 재영입니다 :-)
[Github] https://github.com/chujaeyeong
[E-mail] chujy1224@gmail.com
'Study > 컴퓨터구조, 운영체제' 카테고리의 다른 글
| 프로세스의 동기화, 동기화 기법에 대해 정리해보자 (0) | 2025.01.10 |
|---|---|
| CPU 스케줄링과 알고리즘을 정리해보자 (0) | 2025.01.08 |
| 스레드를 정리해보자 (스레드의 구성 요소, 멀티 스레드, 멀티 프로세스) (1) | 2025.01.07 |
| 프로세스 상태와 계층 구조에 대해 정리해보자 (0) | 2025.01.07 |
| 프로세스의 개요와 PCB, 메모리 영역에 대해 정리해보자 (0) | 2025.01.07 |
