Process scheduling algorithms(Preemptive and Non-Preemptive)

Introduction to Process Scheduling

In the realm of operating systems, process scheduling plays a pivotal role in ensuring efficient execution of processes. As computers juggle multiple tasks, process scheduling algorithms determine which process runs at any given time. The primary aim is to optimize CPU usage and ensure balanced, fair allocation of resources among processes. This article delves into the core concepts of preemptive and non-preemptive process scheduling algorithms, their practical applications, code implementations, and comparative analysis.

Core Concepts and Theory

Process Scheduling

Process scheduling is a fundamental task of the Operating System (OS) that manages the execution of processes by determining their sequence of execution on the CPU. The scheduler is responsible for maximizing CPU utilization while ensuring no process is starved of CPU time.

Types of Scheduling Algorithms

There are primarily two types of scheduling algorithms:

1. Preemptive Scheduling: Allows the OS to interrupt and suspend a currently running process to start or resume another process. Common in environments where time-sharing is needed.

2. Non-Preemptive Scheduling: Once a process gets control of the CPU, it runs to completion. The OS scheduler only schedules a new process when the current process finishes or an I/O operation commands it. Often used in batch systems.

Preemptive Scheduling

• Round Robin (RR): Processes are assigned a fixed time slice or quantum. If a process doesn't complete in this period, it goes to the back of the queue.
• Shortest Remaining Time First (SRTF): Similar to Shortest Job First (SJF) but preempts a running process if a new process has a shorter burst time.
• Priority Scheduling: Processes are assigned a priority. The CPU is allocated to the process with the highest priority.

Non-Preemptive Scheduling

• First-Come, First-Served (FCFS): Processes are attended to in the order of their arrival.
• Shortest Job First (SJF): Processes with the smallest execution time are processed first.
• Priority Scheduling: Similar to its preemptive counterpart but once a process starts, it runs to completion regardless of the arrival of higher-priority processes.

Practical Applications

Preemptive scheduling is ideal in real-time systems or time-sharing environments where process responsiveness is crucial. Non-preemptive scheduling, on the other hand, can be beneficial in batch processing where tasks are repetitive and less interruptive switching is needed.

Code Implementation and Demonstrations

Below is a simple Python demonstration of the Round Robin algorithm, a popular preemptive scheduling technique:

def round_robin(processes, burst_time, quantum):
    n = len(processes)
    wt = [0] * n  # Waiting time
    rem_bt = burst_time[:]

    t = 0  # Current time
    while True:
        done = True
        for i in range(n):
            if rem_bt[i] > 0:
                done = False
                if rem_bt[i] > quantum:
                    t += quantum
                    rem_bt[i] -= quantum
                else:
                    t += rem_bt[i]
                    wt[i] = t - burst_time[i]
                    rem_bt[i] = 0
        if done:
            break
    return wt

processes = [1, 2, 3]
burst_time = [10, 5, 8]
quantum = 4
print("Waiting times: ", round_robin(processes, burst_time, quantum))

This code simulates a Round Robin scheduling where each process receives a fair CPU share repeatedly in small bursts, ensuring a responsive system.

Comparison and Analysis

Preemptive scheduling offers improved responsiveness but at the cost of increased overhead due to frequent context switches. Non-preemptive scheduling, while simpler and sometimes more efficient in terms of resource utilization, can lead to longer wait times for processes arriving later in the queue.

Additional Resources and References

• Books: "Operating System Concepts" by Abraham Silberschatz, Peter B. Galvin, and Greg Gagne.
• Online Courses: Coursera's "Operating Systems and You: Becoming a Power User".
• Research Papers: "The Case for Preemptive Scheduling" by L. Lamport.

By understanding these scheduling algorithms, SDEs can ensure optimal system performance and resource management in their applications. Whether designing real-time systems or managing extensive batch processes, selecting the right scheduling strategy is critical for efficient CPU utilization.