OS1: Process Management – Unit 4: CPU Scheduling

Ontology: Basic Concepts

The objective of multiprogramming is to have some process running at times, in order to maximize CPU utilization. In a uniprocessor system, only one process may run at a time; any other processes must wait until the CPU is free and can be rescheduled.

The idea of multiprogramming is relatively simple. A process is executed until it must wait, typically for the completion of some I/O request. In a simple computer system, the

CPU would then sit idle. All this waiting time is wasted. With multiprogramming, we try to use this time productively. Several processes are kept in memory at one time. When one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. This pattern continues.

Scheduling is fundamental to operating system function. Almost all computer resources are scheduled before use. The CPU is, of course, one of the primary computer resources.

Thus, its scheduling is central to operating system design.

3.1.1 CPU-I/O Burst Cycle

The success of CPU scheduling depends on the following observed property of processes.

Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, then another CPU burst, then another I/O burst, and so on. Eventually, the last CPU burst will end with system request to terminate execution, rather than with another I/O burst (see Figure 3.1)

The duration of these CPU burst have been extensively measured. Although they vary greatly by process and by computer, they tend to have a frequency curve similar to that shown in Figure 3.2. The curve is generally characterized as exponential or hyper- exponential, with many short CPU bursts and a few long CPU bursts. An I/O-bound program would typically have many very short CPU bursts while a CPU-bound program might have a few very long CPU bursts. This distribution can help us select an appropriate CPU-scheduling algorithm.

Figure 3.1 Alternating Sequence of CPU and I/O Bursts of Two Processes.

 Figure 3.2: Histogram of CPU-Bursts Times

3.3.1 CPU Scheduler

Whenever the CPU becomes idle, the operating system must select on the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler (or CPU scheduler). The scheduler selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.

The ready queue is not necessarily a first-in, first-out (FIFO) queue. As you shall see, when we consider the various scheduling algorithms, a ready queue may be implemented as a FIFO queue, a priority queue, a tree, or simply an ordered linked list. Conceptually, however, all the processes in the ready queue are lined up waiting for a chance to run on the CPU. The records in the queues are generally process control blocks (PCBs) of the processes.

3.3.2 Preemptive Scheduling and Non-preemptive Scheduling

CPU scheduling decisions may take place under the following circumstances:

1. When a process switches from the running state to the waiting state (for example, I/O request, or invocation of wait for the termination of one of the child processes)
2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)
3. When a process switches from the waiting state to the ready state ( for example, completion of I/O)
4. When a process terminates

In circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution. There is a choice, however, in circumstances 2 and 3.

When scheduling takes place only under circumstances 1 and 4, we say the scheduling scheme is non preemptive. Otherwise, the scheduling scheme is preemptive. Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. This scheduling method is used by Microsoft Windows 3.1 operating system. It is the only method that can be used on certain hardware platforms, because it does not require the special hardware needed for preemptive scheduling.

Some of the disadvantages of preemptive scheduling are that:

• It incurs a cost
• It also has an effect on the design of the operating system kernel.

3.1.4 Dispatcher

Another component involved in the CPU scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function includes:

• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program.

The dispatcher should be as fast as possible, given that it is invoked during every process switch. The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency.

3.2

Scheduling Criteria

Different CPU-scheduling algorithms have different properties and may favour one class of processes over another. In choosing which algorithm to use in a particular situation, we must consider the properties of the various algorithms.

Many criteria have been suggested for comparing CPU-scheduling algorithms. The characteristics used for comparison can make a substantial difference in the determination of the best algorithm. The criteria include the following:

CPU Utilization: We want to keep the CPU as busy as possible. CPU utilization may range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).

Throughput: if the CPU is busy executing processes, then work is being done. One measure of work is the number of processes completed per time unit, called throughput.

For long processes, this rate may be 1 process per hour or 10 processes per second for short transactions.

Turnaround Time: This is the interval from the time of submission of a process to the time of completion. It is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU and doing I/O.

Waiting Time: The CPU scheduling algorithm does not affect the amount of time during which a process executes or does I/O. It affects only the amount of time that a process spends waiting in the ready queue. Waiting time is, therefore, the sum of the periods spent waiting in the ready queue.

Response Time: This is the amount of time it takes to start responding but not the time it takes to output the response. i.e. the time from the submission of a request until the first response is produced.

We usually want to maximize CPU utilization and throughput, and to minimize turnaround time, waiting time, and response time. In most cases, we optimize the average measure. However, in some circumstances we want to optimize the minimum or maximum values, rather than the average. For instance, to guarantee that all users get good service, we may want to minimize the maximum response time.

3.3

Scheduling Algorithms

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. In this section, we describe many CPU-scheduling algorithms that exist.

3.3.1 First-Come, First Served (FCFS) Scheduling

This is the simplest CPU-scheduling algorithm. In 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 the removed from the queue. The code for FCFS scheduling is simple to write.

The average waiting time under FCFS policy is often quite long.

The average waiting time is now (6 + 0 + 3)/3 = 3 milliseconds. This reduction is substantial. Therefore, the average waiting time under FCFS policy is generally not minimal, and may vary substantially if the process CPU-burst times vary greatly.

FCFS scheduling algorithm may lead to convoy effect whereby all other processes wait for one big process to get off the CPU. This results in lower CPU and device utilization.

FCFS scheduling algorithm is non-preemptive.

3.3.2 Shortest-Job-First (SJF) Scheduling

This algorithm associates with each process the length of the latter’s next CPU burst.

When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie.

Example 3.2 Consider the following set of processes that arrive at time 0, with the length of the CPU-burst time given in milliseconds:

The waiting time is 3 milliseconds for process P1, 16 milliseconds for process P2, 9 milliseconds for process P3, and 0 milliseconds for process P4. Hence the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds. If we were using FCFS scheduling scheme, then the average waiting time would be 10.25 milliseconds.

The SJF scheduling algorithm is provably optimal because it gives the minimum average waiting time for a given set of processes. However, it cannot be implemented at the level of short-term CPU scheduling because there is no way to know the length of the next

CPU burst.

SJF algorithm may be either preemptive or non preemptive. The choice arises when a new process arrives at the ready queue while a previous process is executing. The new process may have a shorter next CPU burst than what is left of the current executing process. A preemptive SJF algorithm will pre-empt the current executing process, whereas a non preemptive SJF algorithm will allow the currently running process to finish its CPU burst. Preemptive SJF scheduling is sometime called shortest-remaining-time-first scheduling.

Example 3.3: Consider the following four processes, with length of the CPU-burst given in milliseconds:

Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives at time 1. The remaining time for process P1 (7 milliseconds) is larger than the time required by process P2 (4 milliseconds), so process P1 is pre-empted, and process P2 is scheduled. The average waiting time for this example is ((10 – 1) + (1 – 1) + (17 – 2) + (5

– 3)/4 = 26/4 = 6.5 milliseconds.

A non preemptive SJF scheduling would result in an average waiting time of 7.75 milliseconds.

3.3.3 Priority Scheduling

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.

An SJF algorithm is therefore simply a priority algorithm where the priority is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority and vice versa.

Priority is expressed in terms of fixed range number such as 0 to 10. however there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority while others use low numbers for high priority. But in this course, we will use low numbers to represent high priority.

Example 3.4: Consider the following set of processes, assumed to have arrived at time 0, in the order P1, P2, …, P5, with the length of the CPU-burst time given in milliseconds:

The average waiting time is 8.2 milliseconds.

Priorities can be defined either internally or externally. Internally defined priorities use measurable quantity (ies) such as time limits, memory requirements, etc. to compute the priority of a process. External priorities are set by criteria that are external to the operating system such as importance of the process, amount being paid for use of the compute, the owner of the process, and other (political) factors.

Priority scheduling may be either preemptive or non preemptive. When a process arrives at the ready queue, its priority is compared with that 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 that of the currently running process. A non preemptive priority-scheduling algorithm will simply put the new process at the head of the ready queue.

The major disadvantage of priority-scheduling algorithms is indefinite blocking or starvation. A situation whereby low priority processes indefinitely wait for the CPU because of a steady stream of higher-priority processes.

A solution to indefinite blocking 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.

3.3.4 Round-Robin (RR) Scheduling

Round-robin (RR) is one of the simplest scheduling algorithms for processes in an operating system. It assigns time slices to each process in equal portions and in circular order, handling all processes without priority. Round-robin scheduling is both simple and easy to implement, and starvation-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks.

The name of the algorithm comes from the round-robin principle known from other fields, where each person takes an equal share of something in turn.

It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a time quantum (or time slice), is defined. A time quantum is generally from 10 – 100 milliseconds. The ready queue is treated as a circular queue. The

CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

To implement the RR scheduling, we keep the ready queue as a FIFO queue of processes.

New processes are added to the tail of the queue. The CPU scheduler picks from the head of the queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.

One of two things will then happen. The process may have a CPU burst of less than one time quantum. In which case the process itself releases the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed, and the process will be put at the tail of the ready queue. The scheduler then selects the next process in the ready queue.

The average waiting time under RR policy is often quite long.

Example 3.5: Consider the following set of processes, assumed to have arrived at time 0, in the order P1, P2, P3, with the length of the CPU-burst time given in milliseconds:

The average waiting time is 17/3 = 5.66 milliseconds.

In RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in a row. If a process’ CPU burst exceeds 1 time quantum, that process is preempted and is put back in the ready queue. The RR scheduling algorithm is preemptive.

3.3.5 Multilevel Queue (MLQ) Scheduling

In this scheduling algorithm, processes are classified into different groups. For instance, a common division is made between foreground (or interactive) processes and background (or batch) processes. Therefore the ready queue is partitioned 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, etc. Each queue has its own scheduling algorithm. E.g. foreground might use RR while background might use

FCFS.

In addition, there must be scheduling among the queues which is usually implemented as fixed priority preemptive scheduling. For example foreground queue may have absolute priority over background queue. Therefore no process in the background queue could run except the foreground queues are empty. If a process entered the foreground queue while a process from the background queue is running, the background queue process will be preempted.

This will lead to possible starvation for the background queue process. To address this problem, time slice can be used between the queue. Each queue gets a certain portion of the CPU time which it an then schedule among the various processes in its queue. For instance, in the background – foreground queue example, the foreground queue can be given 80% of the CPU time for RR scheduling among its processes, whereas the background queue receives 20% of the CPU to give to its processes in FCFS manner.

Figure 3.3: Multilevel Queue Scheduling

3.3.6 Multilevel Feedback Queue (MLFQ) Scheduling

Similar to MLQ, but here processes can move between the queues. The idea is to separate processes with different CPU-burst characteristics (i.e., based on their “behavior”). A process that uses too much CPU time is degraded to a lower-priority queue, a process that waits too long is upgraded to a higher-priority queue. This is a kind of aging that prevents starvation.

In general, MLFQ scheduler is defined by the following parameters:

• Number of queues
• Scheduling algorithms for each queue
• Criteria for determining when to upgrade a process to a higher-priority queue
• Criteria for determining when to demote a process to a lower-priority queue
• The criteria for determining which queue a process will enter when that process needs service.

MLFQ is the most general scheme, and also the most complex.

Example 3.6: Consider a MLFQ scheduler with three queues, Q0 with time quantum 8 milliseconds, Q1 with time quantum 16 milliseconds and Q2 on FCFS basis only when queues Q0 and Q1 are empty.

In this scheduling algorithm a new job enters queue Q0 served by FCFS. Then job receives 8 milliseconds. If not finished in 8 milliseconds, it is moved to Q1. At Q1 job served by FCFS. It then receives 16 milliseconds. If not completed, it is preempted and moved to Q2 where it is served in FCFS order with any CPU cycles left over from queues Q0 and Q1.

Figure 3.4: Multilevel Feedback Queues

3.4

Multiple-Processor Scheduling

Our discussion in this unit so far has focused on the problems of scheduling the CPU in a system with a single processor. If multiple CPUs are available, the scheduling problem is correspondingly more complex. Many possibilities have been tried but as you saw with single processor CPU scheduling, there is no one best solution. In his section we will briefly discuss some of the issues concerning multiple-processor scheduling.

If several identical processors are available, then load sharing can occur. It would be possible to provide a separate queue for each processor. In this case however, one processor could be idle, with an empty queue, while another processor could be very busy. To avoid such situation, we can use a common ready queue. All processes go into one queue and are scheduled onto any available processor.

In such a scheme, one of two scheduling approaches may be used. In one approach, each processor is self-scheduling. Each processor examines the common ready queue and selects a process to execute. However, we must ensure that no two processors choose the same process and that processes are not lost from the queue. The second approach avoids this problem by appointing one processor as scheduler for the other processors, thereby creating a master-slave structure.

Some systems go a step further by having all scheduling decisions, I/O processing, and other system activities handled by one single processor – the master server. The other processors only execute user codes.

SELF ASSESSMENT TEST

Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made.

1. What is the average turnaround time for these processes with the FCFS scheduling algorithm?
2. What is the average turnaround time for these processes with the SJF scheduling algorithm?
3. The SJF is supposed to improve performance, but not ice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future knowledge scheduling.

4.0

Conclusion

In this unit, you have been taken through the various CPU scheduling algorithms. It is our belief that by now you can select a scheduling algorithm that will be optimal for a particular situation/system. However, there are formal techniques for determining the best scheduling algorithm for a particular situation and this we will discuss this in this next unit.