strat9_kernel/process/sched_classes/
real_time.rs

1// SPDX-License-Identifier: MPL-2.0
2
3use super::{CurrentRuntime, SchedClassRq};
4use crate::{arch::x86_64::timer::TIMER_HZ, process::task::Task};
5use alloc::sync::Arc;
6use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListLink};
7
8/// RT Round-Robin quantum in ticks.
9///
10/// POSIX specifies a minimum of 100ms for SCHED_RR (Linux default: 100ms).
11/// At TIMER_HZ=100: 10 ticks x 10 ms/tick = 100 ms.
12const RT_RR_QUANTUM_TICKS: u64 = TIMER_HZ / 10;
13
14/// Real-time priority (0-99). Higher value means higher priority.
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
16pub struct RealTimePriority(u8);
17
18impl RealTimePriority {
19    pub const MIN: Self = Self(0);
20    pub const MAX: Self = Self(99);
21
22    /// Creates a new instance.
23    pub fn new(prio: u8) -> Self {
24        Self(prio.clamp(Self::MIN.0, Self::MAX.0))
25    }
26
27    /// Performs the get operation.
28    pub fn get(self) -> u8 {
29        self.0
30    }
31}
32
33// Intrusive adapter: the list owns Arc<Task> references and navigates via
34// the `rt_link` field embedded directly in the Task control block.
35// Zero heap allocation on enqueue or dequeue; no fixed capacity limit.
36intrusive_adapter!(pub RtTaskAdapter = Arc<Task>: Task { rt_link: LinkedListLink });
37
38/// Single-priority FIFO backed by an intrusive doubly-linked list.
39struct RtPrioQueue {
40    list: LinkedList<RtTaskAdapter>,
41    len: usize,
42}
43
44impl RtPrioQueue {
45    fn new() -> Self {
46        Self {
47            list: LinkedList::new(RtTaskAdapter::new()),
48            len: 0,
49        }
50    }
51
52    fn push_back(&mut self, task: Arc<Task>) {
53        self.list.push_back(task);
54        self.len += 1;
55    }
56
57    fn pop_front(&mut self) -> Option<Arc<Task>> {
58        let task = self.list.pop_front()?;
59        self.len -= 1;
60        Some(task)
61    }
62
63    fn is_empty(&self) -> bool {
64        self.len == 0
65    }
66
67    /// Remove the first task with `task_id`. Returns true when found.
68    ///
69    /// O(n) scan, but no allocation.  In practice each priority queue is short
70    /// (a handful of RT threads), so the scan terminates quickly.
71    fn remove_by_id(&mut self, task_id: crate::process::TaskId) -> bool {
72        let mut cursor = self.list.front_mut();
73        loop {
74            match cursor.get() {
75                None => return false,
76                Some(task) if task.id == task_id => {
77                    // remove() advances cursor to the successor; the returned
78                    // Arc is dropped here, decrementing the task refcount.
79                    let _ = cursor.remove();
80                    self.len -= 1;
81                    return true;
82                }
83                Some(_) => cursor.move_next(),
84            }
85        }
86    }
87}
88
89pub struct RealTimeClassRq {
90    queues: [RtPrioQueue; 100],
91    bitmap: u128, // 100 bits needed (0..=99)
92}
93
94impl RealTimeClassRq {
95    /// Creates a new instance.
96    pub fn new() -> Self {
97        Self {
98            queues: core::array::from_fn(|_| RtPrioQueue::new()),
99            bitmap: 0,
100        }
101    }
102
103    /// Sets bit.
104    fn set_bit(&mut self, prio: u8) {
105        self.bitmap |= 1u128 << prio;
106    }
107
108    /// Performs the clear bit operation.
109    fn clear_bit(&mut self, prio: u8) {
110        self.bitmap &= !(1u128 << prio);
111    }
112}
113
114impl SchedClassRq for RealTimeClassRq {
115    /// Performs the enqueue operation.
116    fn enqueue(&mut self, task: Arc<Task>) {
117        let prio = match task.sched_policy() {
118            super::SchedPolicy::RealTimeRR { prio } => prio.get(),
119            super::SchedPolicy::RealTimeFifo { prio } => prio.get(),
120            _ => return, // Ignore tasks that shouldn't be here
121        };
122        self.queues[prio as usize].push_back(task);
123        self.set_bit(prio);
124    }
125
126    /// Performs the len operation.
127    fn len(&self) -> usize {
128        self.queues.iter().map(|q| q.len).sum()
129    }
130
131    /// Performs the pick next operation.
132    fn pick_next(&mut self) -> Option<Arc<Task>> {
133        if self.bitmap == 0 {
134            return None;
135        }
136        // Highest priority first (99 down to 0).
137        let highest = 127 - self.bitmap.leading_zeros() as u8;
138        let q = &mut self.queues[highest as usize];
139        let task = q.pop_front()?;
140        if q.is_empty() {
141            self.clear_bit(highest);
142        }
143        Some(task)
144    }
145
146    /// Updates current.
147    fn update_current(&mut self, rt: &CurrentRuntime, task: &Task, is_yield: bool) -> bool {
148        if is_yield {
149            return true;
150        }
151        match task.sched_policy() {
152            super::SchedPolicy::RealTimeRR { .. } => {
153                // Round Robin: preempt after RT_RR_QUANTUM_TICKS (POSIX >= 100 ms).
154                rt.period_delta_ticks >= RT_RR_QUANTUM_TICKS
155            }
156            super::SchedPolicy::RealTimeFifo { .. } => {
157                // FIFO: run until blocked or yielded.
158                false
159            }
160            _ => false,
161        }
162    }
163
164    /// Performs the remove operation.
165    fn remove(&mut self, task_id: crate::process::TaskId) -> bool {
166        let mut bits = self.bitmap;
167        while bits != 0 {
168            let i = bits.trailing_zeros() as usize;
169            if self.queues[i].remove_by_id(task_id) {
170                if self.queues[i].is_empty() {
171                    self.clear_bit(i as u8);
172                }
173                // task_id is unique : stop scanning once found.
174                return true;
175            }
176            bits &= !(1u128 << i);
177        }
178        false
179    }
180}
strat9_kernel/process/sched_classes/real_time.rs

strat9_kernel/process/sched_classes/
real_time.rs
