搜索
操作系统课程设计报告南通大学计算机科学与技术学院操作系统课程设计报告专业：学生姓名：学号：时间：操作系统课程设计报告第1页共40页操作系统模拟算法课程设计报告设计要求将本学期三次的实验集成实现：A.处理机管理；B.存储器管理；C.虚拟存储器的缺页调度。设计流程图主流程图开始的图形界面处理机管理存储器管理缺页调度先来先服务时间片轮转首次适应法最佳适应法先进先出LRU算法操作系统课程设计报告第2页共40页A.处理机调度1)先来先服务FCFSNY先来先服务算法流程开始初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队调度数组中首个进程，并让数组中的下一位移到首位计算并打印进程的完成时刻、周转时间、带权周转时间其中：周转时间=完成时间-到达时间带权周转时间=周转时间/服务时间更改计时器的当前时间,即下一刻进程的开始时间当前时间=前一进程的完成时间+其服务时间数组为空结束操作系统课程设计报告第3页共40页2)时间片轮转法开始输入进程总数指针所指的进程是否结束输入各进程信息输出为就绪状态的进程的信息更改正在运行的进程的已运行时间跳过已结束的程序结束N指向下一个进程Y如果存在下一个进程的话YN输出此时为就绪状态的进程的信息时间片轮转算法流程图操作系统课程设计报告第4页共40页B.存储器管理(可变式分区管理）1)首次适应法分配流程图申请xkb内存由链头找到第一个空闲区分区大小≥xkb？大于分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针等于小于延链查找下一个空闲区到链尾了？作业等待返回是否登记已分配表返回分配给进程的内存首地址开始操作系统课程设计报告第5页共40页首次适应算法回收流程图操作系统课程设计报告第6页共40页2）最佳适应法开始输入完成进程的标号在分配区表中查找释放区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放在链首，并修改其状态位为空闲操作系统课程设计报告第7页共40页回收内存流程C.虚拟存储器的缺页调度开始释放分区与上空闲分区相邻释放分区与下空闲分区相邻结束释放分区与下空闲分区相邻TFTFTF摘除链表中上分区。合并释放分区与上分区，将上空闲区长度修改为这二分区的长度。摘除链表中上下分区。合并这三个分区，将上空闲区长度修改为三个分区的长度。摘除链表中下分区。合并释放分区与下分区，将释放分区中长度修改为这二分区的长度。修改自由链表中分区地址：起始地址为上空闲区地址，摘除链表中上分区，修改表项将合并的或释放的分区按长度升序重新插入到自由链表中。操作系统课程设计报告第8页共40页1)先进先出FIFO2）LRU开始FIFO的缺页中断处理查主存分块表有空闲块可用？分配一块J的修改标志=1？J=p[HEAD]输出“将J页复写入交换区”输出“装入L页”调整FIFO队列，将L插入队尾（HEAD=(HEAD+1)modM)修改主存分块表和页表终止NYNYFIFO淘汰算法流程操作系统课程设计报告第9页共40页实现原理开始LRU的缺页中断处理查主存分块表有空闲块可用？分配一块J的修改标志=1？找到栈底元素：J=p[M-1]输出“将J页送到入交换区”输出“装入L页”调整堆栈，使HEAD所指元素及以下的元素下移P[HEAD]=L修改主存分块表和页表终止NYNYLRU淘汰算法流程操作系统课程设计报告第10页共40页主界面设计一个框架分别去链接处理机管理、存储器管理和缺页调度相关的程序。A.处理机调度1)先来先服务FCFS（一）任务先来先服务的调度算法实现处理机调度。（二）要求1.实现对FCFS算法的模拟实现2.计算出该算法的平均作业周转时间、平均带权作业周转时间。（三）原理按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行。（四）数据结构structtask_struct{charname;/*进程名称*/intnumber;/*进程编号*/floatcome_time;/*到达时间*/floatrun_begin_time;/*开始运行时间*/floatrun_time;/*运行时间*/floatrun_end_time;/*运行结束时间*/intpriority;/*优先级*/intorder;/*运行次序*/intrun_flag;/*调度标志*/}tasks[MAX];intfcfs()/*先来先服务算法*/进程名链接指针到达时间估计运行时间进程状态进程控制块结构（五）实现方法建立一个链表按照到达CPU的时间从小到大排列，只需从第一个作业（头结点）依次调度到最后一个作业（尾结点）。操作系统课程设计报告第11页共40页（六）运行界面测试数据：作业名到达时间运行时间A028B09C03执行FCFS算法如下：2)时间片轮转法（一）任务只对进程的运行模拟，将其运行时间加一，判断要求运行时间与已运行时间是否相等，若相等则表示进程结束，进程退出调度，释放资源。（二）要求1.实现对RR算法的模拟实现2.显示执行完一个时间片的结果。（三）原理时间片轮转算法中，系统将所有的就程序按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。（四）数据结构temp-state='R';//初始状态每个进程均为运行态temp-allocation=0;//初始时进程均不占用cpunum+=temp-need_time;//用num来限制循环的次数（五）实现方法处理器调度总是选择标志单元指示的进程运行。执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。当一个进程被选中运行时，必须设置该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，操作系统课程设计报告第12页共40页若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。进程名链接指针到达时间估计运行时间进程状态进程控制块结构（六）运行界面测试数据：作业号执行时间/sA1B2C1执行时间片轮转算法RR如下：B.存储器管理(可变式分区管理）操作系统课程设计报告第13页共40页1)首次适应法（一）任务通过采用首次适应算法实现内存的分配与回收，并可以查看和显示当前内存现状。（二）要求1.实现对FF算法的模拟实现2.输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入已运行的进程ID。（三）原理FF算法要求空闲链已地址递增的次序连接。分配内存时，从链首开始顺序查找，直到找到第一个满足要求的空间并分配给进程，把分配后余下的空间仍然留在链表中。若从链首至链尾都不满足要求，则分配失败。该算法倾向于优先使用低地址的空间。（四）数据结构intconstMEMO=256;//初始化常类型MEMO，用MEMO表示内存大小（常类型的变量或对象的值是不能被更新的）structFreeMemory{intID;intStartAdd;intSize;boolState;//定义state为布尔型变量，其值只有真（TRUE)和假（FALSE)FreeMemory*Next;};FreeMemory*AllocTable=newFreeMemory;//建立全局管理表用于内与回收FreeMemory*PtrforCycleFit=AllocTable;//为循环首次适应定义的指针，此指针用于指向当前查找的起始地址;//初始化内存函数voidMemoryInit(FreeMemory*&tempAdd){tempAdd-ID=0;//初始化当前进程为空tempAdd-Size=MEMO;//初始化可分配空间为内存大小tempAdd-StartAdd=0;//初始化起始地址为0tempAdd-State=false;//初始化状态为未分配tempAdd-Next=NULL;//初始化下一个进程也为空}//反馈内存现态voidDispMemory(){FreeMemory*temp=AllocTable;//全局管理表反映内存状态cout系统总内存:MEMOendl;for(;temp;temp=temp-Next)cout进程ID：temp-ID大小：temp-Size起始操作系统课程设计报告第14页共40页地址:temp-StartAdd是否已分配:temp-Stateendl;}//输出内存的各个变量（五）实现方法可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区的个数是可以调整的。当需要装入一个作业时，根据作业需要的贮存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被分配作业占用，有的分区空闲。在空闲区表中，按空闲区首地址从低到高进行登记。当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时，要考虑相邻空间区合并问题。作业的释放区与空闲区的邻接分以下4种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D、释放区上邻空闲区不邻接。（六）运行界面系统总内存为256时，分别为进程1、2、3分配大小为64、128、64的内存。执行首次适应算法分配内存如下：若回收进程2的内存，执行结果如下：2）最佳适应法（一）任务通过采用最佳适应算法实现内存的分配与回收，并可以查看和显示当前内存现状。操作系统课程设计报告第15页共40页（二）要求1.实现对BF算法的模拟实现2.输入要进行分配内存的进程ID和相应所需内存大小，回收内存时输入需要回收的内存块。（三）原理最佳适应算法扫描整个未分配表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。此算法保证不会分割一个更大的区域，使得装入大作业的要求容易得到满足，同时，通常把空闲区按长度递增顺序排列，查找时总是从最小的一个空闲区开始，直至找到满足要求的分区为止，这时，最佳适应分配算法等同于首次适应算法。此算法的主存利用率好，所找出的分区如果最好满足要求则是最合适的。（四）数据结构intconstMEMO=256;//初始化常类型MEMO，用MEMO表示内存大小（常类型的变量或对象的值是不能被更新的）structFreeMemory{intID;intStartAdd;intSize;boolState;//定义state为布尔型变量，其值只有真（TRUE)和假（FALSE)FreeMemory*Next;};boolAlloc_BestFit(intid