Operating System - Multi-Programming - Deadlock

Deadlock(교착 상태)란 프로세스들이 더 이상 진행하지 못하고 영구적으로 블록 된 상태예요. 여러 프로세스들이 각자 가지고 있던 자원을 반납하지 않고 상대방의 자원을 요구할 때 발생하는데 이러면 응답 없음이 뜨고 해당 프로세스가 보유한 자원이 이 상태에서 벗어나기 전까지는 활용되지 못해요.

	Process P ... Get A ... Get B ... Release A ... Release B ...		Process Q ... Get B ... Get A ... Release B ... Release A ...
3: 프로세스 Q가 자원 B를 획득하고 프로세스 P가 자원 A를 획득하고자 하는데 이 때, Q는 자원 A를 획득하려다 블록되고 P는 자원 B를 획득하려다 블록되어요. 서로 블록되어 기다리고 있기에 더이상 진행이 불가능하죠. 4: P가 자원 A를 획득하고 Q가 자원 B를 하려고 할 때 P는 자원 B를  획득하려다 블록되고 Q는 자원 A를 획득하려다 블록되어요. 마찬가지로 서로 블록되어 기다리고 있기에 더이상 진행은 불가능해요.

위의 3, 4가 교착 상태가 발생하는 영역이고 이를 Critical section(치명적인 영역)이라고 해요. 이 치명적인 영역은 두 프로세스의 로직에 의해 결정되고 위 프로세스 코드를 변경하여 치명적인 영역을 발생시키지 않으면 교착 상태를 피할 수 있죠.

Process P ... Get A ... Release A ... Get B ... Release B ...

Process Q ... Get B ... Get A ... Release B ... Release A ...

이런 교착 상태가 일어나려면 다음과 같은 조건이 필요한데 1~3은 필요조건이지만 마지막 환형 대기 조건은 필요충분조건이에요.

1. 상호 배제 조건 Mutual exclusion

 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 있을 때예요.

2. 점유 대기 조건 Hold and wait

 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 대기할 때예요.

3. 비선점 조건 No pre-emption

 프로세스에게 할당한 자원을 다른 프로세스가 강제적으로 뺏을 수 없을 때예요.

4. 환형 대기 조건 Circular wait

프로세스 사이에 닫힌 연결이 존재할 때예요. 그러니까 위처럼 자원 할당 그래프에서 환형이 만들어질 때죠. 이는 나머지 조건들의 복잡한 상호작용의 결과로 나타나요.

 

그럼 이런 교착 상태를 해결하는 방법을 알아볼까요?

교착 상태 예방

 조건 1~3 중 하나를 허용하지 않는 간접적인 방법과 환형 대기를 허용하지 않는 직접적인 방법이 있어요. 그럼 각각 하나씩 살펴볼까요?

1. 상호 배제를 허용하지 않는다?

 이 조건은 공유 자원의 일관성을 유지하기 위해 반드시 필요해요. 그래서 없앨 수는 없죠.

2. 점유 대기를 허용하지 않는다?

 프로세스는 자신이 사용할 모든 자원을 미리 요청하고 그 자원 중 하나라도 할당받을 수 없다면 아무런 자원도 주지 않고 대기시켜요. 얼핏 듣기만 해도 쓸모없는 시간/자원낭비를 할 것 같죠? 먼저, 프로세스가 자원 A를 종료하는 직전에만 사용한다 했을 때, A를 못 받는다고 계속 기다리기는 프로세스가 머쓱하겠죠? 그런다고 A를 계속 들고 있기에도 눈치 보이고 프로세스 자신도 나중에 사용할 모든 자원을 미리 알기는 상당히 어려워요.

3. 비선점을 허용하지 않는다?

 자원을 점유한 프로세스가 다른 자원을 요청할 때 그 자원을 할당받을 수 없다면 일단 자신이 들고 있던 자원을 반납하고 다시 그 자원과 반납한 자원들을 함께 요청하거나, 다른 프로세스가 갖고 있는 자원을 뺏고 그것을 원하는 프로세스에게 할당하는 두 가지 방법이 있어요.

4. 환형 대기를 못 하게 한다?

 직접적으로 교착 상태를 예방하는 방법인데 자원의 할당 순서를 정하면 돼요. 프로세스가 자원 A를 할당받았다면 이 프로세스는 자원 A 다음의 자원만 요청할 수 있어요. 예컨대 두 자원 A와 B가 있고 운영체제가 정한 할당 순서가 알파벳 순이라면 프로세스는 A를 할당받고 B를 요청할 수 있어요. 이때 교착 상태가 발발하려면 B를 가지고 있는 아무개 프로세스 Q가 A를 요청해야 하지만 이는 사전에 불법화되었기에 상황 자체가 일어날 수 없죠.

교착 상태 회피

 교착 상태 발생 조건 중 1~3은 허용하고 위와 같이 자원 할당 순서를 미리 정하지도 않아요. 대신 자원을 할당할 때 교착 상태가 발생 가능한 상황으로 진행하지 않도록 "현명한 판단"을 내려야 해요. 즉 회피 방법은 예방 방법과 비교해서 더 높은 병행성을 가져 자원 사용의 활용성이 높아요. 프로세스가 자원을 요청할 때 이 할당이 교착 상태를 발생시키는지 동적으로 조사해서 발생시킬 가능성이 있다면 할당하지 않게 해요. 결국 프로세스의 자원 요구량을 미리 컴파일러나 어셈블러가 알고 있어야 가능해요.

1. 프로세스 시작 거부

 프로세스가 시작할 때, 요구하는 자원이 교착 상태 발생의 가능성이 있으면 프로세스를 시작시키지 않고 일단 그 자원을 사용하지 않는 프로세스부터 수행시켜요.

	시스템에 존재하는 전체 자원
	시스템에 존재하는 자원 중 현재 사용 가능한 자원들
	Cnm은 프로세스 n이 자원 m을 요구하는 것을 의미해요.
	Anm은 프로세스 n이 자원 m을 할당받아 이미 점유하고 있는 것을 의미해요.
	모든 자원은 가용하거나 할당되어 있어요.　∴가용 자원 + 할당 자원 = 전체 자원
	프로세스는 자원의 전체 개수보다 더 많은 자원을 요구할 수 없어요.
	요구한 자원보다 더 많은 자원을 할당 할 수 없어요.

모든 프로세스가 요구한 자원의 개수가 전체 자원 개수보다 적으면 교착 상태가 발생하지 않죠. 그래서 교착 상태 회피 기법에서는 다음의 식을 만족할 때 새로운 프로세스를 시작시켜요.

시그마 Cki는 현재 존재하는 모든 프로세스가 요구하는 자원의 개수이며 C(n+1)i는 새로 수행하려는 프로세스가 요구하는 자원의 개수예요.

결국 새로운 프로세스와 기존의 프로세스가 요구하는 자원의 수가 그 자원의 전체 개수보다 적을 때 수행을 허용해요. 이건 모든 프로세스가 동시에 최대 자원을 요구하는 최악의 경우를 가정해서 효율적이지 못 하죠.

 

2. 자원 할당 거부
 은행원 알고리즘이라고도 하는데 자원, 가용이라는 벡터 R, V(1*m 행렬)와 요구, 할당이라는 행렬 C, A로 표현되어요. 은행원 알고리즘은 시스템의 상태를 안전한 상태와 안전하지 않은 상태로 구분하는데 안전한 상태는 교착 상태가 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 진행경로가 존재한다는 것을 의미하겠죠?

ⓐ초기 상태 가용 자원의 개수가 현재 프로세스가 요구하는 자원의 개수보다 많으면(Cij - Aij < Vj) 아무런 문제가 없겠죠? 여기서는 P2가 남은 가용 자원으로 수행 완료할 수 있고 완료하면 자원을 반납하니까 가용 자원을 늘릴 수 있어요.	ⓑ P2 수행 완료 P2가 자원을 반납하여 가용 자원이 늘어난 모습이에요. 이때, 남은 자원으로 P1을 수행시킬 수 있고 그 이후에도 같은 식으로 반복해서 모든 프로세스를 완료시켜요.
ⓒ P1 수행 완료	ⓓ P3 수행 완료

위 케이스는 자원을 할당할 때 ⓐ에서 ⓓ까지 안전한 상태를 계속 유지할 수 있었고 모든 프로세스를 수행 완료할 수 있었어요. 그런데 아래의 경우 모든 프로세스를 수행 완료할 수 없는 상태에 도달해요.

ⓐ 초기 상태

ⓑ P1에 자원을 할당

ⓑ의 경우 그 어떤 프로세스의 자원 요구를 만족시킬 수 없어요. 그래서 수행을 완료하지 못하죠. ⓐ에서 ⓑ로 전이시키는 자원 할당은 시스템을 안전한 상태에서 안전하지 않은 상태로 전이시킨 것인데 자원 할당 거부는 이런 전이를 허용하지 않는 것이에요.

 

교착 상태 발견과 회복

 자원 접근에 대한 제산이나 프로세스의 행위에 제한을 두지 않아요. 즉 자원 할당이 가능하면 항상 할당해주는데 대신 환형 대기 조건이 발생하는지 주기적으로 검사하고 해결해주죠.

 

교착 상태 발견 알고리즘

 자원 할당이 요구될 때마다 매번 수행되면 교착 상태를 조기에 발견할 수 있고 시스템의 상태는 점진적으로 변하기 때문에 발견 알고리즘도 간단해진다는 장점이 있어 대부분이 사용하는 방법이에요. 그러나 시도할 때마다 발생하는 비용이 커진다는 단점이 있죠. 여기에 사용되는 알고리즘은 모든 프로세스의 나올 수 있는 모든 상황을 고려해서 교착 상태를 발견해요. 이 알고리즘도 할당 행렬과 가용 벡터를 사용하고 요청 행렬 Q가 추가되어요. Qij는 프로세스 i에 의해 요청된 자원 j의 개수를 의미해요. 그리고 여기서는 특이하게 교착 상태가 아닌 프로세스를 찾아 마크하는데 자세히 한 번 알아볼까요?

1. 할당 행렬에서 행의 값이 모두 0인 프로세스를 마크해요. (아무것도 할당받지 않은 프로세스 = 자원이 없으므로 교착 상태를 유발하지 않는 프로세스를 체크해요.)

2. 임시 벡터 W를 만들어요. 그리고 현재 가용 벡터의 값을 벡터 W의 초깃값으로 설정해요.(가용 벡터의 temp변수)

3. 표시되지 않은 프로세스 중 요청 행렬 Q의 특정 행의 값이 모두 W보다 작은(현재 가용 자원으로 종료시킬 수 있는) 프로세스를 찾고 그 프로세스를 마크해요. 만약 없으면 알고리즘을 종료시켜요.

4. 3에서 발견한 행의 할당 행렬의 값으로 W를 갱신해요.(발견한 프로세스에게 자원을 줘서 완료시켰다고 가정해요.) 그리고 3으로 돌아가요.

위 그림에서 알고리즘을 실행하면 P1과 P2가 마크되지 않으므로 이 둘이 교착 상태가 나올 것을 알 수 있어요.

 

교착 상태 회복 알고리즘

 위의 방법으로 교착 상태를 발견하면 어떻게든 해결해야겠죠?

1. 교착 상태에 포함된 모든 프로세스를 중지시켜요. 많은 운영체제에서 사용하고 있는 방법이죠.

2. 교착 상태에 포함된 프로세스의 수행을 롤백시켜요. 그러니까 특정 체크포인트까지 되돌리고 다시 수행해요.

3. 교착 상태가 없어질 때까지 교착 상태에 있는 프로세스를 하나씩 종료시켜요. 종료시킬 프로세스는 비용이 적은 것으로 해야 하는데 그 기준은 다음과 같아요.

• 지금까지 사용한 CPU time이 적은 프로세스부터(재시작하면 다시 CPU를 사용해야 하니까)
• 지금까지 생산한 출력량이 적은 프로세스부터(재시작하면 다시 출력해야 하니까)
• 수행 완료까지 걸릴 시간이 긴 프로세스부터
• 할당받은 자원이 적은 프로세스부터(많으면 다시 다 할당해줘야 하니까)
• 우선순위가 낮은 프로세스부터

4. 교착 상태가 없어질 때까지 교착 상태에 포함된 자원을 하나씩 선점시켜요. 희생될 프로세스는 3처럼 비용이 적은 자원부터 선택해요. 그 후 교착 상태 발견 알고리즘을 수행시켜 다시 파악해요. 자원을 선점당한 프로세스는 자원을 할당받기 전으로 롤백시켜요.