Introduction

UNIX's scheduling algorithm combines elements of Round Robin and Multiple Feedback Queue scheduling to achieve fair CPU sharing among interactive and compute-bound processes.

---

Round Robin Scheduling

Concept:

• All runnable processes of the same priority are placed in a queue.
• Each process gets a fixed time quantum (time slice) to execute.
• After the time quantum expires, the process is moved to the back of the queue, and the next process in the queue gets the CPU.
• This continues in a circular fashion.

How it works in UNIX:

Time Quantum = 100ms (1 clock tick)

Queue [P1, P2, P3] (same priority)

Step 1: P1 runs for 100ms → moves to back → [P2, P3, P1]
Step 2: P2 runs for 100ms → moves to back → [P3, P1, P2]
Step 3: P3 runs for 100ms → moves to back → [P1, P2, P3]
... (continues)

Characteristics:

Effect of Quantum Size:

• Too small → excessive context switching overhead.
• Too large → becomes like FCFS (First Come First Served), poor responsiveness.
• UNIX uses a balanced time quantum of ~100ms.

---

Multiple Feedback Queue Scheduling (MFQ / MLFQ)

Concept:

• Instead of a single queue, the system maintains multiple priority queues.
• Processes can move between queues based on their behavior (feedback).
• Interactive processes (I/O-bound) get promoted to higher-priority queues.
• CPU-intensive processes get demoted to lower-priority queues.

How UNIX Implements This:

1. There are multiple priority levels, each with its own queue (e.g., levels 0 to 127).
2. The scheduler always runs the process from the highest-priority non-empty queue.
3. Within each queue, processes are scheduled using Round Robin.
4. Periodically (every second), priorities are recalculated:

• p_cpu is incremented each clock tick while the process runs.
• Every second, p_cpu is decayed: p_cpu = p_cpu / 2
• Priority is recalculated: p_usrpri = base + (p_cpu / 2) + p_nice

1. Processes that used a lot of CPU get demoted (higher priority number).
2. Processes that haven't run recently get promoted (lower priority number).

Feedback Mechanism:

Multiple Priority Queues:

Priority 0:  [highest] ← Kernel processes
Priority 10: [...]
Priority 20: [...]
...
Priority 50: [I/O-bound processes move UP here]
Priority 60: [New processes start here] ← Base
Priority 70: [CPU-bound processes drop DOWN here]
Priority 80: [Heavy CPU users]
...
Priority 127: [lowest]

Example:

• Process A is CPU-bound (uses full time quantum repeatedly).
• Each second, its p_cpu is high → priority increases (worsens) → drops to lower queue.
• Process B is I/O-bound (sleeps often, uses little CPU).
• Its p_cpu is low → priority decreases (improves) → stays in higher queue.
• Result: Interactive processes get better response times, while CPU-bound processes still get their share but with lower priority.

How They Work Together in UNIX

Step 1: All processes start at base priority (e.g., 60).
Step 2: Within priority 60, Round Robin with time quantum.
Step 3: After 1 second, priorities are recalculated:
        - Heavy CPU users → priority 70, 80, ... (demoted)
        - Light CPU users → priority 55, 50, ... (promoted)
Step 4: Scheduler picks from highest-priority queue first.
Step 5: Repeat — continuous feedback loop.

Advantages of MLFQ

• Adaptive — automatically adjusts to process behavior.
• Fair — CPU-bound processes don't starve I/O-bound ones.
• Responsive — interactive processes get quick access to CPU.
• No prior knowledge needed — the system learns from process behavior.

Summary

• Round Robin ensures equal CPU time among same-priority processes.
• Multiple Feedback Queue uses priority decay to adapt scheduling to process behavior.
• CPU-intensive processes are demoted; I/O-intensive processes are promoted.
• Together, they provide fair, responsive scheduling in multi-user UNIX systems.