《操作系统》课程设计报告.doc

课 程 设 计 课程名称 操作系统 题目名称 进程调度 学生学院 计算机学院 专业班级 09级计科 班 学 号 学生姓名 指导教师 林穗 2013 年 1 月 10 日 操作系统 课程设计任务书学生姓名刘婧专业班级09级计科6班学号3209006162题 目进程调度指导教师林穗题目编号2012秋-06主要内容本课程设计要求编程进程调度的四个算法。通过具体的进程调度算法的实现，加深对进程调度算法实现过程的理解。任务要求进程调度是低级调度，它的主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。1. 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间。进程到达时间服务时间A03B26C44D65E822. 分别实现按照先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）以及时间片轮转（RR、时间片=1）调度算法进行CPU调度。 3. 分别在不同算法控制下运行设计的程序，给出各进程的完成时间、周转时间、带权周转时间和平均带权周转时间。（计算到小数点后两位）4. 选用程序设计语言：C、C等。参考文献1 计算机操作系统， 汤小丹等 ，西安电子科技大学出版社2 操作系统实验指导书，傅秀芬，广东工业大学（自编）3 计算机操作系统教程 ( 第二版 )， 张尧学、 史美林，清华大学出版社4 现代操作系统，A.S.Tanenbaum 著，陈向群等译机械工业出版社审查意见指导教师签字：系主任签字： 年 月 日 说明：本表由指导教师填写，由系主任审核后下达给选题学生，装订在设计（论文）首页大纲1、 主要内容-42、 任务要求-43、 设计思想说明-44、 数据结构的说明-55、 各主要模块的算法流程图 -66、 程序运行情况-107、 使用说明书-158、 体会，建议-159、 参考文献-161、 主要内容本课程设计要求编程进程调度的四个算法。通过具体的进程调度算法的实现，加深对进程调度算法实现过程的理解。2、 任务要求进程调度是低级调度，它的主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。1 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间。进程到达时间服务时间A03B26C44D65E822 分别实现按照先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）以及时间片轮转（RR、时间片=1）调度算法进行CPU调度。 3 分别在不同算法控制下运行设计的程序，给出各进程的完成时间、周转时间、带权周转时间和平均带权周转时间。（计算到小数点后两位）4 选用程序设计语言：C、C等。3、 设计思想说明进程调度的思想：（1）当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁1（就绪运行）。（2）在运行进程（包括闲逛进程）的过程中，可能发生变迁2（运行阻塞），即将运行进程插入到阻塞队列（闲逛进程不能被阻塞），可能有其他新的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞就绪），即从阻塞队列中移出并插入就绪队列中。（3）时间片运行结束后，若进程累计占用CPU时间大于等于进程需要运行的时间，则进程执行结束，释放其PCB。若进程累计占用CPU时间小于进程需要运行时间，发生变迁4（运行就绪），即将当前运行的进程插入就绪队列中。五个算法：先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）以及时间片轮转（RR、时间片=1）调度算法。1. 先来先服务（FCFS）先来先服务是最简单的调度算法，按先后顺序进行调度。比较有利于长作业，而不利于短作业。因为长作业会长时间占据处理机。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。 2. 非抢占的短进程优先（SPF）对预计执行时间短的进程优先分派处理机；优点：比FCFS改善平均周转时间和平均带权周转时间、缩短进程的等待时间、提高系统的吞吐量；缺点：对长进程非常不利，可能长时间得不到执行、未能依据进程的紧迫程度来划分执行的优先级、难以准确估计进程的执行时间，从而影响调度性能。3. 抢占的短进程优先（SPF）按进程的预计运行时间长短进行排序，先执行短进程。若内存中运行的进程优先级比就绪队列中的某进程优先级低（即运行的进程预计运行时间比就绪队列中的某进程长），此运行的进程让出内存并进入就绪队列，优先级更高的短进程强占内存资源并运行直到结束或者遇到优先级更高的进程强占为止。4. 高响应比优先（HRRN）最高响应比优先法是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。5. 时间片轮转（RR、时间片=1）所有就绪进程按 FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。如果运行进程用完它的时间片后还为完成，就把它送回到就绪队列的末尾，把处理机重新分配给队首的进程。直至所有的进程运行完毕4、 数据结构的说明进程控制块PCB struct PCBstring name;/进程名int ta;/进程到达时间int ts;/进程估计运行的时间int tb;/进程开始运行时间int tm;/进程仍需运行的时间int to;/进程完成的时间int rn;/进程运行的次数int totalTime;/周转时间double weightTotalTime;/带权周转时间(周转时间/估计运行时间）PCB *next;/定义指向下一个进程的指针;5、 各主要模块的算法流程图1. 先来先服务（FCFS）图6.1.1 main()函数 流程图 图6.1.2 sort()函数 流程图 2. 抢占的短进程优先（SPF）结束SF函数调用调用SF算法是PQueue队列是空？模拟当前进程运行结束，对总周转时间，总带权周转时间，以及运行结束时间点（end_time）赋值。并把进程信息插入Queue队列，且删除其在vector中的进程信息否取PQueue队列第一个元素，即到达时间最早的进程进行模拟运行，并计算出不被强占情况下的结束时间点（atime）取下一个运行进程的信息在atime之前是否有进程到达？是PQueue队列为空？Vector是否为空？否是否否是计算出当前系统时间点，并对运行中的进程进行的预计运行时间进行设置（此处以未标志bvisited时的end_time表示）。并将此进程和所有其他新到达进程都插入vector之中进行排序（排序按预计运行时间短在前长居后），删除新到达的进程在PQeuee队列中的信息取PQueue队列的队首元素取vector第一个元素模拟运行取出vector中的第一个元素进入模拟运行状态。计算出此进程不被强占情况下的结束时间点（atime）3. 高响应比优先（HRRN）4. 时间片轮转（RR、时间片=1）开始初始化PCB,输入进程信息就绪队列空？ 把进程的状态设为W,在把进程插入队尾时间片到，运行进程已占用CPU时间+1运行进程已占用CPU时间已达到所需的运行时间结束就绪队列首进程投入运行进程完成，撤销该进程是否已到达未到达6、 程序运行情况；1测试用例：进程到达时间服务时间A03B26C44D65E822用例分析：算法作业（进程）名ABCDE平均到达时间02468服务时间36452FCFS完成时间39131820-周转时间37912128.6带权周转时间11.172.252.462.56执行顺序A - B - C - D - E SPF -Nonpreemptive完成时间39152011-周转时间37111437.6带权周转时间11.172.752.81.52.14执行顺序A - B - E - C - DSPF -preemptive完成时间32081510-周转时间3184927.2带权周转时间1311.811.56执行顺序A - C - E - B - DHRRN完成时间39132015-周转时间3791478带权周转时间11.172.252.83.52.14执行顺序A - B - C - E - D RRq=1完成时间419142016-周转时间4171014810.6带权周转时间1.332.832.52.842.69执行顺序A - C - E - B - D3 对于HRRN算法中，优先数的计算当前执行完成时间ABCDE结果-1未到达未到达未到达未到达AA3已完成1.17未到达未到达未到达BB9已完成已完成2.251.61.5CC13已完成已完成已完成2.43.5EE15已完成已完成已完成2.8已完成DD20已完成已完成已完成已完成已完成4 运行结果截图1. 先来先服务（FCFS）2. 非抢占的短进程优先（SPF）3. 抢占的短进程优先（SPF）4. 高响应比优先（HRRN）5. 时间片轮转（RR、时间片=1）7、 使用说明书（如何登录、退出、读、写、等操作说明）1. “先来先服务” 和“非抢占的短进程优先”可执行程序分别为FCFS.exe和SPF.exe，用C语言编写。2. “抢占的短进程优先”和“时间片轮转”可执行程序分别为SPF.exe 和RR.exe，用C+语言编写。时间片轮转的时间片取1。对于每一个进程，依次输入进程的信息，进程名字、到达时间、所需服务时间。如下图：3. “高响应比优先”可执行程序为HRRN.exe，用C语言编写。可支持文件输入。系统询问“adopts the file way to input the datas.y/n: ”选择“y”文件“input.txt”为已写好的测试用例。8、 体会，建议通过这次课程设计，加深对处理机进程调度机制的理解，对进程的概念有了更深一层次的认识。通过实现不同调度算法来实现调度进程，比较了不同调度算法的优缺点，掌握进程状态转换过程和处理机调度策略的实现。在编程中我不仅对课本内容有了更好的理解也提高了自己的编程能力。 同样，在此次的课程设计中存在着一些不足之处。在对进程的到达时间以及运行时间的设计中，没有对时间的表示进行具体的设计和模拟，在此次课程设计中对时间的模拟直接采用十进制的形式，另外如果添加了标准时间制来设计进程信息将会取到更好的效果。在设计主函数时候，采用指针实现不同调度算法的选择。在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。特别是设计先来先服务调度算法和强占式短进程优先调度算法的时候，对进程的调度算法有了更好的直观接触。对进程管理中的等待队列，就绪队列，优先级，强占式等概念