2022年操作系统磁盘调度算法 .pdf

1 操作系统课程设计任务书题目：磁盘调度算法院系：专业：班级：姓名：学号：指导教师：设计时间：2018.1.1-2018.1.5 指导教师评语名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 23 页 - - - - - - - - - 2 成绩评定：指导教师签字：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 23 页 - - - - - - - - - 3 目 录1、需求分析 . 4 1.1 课题描述 . 41.2 课题目的 . 41.3 理论依据 . 72、概要设计 . 8 2.1 设计方法 . 82.2 技术 . 82.3 运行环境 . 83、详细设计 . 9 3.1 流程图. 11 3.2 程序主要代码. 134、运行结果及分析 . 14 4.1 运行结果 . 15 4.2 结果详细分析. 165、总结和心得 . 16 6、参考文献 . 17 7、附录：程序源代码 . 23 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 23 页 - - - - - - - - - 4 1、需求分析1.1 课题描述这次课程设计我研究的题目是：磁盘调度算法。具体包括三种算法分别是： 先来先服务算法 （FCFS ） 、最短寻道时间优先算法(SSTF )、扫描算法（电梯调度算法）(SCAN )。1.2 课题目的通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务 FCFS ，最短寻道时间优先SSTF ，扫描 SCAN 算法的实现方法。1.3 理论依据设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3 部分构成，它们是查找 （查找磁道） 时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（ N） ，即： L=（M1+M2+ , +Mi+, +MN ）/N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页 - - - - - - - - - 5 其中 Mi 为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间。 延迟时间指定扇区旋转到磁头下所需的时间。传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后， 再放到下一个盘面上。 而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序，每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。 由于在访问磁盘的时间中， 主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。先来先服务（ FCFS ）调度 :按先来后到次序服务，未作优化。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 23 页 - - - - - - - - - 6 最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当 50 号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达 99 号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50 号柱面的操作结束后，应该先处理 61 号柱面的请求，然后到达32 号柱面执行操作，随后处理 15 号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离， 与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（ SSTF ）调度，FCFS会引起读写头在盘面上的大范围移动， SSTF查找距离磁头最短（也就是查找时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 23 页 - - - - - - - - - 7 最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿） 。SCAN 算法又称电梯调度算法 。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动， SCAN 算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4 层时，依次有 3 位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2 层等待去 10层；伍生在 5 层等待去底层； 张生在 8 层等待 15 层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8 层带到 15 层，然后电梯换成下行方向， 把乘客伍生从 5 层带到底层，电梯最后再调换方向，把乘客陈生从2 层送到 10 层。但是， “电梯调度” 算法在实现时， 不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 23 页 - - - - - - - - - 8 2、概要设计2.1 设计方法通过 C 语言的编程，设计程序模拟先来先服务FCFS ，最短寻道时间优先 SSTF ，和扫描 SCAN 算法的工作过程。假设有n 个磁道号所组成的磁道访问序列， 给定开始磁道号 m和磁头移动的方向 （正向或者反向） ，分别利用不同的磁盘调度算法访问磁道序列，给出磁头每一次移动的过程， 算出磁头移动的距离， 继而计算每种算法的平均寻道长度。2.2 技术C语言、操作系统磁盘调度算法、C+ 。2.3 运行环境Window10 、VC+6.0 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 23 页 - - - - - - - - - 9 3、详细设计 3.1流程图先来先服务算法（ FCFS ） ：开始输 入 当 前 磁道号 now 磁头移动距离Sum=abs(now-array0) 磁头移动总距离Sum+=abs(arrayj-arrayi) 输 出 磁 盘 调 度序列 arrayj 目前的位置变为当前的位置 j+ jm Avg=sum/(m) 结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - 10 最短寻道时间优先算法 (SSTF )：开始结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 23 页 - - - - - - - - - 11 扫描 SCAN 算法：开始结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 23 页 - - - - - - - - - 12 3.2 程序主要代码先来先服务算法（ FCFS ） ：void FCFS(vectorm_vec,int position) /先来先服务算法dis = 0; average_distance = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) dis += abs(position-*it); Sleep(500); cout*it; position = *it; compute_dis(m_vec,dis,average_distance); 最短寻道时间优先算法 (SSTF )：void SSTF(vectorm_vec,int position) /最短寻道时间算法dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /从小到大排序int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; int count = 0; int left = i-1; int right = i; while(count=0 & abs(m_vecright-position) abs(m_vecleft-position) | right=m_vec.size() dis += abs(m_vecleft-position); Sleep(500); coutm_vecleft; position = m_vecleft; left-; else dis += abs(m_vecright-position); Sleep(500); coutm_vecright; position = m_vecright; right+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 23 页 - - - - - - - - - 13 count+; compute_dis(m_vec,dis,average_distance); 扫描 SCAN 算法：void SCAN(vectorm_vec,int position) /电梯调度算法dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /从小到大排序int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; /找到 position 所在的磁道 int left = i - 1; /先从外到内扫描int right = i; while(left = 0) dis += abs(position - m_vecleft); Sleep(500); coutm_vecleft; position = m_vecleft; left -; while(right m_vec.size() dis += abs(position - m_vecright); Sleep(500); coutm_vecright; position = m_vecright; right +; compute_dis(m_vec,dis,average_distance); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 23 页 - - - - - - - - - 14 4、运行结果及分析4.1 运行结果先来先服务算法（ FCFS ） ：最短寻道时间优先算法 (SSTF )：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 23 页 - - - - - - - - - 15 扫描 SCAN 算法：4.2 结果详细分析FCFS ：这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。SSTF ：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。SCAN ：扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。此算法基本上克服了名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 23 页 - - - - - - - - - 16 最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。5、总结和心得通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，才能提高自己实践能力。通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，各种流图设计特别是算法过程图的设计很容易忽略操作性细节，在实际调试中带来很大麻烦，需要特别注意，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解模拟磁盘调度算法，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 23 页 - - - - - - - - - 17 6、参考文献 1. 汤子瀛，哲凤屏，汤小丹 . 计算机操作系统 . 西安电子科技大学出版社 , 2005; 2. 谭浩强编著 . C 语言程序设计（第3 版） . 清华大学出版社， 2005; 3. 吴乃陵，况迎辉 . C+ 程序设计（第二版）. 高等教育出版社，2005。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 23 页 - - - - - - - - - 18 7、附录：程序源代码FCFS：#include #include #include #include #include #include #include #include #include using namespace std; int position = 0; /当前磁道位置int dis = 0; double average_distance = 0; void request(vector&m_vec,ofstream &outfile) cout随机生成磁盘序列：endl; int n = 0; srand(time(NULL); /添加随机数种子n = rand() % 20 + 1; int temp = 0; for(int i=0;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout当前磁道： positionendl; void compute_dis(vectorm_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size(); void FCFS(vectorm_vec,int position) /先来先服务算法dis = 0; average_distance = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) dis += abs(position-*it); Sleep(500); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 23 页 - - - - - - - - - 19 cout*it; position = *it; compute_dis(m_vec,dis,average_distance); void print() coutendlendl; cout经计算，磁头移动的总距离为:disendl; cout磁头平均移动距离:average_distanceendl; coutendlendl; int main() ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /请求服务序列cout磁盘请求的服务状况：endl; FCFS(m_vec, position); print(); outfile.close(); return 0; SSTF: #include #include #include #include #include #include #include #include #include using namespace std; int position = 0; /当前磁道位置int dis = 0; double average_distance = 0; void request(vector&m_vec,ofstream &outfile) cout随机生成磁盘序列：endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 23 页 - - - - - - - - - 20 int n = 0; srand(time(NULL); /添加随机数种子n = rand() % 20 + 1; int temp = 0; for(int i=0;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout当前磁道： positionendl; void compute_dis(vectorm_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size(); void SSTF(vectorm_vec,int position) /最短寻道时间算法dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /从小到大排序int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; int count = 0; int left = i-1; int right = i; while(count=0 & abs(m_vecright-position) abs(m_vecleft-position) | right=m_vec.size() dis += abs(m_vecleft-position); Sleep(500); coutm_vecleft; position = m_vecleft; left-; else dis += abs(m_vecright-position); Sleep(500); coutm_vecright; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 23 页 - - - - - - - - - 21 position = m_vecright; right+; count+; compute_dis(m_vec,dis,average_distance); void print() coutendlendl; cout经计算，磁头移动的总距离为:disendl; cout磁头平均移动距离:average_distanceendl; coutendlendl; int main() ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /请求服务序列cout磁盘请求的服务状况：endl; SSTF(m_vec, position); print(); outfile.close(); return 0; SCAN: #include #include #include #include #include #include #include #include #include using namespace std; int position = 0; /当前磁道位置int dis = 0; double average_distance = 0; void request(vector&m_vec,ofstream &outfile) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 23 页 - - - - - - - - - 22 cout随机生成磁盘序列：endl; int n = 0; srand(time(NULL); /添加随机数种子n = rand() % 20 + 1; int temp = 0; for(int i=0;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout当前磁道： positionendl; void compute_dis(vectorm_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size(); void SCAN(vectorm_vec,int position) /电梯调度算法dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /从小到大排序int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; /找到 position 所在的磁道 int left = i - 1; /先从外到内扫描int right = i; while(left = 0) dis += abs(position - m_vecleft); Sleep(500); coutm_vecleft; position = m_vecleft; left -; while(right m_vec.size() dis += abs(position - m_vecright); Sleep(500); coutm_vecright; position = m_vecright; right +; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 23 页 - - - - - - - - - 23 compute_dis(m_vec,dis,average_distance); void print() coutendlendl; cout经计算，磁头移动的总距离为:disendl; cout磁头平均移动距离:average_distanceendl; coutendlendl; int main() ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /请求服务序列cout磁盘请求的服务状况：endl; SCAN(m_vec, position); print(); outfile.close(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 23 页 - - - - - - - - -