6 CPU Scheduling – III

Mary Anitha Rajam

 

9.1 Introduction

 

CPU scheduling is used in operating systems to maximise CPU utilization and to provide multiple users with a feel that they are the sole users of the system. In earlier modules, we learnt the working of First Come First Served, Shortest Job First (SJF), priority and round robin scheduling algorithms. In this module, we will understand the working of multilevel queue and multilevel feedback queue CPU scheduling algorithm, the issues in multiple-processor scheduling, real-time scheduling and understand how CPU scheduling algorithms are evaluated.

 

9.2 Multilevel Queue Scheduling 

 

In multilevel queue scheduling, the ready queue is partitioned into separate queues as shown i n Figure 9.1. Different categories of processes are added to different queues. For example, the processes are categorized as foreground (interactive), background (batch) processes, interactive editing processes, batch processes and student processes. Each category of process is placed in a different queue. For example, foreground processes are placed in one queue and background processes are placed in a separate queue. The response time requirements are also different for foreground and background processes. Foreground processes need a quicker response compared to background processes. Thus, a process is permanently assigned to a queue based on the property of the process.

 

Each queue can have its own scheduling algorithm. For example, for the queue corresponding to foreground processes, the round robin scheduling algorithm may be used and for background processes, FCFS may be used. Among the queues, scheduling must be done. Fixed priority preemptive scheduling can be used for choosing one of the queues among the different queues available. For example, higher priority may be given to the queue with foreground processes. That is, all processes from the queue with foreground processes are served first; then the queue with background processes is served next. As is the case with any priority scheduling, there is a possibility of starvation for processes present in the queue with lower priority.

 

Rather than using priority to schedule between the queues, different time slices can be assigned to different queues. Each queue gets a certain amount of CPU time, which it can schedule among its processes; that is, 80% to foreground in RR, 20% to background in FCFS.

Fig. 9.1 Multilevel Queue Scheduling (Source: [1])

 

9.3 Multilevel Feedback Queue Scheduling 

Fig. 9.2 Multilevel Feedback Queue (Source: [1])

 

In multilevel queue scheduling, the processes do not move between the queues. Once a process is assigned to a queue, it continues to be i n the same queue till its CPU burst is completed. But, in multilevel feedback queue scheduling, a process can move between the various queues. This movement between the various queues is done to separate processes with different CPU-burst characteristics. Any process that spends too much CPU burst time is moved to a lower priority queue. Hence, I/O bound and interactive processes get a higher priority queue. Processes that are in a lower priority queue for a long time are moved to a higher priority queue. Aging can be implemented this way and prevents starvation. Multi level feedback queue scheduling is the most general CPU scheduling algorithm.

 

Consider the example of a multilevel feedback queue as shown in Figure 9.2. There are three queues Q0 using round robin scheduling with a time quantum of 8 milliseconds, Q1 using round robin scheduling with a time quantum of 16 milliseconds and Q2 with FCFS scheduling. Any new job is first assigned to the queue Q0. When a process in queue Q0 gets the CPU, it is given a time slice of 8 milliseconds. If the process does not finish its CPU burst in 8 milliseconds, it is moved to queue Q1. In queue Q1, the process again is served FCFS and receives 16 additional milliseconds of CPU time. If it still does not complete, it is preempted and moved to queue Q2. Only if there are no processes i n the first queue, processes i n the second queue get the CPU and so on. Thus, if a process has a shorter CPU burst, it can complete its CPU burst even while i n the first queue. Longer processes are moved to other queues and thus get a lower priority.

 

Multilevel-feedback-queue scheduler is defi ned by the followi ng parameters:

 

–  number of queues

–  scheduling algorithms for each queue

–  method used to determine when to upgrade a process

–  method used to determine when to demote a process

–  method used to determine which queue a process will enter when that process needs service

 

9.4 Multiple-Processor Scheduling 

 

All the CPU scheduling algorithms that we have discussed till now are used in systems that have a single processor. CPU scheduling is more complex when multiple CPUs are available. In this section, we will look at different issues related to multi-processor scheduling. In a multiprocessor system, when all the processors are identical, the system is homogeneous. When all the processors are not similar, the system is a heterogeneous system.

 

When the system is homogeneous, load sharing can be done. Separate ready queues can be maintained for each processor. Processes are added to the ready queues as and when they arrive. Since there are different ready queues, if shorter processes get added to a particular queue, then that queue may become empty quickly. Hence, it is possible for one processor to be idle, while another is busy. This problem can be solved by using a common ready queue.

 

When a common ready queue is used, one of the following two scheduling approaches may be used. In one approach, each processor is self-scheduling. That is, each processor picks a process from the ready queue. Here, all the processors are trying to modify a single data structure. Hence , it should be ensured that no two processors pick the same process. Also, while many processors are modifying the ready queue at the same time, no process should be lost. In the second approach, one processor acts as a scheduler for the other processors. This creates a master–slave approach. In some systems, this is further extended by having all scheduling decisions, I/O processing and other system–related activities handled by one single processor. The other processors only execute code. This is called asymmetric multiprocessing.

 

9.5 Real-Time Scheduling 

 

Real-time systems are of two types: hard real-time systems and soft real-time systems. In hard real-time systems, it is required to complete a critical task within a guaranteed amount of time. A process is usually submitted along with the time within which it should be completed. The scheduler admits the process only if the time constraint can be met or else rejects. This is known as resource reservation. For this to be accomplished, the scheduler should know how long each type of OS function takes to perform. This kind of time guarantee is impossible in system with secondary storage or virtual memory. This is because we cannot guarantee how much amount of time a process may have to wait while accessing the secondary storage device. Disk I/O is always slow. Hence, hard real-time systems are composed of special-purpose software running on dedicated hardware.

 

In soft real-time systems, critical processes receive priority over other non-critical processes. Implementing soft real-time systems requires careful design of the scheduler and other aspects of the operating system. We will now discuss the issues related to soft real-time systems. In these systems, priority scheduling is used and real-time systems get the highest priority. The priority of real-time processes must not degrade over time. Also, aging is not allowed.

 

In soft real-time systems, the second criterion is that the dispatch latency must be small. The smaller the latency, the faster the real-time process can start executing once it can run. Suppose that a non-real-time process is currently using the CPU and a real-time process arrives. The non-real-time process must be preempted and the real-time process must be given the CPU. Thus, a context switch needs to happen. For this, the state of the non-real-time process must be saved and the state of the real-time process must be loaded. This takes some amount of time and contributes to the dispatch latency.

 

If the non-real-time process that is currently running is executing a system call, many operating systems are forced to wait for the system call to complete before a context switch. If the process is preempted while the execution of the system call has not yet completed, there may be inconsistent data structures that are being modified by the system call execution. If the system call takes a long time to complete, the dispatch latency increases. To keep the dispatch latency low, it may be necessary to allow system calls to be preemptible. This can be made possible by the insertion of preemption points i n long-duration system calls. The preemption points are points in the system call implementation where the data structures are consistent. At the preemption points, the operating system checks whether a high-priority process needs to be run. If there is a high-priority process waiting, then the low-priority process is preempted at this point, though it has not completed executing the system call. These preemption points can be placed only at safe locations – only when kernel data structures are not being modified.

 

The second possibility by which the dispatch latency can be reduced is by making the entire kernel preemptible. To make the entire kernel preemptible , all data structures of the kernel should be protected. That is, if there is some data structure that is being modified by the low-priority process, that data structure must be locked while the process is preempted. Now the issue is that, what happens if a high-priority process needs to access the same data structures locked by the low-priority process? The high-priority process has to wait for the low-priority process to finish. This is called priority inversion. Sometimes, it is possible that a chain of processes may be using resources needed by the high-priority process. This problem can be solved using the priority inheritance protocol, i n which all processes that use the resources needed by the high-priority process will inherit a high priority temporarily. Once finished, priority reverts to its original value

 

9.6   Algorithm Evaluation 

 

There are a number of CPU scheduling algorithms. How do we select a CPU scheduling algorithm for a particular system? The following subsections explain the different evaluation methods.

 

9.6.1  Deterministic modeling 

 

This method takes a particular predetermined workload and defines the performance of each algorithm for that workload. The performance can be evaluated using measures like CPU utilization, throughput, waiting time, turnaround time and so on. Based on the performance, the best CPU scheduling algorithm is selected. This method is simple and fast. It gives exact numbers allowing the algorithms to be compared . But, it requires too much exact knowledge to be useful.

 

9.6.2 Queuing models 

 

Processes that run on systems vary from day to day. There is no fixed set of processes and corresponding times that can be used for deterministic modeling. However, the distributions of CPU and I/O bursts can be obtained . Distribution of times when processes arrive i n the system is also given. The CPU is looked at as a server with its ready queue. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time and so on. This kind of study is called queuing-network analysis.

 

9.6.3 Simulations 

 

In this method, a model of the computer system is developed as a program. The major components of the computer system are represented by data structures. The clock is represented by a variable. As the clock variable’s value is incremented, the simulator modifies the system state to reflect the activities of the devices, processes, scheduler and so on. As the simulation executes, statistics indicating the performance of the algorithm are gathered and printed. Data to drive the simulation can be got using several ways. One method is to use a random-number generator to generate processes, CPU-burst times, arrivals, departures according to probability distributions. The second method is to use trace tapes. Trace tapes are created by monitoring a real system and these are then used to drive the simulation.

 

Simulations are used to get a more accurate evaluation of scheduling algorithms. But, simulations can be expensive as they require hours of computer time. Trace tapes require large amounts of storage space. Design, coding and debugging of the simulator is a major task.

 

9.6.4 Implementation

 

In this method, the scheduli ng algorithm is coded and is put in the OS to see how it works. The difficulty with this method is the cost of the approach. The expense incurred is not only i n coding the algorithm but also i n modifying the OS and other related data structures.

 

9.7 Summary

 

In this module, we learnt how multilevel queue scheduling and multilevel feedback queue scheduling algorithms work. We also learnt the different issues related to multiprocessor scheduling and real-time scheduling. The different ways i n which CPU scheduling algorithms can be evaluated were also discussed.

 

 

References

  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Sixth Edition, John Wiley & Sons Inc., 2003.
  2. Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
  3. Gary Nutt, “Operating Systems”, Third Edition, Pearson Education, 2009.
  4. William Stallings, “Operating Systems: Internals and Design Principles”, Seventh Edition, Pearson, 2012.