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

南通大学计算机科学与技术学院专南通大学计算机科学与技术学院专业：学生姓名：学号：时间：操作系统课程设计报告操作系统课程设计报告操作系统模拟算法课程设计报告设计要求将本学期三次的实验集成实现：处理机管理；存储器管理；虚拟存储器的缺页调度。设计流程图主流程图开始的图形界面开始的图形界面存储器管理缺页调度处理机管理存储器管理缺页调度处理机管理LRU算法先进先出最佳适应法首次适应法先来先服务 LRU算法先进先出最佳适应法首次适应法先来先服务时间片轮转时间片轮转A.处理机调度1)先来先服务FCFS开始开始初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队调度数组中首个进程，并让数组中的下一位移到首位调度数组中首个进程，并让数组中的下一位移到首位计算并打印进程的完成时刻、周转时间、带权周转时间计算并打印进程的完成时刻、周转时间、带权周转时间其中：周转时间=完成时间-到达时间带权周转时间=周转时间/服务时间更改计时器的当前时间,即下一刻进程的开始时间更改计时器的当前时间,即下一刻进程的开始时间当前时间=前一进程的完成时间+其服务时间数组为空数组为空NY结束结束先来先服务算法流程2)时间片轮转法时间片轮转算法流程图B.存储器管理(可变式分区管理）1)首次适应法分配流程图开始申请xkb内存开始申请xkb内存由链头找到第一个空闲区分区大小≥xkb？大于分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针等于小于延链查找下一个空闲区到链尾了？作业等待返回是否登记已分配表返回分配给进程的内存首地址首次适应算法回收流程图开始开始输入完成进程的标号在分配区表中查找释放区p下邻分区空闲区前一个空闲区的后向指针指向p的后一个分区，p的后一个分区的前向指针指向p的前一个分区，且p的前一个分区大小更改为加上p的大小，释放p释放区p上邻分区空前一个分区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个分区，且p的后一个分区大小更改为加上p的大小释放区p上下均邻空闲区前一个空闲区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个空闲分区，且p的前一个空闲分区大小更改为加上p的大小再加上p的后一个空闲分区的大小，合并后的这个空闲区的后向指针指向p的下下个分区，如果p的下下个分区不为空，则其前向指针指向合并后的这个空闲区，释放p和p的下一个分区释放区p上下均不邻空闲区将p放在链首，并修改其状态位为空闲最佳适应法开始释放分区与上空闲分区相邻开始释放分区与上空闲分区相邻释放分区与下空闲分区相邻结束释放分区与下空闲分区相邻TFTFTF摘除链表中上分区。合并释放分区与上分区，将上空闲区长度修改为这二分区的长度。摘除链表中上下分区。合并这三个分区，将上空闲区长度修改为三个分区的长度。摘除链表中下分区。合并释放分区与下分区，将释放分区中长度修改为这二分区的长度。将合并的或释放的分区按长度升序重新插入到自由链表中。C.虚拟存储器的缺页调度1)先进先出FIFO开始FIFO的缺页中断处理开始FIFO的缺页中断处理查主存分块表查主存分块表有空闲块可用？有空闲块可用？Y分配一块Y分配一块NNJ=p[HEAD]J=p[HEAD]J的修改标志=1？J的修改标志=1？NNY输出“Y输出“将J页复写入交换区”输出“输出“装入L页”调整FIFO队列，将L插入队尾（HEAD=(HEAD+1)modM)调整FIFO队列，将L插入队尾（HEAD=(HEAD+1)modM)修改主存分块表和页表修改主存分块表和页表终止终止FIFO淘汰算法流程FIFO淘汰算法流程2）LRU开始LRU的缺页中断处理开始LRU的缺页中断处理查主存分块表查主存分块表有空闲块可用？有空闲块可用？Y分配一块Y分配一块NN找到栈底元素：J=p[M-1]找到栈底元素：J=p[M-1]J的修改标志=1？J的修改标志=1？NNY输出“Y输出“将J页送到入交换区”输出“输出“装入L页”调整堆栈，使HEAD所指元素及以下的元素下移P[HEAD]=L调整堆栈，使HEAD所指元素及以下的元素下移P[HEAD]=L修改主存分块表和页表修改主存分块表和页表终止终止LRU淘汰算法流程LRU淘汰算法流程实现原理主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。A.处理机调度1)先来先服务FCFS任务先来先服务的调度算法实现处理机调度。要求实现对FCFS算法的模拟实现计算出该算法的平均作业周转时间、平均带权作业周转时间。原理按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行。数据结构structtask_struct{charname;/*进程名称*/intnumber;/*进程编号*/floatcome_time;/*到达时间*/floatrun_begin_time;/*开始运行时间*/floatrun_time;/*运行时间*/floatrun_end_time;/*运行结束时间*/intpriority;/*优先级*/intorder;/*运行次序*/intrun_flag;/*调度标志*/}tasks[MAX];intfcfs()/*先来先服务算法*/进程名链接指针到达时间估计运行时间进程状态进程控制块结构实现方法建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。运行界面测试数据：作业名到达时间运行时间A028B09C03执行FCFS算法如下：2)时间片轮转法任务只对进程的运行模拟，将其运行时间加一，判断要求运行时间与已运行时间是否相等，若相等则表示进程结束，进程退出调度，释放资源。要求实现对RR算法的模拟实现显示执行完一个时间片的结果。原理时间片轮转算法中，系统将所有的就程序按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。数据结构temp->state='R';储器管理(可变式分区管理）1)首次适应法任务通过采用首次适应算法实现内存的分配与回收，并可以查看和显示当前内存现状。要求1.实现对FF算法的模拟实现2.输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入已运行的进程ID。原理FF算法要求空闲链已地址递增的次序连接。分配内存时，从链首开始顺序查找，直到找到第一个满足要求的空间并分配给进程，把分配后余下的空间仍然留在链表中。若从链首至链尾都不满足要求，则分配失败。该算法倾向于优先使用低地址的空间。数据结构intconstMEMO=256;现对BF算法的模拟实现2.输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入需要回收的内存块。原理最佳适应算法扫描整个未分配表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。此算法保证不会分割一个更大的区域，使得装入大作业的要求容易得到满足，同时，通常把空闲区按长度递增顺序排列，查找时总是从最小的一个空闲区开始，直至找到满足要求的分区为止，这时，最佳适应分配算法等同于首次适应算法。此算法的主存利用率好，所找出的分区如果最好满足要求则是最合适的。数据结构intconstMEMO=256;拟存储器的缺页调度1)先进先出FIFO任务采用先进先出FIFO算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。要求1.实现对FIFO算法的模拟实现2.输出每次执行的结果。原理基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。数据结构voidFIFO(){ intlength; intfifo[100]={0}; intpageLength; intfifoPage[100]={0}; inti,j; cout<<"***********************先进先出算法**************************"<<endl; pageLength=3; length=9; for(i=1;i<=length;i++){ intflag=0; for(j=1;j<=pageLength;j++){ if(fifo[i]==fifoPage[j]){ flag=1; j=pageLength+1; }elseif(fifoPage[j]==0){ fifoPage[j]=fifo[i]; j=pageLength+1; flag=1; } }if(flag==1) { } else { cout<<"→淘汰"<<fifoPage[1]<<endl; for(j=1;j<=pageLength;j++){ fifoPage[j]=fifoPage[j+1]; } fifoPage[pageLength]=fifo[i]; }实现方法当采用先进先出算法时，用一个数组构成先进先出队列，数组中各个元素为进程已在主存的页号，其队列头指针初始化为0.假设分配给每个进程的内存块数固定。当队列满需淘汰时，淘汰最先进入主存的一页。若该页修改过，还有存入磁盘。然后要把当前访问的页装入该块，并修改页表和存储分块表的对应标志。运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：4,4,3,5,1,1,2,3,2执行先进先出FIFO算法结果如下：2）LRU任务采用先进先出LRU算法实现分页管理的缺页调度，并输出每次调入调出的页号和运行结果。要求1.实现对LRU算法的模拟实现2.输出每次执行的结果。原理最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还有立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。如果主存中已无空闲块，可采用LRU算法进行缺页处理。数据结构voidLRU(){ intlength; intlru[100]={0}; intpageLength; intlruPage[100]={0};inti,j; cout<<"***********************最近最少使用LRU算法***********************"<<endl; pageLength=3; length=9; for(i=1;i<=length;i++){ intflag=0; for(j=1;j<=pageLength;j++){ if(lru[i]==lruPage[j]){ for(intcc=j;cc>0;cc--){ lruPage[cc]=lruPage[cc-1]; } lruPage[1]=lru[i]; flag=1; j=pageLength+1; }elseif(lruPage[j]==0){ for(intvv=j;vv>0;vv--){ lruPage[vv]=lruPage[vv-1]; } lruPage[1]=lru[i]; j=pageLength+1; flag=1; } }if(flag==1) { } else { cout<<"→淘汰"<<lruPage[pageLength]<<endl; for(j=pageLength;j>0;j--){ lruPage[j]=lruPage[j-1]; } lruPage[1]=lru[i]; }实现方法当采用LRU算法时，用一个数组构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针，初始化为0.假定分配给每个进程的内存块数固定不变。当队列满需淘汰时，操作系统选择栈底元素淘汰，其他元素向下移一个位置，将新调入页放栈指针指示的栈顶。当访问的页在栈中时，还应调整页从当前位置到栈顶。运行界面测试数据：页表长度：9；页框长度：3；页面请求数列：2,3,5,1,5,5,4,4,3执行最近最少使用LRU算法结果如下：总结与体会通过本次课程设计让我对于图形界面设计有了一定的思路和看法，同时我对先来先服务、时间片轮转、首次适应算法、最佳适应算法、先进先出和最近最少使用算法有了更详尽的认识。在编程的过程中发现会用到大量的指针，用指针来操作大量的数据比较方便，但最后应该记得释放资源。从这次实验中我发现我对于c++掌握也有所不足，程序经过了多次修改才得以完善，在以后应该注重编程方面的训练。此外我还更深入的理解了各个进程调度算法，及实现过程。在编写程序时查询了很多资料，间接提高了我的搜索能力。在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。特别是设计先来先服务调度算法和时间片轮转调度算法的时候，对进程的调度算法有了更好的深入理解。对进程管理中的等待队列，就绪队列，时间片等概念有了更深刻的印象。在设计此模拟操作系统的课设中，也加深了对c++知识的把握。解决了一些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的认知，也在同时提高了编程的能力，加强了实践。另外，我觉得此次课程设计虽然主要问题是在编程上，但是经过不断的去调试，还是成功的调试了出来。但是这几个程序用了多天的时间进行分析和修改，虽然出现了不少问题，但收获颇多！源代码：#include<iostream>#include<cstring>#include<cstddef>usingnamespacestd;intfcfsoutput();/*调度结果输出*/intfcfsinput();un_begin_time=time_temp;tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;tasks[i].run_flag=1;time_temp=tasks[i].run_end_time;number_schedul=i;tasks[number_schedul].order=i+1;}fcfsoutput();return0;}intfcfsinput(){ task_structtt;inti,j;un_time=28;tasks[1].run_time=9;tasks[2].run_time=3;ame='A'; tasks[1].name='B'; tasks[2].name='C'; cout<<"************************先来先服务算法************************"<<endl<<endl;for(i=0;i<counter;i++){tasks[i].run_begin_time=0;tasks[i].run_end_time=0;tasks[i].order=0;tasks[i].run_flag=0;}return0;}intfcfsoutput()/*调度结果输出*/{inti;floatturn_round_time=0,f1,w=0;cout<<"作业名到达时间运行时间开始时间停止时间运行次序周转时间"<<endl;for(i=0;i<counter;i++){f1=tasks[i].run_end_time-tasks[i]e_time;turn_round_time+=f1;w+=(f1/tasks[i].run_time);cout<<""<<tasks[i].name<<'\t'<<""<<tasks[i]e_time<<'\t'<<""<<tasks[i].run_time<<'\t'<<""<<tasks[i].run_begin_time<<'\t'<<""<<tasks[i].run_end_time<<'\t'<<tasks[i].order<<'\t'<<f1<<'\t'<<endl;}cout<<"平均周转时间："<<turn_round_time/counter<<endl;cout<<"平均带权周转时间："<<w/counter<<endl;cout<<"";return0;}/**/intrr(){intn=3,num=0;node*head=NULL;node*tail=NULL;cout<<"*********************时间片轮转调度算法*********************"<<endl<<endl;for(inti=0;i<n;i++){node*temp=newnode; if(i==0)strcpy(temp->name,"A");