[컴퓨터 시스템] 교착상태(deadlock)와 기아상태(starvation)

교착상태(deadlock)

2개 이상의 스레드 혹은 프로세스가 서로 상대방의 작업이 종료되기 만을 기다리는 상태. 즉, 절대로 참이 될 수 없는 조건을 기다리면서 정지되어있는 경우를 말한다.

1. 상호 배제 : 공유 자원에 대해 배타적인 접근권을 요구한다.

2. 점유 대기 : 프로세스 혹은 스레드가 할당된 자원을 점유한 채 다른 자원을 기다린다

3. 비선점 : 프로세스 혹은 스레드가 할당된 자원의 사용을 끝낼 때까지 다른 작업이 그 자원을 차지할 수 없다.

4. 순환 대기 : 각 프로세스 혹은 스레드가 순환적으로 다음 프로세스 혹은 스레드가 요구하는 자원을 가지고 있다.

 

이에 대한 쉬운 예시가 '식사하는 철학자 문제' 이다

다섯 명의 철학자들이 원탁에 둘러앉아 각각 하나의 젓가락을 가지고 있는 상태이므로 어느 누구도 젓가락 두 짝을 가지고 스파게티를 먹을 수 없다. 이러한 상태가 위 4개의 조건을 만족하는 교착상태(deadlock)이다. ㅎ.. 갑자기 시험에 여기 앉아있는 사람들이 어떤 직업을 가지고 있는지 4지선다형 문제로 final에 내셨던 멕케나 교수님이 생각나네..

⁕ 여러 작업들이 동일한 자원을 필요로하여 생기는 현상

 

 

기아상태(starvation)

특정 스레드 혹은 프로세스의 우선순위가 낮아서 자원을 계속 할당받지 못하는 상태이다. 대표적으로 reader-writer 문제가 있다. 온라인 항공 예약 시스템의 경우에는 자리를 확인하려는고객(reader)과 예약을 하려는 고객(writer)이 동시적으로 서비스를 요청할 수 있다. 따라서 데이터의 무결성을 지키기 위해 reader와 writer에 우선순위를 두게된다. 가령 reader 요청이 들어 올 때에는 다수의 reader 요청만 허용하고 writer 요청은 대기 상태에 있어야하는 우선순위 조건을 만들게되면, writer 요청이 기아 상태로 이어질 가능성이 있다. 반대로 writer 요청이 우선순위가 높아지게되면 reader 요청이 기아 상태가 될 수 있다.

 

이를 위해서는 세마포어로 공유 자원을 스케줄링 해주어야한다.

writer 요청의 경우에는 뮤텍스로 임계 영역(critical section)에 최대 한 개의 writer 작업만 존재하도록 보장해주고, reader 요청이 임계 영역으로 들어가게되면 오직 다수의 reader 요청들만 임계 영역에 접근할 수 있게 보장해주어야한다. 이를 위해서는 맨 처음 임계 영역(critical section)에 들어가는 reader 작업이 writer 요청을 잠그고, 가장 마지막 reader 요청이 writer 요청을 풀어주는 작업(reader가 writer 뮤텍스를 소유)이 필요하다.

 

general한 기아상태의 대안은 프로세스의 우선순위를 일정시간마다 바꿔주거나, 요청순서대로 처리하는 FIFO 방식을 사용하는 방식이다.

 

⁕ 여러 작업들이 부족한 자원을 놓고 경쟁하는 현상

 

 

임계 영역(critical section)
여러 작업이 공통으로 사용하는 데이터를 업데이트 하는 영역

 

뮤텍스를 소유하다
뮤텍스를 잠겄지만 아직 열지 못한 쓰레드는 뮤텍스를 소유하고 있는 상태이다. 위의 reader-writer 예시에서 reader 스레드가 처음 임계영역에 진입할 경우 writer 뮤텍스를 잠그게(lock) 되고 일정 시간동안 reader 스레드들만 임계영역에 들어갈 수 있게끔 writer 뮤텍스를 소유하게된다. 그리고 마지막 reader 스레드가 writer 뮤텍스를 다시 열어(unlock) writer 스레드에게 다시 제어권을 줄 수 있다. ('컴퓨터 시스템' 970페이지 '읽기-쓰기 문제' 참고)