操作系统实验报告

CENTRALSOUTH操作系统原理学生姓名徐心萌学号0919150112专业班级物联网工程1501学院信息科学与工程学院完成时间2017年6月9日实验报告目录实验一银行家算法........................................4一、实验目的..........................................4二、实验要求..........................................4三、实验原理..........................................4四、程序框图..........................................6五、实验结果..........................................7六、实验小结..........................................8实验二页面置换算法......................................9一、实验目的..........................................9二、实验要求..........................................9三、实验原理..........................................9四、程序框图.........................................10五、实验结果.........................................12六、实验小结.........................................12实验三调度算法.........................................13一、实验目的.........................................13二、实验要求.........................................13三、实验原理.........................................13四、程序框图.........................................14五、实验结果.........................................16六、实验小结.........................................18实验四地址转换.........................................19一、实验目的.........................................19二、实验要求.........................................19三、实验原理.........................................19四、程序框图.........................................20五、实验结果.........................................22六、实验小结.........................................23程序清单................................................24实验一银行家算法一、实验目的1、进一步深入理解死锁的概念、产生死锁的原因、避免死锁和解除死锁的方法；2、掌握利用银行家算法避免死锁的方法。二、实验要求模拟银行家算法避免死锁的实现过程三、实验原理银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，系统必须首先确定是否有足够的资源分配给该进程，然后计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则让进城等待。数据结构如下：（1）可利用资源向量Available：含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max：一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation：一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need：一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。四、程序框图YNYY系统分配资源系统不分配资源开始数据结构初始化资源请求超过该进程的需求值?进程Pi发出资源请求资源请求超过当前可用资源值？系统资源试探性分配是否存在一个安全序列？结束NN五、实验结果六、实验小结银行家算法是一个思路很清楚的办法，在编写的过程中，在安全性算法那一步思考了很久，思考找到安全序列的办法，最后选择用贪心法求得安全序列。整个算法的核心主要是对于安全状态和不安全状态的判断，分两步，第一部是系统对请求值的合法性进行检查，第二部是安全性检查，看是否能找到看安全序列，若试探性分配后能找到安全序列，则进行分配，否则不予分配，从而达到避免死锁的目的。实验二页面置换算法一、实验目的1、进一步了解页面置换的原理和要求；2、理解最佳置换算法、先进先出、最近最久未使用、最少使用等各类置换算法的原理。二、实验要求利用各类置换算法实现对页面的置换三、实验原理1、先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。2、最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。四、程序框图（FIFO置换算法）Y直接调用页面将页面调入内存开始页面申请页面是否在内存里？内存页面数是否达到上限？替换最先进入内存的页面结束YNN（LRU置换算法）Y直接调用页面将页面调入内存开始页面申请页面是否在内存里？内存页面数是否达到上限？替换距离上一次访问时间最久的页面结束YNN五、实验结果六、实验小结本实验研究了若干页面置换算法，在整个学习的过程中收获很多。最后重点学习了先进先出和最近最久未使用这两种算法，这两种算法均是对于最佳置换算法的改进。实验结果显示在234432134这种序列下LRU置换算法的缺页率并没有比FIFO算法更优秀，这源自于序列的特点，一般情况下，LRU算法考虑到页面调入内存后的使用情况，结果比FIFO更优一些。实验三调度算法一、实验目的1、了解处理机调度的层次和调度算法的目标，调度的实质与意义；2、熟悉各类调度算法的原理与实际应用。二、实验要求模拟实现各类调度算法三、实验原理1、先来先服务(FCFS)调度算法先来先服务(FCFS)调度算法是一种最简单的调度算法。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。2、短作业优先（SJF）调度算法最短优先调度算法是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。3、时间片轮转调度算法在时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。4、优先级调度算法当把优先级调度算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程四、程序框图（FIFO调度算法）Y开始处理机是否存在空闲？选择最先进入就绪队列的进程调入结束N（SJF调度算法）（时间片轮转调度算法）Y开始处理机是否存在空闲？选择预计运行时间最短的调入结束NYY开始就绪队列是否为空？选择第i个进程调入一个时间片后是否运行完毕？加入队尾i++结束NN（优先级优先调度）五、实验结果Y开始处理机是否存在空闲？选择优先级最高的调入结束N六、实验小结调度算法是操作系统最基础的算法之一，本次实验通过对先来先服务、短作业优先、优先级优先、时间片轮转等算法的模拟进一步熟悉了各类调度算法，无论是在加深对作业调度或者进程调度的理解上，都收获很大。实验四地址转换一、实验目的1、熟悉基本的分页、分段存储管理方式及其原理；2、理解在分页分段存储管理方式中逻辑地址与物理地址的转化。二、实验要求模拟分页、分段存储管理方式逻辑地址与物理地址的转化三、实验原理1、分页存储管理方式：地址转换时，先从页表控制寄存器中找到相应的页表，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。2、分段存储管理方式：逻辑地址空间由一组段组成。每个段都有名字和长度。地址指定了段名称和段内偏移。因此用户通过两个量来指定地址：段名称和偏移。段是编号的，通过段号而非段名称来引用。因此逻辑地址由有序对构成：segment-number,offset(段号s,段内偏移d)段偏移d因该在0和段界限之间，如果合法，那么就与基地址相加而得到所需字节在物理内存中的地址。因此段表是一组基地址和界限寄存器对。四、程序框图（分页存储管理方式）开始输入逻辑地址是否发生越界？计算块号和偏移量查找页表计算物理地址输出物理地址结束输出错误信息YN（分段存储管理方式）开始输入段号和偏移量是否发生越界？查找段表计算物理地址输出物理地址结束输出错误信息YN五、实验结果六、实验小结总的来说，逻辑地址和物理地址的转化在计算上是一个简单的操作，但是通过这次实验我们更应该了解到它的本质是对不同存储管理方式的映射关系，了解段表、页表等结构，从而更好地理解存储管理方式，这让我受益匪浅。程序清单1、银行家算法#includestdio.h#includestdlib.h#ifndefMY_MAX#defineMY_MAX5#endifintmax1[