1 合格 王兴荣 毕业设计 认真

| You have to believe, there is a way. The ancients said:" the kingdom of heaven is trying to enter". Only when the reluctant step by step to go to it s time, must be managed to get one step down, only have struggled to achieve it. - Guo Ge Tech操作系统仿真实验实验报告报告日期：2011-4-26一 实验目的 采用仿真实验的方法，分析在FCFS SJF RR MLFS算法中，系列因素对平均周转时间的影响场景布置：长短作业不同比例 ；作业不同达到顺序；作业不同到达频率。二 实验原理及方法分析四种调度算法实现原理及方法：（一）基本定义及说明1.定义进程的四个状态：#define ProcessCreate 0 /创建#define ProcessReady 1 /就绪#define ProcessRun 2 /执行#define ProcessWait 3 /等待#define ProcessDestory 4 /结束2.用结构体来表示调度的每一个进程，每个进程的属性有名称（即标识符）、所处状态、到达时间、执行时间、等待时间、周转时间。typedef struct pcbint pid; /进程标识符int state; /进程所处状态int burst_time; /进程执行时间int come_time; /进程到达时间int wait_time; /等待时间int turnaround_time; /周转时间PCB;PCB pcb_running;3.定义用来存放不同进程的容器：vector<PCB> pcb_queue; /全部进程vector<PCB> pcb_finished; /执行完的进程vector<PCB> level0; /处于0级的进程vector<PCB> level1; /处于1级的进程vector<PCB> level2; /处于2级的进程4.定义基本的变量：int algorithm;/0:FCFS 1:SJF 2:RR 3:MLFSint current;/当前进程下标int currenttime;/当前时间int preemptive; /是否可抢占int slice; /时间片int current_level; /当前所处级5. 用函数input()接受输入信息，变量num存放进程数，输入的信息依次有进程数目、每个进程的到达时间、每个进程的运行时间。void input() /确定进程个数，选择算法及是否抢占int i,num; /num代表进程个数ifstream inf;inf.open("0.txt"); /打开文件inf>>num; /输入进程个数for(i=0;i<num;i+)PCB temp; /创建一个进程ZeroMemory( &temp, sizeof(PCB) );/保证该开放区域所要填充的数据都将是应用程序所填充的数据而不是系统的随机数据inf>>temp.come_time; /输入到达时间inf>>temp.burst_time; /输入执行时间temp.pid = i; /进程标记pcb_queue.push_back(temp);/把一个temp存入到vector中cout<<"choose a algorithm:"<<endl<<endl;cout<<"Enter 0 choose FCFS"<<endl;cout<<"Enter 1 choose SJF"<<endl;cout<<"Enter 2 choose RR"<<endl;cout<<"Enter 3 choose MLFS"<<endl;cin>>algorithm; /选择算法cout<<"choose nonpreemptive(0) or preemptive(1) :"<<endl;cin>>preemptive; /选择是否抢占（二）四种调度算法1.FCFS先来先服务的情况，按照进程的到达时间将进程排序case 0: /FCFSif (itr->state = ProcessReady && itr->come_time < pcb_queuecurrent.come_time )/新进程处于就绪状态，且到达时间小于当前进程current = count;break;2.SJF按进程还需要执行的最短时间排序case 1: /SJFif (itr->state = ProcessReady && itr->burst_time < pcb_queuecurrent.burst_time )/新进程处于就绪状态，且执行时间小于当前进程current = count;break;3.RRif (algorithm=2)count = current;current+;int length = pcb_queue.size();current = current%length;while (pcb_queuecurrent.state != ProcessReady )current+;current = current%length;pcb_queuecurrent.state = ProcessRun;return;4MLFS算法中公共设置队列数为3.分别为，进程的level属性可能有0、1、2三个值。值为0的quantum为q0=1，且该队列拥有最高的优先级。值为1的quantum为q1=2，且该队列的优先级仅次于值为0的对列，只有level0队列里空了才能执行该队列，值为2的队列按照FCFS算法调度执行，且优先级最低，只有当level0和level1两个队列空了，才能执行该队列。初始时将所有进程的level属性值均置为-1。仍是按照进程的到达时间将进程排序（同FCFS）详细代码见源程序三、实验测试结果（一）、按长度按作业不同比例观察图表可以看出，随着短作业比例的增加，各算法的平均等待时间和平均周转时间都在减小；其中减小速率最快的RR，其次MLFS，最后是FCFS和SJF；垂直于轴划线看焦点，可以发现， FCFS和SJF更适合短作业比例小的作业，且比例越小优势越明显。MLFS其次，则最不合适。在这里FCFS和SJF之所以会重合，是因为我我再改变短作业比例时是一次将第一个、第二个改为短作业的。而FCFS遵循先来先服务的原则，SJF算法让短作业先做，所以他们执行的顺序是一样的。并不是一定会重合。（二）、按作业到达时间不同这个讨论的是作业不同到达时间，我取的数据是9个需要10个单位的作业和1个需要1个单位的作业。观察图标可以发现作业的不同到达顺序对SJF、RR、MLFS算法的平均等待时间和平均运转时间影响不大，而对FCFS算法的影响。这主要是因为FCFS遵循先来先服务的原则。（三）、按作业不同到达频率四、分析与评价在一般情况下，平均周转时间最短的是SJF算法。FCFS: 这是最简单的一个算法，只遵循先来先服务的原则，但是一般平均周转时间会较长。SJF：该算法让短作业先做，平均周转时间较短。但是缺点是容易产生饥饿，长作业可能一直无法得到CPU。RR：该算法的优点是可以及时给用户反馈，且quantum的选择是关键的，如果太短，则要不断的进行上下文切换，平均周转时间变大，如果太长，就和FCFS差不多，体现不出优势。MLFS:多级反馈算法有效地防止饥饿，让等待时间长的作业的优先级不断上升，终究会使其得到CPU。五、实验心得通过该实验，让我充分地理解了各个算法的同时，还经过比较知道了各个算法的优劣，将理论付诸实践使得理解更加深刻。在编程的过程中也遇到了很多问题但是通过思考请教都能解决。实验中仍然存在着不足，如输入是靠用户一个个输入的，这样当进程数很多的时候就十分繁琐，可以将其用文件导入。且在定义数据结构的时候使用的 固定程度的数组存放process 结构体的，当进程数超过了数组大小的时候就无法运行了，最好是利用链表。希望有机会加以改进。