Home About

CPU SCHEDULING

What is CPU Scheduling

CPU scheduling is a process that allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast, and fair. Whenever the CPU becomes idle, the operating system must select one of 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.
Process Scheduler :
  1. Long Term or job scheduler : It brings the new process to the 'Ready State'. It controls Degree of Multi-programming, i.e., number of process present in ready state at any point of time. It is important that the long-term scheduler make a careful selection of both IO and CPU bound processes.
  2. Short term or CPU scheduler : It is responsible for selecting one process from ready state for scheduling it on the running state.
    Note : Short-term scheduler only selects the process to schedule it doesn't load the process on running.
  3. Medium-term scheduler : It is responsible for suspending and resuming the process. It mainly does swapping (moving processes from main memory to disk and vice versa). Swapping may be necessary to improve the process mix or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up.
Types of CPU Scheduling :
CPU scheduling decisions may take place under the following four circumstances:
  1. When a process switches from the running state to the waiting state(for 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.
Dispatcher :
The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves:
  • Switching context
  • Switching to user mode
  • Jumping to the proper location in the user program to restart that program from where it left last time.
The dispatcher should be as fast as possible, given that it is invoked during every process switch. The time taken by the dispatcher to stop one process and start another process is known as the Dispatch Latency.

Need of Cpu Scheduling

A typical process involves both I/O time and CPU time. In a uni programming system like MS-DOS, time spent waiting for I/O is wasted and CPU is free during this time. In multi programming systems, one process can use CPU while another is waiting for I/O. This is possible only with process scheduling. But, if the long term scheduler picks more I/O bound processes then most of the time, the CPU remains idol. The task of Operating system is to optimize the utilization of resources. If most of the running processes change their state from running to waiting then there may always be a possibility of deadlock in the system. Hence to reduce this overhead, the OS needs to schedule the jobs to get the optimal utilization of CPU and to avoid the possibility to deadlock.

Algorithms

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU ’s core. There are many different CPU - scheduling algorithms. Different CPU-scheduling algorithms have different properties, and the choice of a particular algorithm may favor 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 like how much CPU is utilizeed by algorithm, what is Throughput of algorithm, what is turnaround time, what is waiting time etc.
FIRST COME FIRST SERVE
FCFS (First-come-First-serve) follows the principle of FIFO (First-in-First-out). It is the simplest scheduling algorithm. FCFS simply queues processes in the order that they arrive in the ready queue. In this, the process which comes first will be executed first and the next process starts only after the previous gets fully executed. It is a non-preemptive algorithm.
Characteristics
  1. The simplest form of a CPU scheduling algorithm
  2. Easy to implement
  3. Non-preemptive
  4. Average Waiting Time is not optimal
  5. Not an ideal technique for time-sharing systems.
  6. Can not utilize resources in parallel: Results in Convoy effect. Convoy Effect is a phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to a few slow processes. Consider a situation when many IO-bound processes are there and one CPU bound process. The IO bound processes have to wait for CPU bound process when the CPU bound process acquires CPU. The IO-bound process could have taken CPU for some time, then used IO devices
Read More
SHORTEST JOB FIRST (Non-Preemptive)
The Shortest-Job-First (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next. It is a non-preemptive algorithm. Being a non-preemptive algorithm, the first process assigned to the CPU is executed till completion, then the process whose burst time is minimum is assigned next to the CPU and hence it continues.
Characteristics
  1. Shortest Job first has the advantage of having a minimum average waiting time among all scheduling algorithms.
  2. It is a Greedy Algorithm.
  3. It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of ageing.
  4. It is practically infeasible as Operating System may not know burst time and therefore may not sort them. While it is not possible to predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times. SJF can be used in specialized environments where accurate estimates of running time are available.
Read More
SHORTEST JOB FIRST (Preemptive)
This is a version of Shortest job first with preemption in which the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.
Characteristics
  1. Short processes are handled very quickly.
  2. The system also requires very little overhead since it only makes a decision when a process completes or a new process is added.
  3. When a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute.
  4. It has the potential for process starvation.
  5. Long processes may be held off indefinitely if short processes are continually added.
  6. It is impractical since it is not possible to know the burst time of every process in ready queue in advance.
Read More
ROUND ROBIN
Round-Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot (also called quantum). Once that chunk of time is completed, the process is context-switched with the next in the queue. It is the most common and practically usable scheduling algorithm, as it doesn't require the system to estimate the burst-time of a process. Calculation of burst-time is practically not possible as no one can predict how long a process will take to execute. It although has a minor disadvantage of the overhead of context-switching (some time gets wasted in the process).
Characteristics
  1. Round robin is a pre-emptive algorithm
  2. The CPU is shifted to the next process after fixed interval time, which is called time quantum/time slice.
  3. The process that is preempted is added to the end of the queue.
  4. It doesn't face the issues of starvation or convoy effect.
  5. This method spends more time on context switching
  6. Its performance heavily depends on time quantum and finding a correct time quantum is a quite difficult task in this system.
  7. Round-robin scheduling doesn't give special priority to more important tasks.
Read More

Goals of CPU Scheduling

Different goals for which we use CPU scheduling are as follows :
1. Maximum CPU Utilization :
We want to keep the CPU as busy as possible. To make out the best use of the CPU and not to waste any CPU cycle, the CPU would be working most of the time(Ideally 100% of the time). Considering a real system, CPU usage should range from 40% (lightly loaded) to 90% (heavily loaded.)
2. Maximum Throughput :
It is the total number of processes completed per unit of time or rather says the total amount of work done in a unit of time. This may range from 10/second to 1/hour depending on the specific processes. So the CPU must try to execute maximum number of jobs per unit time.
3. Minimum Turnaround time :
It is the amount of time taken to execute a particular process, i.e. The interval from the time of submission of the process to the time of completion of the process(Wall clock time). We want it to be as minimum as possible.
4. Minimum Waiting Time :
The sum of the periods spent waiting in the ready queue amount of time a process has been waiting in the ready queue to acquire get control on the CPU.
5. Minimum Response Time :
Amount of time it takes from when a request was submitted until the first response is produced. Remember, it is the time till the first response and not the completion of process execution(final response).
6. Fair CPU Allocation :
There are many processes in our system waiting for CPU. We have to make sure that no process starve for CPU i.e no process should wait for so long due to it's burst time or any other property.
Made with by Rajat.