교착상태(Deadlock)란?

Ilhwanee·2022년 9월 17일
0

CS

목록 보기
18/27

Deadlock

교착상태란 멀티 프로그래밍 환경에서 나타날 수 있는 문제점이다.

프로세스1은 자원A가 필요한데, 이는 프로세스2가 사용 중이다.
또한 프로세스2는 자원B가 필요한데, 이는 프로세스1이 사용 중이다.

이러한 상황이라면 프로세스1은 자원A를 사용할 수 있을 때까지 자원B를 반환할 수 없으며, 프로세스2 또한 자원B를 사용할 수 있을 때까지 자원A를 반환할 수 없어 무한히 대기만 하는 현상이 발생하며 이 것이 데드락이라 한다.

교착상태의 발생 조건은 다음 4가지를 모두 만족하는 것이다.

  • 상호 배제(Mutual exclusion)
    • 하나의 자원은 하나의 프로세스만 점유할 수 있다.
  • 점유와 대기(Hold and wait)
    • 필요한 자원이 다른 프로세스가 점유 중이면, 자원을 점유 중인 채로 기다린다.
  • 비선점(No preemption)
    • 필요한 자원이 다른 프로세스가 점유 중이면, 빼앗지 않고 반환할 때까지 기다린다.
  • 환형 대기(Circular wait)
    • Hold and wait 관계인 프로세스들이 서로 기다린다.

그렇다면 교착상태는 어떻게 해결할 수 있을까?
해결 방법으로는 3가지 방법이 있다.

  • 방지
    • 앞서 4가지의 교착상태 발생 조건을 만족하지 않게 하는 것이다.
  • 회피
    • 교착상태 발생의 여지가 있는 자원을 할당하지 않는 것이다.
    • 알고리즘을 사용하여 회피할 수 있다.
  • 탐지 및 회복(Detection and Recovoery)
    • 교착상태가 발생하도록 내버려두고 발생한다면 찾아내어 고치는 것이다.

방지의 경우 4가지 조건을 망가뜨리면 또 다른 오류가 발생할 수 있다.
예를 들어 상호 배제를 만족하지 않으면 두 프로세스가 자원에 접근하여 동시성 문제가 발생할 수 있다.
그나마 조건을 깨는 것이 수월한 것이 환형 대기로, 서로 기다리는 환형에서 순차적으로 접근하는 선형 대기로 순서를 정해주는 것이다.

회피의 경우 대표적으로 은행원 알고리즘을 사용할 수 있다.
은행원 알고리즘이란 안전 상태와 불안전 상태로 나누고, 교착상태가 발생할 수 없는 안전 상태일때만 프로세스의 시스템콜을 받아들이고 교착상태가 발생할 수 있는 불안전 상태의 경우 요청을 거절하는 기법이다.
하지만 안전 상태에서만 자원을 할당하기 때문에 자원 사용률이 낮아져 성능이 저하된다는 단점이 있다.

탐지의 경우 각 자원마다 하나의 프로세스가 존재하면 Cycle을 이용한다. 자원 할당 그래프에서 자원을 제거하고 간선을 프로세스로 향하게 하면 Cycle 발생 여부를 확인할 수 있다.
각 자원마다 여러 프로세스가 존재하면 은행원 알고리즘을 사용할 수 있는데, 이는 회피에서 사용한 은행원 알고리즘과 다르다.
각 프로세스의 자원 요청 개수를 확인하여 불안정 상태가 존재하면 교착상태라고 판단하는 것이다.

교착상태가 탐지 되었다면, 프로세스 종료 혹은 자원 선점을 통하여 복구한다.

  • 프로세스 종료
    • 교착상태가 제거될 때까지 하나씩 프로세스 중지
    • 교착상태의 프로세스 모두 중지
  • 자원 선점
    • 교착상태에 있는 프로세스의 자원을 섬점하여 다른 프로세스에 할당
    • 가장 최소 피해를 주는 프로세스를 선점하는 희생자 선택을 고려해야 함
    • 선점된 프로세스를 문제 없던 상태로 되돌려야 하며(롤백) 보통 가장 안전한 방법은 중지 후 재시작
    • 한 프로세스가 계속 선점되면 자원을 계속 할당받지 못하는 기아상태 될 수 있음
    • 선점될 때마다 우선순위를 높여 해결


profile
블로그 이전 -> https://pppp0722.github.io

0개의 댓글