5.CPU Scheduling - Scheduling algorithms

• First-come, first-served (FCFS) scheduling
• Shortest-job-first (SJF) scheduling
• Priority scheduling
• Round-robin scheduling
• Multilevel queue scheduling
• Multiple feedback-queue scheduling

---

1. First-Come, First-Served Scheduling

• CPU를 먼저 요청하고 CPU를 먼저 할당하는 프로세스
  • Non-preemptive scheduling (중간 스위칭이 없당)
  • 가장 간단한 스케줄링 방법 
   
• 때때로 평균 waiting time이 길다 (CPU, I/O 유틸리티가 비효율적)

FCFS 예시

2. Shortest-Job-First Scheduling

• CPU burst 가장 작은 프로세스에 할당 (작은것부터 처리하쟝!)

SJF

• SJF 알고리즘이 최소 waiting time에 최적임
  * Problem: 다음 CPU burst 길이를 알 수 없음 (해결방법: 히스토리를 보고 미래정보를 예측한다.)

---

Exponential averaging(지수평균화)

지수평균화

• 오래된 history는 영향력이 적음
• 실제값이 크면 Tn을 줄이고 실제값이 작으면 Tn을 크게

Prediction of CPU Burst

---

sjf (Preemptive version)예시

3. Priority scheduling

• CPU에 가장 높은 우선 순위로 프로세스가 할당
• 각 프로세스는 priority가 지정되어 우선순위로 처리 (우선 순위가 동일한 프로세스: FCFS)
• 가장 중요한것이 빨리 돌았다는 관점에서 좋다 (응급실 환자 처리 느낌)

ps

• 우선 순위는 내부 및 외부에서 할당할 수 있음
  • Internally(내부): 프로그램 통계를 보고 우선순위를 변화시킴
  • Externally(외부) : 유저가 명시적으로 주는것 (realtime process같은)
• Priority scheduling은 preemptive, nonpreemptive 둘다 가능
• Priority scheduling 으로 SJF구현가능
  • waiting time 이 짧은것은 우선순위로 두면된다 (I/O bound process 우선순위가 높아야함)

* Major problems

• Indefinite blocking ( = starvation) : 우선순위가 낮은 프로세스의 무기한 차단 (주인님 저 굶어 주거용 ㅠㅠ)
• 우선순위가 낮으면 계속 실행이 안되고 멈춰있게 된다.
• Solution : aging - 오래 기다리는 프로세스의 우선순위를 대폭 증가 (한번 양보하면 우선순위 높여줌)

 

4. Round-Robin scheduling

• FCFS와 비슷하지만 preemptive하다.
• 일정시간이 지나면 무조건 스위칭~
• cpu시간은 time quantum (or time slice)으로 나눈다.
• A time quantum is 10~100 msec. / switching latency: 10 usec / 1msec = 1000usec
• Ready queue는 circular queue로 구현
• CPU schedule 가 ready queue를 돌면서 CPU시간을 최대 1 time quantum으로 할당

 

RR

중요한 문제 : "time quantum 사이즈를 얼마로 적용할것인가"

• RR scheduling성능은 time quantum에 크게 영향을 받음
  • Time quantum is small : processor sharing, 반응성이 좋다
  • Time quantum is large : FCFS, 반응성이 나쁘다

그러면 좋은선택은 어떻게?

A rule of thumb: CPU burst 80% 정도를 커버할수있으면 적정값이다.

Histogram of CPU-burst Durations

여기서 80%정도 커버하는거면 cpu bound process 임

5. Multilevel queue scheduling

• 프로세스를 여러 그룹으로 분류하고 다른 스케줄링 적용 (Memory requirement, priority, process type, …)
• ready queue를 여러 개별 queue로 분할

계층이 나눠진다.

• 각 queue는 고유한 scheduling algorithm이 있다.
• Scheduling among queues
  • 1) Fixed-priority preemptive scheduling
    • 우선 순위가 낮은 대기열의 프로세스는 모든 우선 순위가 높은 대기열이 비어 있는 경우에만 실행할 수 있음 -> 잘쓰이지않음
  • 2) Time-slicing among queues
    • 예 : foreground queue (interactive processes): 80%  / background queue (batch processes): 20%
• 할당이 되면 다른쪽 프로세스로 이동이 안된다. (이게 이 알고리즘 정의 , 위아래로 움직일 수 없음)

 

6. Multiple feedback-queue scheduling

• multilevel queue scheduling이랑 비슷하지만 프로세스가 queues간 이동이 가능하다.
• 윈도우, 맥os 다 이 방식을 쓴다
• Idea: CPU bursts 특성에 따라 프로세스를 분리
• 프로세스가 CPU 시간을 너무 많이 사용하는 경우(cpu bound process) 우선 순위가 낮은 대기열(queue)로 이동
• I/O-bound, interactive processes 는 우선순위가 높은 queue에 있음

시간 제한을 초과시 낮은 순위로 이동

고려해야 할 사항이 많음 ㅠㅠ

• queues 수
• 각 queues에 대한 스케줄링 알고리즘
• 프로세스를 우선 순위가 높은 queues로 업그레이드할 시기를 결정하는 방법
• 프로세스를 낮은 우선 순위 queues로 강등할 시기를 결정하는 방법
• 프로세스가 서비스를 필요로 할 때 어떤 queues에 들어갈지 결정하는 방법

등등 하여튼 복잡한 알고리즘이다.