[운영체제] 교착 상태

교착상태

• 2개 이상의 프로세스 필요
• 다른 프로세스 작업을 기다리느라 다른 작업을 진행하지 못하는 상태

아사현상과의 차이점

• 아사현상
  • 운영체제의 잘못된 정책으로 특정 프로세스가 지연되는 문제 (무한대기)
  • 특정 프로세스가 자원을 가져오지 못해 지연됨
• 교착상태
  • 여러 프로세스가 작업하다보니 자연발생적으로 일어남
  • 교착상태가 계속되면 아사현상이 됨
  • 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
  • 잠금을 사용해도 발생 (임계구역 접근)
  • 데이터베이스 응용 프로그램에서도 발생 (ex. 은행)

자원 할당 그래프

• 원 : 프로세스
• 사각형 : 자원
• 실선 : 할당
• 점선 :대기
• 점 : 자원의 수 (사각형 안의 점) → 다중 자원

식사하는 철학자 문제

• 모드 오른손 포크를 들음 → 모두 못먹음 → 교착상태
• 상호 배제가 필요 (기다리는 사람이 필요)
• 경쟁상황이 있어야 Dead Lock 발생

교착상태 발생 조건 : 모두 만족해야 발생

1. 상호 배제

• 다른 프로세스와 공유할 수 없는 자원

1. 비선점
   • 다른 프로세스가 사용중인 자원을 뺏을 수 없음 → 기다려야 함
2. 점유와 대기
   • 자원 하나가 있는 상태에서 다른 자원을 기다릴 때
3. 원형 대기
   • 자원 할당 그래프가 원형일 때
   • 서로 양보하지 않아 교착상태 발생

조건 분석

상호배제, 비선점 ⇒ 자원의 특징이라 어길 수 없다

점유와 대기, 원형 대기 ⇒ 이 내용을 해결하면 교착상태 해결

교착상태 해결 방법

교착상태 예방

• 교착상태가 발생하지 않도록 애초에 예방해버림
• 가장 보수적
• 유연성과 효율성이 떨어짐
• 종류
  • 상호 배제 예방 → 상호배제를 통해 자원 보호가 필요해서 실현 불가능
  • 비선점 예방 → 모든 자원을 뺏을 수 있도록 하면 아사현상을 비롯한 다양한 문제 발생
  • 점유와 대기 예방
    • 프로세스에 자원을 전부 할당하거나 아예 할당하지 않는 방식
    • → 효율성 저하 (남는 자원 없이 프로세스를 빨리빨리 돌려야 효율적)
    • 자원이 아닌, 할당 방식을 변화시키려는 점에 의미
    • 단점
      • 프로세스가 자신이 사용할 자원을 모두 아는게 어려움
      • 자원 활용성 저하 (효율성 저하)
      • 많은 자원을 사용하는 프로세스가 불리함
  • 원형 대기 예방
    • 모든 자원에 숫자를 두고, 숫자가 큰 방향으로만 자원을 할당 (우선순위)
    • 단점
      • 유연성이 떨어짐
      • 어떤 자원에 어떻게 번호를 부여할지가 문제

교창상태 회피

• 교착상태가 발생할 것 같을 때 해결
• 남은 자원의 수를 조절하면서 사용 → 자원을 줄 때 마다 판단이 필요
• 자원 할당 기준
  • 안정상태 : 자원을 나눠줘도 남는 자원으로 다른 프로세스를 끝낼 수 있는 상태
  • 불안정 상태 : 남은 자원으로 끝낼 수 있는 프로세스가 없는 상태
  • 할당된 자원이 많을수록 불안정해짐
  • 불안정 상태가 커질수록 교착상태 발생 가능성이 커짐
  • 불안정상태 ≠ 교착상태 (가능성만 커질 뿐)
• 문제점
  • 프로세스가 사용할 자원을 미리 선언해야 함
  • 시스템 전체 자원 수가 고정적이어야 함
  • 자원이 낭비됨 → 불안정 상태라고 아예 자원을 안줘버리는건 낭비임

교착상태 검출 및 회복

• 예방하지 않고 실행하다가 발생 하면 그 때 해결
• 검출과 회복은 하나의 묶음

교착상태 검출

• 운영체제가 프로세스 작업을 관찰하며 교착상태 여부를 주시
• 타임아웃을 이용한 검출
  • 일정 시간동안 작업이 없는 프로세스는 교착상태가 발생한 것으로 간주하여 처리
  • 타임아웃이 되면 프로세스 종료
• 데이터베이스에서 타임아웃 문제
  • 타임아웃으로 강제 종료 시 일부 데이터 일관성이 깨질 수 있음
  • 그 문제를 해결하기 위해 체크포인트와 롤백 사용 (둘이 세트)
    • 체크포인트 : 작업 중 문제가 발생하면 되돌아오기 위한 표시
    • 롤 백 : 문제 발생 시 가장 가까운 체크포인트로 돌아가는 것
• 자원 할당 그래프가 Roop면 교착상태

교착상태 회복

• 교착상태 검출 후 상태를 풀기 위한 후속 작업
• 교착상태를 유발한 프로세스를 강제 종료
  • 모두 동시 종료 → 비효율적, 억울한 프로세스가 있을지도..
  • 빅틈 : 하나를 골라 종료 (3단계 순서대로 반복 → 정 안되면 사용자를 통한 강제종료)
    • 우선순위가 낮은 프로세스 종료
    • 작업 시간이 짧은 프로세스 종료 (다시 실행해야 하니 짧은걸 다시 시작하는게 덜 손해)
    • 자원을 많이 사용하는 프로세스 먼저 종료 (회수하여 다른 프로세스를 끝낼 수 있음

은행가 알고리즘

• 은행가 알고리즘
  • 은행의 돈이 많아야 대출해줌.
  • 은행에 돈이 적으면 대출 안해줌.
  • 대출해줘서 갚을 수 있는 사람에게만 해줌
• 변수
  • Total : 시스템 전체의 자원
  • Avaliable : 가용 자원. 시스템에서 줄 수 있는 자원의 수
  • Max : 프로세스가 필요한 최대 자원의 수
  • Allocation : 각 프로세스에 현재 할당된 자원의수
  • Expect = Need : 각 프로세스가 앞으로 필요한 자원
• 할당 기준
  • 가용 자원이 기대 자원보다 크면 할당, 적으면 할당하지 않음
  • 요청 자원 > 필요 자원 ⇒ 에러
  • 요청 자원 > 잔여량 ⇒ 대기
  • 요청 자원 ≤ 잔여량 ⇒ 할당