Scheduling Algorithms
CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. There are many different CPU scheduling algorithms. In this section, we describe several of them.
The simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.
The average waiting time under the FCFS policy, is often quite long. Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds:
Process Burst Time
PI 24
P2 3
P3 3
If the processes arrive in the order PI, P2, P3, and are served in FCFS order we get the result shown as in the Gantt chart.
P1 P2 P3
0 24 27 30
The average waiting time is 0+24+27 = 17 millisec
3
If the processes arrive in the order P2,P3,P1 then the will be as shown in the following chart
P2 P3 P1
0 3 6 30
The average waiting time is 0+3+6 = 3 millisec. Thus the average waiting time under
3
FCFS policy is generally not minimal.
The FCFS algorithm is non preemtive, ie once the CPU has been allocated to a process that process keeps the CPU until it releases the CPU either by terminating or by requesting I/O.
Another approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This algorithm associates with each process the length of the process's next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie.
Consider the following set of processes, with the length of the CPU burst given in milliseconds:
Process Burst Time
PI 6
P2 8
P3 7
P4 3
Using SJF scheduling, we would schedule these processes according to the following Gantt chart
P4 P1 P3 P2
0 3 9 16 24
The average waiting time is 0+3+9+16 = 7 millisec
4
If we use FCFS algorithm, then the average waiting time would be
0+6+14+21 = 10.25 millisec
4
The real difficulty with the SJF algorithm is knowing the length of the next CPU request. For long-term (job) scheduling in a batch system, we can use as the length the process time limit that a user specifies when he submits the job. Thus, users are motivated to estimate the process time limit accurately, since a lower value may mean faster response. SJF scheduling is used frequently in long-term scheduling
The SJF algorithm can be either preemptive or non preemptive. The choice arises when a new process arrives at the ready queue while a previous process is still executing. The next CPU burst of the newly arrived process may be shorter than what is left of the currently executing process. A preemptive SJF algorithm will preempt the currently executing process, whereas a non preemptive SJF algorithm will allow the currently running process to finish its CPU burst. Preemptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling.
The SJF algorithm is a special case of the general priority scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa.
Priorities are generally indicated by some fixed range of numbers, such as 0 to 7. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. We assume that low numbers represent high priority.
Consider the following set of processes, assumed to have arrived at time 0, in the order P1, P2, P3,P4, P5, with the length of the CPU burst given in milliseconds:
Process Burst Time Priority
PI 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
P2 P5 P1 P3 P4
0 1 6 16 18 19
The average waiting time 0+1+6+16+18 = 8.2 millisec
5
Priorities can be defined either internally or externally. Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. For example, time limits, memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities. External priorities are set by criteria outside the operating system, such as the importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other, often political factors.
Priority scheduling can be either preemptive or non preemptive. When a process arrives at the ready queue, its priority is compared with the priority of the currently running process. A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. A non preemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.
A major problem with priority scheduling algorithms is indefinite blocking, or starvation. A process that is ready to run but waiting for the CPU can be considered blocked. A priority scheduling algorithm can leave some low priority processes waiting indefinitely for the CPU.
A solution to the problem of indefinite blockage of low-priority processes is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.
The round-robin (RR) scheduling algorithm is designed especially for timesharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a time slice, is defined. A time slice is generally from 10 to 100 milliseconds. The ready queue is treated as a circular queue.
The average waiting time under the RR policy is often long. Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds and time slice is 4 millisec.
Process Burst time
P1 24
P2 3
P3 3
The Gantt chart representation will be as follows:
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30
The average waiting time is 6+4+7 = 5.66 millisec
3
The performance of the RR algorithm depends heavily on the size of the time slice. At one extreme, if the time slice is extremely large, the RR policy is the same as the FCFS policy. If the time slice is extremely small (say, 1 millisecond), the RR approach is called processor sharing.
The time slice should be large with respect to the context switch time. Turnaround time also depends on the size of the time slice.
Another class of scheduling algorithms has been created for situations in which processes are easily classified into different groups. For example, a common division is made between foreground (interactive) processes and background (batch) processes. These two types of processes have different response-time requirements. Foreground processes may have priority over background processes.
A multilevel queue scheduling algorithm partitions the ready queue into several separate queues. The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority, or process type. Each queue has its own scheduling algorithm.
The foreground queue might be scheduled by an RR algorithm, while the background queue is scheduled by an FCFS algorithm. In addition, there must be scheduling among the queues, which is commonly implemented as fixed-priority preemptive scheduling.
Consider a multilevel queue scheduling algorithm with 5 queues
system processes
interactive processes
interactive editing processes
batch processes
Highest priority
Lowest priority
Each queue has absolute priority over lower-priority queues. No process in the batch queue could run unless the queues for system processes, interactive processes, and interactive editing processes were all empty. If an interactive editing process entered the ready queue while a batch process was running, the batch process would be preempted.
Another possibility is to time-slice among the queues. Here, each queue gets a certain portion of the CPU time, which it can then schedule among its various processes.
The multilevel feedback-queue scheduling algorithm allows a process to move between queues. If a process uses too much CPU time it will be moved to a lower-priority queue. This scheme leaves I/O-bound and interactive processes in the higher-priority queues. A process that waits too long in a lower-priority queue may be moved to a higher-priority
queue. This form of aging prevents starvation.
Consider a multilevel feedback-queue scheduler with three queues, numbered from 0 to 2. The scheduler first executes all processes in queue 0. Only when queue 0 is empty will it execute processes in queue 1. Similarly, processes in queue 2 will only be executed if queues 0 and 1 are empty. A process that arrives for queue 1 will preempt a process in
queue 2. A process in queue 1 will in turn be preempted by a process arriving for queue 0.
Multiple Processor Scheduling
So far we focus on the problem of scheduling the CPU in a system with a single processor. If multiple CPU are available the scheduling problem is more complex. A system where the processors are identical is called a homogeneous system and any available processor can be used to run any process in the queue. A system where the processors are different in terms of their functionality is called a heterogeneous system and only programs complied for a given processor could run on that processor.
Even within a homogeneous multiprocessor, there are limitations on scheduling. Consider a system with I/O device attach to a bus of one processor. Process wishing to use that device must be scheduled to run on that processor. If several identical processors are available then load sharing can occur, we use a common ready queue