操作系统(一个小型操作系统地设计与实现)课程设计

1、文案大全南通大学计算机科学与技术学院操作系统课程设计报告专业：学生姓名：学号：时间：操作系统模拟算法课程设计报告设计要求将本学期三次的实验集成实现:处理机管理；存储器管理；虚拟存储器的缺页调度。设计流程图主流程图A.处理机调度1）先来先服务FCFS先来先服务算法流程2）时间片轮转法开始输入进程总数输入各进程信息输出为就绪状态的进程的信息指针所指的进程是-.否结束更改正在运行的进程的已运行时间跳过已结束的程序输出此时为就绪状态的进程的信息-如果存在下一个进程的话N结束指向下一个进程时间片轮转算法流程图B.存储器管理（可变式分区管理）1）首次适应法分配流程图首次适应算法回收流程图输入完成进程的标号

2、前一个空闲区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个空闲分区，且p的前一个空闲分区大小更改为加上p的大小再加上p的后一个空闲分区的大小，合并后的这个空闲区的后向指针指向p的下下个分区，如果p的下下个分区不为空，则其前向指针指向合并后的这个空闲区，释放p和p的下一个分区2）最佳适应法回收内存流程C.虚拟存储器的缺页调度1）先进先出FIFOFIFO淘汰算法流程2)LRU实现原理LRU淘汰算法流程主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。处理机调度1）先来先服务FCFS（一）任务先来先服务的调度算法实现处理机调度。（二）要求实现对FC

3、FS算法的模拟实现计算出该算法的平均作业周转时间、平均带权作业周转时间。（三）原理按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行（四）数据结构structtaskstructcharname;/*进程名称*/intnumber;/*进程编号*/floatcome_time;/*到达时间*/floatrun_begin_time;/*开始运行时间*/floatrun_time;/*运行时间*/floatrun_end_time;/*运行结束时间*/intpriority;/*优先级*/intorder;/*运行次序*/intrun_flag;/*调度标志*/tasksM

4、AX;intfcfs（）/*先来先服务算法*/进程名链接指针到达时间估计运行时间进程状态进程控制块结构（五）实现方法建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。（六）运行界面测试数据：作业名到达时间运行时间A028B09C03执行FCFS算法如下:C:ProgramFilesMicrosoftVisualStudioMyPrqjectscxiDebugcxl.exe操布系统课程设讦1处理机管理2存储器管理3.缺页调度先来先服务算法2.时间片轮转算法囂返回开始菜单A528533128B79334223SC834245337恒业名到达时

5、间运行时间开始时间停止时间运行次序周转时间5.74074靈时间片轮转法储器管理3.缺页调度片间是否相等，若相等则表示进程结束，进程退出调度，释放资源。（二）要求实现对RR算法的模拟实现显示执行完一个时间片的结果。（三）原理时间片轮转算法中，系统将所有的就程序按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。（四）数据结构/初始状态每个进程均为运行态/初始时进程均不占用cpu/用num来限制循环的次数temp-s

6、tate=R;tempallocation=0;num+二tempneed_time;（五）实现方法-处理器调度总是选择标志单元指示的进程运行。执行:已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。当一个进程被选中运行时，必须设置该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间,实用文档实用文档文案大全处理机管理2-存储器管聂缺页调度若该进程的要求运行时间已运行时间，则表示它尚未执行结束，

7、应待到下一轮时再运行。若该进程的要求运行时间二已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。进程名链接指针到达时间估计运行时间进程状态进程控制块结构（六）运行界面测试数据:作业号执行时间/sA1B2C1执行时间片轮转算法RR如下:C1B2占用cpu时间7A占用cpu时间is2s区M余时间Q0理ABC占用CJH1时间isisIsM余时间Q1远ABC占用cpu时间is0sIsm余时间Q2赶个王ABC占用cpu时间0S0SIs菊除时间12赶1-处理机管理2-存储器管理M缺页调度先来先服务算法2-时间片轮转算

8、法3.返回开始菜单禺C:Program1、炎时-4口昱交禾fl1）首次适应法（一）任务通过采用首次适应算法实现内存的分配与回收，并可以查看和显示当前内存现状。（二）要求实现对FF算法的模拟实现输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入已运行的进程ID。（三）原理FF算法要求空闲链已地址递增的次序连接。分配内存时，从链首开始顺序查找,直到找到第一个满足要求的空间并分配给进程，把分配后余下的空间仍然留在链表中。若从链首至链尾都不满足要求，则分配失败。该算法倾向于优先使用低地址的空间。（四）数据结构intconstMEMO=256;/初始化常类型MEMO,用MEMO表示内存大小（

9、常类型的变量或对象的值是不能被更新的）structFreeMemoryintID;intStartAdd;intSize;boolState;/定义state为布尔型变量，其值只有真（TRUE）和假（FALSE）FreeMemory*Next;FreeMemory*AllocTable二newFreeMemory;/建立全局管理表用于内与回收FreeMemory*PtrforCycleFit二AllocTable;/为循环首次适应定义的指针，此指针用于指向当前查找的起始地址；/初始化内存函数voidMemoryInit（FreeMemory*&tempAdd）tempAdd-ID=O;/初始化

10、当前进程为空tempAdd-Size二MEMO;/初始化可分配空间为内存大小tempAdd-StartAdd=0;/初始化起始地址为0tempAdd-State二false;/初始化状态为未分配tempAdd-Next二NULL;/初始化下一个进程也为空/反馈内存现态voidDispMemory（）FreeMemory*temp二AllocTable;/全局管理表反映内存状态cout系统总内存：MEMONext）cout进程ID：ID大小：Size起始地址：StartAdd是否已分配：StateNext）/*回收操作，回收过程中，要用到三个指针，上一个Last，当前temp，下一个temp-n

11、ext当temp指向表头或表尾时需要特殊考虑*/当要退出工作时,就要回收此退出的工作由执行函数调用voidEndJob（intid）Free_Memory（id）;（五）实现方法空闲区设置为双向链表，其双向链的分区格式为:0（状态位）分区大小（N+2）向前指针大小为N的已分配区或空闲区0（状态位）分区大小（N+2）向后指针（六）运行界面测试数据如下：进程123456所需内存2534451213100111-nJ1:己己己tEH:己己fEnfEnfEnl丁乎已已噩SE否59021025111:.IL=i:匕ik=i=.J.-!T地地地地地地舒厶口厶口厶口厶口厶口A口女鷲蠢席起:大大大大大大大12

12、34560圣.忌ID:ID:ID:ID:ID:ID:ID:迤0丄2呈呈呈呈呈呈呈忖:壬|壬|壬|壬|壬|壬|禾-若回收进程4,执行结果如下:0011nJ1:THUnr-JuffiH:-Ju-Ju比已已託託託否鑫590121025111:起始地址主起始地址主起始地址主起始地址主起始地址主起始地址2起始地址754523012341111652LP、存内择H心IDIDIDIDIDIDID选0丄2E亠亠口王口王口王口王口王口王-乍执行最佳适应算法为其分配内存如下:C.虚拟存储器的缺页调度1）先进先出FIFO（一）任务采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。（

13、二）要求1.实现对FIFO算法的模拟实现2输出每次执行的结果。（三）原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。（四）数据结构voidFIFO（）intlength;intfifo100=0;intpageLength;TxTxTxTxTxTxTxTxTxTxTxTxTx出算法intfifoPage100=0;inti,j;coutvv11TT平平平平平平平平平平平平平平平平平平平平平平平平平平八*an/IpageLength=3;length=9;for(i=1;iv=length;

14、i+)intflag=0;for(j=1;jv=pageLength;j+)if(fifoi=fifoPagej)flag=1;j=pageLength+1;elseif(fifoPagej=0)fifoPagej=fifoi;j=pageLength+1;flag=1;if(flag=1)elsecoutvvf淘汰vvfifoPage1vvendl;for(j=1;j0;cc-)lruPagecc=lruPagecc-1;lruPage1=lrui;flag=1;j=pageLength+1;elseif(lruPagej=0)for(intvv=j;vv0;vv-)lruPagevv=lr

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

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

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

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

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

20、time_temp=tasksO.come_time;for(i=O;ivcounter;i+)tasksi.run_begin_time=time_temp;tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time;tasksi.run_flag=l;time_temp=tasksi.run_end_time;number_schedul=i;tasksnumber_schedul.order=i+1;fcfsoutput();return0;intfcfsinput()task_structtt;inti,j;初始化进程数count

21、er=3;初始化每个到达系统的时间为5、7、e_time=rand()%9;e_time=rand()%9;e_time=rand()%9;for(i=1;iv3;i+)for(j=0;jv3-i;j+)if(e_timetasksj+e_time)tt=tasksj;tasksj=tasksj+1;tasksj+1=tt;初始化每个进程估计运行的时间tasks0.run_time=28;tasks1.run_time=9;tasks2.run_time=3;初始化每个进程的名字tasksO.name=A;=B;=C;J.-ft1*1*1*1*1*1

22、*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*coutname,A);if(i=l)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;p=head;

23、coutvvendlvv初始时刻：vvendl;coutvv进程vvtvv剩余时间vvtvv占用cpu时间vvendl;while(p!=tail)coutvvvvp-namevvtvvvvp-need_timevvtvvtvvp-allocationvvsvvendl;p=p-next;coutvvvvtail-namevvtvvvvtail-need_timevvtvvtvvp-allocationvvsvvendl;node*q;intlabel=1;intm=1;while(label=1&mv=num)coutvvendl;label=0;while(!p-need_time)p=p

24、-next;if(p-need_time)p-need_time-;p-allocation+;if(p-need_time=O)p-state=E;label=l;p=p-next;coutvv执行vvmvv秒后：vvendl;q=head;coutvv进程垃剩余时间北namevvtvvvvq-need_timevvtvvtvvq-allocationvvsvvendl;q=q-next;coutvvvvtail-namevvtvvvvtail-need_timevvtvvtvvq-allocationvvsvvendl;m+;coutvvendlvv;return0;intconstMEM

25、O=256;/初始化常类型MEMO，用MEMO表示内存大小（常类型的变量或对象的值是不能被更新的）structFreeMemoryintID;intStartAdd;intSize;boolState;/定义state为布尔型变量，其值只有真（TRUE）和假（FALSE）FreeMemory*Next;FreeMemory*AllocTable=newFreeMemory;/建立全局管理表用于内存分配与回收FreeMemory*PtrforCycleFit=AllocTable;/为循环首次适应定义的指针，此指针用于指向当前查找的起始地址；初始化内存函数voidMemoryInit(FreeM

26、emory*&tempAdd)tempAdd-ID=O;/初始化当前进程为空tempAdd-Size=MEMO;初始化可分配空间为内存大小tempAdd-StartAdd=O;/初始化起始地址为0tempAdd-State=false;初始化状态为未分配tempAdd-Next=NULL;/初始化下一个进程也为空反馈内存现态voidDispMemory()FreeMemory*temp=AllocTable;/全局管理表反映内存状态coutvv系统总内存：vvMEMOvvendl;for(;temp;temp=temp-Next)coutvv进程ID:ID大小：SizeStartAddvvvv

27、是否已分配:vvtemp-Statevvendl;/输出内存的各个变量分区排序voidSortPartition(boolorder)/在此使用的是快速排序算法FreeMemory*templ=AllocTable;FreeMemory*temp2=AllocTable;FreeMemory*Last1=temp1;FreeMemory*Last2=temp2;if(temp2-Next)temp2=temp2-Next;switch(order)case1:/升序部分for(;temp1;temp1=temp1-Next)for(;temp2;temp2=temp2-Next)if(temp

28、1-Sizetemp2-Size)&!temp1-State&!temp2-State)/找到符合条件的，则交换Lastl-Next=temp2;Last2-Next=templ;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-Stat

29、e)找到符合条件的，则交换Last1-Next=temp2;Last2-Next=temp1;FreeMemory*temp=temp2-Next;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-Nex

30、t)if(TrySizeSize&!temp-State)第一个满足条件的分区已找到if(TrySize=temp-Size)/刚好和申请的大小一致temp-ID=id;保持不变temp-Next,Size,StartAdd都不用变temp-State=true;值为真表示已分配else/比所找到的要小，贝懦要将其拆分FreeMemory*Newltem=newFreeMemory;NewItem-Next=temp-Next;Newltem-ID=O;NewItem-Size=temp-Size-TrySize;NewItem-StartAdd=temp-StartAdd+TrySize;N

31、ewItem-State=false;temp-ID=id;temp-Size=TrySize;temp-State=true;temp-Next=NewItem;returntrue;/endforreturnfalse;boolAlloc_BestFit(intid,intTrySize)/查找满足此条件的xl=TrySizeNext)temp=temp-Next;for(;temp;temp=temp-Next)if(TrySizeSize&!temp-State)第一个满足条件的分区已找到if(TrySize=temp-Size)/刚好和申请的大小一致temp-ID=id;保持不变te

32、mp-Next,Size,StartAdd都不用变temp-State=true;值为真表示已分配else/比所找到的要小，贝懦要将其拆分FreeMemory*NewItem=newFreeMemory;NewItem-Next=temp-Next;NewItem-ID=0;NewItem-Size=temp-Size-TrySize;NewItem-StartAdd=temp-StartAdd+TrySize;NewItem-State=false;temp-ID=id;temp-Size=TrySize;temp-State=true;temp-Next=NewItem;returntru

33、e;/endforreturnfalse;boolAlloc_Memory(intid,intAlgorithm,intTrySize)/对算法进行选择switch(Algorithm)case1:returnAlloc_FirstFit(id,TrySize);break;case2:returnAlloc_BestFit(id,TrySize);break;default:coutvv你没有指定算法,系统将默认为首次适应算法!vvendl;returnAlloc_FirstFit(id,TrySize);/*EndMemoryAlloc内存分配区操作定义完成*/*RecycleMemory

34、回收内存*/boolFree_Memory(intid)FreeMemory*temp=AllocTable;FreeMemory*Last=temp;if(temp-ID=id)考虑第一条记录的特殊情况if(temp-Next&!temp-Next-State)下一分区没有被占用，将与本条合并temp-ID=0;temp-Size=temp-Size+temp-Next-Size;temp-State=O;回收Last=temp-Next;temp-Next=temp-Next-Next;deleteLast;else/只有第一分区为空，则清除相关表项的数据temp-ID=0;temp-St

35、ate=false;改为没有使用状态returntrue;特殊情况第一条if(temp-Next)temp=temp-Next;for(;temp;temp=temp-Next)/*回收操作，回收过程中，要用到三个指针，上一个Last，当前temp，下一个temp-next当temp指向表头或表尾时需要特殊考虑*/if(temp-ID=id)/begin找到该ID表项if(temp-Next)没有到最后一条if(!Last-State&!temp-Next-State)/回收区与插入点的前、后两个分区邻接优先级为1Last-Next=temp-Next-Next;Last-Size=Last-

36、Size+temp-Size+temp-Next-Size;deletetemp-Next;deletetemp;elseif(!Last-State)回收区与插入点的前一个分区相邻接优先级为2Last-Next=temp-Next;Last-Size=Last-Size+temp-Size;deletetemp;elseif(!(temp-Next-State)回收区与插入点的后一个分区相邻接优先级为3/if(temp-Next-Next)Last=temp-Next-Next;/else/Last=NULL;temp-Size=temp-Size+temp-Next-Size;temp-S

37、tate=false;temp-ID=O;FreeMemory*tempfor=temp-Next;temp-Next=Last;deletetempfor;else/回收区为独立单位.优先级为4temp-ID=0;temp-State=false;/最后一条elseif(!Last-State)最后一条的前一条为空Last-Size=Last-Size+temp-Size;Last-Next=NULL;deletetemp;else/最后一条的前一条不为空temp-ID=0;temp-State=O;returntrue;/end找到该ID表项此类情况处理完毕Last=temp;/endfo

38、rreturnfalse;/*MemoryRecycled内存分配完毕Alldone,thejobreferedwillleavesystem*/当进程开始时,就应该为之分配内存voidBeginJob(intid,intAlgorithm,intTrySize)Alloc_Memory(id,Algorithm,TrySize);当要退出工作时,就要回收此退出的工作由执行函数调用voidEndJob(intid)Free_Memory(id);voidFIFO()intlength;intfifo100=0;intpageLength;intfifoPage100=0;inti,j;cout

39、vvpageLength=3;length=9;coutvv时刻tvvt;for(i=O;ivlength;i+)coutvvivvt;coutvvendlvv引用串vvt;for(i=1;iv=length;i+)fifoi=rand()%5+1;coutvvfifoivvt;for(i=1;iv=length;i+)intflag=0;for(j=l;jv=pageLength;j+)if(fifoi=fifoPagej)flag=1;j=pageLength+1;elseif(fifoPagej=0)fifoPagej=fifoi;j=pageLength+1;flag=1;if(flag=1)elsecoutvvf淘汰vvfifoPage1vvendl;for(j=1;j=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;coutvvendlvvt=vvi-1vv时vvt;for(intjk=1;jkv=pageLength;jk+)coutvvPvvjkvvt;coutvvendlvvt;for(ints=1