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-原创力文档...