操作系统电梯调度LRU页面反馈探析.doc

《操作系统原理》 课程设计报告 姓 名： 付豪 班 级： 网络1311 学 号： 131003600139 指导老师： 宁建红 2016 年 1月 目 录 1 背景知识 1 1.1电梯调度算法 1 1.2页故障率反馈模型 1 2 设计内容 2 2.1电梯调度算法 2 2.1.1基本原理分析 2 2.1.2数据结构 2 2.1.3程序流程图 3 2.1.4函数介绍 4 2.1.5源代码 4 2.1.6结果 12 2.2页故障率反馈模型 14 2.2.1基本原理分析 14 2.2.2程序流程图 15 2.2.3函数介绍 16 2.2.4源代码 16 2.2.5结果 18 3 结论 20 参考文献 21 1 背景知识 1.1电梯调度算法 磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），电梯调度算法（SCAN），循环扫描算法（CSCAN） SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于磁头移动规律与电梯运行相似，故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如FCFS算法和SSTF算法好。 算法思想：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。 1.2页故障率反馈模型 在虚拟页式存储管理系统中，进程运行之前会把一部分页面装入内存，而另一部分页面装入外存中。在进程运行过程中，如果所访问的页面在内存，则与无虚拟页存储时的情形相同；所访问的页面不在内存，则发生缺页故障。 建立工作集页面模型，利用随机函数动态生成进程访问页面的序列号，实现页面淘汰算法，实现页故障率反馈模型。在虚拟页式存储管理系统中，进程运行之前会把一部分页面装入内存，而另一部分页面装入外存。在进程运行过程中，如果所访问的页面在内存，则与无虚拟页式存储时的情形相同；如果所访问的页面不在内存，则发生缺页故障，进入操作系统，有操作系统进行页面的动态调度，进行页面的置换。 2 设计内容 2.1电梯调度算法 2.1.1基本原理分析 电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动. 模拟电梯调度算法，对磁盘进行移臂和旋转调度。 磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。 “驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。 2.1.2数据结构 typedef struct PCB { char proc[M];//进程名 int cylinder_num;//柱面号 int track_num;//磁道号 int phy_num;//物理记录号 struct PCB *next;// 进程指向下一节点 }PCB; 2.1.3程序流程图 2.1.4函数介绍 void