Deadlock(2)

Banker’s Algorithm

하나의 자원이 가진 인스턴스가 여러개일 때 Deadlock을 Avoidance하는 방법 프로세스에게 Maximum 자원을 할당해줘도 Safe한지 확인하는 알고리즘

특징

1. Multiple Instance에 적용 가능
2. 사전에 process가 필요로 하는 자원의 정보가 필요
3. 자원을 얻기전에 Process가 기다릴 수도 있다.
4. 프로세스는 자원을 정해진 시간 내에 반납해야한다.

Data Structures for the Banker’s Algorithm

Available : 현재 여유분. 여유 자원의 갯수. Available[j] = k 이면 j자원의 갯수가 여유가 k개 있다. Max : Process가 원하는 자원의 최댓값. Max[i][j] = K 이면 Pi가 Rj를 원하는 갯수의 최댓값은 k개 이다. Allocation : 프로세스에 할당된 자원. Allocation[i][j] = k이면 Pi가 Rj를 k개만큼 갖고있다. Need : 필요로하는 자원의 갯수. Need[i][j] = k이면 Pi가 Rj를 k개만큼 받길 원한다.

Need[i][j] = Max[i][j] - Allocation[i][j] 필요한 자원 = 원하는 최대 자원 - 할당된 자원 이다.

Safety Algorithm.

안전한지 check하는 알고리즘.

1. Work = Available ( Work는 Available이다.) Finish[i] = false for every i (모든 프로세스들이 아직 끝나지 않았다.)
2. Finish[i] = false인치 체크하고, Need[i] <= Work ( 필요한 자원을 줄만큼 여유가 있으면)
3. Finish[i] = true. 일이 끝나고, Work = Work + Allocation[i]. 프로세스가 할당받은 자원을 다시 돌려받는다.
4. Finish[i] == true for every process. ==> safe. 모든 프로세스가 끝나면 safe state에 있다고 할 수 있다.

Safety Algorithm에서 모든 프로세스를 처리하는 순서가 있다는 것이 중요하다. 하지만 그 프로세스의 특정 순서는 중요하지 않다.

Resource-Request Algorithm for Process Pi

특정 프로세스가 요청하는 자원의 할당 요청이 안전한지 판단하는 알고리즘.

1. Request[i] < Need[i] 가 아니면?!! -> Error발생( 프로세스가 필요하다고 말했던 것보다 요청한 것이 크다면 에러가 발생하게 된다.)
2. Request[i] < Available 이면 -> 요청한 자원을 줄만큼 여유자원이 있으면 goto 3. 여유자원이 없으면 기다리게 된다.
3. P[i]에게 자원을 할당해주었다고 가정하고, Safety Algorithm을 실행시킨다. Available = Available - Request[i] -> 자원을 할당해주었다. Allocation[i] = Allocation[i] + Request[i] Need[i] = Need[i] - Request[i] 그 후 Safety Algorithm실행. safe -> 실제로 자원 할당, unsafe -> 자원을 할당하지 않고 P[i]는 기다리게 된다. 그리고 Available, Allocation, Need등 변경시켰던 값들을 다시 복원하게 된다.

Deadlock Detection

Deadlock state에 빠질 수 있게 허용하지만 Deadlock State를 탐지하고 회복한다.

Single Instance of Each Resource Type

 

하나의 자원에 하나의 인스턴스만 있을 때 Detection방법 Wait-for Graph를 그린다. Wait-for Graph에서 Node들은 하나의 프로세스를 의미한다. P[i] -> P[j]는 P[i]가 P[j]가 가진 자원을 기다린다는 것을 의미한다.

주기적으로 Wait-for Graph에 Cycle이 생기는지 검사한다. 검사하는 비용(Overhead)가 많이 든다.

Wait-for Graph는 Resource-Allocation Graph를 단순화시킨 것이라고 할 수 있다. Resource-Allocation Graph에서 자원의 노드를 전부 없앤 것이다. Wait-for Graph에서 Cycle이 생기게 되면 Instance가 하나일 때 무조건 Deadlock이 발생하는데, 여러 Instance일때를 가정하지 않았기 때문에 Cycle이 생기면 무조건 Deadlock이 발생한다고 가정한다.

Several Instances of a Resource Type

하나의 Resource가 여러 Instance를 가질 수 있다고 가정하자.

Available : 현재 여유분. Allocation : 프로세스에 할당된 자원. Request : 프로세스가 요청하는 자원. Request[i][j] =k 이면 P[i]가 R[j]를 k개만큼 요청하는 것이다.

Detection Algorithm

1. Work = Available, 모든 i에 대해서 Allocation[i]가 0이 아니면 Finish[i] = false이다.(자원이 할당된 것이 있으면 아직 프로세스가 종료되지 않았다.)
2. 모든 i에 대해서 Finish[i] == false이고 Request[i] < Available 이면 goto3, 모든 i가 조건을 만족하지 않으면 Deadlock이 발생했다고 가정한다.
3. Work = Work + Allocation[i], Finish[i] = true. 그리고 이 2~3과정을 반복한다.
4. 어떤 Finish[i] == false인데 할당해줄 여유 자원이 없다면 P[i]에서 Deadlock이 발생했음을 알 수 있다.

이 알고리즘은 많은 Overhead 비용을 필요로 한다.

Detection-Algorithm Usage

얼마나 자주 Detection알고리즘을 실행시키는게 좋을까? 다음과 같은 조건에 따라서 결정된다.

1. 얼마나 자주 Deadlock이 발생할 가능성이 있는가?
2. Deadlock에 관련된 Process의 갯수가 많은가? 적은가?

임의로 Algorithm 실행 주기를 결정하게 되면, Deadlock을 발생시킨 프로세스를 특정하기 어려울 수 있다.

Recovery from Deadlock : Process Termination

Process Termination = 비정상적인 프로세스 종료 프로세스를 종료하는 방법.

1. 모든 프로세스를 종료시킨다.
2. 하나씩 프로세스를 종료한다 -> 어느 프로세스를 먼저 죽일 것인가? 2-(1). 우선순위에 따라서 2-(2). 작업한 기간이 짧은 프로세스, 남은 작업기간이 많이 남은 프로세스를 우선적으로 종료시킨다. 2-(3). 사용하는 자원의 갯수가 많은 프로세스를 우선적으로 종료시킨다. 2-(4). 프로세스가 종료할 때 까지 필요한 자원의 수가 많은 프로세스를 우선적으로 종료시킨다. 2-(5). 얼마나 많은 프로세스를 종료시켜야 하는지를 고려한다. 2-(6). Interactive한 작업은 먼저 종료시키고, Batch 작업은 한번에 수행하는 작업의 크기가 크므로 나중에 종료시킨다.

Recovery from Deadlock : Resource Preemption

Resource Preemption = 프로세스를 죽이지 않고 자원을 빼앗아오는것.

어떤 프로세스를 먼저 희생양으로 삼을것인가? -> Cost를 Minimize해야한다. Rollback -> 희생양이 된 프로세스는 종료되지 않고, Safe state가 된다면 프로세스가 Restart된다. Starvation이 발생할 가능성이 있다. 따라서 Preemption된 횟수를 고려하는 것이 한 방법이 될 수 있다.