CPU scheduling cont. #

I/O Bursts #

Round robin #

Round robin strives on optimizing average response time.

If we make the value of \( q \) too small, we will have a lot of overhead due to context switches.

Priority scheduling #

Technically, shortest job first is a type of priority scheduling (prioritizing shortest burst time).

Multilevel queue #

Scheduling in Linux (CFS) #

Priority levels are 0-139.

• The smaller the priority number, the higher the priority.
• The higher priority processes have larger time quantums.
• Feedback based on sleep time (waiting/idle)
  • longer sleep processes are usually interactive, so we bump up the priority (lower value)
  • shorter sleep processes are usually computational process, so we bump the priority down (higher value)
• The run queue is 2 arrays of tasks

Picking the next item in the array is constant time. When we create a process, we add it to the corresponding task list, based on priority.

When the active array is exhausted, it is swapped with the expired array.

However, this scheduling algorithm has some problems

• performance of interactive processes can be slow
• fairness issue

Linux’s new CFS (Completely Fair Scheduler) addresses these problems:

• CFS uses a red-black tree for its run queue
• The value that the red-black tree is ordered is called vruntime, which is the “virtual run time” that is a function of the run time.

• CFS scheduling always picks leftmost node, the smallest value (smallest vruntime value)
• periodically address vruntime and compare to the leftmost, if it is still smaller we will allow the process to continue to run. When the vruntime surpasses the leftmost in the run queue tree, it will switch to the new smaller value. (Similar to shortest run time, but we’re looking at the history)
• vruntime progress rate depends on priority
  • progress rate faster for low priority
  • progress rate slower for high priority
• note that only 1 tree is used, for all priority