Scheduling Algorithm

⏪Previous                                                          Next⏩

Definition:

 A Scheduling Algorithm is the algorithm which tells us how much CPU time we can allocate to the processes.

These scheduling algorithms are either preemptive or non-preemptive.

Preemptive Scheduling Algorithms are those which are based on the priority of the processes. By preference, when a high priority process enters, it preempts a low priority process in between and executes the high priority process first.

Non-preemptive Scheduling Algorithms are those who can’t be preempted in between, i.e. we can not take control of CPU in between until the current process completes its execution.

Purpose or Objectives of a Scheduling Algorithm

The goals of scheduling algorithms are as follows:
• Maximum utilisation of CPU so that we can keep the CPU as busy as possible.

• Throughput means the number of processes which are completing their execution in per unit time. There must be maximum throughput.

• Turnaround time means that the time taken by the processes to finish their implementation. It must be a minimum.

• Waiting time is that time for which the process remains in the ready queue. It must be a minimum.

•  There must be fare allocation of CPU.

• Response time is the time when the process gives its first response. It must be a minimum.

Why do we need scheduling?

As we know, a process needs CPU time and I/O time both for its execution. In a multiprogramming system, one process can use CPU while another process is waiting for I/O whereas, on the other hand in a uni programming system, all the time get wasted in waiting for I/O whereas CPU is free during that time.

Types of Scheduling Algorithms

There are eight different types of scheduling algorithms whose name are as follows:
To understand these scheduling, first, we discuss some terms that we need in each scheduling process.

• Arrival time is the time at which the process arrives in the ready queue for execution, and it is given in our table when we need to calculate the average waiting time.

• Completion time is the time at which the process finishes its execution.

• Turnaround time is the difference between completion time and arrival time, i.e. turnaround time = Completion time- arrival time   

•  Burst time is the time required by the process for execution of the process by CPU.

• Waiting time (W.T) is the difference between turnaround time and burst time, i.e. waiting time= Turnaround time - Burst time
Now we will discuss the scheduling algorithms one by one.

First Come First Serve (FCFS)

Jobs are executed on first come, first serve basis.
It is a non-preemptive, pre-emptive scheduling algorithm.
Easy to understand and implement.
Its implementation is based on FIFO queue.
Poor in performance as average wait time is high.

Wait time of each process is as follows −

Process	Wait Time : Service Time - Arrival Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

This is also known as shortest job first, or SJF
This is a non-preemptive, pre-emptive scheduling algorithm.
Best approach to minimize waiting time.
Easy to implement in Batch systems where required CPU time is known in advance.
Impossible to implement in interactive systems where required CPU time is not known.
The processer should know in advance how much time process will take.

Given: Table of processes, and their Arrival time, Execution time

Process	Arrival Time	Execution Time	Service Time
P0	0	5	0
P1	1	3	5
P2	2	8	14
P3	3	6	8

Waiting time of each process is as follows −

Process	Waiting Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	14 - 2 = 12
P3	8 - 3 = 5

Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems.
Each process is assigned a priority. Process with highest priority is to be executed first and so on.
Processes with same priority are executed on first come first served basis.
Priority can be decided based on memory requirements, time requirements or any other resource requirement.

Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are considering 1 is the lowest priority.

Process	Arrival Time	Execution Time	Priority	Service Time
P0	0	5	1	0
P1	1	3	2	11
P2	2	8	1	14
P3	3	6	3	5

Waiting time of each process is as follows −

Process	Waiting Time
P0	0 - 0 = 0
P1	11 - 1 = 10
P2	14 - 2 = 12
P3	5 - 3 = 2

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion.
Impossible to implement in interactive systems where required CPU time is not known.
It is often used in batch environments where short jobs need to give preference.

Round Robin Scheduling

Round Robin is the preemptive process scheduling algorithm.
Each process is provided a fix time to execute, it is called a quantum.
Once a process is executed for a given time period, it is preempted and other process executes for a given time period.
Context switching is used to save states of preempted processes.

Wait time of each process is as follows −

Process	Wait Time : Service Time - Arrival Time
P0	(0 - 0) + (12 - 3) = 9
P1	(3 - 1) = 2
P2	(6 - 2) + (14 - 9) + (20 - 17) = 12
P3	(9 - 3) + (17 - 12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5

⏪Previous                                                          Next⏩

1. What is an Operating System ?
2. Discuss the structure off OS ?
3. Explain type of OS?
4. Explain Function of OS?
5. Explain OS Services ?
6. What do mean by system call ?List different type ofsystem call available ?

1. what is process ? and Characteristics ?
2. What is different process state? explain the same in details?
3. write short note on user level and kernal level threads?
4. explain what is thread and its type ?
5. explain scheduler ? (short term,medium term,and long term)
6. state and explain scheduling criteria ?
7. Explain scheduling algorithm ? [ FCFS,SJF,PRIORITY,ROUND ROBINE.]    

1. What is process synchronization ? explain critical section problem and race condition ?
2. what is Race Condition ?
3. what is critical section problem?
4. explain classical problem of synchronization?
5. explain bounded - buffer problem?
6. explain reader - writer problem ?
7. explain Dining Philosophers Problem ?
8. explain semaphores ? its type ?

1.  What is deadlock ?
2. What are the 4 condition to produce deadlock ?
3. explain methods of handling deadlock ?
4. explain in detail deadlock prevention ?
5. write short note on deadlock avoidance ?
6. explain deadlock detection ? 
7. explain Banker algorithm with example ? 

1. What are memory management ?
2. what is contiguous memory allocation and non - contiguous memory allocation ?
3. explain concept of paging with neat diagram?
4. differentiate contiguous and non - contiguous memory allocation ?
5. explain in details various partitioning memory management?
6. explain the concept of Segmentation ?
7. what is Thrashing explain in details ?

1. explain virtual memory concept in details ? with advantages and disadvantages ?
2. explain page replacement algorithm ?
3. explain LRU , Optimal ,FIFO.