Process Priority

Depends on	Scheduler • Processes

Periodically, the scheduler has to select the next process to run. Time-slicing with a simple round-robin algorithm would give an equal share of processor time to all processes which are not blocked. This can be too simplistic to be useful. It is often useful to be able to assign priority to processes so that some are favoured over others.

An example could be a background job, which is processor intensive but which the user feels has no great urgency (e.g. mining Bitcoins); this might have a lower priority than (e.g.) a job playing videos which has a strict timing requirement, so that it leaves adequate resource for that whilst occupying any gaps in between.

A process’ priority may be set by the user (or the system) in various ways. It may be constant or calculated dynamically. For example, a process which blocks rather than being time-sliced may have its priority temporarily increased when it can run again; this allows I/O bound processes to run to the next ‘blockage’ quickly and thus make progress without impeding other processes very much.

Priority can be applied in different ways too. In a real-time system it probably dictates that the highest priority ‘ready’ process runs whilst it can. (Equal priority processes may or may not be time-sliced.) In an interactive system, this approach could prevent lower priority processes proceeding at all, so the strategy may be different: for example the priority could determine how often the process receives a time-slice or it could vary the length of the time-slice.

Practical: try running the Unix utility top. This displays the processes which have been occupying the processor recently, together with each process’ priority (maybe labelled “PR”). Confusingly, lower numbers indicate higher priority. You may also spot a nice value (“NI”). “nice” is a user-set value which is used to alter (usually reduce) the priority of that process, causing it to demand less system time. In Unix it varies from -20 (very ‘nasty’) to 19 (very nice); an ordinary ‘user’ cannot go below 0; negative values are for the system/‘root’. The utility “nice” on its own simply echoes the current (inherited) nice (0 by default); with a parameter it increases the ‘niceness’. If you have a couple of Unix ‘shell’ windows, run top in one and try some experiments in the other. (An infinite loop program might help this demonstration: forever.c would do – it can be downloaded here.) Prefixing a command line with “nice” will set the appropriate value.   It may be easier to use two shells for this: one to play in and one to watch the results.

• nice -4 escape should show the application running in top.
  This probably won’t have much actual effect unless your computer is already busy.
  ^C might be useful now.
• nice -2 bash will start a daughter shell
  nice should now echo “2”
  nice -4 escape should show the application running at niceness 6
  ^C
exit will return you to your original shell

If you run several processes at different ‘nice’ settings you should see the CPU allocation divide appropriately. On a single processor machine this is quickly obvious. As you are probably using a multicore processor you will need to start several processes (more than you have ‘cores’) before anything is apparent because, at first, there will be a ‘spare’ core for each new job.   Reminders:

• you can stop the shell waiting for a job with ‘&’

   e.g. nice -3 escape&

• you can find detached jobs in a shell with jobs
• you can kill a job with kill %<n> (where ‘<n>’ is the job number.)
• you can kill a process with k within top.

In some scheduling algorithms – particularly in interactive systems – the effective priority may be dynamic. For instance, ‘ageing’ may raise the effective priority if a process has not been run for a while, eventually guaranteeing it some sort of share.

Priority inversion

This is a rather obscure topic, which is included here because it tends to get mentioned a lot. It is particularly applicable to real-time systems.

A “priority inversion” is a circumstance where a high priority task is prevented from running by a lower priority task. The scenario:

1. A low priority task acquires a mutex.
    
2. A high priority task pre-empts, tries for the same mutex and blocks.
    
3. Before the low priority task can release the mutex a medium priority task occupies the processor.

The high priority task is suspended until the low priority task frees the mutex. Normally this would happen quickly but the low priority task isn’t allowed the chance. The medium priority task – which would normally be pre-empted – hogs the urgently needed resource.

For a famous example of this problem, look up the “Mars Pathfinder” (1997).

Solutions exist, such as priority inheritance, where the priority of the process holding a mutex is temporarily boosted to the priority of anything waiting for that mutex, until it exits the critical section.

Plenty more discussion and other solutions are ‘out there’…

---

Also refer to:	Operating System Concepts, 10th Edition: Chapter 5.3.4, 5.6.2, 5.7.2, 6.8.2, pages 211-214, 229-230, 239-242, 284

Context Dependencies Dependants

Max. number:

Max. distance:

Next

Articles on Processes

About this resource • Atomicity • Containers • Context • Context Switching • Daemons • Fork Unix • Hypervisor • Idle • Interprocess Communication • Multi Threading • Mutual exclusion • Pipes • Pointer Arithmetic • Process Control Block (PCB) • Process Priority • Process Scheduling • Process States • Processes • Queues • Queues Extra • Race Conditions • Real Time • Resources • Scheduler • Signal and Wait • Sleep • Starvation • Synchronisation • Thrashing • Threads • Unix Signals