• Processes vs. Threads, Context Switching
• Scheduling Goals and Metrics
• CFS: Completely Fair Scheduler
• MLFQ: Multi-Level Feedback Queue
• Real-time Scheduling (RM, EDF)
• Exercises

• Process: isolated address space + resources; Thread: schedulable execution context within a process sharing address space.
• Context switch: save/restore registers, PC, stack, MMU state; TLB shootdowns may occur on process switches.
• Preemption: timer interrupts drive timeslicing; optional cooperative yields for runtimes (e.g., green threads).
• Affinity: pinning threads to cores reduces cache misses but may hurt load balance.

• Fairness, throughput, latency/response time, turnaround time, deadline satisfaction, and predictability.
• Workload types: CPU-bound vs I/O-bound; interactive vs batch; real-time (hard/soft).
• Metrics: CPU utilization, average wait/response, tail latency, starvation freedom.

Linux CFS approximates an ideal fair scheduler using a red–black tree ordered by virtual runtime (vruntime).

// Tiny CFS-style simulator
class RBTLike { // use array sorted by key for simplicity
  constructor() { this.a = []; }
  insert(task) { this.a.push(task); this.a.sort((x,y)=>x.vr - y.vr); }
  popMin() { return this.a.shift(); }
  update(task) { this.insert(task); }
  get size() { return this.a.length; }
}

function simulateCFS(tasks, slice=5, niceWeights={0:1.0}) {
  // tasks: [{id, vr:0, weight:1.0, need: runtime}]
  const runq = new RBTLike(); tasks.forEach(t=>runq.insert(t));
  const log = [];
  while (runq.size) {
    const t = runq.popMin();
    const actual = Math.min(slice, t.need);
    t.need -= actual;
    const invWeight = 1.0 / (t.weight || 1.0);
    t.vr += actual * invWeight; // weighted fairness
    log.push({id:t.id, ran:actual, vr:t.vr});
    if (t.need > 0) runq.update(t);
  }
  return log;
}

• Key idea: pick task with smallest vruntime; weight by nice level; target latency determines slice.
• Features: per-CPU runqueues, group scheduling, bandwidth control for cgroups; wakeup preemption.

• Multiple priority queues; new tasks start high; consuming CPU lowers priority; yielding or I/O boosts priority.
• Time slice increases at lower priorities to favor throughput; aging prevents starvation.

// Sketch: queues[0..L-1], 0 is highest
function stepMLFQ(queues) {
  for (let q=0; q0) queues[Math.min(q+1, queues.length-1)].push(t);
      return t.id;
    }
  }
  return null;
}

• Periodic tasks: (C_i, T_i, D_i) execution time, period, deadline. Preemptive, single CPU unless stated.
• Rate Monotonic (RM): fixed priorities by rate (1/T). Utilization test Σ C_i/T_i ≤ n(2^{1/n}−1) ≈ 0.693 for large n.
• Earliest Deadline First (EDF): dynamic priority by earliest absolute deadline; optimal on single CPU; feasible if Σ C_i/T_i ≤ 1.
• Linux RT classes: SCHED_FIFO, SCHED_RR, SCHED_DEADLINE (EDF-like) with runtime/period quotas.

1. Simulate CFS with different weights and target latencies; plot vruntime evolution.
2. Build an MLFQ simulator; demonstrate aging to avoid starvation on mixed workloads.
3. Implement a feasibility checker for RM and EDF given periodic task sets; test boundary cases.