One of the most important functions assigned by an operating system is CPU scheduling because at a given time in a computer, many processes may be competing for CPU time. A modern processor might process instructions at very high speed, but how the operating system decides which of the processes that are ready to run should get the CPU, how long it should have the CPU, and when the CPU should be given to another process must be handled in a systematic manner. If there is no effective scheduling mechanism, then some programs might wait too long, interactive applications might become unresponsive, and the processor resources might be underutilized.
The principles and algorithms that operating systems use to organize the use of the processor are known as CPU scheduling. There are trade-offs among various algorithms for response time, waiting time, throughput, fairness and overall system efficiency. The concept of these tradeoffs sheds light on the importance of scheduling for modern computers.
What is CPU Scheduling?
The sequence of processes in the ready queue that the operating system selects from them and gives the CPU to them is called CPU scheduling. A process may be available for execution but not be able to do so as another process is using the processor. The scheduler looks at the processes waiting for CPU time and follows a scheduling policy to select the process to run next. The decision can occur when the running process completes, is blocked waiting for input or for some other resource, or is interrupted in order to allow another process to use the processor. In a preemptive scheduling system, the OS may suspend a process while it is running, and re-enter it into the ready queue temporarily. That allows multiple applications to share the CPU – albeit under control – and gives the illusion that multiple programs are running concurrently while in reality a single processor core is executing one set of instructions at a time.
The difference in characteristics and requirements of processes makes the scheduler crucial. Some processes may require short CPU bursts and can accomplish a short calculation, while others can require long CPU bursts and do extended calculations. Applications like text editors and web browsers and user interfaces typically need their CPU time quickly as the user would expect an action to have a quick reaction. Background tasks might be less sensitive to immediate responses, but still require processor time to advance. Hence a scheduling algorithm must take into account more than just picking any process available. The operating system may look at the duration of time processes have been waiting, their priority, duration of process expectation to run, or how much CPU time they’ve just been assigned. These factors will be used in CPU scheduling and will play a role in how the user may perceive the behavior and performance of a set of programs running concurrently.
Importance of CPU Scheduling
Even if a user is running just a handful of applications, there are dozens or hundreds of processes running on a computer system in various states. Some processes may be waiting for input or output, while other processes may be waiting to run and will be competing for processor time. Without proper scheduling, a process may be able to tie up the CPU for too long, and prevent other processes from executing. Scheduling is a way to manage the way that processors are accessed to ensure that available CPU time is allocated to the objectives of the system. If this is an interactive desktop, it may be important to highlight the notion of responsiveness and fairness. Predictable processing and throughput may be a focus for a server. If the system is specialized, scheduling might also require deadlines or specific priority requirements.
Also, by scheduling well, the operating system can utilize the processor resources better. The scheduler may choose to switch to another ready process instead of keeping the processor unnecessarily idle when a process is blocked while waiting for an I/O operation. This helps to complete the useful work while the slower operations are completed. Scheduling thus has close interaction with other responsibilities of the OS, such as process management, memory management, and I/O management. The effectiveness of a scheduling policy may have an impact on the response time of applications, the total number of tasks handled over time, and the fairness of the allocation of processor resources. No one scheduling algorithm is optimal for all possible workloads and environments. Operating systems, however, have several different ways of doing things, depending on the purpose and nature of the system.
Concepts of CPU Scheduling
Waiting Time
Waiting time refers to the amount of time a process spends in the ready queue waiting for the CPU. A process might be already in the system and ready to run, but another process may be using the processor. The longer a ready process is waiting, the longer its waiting time will be. A major aspect of how scheduling algorithms are judged is on the extent to which they can minimize this delay. If there are a lot of processes competing for a small number of CPU cores, then waiting times can become very apparent.
For instance, with one scheduling policy, if a process is put in the ready list that will run for a long time, then several processes that will run for shorter durations may be waiting in the ready list for a long time. Minimising the average waiting time can, therefore, make a system seem more efficient but it does not ensure responsiveness or fairness.
Response Time
Response time is the time period a process or interactive request has to wait before it is assigned CPU resources when it becomes ready. It is particularly important in systems where the users are directly interacting with the applications. A delay of several seconds before an application starts to respond to a button click, a typing input or the request for an operation can make the computer feel slow even if the operation is eventually completed.
Interactive scheduling algorithms try to make it possible to repeatedly provide opportunities for ready processes to execute. However, achieving such a goal will require more context switching, and can make applications feel responsive, with short response times. So the operating system must have speedy response time and utilize the processor efficiently.
Throughput
The throughput is the amount of useful work that is done by the system in a specific time. The number of processes performed over a period of time or some other appropriate measure of completed work may be used. A scheduling strategy that allows the processor to spend excessive time switching between processes may reduce the amount of productive work accomplished.
Alternatively, if one process is running too long, it can slow many other processes down. The aim of scheduling policies is thus to maintain good CPU utilization and ensure that processes are given the proper opportunities to run. In systems such as servers and batch processing systems, high throughput is especially beneficial when dealing with multiple computational tasks.
Fairness
Fairness means that processes are given fair opportunities to use the resources of the processor, based on the scheduling policy. If there is a scheduling algorithm which always schedules one set of processes and delays others indefinitely, this means that the delay may be prolonged. This is a typical issue that crops up when a process is waiting for resources but is not getting much or any CPU time as other processes are periodically chosen.
Fairness doesn’t necessarily imply that all processes are allocated the same amount of processor time. When there is a legitimate reason to do so, a system can allow higher priority processes greater access to CPU. The point is that the scheduling policy should exhibit predictable behaviour in line with its goal and should not have an unreasonable indefinite delay when this is not warranted.
First-Come, First-Served Scheduling
One of the simplest CPU scheduling algorithms is First-Come-First-Served, which is abbreviated as FCFS. It schedules processes in the order that they are added to the ready queue. The one process that comes first in the process is given the CPU first, then the next process, etc. This is similar to a traditional queue where people are served first come, first served. There is only one major advantage: simplicity; the operating system does not have to perform complex calculations on which process to select. FCFS can also offer a simple form of fairness in that processes are not continually reordered around by newer processes.
But, FCFS may give poor response and waiting time if a long CPU-bound process has come first and a few shorter processes have followed. The shorter processes may need to wait until the long process is done to get significant CPU time. This is sometimes called the convoy effect as a number of shorter processes may fall behind a long process. FCFS is, therefore, easily understood and easily implemented but may not be a good choice for interactive systems where users do expect to receive responses quickly. It may be reasonably effective in situations where speed of response isn’t as significant as simplicity or guaranteed queue ordering.
Shortest Job First Scheduling
Shortest Job First (SJF), chooses the job with the least CPU burst. The principle is that lower average queueing time of processes due to short tasks. If the operating system can estimate the duration of processes, it is possible to prioritise shorter processes before longer ones. This is one of the reasons why SJF is relevant from a theoretical point of view, as it has the potential to achieve low average waiting time under certain assumptions. It illustrates how knowledge of the requirements of process executions can affect scheduling decisions.
The major problem with SJF is that the OS typically is unable to predict the exact amount of time that a given process will require to execute in the future. It has to therefore make an estimation of the duration of a process. The estimates can be inaccurate, which will cause the algorithm to be less effective. If short processes keep coming in and are chosen first consistently, then SJF can even lead to starvation of long processes. Shortest remaining time first can be used to preemptively interrupt a running process if another process comes along with a smaller remaining execution time. This can help with improved responsiveness for short jobs, but adds scheduling choices and context switching costs.
Priority Scheduling
Priority scheduling allocates a priority to each process and chooses a process based on its priority. The scheduling rules of the system may cause a higher priority process to be served before a lower priority process. System requirements, process characteristics, and other factors can be used to determine priorities. This technique can be beneficial if certain tasks require quicker or more immediate access to processor resources than other tasks. An operating system, for instance, could have to separate between important functions of the system and less time-critical background work.
Another important risk that is brought in by priority scheduling is the risk of starvation. A low priority process could be placed in the ready queue for a very long period of time if high priority processes continue to arrive. A simple way to solve this issue is to age a waiting process, meaning that its priority slowly increases with the passing time. After a period of time, a process that has been waiting long enough can be more likely to be given CPU time. Priority scheduling may then offer a flexible approach to access to processors, but it is essential that priorities are properly assigned and managed to ensure that it is effective. Unfairness or delays can be caused by poorly designed priority policies.
Round Robin Scheduling
Time-sharing systems and interactive computing are commonly associated with Round Robin scheduling. Rather than the CPU remaining in a process until it is finished or blocked, the operating system assigns each process that is ready to run a fixed time period, known as a time quantum or time slice. The running process can be suspended and returned to the ready queue when the time slice is over, so that another process may be allowed to run. The scheduler keeps spinning the queue so that processes can get successive chances to run. This can give good responsiveness since a process typically is not required to wait for others to fully complete their work before it gets CPU time.
The length of the time quantum is an important design consideration. However, if the quantum is very small, there may be a lot of context switching overhead, and a lot of time spent doing nothing useful. For extremely long quantum, Round Robin can start to become similar to FCFS as processes may run for a relatively long time before another process is given the chance. A proper time quantum, thus, tries to find a balance between responsiveness and scheduling overhead. Round Robin is especially useful in situations where several users or interactive processes are frequently using the processor.
Multilevel Queue Scheduling
Multilevel queue scheduling involves creating different queues within the ready queue according to some criteria including process type and priority. A system, for instance, could have separate queues for interactive processes, system processes and background jobs. Each queue can have its own scheduling algorithm. If the queue is interactive, then it may be possible to provide responsive service by using Round Robin, or another queue may use a different method for longer running background processes. This enables the operating system to apply various categories of workloads with varying needs, different scheduling policies.
The queues themselves must also have a way to determine how CPU time should be distributed among them. The processor time can be assigned to a higher priority queue first than lower priority queues, and some systems may be able to allocate a fixed amount of CPU time to each queue. Multilevel queue scheduling can thus be more flexible, but it is also more complex. When processes in lower priority queues are never activated, they may suffer starvation. There must be a well formulated policy for the system to ensure that separation of workloads increases the organization, but does not lead to unreasonable delays.
Preemptive and Non-Preemptive Scheduling
There are two types of CPU scheduling algorithms Preemptive and Non-preemptive. In the non-preemptive scheduling, when a process gets the CPU, it will continue to run until it completes its CPU burst or it gives up the CPU voluntarily. An example of a non-preemptive approach is FCFS. This design may be simpler, since the operating system does not have to interrupt a process just because another process is ready to run. Other processes, however, can be delayed for a long period of time if the long running process is delayed.
Preemptive scheduling: OS can interrupt processes while it is running, allowing another process to use processor time. A common example of this is Round Robin: When a process’s time quantum expires, its execution can be interrupted. Preemption is important in interactive systems because it enables the operating system to avoid the situation in which one process monopolizes the CPU. It does, however, add some overhead as the operating system needs to save the state of the interrupted process and perform context switches. So, it depends on the requirements and design decisions of the OS to choose preemptive or non-preemptive scheduling.
Context Switching and Scheduling Overhead.
It switches the context of the running operating system from one running process to another. The system should maintain the state of the currently running process, and recreate the saved state of the process to be run. This enables processes to stop and subsequently resume at a suitable point. While context switching is necessary to multitask, it isn’t directly doing any useful application work. Too much context switching can then be inefficient and use up processor resources.
This overhead needs to be considered by scheduling algorithms when it comes to deciding the frequency of process switching. For example, in a very small time quantum like Round Robin, the processes may be executed many times, but many context switches may occur. On the other hand, very large time slices will decrease the overhead in switching but can result in longer processing wait times when processes are waiting in the queue. Schedule balancing is thus a balancing process. The operating system should allocate CPU time in such a way that it allows the system to be responsive and fair for the user while not using the processor too much to handle the scheduling process.
Balance between Performance and Fairness
There are multiple conflicting objectives in CPU scheduling. While minimizing average waiting time may lead to the adoption of the one scheduling strategy, and minimizing response time for interactive applications may lead to the adoption of another. Improving throughput may mean decreasing scheduling overhead, while fairness could mean increasing the number of processes that get to run on a regular basis. Sometimes these goals are competing, with a better score in one measurement coming at the expense of another. For instance, if short jobs are prioritized, their average waiting time can be decreased, but long jobs can be increased. Distributing small allocation periods to each process may make processes more responsive and more fair, but may make the frequency of context switching higher.
Given the various environments in which they run, operating systems choose or mix scheduling methods accordingly. Responsiveness is usually key for desktop systems as they should be able to support multiple applications at once. The server can be very throughput-oriented and resource using and be service predictable. Schedules that are specific to a particular system could employ a scheduling method based on deadlines or priorities. It is essential to understand that the job scheduling part of the CPU scheduling is not just about deciding which process gets first shot at the CPU. It’s about using processor time to ensure that the whole system is able to perform its work objectives and that processes are making sensible progress.
Conclusion
The concept of CPU scheduling is the basis for orderly multiprocessor sharing in a multitasking operating system. Different rules are used in the different types of algorithms to decide which process should be given the CPU time, such as First-Come, First-Served, Shortest Job First, Priority Scheduling, Round Robin, and multilevel queues. Both strategies have compromises related to waiting time, response time, throughput, fairness, starvation, and scheduling overhead. FCFS is based on the simple concept of queue ordering, SJF is based on the shorter the job, the sooner the job is served, Priority Scheduling is based on the importance that has been assigned to a process, Round Robin scheduling is based on repeated time slices, and multilevel queues is based on separating processes into groups and handling them differently.
By understanding these methods you can see how an operating system can manage many processes that are competing for the attention of the processor and keep the processor working. Finally, CPU scheduling is necessary because today’s computing systems require efficient and predictable sharing of scarce processor resources among many processes.
