01 교착상태의 개요

1-1 교착상태의 정의

교착상태: 무한 대기 상태

• 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더이상 진행하지 못하는 상태

교착상태와 아사현상 차이
둘다 리소스를 요청하는 프로세스가 오랫동안 지연된 상태

• 아사현상: 운영체제가 큐정책을 잘못 써 특정 프로세스가 무한정 지연되는 문제(무한히 밀림)(CPU 스케쥴링)
  우선순위가 높은 프로세스가 우선순위가 낮은 프로세스가 요구하는 리소스를 지속적으로 사용
  해결- 에이징, HRN 스케쥴링
• 교착상태: 서로 상대방의 결과물을 기다리는 상태

1-2 교착 상태의 발생

다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
공유 변수를 사용할 때 발생

1-3 자원 할당 그래프

자원할당 그래프: 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지
프로세스) 원, 자원) 사각형, 할당 받음) 실선 화살표, 기다림) 점선 화살표
다중 자원) 여러 프로세스가 하나의 자원을 동시에 사용하는 경우, 수용 가능 프로세스 수를 사각형 안에 작은 동그라미로

02 교착상태 필요조건

4가지 중 하나라도 만족하지 않으면 교착상태 발생X
상호 배제
특징)사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적 자원

비선점
특징)사용중인 자원은 빼앗을 수 없는 비선점 자원

점유와 대기
행위)자원을 할당 받은 상태에서 다른 자원을 기다리는 상태

원형 대기
행위)점유와 대기 -> 원형 관계(사이클)

03 교착상태 해결방법

3-1 예방

4가지 필요조건이 발생하지 않도록

1. 상호배제
   독점적으로 사용할 수 있는 자원 제거
   현실적으로 어려움

2. 비선점
   모든 자원을 빼앗을 수 있도록
   아사현상을 일으킴, 무력화 하기 어려움

3. 점유와 대기
   전부 할당하거나 아니면 아예 할당하지 않는 방식
   이미 자원을 할당 받았으면 다른 자원을 기다리지 X
   단점
   - 프로세스가 자신이 사용하는 자원을 자세히 알기 어려움
   - 자원 활용 떨어짐
   - 많은 자원을 사용하는 프로세스가 불리함
   - 결국 일괄 작업 방식으로 동작
   
   

4. 원형 대기
   모든 자원에 숫자 부여, 오름차순으로만 자원 할당
   프로세스 P2는 자원을 할당 받을 수 없어 강제 종료되고 프로세스 P1은 정상적으로 실행
   
   단점
   - 프로세스 작업 유연성 떨어짐
   - 자원 번호 어떻게 부여?

교착상태 예방 정리
상호 배체, 비선점 -> 자원을 보호하기 위해 예방 어렵
점유와 대기, 원형 대기 -> 프로세스 작업 방식 제한, 자원 낭비. 사용할 수 없음

3-2 회피

자원 할당량 조절(포크 개수 조절)
교착 상태가 발생하지 않는 범위 내에서만 자원 할당
발생 범위-> 프로세스 대기

안정상태와 불안정상태
할당된 자원 적음 -> 안정, 할당 자원 많음 -> 불안정
불안정 상태가 커질수록 교착 상태가 발생할 가능성 증가

은행원 알고리즘

대출금이 대출 가능 범위 내(안정 상태)이면 대출해주지만 아니면 거부
기대 자원 <= 가용 자원 -> 할당해줌

문제점
프로세스가 사용할 모든 자원을 미리 선언해야함
시스템 전체 자원 수가 고정적
자원 낭비

3-3 검출과 회복

일어나면 처리하자
검출- 자원할당 그래프를 모니터링
회복- 교착상태가 발생하면 교착상태 회복 단계 진행

검출

타임아웃
-일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
-가정: 교착 상태가 자주 발생하지 않을 것
-특별한 알고리즘이 없음(쉽게 구현가능)
-타임아웃 -> 프로세스 종료

• 데이터 베이스의 타임아웃
  데이터의 일관성 깨질 수 있음
  해결법
  • 체크포인트 : 저장 상태로 돌아오기 위한 표시
  • 롤백 : 과거의 체크포인트로

자원 할당 그래프
단일 자원 사용, 자원할당 그래프에 사이클이 있으면 교착상태

회복

교착상태를 유발한 프로세스 강제 종료
1. 교착상태 일으긴 모든 프로세스 동시에 종료
2. 교착상태 일으킨 프로세스 중 하나를 골라 순서대로 종료

• 우선순위 낮은 순
• 작업시간이 짧은 순
• 자원을 많이 사용하는 순

04 다중자원과 교착 상태 검출

다중 자원과 사이클

• 다중 자원이 포함된 자원 할당 그래프 -> 사이클 찾기(대기 그래프, 그래프 감소 방법)
• 그래프 감소: 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지우는 작업

대기 그래프와 그래프 감소
그래프 감소 결과 사이클X => 교착 상태 발생 X

그래프 감소 결과 사이클 => 교착 상태