Suppose that a user is using gcc to compile some code, while also browsing the web. In this situation it would be appropriate for the web browser to have more CPU access to allow faster responses to the user's input and to the network, while the compiler would have less CPU access since it is running in the "background". Priority scheduling is a useful way to control processes' CPU access in an intelligent way.
A process with a low priority number is said to have high priority. A process with a high priority number is said to have low priority. That is, a priority-1 process has a higher priority than a priority-2 process (and vice-versa).
A priority scheduler is simply one that calculates the priority for each process (with some algorithm) and then schedules the highest-priority job first. A Shortest Job First (SJF) scheduler is a type of priority scheduler with the priority for each process equal to its run length. Priorities that are set explicitly by the user are called external priorities, and those that are set by the operating system (using heuristics from resources used) are called internal priorities.
In Unix/Linux there is a command named "nice" which allows the user to adjust a processes priority. The normal syntax is as follows:
"Niceness" implies less priority. The logic being that if a process is "nice" it will allow other processes to complete first. A "mean" process, or one that is less "nice" will have higher priority because it will want to finish faster. By default the nice command adds 10 to the command's priority number. This makes the command lower priority in the system.
The "nice" command only affects the CPU, rather than disk, network, or memory. However, in modern systems of today, the CPU is rarely the bottleneck anymore.
Since the user cannot be relied on to set a priority for every process, the operating system must compute and set priorities internally. Usually, this entails examining the type and number of resources used by a process. For example, a compliler like gcc would be labelled as "CPU-bound" and given a lower priority, while a browser would be labelled "network-bound" and given a higher priority.
The OS can also dynamically compute priorities. A nice process will, in general, finish last or can be starved much longer than intended by the user. One solution is to compute the priority like so:
Priority = (initial priority) - age // age being elapsed time since it last ran
The OS can also switch the category of a specific job based on what it's going to do next. For example, an interactive process may have higher priority than a bash process. During the execution of a process, say a clock widget, the OS can dynamically switch from one category to the other so that when the user is interacting with the process, (perhaps setting the time of the clock) it has a high priority, but when it is no longer in an interactive state (perhaps running in the background without user interaction), it will be set to a lower priority.
In a Shortest Job First (SJF) scheduler, process starvation is possible. That is, a long-running process may never run if shorter-running processes continually appear. A Round-Robin scheduler may also have this problem if new jobs are not put at the end of the job queue. In a First-Come-First-Serve (FCFS) scheduler, process starvation does not occur, since every process is guaranteed to run once it is requested.
An example of starvation in a Round Robin:
| Job | Runtime | Arrival |
| A | 2 | 0 |
| B | 1 | 1 |
| C | 1 | 2 |
| D | 1 | 3 |
To solve the problem of process starvation, dynamically-computed priorities are used. Besides the user-set priority and the internal priority set by the operating system, the age of each process is usually factored in to the overall priority. That is, the more time that has elapsed since the last time the process ran, the higher the process's priority becomes.
Suppose there is a high-priority process Phigh and a low-priority process Plow running on a system with a priority scheduler. Suppose further that Plow acquires a lock on a certain file or shared object. If Phigh then tries to acquire a lock on the same file or object, it will block until the resource is available. If a medium-priority process Pmed now runs, it will take priority over both Phigh which is blocked, and Plow which is lower priority. Since Phigh is waiting for Plow their priorities have effectively been inverted.
There is a relatively simple solution to avoid the problem of process inversion. If a process needs a lock on a resouce which is already locked by a lower-priority process, the waiting process temporarily "lends" its priority to the process which currently has access to the resource. In the situation described earlier, Phigh would increase the priority of Plow so that it would finish faster and release access to the system resource. After Plow releases the lock, its priority would decrease to its original value.
Realtime scheduling is an alternative scheduling philosophy which is stricter than a generic priority scheduler, and simpler in many ways. With realtime scheduling, predictability trumps performance.
With a hard realtime scheduler, deadlines that processes set for acquiring a resource or task completion cannot be missed. Usually caches are disabled in such a system to eliminate problems with data synchronization among processes. Polling, instead of interrupts, are used to guarantee execution order. Examples of systems which use hard realtime scheduling are nuclear power plants and brake-control software in a car. The reason these particular types of systems require hard realtime are because the consistency of execution is paramount. If a system checking the temperature of a nuclear reactor needs to wait for another process and gets starved or locked, the temperature could reach a critical level without alerting the operators and the plant could fail and leak radiation into the atmosphere. Obviously this is unnacceptable in any capacity so the system needs to be designed around the ability to consistently control the scheduling of processes.
A soft realtime scheduler is not as strict. Performance is more important than with hard realtime scheduling, and some deadlines can be missed if there is currently too much work to be done in the system. Examples of systems which use soft realtime scheduling are: a video player, which may drop frames if there is not enough CPU access to process them; and a rate-monotonic web server which only allows a certain percentage of CPU time to each user.
A modern computer has multiple CPUs running many processes with multiple threads. Synchronization becomes a major issue when threads need to coordinate actions in a shared address space. If two threads store data in the same location, the opportunities for race conditions are rampant. Here is some example C code for accessing a simple bank account which will illustrate the problem of data synchronization:
Besides the problems with overflow and underflow of the account balance, this simplified example provides an opportunity for a race condition. Suppose thread 1 and thread 2 both want to make a deposit. If they both call the deposit() function at the same time, both threads will load the balance variable into a register, add the amount, and store the value back into memory. Because they both loaded the balance with the same initial value, the final value of the balance variable in memory will be the result of the last thread's addition operation. Only one of the operations will have been effective.
A robust solution to the problem of thread synchronization must properly synchronize data in shared memory, provide for high CPU utilization such that the time waiting for resources is minimized, and should be as clear and simple as possible.
There are two main concepts which must be implemented robustly from the user's perspective. The first is sequence coordination; two tasks which are requested in a certain order must complete in the same order (i.e. "X must finish before Y"). The second is isolation; if two tasks which read or write from shared data are running simultaneously, the data operations must not interfere with one other (i.e. "X and Y must not interfere with one another").
In a general sense, the goal of thread synchronization is serializability; that is, we want the system to be consistent with a single sequential abstract machine. Another important notion is that of observability; that is, what part of the system can we see? The internal implementation of data synchronization in a system may be complex with parallel execution and intermediate states, but the implementation is correct if the system behaves exactly as expected from the user's perspective.
To eliminate the problem that occurs with the shared account balance variable in the above example code, some type of exclusive resource access must be enforced. One obvious solution is to introduce the notion of a critical section of code; that is, a (preferably small) sequential set of instructions where at most one thread's instruction pointer is located at any given time. To implement a critical section, an abstract lock called a mutex (MUTual EXclusion) is used. The following is an incomplete but illustrative example of mutex primitives.
This is known as a spin lock, since a process that calls lock() must wait (or spin) until the lock is available. To improve the previous bank account example, we can add a mutex and use the lock() and unlock() primitives to manage access to the account balance variable.
Note that a critical section has been created between the lock() and unlock() calls in each function, protecting the operation that affects the balance variable. If one thread is currently performing an account operation and another thread calls deposit() or withdraw(), the thread will busy-wait until the first thread is done and the lock is available. However, these mutex primitives in themselves still do not eliminate all data synchronization problems. Consider the case when the lock is available and two threads call lock() simultaneously. It is possible for both threads to acquire the lock and then perform data operations that will conflict. This situation will be rectified in the next set of lecture notes.