Scheduling Algorithms - Priority Scheduling

Summary

The lecture discusses priority scheduling, a CPU scheduling algorithm that assigns a priority to each process. The CPU is allocated to the process with the highest priority, and if multiple processes share the same priority, they are scheduled in First Come, First Serve (FCFS) order. The lecture explains both pre-emptive and non-pre-emptive priority scheduling, highlighting its potential issue of starvation, where low-priority processes may wait indefinitely. A solution, known as aging, is proposed to gradually increase the priority of long-waiting processes, ensuring fairness in CPU allocation.

Takeaways

• 📅 Priority scheduling is an algorithm that assigns a priority to each process, with the CPU allocated to the process with the highest priority first.
• 🛑 If two or more processes have the same priority, they are scheduled in a First-Come-First-Serve (FCFS) order.
• 🔄 Priority scheduling can be either preemptive or non-preemptive, with preemptive scheduling allowing a higher-priority process to interrupt a running lower-priority process.
• 🗂 In non-preemptive priority scheduling, the newly arrived higher-priority process waits in the queue until the currently running process finishes its execution.
• 📈 Shortest Job First (SJF) is a form of priority scheduling where priority is determined by the inverse of the predicted next CPU burst (shorter burst, higher priority).
• ⚠️ A significant issue with priority scheduling is the risk of indefinite blocking or starvation, where low-priority processes may never get executed if higher-priority processes keep arriving.
• ⏳ Aging is a technique used to prevent starvation by gradually increasing the priority of processes that have been waiting in the system for a long time.
• 🧮 An example calculation in the video demonstrates how the average waiting time for a set of processes following priority scheduling can be determined using a Gantt chart.
• 📊 In the example, the processes are arranged by priority, and their waiting times are calculated based on their order of execution in the Gantt chart.
• ✅ The technique of aging ensures that even low-priority processes eventually gain a higher priority, preventing them from being indefinitely blocked.

Q & A

What is the priority scheduling algorithm?

In priority scheduling, each process is assigned a priority, and the CPU is allocated to the process with the highest priority. If two processes have the same priority, they are scheduled using the First-Come-First-Serve (FCFS) order.

How does priority scheduling differ from shortest job first (SJF) scheduling?

SJF can be viewed as a form of priority scheduling where the priority is the inverse of the predicted next CPU burst. Processes with shorter CPU bursts have higher priorities.

What is the difference between pre-emptive and non-pre-emptive priority scheduling?

In pre-emptive priority scheduling, if a newly arrived process has a higher priority than the currently running process, it preempts the CPU. In non-pre-emptive priority scheduling, the currently running process continues until completion, and the new process is placed at the head of the ready queue.

What happens in pre-emptive priority scheduling when a new process arrives with a higher priority?

The CPU is preempted from the currently executing process and given to the newly arrived higher-priority process.

What is a major problem with priority scheduling?

A major problem with priority scheduling is indefinite blocking or starvation, where low-priority processes may wait indefinitely if high-priority processes continuously arrive.

What is aging in the context of priority scheduling?

Aging is a technique used to gradually increase the priority of processes that have been waiting in the system for a long time. This helps prevent indefinite blocking or starvation.

How can aging solve the problem of starvation in priority scheduling?

By gradually increasing the priority of waiting processes, aging ensures that even low-priority processes eventually reach a higher priority level and are given CPU time.

How is the waiting time calculated in priority scheduling?

Waiting time is calculated by looking at when each process gets the CPU for the first time in the Gantt chart. The waiting time is the difference between the process's arrival time and the time it starts executing.

What is the average waiting time for the given example in the script?

The average waiting time for the set of processes in the example is 8.2 milliseconds, calculated by adding the waiting times of all processes and dividing by the number of processes.

Can you provide an example of how aging might work with a priority system ranging from 0 to 127?

If priorities range from 127 (lowest) to 0 (highest), aging could increase a waiting process's priority by 1 every 15 minutes. For example, a process starting with a priority of 127 will eventually have its priority increased to a higher level over time, ensuring it gets CPU time.