prioritywork实验报告.docx
《prioritywork实验报告.docx》由会员分享，可在线阅读，更多相关《prioritywork实验报告.docx（23页珍藏版）》请在冰点文库上搜索。
prioritywork实验报告
实验报告——优先级作业调度系统的模拟
课程名称：
数据结构大型试验
实验项目名称：
优先级作业调度系统的模拟
学院：
计算机科学与技术学院
专业：
计算机科学与技术
指导教师：
黄伟
报告人：
徐云静学号：
201226100122班级：
计科1201班
实验时间：
2013下第8周—第16周
实验报告提交时间：
2013年1月13日前
目录
1.实验内容分析......................................3
1.1实验目的..................................................3
1.2实验要求...................................................3
1.3设计分析...................................................3
2.试验验证分析......................................10
2.1输入的形式及输入值的范围..................................10
2.2程序所能达到的结果........................................10
2.3测试数据..................................................11
3.测试分析..........................................12
3.1基础问题...................................................12
3.2技术问题...................................................13
4.调试结果分析......................................15
4.1程序的运行结果.............................................14
4.2边界数据以及极端数据的运行结果.............................16
5.附录..............................................18
一、实验内容分析：
实验目的：
设计优先级队列，实现优先级作业调度系统的模拟。
实验要求：
✧要求自己编程实现堆结构及其相关功能，从而实现优先级队列。
✧优先级队列要求完成主要的功能，包括作业的插入、最小优先级作业的提取和删除、各个作业优先级的修改等；；
✧要求源程序中有相应注释
✧要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确，包括何时作业进入，何时调度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等；
设计分析：
●类的设计
Program:
自定义的作业类。
MinAdt：
自定义的最小堆，用于实现优先级队列
minPQ：
自定义的优先级队列，帮助工程类的实现
Work：
模拟作业调度系统定义的工程类，模拟处理作业的过程。
类的关系图
MinAdt
（最小堆类）
Work
（工程类）
实现工具
数据类型
Program
（作业类）
实现工具
minPQ
（优先级队列类）
数据类型
✧基本数据结构类的设计：
a.堆MinAdt（最小堆）：
因为题目中的优先级是按照作业优先级数越小，优先级越高，所以设计最小堆即可用于实现优先级队列。
这里没有设计类模板，直接以Program（作业类为类型）
数据成员
MinAdt
vectorprograms
popHeap
pushHeap
adjustTop
size
top
empty
成员函数
makeHeap
⏹vectorprograms;//储存二叉树的向量
⏹voidadjustTop（intbegin,intlast）;//根的下调操作，将一个近似堆调整为堆（近似堆：
即除根节点外其他节点满足对结构）【以下代码是下调主要思路】
Ø{
Øif（begin>=0&&last>begin）//一个元素就不用调整了
Ø{
Ø......
Øwhile（ptr<=last）//ptrØ{
Øif（ptrprograms[ptr+1]）//调整ptr的值，使ptr表示左右节点中较小元素的下标。
Øptr=ptr+1;
Ø
Øif（programs[com]>programs[ptr]）//如果被调整元素比他的子节点元素大，则交换两个节点的值。
Ø{......}
Ø
Øelse//如果没有进行下调过程，则表示begin~last的元素满足堆结构，直接跳出函数。
Øreturn;}}}
⏹boolempty（）;//判断堆是否为空，即是否有元素存在
⏹intsize（）;//返回堆中元素的个数
⏹voidpushHeap（Program&pro）;//加入一个新的元素到堆中，调整为一个新的堆
Ø{
Øthis->programs.push_back（pro）;//将新节点加到堆中
Ø......//son表示需要作调整的节点的当前下标位置，father表示以此节点的根节点的当前下标位置
Øwhile（son>0&&!
（this->programs[son]>=this->programs[father]））////son=0,表示目标节点已经调整到根节点位置，跳出循环，或者子节点大于等于父节点的值
Ø{
Øif（!
（this->programs[son]>=this->programs[father]））//如果子节点的值小于父节点的值，则交换两个节点的内容
Ø{......}
Ø}
Ø}
⏹voidpopHeap（）;//删除根节点元素，并将二叉树调整为新堆
Ø{
Øintsize=programs.size（）;
Øthis->programs[0]=this->programs[size-1];//将最后一个元素提到头结点的位置，0~size-2除根节点以外满足堆结构
Øthis->adjustTop（0,size-2）;//将根节点调整到合适的位置，使0~size-2满足堆结构
Ø......//删除向量中最后一个元素
Ø}
⏹voidmakeHeap（）;//将一个储存完全二叉树的向量调整为储存最小堆的的向量
Ø{
Øif（programs.size（）!
=1&&programs.size（）!
=0）//先排除只有一个元素和空堆得情况
Ø{
Øfor（inti=programs.size（）/2-1;i>=0;i--）//从第一个不是叶节点的节点开始，从下往上依次做一次根节点下调过程
ØadjustTop（i,programs.size（）-1）;
Ø}
Ø}
b.minPQ（优先级队列）：
利用自定义的最小堆实现优先级队列，实现主要的功能，包括作业的插入、最小优先级作业的提取和删除、各个作业优先级的修改等，优先级队列中储存的数据类型为Program。
数据成员
MinAdtmi
minPQ
成员函数
changeRank
push
pop
top
size
empty
⏹minPQ（vectorpro）;//队列的构造函数
⏹voidpop（）;//删除队列中优先级最高的项,并重新排列队列
⏹voidpush（Program&pro）;//在队列中加入新项，并重新排列队列
⏹Programtop（）;//返回优先级最高的项
⏹boolempty（）;//判断队列知否为空
⏹intsize（）;//返回队列的中元素的个数
⏹voidchangeRank（）;//将队列中每一项的优先级减一
✧作业类以及工程类的设计
a.Program（作业类）：
Staticintsum
数据成员
Program
Intrank
成员函数
Intlength
operator>
operator>
operator=
intnumber
⏹staticintsum;//总的作业数
⏹intlength;//作业的长度
⏹intrank;//作业的等级
⏹intnumber;//作业标号
⏹Program（）;//无参构造函数，长度随机给定
⏹Program（intlen）;//有参构造函数，长度给定
⏹voidoperator=（constProgram&pro）;//复制赋值函数
⏹booloperator>（constProgram&pro）;//Program的大小比较既要考虑rank的大小，也要考虑number的大小
Ø{
Øif（this->rankØreturn1;
Øelseif（this->rank>pro.rank）
Øreturn0;
Øelse//如果优先级一样，则考虑作业的标号大小，实现优先级相同作业，先进先出
Øreturnthis->numberØ}
⏹booloperator<（constProgram&pro）;
b.Work（工程类）：
模拟优先级作业调度系统的运行的过程，并设计调试程序代码函数
inttime
数据成员
Work
minPQobjects
insertPro
showWork
startWork
⏹minPQobjects;//储存作业组的堆
⏹inttime;//工程运行的时间
⏹voidshowWork（）;//显示当前工程内所有作业的详细情况
⏹voidinsertPro（）;//随机产生1~3项新作业，并加入到工程中
Ø{
Øintnum=rand（）%3+1;//新加入的作业个数可能是1~3中任意数
Ø......//提示新作业即将显示
Øfor（intj=1;j<=num;j++）
Ø{
ØProgrampro;//随机产生一个作业
Øobjects.push（pro）;//这里sum多加了一份
Ø......//显示新作业信息
Ø}
Øthis->showWork（）;//将加入如新工程后的进程中的总项目展现出来
Ø}
⏹voidstartWork（）;
●程序流程的设计：
整个程序的流程其实是在Work类中的starkWork（）
✧startWork（）
先新建一个作业组（作为工程初始时系统内待处理的工作组）
NO
此作业处理完毕
每运行1s，工程内所有作业优先级减一
If（待处理工作数YES
保证加入新工作后工程不会超出超出容量
用sleep函数模拟处理过程
按20%的概率，在1S工程运行结束的间隙，向工程内加入1~3个新作业
YES
处理优先级最高的作业
If（工程内还有作业待处理）
作业处理完毕，关闭工程
将工作组加到工程中，等待处理。
。
。
⏹voidstartWork（）;//自动运作的工程
Ø{
Øintsum=rand（）%3+1;//sum表示工程刚开始运行时，工程内存在的作业数，sum随机产生，在1~3之间
Ø
Øfor（inti=0;iØ{
ØProgramcurr;
Øthis->objects.push（curr）;
Ø}
Ø
ØProgramcurr=objects.top（）;//curr优先级最高的作业副本
Øwhile（!
objects.empty（））//作业还未处理完
Ø{
Ø......
Øobjects.pop（）;
Ø
Øfor（intt=curr.length;t>0;t--）
Ø{
ØSleep（1000）;//处理每单位长度的作业，系统停止运行1000ms，模拟处理过程
Øtime++;//工程运行时间+1
Ø
Øthis->objects.changeRank（）;//将工程中所有作业的优先级都减一
Øif（this->objects.size（）<=MAX_SIZE&&rand（）%5==0）//在队列中的作业组元素不超过MAX_SIZE的前提下，按20%的几率向工作组中加入新工作
Øthis->insertPro（）;
Ø}
Ø......;
Øcurr=objects.top（）;
Ø}
Ø......
Ø}
二、实验验证分析
✧输入的形式和输入值的范围：
1.输入形式及输入值得范围：
1 输入一组数据，作为初始作业组的长度，并输入-1表示输入结束
2 输入的作业不得超过10个
3 每个作业的长度范围：
0<=length<=4
输出样本
2.输出形式：
模拟系统运行过程，详细显示运行过程中系统内各个作业的信息，以及新加入作业组的信息，加入新作业后系统内作业组的信息。
每个作业运行结束，显示当前作业运行总时间，等待时间，和实际运行时间。
部分输出样本：
✧程序所能达到的结果：
能使模拟系统根据作业的优先级大小顺序处理作业，原始优先级只与作业的长度相关，但运行过程的优先级要根据系统运行的时间发生改变，以实现先入先出的原则。
运行过程中，系统会随机产生作业组加到系统中，系统将新的工作组按照优先级大小进行排序。
系统能随时提取出，当前正在处理的作业的详细信息，以及系统内正在等待处理的作业组的信息。
✧测试数据：
1．正确输入：
输入：
123-1
输出
2．错误输入
错误一：
输入作业数超过系统容量，及作业数>10
输入：
1111111111-1
输出：
错误二：
作业长度不合理，及length<0或length>4
输入：
5,3，-1
输出
3、调试分析
✧基础问题
1.静态数据类型的使用：
Program:
:
sum的初始化
解决:
静态数据类型要在class外实现，且要放在cpp文件上声明。
2.vector的运用：
1 end（）的误用
解决：
End（）返回的向量中最后一个元素后面位置的指针
2 earse（）函数的调用
解决：
函数括号内是指针值，不是元素值
3.rand（）的用法
a+rand（）%n
其中的a是起始值，n是整数的范围。
若要0~1的小数，则可以先取得0~10的整数，其它情况依此类推。
通常rand（）产生的随机数在每次运行的时候都是与上一次相同的，这是有意这样设计的，是为了便于程序的调试。
4.sleep（）的用法
1 Sleep函数//S要大写
2 头文件#include
3 函数调用形式Sleep（5000）;//单位是毫秒
✧技术问题
1.作业关系大小的设计
错误理解：
以为只要比较作业的优先级就可以了，这样设计无法实现先进先出的原则
解决：
设计作业大小比较时，优先考虑作业的优先级，如果优先级一样的话，再根据作业的number值比较大小（即进入系统的先后顺序）
2.Sum值变化的异样
错误情况：
sum值的多加现象，会直接导致作业number值不正确，使作业运行顺序出现错误。
错误原因及解决方案：
1.每次工程结束之后没有没有将sum至0，导致第二次启动系统时，作业的number出现问题
解决：
只要在StartWork（）函数最后将sum归0就好
2.在调用voidminPQ:
:
push（Program&pro），sum会加两次
voidminPQ:
:
push（Program&pro）
{
mi.pushHeap（pro）;
//Program:
:
sum--;//如果不把多加的sum减掉
}
错误导致（新加入的作业的number是错的）
解决：
加上Program:
:
sum--
正确运行结果
3.最小堆adjustTop（）函数的设计
难点：
1 下标值以及number值得相互转化：
下标值与number相差一，所以在计算父节点的下标值时要考虑清楚
2 调整节点条件的分析
当二叉树只有一个节点时，不需要进行下调工作
因为进行下调操作的是一个近似堆，只要被调整元素比它的两个子节点多小，就可以直接跳出循环
节点比较不需要考虑相等的情况，因为每个作业的number值一定是不一样的，所以就算rank一样，也一定不会相等
4、测试结果分析：
✧程序的运行结果
加入新作业组后，系统内的所有作业情况。
这里显示的顺序貌似有问题，其实是因为，打印顺序是按照储存二叉树的向量的下标顺序打印的，是满足最小堆的顺序的。
显示神额时候有新作业组加入，以及作业组的信息，注意新作业的number值是跟着之前的nnmber值得。
显示什么时间开始运行哪个作业
已经根据优先级进行排序了
正确输入：
作业长度在合理范围内，作业数不超过容量
每个作业运行完成之后，会显示此作业在什么时候处理完毕，在系统总共消耗的时间，以及等待的时间。
作业长度
作业编号
满足先入先出原则
1
2
3
3
4
4
3
2
1
5
4
6
运行顺序
✧边界数据、或极端数据测试
1 调试优先队列是否满足先进先出原则
Programp1[10]={1,1,1,1,1,1,1,1,1,1};vectortest1（p1,p1+10）;
Worktest11（test1）;
test11.StartWork（）;
运行结果
1
2
3
4
5
6
7
8
9
10
1
1
1
1
1
1
1
1
1
1
作业长度
运行顺序
作业编号
由结果易知，验证正确
2 调试工程是否按照优先级队列运行工程
Programp2[5]={4,4,3,2,1};//调试工程是否按照优先级队列运行工程
vectortest2（p2,p2+5）;
Worktest22（test2）;
test22.StartWork（）;
运行顺序
作业编号
作业长度
5
4
3
1
2
1
2
3
4
4
由结果易知，验证正确
5、附录
在“priority_work”文件夹中
✧Priority_work.h
✧Prority_work.cpp
✧Main_cpp
升级会员 