Priority Scheduling

Priority Scheduling is a CPU scheduling algorithm in which each process is assigned a

priority, and the CPU is allocated to the process with the highest priority first. Processes with
equal priority are executed using FCFS order.

Definition

Priority Scheduling is a scheduling technique where the process with the highest priority gets
the CPU before other processes.

Working of Priority Scheduling

1. Each process is assigned a priority number.

2. Processes are placed in the ready queue.

3. The scheduler selects the process with the highest priority.

4. The selected process gets CPU execution.

5. After completion, the next highest-priority process is selected.

Types of Priority Scheduling

1. Preemptive Priority Scheduling

 A running process can be interrupted if a higher-priority process arrives.

 CPU is immediately allocated to the higher-priority process.

2. Non-Preemptive Priority Scheduling

 Once a process gets the CPU, it continues execution until completion.

 Higher-priority arriving processes must wait.

Characteristics of Priority Scheduling

1. Processes are executed based on priority.

2. Can be preemptive or non-preemptive.

3. Important tasks get CPU first.

4. Suitable for real-time systems.

Advantages
1. Important processes are executed first.

2. Better control over process execution.

3. Suitable for time-critical applications.

4. Flexible scheduling method.

Disadvantages

1. Low-priority processes may suffer starvation.

2. Complex implementation compared to FCFS.

3. Priority inversion may occur.

Starvation in Priority Scheduling

If high-priority processes continuously arrive, low-priority processes may never get CPU
time. This problem is called starvation or indefinite postponement.

Solution: Aging

 The priority of waiting processes is gradually increased over time.

 This ensures every process eventually gets CPU time.

Round Robin (RR) Scheduling

Round Robin Scheduling is a preemptive CPU scheduling algorithm in which each process
is assigned a fixed time interval called a time quantum or time slice. Processes are executed
one by one in a circular order. When the time quantum expires, the currently running process
is preempted and moved to the end of the ready queue, and the next process gets the CPU.

Definition

Round Robin Scheduling is a CPU scheduling technique where each process gets an equal
share of CPU time in cyclic order using a fixed time quantum. It is mainly used in time-
sharing systems.

Working of Round Robin Scheduling

1. Processes are placed in the ready queue.

2. The CPU selects the first process from the queue.

3. The process executes for one time quantum.

4. If the process finishes before the quantum ends, it leaves the system.
5. If the process is not completed, it is preempted and moved to the end of the queue.

6. The next process in the queue gets CPU access.

7. The cycle continues until all processes are completed.

Example

Suppose the time quantum = 4 ms

Process Burst Time

P1 10 ms

P2 5 ms

P3 8 ms

Execution Order
 P1 executes for 4 ms → remaining 6 ms

 P2 executes for 4 ms → remaining 1 ms

 P3 executes for 4 ms → remaining 4 ms

  P1 executes for 4 ms → remaining 2 ms

 P2 executes for 1 ms → completed

 P3 executes for 4 ms → completed

 P1 executes for 2 ms → completed

Characteristics of Round Robin Scheduling

1. Preemptive scheduling algorithm.

2. Each process gets equal CPU time.

3. Uses a circular queue.

4. Fair scheduling method.

5. Suitable for interactive and time-sharing systems.

Advantages

1. Fair allocation of CPU to all processes.

2. No process suffers starvation.

3. Good response time for interactive users.

4. Simple and easy to implement.

Disadvantages
1. Too small time quantum causes many context switches.

2. Too large time quantum behaves like FCFS scheduling.

3. Performance depends on proper quantum size.

4. Higher context switching overhead.

Shortest Job First (SJF) Scheduling

Shortest Job First (SJF) Scheduling is a CPU scheduling algorithm in which the process with
the smallest burst time is selected for execution first. It is designed to minimize the average
waiting time of processes.

Definition

SJF Scheduling is a scheduling technique where the process having the shortest CPU burst
time is executed before the longer processes.

Types of SJF Scheduling

1. Non-Preemptive SJF

 Once a process gets the CPU, it continues execution until completion.

 The currently running process is not interrupted.

2. Preemptive SJF (Shortest Remaining Time – SRT)

 If a new process arrives with a shorter burst time than the remaining time of the
current process, the CPU is switched to the new process.

 Also called Shortest Remaining Time Scheduling.

Working of SJF Scheduling

1. Processes in the ready queue are examined.

2. The process with the shortest burst time is selected.

3. The selected process gets the CPU.

4. After completion, the next shortest process is selected.

Characteristics of SJF Scheduling

1. Can be preemptive or non-preemptive.

2. Gives priority to shorter jobs.

3. Minimizes average waiting time.

4. Efficient for batch systems.

Advantages

1. Minimum average waiting time among scheduling algorithms.

2. Better turnaround time.

3. Efficient CPU utilization.

4. Suitable for batch processing systems.

Disadvantages

1. Difficult to know the exact burst time in advance.

2. Long processes may suffer starvation.

3. Not suitable for interactive systems.

4. Preemptive version is more complex.

First Come First Served (FCFS) Scheduling

First Come First Served (FCFS) Scheduling is the simplest CPU scheduling algorithm in
which the process that arrives first in the ready queue gets the CPU first. It follows the FIFO
(First In First Out) principle.

Definition

FCFS Scheduling is a non-preemptive scheduling algorithm where processes are executed in

the order of their arrival.

Working of FCFS Scheduling

1. Processes enter the ready queue according to arrival time.

2. The first arriving process gets the CPU first.

3. Once a process starts execution, it continues until completion.

4. After completion, the next process in the queue gets the CPU.
Characteristics of FCFS Scheduling

1. Non-preemptive scheduling algorithm.

2. Processes are executed in arrival order.

3. Uses FIFO queue.

4. Simple and easy to implement.

Advantages

1. Easy to understand and implement.

2. Fair according to process arrival.

3. No starvation occurs.

4. Low scheduling overhead.

Disadvantages

1. Long waiting time for short processes.

2. Poor average turnaround time.

3. Suffers from convoy effect.

4. Not suitable for time-sharing systems.

Preemptive and Non-Preemptive Scheduling

Scheduling in an operating system determines which process gets the CPU for execution.
Scheduling algorithms are mainly classified into Preemptive Scheduling and Non-
Preemptive Scheduling.

Preemptive Scheduling

In preemptive scheduling, the operating system can interrupt a running process and allocate
the CPU to another process. This usually happens when a higher-priority process arrives or
when the time quantum expires.

Examples

 Round Robin (RR)

 Shortest Remaining Time (SRT)

 Preemptive Priority Scheduling
Characteristics

1. CPU can be taken away from a running process.

2. Better response time.

3. Suitable for time-sharing systems.

4. Requires context switching.

Advantages

 Better responsiveness.

 Fair CPU sharing.

 Suitable for interactive systems.

Disadvantages

 More context switching overhead.

 Complex implementation.
 Can reduce CPU efficiency.

Non-Preemptive Scheduling

In non-preemptive scheduling, once a process gets the CPU, it continues execution until it
finishes or voluntarily releases the CPU.

Examples

 FCFS (First Come First Served)

 Non-Preemptive SJF

 Non-Preemptive Priority Scheduling

Characteristics

1. Running process cannot be interrupted.

2. Simpler scheduling method.

3. Less context switching.

4. Suitable for batch systems.

Advantages

 Simple and easy to implement.

 Low overhead.
  Better CPU utilization in some cases.

Disadvantages

 Poor response time.

 Long waiting time for short processes.

 Not suitable for interactive systems.