CPU Task Scheduling

First Come First Serve

Queue Non-preemptive

Average waiting time is long

Shortest Job First

Schedule the job with the shortest duration first (when it arrives) Non-preemptive

Can you show a counter example where this is not optimal? (hint: think about different arrival times)

Shortest Remaining Time First

This is the preemptive version of SJF. At each time interval, check the shortest job. Use SJF when the all the jobs are in the queue.

This is unfortunately not practical because CPU cannot know all the duration (burst time) ahead of the time.

Round Robin

So we can just put them into small segments and run them in order.