L-2.8: Pre-emptive Priority Scheduling Algorithm with Example | Operating System

Understanding Priority Scheduling with Preemption

Introduction to Priority Scheduling

• The video introduces the concept of priority scheduling in CPU management, focusing on preemptive modes. It presents a numerical example involving four processes with specified arrival and burst times.

• The criteria for priority scheduling is explained: higher numbers indicate higher priorities, which can be confusing if not clearly stated.

Process Execution Steps

• The speaker emphasizes the importance of identifying which process has arrived at time zero before executing any tasks.

• If only one process arrives, it is executed immediately; however, if multiple processes arrive simultaneously, priority must be assessed.

Handling Multiple Processes

• At time 1, both P1 and P2 are present. Since P2 has a higher priority (higher number), it preempts P1.

• In preemptive mode, each process runs for only one time unit to avoid skipping over higher-priority processes.

Gantt Chart Execution

• After running P1 for one time unit, the remaining burst time is reduced accordingly.

• At time 2, all three processes (P1, P2, and now P3) are checked for their priorities again.

Continuing Process Management

• As execution continues at each timestamp (e.g., from 3 to 4), the highest-priority process is always selected to run next.

• When a new process arrives (P4 at time 4), its priority is evaluated against existing processes before deciding which to execute next.

Finalizing Execution Order

• Once all processes have been executed based on their priorities and remaining burst times are accounted for correctly.

• The final steps involve executing the remaining processes based on their priorities until completion times are established.

Conclusion of Scheduling Example

• The video concludes by summarizing that once all processes have arrived and been prioritized correctly, they can be executed without further interruption as non-preemptive scheduling.

How to Calculate Turnaround Time and Waiting Time in Scheduling

Understanding Completion Time and Turnaround Time

• The completion time (CT) for processes is calculated by noting the last written process times. For example, P2 has a CT of 8, P3 is 4, and P4 is 5.

• The formula for calculating turnaround time (TAT) is: TAT = Completion Time - Arrival Time. This results in values such as 12, 7, 2, and 1.

Calculating Waiting Time

• Waiting time (WT) can be derived from the formula: WT = Turnaround Time - Burst Time. It’s crucial to use the original burst times to avoid common mistakes.

• Example calculations yield waiting times of:

• For TAT of 12 with burst time of 5: WT = 12 - 5 = 7

• For TAT of 7 with burst time of 4: WT = 7 - 4 = 3

• For TAT of 2 with burst time of 4: WT = 2 - 4 = 0

• For TAT of 1 with burst time of 1: WT = 1 -1 = 0

Average Waiting and Turnaround Times

• To find average waiting or turnaround times, sum the individual times and divide by the number of processes.

• Total turnaround time (TAT): 22, divided by number of processes (4), gives an average TAT of 5.5.

• Total waiting time (WT): 10, divided by number of processes (4), results in an average WT of 2.5.

Priority Scheduling Insights

• In priority scheduling with preemption, remember that you only run each process for up to one unit at a time.

• When two or more processes have equal priority and arrive simultaneously, check their arrival times to determine which runs first.