CPU Scheduling

Introduction to multiprogramming

In the early days of computer science, a computer could run only one program at a time. Punch card instructions or instructions given with various electronic switches were considered to execute a given set of instructions, one after another. With the development of technology, computers and computer science was even introduced to general public. Interactive operating systems and easy to understand application software were necessary to make computer easy to use. However, this was not possible with the limitation of only executing single program at a time. Interactive, user-friendly operating systems and such applications required to run interdependently. So that multiprogramming concept was introduced. With multiprogramming it was possible to run multiple programs at a time in a single computer. Today, most of the general computers use multiprogramming and most of the operating systems and applications software are designed to run on such systems.

Why do we need CPU scheduling?

Though, it is possible to run multiple programs simultaneously using multiprogramming, CPU can only execute single instruction at a time. Because of this limit, only a single process or an instance of software can get the control of CPU for its execution. Instructions of this process will be continuously executed by the CPU blocking other processes from being executed. This problem will in turn hide advantages of multiprogramming concept.

In order to solve this problem and to keep multiprogramming concept active, it is necessary to share the CPU among various available processes. Each process should get a chance of being executed or getting the control of CPU. In order to achieve this, execution of processes should be scheduled properly. There are number of algorithms used to schedule processes and these scheduling mechanisms can be divided into two categories, namely “Preemptive scheduling” and “Non-preemptive scheduling”.

* Non-preemptive scheduling gives the control of CPU to a single process. Control is not given to another process until already allocated process completes execution.
* Preemptive scheduling uses a prioritization concept. Processes are prioritizes depending on various factors and the process which has highest priority is given the control of CPU. If a new process with higher priority arrive ready-list, process on processor should be removed and the new process should be given the chance of being executed.

There are number of scheduling algorithms used with multiprogramming systems. These scheduling algorithms will be discussed in next section. However, all these scheduling algorithms share common set of goals. Each algorithm achieves below mentioned goals in different levels.

* Maximize – CPU Utilization/Efficiency: keep the CPU busy 100% of the time with useful work
* Maximize – Throughput: maximize the number of jobs processed per hour
* Minimize – Turnaround time: time taken from the time of submission to the time of completion
* Minimize – Waiting time: sum of times spent in ready queue
* Minimize – Response Time: time taken from submission till the first response is produced
* Maximize – Fairness: make sure each process gets a fair share of the CPU

First-In-First-Out (FIFO) scheduling algorithm

First-In-First-Out scheduling algorithm is a non-preemptive algorithm which means it does not pass control to another process until the process that is allocated with CPU completes execution. First-In-First-Out algorithm can be illustrated as shown below:

As the name suggests, the first process that appear in the ready list will be executed first and next process in the queue is considered only after completely executing the current process. Once a process is placed in the ready list, it is not possible to place another process in front of it.

Consider an example of three processes, Process1 with execution time of 10 units, Process2 with execution time of 3 units and Process3 with execution time of 7units. As First-In-First-Out is a non-preemptive algorithm, Gantt chart for three processes will look like below.

Switching between processes or context switching occurs only when a process is terminated. Ready list will not be reorganized from time to time, so that scheduling overhead is low. Throughput is at a lower rate because a large process might hold the CPU for a longer time. Waiting time is high because of the same reason mentioned before. Turnaround time for process 1 is 10, for process 2 it is 13 and for process 3 it is 20. Average turnaround time is 14.3 in this example (( 10 + 13 + 20 ) / 3) without considering time taken for context switching. Turnaround time is low with First-In-First-Out scheduling because a process is continuously executed until the termination. There is no starvation associated with First-In-First-Out scheduling because each process will certainly reach processors, however long processes can hold processor for a long time making it an unfair algorithm.

First-In-First-Out algorithm is easy to implement. It is possible to avoid large processes from holding the CPU longer by using time slices which define amount of time a process can run without a context switch. This is implemented in Round Robin scheduling algorithm.

Round Robin scheduling algorithm.

Round Robin scheduling algorithm is a preemptive scheduler that acts mostly same as First-In-First-Out algorithm, but a limited time called “time slice” is introduced, which define the maximum time a process can consume CPU without a context switch. Each process consume the CPU for a defined time slice, if process is not terminated within the time slice, it is placed back at the end of the ready list.

Consider out previous example which was Process1 with execution time of 10 units, Process2 with execution time of 3 units and Process3 with execution time of 7units. We”™ll consider time unit as milliseconds for this example, though it is not true in real life situations. If time slice was 2ms long, Gantt chat will look like what is shown below:

Context switching will occurs once per time slice or when a process is terminated and ready list will not be reorganized but it will be altered frequently. So that scheduling overhead is higher than it is with First-In-First-Out algorithm. Wait time is minimized because there is a time slice. Large processes cannot hold CPU longer than the defined time slice. But turnaround time for process 1 in Round Robin algorithm is 20, for process 2 it is 9 and for process 3 it is 18. So that, average turnaround time is 15.6. Average turnaround time is low with Round Robin scheduling but turnaround time of individual process is larger than it is with First-In-First-Out algorithm. There is not starvation associated with Round Robin scheduling because each process will certainly reach processors, however long processes cannot hold processor for a long time, so Round Robin algorithm can be considered as a fair algorithm.

Shortest Job First (SJB)

All previously discussed algorithms allocated CPU for processes that were stored in q queue. New additions to this ready queue were added to the end of the list and they had to wait till proceeding processes complete execution. But when it comes to Shortest Job First scheduling algorithm, processes are sorted in the size of the process. Consider below image:

All the processes are arranged in the queue by the size of the process. In above image a new, smaller process arrives the ready list. So that, currently executing process will be placed in relevant place of the ready list and newly arrived, smallest process will be executed.

Previous example of three processes will be executed in below manner when used with non-preemptive Shortest Job First algorithm.

Context switching will occurs only when process is terminated and ready list will be reorganized whenever a new process arrives the list. Also calculating how long a process is going to run is a complex process and calculation is not guaranteed to be correct. So that scheduling overhead is higher than it is with previously discussed algorithms. But turnaround time for process 1 in Shortest Job First algorithm is 20, for process 2 it is 3 and for process 3 it is 10. So that, average turnaround time is 11. Average turnaround time is low with Shortest Job First and also shortest processes will complete execution quickly. So that, throughput is higher. There is a starvation associated with Shortest Job First scheduling because large process will have to wait for a long time to get executed. Sometimes, if small processes continuously reach the ready queue, large processes will not get a chance of reaching processor. Because of this, this algorithm cannot be considered as fair algorithm.

Priority Based Scheduling (PBS)

In priority based scheduling, each process is given a priority and the ready queue is ordered by this assigned priority. By using this algorithm it is possible to give priority to important processes. Round robin algorithm is used in combine with this algorithm. When a process exceeds allocated time slice, it is placed after all the items in the queue which has equal priority.

Consider the previous example scenario. Imagine that Process 3 has the highest priority, process 1 has medium priority and process 2 has lowest priority. Gantt chart for processes will look like shown below.

Ready list will be reorganized depending on the priority, whenever a new process arrives the list. So that scheduling overhead is higher and Round Robin algorithm. Wait time is minimized because there is a time slice. Large processes cannot hold CPU longer than the defined time slice. But turnaround time for process 1 in Priority Based Scheduling algorithm is 20, for process 2 it is 11 and for process 3 it is 16. So that, average turnaround time is 15.6. There is a starvation associated with Priority Based Scheduling scheduling because process with low priority might not get a chance to reach CPU. A large process with a higher priority might continuously consume CPU for a long time even when time slices are introduced. To avoid this priority of process is decremented in each time it gets executed.

Multi-Level Feedback Queue

In Multi-Level Feedback Queue algorithm, several queues are maintained in the scheduler. Each queue has different priority and may use different algorithms. Because of that, this algorithm can use advantages of several scheduling algorithms. Selection of algorithms suitable for various queues and purposes depend on various facts. These will be discussed below.

Choosing a Scheduling Algorithm

It is not possible to say that a particular scheduling algorithm is best in every occasion. Selection of algorithm should depend upon the situation or upon the requirement of system. Each algorithm achieve goals of a scheduling algorithm which are CPU Utilization/Efficiency,Throughput,Turnaround time, Waiting time,Response Time and Fairness in various levels. Achievement levels of these algorithms were discussed before. Time critical systems should use scheduling algorithms with less turnaround time, waiting time and response time but systems that are not required to handle critical operations can use simple algorithms which are easy to implement.

As an example consider developing a interactive operating system. If First-In-First-Out algorithm is used with this sort of a operating system, users will have to wait for all the processes to complete execution to interact with operating system. Processes running upon the operating system will hold the control of CPU and operating system will get the control back only when all the processes complete execution. First-In-First-Out algorithm could be used with a command lined based operating system because once users key a command, OS might not require control back until completions of process.

There are some real-time computer systems which perform critical operations like medical surgeries. Delay of few seconds of such a system might be deadly mistake. So that scheduling system should have a higher CPU utilization, high throughput, less turnaround time and deadline handling.

However consider a batch processing system where users submit various queries. If the system is user dependent, designers can allow first request to be served first. So that a fair service can be given to all the users. However as throughput of this algorithm is low, this method can only be applied to a system where response time is not critical. Consider a banking system where number of users query for information. If two users are not allowed to perform a query simultaneously it is possible to use First-In-First-Out algorithm in the end system. However if requests sent by administration should be given a higher priority it is possible to use Priority Based Scheduling.

Modern operating systems might have to handle various types of operations, among these operations there could tasks that should be performed in given order. Also there could be operations that should be performed quickly. It is not possible to mention clearly that a certain algorithm is best for an modern operating system. In such case Multi-Level Feedback Queues are used. Windows NT-based operating systems, Mac OS X, Linux and Solaris use multilevel feedback queues in scheduling process, so that these operating systems can use advantages of several scheduling algorithms.

It is clear that selection of a scheduling algorithms is dependent on the situation and that it is required to consider CPU Utilization,Throughput,Turnaround time, Waiting time, Response Time and Fairness of algorithms, in such selection.

Share

2 comments on “CPU Scheduling

  1. Hishan Melanga August 7, 2011 10:16 AM

    Thanks Ayoma for the great help. This is really good. It’s easy to understand.

  2. Pingback: suresh raman

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>