17 July - OS - CPU Scheduling
Duration: 1 hr 25 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
This lecture provides a comprehensive overview of CPU scheduling algorithms in operating systems. The instructor begins by defining non-preemptive and preemptive scheduling, illustrating process state transitions with diagrams. Key scheduling criteria such as CPU utilization, throughput, waiting time, and response time are introduced with real-world analogies. The lecture then details specific algorithms: First Come First Serve (FCFS), Shortest Job First (SJF), Shortest Remaining Time First (SRTF), Priority Scheduling, and Round Robin. Each algorithm is explained with definitions, advantages, disadvantages, and numerical examples involving Gantt charts and calculations for Turn Around Time (TAT) and Waiting Time (WT). Special phenomena like the Convoy Effect and Starvation are discussed, along with solutions like Ageing.
Chapters
0:00 – 2:00 00:00-02:00
The video opens with a black screen displaying the names "Sanchit Jain" and "Deepesh Prajapati" in white text. This serves as an introductory title card, identifying the instructors or contributors for the lecture series. The visual remains static, focusing solely on the text to establish the context for the upcoming technical discussion on operating systems and CPU scheduling.
2:00 – 5:00 02:00-05:00
The lecture transitions to the topic of "Type of scheduling," specifically focusing on Non-Preemptive scheduling. The slide defines this as a method where, once the CPU is allocated to a process, the process retains it until it releases it willingly. The text lists two conditions for leaving the CPU: completion of execution (Termination state) or performing I/O operations (Blocked state). A process state diagram is shown with transitions from Start to Ready, Ready to Running, Running to Terminated, and Running to Blocked, illustrating the flow of a process in this scheduling type.
5:00 – 10:00 05:00-10:00
The concept shifts to Pre-emptive scheduling. The slide explains that in this model, a process can be forced out of the CPU even if it hasn't completed its execution. The text lists four reasons for leaving the CPU: completion, voluntary I/O, arrival of a higher priority process, or expiration of a time quantum. The process state diagram is updated to show a transition from Running back to Ready, labeled with numbers 3 and 4, indicating pre-emption events where the process is interrupted and returned to the ready queue.
10:00 – 15:00 10:00-15:00
The instructor introduces "Scheduling criteria," explaining that different algorithms have different properties and may favor one process over another. The slide lists four key criteria to consider for efficient selection: CPU utilization, Throughput, Waiting time, and Response Time. The instructor draws a diagram showing multiple processes (P1 to Pn) being scheduled onto a single CPU, emphasizing the need to evaluate these metrics to choose the best algorithm for a specific system environment.
15:00 – 20:00 15:00-20:00
The lecture details "CPU utilization," defined as keeping the CPU as busy as possible. An image of a busy office environment is used as an analogy. Next, "Throughput" is defined as the number of processes completed per time unit, illustrated with an image of a car assembly line. "Waiting time" is described as the sum of periods spent waiting in the ready queue, shown with a picture of a long queue of people. Finally, "Response Time" is defined as the time taken to start responding, not the total time to output, illustrated with a food stall scene.
20:00 – 25:00 20:00-25:00
The focus moves to the "FCFS (First Come First Serve)" algorithm. It is described as the simplest scheduling algorithm where the process that requests the CPU first is allocated the CPU first. The implementation is managed by a FIFO Queue, and it is always non-preemptive. An image of a ticket counter queue is used to visualize the FIFO concept. The instructor then sets up a table with five processes (P0 to P4), listing their Arrival Time (AT) and Burst Time (BT) to begin a numerical example.
25:00 – 30:00 25:00-30:00
The instructor begins solving the FCFS example. The table is sorted by Arrival Time, showing P2 arriving at 0, P1 at 1, P0 at 2, P4 at 3, and P3 at 4. A Gantt chart is drawn below the table, showing the sequence of execution: P2 runs from 0 to 3, P1 from 3 to 5, P0 from 5 to 9, P4 from 9 to 10, and P3 from 10 to 12. The Completion Time (CT) for each process is calculated and filled into the table based on the end of their respective execution blocks in the Gantt chart.
30:00 – 35:00 30:00-35:00
The calculation continues with Turn Around Time (TAT) and Waiting Time (WT). TAT is calculated as CT - AT. For P2, TAT is 3 - 0 = 3. For P1, it is 5 - 1 = 4. For P0, it is 9 - 2 = 7. For P4, it is 10 - 3 = 7. For P3, it is 12 - 4 = 8. The instructor then calculates the average TAT by summing these values (3+4+7+7+8 = 29) and dividing by 5, resulting in an average of 5.8. Waiting Time is then calculated as TAT - BT.
35:00 – 40:00 35:00-40:00
The instructor calculates the Waiting Time for each process. For P2, WT is 3 - 3 = 0. For P1, WT is 4 - 2 = 2. For P0, WT is 7 - 4 = 3. For P4, WT is 7 - 1 = 6. For P3, WT is 8 - 2 = 6. The average Waiting Time is calculated by summing these values (0+2+3+6+6 = 17) and dividing by 5, resulting in an average of 3.4. The instructor highlights the Convoy Effect, explaining that if a smaller process has to wait for a larger process, it results in more average waiting time.
40:00 – 45:00 40:00-45:00
The Convoy Effect is further explained with an example. A table shows P0 with AT 0 and BT 100, and P1 with AT 1 and BT 2. In FCFS, P0 runs first, causing P1 to wait 100 units. The average waiting time is calculated as (0 + 99) / 2 = 49.5. The instructor then swaps the arrival times to show the improvement. With P1 arriving at 0 and P0 at 1, P1 runs first. The average waiting time drops significantly to (0 + 1) / 2 = 0.5, demonstrating the inefficiency of FCFS with long processes.
45:00 – 50:00 45:00-50:00
The lecture introduces "Shortest Job First (SJF)" and "Shortest Remaining Time First (SRTF)". SJF is non-preemptive, while SRTF is pre-emptive. The core principle is that the CPU is assigned to the process with the smallest burst time requirement. If there is a tie, FCFS is used to break it. The slide notes that this is a purely greedy approach and supports both non-preemptive and pre-emptive versions. The instructor sets up a new table for an example with five processes (P0 to P4).
50:00 – 55:00 50:00-55:00
The instructor solves the SJF example. The table lists Arrival Times and Burst Times. P0 arrives at 1 with BT 7, P1 at 2 with BT 5, P2 at 3 with BT 1, P3 at 4 with BT 2, and P4 at 5 with BT 8. The instructor draws a Gantt chart. At time 1, P0 arrives. At time 2, P1 arrives. At time 3, P2 arrives with the shortest burst time (1). P0 is preempted or waits? The slide shows a non-preemptive approach initially, but the text mentions SRTF. The Gantt chart shows P0 running from 1 to 3, then P2 runs from 3 to 4.
55:00 – 60:00 55:00-60:00
The Gantt chart for the SJF example is completed. P0 runs from 1 to 3 (2 units), then P2 runs from 3 to 4 (1 unit). Then P3 runs from 4 to 6 (2 units). Then P1 runs from 6 to 10 (4 units). Then P4 runs from 10 to 18 (8 units). The completion times are calculated: P0 at 18, P1 at 10, P2 at 4, P3 at 6, P4 at 18. The instructor calculates TAT and WT for each process based on these completion times.
60:00 – 65:00 60:00-65:00
The instructor calculates TAT and WT for the SJF example. TAT = CT - AT. P0: 18 - 1 = 17. P1: 10 - 2 = 8. P2: 4 - 3 = 1. P3: 6 - 4 = 2. P4: 18 - 5 = 13. The average TAT is calculated. The instructor then lists the advantages of SJF/SRTF, noting that the pre-emptive version guarantees minimal average waiting time and is considered optimal. It provides a standard for other algorithms and offers better response time compared to FCFS.
65:00 – 70:00 65:00-70:00
The disadvantages of SJF/SRTF are discussed. The main issue is that the algorithm cannot be implemented in practice because there is no way to know the length of the next CPU burst in advance. Additionally, processes with longer CPU burst requirements may go into starvation, as shorter processes keep getting priority. There is no idea of priority, and longer processes have poor response time. The instructor uses an analogy of a food stall to illustrate the concept of priority.
70:00 – 75:00 70:00-75:00
The lecture moves to "Priority Scheduling." An image of traffic in Bangalore is shown with the text "Banglore mein aapka swagat hai" (Welcome to Bangalore), using the chaotic traffic to illustrate priority where some vehicles might cut in line. The slide explains that processes are assigned a priority number. The instructor sets up a table with six processes (P0 to P5), listing their Arrival Time, Burst Time, and Priority. P3 has the highest priority (8).
75:00 – 80:00 75:00-80:00
The instructor solves the Priority Scheduling example. Two scenarios are considered: Non-Preemptive (N.P) and Pre-emptive (P). For Non-Preemptive, P0 arrives at 1 and runs. At time 3, P3 arrives with the highest priority (8). Since it's non-preemptive, P0 finishes its burst. Then P3 runs. The Gantt chart shows the sequence: P0, P3, P2, P5, P1, P4. The completion times are calculated based on this sequence.
80:00 – 84:59 80:00-84:59
The Pre-emptive Priority Scheduling calculation is shown. P0 starts at 1. At time 3, P3 arrives with higher priority, so P0 is preempted. P3 runs. The Gantt chart shows P0 running for 1 unit, then P3 running. The instructor calculates the average waiting time and turnaround time for both scenarios. The lecture concludes with a discussion on the advantages and disadvantages of Priority Scheduling, including the issue of starvation for low-priority processes and the solution of "Ageing," which gradually increases the priority of waiting processes.
The lecture systematically builds understanding of CPU scheduling by first defining fundamental concepts like pre-emption and scheduling criteria. It then progresses through specific algorithms, starting with the simple FCFS and its limitations like the Convoy Effect. The instructor then introduces more complex algorithms like SJF and Priority Scheduling, using numerical examples to demonstrate how they improve metrics like average waiting time. The use of Gantt charts and step-by-step calculations helps visualize the execution flow. Finally, the lecture addresses practical issues such as starvation and introduces solutions like Ageing, providing a complete picture of scheduling strategies in operating systems.