교착상태와 스케줄링.md

탐지 detection

• 교착상태를 탐지하는 알고리즘 필요
• 즉시할당하지 못하거나 CPU 사용률이 40% 이하로 떨어지는 경우 호출
• 탐지 자주실행하면 성능 저하
• 교착상태에 빠진 프로세스를 빨리 발견 -> 유휴상태 방지 가능
• 자원할당 그래프를 활용하여 탐지
• 교착 탐지시 회복(복구)과정 필요

회복 recovery

1. 강제종료
   1. 교착을 일으킨 모든 프로세스 중지 (비용큼)
   2. 교착이 해결될 때 까지 하나씩 중지 (오버헤드 큼)
2. 교착 프로세스가 점유하는 자원을 다른 프로세스가 선점하게 함 우선순위가 낮은 프로세스 매번 결과를 기록해서 선점 횟수에 따라 할당해주지 않으면 기아 발생 가능성 있음

프로세스 스케줄링

• 다중프로그래밍 시스템
• I/O Burst, CPU Burst

종류

• 장기스케줄러 (준비-생성)
  • 어떤 프로세스를 준비큐에 넣을 것인지 결정 (시분할에선 X)
  • 메모리에 동시에 올라간 ps의 수를 조정
• 중기스케줄러 (중단)
  • 메모리에 올라간 프로세스 수 관리
  • 메모리 부족하면 swap in(디스크 스왑영역에 저장), 여유 생기면 swap in
• 단기스케줄러
  • 메모리 내 준비상태 작업중 실행할 ps에 CPU 할당
  • 미리 정한 알고리즘에 따라 선택
  • 매우 빈번하게 호출

알고리즘 선택기준

• 프로세서 사용률
• 처리율(단위시간당 완료 작업 수)
• 반환시간(모두완료)
• 대기시간(in 준비큐)
• 반응시간(요청 후첫반응까지)

비선점스케줄링

• 한 프로세스가 자원을 선택했을때 다른 프로세스가 빼앗을 수 없음
• 공정성 O 융통성 X

비선점스케줄링 알고리즘

• FCFS
• SJF(Shortest Job First)
  • 최단시간 작업 우선
  • 준비큐에서 기다리는 ps중 실행시간이 가장 짧은 작업에 할당
  • 평균대기시간을 줄일 수 있음
  • 긴 작업의 ps는 기아상태가 될 가능성이 있음
• HRRN(Highest Response Ratio Next)
  • SJF를 보완한 기법
  • 우선순위 계산값이 큰 수부터 CPU 할당
  • (대기시간/예상실행시간) +1

선점 스케줄링

• 현재 실행중인 ps를 인터럽트하거나 준비상태로 이동시킬 수 있음
• 대화식 시분할, 실시간 시스템 등 빠른 응답시간 위해 필요
• context switching으로 인한 오버헤드 큼
• 우선순위 잘 부여해야함
• 우선순위 높은 ps의 긴급처리요청 가능

선점스케줄링 알고리즘

• RR(Round Robin)
  • 시분할시스템 시간단위(quantam/time slice)로 CPU 할당
  • 할당 크면 FIFO랑 같아짐, 작으면 문맥교환 오버헤드 커짐
  • 응답시간 짧음 - 실시간 시스템 유지
• SRTF(Shortest Remaining Time First)
  • 선점 SJF
    • 현재 ps랑 준비큐의 top중 더 짧은애 실행
    • 시분할에 효과적
    • 실행시간을 추적하여 보유하므로 오버헤드 큼
• MLQ(Multilevel queue)
  • 그룹마다 준비큐 형성
  • 큐마다 다른 Quantum 설정 (우선순위 높으로 tq 짧음)
• MFQ(Multileven Feedback Queue)
  • 다단계큐 + Feedback
  • 사용 후 한칸씩 내려감
  • 가장 하위큐에서 오래 대기할 경우 위로 이동(에이징)
  • 하위큐는 FIFO

우선순위 스케줄링

• 우선순위에 따라 실행
• 선점, 비선점 방식 모두 존재