교착상태(Dead lock)

 

교착상태(Dead lock)란?

 

한정된 컴퓨터 자원을 여러 프로세스가 사용하려고 할 경우 발생한다.

 

 

프로세스는 특성상 자신의 업무처리를 위하여 필히 운영체제에게 자원을 요청하게 되는데

 

이때 프로세스의 상태는 대기상태로 전환된다.

 

 

만약 여러 프로세스가 서로 같은 자원을 사용하려고 한다면?

 

당연하게도 어떤 프로세스는 자원을 사용하지 못하여 대기상태로 들어가게 될 것이다.

 

이때, 대기상태의 프로세스가 더이상 실행상태로 변경될 수 없을 경우에 이것을 교착상태라고 부른다.

 

 

 

[교착상태의 필요조건 4가지]

 

 

1. Mutual exclusion(상호 배제)

 

     > 오직 하나의 프로세스만이 자원을 사용할 수 있다.

 

 

2. Hold and Wait(점유와 대기)

 

     > 자원을 점유 중인 프로세스가 또다른 자원을 사용하기 위하여 대기중이여야 한다.

 

 

3. No preemption(비선점)

 

     > 자원을 점유 중인 프로세스만이 자발적으로 자원을 놓을 수 있다.

        타 프로세스에 의해 자원을 강제로 빼앗기지 않음.

 

 

4. Circular wait(환형 대기)

 

     > 프로세스들이 자원을 대기하는 형태가 순환고리(cycle)를 형성한다.

 

 

 

위의 4가지 조건은 '필요' 조건이다.

 

교착상태가 발생했다면 위의 4가지 조건이 모두 나타나지만

 

4가지 조건이 모두 나타났다고 반드시 교착상태가 발생하는 것은 아니라는 의미이다.

 

 

 

[교착상태 예방]

 

교착상태 예방(Prevention)은 위의 필요조건 중 1개이상을 부정하면 된다.

 

 

1. Mutual exclusion(상호 배제) 부정

 

     > 여러 개의 프로세스가 자원을 공유할 수 있게 한다.

         프린터와 같이 자원 공유를 할 수 없는 경우엔 불가능(Infeasible)하다.

 

 

2. Hold and Wait(점유와 대기) 부정

 

     > 프로세스 실행 전에 모든 자원을 미리 할당하거나, 점유 중인 자원이 없는 프로세스만이 자원을 요청하게 한다.

        낮은 자원 이용률 및 기아 현상(starvation)이 발생할 수 있다.

 

 

        ※ 기아 현상(starvation) : 프로세스의 자원 할당 우선순위가 낮을 경우, 영원히 자원 할당이 되지 않는 현상.

 

 

3. No preemption(비선점) 부정

 

     > 자원을 점유 중인 프로세스가 다른 자원을 요구할 때, 점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해

        대기한다.

 

 

4. Circular wait(환형 대기) 부정

 

     > 자원에 우선순위를 할당하여 한 방향으로만 자원을 요구하게 한다.

 

 

 

[교착상태 회피]

 

교착상태 회피(Avoidance)는 불안정한 상태에서 시스템이 진입하지 않는 것을 보장하는 의미이다.

 

 

1. 자원 할당 그래프

 

     > Cycle이 생기지 않게 해야하며, Single instance일 때만 이 방법을 사용한다.

         그래프에 미래를 예측하는 점선이 존재한다.

 

 

2. Banker's Algorithm(은행원 알고리즘)

 

     > Multiple instance일 경우 이 알고리즘을 사용한다.

        각각의 자원에 대하여 (이용 가능한 자원 >= 필요한 자원) 일 경우,

        해당 프로세스에 대하여 (이용 가능한 자원 += 할당된 자원) 을 하여 Safe sequence를 찾는다.

 

 

 

[교착상태 탐지]

 

교착상태 탐지(Detection)는 교착상태 회피 방법과 아주 유사하다.

 

 

1. 자원 할당 그래프

 

     > Cycle이 존재할 경우 교착상태가 발생한다. Single instance일 때만 이 방법을 사용한다.

         그래프에 점선이 존재하지 않는다.

 

 

2. Banker's Algorithm(은행원 알고리즘)

 

     > Multiple instance일 경우 이 알고리즘을 사용한다.

        각각의 자원에 대하여 (이용 가능한 자원 >= 필요한 자원) 일 경우,

        해당 프로세스에 대하여 (이용 가능한 자원 += 할당된 자원) 을 하여 safe sequence를 찾는다.

        교착상태 회피방법에서 필요한 자원의 값을 실제 요청한 값으로 바꿔준다.

 

 

 

[교착상태 회복]

 

교착상태를 일으킨 프로세스를 종료하거나 할당된 자원을 선점하여 해결한다.

 

 

1. 프로세스 종료

 

     > 교착상태에 걸린 모든 프로세스를 종료하거나, 하나씩 종료하거나 둘 중 하나.

 

 

2. 자원 선점

 

     > 교착상태에 걸린 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당한다.

        자원 선점시, 시스템에 최소의 피해를 줄 수 있는 프로세스를 선택한다.

        혹은, 프로세스를 일시 중지 후 다시 실행한다.

        

        기아 현상(starvation)을 예방하기 위하여 한 프로세스가 계속해서 자원을 선점하는 것을 막아야 한다.

 

 

 

 

 

교착상태 회피 및 탐지의 자원 할당 그래프와 은행원 알고리즘은 링크로 추가 함.

 

 

1. 자원 할당 그래프

 

>  https://stormcoding.tistory.com/entry/%EC%9E%90%EC%9B%90-%ED%95%A0%EB%8B%B9-%EA%B7%B8%EB%9E%98%ED%94%84resource-allocation-graph

자원 할당 그래프(resource allocation graph)

 

2. 은행원 알고리즘

 

> https://has3ong.github.io/banker-algorithm/