操作系统：进程调度.docx

计科112 康岩岩 2011008142202013/4/29操作系统实验报告实验三: 进程调度实验三: 进程调度一、 实验目的加深理解并模拟实现进程（作业）调度算法。1）熟悉常用的进程调度算法，如FCFS、SPF、FPF、高响应比优先、时间片轮转；2）结合所学的数据结构及编程知识，选择一种进程调度算法予以实现。二、 实验属性该实验为设计性实验。三、 实验仪器设备及器材普通PC386以上微机四、 实验要求本实验要求2学时完成。本实验要求完成如下任务：1） 编程实现单处理机系统中的进程调度，要求从FCFS、SPF、FPF、高响应比优先、时间片轮转算法中至少选择三个；2） 最后编写主函数对所做工作进行测试。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。五、 实验步骤(一) 任务分析：本次试验要求利用程序实现操作系统的进程调度算法，只是进行简单的模拟，并不涉及真正的进程创建、通信等操作。对于每一个进程，可以用 一个数据对象PCB进行表示，它包含了进程名称、开始时间、运行时间等所有有关该进程的数据。在模拟程序中，需要用到一个链表来储存所有进程，然后再此链表的基础上进行各种调度算法。为了便于直观表示程序运行（即执行算法）的结果，还需把链表中的数据呈现到界面上，当然在此试验中，界面不是主要的一部分。(二) 程序设计：a. 总体设计：本次试验所用语言依然为java. 对单个进程用类PCB表示，它的定义如下：public class PCB public PCB() private String name; /进程名 private int arriveTime = 0; /到达时间 private int needServerTime = 0; /需要服务的时间 private int pcbLeve = 0; /线程优先级 private int startTime = 0; /开始执行时间 private int doneTime = 0;/已经完成的量，仅仅在时间片轮转中使用 private int finishTime = 0; /结束时间 private int zouzhuanTime = 0; /周转时间 private float weightZzTime = 0; /带权周转时间 /以下为大量的 getXxx/setXxx 函数在此省略 对于进程对象，可以在程序运行过程中随时创建，创建的进程对于其创建时间有一个强制设定，就是其到达时间一定大于上一个个创建的进程的到达时间。 创建好的进程会加入一个全局的链表中。在执行算法时，需要将此链表作为参数传给实现算法的函数。函数执行完毕后，会将处理后的链表返回。此后可以在主界面上显示返回的数据结果。b. 具体实现： 本次试验共实现了四个进程调度算法，分别是： FCFS、SPF、FPF以及时间片轮转算法。其中，SPF与FPF算法几乎代码完全相同，此后会只介绍其中一个算法。 FCFS先来先服务算法：FCFS算法只需要对进程链表进行遍历即可，遍历的前提是进程链表内的进程一定是按照进程到达顺序排列的，在遍历过程总需要记录缓存进程结束的时间，以便给下个进程进行比较。比较原则如下：如果某个进程的到达时间大于上个进程的结束时间，即这个进程在上个进程完成后才到达，则这个进程的开始时间为其自身到达时间。否者其开始时间为上个进程的结束时间。具体实现代码如下：/* * 先来先服务算法 * * return */public List doFCFS() /用于存放计算后的数据的链表List returnList = new ArrayList();PCB temp = new PCB();/遍历进程链表，此时的链表一定是进程按到达时间顺序排列的，这在构造函数中已经确定for (PCB pbc : PcbList) /到达，开始，结束均为时间点 /服务时间，周转时间均为时间段/如果到达时间小于上次任务结束时间，这开始时间为上次任务结束的时间,或者为其到达时间，即到达后就开始if (pbc.getArriveTime() temp.getFinishTime() pbc.setStartTime(temp.getFinishTime(); else pbc.setStartTime(pbc.getArriveTime();/设置结束时间pbc.setFinishTime(pbc.getStartTime() + pbc.getNeedServerTime();/设置周转时间pbc.setZouzhuanTime(pbc.getFinishTime() - pbc.getArriveTime();/设置带权周转时间float wt = (float) pbc.getZouzhuanTime() / (float) pbc.getNeedServerTime();pbc.setWeightZzTime(wt);/加入列表returnList.add(pbc);temp = pbc;return returnList;SPF短作业优先调度算法： 在算法执行过程中，需要动态的从总链表中提取数据，数据提取到缓存链表 （List ）returnList 中，提取方法如下：先从链表头得到一个进程，并在链表中找到比表头进程作业时间更短并且到达时间在上个进程执行完毕之前的进程。这样的进程也可能找不到，找不到的话只能用表头进程。之后修改进程数据，再从总链表中删除现在找到的进程。这样就可以实现优先使用段作业进程并且不浪费时间。具体代码如下：/* * 短作业优先调度算法 * * return */public List doSPF() /用于存放计算后的数据的链表List returnList = new ArrayList();PCB temp_pcb = new PCB();/这个循环用于在 PcbList 中一次找出 作业时间短且能够在上个进程完成之前到达的进程while (this.PcbList.size() 0) int i = 0;int temp_index = i;PCB pcb = PcbList.get(i); /得到现有的第一个进程/得到最短,并且能在上次作业完成之前到达的作业/当然，这里有也可能找不到符合这种条件的for (PCB pp : PcbList) if (pp.getNeedServerTime() pcb.getNeedServerTime() & (pp.getArriveTime() = temp_pcb.getFinishTime() pcb = pp;temp_index = i;/记录下标i+;/如果到达时间小于上次任务结束时间，则其开始时间为上次任务结束的时间, 不然为其到达时间，即到达后就开始执行if (pcb.getArriveTime() temp_pcb.getFinishTime() pcb.setStartTime(temp_pcb.getFinishTime(); else pcb.setStartTime(pcb.getArriveTime();/设置结束时间pcb.setFinishTime(pcb.getStartTime() + pcb.getNeedServerTime();/设置周转时间pcb.setZouzhuanTime(pcb.getFinishTime() - pcb.getArriveTime();/设置带权周转时间float wt = (float) pcb.getZouzhuanTime() / (float) pcb.getNeedServerTime();pcb.setWeightZzTime(wt);temp_pcb = pcb;returnList.add(pcb);PcbList.remove(temp_index);return returnList;时间片轮转算法：所谓时间片轮转，就是在以某个时间片长度轮流执行进程。在某个时间片内，某个进程可能会执行完毕，这样就需要把这个时间片内没用完的时间分给下一个要执行的进程。另外在某个时间片内还会有新的进程加入链表进程队列，这也需要及时的分时间片给这个进程。 分时执行进程显然是一个循环，循环的中止条件是所有的进程都执行完毕。这里需要用一个链表 （List ）returnList 储存当前可执行进程，还需要一个整型变量 gobleTime 来储存当前所有进程已经执行的时间。每次从缓存链表表头提取进程，提取后修改其执行时间，并判断它是否可在当前时间片内完成，执行后在把它加入缓存链表尾部，在这之前还要添加上当前时间下进入的新进程。具体算法如下：/* * 时间片轮转算法 * * param timePiece 时间片长度 * return */public List doTimePiece(int timePiece) /每个时间片下，当进程执行后，这个时间都会随进程执行情况增加，它的初始值为第一个进程的到达时间int gobleTime = PcbList.get(0).getArriveTime();/得到所有进程运行完毕所需的总时间int countTime = getTimeCount(PcbList);System.out.println(总时间： + countTime);List returnList = new ArrayList();returnList.add(PcbList.get(0);/循环条件为 现在进程推进的时间小于总需要的时间while (gobleTime countTime) System.out.println(gobleTime);if (returnList.size() = pbc.getNeedServerTime() returnList.add(pbc);continue;int nextDone = pbc.getDoneTime() + timePiece;/如果已经完成的时间加上时间片后大于或等于线程实际所需时间,即这个线程可以在这个时间片内完成，/则在此设置其结束时间，同时全局运行时间也需要往前推进if (nextDone = pbc.getNeedServerTime() int lastDone = pbc.getNeedServerTime() - pbc.getDoneTime();gobleTime += lastDone;/设置已完成时间pbc.setDoneTime(pbc.getNeedServerTime();/设置结束时间pbc.setFinishTime(gobleTime);/设置周转时间pbc.setZouzhuanTime(pbc.getFinishTime() - pbc.getArriveTime();/设置带权周转时间float wt = (float) pbc.getZouzhuanTime() / (float) pbc.getNeedServerTime();pbc.setWeightZzTime(wt);System.out.println(pbc.getName() + 完成: + gobleTime); else /增加其完成的时间pbc.setDoneTime(nextDone);gobleTime += timePiece; /推进时间System.out.println(pbc.getName() + 运行: + gobleTime);/因为时间片可能已经向前推进，在这个过程中可能有新的进程到达，/所以需要找出它，并把它加入当前链表PCB get = getNextPcb(gobleTime, returnList.size() + 1);System.out.println(现在大小： + (returnList.size() + 1);if (get != null) System.out.println(添加 + get.getName();returnList.add(get);/将现在运行的进程添加到链表尾部returnList.add(pbc);return PcbList;其中有一个getTimeCount（）方法，用它是用来获得进程链表所有进程执行完毕一共需要的时间。它的实现方法如下：/* * 计算所有进行按顺序执行需要耗费的总时间 * * param list * return */ private int getTimeCount(List list) int count = 0; for (PCB p : list) if (p.getArriveTime() count) count = p.getArriveTime() + p.getNeedServerTime(); else count += p.getNeedServerTime(); return count; 还有一个方法为getNextPcb（），它用来查找当前时间下需要进入缓存链表的进程,如下：/* * 找到在时间点 golbTime 之前到达的进程 * param golbTime 当前时间点 * param now 已经获取的进程数目 * return */ private PCB getNextPcb(int golbTime, int now) int i = now; int size = PcbList.size(); /以 now 为起始位置找进程 while (i size) PCB p = PcbList.get(i); if (p.getArriveTime() = golbTime) return p; i+; return null; (三) 程序结果：1-主界面2-创建进程3-算法选择4-FCFS算法结果5-SPF算法6-时间片轮转算法(p=1)7-时间片轮转算法(p=4)(四) 实验总结完成以上四个（实际上是三个）算发，现在觉得很简单，但之前也走了不少弯路，我开始的思路是真正的去开启一些线程，然后再去实现所要求的各种调度。当然，写了好久也没写出来，代码甚至都没有调试运行过，最后意识到这是单纯的写算法，才算从弯路中走出来。代码虽然都实现了，但是现在还是只是在理论基础上了解了这些算法，真正运用到在哪里，现在还没有那个概念。希望能有机会继续深入学习下去六、 附录由于本次实现带有界面，与实验目的无关的代码较多，下面精简附录：文件 PCB.javapublic PCB() private String name; /进程名 private int arriveTime = 0; /到达时间 private int needServerTime = 0; /需要服务的时间 private int pcbLeve = 0; /线程优先级 private int startTime = 0; /开始执行时间 private int doneTime = 0;/已经完成的量，仅仅在时间片轮转中使用 private int finishTime = 0; /结束时间 private int zouzhuanTime = 0; /周转时间 private float weightZzTime = 0; /带权周转时间 .n多getXxx与setXxxfeng方法，此处省500字。 文件ProcessManager.java 实现进程调度算法主类public class ProcessManager List PcbList = null; public ProcessManager(List list) /将进程的非基本数据置零，因为传入的链表可能被其他方法修改过这些数值 for (PCB p : list) p.setDoneTime(0); p.setStartTime(0); p.setFinishTime(0); p.setZouzhuanTime(0); p.setWeightZzTime(0); PcbList = new ArrayList(list); sortPcbList(); /* * 将链表按照进程到达时间顺序进行排序 */ private void sortPcbList() /用于存放计算后的数据的链表 List returnList = new ArrayList(); while (this.PcbList.size() 0) int i = 0; int temp_index = i; PCB p = PcbList.get(temp_index); for (PCB pp : PcbList) if (pp.getArriveTime() p.getArriveTime() p = pp; temp_index = i; i+; returnList.add(p); PcbList.remove(temp_index); PcbList = new ArrayList(returnList); /* * 先来先服务算法 * * return */ public List doFCFS() /用于存放计算后的数据的链表 List returnList = new ArrayList(); PCB temp = new PCB(); /遍历进程链表，此时的链表一定是进程按到达时间顺序排列的，这在构造函数中已经确定 for (PCB pbc : PcbList) /到达，开始，结束均为时间点 /服务时间，周转时间均为时间段 /如果到达时间小于上次任务结束时间，这开始时间为上次任务结束的时间,或者为其到达时间，即到达后就开始 if (pbc.getArriveTime() temp.getFinishTime() pbc.setStartTime(temp.getFinishTime(); else pbc.setStartTime(pbc.getArriveTime(); /设置结束时间 pbc.setFinishTime(pbc.getStartTime() + pbc.getNeedServerTime(); /设置周转时间 pbc.setZouzhuanTime(pbc.getFinishTime() - pbc.getArriveTime(); /设置带权周转时间 float wt = (float) pbc.getZouzhuanTime() / (float) pbc.getNeedServerTime(); pbc.setWeightZzTime(wt); /加入列表 returnList.add(pbc); temp = pbc; return returnList; /* * 短作业优先调度算法 * * return */ public List doSPF() /用于存放计算后的数据的链表 List returnList = new ArrayList(); PCB temp_pcb = new PCB(); /这个循环用于在 PcbList 中一次找出 作业时间短且能够在上个进程完成之前到达的进程 while (this.PcbList.size() 0) int i = 0; int temp_index = i; PCB pcb = PcbList.get(i); /得到现有的第一个进程 /得到最短,并且能在上次作业完成之前到达的作业 /当然，这里有也可能找不到符合这种条件的 for (PCB pp : PcbList) if (pp.getNeedServerTime() pcb.getNeedServerTime() & (pp.getArriveTime() = temp_pcb.getFinishTime() pcb = pp; temp_index = i;/记录下标 i+; /如果到达时间小于上次任务结束时间，则其开始时间为上次任务结束的时间, 不然为其到达时间，即到达后就开始执行 if (pcb.getArriveTime() temp_pcb.getFinishTime() pcb.setStartTime(temp_pcb.getFinishTime(); else pcb.setStartTime(pcb.getArriveTime(); /设置结束时间 pcb.setFinishTime(pcb.getStartTime() + pcb.getNeedServerTime(); /设置周转时间 pcb.setZouzhuanTime(pcb.getFinishTime() - pcb.getArriveTime(); /设置带权周转时间 float wt = (float) pcb.getZouzhuanTime() / (float) pcb.getNeedServerTime(); pcb.setWeightZzTime(wt); temp_pcb = pcb; returnList.add(pcb); PcbList.remove(temp_index); return returnList; /* * 高优先权优先调度算法，这个算法今本同短作业优先调度算法相同 * 只是其中一项比较变成了比较 优先级 * return */ public List doFPF() /用于存放计算后的数据的链表 List returnList = new ArrayList(); PCB temp_pcb = new PCB(); /这个循环用于在 PcbList while (this.PcbList.size() 0) int i = 0; int temp_index = i; PCB pcb = PcbList.get(i); /得到优先级高,并且能在上次作业完成之前到达的作业 for (PCB pp : PcbList) if (pp.getPcbLeve() pcb.getPcbLeve() & (pp.getArriveTime() = temp_pcb.getFinishTime() pcb = pp; temp_index = i;/记录下标 i+; /如果到达时间小于上次任务结束时间，则其开始时间为上次任务结束的时间, 不然为其到达时间，即到达后就开始 if (pcb.getArriveTime() temp_pcb.getFinishTime() pcb.setStartTime(temp_pcb.getFinishTime(); else pcb.setStartTime(pcb.getArriveTime(); /设置结束时间 pcb.setFinishTime(pcb.getStartTime() + pcb.getNeedServerTime(); /设置周转时间 pcb.setZouzhuanTime(pcb.getFinishTime() - pcb.getArriveTime(); /设置带权周转时间 float wt = (float) pcb.getZouzhuanTime() / (float) pcb.getNeedServerTime(); pcb.setWeightZzTime(wt); temp_pcb = pcb; returnList.add(pcb); PcbList.remove(temp_index); return returnList; /* * 时间片轮转算法 * * param timePiece 时间片长度 * return */ public List doTimePiece(int timePiece) /每个时间片下，当进程执行后，这个时间都会随进程执行情况增加，它的初始值为第一个进程的到达时间 int gobleTime = PcbList.get(0).getArriveTime(); /得到所有进程运行完毕所需的总时间 int countTime = getTimeCount(PcbList); System.out.println(总时间： + countTime); List returnList = new ArrayList(); returnList.add(PcbList.get(0); /循环条件为 现在进程推进的时间小于总需要的时间 while (gobleTime countTime) System.out.println(gobleTime); if (returnList.size() = pbc.getNeedServerTime() returnList.add(pbc); continue; int nextDone = pbc.getDoneTime() + timePiece; /如果已经完成的时间加上时间片后大于或等于线程实际所需时间,即这个线程可以在这个时间片内完成， /则在此设置其结束时间，同时全局运行时间也需要往前推进 if (nextDone = pbc.getNeedServerTime() int lastDone = pbc.getNeedServerTime() - pbc.getDoneTime(); gobleTime += lastDone; /设置已完成时间 pbc.setDoneTime(pbc.getNeedServerTime(); /设置结束时间 pbc.setFinishTime(gobleTime); /设置周转时间 pbc.setZouzhuanTime(pbc.getFin