操作系统实验报告
学 院： 理学院
专业班级： 应数
07-2
学生姓名： 宋义洪
学生学号： 200713620
指导教师： 李声
2010 年 05 月 01 日
多级反馈队列调度算法
一、 实验目的
用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调
度算法的理解。
二、 实验环境
操作系统 Window XP
编写环境 dreamweaver
编写语言 Javascript、Html、Css
Javascript 库 Jquery
运行环境 IE 浏览器
三、 内容与要求
编写并调试一个模拟的进程调度程序，采用“基于时间片的轮转调度算法”
对多个进程进行调度。
每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：
进程名、到达时间、需要运行时间、已运行时间、进程状态等等。进程的到达
时间及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的
到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪 W（Wait）、运行 R（Run）两种状态之一。
就绪进程获得 CPU 后都只能运行一个时间片。用运行时间加 1 来表示。
如果运行一个时间片后，进程的已占用 CPU 时间已达到所需要的运行时间，
则撤消该进程，如果运行一个时间片后进程的已占用 CPU 时间还未达所需要的
运行时间，也就是进程还需要继续运行，此时应分配时间片给就绪队列中排在
该进程之后的进程，并将它插入就绪队列队尾。 每进行一次调度程序都打印一
次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
重复以上过程，直到所有进程都完成为止。
四、 实验原理
多级反馈队列算法原理：当一个新进程进入内存后，首先将它放入第一个
队列的末尾，按 FCFS 原则排队等待执行。当轮到该进程执行时，如能在该时
间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调度
程序便将该进程转入第二队列的末尾，再同样地按 FCFS 原则等待调度执行，
以此类推。
五、 实验步骤
1、建立根节点，并在根节点下建立若干队列节点形成队列树
2、当进程进入时便把进程插入到第一队列节点的最左形成最左进程叶节点
3、重复步骤 2 直至无进程进入
4、按照后续遍历队列树找出第一个进程叶节点，就是所要运行的进程
5、运行找到的进程，若该进程时间片执行完毕，则把该节点从所在队列节
点删除；若该进程时间片未执行完毕，则把该节点从所在队列节点删除，
并把节点插入右临近队列节点最左，若无右临近队列节点，则插入该队
列节点最左
6、若有进程进入中断当前进程跳到步骤 2；若无进程进入跳到步骤 4 直至
无进程节点，则运行完毕
S
1
S
2
S
1
就绪队列 1
就绪队列 2
就绪队列 3
就绪队列 n
至 CPU
至 CPU
至 CPU
( 时间片： S
1
<S
2
<S
3
)
图 1 实验原理图
…
时间片未
执行完毕
时间片未
执行完毕
…
…
根节
点
最
右
进
程
…………
队 列
节点
2
队 列
节点
n
队 列
节 点
1
进程进入
新进
程
最右
进程
最左
进程
时间片未
执行完毕
最左
进程
最 右
进程
图 2 实验步骤图
