[운영체제] 7강 - 교착상태(2)

✅ 1. 교착상태 회피

(1) 교착상태 회피란?

• 교착상태 예방: 교착상태가 일어날 수 있는 조건 4가지 중 하나를 제거하는 방식으로 예방을 시도 했음.
• 즉, 4가지 필수 조건 중 하나를 아예 제거해버리는 아주 보수적이고 엄격한 규칙을 적용하는 느낌이었음.
• 교착상태 회피: 프로세스의 자원 사용에 대한 사전 정보를 활용해 교착상태가 발생하지 않는 상태를 계속해서 유지해주는 방법을 의미한다.
• ** 즉, 예방처럼 무조건 막는게 아닌, 자원 요청이 들어올 때마다 나중에 문제가 생길지 미리 계산해보고 안전할 때만 빌려주는 방식으로 보면 됨. **
• 사전 정보: 현재 할당된 자원 정보, 가용상태의 자원 정보, 프로세스들의 최대 요구량에 대한 정보가 필요함.

(2) 안전상태와 안전순서열

• 안전상태: 사전 정보를 기반으로 계산했을 때, 교착상태를 회피하면서 프로세스의 자원 요구량을 모두 충족할 수 있는 상태인 즉, 프로세스가 원하는 자원들을 모두 할당 할 수 있는 상태를 안전상태라고 부름.
• 결론은 안전순서열이 존재하는 경우가 될 수 있음.
• 불안전상태: 안전상태와 상반되게 교착상태가 발생할 수 있는 안전순서열이 존재하지 않는 경우 불안전상태로 볼 수 있음.
• ** 단, 불안전상태는 교착상태가 발생할수도 있고, 안할 수도 있음. **
• 핵심: 안전순서열이 존재하느냐 안하느냐에 따라 안전상태와 불안전상태로 갈릴 수 있으며, 안전상태를 유지하는게 핵심임.

(3) 안전순서열

• 안전순서열: 순서가 존재하는 프로세스들의 집합을 의미함. ( 즉, 프로세스들을 순서대로 나열할 수 있어야 함 )
• 프로세스 순서 결정 기준: 프로세스가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나 혹은 여기에 할당된 자원까지 포함하여 충당 가능한 경우에 따라서 순서가 결정이 된다.

p1(최대요구량:5, 현재 빌린 자원개수:0)
p2(최대요구량:2, 현재 빌린 자원개수:1)
p3(최대요구량:8, 현재 빌린 자원개수:5)
r1(자원총개수:8개, 현재자원개수:2)

• 위의 이미지에 대한 예시를 들면, 현재 가용 가능한 자원의 상태를 보면, 2개를 더 빌릴 수 있는 상태이며 p1 은 5개를 추가로 빌려야 하며, p2는 1개를 추가로 빌려야 하고, p3 는 3개를 추가로 빌려야 하는 상태이다.
• 이 상태에서 r1의 남은 자원의 개수는 2개이므로, 한 번에 빌릴 수 있는 프로세스는 p2가 1개를 추가적으로 빌릴 수 있게 되어 p2가 먼저 빌리게 된다.
• 이후, p2가 자원을 사용 후 반납하게 되면, r1의 자원 개수는 4개가 되기 때문에 p1은 5개, p3는 3개가 필요한 상황이므로, p3 가 4개중 3개의 자원을 빌려가게 된 후, 반납 후 p1이 5개를 빌리는 순으로 프로세스 순서가 결정이 되게 된다.
• 즉, 현재 가용상태의 자원으로 충당을 한 뒤, 여기에 할당된 자원까지 포함하여 충당 가능한 경우에 따라서 순서가 결정이 됨.
• ** 결과적으로, p2, p3, p1 순으로 안전 순서열이 결정이 되며, 해당 상태를 안전상태라고 부르게 됨. **

• 시각 T2: p1 이 만약 1개가 필요하다고 해서, r1에 남아있던 2개 중 1개를 가져간 경우 p2 는 r1에서 1개를 가져다가 사용을 하고 반납을 하게 되어, p2가 먼저 수행이 되어 반납이 될 것이고, 두 번째로는 p1(4개), p3(3개) 필요한 상황인데, r1에는 현재 2개 밖에 가용 자원이 없기 때문에 안전 순서열이 존재하지 않아 불안전상태가 될 것임.
• ** 즉, 가용 상태의 단위 자원이 있다고 해도, 최대요구량에 맞춰서 처리를 해주고 반납을 해주는 것을 우선적인 목표로 삼아야 안전 순서열이 만들어져 안전상태가 됨. **
• 정리: 이러한 불안전상태가 되는 요구를 막아주는 역할이 교착상태 회피임.

(4) 교착상태 회피 - 정리

• 정리하면, 교착상태 회피에서 교착상태는 안전순서열이 존재하지 않는 불안전상태에서만 발생이 가능하며, 항상 안전상태를 유지하는 것이 목표이며, 프로세스가 가용상태의 자원을 요구하더라도 최대요구량에 맞춰서 처리를 해주고 반납을 해주는 것을 목표로 해야하기 때문에 대기상태가 될 수 있음.
• 가용자원이 있음에도 자원 할당 이후에도 각 프로세스가 최대 요구량까지 모두 만족하고 종료될 수 있는 순서(안전 순서)가 존재할 때만 할당이 되기 때문에, 자원이용율은 다소 낮아질 수 있음.

(5) 교착상태 회피 - 알고리즘

• 각 자원의 단위자원이 하나밖에 없는 경우: 변형된 자원할당 그래프를 이용하여 교착상태 회피를 할 수 있음.
• 각 자원의 단위자원이 여러 개일 수 있는 경우: 은행원 알고리즘 이용하여 교착상태 회피를 할 수 있음.

(6) 교착상태 회피 - 알고리즘 ( 변형된 자원할당 그래프 )

• 기존 자원할당 그래프: 요구간선, 할당간선 2종류의 간선이 존재했음.
• 변형된 자원할당 그래프: 단위자원 개수 표시를 제거한 상태이며, 선언간선이 추가 된 자원할당 그래프를 의미한다.
• 선언간선: 프로세스에서 자원으로 향하는 간선이며, 해당 프로세스가 앞으로 해당 자원에 요청을 할 수 있다는 의미임.
• ** 요구간선과 구분을 위해 점선으로 표시를 하며, 앞으로 프로세스가 자원을 요구하게 될 것임을 명시함. **

• 변형된 자원할당 그래프로 교착상태 회피를 하는 방법으로 그래프상에서 진행을 해보고 문제가 없다면 실제로 수행함.
• (1) 자원을 요구받으면 해당 선언간선을 요구간선으로 변경
• (2) 그래프상에서만 그 요구간선을 할당간선으로 변환해 계산을 해보고 사이클이 생기지 않는 경우에만 실제로 자원을 할당하고 할당간선으로 변환을 하게 됨.
• 안전상태 예시: 예시를 보면, p1이 r2를 요구하는 경우에 선언간선을 요구간선으로 변경을 해주고, 그래프 상에서 확인해 본 결과 사이클이 발생하지 않으므로, 안전상태로 보고 할당간선으로 변경을 해주게 됨.
• 불안전상태 예시: 또 다른 불안전상태에 대한 예시를 보면, p2가 r2를 요구하는 경우 p2 는 r1을 요구하는 상황이고, p1은 r1을 이미 빌리고 있는 상황이기 때문에 p2에게 r2를 할당하게 된다면, p1이 r2를 선언간선으로 가지고 있기 때문에 서로의 자원을 요구하는 상황이되어, 사이클이 발생해 교착상태가 될 수 있음. 즉, 불안전상태이며, 이 경우에는 자원을 할당하지 않게 됨.
• 정리: 자원의 단위자원이 하나밖에 없는 경우에는 변형된 자원할당 그래프 만으로 판단해 교착상태를 해결 할 수 있음.

(7) 교착상태 회피 - 알고리즘 ( 은행원 알고리즘 )

• 은행원 알고리즘: 자원을 요구받으면 해당 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인을 하고, 안전상태가 보장되는 경우에만 자원을 할당해주는 방식의 알고리즘임.
• 은행원 알고리즘 또한, 변형된 자원할당 그래프와 동일하게, 자원 요구에 따라 할당을 해준다면 안전순서열이 존재하는가에 대한 계산만을 미리 해보는 알고리즘이라고 보면 됨.
• 은행원 알고리즘 예시: 위의 그림과 같은 예시를 살펴보면 최대요구량, 할당자원, 추가요구, 가용자원 등을 실제로 변수로써 만들어서 계산을 하는 것으로 보면 됨.
• MAX: 프로세스의 최대요구량 ( ex: p1 = 5, p2 = 2, p3 = 8 )
• ALLOC: 현재 프로세스에 할당 되어있는 자원의 양 ( ex: p1 = 0, p2 = 1, p3 = 5 )
• NEED: 프로세스에 앞으로 얼마나 더 자원이 필요한지 나타내는 양 ( ex: pr1 = 5, p2 = 1, p3 = 3 )
• AVAIL: 현재 자원에 있는 가용자원의 양 ( ex: r1 = 2개가 남아있음 )
• ** 또한, 자원의 종류가 r1, r2, r3.. 늘어남에 따라서, 변수의 괄호의 값이 ALLOC(0,3,5,...) 이런식으로 늘어날 수 있음. 즉, 여러개의 값들을 변수 하나로 관리한다고 보면 됨. **

• 핵심 부분은 safe() 함수이며, 해당 함수를 통해서 안전순서열이 존재하는가를 계산해서 파악을 할 수 있음.

• p1(MAX): MAX(최대요구량) 의 값이 r1에게는 7개를 요구하며, r2에는 5개를 요구하고 있음.
• p1(ALLOC): ALLOC(현재할당량) 의 값이 r1에게서 0개, r2에게서 2개를 할당받고 있음.
• p1(NEED): NEED(추가할당량) 의 값이 r1에게서 7개가 필요하며, r2에게서는 3개가 추가적으로 필요함.
• p2(MAX, ALLOC, NEED): p1와 동일하게 최대요구량, 현재할당량, 추가할당량이 r1, r2에 대해서 각각 존재함.
• p3(MAX, ALLOC, NEED): p1, p2와 동일하게 r1, r2에 대해 존재함.
• AVAIL: AVAIL(가용자원양)이 현재 p1,p2,p3 에게 r1,r2 자원들이 할당을 해주고 남은 값인 (3,3) 의 값이 들어가 있음.
• 안전 알고리즘 실행: AVAIL(가용자원양)의 변수값을 가지고와서 WORK 변수에 넣게되며, WORK와 p1,p2,p3 각 프로세스의 NEED(추가할당량) 변수의 값과 비교 후 가용자원양보다 같거나 적어서 할당이 가능한 경우만 false 초기 상태를 true로 변경해주며, 안전 순서열에 넣게 됨.
• ** 즉, AVAIL = (3,3) 인데, p1와 p3는 각각 NEED 값이 AVAIL 보다 크기 때문에 조건을 만족하는 p2가 먼저 자원을 모두 할당 받아 처리 후 자원을 반납해 다음 p3 -> p1 순으로 처리가 되는 것임. **
• 결과적으로 p2, p3, p1 안전 순서열이 만들어질 수 있으며, 안전상태가 됨.

• (1) p1 이 r1과 r2 에게 각 1,1 씩 자원을 원해서 가져간 상태 -> AVAIL = (2, 2) 인 상태
• (2) p2 의 NEED 는 2, 1 이므로, AVAIL(현재가용량) 이 2, 2 라 자원을 빌릴 수 있음.
• (3) p2가 할당을 받고 처리를 한 뒤 반납을 하면 AVAIL(현재가용량)은 3,7 로 변함.
• (4) AVAIL(현재가용량) 이 3, 7 로 p1 또는 p3 프로세스는 NEED 를 더 이상 할 수 없으므로, 불안전상태가 됨.
• safe 함수: 즉, 이렇게 실행 가능한 프로세스를 반복적으로 찾으며, FINISH 배열의 모든 요소가 true 인 상태가 안전 상태로 볼 수 있으며, safe 함수가 안전한지를 판단을 해주는 핵심 로직임.
• ** 또한, 이렇게 시뮬레이션을 돌려본 결과로 REQ = (1, 1) 로 인해 불안전상태가 된 것을 알 수 있기 때문에 REQ 의 요청을 들어주면 안된다고 판단해 안들어주게 됨. **
• ** 결론은 불안전상태로 교착상태가 될 가능성이 존재하게 됨. **

---

✅ 2. 교착상태 탐지 및 복구

(1) 교착상태 탐지 및 복구 방식이란?

• 교착상태 탐지 및 복구 방식은 교착상태가 일어났을 때 즉, 사후에 처리하는 방법이다.

• 교착상태 회피 단점: 각 프로세스의 최대할당량을 알아야하며, 해당 값을 전제조건으로 돌리게 되는데 문제는 최대할당량을 미리 다 알고 있기에는 쉽지가 않다는 단점이 존재함.
• 또한, 안전순서열을 돌리는건 매 순간마다 돌리게 되는데 시스템에 부담이 되는 단점도 존재함.
• 그래서 회피보단 차라리 탐지 및 복구에 대한 접근을 하게 됨.
• 교착상태 탐지: 시스템의 교착상태 여부를 조사하기 위해 매 순간마다 탐지는 하는 것은 아니며(시스템에 부담이 되기 때문), 적당한 시점마다 주기적으로 상태 조사 알고리즘이 수행이 되게 됨.
• 교착상태 복구: 교착상태 탐지를 통해 교착상태 복구 작업이 들어가며, 적절한 조치를 통해 정상상태로 복구를 하게 됨.

(2) 교착상태 탐지

• 교착상태 탐지 알고리즘은 앞서 본 은행원 알고리즘과 동작과정은 거의 비슷함.
• 다만 차이점은 현재 실제 상태를 체크하고 있기 때문에 NEED 는 필요하지 않음.
• 쉽게 말해, 교착상태 회피의 경우 지금 당장 자원을 줘도 미래까지 안전한지 미리 시뮬레이션 해보고 안전하면 할당하는 느낌이지만 교착상태 탐지의 경우 자원을 빌리고 반납하는 과정이 계속 일어나는 상황에서 특정 시점에 탐지 알고리즘을 통해 현재 점유/요청 상태를 통해 파악을 하게 되는 원리임.
• 탐지를 통해 교착상태 여부를 파악한 뒤에는 복구작업을 추가적으로 진행을 해줘야함.

• 시간복잡도가 O(mn^2) 이기 때문에, 계속해서 탐지 알고리즘을 돌리기에는 효율적이지 못함.
• 탐지 알고리즘 수행 시점:
• (1) 정해진 시간간격에 의해 수행이 됨.
• (2) 프로세스가 자원을 요구했는데 할당이 안되는 경우
• (3) CPU 효율이 일정 수준 이하로 떨어질 때
• ** 탐지 알고리즘은 이와같은 상황에서 수행이 됨. **

(3) 교착상태 복구

• 교착상태가 탐지되면 복구를 진행하게 됨.
• 복구 주체: 오퍼레이터(사람)이 수작업으로 복구 또는 운영체제가 자동으로 복구를 진행할 수 있음.
• 복구 방법: 교착상태 프로세스를 종료 시키거나, 교착상태 프로세스가 할당받은 점유 자원을 해제하는 방법이 있음.

• ** 교착상태 프로세스를 종료 시키는 방법으로 크게 2가지 방법이 존재함. **
• 방법1: 교착상태에 관여하는 모든 프로세스를 종료시키는 방법
• 단점: 진행했던 내용에 대한 복원비용이 크다는 단점이 존재함.
• 방법2: 사이클이 제거될 때까지 교착상태 프로세스를 하나씩 종료하면서 진행하는 방법
• 단점: 어떤 프로세스를 먼저 종료할지 종료 대상을 선택하는데 추가적인 비용이 들며, 매 프로세스 종료 후 교착상태 재확인을 또 해줘야 하기 때문에 추가적인 비용이 듦.

• ** 교착상태 프로세스가 할당받은 자원을 해제하는 방법이며, 사이클이 제거될 때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에 할당하는 방식임. **
• 프로세스와 자원 선택 기준: 프로세스 진척도, 사용 중인 자원의 수등을 고려하여 자원을 해제해줘야 하며, 예를들면 p1 의 진척도가 90%, p2 의 진척도가 10% 인 경우 90% 의 p1 의 자원을 해제 시키면 그만큼 많은 자원이 해제가 되므로, 많은 프로세스들이 진행이 될 가능성이 높지만, 해제 후 다시 복구하는 비용이 크다는 단점이 있다. 반면, 10% 인 p2 의 자원을 해제 시키면 복구 비용은 낮지만, 그만큼 적은 자원을 가지고 있으므로 많지 않은 프로세스들이 진행이 될 수 있는 단점이 있음.
• 프로세스의 복귀 시점도 제반 요소를 고려하여 결정: 자원 해제 시 해당 프로세스의 자원을 모두 뺄 것인지 아니면 하나씩 빼면서 체크를 할 것인가에 대한 내용임.
• 기아상태에 빠지지 않도록 프로세스 선택 시 복구 횟수 고려: 자원을 해제당한 프로세스가 복귀 시점에 교착상태가 또 일어나 자원을 또 해제당하는 기아상태에 빠질 수 있기 때문에 프로세스 선택 시 복구 횟수를 고려해야함.

(4) 교착상태 정리

• 교착상태 예방: 교착상태 4조건 중 하나를 무조건 깨버리는 방식
• 교착상태 회피: 지금 요청을 허용했을 때 안전한지 시뮬레이션해서 판단
• 교착상태 탐지 및 복구: 일단 실행하고, 문제 생기면 그때 교착상태를 처리
• 교착상태 예방, 교착상태 회피 방식은 현실에서는 거의 안 쓰고, 실제 시스템에서는 보통 탐지 및 복구 쪽을 더 많이 선택함.

(5) 여기까지 정리

• 프로세스 관리자: 전체 주방장 (총괄)
• CPU 스케줄링: 손님(프로세스)에게 요리(CPU 자원)를 나가는 순서를 정하는 배차/순번 시스템
• 병행성/임계영역/동기화: 여러 요리사가 좁은 주방에서 **공동 도구(공유 자원)**를 쓸 때 싸우지 않게 하는 주방 규칙
• 교착 상태: 두 요리사가 서로의 도구를 기다리며 아무것도 못 하는 마비 상태를 푸는 대책