13장 교착상태

13-1 교착상태란

• 교착상태:일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상

기아현상과의 차이는?

• 교착상태는 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태
• 기아상태는 프로세스가 원하는 자원을 계속 할당받지 못하는 상태

• 교착상태는 여러 프로세스가 동일한 자원 점유를 원할 때 발생, 기아상태는 여러 프로세스가 자원을 점유하기 위해 경쟁할 때 특정 프로세스는 영원히 자원 할당을 받지 못하는 것

자원할당 그래프

1. 프로세스는 원, 자원의 종류는 사각형
2. 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현

• ex) 하드디스크 세 개: 자원의 종류(하드디스크 1종류), 사용 가능한 하드디스크 개수는 3개
• 

3. 프로세스가 어떤 자원을 할당받아 사용중이라면, 자원에서 프로세스를 향해 화살표를 표시

• 자원 👉 프로세스
• 자원이용을 마치면 화살표는 삭제된다.

4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

• 프로세스 👉 자원

식사하는 철학자 문제

• 포크: 자원
• 철학자: 프로세스
• 왼쪽 포크를 든 채, 오른쪽 포크를 들고 기다리고 있는 상황이다.

교착상태 예시

• 게임 프로세스는 자원 A를 할당받은 상태에서 웹 브라우저 프로세스가 할당 받은 자원 B의 사용이 끝나길 기다리고 있다. (반대로 웹브라우저의 상황도 같다.)
• 
• 원의 형태를 띄고 있다는 점!

교착상태 발생 조건

• 아래 조건들이 모두 만족될 때, 교착상태가 발생할 가능성이 높다고 보면 된다.

상호 배제

• 프로세스도 마찬가지로, 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 상호 배제 상황에서 교착상태가 발생할 수 있다.

점유와 대기

• 왼쪽 포크를 들고 다른 철학자의 포크를 기다렸기 때문이다.
• 자원을 보유한 채 다른 자원을 기다렸기 때문에 문제가 발생
• 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

비선점

• 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문

원형대기

• 자원 할당 그래프가 원의 형태로 자원을 대기하는 것
  

p376

1. 4
2. 상호배제, 비선점, 원형대기, 점유와대기
3. 2

13-2 교착상태 해결방법

• 예방, 회피, 검출 후 회복

교착 상태 예방

• 앞서 말한 교착상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법과 같다.

상호배제 없애기?

• 모든 자원 공유 가능하게 만든다
• 현실적으로 모든 자원의 상호배제 없애기에는 어렵기에 현실적으로 무리가 조금 있다.

점유와 대기?

• 포크를 두 개 동시에 들게 하거나, 아니면 아예 들지 못하게 하는 것

• 운영체제는 특정 프로세스에 자원을 모두 할당, 또는 아예 할당하지 않는 방식으로 배분

• 단점: 자원의 활용률이 낮아진다.

  • 한 프로세스에 필요한 자원들을 몰아주고, 그 다음 다른 프로세스에 필요한 자원들을 몰아준다.

  • 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다.

  • 많은 자원을 사용하는 프로세스가 불리해진다.

    • 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵다.
    • 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아현상을 야기할 우려 발생

비선점 조건?

• 자원 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다.
• 철학자의 포크를 빼앗을 수만 있다면 교착 상태 발생하지 않듯, 자원의 비선점 조건을 없애면 교착 상태는 발생하지 x
• 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적
• ex) CPU 프로세스들이 선점할 수 있는 대표적인 자원
• 한 프로세스의 작업이 끝날 때까지 다른 프로세스가 기다려야하는 자원도 있어 범용성에서 떨어진다.

원형 대기 조건?

• 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당
• 모든 포크에 1~5번까지 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크에서 높은 포크를 집어들게 하면 원형 대기 발생 x
• 
• 일렬로 앉아 식사하는 상황
• 비교적 현실적이지만 단점 존재
  • 모든 컴퓨터 시스템 내 존재하는 수많은 자원에 번호를 붙이는 일은 쉽지 않다.
  • 각 사원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 조심조심 자원을 할당하는 방식
• 포크의 양이 충분하지 않은 상태에서 철학자들이 한두 개의 포크를 요구하면 교착 상태는 발생하지 않는다.
• 안전 상태: 교착상태가 발생하지 않고, 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안전 상태: 교착상태가 발생할 수도 있는 상황, 안전 순서열이 없는 상황
• 안전 순서열: 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서를 의미
  • 웹 브라우저 👉 메모장 👉 게임

교착 상태 검출 후 회복

• 교착상태 발생을 인정하고, 사후에 조치하는 방식
• 검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당,
  교착 상태 발생 여부를 주기적으로 검사한다.

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식

프로세스 강제 종료를 통한 회복

• 운영체제는 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도,
  • 단점: 그만큼 많은 프로세스들이 한꺼번에 작업 내역을 잃게 될 가능성이 있다.
• 한 프로세스씩 강제 종료할 수도
  • 단점: 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만, 교착상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.

타조알고리즘

• 교착 상태를 아예 무시하는 방법
• 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식
• 

388p
1. 2
2.
3. 2
4. 4