Workload（工作负载） assumptions:

• Each process run for the same amount of time
• All jobs arrive together
• No process perform IO, they only use CPU
• Known run time

Picking a process to run is what scheduling means.

Performance metric: turnaround time（周转时间）, response time（响应时间） and fairness.

Tturnaround = Tcompletion − Tarrival , Tresponse = Tfirstrun − Tarrival. Performance and fairness are often in conflict.

Scheduling algorithms

FIFO（先进先出）

As it’s called. Simple and easy to implement.

Convoy effect（护航效应）: if an earlier process wants to run much longer than later processes, bad $T_{turnaround}$ is caused.

Shortest Job First（最短任务优先）

Each jobs run for the same amount of time

Non-preemptive（非抢占式） scheduler, won’t stop the existing job to run another

However, if shorter processes arrive later and longer process has already started, it may still act as “FCFS” scheduler.

Shortest Time-to-Completion First（最短完成时间优先）

All jobs arrive together

Add preemption to SJF.

When a new process enters, pick the process with the shortest time to completion to run first.