Operating System - Deadlock & Starvation

 

 

안녕하세요 :)

 

이번 포스팅에서 다루어볼 내용은 Deadlock과 Starvation입니다.

 

지난 포스팅이후로 운영체제 카테고리를 정말 오랜만에 다루어 봅니다. 게으름뱅이 체질은 역시 힘드네요 ㅎ.. 하지만 이제 운영체제과목 기말고사를 앞두고 있기도합니다. 펜만잡고 공부하는것 보단 블로그포스팅을 하면 조금더 정확하게 내용을 정리하고자 노력하니까 머리에 잘 들어오는것 같습니다.

 

서론이 길었네요!

 

이번 포스팅은 Deadlock과 startvation에 대하여 다루어볼것입니다. 지난 포스팅에서도 프로세스를 교체해야 하는상황을 다룰 때나 프로세스의 상태정보를 다룰때 조금씩 언급했던것 같습니다. 이번 포스팅에선 조금더 상세하게 다루어 보겠습니다.

 

principles of Deadlock (데드락의 원리 or 원칙)

-permanet blocking(영구적인 블락)

 시스템 리소스를 경쟁하거나 소통하는 프로세스들을 영구적으로 블락킹시킴 

 

-No efficient solution

 완벽한 솔루션은 존재하지 않는다

 

-Involve conflicting needs for resources by two or more processes

 둘 이상의 프로세스가 리소스에 대한 상반된 요구를 행할때

 

말이 어렵네요, 제가 이해한 내용은 데드락이란 프로세스간의 리소스 점유 경쟁을 행할때 양보가 없어 경쟁관계 또는 소통 관계를 하는 프로세스들이 교착된 상황 정도 일것 같습니다. 

 

그럼 리소스간의 경쟁또는 소통에 관하여 발생한다니까 리소스의 종류를 한번 살펴볼께요(데드락을 말할때 꼭 필요합니다)

 

- 리소스(자원)는 크게 두가지로 나뉩니다. 재사용이 가능한 Reusable Resources와 재사용이 블가능한 Consumable Resources 로 말이죠

 

 

Reusable Resources(재사용 가능한 리소스)

- 재사용 가능한 리소스의 경우 Processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores 등이 있습니다.

 

- 한번에 하나의 프로세스만 사용하고 그 사용으로 인해 고갈되지 않습니다. 

 

- 프로세스는 나중에 다른 프로세스에서 재사용하기 위해 릴리스(풀어주는)하는 리소스를 확보합니다.

 

- 각프로세스가 하나의 리소스를 보유허고 다른 리소스를 요청하는 경우 데드락이 발생합니다.(hold & wait)

  (프로세스가 여러 리소스를 요구하는데 여러 리소스중 하나 이상이 다른 프로세스에게 할당되어있을 경우)

 

 

<데드락의 예>

Request (프로세스가 리소스에 대한 사용 요청)

lock (요청한 프로세스만 사용할수 있게 할당된 상태)

 

위 처럼 하나이상의 프로세스들이 제한된 리소스에 대한 요청으로 인해 교착되어 있는 상태가 데드락의 예가 될수 있습니다.

 

또다른 예로는 제한된 메모리 용량에 대한 요청이 있을수 있습니다.

 

 

 

Consumable Resources (재사용 불가한 리소스)

- 주로 시그널과 관련된 리소스

 

-예로 Interrupts , signals, messages, and information in I/O buffers 가 있습니다.

 

-특이한 (rare) 한 케이스 이지만 발생할 가능성은 있습니다.

 

만약 두 프로세스가 서로 요청을 받아야만 실행이 가능한 상태라 해보겠습니다.

p1은 p2에게 메세지를 수신해야 수행이 가능하고 p2는 p1에게 메세지를 받아야한 수행이 가능하다면 두 프로세스는 서로를 영구적으로 기다리기만하는 데드락 상태에 빠집니다.

 

 

Resource Allocation Graphs

 데드락이 발생한 프로세스와 리소스를 그래프(노드와 디렉션을 갖는 직선)로 표현한다면 싸이클이 생성되어 있는것을 발견할수 있습니다. 당연히 여러 프로세스가 제한된 리소스에 대해 요구할때 발생하겠죠 아래 그림과 같습니다.

 

 

 

 

Conditions for Deadlock

그렇다면 이러한 데드락을 어떻게 발생 할까요? 데드락 컨디션에 대해 다루어 보겠습니다.

 

먼저 데드락이 발생할 필요 충분 조건을 알아보겠습니다.

 

필요조건)

 

1. Mutual exclusion

지난 포스팅에서 다룬 상호 배제입니다. 이는 크리티컬섹션접근에 한하여 프로세스의 접근 갯수에 제한을 두는것 이었습니다. 하나의 프로세스가 섹션안에 있을 때 해당 섹션을 접근하고 싶은 다른 프로세스는 모두 교착상태에 빠지게 되죠 (앞서 들어간 프로세스가 나올때 까지말입니다.)

2. Hold and wait

이 경우는 위의 그래프 그림과 같습니다 하나의 프로세스가 리소스 하나를 점유하고 있으면서 두번째 리소스를 요청하는 경우 입니다. 하지만, 두번쨰 리소스가 다른 프로세스에게 이미 할당된 상태라면 할당이 끝날때 까지 기다려야 겠죠.

 

3. No preemption

이는 선점 방식이라는 이름으로도 불립니다. 한 프로세스가 CPU를 할당받아 실행중 이라도, 다른 프로세스가 현재 프로세스를 중지시키고 강제적으로 뺏을수 있는 방식을 말해죠.

 

충분조건)

 

4. Circular wait

각 프로세스가 다음 프로세스에 필요한 리소스를 체인에 하나 이상 보유하는 폐쇄된 프로세스 체인이 존재합니다.

hold and wait 상태가 위의 그래프처럼 하나이상의 고리를 형성한것을 말합니다.

 

필요 충분 조건에 의거하여 1,2,3번 조건이 만족했을경우 데드락이 발생했을 가능성이 다분한 경우이고, 4번이 조건이 만족했을 때는 무조건 데드락이 발생한 것입니다.

 

 

그렇다면 이러한 데드락을 어떻게 관리 주어야 할까요? 

 

 

 

Deadlock handling

데드락을 관리하는 방법을 알아보겠습니다. 크게 세가지 방법이 존재합니다.

 

1. Deadlock Prevention 2. Deadlock Avoidance 3. Deadlock Detection

 

 

1. Deadlock Prevention

이는 데드락이 발생할 조건을 원천봉쇄하는 방법입니다.

데드락이 발생하기 위한 네가지 조건중 하나라도 제거 해봅시다.

 

Mutual exclusion - 상호 배제를 보장해주지 않는다면 생길수 있는 문제들(이전 포스팅에서 다루어 보았습니다)이 훨씬 많기 때문에 이 조건을 제거하는것은 바람직하지 않습니다.

 

나머지 아래의 세가지 조건을 봉쇄하는것 입니다 하나씩 해보겠습니다.

Hold and wait / No preemption / Circular wait

 

Hold and wait - 처음부터 필요한 모든 리소스를 요청(동시에), 모든 요청(리소스에 대한)이 허락될때 프로세스를 실행하는 방법입니다. 무식하지만 효과는 굉장합니다. 리소스에 대한 요청을 처음부터 모두 해두고 허락이 떨어질때 들어간다면 데드락이 발생할 일이 없을것입니다. 하지만 아직 사용되지 않을수도 있는 리소스가 계속 소비되고 있을수 있습니다. 만약 100가지 작업을하고 프린트하라 라는 요청을 받아들일시, 한꺼번에 요청하고 할당하기 때문에 100가지 작업을 하는동안 프린트라는 리소스는 하염없이 기다리며 시간이 낭비됩니다. 그리고 개발자가 하나의 프로세스 실행에 필요한 모든 리소스를 꿰고 요청해 주어야 하는데, 교수님 말씀을 인용하자면 "개발자가 신도 아니고" 현실적으로 어렵습니다.

 

No preemption - 운영체제가 다른프로세스에 할당된 리소스를 강제로 가져와서 할당해주는 방법, 선점 방식을 깨겠다는 의미 입니다, 할당되어있더라도 뺏겠다! 근데 딱봐도 문제가 보입니다. 만약 리소스가 프린터라면 출력하고 있는데 반 출력하고 다른 내용으로 반을 출력하겠다? 말이 안됩니다. 그래서 단점으로 모든 리소스가 해당 방법을 사용할수는 없다는 것입니다. 그런데 만약 리소스가 CPU라면 가능하겠죠 타임쉐어링 방법을 엄청다뤄봐서 알겠지만 시간단위로 쪼개서 여러 프로세스에 할당해 주었으니까요

 

Circular wait - 리소스에 인덱스를 부여하고 규칙에 따라 리소스를 할당하는 방법입니다. 이는 리소스 활용면에 있어서 너무 비효율적이죠! 놀고있는 리소스 많이 생길것입니다.  

 

2. Deadlock Avoidance

이는 요청이 발생할때마다 현재 상태에서 잘 판단해서 데드락을 피하는 방법입니다.

리소스의 요청이 일어날때마다 데드락이 발생할 확율을 체크해 요청을 처리하는 방법입니다. 이렇게 하면 동시에 다룰수있는 프로세스의 갯수가 Prevention 보다는 더 많아질것입니다. 이를 concurrency 라고도 합니다.

 

이방법의 경우 각 프로세스 마다 리소스 요청에 대한 정보를 제공해야합니다. 하지만 어렵죠!

이 방법은 데드락에 관해 두가지 접근 방식이 있습니다. 첫번째로 데드락을 발생시킬만한 프로세스를 아예 시작하지말라는 방식, 두번째로 데드락을 발생시키만한 요청을 허가하지 말아라 가 있습니다.

 

이제 조금 어려워 보이는 벡터와 메트릭스를 이해해야 하는데 알고보면 정말 별거없습니다. (제가 수학 젬병이니까요)

 

아래에 자세한 필기를 첨부해 두었습니다.

 

 

 

 

정말 핵심만 뽑아보면 클레임 백터와 전체시스템이 보유한 리소스 벡터 R을 비교해서 해당 클레임을 수행했을때 데드락이 발생할까? 만 생각하며 계산하면 됩니다.

 

이과정에서 실제로 할당된 리소스에대한 메트릭스인 A,

클레임 벡터를 모아둔 메트릭스 C,

전체 시스템에서 A 메트릭스에게 할당하고 남은 남은 리소스에 대한 메트릭스 V를 다루게됩니다.

 

뱅커's 알고리즘 - 전체 시스템에서 데드락이 발생할 요청과 데드락이 발생하지 않고 안전하게 종료될 요청을 분간하기위해 밟는 절차,

이때 해당요청이 데드락이 발생하지 않고 프로세스가 종료되는 하나이상의 시퀀스가 존재할때 이를 safe states 라고 한다. 그리고 만약 데드락을 발생시킨다면 unsafe state라 한다.

 

과정)

프로세스가 리소스를 요청 -> 요청을 허락했다 가정 -> 가정한 상태를 update -> safe state or Not 체크 -> 만약 safe 하다면 해당 요청 허락

 

3. Deadlock Detection

이는 데드락의 발생은 방치하지만, 주기적인 체크를 통해 데드락된 프로세스들을 관리해주는 방법입니다.

리소스에 대한 요청은 가능하기만 하다면 바로 허가해주는 방법입니다. 당연히 데드락이 빈번히 발생하겠죠 하지만 주기적인 체크를 통해 이를 해소해주는 방법입니다.

이 방법에선 데드락 발생을 체크하는 주기가 조금 중요하겠네요, 너무 빈번하게 체크한다면 전체 체크시간이 길어져 전체 시스템에 처리시간이 길어질테고, 체크를 자주안해준다면 발생한 데드락을 방치하게 될테니까요.

 

뱅커스 알고리즘과 비슷하지만 다른 방법을 사용합니다. 바로 마크를 이용하는것인데요, 전체 검사를 돌린후 마크가 있다면 정상 마크가 없다면 데드락 발생한 프로세스 입니다. 자세한 내용은 아래의 필기와 같습니다.

 

 

 

그리고 만약 데드락이 존재하고 있다면 마크가 없는 각프로세스간에 싸이클이 존재하고 있을것 입니다.

 

그럼 데드락을 끊어주어야 겠죠? 이미 발생했으니까요

 

이때의 방법은 아래와 같습니다.

 

- 데드락에 참여한 모든 프로세스 종료 (무식하네요, 하지만 효과는 당연하겠죠)

- 데드락의 고리가 끊어질때까지 한 프로세스씩 종료하며 끊김을 도모한다.

- 데드락이 발생하지 않던 시점의 체크포인트를 만들어두고 데드락이 발생시 그 이전의 체크포인트로 돌아간다.

   [이 방법의 단점은 (데드락 발생 <-> 체크포인트 돌아감) 싸이클이 생길수 있습니다.]

- 데드락이 더이상 존재하지 않을때까지 리소스를 각각 프로세스에 독점시킴

   ex) p1,p2,p3 데드락, p1 리소스독점 -> p1 종료 -> p2 리소스 독점 -> p2 종료 -> p3 리소스 독점 -> p3 종료

 

 

만약 무식하게 데드락난 프로세스를 죽여야 한다면 어떠한 기준으로 죽일까요?

낮은 중요도(lowest priority), 수행이 가장 조금됨, 출력된 양이 가장 적음, 리소스 점유가 가장 낮음, 프로세스의 진행이 제일 안됨