Multilevel Queue

• ready queue 를 여러 개로 분할
  • foreground(interactive) : 사용자와 상호작용이 있는 프로세스
  • background(batch - no human interaction) : 사용자와 상호작용이 없는 프로세스
• 각 큐는 독립적인 스케쥴링 알고리즘을 가짐
  • foreground → RR
  • background → FCFS
• 큐에 대한 스케쥴링이 필요
  • Fixed priority scheduling
    • serve all from foreground then from background
    • Possibility of starvation
  • Time slice
    • 각 큐에 CPU time 을 적절한 비율로 할당
    • ex) 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있다
• Multilevel-feedback-queue scheduler 를 정의하는 파라미터들
  • Queue 의 수
  • 각 큐의 scheduling algorithm
  • Process 를 상위 큐로 보내는 기준
  • Process 를 하위 큐로 내쫓는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Example of Multilevel Feedback Queue

• Three Queues:
  • Q0 - time quantum 8 miliseconds
  • Q1 - time quantum 15 miliseconds
  • Q2 - FCFS
• Scheduling
  • new job 이 queue Q0 로 들어감
  • CPU 를 잡아서 할당 시간 8 miliseconds 동안 수행됨
  • 8 miliseconds 동안 다 끝내지 못했으면 queue Q1 으로 내려감
  • Q1 에 줄서서 기다렸다가 CPU 를 잡아서 16 ms 동안 수행됨
  • 16 ms 에 끝내지 못한 경우 queue Q2 로 쫓겨남

Multiple-Processor Scheduling

• CPU 가 여러 개인 경우 스케쥴링은 더욱 복잡해짐
• Homogeneous processor 인 경우
  • Queue 에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load sharing
  • 일부 프로세서에 job 이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs 공통 큐를 사용하는 방법
• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케쥴링 결정
• Asymmetric Multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling