线程调度之 Round Robin 算法

时间片轮转调度算法(Round Robin)的基本思想是让每个线程在就绪队列中的等待时间与占用 CPU 的执行时间成正比例。其大致实现是：

  1. 将系所有的就绪线程按照 FCFS 原则，排成一个就绪队列。
  2. 每次调度时将 CPU 分派（dispatch）给队首进程，让其执行一个时间片。
  3. 在时钟中断时，统计比较当前线程时间片是否已经用完。 　- 如用完，则调度器（scheduler）暂停当前进程的执行，将其送到就绪队列的末尾，并通过切换执行就绪队列的队首进程。 　- 如没用完，则线程继续使用。

对于不同的调度算法，我们实现了一个调度接口框架如下：

  1. pub trait Scheduler {
  2.     fn push(&mut self, tid: Tid);　　　　//把Tid线程放入就绪队列
  3.     fn pop(&mut self) -> Option<Tid>;　 //从就绪队列取出线程
  4.     fn tick(&mut self) -> bool;　　　　　//时钟tick（代表时间片）处理
  5.     fn exit(&mut self, tid: Tid);　　　　//线程退出
  6. }

时间片轮转调度算法对上述四个函数接口有具体的实现。这里我们直接给出时间片轮转调度算法的实现代码，有兴趣者可自行去研究算法细节。

  1. // src/process/scheduler.rs
  3. use alloc::vec::Vec;
  5. #[derive(Default)]
  6. struct RRInfo {
  7.     valid: bool,
  8.     time: usize,
  9.     prev: usize,
  10.     next: usize,
  11. }
  13. pub struct RRScheduler {
  14.     threads: Vec<RRInfo>,
  15.     max_time: usize,
  16.     current: usize,
  17. }
  19. impl RRScheduler {
  20.     // 设置每个线程连续运行的最大 tick 数
  21.     pub fn new(max_time_slice: usize) -> Self {
  22.         let mut rr = RRScheduler {
  23.             threads: Vec::default(),
  24.             max_time: max_time_slice,
  25.             current: 0,
  26.         };
  27.         rr.threads.push(
  28.             RRInfo {
  29.                 valid: false,
  30.                 time: 0,
  31.                 prev: 0,
  32.                 next: 0,
  33.             }
  34.         );
  35.         rr
  36.     }
  37. }
  38. impl Scheduler for RRScheduler {
  39.     // 分为 1. 新线程 2. 时间片耗尽被切换出的线程 两种情况
  40.     fn push(&mut self, tid : Tid) {
  41.         let tid = tid + 1;
  42.         if tid + 1 > self.threads.len() {
  43.             self.threads.resize_with(tid + 1, Default::default);
  44.         }
  46.         if self.threads[tid].time == 0 {
  47.             self.threads[tid].time = self.max_time;
  48.         }
  50.         let prev = self.threads[0].prev;
  51.         self.threads[tid].valid = true;
  52.         self.threads[prev].next = tid;
  53.         self.threads[tid].prev = prev;
  54.         self.threads[0].prev = tid;
  55.         self.threads[tid].next = 0;
  56.     }
  58.     fn pop(&mut self) -> Option<Tid> {
  59.         let ret = self.threads[0].next;
  60.         if ret != 0 {
  61.             let next = self.threads[ret].next;
  62.             let prev = self.threads[ret].prev;
  63.             self.threads[next].prev = prev;
  64.             self.threads[prev].next = next;
  65.             self.threads[ret].prev = 0;
  66.             self.threads[ret].next = 0;
  67.             self.threads[ret].valid = false;
  68.             self.current = ret;
  69.             Some(ret-1)
  70.         }else{
  71.             None
  72.         }
  73.     }
  75.     // 当前线程的可用时间片 -= 1
  76.     fn tick(&mut self) -> bool{
  77.         let tid = self.current;
  78.         if tid != 0 {
  79.             self.threads[tid].time -= 1;
  80.             if self.threads[tid].time == 0 {
  81.                 return true;
  82.             }else{
  83.                 return false;
  84.             }
  85.         }
  86.         return true;
  87.     }
  89.     fn exit(&mut self, tid : Tid) {
  90.         let tid = tid + 1;
  91.         if self.current == tid {
  92.             self.current = 0;
  93.         }
  94.     }
  95. }