Ch06. 교착 상태_03)교착 상태 해결 방법

<쉽게 배우는 운영체제> 교재를 참고하였습니다.

교착 상태 해결 방법

교착 상태 해결 방법

• 교착 상태 예방(prevention) : 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식으로 교착상태 조건 4가지에 대하여 각각의 방법이 존재함
  • 교착상태는 상호배제, 비 선점, 점유와 대기, 원형대기라는 네 가지 조건을 충족해야 발생하기 때문에 이 중 하나라도 막으면 교착상태가 발생하지 않음
  • 그러나, 이 방법은 실효성이 적음
• 교착 상태 회피(avoidance) : 교착상태가 발생하지 않도록 자원 할당량을 조절하여 교착 상태를 회피하는 방식
  • 즉, 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것
  • 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적음
• 교착 상태 검출(detection)과 회복(recovery) : 교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링 하면서 교착 상태가 발생하는지 살펴보는 방식으로 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행됨
  • 교착 상태를 검출한 후 이를 회복시키는 것은 결론적으로 교착 상태를 해결하는 현실적인 접근 방법임

---

교착 상태 예방

교착 상태 조건 4가지에 대하여 각각의 방식이 존재

• 교착 상태 예방은 교착 상태를 유발하는 4가지 조건 중 하나라도 발생하지 않도록 막아 교착 상태를 처리하는 방법
• 말 그대로 사전 예방하는 것이므로 아래와 같은 4가지 방법이 있음

상호 배제 예방

• 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애 버리는 방법
• 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않음
• 식사하는 철학자 문제에서도 모든 철학자가 포크를 누가 점유하는 것이 아니라 공유할 수 있다면 교착 상태가 발생하지 않을 것임. 변수나 파일도 공유하면 교착상태가 없음.
• 그러나 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음 (예: 포크 공유 - 포크를 공유화하여 동시에 사용한다는 것은 말이 안 됨)
• 또한 자원을 공유하게 됨으로써 임계구역(critical section)이 보호받지 못하는 문제가 생기기도 함 (예금문제: 입금한 돈)
• 상호 배제를 무력화하는 것은 사실상 어려움

비선점 예방

• 모든 자원을 빼앗을 수 있도록 만드는 방법
• 식사하는 철학자 문제에서 옆 사람의 포크를 빼앗을 수 있다면 교착 상태가 발생하지 않음
• 그런데 임계구역(critical section)을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없음
• 따라서 시스템의 모든 자원을 빼앗을 수 있도록 하지 못함
• 어떤 자원을 빼앗을 지라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 결정하기 어려움
• 또한 이러한 선점 방식은 starvation현상을 일으킴
• 프로세스가 자원을 무조건 먼저 선점해버린다면 우선 순위가 낮은 프로세스는 starvation 상태에 빠지게 됨
• 무조건적으로 에이징을 사용하는 것도 좋은 해결방법은 아님
• 에이징을 사용하여 특정 조건 이상일 때는 무조건 해당 자원을 사용할 수 있도록 한다는 것 자체가 비 선점 효과를 일으켜 데드락에 빠지게 할 수 있기 때문임
• 즉 아사현상을 해결하기 위해 에이징을 사용하는 것도 어려움
• 따라서 비 선점 조건을 무력화하기 어려움

점유와 대기 예방

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
• '전부 할당하거나 아니면 아예 할당하지 않는' (all or nothing) 방식을 적용
• 이를 위해 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납해야 함
• 이 방법은 식사하는 철학자 문제에서 왼쪽 포크를 잡은 상태에서 오른쪽 포크를 잡지 못하도록 하는 것과 같음
• 이는 철학자들은 식사를 시작할 때 양손에 포크를 잡아야 하며, 그렇게 할 수 없다면, 이미 잡은 포크는 내려놓아야 함
• 그러면 동작이 빠른 철학자가 먼저 식사를 할 수 있음
• 그러나 임계구역으로 보호받는 자원에 대한 제약을 풀기는 어려움
• 점유와 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있음

전부 할당하거나 아니면 아예 할당하지 않는 방식

• [그림 6-11]은 프로세스 P2는 P1이 먼저 자원을 사용하고 놓을 때까지 기다렸다가 자원을 사용함
• 앞에서 살펴본 상호 배제 예방과 비 선점 예방은 자원에 대한 제약을 풀어버리는 것임.

점유와 대기 예방의 단점

• 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
  • 프로세스가 필요한 자원을 모두 확보한 후 실행했는데 추가로 필요한 자원이 생기면 이를 다시 확보하기가 어려움
• 자원의 활용성이 떨어짐
  • 프로세스가 앞으로 사용할 자원까지 미리 선점하기 때문에 그 자원을 필요로 하는 다른 프로세스의 작업이 진행되지 않음
  • 당장 사용하지도 않을 자원을 미리 선점하여 자원 낭비가 심함
• 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
  • 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스보다 자원을 동시에 확보하기가 어려움
  • 그러므로 많은 자원을 사용하는 프로세스의 작업이 지연되는 starvation 현상이 발생함
• 결국 일괄 작업 방식으로 동작
  • 점유와 대기 예방을 실제로 구현하면 거의 모든 프로세스가 일괄 작업 방식으로 처리됨
  • 필요로 하는 자원을 확보한 순서대로 실행하면 그 자원을 획득한 프로세스가 작업을 끝내야 다른 프로세스가 작업을 할 수 있음
  • 결국 모든 작업이 일괄 작업 방식으로 처리되어 시스템의 효율이 떨어짐
  • 자원을 확보한 프로세스가 자원을 잠깐 사용하든, 오래 사용하든 상관없음
  • 무조건 확보한 후 실행해야 하므로 다른 프로세스는 해당 자원을 기다려야 하고, 이는 일괄 작업 방식과 같음
  • [그림 6-12]에 P1 이 자원 R1, R3, R4를 확보했으며, P2는 R1, R2, R5를 기다리고, P3는 자원 R1, R6 기다림
  • 프로세스 P1, P2, P3는 자원 R1을 제외하고 서로 중복되는 자원이 없음
  • 그러나 점유와 대기예방에 따르면 필요한 모든 자원을 확보해야 실행되기 때문에 프로세스 P2와 P3는 프로세스 P1이 종료될 때까지 기다려야 함
  • 프로세스 P1이 자원 R1을 잠깐 사용하든 오랫동안 사용하든 상관없음
  • 무조건 확보한 후 실행해야 하므로 모든 프로세스는 자원 R1 때문에 일괄작업방식으로 처리됨

필요한 자원을 모두 할당한 후 실행

원형 대기 예방

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
  • 프로세스들을 한 줄로 길게 세우면 그 줄의 맨 끝에서부터 문제가 해결됨
  • [그림 6-10]의 철학자들이 사각형 식탁에서 식사를 하면 맨 마지막 사람부터 식사를 마쳐 모든 사람이 식사를 할 수 있음
  • 자원을 한 방향으로만 사용하도록 설정함으로써 원형대기를 예방할 수 있음
  • 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것
  • 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용하지만, 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용하지 않음
  • [그림 6-13] 은 시스템 자원에 숫자를 부여한 것을 보여줌
  • 마우스 1번, 하드디스크 2번, 프린터 3번.
  • 원형대기 예방의 경우 프로세스들이 자원을 사용하려고 할 때 작은 번호의 자원을 할당 받은 후 큰 번호의 자원을 할당 받도록 함
  • 예를 들면 마우스를 할당 받은 상태에서 프린터를 할당 받을 수 있지만 프린터를 할당받은 상태에서 마우스나 하드디스크 할당 받을 수 없음
  • 이렇게 처리하면 모든 자원이 한쪽 방향(작은 번호에서 큰 번호)으로만 사용되기 때문에 원형대기가 발생하지 않음

자원에 대한 번호 매김

원형 대기 예방과 교착 상태 해결

• [그림 6-14]에서 원형대기를 예방함으로써 교착 상태 해결방법을 보여줌
• 프로세스 P1은 자원 R1을 할당 받은 상태에서 자원 R2를 기다리고, 프로세스 P2는 자원 R2를 할당 받은 상태에서 자원 R1을 기다림
• 그러나 자원 R1의 번호가 작아서 프로세스 P2의 요청이 거절됨
• 프로세스 P2는 자원을 할당 받을 수 없어 강제 종료되고 프로세스 P1은 정상적으로 실행됨
• 이와 같이 작은 번호의 자원을 쓸 수 없게 하면 자원 할당 그래프에 원형이 생기지 않음.

원형 대기 조건의 부정

원형 대기 예방의 단점

• 프로세스 작업 진행에(작업진행의) 유연성이 떨어짐
  • [그림 6-13]에서는 프린터를 사용한 다음 마우스를 할당 받으려면 OS가 이를 거부함
  • 사용자 입장에서는 이러한 자원사용을 이해하기 어려움
• 자원의 번호를 어떻게 부여할 것인지가 문제 (자원 번호 부여의 문제점)
  • 프로세스가 큰 번호 자원을 사용한 후 작은 번호의 자원을 사용할 수 없기 때문에 자원에 번호를 부여하는데 매우 신중해야 함(자원에 어떻게 번호를 부여하던 자원사용에 제약)

교착 상태 예방 정리

• 교착 상태를 유발하는 네 가지 조건이 일어나지 않도록 제약을 가하는 방법
• 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려움
• 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없음

---

교착 상태 회피

교착 상태 회피의 개념

• 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어 주는 방법
• 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킴
• 교착상태회피는 할당되는 자원의 수를 조절해서 교착 상태를 피함
• 교착상태예방은 프로세스의 작업방식을 제약하기 때문에 사용할 수 없었음
• 교착상태회피는 시스템의 운영방식에 변경을 가하지 않기 때문에 교착상태 예방보다 조금 더 유연함
• 시스템에 20개 자원이 있다고 가정하고 1개의 자원을 할당하면 교착상태가 발생하지 않음 (점유와 대기 조건이 충족되지 않기 때문임)
• 그러나 20개 자원을 모두 할당하면 교착상태가 발생할 확률이 매우 높아짐
• 교착상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정상태를 유지하도록 자원을 할당함

안정 상태와 불안정 상태

• [그림 6-15]에서 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커짐
• 교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아짐
• 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 회피함

안정 상태와 불안정 상태

은행원 (다이크 스트라) 알고리즘

• 교착 상태 회피를 구현하는 대표적인 알고리즘
• 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정 상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사한 방식
• 어떤 음식점에 우동 10인분과 스파게티 20인분을 만들 수 있는 재료가 준비되어 있다고 가정함
• 은행원 알고리즘에서는 30명을 기준으로 예약을 받지 않고 10명이내로 예약을 받음
• 12명을 예약 받았는데 12명 모두 우동을 주문하면 문제가 되기 때문임

은행원 알고리즘

• 은행원 알고리즘은 최악의 경우를 기준으로 함으로써 문제상황을 철저히 회피하여 교착상태를 막음
• 은행원 알고리즘에서 사용하는 변수 [표 6-2]에 정리됨. 각 프로세스는 자신이 사용할 자원의 최대수를 운영체제에 알 려줌
• 운영체제가 자원을 할당할 때 시스템의 상태를 파악하는데 반드시 필요한 정보임
• 각 프로세스에 할당된 자원의 수는 "할당자원"에 표시됨
• 각 프로세스마다 자신이 선언한 최대 자원에서 현재 할당된 자원의 수를 제외하면 "기대자원" 이 됨
• 또한 전체자원에서 각 프로세스에 할당되고 남은 자원의 수가 "가용자원"임

은행원 알고리즘의 변수

은행원 알고리즘에서 자원 할당 기준

• 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당
• 가용자원이 기대자원보다 크다는 것은 그 자원을 사용해 작업을 종료할 프로세스가 있다는 의미이므로 안정상태임
• 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않음
• 가용자원을 사용해 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태임

안정 상태

안정 상태의 예

• [그림 6-17] 안정상태의 예로써, 시스템에 있는 전체 자원 수 14개, 각 프로세스가 필요한 자원의 수, P1=5, P2=6, and P3=10 개임
• 각 프로세스에 현재 할당된 자원의 수는 P1=2, P2=4, and P3=6 로 총 12개임
• 따라서 시스템 전체에서 사용할 수 있는 가용자원은 2개임
• 기대자원은 P1=3, P2=2, and P3=4임
• [그림 6-17]이 안정상태인 이유는 현재 가용자원이 2개인데 P2가 필요한 자원이 2개임
• 이것은 P2가 가용자원 2개를 사용해 실행을 종료하면 이미 할당 받아 사용하던 자원 6개를 반환하고, 이를 P1 또는 P3에 할당하면 전체 작업을 무사히 완료할 수 있음
• 그러나 현재 가용자원을 P2가 아닌 다른 프로세스에 나누어 주면 [그림 6-17] 은 불안정 상태가 됨
• P1과 P3에 가용자원을 할당하면 기대자원을 충족하지 못하기 때문에 작업을 마칠 수 없음
• P2에 자원을 할당해야만 안정 상태를 계속 유지할 수 있음

은행원 알고리즘 (안정 상태)

불안정 상태의 예

• [그림 6-18]은 불안정 상태의 예시
• 가용자원이 1개인데 이것으로는 어떤 프로세스의 기대자원도 충족할 수 없음
• 은행원 알고리즘에서는 현재 실행중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용자원을 할당해야 함

은행원 알고리즘 (불안정 상태)

교착 상태 회피의 문제점

• 교착상태의 회피의 원칙은 교착 상태가 발생하지 않을 수준까지만 자원을 나누어 주는 것임
• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
  • 미리 선언한 자원이 정확하지 않으면 교착상태 회피에서도 교착상태 발생 가능함
• 시스템의 전체 자원 수가 고정적이어야 함
  • 안정 상태나 불안정 상태를 파악하려면 시스템 자원수가 고정적이여야 함
  • 그러나 일시적인 고장이나 새로운 자원이 추가되는 경우가 자주 발생하므로 현실적으로 자원의 수는 유동적임
• 자원이 낭비됨
  • 음식점 예에서 스파게티 재료가 충분한데도 우동 재료에 맞추어 예약 손님을 10명 받는 것은 자원 낭비임
  • 또한 [그림 6-18] 에서 모든 불안정 상태가 교착상태가 되는 것은 아님에도 불구하고 자원을 할당하지 않는 것은 낭비임
  • 교착상태 회피는 실제로 교착상태가 발생하지 않는데도 발생할 것이라고 예상함으로써 프로세스 자원을 할당하는 데 제약을 둠

---

교착 상태 검출

교착 상태 검출의 개념

• 교착상태 예방은 실제로 구현하기 어렵고, 교착상태 회피는 구현할 수 있지만 자원을 낭비하는 문제가 있음
• 교착상태 해결방법 중 가장 현실적인 방법이 교착상태 검출임
• 교착상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착상태 발생여부를 계속 주시하는 방식임
• 만약 교착상태가 발견되면 이를 해결하기 위해 교착상태 회복 단계를 밟음

타임아웃을 이용한 교착 상태 검출

• 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법
• 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것으로, 특별한 알고리즘이 없어 쉽게 구현할 수 있음
• 타임아웃이 되면 프로세스가 종료됨

타임아웃을이용한 방법의 예

타임아웃을 이용한 교착 상태 검출 문제점

• 엉뚱한 프로세스가 강제 종료될 수 있음
  • 타임아웃을 이용하면 교착상태 외의 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료될 수 있음
• 모든 시스템에 적용할 수 없음
  • 하나의 운영체제 내에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방법을 적용할 수 있음
  • 그러나, 분산 DB는 데이터가 여러 시스템에 나뉘어 있고 각 시스템이 네트워크로 연결되어 있음
  • 이러한 시스템(분산 DB)에서는 원격지에 있는 프로세스의 응답이 없는 것이 교착상태 문제인지, 네트워크 때문인지, 작업지연인지 정확히 알 수 없음
  • 그러므로, 타임아웃 방법을 이용해 교착상태를 파악하기 어려움
• 위와 같은 문제에도 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 선호함

데이터베이스에서 타임아웃의 문제

• 데이터베이스에서 교착상태 처리는 운영체제보다 복잡함
• DB에서 특히 일관성이 깨지면 안됨
• 데이터를 조작할 때는 반드시 잠금을 얻은 후 작업을 시작함
• 만약 여러 개의 잠금을 얻어 작업을 진행 중 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있음
• 데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음
• 데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트(check point)와 롤백(roll back) 사용
  • 체크포인트 : 작업을 하다가 문제가 발생하면 저장된 상태로 돌아오기 위한 표시
  • 롤백 : 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것
• 체크포인트를 설정하면 현재 시스템상태가 하드디스크에 저장되는데, 이렇게 저장된 데이터를 스냅숏이라고 함
• 롤백이 일어나면 저장된 스냅숏을 복원하여 시스템을 체크포인트 시점으로 되돌림
• [그림 6-20] 은 체크포인트와 롤백을 사용해 타임아웃을 처리하는 것을 보여줌
• DB에서 중요한 데이터에 잠금을 요청하면 체크포인트를 만들고 해당 시점의 스냅숏을 저장함
• 그리고 잠금을 얻은 후 작업을 계속 진행함
• 만약 타임아웃이 걸려서 프로세스를 중단하거나 잠금을 포기해야 한다면 롤백을 사용해 체크포인트 시점으로 시스템을 복귀시킴
• 윈도우에서 특정시점으로 복원은 스냅숏과 롤백을 이용해 운영체제를 복원시키는 작업

체크포인트와 롤백

자원 할당 그래프를 이용한 교착 상태 검출

• 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클 있으면 교착 상태

자원 할당 그래프와 교착 상태

• 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있음
  • [그림 6-22] (a)에서 P1은 P2가 자원 R2를 사용하고 반환하기를 기다리고, P4는 P1이 자원 R1을 반납하기를 기다리고, P3는 자원 R3를 기다림
  • 이 자원 할당 그래프에는 사이클이 존재하지 않음
  • 그러므로 P2가 자원 R2를 반환하면 나머지 프로세스의 작업이 진행되고 교착상태가 발생하지 않음
• 운영체제는 자원을 요청하거나 할당할 때마다 자원할당 그래프를 갱신하는데, 이때 사이클이 발생하면 교착상태가 검출된 것으로 판단함
  • [그림 6-22]의 (b)는 프로세스 P2가 추가로 자원 R3를 요구한 경우임, P1→P2→P4→P1로 이어지는 사이클이 존재함으로 운영체제에서 교착상태가 발생한 것으로 판단함
  • [그림 6-22]에서 사각형 안의 작은 동그라미는 동시에 사용가능한 자원의 수를 나타내는데 여기서는 단일 자원으로 간주하고 하나로 표시
  • 단일 자원을 사용하는 경우에는 자원할당 그래프에 사이클이 있으면 교착 상태임

---

교착 상태 회복

교착 상태 회복

• 교착 상태가 검출된 후 교착 상태를 푸는 후속 작업을 하는 것
• 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료
• 프로세스를 강제로 종료하는 방법
  • ① 교착 상태를 일으킨(유발한) 모든 프로세스를 동시에 종료
    • 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착상태를 일으킬 가능성이큼
    • 그러므로 모든 프로세스를 강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야 하며, 이때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요함
  • ② 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
    • 우선순위가 낮은 프로세스를 먼저 종료
    • 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료
    • 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료