Category: Introduction of OS

调度算法

调度算法就是一种资源分配算法。
有的算法适用于作业调度,有的算法适用于进程调度,有的两者都适应。
1) 先来先服务(FCFS/first come first serve)
2) 短作业优先(SPF/Shortest Process First)
3) 时间片轮转算法(Round Robin)
4) 优先级算法(PS/priority Scheduling)
5) 高响应比优先调度算法(HRNN/Highest Response Ratio Next)
6) 多级队列算法
7) 多级反馈队列算法(FB/Multilevel Feedback-Queue scheduling)

【例2】在一个单道的程序设计系统中,有3个作业J1、J2、J3,它们到达输入井的时间分别为8:50、9:00、9:30,它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在10:00按响应比高者优先算法对它们进行调度,请回答:(1)作业被选中执行的次序是什么? (2)每个作业被选中时的响应比分别是多少?
分析 
响应比=作业周转时间/作业运行时间 =1+作业等待时间/作业运行时间
系统在10:00,计算作业的响应比:
以J1为例,它的作业计算时间是1.5小时,即90分钟;J1从8:50到达输入井,在10:00时刻,J1的等待时间为70分钟,因此作业J1的响应比为:1+70分钟/90分钟=1.77
同理,J2:1+60分钟/24分钟=3.5    J3:1+30分钟/60分钟=1.5
因此按照响应比高者优先算法,优先调度J2。
在10:24,J2完成。这时计算J1、J3的响应比:
J1:1+(70+24)分钟/90分钟=2.04    J3:1+(30+24)分钟/60分钟=1.9
按照响应比高者优先算法,优先调度J1。
在11:54,J1完成,系统调度J3,J3的响应比为1+(30+24+90)分钟/60分钟=3.4 因此,作业被选中执行的次序是J2、J1、J3。
三个作业被选中时的响应比分别是:J1,2.04;J2,3.5;J3,3.4。

:(1)作业被选中执行的次序是J2、J1、J3。
(2)三个作业被选中时的响应比分别是:J1,1.04;J2,2.5;J3,2.4。

转载

32/64位系统采用多级页表的判断

启用了物理地址扩展的32 位系统使用了三级页表。Linux的页全局目录对应80×86 的页目录指针表(PDPT),取消了页上级目录,页中间目录对应80×86的页目录,Linux的页表对应80×86的页表。

最后,64位系统使用三级还是四级分页取决于硬件对线性地址的位的划分。

扫描算法(SCAN)电梯调度

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

假定某磁盘有200个柱面 0-199 如果访问53号柱面的请求服务后,当前正在访问100号柱面。这对又有若干请求者要使用磁盘。假定请求者依次要访问的柱面号为84-147-90-155 若采用电梯调度算法,则移动臂共移动了______个柱面距离。

第一点 移动方向是53—>100 移动臂是由外向里(即向柱面号增大的内圈方向)

所以解法思路是 100-147-155-90-84   47+8+65+6=126

 

三级索引的问题

对于一个具有三级索引表的文件,存取一个记录通常要访问三次磁盘。

设有一个包含1000个记录的索引文件,每个记录正好占用一个物理块。一个物理块可以存放10个索引表目。建立索引时,一个物理块应有一个索引表目,试问索引及其文件本身应占()个物理块?

还有就是问 读文件至少应该有___级索引(假设一级索引占用一个物理块)

共1000个记录,即有1000个索引表目,索引级数:lg1000=3;一个物理块可以放10个索引表目,三级索引需1000/10=100个物理块;二级索引:100/10=10;一级索引10/10=1。所以索引及文件共需1000+100+10+1=1111物理快。

索引级数 = lg1000 = 3
第一级需要物理块:1
第二级需要物理块:10
第三级需要物理块:100
文件本身:1000
共:1111个物理块

有关磁道和处理作业速度的问题

假设有4个记录ABCD 顺序放在磁盘的某磁道上,该磁道划分为4块,每块存放一个记录。现在要顺序处理这些记录,如果磁盘的转速时20ms转一周,处理程序每读完一个记录后需要5ms的时间进行处理。

  1. 处理完这4个记录需要多少时间?
  2. 如果按照A-C-B-D的顺序存放 处理完这4个记录又需要多少时间?

 

思路: 明确处理完一个作业的时间应该是20/4+5ms 读取时间+处理时间,另外就是磁盘是一直在转动的,就是说当A读完并处理完的时候,磁盘已经转到C点了,B根本没有来得及读取,所以要再绕一圈回来。

完整思路为

处理A(5+5)+绕到B点(5+5+5 CDA的读取时间 其实就是剩下的3/4转完需要的时间)+B点的处理时间(10)+到绕C(5+5+5)+处理C+绕道D点+处理D点

10+15+10+15+10+15+10=85ms

A-C-B-D 处理A(10)+处理C(10,因为磁盘正好转到C点)+B点(15)+D点(10)

B点的15= C处理完毕正好20ms用到 磁盘转了一周,B的时间就是 磁盘越过A的5ms+读取B的5ms+处理B的5ms=15ms