시스템 내에 임계 구역이 존재하면 프로세스간 상호 배제를 보장해야한다. 운영체제가 상호 배제를 보장하기 위해 잠금을 사용하다 보면 더 이상 진행되지 않는 교착 상태에 빠지는 경우가 있다. 이 장에서는 교착 상태가 무엇인지 그리고 이를 해결하는 방법에는 어떤 것이 있는지 살펴본다.
교착 상태의 개요
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태(dead lock)이라고 한다. 이는 교통 체증이 심하여 서로 비켜주기를 기다리며 꼼짝 못하는 상태에 비유할 수 있다.
컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생할 수 있다. 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 어떤 프로세스가 임계 구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용할 수 없는 시스템 자원을 할당 받은 후 양보하지 않는 경우를 예로 들 수 있다.
자원 할당 그래프
자원 할당 그래프(resource allocation graph)는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 자원 할당 그래프를 사용하면 어떤 프로세스에 자원이 할당되어 있는지 혹은 어떤 프로세스가 자원을 기다리고 있는지 한눈에 알 수 있다.
자원이 2개 이상의 프로세스를 동시에 허용하는 경우가 있다. 여러 프로세스가 하나의 자원을 동시에 사용하면 이를 다중 자원(multiple resource)라고 부른다. 다중 자원은 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현한다.
교착 상태 필요 조건
교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야한다.
- 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 따라서 배타적인 자원을 사용하면 교착상태가 발생한다.
- 비선점(non-preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 공유할 수 없는 배타적인 자원이어야한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 따라서 배타적인 자원을 사용하면 교착 상태가 발생한다.
- 점유와 대기(hold and wait): 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다. 다른 프로세스의 작업을 방해하는 교착 상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다리는 상태가 되어야한다.
- 원형 대기(circular wait): 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아니다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠진다.
사용하는 자원을 동시에 공유할 수도 없고 중간에 빼앗아올 수도 없다면 자원을 가진 프로세스가 자원을 내놓을 때까지 무작정 기다리는 교착상태가 된다. 그리고 점유와 대기, 원형 대기 조건은 프로세스가 어떤 행위를 하고 있는지를 나타낸다. 프로세스가 자원을 점유 및 대기하고 있는 상태에서 다른 프로세스를 방해하는 방향이 원을 이루면 서로 양보하지 않기 때문에 교착 상태가 발생한다.
교착 상태 해결 방법
교착 상태를 해결하는 방법은 예방(prevention), 회피(avoidance), 검출(detection)이며, 추가적으로 교착 상태가 발견된 후에 자원을 회복(recovery)하는 방법도 있다.
교착 상태 예방
교착 상태 예방은 교착 상태 유발 네 가지 조건이 발생하지 않도록 무력화하는 방식이다. 교착 상태는 상호배제, 비선점, 점유와 대기, 원형 대기라는 네가지 조건을 동시에 충족해야 발생하기 때문에 이 중 하나라도 막는다면 교착 상태가 발생하지 않는다. 그러나 이 방법은 실효성이 적어 잘 사용되지 않는다.
- 상호 배제 예방: 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점저긍로 사용할 수 있는 자원을 없애버리는 방법이다. 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않는다. 그러나 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야하는 자원이 있다.
- 비선점 예방: 모든 자원을 빼앗을 수 있도록 만드는 방법. 설사 어떤 자원을 빼앗을 수 있도록 할지라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 결정하기 어렵다.
- 점유와 대기 예방: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게하는 방법이다. 다시말해 전부 할당하거나 아니면 아예 할당하지 않는 방식을 적용하는 것이다.
- 원형 대기 예방: 자원을 한방향으로만 사용하도록 설정함으로써 원형대기를 예방할 수 있다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다.
교착 상태 회피
교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다. 교착 상태가 발생하지 않는 범위 내에서 자원을 할당하고 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다. 교착 상태 회피는 할당되는 자원의 수를 조절하여 교착 상태를 피한다. 교착 상태 예방은 프로세스의 작업 방식을 제약하기 때문에 사용할 수 없었는데, 교착 상태 회피는 시스템의 운영 방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 좀 더 유연하다.
교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다. 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.
교착 상태 회피는 자원할당량을 조절하여 교착 상태를 해결하는 방법이다. 즉 자원을 할당하거나 교착 상태를 유발할 가능성이 있다고 판단하면 자원할당을 중단하고 지켜보는 것이다. 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.
교착 상태 검출은 어떤 제약을 가하지 않고 자원할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식이다. 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행된다. 교착 상태를 검출한 후 이를 회복 시키는 것은 결론적으로 교착 상태를 해결하는 현실적인 접근 방법이다.
은행원 알고리즘
교착 상태 회피를 구현하는 방법은 여러가지인데 그중 하나는 에츠허르 데이크스트라가 제안한 은행원 알고리즘이다. 은행이 대출해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정 상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이렇게 불리게 되었다. 은행원 알고리즘에서 각 프로세스는 자신이 사용할 자원의 최대 수를 운영체제에게 알려준다. 운영체제가 자원을 할당할 때 시스템의 상태를 파악하는데 꼭 필요한 정보이기 때문이다.
각 프로세스마다 자신이 선언한 최대 자원에서 현재 할당된 자원의 수를 빼면 기대자원이 된다. 또한 전체 자원에서 각 프로세스에 할당되고 남은 자원의 수가 '가용 자원'이다. 따라서 가용 자원은 전체 자원에서 모든 프로세스의 할 당 자원을 뺀 값이다. 자원을 할당할 때의 기준은 다음과 같다.
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태이다.
- 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다. 가용자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태이다.
안정 상태란 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.
'CS' 카테고리의 다른 글
| 혼자 공부하는 컴퓨터구조 + 운영체제 | 9장 ~ 11장 (0) | 2022.12.20 |
|---|---|
| 혼자 공부하는 컴퓨터 구조 + 운영체제 | 1장 ~ 3장 (0) | 2022.12.17 |
| 쉽게 배우는 운영체제 | 공유 자원과 임계구역 (0) | 2022.11.16 |
| 쉽게 배우는 운영체제 | 프로세스 동기화 (0) | 2022.11.13 |
| HTTP 완벽 가이드 | URL과 리소스 (0) | 2022.07.25 |
