strat9_kernel/process/sched_classes/
real_time.rs

1// SPDX-License-Identifier: MPL-2.0
2
3use super::{CurrentRuntime, SchedClassRq};
4use crate::{arch::timer::TIMER_HZ, process::task::Task};
5use alloc::sync::Arc;
6use core::sync::atomic::Ordering;
7use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListLink};
8
9/// RT Round-Robin quantum in ticks.
10///
11/// POSIX specifies a minimum of 100ms for SCHED_RR (Linux default: 100ms).
12/// At TIMER_HZ=100: 10 ticks x 10 ms/tick = 100 ms.
13const RT_RR_QUANTUM_TICKS: u64 = TIMER_HZ / 10;
14
15/// RT budget per period in ticks.
16///
17/// An RT task that consumes this many ticks within a single budget period
18/// is temporarily degraded to Fair class until the period expires.  This
19/// prevents a single RT task from permanently starving Fair tasks.
20///
21/// At TIMER_HZ=100: 100 ticks = 1 second of wall-clock time.
22const RT_BUDGET_TICKS: u64 = 100;
23
24/// RT budget period in ticks.
25///
26/// After this many ticks the budget resets.  Must be >= RT_BUDGET_TICKS.
27/// At TIMER_HZ=100: 500 ticks = 5 seconds.
28const RT_BUDGET_PERIOD_TICKS: u64 = 500;
29
30/// Real-time priority (0-99). Higher value means higher priority.
31#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
32pub struct RealTimePriority(u8);
33
34impl RealTimePriority {
35    pub const MIN: Self = Self(0);
36    pub const MAX: Self = Self(99);
37
38    /// Creates a new instance.
39    pub fn new(prio: u8) -> Self {
40        Self(prio.clamp(Self::MIN.0, Self::MAX.0))
41    }
42
43    /// Performs the get operation.
44    pub fn get(self) -> u8 {
45        self.0
46    }
47}
48
49// Intrusive adapter: the list owns Arc<Task> references and navigates via
50// the `rt_link` field embedded directly in the Task control block.
51// Zero heap allocation on enqueue or dequeue; no fixed capacity limit.
52intrusive_adapter!(pub RtTaskAdapter = Arc<Task>: Task { rt_link: LinkedListLink });
53
54/// Single-priority FIFO backed by an intrusive doubly-linked list.
55struct RtPrioQueue {
56    list: LinkedList<RtTaskAdapter>,
57    len: usize,
58}
59
60impl RtPrioQueue {
61    fn new() -> Self {
62        Self {
63            list: LinkedList::new(RtTaskAdapter::new()),
64            len: 0,
65        }
66    }
67
68    fn push_back(&mut self, task: Arc<Task>) {
69        self.list.push_back(task);
70        self.len += 1;
71    }
72
73    fn pop_front(&mut self) -> Option<Arc<Task>> {
74        let task = self.list.pop_front()?;
75        self.len -= 1;
76        Some(task)
77    }
78
79    fn is_empty(&self) -> bool {
80        self.len == 0
81    }
82
83    /// Remove the first task with `task_id`. Returns true when found.
84    fn remove_by_id(&mut self, task_id: crate::process::TaskId) -> bool {
85        let mut cursor = self.list.front_mut();
86        loop {
87            match cursor.get() {
88                None => return false,
89                Some(task) if task.id == task_id => {
90                    let _ = cursor.remove();
91                    self.len -= 1;
92                    return true;
93                }
94                Some(_) => cursor.move_next(),
95            }
96        }
97    }
98}
99
100pub struct RealTimeClassRq {
101    queues: [RtPrioQueue; 100],
102    bitmap: u128,
103}
104
105impl RealTimeClassRq {
106    pub fn new() -> Self {
107        Self {
108            queues: core::array::from_fn(|_| RtPrioQueue::new()),
109            bitmap: 0,
110        }
111    }
112
113    fn set_bit(&mut self, prio: u8) {
114        self.bitmap |= 1u128 << prio;
115    }
116
117    fn clear_bit(&mut self, prio: u8) {
118        self.bitmap &= !(1u128 << prio);
119    }
120
121    /// Check if an RT task's budget has expired and the period has not yet
122    /// elapsed.  Returns `true` if the task should be skipped (degraded).
123    fn is_budget_exhausted(task: &Task, now: u64) -> bool {
124        if !task.rt_degraded.load(Ordering::Relaxed) {
125            return false;
126        }
127        let period_start = task.rt_budget_period_start.load(Ordering::Relaxed);
128        now.saturating_sub(period_start) < RT_BUDGET_PERIOD_TICKS
129    }
130
131    /// Reset the RT budget for a task.  Called when the period has expired
132    /// or when the task is first enqueued.
133    fn reset_budget(task: &Task, now: u64) {
134        task.rt_budget_remaining
135            .store(RT_BUDGET_TICKS, Ordering::Relaxed);
136        task.rt_budget_period_start.store(now, Ordering::Relaxed);
137        task.rt_degraded.store(false, Ordering::Relaxed);
138    }
139
140    /// Check if the front task of a priority queue is degraded.
141    fn front_is_degraded(q: &RtPrioQueue, now: u64) -> bool {
142        if let Some(task) = q.list.front().get() {
143            Self::is_budget_exhausted(task, now)
144        } else {
145            false
146        }
147    }
148}
149
150impl SchedClassRq for RealTimeClassRq {
151    fn enqueue(&mut self, task: Arc<Task>) {
152        let prio = match task.sched_policy() {
153            super::SchedPolicy::RealTimeRR { prio } => prio.get(),
154            super::SchedPolicy::RealTimeFifo { prio } => prio.get(),
155            _ => return,
156        };
157
158        // If the task was degraded and its period has expired, reset budget.
159        let now = crate::process::scheduler::ticks();
160        if task.rt_degraded.load(Ordering::Relaxed) {
161            let period_start = task.rt_budget_period_start.load(Ordering::Relaxed);
162            if now.saturating_sub(period_start) >= RT_BUDGET_PERIOD_TICKS {
163                Self::reset_budget(&task, now);
164            }
165        } else if task.rt_budget_remaining.load(Ordering::Relaxed) == 0 {
166            // First enqueue or budget was never initialized.
167            Self::reset_budget(&task, now);
168        }
169
170        self.queues[prio as usize].push_back(task);
171        self.set_bit(prio);
172    }
173
174    fn len(&self) -> usize {
175        self.queues.iter().map(|q| q.len).sum()
176    }
177
178    fn pick_next(&mut self) -> Option<Arc<Task>> {
179        if self.bitmap == 0 {
180            return None;
181        }
182
183        let now = crate::process::scheduler::ticks();
184
185        // Scan from highest to lowest priority, skipping degraded tasks.
186        let mut scan_bitmap = self.bitmap;
187        while scan_bitmap != 0 {
188            let prio = 127 - scan_bitmap.leading_zeros() as u8;
189            let q = &mut self.queues[prio as usize];
190
191            if Self::front_is_degraded(q, now) {
192                // Rotate: pop front, push back so others at same priority run.
193                if let Some(task) = q.pop_front() {
194                    q.push_back(task);
195                }
196                if q.is_empty() {
197                    self.clear_bit(prio);
198                }
199                scan_bitmap &= !(1u128 << prio);
200                continue;
201            }
202
203            let task = q.pop_front()?;
204            if q.is_empty() {
205                self.clear_bit(prio);
206            }
207            return Some(task);
208        }
209
210        // All RT tasks degraded — let Fair class handle scheduling.
211        None
212    }
213
214    fn update_current(&mut self, rt: &CurrentRuntime, task: &Task, is_yield: bool) -> bool {
215        if is_yield {
216            return true;
217        }
218
219        // Consume budget.
220        let remaining = task.rt_budget_remaining.load(Ordering::Relaxed);
221        let consumed = rt.delta_ticks.min(remaining);
222        let new_remaining = remaining.saturating_sub(consumed);
223        task.rt_budget_remaining
224            .store(new_remaining, Ordering::Relaxed);
225
226        // If budget exhausted, mark degraded.  The task will be skipped
227        // in pick_next until its period expires.
228        if new_remaining == 0 && consumed > 0 {
229            task.rt_degraded.store(true, Ordering::Relaxed);
230            return true; // Preempt immediately.
231        }
232
233        match task.sched_policy() {
234            super::SchedPolicy::RealTimeRR { .. } => {
235                // Round Robin: preempt after RT_RR_QUANTUM_TICKS.
236                rt.period_delta_ticks >= RT_RR_QUANTUM_TICKS
237            }
238            super::SchedPolicy::RealTimeFifo { .. } => {
239                // FIFO: run until blocked, yielded, or budget exhausted.
240                false
241            }
242            _ => false,
243        }
244    }
245
246    fn remove(&mut self, task_id: crate::process::TaskId) -> bool {
247        let mut bits = self.bitmap;
248        while bits != 0 {
249            let i = bits.trailing_zeros() as usize;
250            if self.queues[i].remove_by_id(task_id) {
251                if self.queues[i].is_empty() {
252                    self.clear_bit(i as u8);
253                }
254                return true;
255            }
256            bits &= !(1u128 << i);
257        }
258        false
259    }
260}
strat9_kernel/process/sched_classes/real_time.rs

strat9_kernel/process/sched_classes/
real_time.rs
