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
/* Copyright (c) [2023] [Syswonder Community]
* [Rukos] is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
* http://license.coscl.org.cn/MulanPSL2
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
* See the Mulan PSL v2 for more details.
*/
use alloc::{collections::VecDeque, sync::Arc};
use core::ops::Deref;
use core::sync::atomic::{AtomicIsize, Ordering};
use crate::BaseScheduler;
/// A task wrapper for the [`RRScheduler`].
///
/// It add a time slice counter to use in round-robin scheduling.
pub struct RRTask<T, const MAX_TIME_SLICE: usize> {
inner: T,
time_slice: AtomicIsize,
}
impl<T, const S: usize> RRTask<T, S> {
/// Creates a new [`RRTask`] from the inner task struct.
pub const fn new(inner: T) -> Self {
Self {
inner,
time_slice: AtomicIsize::new(S as isize),
}
}
fn time_slice(&self) -> isize {
self.time_slice.load(Ordering::Acquire)
}
fn reset_time_slice(&self) {
self.time_slice.store(S as isize, Ordering::Release);
}
/// Returns a reference to the inner task struct.
pub const fn inner(&self) -> &T {
&self.inner
}
}
impl<T, const S: usize> Deref for RRTask<T, S> {
type Target = T;
#[inline]
fn deref(&self) -> &Self::Target {
&self.inner
}
}
/// A simple [Round-Robin] (RR) preemptive scheduler.
///
/// It's very similar to the [`FifoScheduler`], but every task has a time slice
/// counter that is decremented each time a timer tick occurs. When the current
/// task's time slice counter reaches zero, the task is preempted and needs to
/// be rescheduled.
///
/// Unlike [`FifoScheduler`], it uses [`VecDeque`] as the ready queue. So it may
/// take O(n) time to remove a task from the ready queue.
///
/// [Round-Robin]: https://en.wikipedia.org/wiki/Round-robin_scheduling
/// [`FifoScheduler`]: crate::FifoScheduler
pub struct RRScheduler<T, const MAX_TIME_SLICE: usize> {
ready_queue: VecDeque<Arc<RRTask<T, MAX_TIME_SLICE>>>,
}
impl<T, const S: usize> RRScheduler<T, S> {
/// Creates a new empty [`RRScheduler`].
pub const fn new() -> Self {
Self {
ready_queue: VecDeque::new(),
}
}
/// get the name of scheduler
pub fn scheduler_name() -> &'static str {
"Round-robin"
}
}
impl<T, const S: usize> BaseScheduler for RRScheduler<T, S> {
type SchedItem = Arc<RRTask<T, S>>;
fn init(&mut self) {}
fn add_task(&mut self, task: Self::SchedItem) {
self.ready_queue.push_back(task);
}
fn remove_task(&mut self, task: &Self::SchedItem) -> Option<Self::SchedItem> {
// TODO: more efficient
self.ready_queue
.iter()
.position(|t| Arc::ptr_eq(t, task))
.and_then(|idx| self.ready_queue.remove(idx))
}
fn pick_next_task(&mut self) -> Option<Self::SchedItem> {
self.ready_queue.pop_front()
}
fn put_prev_task(&mut self, prev: Self::SchedItem, preempt: bool) {
if prev.time_slice() > 0 && preempt {
self.ready_queue.push_front(prev)
} else {
prev.reset_time_slice();
self.ready_queue.push_back(prev)
}
}
fn task_tick(&mut self, current: &Self::SchedItem) -> bool {
let old_slice = current.time_slice.fetch_sub(1, Ordering::Release);
old_slice <= 1
}
fn set_priority(&mut self, _task: &Self::SchedItem, _prio: isize) -> bool {
false
}
}