CPU Process Scheduling Algorithms in OS

Operating System: Q1. Discuss various Scheduling Algorithms with examples? - First Come First Serve scheduling, Shortest Job First scheduling, Round Robin scheduling, Priority scheduling, Multi-Level Queue scheduling, Multi-Level Feedback Queue scheduling. (Operating System all notes) : CPU Scheduling Algorithms in OS, Process Scheduling Algorithms in OS.

Q1. Discuss various Scheduling Algorithms with examples?

Ans. There are various CPU process scheduling algorithms in OS:

1. First Come First Serve (FCFS) Scheduling: CPU Scheduling Algorithms in OS

FCFS is the simplest scheduling algorithm, its implementation is straightforward which is maintained by FIFO (First In First Out) queue. Once a process has the CPU, it runs to completion. A FCFS scheduling is non-preemptive which usually results in poor performance. As a consequence of non-preemption, there is a low rate of resource utilization and system throughput.

Example: Calculate the turn around time, waiting time, average turn around time, average waiting time, throughput, and processor utilization for the given set of processes that arrive at a given arrival time.

2. Shortest Job First (SJF) Scheduling: CPU Scheduling Algorithms in OS

Shortest job first scheduling is a non-preemptive discipline in which a waiting job with the smallest estimated run time to completion is run next. In other words, when CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same CPU burst, FCFS is used. The SJF schedular searches the ready queue to find the job or the process with the shortest execution time.

Example: Consider the following set of processes with the following processing time which arrived at the same time:

Using SJF scheduling because the shortest length process will first get execution.
The Gantt chart will be:

3. Round Robin Scheduling: CPU Scheduling Algorithms in OS

One of the oldest, simplest, fairest, and the most widely used algorithm is Round-Robin. The round-robin scheduling algorithm is primarily used in time-sharing and multi-user system environments where the primary requirement is to provide reasonably good response times and in general to share the system fairly among all system users. Basically the CPU time is divided into the time slices. Each process is allocated a small time slice called Quantum. No process can run for more than quantum while others are waiting in the ready queue.

Example: Consider the following set of processes:

4. Priority Based Scheduling: CPU Process Scheduling Algorithms in OS

A priority number is associated with each process. The basic idea is straightforward: each process is assigned a priority and priority is allowed to run. Equal priority processes are scheduled in FCFS order. The SJF algorithm is a special case of the general priority scheduling algorithm. SJF is a priority scheduling where priority is the predicted next CPU burst time. The CPU is allocated to the process with the highest priority. Equal priority processes are scheduled for FCFS.

Example: Consider the following process:

5. Multi-Level Queue (MLQ) Scheduling: CPU Process Scheduling Algorithms in OS

A multi-queue scheduling algorithm partitions the ready queue in several separate queues. For example, interactive processes and batch processes could be considered as two types of processes. In a multi-level queue scheduling processes are permanently assigned to one queues.

The processes are permanently assigned to one another, based on some property of the process, such as:
(a) Memory size.
(b) Process priority.
(c) Process type.

The algorithm chooses the process from the occupied queue that has the highest priority and run that process either:
(a) Preemptive.
(b) Non-preemptive.
Each queue has its own scheduling algorithm or policy.

Possibility I : If each queue has absolute priority over lower priority queue then no process in the queue could run unless the queue for the highest priority processes were all empty.

Possibility II : If there is a time slice between the queues then each queue gets a certain amount of CPU times, which it can then schedule among the processes in its queue :
(a) 80% of the CPU time to foreground queue using RR.
(b) 20% of the CPU time to background queue using FCFS.

Background queue = Batch processes,
Foreground queue = Interactive processes.

6. Multi-Level Feedback Queue Scheduling:

A process can move between the various queues, aging can be implemented this way. Multi-level feedback queue scheduler is defined by the following parameters:

(a) The number of queues.
(b) The scheduling algorithm for each queue.
(c) The method used to determine when to upgrade a process.
(d) The method used to determine when to demote a process.
(e) The method used to determine which queue a process will enter when that process needs service.

Example: Three queues:
Q₀ - RR with time quantum 8 milliseconds.
Q₁ - RR time quantum 16 milliseconds.
Q₂ - FCFS.

Scheduling: A new job enters queue Q₀ which is served FCFS. When it gains CPU, job receives 8 milliseconds, or it does not finish in 8 milliseconds, the job is moved to queue Q₁ ,

At Q₁ job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to the queue Q₂.




[ Topic= CPU Process Scheduling Algorithms in OS ]
[ Topic= CPU Process Scheduling Algorithms in OS ]
[ Topic= CPU Process Scheduling Algorithms in OS ]



Join us on Facebook, Instagram, and Twitter to get the latest study material. You can also ask us any questions.
Facebook = @allbcaweb
(click on it or search "allbcaweb" on Facebook)
Instagram = @allbcaweb
(click on it or search "allbcaweb" on Instagram)
Twitter = @allbcaweb
(click on it or search "allbcaweb" on Twitter)
Email= allbca.com@gmail.com
Send us your query anytime about CPU Scheduling Algorithms in OS!

External Links:-

1. CPU Scheduling Algorithms in OS - (click here)
2. Process Scheduling Algorithms in OS - (click here)

[ Topic= CPU Process Scheduling Algorithms in OS ]
[ Topic= CPU Process Scheduling Algorithms in OS ]