CPU Scheduling

It is nothing, but picking up a process from the “Ready State” and then giving it to the CPU for its work completion.

Question: Why picking up from the ready state?

Answer: Because there are many processes waiting there to be entertained by the CPU or an I/O. One more thing, there is no other state before ready state which needs to be considered for process completion and all other process states exists after this state.

Points need to be noted before we start with the explanation:

1. WHO = Short-term scheduler and dispatcher are going to schedule processes.

2. WHERE = From “Ready State” to “Running State”

3. WHEN = When a process moves from:

• Running –> Termination
• Running –> Waiting
• Running –> Ready (case of time quantum or priority based processes)
• New         –> Ready (i.e. when a process is just created AND there is no need for CPU Scheduling unless the newly created process is of high priority)
• Waiting   –> Ready

Question: What is preemptive scheduling or preemption?

Answer: A running process is being stopped by the CPU in order to give its time to another process.

Question: What is Non-preemptive scheduling or no-preemption?

Answer: Once a process is in “Running State” it should not be stopped by the CPU until its work is completed.

Note: Before going next, make sure you know about Process Times.

CPU Scheduling OR Process Scheduling Algorithms

First Come First Serve (FCFS)

It says that which process comes first to the scheduler will be scheduled first and others have to wait.

Conditions for FCFS:

• Criteria: Arrival Time
• Interrupt: No Interrupts
• Mode: Non-Preemptive
• I/ O: No I/O

Disadvantages of FCFS:

• Convoy Effect OR Starvation
  • When the process with the highest burst time is first entertained by the CPU.
  • Until the current process is being finished, other processes cannot be entertained.
  • Or understand it like – a VIP car on road.

Example :

Process Number	Arrival Time (AT)	Burst Time (BT)	Completion Time (CT)	Turn Around Time (CT – AT = TAT)	Waiting Time (TAT – BT = WT)
1	0	4	4	4	0
2	1	3	7	6	3
3	2	1	8	6	5
4	3	2	10	7	5
5	4	5	15	11	6

Average Turn Around Time = 6.8

Average Waiting Time = 3.8

Note: FCFS is always a Non-Preemptive.

Shortest Job First (SJF)

In this algorithm, whichever process is having the shortest burst time that is going to be scheduled first. Out of available processes in the “ready state” it is going to schedule the process with shortest burst time.

Conditions for SJF :

• Criteria: Burst Time
• Mode: Non-Preemptive OR Preemptive

Advantages of SJF :

• Maximum Throughput.
• Minimum average weighting time and turn around time.

Disadvantages of SJF:

• Starvation to longer jobs.
• It is not implementable because the burst time of process cannot be known ahead.
  • Solution: SJF with predicted burst times.

Note: SJF can be preemptive or non-preemptive and it is not used practically.

Shortest Remaining Time First (SRTF)

As can be understood by the name of the algorithm itself, this algorithm schedules the processes on the basis of their remaining time and which process is having a shortest remaining time of all is going to be scheduled first.

Conditions for SRTF:

• Criteria: Burst Time
• Mode: Preemptive

Example :

Process Number	Arrival Time (AT)	Burst Time (BT)	Remaining Time (RT)	Completion Time (CT)	Turn Around Time (CT – AT = TAT)	Waiting Time (TAT – BT = WT)
1	0	7	6	19	19	12
2	1	5	4	13	12	7
3	2	3	2	6	4	1
4	3	1	0	4	1	0
5	4	2	1	9	5	3
6	5	1	0	7	2	1

Average Turn Around Time = 7.166

Average Waiting Time = 4

Round Robin Scheduling

This scheduling algorithm is most popular of all and many operating systems use this at practice.

Why? :

• Practically implementable, because it is not dependent on burst time.
• we can implement it with a simple data structure (Queues).
• No kind of starvation.

Every process is executed for a small amount of time which is known as Time Quantum because of this no process has to wait for the CPU. Every process will keep on getting the chance after some amount of time.

Longest Job First (LJF)

Process having the largest burst time gets scheduled first.

Conditions for LJF:

• Criteria: Burst Time
• Mode: Non-Preemptive

Example :

Process Number	Arrival Time (AT)	Burst Time (BT)	Completion Time (CT)	Turn Around Time (CT – AT = TAT)	Waiting Time (TAT – BT = WT)	Response Time (RT)
1	0	3	3	3	0	0
2	1	2	20	19	17	19
3	2	4	18	16	12	12
4	3	5	8	5	0	0
5	4	6	14	10	4	4

Average Turn Around Time = 10.6

Average Waiting Time = 6.6

Priority Scheduling

Whenever a process is scheduled by the scheduler (Long-term scheduler) and whenever it enters the “Ready Queue” it is going to come with a number associated with it, that is nothing but PRIORITY.

Priorities are of two types:

1. Static Priority: Does not change throughout the execution of a process
2. Dynamic Priority: Changes at regular intervals of time.

Note: Priority scheduling can be of two types, preemptive or non-preemptive.

Summary: We have gone through almost every CPU scheduling Algorithms out there, if you still have any queries then please let us know by leaving a comment below.