[운영체제] 교착상태

교착상태란?

 

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

 

 

교착상태 vs 아사현상

교착상태의 정의를 처음 보면 CPU 스케줄링 정책에서 등장한 아사현상과 헷갈릴 수 있는데 두가지는 차이를 가지고 있다.

 

아사현상: 운영체제가 잘못된 CPU 스케줄링 정책을 사용하여 특정 프로세스의 작업이 지연되는 현상 (스케줄링 정책에 따라 다르지만 크게 이야기하면 남아있는 작업 시간이 길거나 애초에 작업 시간이 긴 프로세스들의 작업이 계속 지연되는 현상이다)

교착상태: 여러 프로세스가 작업을 진행하다 보니 자연적으로 발생하는 문제 (운영체제의 잘못이 아님..)

 

 

교착 상태가 발생하는 경우

 

1. 시스템 자원

: 다른 프로세스와 공유할 수 없는 시스템 자원을 사용할 때

: 즉, 각 프로세스가 사용하는 시스템 자원을 꽉 잡고 놓아주지 않을 때

P1, P2는 둘 다 작업을 마무리하기 위해서는 프린터와 CD 레코더가 모두 필요한 상황

-> P1은 프린터를 할당받은 상태에서 CD 레코더를 기다리고, P2는 CD 레코더를 할당받은 상태에서 프린터를 기다리는 상황

-> P1과 P2 둘 다 다른 프로세스의 작업이 끝나기만을 기다리는 상태 즉, 교착 상태가 발생한다.

 

2. 공유 변수

: 서로 다른 프로세스 간 공유 변수(전역 변수나 공유 파일 등)를 사용할 때

-> lock 변수를 사용하여 임계구역에 진입하는 코드를 위 그림과 같이 작성하였을 때 교착상태가 발생할 수 있다.

-> lock1을 true로 바꾼 뒤 P1이 타임아웃되어 P2의 작업으로 넘어가고 그 뒤 lock2를 true로 바꾸었는데 P2도 마침 여기서 타임아웃이 발생한다면 두 프로세스 모두 while 문의 조건 true이기 때문에 무한 대기 상태에 빠지게 된다 (교착상태 발생)

 

3. 응용 프로그램

: 데이터베이스 같은 응용 프로그램에서도 교착 상태가 발생할 수 있다.

: 데이터 베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착 상태가 발생할 수 있다.

 

 

자원 할당 그래프 

 

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

: 프로세스는 원으로, 자원은 사각형으로 표현

: 교착 상태를 알아볼 때 쉬운 이해를 돕기 위해 사용하는 것

할당 받은 상태는 실선 화살표, 할당 받기를 기다리는 상태는 점선 화살표로 표시한다.

여러 프로세스가 동시에 사용할 수 있는 다중 자원일 경우에는 수용할 수 있는 프로세스의 수를 사각형 안에 작은 점으로 표현한다.

 

 

교착상태가 발생하는 조건

 

* 식사하는 철학자 문제 : 양쪽 모두 포크를 들어야 식사가 가능한 상황에서 4명의 철학자 모두가 왼쪽에 있는 포크를 잡은 상태

왼쪽에 있는 포크를 잡은 상태에서 오른쪽에 있는 포크를 잡아야만 식사가 가능 (사람 4명, 포크 4개)

 

1. 철학자들은 서로 포크를 공유할 수 없다 (왼쪽에 잡은 포크 하나를 두명이 동시에 공유해서 사용할 수는 없으니까)

-> 자원을 공유하지 못할 때 (예. 단일 자원일 때)

 

2. 각 철학자는 다른 철학자의 포크를 뺏을 수 없다

->자원을 빼앗을 수 없으며 다른 프로세스가 자원을 놓을 때까지 기다려야 할 때 (프로세스들 간의 우선순위가 없이 모두 동등한 위치에 있음 : 비선점 방식)

 

3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다 (두 자원을 다 점유하거나 두 자원을 다 기다리거나 하는 상황 아님)

-> 자원 하나를 잡은 상태에서 다른 자원을 기다릴 때 (작업을 끝내기 위한 자원이 두 개 이상 필요하다는 뜻)

 

4. 철학자들이 둥그런 식탁에서 식사를 한다 (자원 할당 그래프가 원형)

-> 자원을 요구하는 방향이 사이클을 이루면서 서로 양보하지 않을 때

 

이 네가지가 모두 충족되면 교착 상태가 발생한다.

-> 네가지 중 하나라도 해결하면 교착상태가 해결된다.

 

 

교착 상태 필요 조건

 

1. 상호 배제(mutual exclusion)

: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이다. 

 

2. 비선점(non-preemptive)

: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

 

3. 점유와 대기(hold and wait)

: 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 상태여야 한다.

 

4. 원형 대기(circular wait)

: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다

 

-> 4가지 조건이 모두 발생해야만 교착상태가 발생한다. (필요조건) 즉, 4가지 중 단 한가지라도 만족하지 않으면 교착상태가 발생하지 않는다.

* 상호배제, 비선점 : 자원이 어떤 특징을 가지는지를 나타낸다

* 점유와 대기, 원형 대기 : 프로세스가 어떤 행위를 하고 있는지를 나타낸다

 

 

교착상태 해결 방법

 

1. 교착 상태 예방(prevention)

: 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식으로, 교착 상태 발생 필요 조건 4가지에 대하여 각각의 방법이 존재한다.

 

2. 교착 상태 회피(avoidance)

: 교착 상태가 발생하지 않도록 자원 할당량을 조절하여 교착 상태를 회피하는 방식

 

3. 교착 상태 검출(detection)과 회복(recovery) -> 가장 현실적인 방법

: 교착 상태 검출은 어떤 제약을 가하지 않고, 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식으로 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행된다.

 

 

교착 상태 예방

 

1. 상호 배제 예방

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

-> 현실적으로 모든 자원을 공유할 수는 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있기 때문에 상호 배제를 무력화하는 것은 사실상 어렵다.

 

2. 비선점 예방

: 모든 자원을 빼앗을 수 있도록 만드는 방법 (선점형을 사용하는 방법)

-> 아사 현상이 발생할 수 있기 때문에 비선점 조건을 무력화하는 것은 사실상 어렵다.

 

3. 점유와 대기 예방

: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법(전부 할당 or 아예 할당하지 않는 방식을 적용)

: 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있다. (누가 양보를 할지 결정해야하는 문제가 있긴 하지만..)

* 단점: 프로세스가 자신이 사용하는 모든 자원에 대해 미리 자세히 알기 어렵다. (입력에 따라 달라지는 프로세스일 경우는 더욱더)

           당장 사용하지 않을 자원도 미리 선점하기 때문에 자원의 활용성이 떨어진다.

           많은 자원을 사용하는 프로세스는 적은 자원을 사용하는 프로세스보다 불리하다. (많은 자원을 다 확보해야 실행이 가능하므로 실행 기회가 적음 -> 일괄 작업 방식으로 동작하게 됨)

 

4. 원형 대기 예방

: 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당받을 수 있도록 하여 원형을 이루지 못하도록 막는 방법

-> 프로세스 작업 진행에 대한 유연성이 떨어지며(왜 R2> R1 ?), 자원의 번호를 어떻게 부여할 것인지가 문제이다.

 

* 예) 마우스가 1번, 하드디스크가 2번, 프린터가 3번일 때

   마우스를 할당 받은 상태에서 프린터를 할당 받을 수는 있지만 프린터를 할당 받은 상태에서는 마우스나 하드디스크를 할당 받을 수 없다.

   예) 철학자의 식탁에서 마지막 포크(숫자가 가장 큰)를 집은 사람은 그 다음 포크(숫자가 가장 작은)를 사용할 수 없다.

 

상호배제, 비선점 예방: 자원을 보호해야 하기 때문에 사용하기 어렵다.

점유와 대기, 원형 대기 예방: 자원을 낭비하기 때문에 사용할 수 없다.

 

 

교착 상태 회피

 

: 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여,  그 이하로 자원을 나누어 주는 방법

: 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

: 즉, 할당되는 자원의 수를 조절하여 교착 상태를 피한다.

 

* 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당 

할당 자원이 적으면 안정 상태가 크고, 할당 자원이 늘어날수록 불안정 상태가 커진다.

불안정 상태라고 해서 모두 교착 상태가 발생하는 것은 아니다. -> 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아지는 것

교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.

 

 

교착 상태 회피 : "은행원 알고리즘"

 

: 교착 상태 회피를 구현하는 대표적인 알고리즘

: 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정 상태) 허용되지만 그렇지 않으면 거부되는 것과 유사한 방식

 

예) 우동 10인분, 스파게티 20인분의 재료가 있는 상황에서 10명이 넘는 인원이 우동을 주문하면 문제가 되니까 처음부터 10명만 예약을 받는 상황 ..

 

은행원 알고리즘 사용 변수

(1) 전체 자원(Total): 시스템 내 전체 자원의 수

(2) 가용 자원(Available): 시스템 내 현재 사용할 수 있는 자원의 수(가용자원 = 전체 자원 - 모든 프로세스의 할당 자원)

(3) 최대 자원(Max): 각 프로세스가 선언한 최대 자원의 수 

(4) 할당 자원(Allocation): 각 프로세스에 현재 할당된 자원의 수

(5) 기대 자원(Expect): 각 프로세스가 앞으로 사용할 자원의 수(기대 자원 = 최대 자원 - 할당 자원)

 

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

: 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당 -> 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않음

 

은행원 알고리즘에서 안정 상태

: 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우

 

교착 상태 회피의 문제점

: 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.

: 시스템의 전체 자원 수가 고정적이어야 한다.

: 자원이 낭비된다.

 

 

교착 상태 검출

 

: OS가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식

: 교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟음

 

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

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

: 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것으로, 특별한 알고리즘이 없어 쉽게 구현할 수 있다.

: 타임아웃이 되면 프로세스가 종료된다.

 

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

: 데이터베이스에서 타임아웃으로 프로세스(데이터베이스의 트랜잭션)가 종료되면 일부 데이터의 일관성이 깨질 수 있다.

: 데이터의 일관성이 깨지는 문제를 해결하기 위해 '체크 포인트'와 '롤백'을 사용한다.

  - 체크 포인트: 작업을 하다가 문제가 발생하면 저장된 상태로 다시 돌아가기 위한 표시 (헨젤과 그레텔 빵가루..ㅎㅎ)

  - 롤백: 작업을 하다가 문제가 발생하여 과거의 체크 포인트로 되돌아가는 것

 

 

교착 상태 회복

 

: 교착 상태가 검출된 후 교착 상태를 푸는 후속 작업을 하는 것

: 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료한다.

 

종료 방법

(1) 교착 상태를 일으킨 모든 프로세스를 동시에 종료

(2) 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

  - 우선순위가 낮은 프로세스를 먼저 종료

  - 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료

  - 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료

 

* 쉽게 배우는 운영체제 책 참고