Lecture Operating systems: Lesson 15 - Dr. Syed Mansoor Sarwar. The main topics covered in this lesson include: shortest-job-first, round-Robin scheduling, multi-level queues scheduling, multi-level feedback queues scheduling, non-preemptive SJF, SJF—CPU burst of a process, . | Operating Systems Lecture 15 Agenda for Today Review of previous lecture Shortest-job-first Round-Robin scheduling Multi-level queues scheduling Multi-level feedback queues scheduling Recap of lecture 28 April 2022 Copyright Virtual University of Pakistan Review of Lecture 14 Short-term scheduler Dispatcher Reasons for invoking scheduler Preemptive and non-preemptive schedulers Optimization criteria FCFS 28 April 2022 Copyright Virtual University of Pakistan Shortest-Job-First SJF Scheduling Process with the shortest CPU burst is scheduled first. Non-preemptive once CPU given to a process it cannot be preempted until completes its CPU burst. 28 April 2022 Copyright Virtual University of Pakistan Shortest-Job-First SJF Scheduling Preemptive if a new process arrives with CPU burst length less than remaining time of current executing process preempt it Shortest- Remaining-Time-First SRTF . SJF is optimal non-preemptive scheduling algorithm gives minimum average waiting time for a given set of processes. 28 April 2022 Copyright Virtual University of Pakistan Non-Preemptive SJF Process Arrival Time Burst Time P1 7 P2 4 P3 1 P4 4 Gantt chart P P P1 P 3 2 4 0 7 12 16 Average waiting time 0 6 3 7 4 4 28 April 2022 Copyright Virtual University of Pakistan Preemptive SJF Process Arrival Time Burst Time P1 7 P2 4 P3 1 P4 4 Gantt chart P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16 28Average April 2022 waiting time 9 1 Copyright Virtual University of 0 2 4 3 Pakistan SJF CPU Burst of a Process Can only estimate the length of the next CPU burst. Can be done by using the length of previous CPU bursts using exponential averaging. 28 April 2022 Copyright Virtual University of Pakistan Exponential Averaging Estimation based on historical data tn Length of nth CPU burst n 1 Estimate for n 1 st CPU burst 0 1 n 1 tn 1- n 28 April 2022 Copyright Virtual University of Pakistan Exponential Averaging Plugging in value for n we get n 1 tn 1- tn-1 1- n-1 tn 1- tn-1 1- 2
