Non-Preemptive Scheduling Example: vs Preemptive CPU Scheduling

Study Notes

CPU scheduling is a crucial aspect of operating systems that determines how resources are allocated between concurrent processes. There are two primary types of CPU scheduling strategies: non-preemptive scheduling and preemptive scheduling. Each strategy has its strengths and weaknesses.

Non-Preemptive Scheduling

In non-preemptive scheduling, once a process starts executing, it continues until completion, i.e., it cannot be interrupted by other events while running. This means that if a higher priority process arrives before the lower one finishes, the system will wait until the current task completes before assigning the next task.

Non-preemptive scheduling is straightforward to implement because you do not need to track which tasks have been assigned lately. However, this simplicity comes with the cost of responsiveness, as once you start working with a task, it must finish before you can react to a new event. In addition, non-preemptive scheduling may lead to starvation and low throughput for certain processes if they are always started later than others.

One common example of non-preemptive scheduling is the first-come-first-served algorithm, where processes are executed in the order they arrive. Another example is shortest job first non-preemptive (SJF_NP), where the task with the smallest expected processing time is selected next.

Shortest Job First Non-Preemptive (SJF_NP) Algorithm

The shortest job first non-preemptive algorithm chooses the shortest job from among those available. It also ensures that when all jobs become equal, the job that arrived first gets processed first, ensuring fairness.

Advantages of SJF-NP Algorithm

Utilization of processor capacity increases when there are many small tasks.
Processors spend less time waiting for their turn due to shorter execution times of tasks.

Disadvantage of SJF-NP Algorithm

Disadvantageous for large tasks since smaller ones get preference over larger jobs.

Preemptive Scheduling

Preemptive scheduling allows for interruptions during task execution. If the arrival of a higher priority process occurs while a lower priority one is currently executing, the lower priority process can be stopped without completing and replaced by the higher preemption request. Preemptive scheduling does not suffer from the issue of responsiveness seen in non-preemptive strategies.

An example of preemptive scheduling is the Round Robin Algorithm, where each process is given a fixed quantum time slice within which it must complete or be interrupted to allow another process to run. This ensures that every process receives a fair share of CPU access time.

Round-Robin Scheduling

Round robin scheduling is a type of preemptive scheduling that allocates CPU cycles to all processes cyclically based on their arrival time. This means that after a fixed amount of processing time called a quantum, control is passed to the next process in line. Once all processes have completed their quantum, control returns to the first process again.

Advantages of Round Robin Algorithm

It ensures fairness among processes since every process gets a chance to use the CPU.
Preemption enables the system to react quickly to higher priority tasks.

Disadvantages of Round Robin Algorithm

Processes with smaller quantum times may not have enough time to complete within the quantum, leading to blocking.
As a result, it may cause more context switches, requiring more overhead and resources.

In conclusion, CPU scheduling is a crucial aspect of operating systems that ensures efficient resource allocation among concurrent processes. Non-preemptive scheduling, such as SJF-NP, is straightforward to implement but may suffer from responsiveness issues and may lead to starvation in some cases. Preemptive scheduling, like Round Robin, enables responsiveness and fairness but may require more overhead and context switches. The choice between these strategies depends on the specific requirements and constraints of the system being designed.

Description

Learn about the two primary types of CPU scheduling strategies in operating systems: non-preemptive and preemptive. Explore the advantages and disadvantages of non-preemptive scheduling with the Shortest Job First Non-Preemptive (SJF_NP) Algorithm, and understand preemptive scheduling with the Round Robin Algorithm.

CPU Scheduling Strategies: Non-Preemptive vs. Preemptive

Podcast Beta

Questions and Answers

____ scheduling does not allow interruption of processes once they start executing.

In non-preemptive scheduling, if a higher priority process arrives before the lower one finishes, the system will ____ until the current task completes.

Non-preemptive scheduling is straightforward to implement because you do not need to track which tasks have been assigned ___.

One common example of non-preemptive scheduling is the ____ algorithm.

____ scheduling may lead to starvation and low throughput for certain processes if they are always started later than others.

In shortest job first non-preemptive (SJF_NP), the task with the smallest expected processing time is selected next in a ____ manner.

The shortest job first non-preemptive algorithm chooses the ______ job from among those available.

SJF-NP is advantageous for increasing processor capacity utilization when there are many ______ tasks.

Preemptive scheduling allows for interruptions during task ______.

Round robin scheduling allocates CPU cycles to all processes ______ based on their arrival time.

Round Robin Algorithm ensures ______ among processes since every process gets a chance to use the CPU.

Processes with smaller quantum times in Round Robin Algorithm may not have enough time to complete within the ______.

Study Notes