30 July - OS - DSS 3 (CPU Scheduling 2)
Duration: 1 hr 20 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
This video lecture covers several advanced CPU scheduling problems from an Operating Systems course. The instructor systematically solves problems involving weighted mean completion time, Shortest Remaining Time First (SRTF) scheduling, I/O and computation phase scheduling, Round Robin time-sharing, and periodic task scheduling. For each problem, she defines the parameters, sets up tables or Gantt charts, performs calculations, and derives the final answer. The lecture emphasizes the importance of understanding scheduling algorithms and their impact on metrics like waiting time, completion time, and CPU utilization.
Chapters
0:00 – 2:00 00:00-02:00
The video begins with the instructor introducing a problem about minimizing weighted mean completion time for n jobs. She underlines key terms on the PDF: 'weighted mean completion time', 'execution time $t_i$', 'weight $w_i$', and 'minimize'. The formula $ rac{\sum w_i T_i}{\sum w_i}$ is visible. She emphasizes that the goal is to find the execution order that minimizes this value.
2:00 – 5:00 02:00-05:00
The instructor sets up a table with four processes (P1, P2, P3, P4) having weights 1, 2, 3, 4 and execution times 3, 5, 2, 4 respectively. She begins calculating the weighted mean completion time for a specific sequence. She writes down the completion times for each process in the sequence, starting with P3.
5:00 – 10:00 05:00-10:00
She continues calculating the weighted mean for different sequences. She compares the results, noting that a lower value is better. She writes down the sequence P3, P4, P2, P1 and calculates the total weighted completion time. She writes down the final calculation $ rac{14 imes 1 + 11 imes 2 + 2 imes 3 + 9 imes 4}{10}$.
10:00 – 15:00 10:00-15:00
The instructor moves to a new problem involving four processes with arrival times and CPU burst times. The algorithm is 'preemptive Shortest Remaining Time First'. She needs to find the value of Z given the average waiting time is 1 millisecond. She sets up a table with P1, P2, P3, P4.
15:00 – 20:00 15:00-20:00
She draws a Gantt chart for the SRTF algorithm. She tracks the execution of processes based on their remaining burst times. She calculates the waiting time for each process. She writes down the waiting times: P1 waits 0, P2 waits 0, P3 waits 3, P4 waits Z.
20:00 – 25:00 20:00-25:00
She sets up the equation for the average waiting time: $ rac{0 + 0 + 3 + Z}{4} = 1$. She solves for Z, finding Z = 1. She verifies this by checking the Gantt chart. She writes down the final value of Z.
25:00 – 30:00 25:00-30:00
The instructor moves to a problem about three processes with I/O and computation phases. The algorithm is 'shortest remaining compute time first'. She breaks down the execution times: 20% I/O, 70% compute, 10% I/O. She needs to find the percentage of time the CPU remains idle.
30:00 – 35:00 30:00-35:00
She draws a timeline for the three processes with total execution times of 10, 20, and 30 units. She marks the compute and I/O phases for each process. She tracks when the CPU is busy and when it is idle. She writes down the timeline.
35:00 – 40:00 35:00-40:00
She calculates the total time and the idle time. She determines that the CPU is idle for a specific duration. She computes the percentage of idle time as $ rac{ ext{Idle Time}}{ ext{Total Time}} imes 100$. She writes down the final percentage.
40:00 – 45:00 40:00-45:00
The instructor moves to a problem about three processes A, B, C executing loops. It's a time-sharing system with Round Robin scheduling. Time slice is 50ms. She needs to find when process C completes its first I/O operation. She sets up the timeline with arrival times 0, 5, 10.
45:00 – 50:00 45:00-50:00
She simulates the Round Robin scheduling. She tracks the execution of A, B, and C. She notes that A runs for 50ms, then B, then C. She calculates the time when C gets its first CPU burst. She writes down the timeline.
50:00 – 55:00 50:00-55:00
She calculates the completion time of C's first I/O. She adds the CPU burst time (200ms) and I/O time (500ms) to the start time. She writes down the final time. She verifies the calculation.
55:00 – 60:00 55:00-60:00
The instructor moves to a problem about periodic tasks T1, T2, T3. Priority is inverse of period. Preemptions are allowed. She needs to find when the first instance of T3 completes. She lists the arrival times and execution times.
60:00 – 65:00 60:00-65:00
She simulates the periodic task scheduling. She tracks the execution of T1, T2, and T3. She marks the completion of T3's first instance. She writes down the timeline. She notes the preemptions.
65:00 – 70:00 65:00-70:00
She continues the simulation, tracking the execution of T3. She notes that T3 is preempted by T1 and T2. She calculates the total time T3 spends on the CPU. She writes down the timeline.
70:00 – 75:00 70:00-75:00
She calculates the completion time of T3. She adds the execution times of T1 and T2 to the start time. She writes down the final time. She verifies the result.
75:00 – 80:00 75:00-80:00
She verifies the result. She checks the timeline to ensure T3 completes at the calculated time. She writes down the final answer. She summarizes the key points of the problem.
80:00 – 80:27 80:00-80:27
The video ends. The instructor concludes the lecture. The screen shows the final answer for the periodic task problem.
The lecture progresses through a series of increasingly complex CPU scheduling problems. It starts with a theoretical problem on minimizing weighted mean completion time, establishing the importance of the ratio $w_i/t_i$. It then moves to practical scheduling algorithms like SRTF, where the instructor demonstrates how to calculate waiting times and solve for unknown parameters. The lecture then covers mixed I/O and compute phases, requiring the student to track CPU idle time. Finally, it addresses Round Robin time-sharing and periodic task scheduling, emphasizing the need to simulate the execution timeline step-by-step. Each problem builds on the previous one, reinforcing the concepts of scheduling metrics and algorithm behavior.