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

《操作系统(一个小型操作系统的设计与实现)课程设计》由会员分享，可在线阅读，更多相关《操作系统(一个小型操作系统的设计与实现)课程设计（40页珍藏版）》请在装配图网上搜索。

1、南通大学计算机科学与技术学院操作系统课程设计报告专 业：学生姓名：学号： 时间：操作系统模拟算法课程设计报告设计要求将本学期三次的实验集成实现：A. 处理机管理；B. 存储器管理；C. 虚拟存储器的缺页调度。设计流程图主流程图第 1 页 共 40 页A.处理机调度1）先来先服务FCFS先来先服务算法流程2）时间片轮转法B.存储器管理（可变式分区管理）1）首次适应法分配流程图首次适应算法回收流程图前一个空闲区的后向指针指向 p的后一个空闲分区，p的后一 个空闲分区的前向指针指向p 的前一个空闲分区，且p的前 一个空闲分区大小更改为加上 p的大小再加上p的后一个空 闲分区的大小，合并后的这个 空闲

2、区的后向指针指向p的下 下个分区，如果p的下下个分 区不为空，则其前向指针指向 合并后的这个空闲区，释放p 和p的下一个分区2）最佳适应法回收内存流程C.虚拟存储器的缺页调度1）先进先出FIFOFIFO淘汰算法流程2)LRU实现原理主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。CProgram F在班MiuF。吕口托StudiMyProjcxlDebugs tat e=R;tempallocation=0;num+二tempneed_time;（五） 实现方法-处理器调度总是选择标志单元指示的进程运行。执行:已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单

3、位的时间。当一个进程被选中运行时，必须设置该进程可以运行的时间片值，以及恢复进程的现场，让 它占有处理器运行，直到出现等待事件或运行满一个时间片进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间,若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮 时再运行。若该进程的要求运行时间二已运行时间，则表示它已经执行结束，应 指导它的状态修改成“结束”且退出队列。此时，应把该进程的进程控制块中的 指针值送到前面一个进程的指针位置。进程名链接指针到达时间估计运行时间进程状态进程控制块结构（六）运行界面

4、测试数据：作业号执行时间/sA1B2C1执行时间片轮转算法RR如下:BIsB占用3U时间徐时间023開秒鬣余时间n1B2C0占用cpu时间Is乐：Is占用 cpuHlBjIs占用 cpuSlEJlIs塞押杪常卜余时间auR1C0丄-外王甲机筲卿 2. T7桃盟省坍3 .徐H将恿M.返回幵殆菜单日寸 | 日 | ,1-| 丰色丰老!周.ft 驴?I：匸 HKNXJCKUHKKHmCXJCXKHKKX处理机管理齐存储器管理 日.缺厌调度1-先来先服务算法2 -时间片轮转算法ISU3FilesXMi0秋1S.八+-.:U 0B. 存储器管理（可变式分区管理）1）首次适应法（一）任务 通过采用首次适应

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

6、nt ID;int StartAdd;int Size;bool State;/定义state为布尔型变量，其值只有 真（TRUE）和假（FALSE） FreeMemory* Next;FreeMemory * AllocTable二new FreeMemory;/建立全局管理表用于内与回收 FreeMemory* PtrforCycleFit二AllocTable;/为循环首次适应定义的指针，此指 针用于指向当前查找的起始地址;/初始化内存函数void MemoryInit（FreeMemory* &tempAdd）tempAdd-ID=O;/初始化当前进程为空t empAdd-Size二M

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

8、t 当 temp 指向表头或表尾时需要特殊考虑*/当要退出工作时，就要回收/此退出的工作由执行函数调用void EndJob（int id）Free_Memory（id）;（五）实现方法空闲区设置为双向链表，其双向链的分区格式为0 （状态位）分区大小（N+2）向前指针大小为N的已分配区或空闲区0 （状态位）分区大小（N+2）向后指针（六）运行界面 测试数据如下：进程123456所需内存253445121310执行最佳适应算法为其分配内存如下:1- 1- 1- 1-1- - - 1 nJ nJ nJ tEII 己己 分*手已已已転 5 9 0 12 1 0 2 5 1 1 1 如.J-LJii.

9、,J-i.J-ii-.Jt.Jl:蚯 地地地地地地肪 4 口4 口4 口A口A口台女 己己己己己己走. 二二二二二二二二- 一-上 一-上 一-兀 一 卜:大犬大大大大大112345G0存存存内内内 it配收示 睪EX分回显D:D:D:D:D右心 0 12 3若回收进程4，执行结果如下:00 11:1 -1己酉酉-rj肉y 2$孑夕J1 疔夕乡nnn七出已已疋肥詈a5 90 2 5址址址址址址4j 地地地地地龍飪 A口台4 口4 口4 口A口女 女女女女女女己 _d _d B己己己走.75 4 5 2 3 0 12 3 4 1111652存存存內內內 i.tsll收示 i3a5Ga番EX勞回显

10、0 12 3:大犬大犬犬大 存 內 1 1 一 1| 总IDIDIDIDIDIDID选 呈呈呈呈呈口王呈F 1C 兰门!-I_.T.丿Tl兰戶 fULI-C. 虚拟存储器的缺页调度1）先进先出FIFO（一）任务采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号 和运行结果。（二）要求1. 实现对FIFO算法的模拟实现2输出每次执行的结果。（三）原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页 面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可 能性较大。（四）数据结构void FIFO（）int length;int fifo

11、100=0;int pageLength;int fifoPage100=0;int i,j;coutTx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx进先出算法pageLength=3;length=9;for(i=1;i=length;i+)int flag=0;for(j=1;j=pageLength;j+) if(fifoi=fifoPagej) flag=1; j=pageLength+1;else if(fifoPagej=0) fifoPagej=fifoi; j=pageLength+1; f

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

13、求数列：4,4,3,5,1,1,2,3,2执行先进先出FIFO算法结果如下：C Prcy rar F 1七丸胡ib。吕口ft Vkual StudiMyFrejectDeb-igxlM1門1 处理机管理32 存储器管理3-缺贝调度先进先岀算法2丄刖算法囂返回幵始菜单1耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳节井节出 嘗;才耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳耳时刻七12345&78引用串1123221320时P1P2P3睡t=l时P1P2P3122时P1P2P31t =3时P1P2P312T*=4时P1P2P3123Z时P1P2P3123t=&时P1P2P3123七=7时P

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

15、构void LRU()int length;int lru100=0;int pageLength;int lruPage100=0;int i,j;cout * 最 近 最 少 使 用 LRU 算 法pageLength=3;length=9; for(i=1;i=length;i+)int flag=0;for(j=1;j0;cc-)lruPagecc=lruPagecc-1; lruPage1=lrui; flag=1; j=pageLength+1;else if(lruPagej=0)for(int vv=j;vv0;vv-)lruPagevv=lruPagevv-1;lruPage

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

17、4,4,3执行最近最少使用LRU算法结果如下：-C!Progr3m Fileh/1 cro-soft ViiLja StudioVIyProjecscy|Debugcxl.exe*1 先进先出算法N.LRlM法3底回幵姑菜单2.宦醛資时-植-咸低鼻-賈-拭-时-賊嗔-資鼻-賈-植宦-弱.:M 扇 |/| 吊 少田 TR薛左 :M-M:JHOHHeH:MX时刻 t1312345&7引用串 235155匕=0 时PlP2P3200七=:.时PiP?G冲时P1P2*1P3*1J亠淘沐2L -3吋PiP2P3153丄处理机菅理2 存储器管理3 缺页调度L -4吋p丄5FZ1F33*=5时PiF2F35

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

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

20、成功的调试了出来。但是这几个 程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！源代码： #include #include #include using namespace std;int fcfsoutput(); /*调度结果输出*/int fcfsinput(); /进程参数的初始化 void kaishi();#define MAX 10struct node/建立链表来存放进程数据char name5;/进程名称int need_time;/所需要的时间int allocation;/占用 cpu 的情况char state;目前的状态R为运行，E为运行完毕node

21、 *next;/链表的尾结点 ;struct task_struct/*进程名称*/*进程编号*/*到达时间*/*开始运行时间*/*运行时间*/*运行结束时间*/*优先级*/*运行次序*/*调度标志*/char name;int number;float come_time;float run_begin_time; float run_time;float run_end_time; int priority;int order;int run_flag;tasksMAX;int counter; /*实际进程个数*/int fcfs()/*先来先服务算法*/fcfsinput();floa

22、t time_temp=0;int i;int number_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();return 0;int fcfsinpu

23、t()task_struct tt;int i,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+e_time) tt=tasksj; tasksj=tasksj+1; tasksj+1=tt;/初始化每个进程估计运行的时间 tasks0.run_time=28;tasks1.run_time=9;tasks2.run_time=3; /初始化每个进程的名字tasks0.name=A;tasks1.nam

24、e=B;tasks2.name=C;J.-ft 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* 1*cout*来先服务算for(i=0;icounter;i+)tasksi.run_begin_time=0; tasksi.run_end_time=0; tasksi.order=0; tasksi.run_flag=0;return 0;int fcfsoutput() /*调度结果输出*/int i;float turn_round_time=0,f1,w=0;coutvv作业名 到达时间运行时间开始

25、时间停止时间 运行次序周转时间vvendl;for(i=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;p=head;cout

26、vvendlvv初始时刻：vvendl;coutvv进程vvtvv剩余时间vvtvv占用 cpu 时间vvendl;while(p!=tail)coutvv vvp-namevvtvv vvp-need_timevvtvvtvvp-allocationvvsvvendl; p=p-next;coutvv vvtail-namevvtvv vvtail-need_timevvtvvtvvp-allocationvvsvvendl;node *q;int label=1;int m=1;while(label=1&mv=num)coutvvendl;label=0;while(!p-need_ti

27、me)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;coutvv执行vvmvv秒后：vvendl;q=head;coutvv进程vvtvv剩余时间vvtvv占用 cpu 时间vvendl;while(q!=tail)coutvvvvq-namevvtvvvvq-need_timevvtvvtvvq-allocationvvsvvendl;q=q-next;coutvvvvtail-namevvtvvvvtail-need_timevvtvvtvvq

28、-allocationvvsvvendl;m+;coutvvendlvv;return 0;int const MEMO=256;/初始化常类型MEMO，用MEMO表示内存大小（常类型的变量或对 象的值是不能被更新的）struct FreeMemoryint ID;int StartAdd;int Size;bool State;/定义state为布尔型变量，其值只有真（TRUE）和假（FALSE） FreeMemory* Next;FreeMemory* AllocTable=new FreeMemory;/建立全局管理表用于内存分配与回收FreeMemory* PtrforCycleFit

29、=AllocTable;/为循环首次适应定义的指针，此指针用于指向当前 查找的起始地址;/初始化内存函数void MemoryInit(FreeMemory* &tempAdd)tempAdd-ID=O;/初始化当前进程为空 tempAdd-Size=MEMO;初始化可分配空间为内存大小 tempAdd-StartAdd=O;/初始化起始地址为0 tempAdd-State=false;/ 初始化状态为未分配 tempAdd-Next=NULL;/初始化下一个进程也为空/反馈内存现态void DispMemory()FreeMemory* temp=AllocTable;/全局管理表反映内存状

30、态 coutvv系统总内存：vvMEMOvvendl;for(;temp;temp=temp-Next)cout 进 程 ID ：ID 大 小 ： Size StartAddvv Statevvendl;/ 输出内存的各个变量/分区排序void SortPartition(bool order)/在此使用的是快速排序算法FreeMemory* temp1=AllocTable;FreeMemory* temp2=AllocTable;FreeMemory* Last1=temp1;FreeMemory* Last2=temp2; if(temp2-Next) temp2=temp2-Next;

31、switch(order)case 1:/升序部分for(;temp1;temp1=temp1-Next)for(;temp2;temp2=temp2-Next)if(templ-Size temp2-Size)& !templ-State&!temp2-State)/找到符合条件的，则交 换Last1-Next=temp2;Last2-Next=temp1;FreeMemory* temp=temp2-Next;temp2-Next=temp1-Next;temp1-Next=temp-Next;Last2=temp2;Last1=temp1;break;case 0:/降序部分for(;t

32、emp1;temp1=temp1-Next) for(;temp2;temp2=temp2-Next)if(templ-Size Size )& !templ-State& !temp2-State) 找到符合条件的，则交 换Lastl-Next=temp2;Last2-Next=templ;FreeMemory* temp=temp2-Next;temp2-Next=templ-Next;templ-Next=temp-Next;Last2=temp2;Lastl=templ;/*内存分配*/bool Alloc_FirstFit(int id, int TrySize)/ 定义布尔型函数

33、Alloc_FirstFit()/查找一个可用第一个满足分配请求的分区，如果满足将其写入内存分配表/否则分配失败，返回FreeMemory* temp=AllocTable;for(;temp;temp=temp-Next)if(TrySizev=temp-Size & !temp-State)第一个满足条件的分区已找到if(TrySize=temp-Size)/刚好和申请的大小一致temp-ID=id;/保持不变 temp-Next,Size,StartAdd 都不用变temp-State=true; /值为真表示已分配else/比所找到的要小，贝懦要将其拆分FreeMemory* NewI

34、tem=new FreeMemory;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;return true;/end forreturn false;bool Alloc_BestFit(int id,int TrySize)/查找满足此条件的xlv=TrySize

35、v=x2的分区，然后将其放置在x2中，并将x2拆分成两个 分区SortPartition(true);/使用快速排序算法，升序排序FreeMemory* temp=AllocTable;if(temp-Next)temp=temp-Next;for(;temp;temp=temp-Next)if(TrySizev=temp-Size & !temp-State)第一个满足条件的分区已找到if(TrySize=temp-Size)/刚好和申请的大小一致temp-ID=id;/保持不变 temp-Next,Size,StartAdd 都不用变 temp-State=true; /值为真表示已分配e

36、lse/比所找到的要小，贝懦要将其拆分FreeMemory* NewItem=new FreeMemory; 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;return true;/end forreturn false;bool Alloc_Memory(in

37、t id, int Algorithm,int TrySize)/对算法进行选择 switch(Algorithm)case 1 :return Alloc_FirstFit(id,TrySize);break;case 2:return Alloc_BestFit(id,TrySize);break;default:coutvv你没有指定算法,系统将默认为首次适应算法vvendl; return Alloc_FirstFit(id,TrySize);/*End Memory Alloc 内存分配区操作定义完成*/*Recycle Memory 回收内存*/bool Free_Memory(i

38、nt id)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;delete Last;else/只有第一分区为空，则清除相关表项的数据temp-ID=0;temp-State=false;改为没有

39、使用状态return true;/特殊情况第一条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-Size+t

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

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

42、st=temp;/endforreturn false;/*Memory Recycled 内存分配完毕 All done ,the job refered will leave system */当进程开始时,就应该为之分配内存void BeginJob(int id,int Algorithm,int TrySize)Alloc_Memory(id,Algorithm,TrySize);/当要退出工作时,就要回收/此退出的工作由执行函数调用 void EndJob(int id)Free_Memory(id);void FIFO()int length;int fifo100=0;int pageLength;int fifoPage100=0; int i,j;cout