线程调度之 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. }