13장 교착상태

• 교착 상태

  • 식사하는 철학자 문제

    • 동그란 원탁에 다섯명의 철하자가 앉아있다. 이 철학자들 앞에는 음식이 있고 철학자 사이마다 식사에 필요한 포크고 있다.
    1. 계속 생각하다가 왼쪽 포크가 사용가능하면 집어든다.
    2. 계속 생각하다가 오른쪽 포크가 사용가능하면 집어든다
    3. 왼쪽가 오른쪽 포크가 모드 집어들면 정해신 시간동안 식사한다.
    4. 식사가 끝나면 오른쪽 포크는 내려 놓는다.
    5. 오른쪽 포크를 내려 놓은 뒤 왼쪽 포크를 내려 놓는다.
    6. 다시 1번부터 반복한다.
    • 문제
      • 한두명의 철학자가 음식을 먹을때는 상관이 없다.
      • 하지만 모든 철학자가 동시에 포크를 집으면 더 이상 집을 포크가 없어 아무도 식사를 할 수 없다.
      • 이를 교착 상태라 한다.

    • 자원 할당 그래프

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

    • 교착 상태 발생 조건

      • 상호 배제

        • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 발생

        • 점유와 대기

          • 철학자 문제와 같이 자원을 할당받은 상태에서 다른 자원을 할당받기 기다리는 상태

        • 비선점

          • 자원을 사용하는 프로세스가 끝나야 사용 가능한 상태
          • 자원을 사용중인 프로세스를 강제로 빼앗지 못함

        • 원형 대기

          • 자원 할당 그래프가 원의 형태로 그려지면 교착상태가 발생할 수 있음

• 교착 상태 해별 방법

  • 예방

    • 상호 배제를 제거

      • 이론적으로는 가능하지만 현실적이지 못함

      • 점유와 대기를 제거

        • 이론적으로 가능하지만 현실적이지 못함
        • 자원 활용률이 낮아지고 기아 현상이 일어날 수 있다.

      • 비선점 조건 제거

        • 일부 자원에서는 효과적이나 범용성이 떨어진다.

      • 원형 대기 조건 제거

        • 순서를 매겨 해결 가능하지만 특정 자원의 활용률이 떨어질 수 있다.

    • 회피

      • 안전 순서열

        • 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서를 의미
        • 이 때, 교착 상태가 일어나지 않는 안전 순서열을 안전 상태, 안전 순서열이 없는 상태를 불안전 상태라 한다.
        • 안전 상태 : 교착 상태가 발생하지 않고 정상 종료될 수 있는 상태
        • 불안전 상태 : 교착상태가 발생할 수도 있는 상태

    • 검출 후 회복

      • 선점을 통한 회복

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

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

          • 가장 단순하며 확실한 방법
          • 작업내역을 잃게 될 가능성이 있다.

    • 무시

      • 타조 알고리즘

        • 교착 상태의 발생 빈도나 심각성이 낮다고 판단할 때 교착 상태를 무시

참고) 혼자 공부하는 컴퓨터 구조+운영체제