[운영체제] CPU Scheduling

Scheduling Criteria

• CPU utillzation (이용률)
• Throughput (처리량)
• Turnaround time (소요시간, 반환시간)
• Wating time (대기 시간)
• Response time (응답 시간)

---

SJF (Shortest-Job-First)

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• Two schemes :
  • Nonpreemptive
    • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
  • Preemptive
    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다
• SJF is optimal
  • 주어진 프로세스들에 대해 minimum average waiting time을 보장

---

다음 CPU Burst Time의 예측

• 다음번 CPU burst time을 어떻게 알 수 있는가?
• → input data, branch, user …
• 추정(estirmate)만이 가능하다
• 과거의 CPU burst time을 이용해서 추정 (exponential averaging)

---

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 milliseconds)
• 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
  • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• Performance
  • q large ⇒ FIFO
  • q small ⇒ context switch 오버헤드가 커진다

---

Multilevel Queue

• Ready queue를 여러개로 분할
  • foreground (interactive)
  • background
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
• Time slice
  • 각 큐에 CPU time을 적절한 비율로 할당

---

Multiple - Processor Scheduling

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

---

Real - Time Scheduling

• Hard real - time systems
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
• Soft real - time computing
  • Soft real - time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

---

Thread Scheduling

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