CPU Scheduling

CPU scheduling

무슨 process가 다음에 실행하고, runnable process의 set을 제공하는 정책이다.
Mechanism : How to transition?
Policy : When to transition/

Terminologies

Workload
- A set of job(program이랑 비슷하다 보면 됨) descriptions: 동작시킬 job들의 명세
- e.g. arrival time, run time etc
Scheduler
- A logic that decides when jobs run
Metric
- scheduling quality를 평가하는 척도
- e.g. turnaround time, response time, fairness etc

Scheduling Performance Metrics

Miniminze turnaround time
- job이 끝나기까지 오래 기다리고싶지 않음
- Turnaroundtime = Time of completion - Time of arrival
- 내가 시스템에 job을 제출한 시각으로부터 끝날때까지의 시간
- sched 위해 기다리는 시간 + 실행시
Minimize response time
- 요청을 보낸 후 첫번째 응답까지의 시간
- Interactive job들을 신속하게 schedule함으로써 user가 결과를 빠르게 볼 수 있도록 함
- Response time = Time of firstrun - Time of arrival
이 밖에도
- Ready queue에서 대기하는 waiting time을 최소화
- Throughput(# of jobs to complete per unit of time) maximize
- Resource utilization maximize
- Overhead minimize
- fairness maximize 등이 있다.

본격적으로 scheduling에 대해서 알아보기 전에, 다음과 같은 5가지 Workload assumptions를 한다.

각각의 job들은 같은 양의 시간동안 CPU를 사용한다.
모든 job들은 동시에 도착한다
한번 시작되면, 완료될때까지 동작한다
모든 job들은 i/o없이 CPU만 사용한다
job들의 run time은 알 수 없다.

Metric은 Turnaround time으로 가정한다.

FIFO

First in, First out
Real-world와 같은 scheduling
Non-preemptive이고, starvation이 없다. (이론상 언젠가 실행됨)
하지만, Convoy effect가 발생함. (평균 turnaround time이 길다.)
- 매우 긴 작업이 실행되면 뒤의 작업은 오래 기다려야함.

⇒ 이와 같은 Convoy effect를 방지하기 위해

Shortest Job FIrst ( SJF )

Each job들은 run time이 다르다고 가정한다. (Assumption 1 relaxed)
고를 수 있는 job들 중 가장 run time이 짧은 것을 고른다.
이 때 우리의 가정에 한해서는 가장 최적의 turnaround time을 보여준다.
Non-preemptive
Problems
- job이 언제 도착할지 모르는 상황에서는 optimal하지 못함
- 잠재적으로, starvation이 발생할 가능성이 있음

FIFO vs. SJF

만약 동시에 도착한다는 가정 하에서는, 가장 Turnaround time을 줄일 수 있지만
오른쪽 밑의 그림처럼 동시에 job이 도착하지 않으면 비효율적일 수 있다.

STCF( Shortest Time-to-Completion First)

Job들은 동시에 도착하지 않는다(가정 2번 배제)
SJF의 Preemptive 버전이다. ( 가정 3번 배제)
만약 나중에 도착한 job의 run time이 현재 job의 remain time보다 작다면, preempt한다.

Round Robin

Run queue를 circular FIFO queue라고 생각한다.
각각의 job에게는 time slice가 주어진다.
- tick이라고 부르는 timer or timer interrupt주기의 n배
- 너무 짧으면 context switch overhead
- 너무 길면 less reponsive 이므로 보통 10~100ms로 설정
일정 time slice동안 작업을 수행하고, 다음 job에게 넘겨준다.
Preemptive하고, starvation이 없다.
response time이 좋기에 time-sharing 하기 좋다
Turnaround time보다는 response time에 초점을 맞춤

SJF vs RR

(static) Priority Scheduling

각각의 job들에게 priority를 부여하고 우선순위가 높은 job에게 다음 실행 순서를 주는 방식
- ex) shortest job in SJF
같은 우선순위를 가진 job들에게는 RR 혹은 FIFO 방식으로 동작하게함
선점형, 비선점형 모두 가능
- 선점형 : 더 높은 priority의 job 도착하면 중단시키고 그 job 수행
- 비선점형: 더 높은 priority job 도착해도 끝날때까지 current job 수행
하지만, Starvation problem 발생 : 계속 높은 우선순위의 job만 도착하면 우짬

Incorporating I/O

또, I/O가 포함되어있는 job이면 우짬?
- 가정 4 배제
- Overlap computation with I/O라고 생각해보자 ( I/O 기다리는 동안 다른 연산 가능)
- 또한, 각각의 CPU는 사용기간 (burst을 독립적인 작업이라고 가정
만약, A ( interactive) + B ( CPU-intensive)가 합쳐진 작업이 있다면

A에서 I/O작업을 요청하는 동안, B의 작업을 수행함으로써 시간을 단축시킬 수 있음

xv6 : CPU shceduler

xv6에서는 yield(), shced(), scheduler()을 통해서 구현
trap.c에 있는 trap()함수로 Every timer IRQ마다 CPU yield 구현 (RR)

⇒ 그렇다면, 더 General한 CPU Scheduler을 만들기 위해서는?

Goals
- turnaround time Opimize하기
- interactive job들의 response time Minimize하기
Challenge
- workload에서 가정했던 5가지의 가정들 중 아는 것 하나도 없음
Learn from past to predict the future : branch predictors or cache algorithms

→ 그래서 등장한, MLFQ

MLFQ (Multi-Level Feedback Queue)

Multi-Level Feedback Queue
- 각 Priority level마다 queue가 존재함
일단, 다음과 같은 2가지 Rule이 존재

If Priority(A) > Priority(B) , A runs
If Priority(A) = Priority(B), A & B run in RR

Priority는 동적으로 달라질 수 있음

Changing Priority

일단, 전형적으로 갖는 workload는
- Interactive job : short-running, require fast response time ( I/O 처리 포함)
- CPU-intensive job : CPU time을 많이 차지하고, response time은 신경쓰지 않음

이를 고려해 다음과 같이 동적으로 Priority를 바꾸는 Rule을 추가한다.

3.Job이 처음 system에 들어오면, 가장 높은 priority queue에 위치한다. (topmost queue)

4a. 만약 Job이 실행 중 모든 time slice를 사용하면, priority가 감소한다. (queue 하나 내려옴)

4b. 만약 time slice가 끝나기 전에 CPU를 포기하면 같은 priority level을 유지한다.

→1-4의 Rule을 고려해 Scheduling을 하면 다음과 같다.

⇒ 이렇게 shceduling 하면 무엇이 문제냐?

시간이 오래걸리는 Job들은 너무 많은 interactive job들로 인해 Starvation이 생길 수 있음
악성 user가 Cpu time slice가 끝나기 전에 포기해서 계쏙 scheduler을 사용할 우려가 있음
프로그램의 실행패턴이 바뀔 수 있음 (Cpu intensive → interactive job)

그럼, 다음과 같은 Rule을 추가하면 어떨까

5. Some time period S가 지나면, 모든 job들을 topmost queue로 옮김

그림에서 볼 수 있듯, A의 starvation 현상이 사라진다.

또한,문제점 2번을 해결하기 위해, Rule 4a와 4b를 다음과 같이 수정한다.

4.JOb이 자신의 level에서 time allotment를 다 사용했으면 CPU를 포기했던 적이 있는지 여부와

관계없이 priority를 감소시킨다. 만약 Cpu 포기하느라 time slice 다 사용 못했으면, 후에 사용 못한만큼만 다시 할당해주면 됨!

정리하자면, 다음과 같은 5개의 rule을 적용한다.

이를 적용한 MLFQ의 장점: Process의 Cpu usage를 선험적으로 알아야할 필요가 없다는 것이다.

UNIX Scheduler

MLFQ 사용
CPU-bound process보다 interactive process 선호
aging 기법(대기 시간이 길어질수록 프로세스의 우선 순위를 점진적으로 높여, 결국 모든 프로세스가 CPU 시간을 받을 수 있도록 하는 기법)을 사용해 starvation 방지
Many ugly heuristics for voo-doo constants( 경험적 상수 사용)

⇒ 그렇다면, Fairness에 가장 중점을 둔 Scheduler은 없을까?

Proportional Share Scheduling

Basic concept
- 각각의 process마다, 가중치가 주어진다고 가정한다.
- 이때, CPU time은 가중치의 비율마다 주어진다.

이에대한 2가지 적용 맥락이 존재한다
- Fair queueing (통신 네트워크의 맥락 : 공평한 대역폭 확보)
  - Packet Scheduling
- Proportional share ( OS의 맥락)
  - Process scheduling

Lottery and Stride Scheduling

임의의 시점이 누구에게 CPU 줄것인가 하는 문제.
각각의 Task에게 임의의 티켓을 부여하고, Task들의 티켓 합산은 M이라고 가정한다.
Lottery scheduling은 확률 이론에 근거해 m/M 확률로, Cpu를 사용할 수 있다.
Stride scheduling에서는 deterministic algorithm을 사용한다.
- Stride는 weight의 역수이다.
- 1번 시행시 Stride만큼 value가 증가하고, 다음 시행 시 value가 가장 적은 것을 Cpu에 할당시킨다.

슬기로운 CS생활