操作系统一个小型操作系统的设计与实现课程设计

1、南通大学计算机科学与技术学院操作系统课程设计报告专业：学生姓名：学号：时间：操作系统模拟算法课程设计报告设计要求将本学期三次的实验集成实现：A. 处理机管理；B. 存储器管理；C. 虚拟存储器的缺页调度。设计流程图主流程图处理机管理开始的图形界面存储器管理先首最来时次佳A. 处理机调度间先1) 先来先服务 FCFS适适服片开始应应务轮法法初始化进程控制块，让进程转调度数组中首个进程，并计算并打印进程的完成时刻、周更改转计时时间器、的带当权前周时转间时间, 即下一刻进程的缺页调度先LR进U先算出法N数组为空Y结束先来先服务算法流程2) 时间片轮转法时间片轮转算法流程图B. 存储器管理 ( 可变式

2、分区管理）1) 首次适应法分配流程图延链查找否到链作业等待是开申请 xkb 内由链头找到第一个空小于分区大小 xkb ？等于大于分区大小 =分将该空闲区从区大小 -xkb ，链中摘除：修修改下一个空改下一个空闲闲区的后向指区的后向地址返登记已分配返回分配给进程的内存首次适应算法回收流程图开始输入完成进程的标号在分配区表中查找释放区 p 下邻分区空前一个空闲区的后向指针指向 p 的后一个分区， p 的后一个分区的前向指针指向p的前一个分区，且p的前一个分区大小更改为加上 p 的大小，释放 p释放区 p 上下均邻空闲区前一个空闲区的后向指针指向p 的后一个空闲分区，p 的后一个空闲分区的前向指针指

3、向p的前一个空闲分区，且p 的前一个空闲分区大小更改为加上p 的大小再加上p 的后一个空闲分区的大小，合并后的这个空闲区的后向指针指向p 的下下个分区，如果p 的下下个分区不为空，则其前向指针指向合并后的这个空闲区，释放p和 p 的下一个分区释放区 p 上邻分区空前一个分区的后向指针指向 p 的后一个空闲分区， p 的后一个空闲分区的前向指针指向 p 的前一个分区，且 p 的后一个分区大小更改为加上p的大小释放区 p 上下均不邻空闲区将 p 放在链首，2）最佳适应法回收内存流程C. 虚拟存储器的缺页调度1) 先进先出 FIFO开始开始 FIFO的缺页T释放分区与上F空闲分区相邻查主存分块表T释

4、放分区与下FY释放分区与下F空闲分区相邻有空闲空闲分区相邻分配一T摘除链表中上下分摘除链表中上分摘除链表中下分区。合并这三个分区。合并释放分区区。合并释放分区区，将上空闲区长与上分区，将上空与下分区，将释放度修改为三个分区闲区长度修改为这分区中长度修改为的长度。二分区的长度。这二分区的长度。将合并的或释放的分区按长度升序重新插入到自由链表中。NJ=pHEAD结束NJ 的修改Y输出“将 J 页复写入交输出“装入L调整 FIFO 队列，将 L 插修改主存分块表和终止2）LRUFIFO 淘汰算法流程开始 LRU的缺页查主存分块表Y有空闲分配一N找到栈底元素：NJ 的修改Y输出“将 J 页送到入交输出

5、“装入L调整堆栈，使HEAD所指修改主存分块表和实现原理主界面终止LRU淘汰算法流程设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。A. 处理机调度1) 先来先服务 FCFS （一）任务先来先服务的调度算法实现处理机调度。（二）要求1. 实现对 FCFS算法的模拟实现2. 计算出该算法的平均作业周转时间、平均带权作业周转时间。（三）原理按作业到达 CPU时间先后顺序进行非剥夺式调度，先到达 CPU的作业先被执行。（四）数据结构structtask_structcharname;/*进程名称 */intnumber;/*进程编号 */floatcome_time;/*到达时间

6、*/floatrun_begin_time;/*开始运行时间 */floatrun_time;/*运行时间 */floatrun_end_time;/*运行结束时间 */intpriority;/*优先级 */intorder;/*运行次序 */intrun_flag;/*调度标志 */tasksMAX;intfcfs()/*先来先服务算法 */进程名链接指针到达时间估计运行时间进程状态进程控制块结构（五）实现方法建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。（六）运行界面测试数据：作业名到达时间运行时间A028B09C03执行 FC

7、FS算法如下：2) 时间片轮转法（一）任务只对进程的运行模拟，将其运行时间加一，判断要求运行时间与已运行时间是否相等，若相等则表示进程结束，进程退出调度，释放资源。（二）要求1. 实现对 RR算法的模拟实现2. 显示执行完一个时间片的结果。（三）原理时间片轮转算法中，系统将所有的就程序按先来先服务的原则排成一个队列，每次调度时，把 CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。（四）数据结构temp-state=R;/初始状态每个进程均为运行态temp

8、-allocation=0; / 初始时进程均不占用 cpu num+=temp-need_time;/ 用 num来限制循环的次数（五）实现方法处理器调度总是选择标志单元指示的进程运行。执行：已运行时间 +1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。当一个进程被选中运行时，必须设置该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间 已运行时间，则表示它尚未执行结束，应待到下

9、一轮时再运行。若该进程的要求运行时间 =已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。进程名链接指针到达时间估计运行时间进程状态进程控制块结构（六）运行界面测试数据：作业号执行时间 /sA1B2C1执行时间片轮转算法RR如下：B. 存储器管理 ( 可变式分区管理）1) 首次适应法（一）任务通过采用首次适应算法实现内存的分配与回收，并可以查看和显示当前内存现状。（二）要求1. 实现对 FF 算法的模拟实现2. 输入要进行分配内存的进程 ID 和相应所需内存大小，回收内存时输入已运行的进程 ID。（三）原

10、理FF 算法要求空闲链已地址递增的次序连接。分配内存时，从链首开始顺序查找，直到找到第一个满足要求的空间并分配给进程，把分配后余下的空间仍然留在链表中。若从链首至链尾都不满足要求，则分配失败。该算法倾向于优先使用低地址的空间。（四）数据结构intconstMEMO=256;/ 初始化常类型 MEMO，用 MEMO表示内存大小（常类型的变量或对象的值是不能被更新的）structFreeMemoryintID;intStartAdd;intSize;boolState;/定义 state为布尔型变量，其值只有真（TRUE)和假（ FALSE)FreeMemory*Next;FreeMemory*A

11、llocTable=newFreeMemory;/ 建立全局管理表用于内与回收FreeMemory*PtrforCycleFit=AllocTable;/为循环首次适应定义的指针，此指针用于指向当前查找的起始地址;/ 初始化内存函数 voidMemoryInit(FreeMemory*&tempAdd)tempAdd-ID=0;/ 初始化当前进程为空tempAdd-Size=MEMO;/初始化可分配空间为内存大小 tempAdd-StartAdd=0;/ 初始化起始地址为 0 tempAdd-State=false;/ 初始化状态为未分配 tempAdd-Next=NULL;/ 初始化下一个进

12、程也为空/ 反馈内存现态voidDispMemory()FreeMemory*temp=AllocTable;/ 全局管理表反映内存状态 cout 系统总内存 :MEMONext)cout 进程 ID：ID 大小： Size 起始地址 :StartAdd 是否已分配 :Stateendl; / 输出内存的各个变量（五）实现方法可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区的个数是可以调整的。当需要装入一个作业时，根据作业需要的贮存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小

13、小的分区。有的分区被分配作业占用，有的分区空闲。在空闲区表中，按空闲区首地址从低到高进行登记。当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时，要考虑相邻空间区合并问题。作业的释放区与空闲区的邻接分以下4 种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D、释放区上邻空闲区不邻接。（六）运行界面系统总内存为 256 时，分别为进程 1、2、3 分配大小为 64、 128、64 的内存。执行首次适应算法分配内存如下：若回收进程 2 的内存，执行结果如下：2）最佳适应法（一）任务通过采用最佳适应算法实现内存的分配与回收，并可以查看和显示当前内存现状

14、。（二）要求1. 实现对 BF 算法的模拟实现2. 输入要进行分配内存的进程 ID 和相应所需内存大小，回收内存时输入需要回收的内存块。（三）原理最佳适应算法扫描整个未分配表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。此算法保证不会分割一个更大的区域，使得装入大作业的要求容易得到满足，同时，通常把空闲区按长度递增顺序排列，查找时总是从最小的一个空闲区开始，直至找到满足要求的分区为止，这时，最佳适应分配算法等同于首次适应算法。此算法的主存利用率好，所找出的分区如果最好满足要求则是最合适的。（四） 数据结构intconstMEMO=256;/初始化常类型MEMO，用 MEMO表

15、示内存大小 （常类型的变量或对象的值是不能被更新的）structFreeMemoryintID;intStartAdd;intSize;boolState;/定义 state为布尔型变量，其值只有真（ TRUE)和假（ FALSE)FreeMemory*Next;boolAlloc_BestFit(intid,intTrySize)/ 查找满足此条件的x1=TrySizeNext)/* 回收操作 , 回收过程中，要用到三个指针，上一个Last, 当前 temp, 下一个 temp-next当 temp 指向表头或表尾时需要特殊考虑*/ 当要退出工作时 , 就要回收 / 此退出的工作由执行函数调

16、用voidEndJob(intid)Free_Memory(id);（五）实现方法空闲区设置为双向链表，其双向链的分区格式为：0（状态位）分区大小（ N+2）向前指针大小为 N的已分配区或空闲区0（状态位）分区大小（ N+2)向后指针（六）运行界面测试数据如下：进程123456所需内存253445121310执行最佳适应算法为其分配内存如下：若回收进程 4，执行结果如下：C. 虚拟存储器的缺页调度1) 先进先出 FIFO （一）任务采用先进先出 FIFO 算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。（二）要求1. 实现对 FIFO 算法的模拟实现2. 输出每次执行的结果。（

17、三）原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。（四）数据结构voidFIFO()intlength;intfifo100=0;intpageLength;intfifoPage100=0;inti,j;cout*先进先出算法*endl;pageLength=3;length=9;for(i=1;i=length;i+)intflag=0;for(j=1;j=pageLength;j+)if(fifoi=fifoPagej)flag=1;j=pageLength+1;elseif(fi

18、foPagej=0)fifoPagej=fifoi;j=pageLength+1;flag=1;if(flag=1)elsecout 淘汰 fifoPage1endl;for(j=1;j=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;（五）实现方法当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进程已在主存的页号，其队列头指针初始化为 0. 假设分配给每个进程的内存块数固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存入磁盘。然后要把当前访问的页装入该块，并修改页表和存储分块表的对应

19、标志。（六）运行界面测试数据：页表长度： 9；页框长度： 3；页面请求数列： 4,4,3,5,1,1,2,3,2执行先进先出 FIFO 算法结果如下：2）LRU（一）任务采用先进先出 LRU算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。（二）要求1. 实现对 LRU算法的模拟实现2. 输出每次执行的结果。（三）原理最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。

20、如果主存中已无空闲块，可采用 LRU算法进行缺页处理。（四）数据结构voidLRU()intlength;intlru100=0;intpageLength;intlruPage100=0;inti,j;cout*最近最少使用LRU算法*endl;pageLength=3;length=9;for(i=1;i=length;i+)intflag=0;for(j=1;j0;cc-)lruPagecc=lruPagecc-1;lruPage1=lrui;flag=1;j=pageLength+1;elseif(lruPagej=0)for(intvv=j;vv0;vv-)lruPagevv=lru

21、Pagevv-1;lruPage1=lrui;j=pageLength+1;flag=1;if(flag=1)elsecout 淘汰 lruPagepageLength0;j-)lruPagej=lruPagej-1;lruPage1=lrui;（五）实现方法当采用 LRU算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针，初始化为 0. 假定分配给每个进程的内存块数固定不变。当队列满需淘汰时，操作系统选择栈底元素淘汰，其他元素向下移一个位置，将新调入页放栈指针指示的栈顶。当访问的页在栈中时，还应调整页从当前位置到栈顶。（六）运行界面测试数据：页

22、表长度： 9；页框长度： 3；页面请求数列： 2,3,5,1,5,5,4,4,3执行最近最少使用LRU算法结果如下：总结与体会通过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出和最近最少使用算法有了更详尽的认识。在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该记得释放资源。从这次实验中我发现我对于 c+掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。此外我还更深入的理解了各个进程调度算法，及实现过程。在编写程序时查询了很多资料，间接提高了我的搜索能力。在此次课程

23、设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。特别是设计先来先服务调度算法和时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。对进程管理中的等待队列，就绪队列，时间片等概念有了更深刻的印象。在设计此模拟操作系统的课设中，也加深了对 c+知识的把握。解决了一些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。另外，我觉得此次课程设计虽然主要问题是在编程上，但是经过不断的去调试，还

24、是成功的调试了出来。但是这几个程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！源代码：#include#include#includeusingnamespacestd;intfcfsoutput();/*调度结果输出 */intfcfsinput();/进程参数的初始化voidkaishi();#defineMAX10structnode/建立链表来存放进程数据charname5;/进程名称intneed_time;/所需要的时间intallocation;/占用 cpu 的情况charstate;/目前的状态R为运行， E 为运行完毕node*next;/链表的尾结点;s

25、tructtask_structcharname;/* 进程名称 */intnumber;/*进程编号 */floatcome_time;/*到达时间 */floatrun_begin_time;/*开始运行时间 */floatrun_time;/*运行时间 */floatrun_end_time;/*运行结束时间 */intpriority;/*优先级*/intorder;/*运行次序*/intrun_flag;/*调度标志*/tasksMAX;intcounter;/*实际进程个数*/intfcfs()/*先来先服务算法*/fcfsinput();floattime_temp=0;inti

26、;intnumber_schedul;time_temp=e_time;for(i=0;icounter;i+)tasksi.run_begin_time=time_temp;tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time;tasksi.run_flag=1;time_temp=tasksi.run_end_time;number_schedul=i;tasksnumber_schedul.order=i+1;fcfsoutput();return0;intfcfsinput()task_structtt;

27、inti,j;/ 初始化进程数counter=3;/ 初始化每个到达系统的时间为 5、 7、 8 e_time=rand()%9; e_time=rand()%9; e_time=rand()%9; for(i=1;i3;i+)for(j=0;jtasksj+1.come_time)tt=tasksj;tasksj=tasksj+1;tasksj+1=tt;/ 初始化每个进程估计运行的时间tasks0.run_time=28;tasks1.run_time=9;tasks2.run_time=3;/ 初始化每个进程的名字tasks0.

28、name=A;=B;=C;cout*先来先服务算法*endlendl;for(i=0;icounter;i+)tasksi.run_begin_time=0;tasksi.run_end_time=0;tasksi.order=0;tasksi.run_flag=0;return0;intfcfsoutput()/*调度结果输出 */inti;floatturn_round_time=0,f1,w=0;cout 作业名到达时间运行时间开始时间停止时间运行次序周转时间endl;for(i=0;icounter;i+)f1=tasksi.run_end_

29、e_time;turn_round_time+=f1;w+=(f1/tasksi.run_time);e_timettasksi.run_timettasksi.run_begin_timettasksi.run_end_timettasksi.ordertf1tendl;cout 平均周转时间： turn_round_time/counterendl;cout 平均带权周转时间：w/counterendl;cout;return0;/*-*/intrr()intn=3,num=0;node*head=NULL;

30、node*tail=NULL;cout* *endlendl; for(inti=0;iname,A);if(i=1)strcpy(temp-name,B);if(i=2)strcpy(temp-name,C);temp-need_time=rand()%4+1;temp-state=R;/初始状态每个进程均为运行态temp-allocation=0;/ 初始时进程均不占用cpunum+=temp-need_time;/用 num来限制循环的次数if(!head)tail=head=temp;elsetail-next=temp;tail=temp;tail-next=head;node*p;

31、p=head;coutendl 初始时刻： endl;cout 进程 t剩余时间 t占用 cpu 时间 endl;while(p!=tail)coutnametneed_timettallocationsnext;coutnametneed_timettallocationsendl;node*q;intlabel=1;intm=1;while(label=1&m=num)coutneed_time)p=p-next;if(p-need_time)p-need_time-;p-allocation+;if(p-need_time=0)p-state=E;label=1;p=p-next;cou

32、t 执行 m秒后： endl;q=head;cout 进程 t剩余时间 t占用 cpu 时间 endl;while(q!=tail)coutnametneed_timettallocationsnext;coutnametneed_timettallocationsendl;m+;coutendlID=0;/初始化当前进程为空tempAdd-Size=MEMO;/ 初始化可分配空间为内存大小tempAdd-StartAdd=0;/初始化起始地址为0tempAdd-State=false;/初始化状态为未分配tempAdd-Next=NULL;/ 初始化下一个进程也为空/ 反馈内存现态voidD

33、ispMemory()FreeMemory*temp=AllocTable;/全局管理表反映内存状态cout 系统总内存 :MEMONext)cout 进程 ID ： ID大小： Size起始地址 :StartAdd是否已分配 :StateNext)temp2=temp2-Next;switch(order)case1:/升序部分for(;temp1;temp1=temp1-Next)for(;temp2;temp2=temp2-Next)if(temp1-Sizetemp2-Size)&!temp1-State&!temp2-State)/找到符合条件的，则交换Last1-Next=temp

34、2;Last2-Next=temp1;FreeMemory*temp=temp2-Next;temp2-Next=temp1-Next;temp1-Next=temp-Next;Last2=temp2;Last1=temp1;break;case0:/降序部分for(;temp1;temp1=temp1-Next)for(;temp2;temp2=temp2-Next)if(temp1-SizeSize)&!temp1-State&!temp2-State)/找到符合条件的，则交换Last1-Next=temp2;Last2-Next=temp1;FreeMemory*temp=temp2-N

35、ext;temp2-Next=temp1-Next;temp1-Next=temp-Next;Last2=temp2;Last1=temp1;/* 内存分配 */boolAlloc_FirstFit(intid,intTrySize)/定义布尔型函数Alloc_FirstFit()/ 查找一个可用第一个满足分配请求的分区，如果满足将其写入内存分配表/ 否则分配失败，返回FreeMemory*temp=AllocTable;for(;temp;temp=temp-Next)if(TrySizeSize&!temp-State)/第一个满足条件的分区已找到if(TrySize=temp-Size)/刚好和申请的大小一致temp-ID=id;/ 保持不