小邪操作系统课程设计 电梯调度

石家庄经济学院石家庄经济学院 课程设计报告课程设计报告 学 院 系 华信学院 专 业 计算机科学与技术 姓 名 小邪 班 级 学 号 指导教师 王颖 2010 年年 6 月月 24 日日 操作系统操作系统 课程设计报告课程设计报告 姓名姓名 小邪学号学号日期日期 6 24 2010 实验室实验室152 机房指导教师指导教师王颖设备编号设备编号52 课程设计题目课程设计题目实习九 驱动调度 一 实验内容一 实验内容 模拟电梯调度算法 实现对磁盘的驱动调度 二 实验目的二 实验目的 磁盘是一种高速 大容量 旋转型 可直接存取的存储设备 它作为计算机系统的辅助存储器 担负着繁重的输入输出任务 在多道程序设计系统中 往往同时会有若干个要求访问磁盘的输入输出 请求等待处理 系统可采用一种策略 尽可能按最佳次序执行要求访问磁盘的诸输入输出请求 这就 叫驱动调度 使用的算法称为驱动调度算法 驱动调度能降低为若干个输入输出请求服务所需的总时 间 从而提高系统效率 本实验要求学生模拟设计一个驱动调度程序 观察驱动调度程序的动态运行 过程 通过实验使学生理解和掌握驱动调度的职能 三 实验过程三 实验过程 1 数据结构设计数据结构设计 struct pcb int name 进程名 int sector 柱面号 199 int track 磁道号 19 int record 物理记录号 7 struct pcb next 2 算法设计算法设计 算法思想 电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的 所以每 次启动磁盘时都应登记移动臂方向和当前位子 电梯调度算法是一种简单而实用的驱动调度方法 这 种调度策略总是优先选择与当前柱面号相同的访问请求 从这些请求中再选择一个能使旋转距离最短 的等待访问者 如果没有与当前柱面号相同的访问请求 则根据移臂方向来选择 每次总是沿臂移动 方向选择一个与当前柱面号最近的访问请求 若沿这个方向没有访问请求时 就改变臂的移动方向 这种调度策略能使移动臂的移动频率极小 从而提高系统效率 用电梯调度算法实现驱动 在驱动调度的程序中我一共编写了七个函数 pcb create struct pcb a 是初始化一个请求调度表 根据用户输入的进程个数依次创建进程 每次创建的进程都插到链表的末尾 而且数据由 rand 直接 生成 不用用户输入 pcb insert struct pcb a 是插入一个新的请求进程 同样数据也是由 rand 生成 之后把创建好的进程插入到链表的尾部 void showpcb struct pcb a 是打印进程链表的数据 int sequenceup int a int n 把对进程链表中的所有进程柱面号取出 放入一个数组 之后对数组进行升序 排列 int sequencedown int a int n 结构和上面的函数一样 不过是对数组进行降序排列 void show int a int n 是打印磁道移动的情况 之前把磁道移动的过程都存储在一个数组里 通过这个函数 来打印数组 pcb scancal struct pcb a 是这个程序的关键函数 用 scan 算法进行驱动调度 首先要 判断磁头移动的方向 然后根据方向找离磁头当前位置最近的磁道 这样一直找下去 如果一个方向 找完就按相反的方向继续找 直到找完为止 开始 把i o请求表中的磁 道号全部拷贝到数 组a和数组b中 队数组a进行升 序排列数组b进 行降序排列 判断输出数组的元 素的个数是否等于 进程的个数 判断当前磁道方 向 从升序排列的数组中找 出比当前磁道号大的磁 道放入输出数组 从降序排列的数组中找 出比当前磁道号晓得磁 道翻入输出数组 打印输出数组中的寻 道的序列 是 向上 向下 否 结束 图 1 实现 scan 算法的流程图 3 程序实现及运行结果程序实现及运行结果 1 源程序链接 include stdio h include stdlib h include iostream h struct pcb int name 进程名 int sector 柱面号 199 int track 磁道号 19 int record 物理记录号 7 struct pcb next int direct 方向 int r 进程个数 int f 当前此道的位置 pcb create struct pcb a a 表示队列 n 表示进程个数 struct pcb q s int n n r s q NULL s a for int i 1 iname rand 80 q sector rand 199 q track rand 19 q record rand 7 q next NULL if a NULL a s q else s next q s s next return a pcb insert struct pcb a 插入一个进程 进程所在磁道 k struct pcb q s s q NULL q a s struct pcb malloc sizeof struct pcb s name rand 40 s sector rand 200 s track rand 19 s record rand 7 s next NULL if q NULL return s while q NULL 找队尾 if q next NULL q q next else break q next s return a void showpcb struct pcb a struct pcb p p a printf 初始化请求 I O 表 n printf 进程名 柱面号 磁道号 物理记录号 n while p NULL printf d t d t d t d t n p name p sector p track p record p p next int sequenceup int a int n n 表示元素的个数 按升序排列 用的是冒泡排 序法 int i j k w for j 0 j n 1 j w j for i j i n i if a i a w w i k a w a w a j a j k return a int sequencedown int a int n n 表示元素的个数 按降序排列 用的是冒泡排 序法 int i j k w for j 0 j n 1 j w j for i j ia w w i k a w a w a j a j k return a void show int a int n 显示调度的序列 int p p n if p 2 printf d a 0 printf n printf 当前磁头的位置 d n a 0 f a 0 return for int i 0 inext NULL printf 当前没有请求 n return NULL for int i 0 isector q q next z sequenceup c n 生序排列 v sequencedown d n 降序排列 q a if q sector q next sector direct 1 else direct 0 if f 0 direct 0 printf 当前磁臂移动的方向 if direct 0 printf s n up else printf s n down while e n if direct 0 0 表示从小往大移动 表示 up if o 2 h 0 z 1 break for i 0 if if h e i z i if h e i z i continue h e z i e if e n break continue direct 1 else 1 表示从大往小的方向 表示 down if o 2 h 0 v 1 break for i 0 i n i if v i sector t if a sector f 找到磁道当前的位置 更改请求链表 p a p next NULL r 1 break else a a next printf 当前磁臂的移动方向是 if direct 0 printf s n up else printf s n down return p void main int n struct pcb a a NULL direct 0 while 1 printf 资源分配 n printf 1 初始化请求 I O 表 n printf 2 进行磁盘调度 n printf 3 插入一个新的请求 n printf 请根据提示选择选择 n scanf d switch n case 1 printf 请输入要创建进程的个数 n scanf d a NULL f 0 a create a showpcb a printf n break case 2 a scancal a printf n break case 3