物理与电子信息工程学院。
操作系统》课程设计报告。
题目：1、 页面淘汰算法。
2、 磁盘调度算法。
一、 设计目的：
1、 掌握基本操作系统理论。
2、 根据操作系统理论算法编写相应的调度程序。
3、 使用多种算法在特定的数据下比较其优点与缺陷。
4、 尝试改进相应数据结构，使调度更加简易、明显。
5、 锻炼实践能力为后继课程奠定基础。
二、 设计环境：
1、 windows xp操作系统或者linux（ubuntu 12.04）
2、 microsoft visual c++ 6.0 编译器或者 gun g++，matlab数学统计分析软件。
3、 编辑插件：va view、vim
4、 shell运行良好，无特殊异常。
三、 设计内容（全部设计内容）：
a) 小组从进程调度算法实现。
b) 页面淘汰算法实现。
c) 磁盘调度算法实现。
d) 实际磁盘管理方式演示实现。
e) 二级文件系统设计实现。
经过小组参考与讨论，最终绝对选定b(页面淘汰算法实现)、c(磁盘调度算法实现)。
四、 设计要求：
1、 页面淘汰算法实现设计要求：
a) 设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响。
b) 要求有一定的参数控制能力，可以用户自己调节随机性能。
c) 编写页面淘汰算法本身。
d) 结果数据的显示或提取。
e) 结果数据的分析。
2、 磁盘调度算法实现设计要求：
a) 设计随机磁道访问产生程序，并说明随机的性能和其性能可能对算法的影响。
b) 要求有一定的参数控制能力，可以用户自己调节随机性能。
c) 编写磁盘调度算法本身。
d) 结果数据的显示或提取。
e) 结果数据的分析。
五、 设计原理：
1、 页面淘汰算法原理：
1.1、 页面淘汰算法定义与简介：
在进程运行过程中，若其要访问的页面不在内存而需把它们调入内存，但内存已经无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面淘汰算法或者页面置换算法（page-replacement algorithms）。
置换算法的好坏，将直接影响到系统的性能。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或把那些在较长时间内不会再访问的页面调出。目前存在着许多页面置换算法，它们都试图更接近于理论上的目标。
1.2、 先进先出（fifo）页面置换算法。
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留实践最久的页面予以淘汰。该算法实现简单，只需把一个进程调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如含有全局变量、常用函数、例程等地页面，fifo算法并不能保证这些页面不被淘汰。具体实现流程图如下：
注：在 fifo 算法中，无论有无发生缺页或者置换，都需要对每个在内存中的页面的 time值进行增加操作，以保持最先进入的那个页面的 time 值是最大的；一个新进来的页面，其time 值设置为 0。算法也可以通过队列结构来实现，利用队列的先进先出（fifo）特性完成，无需设置 time 字段。
1.2.1、 数据结构介绍：
1.2.2、 算法源程序：（见附录）。
1.3 、最佳置换法（opt）背景与简介：
它是由 belady 于 1966 年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。具体流程图如下：
注：distance 用于记录内存物理块集合中每个页面距离再次被使用的页面跨度，缺省值为int_max，如果某个页面在后续指令集合中不再出现，则用最大值 int_max 缺省取代；如果页面再次被使用，则两次使用所跨的页面数，为页面跨度。用最大页面跨度表示以后永不使用或未来最长时间内不再被访问。
1.3.1、数据结构介绍：
1.3.2、算法源程序：（见附录）
1.4、最近最久未使用（lru）页面置换算法：
最近最久未使用（lru）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法**各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，lru 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间time,，当须淘汰一个页面时，选择现有页面中其time值最大的，即最近最久未使用的页面予以淘汰。
注：在 lru 算法中，无论是否发生缺页或者置换，除了命中（刚刚被访问过的页面）页面time 值清零之外，其它所有内存中的页面的 time 值都加一，以保证最近刚刚被访问的页面的 time 值最小，相应 time 值最大的页面就是最近最久没有被访问的页面。
1.4.1、数据结构介绍：
1.4.2、算法源程序：（见附录）
2、磁盘调度主要思想。
设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。
操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。
因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。
平均寻道长度（l）为所有磁道所需移动距离之和除以总的所需访问的磁道数（n），即：
l=（m1+m2+……mi+……mn）/n 其中mi为所需访问的磁道号所需移动的磁道数。
启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：
a、寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。
b、延迟时间——指定扇区旋转到磁头下所需的时间。
c、传送时间——由磁头进程读写完成信息传送的时间。
其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。
为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。
2.1、先来先服务（fcfs，first come first served）
这是一种最简单的磁盘调度算法。它是根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。
但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
2.2、scan算法。
该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的时磁头当前的移动方向。例如，当磁头正在自里向外移动时，scan算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样的自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。
这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。由于在这种算法种磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。
2.3、cscan算法。
单向扫描调度算法（cscan）是scan进行了改进。扫描调度算法（scan）存在这样的问题：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这是该进程必须等待，待磁头从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被严重地推迟。
为了减少这种延迟，cscan算法规定磁头只做单向移动。[1]例如，磁头只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
2.4、最短寻道时间优先(shortestseektimefirst，sstf)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。sstf算法的平均每次磁头移动距离，明显低于fcfs的距离。sstf较之fcfs有更好的寻道性能，故过去一度被广泛采用过。
2.5、程序流程图：（可见附录图，此图为截图，不清晰）
2.5、各个算法的比较：
六、 数据收集与统计分析。
小组采用随机函数生成足够大的数据量，并且采用matlab数学统计分析软件进行绘图与分析，探索算法之间变量与因变量的关系。
注：matlab源**附表。
1、磁盘调度算法分析。
数据内容分别存储在“disk队列”与“disk移动距离”纯文本文件中。
我们以数列长度为横坐标(x)，移动距离为纵坐标(y)，采取matlab作图工具分析得下图：
根据上图，可以很明显地看出fsfc算法是平均总移动距离最长的，它的y轴差等值为2000，而其它三个图像为500。
现在，我们假定它们存**性的关系。对四种算法做出线性拟合。
假设方程为：。
其中y为总移动距离，x为队列长度，那么其斜率就可以抽象为它线性范围内的平均移动长度。
在fcfs算法中，可得斜率为165.4，置信区间为[162.3,168.5]；
在scan算法中，可得斜率为44.0，置信区间为[42.3,45.7]；
操作系统课程设计
课程设计 河北大学工商学院。装。订。线。操作系统课程设计。题目 操作系统课程设计 学院工商学院 学部信息科学与工程 专 操作系统课程设计。题目 操作系统课程设计 学院工商学院 学部信息科学与工程 专业计算机类 学号 姓名。指导教师。年 6 月 24 日。设备管理 2 2.1设计任务2 2.2设计要求...
操作系统课程设计
银行家算法模拟。系别 班级 组员 银行家算法模拟。1.课程设计目的。通过本次课程设计，加深对最经典的避免死锁的银行家算法的理解，掌握死锁形成必要条件 安全状态等概念的理解，通过用c语言编程模拟该算法，并在windows平台上实现，更好地掌握操作系统的原理及实现方法。2.任务及要求。设n为系统进程的个...
操作系统课程设计
学生实习实训报告。实习类型 操作系统课程设计 学号 0901110005 学生姓名 田兴杰 指导教师 曹春梅 专业班级 信息安全技术0901班 院 部 电子信息系 2011年 1 月 7日。实习实训成绩评定表。目录。目录3 摘要4关键字4 1.1虚拟机简介5 1.1.1 一般意义的虚拟机5 1.1....