1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//! Round Robin Scheduler for Tock
//!
//! This scheduler is specifically a Round Robin Scheduler with Interrupts.
//!
//! See: <https://www.eecs.umich.edu/courses/eecs461/lecture/SWArchitecture.pdf>
//! for details.
//!
//! When hardware interrupts occur while a userspace process is executing, this
//! scheduler executes the top half of the interrupt, and then stops executing
//! the userspace process immediately and handles the bottom half of the
//! interrupt. This design decision was made to mimic the behavior of the
//! original Tock scheduler. In order to ensure fair use of timeslices, when
//! userspace processes are interrupted the scheduler timer is paused, and the
//! same process is resumed with the same scheduler timer value from when it was
//! interrupted.

use core::cell::Cell;

use crate::collections::list::{List, ListLink, ListNode};
use crate::kernel::StoppedExecutingReason;
use crate::platform::chip::Chip;
use crate::process::Process;
use crate::scheduler::{Scheduler, SchedulingDecision};

/// A node in the linked list the scheduler uses to track processes
/// Each node holds a pointer to a slot in the processes array
pub struct RoundRobinProcessNode<'a> {
    proc: &'static Option<&'static dyn Process>,
    next: ListLink<'a, RoundRobinProcessNode<'a>>,
}

impl<'a> RoundRobinProcessNode<'a> {
    pub fn new(proc: &'static Option<&'static dyn Process>) -> RoundRobinProcessNode<'a> {
        RoundRobinProcessNode {
            proc,
            next: ListLink::empty(),
        }
    }
}

impl<'a> ListNode<'a, RoundRobinProcessNode<'a>> for RoundRobinProcessNode<'a> {
    fn next(&'a self) -> &'a ListLink<'a, RoundRobinProcessNode> {
        &self.next
    }
}

/// Round Robin Scheduler
pub struct RoundRobinSched<'a> {
    time_remaining: Cell<u32>,
    pub processes: List<'a, RoundRobinProcessNode<'a>>,
    last_rescheduled: Cell<bool>,
}

impl<'a> RoundRobinSched<'a> {
    /// How long a process can run before being pre-empted
    const DEFAULT_TIMESLICE_US: u32 = 10000;
    pub const fn new() -> RoundRobinSched<'a> {
        RoundRobinSched {
            time_remaining: Cell::new(Self::DEFAULT_TIMESLICE_US),
            processes: List::new(),
            last_rescheduled: Cell::new(false),
        }
    }
}

impl<'a, C: Chip> Scheduler<C> for RoundRobinSched<'a> {
    fn next(&self) -> SchedulingDecision {
        let mut first_head = None;
        let mut next = None;

        // Find next ready process. Place any *empty* process slots, or not-ready
        // processes, at the back of the queue.
        for node in self.processes.iter() {
            // Ensure we do not loop forever if all processes are not ready
            match first_head {
                None => first_head = Some(node),
                Some(first_head) => {
                    // We made a full iteration and nothing was ready. Try to sleep instead
                    if core::ptr::eq(first_head, node) {
                        return SchedulingDecision::TrySleep;
                    }
                }
            }
            match node.proc {
                Some(proc) => {
                    if proc.ready() {
                        next = Some(proc.processid());
                        break;
                    }
                    self.processes.push_tail(self.processes.pop_head().unwrap());
                }
                None => {
                    self.processes.push_tail(self.processes.pop_head().unwrap());
                }
            }
        }
        let timeslice = if self.last_rescheduled.get() {
            self.time_remaining.get()
        } else {
            // grant a fresh timeslice
            self.time_remaining.set(Self::DEFAULT_TIMESLICE_US);
            Self::DEFAULT_TIMESLICE_US
        };
        assert!(timeslice != 0);

        // next will not be None, because if we make a full iteration and nothing
        // is ready we return early
        SchedulingDecision::RunProcess((next.unwrap(), Some(timeslice)))
    }

    fn result(&self, result: StoppedExecutingReason, execution_time_us: Option<u32>) {
        let execution_time_us = execution_time_us.unwrap(); // should never fail
        let reschedule = match result {
            StoppedExecutingReason::KernelPreemption => {
                if self.time_remaining.get() > execution_time_us {
                    self.time_remaining
                        .set(self.time_remaining.get() - execution_time_us);
                    true
                } else {
                    false
                }
            }
            _ => false,
        };
        self.last_rescheduled.set(reschedule);
        if !reschedule {
            self.processes.push_tail(self.processes.pop_head().unwrap());
        }
    }
}