1학년 1학기 기말고사 컴퓨터 시스템 일반 - 교착 상태

교착상태

두 개 이상의 작업이 다음에 진행되어야 할 작업과 맞물려 서로가 끝나기만을 기다리기 때문에 아무것도 완료하지 못하는 상태
다중프로그래밍 시스템에서, 한 프로세스가 자원을 요청할 때 그 자원을 사용할 수 없으면 프로세스가 대기상태로 들어감

이 처럼 대기 중인 프로세스가 원하는 자원이 모두 다른 프로세스에게 점유되어 있고, 그들도 모두 대기상태여서 상태 변경이 불가능할 때 교착상태가 발생한다.

프로세스의 자원 이용 순서

요청

프로세스가 필요한 자원을 요청

요청이 즉시 수락되지 않으면 할당 받을 때까지 대기
사용

프로세스가 요청한 자원을 사용
방출

프로세스가 자원 사용을 마친 후 할당받은 자원을 되돌려줌

교착상태 발생 원인

상호배제

한 번에 한 프로세스만 자원 이용 가능
점유/대기

프로세스가 할당된 자원을 점유한 상태에서 다른 자원 대기
비선점

프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없음
순환대기

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원 점유

4가지 조건 모두 만족 시 교착상태 발생

자원 할당 그래프

프로세스 Pi : 원
자원 Rj : 사각형
자원의 인스턴스 : 점
그래프가 사이클을 포함하지 않음 : 교착상태x
그래프가 사이클 포함 & 인스턴스 하나씩 : 교착상태o
그래프가 사이클 포함 & 인스턴스 여러개 : 교착상태 o/x

교착상태의 관리

교착상태의 예방

교착상태 발생 가능성을 사전에 모두 제거

교착상태 4가지 조건 중 하나를 부정
교착생태의 회피

프로세스가 요구하고 사용할 자원에 대한 부가 정보 미리 제공

발생 가능성 인정 & 교착 상태가 발생 하려고 할 때 회피
교착상태의 발견

일단 교착상태 발생을 혀용하고, 발생 시 그와 관련된 프로세스와 자원을 조사 후 결정
교착상태의 회복

시스템으로부터 교착상태를 제거하여 이후로는 교착상태에 빠지지 않도록 함

보통 교착상태에 빠진 프로세스 제거
리눅스/윈도우 등의 운영체제는 문제를 무시하고 교착상태가 발생하지 않은 척 함(비용 적게 소모)

교착상태의 예방(사전 조치)

교착상태의 4가지 조건 중 최소한 하나가 성립하지 않도록 보장
상호 배제의 부정 : 적어도 하나의 자원은 공유가 불가능해야 함을 부정(공유 허용)
- 자원의 비공유를 전제 -> 공유 가능한 자원에는 해당 없음(읽기 전용 파일)
점유와 대기(Hold&Wait)의 부정
- 프로세스가 실행되기 전에 각 프로세스가 요청하는 모든 자원을 한번에 할당(wait 부정)
- 프로세스가 자원을 갖고 있지 않을 때만 자원 요청 가능(hold부정)
- 추가 자원 요청 시 자신이 갖고 있는 모든 자원 반납(hold부정)
- 많은 자원들이 할당되어 오랫동안 사용되지 않으면 자원 낭비(기아상태)
비선점 조건의 부정 : 이미 할당된 자원이 선점되지 않아야 한다는 것을 부정(선점 허용)
- 자원을 점유하고 있는 프로세스가 즉시 할당 불가능한 다른 자원 요청 시, 현재 점유중인 모든 자원 반납 후 필요할 때 다시 요구
- 프로세스가 자원 반납 시 현 시점까지 수행한 작업이 취소될 수 있음
- 요구하는 자원을 다른 프로세스가 사용 시 무기한 연기 발생
순환 대기의 부정
- 모든 프로세스에게 각 자원의 유형별로 순서 배정
  -> 현재 가지고 있는 자원보다 더 큰 번호를 가진 자원만 요청하도록 제한
- 실제 프로세스가 실행 중에 자원 사용 순서를 반영해야 함
- 새로운 자원 추가 시 순서 재구성
- 급한 프로그램 발생 시 자원할당 어려움
교착상태 예방 방법은 장치 이용률 저하, 시스템 처리율 감소

교착상태의 회피(안전상태 유지, 위험 인지하고 조치)

각 프로세스가 필요한 자원마다 최대수를 선언하고 교착상태가 발생하지 않도록 함
안전 상태와 불안전 상태
- 안전/불안전을 파악하여 프로세스의 자원 요청 즉시 할당/대기 여부 결정
- 안전(safe) 상태
  - 모든 작업이 완료될 수 있는 상태
  - 시스템이 순서대로 각 프로세스에 자원 할당 가능
  - 교착상태 방지 가능
- 불안전 상태
  - 결국에는 교착상태가 발생할 수 있는 상태
교착 상태 회피 알고리즘 : 자원할당 그래프 알고리즘, 은행원 알고리즘

교착상태의 발견

자원 할당 그래프의 소거

교착상태의 회복

프로세스 중지
- 교착 상태의 프로세스를 모두 중지
  - 확실하지만 비용 많이 듬
- 교착 상태가 해결될 때 까지 한 프로세스씩 중지
  - 매번 교착 상태 발견 알고리즘을 호출해야 하므로 부담 큼
- 중지할 프로세스 선택
  - 여러 기준을 토대로 중지할 프로세스를 선택
  - 사용한 자원의 유형과 수, 더 필요한 자원의 수 등등
자원 선점
- 희생자 선택
  - 어느 자원과 프로세스들이 선점될 것인가?(실행 시간, 점유 자원 수)
- 복귀
  - 프로세스로부터 자원 선점 뒤, 해당 프로세스를 안전 상태로 복귀 후 재시작
  - 어느 시점으로 복귀할 지 생각해야 함
- 기아 상태
  - 자원이 동일한 프로세스로부터 항산 선점되지 않도록 희생자 반복 선택의 상한선을 정할 필요가 있음

은행원 알고리즘

안전 알고리즘

let available : 사용 가능한 자원의 수
let allocation[] : 현재 각 프로세스에 할당되어 있는 자원의 수
let max[] : 각 프로세스의 최대 자원 요구 수
let need[] : 각 프로세스에 남아 있는 자원 요구 수
  need[i] = max[i] - allocation[i]

int work = available;
bool finish[] = {0};
bool isFinish = false;

while(!isFinish){
  for(int i=1; i<=n; i++){
    if(!finish[i] && need[i]<=work){
      work += allocation[i];
      finish[i] = true;
    }
  }
  bool flag = true;
  for(int i=1; i<=n; i++){
    if(!finish[i]) flag = false;
    if(need[i]<=work) flag = false;
  }
  isFinish = flag;
}

bool isSafe = true;
for(int i=1; i<=n; i++){
  if(!finish[i]) isSafe = false;
}
if(isSafe) printf("안전");
else printf("불안전");

자원 요청 알고리즘

let available : 사용 가능한 자원의 수
let allocation[] : 현재 각 프로세스에 할당되어 있는 자원의 수
let max[] : 각 프로세스의 최대 자원 요구 수
let need[] : 각 프로세스에 남아 있는 자원 요구 수
  need[i] = max[i] - allocation[i]
let request[] : 프로세스의 자원 추가 요구량

...
if(request[i] > need[i]) return "error";
if(requese[i] > available) return "wait";
available -= request[i];
allocation[i] += request[i];
need[i] -= request[i];
if(safe) return "pass";
else return "fail";
...