使用优先队列实现 Stride Scheduling
在上述的实现描述中,对于每一次pick_next函数,我们都需要完整地扫描来获得当前最小的stride及其进程。这在进程非常多的时候是非常耗时和低效的,有兴趣的同学可以在实现了基于列表扫描的Stride调度器之后比较一下priority程序在Round-Robin及Stride调度器下各自的运行时间。考虑到其调度选择于优先队列的抽象逻辑一致,我们考虑使用优化的优先队列数据结构实现该调度。
优先队列是这样一种数据结构:使用者可以快速的插入和删除队列中的元素,并且在预先指定的顺序下快速取得当前在队列中的最小(或者最大)值及其对应元素。可以看到,这样的数据结构非常符合 Stride 调度器的实现。
本次实验提供了libs/skew_heap.h 作为优先队列的一个实现,该实现定义相关的结构和接口,其中主要包括:
1 // 优先队列节点的结构
2 typedef struct skew_heap_entry skew_heap_entry_t;
3 // 初始化一个队列节点
4 void skew_heap_init(skew_heap_entry_t *a);
5 // 将节点 b 插入至以节点 a 为队列头的队列中去,返回插入后的队列
6 skew_heap_entry_t *skew_heap_insert(skew_heap_entry_t *a,
7 skew_heap_entry_t *b,
8 compare_f comp);
9 // 将节点 b 插入从以节点 a 为队列头的队列中去,返回删除后的队列
10 skew_heap_entry_t *skew_heap_remove(skew_heap_entry_t *a,
11 skew_heap_entry_t *b,
12 compare_f comp);
其中优先队列的顺序是由比较函数comp决定的,sched_stride.c中提供了proc_stride_comp_f比较器用来比较两个stride的大小,你可以直接使用它。当使用优先队列作为Stride调度器的实现方式之后,运行队列结构也需要作相关改变,其中包括:
struct run_queue中的lab6_run_pool指针,在使用优先队列的实现中表示当前优先队列的头元素,如果优先队列为空,则其指向空指针(NULL)。
struct proc_struct中的lab6_run_pool结构,表示当前进程对应的优先队列节点。本次实验已经修改了系统相关部分的代码,使得其能够很好地适应LAB6新加入的数据结构和接口。而在实验中我们需要做的是用优先队列实现一个正确和高效的Stride调度器,如果用较简略的伪代码描述,则有:
init(rq):
– Initialize rq->run_list
– Set rq->lab6_run_pool to NULL
– Set rq->proc_num to 0enqueue(rq, proc)
– Initialize proc->time_slice
– Insert proc->lab6_run_pool into rq->lab6_run_pool
– rq->proc_num ++dequeue(rq, proc)
– Remove proc->lab6_run_pool from rq->lab6_run_pool
– rq->proc_num --pick_next(rq)
– If rq->lab6_run_pool == NULL, return NULL
– Find the proc corresponding to the pointer rq->lab6_run_pool
– proc->lab6_stride += BIG_STRIDE / proc->lab6_priority
– Return procproc_tick(rq, proc):
– If proc->time_slice > 0, proc->time_slice --
– If proc->time_slice == 0, set the flag proc->need_resched