操作系统课程设计报告

课 程 设 计 说 明 书 设计题目 设计题目 操作系统课程设计操作系统课程设计 班班 级 级 信息学管理与信息系统信息学管理与信息系统 20112011 级级 学学 号 号 201101051012201101051012 姓姓 名 名 李克乾李克乾 山山 东东 科科 技技 大大 学学 20132013 年年 1212 月月 1111 日日 课课 程程 设设 计计 任任 务务 书书 学院学院 信息科学与工程 专业专业 信息学管理与信息系统 班级班级 2011 2 姓名姓名 李克乾 一 课程设计题目 一 课程设计题目 操作系统课程设计 二 课程设计主要参考资料二 课程设计主要参考资料 1 Abraham Silberschatz 进程名称 int number 进程编号 float come time 到达时间 float run begin time 开始运行时间 float run time 运行时间 float run end time 运行结束时间 int priority 优先级 int order 运行次序 int run flag 调度标志 tasks MAX 运用 switch 语句对输入的进程进行相应的算法运行 进入相应 的算法函数后会对进程进行调度并输出结果 并对结果进行评估 1 先来先服务算法 FCFS 可用于作业调度 也可用于进程调 度 每次调度都是从后备队列中选择一个或者多个最先进入队列 的作业或进程 将他们调入内存进行分配资源 创建进程 放入 CPU 调度算法 就绪队列并开始执行 实现函数 int fcfs 先来先服务 主要实现方法如下 执行程序 输入进程相关信息 寻找第一 进程 将进程保存至调度列 并进行调度 判断所有进 程都被调度 在未调度的算法中需找最 先到达进程 是 否 打印结果信息 2 短作业优先调度算法 SJF 即从后备队列中选择一个或几 个估计运行时间最短的作业或进程对其分配资源 并进行调度执 行 实现函数 int sjf 短作业优先 主要实现方法如下 执行程序 输入进程信息 判断最短服务时间进程 把进程储存在调度序列并执行 在未调度并已到达进程中寻找服务时间最短进程 打印调度结果 所有进程被调度 否 是 3 优先级调度算法即在将第一个到达的进程执行完毕后 会在 此刻已经到达的进程或作业中选择优先权最高的一个或者几个进 程对其进行资源分配并创建进程执行 实现函数 int ps 优先 级调度 主要实现方法如下 程序执行 输入进程信息 判断优先级最高进程 把进程存储在调度序列并执行 在未调度并已到达进程中寻找优先级最高进程 打印调度结果 所有进程被调度 否 是 4 在时间片调度算法的模拟实现中 时间片就是分配给进程运 行的一段时间 在轮转法中 系统将所有的可运行 即就绪 进 程按先来先服务的原则 排成一个队列 每次调度时把 CPU 分 配给队首进程 并令其执行一个时间片 当某进程执行的时间片 用完时 系统发出信号 通知调度程序 调度程序便据此信号来 停止该进程的执行 并将刚运行的进程送到运行队列的末尾 等 待下一次执行 然后 把处理机分配给就绪队列中新的队首进程 同时也让它执行一个时间片 这样就可以保证运行队列中的所有 进程 在一个给定的时间内 均能获得一时间片的处理机执行时 间 实现函数 单独程序 主要实现方法如下 四 运行结果及分析四 运行结果及分析 设有如下 3 个进程 进程名称到达时间运行时间优先级 A453 B6101 C582 注 优先级 一栏 数字大的表示优先级越高 根据本例来运行本算法 结果如下 采用先来先服务算法 采用优先级调度 采用短作业优先 时间片轮转算法 本程序已通过测试阶段 未出现进程调度错误情况 运行程 序后 只需按照提示输入相应的进程的信息 进程名尽量输入单 个字母 后选择需要的调度算法即可得出相应结果 并且可以循 环运行多次 后期进行相应的美化加工 如需要 可进行可视化 改造 结果分析 结果分析 对于进程调度后得出的各项数据基本准确 当输入时间或其 他数据信息出现精确度较高的数值时可能会出现一些误差 属于 误差范围之内 程序基本可以实现 CPU 调度算法的过程解释 五 总结五 总结 通过此次课程设计 更深入的理解了各个进程调度算法 及实现过程 在此过程中 遇到了困难 能及时请教同学 查询 相关资料 及时解决了问题 但仍有不足之处 将会在今后学习 中更加努力 六 附录 完整代码 六 附录 完整代码 include using namespace std define MAX 10 struct task struct char name 10 进程名称 int number 进程编号 float come time 到达时间 float run begin time 开始运行时间 float run time 运行时间 float run end time 运行结束时间 int priority 优先级 int order 运行次序 int run flag 调度标志 tasks MAX int counter 实际进程个数 int fcfs 先来先服务 int ps 优先级调度 int sjf 短作业优先 int hrrn 响应比高优先 int pinput 进程参数输入 int poutput 调度结果输出 int main int option pinput printf 请选择调度算法 0 4 n printf 1 先来先服务 n printf 2 优先级调度 n printf 3 短作业优先 n printf 0 退出 n scanf d switch option case 0 printf 运行结束 n break case 1 printf 对进程按先来先服务调度 n n fcfs break case 2 printf 对进程按优先级调度 n n ps break case 3 printf 对进程按短作业优先调度 n n sjf break int fcfs 先来先服务 float time temp 0 int i int number schedul time temp tasks 0 come time for i 0 i counter i tasks i run begin time time temp tasks i run end time tasks i run begin time tasks i run time tasks i run flag 1 time temp tasks i run end time number schedul i tasks number schedul order i 1 poutput return main int ps 优先级调度 float temp time 0 int i 0 j int number schedul temp counter int max priority max priority tasks i priority j 1 while jtasks i priority max priority tasks j priority i j j 查找第一个被调度的进程 对第一个被调度的进程求相应的参数 number schedul i tasks number schedul run begin time tasks number schedul come time tasks number schedul run end time tasks number schedul run begin time tasks number schedul run time tasks number schedul run flag 1 temp time tasks number schedul run end time tasks number schedul order 1 temp counter 1 while temp counter counter max priority 0 for j 0 j counter j if tasks j come timemax priority max priority tasks j priority number schedul j 查找下一个被调度的进程 对找到的下一个被调度的进程求相应的参数 tasks number schedul run begin time temp time tasks number schedul run end time tasks number schedul run begin time tasks number schedul run time tasks number schedul run flag 1 temp time tasks number schedul run end time temp counter tasks number schedul order temp counter poutput return main int sjf 短作业优先 float temp time 0 int i 0 j int number schedul temp counter float run time run time tasks i run time j 1 while j counter i j j 查找第一个被调度的进程 对第一个被调度的进程求相应的参数 number schedul i tasks number schedul run begin time tasks number schedul come time tasks number schedul run end time tasks number schedul run begin time tasks number schedul run time tasks number schedul run flag 1 temp time tasks number schedul run end time tasks number schedul order 1 temp counter 1 while temp counter counter for j 0 j counter j if tasks j come time temp time number schedul j break for j 0 j counter j if tasks j come time temp time number schedul j 查找下一个被调度的进程 对找到的下一个被调度的进程求相应的参数 tasks number schedul run begin time temp time tasks number schedul run end time tasks number schedul run begin time tasks number schedul run time tasks number schedul run flag 1 temp time tasks number schedul run end time temp counter tasks number schedul order temp counter poutput return main int pinput 进程参数输入 int i printf please input the process counter n scanf d if counter 0 return 0 else for i 0 i counter i printf n printf please input the process of d th n i 1 printf please input the name n scanf s tasks i name printf please input the come time n scanf f printf please input the run time n scanf f printf please input the priority n scanf d tasks i run begin time 0 tasks i run end time 0 tasks i order 0 tasks i run flag 0 return 0 int poutput 调度结果输出 int i float turn round time 0 f1 w 0 printf name come time run time run begin time run end time priority order turn round time n for i 0 i counter i f1 tasks i run end time tasks i come time turn round time f1 w f1 tasks i run time printf s 5 3f 5 3f 5 3f 5 3f d d 5 3f n tasks i name tasks i come time tasks i run time tasks i run begin time tasks i run end time tasks i priority tasks i order f1 printf average turn round timer 5 2f n turn round time counter printf weight average turn round timer 5 2f n w counter return 0 include include define Myprintf printf n typedef struct PCB int ID int ReachTime int TotalTime PCB 进程号 到达时间和服务时间 typedef struct NOTE 备份 int ID int TotalTime NOTE PCB A 100 5 个进程 PCB a 100 NOTE temp int queue 50 记录调度的进程 int K 0 调度进程数组的标识 void INIT int M 初始化 int i int m m M for i 0 i m i A i ID 1 int GetNum int M 计算进程数 int m m M int i int j 0 for i 0 i m i if A i ID 1 j return j int GetReach int time int M 找出到达进程号 int i int m m M for i 0 i m i if a i ReachTime time a i ReachTime 100 return i return 1 int GetInsert int M 找出插入位置 int i int m m M for i 0 i m i if A i ID 1 return i return 1 void Forward int num 前移 int i for i 0 i num 1 i A i ID A i 1 ID A i TotalTime A i 1 TotalTime A num 1 ID 1 void Process int Jiange 执行进程 int jiange jiange Jiange queue K A 0 ID K A 0 TotalTime A 0 TotalTime jiange temp ID A 0 ID temp TotalTime A 0 TotalTime int main int i int time int t 0 int reach int insert int num int M int Jiange printf RR 算法 n n printf 请输入进程个数 n scanf d printf 请输入 R 值 n scanf d INIT M for i 0 i M i printf 请输入进程 ID scanf d printf 请输入到达时间 scanf d printf 请输入服务时间 scanf d for i 0 i M i 运行时间 t t a i TotalTime for i 0 i 50 i 初始化 queue i 1 for time 0 time t time reach GetReach time M if reach 1 有进程到达 insert GetInsert M A insert ID a reach ID A insert TotalTime a reach TotalTime num GetNum M if num 1 continue 进程数为 1 else 进程数不为 1 Process Jiange Forward num if temp TotalTime 0 A num 1 ID temp ID A num 1 TotalTime temp TotalTime else 没有进程到达 num GetNum M if num 1 进程数为 1 Process Jiange if temp TotalTime 0 A 0 ID 1 else if num 0 continue 进程数为 0 else Process Jiange Forward num if temp TotalTime 0 A num 1 ID temp ID A num 1 TotalTime temp TotalTime printf n printf 调度顺序为 n Myprintf for i 0 i 50 i if queue i 1 printf 2d queue i printf n Myprintf printf n return 0 设计设计 2 2 死锁相关算法的实现死锁相关算法的实现 一 设计目的一 设计目的 编写算法 实现银行家算法 安全性算法 死锁检测算法判 断系统安全状态 判断进程的资源请求是否可以被满足 判定系 统是否为死锁状态 银行家算法是避免死锁的一种重要方法 通 过编写一个简单的银行家算法程序 加深了解有关资源申请 避 免死锁等概念 并体会和了解死锁和避免死锁的具体实施方法 二 设计要求二 设计要求 其中算法所需的各种参数由输入产生 手工输入或者随机数 产生 本模块课程设计的基本要求是能够输出各种判定结果 是否 安全 安全序列 是否死锁 是否允许分配 3 3 设计说明设计说明 1 1 算法思路 先对用户提出的请求进行合法性检查 即检查 请求是否大于需要的 是否大于可利用的 若请求合法 则进行 预分配 对分配后的状态调用安全性算法进行检查 若安全 则 分配 若不安全 则拒绝申请 恢复到原来的状态 拒绝申请 2 银行家算法步骤 1 如果 Requesti or Need 则转向步骤 2 否则 认为出 错 因为它所需要的资源数已超过它所宣布的最大值 2 如果 Request or Available 则转向步骤 3 否则 表 示系统中尚无足够的资源 进程必须等待 3 系统试探把要求的资源分配给进程 Pi 并修改下面数据结 构中的数值 Available Available Request i Allocation Allocation Request Need Need Request 4 系统执行安全性算法 检查此次资源分配后 系统是否 处于安全状态 3 安全性算法步骤 1 设置两个向量 工作向量 Work 它表示系统可提供进程继续运行所需要的各 类资源数目 执行安全算法开始时 Work Allocation 布尔向量 Finish 它表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做 Finish i false 当有足够资源分 配给进程时 令 Finish i true 2 从进程集合中找到一个能满足下述条件的进程 Finish i false Need0 request i j 0 Finish false 判断 开始 运用 c 实现对这三个算法的进行实现 通过自定义进程数和进 程资源的各项数据情况对其进行分配 将其用函数分开 在实现 每一步时进行调用 主要函数如下 showdata 显示资源矩阵 int changdata int i 进行资源分配 int safe 安全性算法 void share 利用银行家算法对申请资源对进行判定 int compare int request int work int N int k 如果 Request i work 则返回 false 即对需求与现有资源的比较 int check int work int request int allocation int finish int p int m int n 调用安全公式进行检测 void jiesuo int work int request int allocation int finish int p int m int n 解锁函数 void operate int work int request int allocation int finish int p int m int n 操作函数 int main 主函数 4 4 运行结果及分析运行结果及分析 假设系统中有三个进程 p q r 和三类资源 a b c 各种资 源的数量分别为 10 5 7 在 T0 时刻的资源分配情况如图 资源情况 进程 Max a b c Allocation a b c Need a b c Available a b c P 7 5 3 0 1 07 4 33 3 2 Q 3 2 22 0 01 2 2 R 9 0 23 0 26 0 0 运行程序后输入数据如图 使用银行家算法所分配的情况和安全检查情况为 死锁检测与排除的运行结果为 这两个程序已经完成了对进程以资源之间检测与分配功能 并且能够在给出资源的分配情况后检测需求是否会发生死锁状况 并给出解除方案 运行程序后只需按照提示操作即可观察到进程 对资源的调用情况 5 5 总结总结 多个进程同时运行时 系统根据各类系统资源的最大需求和 各类系统的剩余资源为进程安排安全序列 使得系统能快速且安 全地运行进程 不至发生死锁 银行家算法是避免死锁的主要方 法 其思路在很多方面都非常值得我们来学习借鉴 通过对算法 的编写让我了解到计算机在调度进程时的具体过程 也明白了解 决死锁的原理 六 附录六 附录 include include include define False 0 define True 1 int Max 100 100 0 各进程所需各类资源的最大需求 int Avaliable 100 0 系统可用资源 char name 100 0 资源的名称 int Allocation 100 100 0 系统已分配资源 int Need 100 100 0 还需要资源 int Request 100 0 请求资源向量 int temp 100 0 存放安全序列 int Work 100 0 存放系统可提供资源 int p 100 0 int q 100 100 0 int z 100 100 0 int M 100 作业的最大数为 100 int N 100 资源的最大数为 100 int gg 1 void showdata 显示资源矩阵 int i j cout endl 此时刻的资源分配情况为 endl cout Max Allocation Need Avaliable endl cout 进程名 for j 0 j 4 j for i 0 i N i cout name i cout cout endl for i 0 i M i cout i for j 0 j N j cout Max i j cout for j 0 j N j cout Allocation i j cout for j 0 j N j cout Need i j if i 0 cout for j 0 j N j cout Avaliable j 输出分配资源 cout endl int changdata int i 进行资源分配 int j for j 0 j M j p j Avaliable j Avaliable j Avaliable j Request j q i j Allocation i j Allocation i j Allocation i j Request j z i j Need i j Need i j Need i j Request j return 1 int safe 安全性算法 int i d k 0 m h s apply Finish 100 0 int j int flag 0 for i 0 i N i Work i Avaliable i cout endl 安全性检查 endl cout Work Need Allocation Work Allocation Finish endl cout 进程名 for h 0 h 4 h for s 0 s N s cout name s cout cout endl for i 0 i M i apply 0 for j 0 j N j if Finish i False if apply N cout i for d 0 d N d cout Work d cout for d 0 d N d cout Need i d cout for d 0 d N d cout Allocation i d cout for m 0 m N m Work m Work m Allocation i m cout Work m 变分配数 Finish i True temp k i cout cout true cout endl i 1 k flag for i 0 i M i if Finish i False for j 0 j N j Avaliable j Avaliable j Request j Allocation i j Allocation i j Request j Need i j Need i j Request j cout endl 系统进入不安全状态 此时系统不分配资源 endl 不成功系统不安全 return 0 cout endl 此时系统是安全的 endl 如果安全 输出成功 cout 安全序列为 for i 0 i M i 输出运行进程数组 cout temp i if i M 1 cout cout endl return 0 void share 利用银行家算法对申请资源对进行判定 char ch int i 0 j 0 ch y cout endl 请输入要求分配的资源进程号 0 M 1 i 输入须申请的资源号 cout endl 请输入进程 i 申请的资源 endl for j 0 j N j cout name j Request j 输入需要申请的资源 for j 0 jNeed i j 判断申请是否大于需求 若大于则出错 cout endl 进程 i 申请的资源大于它需要的资源 cout 分配不合理 不予分配 Avaliable j 判断申请是否大于当前资源 若 大于则 出错 cout endl 进程 i 申请的资源大于系统现在可利用的资源 cout 分配出错 不予分配 endl ch n break if ch y changdata i 根据进程需求量变换资源 showdata 根据进程需求量显示变换后的资源 safe 根据进程需求量进行银行家算法判断 int main 主函数 int t 1 i j number choice m n flag char ming cout 银行家算法的设计与实现 endl cout endl n N n for i 0 i n i cout 资源 i 1 ming name i ming cout number Avaliable i number cout endl cout m M m cout endl 请输入各进程的最大需求量 m n 矩阵 Max endl for i 0 i m i for j 0 j Max i j do flag 0 cout endl 请输入各进程已经申请的资源量 m n 矩 阵 Allocation endl for i 0 i m i for j 0 j Allocation i j if Allocation i j Max i j flag 1 Need i j Max i j Allocation i j if flag cout endl 申请的资源大于最大需求量 请重新输入 n endl while flag showdata 显示各种资源 safe 用银行家算法判定系统是否安全 while 1 if t 1 cout endl 利用银行家算法预分配资源 endl share t 0 else break cout endl t cout endl return 1 死锁检测 include include include using namespace std 名字空间 define TRUE 1 define FALSE 0 布尔值 int compare int request int work int N int k 如果 Request i work 则返 回 false int j c 0 for j 0 jwork j c if c 0 return FALSE else if c 0 return TRUE 判断 int check int work int request int allocation int finish int p int m int n int i j flag TRUE K 0 while flag TRUE 反复判断 直到无法判断 flag FALSE for i 0 i m i 对任一进程进行判断 if finish i FALSEj n j 增加工作向量 work j allocation i j finish i TRUE p i TRUE 第 i 个进程放完资源 flag TRUE break 若所有的进程都放完 则返回 ture 否则返回 false if flag FALSE for i 0 i0 return FALSE else if K 0 return TRUE 8 解锁函数 void jiesuo int work int request int allocation int finish int p int m int n int i j t flag int sum new int m for i 0 i m i 初始化数组 sum i 0 for i 0 i m i 统计死锁资源 释放 if p i FALSE for j 0 j n j sum i sum i allocation i j allocation i j 0 t sum 0 for i 1 i m i 找出最大死锁进程 i if t sum i t sum i flag i cout 撤消占资源最大的进程 flag endl for j 0 j n j 回收资源 work j allocation flag j finish flag TRUE 完成 flag 进程的操作 p flag FALSE 不再对它进行判断 flag check work request allocation finish p m n 判断是否已经解除死 锁 if flag TRUE cout endl cout 成功解除死锁 endl else jiesuo work request allocation finish p m n 如果还没解除 继续放 资源 void operate int work int request int allocation int finish int p int m int n int flag flag check work request allocation finish p m n 判断 if flag TRUE cout 不会发生死锁 endl else cout 会发生死锁 死锁进程如下 endl for int i 0 i m i 找出死锁进程 if p i FALSE cout i cout endl jiesuo work request allocation finish p m n 解锁 void main 主函数 cout 死锁检测与解除算法示例 endl int m 0 int n 0 int i j cout m cout endl cout n cout endl int allocation new int m 定义数组 int max new int m int need new int m int request new int m int available new int n int p new int m int finish new int m int work new int n for i 0 i m i 初始每个进程放资源状态为 false p i FALSE cout 输入可用矩阵 available n endl for i 0 i n i cout available i available i cout endl for i 0 i m i allocation i new int n cout 输入已分配矩阵 allocation m n endl for i 0 i m i for j 0 j n j cout allocation i j allocation i j cout endl for i 0 i m i max i new int n cout 输入最大需求矩阵 max m n endl for i 0 i m i for j 0 j n j cout max i j max i j cout endl for i 0 i m i need i new int n cout 需求矩阵为 need m n endl for i 0 i m i for j 0 j n j need i j max i j allocation i j cout need i j cout endl for i 0 i m i request i new int n cout 请输入请求矩阵 request m n endl for i 0 i m i for j 0 j n j cout request i j request i j cout endl cout endl for i 0 i m i finish i TRUE 初始标记为 true for j 0 j0 request i j 0 finish i FALSE for j 0 j n j work j available j 初始情况 operate work request allocation finish p m n 开始判断 设计设计 3 3 磁盘调度算法的实现磁盘调度算法的实现 1 1 设计目的设计目的 设计程序模拟先来先服务 FCFS 最短寻道时间优先 SSTF SCAN 和循环 SCAN 算法的工作过程 假设有 n 个磁道 号所组成的磁道访问序列 给定开始磁道号 m 和磁头移动的方 向 正向或者反向 分别利用不同的磁盘调度算法访问磁道序 列 给出每一次访问的磁头移动距离 计算每种算法的平均寻道 长度 本程序采用随机数来产生磁道数 2 2 设计要求设计要求 算法所需的各种参数由输入产生 手工输入或者随机数产生 最后的结果要求是在运行四种算法的程序后 能够输出调度 过程 平均寻道长度的正确结果 3 3 设计说明设计说明 1 先来先服务 FCFS 这是一种简单的磁盘调度算法 它根据进程请求访问磁盘的 先后次序进行调度 此算法的优点是公平 简单 且每个进程的 请求都能依次得到处理 不会出现某一进程的请求长期得不到满 足的情况 但此算法由于未对寻道进行优化 致使平均寻道时间 可能较长 2 最短寻道时间优先 SSTF 该算法选择这样的进程 其要求访问的磁道与当前磁头所 在的磁道距离最近 以使每次的寻道时间最短 但这种调度算法 却不能保证平均寻道时间最短 3 扫描算法 SCAN SCAN 算法不仅考虑到欲访问的磁道与当前磁道的距离 更 优先考虑的是磁头的当前移动方向 例如 当磁头正在自里向外 移动时 SCAN 算法所选择的下一个访问对象应是其欲访问的磁 道既在当前磁道之外 又是距离最近的 这样自里向外地访问 直到再无更外的磁道需要访问才将磁臂换向 自外向里移动 这 时 同样也是每次选择这样的进程来调度 即其要访问的磁道 在当前磁道之内 从而避免了饥饿现象的出现 由于这种算法中 磁头移动的规律颇似电梯的运行 故又称为电梯调度算法 4 循环扫描算法 CSCAN CSCAN 算法是对扫描算法的改进 如果对磁道的访问请求 是均匀分布的 当磁头到达磁盘的一端 并反向运动时落在磁头 之后的访问请求相对较少 这是由于这些磁道刚被处理 而磁盘 另一端的请求密度相当高 且这些访问请求等待的时间较长 为 了解决这种情况 循环扫描算法规定磁头单向移动 例如 只自 里向外移动 当磁头移到最外的被访问磁道时 磁头立即返回到 最里的欲访磁道 即将最小磁道号紧接着最大磁道号构成循环 进行扫描 本系统划分为四个模块 先来先服务算法模块 void FCFS int array int m 最短寻道时间优先算法模块 void SSTF int array int m 扫描算法模块 void SCAN int array int m 循环扫描模 块 void CSCAN int Han int DiscL 系统模块图 磁盘调度模拟系统 先 来 先 服 务 算 法 最 短 寻 道 时 间 优 先 扫 描 算 法 循 环 扫 描 算 法 1 先来先服务算法模块 void FCFS int array int m 输入磁道号 按先来先服务的策略输出磁盘请求序列 求平均寻 道长度 输出移动平均磁道数 2 最短寻道时间优先算法模块 void SSTF int array int m 将磁道号用冒泡法从小到大排序 输出排好序的磁道序列 输入 当前磁道号 根据前磁道在已排的序列中的位置 选择扫描的顺 序 求出平均寻道长度 输出移动的平均磁道数 3 扫描算法模块 void SCAN int array int m 将磁道号用冒泡法从小到大排序 输出排好序的序列 输入当前 磁道号 选择移动臂的移动方向 根据当前磁道在已排的序列中 的位置 选择扫描的顺序 求出平均寻道长度 输出移动的平均 磁道数 4 循环扫描算法模块 void CSCAN int array int m 将磁道号用冒泡法从小到大排序 输出排好序的序列 输入当前 磁道号 规定移动臂单向反复的从内向外移动 根据当前磁道在 已排的序列中的位置 选择扫描的顺序 求出平均寻道长度 输 出移动的平均磁道数 1 1 先来先服务 先来先服务 FCFS FCFS 这是一种简单的磁盘调度算法 它根据进程请求访问磁盘的 先后次序进行调度 此算法的优点是公平 简单 且每个进程的 请求都能依次得到处理 不会出现某一进程的请求长期得不到满 足的情况 但此算法由于未对寻道进行优化 致使平均寻道时间 可能较长 实现函数 void FCFS int Han int DiscL 先来先服务算法 FCFS 流程图 输入磁道号 求平均寻道长度 输出移动的平均磁道数 按输入顺序将磁道序列输出 开始 结束 2 最短寻道时间优先最短寻道时间优先 SSTF SSTF 该算法选择这样的进程 其要求访问的磁道与当前磁头所在 的磁道距离最近 以使每次的寻道时间最短 但这种调度算法却 不能保证平均寻道时间最短 实现函数 void SSTF int Han int DiscL 最短寻道时间优先流程图 求平均寻道长 度 选择与当前磁道距 离最近的磁道进行 扫描 移动到最小 大 号 改向外 内 移动扫描未扫描 的磁道 输出移动的平均磁道 数 输出排好序的磁道序 列 判断当前磁 头在序列中 的位置 结 束 开 始 输入磁道 号 使用冒泡法从小到大 排序 输入当前磁道 号 3 扫描算法扫描算法 SCAN SCAN SCAN 算法不仅考虑到欲访问的磁道与当前磁道的距离 更 优先考虑的是磁头的当前移动方向 例如 当磁头正在自里向外 移动时 SCAN 算法所选择的下一个访问对象应是其欲访问的磁 道既在当前磁道之外 又是距离最近的 这样自里向外地访问 直到再无更外的磁道需要访问才将磁臂换向 自外向里移动 这 时 同样也是每次选择这样的进程来调度 即其要访问的磁道 在当前磁道之内 从而避免了饥饿现象的出现 由于这种算法中 磁头移动的规律颇似电梯的运行 故又称为电梯调度算法 实现函数 int SCAN int Han int DiscL int x int y 求平均寻道长 度 选择移动臂移 动方向 开始 扫描 移动到最小 大 号 改向外 内 移动扫描未扫描 的磁道 输出移动的平均磁 道数 输出排好序的磁道 序列 开 始 结 束 输入磁道 号 使用冒泡法从小到大 排序 输入当前磁道 号 判断当前磁 头在序列中 的位置 4 循环扫描算法 CSCAN CSCAN 算法在 SCAN 算法的基础上规定了刺头单向移动 减少了进程的请求延迟 例如 只是自理向外移动 当磁头移到 最外的磁道并访问后 磁头立即返回到最里的欲访问磁道 亦即 将最小的磁道号紧接着最大的磁道号构成循环 进行循环扫描 实现函数 void CSCAN int Han int DiscL 求平均寻道 长度 扫描到最大号后 直接移动到最小 号从内向外扫描 未扫描的磁道 输出移动的平均 磁道数 输出排好序的磁 道序列 判断当前 磁头在序 列中的位 置 规定移动臂单 向反复的从内 向外扫描 开 始 结 束 输入磁道 号 使用冒泡法从小到 大排序 输入当前磁 道号 4 4 运行结果及分析运行结果及分析 输入初始磁道数 100 磁道范围 180 然后选择相应算法操作 如下图 FCFS SSTF SCAN CSCAN 本系统具有很强的健壮性 当输入错误数据类型时 系统提示用 户输入的数据类型错误 让用户重新输入 保证系统的稳定性 不会因为用户的误操作而致使系统瘫痪 虽然是在 dos 状态下 但是本系统界面还是设计的比较漂亮的 具有比较好的交互性 对于软件中的重用代码 设计成一个函