CPU SCHEDULING ALGORITHM simulation.pptx

THIS PPT IS ON CPU SCHEDULING ALGOS

1. CPU SCHEDULING ALGORITHM Team: Krishnakanth a - 22l230 Nahul aariya dk- 22l238

2. CPU SCHEDULING ALGORITHM TYPES Fcfs (first come first serve) Sjf (shortest job first) Srjf (shortest remaining job first) Rr (round robin)

3. First come – first served (FCFS), is the simplest scheduling algorithm. It simply queues processes according to the order they arrive in the ready queue. In this algorithm, the process that comes first will be executed first and next process starts only after the previous gets fully executed. No process is interrupted once it starts; it runs to completion. FCFS:

4. The process with the shortest burst time is executed first. Minimizes average waiting time but requires knowledge of burst times in advance. Non-preemptive: once a process starts, it cannot be interrupted. May lead to starvation of longer processes if many short processes keep arriving. SJF:

5. Preemptive version of SJF: a process can be interrupted if a shorter process arrives. Aims to minimize waiting time by continuously selecting the process with the shortest remaining time. Requires frequent context switching, which adds overhead. Like SJF, it can cause starvation for longer processes. SRJF:

6. Each process gets a fixed time slice (time quantum) to execute before switching to the next. Preemptive: if a process doesn’t finish in its time quantum, it's placed back in the queue. Ensures fairness, as all processes get CPU time. Ideal for interactive systems where responsiveness is key. RR:

7. FCFS: avg_turn = sum( turn_t ) / n avg_wait = sum( wait_t ) / n return comp_t , turn_t , wait_t , avg_turn , avg_wait def fcfs ( arr_t , burst_t ): n = len ( arr_t ) comp_t , turn_t , wait_t = [0]*n, [0]*n, [0]*n curr_t = 0 for i in range(n): curr_t = max( curr_t , arr_t [ i ]) + burst_t [ i ] comp_t [ i = curr_t turn_t [ i ] = comp_t [ i ] - arr_t [ i ] wait_t [ i ] = turn_t [ i ] - burst_t [ i ]

8. SJF: curr_t += rem_bt [ short_idx ] comp_t [ short_idx ], rem_bt [ short_idx ] = curr_t , 0 completed += 1 turn_t [ short_idx ] = comp_t [ short_idx ] - arr_t [ short_idx ] wait_t [ short_idx ] = turn_t [ short_idx ] - burst_t [ short_idx ] avg_turn = sum( turn_t ) / n avg_wait = sum( wait_t ) / n return comp_t , turn_t , wait_t , avg_turn , avg_wait def sjf ( arr_t , burst_t ): n = len ( arr_t ) rem_bt , comp_t , turn_t , wait_t = burst_t [:], [0]*n, [0]*n, [0]*n curr_t , completed = 0, 0 while completed < n: short_idx = -1 short_time = float('inf') for i in range(n): if arr_t [ i ] <= curr_t and rem_bt [ i ] < short_time and rem_bt [ i ] > 0: short_time , short_idx = rem_bt [ i ], i if short_idx == -1: curr_t += 1 continue

9. SRJF: if rem_bt [ short_idx ] == 0: comp_t [ short_idx ], completed = curr_t , completed + 1 turn_t [ short_idx ] = comp_t [ short_idx ] - arr_t [ short_idx ] wait_t [ short_idx ] = turn_t [ short_idx ] - burst_t [ short_idx ] avg_turn = sum( turn_t ) / n avg_wait = sum( wait_t ) / n return comp_t , turn_t , wait_t , avg_turn , avg_wait def srfj ( arr_t , burst_t ): n = len ( arr_t ) rem_bt , comp_t , turn_t , wait_t = burst_t [:], [0]*n, [0]*n, [0]*n curr_t , completed = 0, 0 while completed < n: short_idx = -1 short_time = float('inf') for i in range(n): if arr_t [ i ] <= curr_t and rem_bt [ i ] < short_time and rem_bt [ i ] > 0: short_time , short_idx = rem_bt [ i ], i if short_idx == -1: curr_t += 1 continue rem_bt [ short_idx ] -= 1 curr_t += 1

10. RR: else: curr_t += rem_bt [ i ] comp_t [ i ] = curr_t rem_bt [ i ] = 0 completed += 1 turn_t [ i ] = comp_t [ i ] - arr_t [ i ] wait_t [ i ] = turn_t [ i ] - burst_t [ i ] avg_turn = sum( turn_t ) / n avg_wait = sum( wait_t ) / n return comp_t , turn_t , wait_t , avg_turn , avg_wait def calculate_rr ( arr_t , burst_t , tq ): n = len ( arr_t ) rem_bt , comp_t , turn_t , wait_t = burst_t [:], [0]*n, [0]*n, [0]*n curr_t , completed = 0, 0 while completed < n: for i in range(n): if arr_t [ i ] <= curr_t and rem_bt [ i ] > 0: if rem_bt [ i ] > tq : curr_t += tq rem_bt [ i ] -= tq

11. OUTPUT:

12. PROBLEM: PROCESS ARRIVAL TIME BURST TIME A 3 B 2 6 C 4 4 D 6 5 E 8 2

13. FCFS: PROCESS ARRIVAL TIME BURST TIME WAITING TIME TURNAROUND TIME AVERAGE WAITING TIME AVERAGE TURNAROUND TIME A 3 3 4.6 8.6 B 2 6 1 7 C 4 4 5 9 D 6 5 7 12 E 8 2 10 12 A B C D E GANTT CHART: 3 9 13 18 20

14. SJF: PROCESS ARRIVAL TIME BURST TIME WAITING TIME TURNAROUND TIME AVERAGE WAITING TIME AVERAGE TURNAROUND TIME A 3 3 3.6 7.6 B 2 6 1 7 C 4 4 7 11 D 6 5 9 11 E 8 2 1 3 A B B C D E E C D GANTT CHART: 3 9 11 15 2 2 4 6 8

15. SRJF: PROCESS ARRIVAL TIME BURST TIME WAITING TIME TURNAROUND TIME AVERAGE WAITING TIME AVERAGE TURNAROUND TIME A 3 3 3.2 7.2 B 2 6 12 18 C 4 4 4 D 6 5 4 9 E 8 2 2 A B B C D E D B GANTT CHART: 3 4 8 10 20 15 2 6

16. RR: (Quantum->4) PROCESS ARRIVAL TIME BURST TIME WAITING TIME TURNAROUND TIME AVERAGE WAITING TIME AVERAGE TURNAROUND TIME A 3 3 6 10 B 2 6 11 17 C 4 4 3 7 D 6 5 9 14 E 8 2 7 9 A B C D E B D GANTT CHART: 3 11 15 17 20 7 19

17. REFERENCE: https://www.gatevidyalay.com/cpu-scheduling-practice-problems-numericals/ https://www.geeksforgeeks.org/cpu-scheduling-in-operating-systems/?ref=lbp

18. THANK YOU