Module round_robin 

Multicore Round-Robin Scheduling.

The scheduler is an essential component of process management in any operating system. It ensures that multiple threads share CPU time in a fair and orderly manner.

In an operating system, a thread is an abstraction of a CPU core. The thread abstraction enables the operating system to run multiple tasks concurrently, even on a single CPU core. At any given time, exactly one thread runs on the CPU, while other threads that are not active remain in an inactive state.If there are no threads ready to run, a special idle thread is executed to prevent the CPU from being idle.

Round-Robin scheduling is a preemptive scheduling algorithm that assigns each thread a fixed time slice (or quantum) in a circular order. Once a thread’s time slice expires, it is preempted and pushed back to the end of the ready queue, while the next thread in the queue gets to run. This guarantees that all threads receive a fair share of CPU time.

Scheduling in KeOS

KeOS already provides basic thread functionalities such as thread creation and thread switching. You can create a new thread using the ThreadBuilder. By calling ThreadBuilder::spawn, you pass a function that will be executed when the thread is first run. The thread will terminate once the function completes its execution. Each thread effectively acts as a mini-program running within the kernel, isolated from the others.

The scheduler manages the CPU resources between the threads, by determines which thread runs next or whether yielding the running thread. After determining the next thread, the kernel conducts a context switch to run the thread. The magic of a context switch happens through the Thread::run function, which saves the state of the currently running thread and restores the state of the next thread to be executed.

The core of schedulers in KeOS lies in Scheduler traits. This trait defines the scheduling policy. The kernel consults with the scheduler implementation to determine next thread with Scheduler::next_to_run, and determine to yield the current thread within Scheduler::timer_tick.

Per-Core Scheduler State

In a multi-core system, each CPU core must manage its own scheduling queue and state independently. This is crucial for implementing an efficient multi-core scheduler, which is why the PerCore structure is used.

The PerCore struct represents the per-core scheduling state. Each core has its own scheduling queue (run_queue) and time slice (remain). These allow each CPU core to manage threads independently, ensuring no thread monopolizes CPU time on any core.

struct PerCore {
    /// Queue of threads ready to run on this CPU core.
    run_queue: SpinLock<VecDeque<Box<Thread>>>,

    /// Remaining time slice for the currently running thread.
    remain: AtomicIsize,
}

The PerCore struct is essential in ensuring each CPU core can independently manage its threads. Key components include:

• run_queue: This is a queue of threads ready to run on the respective CPU core. It is protected by a SpinLock to ensure that only one core can modify the queue at a time, preventing race conditions. The VecDeque allows for efficient push and pop operations, making it an ideal choice for managing threads in the ready state.

• remain: This field holds the remaining time slice for the currently running thread on the CPU core. The remaining time slice is typically decremented on each timer interrupt, and when it reaches zero, a context switch occurs, and the current thread is preempted to allow the next thread to execute.

Round-Robin Scheduler

The RoundRobin scheduler in KeOS implements a time-sharing policy across multiple CPU cores using a round-robin approach. Each CPU core is associated with a dedicated PerCore structure, which maintains its own ready queue and scheduling state. This per-core design enables efficient parallel scheduling, minimizes contention, and ensures that all cores participate in thread execution without interference.

In a round-robin policy, each runnable thread is assigned a fixed time slice (quantum) during which it can execute before being preempted. You will use the default quantum as 5 milliseconds. When a thread exhausts its time slice, it is reschdules with Scheduler::reschedule. This ensures fair CPU allocation among all threads and prevents starvation.

KeOS employs a periodic timer interrupt that fires every 1 millisecond on each core. These timer interrupts invoke Scheduler::timer_tick, which updates the scheduling state, decrements the current thread’s time slice, and triggers a context switch if the quantum has expired.

A challenge in per-core scheduling arises when a core’s local run queue is empty: the CPU becomes idle, even though other cores may have work queued. To address this, the scheduler implements work stealing, a mechanism that allows idle cores to “steal” runnable threads from the queues of other cores. This dynamic load-balancing strategy ensures that CPU resources are used efficiently and that no core remains idle while runnable threads exist elsewhere in the system.

Overall, the round-robin scheduler in KeOS offers a simple yet effective baseline for multicore scheduling, balancing responsiveness, fairness, and throughput across all available cores.

Implementation Requirements

You need to implement the followings:

• RoundRobin::next_to_run
• RoundRobin::push_to_queue
• RoundRobin::timer_tick

This ends project 4.

Structs

PerCore

Per-core scheduler state.

RoundRobin

A round robin scheduler.