Classification of CPU Scheduling Algorithms

Phase when CPU becomes idle and to have efficient use of available resources (processing power, hardware etc) in a given time constraint, it is the job of the CPU Scheduler to select another process from the ready queue to run next. CPU Scheduling algorithms are used. This raises the question in mind what is meant by CPU Scheduling algorithms?

CPU Scheduling Algorithm is a set of rules through which CPU executes given number of processes by utilizing the available resources efficiently and within the provided time constraint. While reading this article, currently in background lot of processes might be in working and all such processes are scheduled and managed by the CPU scheduling algorithms which are implemented by processor manufacturer.

There are two types of CPU scheduling algorithms.

• Preemptive Scheduling Algorithm
• Non-preemptive Scheudling Algorithm

Preemptive Scheduling Algorithm covers the following algorithms:

1. Round Robin scheduling Algorithm.
2. Priority Scheduling Algorithm.
3. Shortest Remaining Time First scheduling Algorithm.
4. Multilevel Queue Scheduling.

Non-Preemptive Scheduling Algorithm covers the following algorithms:

1. First Come First Serve (FCFS) / Co-operative scheduling algorithm / First In First Out (FIFO) / Run-to-Completion / Run-Until-Done.
2. Priority Scheduling Algorithm.
3. Shortest Job First (SJF) / Shortest-Process-Next (SPN).
4. Multilevel Feedback Queue Scheduling (robust algorithm among available).

Each processes contains following parameters :

• Process Identity : Alias given to process.
• Arrival Time : Time at which process is in ready queue.
• Priority : Priority of execution (standard differs according to algorithm implementation). Optional in few cases.
• Burst Time : Time required by CPU for execution of a process. It is also called as Running Time or Execution Time.

Terms to be known while studying CPU Scheduling Algorithms

Terms to be known while studying CPU Scheduling Algorithms are:

• Response Time : Time spent when the process is in the ready state and gets the CPU for the first time is called Response Time.
• Throughput : Throughput is used to compute the efficiency of the CPU.
• Turnaround Time : Time taken by the process to complete its execution right from its arrival at ready state till it gets completely executed.
• Policy of Fairness : Policy of Fairness states that no process should experience undetermined waiting time, each and every process must get its chance of execution.

Preemptive CPU Scheduling Algorithm

Preemptive CPU scheduling algorithms is a type of CPU scheduling algorithms where the processes having highest priority is executed first. Despite current execution of low priority processes which is arrived according to its respective arrival time is halted and the process with highest priority is executed. Meanwhile, low priority task is preempted and gets chance to execute after the execution of high priority process.

When an older process get completly executed or When a process switches from the running state to the waiting state Preemptive CPU Scheduling algorithms are used.

Following are the CPU scheduling algorithms which falls under Preemptive CPU Scheudling Algorithm:

1. Round Robin scheduling Algorithm.
2. Priority Scheduling Algorithm.
3. Shortest Remaining Time First scheduling Algorithm.
4. Multilevel Queue Scheduling.

Advantages of using Preemptive CPU Scheduling Algorithms

Advantages of using Preemptive CPU Scheduling Algorithms are:

• More robust, one process cannot monopolize the CPU.
• Good response time.
• Policy of Fairness is applied here. The OS makes sure that CPU usage is the same by all running process.

Disadvantages of using Preemptive CPU Scheduling Algorithms

Disadvantages of using Preemptive CPU Scheduling Algorithms are:

• Complex to implement.
• User is prime responsible to handle to halt the processes and save the execution state.
• Throughput generated may not be upto the mark(requirement).

Non-Preemptive CPU Scheduling Algorithm

Non-Preemptive CPU scheduling algorithms is a type of CPU scheduling algorithms where the particular process executes completely and CPU resources are unlocked only after the execution of the current process is completed. Meanwhile the other process are in waiting state. Here no preemption is occured for any of the process.

When a process switches from the running state to the ready state say for respose to interrupt or When a process switches from the waiting state to the ready state Non-Preemptive CPU Scheduling Algorithms are used.

Following are the CPU scheduling algorithms which falls under Non-Preemptive CPU Scheudling Algorithm:

1. First Come First Serve (FCFS) / Co-operative scheduling algorithm / First In First Out (FIFO) / Run-to-Completion / Run-Until-Done.
2. Priority Scheduling Algorithm.
3. Shortest Job First (SJF) / Shortest-Process-Next (SPN).
4. Multilevel Feedback Queue Scheduling (robust algorithm among available).

Advantages of using Non-Preemptive CPU Scheduling Algorithms

Advantages of using Non-Preemptive CPU Scheduling Algorithms are:

• Simple and easy to implement.
• Low scheduling overhead.
• Intended potential to produce high throughput .

Disadvantages of using Non-Preemptive CPU Scheduling Algorithms

Disadvantages of using Non-Preemptive CPU Scheduling Algorithms are:

• Low reponse time for processes.
• No policy of fairness.
• Poor implementation may led to machine in unresponsive state.
• Not preferred for real time scheduling.\

Key Differences between Preemptive Non-Preemptive CPU Scheduling Algorithms

Key Differences between Preemptive Non-Preemptive CPU Scheduling Algorithms are:

• The major contrast between these two types of CPU scheduling algorithm is is that in preemptive CPU scheduling algorithms the CPU uses available resources for execution of the processes for the limited period of time. Whereas in Non-preemptive CPU scheduling algorithms, the CPU resources are allocated to the process until it finishes its execution or make switch to waiting state.
• CPU utilization is more compared to Non-Preemptive Scheduling.
• Preemptive CPU Scheduling algorithms are associated by a cost of priority compared to Non-Preemptive CPU Scheduling algorithms.
• Overhead of switching the process from ready state to running state and maintaining the ready queue datastructure is present in Preemptive CPU Scheduling algorithms whereas, Non-Preemptive CPU Scheduling algorithms has no overhead of switching the process from running state to ready state.
• Preemptive CPU Scheduling algorithms are flexible in terms of computations means demanding processes are allowed to access CPU as they arrive into the ready queue, no matter which process is executing currently. whereas Non-Preemptive CPU Scheduling algorithms are rigid in which running CPU is not disturbed at no cost.
• Non-Preemptive CPU Scheduling algorithms makes less CPU utilization compared to Preemptive CPU Scheduling algorithms which is good.
• Waiting time and Response time is less in Preemptive CPU Scheduling algorithms compared to Non-Preemptive CPU Scheduling algorithm.
• Example for preemption: While updating critical kernel data structure, if process with higher priority interrupts the CPU. Hence to solve the above stated problem many modern UNIX architectures make the process wait until the system call has either completed or blocked before allowing the preemption Unfortunately this solution is problematic for real-time systems, as real-time response can no longer be guaranteed.