Priority based scheduling, is in its raw form very simple. From a list of runable processes the process with the highest priority is chosen to run.

Preemptive vs. Non-preemptive

Priority Scheduling can be used for both versions of scheduling. Non-preemption is simple and unproblematic. Preemptive priority scheduling has the normal problems involved with preemption. Additionally there are priority specific problems.

Problem

The main problem with priority scheduling is that low-priority processes can starve. If an operating system hasn't any precautions and just chooses the process with the highest priority, low priority processes wouldn't get any processor time, as long as high priority processes are runable.

Solution

To prevent the above mentioned situation, the simplest solution are dynamic priorities. On one hand the operating system can reduce the priority of a running process for each quantum it used the CPU and on the other hand it could boost the priority of other processes (which finally leads to the first situation because the boost should only be temporary) which didn't get the cpu for a certain amount of time. Whether the operating system uses one or another solution, processes have a base priority which remains unchanged, and a real priority which is used for scheduling. Often the real priority is limited to a specific range, so that important process still get the processor when they need it.

Though dynamic priorities are simple and work very well, one could implement a solution using static priorities. The operating system has to keep a record of how long a process has used the CPU. If it reaches a certain limit, the next highest priority process is allowed to run. I personally think this is not very practical and that it just hides the use of dynamic priorities. Processes have a static priority, but the time limit works as dynamic priorities.

Priority Classes

Priority classes are a way to combine the advantages of priority and round robin scheduling (but also some of their disadvantages). Processes are grouped in classes depending on their priority. The scheduler uses priority scheduling to choose the highest-priority, non-empty class. Inside the classes round robin is used. This algorithm should be faster than simple priority scheduling, as it has not to compare the priorities of all processes, and against round-robin it has the advantage of giving important processes more CPU time.

But as you might have guessed already, it has the same problem of starvation has simple priority scheduling. To prevent starvation, several solutions are conceivable. One could temporarily switch classes, could promote processes or one could merge classes. The first solution isn't practical, as important process won't get the needed CPU time. I would choose the merging of classes. When linked lists are used, the merging and the splitting are very fast.

Is priority scheduling used?

Yes! Almost every desktop or server operating system uses some kind of priorities. Depending on the usage of the OS, the implementations are very different. A scheduler could for example boost processes which interact with users or which heavily use I/O.

Log in or register to write something here or to contact authors.