首页 > 代码库 > FCFS,SSTF,SCAN,FIFO,LRO考点题解

FCFS,SSTF,SCAN,FIFO,LRO考点题解

 


四、应用题 ( 本大题共5 小题,50 分 )

1. 假设某系统中有五个进程,每个进程的执行时间(单位:ms)和优先数如下表所示(优先数越小,其优先级越高)。

进程

执行时间

优先数

   P1

   P2

   P3

   P4

   P5

10

1

2

1

5

   3

   1

   5

   4

   2

 

 

 

 

 

 

 

如果在0时刻,各进程按P1、P2、P3、P4、P5的顺序同时到达,请回答以下问题:(12分)

(1)当系统采用先来先服务调度算法时:

进程执行顺序是      p1 p2 p3 p4 p5      平均周转时间是  13.4ms    


 

 


(2)当系统采用高优先级优先调度算法时:

进程执行顺序是     p2 p5 p1 p4 p3    平均周转时间是        11.8ms       

 


 


 

 (3)当系统采用时间片轮转法时

进程执行顺序是   p1、p2、p3、p4、p5、p1、p3、p5、p1、p5、p1、p5、p1、p5、 p1  平均周转时间是      9.2ms  

 


 


2.在一个段式存储管理系统中,其段表如下表所示:

段号

内存起始地址

段长

 0

 1

 2

 3

 4

   210

   2350

   100

   1350

1938

 500

 20

90

590

95

请将下列逻辑地址所对应的物理地址填入下表中(10分):

段号

段内位移

物理地址

  0

  430

 640

  1

  10

 2360

  2

  500

 段长越界

  3

  400

 1750

  5

  32

 段号越界

 

 


解析:

0段号内存起始地址为210,段内位移430<段长500,说明段长没有越界,所以物理地址为210+430=640

1段号内存起始地址为2350,段内位移10<段长20,说明段长没有越界,所以物理地址为2350+10=2360

2段号内存起始地址为100,段内位移500>段长90,说明段长越界。

3段号内存起始地址为1350,段内位移400<段长590,说明段长没有越界,所以物理地址为1350+400=1750

由于段表中没有5段号,所以段号5段号越界。

 

 


 3.设某移动头磁盘有200道,编号为0~199,磁头刚从143道完成了读写,且正向磁道号增加方向移动,对于如下访盘请求序列(磁道号):

       86,147,91,177,94,150,102,175,130

请回答以下问题:(12分)

(1)在FCFS调度算法下的磁头移动顺序为 143,86,147,91,177,94,150,102,175,130   ;磁头移动的总距离为565

 


解析:

百度百科

FCFS(First Come First Served )先来先服务,英语谚语。在计算机领域中,有时被用以描述数据结构中的队列性质,类似于FIFO(先进先出)。

任务

在计算机并行任务处理中,被视为最简单的任务排序策略,即是无论任务大小和所需完成时间,对先到的任务先处理,后到的任务后处理。它是一种非抢占式策略。

FCFS:先来先服务调度算法。

磁头刚从143道完成了读写,如下访盘请求序列(磁道号):

 

       86,147,91,177,94,150,102,175,130

那么按照FSFS算法读取顺序为:

 

      143, 86,147,91,177,94,150,102,175,130

 那么 读取86时磁头移动距离为:  143-86=57

           读取147时磁头移动距离为:147-86=61

           读取91时磁头移动距离为:  147-91=56

           读取177时磁头移动距离为:177-91=86

           读取94时磁头移动距离为:   177-94=83

           读取150时磁头移动距离为: 150-94=56

           读取102时磁头移动距离为: 150-102=48

          读取175时磁头移动距离为:  175-102=73

          读取130时磁头移动距离为:  175-130=45

因此,磁头移动的总距离为57+61+56+86+83+56+48+73+45=565

 


(2)在SSTF调度算法下的磁头移动顺序为  143,147,150,130,102,94,91,86,175,177                                ;磁头移动的总距离为     162     

*******************************************************

解析:

百度百科

SSTF

最短寻道时间优先(ShortestSeekTimeFirst,SSTF)
 
该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,但这种调度算法却不能保证平均寻道时间最短。SSTF算法的平均每次磁头移动距离,明显低于FCFS的距离。SSTF较之FCFS有更好的寻道性能,故过去一度被广泛采用过。
 

SSTF:最短寻道时间优先调度算法。

0  86  91  94  102  130  143  147  150  175  177


 磁头刚从143道完成了读写,如下访盘请求序列(磁道号):

       86,147,91,177,94,150,102,175,130

那么按照当处于143道时,查找最短寻道时间。

143-130=13>4=147-143

所以下一个最短寻道时间访问的应该是147。

这时访问磁道顺序为143,147

同理,147-130=17>3=150-147

 这时访问磁道顺序为143,147,150

175-150=25>20=150-130

这时访问磁道顺序为143,147,150,130

130-102=28<45=175-130

这时访问磁道顺序为143,147,150,130,102

依次类推,最后访问磁道顺序为:

143,147,150,130,102,94,91,86,175,177

访问147磁道距离:147-143=4

访问150磁道距离:150-147=3

访问130磁道距离:150-130=20

访问102磁道距离:130-102=28

访问94磁道距离:102-94=8

访问91磁道距离:94-91=3

访问86磁道距离:91-86=5

访问175磁道距离:175-86=89

访问177磁道距离:177-175=2

因此,磁头移动总距离为:4+3+20+28+8+3+5+89+2=162


 

(3)在SCAN调度算法下的磁头移动顺序为   143,147,150,175,177,130,102,94,91,86  ;磁头移动的总距离为  125         

 


 解析:

百度百科

SCAN:扫描调度算法(又称电梯调度算法)是计算机磁盘驱动调度的一种方法。

实现方法:

                    扫描算法(SCAN)不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。当磁头正在由里向外移动时,SCAN算法所选择的下一 个访问对象应是其欲访问的磁道,既在当前磁道之外,又是距离最近的。这样由里向外地访问,直至再无更外的磁道需要访问时,才将磁臂换向,由外向里移动。这 时,同样也是每次选择在当前磁道之内,且距离最近的进程来调度。

SCAN:扫描算法(SCAN)不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。

0  86  91  94  102  130  143——> 147  150  175  177

 


 当处于143道时,优先考虑的是磁头的当前移动方向

所以访问时磁头当前移动的方向优先,即

143——>147——>150——>175——>177

当磁头访问到177时,已经没有了更外的磁道需要访问,这时磁臂换向,然后由外向里移动。


因此,采用SCAN调度算法磁头移动顺序为:

143——>147——>150——>175——>177——>130——>102——>94——>91——>86

访问147磁道距离:147-143=4

访问150磁道距离:150-147=3

访问175磁道距离:175-150=25

访问177磁道距离:177-175=2

访问130磁道距离:177-130=47

访问102磁道距离:130-102=28

访问94磁道距离:  102-94=8

访问91磁道距离:94-91=3

访问86磁道距离:91-86=5

因此,磁头移动总距离:4+3+25+2+47+28+8+3+5=125

 

 


 

4.设系统分配给某作业4个页帧使用,执行时的页面走向为:

                     1,2,3,6,4,7,3,2,1,4,7,5,6,5,2,1

请回答以下问题:(10分)

(1)采用FIFO页面置换算法时:

淘汰页面的顺序为      1,2,3,6,4,7     

缺页中断次数为      10    

 


 

解析:

FIFO:先进先出页面置换算法。

算法实现:总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面进行淘汰。

由上图可知,淘汰顺序为:1,2,3,6,4,7

缺页次数为:10次。

 

 


 

(2)采用LRU页面置换算法时:

淘汰页面的顺序为  1,2,6,4,7,3,2,1,4, 7                                      

缺页中断次数为     14     

 


 

 解析:

LRU页面置换算法:最近最久未使用LRU页面置换算法,是根据页面调入内存后的使用情况进行决策的。

算法的实现:选择最近最久未使用的页面予以淘汰。

由于LRU算法淘汰的是上次使用距离t时刻最远的页,故需记录这个距离。


 

5.一系统具有150个存储单元,在T0时刻系统按下表所示分配给3个进程。

    进程

最大需求

已分配

  P1

  P2

  P3

70

60

60

25

40

45

对下列请求应用银行家算法分别分析判定是否安全?(6分)

(1)第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元。试问,若系统接受该请求,处于安全状态吗?

 答:一系统具有150个存储单元,在T0时刻系统按下表所示分配给3个进程,分配第四个进程25个单元。

那么四个进程分配完毕后,剩下可分配存储单元数为:150-25-40-45-25=15个存储单元。

p1还需要分配存储单元数目:70-25=45

p2还需要分配存储单元数目:60-40=20

p3还需要分配存储单元数目:60-45=15

p4还需要分配存储单元数目:60-25=35

此时,系统只剩下存储单元15个,能满足的只有进程p3。

所以系统将剩下全部15个存储单元分配给进程p3,进程p3完成后可以回收45个存储单元。

此时系统剩余可分配存储单元为60个,可以满足进程p1,p2,p4任意一个。(所以结果不唯一)

假设我们选择进程p2,那么分配给进程p2存储单元20个,进程p2执行完成,回收存储单元40。

此时系统剩余可分配存储单元60+40=100个,进程p1和进程p4都可以满足。

假设我们选择进程p1,那么分配给进程p1存储单元45个,进程p2执行完成,回收存储单元25。

此时系统剩余可分配存储单元100+25=125

最后选择进程p4,分配给进程p4存储单元35个,回收存储单元25.

由上可知,当执行顺序为p3——>p2——>p1——>p4时,可以满足所有进程。

所以是安全状态。

(2)第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元。试问,若系统接受该请求,处于安全状态吗?

 答:一系统具有150个存储单元,在T0时刻系统按下表所示分配给3个进程,再分配第四个进程35个单元。

那么四个进程分配完毕后,剩下可分配存储单元数为:150-25-40-45-35=5个存储单元。

 

p1还需要分配存储单元数目:70-25=45

 

p2还需要分配存储单元数目:60-40=20

 

p3还需要分配存储单元数目:60-45=15

 

p4还需要分配存储单元数目:50-35=15

所剩下的存储单元5个不足以满足任何一个进程,因此找不到一个安全序列,所以为不安全状态。

 


 

最近复习操作系统准备期末,找的经典题目,自己写的题解。

文中有些内容为了保留原来整齐排版格式,使用了图片截图。

交流即分享,分享才能进步!

不足之处,还请各位前辈多多指教。