OS ucore lab 6

练习零： 填写已有实验：

<pre mdtype="fences" cid="n88" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">复制以下文件 其中 proc.c 和 trap.c 需要进行修正
vmm.c trap.c default_pmm.c pmm.c proc.c swap_fifo.c
proc.c:
static struct proc_struct *alloc_proc(void) {
//初始化进程所属就绪队列
proc->rq = NULL;
//初始化就绪队列指针
list_init(&(proc->run_link));
//初始化时间片
proc->time_slice = 0;
}
trap.c:
static void trap_dispatch(struct trapframe *tf) {
// 在时钟中断下添加以下几行并去掉之前设置 进程需要调度标记
// 这个标记现在已经被调度程序所使用了，不再需要自己控制
++ticks;
sched_class_proc_tick(current);
// current->need_resched = 1;
}</pre>

练习一：使用 Round Robin 调度算法（不需要编码）

完成练习0后，建议大家比较一下（可用kdiff3等文件比较软件）个人完成的lab5和练习0完成后的刚修改的lab6之间的区别，分析了解lab6采用RR调度算法后的执行过程。执行make grade，大部分测试用例应该通过。但执行priority.c应该过不去。

请在实验报告中完成

• Q1： 请理解并分析sched_calss中各个函数指针的用法，并接合Round Robin 调度算法描ucore的调度执行过程

• Q2：请在实验报告中简要说明如何设计实现”多级反馈队列调度算法“，给出概要设计，鼓励给出详细设计

• Q1:

<pre mdtype="fences" cid="n76" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">// 初始化算法所需要的数据结构
static void RR_init(struct run_queue rq) {
list_init(&(rq->run_list));
rq->proc_num = 0;
}
/** 进程入队:
将进程加入就绪队列(不同的就绪队列的时间片不同 也就是说有不同优先级的就绪队列)
在RR调度中,当进程时间片为0或因某种情况被阻塞，则将其加入到就绪队列并将其时间片进行重置
***/
​
static void RR_enqueue(struct run_queue *rq, struct proc_struct proc) {
assert(list_empty(&(proc->run_link)));
list_add_before(&(rq->run_list), &(proc->run_link));
if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) {
proc->time_slice = rq->max_time_slice;
}
proc->rq = rq;
rq->proc_num ++;
}
​
// 进程出队：将进程从就绪队列中删去
static void RR_dequeue(struct run_queue rq, struct proc_struct proc) {
assert(!list_empty(&(proc->run_link)) && proc->rq == rq);
list_del_init(&(proc->run_link));
rq->proc_num --;
}
/挑选出下一个进程
占用处理机去运行
在 RR调度中 直接按照就绪队列的顺序轮询
***/
static struct proc_struct * RR_pick_next(struct run_queue *rq) {
list_entry_t *le = list_next(&(rq->run_list));
if (le != &(rq->run_list)) {
return le2proc(le, run_link);
}
return NULL;
}
// 时钟中断时调用此函数
// 在RR调度中，每次调用都会减少当前进程时间片
static void RR_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
if (proc->time_slice > 0) {
proc->time_slice --;
}
if (proc->time_slice == 0) {
proc->need_resched = 1;
}
}
​</pre>

Round Robin 调度执行过程：

<pre mdtype="fences" cid="n116" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">* 在ucore中调用调度器的主体函数（不包括init，proc_tick）的代码仅存在在wakeup_proc和schedule，前者的作用在于将某一个指定进程放入可执行进程队列中，后者在于将当前执行的进程放入可执行队列中，然后将队列中选择的下一个执行的进程取出执行；
​

• 当需要将某一个进程加入就绪进程队列中，则需要将这个进程的能够使用的时间片进行初始化，然后将其插入到使用链表组织的队列的对尾；这就是具体的Round-Robin enqueue函数的实现；
  ​

• 当需要将某一个进程从就绪队列中取出的时候，只需要将其直接删除即可；
  ​

• 当需要取出执行的下一个进程的时候，只需要将就绪队列的队头取出即可；
  ​

• 每当出现一个时钟中断，则会将当前执行的进程的剩余可执行时间减1，一旦减到了0，则将其标记为可以被调度的，这样在ISR中的后续部分就会调用schedule函数将这个进程切换出去</pre>

• Q2：

  <pre mdtype="fences" cid="n139" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit;">在proc_struct中添加总共N个多级反馈队列的入口，每个队列都有着各自的优先级，编号越大的队列优先级约低，并且优先级越低的队列上时间片的长度越大，为其上一个优先级队列的两倍；并且在PCB中记录当前进程所处的队列的优先级；
  处理调度算法初始化的时候需要同时对N个队列进行初始化；
  在处理将进程加入到就绪进程集合的时候，观察这个进程的时间片有没有使用完，如果使用完了，就将所在队列的优先级调低，加入到优先级低1级的队列中去，如果没有使用完时间片，则加入到当前优先级的队列中去；
  在同一个优先级的队列内使用时间片轮转算法；
  在选择下一个执行的进程的时候，有限考虑高优先级的队列中是否存在任务，如果不存在才转而寻找较低优先级的队列；（有可能导致饥饿）
  从就绪进程集合中删除某一个进程就只需要在对应队列中删除即可；
  处理时间中断的函数不需要改变；
  至此完成了多级反馈队列调度算法的具体设计；
  ​</pre>

---

练习二: 实现 Stride Scheduling 调度算法（需要编码）

首先需要换掉RR调度器的实现，即用default_sched_stride_c覆盖default_sched.c。然后根据此文件和后续文档对Stride度器的相关描述，完成Stride调度算法的实现。

<pre mdtype="fences" cid="n156" lang="c#" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">proc.c:
static struct proc_struct *alloc_proc(void) {
proc->rq = NULL;
list_init(&(proc->run_link));
proc->time_slice = 0;
// 斜堆实现的 Priority Queue
proc->lab6_run_pool.parent = proc->lab6_run_pool.left = proc->lab6_run_pool.right = NULL;
// 优先级 (和步进成反比)
proc->lab6_priority = 0;
// 步进值
proc->lab6_stride = 0;
}</pre>

<pre mdtype="fences" cid="n157" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">// 就是32位系统下int的最大值 2147483647

define BIG_STRIDE (((uint32_t)-1) / 2)

​
static void stride_init(struct run_queue *rq) {
list_init(&rq->run_list);
rq->lab6_run_pool = NULL;
rq->proc_num = 0;
}
//在将指定进程加入就绪队列的时候，需要调用斜堆的插入函数将其插入到斜堆中，然后对时间片等信息进行更新
static void stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
if (proc->lab6_priority == 0) {
proc->lab6_priority = 1;
}
if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) {
proc->time_slice = rq->max_time_slice; // 将该进程剩余时间置为时间片大小
}
proc->rq = rq; // 更新进程的就绪队列
++rq->proc_num;// 维护就绪队列中进程的数量
}
​
//stride_dequeue：将指定进程从就绪队列中删除，只需要将该进程从斜堆中删除掉
static void stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {
rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
--rq->proc_num;// 维护就绪队列中的进程总数
}
//stride_pick_next: 选择下一个要执行的进程，根据stride算法，只需要选择stride值最小的进程，即斜堆的根节点对应的进程
static struct proc_struct * stride_pick_next(struct run_queue *rq) {
if (rq->lab6_run_pool == NULL) {
return NULL;
}
// 斜堆的顶就是 stride 值最小的进程
struct proc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool);
// 提前增加 stride 的值 因为在之后调度别的进程之前一定会执行这么多
p->lab6_stride += BIG_STRIDE / p->lab6_priority;
return p;
}
//stride_proc_tick：每次时钟中断需要调用的函数，与RR算法中的实现没有区别
static void stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
if (proc->time_slice == 0) {
proc->need_resched = 1;
} else {
--proc->time_slice;// 维护就绪队列中的进程总数
}
}</pre>

实验结果：

图

参考链接