use crate::{ProcessControlBlock, ProcessId, ProcessState};
use alloc::boxed::Box;
use alloc::collections::VecDeque;
use alloc::vec::Vec;
pub struct ReadyQueue {
queue: VecDeque<Box<ProcessControlBlock>>,
}
impl ReadyQueue {
pub fn new() -> Self {
Self {
queue: VecDeque::new(),
}
}
pub fn push_back(&mut self, process: Box<ProcessControlBlock>) {
self.queue.push_back(process);
}
pub fn pop_front(&mut self) -> Option<Box<ProcessControlBlock>> {
self.queue.pop_front()
}
pub fn is_empty(&self) -> bool {
self.queue.is_empty()
}
pub fn len(&self) -> usize {
self.queue.len()
}
pub fn retain(&mut self, f: impl Fn(&ProcessControlBlock) -> bool) {
self.queue.retain(|p| f(p));
}
pub fn iter(&self) -> impl Iterator<Item = &ProcessControlBlock> {
self.queue.iter().map(|b| b.as_ref())
}
pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut ProcessControlBlock> {
self.queue.iter_mut().map(|b| b.as_mut())
}
}
impl Default for ReadyQueue {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SchedulerStats {
pub current_pid: Option<ProcessId>,
pub ready: usize,
pub blocked: usize,
pub zombies: usize,
pub remaining_ticks: usize,
pub total: usize,
}
pub struct RoundRobinScheduler {
ready_queue: ReadyQueue,
blocked_queue: VecDeque<Box<ProcessControlBlock>>,
current: Option<Box<ProcessControlBlock>>,
zombies: Vec<ProcessControlBlock>,
time_slice: usize,
remaining_ticks: usize,
}
impl RoundRobinScheduler {
pub fn new(time_slice: usize) -> Self {
let time_slice = time_slice.max(1);
Self {
ready_queue: ReadyQueue::new(),
blocked_queue: VecDeque::new(),
current: None,
zombies: Vec::with_capacity(8),
time_slice,
remaining_ticks: time_slice,
}
}
pub fn add_process(&mut self, process: Box<ProcessControlBlock>) -> Result<(), &'static str> {
if process.state() != ProcessState::Ready {
return Err("Process must be in Ready state");
}
self.ready_queue.push_back(process);
Ok(())
}
fn park_process(&mut self, mut process: Box<ProcessControlBlock>) {
match process.state() {
ProcessState::Running => {
process
.set_state(ProcessState::Ready)
.expect("running process can return to ready");
self.ready_queue.push_back(process);
}
ProcessState::Ready => self.ready_queue.push_back(process),
ProcessState::Blocked => self.blocked_queue.push_back(process),
ProcessState::Zombie => self.zombies.push(*process),
}
}
fn select_next_ready(&mut self) -> Option<&mut ProcessControlBlock> {
let mut pcb = self.ready_queue.pop_front()?;
pcb.set_state(ProcessState::Running)
.expect("ready process can be scheduled");
self.remaining_ticks = self.time_slice;
self.current = Some(pcb);
self.current.as_deref_mut()
}
pub fn schedule(&mut self) -> Option<&mut ProcessControlBlock> {
if let Some(proc) = self.current.take() {
self.park_process(proc);
}
self.select_next_ready()
}
pub fn yield_current(&mut self) {
let _ = self.schedule();
}
pub fn tick(&mut self) {
if self.current.is_none() {
let _ = self.schedule();
return;
}
if self.remaining_ticks > 0 {
self.remaining_ticks -= 1;
}
if self.remaining_ticks == 0 {
let _ = self.schedule();
}
}
pub fn current(&self) -> Option<&ProcessControlBlock> {
self.current.as_deref()
}
pub fn current_mut(&mut self) -> Option<&mut ProcessControlBlock> {
self.current.as_deref_mut()
}
pub fn ready_count(&self) -> usize {
self.ready_queue.len()
}
pub fn blocked_count(&self) -> usize {
self.blocked_queue.len()
}
pub fn zombie_count(&self) -> usize {
self.zombies.len()
}
pub fn stats(&self) -> SchedulerStats {
let current = usize::from(self.current.is_some());
let ready = self.ready_queue.len();
let blocked = self.blocked_queue.len();
let zombies = self.zombies.len();
SchedulerStats {
current_pid: self.current.as_ref().map(|p| p.pid()),
ready,
blocked,
zombies,
remaining_ticks: self.remaining_ticks,
total: current + ready + blocked + zombies,
}
}
pub fn is_idle(&self) -> bool {
self.current.is_none() && self.ready_queue.is_empty()
}
pub fn find_zombie_child(&self, parent_pid: ProcessId) -> Option<(ProcessId, i32)> {
for pcb in &self.zombies {
if pcb.parent_pid() == Some(parent_pid) && pcb.state() == ProcessState::Zombie {
return Some((pcb.pid(), pcb.exit_code().unwrap_or(0)));
}
}
None
}
pub fn remove_zombie(&mut self, pid: ProcessId) -> bool {
if let Some(pos) = self.zombies.iter().position(|p| p.pid() == pid) {
self.zombies.remove(pos);
true
} else {
false
}
}
pub fn has_living_children(&self, parent_pid: ProcessId) -> bool {
let in_current = self
.current
.as_ref()
.is_some_and(|p| p.parent_pid() == Some(parent_pid));
let in_ready = self
.ready_queue
.iter()
.any(|p| p.parent_pid() == Some(parent_pid));
let in_blocked = self
.blocked_queue
.iter()
.any(|p| p.parent_pid() == Some(parent_pid));
in_current || in_ready || in_blocked
}
pub fn unblock_process(&mut self, pid: ProcessId) -> bool {
if let Some(pos) = self.blocked_queue.iter().position(|p| p.pid() == pid) {
if let Some(mut pcb) = self.blocked_queue.remove(pos) {
pcb.set_state(ProcessState::Ready)
.expect("blocked process can be readied");
self.ready_queue.push_back(pcb);
return true;
}
}
false
}
pub fn all_processes(&self) -> Vec<&ProcessControlBlock> {
let mut out = Vec::new();
if let Some(ref p) = self.current {
out.push(p.as_ref());
}
for p in self.ready_queue.iter() {
out.push(p);
}
for p in &self.blocked_queue {
out.push(p.as_ref());
}
for p in &self.zombies {
out.push(p);
}
out
}
pub fn block_current(&mut self) {
if let Some(ref mut pcb) = self.current {
pcb.set_state(ProcessState::Blocked)
.expect("running process can block");
}
}
pub fn pick_next_ready(&mut self) -> Option<&ProcessControlBlock> {
if let Some(old) = self.current.take() {
self.park_process(old);
}
self.select_next_ready().map(|p| &*p)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn process(pid: usize, state: ProcessState, parent: Option<usize>) -> Box<ProcessControlBlock> {
let mut pcb = ProcessControlBlock::new(
ProcessId::from_usize(pid),
"test",
parent.map(ProcessId::from_usize),
);
pcb.set_state_unchecked(state);
Box::new(pcb)
}
#[test]
fn tick_switches_after_configured_time_slice() {
let mut scheduler = RoundRobinScheduler::new(2);
scheduler
.add_process(process(40, ProcessState::Ready, None))
.unwrap();
scheduler
.add_process(process(41, ProcessState::Ready, None))
.unwrap();
scheduler.schedule();
scheduler.tick();
assert_eq!(scheduler.current().map(|p| p.pid().as_usize()), Some(40));
scheduler.tick();
assert_eq!(scheduler.current().map(|p| p.pid().as_usize()), Some(41));
}
#[test]
fn blocked_process_can_be_unblocked() {
let mut scheduler = RoundRobinScheduler::new(2);
scheduler
.add_process(process(20, ProcessState::Ready, None))
.unwrap();
scheduler
.add_process(process(21, ProcessState::Ready, None))
.unwrap();
scheduler.schedule();
scheduler.block_current();
scheduler.pick_next_ready();
assert!(scheduler.unblock_process(ProcessId::from_usize(20)));
assert_eq!(scheduler.blocked_count(), 0);
assert_eq!(scheduler.ready_count(), 1);
}
#[test]
fn zombie_current_is_retained_for_wait() {
let parent = ProcessId::from_usize(99);
let mut scheduler = RoundRobinScheduler::new(2);
scheduler
.add_process(process(30, ProcessState::Ready, Some(parent.as_usize())))
.unwrap();
scheduler
.add_process(process(31, ProcessState::Ready, None))
.unwrap();
scheduler.schedule().unwrap().set_exit_code(7);
scheduler.schedule();
assert_eq!(
scheduler.find_zombie_child(parent),
Some((ProcessId::from_usize(30), 7))
);
assert!(scheduler.remove_zombie(ProcessId::from_usize(30)));
}
#[test]
fn living_child_query_excludes_reapable_zombies() {
let parent = ProcessId::from_usize(77);
let mut scheduler = RoundRobinScheduler::new(1);
scheduler
.add_process(process(78, ProcessState::Ready, Some(parent.as_usize())))
.unwrap();
scheduler.schedule().unwrap().set_exit_code(9);
scheduler.schedule();
assert_eq!(
scheduler.find_zombie_child(parent),
Some((ProcessId::from_usize(78), 9))
);
assert!(!scheduler.has_living_children(parent));
}
}