1、1习题复习课习题复习课2n第一部分第一部分 同步和互斥问题同步和互斥问题3n1.有三个进程，进程有三个进程，进程get从输入设备上不断读数据，从输入设备上不断读数据，并存入并存入buffer1;进程进程cut不断将不断将buffer1的内容剪切到的内容剪切到缓冲区缓冲区buffer2，进程，进程put则不断将则不断将buffer2的内容在的内容在打印机上输出。三个进程并发执行，协调工作。写出打印机上输出。三个进程并发执行，协调工作。写出该三个进程并发执行的同步模型。该三个进程并发执行的同步模型。getcutputbuffer1buffer24buffer1buffer2getcutputemp
2、ty1empty2full1full2n分析存在如下分析存在如下同步同步关系：关系：(1)(1)只有只有buffer1为空，为空，get才能工作，并使才能工作，并使buffer1为满。为满。(2)(2)要求要求buffer1为满，同时为满，同时buffer2为空，为空，cut才能工作，工才能工作，工作结果使作结果使buffer1为空，为空，buffer2为满。为满。(3)(3)只有只有buffer2为满，为满，put才能工作，并使才能工作，并使buffer2为空。为空。5n解答：解答：（1）设置信号量）设置信号量n设信号量设信号量empty1表示缓冲区表示缓冲区buffer1为空为空,初值为初
3、值为1n设信号量设信号量full1表示缓冲区表示缓冲区buffer1为满为满,初值为初值为0n设信号量设信号量empty2表示缓冲区表示缓冲区buffer2为空为空,初值为初值为1n设信号量设信号量full2表示缓冲区表示缓冲区buffer2为满为满,初值为初值为0buffer1buffer2getcutputempty1empty2full1full26（2）同步算法描述如下：）同步算法描述如下：cut( ) while(true) Wait(full1) Wait(empty2) cut操作操作 Signal(empty1) Signal(full2) get( ) while(true)
4、 Wait(empty1) get操作操作 Signal(full1) put( ) while(true) Wait(full2) put操作操作 Signal(empty2) buffer1buffer2getcutputempty1empty2full1full27semaphore empty1=1,full1=0,empty2=1,full2=0;get( ) while(true) Wait(empty1); get操作操作; Signal(full1); cut( ) while(true) Wait(full1); Wait(empty2); cut操作操作; Signal(e
5、mpty1); Signal(full2); put( ) while(true) Wait(full2); put操作操作; Signal(empty2); main() parbegin(get,cut,put);8n2.用用PV操作解决司机和售票员的问题。操作解决司机和售票员的问题。司机进程：司机进程： while (true) 启动车辆启动车辆 正常驾驶正常驾驶 到站停车到站停车 售票员进程：售票员进程：while (true) 关门关门 售票售票 开门开门 n分析存在如下同步关系：分析存在如下同步关系：(1)(1)售票员关门后，司机才能开车。售票员关门后，司机才能开车。(2)(2)司
6、机到站停车后，售票员才能开门。司机到站停车后，售票员才能开门。n设信号量设信号量close表示关门开车表示关门开车,初值为初值为0；n设信号量设信号量stop表示到站开门表示到站开门,初值为初值为09semaphore close=0,open=0;driver( ) while(true) Wait(close) 启动车辆启动车辆; ; 正常行驶正常行驶; ; 到站停车到站停车; ; Signal(stop) seller( ) while(true) 关门关门 Signal(close) 售票售票 Wait(stop) 开门开门 main() parbegin(driver,seller)
7、;10n3.有一个阅览室，共有有一个阅览室，共有100个座位，读者进入时必须个座位，读者进入时必须先在一张登记表上登记，该表为每一位列一表目，包先在一张登记表上登记，该表为每一位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息。括座号和读者姓名等，读者离开时要消掉登记的信息。 试用试用PV操作描述读者进程之间的同步关系。操作描述读者进程之间的同步关系。n分析：分析：读者填表进入阅览室，这时要考虑阅览室里是读者填表进入阅览室，这时要考虑阅览室里是否有座位；同时还要考虑登记表的互斥使用。否有座位；同时还要考虑登记表的互斥使用。n设设信号量信号量seats=100，mutex=1。前者用于
8、约束只能前者用于约束只能有有100个进程共享阅览室，后者用来约束登记表的互个进程共享阅览室，后者用来约束登记表的互斥使用。斥使用。11semaphore seats=100 reader( )while (true) Wait（seats）；）； 选书读书；选书读书； Signal（ seats ）；）； Wait（mutex）；）； 填写登记表；填写登记表；Signal（mutex）；）； Wait（mutex）；）；消掉登记；消掉登记；Signal（mutex）；）；12思考题思考题n某小型超级市场，可容纳某小型超级市场，可容纳50个人同时购物。入口处备个人同时购物。入口处备有篮子，每个购
9、物者可拿一只篮子入内购物。出口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。结帐，并归还篮子（出、入口禁止多人同时通过）。试用试用PV操作写出购物者的同步算法。操作写出购物者的同步算法。n第二部分第二部分单道程序和多道程序单道程序和多道程序132.2操作系统的发展过程操作系统的发展过程2.2.2单道批处理系统单道批处理系统(Simple Batch Processing System) （1955-1965，晶体管时代，晶体管时代，出现监控程序）出现监控程序） 编程语言：汇编语言编程语言：汇编语言 单道：内存中仅有一道作业在运行单道：内存中仅有一
10、道作业在运行 批处理：计算机系统对一批作业自动进行处批处理：计算机系统对一批作业自动进行处理理2.2操作系统的发展过程操作系统的发展过程2.2.2单道批处理系统单道批处理系统1处理过程处理过程 把一把一批批作业作业(用户程用户程序序+数据数据+作业说明书作业说明书)以以脱机脱机方式输入到方式输入到磁盘磁盘上，上，并在系统中配以并在系统中配以监督程监督程序序(Monitor，OS雏形雏形)将作业将作业逐个逐个送入送入内存内存并并运行运行。还 有 下 一个 作 业把 下 一 个 程序 的 源 程 序读 入 内 存检 查 源 程 序源 程 序 有错 吗 ？装 配 目 标程 序运 行 目 标程 序开
11、始停 止是否是否提 示 错 误2.2操作系统的发展过程操作系统的发展过程2.2.2单道批处理系统单道批处理系统2特征：单道性、顺序性、自动性特征：单道性、顺序性、自动性J优点：减少优点：减少CPU空闲时间，提高资源利用率和系空闲时间，提高资源利用率和系统吞吐量。统吞吐量。L缺点：缺点：人机交互性差，人机交互性差，CPU和和I/O设备忙闲不均设备忙闲不均(取决于作业的特性取决于作业的特性)。解决办法：多道程序设计技术解决办法：多道程序设计技术2.2操作系统的发展过程操作系统的发展过程2.2.3多道批处理系统多道批处理系统(Multiprogrammed Batch Processing Syst
12、em) （1965-1980，半导体、小规模半导体、小规模集成电路时代）集成电路时代） 1多道程序设计的基本概念多道程序设计的基本概念 在在内存中同时存放多个作业内存中同时存放多个作业，使之同时处于运行状态，使之同时处于运行状态(均均已开始运行但尚未结束已开始运行但尚未结束)共享系统资源。共享系统资源。n单单CPU系统中的多道程序运行的特征系统中的多道程序运行的特征宏观上并行：宏观上并行：并发程序都已开始执行，但都未结束并发程序都已开始执行，但都未结束微观上串行：微观上串行：并发程序轮流占有并发程序轮流占有CPU交替交替执行执行tAAt等待等待I/O的时间的时间（6个个t）（a）单道情况）单道
13、情况11078BBtAAt（b）两道情况）两道情况1107189tt（c）四道情况）四道情况1107189BBAACDCD2310单道、两道和四道情况单道、两道和四道情况1421/8t = 0.125道程序道程序/t2/9t = 0.222道程序道程序/tAI/OAI/OBI/O4/11t = 0.363道程序道程序/t下一下一步步A,B,C,D为程为程序，忽略外设；序，忽略外设；假定假定4个程序个程序都需都需运行运行2个个t时间，在时间，在期期间有间有6个个t时时间的间的I/O操作操作；吞吐率分别为：吞吐率分别为：1/8 = 0.125 2/9 = 0.222 4/11 = 0.363 4道
14、程序情况比道程序情况比单道提高了近单道提高了近 3 倍倍。显然不仅使。显然不仅使内存充分利用，内存充分利用，还带来处理机利还带来处理机利用率的提高，使用率的提高，使整个系统效率得整个系统效率得以提高。以提高。下一下一步步结束结束下一下一步步多道程序设计的基本概念多道程序设计的基本概念（a）单道情形：）单道情形：打印请求打印请求打印请求打印请求单道与单道与多道程序运行情况多道程序运行情况（b）多道情形：）多道情形：程序A OSI/O设备绘图仪请求绘图仪请求t1t2t3t4t5t6t7t8CPU打印机绘图仪程序B打印完成打印完成绘图完成绘图完成CPU空闲空闲t9t10仍有空闲仍有空闲A/B运行运行
15、? 用户程序用户程序监督程序监督程序I/O操作操作I/O中断中断请求请求 启动启动I/OI/O完成中断完成中断I/O中断请求中断请求启动启动I/Ot1I/O中断中断处理结束处理结束t2t3t4t5t6t7t8CPU CPU空闲空闲 空闲空闲多道程序设计的基本概念多道程序设计的基本概念例题例题1n若内存中有若内存中有3道程序道程序A、B、C，它们按，它们按A、B、C优先优先次序运行。各程序的计算轨迹为：次序运行。各程序的计算轨迹为：nA：计算：计算(20)、I/O(30)、计算、计算(10) n B：计算：计算(40)、I/O(20)、计算、计算(10)nC：计算：计算(10)、I/O(30)、
16、计算、计算(20)n如果三道程序都使用相同设备进行如果三道程序都使用相同设备进行I/O(即程序用串行即程序用串行方式使用设备，调度开销忽略不计方式使用设备，调度开销忽略不计)。试分别画出单。试分别画出单道和多道运行的时间关系图。两种情况下，道和多道运行的时间关系图。两种情况下，CPU的平的平均利用率各为多少均利用率各为多少?20单道单道21多道多道22例题例题2 理解单道和多道程序执行时的不同理解单道和多道程序执行时的不同例：例：A A、B B两个程序，程序两个程序，程序A A按顺序使用按顺序使用CPU 10sCPU 10s，设备，设备甲甲5s5s，CPU 5sCPU 5s，设备乙，设备乙10
17、s10s，CPU 10sCPU 10s，程序按顺，程序按顺序使用设备甲序使用设备甲10s10s，CPU 10sCPU 10s，设备乙，设备乙5s5s，CPU 5sCPU 5s，设备乙设备乙10s10s。问：在顺序环境下执行程序。问：在顺序环境下执行程序A A和和B B，CPUCPU利用率多少？利用率多少？ 在多道环境下呢？在多道环境下呢？答：答：A和和B顺序执行时，顺序执行时，A执行完毕执行完毕B才开始，总共耗才开始，总共耗时时80s，占用，占用CPU40s，故，故CPU利用率为利用率为40/80=50%。多道时，两程序共耗时多道时，两程序共耗时45s，故，故CPU利用率为利用率为40/45=
18、88.89%CPU: A: B:CPU甲甲乙乙CPU等待等待乙乙CPU甲甲CPU等待等待乙乙CPUABAB空闲空闲A10s20s30s40s45s24n第三部分第三部分 处理机调度处理机调度253. 低级调度的功能和类型低级调度的功能和类型1.低级调度的主要功能低级调度的主要功能调度程序两项任务：调度和分派。调度程序两项任务：调度和分派。调度实现调度策略，确定就绪进程调度实现调度策略，确定就绪进程/线程竞争使用处线程竞争使用处理器的次序的裁决原则，即进程理器的次序的裁决原则，即进程/线程何时应放弃线程何时应放弃CPU和选择哪个来执行；和选择哪个来执行；分派实现调度机制，确定如何时分复用分派实现
19、调度机制，确定如何时分复用CPU，处理，处理上下文交换细节，完成进程上下文交换细节，完成进程/线程和线程和CPU的绑定和放的绑定和放弃的实际工作。弃的实际工作。26调度机制逻辑功能程序模块组成调度机制逻辑功能程序模块组成n队列管理程序：管理等待调度的进程队列管理程序：管理等待调度的进程/线程线程（排队）。（排队）。n上下文切换程序时：当发生进程上下文切换程序时：当发生进程/线程切换线程切换时，用来保存旧现场，调入新现场。时，用来保存旧现场，调入新现场。n分派程序：分派分派程序：分派CPU给选中的进程给选中的进程/线程。线程。273.1.低级调度的基本类型低级调度的基本类型n第一类称剥夺式：第一
20、类称剥夺式： 两种处理器剥夺原则两种处理器剥夺原则 一是高优先级进程一是高优先级进程/线程可剥夺低优先级进程线程可剥夺低优先级进程/线程，线程， 二是当运行进程二是当运行进程/线程时间片用完后被剥夺。线程时间片用完后被剥夺。n第二类称非剥夺式：第二类称非剥夺式：一旦某个进程一旦某个进程/线程开始运行后便不再让出处线程开始运行后便不再让出处理器。理器。n比较比较剥夺式策略的开销大，但可以避免进程剥夺式策略的开销大，但可以避免进程/线程线程长时间的独占处理器；长时间的独占处理器；很多操作系统使用两种测略的组合，内核关键很多操作系统使用两种测略的组合，内核关键程序是非剥夺式的，用户进程是剥夺式的。程
21、序是非剥夺式的，用户进程是剥夺式的。281、先到先服务调度（、先到先服务调度（first-come,first-served,FCFS）n先请求先请求CPU的进程被首先分配到的进程被首先分配到CPU，可用，可用FIFO队列来队列来实现实现n平均周转时间通常相当长，与作业的提交和调度顺序有关平均周转时间通常相当长，与作业的提交和调度顺序有关n非抢占调度非抢占调度n例例 进程进程 区间时间区间时间 P1 24 P2 3 P3 3P1P1P2P2P3P30 24 27 300 24 27 30平均周转时间平均周转时间(24+27+30)/3=27(24+27+30)/3=27P2P2P3P3P1P1
22、0 3 6 300 3 6 30平均周转时间平均周转时间(3+6+30)/3=13(3+6+30)/3=133.2 作业调度和低级调度算法作业调度和低级调度算法292. 最短作业优先算法最短作业优先算法nSJF算法以进入系统的作业所要求的算法以进入系统的作业所要求的CPU时间为标时间为标准，总选取估计计算时间最短的作业投入运行。准，总选取估计计算时间最短的作业投入运行。n算法易于实现，效率不高，主要弱点是忽视了作业算法易于实现，效率不高，主要弱点是忽视了作业等待时间。等待时间。n会出现饥饿现象。会出现饥饿现象。nSJF的平均作业周转时间比的平均作业周转时间比FCFS要小，故它的调度要小，故它的
23、调度性能比性能比FCFS好。好。n实现实现SJF调度算法需要知道作业所需运行时间，否调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时则调度就没有依据，要精确知道一个作业的运行时间是办不到的。间是办不到的。303.最短剩余时间优先算法最短剩余时间优先算法nSRTF把把SJF算法改为抢占式的。一个新作业进入就算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的绪状态，如果新作业需要的CPU时间比当前正在执时间比当前正在执行的作业剩余下来还需的行的作业剩余下来还需的CPU时间短，时间短，SRTF强行强行赶走当前正在执行作业。称最短剩余时间优先算法赶走当前正在执行
24、作业。称最短剩余时间优先算法n此算法不但适用于此算法不但适用于JOB调度，同样也适用于进程调调度，同样也适用于进程调度。度。31SJF调度例：调度例：进程进程 区间时间区间时间 P1 6 P2 8 P3 7 P4 3SRTF调度例：调度例：进程进程 到达时间到达时间 区间时间区间时间 P1 0 8 P2 1 4 P3 2 9 P4 3 5P4P1P3P2P1P2P4P1P30 3 9 16 24平均周转时间：平均周转时间： (9+24+16+3)/4=130 1 5 10 17 26平均周转时间：平均周转时间： (17-0)+(5-1)+(26-2)+(10-3)/4=13321 1、设作业设
25、作业J1J1和和J2J2的运行时间的运行时间t1=t2t1=t2， 当采用短作业优先时，调度顺序为当采用短作业优先时，调度顺序为J1J1、J2J2，平均周转时间为，平均周转时间为(t1+(t1+t2)/2=(t1+(t1+t2)/2=(2t1+t2)/2(2t1+t2)/2。 不采用短作业优先时，调度顺序为不采用短作业优先时，调度顺序为J2J2、J1J1，平均周转时间为，平均周转时间为(t2+(t2+t1)/2(t2+(t2+t1)/2(t1+2t2)/2(t1+2t2)/2。显然，得证。显然，得证。2 2、假设当假设当n=kn=k时成立，则当时成立，则当 n=k+1n=k+1时，时， J1J
26、1，J2J2， ，J Jk k ，J Jk+1k+1，它，它们的运行时间分别为：们的运行时间分别为：t1t1，t2t2， t tk k ， t tk+1k+1。(t(ti i =0)/n=0。得证。得证。证明：采用证明：采用SJFSJF调度算法可以使平均周转时间最少。调度算法可以使平均周转时间最少。33n1.系统系统 有有5个进程个进程: A, B, C, D ,E。它们的到达时间以及估。它们的到达时间以及估计运行的时间如下图所示：计运行的时间如下图所示：n请计算使用下述调度算法时，进程的周转时间和进程流的请计算使用下述调度算法时，进程的周转时间和进程流的平均周转时间。平均周转时间。n(1)F
27、CFS (2) SPN (3) HRRN (4) RR(q=1)进程进程到达时间到达时间(ms)估计运行时间估计运行时间(ms)A03B26C44D65E8234(1)FCFS算法：按照先来先服务原则，调度顺序为算法：按照先来先服务原则，调度顺序为A,B,C,D,E，详细情况如下图所示，详细情况如下图所示因此，因此，A的周转时间为的周转时间为3ms；B的周转时间为的周转时间为9-2=7ms；C的周转时间为的周转时间为13-4=9ms； D的周转时间为的周转时间为18-6=12ms； E的周转时间为的周转时间为20-8=12ms； 平均周转时间为（平均周转时间为（3+7+9+12+12）/5=8
28、.6ms35(2)SPN算法：按照短进程原则，调度顺序为算法：按照短进程原则，调度顺序为A,B,E,C,D，详细情况如下图所示详细情况如下图所示因此，因此，A的周转时间为的周转时间为3ms；B的周转时间为的周转时间为9-2=7ms；C的周转时间为的周转时间为15-4=11ms； D的周转时间为的周转时间为20-6=14ms； E的周转时间为的周转时间为11-8=3ms； 平均周转时间为（平均周转时间为（3+7+11+14+3）/5=7.6ms051015201234536(3)HRRN算法：算法：n初始时刻只有初始时刻只有A，因此先调度，因此先调度A执行。执行。 A的周转时间为的周转时间为3m
29、s。nA执行完，只有执行完，只有B就绪，因此再调度就绪，因此再调度B执行。执行。 B的周转的周转时间为时间为9-2=7ms；nB执行后，执行后，C,D,E均就绪，按照最高响应比调度原则，均就绪，按照最高响应比调度原则， Rc=(9+4-4)/4=2.25， Rd=(9+5-6)/5=1.6， Re=(9+2-8)/2=1.5 因此再调度因此再调度C执行，执行，C的周转时间为的周转时间为13-4=9ms；nC执行后，执行后， Rd=(13+5-6)/5=2.4, Re=(13+2-8)/2=3.5 ,因此因此调度调度E执行，执行，E的周转时间为的周转时间为15-8=7ms；n最后调度最后调度D，
30、D的周转时间为的周转时间为20-6=14ms37n即，调度过程如图所示即，调度过程如图所示1234505101520n平均周转时间为（平均周转时间为（3+7+9+7+14）/5=8ms38(4)RR (q=1)算法：按照时间片轮转法原则，调度情况算法：按照时间片轮转法原则，调度情况如下图所示如下图所示因此，因此，A的周转时间为的周转时间为4ms；B的周转时间为的周转时间为18-2=16ms；C的周转时间为的周转时间为17-4=13ms； D的周转时间为的周转时间为20-6=14ms； E的周转时间为的周转时间为15-8=7ms； 平均周转时间为（平均周转时间为（4+16+13+14+7）/5=
31、10.8ms39n点评：点评：各种调度算法下，进程的调度顺序及调度执行各种调度算法下，进程的调度顺序及调度执行的详细过程需要以图或文字的形式进行说明。的详细过程需要以图或文字的形式进行说明。仅给出最后的结果是不完整的。仅给出最后的结果是不完整的。40n第四部分第四部分 死锁死锁41n考虑有考虑有5个进程共享个进程共享4类资源，它们的占有量和尚需量类资源，它们的占有量和尚需量如下：如下：进程已分配尚需可用P00 0 2 30 0 1 21 6 2 3 P11 0 0 02 0 0 0P20 3 3 00 1 4 0P31 0 1 00 8 1 3P40 0 1 43 0 0 0n(1) 当前状态
32、安全吗当前状态安全吗?n(2) 如果进程如果进程2提出资源请求提出资源请求 (0,1,2,0), 按照银行家算法，能否满按照银行家算法，能否满足要求？足要求？42(1)利用安全性算法对上述状态进行分析，如下表所示，利用安全性算法对上述状态进行分析，如下表所示，WorkA B C DNeed A B C DAllocation A B C DFinishP0P2P3P1P41 6 2 31 6 4 61 9 7 62 9 8 63 9 8 6 0 0 1 2 0 1 4 00 8 1 32 0 0 03 0 0 00 0 2 30 3 3 01 0 1 01 0 0 00 0 1 4truetr
33、uetruetruetrue因为存在安全序列因为存在安全序列 P0P0、P2P2、P3P3、P1P1、P4P4，所以系统是安全的。所以系统是安全的。43n(2)P2发出请求发出请求(0,1,2,0)后，系统按银行家算法进行检查：后，系统按银行家算法进行检查：Request(0,1,2,0)=Need2(0,1,4,0);Request(0,1,2,0)=Available(1,6,2,3);试探为试探为P2分配资源，并修改数据：分配资源，并修改数据： Available=(1,5,0,3); Allocation2=(0,4,5,0) Need2=(0,0,2,0)。进行安全性检查，发现进行安
34、全性检查，发现Available (1,5,0,3)10,超过作业的地址空超过作业的地址空间长度，系统发生地址越界中断，程序运行终止。间长度，系统发生地址越界中断，程序运行终止。练习题练习题。练习题练习题虚地址虚地址0AFEH0000 1010 1111 1110P1 W010 1111 1110PA00100 1010 1111 1110 4AFEH虚地址虚地址1ADDH0001 1010 1101 1101P3 W010 1101 1101PA0010 1010 1101 1101 2ADDHn若在一分页存储管理若在一分页存储管理系统中，某作业的页系统中，某作业的页表如右所示。已知页表如右
35、所示。已知页面大小为面大小为1024字节，字节，试将逻辑地址试将逻辑地址0A5CH，07EFH，3000，5012转化为相应的物理地转化为相应的物理地址。址。页号页号块号块号0 02 21 13 32 21 13 36 6n对于逻辑地址对于逻辑地址0A5CHn0A5CH=0000 1010 0101 1100 页号页号2，对应物理块，对应物理块1n物理地址为物理地址为0000 0110 0101 1100 即即065CH n对于逻辑地址对于逻辑地址07EFHn0A5CH=0000 0111 1110 1111 页号页号1，对应物理块，对应物理块3n物理地址为物理地址为0000 1111 111
36、0 1111 即即0FEFH n对于逻辑地址对于逻辑地址3000nPint(3000/1024)2nW3000 mod 1024952 n查页表第查页表第2页在第页在第1块，所以物理地址为块，所以物理地址为1976。n对于逻辑地址对于逻辑地址5012 nPint(5012/1024)4nW5012 mod 1024916n因页号超过页表长度，该逻辑地址非法。因页号超过页表长度，该逻辑地址非法。 习题解答习题解答虚地址虚地址 3412P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=19796虚地址虚地址3412的内存地址的内存地址是：是：19796六
37、六. . 磁盘的调度算法磁盘的调度算法图 5-23 FCFS调度算法1. 1. 先来先服务先来先服务FCFS(First-Come, First Served)FCFS(First-Come, First Served)n仅用于请仅用于请求磁盘求磁盘I/OI/O的进的进程数目较程数目较少的场合。少的场合。图 5-24 SSTF调度算法 2. 2. 最短寻道时间优先最短寻道时间优先SSTF(Shortest Seek Time First)SSTF(Shortest Seek Time First)3. 3. 扫描扫描(SCAN)(SCAN)算法算法SCAN调度算法调度算法100道开始，增加方向
38、道开始，增加方向被访问下一个磁道被访问下一个磁道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.84. 4. 循环扫描循环扫描(CSCAN)(CSCAN)算法算法CSCAN调度算法调度算法100道开始，增加方向道开始，增加方向被访问的下一个磁道被访问的下一个磁道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5n若某磁盘共有若某磁盘共有200个柱面，其编号为个柱面，其编号为0199，假，假设已完成设已完成96号柱面的访问请求，还有若干个请求号
39、柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别，分别用用先来先服务调度算法、最短寻道时间调度算法、先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加电梯调度算法和单向扫描调度算法（向序号增加的方向移动）的方向移动）来确定实际服务的次序，并计算上来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。述两种算法下移动臂需移动的距离。(1)先来先服务调度算法：先来先服务调度算法： n实际服务的次序：实际服务的次序： 961755215
40、73615910610872 n移动臂需移动的距离为：移动臂需移动的距离为： n(175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642 移动臂需移动移动臂需移动642柱面的距离。柱面的距离。 n(2)最短寻找时间优先调度算法：最短寻找时间优先调度算法： n实际服务的次序：实际服务的次序：96106108725236157159175 n移动臂需移动的距离为：移动臂需移动的距离为： n(106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159
41、-l57)+(175-159)=223 移动臂需移动移动臂需移动223个柱面的距离。个柱面的距离。 n(1)电梯调度算法：电梯调度算法： n实际服务的次序：实际服务的次序：96106108157159175725236 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72-52)+(52-36)=218 移动臂需移动移动臂需移动218个柱面的距离。个柱面的距离。 n(2)单向扫描调度算法：单向扫描调度算法： n实际服务的次序：实际服务的次序：96106108157159175365272 n(106-96)+(108-l06
42、)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254 除了移动臂由里向外返回所用的时间外，还需移除了移动臂由里向外返回所用的时间外，还需移动动254个柱面的距离。个柱面的距离。 七、七、最佳置换算法和先进先出算法最佳置换算法和先进先出算法引用率70770170122010323104430230321013201770201页框230420423023012712701最佳置换算法和先进先出算法最佳置换算法和先进先出算法FIFO123412512345页 0123412555344页 112341222533页 2123411
43、1255缺 页xxxxxxxxX如果在内存中分配如果在内存中分配4 4个页面，则缺页情况如下：个页面，则缺页情况如下：1212次访问中有缺页次访问中有缺页1010次；次；FIFO123412512345页 0123444512345页 112333451234页 21222345123页 3111234512缺 页xxxxxxxxxxBeladyBelady现象的现象的原因原因：FIFOFIFO算法的算法的置换特征置换特征与进与进程程访问内存的动态特征访问内存的动态特征是是矛盾矛盾的，即被置换的页的，即被置换的页面并不是进程不会访问的。面并不是进程不会访问的。习题习题习题习题习题习题习题习题n
44、请求分页存储管理方式中，假定系统为某进程分请求分页存储管理方式中，假定系统为某进程分配了配了4个页框，页面的引用顺序为：个页框，页面的引用顺序为：6、1、2、0、3、0、4、2、3、0、3、2、6、0，采用，采用FIFO置置换算法产生多少次页面置换？缺页率是多少？换算法产生多少次页面置换？缺页率是多少？(2)(2)页面置换次数为页面置换次数为3 3次次 (3)(3)缺页率为：缺页率为：7/14=50% 7/14=50% n请求分页存储管理方式中，假设分配给某进程的请求分页存储管理方式中，假设分配给某进程的页框数为页框数为3，若程序的页面引用顺序为：，若程序的页面引用顺序为：0、2、3、4、1、2、5、0、2、3、2、5，采用最佳置换算，采用最佳置换算法产生多少次页面置换？缺页率是多少？法产生多少次页面置换？缺页率是多少？(2)(2)页面置换次数为页面置换次数为4 4次次 (3)(3)缺页率为：缺页率为：7/12=58% 7/12=58%
