Multiprocessor Scheduling

When multiple CPUs are available, the scheduling problem becomes more complex. We must decide not only when a process runs, but also where it runs.

1. Symmetric Multiprocessing (SMP)

In SMP, each processor is self-scheduling. All processes are either in a common ready queue or each processor has its own private queue of ready processes. This is the standard in modern systems like Linux, Windows, and macOS.

2. Processor Affinity

Due to the cost of invalidating and repopulating caches, most OSs try to keep a process running on the same processor.

• Soft Affinity: The OS has a policy of attempting to keep a process on the same processor, but it does not guarantee it.
• Hard Affinity: The OS allows a process to specify a subset of processors on which it may run (e.g., via the sched_setaffinity() system call).

3. Load Balancing

To prevent one processor from sitting idle while others are overloaded, the OS uses two techniques:

• Push Migration: A specific task periodically checks the load on each processor and "pushes" processes from overloaded to idle CPUs.
• Pull Migration: An idle processor "pulls" a waiting task from a busy processor's queue.

Multicore Processors and Hardware Threads

Modern hardware places multiple computing cores on a single physical chip. This introduces a new challenge: the Memory Stall.

When a processor accesses memory, it may spend a significant amount of time (hundreds of clock cycles) waiting for the data to become available. During this time, the core is doing no useful work.

Hardware Multithreading (Hyper-threading)

To solve memory stalls, many cores support multiple hardware threads.

• If one hardware thread stalls (waiting for memory), the core can immediately switch to another hardware thread.
• From the OS perspective, each hardware thread looks like a logical CPU.

Real-Time CPU Scheduling

A Real-Time Operating System (RTOS) must guarantee that critical tasks be completed within a specific time frame.

Types of Real-Time Systems:

• Soft Real-Time: Critical tasks have priority, but there is no absolute guarantee they will meet their deadlines.
• Hard Real-Time: A task must be serviced by its deadline; failure to do so is considered a total system failure.

Critical Latencies:

In an RTOS, the goal is to minimize two types of latency:

1. Interrupt Latency: The period from the arrival of an interrupt at the CPU to the start of the routine that services the interrupt.
2. Dispatch Latency: The time required for the scheduling dispatcher to stop one process and start another. For an RTOS to be effective, it must support Preemptive Kernels.

RTOS Scheduling Algorithms

Most RTOSs use a priority-based algorithm with preemption. Two of the most common are:

1. Rate-Monotonic (RM) Scheduling

A static priority scheduling algorithm using preemption.

• The Rule: Priority is assigned based on the inverse of the task's period.
• Logic: Shorter period = Higher frequency = Higher priority.
• Limit: If the total CPU utilization of all tasks exceeds $N(2^{1/N} - 1)$, RM might fail to meet deadlines (for a large $N$, this is roughly 69%).

2. Earliest-Deadline-First (EDF) Scheduling

A dynamic priority scheduling algorithm.

• The Rule: Priorities are assigned according to deadlines. The earlier the deadline, the higher the priority.
• Logic: When a process becomes ready, it announces its deadline to the OS.
• Efficiency: In theory, EDF can reach 100% CPU utilization while still guaranteeing all deadlines are met (unlike RM).