CPU Scheduling Algorithms and Message Passing Mechanisms

Guaranteed Scheduling

Guaranteed scheduling algorithms aim to ensure that each process receives its fair share of CPU time. These systems penalize processes that have consumed a large amount of CPU time, though this penalty fades over time. This approach is utilized in most versions of UNIX, Windows NT, and subsequent Linux distributions.

BSD Scheduler

Unlike legacy UNIX schedulers, the BSD scheduler accounts for system load by monitoring the length of the ready queue, known as the "Load average." Additionally, it forgives old CPU usage more slowly when the system load is high.

Linux 2.4 Scheduler

Epoch-Based Allocation

The Linux 2.4 scheduler partitions CPU time into epochs. At the start of each epoch, every process is assigned a time quantum, which specifies the maximum CPU time the process can utilize during that period. Processes that exhaust their time quantum cannot receive further CPU time until the next epoch begins.

Dynamic Priority and Execution

Processes that release the CPU before their time quantum is exhausted may receive additional CPU time within the same epoch. An epoch concludes when all ready processes have exhausted their time quanta. The priority of a process is calculated as the sum of its base priority plus the amount of CPU time remaining before its quantum expires.

FreeBSD 5.0 ULE Scheduler

Designed specifically for threads running on multicore architectures, the ULE scheduler consists of two primary components:

• Low-level scheduler: Executes every time a core is released.
• High-level scheduler: Executes every second.

Low-Level Scheduler Mechanics

The kernel maintains a set of run queues for each CPU, categorized by different priorities. The low-level scheduler selects the first thread on the highest-level nonempty run queue.

High-Level Scheduler Functions

The high-level scheduler reevaluates thread priorities:

• Real-time threads are assigned fixed priorities.
• The scheduler detects interactive threads based on an interactivity score, calculated as: Scaling factor × (Sleep time / Run time).
• It also manages the complex process of assigning threads to specific CPUs.

Message Passing

Message passing allows processes to exchange data by sending and receiving messages. Any exchange requires a send(addr, msg, length) and a receive(addr, msg, length) operation.

Advantages

• Generality: Highly versatile communication method.
• Distributed capability: Senders and receivers can reside on different machines.
• Security: Relatively secure, as the receiver can inspect messages before processing them.

Disadvantages

• Complexity: Difficult to implement.
• Overhead: Every data transfer requires both a send() and a receive().
• Synchronization: The receiving process must expect the send(), which might require forking a special thread.