5-2 CPU Scheduling

Multilevel Queue

• 우선순위에 따라 프로세스의 순서

• 생성 시에 우선순위가 결정

• Ready Queue를 여러 개로 분할

  • foreground (interactive)
  • background (batch - no human interaction)

• 각 큐는 독립적인 스케줄링 알고리즘을 가짐

  • foreground - RR
  • background - FCFS

• 큐에 대한 스케줄링이 필요

  • Fixed Priority Scheduling
    • foreground 먼저 수행 후 background를 수행
    • starvation이 발생할 수 있다.
      • 해결책 : timeslice - 각 큐에 CPU time을 적절한 비율로 할당(80% - foreground, 20% - background)

Multilevel Feedback Queue

• 우선순위가 변경된다.
• 할당 시간 내에 처리가 되지 않는 경우 time quantum을 점점 늘여나간다. (우선순위는 점점 낮춘다.)

Real-Time Scheduling

• Hard real-time systems
  • 정해진 시간 내에 반드시 수행되도록 해야 한다.
• Soft real-time systems
  • soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 한다.

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할 지 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할 지 결정

Algorithm Evaluation

• Queueing models
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
• Implementation (구현) & Measurement (성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
• Simulation (모의 실험)
  • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교