[운영체제] 120406 챕터5. 교착상태와 기아상태

*교착상태(Deadlock)의 개념
 1. 시스템 측면에서 자원의 요구가 뒤엉킨 상태. ex> 교통 마비
  1) 한 프로세스 집합 내의 프로세스들에 의해 발생한 사건(event)을 프로세스들이 서로 기다리고 있는 상태.
  2) 둘 이상의 작업이 보류 상태에 놓여 중요한 자원을 이용하기 위해 기다릴 때 발생함.
  3) 제한된 자원 이용률을 높이고 시스템 효율성을 증가시키기 위해 사용하는 병행 처리 기술과 자원에 따른 부작용임.

 2. 초기 일괄처리 시스템
  1) 사용자들이 작업 제어카드에 작업을 완료하기 위해 필요한 자원을 명시하여 교착상태가 자주 발생하지 않음.
  2) 운영체제가 요청한 자원이 준비 큐로 이동하기 전 사용 가능 여부를 확인하여 할당.
  3) 자원이 확보되지 않으면 작업이 준비 큐로 이동할 수 없어 교착상태가 발생하지 않음.

 3. 대화식 시스템
  1) 동작 자원 공유로 자원의 이용도를 높이는 과정에서 교착상태 발생
  2) 예1: DVD 드라이브와 프린트가 각각 하나씩 존재하고 다음과 같은 경우
   - 프로세스P : DVD드라이브 점유 -> 프린터 요청
   - 프로세스Q : 프린터 점유 -> DVD드라이브 요청
  3) 예2: 테이프 드라이브가 3개 존재하고 다음과 같은 경우.
   - 프로세스P : 테이프 드라이브 점유 -> 또 다른 테이프 드라이브 요청
   - 프로세스Q : 테이프 드라이브 점유 -> 또 다른 테이프 드라이브 요청
   - 프로세스R : 테이프 드라이브 점유 -> 또 다른 테이프 드라이브 요청

 4. 프로세스는 다음 순서로 자원을 이용
  1) 요청
   - 프로세스가 필요한 자원을 요청함.
   - 요청이 즉시 받아들여지지 않으면 다른 프로세스가 사용 중이므로 할당 받을 때까지 대기.
  2) 사용
   - 프로세스가 요청한 자원을 사용.
  3) 해제
   - 프로세스가 자원 사용을 마친 후, 할당 받은 자원을 되돌려 줌.
  4) 자원의 요청과 해제 그리고 파일이나 입출력 장치를 일걱나 쓰는 자원의 사용도 시스템 호출에 의해 이루어짐
  5)

*교착상태 발생
 1. 파일을 요청할 때의 교착상태
  1) 파일을 이용해 작업이 실행되는 동안, 파일에 대한 다른 작업의 점유 요청이 인정되면 교착상태 발생
  2) 파일 요청 시 발생하는 교착상태의 예.
   - 두개의 프로세스(판매,재고)와 두개의 파일(공급자 파일, 재고파일) 자원을 이용한 교착상태 표현.
   - 할당 요구 순서는 아래와 같음. -> 사이클 형태 -> 교착상태 발생
    ㄱ. 프로세스1(판매)은 판매 계획을 위해 공급자 파일을 요청해서 얻는다(할당).
    ㄴ. 프로세스2(재고)는 재고 확인을 위해 재고 파일을 요청해서 얻는다.(할당).
    ㄷ. 프로세스 1은 주문 요청한 판매를 위해 재고 파일을 요청하지만 허용되지 않는다.
    ㄹ. 프로세스 2는 주문을 위해 공급자 파일을 요청하지만 허용되지 않는다.     

 2. 전용장치를 할당할 때 의 교착상태
  1) 교착상태의 예
   - 두 사용자(프로세스 1, 프로세스2)가 각각 테이프 드라이브 한 대를 사용하고, 한 테이프에서 다른 테이프로 복사하는 작업을 할 경우.
   - 할당 요구 순서는 다음과 같이 이루어진다 가정.

 3. 스풀링 시스템에서의 교착상태
  1) 

 4. 디스크를 공유할 때의 교착상태 
  1)

 5. 네트워크에서의 교착상태
  1)

 6. 교착상태 발생 조건
  1) 다음 네 가지 조건이 동시에 발생할 때, 즉 필요충분조건이 성립될 때 발생.
   - 상호배제
    ㄱ.
   - 점유와 대기
    ㄱ.
   - 비선점
    ㄱ.
--------> 위의 세 가지 조건으로 발생할 수 있으나, 발생하지 않을 수도 있으며, 교착상태 발생에는 반드시 아래의 조건이 요구됨.
   - 순환대기
    ㄱ.

 7. 강 건너기 교착상태의 예
  1) 여러 개의 돌로 된 징검다리가 있는 강을 건너는 경우.

* 자원 할당 그래프를 이용한 교착상태 표현
 1. 방향 그래프인 시스템 자원 할당 그래프를 이용하여 교착상태 기술
   1)

* 교착상태 해결 기법
 1. 예방(방지)하는 것.
 2. 가능한 교착상태 직전에 회피
 3. 교착상태를 허용하되 교착상태에서 다시 회복할수 있게 함.
  1) 사용하기 어렵고 오버헤드가 증가함

1* 교착상태 예방 기법
 1. 4가지 교착상태 조건 중 하나라도 발생하지지 않도록 함.
  1) 상호배제 문제는 무조건 고려해야 함 -> 운영체제 차원에서 필요
   - 전용자원에서는 교착상태가 발생하지 않으므로 프로세스가 원하는 자원을 배타적으로 사용하려는 것은 제외시켜야 함.

 2. 하벤더가 상호배제를 제외한 세 가지 기본 방법 제안
  1) 각 프로세스는 한 번에 필요한 모든 자원을 요구해야 하며, 요청한 자원을 모두 제공받기 전까지는 작업을 진행할 수 없음.
  2) 어떤 자원을 점유하고 있는 프로세스의 요구가 더 이상 허용되지 않으면 점유한 자원을 모두 반납하고 필요할 때 다시 자원을 요구해야 함.
  3) 모든 프로세스에 자원을 순서대로 할당해야 함. 모든 프로세스에 각 자원 유형별로 할당 순서를 부여한 후 , 순서에 따라 자원을 요구.

 3. 상호배제 조건 방지
  1) 상호배제 조건은 자원의 비공유를 전제로 함.
   -
  2) 일반적으로 상호배제 조건을 거부하면 교착상태를 예방하는 것이 불가능함.
   -
  3) 파일쓰기는 배타적인 접근만이 허용되어야 함.
   -

 4. 점유와 대기 조건 방지
  1) 최대 자원 할당
   -
   -
  2) 점유와 대기 조건 방지를 위한 두가지 방법.
   -
   -
    ㄱ.
    ㄴ.
  3) 단점
   - 자원의 효율성이 낮음
    ㄱ.
   - 기아상태 발생이 가능함
    ㄱ.
    ㄴ.

 5. 비선점 조건 방지
  1) 이미 할당된 자원에 대한 선점권이 없어야 한다는 전제 조건을 가짐. (다른 쪽에서 자원을 빼앗아 갈수 있도록 해야함)
   -
   -
   -
  2) 두 가지 대안이 제시됨
   -

 6. 순환대기 조건 방지
  1) 계층적 요구 기법
   -
   -
   -
  2) R={R1,R2,R3,...}을 자원 형태 집합이라 가정, 각 자원 형태에 고유 숫자를 부여.
  3) 1:1 함수인 'F:R->N' 으로 정의 가능하며, N은 자연수 집합을 의미함.
   -
   -
   -
  4) 계층적 요구의 단점
   -
   -

 2*교착상태 회피 기법
  -
  -
 1) 회피 기법은 크게 두가지 방법 제시 됨.
  - 프로세스의 시작 거부
   ㄱ.
  - 자원 할당의 거부
   ㄱ.
   ㄴ. 일반적으로 은행가 알고리즘 이라 부름.
  - 교착상태 회피를 위해 자원이 언제 요구되는지에 대한 추가정보가 필요함
   ㄱ.
  - 요구를 받아들일 지 또는 기다리게 할 지를 결정하기 위해 각 프로세스에 대한 요구와 해제를 미리 알고 있어야함.
   ㄱ.
   ㄴ.
 2) 안정상태와 불안정상태
  - 교착상태 회피 알고리즘은 시스템이 순환-대기 조건이 발생하지 않도록 자원 할당 상태를 검사함
  -
  - 안정한 상태
   ㄱ.
   ㄴ.
   ㄷ.
   ㄹ.
  - 불안정한 상태
   ㄱ.
-----------> 교착상태는 불안정상태이나, 모든 불안정상태가 교착상태인 것은 아님.    -> 교착상태<불안정상태
 
 3* 시스템 상태 변화
  1.