This model paper was revised by LINDA on December 15, .
This model paper was revised by LINDA on December 15, .
多级反馈队列调度算法的实现
学生实习报告
课程名称_ 数据结构与数据处理应用训练
题目名称 多级反馈队列调度算法的实现
学生学院 计算机与计算科学
专业班级
学 号
学生姓名
指导教师
年 2
多级反馈队列调度算法的实现
【摘要】
多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程(任务)得到响应又能使短进程(任务)迅速完成。UNIX操作系统便采取这种算法，而本次试验就是试用C语言模拟某多级反馈队列调度算法。本次试验中前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8，最后一级就绪队列采用FIFO调度，将任务进入多级队列进行模拟，任务从优先级高的队列到优先级地的队列的顺序逐一进入，还用了算法支持抢占式，最后完成模拟，得到各个任务先后完成的顺序，还有得到各个任务的响应时间、离开时间、周转时间。
【关键词】 队列 优先级 任务 时间
1 内容与要求
【内容】
多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程(任务)得到响应又能使短进程(任务)迅速完成。UNIX操作系统便采取这种算法，本次试验就是试用C语言模拟某多级反馈队列调度算法，通过输入任务号、到达时间、运行时间，求出任务完成的先后顺序以及各个任务的响应时间、离开时间、周转时间。
【要求】
多级反馈队列调度算法描述：
1、该调度算法设置四级就绪队列：前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8；最后一级就绪队列采用FIFO调度。
2、任务在进入待调度的队列等待时，首先进入优先级最高的队列等待。
3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务，则调度次优先级队列中的任务，依次类推。
4、对于同一个队列中的各个任务，按照队列指定调度方法调度。每次任务调度执行后，若没有完成任务，就被降到下一个低优先级队列中。
5、在低优先级的队列中的任务在运行时，又有新到达的任务，CPU马上分配给新到达的任务。(注：与原来的题目不同，原题是在低优先级的队列中的任务在运行时，又有新到达的任务时，要在运行完这个时间片后，CPU马上分配给新到达的任务，而本题不需要在运行完这个时间片，即正在进行的任务立刻停止，CPU马上分配给新到达的任务)
6、为方便实现，时间以1为单位，用整数数据表示；且每个时间点，最多只有一个任务请求服务(即输入)。
2 总体设计
算法总体思路：
这是建立在一个时间轴上的，即时刻，一个一个时刻(时间点)进行。
2.1.1 主函数思路：
先初始化所有队列，再输入任务个数，如果输入个数为0，则重新输入，然后输入各个任务的信息，即任务号、到达时间、运行时间，再当时刻到任务的到达时间时，就创建任务，然后运行任务，时刻自动加1 ，创建任务与运行任务进行循环，直到所有任务进行完或所有队列为空才跳出循环，最后清空所有队列。
2.1.2 功能函数思路：
void create(LinkQueue* x,Job job)：使任务的已运行时间为0，再使任务进入第一个队列。
void function(LinkQueue* x, int timing)：四个队列从第一个到第四个，即从最高优先级开始，任务在4个队列中逐个进行，根据任务是否为第一次执行，求出响应时间，任务完成时，求出离开时间和周转时间输出信息，在前3个队列，如果任务刚完成一个就绪队列的时间片，就降低优先级，使任务进入下一个队列。
功能模块介绍：
void main ()
函数功能：主函数
void InitQueue(LinkQueue& HQ)：队列的初始化
void EnQueue(LinkQueue& HQ,ElemType item)
函数功能：向队列中插入一个元素
ElemType OutQueue(LinkQueue& HQ)
函数功能：从队列中删除一个元素
ElemType *PeekQueue(LinkQueue& HQ)
函数功能：读取队首元素
bool Empty
c语言模拟多级反馈队列调度算法实验报告 多级反馈队列调度算法的实现-0323055826.docx-原创力文档...
