[OS] 2. 교착상태(DeadLock)

※본 포스팅은 공부목적(https://develaniper-devpage.tistory.com/77)에 따라 해당 블로그와 깃허브를 참조하여 제작된 포스팅 입니다.

 

 

1. 교착상태(DeadLock)

 교착상태는 상호배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 무한정 기다리는 현상을 말합니다.

 

교착상태(DeadLock)

그림으로 표현하면 위와 같습니다.

 

이와 같이 교착상태가 발생되는 조건은 다음과 같은 4가지가 있습니다.

1. 상호배제
   • 한 자원은 하나의 프로세스에서만 사용이됩니다.(한 자원이 2개의 프로세스에서 사용될 수 없음)
2. 점유대기
   • 프로세스A는 자원1을, 프로세스B는 자원2를, 프로세스C는 자원 3을 각각 소유하고 있으면서 다른 자원을 사용하기 위해 대기하고 있습니다.
3. 환형(순환)대기
   • 각각 A->B, B->C, C->A 가 사용하고 있는 자원을 대기하며 대기 상태에 사이클이 생겼음을 볼 수 있습니다.
4. 비선점
   • 각각 자원이 서로가 사용하는 자원이 필요하지만 다른 자원이 사용하는 자원을 뺐어서(강제로) 사용할 수 없습니다.

교착상태는 위 4가지의 조건을 모두 만족해야만 교착상태가 일어납니다.

 

이 말을 바꿔서 말하면 4가지 조건중 하나라도 만족하지 못하게 한다면 교착상태는 일어나지 않습니다.

 

2. 교착상태 해결방법

더 자세한 교착상태를 해결하는 방법입니다.

• 예방 - 4가지 조건 중 하나라도 만족되지 못하게 함 => 자원낭비가 가장 심한 기법
• 회피 -  교착상태가 발생할 가능성을 배제하지 않고 적절하게 피해나가는 방법이다. (은행원 알고리즘)
• 탐지 & 회복 - 교착상태가 발생하면 그때 해결함
• 무시&모른척 - 대부분의 운영체제가 사용하는 방법으로 교착상태의 해결을 응용 개발자의 몫으로 돌린다.

위 내용들을 자세히 들여다 보겠습니다.

 

1) 예방

• 상호 배제 부정
  • 프린트 같은 자원은 한번에 한 프로세스만 점유할 수 있지만 ReadOnly파일 같은 경우에는 한번에 여러 프로세스가 접근해도 괜찮습니다. 이런 경우에는 한 자원을 여러 프로세스가 사용하게 하여 상호배제조건을 없앨 수 있습니다.
  • 다만, 어떤 자원은 근본적으로 공유가 불가능 하기 때문에 상호배제조건을 없애는 것은 불가능 합니다.
• 점유 대기 부정
  • 프로세스에게 자원을 할당 할 때 자신에게 할당된 자원을 모두 방출한 후 자원을 요청하도록 하여 점유대기 조건을 없앨 수 있습니다.
  • 하지만 많은 2개 이상의 자원이 필요할 때, 자원이 한꺼번에 할당이 된다면 자원의 이용율이 낮을 수 있다는 문제점이 있습니다.
  • 또한, 필요한 자원 중 자주사용되는 자원을 필요로 한다면 무한정 대기해야하는 기아 상태가 될 수 있습니다.
• 비선점 부정
  • 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 자원들이 선점됩니다.(묵시적으로 방출됨)
  • 즉, A프로세스가 자원2를 사용하려 했을 때 대기 중인 B프로세스가 자원2를 가지고 있다면 자원2를 선점해서 사용합니다. 하지만 자원2를 다른 프로세스가 사용 중이라면 A프로세스는 대기 상태로 기다립니다.
  • 이 방법은 CPU레지스터나 메모리 공간처럼 그 생태가 쉽게 저장되고 후에 복원될 수 있는 자원에 종종 적용지만, 프린터나 테이프 드라이브 같은 자원에 적용 될 수 없다는 문제가 있습니다.
• 순환 대기 순환대기
  • 자원에 순서를 부여하여 오름차순으로 자원을 요청하도록 요구하게 하여 순환대기를 없앨 수 있습니다.
  • 자원에 각 R1~Rn이라는 번호를 붙이고 처음에는 몇개든 Ri를 요청합니다.
  • 그 후 또 다시 자원을 요청할 일이 있다면 Ri<Rj인 자원에 대해서만 요청하는 방법입니다. 이때 Ri>Rj인 자원은 모두 방출하도록 합니다.

교착상태 예방방법을 사용한다면 장치의 이용률이 저하되고 시스템 처리율이 감소된다는 문제점이 있습니다.

 

2) 회피

 

교착상태 회피는 시스템에서 순환대기 상황이 발생하지 않도록 자원 할당 상태를 검사하는 방법입니다. 자원할당 상태는 1)가용자원의 수, 2)할당된 자원의 수, 3) 프로세스들의 최대 요구수 에 의해 정의 됩니다.

 

 [1] 안전상태(Safe State)

 - 시스템 상태가 안전 하다는 것 : 교착상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것입니다.(시스템이 안전 순서를 찾을 수 있다.) 즉, 어떤 프로세스에 대해서도 현재 가용중인 자원과 반납될 자원을 사용하여 작업을 마칠 수 있다는 것입니다. 만일 현재 프로세스가 이전 프로세스의 작업이 끝날 때까지 자원상태를 만족시킬 수 없다면 대기합니다.

 - 시스템 상태가 불안전하다는 것 : 프로세스들을 무사히 마칠 수 있는 순서를 찾지 못했을 때 불안전하다고 합니다.

 

예를들어 12개의 자원을 P0, P1, P2가 각각 10, 4, 9개 필요 했는데 다음 과 같은 일이 발생했다고 가정하자.

 

	안전상태				불안전상태
process	p0	p1	p2	남은(가용) 자원	p0	p1	p2	남은(가용) 자원
총 필요	10	4	9		10	4	9
t0	5	2	2	3	5	2	2	3
t1	5	4	2	1	5	2	3	2
t2	5	반환	2	5	5	4	3	0
t3	10	-	2	0	5	반환	3	4
t4	반환	-	2	10	5	-	3	4
t5	-	-	9	3	-- 진행 불가 --
t6	-	-	반환	12

위와 같은 표에서 볼 수 있듯이 p2가 1만큼의 자원이 필요하다고 해서 먼저 1을 부여해 버리면 p1이 작업이 끝난 후에는 모든 프로세스가 자원을 사용할 수 없는 불안전 상태로 남아 있게 됩니다.(DeadLock)

 안전상태는 이렇게 시스템이 안전상태에 머무르게하며 교착상태가 예상되면 회피하는 방법입니다.

 [2]은행원 알고리즘

은행에 적용하면 고객들이 현금을 찾으러 와도 한정된 금액 내에서 일정한 순서에 의해 모든 고객의 요청을 들어 줄 수 있게 되기 때문입니다.

 

 우선 프로세스가 시작할 때 프로세스가 가지고 있어야 할 자원의 최대 개수를 미리 신고해야합니다.

 만일 이것을 들어 주었을 때 시스템이 계속 안전상태에 머무른다면 자원을 할당해 주고, 그렇지 않다면 대기상태에 머무르게 합니다.

 

은행원 알고리즘은 위의 표에 대해서 자원이 1개가 아닌 여러개로 나누어서 생각해보는 방법입니다. 상태를 불안전하게 만들거나 가용자원이 없으면 프로세스를 대기상태로 만들고, 그렇지 않다면 자원을 할당하는 방법입니다.

 

하지만, 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원의 수가 일정해야 하는등 사용에 있어 제약조건이 많고, 그에 따른 자원 이용도가 하락한다는 단점이 있습니다. 즉, 회피는 자원의 요청이 있을때 마다 회피 알고리즘을 돌리는데 이 오버헤드가 매우 크기때문에 회피알고리즘을 많이 사용하지 않는다고 합니다.

3) 탐지& 회복

교착상태를 예방하거나 회피하는 방법의 단점으로 인해 탐지 및 회복은 교착상태가 많이 발생하는 시스템에서 많이 사용하는 방법이라고 합니다.

[1]교착상태 탐지

대기그래프 라고 하는, 자원 할당 그래의 변형을 사용해 교착상태 탐지 알고리즘을 정의합니다.

위 그래프는 교착상태인 자원에 대한 대기 그래프 입니다.

쉽게말해서 위와 같이 사이클이 생긴경우에 교착상태가 일어났다고 판단할 수 있습니다.

 그래프에서 사이클을 탐지하는 알고리즘은 O(n^2)의 연산을 요구합니다.

 

[2]교착상태 회복

교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함을써 회복하는 것을 의미합니다.

 

1.  프로세스 종료
   • 교착 상태 프로세스를 모두 중지
     교착상태를 확실하게 회복하지만 오랫동안 연산했을 프로세스를 모두 종료할 가능성이 있어 비용이 큽니다. 그동안 연산했던 부분 계산결과를 모두 폐기하여 다시 시작해야 하기 때문입니다.
   • 교착상태가 제거될 때 까지 한 프로세스 씩 중지
     프로세스가 중지될 때마다 아직 교착상태인지 확인해야 하기 때문에 오버헤드가 큰 방법입니다.
2. 자원 선점
   교착상태 해결을 위해 자원을 선점한다면 다음과 같은 것들을 고려해 봐야한다.
   • 희생자 선택 : 어느 자원과 어느 프로세스들이 선점될 것인가.
   • 롤백 : 자원을 선점하려면 그 프로세스를 안전한 상태로 롤백 시키고 그 상태부터 다시 시작해야합니다. 교착상태만 깨뜨릴정도로 롤백을 하는게 가장 효과적이지만 보다 많은 정보의 필요로 인해 오버헤드가 증가할 것입니다.
   • 기아상태 : 기아상태가 발생하지 않는지 어떻게 보장할 것인지 생각해 봐야합니다. 즉, 같은 프로세스만 계속하여 선점당한다면 그 프로세스는 무한대기 즉, 기아상태에 빠질 수 있습니다.

 

 

 

 

 

 

 

참고블로그

https://chanhuiseok.github.io/posts/cs-2/
https://coding-factory.tistory.com/311
https://velog.io/@hygoogi/기술면접-준비하기

관련 내용을 더 쉽게 보려면 아래 유트브 영상으로 먼저 간단한 내용을 확인하세요

https://www.youtube.com/watch?v=FXzBRD3CPlQ