교착상태, Deadlock

교착상태, Deadlock

• 어떤 집합 내 모든 프로세스들이 모두 Wait Queue에서 빠져나가지 못하는 상태
• 다시 말해, 모두 대기하고 CPU를 할당받지 않음

시스템 모델 System Model

• 시스템은 경쟁하는 스레드들 사이에 분배돼야 할 유한한 수의 자원으로 구성
  • e.g. CPU가 4개면, 4개의 인스턴스를 가진다.
• Mutex, semaphore 또한 시스템 자원
• 프로세스의 자원 사용 순서
  • 1. 요청 : 스레드 -> 자원 요청 (자원을 받을 때까지 대기)
  • 2. 사용 : 자원에 대해 작업 수행
  • 3. 방출 : 스레드가 자원 방출

라이브락 Livelock

• 또 다른 형태의 라이브니스 장애
• 교착상태가 같은 스레드 집합 내부에서 같은 집합에 속한 다른 스레드에서만 발생하는 이벤트를 기다리며 봉쇄되는 반면, 라이브락은 스레드가 실패한 행동을 계속해서 시도할 때 발생

교착상태 특성 Dealock Characterization

• 필요조건 동시에 네가지가 발생하면 교착상태가 이뤄진다.
• 1. 상호 배제 : 하나으 ㅣ자원이 비굥유 모드로 점유
• 2. 점유하며 대기 : 하나의 자원을 점유한 채 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기
• 3. 비선점 : 자원을 선점할 수 없어야 함
• 4. 순환대기 : 자원들이 cyclic 하게 점유한 자원들을 대기해야 함

자원 할당 그래프

• deadlock을 쉽게 이해하기 위한 그래프
• T : Set of threads
• T = SEt of Resources
• T -> R : Thread가 Resource에 요청했다. (Request edge)
• R -> T : 할당 엣지 (assignment edge)

교착상태 예방

• 4가지 요인 중 적어도 하나만 발생하지 않게
• 1. 상호배제 : 공유 가능한 리소스 설정 (읽기 전용 파일)
• 2. 점유하며 대기 : 프로세스 작업을 수행하기 전에 필요한 자원을 모두 요청하고 획득, starvation 가능성 있음
• 3. 비선점 : 중간에 선점하면 기존에 사용중이던 프로세스가 작업 내용을 잃을 수 있음
• 4. 순환대기 : priority, 자원낭비의 가능성이 있음
• 현실적이지 않아 교착상태 회피를 사용

교착상태 회피

• 상태를 안전상태/불안전상태로 분류
• 안전상태를 유지할 수 있는 요청만을 수락, 불안전상태의 경우 추후 만족하는 상태로 바뀔 때까지 계속 거절
  • 안전상태 : 각 스레드에 resource를 할당해줄 수 있다는 것
  • 순서가 있다면 deadlock을 피할 수 있다.
  • 안전순서를 찾을 수 있다면 시스템은 안전하다.
• 만약 가능한 미래의 deadlock이 있다면 대기
• 추가적 정보 필요
  • 현재 점유량 : 현재 프로세스 별 할당 자원의 수
  • 최대 요구자원 : 프로세스 별 최대 자원의 요구
  • 현재 여유자원 : 사용 가능한 자원의 수
  • 필요량 : 프로세스 별 남아있는 자원의 수