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

南通大学计算机科学与技术学院操作系统课程设计报告专业：计嵌151学生姓名：王志宏学号：1513052018时间：2017/6/28第 48 页设计一个小型的操作系统设计要求将本学期三次的实验集成实现：1. 中断处理2. 作业调度3. PV原语4. 死锁5. 页面替换6. 磁盘调度(一)设计流程图主流程图开始的图形界面作业调度PV原语死锁页面替换磁盘调度中断处理哲学家吃通心面先来先服务时钟银行家算法先进先出算法LRU算法先来先服务1. 中断处理模拟时钟中断的产生与设计一个对时钟中断事件进行处理的模拟程序。计算机系统工作过程中，若出现中断事件，硬件就把它记录在中断寄存器中。中断寄存器的每一位可与一个中断事件对应，当出现某中断事件后，对应的中断寄存器的某一位就被置成1。处理器每执行一条指令后，必须查中断寄存器，当中断寄存器内容不为0时，说明有中断事件发生。硬件把中断寄存器内容以与现行程序的断点存在主存的固定单元，且让操作系统的中断处理程序占用处理器来处理出现的中断事件。操作系统分析保存在主存固定单元中的中断寄存器内容就可知道出现的中断事件的性质，从而作出相应的处理。本实习中，用从键盘读入信息来模拟中断寄存器的作用，用计数器加 1 来模拟处理器执行了一条指令。每模拟一条指令执行后，从键盘读入信息且分析，当读入信息=0 时，表示无中断事件发生，继续执行指令；当读入信息=1 时，表示发生了时钟中断事件，转时钟中断处理程序 1)先来先服务FCFS开始初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队调度数组中首个进程，并让数组中的下一位移到首位计算并打印进程的完成时刻、周转时间、带权周转时间其中：周转时间 = 完成时间 - 到达时间带权周转时间=周转时间/服务时间更改计时器的当前时间,即下一刻进程的开始时间当前时间=前一进程的完成时间+其服务时间数组为空NY结束 先来先服务算法流程 1）哲学家吃通心面问题哲学家吃通心面：在这道题目里，每把叉子必须互斥使用，当一位哲学家吃通心面之前必须执行两个P操作，获得自己左右两边的叉子，在吃完通心面后必须执行两个V操作，放下叉子。4. 死锁1） 银行家算法 1)先进先出FIFO开始FIFO的缺页中断处理查主存分块表有空闲块可用？Y分配一块NJ=pHEADJ的修改标志=1？NY输出“将J页复写入交换区”输出“装入L页”调整FIFO队列，将L插入队尾（HEAD=(HEAD+1)modM)修改主存分块表与页表终止FIFO淘汰算法流程2）LRU开始LRU的缺页中断处理查主存分块表有空闲块可用？Y分配一块N找到栈底元素：J=pM-1J的修改标志=1？NY输出“将J页送到入交换区”输出“装入L页”调整堆栈，使HEAD所指元素及以下的元素下移PHEAD=L修改主存分块表与页表终止LRU淘汰算法流程6. 磁盘调度1）先来先服务算法FCFS）（二）实现原理主界面设计一个框架分别去链接处理机管理、存储器管理与缺页调度相关的程序。1. 中断 1)先来先服务FCFS（一） 任务先来先服务的调度算法实现处理机调度。（二） 要求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 priority; /*优先级*/ int order; /*运行次序*/ int run_flag; /*调度标志*/ tasksMAX;int fcfs()/*先来先服务算法*/进程名链接指针到达时间估计运行时间进程状态进程控制块结构（五） 实现方法建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。（六） 运行界面测试数据：作业名到达时间运行时间A028B09C03执行FCFS算法如下：3. 死锁假定本系统中的各个所需资源均是独占型资源，在进程运行的过程中不再释放，故只需要遍历链表将各个进程中所需的资源统计出来，只要不大于系统中预设的即可，一旦进程所需的资源大于系统中的最大量，给予用户选择kill一进程，已达到释放资源的目的。死锁检测函数：void sisuo() 死锁解除函数：void safe() 1)先进先出FIFO（一） 任务采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号与运行结果。（二） 要求2.输出每次执行的结果。（三） 原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。（四） 数据结构void FIFO()int length;int 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<<" 淘汰"<<fifoPage1<<endl;for(j=1;j<=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;（五） 实现方法当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进程已在主存的页号，其队列头指针初始化为0.假设分配给每个进程的内存块数固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存入磁盘。然后要把当前访问的页装入该块，并修改页表与存储分块表的对应标志。（六） 运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：4,4,3,5,1,1,2,3,2执行先进先出FIFO算法结果如下：2）LRU（一） 任务采用先进先出LRU算法实现分页管理的缺页调度，并输出每次调入调出的页号与运行结果。（二） 要求2.输出每次执行的结果。（三） 原理最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。如果主存中已无空闲块，可采用LRU算法进行缺页处理。（四） 数据结构void LRU()int length;int lru100=0;int pageLength;int lruPage100=0; int i,j;cout<<" *最近最少使用LRU算法*"<<endl;pageLength=3;length=9; 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;lruPage1=lrui;flag=1;j=pageLength+1;else if(lruPagej=0)for(int vv=j;vv>0;vv-)lruPagevv=lruPagevv-1;lruPage1=lrui;j=pageLength+1;flag=1; if(flag=1)elsecout<<" 淘汰"<<lruPagepageLength<<endl;for(j=pageLength;j>0;j-)lruPagej=lruPagej-1;lruPage1=lrui;（五） 实现方法当采用LRU算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针，初始化为0.假定分配给每个进程的内存块数固定不变。当队列满需淘汰时，操作系统选择栈底元素淘汰，其他元素向下移一个位置，将新调入页放栈指针指示的栈顶。当访问的页在栈中时，还应调整页从当前位置到栈顶。（六） 运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：2,3,5,1,5,5,4,4,3执行最近最少使用LRU算法结果如下：5. 磁盘调度1）先来先服务算法FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。（三）总结与体会通过本次课程设计让我对于图形界面设计有了一定的思路与看法，同时我对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出与最近最少使用算法有了更详尽的认识。在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该记得释放资源。从这次实验中我发现我对于c+掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。此外我还更深入的理解了各个进程调度算法，与实现过程。在编写程序时查询了很多资料，间接提高了我的搜索能力。在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在与价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计与管理以与调度的算法都有助于对书本知识的理解与掌握。特别是设计先来先服务调度算法与时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。对进程管理中的等待队列，就绪队列，时间片等概念有了更深刻的印象。在设计此模拟操作系统的课设中，也加深了对c+知识的把握。解决了一些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。另外，我觉得此次课程设计虽然主要问题是在编程上，但是经过不断的去调试，还是成功的调试了出来。但是这几个程序用了多天的时间进行分析与修改，虽然出现了不少问题，但收获颇多！源代码：#include<iostream>#include<cstring>#include <cstddef>#include <windows.h> #include <time.h> #include <string> #include <assert.h> #include<stdio.h>#include<stdlib.h>using namespace std;int fcfsoutput(); /*调度结果输出*/int fcfsinput(); /进程参数的初始化void kaishi();#define MAX 10#define maxsize 1000struct node /建立链表来存放进程数据 char name5; /进程名称 int need_time; /所需要的时间 int allocation; /占用cpu的情况 char state; /目前的状态 R为运行，E为运行完毕 node *next; /链表的尾结点 struct task_structchar 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();float time_temp = 0;int i;int number_schedul;time_temp = tasks0e_time;for (i = 0; i<counter; 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 fcfsinput()task_struct tt;int i, j;/初始化进程数counter = 3;/初始化每个到达系统的时间为5、7、8tasks0e_time = rand() % 9;tasks1e_time = rand() % 9;tasks2e_time = rand() % 9;for (i = 1; i<3; i+)for (j = 0; j<3 - i; j+)if (tasksje_time>tasksj + 1e_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.name = 'B'tasks2.name = 'C'cout << "*先来先服务算法*" << 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;return 0;int fcfsoutput() /*调度结果输出*/int i;float turn_round_time = 0, f1, w = 0;cout << " *先来先服务*" << endl;cout << "作业名 到达时间 运行时间 开始时间 停止时间 运行次序 周转时间" << endl;for (i = 0; i<counter; i+)f1 = tasksi.run_end_time - tasksie_time;turn_round_time += f1;w += (f1 / tasksi.run_time);cout << " " << tasksi.name << 't' << " " << tasksie_time << 't' << " "<< tasksi.run_time << 't' << " " << tasksi.run_begin_time << 't' << " "<< tasksi.run_end_time << 't' << tasksi.order << 't' << f1 << 't' << endl;cout << "平均周转时间：" << turn_round_time / counter << endl;cout << "平均带权周转时间：" << w / counter << endl;cout << " "return 0;void zuoyediaodu()/作业调度int n;cout << "t1.先来先服务算法t 2.返回开始菜单" << 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 << " *先进先出算法*" << endl;pageLength = 3;length = 9;cout << "时刻t" << 't'for (i = 0; i<length; i+)cout << i << 't'cout << endl << "引用串" << 't'for (i = 1; i <= length; i+)fifoi = rand() % 5 + 1;cout << fifoi << 't'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 << " 淘汰" << fifoPage1 << endl;for (j = 1; j <= pageLength; j+)fifoPagej = fifoPagej + 1;fifoPagepageLength = 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+)cout << fifoPages << 't'cout << endl;void LRU()int length;int lru100 = 0 ;int pageLength;int lruPage100 = 0 ;int i, j;cout << " *最近最少使用LRU算法*" << endl;pageLength = 3;length = 9;cout << "时刻t" << 't'for (i = 0; i<length; i+)cout << i << 't'cout << endl << "引用串" << 't'for (i = 1; i <= length; i+)lrui = rand() % 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;lruPage1 = lrui;flag = 1;j = pageLength + 1;else if (lruPagej = 0)for (int vv = j; vv>0; vv-)lruPagevv = lruPagevv - 1;lruPage1 = lrui;j = pageLength + 1;flag = 1;if (flag = 1)elsecout << " 淘汰" << lruPagepageLength << endl;for (j = pageLength; j>0; j-)lruPagej = 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 <= pageLength; s+)cout << lruPages << 't'cout << endl;void queye()/页面替换int n;cout << endl;cout << "t1.先进先出算法t2.LRU算法t3.返回开始菜单" << endl;cin >> n;switch (n)case 1: FIFO(); kaishi(); break;case 2: LRU(); kaishi(); break;case 3: kaishi(); kaishi(); break;/*判断输入数据是否有效*/int decide(char str) /判断输入数据是否有效int i = 0;while (stri != '0')if (stri<'0' | stri>'9')return 0;break;i+;return i;/*将字符串转换成数字*/int trans(char str, int a) /将字符串转换成数字int i;int sum = 0;for (i = 0; i<a; i+)sum = sum + (int)(stri - '0')*pow(10, a - i - 1);return sum;/*先来先服务调度算法*/void FCFS(int cidao, int m) /磁道号数组，个数为mint now;/当前磁道号int sum = 0; /总寻道长度int j, i;int a;char str100;float ave; /平均寻道长度cout << " *先来先服务*" << endl;cout << "磁盘请求序列为："for (i = 0; i<m; i+) /按先来先服务的策略输出磁盘请求序列cout << cidaoi << " "cout << endl;cout << "请输入当前的磁道号："B: cin >> str; /对输入数据进行有效性判断a = decide(str);if (a = 0)cout << "输入数据的类型错误,请重新输入！" << endl;goto B;elsenow = trans(str, a); /输入当前磁道号sum += abs(cidao0 - now);cout << "磁盘扫描序列为："for (i = 0; i<m; i+) /输出磁盘扫描序列cout << cidaoi << " "for (i = 0, j = 1; j<m; i+, j+) /求平均寻道长度sum += abs(cidaoj - cidaoi);ave = (float)(sum) / (float)(m);cout << endl;cout << "平均寻道长度：" << ave << endl;void cipandiaodu() /磁盘调度int a;int c; /菜单项int cidaomaxsize;int i = 0, count;char str100;cout << endl;cout << "t1.先来先服务t2.返回开始菜单" << endl;F:cin >> str; /对输入数据进行有效性判断a = decide(str);if (a = 0)cout << "输入数据的类型错误,请重新输入！" << endl;goto F;/输入错误，跳转到F，重新输入elsec = trans(str, a);cout << "请输入磁道序列（0结束）：" << endl;A:cin >> str; /对输入数据进行有效性判断a = decide(str);if (a = 0)cout << "输入数据的类型错误,请重新输入！" << endl;goto A;/输入错误，跳转到A，重新输入elsecidaoi = trans(str, a);i+;while (cidaoi - 1 != 0)cin >> str; /对输入数据进行有效性判断a = decide(str);if (a = 0)cout << "输入数据的类型错误,请重新输入！" << endl;elsecidaoi = trans(str, a);i+;count = i - 1; /要访问的磁道数cout << "你输入的磁道序列为："for (i = 0; i<count; i+)cout << cidaoi << " " /输出磁道序列cout << endl;switch (c)case 1: /使用FCFS算法FCFS(cidao, count); kaishi(); break;case 2: kaishi(); kaishi(); break;bool tools5; /全局变量，用餐工具CRITICAL_SECTION cs; /信号量, 在线程中使用，临界区class Philosopherprivate:int number;int status; /标记当前哲学家的状态,0表示正在等待/ (即处于饥饿状态),1表示得到两支筷子正在吃饭,2表示正在思考public:Philosopher(int num = 0) : status(2), number(num) const int find()return number;const int getinfo()return status;void Change(); /状态改变函数void dead_lock();void Philosopher:dead_lock()EnterCriticalSection(&cs); /进入临界区string s;if (status = 1)toolsnumber % 5 = true;/ tools(number-1)%5=true;status = 2;else if (status = 2)status = 0;/tools(number-1)%5=false;/tools(number-1)%5=true;else if (status = 0)toolsnumber % 5 = false;tools(number - 1) % 5 = false;status = 1;LeaveCriticalSection(&cs);/ cout<<"*"void Philosopher:Change()EnterCriticalSection(&cs); /进入临界区if (status = 1) /正在进餐toolsnumber % 5 = true; /放下左手工具tools(number - 1) % 5 = true; /放下右手工具status = 2; /改变状态为思考else if (status = 2) /思考中status = 0; /改变状态为等待else if (status = 0) /等待中if (toolsnumber % 5 && tools(number - 1) % 5) /左右手两边工具均为空闲状态toolsnumber % 5 = false; /拿起左手工具tools(number - 1) % 5 = false; /拿起右手工具status = 1;LeaveCriticalSection(&cs);string print(Philosopher *pA)/pA->Change(); int i = pA->getinfo();string str;if (i = 0)s