교착 상태

교착상태는 일괄 처리 시스템이 아닌 이상 어쩔 수 없이 발생하는 문제이다. CPU가 여러가지 프로세스에 시간을 할당하면서 생기는 문제인데 모든 해결법에 문제점이 하나씩 있다.

 

내 개인적인 생각이지만 완벽히 교착 상태를 해결할 때 쯤이면 시분할 시스템이 사라지지 않을까?

---

교착상태의 정의

define : 2개 이상의 프로세스가 서로 다른 프로세스의 작업이 끝나기만을 기다리며 기다리는 상황

 

교착상태의 발생

1. 시스템자원 

2. 공유변수 

3. 응용 프로그램

 

자원 할당 그래프

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

원 : 프로세스

사각형 : 자원

다중자원 : 하나의 자원이 2개 이상의 프로세스를 수용할 수 있음 

 

식사하는 철학자 문제

식사하는 철학자 문제는 교착상태의 대표적인 예시 문제이다. 

 철학자가 식사를 하기 위해서는 오른쪽과 왼쪽에 있는 포크를 모두 집어야만 식사를 할 수 있다.

 

하지만 모두가 왼쪽 포크를 집는다면 오른쪽 포크를 집으려 했을 때 옆사람의 왼쪽 손에 포크가 들려 있는 것을 볼 수 있다.

 

이렇게 서로의 포크를 내려놓기만을 무한정 기다리기만 한다. 이러한 문제를 '식사하는 철학자 문제'라고 한다.

 

교착 상태 해결 방법

• 예방 : 교착 상태를 유발하는 네 가지 조건을 무력화 → 실효성이 떨어져 사용하지 않음
• 회피 : 교착 상태가 발생하지 않는 수준으로 자원을 할당 → 실효성이 떨어져 사용하지 않음
• 검출 : 자원 할당 그래프를 사용하여 교착 상태를 발견 → 회복과 같이 사용 가장 현실적인 방법 
• 회복 : 교착 상태를 검출한 후 해결 → 검출과 같이 사용 가장 현실적인 방법

교착상태 예방

1. 상호 배제 예방

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

→ 현실적으로 모든 자원을 공유할 수 없고, 임계구역과 같은 보호해야 하는 자원이 있기 때문에 불가능

 

2. 비선점 예방

: 모든 자원을 빼앗을 수 있도록 만드는 방법. 

→ 임계구역과 같은 자원을 빼앗을 수 있다면 문제가 발생하며, 아사현상, 어떠한 기준으로 빼앗을지 뺴앗을 시간 중 얼마를 사용할지에 대한 문제가 발생한다. 현실적으로 불가능

 

3. 점유와 대기 예방

: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법 

→ 전부 할당하거나 아예 할당하지 않는다.

→ 프로세스가 자신이 필요한 자원을 정확히 알기 어려우며 결국 일괄작업 방식으로 동작하기 때문에 현실적으로 불가능

 

4. 원형 대기 예방

: 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법

→ 자원을 한 방향으로만 사용하도록 설정. 프로세스 작업 진행에 유연성이 떨어지며 자원의 번호부여의 기준을 정하는데 문제가 있어 현실적으로 불가능

 

교착상태 회피

 

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

 

1. 은행원 알고리즘 

: 교착상태 회피를 구현하는 대표적인 예시. 최악의 상황을 기준으로 하여 교착상태를 막음

ex) 스파게티 면이 20인분있고 우동면이 10인분 있다고 했을 때 우동면을 기준으로 10명 이상의 예약을 받지 않음

 

은행원 알고리즘의 변수

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

 

교착상태 회피의 문제점

 

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

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

3. 자원이 낭비된다.

 

교착상태 검출

 

개념 : 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법

 

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

 

→ 일정시간동안 작업이 진행되지 않은 프로세스를 교착상태로 간주

 

문제점

1. 엉뚱한 프로세스가 강제 종료 될 수 있다. 

→ 타임아웃 시간동안 진행되지 않은 모든 프로세스가 교착상태 때문에 작업이 이루어지지 않은 것은 아니기 때문

 

2. 모든 시스템에 적용할 수 없다. 

→ 분산 데이터 베이스 같은 여러군데에 데이터가 나뉘어 있는 경우 타임아웃이 난다면 그게 교착상태 때문인지 네트워크 문제인지 정확히 알 수 없다. 

 

→ 운영체제와 데이터 베이스는 타임아웃 검출을 선호

운영체제의 선호 이유 : 자주 발생하지 않는 교착상태 때문에 자원 할당 그래프를 유지하면서 모든 자원을 감시하는 것은 어렵기 때문

 

데이터베이스의 선호 이유 : 데이터의 일관성이 깨지면 안되기 때문에 잠금을 얻은 후 조작한다. 

• 체크 포인트 : 문제가 발생하면 저장된 상태로 되돌아 오기 위한 표시
• 스냅숏 : 체크포인트의 상태를 하드웨어에 저장
• 롤백 : 문제가 발생하여 과거의 체크포인트로 돌아가는 것

 

 

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

 

자원 할당 그래프를 이용하여 시스템 내의 프로세스가 어떤 자원을 필요로 하고 가지고 있는지 알 수 있다. 

이처럼 그래프를 통하여 사이클이 있는지를 확인해서 교착상태가 일어났는지 확인할 수 있다. 

 

교착상태 회복

 

개념 : 교착상태가 발생되면 강제종료를 통해 교착상태를 해결하는 작업

 

교착상태 회복의 종류

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

→ 종료된 프로세스들이 동시에 작업을 실행하면 다시 교착상태가 발생할 확률이 높음 

 

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

→ 프로세스를 종료할 때의 기준

• 우선순위가 낮은 프로세스를 먼저 종료
• 작업시간이 짧은 프로세스를 먼저 종료
• 자원을 많이 사용하는 프로세스를 먼저 종료