桂林电子科技大学信息科技学院操作系统习题复习课.ppt

SCAN调度算法 100道开始，增加方向 被访问下一个磁道 移动距离 150 50 160 10 184 24 90 94 58 32 55 3 39 16 38 1 18 20 平均寻道长度：27.8 Cscan算法规定磁头单项移动，进行循环扫描。一个方向读完，不是象SCAN那样回头，而是循环。 访问时间：2T?T+Smax T是从外向里或从里向外单向扫描完要访问的磁道的寻道时间。 而Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道的寻道时间。 4. 循环扫描(CSCAN)算法 CSCAN调度算法 100道开始，增加方向 被访问的下一个磁道 移动距离 150 50 160 10 184 24 18 166 38 20 39 1 55 16 58 3 90 32 平均寻道长度：27.5 若某磁盘共有200个柱面，其编号为0～199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。 (1)先来先服务调度算法： 实际服务的次序： 96→175→52→157→36→159→106→108→72 移动臂需移动的距离为： (175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642 移动臂需移动642柱面的距离。 (2)最短寻找时间优先调度算法： 实际服务的次序：96→106→108→72→52→36→157→159→175 移动臂需移动的距离为： (106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223 移动臂需移动223个柱面的距离。 (1)电梯调度算法： 实际服务的次序：96→106→108→157→159→175→72→52→36 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72-52)+(52-36)=218 移动臂需移动218个柱面的距离。 (2)单向扫描调度算法： 实际服务的次序：96→106→108→157→159→175→36→52→72 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254 除了移动臂由里向外返回所用的时间外，还需移动254个柱面的距离。 七、最佳置换算法和先进先出算法 1、FIFO 淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。 出发点：最早调入主存中的页面不再使用的可能性越大，应该最先淘汰。算法简单对具有按线性顺序访问的程序比较合适，而对其它情况效率不高 最佳置换算法和先进先出算法 进程P执行时的页面走向为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次； 如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次； Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。 习题 1．某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5，分别画出其分配物理块为3的最佳置换算法的置换图。 2．某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5，分别画出其分配物理块为3和4的FIFO算法的置换图。 3．在请求分页管理系统中，一个作业要依次访问如下页面：3 4 2 1 4 3 1 4 3 1 4 5，采用LRU置换算法求出访问过程中发生的缺页中断的次数及缺页率。设分给作业的存储块数为3. 4．在请求分页管理系统中，一个作业要依次访问如下页面：2 3 2 1 5 2 4 5 3 2 5 2，设分给作业的存储块数为3。若用最佳置换算法，先进先出，LRU置换算法求出访问过程中发生的缺页次数及缺页率。 习题 1．某进程执行时的页面走