[OS] Ch.6 교착상태

1. 교착상태의 개요

1. 교착상태의 정의

교착상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태

 

 

아사현상과의 차이점

아사현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

교착상태는 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제

 

따라서 운영체제는 감시를 하다가 교착 상태가 발생하면 강압적으로 해결해야 함

 

 

2. 교착상태의 발생

컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생 가능

 

시스템 자원

어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않은 경우

 

공유 변수

한 변수를 할당받은 상태에서 다른 변수를 기다리면 교착상태가 발생

 

응용 프로그램

데이터베이스와 같은 응용 프로그램에서도 교착상태 발생

여러 프로세스가 데이터베이스에 저장된 데이터를 사용할 때는 데이터의 일관성을 유지해야 함

이 때, 일관성을 유지하기 위해 잠금을 사용하고 이로 인해 교착상태가 발생할 수 있음

 

 

3. 자원 할당 그래프

자원 할당 그래프

프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것

프로세스 = 원 / 자원 = 사각형

 

다중 자원

• 여러 프로세스가 하나의 자원을 동시에 사용
• 다중 자원은 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현

 

식사하는 철학자 문제

 

왼쪽 포크를 잡은 후 오른쪽 포크 잡기!

 

교착상태 발생 조건

1. 철학자들은 서로 포크를 공유할 수 없음
2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없음
3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림
4. 자원 할당 그래프가 원형임

 

2. 교착 상태 필요조건

1. 교착 상태 필요조건

4가지를 모두 충족해야 교착상태가 발생함

• 상호 배제
  
  • 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적 자원이어야 함
  • 배타적 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없음
• 비선점
  • 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함
  • 시간간격을 두고 자원을 공유할 수 있음
• 점유와 대기
  • 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 상태여야 함
  • 다른 프로세스의 작업 진행을 방해하는 교착 상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다리는 상태가 되어야 함
• 원형 대기
  • 점유와 대기를 하는 프로세스 간의 관계가 원일 이루어야 함
  • 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착상태가 됨

 

이 중 상호 배제와 비선점 조건은 자원이 어떤 특징을 가지는지를 나타냄

점유와 대기, 원형 대기 조건은 프로세스가 어떤 행위를 하고 있는지를 나타냄

 

 

2. 식사하는 철학자 문제와 교착 상태 필요조건

• 상호 배제 : 포크는 한 사람이 사용하면 다른 사람이 사용할 수 없는 배타적인 자원
• 비선점 : 식사하는 철학자 중 어떤 사람의 힘이 월등하여 옆 사람의 포크를 빼앗을 수 있다면 교착 상태 발생 x
  • 자원을 빼앗을 수 있다는 것은 시간 간격을 두고 그 자원을 공유할 수 있다는 의미로 상호 배제가 성립되지 않음

        → 임계구역을 보호하기 위해 잠금장치를 사용 → 교착 상태 발생할 수 있음

• 점유와 대기 : 한 철학자가 두 포크를 다 점유하거나, 반대로 두 자원을 다 기다리는 상태라면 교착 상태 발생 x
  • 한 프로세스가 자원을 점유한 상태에서 다른 프로세스의 자원을 기다리면 서로 진행을 방해하는 상태가 되므로 교착 상태가 발생
• 원형 대기 : 식사하는 철학자들은 둥그럼 식탁에서 식사를 진행
  • 선후 관계를 결정할 수 없어 문제가 계속 맴돈다는 의미
  • 점유와 대기를 하는 프로세스들이 원을 이루면 서로 진행을 방해하는 상태가 되므로 교착 상태 발생

 

• 아사현상은 정책상 잘못으로 일어나며, 에이징으로 해결할 수 있음
• 교착 상태는 정책상 잘못이나 오류가 없어도 자연적으로 발생

 

 

3. 교착 상태 해결 방법

1. 교착 상태 해결 방법

• 교착 상태 예방 : 교착 상태를 유발하는 네 가지 조건을 무력화
  • 실효성이 적어 잘 사용되지 않음
• 교착 상태 회피 : 교착 상태가 발생하지 않는 수준으로 자원을 할당
  • 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것
  • 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기때문에 실효성이 적음
• 교착 상태 검출 : 자원 할당 그래프를 사용하여 교착 상태를 발견
• 교착 상태 회복 : 교착 상태를 검출한 후 해결

 

2. 교착 상태 예방

1) 상호 배제 예방

시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법

하지만 현실적으로 상호 배제를 무력화하는 것은 어려움

 

 

2) 비선점 예방

• 모든 자원을 빼앗을 수 있도록 만드는 방법
• 아사 현상을 일으킴 → 에이징으로 해결할 수 있지만...
  • 우선 순위가 낮은 프로세스가 몇 번 양보 끝에 무조건 자원을 사용한다고 가정하면 이는 다시 비선점 자원이 되어 교착 상태에 빠질 수 있음
  • 즉, 아사 현상을 해결하기 위해 에이징을 사용하는 것도 힘듦
• 따라서 비선점 조건도 무력화하기 어려움

 

3) 점유와 대기 예방

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
• ‘전부 할당하거나 아니면 아예 할당하지 않는(all or nothing)’ 방식 적용
• 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리

단점

1. 프로세스가 자신이 사용하는 모든 자원을 자세히 알게 어려움
   • 프로세스가 필요한 자원을 모두 확보한 후 실행했는데 추가로 필요한 자원이 생기면 이를 다시 확보하기 어려움
2. 자원의 활용성이 떨어짐
   • 당장 사용하지도 않을 자원을 미리 선점하여 자원 낭비가 심함
3. 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
   • 많은 지원을 사용하는 프로세스의 작업이 지연되는 아사현상 발생
4. 결국 일괄 작업 방식으로 동작

 

4) 원형 대기 예방

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
• 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다.
  • 즉, 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것

단점

1. 프로세스 작업 진행에 유연성이 떨어짐
2. 자원의 번호를 어떻게 부여할 것인기가 문제

 

5) 교착 상태 예방 정리

자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려우며 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없음

 

 

3. 교착 상태 회피

1) 교착 상태 회피의 개념

• 교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
  • 범위에 있으면 프로세스를 대기
• 할당되는 자원의 수를 기준으로 시스템을 안정상태(safe state)와 불안정 상태(unsafe state)로 나누고, 시스템이 안정 상태를 유지하도록 자원을 할당함
• 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.

 

2) 은행원 알고리즘

운영체제 알고리즘에서 각 프로세스는 자신이 사용할 자원의 최대수(Max)를 운영체제에 알려줌

운영체제가 자원을 할당 할 때 시스템의 상태를 파악하는데 꼭 필요한 정보

 

은행원 알고리즘의 변수

변수	설명
전체 자원	시스테 내 전체 자원의 수
가용 자원	시스템 내 현재 사용할 수 있는 자원의 수 (가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원)
최대 자원	각 프로세스가 선언한 최대 자원의 수
할당 자원	각 프로세스에 현재 할당된 자원의 수
기대 자원	각 프로세스가 앞으로 사용할 자원의 수 (기대 자원 = 최대 자원 - 할당 자원)

 

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

여기서 안정상태란, 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말함

 

[6-17]

가용 자원 : 최대 자원 수(14) - 할당된 자원 ( 2+4+6=12 ) =2

기대 자원 : 최대 자원 수(5 , 6 , 10) - 현재 할당된 자원의 수 (2 , 4 , 6 ) = 3 , 2 , 4

P2가 필요로 하는 자원의 수 =2 , 가용 자원 = 2 , 둘이 같음 ⇒ 안정자원

2를 P2에 할당시켜 실행하고 반환하면(6) 전체 작업을 무사 완료 가능

 

[6-18]

가용 자원 : 최대 자원 수 (14) - 할당된 자원 (3+4+6=13) = 1

기대 자원 : 최대 자원 수 ( 7, 6, 10 ) - 현재 할당된 자원의 수 (3, 4, 6) = 4, 2, 4

어떠한 프로세스에도 못 줌 (1 과 같거나 큰 기대자원이 없음) ⇒ 불안정 자원

 

 

 

 

3) 교착 상태 회피의 문제점

1. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
   • 미리 선언하는 일 쉽지 않음
   • 또한 선언한 자원이 정확하지 않으면 교착상태 발생
2. 시스템의 전체 자원 수가 고정적이어야 함
   • 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번하므로 시스템의 자원 수는 유동적
3. 자원이 낭비됨
   • 실제로 교착 상태가 발생하지 않는데도 발생할 것이라고 예상함으로써 프로세스에 자원을 할당하는 데 제약을 둠

 

4. 교착 상태 검출

1) 교착 상태 검출의 개념

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

 

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

일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법

 

단점

1. 엉뚱한 프로세스가 강제 종료될 수 있음
   • 교착 상태 외의 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료될 수 있음
2. 모든 시스템에 적용할 수 없음
   • 하나의 운영체제 내에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방법을 적용할 수 있음
   • 여러 군데에 데이터가 나뉘어 있고 각 시스템이 네트워크로 연결되어 있는 경우에는 응답이 없는 것이 교착 상태 떄문인지, 네트워크 문제 때문인지, 단순히 처리가 늦어지는 것인지 정확히 알 수 없음 (ex. 분산 데이터 베이스)

 

그럼에도 불구하고 많이 선호함

• 가벼운 교착 상태 검출 이라고도 부름 ↔ 무거운 교착 상태 검출
• 데이터베이스의 교착상태 처리는 운영체제보다 복잡
  • 데이터 베이스에서는 특히 데이터의 일관성이 깨지면 안 됨→ 반드시 잠금을 얻은 후 작업
  • 만약 여러 개의 잠금을 얻어 작업을 하던 중 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있음
  → 체크포인트(check point)와 롤백(roll back)을 사용
  • 체크포인트 : 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시 (현재 시스템 상태가 하드디스크에 저장됨 : 스냅숏(snap shot))
  • 롤백 : 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것

 

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

단, 단일 자원일 경우에만 해당함

다중 자원에 대한 내용은 밑에서 설명

 

자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있음

• 교착상태가 없는 자원 할당 그래프
  • 프로세스 P1은 프로세스 P2가 자원 P2를 다 사용하고 반환하기를 기다리고, 프로세스 P4는 프로세스 P1을 , 프로세스 P3은 프로세스 P4를 기다리고 있음
  • 사이클 x
• 교착상태가 있는 자원 할당 그래프
  • 운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신하는데, (단일 자원일 때) 이때 사이클이 발생하면 교착 상태가 검출된 것으로 판단
  • (다중 자원일 때) 사이클이 발생하면 모두 교착상태라고 판단할 수 없음
• 장점 : 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것
• 단점 : 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생
  • 이러한 추가 작업을 줄이기 위해 자원이 할당될 때마다가 아닌 일정시간마다 하는 방법도 존재

 

5. 교착 상태 회복

교착 상태를 유발한 프로세스를 강제로 종료

1. 교착 상태를 일으킨 모든 프로세스들 동시에 종료
   • 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 큼
   • 모든 프로세스를 강제로 종료한 후, 다시 실행할 때는 순차적으로 실행해야 하며, 이때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요
2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
   • 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법
   • 어떤 프로세스부터 종료할 것인지 기준 필요
     • 우선순위가 낮은 프로세스를 먼저 종료
     • 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료
     • 위의 두 조건이 같은 경우, 자원을 많이 사용하는 프로세스를 먼저 종료

 

종료하는 일 뿐만 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 함

• 시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식 ⇒ 체크포인트를 선택적으로 사용해야 함 → 작업량이 상당하여 시스템에 부하 줌

 

4. 다중 자원과 교착 상태 검출

1. 다중 자원과 사이클

• 자원 R1는 두 프로세스가 동시에 사용할 수 있는 다중 자원
• 사이클이 형성되어 교착 상태 같지만 R1의 자원수가 2개이므로 프로세스 P2가 자원 R1과 R2를 사용하여 작업을 마친 후 , 프로세스 P1이 자원 R2를 사용하여 작업을 마칠 수 있음
• 교착 상태 발생 x

 

2. 대기 그래프와 그래프 감소

• 대기 그래프(wait for graph) :  자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프
• 그래프 감소(graph reduction) : 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업

교착상태 발생 X

 

1. 작업이 끝날 수 있는 프로세스, 기다리는 자원이 없는 프로세스 P2에 대해 프로세스 P1에서 P2로 가는 화살표를 지움
2. 프로세스 P1이 작업을 종료할 수 있으므로 프로세스 P4에서 P1로 가는 화살표를 지움
3. 프로세스 P4가 작업을 종료할 수 있으므로 프로세스 P3에서 P4로 가는 화살표를 지움
4. 프로세스 P3이 작업을 종료할 수 있으므로 프로세스 P1에서 P3으로 가는 화살표를 지움

 

교착상태 발생 O

• 여전히 사이클이 남아있어 교착상태 발생

⇒ 단일 자원만 있는 자원 할당 그래프에서는 사이클만으로 교착 상태 검출이 가능하지만, 다중 자원을 사용할 때는 그래프 감소를 한 후 사이클이 남아 있는지 확인하여 교착 상태를 검출