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

1、南通大学计算机科学与技术学院操作系统课程设计报告专 业：计嵌151学生姓名：王志宏学号：18 时间：2017/6/28设计一个小型的操作系统设计要求将本学期三次的实验集成实现:1. 中断处理2作业调度3. PV原语4. 死锁5. 页面替换6. 磁盘调度（一）设计流程图主流程图1. 中断处理模拟时钟中断的产生及设计一个对时钟中断事件进行处理的模拟程序。计算机系统工作过程中，若出现中断事件，硬件就把它记录在中断寄存器中。 中断寄存器的每一位可与一个中断事件对应， 当出现某中断事件后，对应的中断 寄存器的某一位就被置成一1 llo处理器每执行一条指令后，必须查中断寄存器， 当中断寄存器内容不为一0

2、1时，说明有中断事件发生。硬件把中断寄存器内容 以及现行程序的断点存在主存的固定单元，且让操作系统的中断处理程序占用处 理器来处理出现的中断事件。操作系统分析保存在主存固定单元中的中断寄存器 内容就可知道出现的中断事件的性质， 从而作出相应的处理。本实习中，用从键 盘读入信息来模拟中断寄存器的作用，用计数器加1来模拟处理器执行了一条指令。每模拟一条指令执行后，从键盘读入信息且分析，当读入信息=0时，表示无中断事件发生，继续执行指令；当读入信息 =1时，表示发生了时钟中断事 件，转时钟中断处理程序2作业调度1）先来先服务FCFS数组为空结束先来先服务算法流程原语当一位哲学家吃 在吃完通心面后必1

3、 ）哲学家吃通心面问题哲学家吃通心面：在这道题目里，每把叉子必须互斥使用, 通心面之前必须执行两个P操作，获得自己左右两边的叉子， 须执行两个V操作，放下叉子。4.死锁1）银行家算法5.页面替换1）先进先出FIFO2) LRUFIFO淘汰算法流程修改主存分块表和页表LRU淘汰算法流程6.磁盘调度1）先来先服务算法FCFS幵始输入呈的讎道数输入握岀磁盘10申请 的进程数输入磁道序列（10结束谕入开始的磁道号谕出磁盘请求疼列和打描 序列求移动的总的5S道数求平均尋道长度结東（二）实现原理主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序操作系统课程祓计1中断处理 2-作业调度3

4、死锁4.页面替换5磁盘调度1. 中断1申曲处鱼乩柞玄死櫃丄口匠替枫11开始£惫回开汹某隼1 _当前杀圮咖：Tun 28 13:9:53 2D 17肪 断 时晰 中 冲 中中 -I - rr 亍示 谨 區 喘m寺 lr- -牢 亍 亮一进程名称*/进程编号*/到达时间*/开始运行时间*/ 运行时间*/ 运行结束时间*/ 优先级*/ 运行次序*/ 调度标志*/2作业调度1）先来先服务FCFS（一）任务先来先服务的调度算法实现处理机调度。（二）要求1. 实现对FCFS算法的模拟实现2. 计算出该算法的平均作业周转时间、平均带权作业周转时间。（三）原理按作业到达CPU时间先后顺序进行非剥夺式

5、调度，先到达CPU的作业先被执 彳亍。（四）数据结构struct task_struct _char n ame;/*int nu mber;/*float come_time; /* float run_ begin_time;/*float run _time;/*float run_en d_time;/*int priority;/*int order;/*int run _flag;/*tasksMAX;int fcfs（）/*先来先服务算法*/进程名链接指针 到达时估计运行时间 进程状态 ： 进程控制块结构（五）实现方法建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业

6、（头结 点）依次调度到最后一个作业（尾结点）。（六）运行界面 测试数据：作业名到达时间运行时间A028B09C03执行FCFS算法如下:2.返国H冰林冰水畔和并栩林冰半押栩林#先来先 服 务算法林林木林林半林木林林半林水林半33424553342【乍业名到达时间运行时间开始时间停止时间运行次序周转时间1233.3333|： 5. 740741-中断处理£作业调度3死锁4页面替换5.磁盘调度3. 死锁假定本系统中的各个所需资源均是独占型资源，在进程运行的过程中不再释放，故只需要遍历链表将各个进程中所需的资源统计出来，只要不大于系统中预 设的即可，一旦进程所需的资源大于系统中的最大量，给

7、予用户选择 kill 一进 程，已达到释放资源的目的。死锁检测函数：void sisuo（）死锁解除函数：void safe（）rror!申请的労労卢專隶诂3 22 2 3o o 0-1 24 2 05 仃o 2 31 o o- .1 oTf rp-.帀3 炷.:r7risnr3. 7 3 nH 2 4己 0 2 3 2 oLls 丄$星 辛4. 缺页调度1）先进先出FIFO（一）任务采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的 页号和运行结果。（二）要求1. 实现对FIFO算法的模拟实现2. 输出每次执行的结果。（三）原理基于程序总是按线性顺序来访问物理空间这一假设，

8、总是淘汰最先调入主存 的页面，即淘汰在主存中驻留时间最长的页面， 认为驻留时间最长的页不再使用 的可能性较大。（四）数据结构void FIFO（）int len gth;int fifo100=0;int pageLe ngth;int fifoPage100=0;*先进先出算法int i,j;cout<<""<<e ndl;*pageLe ngth=3;len gth=9;for(i=1;i<=le ngth;i+)int flag=0; for(j=1;j<=pageLe ngth;j+) if(fifoi=fifoPagei) fl

9、ag=1;j=pageLe ngth+1;else if(fifoPagej=0)fifoPagej=fifoi;j=pageLe ngth+1;flag=1;if(flag=1)elsecout<<"f 淘汰"<<fifoPage1<<endl;for(j=1;j<=pageLe ngth;j+)fifoPagej=fifoPagej+1; fifoPagepageLe ngth=fifoi;(五) 实现方法当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为 进程已在主存的页号，其队列头指针初始化为0.假设分配给每

10、个进程的内存块数固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存 入磁盘。然后要把当前访问的页装入该块，并修改页表和存储分块表的对应标志。(六) 运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：4,4,3,5,1,1,2,3,2执行先进先出FIFO算法结果如下：最近最少使用 LRU 算法*"<<e ndl;2） LRU（一）任务采用先进先出LRU算法实现分页管理的缺页调度，并输出每次调入调出的页 号和运行结果。（二）要求1. 实现对LRU算法的模拟实现2. 输出每次执行的结果。（三）原理最近最少使用页面替换算法淘汰的页面是在最近一段时间内最

11、久未被访问 的那一页，它是基于程序局部性原理来考虑的， 认为那些刚被使用过的页面可能 还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。如果主存中已无空闲块，可采用LRU算法进行缺页处理。（四）数据结构void LRU（）int len gth;int lru1OO=O;int pageLe ngth;int lruPage100=0;int i,j;m* pageLe ngth=3;len gth=9;for(i=1;i<=le ngth;i+)int flag=0;for(j=1;j<=pageL

12、e ngth;j+) if(lrui=lruPagej) for(i nt cc=j;cc>0;cc-)lruPagecc=lruPagecc-1; lruPage1=lrui;flag=1; j=pageLe ngth+1;else if(lruPagej=0) for(i nt vv=j;vv>0;vv-)lruPagevv=lruPagevv-1; lruPage1=lrui; j=pageLe ngth+1; flag=1;if（flag=1）elseCOUt<<"T 淘汰"<<lruPagepageLe ngth<<

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

14、5. 磁盘调度1）先来先服务算法FCFS这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况 下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。5.彳迈盘谐崔1 中断处理 2作业调度&死锁 匸页面替换E为12号12殆 列：道:2.55 - 道禽列度 肇前序长4戈扫寻 1请1120恨蹙焜毗平& 97M6S5nz- 1± _ro1 15 5

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

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

17、断的去调试，还是成功的调试了出来。但是这几个 程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！源代码:#inelude <iostream>#inelude <cstring>#i nclude<estddef>#in elude<>#in elude<>#in elude<stri ng>#in elude<>#inelude <>#inelude <> using namespaeestd;int fcfsoutput(); /* 调度结果输岀 */int fefs

18、input(); un_begin_time = time_temp;tasksi.ru n_en d_time = tasksi.ru n_beg in _time + tasksi.ru n_time;tasksi.ru n_flag = 1;time temp = tasksi.ru n en d time;n umber_sehedul = i;tasks n umber_schedul.order = i + 1;fefsoutput();return 0;int fefsinput()task_struet tt;int i, j;un _time = 28;tasks1.ru n

19、_ time = 9;tasks2.ru n_ time = 3;ame = 'A' =B ; =C ;eout <<“*先来先服务算法*'、<< endl <<endl;for (i = 0; i<eounter; i+)tasksi.ru n_beg in _time = 0; tasksi.ru n_en d_time = 0; tasksi.order = 0;tasksi.ru n_flag = 0;return 0;int fcfsoutput() /* 调度结果输岀 */

20、 int i;float tur n_rou nd_time = 0, f1, w = 0;cout << "*先来先服*"<< endrcout << "作业名 到达时间 运行时间 开始时间 停止时间运行次序 周转时间"vv endl;for (i = 0; i<counter; i+)fl = tasksi.ru n_en d_time - tasksie_time;tur n_rou nd_time += f1;w += (f1 / tasksi.ru n_time);I!cout << &qu

21、ot; "<< <<'t'<< " "<< tasksie_time <<'t' vv "<< tasksi.ru n time<< 't'<< ""<< tasksi.ru n beg in timevv 't'vvI!I!<< tasksi.ru n_en d_time <<'t'<<

22、tasksi.order <<'t'<< fl <<'t'<<en dl;cout << "平均周转时间："<< tur n roun d time / cou nter << en dl;cout << "平均带权周转时间："<< w / cou nter << endl;cout << ""return 0;void zuoyediaodu() 来先服务算法t 2.返回

23、开始菜单"<< endl; cin >> n;switch (n)case 1: fcfs(); kaishi();break ;case 2: kaishi(); kaishi();break;/* */void FIFO()int length;int fifo100 = 0 ;int pageLength;int fifoPage100 = 0 ;int i, j;cout << "*先进先出算法*' I<< en dl;pageLe ngth = 3;len gth = 9;cout << &quo

24、t;时刻 t" << 't'for (i = 0; i<length; i+)cout << i <<'t'cout << endl <<"引用串"<< 't'for (i = 1; i <= length; i+)fifoi = ran d() % 5 + 1;cout << fifoi <<'t'for (i = 1; i <= length; i+)int flag = 0;for

25、(j = 1; j <= pageLength; j+)if (fifoi = fifoPagej)flag = 1;j = pageLe ngth + 1;else if (fifoPagej = 0)fifoPagej = fifoi;j = pageLe ngth + 1;flag = 1;if (flag = 1)elsecout << "t淘汰"<< fifoPage1 << endl;for (j = 1; j <= pageLength; j+)fifoPagej = fifoPagej + 1; fifoPag

26、epageLe ngth = fifoi;cout << endl <<"t=" << i - 1 <<"时"<< 't'for (int jk = 1; jk <= pageLength; jk+)cout << "P" << jk <<'t'cout << endl <<'t'for ( int s = 1; s <= pageLength; s+)co

27、ut << en dl;void LRU() int length;int lru100 = 0 ;int pageLength;int lruPage100 = 0 ;int i, j;cout << I *最近最少使用LRU算法*'、<<en dl;pageLe ngth = 3;len gth = 9;cout << "时刻 t" << 't'for (i = 0; i<length; i+)cout << i <<'t'cout <

28、< endl <<"引用串"<< 't'for (i = 1; i <= length; i+)lrui = ran d() % 5 + 1;cout << lrui <<'t'for (i = 1; i <= length; i+)int flag = 0;for (j = 1; j <= pageLength; j+)if (lrui = lruPagej)for (int cc = j; cc>0; cc-) lruPagecc = lruPagecc - 1

29、;lruPage1 = lrui;flag = 1;j = pageLe ngth + 1;else if (lruPagej = 0)for ( int vv = j; vv>0; vv-) lruPagevv = lruPagevv - 1;lruPage1 = lrui;j = pageLe ngth + 1; flag = 1;if (flag = 1) |cout << "t淘汰"<< lruPagepageLength << endl;for (j = pageLength; j>0; j-)lruPagej =

30、lruPagej - 1;lruPage1 = lrui;cout << endl <<"t=" << i - 1 <<"时"<< 't'for ( int jk = 1; jk <= pageLength; jk+)| |cout << "P" << jk <<'t'cout << endl <<'t'for ( int s = 1; s <= pageL

31、ength; s+)cout << lruPages <<'t'cout << en dl; void queye()进先岀算法 算法t3.返回开始菜单"<< endl;cin >> n;switch (n)case 1: FIFO(); kaishi();break ;case 2: LRU(); kaishi(); break;case 3: kaishi(); kaishi();break;*/*判断输入数据是否有效*F:cin >> str; 始t2.返回开始菜单"<<

32、; endl;cin >> n;switch (n)case 1: dead_lock(); kaishi();break;case 2: kaishi(); kaishi();break;/* */void ZD()double p;int a, m, r, n, e, o, u;struct tm *local;char *st, s27;time_t t;t = time( NULL;local = localtime(&t);st = asctime(local);始t2.返回开始菜单"<< endl;cin >> n;switch

33、 (n)case 1: ZD(); kaishi();break ;case 2: kaishi(); kaishi();break;/* */struct processstri ng n ame;float arrivetime;ame >> i.ru ntime;cout << en dl;float search( strings, program p, int n)for ( int i = n - 1; i >= 0; i-)if i.flag&& =s)retur n i.fi ni shtime;return 0;vv

34、"tt"void Print( program p, int n)ame << "t"<< k.starttime << "tt"<< k.finishtime<< k.arrivetime <<"tt"<< k.runtime << endl;void P n1, n2;program a, b;cout vv "*cout vv "输入程序A的运行步骤: cin >>

35、; n1;cout << en dl;in put(a, n 1);cout << "输入程序B的运行步骤: cin >> n2;cout << en dl;in put(b, n2);0.arrivetime = 0;0.arrivetime = 0;0.fi ni shtime = 0;多道程序设计*' I<< en dl;0.fi ni shtime = 0;int i = 0, j = 0;float f;doif i.arrivetime <= j.arrivetime)f = searchi. na

36、me, b, n 2);if (f <= i.arrivetime)i.starttime = i.arrivetime;else i.starttime = f;i.fi ni shtime = i.starttime + i.ru ntime;i.flag = true ;if (i < n1 - 1)i + 1.arrivetime = i.fi ni shtime;i+；if i.arrivetime >= j.arrivetime)f = search。, name, a, n 1);if (f <= j.arrivetime)j.starttime = j.

37、arrivetime;elsej.starttime = f;j.fi ni shtime = j.starttime + j.ru ntime;j.flag = true ;if (j < n2 - 1)j + 1.arrivetime = j.fi ni shtime; j+; while (!n1 - 1.flag && !n2 - 1.flag);while n 1 - 1.flag&& !n2 - 1.flag)|j.starttime = j.arrivetime;j.fi ni shtime = j.starttime + j.ru ntim

38、e;j.flag = true ;if (j < n2 - 1)j + 1.arrivetime = j.fi ni shtime;j+;while n2 - 1.flag&&!n 1 - 1.flag)|i.starttime = i.arrivetime;i.fi ni shtime = i.starttime + i.ru ntime;i.flag = true ;if (i < n1 - 1)i + 1.arrivetime = i.fi ni shtime;i+；Prin t(a, n1);Prin t(b, n2);system( "pause

39、");void duodaochengxu()int n;cout << en dl;cout << "t1.开始t2.返回开始菜单"<< endl;cin >> 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

40、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 sqjc = 0, i = 0, l = 0, a = 0, b = 0, c = 0;<< en dl;char contn = 0;cout << endl << "进程个数：5 资源个数

41、：3" << endl << "可用资源向量 Available:" for (i = 0; i<3; i+)cout << avaResouri <<"" |cout << endl <<"最大需求矩阵 Max:" << endl;for (i = 0; i<5; i+)for (l = 0; l<3; l+)cout << maxRequestil <<""cout <&

42、lt; en dl;cout << "已分配矩阵 Allocation:"<< endl;for (i = 0; i<5; i+)for (l = 0; l<3; l+)cout << allocatio n il <<"" |cout << en dl;cout << "需求矩阵 Need:" << endl;for (i = 0; i<5; i+)|for (l = 0; l<3; l+)cout << nn e

43、edil <<""cout << en dl;cout << "输入发起请求的进程(0-4):"cin >> sqjc;while (sqjc>4 | sqjc<0)cout << endl <<"不要乱输！ A_A"<< endl;cout << endl <<"输入发起请求的进程(0-4):"cin >> sqjc; |cout << "输入请求资源的数目，按

44、照这样的格式输入x x x:"cin >> a >> b >> c;if (a <= nneedsqjc0 && b <= nneedsqjc1 && c <= nneedsqjc2)cout << endl <<"开始执行银行家算法."<< endl;if (a <= avaResour0 && b <= avaResour1 && c <= avaResour2)avaResour0 = a

45、vaResour0 - a; avaResour1 = avaResour1 - b;avaResour2 = avaResour2 - c;allocati on sqjc0 = allocati on sqjc0 + a;allocatio nsqjc1 = allocatio nsqjc1 + b;allocati on sqjc2 = allocati on sqjc2 + c;nn eedsqjc0 = nn eedsqjc0 - a;nn eedsqjc1 = nn eedsqjc1 - b;nn eedsqjc2 = nn eedsqjc2 - c;cout << e

46、ndl <<"试分配完成."<< endl;if (safeTest()<< endlcout << endl <<"开始给第"<< sqjc <<"个进程分配资源<< "分配完成，已更新"<< endl;for (i = 0; i<5; i+)if (nneedi0 = 0 && nneedi1 = 0 && nneedi2 = 0) for (I = 0; l<3; l+

47、)avaResourI = avaResourI + allocati on il; allocatio n il = 0;elsecout << endl <<"系统已恢复试分配前状态。"<< endl;avaResour0 = avaResour0 + a; avaResour1 = avaResour1 + b; avaResour2 = avaResour2 + c;allocati on sqjcO = allocati on sqjcO - a;allocati on sqjc1 = allocati on sqjc1 - b

48、;allocati on sqjc2 = allocati on sqjc2 - c;nn eedsqjc0 = nn eedsqjc0 + a;nn eedsqjc1 = nn eedsqjc1 + b;nn eedsqjc2 = nn eedsqjc2 + c;elsecout << endl <<"试分配失败，系统无足够资源"<< endl;elsecout << endl << "Error!申请的资源大于需求值"<< endl;xz:cout << "nn"<< "要继续吗？ ( y-继续；n-终止):"cin >> contn;switch (contn)case 'y' :rrequest(); |case 'n' : break ;default :