[OS] 9. 교착 상태(Deadlock)
교착 상태 (Deadlock)
- 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착상태라고 한다.
- 즉 둘 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하여 무한정 기다리는 현상을 의미한다.
- 교착 상태 vs. 아사 현상
- 아사 현상(기아 현상)
- 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제 또는 시스템 부하가 많아서 낮은 등급에 있는 준비 큐에 있는 프로세스가 무한정 기다리는 현상
- 에이징(Aging)으로 해결할 수 있다.
- 에이징: 몇 번 이상 양보를 했다면 더이상 양보하지 않도록 조정한다. 즉 오랫동안 기다린 프로세스에게 우선순위를 높여줌으로서 처리하는 기법
- 교착 상태(Deadlock)
- 여러 프로세스가 작업을 진행하다보니 자연적으로 일어나는 문제
- 운영체제는 감시를 하다가 교착 상태가 발생하면 강압적으로 해결해야한다.
- 교착 상태의 발생 예시
- 시스템 자원
- 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다.
- e.g. 어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너, CD 등 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우
- 공유 변수
- 응용 프로그램
- 데이터베이스에서 데이터의 일관성을 유지하기 위해 잠금(lock)을 사용하는 경우
- 교착 상태 필요 조건
- 아래 4가지 조건을 모두 충족하면 교착상태가 발생한다. 즉 모두 만족하면 좋지 않다는 의미이다.
- 상호 배제(Mutual Exclusion)
- 배타적인 자원은 임계구역으로 보호가 되기 때문에 다른 프로세스가 동시에 사용할 수 없다.
- 임계구역을 보호하기 위해 잠금 장치(lock)를 사용하면 상호 배제와 비선점 조건이 보장되기 때문에 교착상태가 일어날 수 있다.
- 비선점(Non-preemption)
- 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없다. 즉 공유할 수 없다.
- 점유와 대기(Hold and Wait)
- 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다려야한다.
- 원형 대기(Circular Wait)
- 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이룬다.
교착 상태 해결 방법
교착 상태 예방
- 교착 상태를 유발하는 4가지 조건을 예방하여 해결한다.
- 상호 배제 예방
- 시스템 내에 있는 상호 배타적인 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버린다.
- 시스템 내의 자원을 공유할 수 있다면 교착 상태가 일어나지 않는다.
- 한계
- 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야하는 자원이 있다.
- 비선점 예방
- 모든 자원을 빼앗을 수 있도록 만든다.
- 한계
- 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제도 보장할 수 없다.
- 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 기준을 정하기가 어렵다.
- 아사 현상을 유발한다.
- 점유와 대기 예방
- 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 한다.
- 전부 할당하거나 아니면 아예 할당하지 않는 방식을 적용한다.
- 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나 그렇지 못할 경유 자원을 모두 반납해야한다.
- 한계
- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기어렵다.
- 자원의 활용성이 떨어진다.
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
- 결국 일괄방식으로 작동한다.
- 원형 대기 예방
- 점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 한다.
- 프로세스들이 한줄로 길게 늘어선다면 그 줄의 맨끝에서부터 문제가 해결될 것이다.
- 자원을 한 방향으로만 사용하도록 설정한다.
- 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당한다.
- 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는것은 허용하지만, 그 반대의 경우는 허용하지 않는다.
- 한계
- 프로세스 작업 진행에 유연성이 떨어진다.
- 자원의 번호를 어떻게 부여할지가 문제이다.
교착 상태 회피
- 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고 교착상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.
- 할당되는 자원의 수를 조절한다.
- 자원이 많이 할당될수록 교착상태가 발생할 확률이 커진다.
- e.g. 자원이 20개일 때, 20개의 자원을 모두 할당할 경우
- 자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(Safe State)와 불안정 상태(Unsafe State)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
- 할당된 자원이 적으면 안정상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 크다.
- 한계
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야한다.
- 시스템의 전체 자원 수가 고정적이여야한다.
- 자원이 낭비된다.
- 은행원 알고리즘
- 은행이 대출해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정상태) 허용되지만 그렇지 않으면 거절되는 것과 유사해서 이렇게 불리게 되었다.
- 용어
- 전체 자원(Total) : 시스탬 내 전체 자원의 수
- 가용 자원(Available) : 시스템 내 현재 사용할 수 있는 자원의 수(가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원)
- 최대 자원(Max) : 각 프로세스가 선언한 최대 자원의 수
- 할당 자원(Allocation) : 각 프로세스에 현재 할당된 자원의 수
- 기대 자원(Expect) : 각 프로세스가 앞으로 사용할 자원의 수 (기대 자원 = 최대 자원 - 할당 자원)
- 방식
- 각 프로세스는 자신이 사용할 자원의 최대수(max)를 운영체제에 알려준다.
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다.(안정상태)
- 가용 자원이 어떤 기대 자원보다 작으면 할당하지 않는다.(불안정 상태)
- 현재 실행중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용자원을 할당 해야한다.
교착 상태 검출
- 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법이다.
- 만약 교착 상태가 발견되는 회복 단계를 밟아서 해결한다.
- 타임 아웃 이용 (가벼운 교착 상태 검출)
- 자원 할당 그래프 이용 (무거운 교착 상태 검출)
- 타임아웃(Timeout)
- 일정시간 동안 작업이 진행되지 않은 프로세스를 교착상태로 간주하여 처리하는 방법
- 교착상태가 자주 발생하지 않을 것이라는 가정 하에 사용한다.
- 대부분의 데이터베이스에와 운영체제에서 많이 선호하는 방식이다.
- 한계
- 엉뚱한 프로세스가 종료될 수 있다.
- 모든 시스템에 적용할 수 없다.
- 하나의 운영체제에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방식을 적용할 수 있다.
- 분산 데이터베이스의 경우, 데이터가 여러 시스템이 나뉘어있고 각 시스템이 네트워크로 연결되어있다. → 원격지에 프로세스가 응답이 없는것이 교착상태인지 네트워크 문제인지, 처리가 늦어지는 건지 파악이 어렵다.
- 데이터베이스의 교착 상태 처리
- 데이터베이스에서는 데이터의 일관성이 깨지면 안된다.
- 데이터를 조작할 때는 반드시 잠금을 얻은 후 작업을 시작한다.
- 만약 여러 개의 잠금을 얻어 작업을 하던 중 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있다.
- 데이터베이스에서 중요한 데이터에 잠금을 요청하면 체크포인트를 만들고 해당 시점의 스냅샷을 저장한다.
- 체크포인트(checkpoint) : 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시
- 스냅샷(snapshot) : 체크포인트 설정시, 하드디스크에 저장되는 현재의 시스템 상태
- 잠금을 얻은 후 작업을 진행한다.
- 타임아웃이 걸려서 프로세스를 중단하거나 잠금을 포기해야 한다면 롤백을 사용하여 체크포인트 지점으로 시스템을 복귀시킨다.
- 롤백(rollback) : 작업을 하다가 문제가 발생하여 과거의 체크포인트로 돌아가는 것
- e.g. 윈도우의
시스템 복원은 스냅샷과 롤백을 이용하여 운영체제를 복원시키는 작업이다.
- 자원 할당 그래프 (Resource-Allocation Graph)
- 자원할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있다.
- 프로세스 작업 장식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다.
- 한계
- 오버헤드가 발생한다.
- 그래프 유지, 갱신, 사이클을 검사 등 추가 작업이 있기 때문이다.
- 교착 상태가 있는 자원 할당 그래프
- 운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신한다.
- 이 때 사이클이 발생하면 교착 상태가 검출된 것으로 판단한다.
- 단일 자원을 사용하는 경우에만 해당
- 다중 자원의 경우, 그래프를 감소한 후 사이클이 남아있는지 확인하여 교착상태를 검출한다.
- 교착 상태 예방은 실제로 구현하기 어렵다. 교착 상태 회피는 구현할 수 있지만 낭비가 심하다. 교착 상태 검출이 가장 현실적인 방법이다.
교착 상태 회복
- 교착 상태가 검출된 경우 교착 상태를 푸는 후속작업이다.
- 교착 상태를 유발한 프로세스를 강제 종료한다. 그리고 프로세스가 실행되기 전에 시스템을 복구한다.
- 강제 종료하는 방법
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료
- 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착상태를 일으킬 가능성이 크다.
- 모든 프로세스를 강제로 종료한 후 다시 실행할 때 순차적으로 실행해야하며, 이 때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요하다.
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
- 교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악한다.
- 우선순위가 낮은 프로세스를 먼저 종료한다.
- 우선순위가 같은 경우 작업시간이 짧은 프로세스를 먼저 종료한다.
- 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다.
- 시스템 복구
- 명령어가 실행될 때마다 체크포인트를 만들어서 가장 최근의 검사 시점으로 돌아간다.
- 이 방법은 작업량이 상당해서 시스템에 부하를 주므로 선택적으로 사용해야한다.
- 다중 자원과 사이클
- 단일 자원만 있는 자원 할당 그래프에서는 사이클만으로 교착 상태를 검출할 수 있다.
- 다중 자원을 사용할 때는 그래프 감소를 한 후 사이클이 남아있는지 확인하여 교착상태를 검출한다.
- 다중 자원
- 하나의 자원을 여러 개의 프로세스가 동시에 사용할 수 있는 경우에는 교착 상태 검출이 복잡하다.
- 다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다.
- 사이클
- 대기 그래프(Wait for graph)
- 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프
- 그래프 감소(Graph reduction)
- 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업이다.
- 작업이 끝날 가능성이 있는 프로세스는 기다리는 자원이 없는 프로세스다.
- 그래프 감소를 완료한 후에도 사이클이 남아있으면 교착상태가 발생한 것으로 간주한다.
맨 위로 이동 ↑
댓글 남기기