Operating System Lab
CPU Scheduling
Aims
1. Implement CPU Scheduling algorithms:
First-Come, First-Served (FCFS) Scheduling
Shortest-Job-Next (SJN) Scheduling
Priority Scheduling
Round Robin(RR) Scheduling
First Come First Serve
First Come First Serve is the full form of FCFS. It is the easiest and the simplest CPU
scheduling algorithm. In this type of algorithm, the process which requests the CPU gets
the CPU allocation first. This scheduling method can be managed with a FIFO queue.
Algorithm for FCFS
Step 1: Start the process
Step 2: Accept the number of processes in the ready Queue
Step 3: For each process in the ready Q, assign the process id and accept the CPU burst
time
Step 4: Set the waiting of the first process as ‘0’ and its burst time as its turnaround time
Step 5: for each process in the Ready Q calculate
(a) Waiting time for process(n)= waiting time of process (n-1) + Burst time of
process(n-1)
(b) Turnaround time for Process(n)= waiting time of Process(n)+ Burst time for
process(n)
Step 6: Calculate
(a) Average waiting time = Total waiting Time / Number of process
(b) Average Turnaround time = Total Turnaround Time / Number of process
Step 7: Stop the process.
1
Operating System Lab
2
Operating System Lab
Shortest-Job-Next (SJN) Scheduling
SJF is a full form of (Shortest job first) is a scheduling algorithm in which the process
with the shortest execution time should be selected for execution next. This scheduling
method can be preemptive or non-preemptive. It significantly reduces the average waiting
time for other processes awaiting execution.
Algorithm for SJN
Step 1: Start the process
Step 2: Accept the number of processes in the ready Queue
Step 3: For each process in the ready Q, assign the process id and accept CPU burst time
Step 4: Start the Ready Q according the shortest Burst time by sorting according to
lowest to highest burst time.
Step 5: Set the waiting time of the first process as ‘0’ and its turnaround time as its burst
time.
Step 6: For each process in the ready queue, calculate
(c) Waiting time for process(n)= waiting time of process (n-1) + Burst time of
process(n-1)
(d) Turnaround time for Process(n)= waiting time of Process(n)+ Burst time for
process(n)
Step 7: Calculate
(c) Average waiting time = Total waiting Time / Number of process
(d) Average Turnaround time = Total Turnaround Time / Number of process
Step 7: Stop the process
3
Operating System Lab
Priority Scheduling
Priority scheduling is a method of scheduling processes based on priority. In this method,
the scheduler selects the tasks to work as per the priority.
Priority scheduling also helps OS to involve priority assignments. The processes with
higher priority should be carried out first, whereas jobs with equal priorities are carried
out on a round-robin or FCFS basis. Priority can be decided based on memory
requirements, time requirements, etc.
Algorithm for Priority
Step 1: Start the process
Step 2: Accept the number of processes in the ready Queue
Step 3: For each process in the ready Q, assign the process id and accept the CPU burst
time
Step 4: Read the Priority for each process
Step 5: Sort the ready queue according to the priority number.
Step 6: Set the waiting of the first process as ‘0’ and its burst time as its turnaround time
Step 7: For each process in the Ready Q calculate
(e) Waiting time for process(n)= waiting time of process (n-1) + Burst time of
process(n-1)
(f) Turnaround time for Process(n)= waiting time of Process(n)+ Burst time for
process(n)
4
Operating System Lab
Step 8: Calculate
(e) Average waiting time = Total waiting Time / Number of process
(f) Average Turnaround time = Total Turnaround Time / Number of process
Step 9: Stop the process
Round Robin:
Round robin is the oldest, simplest scheduling algorithm. The name of this algorithm
comes from the round-robin principle, where each person gets an equal share of
something in turn. It is mostly used for scheduling algorithms in multitasking. This
algorithm method helps for starvation free execution of processes.
Algorithm for Round Robin:
Step 1: Start the process
Step 2: Accept the number of processes in the ready Queue and time quantum (or) time
slice
Step 3: For each process in the ready Q, assign the process id and accept the CPU burst
time
Step 4: Calculate the no. of time slices for each process where
No. of time slice for process (n) = burst time process (n)/time slice
Step 5: If the burst time is less than the time slice then the no. of time slices =1.
Step 6: Consider the ready queue is a circular Q, calculate
(a) Waiting time for process(n) = waiting time of process(n-1)+ burst time of
process(n-1 ) + the time difference in getting the CPU from process(n-1)
(b) Turnaround time for process(n) = waiting time of process(n) + burst time of
process(n)+ the time difference in getting CPU from process(n).
Step 7: Calculate
(g) Average waiting time = Total waiting Time / Number of process
(h) Average Turnaround time = Total Turnaround Time / Number of process
Step 8: Stop the process
Exercises:
5
Operating System Lab
Write programs to implement the above algorithms.
