成绩
课程设计报告
题 目 操作系统算法设计
课 程 名 称 操作系统课程设计 院 部 名 称 计算机工程学院 专 业 计算机科学与技术 班 级 14计算机科学与技术单 学 生 姓 名 邵佳楠 学 号 141320100 课程设计地点 A107 课程设计学时 20学时 指 导 教 师 潘
金陵科技学院教务处制
.
目 录
摘 要................................................................................................................................................. 2 一、 课程设计的目的和要求 ................................................................................................... 3 二、系统需求分析 ........................................................................................................................... 3 三、总体设计 ................................................................................................................................... 3 四、详细设计 ................................................................................................................................... 4 五、测试、调试过程 ....................................................................................................................... 7 六、结论与体会 ............................................................................................................................. 16 附录：源程序 ................................................................................................................................. 17 摘 要............................................................................................................................................... 32 一、 课程设计的目的和要求 ................................................................................................. 33 二、系统需求分析 ......................................................................................................................... 33 三、总体设计 ................................................................................................................................. 33 四、详细设计 ................................................................................................................................. 33 五、测试、调试过程 ..................................................................................................................... 34 六、结论与体会 ............................................................................................................................. 38 附录：源程序 ................................................................................................................................. 39 摘 要............................................................................................................................................... 47 一、 设计的目的和要求 ......................................................................................................... 47 二、系统需求分析 ......................................................................................................................... 48 三、总体设计 ................................................................................................................................. 48 四、详细设计 ................................................................................................................................. 48 五、测试、调试过程 ..................................................................................................................... 50 六、结论与体会 ............................................................................................................................. 54 附录：源程序 ................................................................................................................................. 55
;1
.
操作系统算法设计-进程调度程序
摘 要
随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学好这门课程，必须把理论和时间紧密结合，才能取得较好的学习效果。
本次课程设计师在学习完《操作系统教程》后，进行的一次全面的综合训练，通过课程设计，让学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。
熟悉“最高优先级优先调度算法”、“基于时间片轮转法”、“多级反馈队列调度算法”、“最高优先级优先算法”，虽然不用全部每一个都弄清楚，但是了解其中的算法思想也是有好处的。
关键词：最高优先级优先调度算法、基于时间片轮转法、多级反馈队列调度算
法、最高优先级优先算法
;2
.
一、 课程设计的目的和要求
程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。
二、系统需求分析
在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度（又称高级调度或长程调度）和进程调度（又称低级调度或短程调度）两个过程后方能获得处理机；对于终端型作业，则通常只需经过进程调度即可获得处理机。在较完善的操作系统中，为提高内存的利用率，往往还设置了中级调度（又称中程调度）。对于上述的每一级调度，又都可采用不同的调度方式和调度算法。
三、总体设计
编写进程调度程序，“最高优先级优先”算法常用语批处理系统中，在进程调度中，每次调度时，系统把处理机给就绪队列中优先级最高的进程。在非抢占式优先级算法下系统一旦把处理机分配给就绪队列中优先级最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的理你个优先级最高的进程。静态优先级是在创建进程时确定的，并在整个运行期间不再改变。动态优先级是指进程的优先级在创建进程时可以给定一个初始值，并且可以按一定原则修改优先级。
“轮转法”算法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾;然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。
;3
.
“多级反馈队列调度”算法中，进程在进入待调度的队列等待时，首先进入优先级最高的队列等待。先调度优先级高的队列中的进程，若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。对于同一个队列中的各个进程，按照时间片轮转法调度。在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
最高优先级优先算法:从键盘输入若干个进程，进程包括进程名，进程优先级，进程运行时间。就绪队列按照优先级从高到低排列，进程调度中，获取就绪队列队首进程，即优先级最高的进程，在进程获得一次CPU后，就将该进程的优先级减1。重新排列就绪队列，获取就绪队列队首进程进行调度。
四、详细设计
进程调度程序中，静态优先级算法的基本原理与简单轮转调度的算法还有多级反馈调度算法相似，都是先用户输入进程信息、对用户输入的进程按优先级排序，然后输出就绪队列中的进程、输出正在运行的进程、输出已完成的进程、静态优先级算法，区别在于简单轮转调度算法多一个对用户输入的进程按FCFS排序。动态优先级算法是根据静态优先级算法进行更改，总体差不多只是相对灵活性更加灵活。而多级反馈调度算法是按优先级排序，整体上差不多。
下面是各个算法的程序流程图：
;4
.
初始化 N 是否开始 Y 输入进程 结束 按优先级高低排入就绪队列中 Y 是否继续输入进程 Y N 就绪队列是否为空 N 获取就绪队列队首进程 进程获得一个CPU Y 该进程是否完成 N 释放进程节点 按优先级高低插入就绪队列中
图1.1 最高优先级优先算法流程图
;5
.
初始化 N 是否开始 Y 结束 输入进程 按先来先服务排入就绪队列中 Y 是否继续输入进程 N Y 就绪队列是否为空 N 获取就绪队列队首进程 进程在时间片T内运行 Y 该进程是否完成 N 释放进程节点 排入就绪队列队尾 图1.2 简单轮转法优先算法流程图
;6
.
初始化 选择功能菜单 输入进程 退出系统 获取最高优先队列队首进程，若为空，则，寻在下一队列 按先来先服务算法插入就绪第一队列 是否找到进程 是否继续输入 该进程获取CPU的一个时间片时间 是否完成 把该进程插入所在队列（n）的下一个队列（n+1）的队尾 释放进程节点
图1.3 多级反馈调度算法流程图
五、测试、调试过程
在静态优先级调度算法中，判断出了在运用getch()的时候需要头文件#include ;7 . 调度算法都有一个通用的问题就是conio.h，在编写程序的过程中要熟悉系统文件的头文件对应的功能。 下面是各个程序的运行结果： 静态优先级调度算法： ;8 . ;9 . 动态优先级调度算法： ;10 . 简单轮转调度算法： ;11 . 多级反馈调度算法： ;12 . ;13 . ;14 . ;15 . 六、结论与体会 在运行的这几个程序中，普遍的问题就是缺少头文件，或者是系统的函数在没有弄清楚的情况下没有注意分开。操作系统这门课与实际运用联系也是很大的，比如银行家算法，虽然课程设计里面没有做到。在程序的几个调度算法中其实也可以看到现实的例子，比如进程调度，我们可以把他设计成一个公司内部管理调度，其性质和原理其实是一样的并没有什么太大的区别。在这门课上我学习到了如何独立自主的面对程序调试运行出现的问题。冷静的思考是很有必要的。 ;16 . 附录：源程序 进程调度程序 //静态优先级调度算法.c #include struct pcb//建立进程控制块 { char pname[10]; 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\for(i=0;i printf(\"\\n请输入第%d个进程的优先级:\scanf(\"%d\ printf(\"\\n进程的默认到达时间为O.\\n\"); printf(\"\\n请输入第%d个进程的运行时间:\scanf(\"%d\pcb[i].reachtime=0; pcb[i].usecputime=0; pcb[i].status='r'; ;17 . } void paixupcb(PCB pcb[],int n)//对用户输入的进程按优先级排序 { } void printpcb(PCB pcb[],int n)//输出就绪队列中的进程 { int i; printf(\"\\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i if(pcb[i].status!='F') int i,j; PCB pcbtemp; for(i=0;i } *n=num; ame,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status); } void printRpcb(PCB pcb[],int n)//输出正在运行的进程 { } printf(\"\\n\"); ;18 . int i; printf(\"\\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i printf(\"\\n %s %d %d %d %d %c\ ame,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status); } void printFpcb(PCB pcb[],int n)//输出已完成的进程 { int i; printf(\"\\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i printf(\"\\n\"); printf(\"\\n %s %d %d %d %d %c\ ame,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status); } void staPRI(PCB pcb[],int n,int times)//静态优先级算法 { int i=0; printf(\"\\n当前的系统时间为:%d\\n\getch(); printf(\"\\n按优先级排序，到达就绪队列中的进程为：\"); paixupcb(pcb,n); getch(); for(i=0;i pcb[i].status='R'; } printf(\"\\n\"); ;19 . printf(\"\\n按静态优先级对进程调度，正在运行的进程为：\"); pcb[i].usecputime++; times++; printRpcb(pcb,n); getch(); printf(\"\\n当前的系统时间为:%d\\n\getch(); pcb[i].status='r'; paixupcb(pcb,n); if(pcb[i].needtime==pcb[i].usecputime) { pcb[i].status='F'; printf(\"\\n 此时刻，进程%s 已经完成，进程%s 被撤 销!\\n\ } //动态优先级算法 void dynPRI(PCB pcb[],int n,int times) { int i=0; } printf(\"\\n按优先级队列中已经没有进程，至此，所有的进程已经完成!\\n\"); getch(); printf(\"\\n完成信息如下：\"); printFpcb(pcb,n); getch(); printf(\"\\n\\n进程调度完毕!请按任意键退出!\"); } } printf(\"\\n按优先级排序，就绪队列中的进程为：\"); printpcb(pcb,n); getch(); getch(); char temp[10]; int min; ; ;20 . printf(\"\\n当前的系统时间为:%d\\n\getch(); printf(\"\\n按优先级排序，到达就绪队列中的进程为：\"); paixupcb(pcb,n); printpcb(pcb,n); getch(); for(i=0;i min=pcb[i].reachtime; pcb[i].reachtime=pcb[i+1].reachtime; pcb[i+1].reachtime=min; min=pcb[i].needtime; pcb[i].needtime=pcb[i+1].needtime; pcb[i+1].needtime=min; min=pcb[i].priority; pcb[i].priority=pcb[i+1].priority; pcb[i+1].priority=min; strcpy(temp,pcb[i].pname); strcpy(pcb[i].pname,pcb[i+1].pname); strcpy(pcb[i+1].pname,temp); } } for(i=0;i pcb[i].priority=pcb[i+1].priority; pcb[i+1].priority=min; min=pcb[i].reachtime; pcb[i].reachtime=pcb[i+1].reachtime; pcb[i+1].reachtime=min; ;21 . min=pcb[i].needtime; pcb[i].needtime=pcb[i+1].needtime; pcb[i+1].needtime=min; strcpy(temp,pcb[i].pname); strcpy(pcb[i].pname,pcb[i+1].pname); strcpy(pcb[i+1].pname,temp); // pcbs[i].usetime++; } //按进程优先级排序，最高的排在最前面 } } void main() { } //简单轮转法调度算法.c #include printf(\"\\n按优先级队列中已经没有进程，至此，所有的进程已经完成!\\n\"); getch(); printf(\"\\n完成信息如下：\"); printFpcb(pcb,n); getch(); printf(\"\\n\\n进程调度完毕!请按任意键退出!\"); PCB pcbr[MAX]; int pnum=0; int systime=0; printf(\"\\\\进程调度模拟演示程序\"); inputpcb(pcbr,&pnum); printf(\"\\n用户输入的进程信息为：\"); printpcb(pcbr,pnum); staPRI(pcbr,pnum,systime); ;22 . struct pcb//建立进程控制块 { }; typedef struct pcb PCB; void inputpcb (PCB pcb[],int *n)//用户输入进程信息 { } void fcfspcb(PCB pcb[],int n)//对用户输入的进程按FCFS排序 { int i,j; PCB pcbtemp; for(i=0;i int i; int num; printf(\"\\n请输入进程个数\"); scanf(\"%d\for(i=0;i printf(\"\\n请输入第%d个进程的提交时间:\scanf(\"%d\ printf(\"\\n请输入第%d个进程的运行时间:\scanf(\"%d\pcb[i].usecputime=0; pcb[i].status='r'; ;23 . } void printpcb(PCB pcb[],int n)//输出用户输入的进程 { printf(\"\\n %s %d %d\int i; printf(\"\\n进程名 到达时间 需要运行时间\"); for(i=0;i if(pcb[i].reachtime>pcb[j].reachtime) { } pcbtemp=pcb[i]; pcb[i]=pcb[j]; pcb[j]=pcbtemp; i].needtime); } void printrpcb(PCB pcb[],int n)//输出就绪队列中的进程 { int i; printf(\"\\n进程名 到达时间 需要运行时间 已用CPU时间 } printf(\"\\n\"); 进程状态\"); for(i=0;i if(pcb[i].status=='r') %c\ } printf(\"\\n\"); ;24 . } void printRpcb(PCB pcb[],int n)//输出正在运行的进程 { int i; printf(\"\\n进程名 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i if(pcb[i].status=='R') %c\ } void printFpcb(PCB pcb[],int n)//输出已完成的进程 { int i; printf(\"\\n进程名 到达时间 需要运行时间 已用CPU时间 } printf(\"\\n\"); 进程状态\"); for(i=0;i if(pcb[i].status=='F') %c\ } void simTSC(PCB pcb[],int n) { int i=0; int j; PCB pcbtemp; printf(\"\\n按先来先服务排序，就绪队列中的进程:\"); } printf(\"\\n\"); ;25 . fcfspcb(pcb,n); getch(); while(pcb[i].needtime>pcb[i].usecputime&&i if(pcb[i].needtime==pcb[i].usecputime) { pcb[i].status='F'; printf(\"\\n 此时刻，进程%s 已经完成，进程%s 销!\\n\ getch(); i++; } else { pcb[i].status='r'; pcbtemp=pcb[i]; for(j=i;j pcb[j]=pcbtemp; } printf(\"\\n本次调度完成!准备进行下一次调度.\\n\"); getch(); printf(\"\\n就绪队列中的进程为:\"); printrpcb(pcb,n); getch(); } printf(\"\\n就绪队列中已经没有进程，致辞，所有的进程已经完成\"); getch(); ;26 被撤 . } void main() { } //多级反馈队列调度算法.c #include struct pcb//建立进程控制块 { }; typedef struct pcb PCB; void inputpcb(PCB pcb[],int *n)//用户输入进程信息 { int i; printf(\"\\n完成信息如下:\"); printFpcb(pcb,n); getch(); printf(\"\\n\\n进程调度完毕!请按任意键退出!\"); PCB pcbr[MAX]; int pnum=0; printf(\"\\\\进程调度模拟演示程序\"); inputpcb(pcbr,&pnum); printf(\"\\n用户输入的原始程序信息为:\"); printpcb(pcbr,pnum); simTSC(pcbr,pnum); char pname[10]; int priority; int reachtime; int needtime; int usecputime; char status; ;27 . } void paixupcb(PCB pcb[],int n)//对用户输入的进程按优先级排序 { } int num; printf(\"\\n请输入进程个数\"); scanf(\"%d\for(i=0;i printf(\"\\n请输入第%d个进程的优先级:\scanf(\"%d\ printf(\"\\n进程的默认到达时间为O.\\n\"); printf(\"\\n请输入第%d个进程的运行时间:\scanf(\"%d\pcb[i].reachtime=0; pcb[i].usecputime=0; pcb[i].status='r'; int i,j; PCB pcbtemp; for(i=0;i ;28 . void printpcb(PCB pcb[],int n)//输出就绪队列中的进程 { int i; printf(\"\\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i if(pcb[i].status!='F') ].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status); } void printRpcb(PCB pcb[],int n)//输出正在运行的进程 { int i; printf(\"\\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i if(pcb[i].status=='R') } printf(\"\\n\"); ].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status); } void printFpcb(PCB pcb[],int n)//输出已完成的进程 { int i; printf(\"\\n进程名 优先级 到达时间 需要运行时间 已用CPU时间 进程状态\"); for(i=0;i printf(\"\\n\"); if(pcb[i].status=='F') ;29 . printf(\"\\n %s %d %d %d %d %c\ ].pname,pcb[i].priority,pcb[i].reachtime,pcb[i].needtime,pcb[i].usecputime,pcb[i].status); } printf(\"\\n\"); } void staPRI(PCB pcb[],int n,int times)//静态优先级算法 { int i=0; printf(\"\\n当前的系统时间为:%d\\n\ getch(); printf(\"\\n按优先级排序，到达就绪队列中的进程为：\"); paixupcb(pcb,n); getch(); for(i=0;i printf(\"\\n按静态优先级对进程调度，正在运行的进程为：\"); pcb[i].usecputime++; times++; printRpcb(pcb,n); getch(); printf(\"\\n当前的系统时间为:%d\\n\ getch(); pcb[i].status='r'; paixupcb(pcb,n); if(pcb[i].needtime==pcb[i].usecputime) { pcb[i].status='F'; printf(\"\\n 此时刻，进程%s 已经完成，进程%s 销!\\n\ getch(); } printf(\"\\n按优先级排序，就绪队列中的进程为：\"); ;30 被撤 . } void main() { } } } printpcb(pcb,n); getch(); printf(\"\\n就绪队列中已经没有进程，至此，所有的进程已经完成!\\n\"); getch(); printf(\"\\n完成信息如下：\"); printFpcb(pcb,n); getch(); printf(\"\\n\\n进程调度完毕!请按任意键退出!\"); PCB pcbr[MAX]; int pnum=0; int systime=0; printf(\"\\\\进程调度模拟演示程序\"); inputpcb(pcbr,&pnum); printf(\"\\n用户输入的进程信息为：\"); printpcb(pcbr,pnum); staPRI(pcbr,pnum,systime); ;31 . 操作系统算法设计-主存分配回收 摘 要 在内存初始化完成以后，内存中就常驻有内核映像（内核代码和数据）。以后，随着用户程序的执行和结束，就需要不断地分配和释放物理页面，内核应该为分配一组连续的页面而建立一种稳定、高效的分配策略。为此，必须解决一个比较重要的内存管理问题，即外碎片问题。频繁地请求和释放不同大小的一组连续页面，必然导致在已分配的内存块中分散许多小块的空闲页面。由此带来的问题是，即使这些小块的空闲页面加起来足以满足所请求的页面，但是要分配一个大块的连续页面可能就根本无法满足，Linux采用注明的伙伴（Buddy）系统算法来解决外碎片问题。但是请注意，在Linux中，CPU不能按物理地址来访问存储空间，而必须使用虚拟地址；因此，对于内存页面的管理，通常是在虚存空间中分配一个虚存区间，然后才根据需要为此区间分配相应的物理页面并建立起映射，也就是说，虚存区间的分配在前，而物理页面的分配在后，但是为了承接上一节的内容，我们先介绍内存的分配和回收，然后在介绍用户进程虚存区间的建立。分配效率、碎片问题是操作系统中内存分配的两大问题。一个好的分配器应该能够快速地满足各种大小的分配要求，同时不能产生大量的碎片浪费空间。基于数据结构的伙伴系统的分配与回收思想给出了一个有效的算法。 关键词：操作系统 内存分配 首次适应算法 循环首次适应算法 最佳适应算法 最坏适应算法 ;32 . 一、 课程设计的目的和要求 操作系统的课程设计非常有必要，可以是学生通过编程实验，更加深入得理解和掌握了操作系统的基本理论和功能技术。示例如下： 1.掌握进程的概念、加深对进程调度算法的理解、掌握C语言的编程初步； 2.写出主存空间的分配和回收程序的设计方案，包括方案描述及流程图； 3.用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。 二、系统需求分析 主存分配与回收采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法设计。 设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行，或在程序运行过程，由用户指定申请与释放。 设计一个空闲区说明表，以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。 三、总体设计 编程序实现下述在不同的存储管理方式下的主存空间的分配与回收，其中原始数据设为空闲区说明表结构体 (1).设计基于空闲区说明表的可变分区分配与回收算法； (2).或设计基于空闲区链表的可变分区的分配与回收； 四、详细设计 主存分配回收程序中，采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。主存分配回收中，我采用的是让应用人员自己选择运用的采用什么算法，首次适应算法、最佳适应算法，任务书上是有四种算法的，我选择了这两种。当然程序中需要初始化函数、输出列表函数、首次适应载入进程函数：让你尝试一把自己把需要的数据插入进去、最佳算法载入进程函数：和首次适应载入进程函数 ;33 . 差不多，但是看你选择的过程中亲自体验哪个算法比较好、释放进程的子函数：程序运行结束需要结束进程。 下面是各个算法的程序流程图： 开始 按enter进入程序 1？ Y 输入字符s N N s=a? Y 返回1 s=r? Y 执行r(),shu() 输出4个选项 N 执行a(),shu() 输出4个选项 s=d? Y 执行d(),shu() 输出4个选项 N 返回0 结束 图1.4 主存分配回收流程图 五、测试、调试过程 （1）程序运行没有按预期完成任务，解决方法是每次对内存分配和回收之 ;34 . 前和之后都要对空闲区按地址进行排序 （2）程序不能显示作业状况，解决办法是为作业作一个已分配表用来存储作业记录 下面是各个程序的运行结果： 主存分配回收： ;35 . ;36 . ;37 . 六、结论与体会 在这次设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西在实际运用中的还是有一定距离的。一切问题必须要靠自己一点一滴的解决，而在解决的过程当中你会发现自己在飞速的提升。程序设计是一个很灵活的东西，它反映了你解决问题的逻辑思维和创新能力，是一个设计的灵魂所在，通过这次课程设计我也发现了自己存在的不足之处，虽然感觉理论上已经掌握，但在运动到实践过程中仍有意想不到的困惑，经过一番努力才得以解决。总之，通过这次课程设计的细节问题，而这些问题是我在从低级的程序员向高级程序设 ;38 . 计师过度的过程必须要解决的。而我个人认为，我越早接触，越多接触，越快解决对我本人所断过程有重要的意义。 附录：源程序 #include char name[10]; int size; int begin; char status; int end; }PCB[20]; int n=1;int size=1024; void c()//初始化函数 { } shu()//输出列表函数 { printf(\"\\n初始化，设内存总存量为1M\\n\"); printf(\"\\n系统从低地址部分开始使用，占用100K;\\n\"); strcpy(PCB[0].name,\"SYSNAME\"); PCB[0].begin=0;//开始地址为0 PCB[0].status='u';//状态忙碌 PCB[0].size=100;//占用内存大小100K PCB[0].end=100;//结束地址为100 strcpy(PCB[1].name,\"----\"); PCB[1].begin=PCB[0].end; PCB[1].size=size-PCB[0].size;//剩下空闲的内存大小 PCB[1].status='f'; PCB[1].end=1024; size=size-100; int i; ;39 . int a=1; while(n==0) { } printf(\"空闲列表区Free:\\n\\n\"); printf(\" NO proname begin size status\\n\"); for(i=0;i printf(\" printf(\"队列为空\\n\"); return 1; NO.%d%8s%7d%7d%6c\\n\ } printf(\"\\n============================================================ } a=a+1; =========\\n\"); a=1; printf(\"已分配列表区Userd：\\n\\n\"); printf(\" NO proname begin size status\\n\"); for(i=0;i printf(\" NO.%d%8s%7d%7d%6c\\n\ } printf(\"\\n============================================================ a=a+1; =========\\n\"); printf(\"内容使用情况，按照起始地址的增长排\\n\\n\"); printf(\" NO proname begin size status\\n\"); for(i=0;i ;40 . NO.%d%8s%7d%7d%6c\\n\ } a()//首次适应载入进程函数 { int i,j,a; char str[10]; printf(\"请输入进程的名字：\\n\"); scanf(\"%s\ printf(\"请输入进程的大小：\\n\"); scanf(\"%d\size=size-a; for(i=1;i if(PCB[i].status==a) { } else if(PCB[i].size>a)//当插入进程的大小小于空闲区大小时，插入 { for(j=n+1;j>i+1;j--)//空闲区下面的书序下移一位 if(i strcpy(PCB[i].name,str); PCB[i].begin=PCB[i-1].end; PCB[i].end=PCB[i].begin+PCB[i].size; PCB[i].status='u'; printf(\"插入完成\\n\");//当插入进程的大小等于空闲去的大小时，直接插入 return 1; printf(\"\\n\"); return 1; PCB[i].begin=PCB[i-1].end;//为插入进程分配空间 strcpy(PCB[i].name,str); PCB[i].size=a; PCB[i].end=PCB[i].begin+PCB[i].size; ;41 . } r()//释放进程的子函数 { int i,j,h=0; char str[10]; printf(\"请输入要释放的进程的名字：\"); gets(str); gets(str); for(i=1;i<=n;i++) if(strcmp(PCB[i].name,str)==0) { } PCB[i].status='f'; strcpy(PCB[i].name,\"----\"); h=1; } } PCB[i].status='u'; PCB[i+1].begin=PCB[i].end; if(i PCB[i+1].end=PCB[i+2].begin; PCB[i+1].size=PCB[i+1].end-PCB[i+1].begin; PCB[i+1].status='f'; strcpy(PCB[i+1].name,\"----\"); n=n+1; printf(\"插入完成\\n\"); return 1; for(i=1;i<=n;i++) if(PCB[i].status=='f'&&PCB[i+1].status=='f') { strcpy(PCB[i].name,\"----\"); PCB[i].size=PCB[i].size+PCB[i+1].size; PCB[i].end=PCB[i].begin+PCB[i].size; ;42 . } d()//最佳算法载入进程函数 { int i,j,a; char str[10]; char s; printf(\"请输入进程的名字：\\n\"); scanf(\"%s\ printf(\"请输入进程的大小：\\n\"); scanf(\"%d\size=size-a; for(i=1;i if(PCB[i].size==a) { } else if(PCB[i].size>a) { for(j=i;j<=n;j++) if(PCB[j].status=='f'&&PCB[j].size>a) if((PCB[i].size-a)>(PCB[j].size-a)) } for(j=i+1;j<=n;j++) i=0; n=n-1; PCB[j]=PCB[j+1]; return 1; strcpy(PCB[i].name,str); PCB[i].begin=PCB[i-1].end; PCB[i].end=PCB[i].begin+PCB[i].size; PCB[i].status='u'; printf(\"插入完成\\n\"); return 1; ;43 . } main() { char s; printf(\"\\n\###################################\\n\"); printf(\"\\n\\此为动态分配存储空间程序\\n\"); } } i=j; for(j=n+1;j>i+1;j--) if(i PCB[i].begin=PCB[i-1].end; strcpy(PCB[i].name,str); PCB[i].size=a; PCB[i].end=PCB[i].begin+PCB[i].size; PCB[i].status='u'; PCB[i+1].begin=PCB[i].end; if(i PCB[i+1].end=PCB[i+2].begin; PCB[i+1].size=PCB[i+1].end-PCB[i+1].begin; PCB[i+1].status='f'; strcpy(PCB[i+1].name,\"----\"); n=n+1; printf(\"插入完成\\n\"); return 1; printf(\"插入错误，内存空间大小不够\\n\"); printf(\"a重新插入 b返回上一级\\n\"); scanf(\"%c\if(s=='a') else return 1; d(); ;44 . printf(\"\\n\\a为：首次适应算法\\n\"); printf(\"\\n\\d为：最佳适应算法\\n\"); printf(\"\\n\\内存空间的前100K为系统空间\\n\"); printf(\"\\n\###################################\\n\"); printf(\"注意：因为删除程序时，按程序名删除，请不要输入相同的程序名\\n\"); printf(\"\\n按下enter进入程序\\n\"); scanf(\"%c\system(\"cls\"); c(); shu(); printf(\"请输入指令：（a为首次适应算法，d为最佳适应算法，r为释放进程，e结束）\\n\"); while(1) { scanf(\"%c\if(s=='a') { a(); shu(); printf(\"请输入指令：（a为首次适应算法，d为最佳适应算法，r为释放进程，e 结束）\\n\"); } else if(s=='r') { r(); shu(); printf(\"请输入指令：（a为首次适应算法，d为最佳适应算法，r为释放进 程，e结束）\\n\"); else if(s=='d') { d(); shu(); printf(\"请输入指令：（a为首次适应算法，d为最佳适应算法，r为释放进 } ;45 . 程，e结束）\\n\"); else if(s=='e') { return 0; } } } return 1; } 操作系统算法设计-文件系统 ;46 . 摘 要 课程设计内容是要完成一个多用户的文件系统。使用的设计语言是C++，开发环境是VC6.0，参考资料有“C++Builder6程序设计”，“C++编程开发实例”，“Java案例开发激进”，因为在学习的过程中，发现其中有很多东西很有用，而且发各种语言虽然有很大的不同，但是也有很多共同的东西，之前可以相互参考。所以在用一门语言开发时，我们也可以参考下其他的语言，这个可能对我们的开发有很大帮助。而且可以扩大我们的知识面。 关键词：多用户的文件系统 VC6.0 一、 设计的目的和要求 通过操作系统内其中一个子系统的设计与实现，掌握C文件系统的基本原理、结构和实现方法，掌握C文件系统中文件的建立、打开、读/写、执行、属 ;47 . 性等系统调用的使用，学会设计简单的文件系统并实现一组操作，一级学习文件系统的系统调用命令，提高对文件系统实现功能的理解和掌握。同事，掌握操作系统设计的方法与技巧，增强系统软件的实际工作能力。 二、系统需求分析 根据市场需求，要求系统具有以下功能。 (1) (2) (3) (4) (5) 处理大量的复合文档型的数据信息； 通过系统查看文档内容和属性； 通过系统可以完成对文档一系列的日常操作； 保证系统的安全性、可靠性； 由于操作人员的计算机偿债能力普遍较低，因此要求系统具有良好 的人机交互界面； (6) 完全人性化设计，无需专业人士知道，即可操作本系统 三、总体设计 该编程模拟一个简单的文件系统，实现文件系统的管理和控制功能。要求本文件系统采用两级目录，即设置主文件目录[MFD]和用户文件目录[UED]。 另外，为打开文件设置运行文件目录[AFD]。设计一个10个用户的文件系统，每次用户可保存10个文件，一次运行用户可以打开5个文件，并对文件必须设置保护措施。 在用户程序中通过使用文件系统提供的Create、open、read、write、close、delete等文件命令，对文件进行操作。 四、详细设计 该文件系统是一个多用户、多任务的文件系统。对用户和用户的文件数目并没有上限。也就是说该系统允许仍和用户申请空间，而且在其目录下的文件数目并不做任何限制。 该系统可以支持的操作命令如下：Create、open、read、write、close、delete。 系统采用二级文件目录，设置主目录（MFD）和用户文件目录（UFD），分别 ;48 . 以文件的方式保存在磁盘中。在主目录中有注册用户的用户名和另一标志用户目录下是否有文件的指针标记。用户文件目录采用用名户名作为文件名保存于磁盘，以便检索时方便对应。在用户文件目录中保存着该目录下所有的文件的文件名称、保护码、文件长度。 该系统大量使用高级语言中的文件操作函数，所以能实际看到文件的创建、写入、读出、删除等效果。 下面是各个算法的程序流程图： 49 ;. 开始 输出初始化界面 初始化MDF表 检测登录的用户名 输入的用户名和里面的用户N 名比较 输出用户名不存在 Y 初始化AFD 命令识别 根据对应的 命令执行程序 结束 图1.5 文件系统流程图 五、测试、调试过程 ;50 . 下面是各个程序的运行结果： 文件系统： ;51 . ;52 . ;53 . 六、结论与体会 经过几天的努力，我终于把文件系统的代码看完和修改好，完成这次课程设计的要求。在这个过程中，我受益匪浅。由于文件系统的源代码实在太多了，而且它里面的功能实现方面有所欠缺，要改动的地方十分地多，在加上时间的问题，所以程序有所改动，完成的相关的功能，但还不是最好的。这个过程过我也遇到了一些问题，但在自己的支持下，问题终于一个一个地解决。其中有一个写文件程序出现了一个问题，但在老师的指导下，也顺利地解决。 这几天的学习，是我更加了解了文件系统的相关知识，掌握C文件系统中文件的建立、打开、读/写、执行、属性等系统调用的使用，掌握操作系统设计的方法与技巧，增强系统软件设计的实际工作能力。 ;54 . 附录：源程序 #include struct mdf *next; }MDF; typedef struct ufd { char filename[20]; int protect; unsigned int length; struct ufd *next; }UFD; typedef struct afd { char filename[20]; int protect; unsigned int point; struct afd *next; }AFD; MDF *pmdf; UFD *pufd; AFD *pafd; char UserUFD[20]; void initMDF() { FILE *fp; pmdf=(MDF*)malloc(sizeof(MDF)); 55 ;. } void printUFD() { } void initUFD(char *name) { FILE *fp; pufd=(UFD*)malloc(sizeof(UFD)); UFD *p=pufd; if((fp=fopen(name,\"r+\"))==NULL) { MDF *p=pmdf; if((fp=fopen(\"MDF\{ } while(!feof(fp)) { } p->next=NULL; fclose(fp); p->next=(MDF*)malloc(sizeof(MDF)); p=p->next; fscanf(fp,\"%s\fscanf(fp,\"%s\puts(\"the MDF cannot open!\\n\"); exit(1); UFD *p=pufd->next; puts(\"文件名\\保护码\\文件长度\\n\"); while (p) { } printf(\"%s\printf(\"\\%d\printf(\"\\%d\\n\p=p->next; ;56 . } int checkuser() { char username[20]; while(1) { puts(\"请输入用户名：\\n\"); scanf(\"%s\MDF *p=pmdf; while(p) { } puts(\"同户名不存在\\n\"); } puts(\"the UFD cannot open !\\n\"); exit(1); while(!feof(fp)) { } p->next=NULL; fclose(fp); p->next=(UFD*)malloc(sizeof(UFD)); p=p->next; fscanf(fp,\"%s\fscanf(fp,\"%d\fscanf(fp,\"%d\fgetc(fp); if(strcmp(username,p->username)==0) { } p=p->next; strcpy(UserUFD,p->username); initUFD(p->filename); printUFD(); return 1; ;57 . } void initAFD() { } bool create() { char filename[20]; UFD *p=pufd->next; AFD *pa=pafd; puts(\"请输入要创建的文件名：\\n\"); scanf(\"%s\while(p) { } p->next=(UFD*)malloc(sizeof(UFD)); p=p->next; strcpy(p->filename,filename); p->protect=2; p->length=0; p->next=NULL; while(pa->next) { } } pafd=(AFD*)malloc(sizeof(AFD)); pafd->next=NULL; if(strcmp(filename,p->filename)==0) { } if(!p->next) break; puts(\"此文件已经存在了:\\n\"); return 0; p=p->next; pa=pa->next; ;58 . } bool _delete() { } bool open() { char filename[20]; unsigned int protect; pa->next=(AFD*)malloc(sizeof(AFD)); pa=pa->next; strcpy(pa->filename,filename); pa->protect=2; pa->point=0; pa->next=NULL; return 1; char filename[20]; puts(\"请输入要删除的文件名:\\n\"); scanf(\"%s\UFD *p=pufd; UFD *temp; while(p->next) { } puts(\"要删除的文件不存在!\\n\"); return 0; if(strcmp(filename,p->next->filename)==0) { } p=p->next; temp=p->next; p->next=p->next->next; free(temp); printf(\"文件%s删除成功！\\n\return 1; ;59 . puts(\"请输入要打开的文件名:\\n\"); scanf(\"%s\ puts(\"请输入要打开的文件保护类型:\\n\"); scanf(\"%d\UFD *p=pufd->next; AFD *pa=pafd->next; while(pa) { } if(!pa) pa=pafd; if(strcmp(filename,pa->filename)==0) { } if(!pa->next) break; printf(\"文件%s已经打开!\\n\return 1; pa=pa->next; while(p) { if(strcmp(filename,p->filename)==0) { } pa->next=(AFD*)malloc(sizeof(AFD)); pa=pa->next; strcpy(pa->filename,p->filename); pa->protect=protect; if(protect==1) pa->point=0; else pa->point=p->length; pa->next=NULL; printf(\"文件%s已经打开!\\n\return 1; ;60 . } void close() { char filename[20]; UFD *pu=pufd->next; puts(\"请输入要关闭的文件名:\\n\"); scanf(\"%s\AFD *p=pafd; AFD *temp; while(p&&p->next) { if(strcmp(filename,p->next->filename)==0) { } } p=p->next; puts(\"要打开的文件不存在!\\n\"); return 0; temp=p->next; p->next=p->next->next; if(temp->protect==2) { } free(temp); printf(\"文件%s关闭成功!\\n\return ; while(pu) { } if(strcmp(temp->filename,pu->filename)==0) { } pu=pu->next; pu->length=temp->point; break; ;61 . } int read() { } int write() { char filename[20]; unsigned int length; AFD *p=pafd->next; puts(\"请输入要写的文件名:\\n\"); scanf(\"%s\while(p) { } p=p->next; puts(\"要关闭的文件没有别打开!\\n\"); char filename[20]; unsigned int length; AFD *p=pafd->next; puts(\"请输入要读的文件名:\\n\"); scanf(\"%s\puts(\"请输入要读的长度\\n\"); scanf(\"%d\while(p) { } puts(\"读取失败文件没有打开过!\\n\"); return 0; if(strcmp(filename,p->filename)==0) { } p=p->next; p->point+=length; printf(\"文件%s读取成功!\\n\return 1; ;62 . } void destroy() { MDF *pm=pmdf; while(pm) { } AFD *pa=pafd; while(pa) { } UFD *pu =pufd; } if(strcmp(filename,p->filename)==0) { } p=p->next; if(p->protect!=2) { } puts(\"请输入要写的长度\\n\"); scanf(\"%d\p->point+=length; printf(\"文件%s写入成功!\\n\return 1; printf(\"文件%s不可写!\\n\return 0; puts(\"写入失败文件没有打开过!\\n\"); return 0; pmdf=pmdf->next; free(pm); pm=pmdf; pafd=pafd->next; free(pa); pa=pafd; ;63 . } void saveUFD() { } void bye() { AFD *pa=pafd->next; UFD *pu=pufd->next; while(pa) { if(pa->protect==2) { while(pu) while(pu) { } pufd=pufd->next; free(pu); pu=pufd; FILE *fp; UFD *p=pufd->next; if((fp=fopen(UserUFD,\"w\"))==NULL) { } while(p) { } fclose(fp); fprintf(fp,\"%s\ fprintf(fp,\"%s%s\fprintf(fp,\"%d%s\fprintf(fp,\"%d\p=p->next; puts(\"the UFD cannot open!\\n\"); exit(1); ;64 . } void operate() { while(1) { char command[20]; char name[][8]={\"create\ \"read\ } saveUFD(); printUFD(); destroy(); } pa=pa->next; { } if(strcmp(pa->filename,pu->filename)==0) { } pu=pu->next; pu->length=pa->point; break; puts(\"请输入命令:\\n\"); scanf(\"%s\ if(strcmp(command,name[0])==0) create(); else if(strcmp(command,name[1])==0) _delete(); else if(strcmp(command,name[2])==0) open(); else if(strcmp(command,name[3])==0) close(); else if(strcmp(command,name[4])==0) read(); else if(strcmp(command,name[5])==0) ;65 . } void print() { puts(\"*******************邵佳楠1413201036****************\\n\"); puts(\"***使用说明***:\\n\"); puts(\"本文件系统共有6个用户分别是邵佳楠 user1 user2 user3 user4 user5\\n系统命令有 } write(); else if(strcmp(command,name[6])==0) { } else puts(\"无效命令，请重新输入:\\n\"); bye(); return ; create,delete,open,close,read,write,bye\\\\nbye---------------------退出系统\"); } int main() { } print(); initMDF(); checkuser(); initAFD(); operate(); return 0; ;66 因篇幅问题不能全部显示，请点此查看更多更全内容