📢 본 글은 혼공학습단 미션과 함께 정리해보는 글 입니다.
교착 상태란
교통 상황에서 움직이지 못하는 상황이 발생하는 것 처럼, 프로세스 실행 과정에서도 이와 같은 문제가 발생할 수 있다.
또는 아래와 같은 예시가 해당될 수 있다. 🥲
두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 교착 상태가 된다.
식사하는 철학자 문제
식사하는 철학자 문제는 교착 상태가 어떤 상태에서 발생하는지, 어떻게 해결할 수 있는지를 볼 수 있는 문제이다.
1️⃣ 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2️⃣ 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3️⃣ 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4️⃣ 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5️⃣ 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6️⃣ 다시 1️⃣ 번부터 반복한다.
이때 모든 철학자들이 왼쪽 포크를 사용할 경우 오른쪽 포크를 사용하지 못할 것 이다.
포크는 실행에 반드시 필요한 자원, 식사를 하는 것은 자원을 사용하는 것에 해당된다.
교착 상태
게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다리는 상황과 같고, 이 경우에는 게임과 웹 브라우저 프로세스가 상대방이 가진 자원을 기다리기만 하다가 실행을 못 하는 상황이 일어난다. 이를 교착 상태라고 한다.
해결법
교착 상태를 해결하기 위해서는 교착 상태가 발생했을 때의 상황을 정확히 표현해야 하며, 교착 상태가 일어나는 근본적인 이유를 이해해야 한다.
자원 할당 그래프
교착 상태가 발생했을 때의 상황을 파악하기 위한 그래프를 자원 할당 그래프라 한다.
교착 상태가 어떤 조건에서 발생하는지 대략적으로 파악, 어떤 프로세스가 어떤 자원을 할당 받아 사용중인지 확인, 어떤 프로세스가 어떤 자원을 기다리고 있는지 등을 확인할 수 있다.
1️⃣ 프로세스는 원으로 그리고, 자원의 종류는 사각형으로 표현한다.
2️⃣ 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다. (아래 그림에서는 스킵)
3️⃣ 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표현한다.
4️⃣ 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.
식사하는 철학자 문제를 나타내면 다음과 같다.
위의 예시인 게임과 웹 브라우저를 나타내면 다음과 같다.
이 둘을 통해, 자원 할당 그래프가 원의 형태를 띠었을 경우 교착 상태가 일어남을 알 수 있다.
교착 상태 발생조건
교착 상태의 발생 조건 네 가지가 모두 성립하면 교착 상태가 발생한다.
상호 배제
상호 배제 (mutual exclusion)는 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태를 뜻한다.
점유와 대기
점유와 대기 (hold and wait)는 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 뜻한다.
비선점
비선점 (nonpreemption)은 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태를 뜻한다.
원형 대기
원형 대기 (circular wait)는 프로세스들이 원의 형태로 대기하는 것을 뜻한다. (원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다. 그러나 교착 상태가 일어나기 위해서는 이 조건이 충족되어야 한다.)
교착 상태 해결 방법
교착 상태 (deadlock)를 해결하기 위한 방법으로는 크게 세 가지가 있다.
교착 상태 예방 (prevent)
애초에 교착 상태가 일어나지 않도록 예방하는 방법이다.- 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없앤다.
상호 배제 (mutual exclusion)를 없앨 경우: ❌
상호 배제를 없앤다면 여러 프로세스가 동시에 자원에 접근이 가능할 것이다. 이것은 현실적으로 불가능하다.
점유와 대기 (hold and wait)를 없앨 경우: ❌
점유와 대기는 자원을 할당받은 상태에서 자원을 대기하는 것이다.
특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 한다면 자원의 활용률을 낮출 수 있다.
그러나 자원의 활용도가 너무 떨어질 수 있다.
지금 당장 자원이 필요한데 사용하지 못하는 프로세스가 있을 수 있으며, 할당을 받지 못해 오랫동안 대기해야 하는 프로세스가 있을 수도 있으며, 프로세스에게 모든 자원을 할당했는데 어떤 자원은 별로 쓰지 않아 낭비될 수 있다.
비선점 조건 (no preemption)을 없앨 경우: ❌
비선점은 한 프로세스가 다른 프로세스의 자원을 뺏을 수 없는 조건이다.
이 조건을 없앤다면 선점이 가능한 자원 (CPU 등)에 한해서는 효과적이겠으나, 모든 자원이 선점 가능한 것은 아니기에 불가능하다.
결론: 원형 대기 (circular wait) 없애기: ✅
모든 자원에 번호를 붙이고, 그 붙인 번호의 오름차순대로 자원을 할당하면 원형 대기 조건을 없앨 수 있다.
식사하는 철학자 문제에서 자원인 포크에 번호를 할당하고, 철학자들에게 낮은 포크에서 높은 포크를 집도록 요구한다.
마지막에 5번 포크를 들고 1번 포크는 들지 못할 것이다. (그 전까지는 1번 포크와 2번 포크를 동시에 드는 등이 가능하지만)
그런데 이 방식도 약간의 단점이 있다.
자원에 번호를 붙이는 것은 어려운 작업이며, 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.
그러나 가장 실용적인 방식이다.
교착 상태 회피 (avoidance)
- 교착 상태를
무분별한 자원 할당으로 인해 발생했다고 간주한다. 교착 상태가 발생하지 않을 만큼 조심스럽게 할당한다.- `배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분`한다.
안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식이기도 하다.은행원 알고리즘 (banker’s algorithm)이 이것에 해당한다.
용어 이해
안전 순서열
교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 뜻한다.
안전 상태
교착 상태 없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태를 뜻한다. 안전 순서열이 있다.
불안전 상태
교착 상태가 발생할 수도 있는 상태를 뜻한다. 안전 순서열이 없다.
예시
- 컴퓨터 시스템에 총 12개의 자원이 있다고 가정한다.
- 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받아 사용 중이다.
- 운영체제가 배분할 수 있는 자원의 갯수는 3개이다. (남은 게 3개이므로)
- 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다.
P1, P2, P3이 각각 최대 자원 요구를 하기 위해 5개, 2개, 7개를 더 요구했다고 가정한다.
P2를 먼저 해 보면, P2에게 2개를 주면 남은 자원은 1개이다.
이제 P2의 작업이 끝나면 반환된다. 남은 자원은 5개이다.
P1을 다음으로 해 보면, P1에게 5개를 주므로 남은 자원은 0개이다.
P1의 작업이 끝나면 반환되기에 남은 자원은 10개이다.
마지막으로 P3을 하면, P3에게 7개를 더 주므로 남은 자원은 3개이다.
이렇듯 P2→P1→P3 순서로 제공하면 (안전 순서열), 모든 프로세스가 실행 가능하다. (즉, 안전 상태)
그러나 만약 처음의 상태에서 운영체제가 P3에게 자원 하나를 내주었을 때를 가정해보자.
남은 자원은 2개가 될 것이다. 이런 상황에서는 교착 상태가 발생할 위험이 있다. (즉, 불안전 상태)
이 경우에는 P1이 5개, P2가 2개, P3이 6개의 자원을 추가로 요구한다.
P2에게 제공한 뒤 P2의 최대 요구량인 4개를 반환해줘도, P1은 5개가 필요하며, P3은 6개가 필요하기 때문에 충족될 수 없기 때문이다.
교착 상태 검출 후 회복 (detection & recovery)
교착 상태의 발생을 인정하고사후에 조치하는 방식이다.프로세스가 자원을 요구하면 일단 할당하고,교착 상태가 검출되면 회복한다.선점을 통한 회복: 교착 상태가 해결될 때 까지한 프로세스씩 자원을 몰아준다.프로세스 강제 종료를 통한 회복- 교착 상태에 놓인
프로세스 모두를 강제 종료한다. →작업 내역을 잃을 위험이 있다. - 교착 상태가 해결될 때 까지
한 프로세스씩 강제 종료한다. →오버헤드 발생 위험이 있다.
- 교착 상태에 놓인
여담: 교착 상태 무시
교착 상태가 드물게 발생한다면, 이 잠재적인 문제는 그냥 무시하자는 알고리즘도 있다. 대표적인 예시로는 타조 알고리즘이 있다.
빈도 수, 심각성에 따라 최대 효율성을 추구해야 하는 엔지니어에게는 때로 이 알고리즘이 적합할 수도 있다.
미션
- 363p 문제 1번 인증
- 뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것
- 1️⃣ 뮤텍스 락은 임계 구역을 잠근 뒤 임계 구역에 진입함으로써 상호 배제를 위한 동기화를 이룬다. - 탈의실 예를 생각하면 된다.
- 2️⃣ 세마포는 공유 자원이 여러 개 있는 상황에서도 이용할 수 있다. - 뮤텍스 락에서 공유 자원이 여러 개 있을 수 있는 상황이 세마포이다.
- 3️⃣ 세마포를 이용해 프로세스 실행 순서 제어를 위한 동기화도 이룰 수 있다. - wait과 signal을 통해 실행 순서 제어를 할 수 있다고 하였다.
- 4️⃣ 세마포를 이용하면 반드시 바쁜 대기를 해야 한다. - 바쁜 대기 (busy waiting)을 함으로써 CPU에게 부담을 줄 수 있다고 하였고, 이를 개선할 방법 또한 가지고 있다고 하였다.
- 따라서 최종 답은 4번이다.
- 뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것
부족하거나 보완할 점이 있다면 댓글 부탁드립니다 😃
