교착 상태(면접을 위한 CS 전공지식 노트)

교착 상태

교착 상태

교착상태(Deadlock)는 컴퓨터 과학 및 운영 체제 분야에서 중요한 개념 중 하나로, 

다중 프로세스 또는 스레드가 서로의 실행을 막고 무한 대기 상태에 빠지는 상황을 말합니다. 

이러한 상황에서는 시스템이 진행할 수 없게 되며, 

사용 가능한 리소스를 효과적으로 활용하지 못하게 됩니다. 

교착상태는 일반적으로 다음과 같은 네 가지 조건이 동시에 충족될 때 발생합니다.

 

상호 배제 (Mutual Exclusion): 

리소스는 한 번에 하나의 프로세스 또는 스레드만 사용할 수 있어야 합니다. 

즉, 어떤 프로세스가 리소스를 사용 중이면 다른 프로세스는 기다려야 합니다.

점유 및 대기 (Hold and Wait): 

프로세스가 최소한 하나의 리소스를 점유한 상태에서 다른 리소스를 기다립니다. 

이때, 다른 프로세스가 사용 중인 리소스를 점유하기 위해 대기합니다.

비선점 (No Preemption): 

프로세스가 자발적으로 리소스를 해제하지 않습니다. 

다른 프로세스가 점유 중인 리소스를 강제로 빼앗을 수 없습니다.

순환 대기 (Circular Wait): 

프로세스 집합에서 각 프로세스는 다음 프로세스가 필요로 하는 리소스를 점유하며 

순환 대기 상태를 형성합니다. 

즉, 순환적으로 리소스를 기다립니다.

교착상태가 발생하면 시스템은 더 이상 진행할 수 없으며, 특별한 조치 없이 무한히 대기하게 됩니다. 

따라서 교착상태를 해결하거나 미리 예방하기 위한 다양한 방법과 알고리즘이 개발되었습니다. 

 

교착 상태 해결 및 예방 방법

리소스 할당 그래프 (Resource Allocation Graph): 

시스템 내의 리소스와 프로세스 간의 상호 작용을 그래프로 표현하여 교착상태를 탐지하고 

해결하는 데 사용됩니다.

자원 할당 알고리즘: 

교착상태를 방지하기 위해 리소스 할당 시 특정 규칙을 따르도록 하는 알고리즘을 사용합니다.

대표적인 예로은 뱅커스 알고리즘(Banker's Algorithm)이 있습니다.

타임아웃 및 프로세스 중지: 

일정 시간 내에 교착상태가 해결되지 않으면 시스템은 특정 프로세스를 중지하거나 리소스 할당을 

해제하는 방법을 사용할 수 있습니다.

자원 재할당: 

교착상태가 발생하면 일부 프로세스의 리소스 할당을 취소하고 다시 할당함으로써 해결할 수 있습니다.

교착상태는 프로세스 동기화 및 리소스 관리에 관련된 복잡한 문제로, 

효과적인 해결책을 찾는 것이 중요합니다.

 

교착상태 자세히 알기!!

해성이는 학교에서 팀 프로젝트를 수행하고 있습니다. 

그리고 그의 팀원 중 한 명인 지연이가 교착상태를 만들고 있는 상황입니다.

상호 배제 (Mutual Exclusion): 

해성이와 지연이가 공통된 자료실에 들어가야 하는데, 자료실은 한 번에 한 사람만 들어갈 수 있습니다. 

해성이가 자료실에 들어가서 자료를 찾고 있을 때, 지연이는 기다려야 합니다.

점유 및 대기 (Hold and Wait): 

해성이가 자료실에서 자료를 찾고 나와서도 아직 작업을 마치지 않은 상태에서, 

다른 자료를 찾기 위해 또 다른 자료실에 들어가려고 합니다. 

이때, 지연이가 그 자료실에 들어가기 위해 기다리고 있습니다.

비선점 (No Preemption): 

해성이가 한 자료실을 사용 중일 때, 다른 사람이 강제로 자료실을 빼앗을 수 없습니다. 

자료실 사용 중인 해성이는 자료를 찾을 때까지 자리를 비울 수 없으며, 다른 자료실에도 들어갈 수 없습니다.

순환 대기 (Circular Wait): 

해성이와 지연이는 자료실에 접근하기 위해 서로를 기다리는 상황입니다. 

해성이는 한 자료실에서 자료를 찾고, 

그 자료를 사용하면서도 다른 자료를 찾기 위해 다른 자료실에 들어가야 하며, 

이때 지연이가 기다리고 있습니다. 

동시에 지연이도 자료실에 들어가려면 해성이의 작업이 끝나기를 기다려야 합니다. 

이런 식으로 두 사람은 서로를 기다리며 순환 대기 상태에 빠집니다.

이렇게 해성이와 지연이가 서로의 작업을 기다리며 더 이상 진행하지 못하는 상황이 교착상태의 예입니다. 

이런 상황에서는 학교나 시스템 내에서 교착상태를 해결하기 위한 추가적인 정책이나 알고리즘이 

필요하며, 자원을 효과적으로 관리하여 교착상태를 피하거나 해결할 수 있어야 합니다.

 

 

 

*바쁜 사람을 위한 깜찍한 정리

교착상태는 프로세스 또는 스레드가 서로의 실행을 막고 무한 대기 상태에 빠지는 상황을 말합니다. 교착상태는 상호 배제, 점유 및 대기, 비선점, 순환대기 조건이 동시에 충족될 때 발생하며 해결 및 예방법은 리소스를 그래프로 표현하여 교착상태를 탐지할 수 있으며 일정 시간 내에 교착상태가 해결되지 않으면 프로세스를 중지하거나 리소스 할당을 해제하는 방법 등이 있습니다.