kernel/scheduler/
mlfq.rs

1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Multilevel feedback queue scheduler for Tock
6//!
7//! Based on the MLFQ rules described in "Operating Systems: Three Easy Pieces"
8//! by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau.
9//!
10//! This scheduler can be summarized by the following rules:
11//!
12//! - Rule 1: If Priority(A) > Priority(B), and both are ready, A runs (B
13//!   doesn't).
14//! - Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fashion
15//!   using the time slice (quantum length) of the given queue.
16//! - Rule 3: When a job enters the system, it is placed at the highest priority
17//!   (the topmost queue).
18//! - Rule 4: Once a job uses up its time allotment at a given level (regardless
19//!   of how many times it has given up the CPU), its priority is reduced (i.e.,
20//!   it moves down one queue).
21//! - Rule 5: After some time period S, move all the jobs in the system to the
22//!   topmost queue.
23
24use core::cell::Cell;
25use core::num::NonZeroU32;
26
27use crate::collections::list::{List, ListLink, ListNode};
28use crate::hil::time::{self, ConvertTicks, Ticks};
29use crate::platform::chip::Chip;
30use crate::process::ProcessSlot;
31use crate::process::StoppedExecutingReason;
32use crate::scheduler::{Scheduler, SchedulingDecision};
33
34#[derive(Default)]
35struct MfProcState {
36    /// Total CPU time used by this process while in current queue
37    us_used_this_queue: Cell<u32>,
38}
39
40/// Nodes store per-process state
41pub struct MLFQProcessNode<'a> {
42    proc: &'static ProcessSlot,
43    state: MfProcState,
44    next: ListLink<'a, MLFQProcessNode<'a>>,
45}
46
47impl<'a> MLFQProcessNode<'a> {
48    pub fn new(proc: &'static ProcessSlot) -> MLFQProcessNode<'a> {
49        MLFQProcessNode {
50            proc,
51            state: MfProcState::default(),
52            next: ListLink::empty(),
53        }
54    }
55}
56
57impl<'a> ListNode<'a, MLFQProcessNode<'a>> for MLFQProcessNode<'a> {
58    fn next(&'a self) -> &'a ListLink<'a, MLFQProcessNode<'a>> {
59        &self.next
60    }
61}
62
63pub struct MLFQSched<'a, A: 'static + time::Alarm<'static>> {
64    alarm: &'static A,
65    pub processes: [List<'a, MLFQProcessNode<'a>>; 3], // Using Self::NUM_QUEUES causes rustc to crash..
66    next_reset: Cell<A::Ticks>,
67    last_reset_check: Cell<A::Ticks>,
68    last_queue_idx: Cell<usize>,
69}
70
71impl<'a, A: 'static + time::Alarm<'static>> MLFQSched<'a, A> {
72    /// How often to restore all processes to max priority
73    pub const PRIORITY_REFRESH_PERIOD_MS: u32 = 5000;
74    pub const NUM_QUEUES: usize = 3;
75
76    pub fn new(alarm: &'static A) -> Self {
77        Self {
78            alarm,
79            processes: [List::new(), List::new(), List::new()],
80            next_reset: Cell::new(A::Ticks::from(0)),
81            last_reset_check: Cell::new(A::Ticks::from(0)),
82            last_queue_idx: Cell::new(0),
83        }
84    }
85
86    fn get_timeslice_us(&self, queue_idx: usize) -> u32 {
87        match queue_idx {
88            0 => 10000,
89            1 => 20000,
90            2 => 50000,
91            _ => panic!("invalid queue idx"),
92        }
93    }
94
95    fn redeem_all_procs(&self) {
96        for queue in self.processes.iter().skip(1) {
97            if let Some(proc) = queue.pop_head() {
98                self.processes[0].push_tail(proc)
99            }
100        }
101    }
102
103    /// Returns the process at the head of the highest priority queue containing a process
104    /// that is ready to execute (as determined by `has_tasks()`)
105    /// This method moves that node to the head of its queue.
106    fn get_next_ready_process_node(&self) -> (Option<&MLFQProcessNode<'a>>, usize) {
107        for (idx, queue) in self.processes.iter().enumerate() {
108            let next = queue
109                .iter()
110                .find(|node_ref| node_ref.proc.get().is_some_and(|proc| proc.ready()));
111            if let Some(inner) = next {
112                // pop procs to back until we get to match
113                loop {
114                    let cur = queue.pop_head();
115                    if let Some(node) = cur {
116                        if core::ptr::eq(node, inner) {
117                            queue.push_head(node);
118                            // match! Put back on front
119                            return (next, idx);
120                        } else {
121                            queue.push_tail(node);
122                        }
123                    }
124                }
125            }
126        }
127        (None, 0)
128    }
129}
130
131impl<A: 'static + time::Alarm<'static>, C: Chip> Scheduler<C> for MLFQSched<'_, A> {
132    fn next(&self) -> SchedulingDecision {
133        let now = self.alarm.now();
134        let next_reset = self.next_reset.get();
135        let last_reset_check = self.last_reset_check.get();
136
137        // storing last reset check is necessary to avoid missing a reset when the underlying
138        // alarm wraps around
139        if !now.within_range(last_reset_check, next_reset) {
140            // Promote all processes to highest priority queue
141            self.next_reset
142                .set(now.wrapping_add(self.alarm.ticks_from_ms(Self::PRIORITY_REFRESH_PERIOD_MS)));
143            self.redeem_all_procs();
144        }
145        self.last_reset_check.set(now);
146        let (node_ref_opt, queue_idx) = self.get_next_ready_process_node();
147        if node_ref_opt.is_none() {
148            return SchedulingDecision::TrySleep;
149        }
150        let node_ref = node_ref_opt.unwrap();
151        // Schedule for (timeslice - runtime) us
152        let timeslice = self.get_timeslice_us(queue_idx) - node_ref.state.us_used_this_queue.get();
153        let next = node_ref.proc.get().unwrap().processid();
154        self.last_queue_idx.set(queue_idx);
155
156        SchedulingDecision::RunProcess((next, NonZeroU32::new(timeslice)))
157    }
158
159    fn result(&self, result: StoppedExecutingReason, execution_time_us: Option<u32>) {
160        let execution_time_us = execution_time_us.unwrap(); // should never fail as we never run cooperatively
161        let queue_idx = self.last_queue_idx.get();
162        // Last executed node will always be at head of its queue
163        let node_ref = self.processes[queue_idx].head().unwrap();
164
165        let punish = result == StoppedExecutingReason::TimesliceExpired;
166        if punish {
167            node_ref.state.us_used_this_queue.set(0); // Reset runtime to 0 since we are moving queues
168            let next_queue = if queue_idx == Self::NUM_QUEUES - 1 {
169                queue_idx
170            } else {
171                queue_idx + 1
172            };
173            self.processes[next_queue].push_tail(self.processes[queue_idx].pop_head().unwrap());
174        } else {
175            // Increment runtime in the current queue with execution_time_us
176            node_ref
177                .state
178                .us_used_this_queue
179                .update(|runtime| runtime + execution_time_us);
180            self.processes[queue_idx].push_tail(self.processes[queue_idx].pop_head().unwrap());
181        }
182    }
183}
kernel/scheduler/mlfq.rs

kernel/scheduler/
mlfq.rs
