《一个小型的操作系统设计与实现.pdf》由会员分享，可在线阅读，更多相关《一个小型的操作系统设计与实现.pdf（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一个小型的操作系统设计与实现 Prepared on 24 November 2020南通大学计算机科学与技术学院操作系统课程设计报告专业：计嵌 151学生姓名：王志宏学号：时间2017/6/28：设计一个小型的操作系统设计一个小型的操作系统设计要求设计要求将本学期三次的实验集成实现：1.中断处理2.作业调度3.PV 原语4.死锁5.页面替换6.磁盘调度(一一)设计流程图设计流程图主流程图中断处理作业调度先来先服PV原语哲学开始的图形界面开始的图形界面死锁银页面替换先L磁盘调度时1.中断处理先来先服务钟行进R家模拟时钟中断的产生及设计一个对时钟中断事件进行处理的模拟程序。家先U吃计算机系统工作
2、过程中，若出现中断事件，硬件就把它记录在中断寄存器算出算通中。中断寄存器的每一位可与一个中断事件对应，当出现某中断事件后，对应法算法心1。处理器每执行一条指令后，必须查中断的中断寄存器的某一位就被置成寄存器，当中断寄存器内容不为0时，说明有中断事件发生。硬件把中断寄存器内容以及现行程序的断点存在主存的固定单元，且让操作系统的中断处理程序占用处理器来处理出现的中断事件。操作系统分析保存在主存固定单元中务的中断寄存器内容就可知道出现的中断事件的性质，从而作出相应的处理。本实习中，用从键盘读入信息来模拟中断寄存器的作用，用计数器加 1 来模拟处理器执行了一条指令。每模拟一条指令执行后，从键盘读入信息
3、且分析，当读入信息=0 时，表示无中断事件发生，继续执行指令；当读入信息=1 时，表示发生了时钟中断事件，转时钟中断处理程序2.作业调度 1)先来先服务 FCFS开始初始化进程控制块，让进程控制调度数组中首个进程，并让计算并打印进程的完成时刻、周转时更改计时器的当前时间,即下一刻进程的开始N N间、带权周转时间数组为空 Y Y结束先来先服务算法流程原语 1）哲学家吃通心面问题哲学家吃通心面：在这道题目里，每把叉子必须互斥使用，当一位哲学家吃通心面之前必须执行两个 P 操作，获得自己左右两边的叉子，在吃完通心面后必须执行两个 V 操作，放下叉子。4.死锁1）银行家算法5.页面替换 1)先进先出
4、FIFO开始 FIFO的缺页查主存分块表2）LRUFIFO淘汰算法流程调整 FIFO队列，将 L插修改主存分块表和终止NJ 的修改Y输出“将 J 页复写入交换输出“装入 L页”有空闲NJ=pHEADY分配一开始 LRU的缺页查主存分块表Y有空闲N找到栈底元素：分配一NJ 的修改Y输出“将 J 页送到入交换输出“装入 L页”6.磁盘调度调整堆栈，使 HEAD所指修改主存分块表和终止LRU淘汰算法流程1）先来先服务算法 FCFS）（二）实现原理（二）实现原理主界面主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。1.1.中断中断2.2.作业调度作业调度 1)先来先服务 FCF
5、S（一）任务先来先服务的调度算法实现处理机调度。（二）要求1.实现对 FCFS 算法的模拟实现2.计算出该算法的平均作业周转时间、平均带权作业周转时间。（三）原理按作业到达 CPU 时间先后顺序进行非剥夺式调度，先到达 CPU 的作业先被执行。（四）数据结构 struct task_struct char name;/*进程名称*/int number;/*进程编号*/float come_time;/*到达时间*/float run_begin_time;/*开始运行时间*/float run_time;/*运行时间*/float run_end_time;/*运行结束时间*/int pri
6、ority;/*优先级*/int order;/*运行次序*/int run_flag;/*调度标志*/tasksMAX;int fcfs()/*先来先服务算法*/进程名链接指针到达时间估计运行时间进程状态进程控制块结构（五）实现方法建立一个链表按照到达 CPU 的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。（六）运行界面测试数据：作业名AB到达时间00运行时间289C执行 FCFS 算法如下：033.3.死锁死锁假定本系统中的各个所需资源均是独占型资源，在进程运行的过程中不再释放，故只需要遍历链表将各个进程中所需的资源统计出来，只要不大于系统中预设的即可，一
7、旦进程所需的资源大于系统中的最大量，给予用户选择 kill一进程，已达到释放资源的目的。死锁检测函数：void sisuo()死锁解除函数：void safe()4.4.缺页调度缺页调度 1)先进先出 FIFO（一）任务采用先进先出 FIFO 算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。（二）要求1.实现对 FIFO 算法的模拟实现2.输出每次执行的结果。（三）原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。（四）数据结构void FIFO()int length;in
8、t fifo100=0;int pageLength;int fifoPage100=0;int i,j;cout *先进先出算法*endl;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;flag=1;if(flag=1)elsecout淘汰fifoPage1endl;for(j=1;j=pageLengt
9、h;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;（五）实现方法当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进程已在主存的页号，其队列头指针初始化为 0.假设分配给每个进程的内存块数固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存入磁盘。然后要把当前访问的页装入该块，并修改页表和存储分块表的对应标志。（六）运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：4,4,3,5,1,1,2,3,2执行先进先出 FIFO 算法结果如下：2 2）LRULRU（一）任务采用先进先出 LRU 算法实现分页
10、管理的缺页调度，并输出每次调入调出的页号和运行结果。（二）要求1.实现对 LRU 算法的模拟实现2.输出每次执行的结果。（三）原理最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。如果主存中已无空闲块，可采用 LRU 算法进行缺页处理。（四）数据结构void LRU()int length;int lru100=0;int pageLength;int lruPage100=0;i
11、nt i,j;cout *最近最少使用 LRU算法*endl;pageLength=3;length=9;for(i=1;i=length;i+)int flag=0;for(j=1;j0;cc-)lruPagecc=lruPagecc-1;if(flag=1)elselruPage1=lrui;flag=1;j=pageLength+1;else if(lruPagej=0)for(int vv=j;vv0;vv-)lruPagevv=lruPagevv-1;lruPage1=lrui;j=pageLength+1;flag=1;cout淘汰lruPagepageLength0;j-)lru
12、Pagej=lruPagej-1;lruPage1=lrui;（五）实现方法当采用 LRU 算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针，初始化为 0.假定分配给每个进程的内存块数固定不变。当队列满需淘汰时，操作系统选择栈底元素淘汰，其他元素向下移一个位置，将新调入页放栈指针指示的栈顶。当访问的页在栈中时，还应调整页从当前位置到栈顶。（六）（六）运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：2,3,5,1,5,5,4,4,3执行最近最少使用 LRU 算法结果如下：5.5.磁盘调度磁盘调度1）先来先服务算法 FCFS）这是一种比
13、较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。（三）总结与体会（三）总结与体会通过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出和最近最少使用算法有了更详尽的认识。在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该
14、记得释放资源。从这次实验中我发现我对于 c+掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。此外我还更深入的理解了各个进程调度算法，及实现过程。在编写程序时查询了很多资料，间接提高了我的搜索能力。在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。特别是设计先来先服务调度算法和时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。对进程管理中的等待队列，就绪队列，时间片等概念有了更深刻的印象。在设计此模拟操作
15、系统的课设中，也加深了对 c+知识的把握。解决了一些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。另外，我觉得此次课程设计虽然主要问题是在编程上，但是经过不断的去调试，还是成功的调试了出来。但是这几个程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！源代码：#include#include#include#include#include#include#include#include#includeusing namespace std;int fcfsoutput();/*调度结果输出*/int fcfsinpu
16、t();un_begin_time=time_temp;int fcfsinput()int fcfsoutput()/*调度结果输出*/endl;endl;for(i=0;icounter;i+)f1=tasksi.run_end_time-tasksie_time;cout 作业名到达时间 运行时间 开始时间 停止时间运行次序 周转时间 int i;float turn_round_time=0,f1,w=0;cout *先来先服务*task_struct tt;int i,j;un_time=28;tasks1.run_time=9;tasks2.run_time=3;ame=A;tas
17、ks1.name=B;tasks2.name=C;cout *先来先服务算法*for(i=0;icounter;i+)return 0;tasksi.run_begin_time=0;tasksi.run_end_time=0;tasksi.order=0;tasksi.run_flag=0;fcfsoutput();return 0;tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time;tasksi.run_flag=1;time_temp=tasksi.run_end_time;number_schedul=i;tasksnum
18、ber_schedul.order=i+1;endl endl;turn_round_time+=f1;w+=(f1/tasksi.run_time);cout tasksi.name t tasksie_time tasksi.run_time t tasksi.run_end_time t tasksi.order t f1t tasksi.run_begin_time t t endl;cout 平均周转时间：turn_round_time/counter endl;cout 平均带权周转时间：w/counter endl;cout ;return 0;void zuoyediaodu(
19、)来先服务算法t 2.返回开始菜单 endl;/*-*/void FIFO()endl;pageLength=3;length=9;cout 时刻 t t;for(i=0;ilength;i+)cout i t;cout endl 引用串 t;for(i=1;i=length;i+)for(i=1;i=length;i+)fifoi=rand()%5+1;cout fifoi t;int length;int fifo100=0;int pageLength;int fifoPage100=0;int i,j;cout *先进先出算法*n;switch(n)case 1:fcfs();kais
20、hi();break;case 2:kaishi();kaishi();break;endl;int flag=0;for(j=1;j=pageLength;j+)if(flag=1)elsecout endl t=i-1 时 t;for(int jk=1;jk=pageLength;jk+)cout endl t;for(int s=1;s=pageLength;s+)cout endl;cout fifoPages t;cout P jk t;cout 淘汰 fifoPage1 for(j=1;j=pageLength;j+)fifoPagepageLength=fifoi;fifoPag
21、ej=fifoPagej+1;if(fifoi=fifoPagej)else if(fifoPagej=0)fifoPagej=fifoi;j=pageLength+1;flag=1;flag=1;j=pageLength+1;void LRU()int length;int lru100=0;int pageLength;int lruPage100=0;int i,j;cout *最近最少使用 LRU 算法*pageLength=3;length=9;cout 时刻 t t;for(i=0;ilength;i+)cout i t;cout endl 引用串 t;for(i=1;i=leng
22、th;i+)for(i=1;i=length;i+)int flag=0;for(j=1;j=pageLength;j+)if(flag=1)elsecout 淘汰 0;j-)lruPagej=lruPagej-1;if(lrui=lruPagej)else if(lruPagej=0)for(int vv=j;vv0;vv-)lruPage1=lrui;j=pageLength+1;flag=1;lruPagevv=lruPagevv-1;for(int cc=j;cc0;cc-)lruPage1=lrui;flag=1;j=pageLength+1;lruPagecc=lruPagecc-
23、1;lrui=rand()%5+1;cout lrui t;endl;lruPagepageLength endl;lruPage1=lrui;cout endl t=i-1 时 t;for(int jk=1;jk=pageLength;jk+)cout endl t;for(int s=1;s=pageLength;s+)cout endl;cout lruPages t;cout P jk t;void queye()进先出算法算法t3.返回开始菜单 endl;/*-*/*判断输入数据是否有效*/int decide(char str)来先服务t2.返回开始菜单 str;始t2.返回开始菜
24、单 n;switch(n)case 1:dead_lock();kaishi();break;case 2:kaishi();kaishi();break;cin n;switch(n)case 1:FIFO();kaishi();break;case 2:LRU();kaishi();break;case 3:kaishi();kaishi();break;st=asctime(local);始t2.返回开始菜单 n;switch(n)case 1:ZD();kaishi();break;case 2:kaishi();kaishi();break;/*-*/struct processfl
25、oat search(string s,program p,int n)void Print(program p,int n)ame t k.starttime tt k.finishtime ttvoid Program()endl;cout n1;cout endl;input(a,n1);cout 输入程序 B 的运行步骤：;int n1,n2;program a,b;cout *多道程序设计*k.arrivetime tt k.runtime=0;i-)return 0;if i.flag&i.name=s)return i.finishtime;string name;float a
26、rrivetime;ame i.runtime;cout n2;cout endl;input(b,n2);0.arrivetime=0;0.arrivetime=0;0.finishtime=0;0.finishtime=0;int i=0,j=0;float f;doif i.arrivetime=j.arrivetime)f=searchj.name,a,n1);if(f=j.arrivetime)elsej.finishtime=j.starttime+j.runtime;j.flag=true;if(j n2-1)j.starttime=f;j.starttime=j.arrivet
27、ime;f=searchi.name,b,n2);if(f=i.arrivetime)elsei.finishtime=i.starttime+i.runtime;i.flag=true;if(i n1-1)i+1.arrivetime=i.finishtime;i+;i.starttime=f;i.starttime=i.arrivetime;j+1.arrivetime=j.finishtime;j+;while(!n1-1.flag&!n2-1.flag);while n1-1.flag&!n2-1.flag)while n2-1.flag&!n1-1.flag)Print(a,n1);
28、Print(b,n2);system(pause);i.starttime=i.arrivetime;i.finishtime=i.starttime+i.runtime;i.flag=true;if(i n1-1)i+1.arrivetime=i.finishtime;i+;j.starttime=j.arrivetime;j.finishtime=j.starttime+j.runtime;j.flag=true;if(j n2-1)j+1.arrivetime=j.finishtime;j+;void duodaochengxu()int n;cout endl;cout t1.开始t2
29、.返回开始菜单 n;switch(n)case 1:Program();kaishi();break;case 2:kaishi();kaishi();break;/*-*/int avaResour3=3,3,2;int allocation53=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2 ;int maxRequest53=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3 ;int nneed53=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1 ;void rrequest();bool safeTest();void rrequest()int sq
30、jc=0,i=0,l=0,a=0,b=0,c=0;char contn=0;cout endl 进程个数：5资源个数：3 endl 可用资源向量 Available:for(i=0;i3;i+)cout avaResouri ;cout endl 最大需求矩阵 Max:endl;for(i=0;i5;i+)cout 已分配矩阵 Allocation:endl;for(i=0;i5;i+)cout 需求矩阵 Need:endl;for(i=0;i5;i+)cout sqjc;while(sqjc4|sqjc0)cout endl 不要乱输!_ endl;cout endl 输入发起请求的进程(0
31、-4):;for(l=0;l3;l+)cout nneedil ;cout endl;for(l=0;l3;l+)cout allocationil ;cout endl;for(l=0;l3;l+)cout maxRequestil ;cout endl;sqjc;cout a b c;if(a=nneedsqjc0&b=nneedsqjc1&c=nneedsqjc2)cout endl 开始执行银行家算法.endl;if(a=avaResour0&b=avaResour1&c=avaResour2)endl=0)avaResour1+b;avaResour0=avaResour0-a;av
32、aResour1=avaResour1-b;avaResour2=avaResour2-c;allocationsqjc0=allocationsqjc0+a;allocationsqjc1=allocationsqjc1+b;allocationsqjc2=allocationsqjc2+c;nneedsqjc0=nneedsqjc0-a;nneedsqjc1=nneedsqjc1-b;nneedsqjc2=nneedsqjc2-c;cout endl 试分配完成.endl;if(safeTest()cout endl 开始给第 sqjc 个进程分配资源.分配完成，已更新 endl;for(
33、i=0;i5;i+)if(nneedi0=0&nneedi1=0&nneedi2for(l=0;l3;l+)avaResourl=avaResourl+allocationil;allocationil=0;elsecout endl 系统已恢复试分配前状态。endl;avaResour0=avaResour0+a;avaResour1=avaResour2=avaResour2+c;allocationsqjc0=allocationsqjc0-a;allocationsqjc1=allocationsqjc1-b;allocationsqjc2=allocationsqjc2-c;nnee
34、dsqjc0=nneedsqjc0+a;nneedsqjc1=nneedsqjc1+b;nneedsqjc2=nneedsqjc2+c;xz:elseelsecout endl 试分配失败，系统无足够资源 endl;cout endl Error!申请的资源大于需求值 endl;cout nn contn;switch(contn)case y:rrequest();case n:break;default:cout 亲，不要乱输哦;int s=0,m=0,z=0,r5=0,y=0,wwork3=0;bool ffinish5=0;cout endl 进入安全性测试!endl;for(s=0;
35、s3;s+)if(y=5)cout endl 找到一个安全序列：;for(s=0;s2;s+)cout P r2*s P r2*s+1 -for(s=0;s5;s+)if(ffinishs=0&nneeds0=wwork0&nneeds1=wwork1for(m=0;m3;m+)wworkm=wworkm+allocationsm;ffinishs=1;ry=s;y+;&nneeds2=wwork2)wworks=avaResours;for(z=0;z5;z+)cout P r4 endl 已通过安全检测！endl;return 1;cout endl 没有找到安全序列！endl 安全测试失
36、败。endl;return 0;void Sisuo()void sisuo()/*-*/void kaishi()int main(void)cout endl endl;int n;cout n;switch(n)case 1:zhongduan();break;case 2:zuoyediaodu();break;case 3:PV();break;case 4:queye();break;case 5:cipandiaodu();break;case 6:duodaochengxu();break;case 7:sisuo();break;default:cout 错误请重新选择！endl;kaishi();int n;cout endl;cout t1.开始t2.返回开始菜单 n;switch(n)case 1:Sisuo();kaishi();break;case 2:kaishi();kaishi();break;rrequest();t7.死锁 endl;cout -操作系统课程设计-endl;kaishi();return 0;