实验四 用先进先出（FIFO ）页面调度算法处理缺页中断
1．实验目的
深入了解页式存储管理如何实现地址转换；
进一步认识页式虚拟存储管理中如何处理缺页中断。
2．实验预备知识
页式存储管理中的地址转换的方法；
页式虚拟存储的缺页中断处理方法。
3．实验内容
编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所作工作进程测试。
假定主存64KB ，每个主存块1024字节，作业最大支持到64KB ，系统中每个作业分得主存块4块。
4．提示与讲解
页式存储管理中地址转换过程很简单，假定主存块的大小为2n 字节，主存大小为2m'字节和逻辑地址m 位，则进行地址转换时，首先从逻辑地址中的高m-n 位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n 位，最后从逻辑地址中取得低n 位放入物理地址的低n 位就得到了物理地址，过程如图1所示。
图1 页式存储管理系统地址转换示意图
地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图2所示（实验中假定主存64KB ，每个主存块1024字节，即n=10,m'=16，物理地址中块号6位、块内地址10位；作业最大64KB ，即m=16，逻辑地址中页号6位、页内地址10位）。
在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，
逻辑地址
由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。这样，在实验中页表格式如图2所示。
页表用数组模拟，在实验中页表数据结构定义为(同学们可自行定义其它功能等价的结构)：
define n 32 /*实验中假定的页表长度，页表的长度实际上是由系统按照作业长度决定的*/
struct
{int lnumber; /*页号*/
int flag; /*表示该页是否在主存，“1”表示在主存，“0”表示不在主存*/
int pnumber; /*该页所在主存块的块号*/
int write; /*该页是否被修改过，“1”表示修改过，“0”表示没有修改过*/
int dnumber; /*该页存放在磁盘上的位置，即磁盘块号*/ }page[n]; /*页表定义*/
图2 模拟地址转换的流程图
缺页处理过程简单阐述如下：
①根据当前执行指令中逻辑地址中的页号查页表，判断该页是否在主存储器中，若该页标志为“0”，形成缺页中断。中断装置通过交换PSW让操作系统的
中断处理程序占用处理器；
②操作系统处理缺页中断的方法就是查主存分配表，找一个空闲主存块；若无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。若在执行过程中该页被修改过，则需将该页信息写回磁盘，否则不必写回；
③找出该页的磁盘位置，启动磁盘读出该页信息，把磁盘上读出的信息装入第2步找到的主存块，修改页表中该页的标志为“1”；
④由于产生缺页中断的那条指令没有执行完，所以页面装入后应重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已在主存中，所以可正常执行。
关于第②步的查找装入新页面的主存块的处理方式，不同系统采用的策略可能有所不同，这里采用局部置换算法，就是每个作业分得一定的主存块，只能在分得的主存块内查找空闲块，若无空闲主存块，则从该作业中选择一个页面淘汰出主存。实验中使用局部置换算法。
使用局部置换算法时，存在这样一个问题：就是在分配给作业主存空间时，装入哪些页？有的系统采取不装入任何一页，当执行过程中需要时才将其调入。有的系统采用页面预置的方法，就是估计可能某些页面会先用到，在分配主存块后将这些页面装入。实验中，采用第二种方法，分配主存空间时将前几页调入主存，假定系统中每个作业分得主存块m（m=4）块，则将第0~m-1页装入主存。
因为是模拟硬件工作，所以实验中如果访问的页不在主存时，则输出该页页号，表示硬件产生缺页中断，然后直接转去缺页中断处理；由于采用页面预置方法，在给定的主存块中一定无空闲块，只能淘汰已在主存的一页；没有启动磁盘的工作，淘汰的页需要写回磁盘时，用输出页号表示，调入新的一页时，将该页在页表中的存在标志置为“1”，输出页号表示将该页调入主存。
图3 采用先进先出页面置换算法的缺页中断流程图
主存中无空闲块时，为装入一个页面，必须按某种算法从已在主存的页中选择一页，将它暂时调出主存，让出主存空间，用来存放需装入的页面，这个工作称为“页面调度”。如何选择调出的页是很重要的，常用的页面调度算法有先进先出算法、最近最少用算法和最近最不常用算法。实验中使用先进先出调度算法。先进先出调度算法总是选择驻留在主存时间最长的一页调出。先进先出算法简单，易实现。可以把在主存储器的页的页号按进入主存的先后次序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排入队尾。实验中，用一个数组存放页号的队列。假定分配给作业的主存块数为m，数组可由m个元素组成，p[0]，p[1]……p[m-1]；队首指针head；采用页面预置的方法，页号队列的长度总是m，tail等于(head+1)%m。因此可以使用一个指针，只用head即可。在装入一个新的页时，装入页和淘汰页同时执行，当装入一个新的页时，将其页号存入数组：
淘汰页的页号=p[head];
p[head]=新装入页的页号；
head=(head+1)%m;
实验中，采用先进先出页面置换算法的缺页中断流程图如图3所示。
图4一条指令执行的模拟流程图
实验执行一条指令时，不模拟指令的执行，只是考虑指令执行是否修改页面，若修改页面，则将该页的页表中修改标志为置“1”，然后输出转换后的物理地址，并输出物理地址来表示一条指令执行完成；如果访问的页不在主存时，则产生缺页中断，然后直接转去缺页中断处理，最后模拟中断返回，就是返回重新进行地址转换。一条指令执行的模拟流程图如图4所示。
因为没有实际主存，所以在模拟程序中首先手工输入页表信息，创建该作业的页表；然后循环执行假定的指令，观察地址转换情况。
5. 实验报告的内容
（1）实验题目。
（2）程序中使用的数据结构及符号说明。
（3）编写一份源程序并附上注释。
（4）打印显示初始页表，每次调出（要调出一页时）和装入的页号以及执行最后一条指令后在主存中的页面号（即数组的值）。
《计算机操作系统》实验报告 实验五：页面调度算法模拟 学校：╳╳╳ 院系：╳╳╳ 班级：╳╳╳ 姓名：╳╳╳ 学号：╳╳╳
指导教师：╳╳╳ 目录 一、实验题目 (3) 二、实验学时 (4) 三、指导老师 (4) 四、实验日期 (4) 五、实验目的 (4) 六、实验原理 (4) 6.1页面的含义 (4) 6.2 页面置换算法的含义 (4) 6.3 置换算法 (4) 6.3.1最佳置换算法(Optimal) (5) 6.3.2先进先出(FIFO)页面置换算法 (5) 6.3.3 LRU置换算法 (5) 七、实验步骤及结果 (5)
7.1 验证最佳置换算法 (5) 7.1.1 实验截图 (5) 7.1.2 实验分析 (6) 7.2 验证先进先出(FIFO)页面置换算法 (7) 7.2.1 实验截图 (7) 7.2.2 实验分析 (7) 7.3 验证LRU置换算法 (8) 7.3.1 实验截图 (8) 7.3.2 实验分析 (8) 八、报告书写人 (9) 附录一最佳置换算法(Optimal) (9) 附录二先进先出(FIFO)页面置换算法 (15) 附录三LRU置换算法 (20) 实验五：页面调度算法模拟 一、实验题目 页面调度算法模拟
二、实验学时 2学时 三、指导老师 ╳╳╳ 四、实验日期 2018年12月10日星期一 五、实验目的 (1)熟悉操作系统页面调度算法 (2)编写程序模拟先进先出、LRU等页面调度算法，体会页面调度算法原理 六、实验原理 6.1页面的含义 分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。 6.2 页面置换算法的含义 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 6.3 置换算法 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
操作系统 实验报告 哈尔滨工程大学 计算机科学与技术学院
第六讲磁盘调度算法 一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的 （1）通过学习EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机； （2）观察 EOS 实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法； （3）编写 CSCAN和 N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。 3. 实验类型 验证性+设计性实验 4. 实验内容 （1）验证先来先服务（FCFS）磁盘调度算法； （2）验证最短寻道时间优先（SSTF）磁盘调度算法； （3）验证SSTF算法造成的线程“饥饿”现象； （4）验证扫描（SCAN）磁盘调度算法； （5）改写SCAN算法。 二、实验环境 在OS Lab实验环境的基础上，利用EOS操作系统，由汇编语言及C语言编写代码，对需要的项目进行生成、调试、查看和修改，并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。 三、实验过程 1. 设计思路和流程图 （1）改写SCAN算法 在已有 SCAN 算法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求，就可以选中下一个要处理的请求。算法流程图如下图所示。 图 3.1.1 SCAN算法IopDiskSchedule函数流程图（2）编写循环扫描（CSCAN）磁盘调度算法 在已经完成的SCAN算法源代码的基础上进行改写，不再使用全局变量ScanInside 确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。算法流程图如下图所示。
实验四 用先进先出（FIFO ）页面调度算法处理缺页中断 1．实验目的 深入了解页式存储管理如何实现地址转换； 进一步认识页式虚拟存储管理中如何处理缺页中断。 2．实验预备知识 页式存储管理中的地址转换的方法； 页式虚拟存储的缺页中断处理方法。 3．实验内容 编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所作工作进程测试。 假定主存64KB ，每个主存块1024字节，作业最大支持到64KB ，系统中每个作业分得主存块4块。 4．提示与讲解 页式存储管理中地址转换过程很简单，假定主存块的大小为2n 字节，主存大小为2m'字节和逻辑地址m 位，则进行地址转换时，首先从逻辑地址中的高m-n 位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n 位，最后从逻辑地址中取得低n 位放入物理地址的低n 位就得到了物理地址，过程如图1所示。 图1 页式存储管理系统地址转换示意图 地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图2所示（实验中假定主存64KB ，每个主存块1024字节，即n=10,m'=16，物理地址中块号6位、块内地址10位；作业最大64KB ，即m=16，逻辑地址中页号6位、页内地址10位）。 在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”， 逻辑地址
《操作系统原理及应用》课程设计报告 磁盘调度算法 学院（系）：计算机科学与工程学院 班级：37-5 学号 学生姓名： 时间：从2013 年12 月16日到2013 年12月20日
1、课程设计的目的 本课程设计是学生学习完《操作系统原理及应用》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 2、课程设计的内容及要求 编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3、实现原理 磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先、扫描和循环扫描等算法。 其中，平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N 其中Mi为磁头从上一各磁道到这个磁道所需移动的距离。 4、算法 1.先来先服务算法（FCFS） 这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法只考虑访问者提出访问请求的先后次序，按照先后次序依次访问磁道号。移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。 2.短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，而不管访问者到来的先后次序。实现时可以先对磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，选择离自己最近的访问，每比较一次，当前磁道号也跟着变化，移动距离等于上一个被访问的
江西师范大学计算机信息工程学院学生实验报告专业计算机科学与技术姓名李洋_ 学号0908061086 日期2011/5/17 课程名称计算机操作系统实验室名称X4313 实验名称先进先出调度算法 指导教师朱明华成绩 1.实验目的 了解的先进先出调度算法的调度原理，再用数据结构和c语言，以程序的形式来实现该算法 2.实验原理和内容 先进先出调度算法的原理是把一个进程已调入内存的页面，按照先后测序链接成一个队列，并设置一个指针，使他总是指向最老的页面。 3.实验步骤 （1）在c-free中定义函数 （2）根据原理进行编写 （3）运行并验证 源程序： #include
using namespace std; #define Max 30 //某进程调入内存中的最大页面数 #define Size 10 //系统为某进程分配的最大物理块数 void Init(int Block[],int m) //初始化物理块 { int i; for(i=0;i 模拟磁盘调度算法操作系 统课程设计 Final approval draft on November 22, 2020 某某大学 课程设计报告课程名称：操作系统 设计题目：模拟磁盘调度算法 系别：计算机系 专业：计算机科学与技术 组别： 学生姓名: 学号: 起止日期: 指导教师: 目录 第一章需求分析 课程设计的简介 这是一个用VC++为工具、C++为编程语言而实现模拟先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）的一个磁盘调度程序。该程序设计系统主界面可以灵活选择某种算法并算出磁头移动的总磁道数以及平均磁道数。 课程设计的目的 本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）等磁盘调度算法的理解。 磁盘调度主要思想 设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。 平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即： L=（M1+M2+……+Mi+……+MN）/N。其中Mi为所需访问的磁道号所需移动的磁道数。 启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有： 寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。 延迟时间——指定扇区旋转到磁头下所需的时间。 传送时间——由磁头进程读写完成信息传送的时间。 QoS队列调度算法概述 作者：上传时间：2011-04-22 关键字：网络大爬虫4-QoS专题 文常慧锋 【摘要】本文概述了常用队列调度算法的实现机制，并在此基础上对比了基于理想流模型的WFQ队列算法与其他队列调度算法的公平性能。 【关键字】服务质量队列调度通用处理器共享加权公平队列 1. 引言 队列调度算法是实现网络QoS(Quality of Service，服务质量)控制的核心机制之一，是网络资源管理的重要内容，通过控制不同类型的分组对链路带宽的使用，使不同的数据流得到不同等级的服务。 通常调度算法的工作模式可以分为两种：工作保留模式(work-conserving)和非工作保留模式(non-work-conserving)。如果队列中有数据包等待发送服务器就工作的调度算法称为工作保留调度算法；如果队列中有数据包等待发送但服务器仍然处于空闲状态的调度算法称为非工作保留调度算法，例如，即使服务器处于空闲状态同时队列中有数据包等待发送，但是为了等待下一个高优先级的数据包服务器也会推迟当前数据包的传输，这种调度算法就属于非工作保留调度算法。当数据包的传输时间很短时，非工作保留调度算法几乎是不公平的。 调度算法的另一种分类方法是根据调度算法的内部结构来划分的，主要有两种：基于优先级分类的调度算法和基于帧结构的调度算法。在基于优先级的调度算法中有一个称为虚拟时间(virtual time)的全局变量。调度算法根据该变量为每个数据包计算一个时间戳，然后根据时间戳对数据包排序和调度。虚拟时钟，加权公平队列都属于这种结构。基于优先级的调度算法的实现复杂度取决于两个因素：更新优先级列表算法和选择最高优先级数据包算法的复杂度(至少是，其中是共享输出链路的队列数)和计算时间戳算法的复杂度(这主要取决于所采用的调度算法，加权公平队列(WFQ)的时间戳的计算复杂度为，虚拟时钟的计算复杂度只为O(1))。 在基于帧结构的调度算法中，时间被分为固定长度或可变长度的帧。每个数据流所能使用的带宽资源就是每一帧中所允许传输业务量的最大值。存储转发队列是帧长度固定的基于帧结构的调度算法，在这种结构中，如果一帧中数据流的业务量小于预留带宽，服务器就会空闲。加权循环队列，差额循环队列允许帧长度可变，同时，如果一个数据流的业务量小于预留带宽时，下一个数据流就可以提前被调度。基于帧结构的调度算法最大的优点是实现简单，成本低，最大的缺点是缺乏灵活性和扩展性。 2. 典型的调度算法简介 2.1先进先出队列(FIFO) FIFO队列是最简单的基于优先级的调度算法。在FIFO队列中数据包的时间戳就是数据包的到达时间。FIFO队列提供了基本的存储转发功能，也是目前因特网中使用最广泛的一种方式，它采用默认的排队方法，不需要配置。其优点是实现简单，成本低，缺点是不能提供 磁盘调度算法的模拟实现 学院 专业 学号 学生姓名 指导教师姓名 2014年3月19日 目录 一、课设简介 (2) 1.1 课程设计题目 (2) 1.2 课程设计目的 (2) 1.3 课程设计要求 (2) 二、设计内容 (3) 2.1功能实现 (3) 2.2流程图 (3) 2.3具体内容 (3) 三、测试数据 (4) 3.3 测试用例及运行结果 (4) 四、源代码 (5) 五、总结 (12) 5.1 总结............................................ 一、课设简介 1.1课程设计题目 磁盘调度算法的模拟实现1 1.2程序设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 1）进一步巩固和复习操作系统的基础知识。 2）培养学生结构化程序、模块化程序设计的方法和能力。 3）提高学生调试程序的技巧和软件设计的能力。 4）提高学生分析问题、解决问题以及综合利用C语言进行程 序设计的能力。 1.3 设计要求 1）磁头初始磁道号，序列长度，磁道号序列等数据可从键盘输入，也可从文件读入。 2）最好能实现磁道号序列中磁道号的动态增加。 3）磁道访问序列以链表的形式存储 4）给出各磁盘调度算法的调度顺序和平均寻道长度 二、设计内容 2.1 功能实现 设计并实现一个本别利用下列磁盘调度算法进行磁盘调度的模拟程序。 1）先来先服务算法FCFS 2）最短寻道时间优先算法SSTF 2.2流程图 开始 2.3具体内容 1)先来先服务算法FCFS 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘 操作系统课程设计任务书 题目：磁盘调度算法 院系： 专业： 班级： 姓名： 学号： 指导教师： 设计时间： 2018.1.1-2018.1.5 指导教师评语 目录 1、需求分析 (4) 1.1课题描述 (4) 1.2课题目的 (4) 1.3理论依据 (7) 2、概要设计 (8) 2.1设计方法 (8) 2.2技术 (8) 2.3运行环境 (8) 3、详细设计 (9) 3.1流程图 (11) 3.2程序主要代码 (13) 4、运行结果及分析 (14) 4.1运行结果 (15) 4.2结果详细分析 (16) 5、总结和心得 (16) 6、参考文献 (17) 7、附录：程序源代码 (23) 1、需求分析 1.1课题描述 这次课程设计我研究的题目是：磁盘调度算法。具体包括三种算法分别是：先来先服务算法（FCFS）、最短寻道时间优先算法(SSTF)、扫描算法（电梯调度算法）(SCAN)。 1.2课题目的 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS，最短寻道时间优先SSTF，扫描SCAN算法的实现方法。 1.3理论依据 设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。 平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN） #include"stdio.h" #define N 50 int n; int sj; struct Gzuo{ int id; //进程名字 int dt; //到达时刻 int st; //服务时间 int wct; //完成时刻 int yxj; //优先级 int st2; //标志是否完成 float zt; //周转时间 float dczt; //带权周转时间 }; Gzuo a[N]; void input(Gzuo a[]) { printf("请输入进程个数："); scanf("%d",&n); for(int i=0;i printf("\n\n"); printf("\t请输入时间片大小(0 计算机操作系统课程设计 设计说明书 （题目） 磁盘调度算法的实现与分析 起止日期：2013 年12 月25 日至2013年12 月31 日 学生姓名 班级 学号 成绩 指导教师(签字) 计算机与通信学院 2013年12 月31 日 目录 1 课程设计简介 (3) 1.1 课程设计的目的 (3) 1.2 课程设计内容 (3) 2 数据结构的设计 (4) 2.1 变量和数组的定义 (4) 2.2函数的定义 (4) 3 功能模块（或算法）描述 (4) 3.1模块划分 (4) 3.2 模块调用关系图 (8) 4 程序运行结果..................................... 错误！未定义书签。 5 心得体会 (12) 参考文献 (13) 附源代码 (13) 1 课程设计简介 1.1 课程设计的目的 本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。 1.2 课程设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 1、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 2、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 3、扫描算法（SCAN） 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即 答卷封面 (COVER) 课程名称（Subject）：操作系统课程设计 编号(No.)： 系别(Department): 专业(Major)： 姓名(Name)： 学号(Student’s Number)： 注意事项（Notes） 1.考生需将上述有关项目填写清楚 2.字迹要清楚，保持卷面清洁。 3.交卷时请将本答卷和题签一起上交，题签作为封面下一页装订。 1、Candidates should fill in the information appropriately. 2、Keep the handwriting clear and the paper tidy. 3、Candidate should hand in this cover and paper together; the answer sheet should be attached to the cover. 机密（Confidential）编号（No.）：11-12-1-050154 试题（Test） 课程名称（Subject）：操作系统课程设计考核类别（Type of test）：考查课程类别(Type of course) : 实践环节考试形式(Test type) : 论文 使用范围（Target group）：计算机科学与技术 要求： 一、通过本课程设计，使学生在上机实验中体会计算机操作系统的基本原理，训练学生模拟实现操作系统管理和控制资源的能力。 二、学生可在下列14个题目中任选1个。 （1）先来先服务调度算法、短作业优先调度算法、时间片轮转调度算法、优先级调度算法 （2）生产者-消费者问题、读者-写者问题 （3）最先适应算法、最佳适应算法、最坏适应算法 （4）先进先出算法、最久未使用淘汰算法、理想淘汰算法 （5）银行家算法 （6）进程通信 （7）小型文件系统 三、模拟实现算法在Windows平台下，可用C语言、C++语言和Java 语言等。 摘要 本文围绕Java编程，按照进程进入就绪队列的先后次序来分配处理器，对先进先出程序进行需求分析、概要设计、详细设计，最后使用Java编程实现的全过程。 关键词：操作系统先进先出算法 java语言 实验四磁盘调度 一、实验目的： 本实验要求学生模拟设计一个磁盘调度程序，观察调度程序的动态运行过程。通过实验让学生理解和掌握磁盘调度的职能。 二、实验内容： 对磁盘进行移臂操作，模拟磁盘调度算法并计算平均寻道时间 三、实验准备： 1.相关理论知识： （1）假设磁盘只有一个盘面，并且磁盘是可移动头磁盘。 （3）磁盘是高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出工作，在现代计算机系统中往往同时会有若干个要求访问磁盘的输入输出要求。系统可采用一种策略，尽可能按最佳次序执行访问磁盘的请求。由于磁盘访问时间主要受寻道时间T的影响，为此需要采用合适的寻道算法，以降低寻道时间。 （2）磁盘是可供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其它想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求而处于等待状态时，可用磁盘调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。 2.测试数据： 磁盘读写请求队列：20，44，40，4，80，12，76 当前磁头位置：50 试问采用FCFS、SSTF、SCAN磁盘调度算法时寻道顺序及平均寻道时间分别为多少？ 四、实验过程： 1.流程图 SCAN算法（扫描算法）流程图： 2. 源代码 #include 吉首大学数学与计算机科学学院计算机操作系统课程设计报告 课题名称:进程调度 开发人员：肖海波 学号: 20054044029 班级：2005级计算机科学与技术2班 实现算法:最高优先数度算法 完成日期:2007年12月21日 指导老师：李必云 计算机操作系统进程调度模拟算法第一章绪论 (1) 第二章算法简介……………………………………………… 1．1 最高优先数算法………………………………… 第三章程序开发平台及开发工具…………………………… 第四章算法数据结构及流程图………………………………… 4．1 算法数据结构……………………………………………… 4．2 算法流程图…………………………………………… 第五章程序源代码……………………………………………………第六章测试数据及测试结果…………………………………… 6．1 最高优先数…………………………………………… 6．1．1 测试数据 6．1．2 测试结果 6．2 测试总结……………………………………………… 第七章算法分析………………………………………………… 结束语…………………………………………………… 参考文献………………………………………………… 第一章绪论 进程调度是操作系统中最基本的一种调度,在各种类型的操作系统中都必须设有进程调度.进程调度的基本方式可分为非抢占方式和抢占式方式(也称为剥夺方式) (1) 非抢占方式 在这种进程调度方式下,一旦一个进程被选中投入运行,它就一直运行下去,直至完成工作,自愿放弃CPU,或者因某个事件而被阻塞为止,才把CPU让出给其他进程,即得到CPU的进程不会因为时钟中断等原因而被迫让出CPU. (2) 抢占方式 与非抢占方式相反,抢占方式允许进程调度程序根据某种策略终止当前正在运行的进程,将其移入就绪队列,并再根据某种调度算法选择另一个进程投入运行. 第二章算法简介 2．1 最高侁先数算法 最简单的调度算法就是先来先服务,也可以称为先进先出(First In First Out)或严格排队方式.对于进程调度算法来说,先来先服务调度算法就是从就绪队列中选择一个最先进入队列的进程,将CPU分配于它,让其运行.该进程一直运行下去直到完成或由于某事件而被阻塞入放弃CPU.这样,当一个进程进入就绪队列时,它的PCB就链入了该就绪队列的末尾,排队等待 磁盘调度算法 操作系统课程设计任务书 学院专业 课程名称题目磁盘调度 完成期限自2014年6月9日至2014年6月22日共2周 一、项目的目的 通过设计一个磁盘调度模拟系统～从而使磁盘调度算法更加形 象化～容易使人理解～使磁盘调度的特点更简单明了～能使使用者 加深对扫描算法以及循环扫描算法等磁盘调度算法的理解。 二、项目任务的主要内容和要求 根据磁盘调度算法的思想～编程实现扫描算法、循环扫描算法～ 并通过数据分析比较各种算法的平均寻道长度。 内 三、项目设计,研究,思路 容 1.扫描算法,SCAN,:将磁道号用冒泡法从小到大排序～输出及 排好序的序列～输入当前磁道号～选择移动臂的移动方向～根据当任前磁道在已排的序列中的位臵～选择扫描的顺序～求出平均寻道长务度～输出移动的平均磁道数。 2.循环扫描算法,CSCAN,:将磁道号用冒泡法从小到大排序～ 输出排好序的序列～输入当前磁道号～规定移动臂单向反复的从内 向外移动～根据当前磁道在已排的序列中的位臵～选择扫描的顺序～ 求出平均寻道长度～输出移动的平均磁道数。 四、具体成果形式和要求 设计一个磁盘调度的程序～按用户不同的选择～用不同的算法 进行不同的模拟。 进起止日期工作内容 度 理解磁盘调度的原理背景、查询相关安 资料设计规划设计总体思路排 编写代码实现各部分的功能 进行测试代码以及对代码进行调试、 修改。最后编写文档 主 [1]汤小丹, 梁红兵.计算机操作系统[M].西安:西安电子科技大学出要版社～2007 参 [2]何钦铭, 颜晖.C语言程序设计[M].北京:高等教育出版社～2008 考 [3]严蔚敏, 吴伟民. 数据结构,C语言版,[M].北京:清华大学出 资版社～2011 料 指导教师 意见 ,签字,: 年月日 系,教研 室,主任意 见 ,签字,: 年月日 磁盘调度课程设计说明书 操作系统实验报告 专业计算机及应用（本）姓名 考号 指导老师 实验一 DOS/Windows用户接口与进程管理 一.实验目的 了解和掌握DOS/Windows有关用户接口和进程管理的特点 二.实验内容 1.MS-DOS的命令接口 （1）再当前目录下建立子目录MYTEMP和MYTEMP2，将当前目录设定为MYTEMP; 解： c:\>md MYTEMP MYTEMP2 c:\>cd MYTEMP （2）再当前目录下创建新文件B.BAT,其内容为：清除屏幕内容，显示当前DOS版本； 解: c:\MYTEMP>edit cls ver （3）使用type命令显示B.BAT的内容，执行他； 解: C:\MYTEMP>type b.bat C:\MYTEMP>b.bat （4）拷贝B.BAT到路径MYTEMP2中； 解: c:\MYTEMP>copy b.bat c:\MYTEMP2 （5）删除MYTEMP2中的文件B.BAT，删除目录MYTEMP2;解: c:\MYTEMP>del c:\MYTEMP2\B.BAT c:\MYTEMP>rd c:\MYTEMP2 （6）使用deltree命令删除MYTEMP. 解： c:\MYTEMP>cd\ c:\>deltree MYTEMP 2.MS-DOS的进程管理 （1）运行编辑程序EDIT，可以同时再运行其它命令吗？ 答：不可以再运行其他命令。 （2）执行如下管道和换向命令： C:\>dir>dir.lst 答： dir 命令生成的C:\ 盘下的目录和文件列表重定向到dir.lst文件：如果dir.lst文件不存在，将创建该文件。如果dir.lst 存在，将使用 dir 命令的输出替换文件中的信息。 C:\>type dir.lst|more 1.实验题目: 磁盘调度算法。 建立相应的数据结构； 在屏幕上显示磁盘请求的服务状况； 将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支持算法：FIFO、SSTF、SCAN、CSCAN; 2.设计目的: 调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。 3.任务及要求 3.1设计任务 编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度： 1、先来先服务算法（FCFS） 2、最短寻道时间算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3.2设计要求 对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。 4.算法及数据结构 4.1算法的总体思想 queue[n] 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道①先来先服务算法（FCFS） 按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。 ②最短寻道时间优先算法（SSTF） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。 ③扫描算法（SCAN） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁 道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 ④循环扫描算法（CSCAN） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 5、源代码： #include 实验四用先进先出（FIFO）页面调度算法处理缺页中断 1．实验目的 深入了解页式存储管理如何实现地址转换； 进一步认识页式虚拟存储管理中如何处理缺页中断。 2．实验预备知识 页式存储管理中的地址转换的方法； 页式虚拟存储的缺页中断处理方法。 3．实验内容 编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所作工作进程测试。 假定主存64KB，每个主存块1024字节，作业最大支持到64KB，系统中每个作业分得主存块4块。 4．提示与讲解 n字节，主存大2页式存储管理中地址转换过程很简单，假定主存块的大小为m'字节和逻辑地址m位，则进行地址转换时，首先从逻辑地址中的高m-n小为2位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n位，最后从逻辑地址中取得低n位放入物理地址的低n位就得到了物理地址，过程如图1所示。 m n n-1 逻辑地址页内地址号页 ?块页号号 m' n n-1 物理地址块内地址号块 ? ? ? 页式存储管理系统地址转换示意图图1 模拟地实验中使用软件程序模拟地址转换过程，地址转换是由硬件完成的，字节，102464KB，每个主存块址转换的流程图如图2所示（实验中假定主存，m=1664KB，即10物理地址中块号即n=10,m'=16，6位、块内地址位；作业最大。位）逻辑地址中页号6位、页内地址10作业执行时仅作业信息作为副本放在磁盘上，在页式虚拟存储管理方式中，则按作业执行时若访问的页面在主存中，把作业信息的部分页面装入主存储器，，上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”1 / 5 由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。这样，在实验中页表格式如图2所示。 页表用数组模拟，在实验中页表数据结构定义为(同学们可自行定义其它功能等 价的结构)： define n 32 /*实验中假定的页表长度，页表的长度实际上是由系统按照作业长度决定的*/ struct {int lnumber; /*页号*/ int flag; /*表示该页是否在主存，“1”表示在主存，“0”表示不在主存*/ int pnumber; /*该页所在主存块的块号*/ int write; /*该页是否被修改过，“1”表示修改过，“0”表示没有修改过*/ int dnumber; /*该页存放在磁盘上的位置，即磁盘块号*/ LRU页面调度算法实现 学院计算机科学与技术专业计算机科学与技术学号 学生姓名 指导教师姓名 2014年3月16 日 目录 1.实验要求 (2) 2.实验目的 (2) 3.实验内容 (2) 4.相关知识 (2) 5.实验原理 (3) 6.流程图 (4) 7.源代码 (5) 8.运行结果 (9) 9.实验心得 (10) 10.参考文献 (11) LRU页调度算法实现 一实验要求： 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清 楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 二实验目的： 将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学 生分析问题、解决问题以及综合利用C 语言进行程序设计的能力。 三实验内容： 程序应模拟实现LRU 算法思想，对n个页面实现模拟调度。 四相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。模拟磁盘调度算法操作系统课程设计
4.QoS队列调度算法概述
磁盘调度算法的模拟实现
操作系统磁盘调度算法
四种进程调度算法 先到先服务,优先级,短作业优先,时间片轮转
(完整word版)磁盘调度算法的实现与分析
先进先出算法实验报告
操作系统实验四-磁盘调度算法
进程调度 最高优先数度算法
磁盘调度算法
操作系统实验-页面调度算法
操作系统课程设计-磁盘调度算法
大作业用先进先出FIFO页面调度算法处理缺页中断
LRU页面调度算法实现
相关主题
文本预览