교착상태 예방

• 교착상태를 예방하는 전략
  - 운영체제를 설계할 때 교착상태가 발생할 가능성을 없애기
• 직접적인 방법
  - 환형대기를 허용하지 않는 것
• 간접적인 방법
  - 조건 1~3(상호 배제, 점유대기, 비선점 조건)중에 하나를 허용하지 않는 것

간접적인 방법 - 조건별 방법

조건1. 상호 배제

• 시스템 설계에서 상호 배제 조건을 없앨 수는 없지만 공유 자원의 일관성을 위해 반드시 필요함
  => 운영체제의 지원 필요
• 다수의 읽기 접근은 허용되지만 쓰기 접근은 한 시점에 하나만 배타적으로 허용

조건2. 점유대기

• 프로세스는 자신이 사용할 모든 자원을 한 순간에 요청
  => 비효율적임
  - 자원 흭득까지 오랜 시간 기다릴 수 있음
  - 나중에 사용하는 자원을 오랜 시간 점유 -> 실제 수행이 끝날 때쯤에 사용될 수 있으므로
  - 프로세스가 미래에 사용될 모든 자원을 미리 알기 어려움

비선점

• 자원을 점유한 프로세스가 다른 자원 할당 불가 시 점유 자원 반납
• 다른 프로세스가 점유한 자원을 강제로 반납시키고 점유
  - 우선순위가 있을 때 적용 가능
• Database transaction(원자적 연산)
  - 중간에 끊겨도 온전히 실행되거나 모두 실행되지 않게 하여 정보의 유지 보장

환형대기 예방

• 자원들의 할당 순서를 정하면 없앨 수 있음
• 실제로는 연산이 오래 걸려 쓸 수 없음
• 운영체제의 자원 할당 순서에 위배되기 때문에 나타날 수 없음

교착상태 회피

• 교착상태 발생 조건 1~3(상호 배제, 점유대기, 비선점 조건) 허용 + 예방처럼 자원 할당 순서를 미리 정하지 않음
• 자원을 할당할 때 교착 상태가 발견 가능한 상황으로 진행하지 않도록 교려
  => 병행성의 더 많은 제공
• 할당 전에 이 할당이 교착 상태를 발생시킬 가능성이 있는지 동적 검사
• 교착상태 예방은 비효율적
  - 현재 자원의 가용 개수와 프로세스 자원 요구량을 미리 알고 있어야 가능
  => 현실적으로 불가능
• 교착상태 회피 방법
  - 프로세스가 시작하려 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있을 경우 프로세스를 시작시키지 않음
  - 수행 중인 프로세스가 요구하는 추가적인 자원 할당의 교착상태의 발생 가능성이 있으면, 자원을 할당하지 않는다
  

교착상태 회피 - 프로세스 시작 거부

• 벡터와 행렬을 정의한 뒤 이에 대해 회피 방법 논의

$R_j = V_j + \sum_{i=1}^{n} A_{ij}$ (모든 j에 대해) R은 모든 자원, V는 가용자원, 시그마 안 할당 열에 대해 전체 더한값	모든 자원은 가용 가능하거나 할당되어 있다(이 식은 가용 자원과 할당된 자원의 합이 결국 그 자원의 전체 개수와 동일함을 의미)
$C_{ij} <= R_j$ (모든 i,j에 대해) C는 요구 R은 자원	프로세스는 자원의 전체 개수보다 더 많은 개수의 자원을 요구할 수 없다.
$A_{ij} <= C_{ij}$ (모든 i,j에 대해) A는 할당 C는 요구	프로세스는 자신이 요구한 자원보다 더 많은 개수의 자원을 할당할 수 없다.

• 모든 프로세스들이 요구한 자원의 개수가 전체 자원 개수보다 적으면 교착상태가 발생하지 않음
• $R_j >= C_{(n+1)j} + \sum_{i=1}^n C_{ij}$
  - $\sum_{i=1}^n C_{ij}$ = 현재 존재하는 모든 프로세스들이 요구하는 자원의 개수
  - $C_{(n+1)j}$ = 새로 수행하려는 프로세스가 유행
• 모든 프로세스들이 동시에 최대 자원을 요구하여 사용함을 가정하고 있어 효율적이지 않음

교착상태 회피 - 자원 할당 거부

- 은행원 알고리즘(banker's algorithm) - 상태(state)와 안전한 상태(safe state) - 상태 => 프로세스들이 자원을 요구하고 할당받은 관계 - 안전한 상태 => 교착상태가 발생하지 프로세스에게 자원을 할당할 수 있는 진행 경로가 존재함 - 불안전한 상태 => 그러한 진행 경로가 없는 상태 #### (a) 초기상태

자원벡터 R	전체 자원의 개수
가용벡터 V	프로세서들의 자원에서 각각 사용하고 남은 자원
요구(C) - 할당(A)	해당 프로세스를 종료(완료)하는데 필요한 자원의 개수

• P1의 경우 => R1 자원 부족(가용벡터 0개), R2 자원 부족(가용 벡터 1개), R3 자원 부족(가용 벡터 1개)
• P2의 경우 => R3만 1개의 자원이 필요한데 가용 벡터에도 R3가 하나 있기 떄문에 종료가 가능
• P3의 경우 => R1 자원 부족(가용벡터 0개), R3 자원 부족(가용 벡터 1개)
• P4의 경우 => R1 자원 부족(가용벡터 0개), R2 자원 부족(가용 벡터 1개)
• 결과
  - P2 프로세스만 완료 수행이 가능한 상태 => P2 프로세스 완료

(b) P2 수행 완료

• P2 프로세스가 차지하고 있던 자원이 완료되자 다시 반환됨
• P1, P3, P4 모두 수행 완료가 가능한 상태
• 그 중에서 가장 가까운 P1이 수행 완료됨
• P1이 종료하는데 요구하는 자원의 양이 다 많기 때문에 P1 프로세스 완료

(c) P1수행완료

• P1이 수행 완료되고 다시 자원이 반환됨
• P1, P2는 모두 수행 완료되어 차지하고 있는 자원이 없는 상태
• P3이 종료하는데 필요한 조건을 만족하여 수행 완료

(d) P3 수행 완료

• P1, P2, P3가 모두 종료하고 P4만 남은 경우
• P4만 남아서 조건을 체크 -> 수행 완료가 가능한 조건을 가지고 있어 해당 프로세스 완료