实验四磁盘驱动调度算法的模拟
一.实验内容:
熟悉磁盘的结构以及磁盘的驱动调度算法的模拟,编程实现简单常用的磁盘驱动调度算法:先来先服务(FIFO)、电梯调度算法、最短寻道时间优先算法、扫描(双向扫描)算法、循环扫描算法等。
编程语言建议采用c/c++或Java。模拟程序鼓励采用随机数技术、动态空间分配技术,有条件的最好能用图形界面展现甚至用动画模拟。
实验性质:验证型。
二.实验目的和要求
1)掌握使用一门语言进行磁盘驱动调度算法的模拟;
2)编写程序将磁盘驱动调度算法的过程和结果能以较简明直观的方式展现出来。
三.实验原理、方法和步骤
1. 实验原理
磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率,从而影响计算机系统的整体效率。
常用的磁盘驱动调度算法有:
最简单的磁盘驱动调度算法是先入先出(FIFO)法。这种算法的实质是,总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平,不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移动方向,效率有待提高。
最短寻道时间优先算法:总是优先处理最靠近的请求。该算法移动的柱面距离较小,但可能会经常改变移动方向,并且可能会发生进程饥饿现象。
电梯调度:总是将一个方向上的请求全部处理完后,才改变方向继续处理其他请求。
扫描(双向扫描):总是从最外向最里进行扫描,然后在从最里向最外扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或最里的请求时不会移动到最外或最里柱面,二是扫描算法总是移到最外、最里柱面。
循环扫描(单向扫描):从最外向最里进行柱面请求处理,到最里柱面后,直接跳到最外柱面然后继续向里进行处理。
2. 实验方法
1)使用流程图描述演示程序的设计思想;
2)选取c/c++、Java等计算机语言,编程调试,最终给出运行正确的程序。
作业6磁盘驱动调度 1磁盘共有100各柱面,若干个等待访问磁盘者依次要访问的柱面为20 , 44, 40, 4, 80, 12, 76。假设每移动一个柱面需要3ms时间,移动臂当前位于36号柱面,试问对以下 几种磁盘请求调度算法而言,满足以上请求序列,磁头将分别如何移动?并计算为完成 上述各次访问总共花费的寻找时间。 ①先来先服务算法(FCFS)。 ②最短寻找时间优先算法(SSTF)。 ③扫描算法(SCAN)。 ④循环扫描算法(CSCAN)。 1.解 ①先来先服务算法,磁头移动示意图: 0 4 12 20 36 40 44 先来先服务算法磁头的移动顺序为:20,44,40,4,80,12,76。 花费的寻找时间为:(16+24+4+36+76+68+64)*3=864(ms) ②最短寻找时间优先算法,磁头移动示意图: 0 4 12 20 36 40 44 76 80 99 最短寻找时间优先算法磁头的移动顺序为:40,44,20,12,4,76,80 花费的寻找时间为:(4+4+24+8+8+72+4)*3=372 ( ms) 76 80 99
③扫描(电梯调度)算法,磁头移动示意图: 电梯调度算法磁头移动的顺序为:40, 44, 76, 80, 20, 12, 4 花费的寻找时间为:(44+76)*3=360(ms) ④循环扫描算法(CSCAN,磁头移动示意图: 循环扫描算法磁头移动的顺序为:40, 44, 76, 80, 4, 12, 20 花费的寻找时间为:(44+76+16)*3=408(ms) 【下载本文档,可以自由复制内容或自由编辑修改内容,更多精彩文章,期待你的好评和关注,我将一如既往为您服务】
操作系统上机 实验报告 成绩 教师: 2012 年 12月 5日 班级: 学号: 姓名: 实验地点: 实验时间:
实验一进程的建立 【实验目的】 创建进程及子进程 在父子进程间实现进程通信 【实验软硬件环境】 Linux 、Windows98、Windows2000 【实验内容】 创建进程并显示标识等进程控制块的属性信息; 显示父子进程的通信信息和相应的应答信息。 (进程间通信机制任选) 【实验程序及分析】 编程思路:首先本程序在Linux用C语言完成的,父子进程的创建用fork函数来实现,然后是父子进程间的通信,这里用pipe实现。可以定义chan1[2], chan1[2],chanx[0]表示读,chanx[1]表示写。他们配合使用。 【实验截图】 【实验心得体会】 通过这次上机练习,我熟悉了用c++实现进程的创建,销毁,父子进程间的通讯等一系列课程中需要学习的内容。本来进程的概念在一开始我始终无法清晰地理解,但是通过自己用mfc的方法去实现它后,我开始慢慢地理解操作系统的进程的运作机制。 虽然,我只是实现了一个父子进程的创建和通讯,但是,管中窥豹,我想自己开始明白一个操作系统正是由很多这种进程实现功能的。其中,系统整体的进程调度,管理等等还有很多东西等着我们去进一步学习、理解。 实验二进程间的同步 【实验目的】
理解进程同步和互斥模型及其应用 【实验软硬件环境】 Linux 、Windows98、Windows2000 【实验内容】 利用通信API实现进程之间的同步: 建立司机和售票员进程; 并实现他们间的同步运行。 【实验程序及分析】 程序总体思路:由于本次试验时用PV操作实现的互斥与同步模型,所以先实现P、V操作的函数,然后在主程序中利用PV操作函数实现司机和售票员的同步。司机和售票员分别为父进程和子进程,假设司机停车开门,此时为父进程中运行,然后申请开车,但是此时乘客没上车,所以只能阻塞。此时进入子进程,乘客上车,关门,售票员检票,释放开车,然后死机开车,到站,释放开车门。如此循环。 示意图 #include
操作系统实验报告实验3 磁盘调度算法 报告日期:2016-6-17 姓名: 学号: 班级: 任课教师:
实验3 磁盘调度算法 一、实验内容 模拟电梯调度算法,实现对磁盘的驱动调度。 二、实验目的 磁盘是一种高速、大量旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器,负担着繁重的输入输出任务,在多道程序设计系统中,往往同时会有若干个要求访问磁盘的输入输出请示等待处理。系统可采用一种策略,尽可能按最佳次序执行要求访问磁盘的诸输入输出请求,这就叫驱动调度,使用的算法称驱动调度算法。驱动调度能降低为若干个输入输出请求服务所须的总时间,从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序,观察驱动调度程序的动态运行过程。 三、实验原理 模拟电梯调度算法,对磁盘调度。 磁盘是要供多个进程共享的存储设备,但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时,其他想访问该磁盘的进程必须等待,直到磁盘一次工作结束。当有多个进程提出输入输出请求处于等待状态,可用电梯调度算法从若干个等待访问者中选择一个进程,让它访问磁盘。当存取臂仅需移到一个方向最远的所请求的柱面后,如果没有访问请求了,存取臂就改变方向。 假设磁盘有200个磁道,用C语言随机函数随机生成一个磁道请求序列(不少于15个)放入模拟的磁盘请求队列中,假定当前磁头在100号磁道上,并向磁道号增加的方向上移动。请给出按电梯调度算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度。 四、实验过程 1.画出算法流程图。
2.源代码 #include
#include
操作系统实验 (第三次) 一、实验内容 模拟电梯调度算法,实现对磁盘的驱动调度。 二、实验目的
磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅 助存储器,担负着繁重的输入输出任务、在多道程序设计系统中,往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略,尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度,使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间,从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序,观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。 三、实验题目 模拟电梯调度算法,对磁盘进行移臂和旋转调度。 [提示]: (1)磁盘是可供多个进程共享的存储设备,但一个磁盘每时刻只能为一个进程服务。 当有进程在访问某个磁盘时,其他想访问该磁盘的进程必须等待,直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时,可用电梯调度算法从若干个等待访问者中选择一个进程,让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时,占有处理 器的另一进程可以提出使用磁盘的要求,也就是说,系统能动态地接收新的输入输出请求。为了模拟这种情况,在本实验中设置了一个“接收请求”进程。 “驱动调度”进程和“接收请求”进程能否占有处理器运行,取决于磁盘的结束中断信 号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序,以代替中断四、处理和处理器调度选择的过程。因而,程序的结构可参考图3—1
《操作系统原理》 课程设计报告书 题目:磁盘调度 专业:网络工程 学号: 学生姓名: 指导教师: 完成日期:
目录 第一章课程设计目的 (1) 1.1编写目的 (1) 第二章课程设计内容 (2) 2.1设计内容 (2) 2.1.1、先来先服务算法(FCFS) (2) 2.1.2、最短寻道时间优先算法(SSTF) (2) 2.1.3、扫描算法(SCAN) (3) 2.1.4、循环扫描算法(CSCAN) (3) 第三章系统概要设计 (4) 3.1模块调度关系图 (4) 3.2模块程序流程图 (4) 3.2.1 FCFS算法 (5) 3.2.2 SSTF算法 (6) 3.2.3 SCAN算法 (7) 3.2.4 CSCAN算法 (8) 第四章程序实现 (9) 4.1 主函数的代码实现 (9) 4.2.FCFS算法的代码实现 (11) 4.3 SSTF算法的代码实现 (13) 4.4 SCAN算法的代码实现 (15) 4.5 CSCAN算法的代码实现 (17) 第五章测试数据和结果 (20) 第六章总结 (23)
第一章课程设计目的 1.1编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统,从而使磁盘调度算法更加形象化,容易使人理解,使磁盘调度的特点更简单明了,能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解 1
第二章课程设计内容 2.1设计内容 系统主界面可以灵活选择某种算法,算法包括:先来先服务算法(FCFS)、最短寻道时间优先算法(SSTF)、扫描算法(SCAN)、循环扫描算法(CSCAN)。 2.1.1、先来先服务算法(FCFS) 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化,在对磁盘的访问请求比较多的情况下,此算法将降低设备服务的吞吐量,致使平均寻道时间可能较长,但各进程得到服务的响应时间的变化幅度较小。 2.1.2、最短寻道时间优先算法(SSTF) 该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的,因而导致响应时间的变化幅度很大。在服务请求很多的情况下,对内外边缘磁道的请求将会无限期的被延迟,有些请求的响应时间将不可预期。 2
实验报告学院(系)名称:计算机与通信工程学院
【实验过程记录(源程序、测试用例、测试结果及心得体会等)】 #include
实验三驱动调度 一、实验容 模拟电梯调度算法,实现对磁盘的驱动调度。 二、实验目的 磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器,担负着繁重的输入输出任务、在多道程序设计系统中,往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略,尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度,使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间,从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序,观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。 三、数据结构 #define M 20 typedef struct PCB { char proc[M];//进程名 int cylinder_num;//柱面号 int track_num;//磁道号
int phy_num;//物理记录号 struct PCB *next; }PCB; 四、实验题目 模拟电梯调度算法,对磁盘进行移臂和旋转调度。 (1)磁盘是可供多个进程共享的存储设备,但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时,其他想访问该磁盘的进程必须等待,直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时,可用电梯调度算法从若干个等待访问者中选择一个进程,让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时,占有处理器的另一进程可以提出使用磁盘的要求,也就是说,系统能动态地接收新的输入输出请求。为了模拟这种情况,在本实验中设置了一个“接收请求”进程。 “驱动调度”进程和“接收请求”进程能否占有处理器运行,取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序,以代替中断处理和处理器调度选择的过程。因而,程序的结构可参考图3—1 (2)“接收请求”进程建立一“请求I/O”表,指出访问磁盘的进程要求访问的物理地址,表的格式为:
实验三驱动调度 一、实验内容 模拟电梯调度算法,实现对磁盘的驱动调度。 二、实验目的 磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器,担负着繁重的输入输出任务、在多道程序设计系统中,往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略,尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度,使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间,从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序,观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。 三、实验题目 模拟电梯调度算法,对磁盘进行移臂和旋转调度。 [提示]: (1)磁盘是可供多个进程共享的存储设备,但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时,其他想访问该磁盘的进程必须等待,直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时,可用电梯调度算法从若干个等待访问者中选择一个进程,让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时,占有处理器的另一进程可以提出使用磁盘的要求,也就是说,系统能动态地接收新的输入输出请求。为了模拟这种情况,在本实验中设置了一个“接收请求”进程。 “驱动调度”进程和“接收请求”进程能否占有处理器运行,取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序,以代替中断处理和处理器调度选择的过程。因而,程序的结构可参考图3—1
(2)“接收请求”进程建立一张“请求I/O”表,指出访问磁盘的进程要求访问的物理地址,表的格式为: 假定某个磁盘组共有200个柱面,由外向里顺序编号(0—199),每个柱面上有20个磁道,编号为0—19,每个磁道分成8个物理记录,编号0—7。进程访问磁盘的物理地址可以用键盘输入的方法模拟得到。图3—2是“接收请求”进程的模拟算法。
操作系统实验报告课程名称:计算机操作系统 实验项目名称:磁盘调度实验时间: 班级:姓名:学号: 实验目的: 对操作系统的磁盘调度基础理论和重要算法的理解,加强动手能力。 实验环境: PC机 win7 Visual C++ 实验内容: 编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度,要求设计主界面以灵 活选择某算法,且以下算法都要实现: 1、先来先服务算法(FCFS) 2、最短寻道时间优先算法(SSTF) 3、扫描算法(SCAN) 4、循环扫描算法(CSCAN) 实验过程: 1.依次输入8个磁道数:123 45 31 67 20 19 38,并以0 结束 2.选择调度算法: (1)先来先服务算法(FCFS) (2)最短寻道时间优先算法(SSTF) 成绩: 指导教师(签名):
(3)扫描算法(SCAN) (4)循环扫描算法(CSCAN) 实验心得: 通过本次实验,学习了解磁盘调度的工作原理及四种调度方法的工作原理,并且在当中