操作系统课程设计报告

1、操作系统课程设计报告时间：2011-12-262012-01-06地点：信息技术试验中心计算机科学与技术专业2009级091班01号目录一 课程设计的目的和意义3二 进程调度算法模拟31 设计目的32 设计要求33 时间片轮转算法模拟4(1)设计要求4(2)基本实现思想4(3)流程图6(4)实现的效果图6(5)部分源代码74 先来先服务算法模拟10(1)设计要求10(2)基本实现思想及算法分析10(3)流程图11(4)实现的效果图12三 主存空间的回收与分配121 设计目的122 设计要求133 模拟算法的实现134运行效果图145源程序部分代码16四 模拟DOS文件的建立和使用191 设计目

2、的192 设计要求19(1)模拟设计DOS操作系统中磁盘文件的存储结构19(2)模拟设计便于直接存取的索引文件结构213 模拟算法的实现22(1)流程图22(2)运行效果图23五 磁盘调度241 设计目的242 设计要求243 模拟算法的实现24(1)算法分析24(2)流程图26(3)各函数的运行效果示意图30六 总结33参考文献33一 课程设计的目的和意义本次操作系统课程设计的主要任务是进行系统级的程序设计。本课程设计是操作系统原理课程的延伸。通过该课程设计，使学生更好地掌握操作系统各部分结构、实现机理和各种典型算法，加深对操作系统的设计和实现思路的理解，培养学生的系统设计和动手能力，学会分

3、析和编写程序。课程设计的实施将使学生在以下几个方面有所收获：（1） 加深对操作系统原理的理解，提高综合运用所学知识的能力；（2） 培养学生自主查阅参考资料的习惯，增强独立思考和解决问题的能力；（3）通过课程设计，培养严谨的科学态度和协作精神。 二 进程调度算法模拟1 设计目的（1）要求学生设计并实现模拟进程调度的算法：时间片轮转及先来先服务。（2）理解进程控制块的结构。（3）理解进程运行的并发性。（4）掌握进程调度算法。2 设计要求在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配

4、处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。进程是程序在处理机上的执行过程。进程存在的标识是进程控制块（PCB），进程控制块结构如下：typedef struct node char name10; /* 进程标识符 */ int prio; /* 进程优先数 */ int round; /* 进程时间轮转时间

5、片 */ int cputime; /* 进程占用 CPU 时间*/ int needtime; /* 进程到完成还需要的时间*/ int count; /* 计数器*/ char state; /* 进程的状态*/ struct node *next /*链指针*/ PCB; 系统创建一个进程，就是由系统为某个程序设置一个PCB，用于对该进程进行控制和管理，进程任务完成，由系统收回其PCB，该进程便消亡。每个进程可以有三个状态：运行状态、就绪状态和完成状态。3 时间片轮转算法模拟(1)设计要求（a）进程的调度采用时间片轮转算法。（b）设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。

6、（c）用户输入进程标识符以及进程所需的时间，申请空间存放进程 PCB信息。（d）输出的格式和上面的运行结果分析中的格式相同。时间片轮转调度，具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理器的切换工作。(2)基本实现思想(a) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程

7、控制块的格式为：进程名指针要求运行时间已运行时间状态其中，进程名作为进程的标识，假设N进程的进程名分别为Q1，Q2，Q3，Qn。指针进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。要求运行时间假设进程需要运行的单位时间数。已运行时间假设进程已经运行的单位时间数，初始值为“0”。状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“W”表示。(b) 每次运行所设计的进程调度程序前，为每个进程任意确定它的“要求运行时间”。(c) 把N个进程按顺序排成循环队列，用指针

8、指出队列连接情况。另用一标志单元记录轮到运行的进程。(d) 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。请注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。(e) 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断

9、该进程的要求运行时间与已运行时间，若该进程的要求运行时间?已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（W）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。(f) 若“就绪”状态的进程队列不为空，则重复上面的（d）和（e）的步骤，直到所有的进程都成为“结束”状态。(g) 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。(h) 为N个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程

10、名以及进程控制块的动态变化过程。(3)流程图开始输入进程总数初始化进程队列更改正在运行的进程信息runtime输出就绪进程列表输出就绪状态的进程信息指针所指的进程是否结束？N是否存在下一进程YYN跳过已结束的进程程序结束 (4)实现的效果图 main（）函数主窗口时间片转法进程运行效果(5)部分源代码typedef struct PNode struct PNode *next; / 定义指向下一个节点的指针 char nameN; / 定义进程名，并分配空间 int All_Time; int Runed_Time; char state; / 定义进程状态 Ready / End * Pr

11、oc; / 指向该PCB的指针int ProcNum; / 总进程个数void InitPCB(Proc &H) coutProcNum; / 进程总个数 int Num=ProcNum; H=(Proc)malloc(sizeof(PNode); / 建立头节点 H-next=NULL; Proc p=H; /定义一个指针 cout总进程个数为 ProcNumnext=(Proc)malloc(sizeof(PNode); coutp-namep-All_Timep-Runed_Time; p-state=R; p-next=NULL; p-next=H-next; /输出每次进程运行中的信

12、息： void DispInfo(Proc H) Proc p=H-next; do if (p-state != E) /如果该进程的状态不是End的话 cout进程名:namet总运行时间:All_Time t已运行时间:Runed_Time t状态:statenext; else p=p-next; while(p != H-next); / 整个进程链条始终完整，只是状态位有差异/ 时间片轮转法void SJP_Simulator(Proc &H) coutendlnext; while (p-All_Time p-Runed_Time) / 即未结束的进程 round+; coute

13、ndlRound round-正在运行 name 进程Runed_Time+; / 更改正在运行的进程已运行时间 DispInfo(H); / 输出此时为就绪状态的进程的信息 if (p-All_Time = p-Runed_Time) / 并判断该进程是否结束 p-state=E; flag-; coutnamenext; while (flag & p-All_Time = p-Runed_Time) p=p-next; / 跳过结束 coutendl=0;j-) for(i=0;iai+1.dt) min=ai.dt;ai.dt=ai+1.dt;ai+1.dt=min;min=ai.cp

14、utime;ai.cputime=ai+1.cputime;ai+1.cputime=min; c=;=ai+1.name;ai+1.name=c; a0.wct=a0.cputime+a0.dt;a0.zt=(float)a0.cputime;a0.dczt=a0.zt/a0.cputime;for(i=1;iai-1.wct)ai.wct=ai.dt+ai.cputime;ai.zt=(float)ai.cputime;ai.dczt=ai.zt/ai.cputime;elseai.wct=ai-1.wct+ai.cputime;ai.zt=(float)(ai

15、.wct-ai.dt);ai.dczt=ai.zt/ai.cputime;开始(3)流程图选择服务菜单按要求输入进程数，建立进程队列ai.dtai+1.dt？NYai.wct=ai.dt+ai.cputime;ai.zt=(float)ai.cputime;ai.dczt=ai.zt/ai.cputime;min=ai.dt;ai.dt=ai+1.dt;ai+1.dt=min；min=ai.cputime;ai.cputime=ai+1.cputime;ai+1.cputime=min; c=;=ai+1.name;ai+1.name=c;平均周转时间：sum1/n

16、平均带权周转时间：sum2/n输出服务结果队列表等信息结束(4)实现的效果图三 主存空间的回收与分配1 设计目的主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机系统的性能。主存分配是指在多道作业和多进程环境下，如何共享主存空间。主存回收是指当作业执行完毕或进程运行结束后将主存空间归还给系统。主存分配与回收的实现是与主存储器的管理方式有关。本次设计主要是为了帮助学生深入理解主存空间的分配与回收的几种算法。（1）掌握最先适应分配算法（2）掌握最优适应分配算法（3）掌握最坏适应分配算法2 设计要求用户提出内存空间请求，系统根据申请者要求，按照最先适应分

17、配算法的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者，当程序执行完毕时，系统要收回它所占用的内存空间。建立空闲数据文件，空闲区数据文件包括若干行，每行有两个字段：起始地址、内存块大小（均为整数），各字段以逗号隔开。下面是一个空闲区数据文件的示例：0，10 10，08 18，10 28，06 34，10 44，09 读取空闲区数据文件，建立空闲区表并在屏幕上显示空闲内存状态，空闲区表记录了可供分配的空闲内存的起始地址和大小，用标志位指出该分区是否是未分配的空闲区。接收用户的内存申请，格式为：作业名、申请空间的大小。按照内存分配算法中的一种方法选择一个空闲区，分割并分配，修改

18、空闲区表，填写内存已分配区表（起始地址、长度、标志位），其中标志位的一个作用是指出该区域分配给哪个作业。进程结束后回收内存。空闲区表的结构如下：typedef struct node int start; int length; char tag20; job; 本次设计要求完成如下算法：（1）设计一个内存分配回收的程序使用最先适应分配算法（2）设计一个内存分配回收的程序使用最优适应分配算法（3）设计一个内存分配回收的程序使用最坏适应分配算法用户提出内存空间请求，系统根据申请者要求，选择上述算法的一种分配策略分析内存空间的使用情况，找出合适的空闲区，分给申请者，当进程执行完毕时，系统收回它所占

19、用的内存空间。3 模拟算法的实现 运行结果分析按照自己编写的测试文件的内容，先分析一下算法应该是一个什么样的执行效果，然后实际运行程序验证一下自己的分析结果，另外还可以通过修改测试文件中的数据来看看程序运行的情况。（1） 最先适应分配算法 算法分析：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止；然后再按作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。（2） 最优适应分配算法 算法分析：最佳 是指每次为作业分配内存时，总是把能满足要求、又是最小的空间分区分配给作业，避免“大材小用”。为了加速

20、寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链，这样第一次找到的能满足要求的空闲区必然是最佳的。（3） 最坏适应分配算法算法分析：该算法要扫描整个空闲分区表，总是挑选一个最大的空闲区分给作业使用，其优点是可是剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应适应分配算法查找效果最高。4运行效果图 最先适应分配算法 首次循环适应分配算法 最坏适应分配算法5源程序部分代码 （1） struct fq/*分区链的结构*/ int link; /*指向前一个空闲分区块或者后一个空闲分区块*/ int size; /*空闲分区的大小*/*p=NULL;t

21、ypedef struct fq FQ;int insert(int first,int fqsize)/*构造空闲分区时插入空闲分区*/ int tmp,tmp1,a; if(freeslink=-1; /*因为是第一个,前向指针为-1*/ p-size=fqsize; /*printf(%d,(char*)p-memfirst); */ p=(FQ*)(memfirst+first+fqsize-sizeof(FQ); p-size=fqsize; p-link=-1; /*因为是第1个,所以后向指针也为-1*/ return 1; else/*空闲分区不是应该插入到最前面*/ tmp=f

22、rees; p=(FQ*)(memfirst+frees); p=(FQ*)(memfirst+frees+p-size)-1; tmp1=p-link; while(firsttmp1&tmp1!=-1)/*找到应该插入的位置*/ p=(FQ*)(memfirst+tmp1); p=(FQ*)(char*)p+p-size)-1; tmp=tmp1 ; tmp1=p-link; make()/*初始化空闲分区链*/ int first,fqsize; char yn; printf(请输入内存的空间大小（字节为单位）：); scanf(%d,&memsize); memfirst=getpc

23、h(char,memsize); printf(=下面开始构造空闲分区=n); while(1) printf(请输入空闲分区的首地址：); scanf(%d,&first); if(first0)/*判断首地址是否合法*/ printf(首地址不能小于0!请重新输入!n); continue ; printf(请输入空闲分区的大小：); scanf(%d,&fqsize); if(fqsizesize)-1; next=hou-link ; while(next!=-1) printf(%dtt%dn,(char*)p-memfirst,p-size); p=(FQ*)(memfirst+h

24、ou-link); hou=(FQ*)(char*)p+p-size)-1; next=hou-link; printf(%dtt%dn,(char*)p-memfirst,p-size)int freemem()/*回收内存*/ char yn; int first,size,res; FQ *tmp1,tmp2; printf(请输入要回收的内存的首址:); scanf(%d,&first); printf(请输入要回收的内存的大小:); scanf(%d,&size); res=insert(first,size); if(res=1) printf(首址为:%d,大小为:%d有内存已成

25、功回收!n,first,size); return 1; return -1;int requestmen()/*分配内存*/ int size; FQ *tmp,*tmp1; printf(请输入要分配的内存大小:); scanf(%d,&size); if(sizememsize) printf(要分配的内存大小太大或太小!n); return ; p=(FQ*)(memfirst+frees); tmp=p; p=(FQ*)(char*)p+p-size)-1; if(p-size=size) if(p-size-size=2*sizeof(FQ)/*如果剩余空间大于2倍的FQ的大小,就

26、把前面部分分配出去*/ p-size=p-size-size; size=p-size;/*保存新的空闲分区大小*/ tmp1=(FQ*)(char*)(+p)-size); tmp1-size=size; tmp1-link=-1; frees=(char*)tmp1-memfirst; return (char*)tmp-memfirst; else/*如果剩余空间小于2倍的FQ的大小,就把整个空闲分区分配出去*/ frees=p-link; return (char*)tmp-memfirst; while(p-sizelink!=-1) p=(FQ*)(memfirst+p-link)

27、; tmp=p; p=(FQ*)(char*)p+p-size)-1; if(p-size=size) if(p-size-size=2*sizeof(FQ) p-size=p-size-size; size=p-size;/*保存新的空闲分区大小*/ tmp1=(FQ*)(char*)(+p)-size); tmp1-size=size; tmp1-link=tmp-link; p=(FQ*)(memfirst+tmp-link); p-link=(char*)tmp1-memfirst; return (char*)tmp-memfirst; main() char yn; int res

28、; make(); display(); while(1) getchar(); printf(是否分配内存(Y/N)?); scanf(%c,&yn); if(yn=y|yn=Y) res=requestmen(); if(res=-1) printf(分配失败!n); else printf(分配成功!分配的首址为:%dn,res); display(); （2）使用首次适应算法的模拟,使用空闲分区链*/struct fq/*分区链的结构*/ int link; /*指向前一个空闲分区块或者后一个空闲分区块*/ int size; /*空闲分区的大小*/*p=NULL;typedef st

29、ruct fq FQ;int insert(int first,int fqsize)/*构造空闲分区时插入空闲分区*/ int tmp,tmp1,a; if(freeslink=-1; /*因为是第一个,前向指针为-1*/ p-size=fqsize; p=(FQ*)(memfirst+first+fqsize-sizeof(FQ); /*在空闲分区的尾部来记录该空闲分区的信息和前向指针*/ p-size=fqsize; p-link=-1; /*因为是第1个,所以后向指针也为-1*/ return 1; else if(firstfrees) printf(空闲分区有部分重叠!); ret

30、urn -1; if(first+fqsize=frees) p=(FQ*)(memfirst+frees); p=(FQ*)(memfirst+frees+p-size)-1; p-size=p-size+fqsize; tmp=p-size; p=(FQ*)(memfirst+first); p-size=tmp; p-link=-1; frees=first; return 1; p=(FQ*)(memfirst+first); p-size=fqsize; p-link=-1; p=(FQ*)(memfirst+first+fqsize)-1; p-size=fqsize; p-lin

31、k=frees; p=(FQ*)(memfirst+frees); p-link=first+fqsize-sizeof(FQ); frees=first; return 1; if(first+fqsize=tmp1) p=(FQ*)(memfirst+tmp1); a=p-link;/*保存前一空闲分区的尾部*/ p=(FQ*)(memfirst+tmp1+p-size)-1; p-size=p-size+fqsize; fqsize=p-size;/*保存当前的大小*/ p=(FQ*)(memfirst+first); p-size=fqsize; p-link=a; p=(FQ*)(m

32、emfirst+a); p-link=first; return 1; p-link=first; tmp=(char*)p-memfirst; p=(FQ*)(memfirst+first); p-size=fqsize; p-link=tmp; p=(FQ*)(memfirst+first+p-size)-1; p-size=fqsize; p-link=tmp1; tmp=(char*)p-memfirst; p=(FQ*)(memfirst+tmp1); p-link=tmp; return 1; return -1;make() int first,fqsize; char yn;

33、printf(请输入内存的空间大小（字节为单位）：); scanf(%d,&memsize); memfirst=getpch(char,memsize); printf(=下面开始构造空闲分区=n); while(1) printf(请输入空闲分区的首地址：); scanf(%d,&first); if(first0) printf(首地址不能小于0!请重新输入!n); continue ; printf(请输入空闲分区的大小：); scanf(%d,&fqsize); if(fqsizesize)-1; next=hou-link ; while(next!=-1) printf(%dtt

34、%dn,(char*)p-memfirst,p-size); p=(FQ*)(memfirst+hou-link); hou=(FQ*)(char*)p+p-size)-1; next=hou-link; printf(%dtt%dn,(char*)p-memfirst,p-size);int freemem()/*回收内存*/ char yn; int first,size,res; FQ *tmp1,tmp2; printf(请输入要回收的内存的首址:); scanf(%d,&first); printf(请输入要回收的内存的大小:); scanf(%d,&size); res=inser

35、t(first,size); if(res=1) printf(首址为:%d,大小为:%d有内存已成功回收!n,first,size); return 1; return -1;int requestmen() int size,f,l; FQ *tmp,*tmp1; printf(请输入要分配的内存大小:); scanf(%d,&size); if(sizememsize) printf(要分配的内存大小太大或太小!n); return ; p=(FQ*)(memfirst+current); tmp=p; p=(FQ*)(char*)p+p-size)-1; while(p-sizelink!=current)/*找到合适分配的