For this class I thought I'd dive a little deeper into process scheduling and the different schedulers used in modern operating systems.
I'm reading a bit about four different schedulers:
After the reading I plan to write up something about the differences between the scheduling algorithms, which may or may not include some code.
Here's my notes from the readings:
Multiple (16) priority queues
General hierarchy:
system tasks/clock > drivers > servers > user processes >>> idle process (lowest level)
Processes can be "demoted" to a different queue by the scheduler if they use the whole quantum (especially repeatedly). Processes can also be "promoted" if they are using the entire quantum and not getting in the way of others.
Queues run in round robin, unless a process blocks before the end of its quantum. If that happens, the process is placed back at the beginning of its queue with only the "leftover" quantum to use when it runs the next time.
Priority of queues is strict: no process on a lower queue will run until all higher-priority queued jobs are inactive/finished.
Processes are allotted different quantums based on priority. More important drivers and servers almost never use the entire time slot.
Aimed at providing the best/smoothest user experience
Uses earliest eligible deadline algorithm with virtually-generated deadlines. Deadlines are computed as a function of the flat-value (6ms) time-slice and the nice value of a task.
Algorithm always selects the task with the nearest deadline to run.
Tasks that use their full time-slice are requeued with a new (later) deadline. Tasks that block or sleep before using the entire slice are requeued with the same priority, ensuring that they will run as soon as possible.
Queue is structured as a skip-list, with insertion being an O(log n) operation, and extraction an O(1) operation (algorithm is always picking the top job).
Does not use timeslices
Aims to be 'completely fair' to all processes, dividing CPU time/resources up as equally as possible.
Orders processes in the queue based on accumulated wait time. Processes accumulate wait time based on the wait time clock, which progresses at the speed of the wall clock divided by the number of processes currently in the queue.
While a process runs, it decrements its wait time. When it has a lower wait time value than the highest-wait-time queued process, it is swapped out.
Ignores any concept of what is or isn't a user process in the name of "fairness."
