[10] 운영체제 - Deadlock-2

안녕하세요. 이번 글에서는 지난 글에서 다루지 못했던 Deadlock을 다루는 방법,  예방하고 해결하는 방법에 대해 알아보도록 하겠습니다. 그럼 바로 시작해보겠습니다. Methods of Handling Deadlocks Deadlock을 다루는 방법에는 크게 세 가지가 있습니다. 첫째, Deadlock 현상 자체를 미연에 방지하는 방법     말 그대로 애초에 Deadlock이 발생하지 않도록 하는 방법입니다.     -Deadlock prevention, Deadlock Avoidance 둘째, Deadlock 상태를 허용하면서 그것을 복구하는 방법     현재 상태를 주기적으로 체크하면서 Deadlock 상태인지를 확인하며 Deadlock에 빠지면 복구를 하는 방법입니다.     -Deadlock Detection Algorithm 셋째, Deadlock 문제 자체를 무시해버리는 방법     사실상 대부분의 운영체제가 이 방법을 사용합니다. 위의 두 가지 방법은 그에 따른 비용이 높기 때문에     문제가 있는 프로세스를 Kill 하거나 시스템 자체를 리부팅하여 Deadlock 문제를 해결을 합니다.     -Kill Process, Rebooting 그럼 중요한 것들만 다뤄보도록 하겠습니다. 1. Deadlock Prevention Deadlock Prevention은 이전 글에서 다루었던 Deadlock이 일어나기 위한 조건 4 가지 중 아무것이나 하나를 충족시키지 않게 함으로써 Deadlock을 방지하는 방법입니다. 4 가지의 조건이 모두 만족해야 Deadlock이 발생하기 때문에 하나만 충족시키지 않아도 Deadlock은 발생하지 않게 됩니다.          (1) Mutual Exclusion 부정         사실 이 조건을 충족시키지 않는 방법은 존재하지 않습니다.         애초에 자원에 동시 접근이 불가능하기 때문에 동시에 접근을 하게 하는것은 불가능     (2) Hold and Wait 부정         프로세스가 자원을 요청할 때는 항상 어느 자원도 소유하고 있지 않게 해야 한다.         프로세스가 실행되기 전에 필요한 자원들을 모두 요청하고 할당받아야 합니다.                      ex) 프로세스 P가 Disk 자원과 Printer의 자원을 필요로 할 때 두 자원을 모두 할당받은 상태에서 시작을 해야 합니다.                     하지만 만일 Disk 자원을 먼저 사용하고 일정 시간이 지난 후 Printer 자원을 사용하는 순서라면  P는 Printer 자원을                     갖고 있으면서도 바로 사용하지 않기 때문에 전체적인 자원의 효율성이 떨어지고 이러한 비효율적인 자원 할당으로 인한                     우선순위가 낮은 프로세스들은 자원을 할당받지 못하는 시간이 길어지는 Starvation 문제가 생길 가능성도 생깁니다.     (3) No Preemption 부정         No Preemption은 갖고 있는 자원을 프로세스가 스스로 반납하기 전까지는 회수되지 않는 조건인데, 이를 부정하는 방법으로는         프로세스가 하나 이상의 자원을 소유하고 있고 즉시 할당받을 수 없는(다른 프로세스가 소유한) 다른 자원을 요청한다면         소유하고있는 자원을 모두 반납하게 하는 것입니다.         그리고 이전에 사용하던 자원들과 할당을 요청한 자원을 모두 할당받았을 때만 다시 프로세스 수행이 가능합니다.     (4) Circular Wait 부정         Circular Wait란 프로세스 간 자원을 소유하고 요청하는 형태가 원형을 이루는 현상을 말합니다. 이를 부정하기 위해서는         자원들의 Total Ordering을 반환하는 F() 함수를 사용해야 합니다.                  여기서 잠깐! Total Ordering은 무엇일까요?                 Ordering에는 두 가지가 있는데 Partial Ordering과 Total Ordering이 있습니다. 예를 들어 설명해보도록 하겠습니다.                 (5,2,3,1,6,11) : Total Ordering                 (c, d, e, f a, z , 1, 4, 2, 바, 가, 나) : Partial Ordering                 두 개의 차이점을 아시겠나요? Total Ordering 이란 해당 자료들을 일정한 기준에 따라 모두 정렬할 수 있는 것이고                 Partial Ordering은 부분으로는 정렬을 할 수 있으나 전체를 정렬하기는 불가능 한 것을 말합니다.         자! 다시 본론으로 돌아와 Circular Wait를 부정하는 방법을 설명하고 예를 들어보겠습니다. 방법은 다음과 같습니다.         프로세스는 현재 소유하고 있는 자원의 타입의 F() 함수 우선순위보다 높은 우선순위의 자원들만 요청할 수 있으며         소유하고 있는 자원의 우선순위가 가장 높다면 소유하고 있던 자원들을 모두 반납하게 됩니다.             ex) 자원에는 Disk, Printer, Tape 이렇게 세 가지가 있고 각각은 F(Disk) = 10, F(Printer) = 20, F(Tape) = 30 의 우선순위를             갖고 있다고 가정하자. 만일 프로세스 P가 Disk 자원을 소유하고 있다면 Printer나 Tape의 자원을 요청할 수 있으며             만일 P가 Tape의 자원을 소유하고 있는 상태에서 Disk나 Printer를 요청하게 된다면 모든 자원을 반납하게 됩니다.             그리하여 만일 P1이 P2의 자원을 요청할 때 P2가 소유한 자원의 우선순위가 P1이 소유한 우선순위보다 낮다면 요청 자체가             불가능하게 되므로 Circular Wait 상태가 일어나지 않게 됩니다. 2. Deadlock Avoidance Deadlock Avoidance는 운영체제에게 자원 요청이 들어오면 자원을 할당해주었다고 가정한 상태에서 잠재적으로 Deadlock이 일어나는지 유무를 판단하여 Deadlock이 일어난다면 자원이 충분함에도 불구하고 할당해주지 않는 방법입니다. 판단을 했을 때 Deadlock이 일어나지 않는 상태를 Safe State라 하고 현재 이용 가능한 자원, 현재 각각의 프로세스에게 할당되어 있는 자원 그리고 각각의 프로세스들이 사용하고 반납할 자원들의 정보를 바탕으로 잠재적 Deadlock의 유무를 판단합니다. 프로세스 간 자원 할당 순서 중 Safe State Sequence가 하나라도 존재한다면 Safe State라고 판단을 합니다. 위의 문장이 전혀 이해가 되시지 않죠? 천천히 설명해보도록 하겠습니다. 먼저 Safe State Sequence란 일종의 자원을 필요로 하는 프로세스들에게 자원을 할당해주는 순서인데 바로 이전 프로세스가 수행을 마치고 반납한 자원과 현재 할당 가능한 자원을 이용해 현재 프로세스에게 할당이 가능한 프로세스의 자원 할당 순서를 Safe State Sequence라고 합니다.  당장 할당이 불가능해도 이전의 프로세스들이 반납을 함으로써 할당이 가능하다면 그 순서 또한 Safe State Sequence라고 합니다. 이 설명을 또한 상당히 부족하다고 느끼시는 분도 계실 것입니다. 그럼 예를 들어 설명해보도록 하겠습니다. 집중하고 읽어보세요! 현재 두 개의 프로세스 P1, P2는 Printer라는 자원을 필요로 하고 있습니다. 그럼 운영체제는 Printer 자원을 P1 - P2 순서로 할당해 줄 수도 있고 P2-P1 순서로 할당해 줄 수 있습니다.  물론 Printer 자원이 충분히 많다면 동시에 할당해줌으로써 병렬적 처리를 하게 됩니다. 하지만 만일 Printer 자원이 부족하다면 하나의 프로세스가 작업을 끝내고 자원을 반납해야 다음 프로세스가 사용할 수 있습니다. 자! 만약 현재 상태에서 Printer의 자원 인스턴스가 8개이고 P1은 Printer 자원을 5개 소유하고 있으며 작업을 끝내려면 Printer 자원 6개가 더 필요하며 P2는 2개를 소유하고 있으며 9개를 요청한 상태라고 가정해봅시다. 만일 P2-P1의 순서대로 Printer 자원을 요청한다면 P2는 9개의 자원을 요청했지만 현재 지원 가능한 자원은 8개이므로 지속해서 대기해야 하고 다른 프로세스가 반납을 해야 자원을 할당받고 작업을 수행할 수 있기 때문에 Deadlock의 가능성이 있습니다. 그럼 반대로 P1-P2의 순서대로 Printer 자원을 지원한다면 P1은 6개만을 요청하였기 때문에 현재 자원으로 할당이 가능합니다. 그리고 할당받은 자원으로 작업을 수행하고 끝낸다면 원래 소유하고 있던 Printer 자원 5개와 할당받은 자원 6개를 반납하여 Printer의 현재 할당 가능한 자원 인스턴스의 수는  2 + 5  + 6 = 13이 되게 됩니다. 그러면 현재 할당 가능한 Printer의 자원은 13이므로 P2가 요청하는 9개를 할당해주고 P2까지 Printer 자원을 필요로 하는 모든 작업들을 Deadlock 없이 완료할 수 있게 됩니다. 여기서 P1-P2, 이 순서를 Safe State Sequence라고 합니다. 자원을 주었다고 가정한 상태에서 계산을 했다는 것이 요점입니다. Safe State Sequence가 1개라도 존재한다면 Safe State입니다. 만일 Safe State라면 Deadlock은 반드시 일어나지 않고 Safe State가 아니라 해도 Deadlock이 일어날 수도 있고 일어나지 않을 수도 있습니다. Deadlock Avoidance Alogrithm - Banker's Algorith Safe State Sequence를 선택할 때 만일 자원의 인스턴스가 하나라면 이전  글에서 언급한 자원 할당 그래프로 판단할 수 있지만 자원의 인스턴스가 여러 개라면 Banker's Algorithm을 사용하는 것이 바람직합니다. Resource Allocation Graph 위의 예시에서 R2라는 자원을 P1과 P2가 차후에 요청할 때 만일 여기서 P2에게 할당을 해주면 사이클이 생기고 Deadlock 상태에 빠지므로 R2를 P1에게 먼저 할당을 해주고 P1이 작업을 완료하고 R1과 R2를 반납하면 반납된 자원으로 P2가 작업을 수행하고 완료할 수 있습니다. 그렇다면 여기서 Safe State Sequence는 P1 - P2 가 됩니다. 이렇게 자원의 인스턴스가 하나라면 자원 할당 그래프를 이용하여  Safe State Sequence를 찾을 수 있습니다. 자원의 인스턴스가 다수라면 Banker's Algorithm을 사용해야 합니다. Banker's Algorithm는 Resource Request Algorithm의 큰 흐름으로 이루어져 있는데요 Resource Request Algorithm 이란 어느 프로세스로부터 운영체제에게 자원 할당의 요청이 들어온다면 운영체제는 해당 프로세스가 요청한 자원에 대해 할당이 가능한지를 판단하고 할당이 가능하다면 할당을 해주었다 가정한 이후에 프로세스들 간의 Deadlock의 발생할지를 검사하여 만약 Deadlock이 발생한다고 판단되어지면 자원을 할당하지 않고, Deadlock이 발생하지 않는다면 자원을 할당해주는 알고리즘입니다. 먼저 Resource Request Algorithm의 큰 흐름부터 알아보도록 하겠습니다. Resource Request Algorithm Resource Request Algorithm은 이해하시는데 큰 무리가 없으실 거라 생각됩니다. 먼저 필요한 자료구조가 무엇인지 살펴보고 알고리즘에 대해 설명해보도록 하겠습니다. 1. n : 프로세스의 개수, m : 자원 타입의  개수 2. Available : m 길이의 Vector로 현재 자원들의 할당 가능한 인스턴스들을 나타냅니다. 3.  Max : n X m 형태의 Matrix로 Max[i, j] = k라면 이는 P(i) 프로세스는 작업을 완료하기 위해 R(j) 자원을 최대 k 개 필요함을 의미. 4. Allocation : n X m 형태의 Matrix로 Allocation[i, j] = k라면 현재 P(i) 프로세스는 R(j) 자원을 k 개 할당받았다는 것을 의미. 5. Need : n X m 형태의 Matrix로 Need[i, j] = k라면 현재 P(i) 프로세스는 작업을 완료하기까지 R(j) 자원을 k 개 더 필요함을 의미. 즉 Max[i, j] - Allocation[i, j] = Need[i, j] 먼저 하나의 프로세스 P가 자원을 요청을 하면 요청한 자원의 양이 현재 P가 필요로 하는 자원의 양과 비교를 합니다. 만약 필요한 양보다 많은 양을 요청을 하게 된다면 에러 처리를 합니다. 그리고 요청한 자원의 양이 현재 할당 가능한 자원의 양보다 크다면, 즉 당장 요청한 자원에 대해 할당해줄 자원이 부족하다면  다른 프로세스들이 반납할 때까지 기다립니다. 두 조건을 모두 만족하면 할당해주었다 가정하고 다음과 같은 값의 상태(가정)로 Safe State를 검사합니다. Available = Available - Request Allocation = Allocation + Request Need = Need - Request 그리고 위의 상태에서 Safe State 인지를 판단하기 위해 Safe State Sequence를 찾는 Safety Algorithm을 사용합니다. 그리하여 Safe State라 판단이 된다면 실제로 자원을 할당하고 위의 상태로 바꿔줍니다. Safety Algorithm Safety Algorithm은 직접적으로 Safe State 인지를 검사하는 알고리즘으로 Safe State Sequence를 찾는 알고리즘입니다. 알고리즘의 내용을 보시고 밑의 예를 보며 설명을 보시면 이해가 가실 것입니다. Safety Algorithm Safety Algorithm으로 위의 예시의 상황에서 Safe State Sequence 중 하나로 < P1, P3, P4, P0, P2 > 순서가 뽑힐 수 있습니다. 천천히 설명해보도록 하겠습니다. 자원들의 시작 전 총 Available은 (10 , 5, 7)이나 현 상태에서는  (3, 3, 2)가 됩니다. 그러므로 Work는 (3, 3, 2)가 되고 Finish들은 모두 false로 초기화됩니다. 결과론적인 방법이긴 하나 먼저 P1에게 자원들을 할당해주면 현재 Finish[1] 은 false이며 P1의 Allocation은 (2, 0, 0)이고 Max는 (3, 2, 2)이므로 Need는 (1, 2, 2)가 됩니다. 그러므로 Need <= Work이므로 3단계로 넘어가서 Work는 Work(3, 3, 2)에 현재 P1의 Allocation (2, 0, 0)을 더한 (5, 3, 2)가 됩니다. 그리고 Finish[1]을 작업을 완료했다는 의미로 True로 바꿔주고 다시 2단계로 돌아가 자원을 할당해줄 프로세스를 선택하고 이 과정은 Finish의 모든 값이 True가 될 때까지 반복해줍니다. 왜 이렇게 하는 것일까요? P1이 현재 필요로 하는 자원의 양이 현재 할당 가능한 자원보다 작다는 것은 할당해줄 수 있다는 뜻이고 그것을 할당해주고 작업을 완료하면 현재 할당되어 있는 자원들까지 회수되기 때문에 작업이 완료되었다 가정하고 Available에 Allocation을 더해줌으로써 P1이 끝난 후에 Available 현황을 알 수 있게 됩니다. 그리고 Available의 현황을 이용하여 다음 프로세스를 고르는 작업을 반복하고 회수한 자원들로 증가된 Available로 자원을 할당하여 모든 프로세스의 작업을 끝내게 되면 Finish는 모두 True가 되고 그렇게 뽑힌 순서가 바로 Safe State Sequence가 됩니다. 여기서! Deadlock Prevention 과 Avoidance의 차이점을 아셔야 합니다! Prevention은 자원을 할당해주되 Deadlock이 일어나지 않게끔 할당해주는 것이고 Avoidance는 Deadlock이 발생하는지 미리 검사를 하고 일어난다면 자원이 충분히 있음에도 불구하고 할당해주지 않는 것을  의미합니다. 이번 주는 Deadlock을 미리 방지하는 방법들인 Deadlock Prevention과 Deadlock Avoidance에 대해 공부를 해보았는데요. 다음 주 수업 시간 포스팅에서는 나머지 방법들에 대해 공부해보도록 하겠습니다. 감사합니다.