201308010314计科3班王操解读.doc

HUNAN UNIVERSITY 操作系统 实验报告 题 目： 调度器 学生姓名： wc 学生学号： 201308010314 专业班级： 计科1303 同组成员： 上课老师： 肖德贵 目 录 一、内容 2 二、目的 2 三、实验设计思想和流程 2 四、主要数据结构及符号说明 2 五、程序初值及运行结果 2 六、实验体会和思考题 2 附录（源代码及注释） 2 一、内容 实验五完成了用户进程的管理，可在用户态运行多个进程。但到目前为止，采用的调度策略是很简单的FIFO调度策略。本次 实验，主要是熟悉ucore的系统调度器框架，以及基于此框架的Round-Robin（RR） 调度算法。然后参考RR调度算法的实 现，完成Stride Scheduling调度算法。 二、目的 理解操作系统的调度管理机制 熟悉 ucore 的系统调度器框架，以及缺省的Round-Robin 调度算法 基于调度器框架实现一个(Stride Scheduling)调度算法来替换缺省的调度算法 三、实验设计思想和流程 实行一个进程调度策略，到底需要实现哪些基本功能对应的数据结构？首先考虑到一个无论哪种调度算法都需要选择一个就 绪进程来占用CPU运行。为此我们可把就绪进程组织起来，可用队列（双向链表）、二叉树、红黑树、数组…等不同的组织方式。 在操作方面，如果需要选择一个就绪进程，就可以从基于某种组织方式的就绪进程集合中选择出一个进程执行。需要注意，这里“选择”和“出”是两个操作，选择是在集合中挑选一个“合适”的进程，“出”意味着离开就绪进程集合。另外考虑到一个处于运行态的进程还会由于某种原因（比如时间片用完了）回到就绪态而不能继续占用CPU执行，这就会重新进入到就绪进程集合中。这两种情况就形成了调度器相关的三个基本操作：在就绪进程集合中选择、进入就绪进程集合和离开就绪进程集合。 这三个操作属于调度器的基本操作。在进程的执行过程中，就绪进程的等待时间和执行进程的执行时间影响调度选择的重要因素，这两个因素随着时间的流逝和各种事件的发生在不停地变化，比如处于就绪态的进程等待调度的时间在增长，处于运行态的进程所消耗的时间片在减少 等。这些进程状态变化的情况需要及时让进程调度器知道，便于选择更合适的进程执行。所以这种进程变化的情况就形成了调度器相关的一个变化感知操作：timer时间事件感知操作。这样在进程运行或等待的过程中，调度器可以调整进程控制块中与进程调度相关的属性值（比如消耗的时间片、进程优先级等）并可能导致对进程组织形式的调整（比如以时间片大小的顺序来重排双向链表等），并最终可能导致调选择新的进程占用CPU运行。这个操作属于调度器的进程调度属性调整操作。考察 round-robin 调度器，在假设所有进程都充分使用了其拥有的 CPU 时间资源的情况下，所有进程得到的 CPU 时间应该 是相等的。但是有时候我们希望调度器能够更智能地为每个进程分配合理的 CPU 资源。假设我们为不同的进程分配不同的优先级，则我们有可能希望每个进程得到的时间资源与他们的优先级成正比关系。Stride调度是基于这种想法的一个较为典型和简单的算法。除了简单易于实现以外，它还有如下的特点： 可控性：如我们之前所希望的，可以证明 Stride Scheduling对进程的调度次数正比于其优先级。 确定性：在不考虑计时器事件的情况下，整个调度机制都是可预知和重现的。该算法的基本思想可以考虑如下： 1. 为每个runnable的进程设置一个当前状态stride，表示该进程当前的调度权。另外定义其对应的pass值，表示对应进 程在调度后，stride 需要进行的累加值。 2. 每次需要调度时，从当前 runnable 态的进程中选择 stride最小的进程调度。 3. 对于获得调度的进程P，将对应的stride加上其对应的步长pass（只与进程的优先权有关系）。 4. 在一段固定的时间之后，回到 2.步骤，重新调度当前stride最小的进程。 可以证明，如果令 P.pass =BigStride / P.priority 其中 P.priority 表示进程的优先权（大于 1），而 BigStride 表示一 个预先定义的大常数，则该调度方案为每个进程分配的时间将与其优先级成正比。证明过程我们在这里略去，有兴 趣的同学可以在网上查找相关资料。将该调度器应用到 ucore 的调度器框架中来，则需要将调度器接口实现如下： init: – 初始化调度器类的信息（如果有的话）。 – 初始化当前的运行队列为一个空的容器结构。（比如和RR调度算法一样，初始化为一个有序列表） enqueue – 初始化刚进入运行队列的进程 proc的s