Process Scheduling Algorithms

Process Scheduling Algorithms

Description
Process scheduling algorithms are methods used by operating systems to decide which ready process gets CPU time. Their core goals include improving CPU utilization, ensuring fairness, reducing response time, etc. Different scheduling algorithms are suitable for different scenarios (such as batch processing systems, interactive systems, etc.).

Key Concepts

  1. CPU-I/O Burst Cycle: Process execution consists of alternating CPU computation and I/O wait periods.
  2. Scheduling Queues: Ready queue (holds processes waiting for CPU), device queue (processes waiting for I/O).
  3. Preemptive vs. Non-preemptive:
    • Non-preemptive: A process runs until it voluntarily releases the CPU.
    • Preemptive: The scheduler can forcibly suspend the current process and allocate the CPU to another process.

Detailed Explanation of Common Scheduling Algorithms

1. First-Come, First-Served (FCFS)

  • Rule: Allocates CPU to processes in the order they arrive in the ready queue; non-preemptive.
  • Example: Suppose processes P1, P2, P3 arrive at times 0, 1, 2, with required CPU times of 24, 3, and 3 respectively.
    • Timeline:
      P1 runs 0→24 (P2, P3 wait in queue)
      P2 runs 24→27
      P3 runs 27→30
    • Average Waiting Time: (0 + 23 + 25) / 3 = 16
  • Disadvantage: Short processes may wait a long time behind a long process ("convoy effect").

2. Shortest Job First (SJF)

  • Rule: Selects the process with the shortest estimated run time; can be non-preemptive or preemptive.
  • Non-preemptive SJF Example: Process arrival time/run time: P1(0,6), P2(2,4), P3(4,2)
    • At time 0, only P1, runs 0→6
    • At time 6, ready queue has P2(run time 4), P3(run time 2), selects P3 first → runs 6→8, then P2 runs 8→12
    • Average Waiting Time: P1(0), P2(8-2=6), P3(6-4=2), average=(0+6+2)/3≈2.67
  • Preemptive SJF (Shortest Remaining Time First):
    • Time 0, P1 runs.
    • Time 2, P2 arrives, remaining time (4) < P1 remaining time (4), P1 is preempted, P2 runs.
    • Time 4, P3 arrives, shortest remaining time (2), P2 is preempted, P3 runs until 6 ends. Then selects the shortest remaining time process P2(remaining 2) runs until 8, finally P1 runs until 14.
    • Average Waiting Time: P1(0+8-2=6), P2(2-2=0), P3(4-4=0), average=2.

3. Priority Scheduling

  • Rule: Each process has a priority; selects the process with the highest priority (a smaller number may indicate higher priority).
  • Problem: Low-priority processes may experience "starvation" (never get CPU).
  • Solution: Use "aging" technique, gradually increasing the priority of waiting processes.

4. Round Robin (RR)

  • Rule: Assigns a fixed time slice (e.g., 10ms) to each process; after timeout, process is moved to the end of the ready queue; preemptive.
  • Example: Processes P1(0,5), P2(1,3), P3(2,2), time quantum = 2:
    • Time 0: P1 runs 2 units (remaining 3)
    • Time 2: queue P2(3), P3(2), P2 runs 2 units (remaining 1)
    • Time 4: queue P3(2), P1(3), P3 runs 2 units (ends)
    • Time 6: queue P1(3), P2(1), P1 runs 2 units (remaining 1)
    • Time 8: queue P2(1), P1(1), P2 runs 1 unit (ends)
    • Time 9: P1 runs 1 unit (ends)
  • Characteristics: A large time quantum degenerates to FCFS; too small increases context-switching overhead.

5. Multilevel Queue Scheduling

  • Scenario: Divides the ready queue into multiple separate queues (e.g., foreground interactive queue, background batch queue), each can use different scheduling algorithms (e.g., RR for foreground, FCFS for background).
  • Scheduling between queues:
    • Fixed priority: Process foreground queue first, may cause background starvation.
    • Time slice allocation: For example, foreground queue gets 80% CPU time, background gets 20%.

6. Multilevel Feedback Queue (MLFQ)

  • Goal: Optimize both turnaround time and response time without prior knowledge of process run times.
  • Example Rules:
    • Set up multiple queues Q0, Q1, Q2..., with decreasing priority and increasing time slices (e.g., Q0 time slice = 8ms, Q1 = 16ms).
    • New processes enter the highest priority queue Q0.
    • If a process does not complete within its time slice, it's demoted to the next lower priority queue.
    • Periodically move all processes back to the highest queue to prevent starvation.
  • Advantages: Short jobs finish quickly, long jobs do not starve completely.

Summary

  • CPU-bound processes: Suitable for SJF to reduce average waiting time.
  • Interactive processes: Suitable for RR or priority scheduling to ensure responsiveness.
  • General-purpose systems: Multilevel feedback queue is a practical method to balance multiple metrics.
    Choosing an algorithm requires trade-offs between fairness, efficiency, overhead, and implementation complexity.