keos/thread/
scheduler.rs

1//! Thread scheduler
2
3use super::{ParkHandle, STACK_SIZE, THREAD_MAGIC, Thread, ThreadStack, ThreadState};
4use abyss::spinlock::SpinLock;
5use alloc::boxed::Box;
6use core::{arch::asm, sync::atomic::AtomicBool};
7
8/// A trait for a thread scheduler.
9///
10/// The [`Scheduler`] trait defines the common functionality expected from a
11/// thread scheduler. It provides an interface for managing threads, determining
12/// which thread to run next, and handling periodic timer interrupts. A thread
13/// scheduler is responsible for controlling the execution of threads in a
14/// system. The scheduler determines when each thread is allowed to run, how to
15/// handle context switching, and ensures fair allocation of CPU time among all
16/// threads.
17///
18/// This trait can be implemented by different types of schedulers, such as
19/// Round Robin, Priority-based, or Multi-level Queue schedulers. Each
20/// implementation may have a unique strategy for selecting the next
21/// thread to run and handling thread management.
22pub trait Scheduler {
23    /// Peek a next thread to run.
24    ///
25    /// This method checks the queue and returns the next thread to run. If no
26    /// threads are available, it returns `None`.
27    ///
28    /// # Returns
29    ///
30    /// Returns an `Option<Box<Thread>>` containing the next thread to run or
31    /// `None` if no threads are available to execute.
32    fn next_to_run(&self) -> Option<Box<Thread>>;
33
34    /// Push a thread `th` into scheduling queue.
35    ///
36    /// This method adds the specified thread to the queue of threads waiting to
37    /// be scheduled.
38    ///
39    /// # Arguments
40    ///
41    /// * `th` - A boxed [`Thread`] object that represents the thread to be
42    ///   added to the scheduler's queue.
43    fn push_to_queue(&self, th: Box<Thread>);
44
45    /// Called on every timer interrupt (1ms).
46    ///
47    /// This method is triggered by the timer interrupt (e.g., every 1ms) and
48    /// allows the scheduler to manage time slices, perform context
49    /// switching, or adjust thread priorities as needed.
50    fn timer_tick(&self);
51}
52
53pub(crate) static mut SCHEDULER: Option<&'static dyn Scheduler> = None;
54
55/// A First-in-first-out scheduler.
56struct Fifo {
57    runqueue: SpinLock<alloc::collections::VecDeque<Box<Thread>>>,
58}
59
60unsafe impl core::marker::Sync for Fifo {}
61
62impl Scheduler for Fifo {
63    fn next_to_run(&self) -> Option<Box<Thread>> {
64        let mut guard = self.runqueue.lock();
65        let val = guard.pop_back();
66        guard.unlock();
67        val
68    }
69    fn push_to_queue(&self, th: Box<Thread>) {
70        let mut guard = self.runqueue.lock();
71        guard.push_back(th);
72        guard.unlock();
73    }
74    fn timer_tick(&self) {}
75}
76
77static FIFO: Fifo = Fifo {
78    runqueue: SpinLock::new(alloc::collections::VecDeque::new()),
79};
80
81/// Set the scheduler of the kernel.
82pub(crate) unsafe fn set_scheduler(t: impl Scheduler + 'static) {
83    unsafe {
84        SCHEDULER = (Box::into_raw(Box::new(t)) as *const dyn Scheduler).as_ref();
85    }
86}
87
88/// Get the reference of the kernel scheduler.
89pub fn scheduler() -> &'static (dyn Scheduler + 'static) {
90    if let Some(sched) = unsafe { SCHEDULER.as_mut() } {
91        *sched
92    } else {
93        &FIFO
94    }
95}
96
97impl dyn Scheduler {
98    /// Reschedule the current thread.
99    pub fn reschedule(&self) {
100        let _p = Thread::pin();
101        match self.next_to_run() {
102            Some(th) => {
103                th.run();
104            }
105            _ => unsafe {
106                IDLE[abyss::x86_64::intrinsics::cpuid()]
107                    .as_mut()
108                    .unwrap()
109                    .do_run();
110            },
111        }
112    }
113
114    /// Park a thread 'th' and return ParkHandle.
115    pub(crate) unsafe fn park_thread(&self, th: &mut Thread) -> Result<ParkHandle, ()> {
116        let mut state = th.state.lock();
117        if matches!(*state, ThreadState::Parked) {
118            return Err(());
119        }
120        *state = ThreadState::Parked;
121        state.unlock();
122        unsafe {
123            Ok(ParkHandle {
124                th: Box::from_raw(th),
125            })
126        }
127    }
128}
129
130pub(crate) static BOOT_DONE: AtomicBool = AtomicBool::new(false);
131const INIT: Option<Box<Thread>> = None;
132static mut IDLE: [Option<Box<Thread>>; abyss::MAX_CPU] = [INIT; abyss::MAX_CPU];
133
134/// Transmute this thread into the idle.
135pub(crate) fn idle(core_id: usize) -> ! {
136    let mut sp: usize;
137    unsafe {
138        asm!("mov {}, rsp", out(reg) sp);
139    }
140
141    let mut tcb = Thread::new("idle");
142    let mut state = tcb.state.lock();
143    *state = ThreadState::Idle;
144    state.unlock();
145
146    tcb.stack = unsafe { Box::from_raw((sp & !(STACK_SIZE - 1)) as *mut ThreadStack) };
147    tcb.stack.magic = THREAD_MAGIC;
148    tcb.stack.thread = tcb.as_mut() as *mut _;
149    unsafe {
150        IDLE[core_id] = Some(tcb);
151    }
152
153    while !BOOT_DONE.load(core::sync::atomic::Ordering::SeqCst) {
154        core::hint::spin_loop();
155    }
156    let scheduler = crate::thread::scheduler::scheduler();
157    loop {
158        if let Some(th) = scheduler.next_to_run() {
159            th.run();
160        }
161        unsafe { asm!("sti", "hlt", "cli") }
162    }
163}
keos/thread/scheduler.rs

keos/thread/
scheduler.rs
