操作系统算法设计-操作系统课程设计.doc

成绩 课程设计报告 题 目 操作系统算法设计 课 程 名 称 操作系统课程设计 院 部 名 称 计算机工程学院 专 业 计算机科学与技术 班 级 14计算机科学与技术单 学 生 姓 名 邵佳楠 学 号 141320100 课程设计地点 A107 课程设计学时 20学时 指 导 教 师 潘 金陵科技学院教务处制目 录摘 要1一、课程设计的目的和要求3二、系统需求分析3三、总体设计3四、详细设计4五、测试、调试过程7六、结论与体会16附录：源程序17摘 要32一、课程设计的目的和要求33二、系统需求分析33三、总体设计33四、详细设计33五、测试、调试过程34六、结论与体会38附录：源程序39摘 要47一、设计的目的和要求48二、系统需求分析48三、总体设计48四、详细设计48五、测试、调试过程50六、结论与体会54附录：源程序55操作系统算法设计-进程调度程序摘 要随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学好这门课程，必须把理论和时间紧密结合，才能取得较好的学习效果。本次课程设计师在学习完操作系统教程后，进行的一次全面的综合训练，通过课程设计，让学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。熟悉“最高优先级优先调度算法”、“基于时间片轮转法”、“多级反馈队列调度算法”、“最高优先级优先算法”，虽然不用全部每一个都弄清楚，但是了解其中的算法思想也是有好处的。关键词：最高优先级优先调度算法、基于时间片轮转法、多级反馈队列调度算法、最高优先级优先算法 一、 课程设计的目的和要求程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。二、系统需求分析在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度（又称高级调度或长程调度）和进程调度（又称低级调度或短程调度）两个过程后方能获得处理机；对于终端型作业，则通常只需经过进程调度即可获得处理机。在较完善的操作系统中，为提高内存的利用率，往往还设置了中级调度（又称中程调度）。对于上述的每一级调度，又都可采用不同的调度方式和调度算法。三、总体设计编写进程调度程序，“最高优先级优先”算法常用语批处理系统中，在进程调度中，每次调度时，系统把处理机给就绪队列中优先级最高的进程。在非抢占式优先级算法下系统一旦把处理机分配给就绪队列中优先级最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的理你个优先级最高的进程。静态优先级是在创建进程时确定的，并在整个运行期间不再改变。动态优先级是指进程的优先级在创建进程时可以给定一个初始值，并且可以按一定原则修改优先级。“轮转法”算法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾;然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。 “多级反馈队列调度”算法中，进程在进入待调度的队列等待时，首先进入优先级最高的队列等待。先调度优先级高的队列中的进程，若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。对于同一个队列中的各个进程，按照时间片轮转法调度。在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。最高优先级优先算法:从键盘输入若干个进程，进程包括进程名，进程优先级，进程运行时间。就绪队列按照优先级从高到低排列，进程调度中，获取就绪队列队首进程，即优先级最高的进程，在进程获得一次CPU后，就将该进程的优先级减1。重新排列就绪队列，获取就绪队列队首进程进行调度。四、详细设计进程调度程序中，静态优先级算法的基本原理与简单轮转调度的算法还有多级反馈调度算法相似，都是先用户输入进程信息、对用户输入的进程按优先级排序，然后输出就绪队列中的进程、输出正在运行的进程、输出已完成的进程、静态优先级算法，区别在于简单轮转调度算法多一个对用户输入的进程按FCFS排序。动态优先级算法是根据静态优先级算法进行更改，总体差不多只是相对灵活性更加灵活。而多级反馈调度算法是按优先级排序，整体上差不多。下面是各个算法的程序流程图：初始化是否开始输入进程按优先级高低排入就绪队列中是否继续输入进程就绪队列是否为空获取就绪队列队首进程进程获得一个CPU该进程是否完成按优先级高低插入就绪队列中释放进程节点结束NYYNNYYN图1.1 最高优先级优先算法流程图初始化是否开始输入进程按先来先服务排入就绪队列中是否继续输入进程就绪队列是否为空获取就绪队列队首进程进程在时间片T内运行该进程是否完成排入就绪队列队尾释放进程节点结束NYYNNYYN图1.2 简单轮转法优先算法流程图初始化退出系统选择功能菜单输入进程是否继续输入按先来先服务算法插入就绪第一队列是否完成获取最高优先队列队首进程，若为空，则，寻在下一队列该进程获取CPU的一个时间片时间释放进程节点把该进程插入所在队列（n）的下一个队列（n+1）的队尾是否找到进程图1.3 多级反馈调度算法流程图五、测试、调试过程在静态优先级调度算法中，判断出了在运用getch()的时候需要头文件#include 这一项的。动态优先级算法在根据静态优先级算法的基础上改的整体的框架没有改变，简单轮转调度算法、多级反馈调度算法和静态优先级调度算法都有一个通用的问题就是conio.h，在编写程序的过程中要熟悉系统文件的头文件对应的功能。下面是各个程序的运行结果：静态优先级调度算法：动态优先级调度算法：简单轮转调度算法：多级反馈调度算法：六、结论与体会在运行的这几个程序中，普遍的问题就是缺少头文件，或者是系统的函数在没有弄清楚的情况下没有注意分开。操作系统这门课与实际运用联系也是很大的，比如银行家算法，虽然课程设计里面没有做到。在程序的几个调度算法中其实也可以看到现实的例子，比如进程调度，我们可以把他设计成一个公司内部管理调度，其性质和原理其实是一样的并没有什么太大的区别。在这门课上我学习到了如何独立自主的面对程序调试运行出现的问题。冷静的思考是很有必要的。附录：源程序进程调度程序/静态优先级调度算法.c#include #include #include #define MAX 24struct pcb/建立进程控制块char pname10;int priority;int reachtime;int needtime;int usecputime;char status;typedef struct pcb PCB;void inputpcb(PCB pcb,int *n)/用户输入进程信息int i;int num;printf(n请输入进程个数);scanf(%d,&num);for(i=0;inum;i+)printf(n请输入第%d个进程的名称:,i+1);scanf(%s,pcbi.pname);printf(n请输入第%d个进程的优先级:,i+1);scanf(%d,&pcbi.priority);printf(n进程的默认到达时间为O.n);printf(n请输入第%d个进程的运行时间:,i+1);scanf(%d,&pcbi.needtime);pcbi.reachtime=0;pcbi.usecputime=0;pcbi.status=r;*n=num;void paixupcb(PCB pcb,int n)/对用户输入的进程按优先级排序int i,j;PCB pcbtemp;for(i=0;in-1;i+)for(j=i+1;jn;j+)if(pcbi.prioritypcbj.priority)pcbtemp=pcbi;pcbi=pcbj;pcbj=pcbtemp;void printpcb(PCB pcb,int n)/输出就绪队列中的进程int i;printf(n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status!=F)printf(n %s %d %d %d %d %c,pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void printRpcb(PCB pcb,int n)/输出正在运行的进程int i;printf(n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status=R)printf(n %s %d %d %d %d %c,pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void printFpcb(PCB pcb,int n)/输出已完成的进程int i;printf(n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status=F)printf(n %s %d %d %d %d %c,pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void staPRI(PCB pcb,int n,int times)/静态优先级算法int i=0;printf(n当前的系统时间为:%dn,times);getch();printf(n按优先级排序，到达就绪队列中的进程为：);paixupcb(pcb,n);getch();for(i=0;ipcbi.usecputime)pcbi.status=R;printf(n按静态优先级对进程调度，正在运行的进程为：);pcbi.usecputime+;times+;printRpcb(pcb,n);getch();printf(n当前的系统时间为:%dn,times);getch();pcbi.status=r;paixupcb(pcb,n);if(pcbi.needtime=pcbi.usecputime)pcbi.status=F;printf(n此时刻，进程%s已经完成，进程%s被撤销!n,pcbi.pname,pcbi.pname);getch();printf(n按优先级排序，就绪队列中的进程为：);printpcb(pcb,n);getch();printf(n按优先级队列中已经没有进程，至此，所有的进程已经完成!n);getch();printf(n完成信息如下：);printFpcb(pcb,n);getch();printf(nn进程调度完毕!请按任意键退出!);/动态优先级算法void dynPRI(PCB pcb,int n,int times) int i=0; char temp10; int min; ;printf(n当前的系统时间为:%dn,times);getch();printf(n按优先级排序，到达就绪队列中的进程为：);paixupcb(pcb,n);printpcb(pcb,n);getch(); for(i=0;ipcbi+1.reachtime) min=pcbi.reachtime; pcbi.reachtime=pcbi+1.reachtime; pcbi+1.reachtime=min; min=pcbi.needtime; pcbi.needtime=pcbi+1.needtime; pcbi+1.needtime=min; min=pcbi.priority; pcbi.priority=pcbi+1.priority; pcbi+1.priority=min; strcpy(temp,pcbi.pname); strcpy(pcbi.pname,pcbi+1.pname); strcpy(pcbi+1.pname,temp); for(i=0;in;i+) if(pcbi.prioritypcbi+1.priority) min=pcbi.priority; pcbi.priority=pcbi+1.priority; pcbi+1.priority=min; min=pcbi.reachtime; pcbi.reachtime=pcbi+1.reachtime; pcbi+1.reachtime=min; min=pcbi.needtime; pcbi.needtime=pcbi+1.needtime; pcbi+1.needtime=min; strcpy(temp,pcbi.pname); strcpy(pcbi.pname,pcbi+1.pname); strcpy(pcbi+1.pname,temp); / pcbsi.usetime+; /按进程优先级排序，最高的排在最前面 printf(n按优先级队列中已经没有进程，至此，所有的进程已经完成!n);getch();printf(n完成信息如下：);printFpcb(pcb,n);getch();printf(nn进程调度完毕!请按任意键退出!);void main()PCB pcbrMAX;int pnum=0;int systime=0;printf(tttt进程调度模拟演示程序);inputpcb(pcbr,&pnum);printf(n用户输入的进程信息为：);printpcb(pcbr,pnum);staPRI(pcbr,pnum,systime);/简单轮转法调度算法.c#include #include #include #define MAX 24struct pcb/建立进程控制块char pname10;int reachtime;int needtime;int usecputime;char status;typedef struct pcb PCB;void inputpcb (PCB pcb,int *n)/用户输入进程信息int i;int num;printf(n请输入进程个数);scanf(%d,&num);for(i=0;inum;i+)printf(n请输入第%d个进程的名称:,i+1);scanf(%s,&pcbi.pname);printf(n请输入第%d个进程的提交时间:,i+1);scanf(%d,&pcbi.reachtime);printf(n请输入第%d个进程的运行时间:,i+1);scanf(%d,&pcbi.needtime);pcbi.usecputime=0;pcbi.status=r;*n=num;void fcfspcb(PCB pcb,int n)/对用户输入的进程按FCFS排序int i,j;PCB pcbtemp;for(i=0;in-1;i+)for(j=i+1;jpcbj.reachtime)pcbtemp=pcbi;pcbi=pcbj;pcbj=pcbtemp;void printpcb(PCB pcb,int n)/输出用户输入的进程int i;printf(n进程名 到达时间 需要运行时间);for(i=0;in;i+)printf(n %s %d %d,pcbi.pname,pcbi.reachtime,pcbi.needtime);printf(n);void printrpcb(PCB pcb,int n)/输出就绪队列中的进程int i;printf(n进程名 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status=r)printf(n %s %d %d %d %c,pcbi.pname,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void printRpcb(PCB pcb,int n)/输出正在运行的进程int i;printf(n进程名 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status=R)printf(n %s %d %d %d %c,pcbi.pname,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void printFpcb(PCB pcb,int n)/输出已完成的进程int i;printf(n进程名 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;ipcbi.usecputime&in)pcbi.status=R;printf(n按简单时间片轮转发对进程进行调度，正在运行的进程为:);pcbi.needtime+;printRpcb(pcb,n);getch();if(pcbi.needtime=pcbi.usecputime)pcbi.status=F;printf(n此时刻，进程%s已经完成，进程%s被撤销!n,pcbi.pname,pcbi.pname);getch();i+;elsepcbi.status=r;pcbtemp=pcbi;for(j=i;jn-1;j+)pcbj=pcbj+1;pcbj=pcbtemp;printf(n本次调度完成!准备进行下一次调度.n);getch();printf(n就绪队列中的进程为:);printrpcb(pcb,n);getch();printf(n就绪队列中已经没有进程，致辞，所有的进程已经完成);getch();printf(n完成信息如下:);printFpcb(pcb,n);getch();printf(nn进程调度完毕!请按任意键退出!);void main()PCB pcbrMAX;int pnum=0;printf(tttt进程调度模拟演示程序);inputpcb(pcbr,&pnum);printf(n用户输入的原始程序信息为:);printpcb(pcbr,pnum);simTSC(pcbr,pnum);/多级反馈队列调度算法.c#include #include #include #define MAX 24struct pcb/建立进程控制块char pname10;int priority;int reachtime;int needtime;int usecputime;char status;typedef struct pcb PCB;void inputpcb(PCB pcb,int *n)/用户输入进程信息int i;int num;printf(n请输入进程个数);scanf(%d,&num);for(i=0;inum;i+)printf(n请输入第%d个进程的名称:,i+1);scanf(%s,pcbi.pname);printf(n请输入第%d个进程的优先级:,i+1);scanf(%d,&pcbi.priority);printf(n进程的默认到达时间为O.n);printf(n请输入第%d个进程的运行时间:,i+1);scanf(%d,&pcbi.needtime);pcbi.reachtime=0;pcbi.usecputime=0;pcbi.status=r;*n=num;void paixupcb(PCB pcb,int n)/对用户输入的进程按优先级排序int i,j;PCB pcbtemp;for(i=0;in-1;i+)for(j=i+1;jn;j+)if(pcbi.prioritypcbj.priority)pcbtemp=pcbi;pcbi=pcbj;pcbj=pcbtemp;void printpcb(PCB pcb,int n)/输出就绪队列中的进程int i;printf(n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status!=F)printf(n %s %d %d %d %d %c,pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void printRpcb(PCB pcb,int n)/输出正在运行的进程int i;printf(n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status=R)printf(n %s %d %d %d %d %c,pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void printFpcb(PCB pcb,int n)/输出已完成的进程int i;printf(n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态);for(i=0;in;i+)if(pcbi.status=F)printf(n %s %d %d %d %d %c,pcbi.pname,pcbi.priority,pcbi.reachtime,pcbi.needtime,pcbi.usecputime,pcbi.status);printf(n);void staPRI(PCB pcb,int n,int times)/静态优先级算法int i=0;printf(n当前的系统时间为:%dn,times);getch();printf(n按优先级排序，到达就绪队列中的进程为：);paixupcb(pcb,n);getch();for(i=0;ipcbi.usecputime)pcbi.status=R;printf(n按静态优先级对进程调度，正在运行的进程为：);pcbi.usecputime+;times+;printRpcb(pcb,n);getch();printf(n当前的系统时间为:%dn,times);getch();pcbi.status=r;paixupcb(pcb,n);if(pcbi.needtime=pcbi.usecputime)pcbi.status=F;printf(n此时刻，进程%s已经完成，进程%s被撤销!n,pcbi.pname,pcbi.pname);getch();printf(n按优先级排序，就绪队列中的进程为：);printpcb(pcb,n);getch();printf(n就绪队列中已经没有进程，至此，所有的进程已经完成!n);getch();printf(n完成信息如下：);printFpcb(pcb,n);getch();printf(nn进程调度完毕!请按任意键退出!);void main()PCB pcbrMAX;int pnum=0;int systime=0;printf(tttt进程调度模拟演示程序);inputpcb(pcbr,&pnum);printf(n用户输入的进程信息为：);printpcb(pcbr,pnum);staPRI(pcbr,pnum,systime);操作系统算法设计-主存分配回收摘 要在内存初始化完成以后，内存中就常驻有内核映像（内核代码和数据）。以后，随着用户程序的执行和结束，就需要不断地分配和释放物理页面，内核应该为分配一组连续的页面而建立一种稳定、高效的分配策略。为此，必须解决一个比较重要的内存管理问题，即外碎片问题。频繁地请求和释放不同大小的一组连续页面，必然导致在已分配的内存块中分散许多小块的空闲页面。由此带来的问题是，即使这些小块的空闲页面加起来足以满足所请求的页面，但是要分配一个大块的连续页面可能就根本无法满足，Linux采用注明的伙伴（Buddy）系统算法来解决外碎片问题。但是请注意，在Linux中，CPU不能按物理地址来访问存储空间，而必须使用虚拟地址；因此，对于内存页面的管理，通常是在虚存空间中分配一个虚存区间，然后才根据需要为此区间分配相应的物理页面并建立起映射，也就是说，虚存区间的分配在前，而物理页面的分配在后，但是为了承接上一节的内容，我们先介绍内存的分配和回收，然后在介绍用户进程虚存区间的建立。分配效率、碎片问题是操作系统中内存分配的两大问题。一个好的分配器应该能够快速地满足各种大小的分配要求，同时不能产生大量的碎片浪费空间。基于数据结构的伙伴系统的分配与回收思想给出了一个有效的算法。关键词：操作系统 内存分配 首次适应算法 循环首次适应算法 最佳适应算法最坏适应算法一、 课程设计的目的和要求操作系统的课程设计非常有必要，可以是学生通过编程实验，更加深入得理解和掌握了操作系统的基本理论和功能技术。示例如下：1.掌握进程的概念、加深对进程调度算法的理解、掌握C语言的编程初步；2.写出主存空间的分配和回收程序的设计方案，包括方案描述及流程图；3.用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。二、系统需求分析主存分配与回收采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法设计。设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行，或在程序运行过程，由用户指定申请与释放。设计一个空闲区说明表，以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。三、总体设计编程序实现下述在不同的存储管理方式下的主存空间的分配与回收，其中原始数据设为空闲区说明表结构体(1).设计基于空闲区说明表的可变分区分配与回收算法；(2).或设计基于空闲区链表的可变分区的分配与回收；四、详细设计主存分配回收程序中，采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。主存分配回收中，我采用的是让应用人员自己选择运用的采用什么算法，首次适应算法、最佳适应算法，任务书上是有四种算法的，我选择了这两种。当然程序中需要初始化函数、输出列表函数、首次适应载入进程函数：让你尝试一把自己把需要的数据插入进去、最佳算法载入进程函数：和首次适应载入进程函数差不多，但是看你选择的过程中亲自体验哪个算法比较好、释放进程的子函数：程序运行结束需要结束进程。下面是各个算法的程序流程图：NNNNYYY开始按enter进入程序1？Y输入字符ss=a?s=r?s=d?返回1执行a(),shu()输出4个选项执行r(),shu()输出4个选项执行d(),shu()输出4个选项返回0结束图1.4 主存分配回收流程图五、测试、调试过程（1）程序运行没有按预期完成任务，解决方法是每次对内存分配和回收之前和之后都要对空闲区按地址进行排序（2）程序不能显示作业状况，解决办法是为作业作一个已分配表用来存储作业记录下面是各个程序的运行结果：主存分配回收：六、结论与体会在这次设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西在实际运用中的还是有一定距离的。一切问题必须要靠自己一点一滴的解决，而在解决的过程当中你会发现自己在飞速的提升。程序设计是一个很灵活的东西，它反映了你解决问题的逻辑思维和创新能力，是一个设计的灵魂所在，通过这次课程设计我也发现了自己存在的不足之处，虽然感觉理论上已经掌握，但在运动到实践过程中仍有意想不到的困惑，经过一番努力才得以解决。总之，通过这次课程设计的细节问题，而这些问题是我在从低级的程序员向高级程序设计师过度的过程必须要解决的。而我个人认为，我越早接触，越多接触，越快解决对我本人所断过程有重要的意义。附录：源程序#include #include #include struct pcbchar name10;int size;int begin;char status;int end;PCB20;int n=1;int size=1024;void c()/初始化函数printf(n初始化，设内存总存量为1Mn);printf(n系统从低地址部分开始使用，占用100K;n);strcpy(PCB0.name,SYSNAME);PCB0.begin=0;/开始地址为0PCB0.status=u;/状态忙碌PCB0.size=100;/占用内存大小100KPCB0.end=100;/结束地址为100strcpy(PCB1.name,-);PCB1.begin=PCB0.end;PCB1.size=size-PCB0.size;/剩下空闲的内存大小PCB1.status=f;PCB1.end=1024;size=size-100;shu()/输出列表函数int i;int a=1;while(n=0)printf(队列为空n);return 1;printf(空闲列表区Free:nn);printf( NO prona