[OS] 6. 교착상태와 무기한 연기

4/10, 4/13

 

Part 1.

교착상태(deadlock): 프로세스나 쓰레드가 아무리 기다려도 일어날 수 없는 사건을 대기하는 상태

 

자원 경쟁 교착상태

• 독점 자원에 대한 경쟁에서 교착상태 발생. 환형 대기(또는 순환대기)가 있을 때 발생.
• 어느 프로세스도 보유 자원을 포기하려고 하지 않은 상황의 환형 대기
• 자원할당 그래프에 의한 표현(노드와 엣지로 표현)

스풀링 시스템[1]의 교착상태

• 스풀 파일 공간이 도중에 차버리는 경우
• 충분히 공간을 확보하거나, 일정 임계치를 넘지 못하게 강제, 전부 차기 전에 프린팅 등.

 

자원(resource)

• 선점자원
  • 손실없이 프로세스로부터 회수 가능
  • 프로세서 메인메모리 등
• 비선점자원
  • 회수시 손실이 발생가능한 자원
  • 프린터, 스캐너 등
• 공유가능자원
  • 재 진입코드
  • 사용중 변경 X, 여러 프로세스에 의해 공유 가능
• 공유불가자원
  • 순차적 재 사용가능 코드
  • 한번에 한 프로세스만 사용 가능
  • local & static

 

무기한 연기(indefinite postponement)

• 프로세스가 자원을 사용할 수 있지만, 자원할당스케줄링 정책 때문에 대기하는 상황
• 운영체제의 편중된 자원할당정책 때문에 발생
• ex) 식사하는  철학자 문제
  • 생각하거나/먹거나
  • 배가 고프면 젓가락 2개 집어서 식사
  • 한번에 한 사람이 사용
  • 근데 5개임.ㅋ
  • 제약조건) 기아 상태에 빠지지 않아야함.(교착 배제, 무기한 연기 배제
  • 제약조건) 상호 배제 강제(동시에 같은 젓가락 사용 불가)
  • eat() 구현시) 상호배제, 교착상태, 무기한 연기 고려

교착상태 발생의 4가지 필요조건

• 상호배제
• 점유와 대기
• 비선점
• 환형대기(순환대기)

교착상태 처리 방법

• 예방(prevention)
  • 발생 가능성을 사전 제거
  • 상호배제를 제외하고는 배제 가능.
  • 점유와 대기 배제
    • 필요한 자원 한꺼번에 요청/전부 할당하거나, 전혀 할당하지 않거나
    • 자원 낭비 가능성, 비효율적 자원공유, 무기한 연기 발생 가능
  • 비선점 조건 배제
    • 추가 자원 요구가 거절되면 점유한 자원 반납->작업 손실 가능
    • 비용 및 시간 증가, 무기기한 연기 발생 가능
  • 환형 대기 조건 배제
    • 각 자원의 유형별 할당 순서 부여
    • 프로세스가 어떤 유형의 모든 자원을 받으면, 순서에 따라 나중에 위치하는 자원반 요구 가능
    • 가진 자원보다 큰 번호 자원만 요청 가능
    • 할당 융통성 부족, 순서와 부여된 번호가 다르면 미리 할당(자원 낭비), 새로운 자원 추가시 시스템 재구성 필요, 급한 프로세스에 대한 자원할당 어려움, 프로그래머가 순서를 고려해서 프로그래밍
• 회피(avoidance)
  • 적절히 피해가는 방법
  • 효율적 이용을 위해 덜 엄격한 제약
  • 패턴에 제약을 주는 미래의 프로세스 행위에 대한 지식에 의존
  • Dijkstra의 은행가 알고리즘(banker's algorithm)
    • 안전상태(모든 프로세스를 일정 시간내에 완료 가능)
    • 불안전상태(모든 프로세스 완료를 보장하지 못함=>교착상태 발생 가능)
    • 프로세스의 자원요청 및 반환 순서를 완전히 안다고 전제
    • 필요한 각 자원별 최대 개수 선언
    • 프로세스의 요청에 대해 허용/대기 여부 결정(if 할당해도 안전하면 할당. 그렇지 않으면 대기)
    • 개수 고정, 프로세스 집단 고정, 미리 최대 필요자원 개수 보고 필요, 유한한 시간내에 모든 자원 반환 가정.
    • 실제 적용 사례 적음
• 감지(detection)
  • 교착상태가 발생할 수 있는 시스템에 사용
  • 발생 여부 결정
  • 발생시 관련 프로세스 및 자원 식별
  • 감지 알고리즘은 상당한 시간 부담 초래
  • 자원 할당 그래프 사용
• 회복(recovery)
  • 교착상태를 벗어나게 하는 것
  • suspend/resume: 임시로 중단. 처리내용 손실 없음.
  • checkpoint/rollback: 체크포인트 이후는 손실 가능

 

자원-할당 그래프

• 사각형: 프로세스
• 큰 원: 동일 자원의 클래스
• 작은 원: 자원

그래프 축약

• 프로세스의 자원 요청이 수용될 수 있으면 그래프 축약(연결선 삭제)
• 모든 프로세스에 의해 축약되면 교착상태에서 자유
• 축약되지 않은 프로세스들이 교착

 

라이브락

• 교착상태와 유사하게 진행이 되지 않은 것.
• 그러나 라이브락에선 지속적으로 상태가 변화.(특정 루프를 반복)

 

---

[1] 속도가 다른 시스템(I/O 등)을 사용하기 위해 spool 공간에 데이터를 보내두고, 거기서 읽는 방식.