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

1、南通大学计算机科学与技术学院操作系统课程设计报告专 业：学生姓名：学号： 时间:操作系统模拟算法课程设计报告设计要求将本学期三次的实验集成实现:A. 处理机管理；B. 存储器管理；C. 虚拟存储器的缺页调度。设计流程图主流程图先A.处理机时度来1）先来先服务间先片服轮务转处理机管理FCFS次佳开始算并位移到首位先来先服束务算法流程厂进程到组中首个进程进程排陽组中 （计算的打印进程的首进应刻二组中 更改权周转的当前时间，八 :初始化进程控制块，适让进程控制块按适、7 f , 一一.一rvV刻、周转时间、带丿应，即下一刻进程的开始时间当前时间:=前一进程带权周转时间=数组为空/服务时间间法先缺页调

2、旷L进R先U出算法2）时间片轮转法时间片轮转算法流程图B.存储器管理（可变式分区管理） 1）首次适应法 分配流程图首次适应算法回收流程图开始输入完成进程的标号在分配区表中查找前一个分区的后向指释放区p下邻分区空释放区p上邻分区空前一个空闲区的后向 指针指向p的后一个 分区，p的后一个分 区的前向指针指向p 的前一个分区，且 p 的前一个分区大小更 改为加上p的大小， 释放p 针指向p的后一个空 闲分区，p的后一个 空闲分区的前向指针 指向p的前一个分 区，且p的后一个分 区大小更改为加上 p 的大小前一个空闲区的后向指针指向p的后一个空闲分区，p的后一 个空闲分区的前向指针指向 p 的前一个空

3、闲分区，且 p的前 一个空闲分区大小更改为加上释放区p上下均邻空闲区释放区p上下均不邻空闲区p的大小再加上p的后一个空 闲分区的大小，合并后的这个 空闲区的后向指针指向 p的下 下个分区，如果p的下下个分 区不为空，则其前向指针指向 合并后的这个空闲区，释放p和p的下一个分区将p放在链首， 并修改其状态位 为空闲2）最佳适应法回收内存流程C.虚拟存储器的缺页调度1）先进先出FIFO£开始T卜理开始FIFO的缺页中断释放分区与上释放分区与下空闲分区相邻有空闲块可用？T摘除链表中下分释放分区与下配一块闲分区相邻摘除链表中上下分区。合并这三个分区，将上空闲区长 度修改为三个分区 的长度。2

4、)LRU摘除链表中上分 区。合并释放分区与上分区，将上空 闲区长度修改为这 二分区的长度。区。合并释放分区与下分区，将释放 分区中长度修改为这二分区的长度。FIFO淘汰算法流程LRU淘汰算法流程实现原理主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。A. 处理机调度1）先来先服务FCFS（一）任务先来先服务的调度算法实现处理机调度。（二）要求1. 实现对FCFS算法的模拟实现2. 计算出该算法的平均作业周转时间、平均带权作业周转时间。（三）原理按作业到达CPU寸间先后顺序进行非剥夺式调度，先到达 CPU勺作业先被执行（四）数据结构structtask_structcha

5、rname;/* 进程名称 */ intn umber;/* 进程编号 */ floatcome_time;/*到达时间 */floatru n_begin_time;/* 开始运行时间 */ floatrun_time;/*运行时间 */floatrun_end_time;/*运行结束时间 */in tpriority;/*优先级 */intorder;/*运行次序 */intrun_flag;/*调度标志 */tasksMAX;intfcfs（）/*先来先服务算法*/进程名 链接指针 到达时间 估计运行时间 进程状态 进程控制块结构（五）实现方法 建立一个链表按照到达CPU勺时间从小到大排

6、列，只需从第一个作业（头结点） 依次调度到最后一个作业（尾结点）。（六）运行界面 测试数据：作业名到达时间运行时间A028B09C03执行FCFS算法如下:2）时间片轮转法（一）任务只对进程的运行模拟，将其运行时间加一，判断要求运行时间与已运行时 间是否相等，若相等则表示进程结束，进程退出调度，释放资源。（二）要求1. 实现对RR算法的模拟实现2. 显示执行完一个时间片的结果。（三）原理时间片轮转算法中，系统将所有的就程序按先来先服务的原则排成一个队 列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行 的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末 尾；然后

7、，再把处理机分配给就绪队列中新的队首进程，同时也让它执行 一个时间片。（四）数据结构temp->state='R'初始状态每个进程均为运行态temp->allocation=0;/初始时进程均不占用cpunum+=temp->need_time;用num来限制循环的次数（五）实现方法处理器调度总是选择标志单元指示的进程运行。执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。当一个进 程被选中运行时，必须设置该进程可以运行的时间片值，以及恢复进程的现 场，让它占有处理器运行，直到出现等待事件或运行满一个时间片进程运行一次后，应把该进程的

8、进程控制块中的指针值送到标志单元，以 指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时 间，若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结 束，应指导它的状态修改成“结束”且退出队列。此时，应把该进程的进程控 制块中的指针值送到前面一个进程的指针位置。进程名 链接指针到达时间估计运行时间进程状态进程控制块结构（六）运行界面测试数据:作业号执行时间/sA1B2C1执行时间片轮转算法RR如下:B.存储器管理（可变式分区管理） 1）首次适应法（一）任务通过采用首次适应算法实现内存的分配与回收，并

9、可以查看和显示当前内存现 状。（二）要求1. 实现对FF算法的模拟实现2. 输入要进行分配内存的进程 ID 和相应所需内存大小，回收内存时输入已运行 的进程 ID 。（三）原理FF算法要求空闲链已地址递增的次序连接。分配内存时，从链首开始顺序查 找，直到找到第一个满足要求的空间并分配给进程，把分配后余下的空间仍然 留在链表中。若从链首至链尾都不满足要求，则分配失败。该算法倾向于优先 使用低地址的空间。（四）数据结构intconstMEMO=256;初始化常类型MEMO用MEM表示内存大小（常类型的变 量或对象的值是不能被更新的）structFreeMemoryintID;intStartAdd

10、;intSize;boolState;/ 定义state为布尔型变量，其值只有真（TRUE和假（FALSE） FreeMemory*Next;FreeMemory*AllocTable=newFreeMemory;/ 建立全局管理表用于内与回收 FreeMemory*PtrforCycleFit=AllocTable;/ 为循环首次适应定义的指针，此指 针用于指向当前查找的起始地址 ;/ 初始化内存函数voidMemoryInit（FreeMemory*&tempAdd）tempAdd->ID=0;/ 初始化当前进程为空 tempAdd->Size=MEMO;初始化可分配空

11、间为内存大小 tempAdd->StartAdd=0;/ 初始化起始地址为 0 tempAdd->State=false;/ 初始化状态为未分配 tempAdd->Next=NULL;/ 初始化下一个进程也为空/ 反馈内存现态voidDispMemory（）FreeMemory*temp=AllocTable;/ 全局管理表反映内存状态cout<<" 系统总内存 :"<<MEMO<<endl;for（;temp;temp=temp->Next）cout<<" 进程 ID："<&

12、lt;temp->ID<<""<<" 大小： "<<temp->Size<<""<<" 起始地 址:"<<temp->StartAdd<<""<<"是否已分配:"<<temp->State<<endl;/ 输出内存的各个变量（五）实现方法 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的 需要，并且分区的个数是可以

13、调整的。当需要装入一个作业时，根据作业需要 的贮存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作 业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大 小小的分区。有的分区被分配作业占用，有的分区空闲。在空闲区表中，按空 闲区首地址从低到高进行登记。当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时，要考虑 相邻空间区合并问题。作业的释放区与空闲区的邻接分以下 4 种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D释放区上邻空闲区不邻接。（六）运行界面系统总内存为 256 时，分别为进程 1、 2、 3 分配大小为

14、64、 128、 64 的内存。 执行首次适应算法分配内存如下：若回收进程 2 的内存，执行结果如下：2）最佳适应法（一）任务 通过采用最佳适应算法实现内存的分配与回收，并可以查看和显示当前内存现 状。（二）要求1. 实现对BF算法的模拟实现2. 输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入需要回 收的内存块。（三）原理 最佳适应算法扫描整个未分配表或链表，从空闲区中挑选一个能满足用户进程 要求的最小分区进行分配。此算法保证不会分割一个更大的区域，使得装入大 作业的要求容易得到满足，同时，通常把空闲区按长度递增顺序排列，查找时 总是从最小的一个空闲区开始，直至找到满足要求的分

15、区为止，这时，最佳适 应分配算法等同于首次适应算法。此算法的主存利用率好，所找出的分区如果 最好满足要求则是最合适的。（四） 数据结构intconstMEMO=256;/ 初始化常类型 MEMO ，用 MEMO 表示内存大小（常类型的变量或对象的 值是不能被更新的）structFreeMemory intID;intStartAdd;intSize;boolState;/定义state为布尔型变量，其值只有真（ TRUE）和假（FALSE）FreeMemory*Next;boolAlloc_BestFit（intid,intTrySize）/查找满足此条件的 x1<=TrySize<

16、;=x2 的分区 ,然后将其放置在 x2 中，并将 x2 拆分成两个分区 SortPartition（true）;/ 使用快速排序算法，升序排序for（;temp;temp=temp->Next）/*回收操作，回收过程中，要用到三个指针，上一个Last,当前temp,下一个temp->next当temp指向表头或表尾时需要特殊考虑*/当要退岀工作时，就要回收/此退岀的工作由执行函数调用voidE ndJob（i ntid）Free_Memory（id）;（五）实现方法空闲区设置为双向链表，其双向链的分区格式为:0 （状态位）分区大小（N+2向前指针大小为N的已分配区或空闲区0 （状

17、态位）分区大小（N+2）向后指针（六）运行界面 测试数据如下：进程123456所需内存253445121310执行最佳适应算法为其分配内存如下:若回收进程4,执行结果如下:C. 虚拟存储器的缺页调度1）先进先出FIFO（一）任务采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号 和运行结果。（二）要求1. 实现对FIFO算法的模拟实现2. 输出每次执行的结果。（三）原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的 页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用 的可能性较大。（四）数据结构voidFIFO（）in tle ng

18、th;in tfifo100=0;in tpageLe ngth;in tfifoPage100=0;in ti,j;Coutvv"*先进先出算*"<<e ndrpageLe ngth=3;len gth=9;for(i=1;i<=le ngth;i+)in tflag=0;for(j=1;j<=pageLe ngth;j+) if(fifoi=fifoPagej)flag=1;j=pageLength+1;elseif（fifoPagej=0） fifoPagej=fifoi;j=pageLength+1;flag=1; if（flag=1）els

19、ecout«" t淘汰"vvfifoPage1v<endl;for（j=1;j<=pageLength;j+）fifoPagej=fifoPagej+1; fifoPagepageLength=fifoi;（五）实现方法 当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进 程已在主存的页号，其队列头指针初始化为 0. 假设分配给每个进程的内存块数 固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存 入磁盘。然后要把当前访问的页装入该块，并修改页表和存储分块表的对应标 志。（六）运行界面 测试数据： 页表长度： 9；

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

21、行缺页处理。(四) 数据结构voidLRU()intlength; intlru100=0; intpageLength; intlruPage100=0; inti,j;cout<<"I *最近最少使用 LRU 算法<<endl;*11pageLength=3;length=9;for(i=1;i<=length;i+)intflag=0;for(j=1;j<=pageLength;j+)if(lrui=lruPagej)for(intcc=j;cc>0;cc-) lruPagecc=lruPagecc-1;lruPage1=lrui;fl

22、ag=1;j=pageLength+1;elseif(lruPagej=0) for(intvv=j;vv>0;vv-) lruPagevv=lruPagevv-1;lruPage1=lrui;j=pageLength+1;flag=1;if(flag=1)elsecout«" t淘汰"<<lruPagepageLength«endl;for(j=pageLength;j>0;j-)lruPagej=lruPagej-1;lruPage1=lrui;(五) 实现方法当采用LRU算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主

23、存的 页号，为了进行页面置换，可设置一个栈指针，初始化为 0. 假定分配给每个进 程的内存块数固定不变。当队列满需淘汰时，操作系统选择栈底元素淘汰，其 他元素向下移一个位置，将新调入页放栈指针指示的栈顶。当访问的页在栈中 时，还应调整页从当前位置到栈顶。(六) 运行界面测试数据：页表长度： 9；页框长度： 3；页面请求数列： 2,3,5,1,5,5,4,4,3执行最近最少使用LRU算法结果如下：总结与体会通过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我 对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出和最近 最少使用算法有了更详尽的认识。在编程的过程中发现会用到大

24、量的指针，用 指针来操作大量的数据比较方便，但最后应该记得释放资源。从这次实验中我 发现我对于C+掌握也有所不足，程序经过了多次修改才得以完善，在以后应 该注重编程方面的训练。此外我还更深入的理解了各个进程调度算法，及实现过程。在编写程序时 查询了很多资料，间接提高了我的搜索能力。在此次课程设计过程中，对进程 的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更 进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调 度的算法都有助于对书本知识的理解和掌握。特别是设计先来先服务调度算法 和时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。对进 程管理中

25、的等待队列，就绪队列，时间片等概念有了更深刻的印象。在设计此模拟操作系统的课设中，也加深了对 C+知识的把握。解决了一 些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的 认知，也在同时提高了编程的能力，加强了实践。另外，我觉得此次课程设计 虽然主要问题是在编程上，但是经过不断的去调试，还是成功的调试了出来。 但是这几个程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收 获颇多！ 源代码：#inClude<iostream>#inClude<Cstring>#inClude<Cstddef>usingnamespaCestd;int

26、fCfsoutput();/* 调度结果输出 */intfCfsinput();/ 进程参数的初始化voidkaishi();#defineMAX10struct no de/建立链表来存放进程数据charname5;/ 进程名称 intneed_time;/ 所需要的时间 intallocation;/ 占用 cpu 的情况charstate;/目前的状态 R为运行，E为运行完毕 node*next;/ 链表的尾结点;structtask_structcharname;/* 进程名称 */ intnumber;/* 进程编号 */ floatcome_time;/* 到达时间 */ floa

27、trun_begin_time;/* 开始运行时间 */ floatrun_time;/* 运行时间 */ floatrun_end_time;/* 运行结束时间 */ intpriority;/* 优先级 */ intorder;/* 运行次序 */ intrun_flag;/* 调度标志 */tasksMAX;intcounter;/* 实际进程个数 */ intfcfs()/* 先来先服务算法 */ fcfsinput();floattime_temp=0;inti;intnumber_schedul; time_temp=e_time; for(i=0;i<c

28、ounter;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;inti,j;/初始化进程数 counter=3;/初始化每个到达系统的时间为5、 7、 8tas

29、e_time=rand()%9;e_time=rand()%9;e_time=rand()%9; for(i=1;i<3;i+)for(j=0;j<3-i;j+) if(e_time>tasksj+1.come_time) tt=tasksj; tasksj=tasksj+1;tasksj+1=tt;/初始化每个进程估计运行的时间 tasks0.run_time=28;tasks1.run_time=9;tasks2.run_time=3; /初始化每个进程的名字 ='A&

30、#39;='B'='C'cout<<"I*先来先服务算法"<<endl<<endl;for(i=0;i<counter;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<<&qu

31、ot; 作业名到达时间运行时间开始时间停止时间运行次序周转时间"<<endl;for(i=0;i<counter;i+)f1=tasksi.run_end_e_time;turn_round_time+=f1;w+=(f1/tasksi.run_time);cout<<""<<<<'t'<<""<<e_time<<'t'<<"&qu

32、ot;<<tasksi.run_time<<'t'<<""<<tasksi.run_begin_time<<'t'<<""<<tasksi.run_end_time<<'t'<<tasksi.order<<'t'<<f1<<'t'<<endl;cout<<" 平均周转时间： "<<

33、;turn_round_time/counter<<endl;cout<<" 平均带权周转时间： "<<w/counter<<endl;cout<<""return0;/*/intrr()intn=3,num=0; node*head=NULL;node*tail=NULL;cout<<"I*时间片轮转调度算法 *"<<endl<<endl;for(inti=0;i<n;i+)node*temp=newnode;if(i=0)strc

34、py(temp->name,"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;elsetai

35、l->next=temp; tail=temp;tail->next=head;node*p;p=head;cout<<endl<<" 初始时刻： "<<endl;cout<<" 进程 "<<'t'<<" 剩余时间 "<<'t'<<" 占用 cpu 时间 "<<endl; while(p!=tail)cout<<""<<p

36、->name<<'t'<<""<<p->need_time<<'t'<<'t'<<p->allocation<<'s'<<endl; p=p->next; cout<<""<<tail->name<<'t'<<""<<tail->need_time<<&#

37、39;t'<<'t'<<p->allocation<<'s'<<endl; node*q;intlabel=1;intm=1;while(label=1&&m<=num)cout<<endl;label=0;while(!p->need_time)p=p->next;if(p->need_time)p->need_time-;p->allocation+;if(p->need_time=0)p->state='E

38、9;label=1;p=p->next;cout<<" 执行 "<<m<<" 秒后： "<<endl;q=head;cout<<" 进程 "<<'t'<<" 剩余时间 "<<'t'<<" 占用 cpu 时间 "<<endl;while(q!=tail) cout<<""<<q->name&l

39、t;<'t'<<""<<q->need_time<<'t'<<'t'<<q->allocation<<'s'<<endl;q=q->next; cout<<""<<tail->name<<'t'<<""<<tail->need_time<<'t'<

40、;<'t'<<q->allocation<<'s'<<endl; m+;cout<<endl<<""return0;/*/intconstMEMO=256;/ 初始化常类型 MEMO ，用 MEMO 表示内存大小(常类型的变量或对象的 值是不能被更新的) structFreeMemoryintID;intStartAdd;intSize;boolState;/定义state为布尔型变量，其值只有真( TRUE)和假(FALSE)FreeMemory*Next;FreeMe

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

42、化状态为未分配 tempAdd->Next=NULL;/ 初始化下一个进程也为空 /反馈内存现态 voidDispMemory() FreeMemory*temp=AllocTable;/ 全局管理表反映内存状态cout<<" 系统总内存 :"<<MEMO<<endl; for(;temp;temp=temp->Next) cout<<" 进程 ID ："<<temp->ID<<""<<" 大小： "<<

43、;temp->Size<<""<<" 起始地 址:"v<temp->StartAddvv""vv"是否已分配:"<<temp->State<<endl;/输出内存的各个变量/分区排序voidSortPartition(boolorder)/ 在此使用的是快速排序算法FreeMemory*temp1=AllocTable;FreeMemory*temp2=AllocTable;FreeMemory*Last1=temp1;FreeMemory*L

44、ast2=temp2; if(temp2->Next) temp2=temp2->Next;switch(order)case1:升序部分for(;temp1;temp1=temp1->Next)for(;temp2;temp2=temp2->Next)if(temp1->Size>temp2->Size)&&!temp1->State&&!temp2->State)/ 找到符合条件的，则交换Last1->Next=temp2;Last2->Next=temp1;FreeMemory*temp=t

45、emp2->Next;temp2->Next=temp1->Next;temp1->Next=temp->Next;Last2=temp2;Last1=temp1;break;caseO:/降序部分for(;temp1;temp1=temp1->Next)for(;temp2;temp2=temp2->Next)if(temp1->Size<temp2->Size)&&!temp1->State&&!temp2->State)/ 找到符合条件的，则交换 Last1->Next=temp

46、2;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-&

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

48、; 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;returntrue;/endforreturnfalse; boolAlloc_BestFit(intid,intTrySize)/查找满足此条件的 x1<=TrySize<=x2 的分区 ,然后将其

49、放置在 x2 中，并将 x2 拆分成两个分区 SortPartition(true);/ 使用快速排序算法，升序排序FreeMemory*temp=AllocTable;if(temp->Next)temp=temp->Next; for(;temp;temp=temp->Next) if(TrySize<=temp->Size&&!temp->State)/ 第一个满足条件的分区已找到if(TrySize=temp->Size)/ 刚好和申请的大小一致temp->ID=id;/保持不变 temp->Next,Size,St

50、artAdd 都不用变 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->

51、;State=true; temp->Next=NewItem;returntrue;/endforreturnfalse;boolAlloc_Memory(intid,intAlgorithm,intTrySize)/ 对算法进行选择switch(Algorithm)case1:returnAlloc_FirstFit(id,TrySize);break;case2:returnAlloc_BestFit(id,TrySize);break;default:cout<<" 你没有指定算法 ,系统将默认为首次适应算法 !"<<endl; ret

52、urnAlloc_FirstFit(id,TrySize);/*EndMemoryAlloc 内存分配区操作定义完成 */*RecycleMemory 回收内存 */ 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+t

53、emp->Next->Size;temp->State=0;/ 回收Last=temp->Next;temp->Next=temp->Next->Next;deleteLast;else/只有第一分区为空，则清除相关表项的数据temp->ID=0;temp->State=false;/ 改为没有使用状态returntrue;/特殊情况第一条if(temp->Next)temp=temp->Next;for(;temp;temp=temp->Next)/*回收操作，回收过程中，要用到三个指针，上一个 Last,当前temp,

54、下一个temp->next 当 temp 指向表头或表尾时需要特殊考虑 */ if(temp->ID=id)/begin 找到该 ID 表项if(temp->Next)/ 没有到最后一条if(!Last->State&&!temp->Next->State)/ 回收区与插入点的前、后两个分区邻接优先级为 1 Last->Next=temp->Next->Next;Last->Size=Last->Size+temp->Size+temp->Next->Size;deletetemp->Ne

55、xt;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+te

56、mp->Next->Size;temp->State=false;temp->ID=0;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/最后一条的前

57、一条不为空temp->ID=0;temp->State=0;returntrue;/end 找到该 ID 表项此类情况处理完毕Last=temp;/endforreturnfalse;/*MemoryRecycled 内存分配完毕 Alldone,thejobreferedwillleavesystem*/ /当进程开始时 ,就应该为之分配内存 voidBeginJob(intid,intAlgorithm,intTrySize)Alloc_Memory(id,Algorithm,TrySize);/当要退出工作时 ,就要回收 /此退出的工作由执行函数调用 voidEndJob(i

58、ntid)Free_Memory(id);/*/voidFIFO()intlength;intfifo100=0;intpageLength; intfifoPage100=0;inti,j;cout<<"I*"<<endl;pageLength=3;length=9;cout<<" 时刻 t"<<'t'for(i=0;i<length;i+)cout<<i<<'t'cout<<endl<<" 引用串 "

59、;<<'t'for(i=1;i<=length;i+)fifoi=rand()%5+1;cout<<fifoi<<'t'for(i=1;i<=length;i+)intflag=0;for(j=1;j<=pageLength;j+)if(fifoi=fifoPagej)flag=1; j=pageLength+1; elseif(fifoPagej=0) fifoPagej=fifoi; j=pageLength+1;flag=1;if(flag=1)elsecout«" t淘汰"vvfifoPage1v<endl;for(j=1;j<=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;cout«e ndlvv"t="vvi-1<v"时"<v't： for(intjk=1;jk<=pageLength;jk+)cout<<"P"<<jk<<'t'cout&l