CPU scheduling

A machine usually has far more runnable threads than CPU cores. The scheduler is the part of the OS that picks which ready thread gets a core next. It runs whenever a thread blocks, finishes, or (in preemptive scheduling) uses up its time slice or is overtaken by a higher-priority thread.

Classic algorithms are First-Come First-Served (FCFS), Shortest Job First (SJF) and its preemptive form Shortest Remaining Time First (SRTF), Priority scheduling, Round Robin (RR) with a fixed time slice called a quantum, and the Multilevel Feedback Queue (MLFQ). Real operating systems combine these ideas, for example Linux's Completely Fair Scheduler and its successor EEVDF.

1. 1Key metrics: waiting time (time spent in the ready queue), turnaround time (finish time minus arrival time), response time (first time it runs minus arrival), throughput (jobs finished per unit of time) and CPU utilisation.
2. 2FCFS runs jobs in arrival order without preemption. Simple, but one long job makes every short job behind it wait (the convoy effect).
3. 3SJF runs the shortest job first and gives the minimum average waiting time when all jobs are known in advance; SRTF is its preemptive version. The catch: real burst lengths are unknown, so they are estimated (for example from past bursts), and long jobs can starve.
4. 4Priority scheduling runs the highest-priority job first. Low-priority jobs can starve; aging (slowly raising the priority of jobs that have waited long) fixes this.
5. 5Round Robin gives each job a quantum (for example 10-100 ms) in turn, then moves it to the back of the queue. It gives good response time; too small a quantum wastes time on context switches, too large turns it into FCFS.
6. 6MLFQ uses several queues: new jobs start at high priority with short quanta; jobs that use their full quantum drop to lower queues. Interactive jobs stay responsive while long CPU-bound jobs still make progress. Periodic priority boosts prevent starvation.

from collections import deque

def round_robin(bursts, quantum):
    """bursts: {name: burst_time}, all arriving at time 0.
    Returns each process's waiting time."""
    remaining = dict(bursts)
    ready = deque(bursts)          # names in arrival order
    time, finish = 0, {}
    while ready:
        p = ready.popleft()
        run = min(quantum, remaining[p])
        time += run
        remaining[p] -= run
        if remaining[p] > 0:
            ready.append(p)        # preempted: back of the queue
        else:
            finish[p] = time
    # waiting time = finish time - burst time (arrival is 0)
    return {p: finish[p] - bursts[p] for p in bursts}

print(round_robin({"P1": 24, "P2": 3, "P3": 3}, 4))
# {'P1': 6, 'P2': 4, 'P3': 7} -> average 5.67

Simulates Round Robin for jobs that all arrive at time 0 and returns each waiting time. With the textbook input the result matches the hand trace: 6, 4 and 7 ms. Each job is queued at most once at a time, so the loop runs once per time slice.

Cost: Picking the next job is O(1) for FCFS and Round Robin queues and O(log n) with a heap or balanced tree for SJF, priority or CFS-style schedulers.