Introduction

The process scheduler is the kernel component that decides which process gets the CPU and for how long. Since UNIX is a multi-tasking system with many runnable processes, the scheduler must ensure fairness, responsiveness, and efficient CPU utilization.

Goals of the Scheduler

1. Fairness — Every process should get a fair share of CPU time.
2. Responsiveness — Interactive processes should respond quickly.
3. Throughput — Maximize the number of processes completed per unit time.
4. Low Turnaround Time — Minimize the total time from submission to completion.
5. CPU Utilization — Keep the CPU busy as much as possible.

UNIX Scheduling Algorithm

UNIX uses a preemptive, priority-based, time-sharing scheduling algorithm.

Key Characteristics:

• Processes are assigned priorities — lower numbers mean higher priority.
• The process with the highest priority (lowest number) gets the CPU.
• If multiple processes have the same priority, they are scheduled in round-robin fashion.
• The scheduler is preemptive — it can forcibly remove a process from the CPU.
• Preemption happens only when a process returns from kernel mode to user mode (not while in kernel mode).

How Scheduling Works

1. Every process has a priority value that is recalculated periodically (every clock tick, typically 100ms).
2. The kernel maintains priority queues — separate queues for each priority level.
3. At each scheduling decision point, the scheduler picks the process from the highest-priority non-empty queue.
4. The selected process runs for one time quantum (time slice) or until it makes a system call / sleeps.

Priority Calculation

User Mode Priority Formula:

Priority = (recent CPU usage / 2) + base priority

• Base priority — default priority for user processes (typically 60).
• Recent CPU usage — a measure of how much CPU the process has used recently.
• CPU usage decays over time — a process that hasn't run for a while will have its CPU usage value reduced, causing its priority to improve.

Kernel Mode Priority:

• Processes sleeping in kernel mode get kernel-level priorities (lower values = higher priority).
• These are not interruptible by user-level scheduling.
• Example priorities: waiting for disk I/O (very high), waiting for buffer (high), waiting for terminal input (medium).

Priority Queue Structure

Priority   Queue
───────    ─────────────────────
  0        [Swapper]                     ← Highest (kernel)
  5        [Disk I/O wait]
 10        [Buffer wait]
 25        [Inode wait]
 27        [TTY input wait]
 ...
 60        [Process A, Process C]        ← Base user priority
 65        [Process B]                   ← Lower priority (high CPU usage)
 75        [Process D]                   ← Lowest priority

Scheduling Parameters

The nice Value

• Users can influence their process's priority using the nice command.
• nice value ranges from -20 (highest priority) to +19 (lowest priority).
• Default nice value is 0.
• Only root can set negative nice values (increase priority).
• Formula: Priority = base + nice + (CPU usage / 2)

Summary

• UNIX uses preemptive, priority-based scheduling.
• Priorities are dynamically recalculated based on CPU usage.
• Processes that use more CPU get lower priority (higher number) to ensure fairness.
• The nice command lets users adjust their process priority.
• Kernel-mode processes have higher priority than user-mode processes.