kernel/scheduler/
cooperative.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//! Cooperative Scheduler for Tock
6//!
7//! This scheduler runs all processes in a round-robin fashion, but does not use
8//! a scheduler timer to enforce process timeslices. That is, all processes are
9//! run cooperatively. Processes are run until they yield or stop executing
10//! (i.e. they crash or exit).
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. However it then continues executing the same userspace process
16//! that was executing.
17
18use crate::collections::list::{List, ListLink, ListNode};
19use crate::platform::chip::Chip;
20use crate::process::Process;
21use crate::process::StoppedExecutingReason;
22use crate::scheduler::{Scheduler, SchedulingDecision};
23
24/// A node in the linked list the scheduler uses to track processes
25pub struct CoopProcessNode<'a> {
26    proc: &'static Option<&'static dyn Process>,
27    next: ListLink<'a, CoopProcessNode<'a>>,
28}
29
30impl<'a> CoopProcessNode<'a> {
31    pub fn new(proc: &'static Option<&'static dyn Process>) -> CoopProcessNode<'a> {
32        CoopProcessNode {
33            proc,
34            next: ListLink::empty(),
35        }
36    }
37}
38
39impl<'a> ListNode<'a, CoopProcessNode<'a>> for CoopProcessNode<'a> {
40    fn next(&'a self) -> &'a ListLink<'a, CoopProcessNode<'a>> {
41        &self.next
42    }
43}
44
45/// Cooperative Scheduler
46pub struct CooperativeSched<'a> {
47    pub processes: List<'a, CoopProcessNode<'a>>,
48}
49
50impl<'a> CooperativeSched<'a> {
51    pub const fn new() -> CooperativeSched<'a> {
52        CooperativeSched {
53            processes: List::new(),
54        }
55    }
56}
57
58impl<C: Chip> Scheduler<C> for CooperativeSched<'_> {
59    fn next(&self) -> SchedulingDecision {
60        let mut first_head = None;
61
62        // Find the first ready process in the queue. Place any *empty* process slots,
63        // or not-ready processes, at the back of the queue.
64        while let Some(node) = self.processes.head() {
65            // Ensure we do not loop forever if all processes are not not ready
66            match first_head {
67                None => first_head = Some(node),
68                Some(first_head) => {
69                    // We make a full iteration and nothing was ready. Try to sleep instead
70                    if core::ptr::eq(first_head, node) {
71                        return SchedulingDecision::TrySleep;
72                    }
73                }
74            }
75            match node.proc {
76                Some(proc) => {
77                    if proc.ready() {
78                        let next = proc.processid();
79                        return SchedulingDecision::RunProcess((next, None));
80                    }
81                    self.processes.push_tail(self.processes.pop_head().unwrap());
82                }
83                None => {
84                    self.processes.push_tail(self.processes.pop_head().unwrap());
85                }
86            }
87        }
88
89        // If the length of `self.processes` is 0, the while loop never executes. In this case,
90        // return `SchedulingDecision::TrySleep` as there is no process that can be scheduled.
91        SchedulingDecision::TrySleep
92    }
93
94    fn result(&self, result: StoppedExecutingReason, _: Option<u32>) {
95        let reschedule = match result {
96            StoppedExecutingReason::KernelPreemption => true,
97            _ => false,
98        };
99        if !reschedule {
100            self.processes.push_tail(self.processes.pop_head().unwrap());
101        }
102    }
103}
kernel/scheduler/cooperative.rs

kernel/scheduler/
cooperative.rs
