데드락

다. DeadLock

  A. Dining philosopher 문제.

    데드락을 이해하기 위해 Dining Philosopher라는 문제를 고려해 볼 수 있다. 아래 그림은 위키백과를 참조했다. 아래 그림처럼 다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에 스파게티 그리고 양 옆의 포크가 하나 씩 있다. 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다. 포크 두 개를 집어 스파게티를 한 번 먹고 나면 포크는 내려놓아야 한다. 만약 한명이 스파게티를 먹는다면 그 한 명 양 옆의 철학자는 스파게티를 먹지 못할 것이지만 조금 기다리면 처음 철학자가 포크를 내려놓고 두 명은 먹을 수 있는 상태가 될 것이다. 그런데 만약 모든 철학자가 동시에 자신 왼쪽의 포크를 집게 되면 문제가 생긴다. 그 어떤 사람도 스파게티를 먹을 수 없고, 포크를 내려놓는 사람이 없기 때문에 무한 교착상태에 빠지게 된다.

철학자를 프로세스로 포크를 하드웨어 리소스로 생각하게 되면 데드락 상태에 빠지게 되는 상황이 바로 위의 교착상태이다. 이런 데드락의 문제를 해결하려면 간단하게 2가지 방법이 있다. 데드락 상태를 확인하고 하나의 프로세스를 kill하는 것과 처음부터 데드락이 발생하지 않는 구동 순서를 어느정도 정해주는 것이다.

 

사진 출처 : 위키백과

B. DeadLock의 해결 방안.

먼저 데드락이 발생하는 조건은 아래와 같다.

상호 배제 (Mutual exclusion)	- 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.
점유 대기 (Hold and wait)	- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
비선점 (No preemption)	- 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
순환 대기 (Circular wait)	- 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

표 출처: https://includestdio.tistory.com/12 [includestdio]

 

위의 조건을 깨트리는 데드락 해결방안으로는 쉽게 3가지를 생각해볼 수 있다.

 

1) DeadLock prevention : 교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법이다. 예를 들어서 상호 배제를 없애서, 자원에 여러 프로세스가 동시에 사용할 수 있도록 할 수 있다.

 

2) Deadlock avoidance : 특정 순서로 프로세스들에게 자원을 할당하고 자원을 리턴하는 순서를 지정하여 회피할 수 있다. 이 예로 그 순서가 있는지 판별하는 Banker’s Alogrithm이 존재한다. Banekr’s Alogrithm은 간단하게, 자원을 할당한 이후에 데드락을 피할 수 있는 경우의 수가 있는지 파악하는 것이다. 존재한다면 계속 피할 수 있는 방향으로 할당을 해나갈 수 있다.

 

3) Deadlock detection and recovery : 어떤 시스템이 데드락이 걸렸는지 찾고 그 중 하나의 프로세스를 Kill하여 Resource를 Release 시키는 방법이다. 이 방법은 데드락 걸린 프로세프로 찾는 것에 어려움이 있고 가장 중요한 부분이다.

 

 

Banker's Alogrithm의 Safety Algorithm

1. 초기화

2. 끝나지 않은 프로세스를 가상으로 할당시키고 완료시킨다.

3. 가상으로 리소스를 릴리즈하고 2번으로 돌아간다.

 

정리 : 특정 프로세스에게 자원을 할당했을 때 데드락이 걸리지 않는 방법이 존재하는가? 를 판단한 후 Safety하다고 판정되면 실제로 자원을 할당한다.

 

bool CheackSafety(int* request, int pid)
{//init code...
    //init finish_flag
    bool* Finish = nullptr;
    Finish = new bool[m_NumOfProc];
    for (int i = 0; i < m_NumOfProc; i++)
        Finish[i] = false;
 
    bool found = false;
    //Cheack Safety
    while (!Safety)
    {
        found = false;
        Safety = true;
 
        //Cheack Finish and Cheack Need_i <= Work
        for (int i = 0; i < m_NumOfProc; i++)
        {
            //if true -> Finish = True, and Releas Resource
            if (!Finish[i] && p_IsAllocatable(Pseudo[i].m_Need))
            {
                Finish[i] = true;
                p_ResourceRelease(Pseudo[i]);
                Safety = false;
                found = true;
                break;
            }
            Safety &= Finish[i];
        }
 
        // not safety but not found -> return false;
        if (!Safety && !found)
        {
            delete[] Finish;
            return false;
        }
    }
    //is All Finish True? -> yes : return true 
    delete[] Finish;
    return true;
}