PROGRAM 2
Simulate the following CPU scheduling algorithms
A) FCFS b) SJF c) Round Robin d) Priority
❖ There are two types of scheduling methods:-
1. Preemptive scheduling
2. Non preemptive scheduling
❖ PREEMPTIVE SCHEDULING
➢ The tasks are usually assigned with priorities.
➢ At times it is necessary to run a certain task that has a
higher priority before another task although it is running.
➢ Therefore the running task is interrupted for some time and
resumes later when the priority task has finished its
execution.
❖ NON PREEMPTIVE SCHEDULING
➢ Once the CPU has been allocated to the process, the process
keeps the CPU until it releases the CPU either by terminating
or by switching to the waiting state.
❖ SCHEDULING ALGORITHMS
➢ To decide which process to run first and which process to run
last to achieve maximum CPU utilization, we have some
algorithms.
■ First come first served FCFS scheduling
■ Shortest job first SJF scheduling
■ Priority scheduling
■ Round Robin RR scheduling
■ Multilevel Queue Scheduling
■ Multilevel Feedback Queue Scheduling
1. FIRST COME FIRST SERVE (FCFS)
❖ Fcfs is an operating system scheduling algorithm that automatically
executes queued requests and processes in order of their arrival.
❖ Easiest and simplest scheduling algorithm.
❖ Processes which request the CPU first, get the CPU allocation first
❖ Managed with FIFO Queue.
❖ As the process enters the ready state its PCB (Process control
block) is linked with the tail of the queue.
❖ When the CPU becomes free it should be assigned to the process at
the beginning of the queue.
CHARACTERISTICS
❖ Easy to implement and use.
❖ Supports both non preemptive and preemptive.
❖ Jobs are always executed on a First come First serve basis.
❖ Poor performance and general waiting time is quite high.
EXAMPLE
PROCESS BURST TIME ARRIVAL TIME PRIORITY
P1 4 0 5
P2 3 1 1
P3 1 2 2
P4 2 3 4
P5 5 4 3
Step 1
Process begins with P1 which has arrival time 0.
P1
0 1
Step 2
At time = 1,P2 arrives. Since P1 is still executing P2 is kept in the queue.
P1
0 2
Step 3
At time = 2, P3 arrives, P1 and P3 are in queue.
P1
0 3
Step 4
At a time = 3, P4 arrives and P1 completes the task.
P1 P2
0 4 3
Step 5
At a time = 4, P5 arrives, P3, P4, P5 are in queue.
P1 P2
0 4 7
Step 6
At a time = 7, P2 completes the task and P3 starts.
P1 P2 P3
0 4 7 8
Step 7
At the time = 8, P3 completes the task and P4 starts.
P1 P2 P3 P4
0 4 7 8 10
Step 8
At time = 10, P4 completes and P5 starts.
P1 P2 P3 P4 P5
0 4 7 8 10 15
Step 9
At time = 15, P5 completes the execution and there are no processes in
queue.
P1 P2 P3 P4 P5
0 4 7 8 10 15
Average Waiting time = 0+4+7+8+10/5 = 29/5 = 5.8 sec
PYTHON CODE FOR FIRST COME FIRST SERVE
IMPLEMENTATION:
n = int(input("Enter number of processes: "))
processes = []
for i in range(n):
arrival_time = int(input(f"Enter arrival time for process {i+1}: "))
burst_time = int(input(f"Enter burst time for process {i+1}: "))
processes.append((i+1, arrival_time, burst_time))
# sort the processes based on their arrival time
processes.sort(key=lambda x: x[1])
# initialize waiting time for the first process as 0
waiting_time = 0
# calculate waiting time for each process
for i in range(n):
waiting_time += processes[i][2]
processes[i] = (processes[i][0], processes[i][1], processes[i][2],
waiting_time - processes[i][2])
# calculate average waiting time
avg_waiting_time = waiting_time / n
# print the final results
print("\nFCFS Scheduling:")
print("Process\tArrival Time\tBurst Time\tWaiting Time")
for i in range(n):
print(f" P{processes[i][0]}\t\t{processes[i][1]}\t\t{processes[i][2]}\
t\t{processes[i][3]}")
print(f"\nAverage Waiting Time: {avg_waiting_time:.2f}")
OUTPUT:
2. SHORTEST JOB FIRST (SJF)
❖ Shortest job first is an algorithm that selects the process with the
least execution time for the next execution.
❖ This scheduling method can be preemptive or non-preemptive.
❖ By this method the average waiting time for the other processes
waiting for execution is significantly reduced.
CHARACTERISTICS
❖ Each job is associated with a unit of time for execution.
❖ Helpful for batch processing where waiting for jobs to complete is
not critical.
❖ It can improve process throughput by ensuring that shorter jobs
are executed first and thus may have a shorter turnaround time.
EXAMPLE
PROCESS BURST TIME ARRIVAL TIME PRIORITY
P1 4 0 5
P2 3 1 1
P3 1 2 2
P4 2 3 4
P5 5 4 3
Step 1
Since arrival time is not considered, the first process P3 with low burst
time is implemented from 0 to 1 second.
P3
0 1
Step 2
Process P4 is executed next from 1 to 3 seconds as its burst time is 2
seconds.
P3 P4
0 1 3
Step 3
Process P2 is executed from 3 to 6 seconds.
P3 P4 P2
0 1 3 6
Step 4
Process P1 is executed from 6 to 10 seconds.
P3 P4 P2 P1
0 1 3 6 10
Step 5
Process P5 is executed from 10 to 15 seconds.
P3 P4 P2 P1 P5
0 1 3 6 10 15
Average Waiting time = 6+3+0+1+10/5 = 20/5 = 4 sec
PYTHON CODE FOR SHORTEST JOB FIRST
IMPLEMENTATION
n = int(input("Enter the number of processes: "))
processes = []
for i in range(n):
arrival_time = int(input(f"Enter arrival time for process {i+1}: "))
burst_time = int(input(f"Enter burst time for process {i+1}: "))
processes.append((i+1, arrival_time, burst_time))
processes.sort(key=lambda x: x[1])
current_time = 0
waiting_time = 0
for i in range(n):
shortest_job = min(processes[i:], key=lambda x: x[2])
index = processes.index(shortest_job)
waiting_time += current_time - processes[index][1]
current_time += processes[index][2]
avg_waiting_time = waiting_time / n
print(f"Average waiting time: {avg_waiting_time:.2f}")
OUTPUT:
3. ROUND ROBIN SCHEDULING
❖ The oldest and simplest scheduling algorithm.
❖ Mostly used for multitasking
❖ It offers starvation free execution of processes.
❖ Each ready task runs by turn by turn only in a cyclic queue for a
limited Time slice.
CHARACTERISTICS
❖ Preemptive algorithm
❖ The process that is preempted is appended to the end of the queue
❖ Oldest, fairest and simplest algorithm
❖ Widely used scheduling method in traditional operating systems
❖ It is a hybrid model, which is clock-driven
❖ It is a real-time algorithm that reacts to an event within a certain
period of time.
EXAMPLE
PROCESS BURST TIME ARRIVAL TIME PRIORITY
P1 4 0 5
P2 3 1 1
P3 1 2 2
P4 2 3 4
P5 5 4 3
Step 1
P1 executes for 2 seconds and waits remaining is P₁².
P1
0 2
Step 2
At t =2, P2 executes till t = 4 remaining P₂¹.
P1 P2
0 2 4
Step 3
At t =4, P3 executes for 1 second and completes at t = 5.
P1 P2 P3
0 2 4 5
Step 4
At t =5, P4 executes for 2 seconds till t = 7 and completes.
P1 P2 P3 P4
0 2 4 5 7
Step 5
At t = 7, P5 executes for 2 seconds till t = 9 remaining P₅³.
P1 P2 P3 P4 P5
0 2 4 5 7 9
Step 6
Remaining processes are executed at the same time quantum repeating
from P1.
P1 P2 P3 P4 P5 P1 P2 P5 P5
0 2 4 5 7 9 11 12 14 15
Average Waiting time = 5+7+11+5+10/5= 38/5 = 7.65 sec
PYTHON CODE FOR ROUND ROBIN SCHEDULING
n = int(input("Enter number of processes: "))
processes = []
for i in range(n):
name = "P" + str(i+1)
arrival_time = int(input("Enter arrival time for " + name + ": "))
burst_time = int(input("Enter burst time for " + name + ": "))
processes.append([name, arrival_time, burst_time])
time_quantum = int(input("Enter time quantum: "))
waiting_time = [0] * n
turnaround_time = [0] * n
completion_time = [0] * n
remaining_time = [process[2] for process in processes]
current_time = 0
current_process = 0
while sum(remaining_time) > 0:
execute_time = min(time_quantum, remaining_time[current_process])
remaining_time[current_process] -= execute_time
current_time += execute_time
if remaining_time[current_process] == 0:
completion_time[current_process] = current_time
turnaround_time[current_process] =
completion_time[current_process] - processes[current_process][1]
waiting_time[current_process] = turnaround_time[current_process]
- processes[current_process][2]
current_process = (current_process + 1) % n
avg_waiting_time = sum(waiting_time) / n
avg_turnaround_time = sum(turnaround_time) / n
print("Process\tArrival Time\tBurst Time\tCompletion Time\tWaiting
Time\tTurnaround Time")
for i in range(n):
print(processes[i][0], "\t\t", processes[i][1], "\t\t", processes[i][2], "\
t\t", completion_time[i], "\t\t", waiting_time[i], "\t\t",
turnaround_time[i])
print("Average waiting time:", avg_waiting_time)
print("Average turnaround time:", avg_turnaround_time)
OUTPUT
4. PRIORITY SCHEDULING
❖ It is a method of scheduling processes based on priorities
❖ The scheduler selects the tasks to be processed based on priority.
❖ The processes with higher priority should be executed first, while
tasks with the same priority are executed on a round robin or FCFS
basis.
❖ Priority depends on memory requirements, time requirements, etc.
❖ With this type of scheduling algorithm, if a newer process arrives
that has a higher priority than the currently running processes,
then the currently running process is preempted.
CHARACTERISTICS
❖ Schedule Processes based on priority.
❖ Performs batch processes
❖ Lower the number, higher is the priority
❖ If two jobs have the same priority it works on an FCFS basis.
❖ A number is assigned to indicate its priority level.
EXAMPLE
PROCESS BURST TIME ARRIVAL TIME PRIORITY
P1 4 0 5
P2 3 1 1
P3 1 2 2
P4 2 3 4
P5 5 4 3
Step 1
At t=0, since arrival time is not considered , P2 arrives with priority one
and executes still t = 3 seconds.
P2
0 3
Step 2
At t = 3, P3 arrives with second priority and executes till t = 4.
P2 P3
0 3 4
Step 3
At t= 4 p5 arrives with third priority and executes till t = 9.
P2 P3 P5
0 3 4 9
Step 4
At t =9, P4 arrives and executes till t = 11.
P2 P3 P5 P4
0 3 4 9 11
Step 5
At t=11, P1 arrives with 5th priority and executes till t = 15.
P2 P3 P5 P4 P1
0 3 4 9 11 15
Average Waiting time = 0+3+4+9+11/5 = 27/5 = 5.4 sec
PYTHON CODE IMPLEMENTATION FOR PRIORITY
SCHEDULING
n = int(input("Enter number of processes: "))
processes = []
for i in range(n):
name = "P" + str(i+1)
burst_time = int(input("Enter burst time for " + name + ": "))
arrival_time = int(input("Enter arrival time for " + name + ": "))
priority = int(input("Enter priority for " + name + ": "))
processes.append([name, burst_time, arrival_time, priority])
processes.sort(key=lambda x: (x[2], -x[3]))
waiting_time = [0] * n
completion_time = [0] * n
for i in range(n):
completion_time[i] = processes[i][1] + (completion_time[i-1] if i > 0
else 0)
waiting_time[i] = completion_time[i] - processes[i][1] - processes[i][2]
avg_waiting_time = sum(waiting_time) / n
print("Process\tBurst Time\tArrival Time\tPriority\tCompletion Time\
tWaiting Time")
for i in range(n):
print(processes[i][0], "\t\t", processes[i][1], "\t\t", processes[i][2], "\
t\t", processes[i][3], "\t\t", completion_time[i], "\t\t", waiting_time[i])
print("Average waiting time:", avg_waiting_time)
OUTPUT
