kernel/scheduler/
round_robin.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//! Round Robin Scheduler for Tock
6//!
7//! This scheduler is specifically a Round Robin Scheduler with Interrupts.
8//!
9//! See: <https://www.eecs.umich.edu/courses/eecs461/lecture/SWArchitecture.pdf>
10//! for details.
11//!
12//! When hardware interrupts occur while a userspace process is executing, this
13//! scheduler executes the top half of the interrupt, and then stops executing
14//! the userspace process immediately and handles the bottom half of the
15//! interrupt. This design decision was made to mimic the behavior of the
16//! original Tock scheduler. In order to ensure fair use of timeslices, when
17//! userspace processes are interrupted the scheduler timer is paused, and the
18//! same process is resumed with the same scheduler timer value from when it was
19//! interrupted.
20
21use core::cell::Cell;
22use core::num::NonZeroU32;
23
24use crate::collections::list::{List, ListLink, ListNode};
25use crate::platform::chip::Chip;
26use crate::process::Process;
27use crate::process::StoppedExecutingReason;
28use crate::scheduler::{Scheduler, SchedulingDecision};
29
30/// A node in the linked list the scheduler uses to track processes
31/// Each node holds a pointer to a slot in the processes array
32pub struct RoundRobinProcessNode<'a> {
33    proc: &'static Option<&'static dyn Process>,
34    next: ListLink<'a, RoundRobinProcessNode<'a>>,
35}
36
37impl<'a> RoundRobinProcessNode<'a> {
38    pub fn new(proc: &'static Option<&'static dyn Process>) -> RoundRobinProcessNode<'a> {
39        RoundRobinProcessNode {
40            proc,
41            next: ListLink::empty(),
42        }
43    }
44}
45
46impl<'a> ListNode<'a, RoundRobinProcessNode<'a>> for RoundRobinProcessNode<'a> {
47    fn next(&'a self) -> &'a ListLink<'a, RoundRobinProcessNode<'a>> {
48        &self.next
49    }
50}
51
52/// Round Robin Scheduler
53pub struct RoundRobinSched<'a> {
54    time_remaining: Cell<u32>,
55    timeslice_length: u32,
56    pub processes: List<'a, RoundRobinProcessNode<'a>>,
57    last_rescheduled: Cell<bool>,
58}
59
60impl<'a> RoundRobinSched<'a> {
61    /// How long a process can run before being pre-empted
62    const DEFAULT_TIMESLICE_US: u32 = 10000;
63    pub const fn new() -> RoundRobinSched<'a> {
64        Self::new_with_time(Self::DEFAULT_TIMESLICE_US)
65    }
66
67    pub const fn new_with_time(time_us: u32) -> RoundRobinSched<'a> {
68        RoundRobinSched {
69            time_remaining: Cell::new(time_us),
70            timeslice_length: time_us,
71            processes: List::new(),
72            last_rescheduled: Cell::new(false),
73        }
74    }
75}
76
77impl<C: Chip> Scheduler<C> for RoundRobinSched<'_> {
78    fn next(&self) -> SchedulingDecision {
79        let mut first_head = None;
80        let mut next = None;
81
82        // Find the first ready process in the queue. Place any *empty* process slots,
83        // or not-ready processes, at the back of the queue.
84        while let Some(node) = self.processes.head() {
85            // Ensure we do not loop forever if all processes are not ready
86            match first_head {
87                None => first_head = Some(node),
88                Some(first_head) => {
89                    // We made a full iteration and nothing was ready. Try to sleep instead
90                    if core::ptr::eq(first_head, node) {
91                        return SchedulingDecision::TrySleep;
92                    }
93                }
94            }
95            match node.proc {
96                Some(proc) => {
97                    if proc.ready() {
98                        next = Some(proc.processid());
99                        break;
100                    }
101                    self.processes.push_tail(self.processes.pop_head().unwrap());
102                }
103                None => {
104                    self.processes.push_tail(self.processes.pop_head().unwrap());
105                }
106            }
107        }
108
109        let next = match next {
110            Some(p) => p,
111            None => {
112                // No processes on the system
113                return SchedulingDecision::TrySleep;
114            }
115        };
116
117        let timeslice = if self.last_rescheduled.get() {
118            self.time_remaining.get()
119        } else {
120            // grant a fresh timeslice
121            self.time_remaining.set(self.timeslice_length);
122            self.timeslice_length
123        };
124        // Why should this panic?
125        let non_zero_timeslice = NonZeroU32::new(timeslice).unwrap();
126
127        SchedulingDecision::RunProcess((next, Some(non_zero_timeslice)))
128    }
129
130    fn result(&self, result: StoppedExecutingReason, execution_time_us: Option<u32>) {
131        let execution_time_us = execution_time_us.unwrap(); // should never fail
132        let reschedule = match result {
133            StoppedExecutingReason::KernelPreemption => {
134                if self.time_remaining.get() > execution_time_us {
135                    self.time_remaining
136                        .set(self.time_remaining.get() - execution_time_us);
137                    true
138                } else {
139                    false
140                }
141            }
142            _ => false,
143        };
144        self.last_rescheduled.set(reschedule);
145        if !reschedule {
146            self.processes.push_tail(self.processes.pop_head().unwrap());
147        }
148    }
149}
kernel/scheduler/round_robin.rs

kernel/scheduler/
round_robin.rs
