keos_project4/

round_robin.rs

//! # 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.
//!
//! ```rust
//! 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.
//!
//! [`Scheduler::reschedule`]:../../keos/thread/scheduler/trait.Scheduler.html#method.reschedule
//! [`RoundRobin`]: RoundRobin
//! [`Thread::run`]: keos::thread::Thread::run
//! [`Box`]: https://doc.rust-lang.org/alloc/boxed/struct.Box.html
//! [`VecDeque`]: https://doc.rust-lang.org/alloc/collections/vec_deque/struct.VecDeque.html
//! [`STACK_SIZE`]: keos::thread::STACK_SIZE
//! [`ThreadBuilder`]: keos::thread::ThreadBuilder
//! [`ThreadBuilder::spawn`]: keos::thread::ThreadBuilder::spawn
//! [`Scheduler`]: keos::thread::scheduler::Scheduler
//! [`Scheduler::next_to_run`]: keos::thread::scheduler::Scheduler::next_to_run

use alloc::{boxed::Box, collections::VecDeque};
use keos::{
    MAX_CPU,
    intrinsics::cpuid,
    sync::SpinLock,
    sync::atomic::AtomicIsize,
    thread::{Thread, scheduler::Scheduler},
};

/// Per-core scheduler state.
///
/// The [`PerCore`] struct represents the per-core scheduling state in a
/// multi-core system. Each CPU core maintains its own scheduling queue to
/// manage runnable threads independently. This structure is used within the
/// [`RoundRobin`] scheduler to ensure that each core schedules and executes
/// threads in a fair and efficient manner.
pub struct PerCore {
    /// Queue of threads ready to run on this CPU core.
    /// - Protected by a [`SpinLock`] to prevent concurrent access issues.
    /// - Threads are stored in a [`VecDeque`] to allow efficient push/pop
    ///   operations.
    pub run_queue: SpinLock<VecDeque<Box<Thread>>>,

    /// Remaining time slice for the currently running thread.
    /// - Uses [`AtomicIsize`] for safe atomic updates across multiple CPU
    ///   cores.
    /// - Typically decremented on each timer interrupt, triggering a context
    ///   switch when it reaches zero.
    /// - You can use [``] for load, store to this variable.
    pub remain: AtomicIsize,
}

/// A round robin scheduler.
///
/// The [RoundRobin] struct represents a round-robin scheduler, which is a type
/// of preemptive scheduling used in operating systems to manage the execution
/// of processes. In a round-robin scheduler, each process is assigned a fixed
/// time slice (quantum) in which it can run. Once the time slice expires,
/// the process is suspended, and the next process in the queue is scheduled to
/// run. This continues in a circular manner, ensuring fair distribution of CPU
/// time among processes.
pub struct RoundRobin {
    percores: [PerCore; MAX_CPU],
}
unsafe impl Send for RoundRobin {}
unsafe impl Sync for RoundRobin {}

impl Default for RoundRobin {
    fn default() -> Self {
        Self::new()
    }
}

impl RoundRobin {
    /// Create a new [`RoundRobin`] scheduler.
    pub fn new() -> Self {
        Self {
            percores: [0; MAX_CPU].map(|_| PerCore {
                run_queue: SpinLock::new(VecDeque::new()),
                remain: AtomicIsize::new(0),
            }),
        }
    }
}

impl Scheduler for RoundRobin {
    fn next_to_run(&self) -> Option<Box<Thread>> {
        todo!()
    }
    fn push_to_queue(&self, thread: Box<Thread>) {
        let coreid = cpuid();
        todo!()
    }
    fn timer_tick(&self) {
        // Hint: you can yield the current thread by calling
        // [`keos::thread::scheduler::Scheduler::reschedule`]
        let coreid = cpuid();
        todo!()
    }
}