Chapter 13 교착 상태 - goorm-6th-Als/for_study_Algorithm GitHub Wiki

• 이미지 처럼 일어나지 않을 사건을 기다리며 무한히 대기하는 현상을 뜻합니다.
  

• 완벽하진 않지만 비슷한 예시를 들자면 👀

  • 진수 : 다영님이 과제 끝나면 나도 과제 시작해야지
  • 현빈 : 진수님이 끝내면 나도 시작해야지,
  • 수연 : 현빈님이 끝내고 깃에 올리면 그때 시작해야지,
  • 준수 : 수연님이 끝내면 참고해서 시작해야지
  • 다영 : 준수님이 과제 끝내면 참고해서 과제 끝내야지..
  • 수지 : 나는 나만의 길을 간다. ⛏

위 예시에선 아무도 과제를 하지 않게되는 교착상태가 일어나게 됩니다.

다양한 상황에서 이 같은 교착 상태가 발생하는데 어떤 상황에서 교착 상태인지 판단하기 어렵습니다.
자연어도 어려운데 코드로 작성되어 있으면 더 판단이 어렵습니다.
방금 저희 팀원 이미지 예시로 이해가 편하지 않았나요?
그래서 우리는 이 처럼 교착상태를 확인하려구 그래프를 그립니다.
이를 자원 할당 그래프라고 합니다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
   
2. 사용할 수 있는 자원의 개수를 자원 사각형에 점으로 표기한다.
   
3. 프로세스가 자원을 할당 받아 사용중이라면 자원에서 프로세스를 향해 화살표를 표기한다.
   
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표 표기.
   

• 앞서 저희 팀원 예시를 이미지화 한것처럼 확인할 수 있습니다.
  
• 그럼 이제 그래프 그리는 법은 알았는데 그럼 어떻게 교착 상태를 판단하느냐?
  

1. 상호배제　 :　한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태.
2. 점유와 대기 :　자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태.
3. 비선점 　　 :　어떤 프로세스도 다른 프로세스의 자원을 강제로 못 뺏는 상태.
4. 원형 대기　 :　프로세스들이 원의 형태로 자원을 대기하는 상태.

• 위 네가지 모두 만족하면 교착 상태가 발생할 수 있습니다.

교착 상태의 해결하기 위해서는 이 4가지를 일어나지 않게 예방하거나, 일어날 가능성을 제거하거나, 일어났을 때, 대처하는 경우, 무시가 이 4가지의 방법이 있습니다.

즉 교착 상태을 해결하는 방법은 예방, 회피, 탐지 및 해결, 무시가 있습니다.

교착 상태를 발생하는 4가지 경우 중 하나를 충족하지 못하게하는 방법입니다.

상호 배재를 예방하는 것은 모든 자원을 공유 가능하게 만든다는 말과 같습니다. 현실적으론 모든 자원을 공유하는 것은 무리가 있습니다

프로세스가 실행되기 전에 필요한 모든 자원을 할당하거나, 아예 할당하지 않는 방식입니다.

이 방법을 사용하면 교착 상태를 해결할 수 있지만, 자원의 활용률이 낮아질 우려가 있습니다.

여러 프로세스에 필요한 자원이 겹칠 경우, 다른 프로세스에 필요한 자원들을 몰아줘서 프로세스가 종류될 때까지 자원을 기다려야 하는 상황이 발생합니다.

많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵습니다.

그래서 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상이 발생할 수 있습니다.

자원을 이용중인 프로세스에서 자원을 뺏는 방식입니다.

이 방법이 일부 자원에 대해서는 효과적인 방법이지만 모든 자원을 빼앗을 수 없습니다.

하나의 프로세스의 작업이 끝나고 실행해야 되는 프로세스가 있을 수도 있고, 프린트에 하나의 프로세스가 자원을 받아 출력하고 있는데, 이 과정을 빼앗아 올수는 없습니다.

그렇기에 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착 상태를 예방하는 방법은 다소 범용성이 떨어지는 방식입니다.

모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기가 발생하지 않습니다.

하지만, 하나의 프로세스에 파생되는 프로세스가 있을수도 있고, 모든 수백가지 프로세스가 각각의 번호를 부여하는 것은 쉬운일이 아닙니다.

또한 어떤 번호를 붙이는 지에 따라 특정 자원의 활용률이 떨어질 수도 있습니다.

즉 예방하는 방법은 교착상태를 발생하지 않을 수 있지만, 부작용이 따릅니다.

프로세스들에게 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법입니다

안전 상태는 교착상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종류될 수 있는 상태를 말합니다.

불안전 상태는 교착 상태가 발생할수도 있는 상태를 말합니다.

안전 순서열은 교착 상태 없이 안전하게 프로세스에게 자원을 할당할 수 있는 순서를 의미합니다.

즉 프로세스에게 자원을 할당받은 상태에서 남은 자원에게 필요한 자원을 요청할 때, 필요한 자원이 남은 자원보다 갯수가 클 때, 불안전 상태로 판단하여 다른 프로세스가 요청한 자원을 탐색합니다.

남은 자원의 갯수와 요청한 자원의 갯수가 동일하거나, 남은 자원의 갯수가 많으면, 안전 상태로 판단하고, 안전 순서열에 기록을 합니다.

이런 방식을 반복하여 교착 상태를 회피하게 됩니다.

위와 같이 회피하는 방법을 은행원 알고리즘 입니다.

자원 할당 그래프 알고리즘에 대해서도 알아보세요

이전의 방식들과 달리 교착 상태를 인정하고 사후에 조치하는 방식입니다.

운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사합니다.

그리고 교착 상태가 검출되면 그때 비로소 다음과 같은 방식으로 회복합니다.

선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식입니다.

교착 상태가 해결될 때까지 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식입니다.

교착 상태에 놓은 프로세스를 모두 강제 종료할 수도 있고, 교착 상태가 없어질 때까지 한 프로세스의 강제 종료할 수도 있는 방식입니다.

이러한 방식은 가장 단순하면서 교착 상태를 확실히 해결할수 있습니다.

하지만, 그만큼 많은 프로세스들이 작업 내역을 읽게 될 가능성이 있고, 후자는 작업 내역을 잃는 프로세스는 최대한 줄일수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드가 발생할수도 있습니다.