操作系统原理算法me

1、2021-10-21进程同步互斥1信号量机制（ semaphore ） 1965年，由荷兰学者dijkstra提出（p、v分别是荷兰语的test (proberen) 和increment (verhogen) ） 一种卓有成效的进程同步机制 最初提出的是二元信号量（互斥） 推广到一般信号量（多值）（同步） p、v操作是原语2021-10-21进程同步互斥2整型信号量 定义一个整数s，仅能通过两个原子操作来访问： wait(s): while s=0 then do no-op s := s 1; signal(s): s := s + 1; 很明显，不满足让权等待。2021-10-21进程同

2、步互斥3记录型信号量是一个数据结构定义如下： struct semaphore int value; pointer_pcb queue; 信号量说明： semaphore s;2021-10-21进程同步互斥4wait（p操作）wait(s) s.value = s.value -1 ; if (s.value 0) block(s.l);/ 该进程状态置为等待状态/ 将pcb插入相应的等待队列s.queue; 2021-10-21进程同步互斥5signal（v操作）signal(s) s.value = s.value +1; if (s.value 0表示有s个资源可用s=0表示无资源可

3、用s0则| s |表示s等待队列中的进程个数p(s)：表示申请一个资源 v(s)：表示释放一个资源。信号量的初值应该大于等于02021-10-21进程同步互斥102) p.v操作必须成对出现，有一个p操作就一定有一个v操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果p(s1)和p(s2)两个操作在一起，那么p操作的顺序至关重要。一个同步p操作与一个互斥p操作在一起时同步p操作在互斥p操作前而两个v操作无关紧要2021-10-21进程同步互斥11进程互斥用信号量实现临界区互斥:设置一信号量，信号量初值唯一，进入临界区以前对信号量执行p操作，退出临界区后对信号量执行v

4、操作.2021-10-21进程同步互斥12进程同步 同步问题可分为两类： 保证一组合作进程按确定的次序执行 保证共享缓冲区的合作进程的同步。 2021-10-21进程同步互斥13合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。如图2021-10-21进程同步互斥14例如图，试用信号量实现这三个进程的同步。 设有两个信号量sb、sc，初值均为pa： pb： pc： p(sb); p(sc) v(sb); v(sc);2021-10-21进程同步互斥15【思考题1】

5、如图，试用信号量实现这三个进程的同步。2021-10-21进程同步互斥16解设有两个信号量s1、s2，初值均为p1： p2： p3： p(s1) v(s1); v(s2); p(s2) 2021-10-21进程同步互斥17【思考题2】如图，试用信号量实现这6个进程的同步2021-10-21进程同步互斥18解设有5个信号量s2、s3、s4、s5、s6，初值均为p1： p2： p3： p(s2); p(s3) v(s2); v(s3)；v(s4); v(s6); v(s5)p4： p5： p6： p(s4); p(s5); p(s6); p(s5); p(s6); v(s5)； v(s6); 20

6、21-10-21进程同步互斥19共享缓冲区的进程的同步 设某计算进程cp和打印进程iop共用一个单缓冲区，cp进程负责不断地计算数据并送入缓冲区t中，iop进程负责不断地从缓冲区t中取出数据去打印。2021-10-21进程同步互斥20分析通过分析可知，cp、iop必须遵守以下同步规则： 当cp进程把计算结果送入缓冲区时，iop进程才 能从缓冲区中取出结果去打印; 当iop进程把缓冲区中的数据取出打印后，cp进程才能把下一个计算结果送入缓冲区2021-10-21进程同步互斥21解 为此设有两个信号量sa=0，sb=1，sa表示缓冲区中有无数据，sb表示缓冲区中有无空位置。 两个进程的同步可以描述

7、如下：2021-10-21进程同步互斥22【思考题】1.用p.v操作解决下图之同步问题提示：分别考虑对缓冲区s和t的同步，再合并考虑getcopyputst2021-10-21进程同步互斥23解 设置四个信号量sin=1，sout=0，tin=1，tout=0；get： while（1） p(sin）; 将数放入s; v(sout); copy： while（1） p(sout）; p(tin）; 将数从s放入t; v(tout); v(sin); put： while（1） p(tout）; 将数从t取走; v(tin); 2021-10-21进程同步互斥24【思考题】 桌上有一空盘，最多允

8、许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用p、v操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。2021-10-21进程同步互斥25解设置三个信号量s,so,sa ，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。2021-10-21进程同步互斥26father() while(1) p(s); 将水果放入盘中将水果放入盘中; if(是桔子是桔子)v(so); else v(sa); son() while(1) p(so) 取桔

9、子取桔子 v(s); 吃桔子吃桔子; daughter() while(1) p(sa) 取苹果取苹果 v(s); 吃苹果吃苹果; 2021-10-21进程同步互斥274 经典的进程同步问题 4.1 生产者/消费者问题 4.2 读者/写者问题 4.3 哲学家进餐问题 2021-10-21进程同步互斥284.1 生产者/消费者问题 生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。 当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。2021-1

10、0-21进程同步互斥29问题描述通过一个有界缓冲区可以把一群生产者p1,p2,pm，和一群消费者q1,q2, qn联系起来。如图 只要缓冲区未满，生产者就可以把产品送入缓冲区; 只要缓冲区未空，消费者就可以从缓冲区中取走物品。2021-10-21进程同步互斥30图.pq放 消 息取 消 息nn个 缓 冲 区(buffer)ij2021-10-21进程同步互斥31问题分析 为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用s1表示，初值为有界缓冲区的大小n，另一个说明已用缓冲区的数目，用s2表示，初值为。 由于在此问题中有m个生产者和n个消费者，它们在执行生产活动和消费活动

11、中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。2021-10-21进程同步互斥32问题的解q： j = 0; while (1) p(s2); p(mutex); 从bufferj取产品; j = (j+1) % n; v(mutex); v(s1); 消费产品; ;p：i = 0;while (1) 生产产品; p(s1); p(mutex); 往buffer i放产品; i = (i+1) % n; v(mutex); v(s2); ;2021-10-21进程同步互斥33采用and信号量集解决生产者-消费者问题

12、q： j = 0; while (1) swait(s2, mutex); 从bufferj取产品; j = (j+1) % n; ssignal(s1, mutex); 消费产品; ;p：i = 0;while (1) 生产产品; swait(s1, mutex); 往buffer i放产品; i = (i+1) % n; ssignal(s2, mutex); ;2021-10-21进程同步互斥34【思考题】有一个仓库，可以存放a和b两种产品，但要求：（1） 每次只能存入一种产品（a或b）（2） na产品数量b产品数量m。其中，n和m是正整数。试用p、v操作描述产品a与b的入库过程。提示：

13、设两个信号量sa、sbsa表示允许a产品比b产品多入库的数量sb表示允许b产品比a产品多入库的数量2021-10-21进程同步互斥35解设两个信号量sa、sb，初值分别为m-1，n-1sa表示允许a产品比b产品多入库的数量sb表示允许b产品比a产品多入库的数量设互斥信号量mutex，初值为1。2021-10-21进程同步互斥36 b产品入库进程： j = 0; while (1) p(sb); p(mutex); b产品入库 v(mutex); v(sa); 消费产品; ;a产品入库进程：i = 0;while (1) 生产产品; p(sa); p(mutex); a产品入库 v(mutex)

14、; v(sb); ;2021-10-21进程同步互斥374.2 读者/写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作2021-10-21进程同步互斥38第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待2021-10-21进程同步互斥39第一类读者写者问题的解法 设有两个信号量w=1，mutex=1 另设一个全局变量readcount =0

15、 w用于读者和写者、写者和写者之间的互斥 readcount表示正在读的读者数目 mutex用于对readcount 这个临界资源的互斥访问2021-10-21进程同步互斥40读者： while (1) p(mutex); readcount +; if (readcount=1) p (w); v(mutex); 读 p(mutex); readcount -; if (readcount=0) v(w); v(mutex); ;写者： while (1) p(w); 写 v(w); ;2021-10-21进程同步互斥41第一类读者写者问题的解法（一般信号量集）写者：while(1) swa

16、it(wmutex,1,1; rcount,r,0); 写； ssignal(wmutex,1);读者：while(1) swait(rcount,1,1; wmutex,1,0); 读； ssignal(rcount,1);n增加一个限制条件：同时读的“读者”最多r个uwmutex表示“允许写”，初值是1urcount表示“允许读者数目”，初值为r2021-10-21进程同步互斥42【思考题】写优先 修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。 提示，增加一个信号量，用于在写者到达后封锁后续的读者2021-10-21进程同步互斥4

17、3解 增加一个信号量s，初值为1读者： while (1) p(s); p(mutex); readcount +; if (readcount=1) p (w); v(mutex); v(s); 读 p(mutex); readcount - -; if (readcount=0) v(w); v(mutex); ;写者： while (1) p(s); p(w); 写 v(w); v(s); ;2021-10-21进程同步互斥444.3 哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉

18、 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子2021-10-21进程同步互斥45设fork5为5 个信号量，初值为均1philosopheri：while (1) 思考； p(forki); p(fork(i+1) % 5)； 进食； v(forki); v(fork(i+1) % 5)；解2021-10-21进程同步互斥46以上解法会出现死锁为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 分析202

19、1-10-21进程同步互斥47采用and信号量集解决哲学家就餐问题设fork5为5 个信号量，初值为均1philosopheri：while (1) 思考； swait( forki, fork(i+1) % 5 )； 进食； ssignal( forki, fork(i+1) % 5 )；2021-10-21进程调度483.2 调度算法 先来先服务算法（fcfs：first come first serve）有利于长作业，不利于短作业 最短作业优先算法（sjf：shortest job first）-提高了系统吞吐量对长作业不利未考虑作业的紧迫程度作业时间的估计时间不准2021-10-21进

20、程调度49高优先权调度算法 照顾紧迫作业，常用于批处理 静态优先权依据进程类型：系统进程高于一般用户进程依据对资源的要求：要求少的高于多的依据用户要求：紧迫程度和付费情况 动态优先权创建进程时赋予的优先权，遂进程的推进或随其等待时间的增加而改变，可防止某些进程无限期的等待2021-10-21进程调度50 最高响应比优先算法（hrn：highest response ratio next） 响应比r = 作业周转时间 / 作业处理时间 =（作业处理时间+作业等待时间）/ 作业处理时间 = 1 +（作业等待时间 / 作业处理时间）2021-10-21进程调度51调度算法应用例子1 假设在单道批处理

21、环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间2021-10-21进程调度522021-10-21进程调度53先来先服务调度算法计算结果作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间job18：001208：0010：001201job28：505010：0010：501202.4job39：001010：5011：0012012job49：502011：0011：20904.5作作

22、业业平平均均周周转转时时间间 t = 112.5作作业业带带权权平平均均周周转转时时间间 w = 4.97545019.92021-10-21进程调度54最短作业优先作业算法计算结果作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间job18：001208：0010：001201job28：505010：3011：201503job39：001010：0010：10707job49：502010：1010：30402作作业业平平均均周周转转时时间间 t = 95作作业业带带权权平平均均周周转转时时间间

23、 w = 3.25380132021-10-21进程调度55最高响应比优先作业算法计算结果2021-10-21进程调度56多队列反馈调度算法 将就绪队列分为n级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越长，级别越小，时间片越短； 当进程第一次就绪时，进入第一级队列 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃cpu时，进入下一级队列； 等待进程被唤醒时，进入原来的就绪队列；2021-10-21进程调度57就绪队列1就绪队列2就绪队列3就绪队列4至cpu至cpu至cpu至cpu2021-10-21进程调度583.6.3 利用银行家算法避免死

24、锁最有代表性的避免死锁算法，由dijkstra提出。1、银行家算法中的数据结构 可利用资源向量available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。 如： abc5232021-10-21进程调度59 最大需求矩阵max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。abcp1562p2331p3425p43322021-10-21进程调度60 分配矩阵allocation 。n*m矩阵，表示每个进程分配的资源数。abcp1212p2121p3222p41322021-10-21进程调度61 需求矩阵need 。n*m矩阵，表示每个进程还需要各类资源数。

25、abcp1352p2211p3223p42322021-10-21进程调度62例设系统有五个进程和三类资源，每类资源分别有10、5、7。在t0时刻资源分配情况如图2021-10-21进程调度63银行家算法描述当进程pi提出资源申请时，系统执行下列步骤：（1）若requestineedi,转（2）； 否则错误返回（2）若requestiavailable, 转（3）；否则进程等待2021-10-21进程调度64（3）假设系统分配了资源，则有：available:=available-requesti;allocationi:=allocationi+requesti;needi:=needi-r

26、equesti（4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待2021-10-21进程调度65安全性算法为进行安全性检查，定义数据结构：work:array0.m-1 of integer;finish:array0.n-1 of boolean;m代表资源的数量，n代表进程的数量2021-10-21进程调度66安全性算法步骤(1) work:=available; finish:=false;(2) 寻找满足下列条件的i： a). finishi=false; b). neediwork;如果不存在，则转(4)2021-10-21进程调度

27、67(3) work:=work+allocationi; finishi:=true; 转(2)(4) 若对所有i,finishi=true,则系统处于安全状态，否则处于不安全状态2021-10-21进程调度68t0时刻的安全性检查 t0时刻可以找到一个安全序列p1,p3,p4,p2,p0. 系统是安全的。2021-10-21进程调度69例1：t0时刻p1请求资源 p1发出请求request(1,0,2)，执行银行家算法2021-10-21进程调度70执行安全性算法 可以找到一个安全序列p1,p3,p4,p0,p2. 系统是安全的，可以将p1的请求分配给它。2021-10-21进程调度71p

28、1请求资源 p1发出请求request(1,0,2), 执行银行家算法 条件满足，找到安全序列p1,p3,p4,p2,p0 分配2021-10-21进程调度72p4请求资源 p4发出请求request(3,3,0), 执行银行家算法 available=2 3 0 不能通过算法第2步（ requestiavailable ），所以p4等待。2021-10-21进程调度73p0请求资源 request（0，2，0），执行银行家算法2021-10-21进程调度74进行安全性检查 available2,1,0已不能满足任何进程需要，所以系统进入不安全状态，p0的请求不能分配2021-10-21进程调

29、度75 练习：有三类资源a(17)、b(5)、c(20)。有5个进程p1p5。t0时刻系统状态如下：问(1)、t0时刻是否为安全状态，给出安全系列。(2)、t0时刻，p2: request(0,3,4)，能否分配，为什么？(3)、在(2)的基础上p4：request(2,0,1)，能否分配，为什么？(4)、 在(3)的基础上p1：request(0,2,0)，能否分配，为什么？ 最大需求最大需求已分配已分配p15 5 92 1 2p25 3 64 0 2p34 0 114 0 5p44 2 52 0 4p54 2 43 1 42021-10-21进程调度76解：(1) t0时刻的出安全系列最大

30、需求最大需求已分配已分配needp15 5 92 1 23 4 7p25 3 64 0 21 3 4p34 0 114 0 50 0 6p44 2 52 0 42 2 1p54 2 43 1 41 1 0a(17)、b(5)、c(20)work=2 3 3先求出need和work2021-10-21进程调度77workallocationneedw+afinishp52 3 33 1 41 1 05 4 7tp45 4 72 0 42 2 17 4 11tp37 4 114 0 50 0 611 4 16tp211 4 164 0 21 3 415 4 18tp115 4 182 1 23 4

31、 717 5 20twork=2 3 32021-10-21进程调度78(2) p2: request(0,3,4) 因（available =2 3 3） request(0,3,4) 所以不能分配2021-10-21进程调度79(3) p4：request(2,0,1)workallocationneedw+afinishp40 3 24 0 50 2 04 3 7tp54 3 73 1 41 1 07 4 11tp37 4 114 0 50 0 611 4 16tp211 4 164 0 21 3 415 4 18tavailable =2 3 3allocationneedavaila

32、blep12 1 23 4 70 3 2p24 0 21 3 4p34 0 50 0 6p44 0 50 2 0p53 1 41 1 0有安全序列p4 p5 p3 p2 p1 可以分配2021-10-21进程调度80(4) p1：request(0,2,0)allocationneedavailablep12 3 23 2 70 1 2p24 0 21 3 4p34 0 50 0 6p44 0 50 2 0p53 1 41 1 00 1 2 已不能满足任何进程的需要，不能分配2021-10-21内存管理置换算法4.7 页面淘汰算法先进先出页面淘汰算法（fifo） 选择在内存中驻留时间最长的页并

33、淘汰之第二次机会淘汰算法 (scr) 按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0理想淘汰算法最佳页面算法（opt） 淘汰以后不再需要的或最远的将来才会用到的页面2021-10-21内存管理置换算法1、最佳置换算法 最佳置换算法是一种理想化的理论上算法，具有最好的性能，但在实际上却难于实现。 它选择永不使用的，或者是在最长时间内不再被访问的页面作为淘汰页面。但这是无法预知的，因而该算法无法实现。它在固定分配页面方式中可保证获得最低的缺页率。 2021-10-21内存管理置换算法2、先进先出页面置换算法 该算法总是淘汰最先调入内存的页

34、面，即选择在内存中驻留时间最久的页面予以淘汰。 该算法实现时把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个替换指针，指向最老页面。 2021-10-21内存管理置换算法最近最久未使用页面淘汰算法（lru）选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页 实现代价很高 软件方法或硬件方法2021-10-21内存管理置换算法lru软件解法：设置一个页号栈，当一个页面被访问时，就立即将它的页号压入页号栈，并检查页号栈中是否有与刚压入栈顶的相同的页号，若有，则从页号栈中抽出，以保证页号栈中无相同的页号。当系统要淘汰一节时，总是从页号栈底取出一个页号淘汰，

35、即淘汰的页是最久未使用的。2021-10-21内存管理置换算法lru近似算法：clock算法在页表中增加一访问位，每当访问一页时，将该页的访问位由硬件置1，软件周期（t）性地将所有访问位置0。在时间t内，访问过的页其访问位为1，反之为0，淘汰为0 的页。缺点：t难定。太小，访问位为0的页相当多，所选的不一定是最久未用的。太大，所有页的引用位可能都为1，找不到合适的淘汰页。 2021-10-21内存管理置换算法最不经常使用（lfu） 选择访问次数最少的页面淘汰之 与lru的硬件解法类似。2021-10-21内存管理置换算法页面缓冲算法(pba: page buffering algorithm

36、) 页面缓冲算法采用了可变分配和局部置换方式 页面缓冲算法中，设置了两个链表（队列）存放被淘汰的页：空闲页链表（实际上就是空闲物理块链表：页面未修改）已修改页面链表。2021-10-21内存管理置换算法 当需要读入一个页面时，便利用空闲物理块链表中的第一个物理块来装入。当有一个未被修改的页要换出时，并不将它换出内存，而是直接把它所在的物理块挂在空闲页链表的末尾。换出一个已修改的页面时，则将其所在的物理块挂在修改页面链表的末尾。 注：换出页面时，页面在内存并不做物理上的移动，只是将页表中的表项移到上述两个链表之一中。 2021-10-21内存管理置换算法 优点：可使已被修改的页面和未被修改的页面

37、，都仍留在内存中。当进程以后再次访问这些页面时，就有可能只须花费较小的开销。只有当被修改页面达到一定数量，例如64个页面时，再将它们一起写回到磁盘，从而显著地减少了磁盘io的操作次数。2021-10-21内存管理置换算法某程序在内存中分配三个块，访问页的顺序为4，3，2，1，4，3，5，4，3，2，1，5，按fifo、 lru、opt算法分别计算缺页次数假设开始时所有页均不在内存例12021-10-21内存管理置换算法fifo 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 5 5 2 1 1页2 4 3 2 1 4 3 3 3 5 2 2页3 4 3 2 1

38、4 4 4 3 5 5 x x x x x x x x x 共缺页中断9次fifo2021-10-21内存管理置换算法 lru 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 4 3 2 1 5页2 4 3 2 1 4 3 5 4 3 2 1页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共缺页中断10次 lru 2021-10-21内存管理置换算法 opt 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 5 5 2 1 1页2 4 3 3 3 3 3 3 3 5 5 5页3 4 4 4 4 4

39、 4 4 4 4 4 x x x x x x x 共缺页中断7次opt2021-10-21内存管理置换算法练习某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按lru、opt算法分别计算缺页次数假设开始时所有页均不在内存2021-10-21内存管理置换算法lru 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 4 3 2 1 5页2 4 3 2 1 4 3 5 4 3 2 1页3 4 3 2 1 4 3 5 4 3 2页4 4 3 2 1 1 1 5 4 3 x x x x x x x x共缺页中断8次2021-10-21

40、内存管理置换算法opt 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 5 5 5 1 1页2 4 3 2 2 2 2 2 2 2 5 5页3 4 3 3 3 3 3 3 3 3 3页4 4 4 4 4 4 4 4 4 4 x x x x x x 共缺页中断6次2021-10-21内存管理置换算法有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为 4 3 2 1 4 3 5 4 3 2 1 5(1)该进程运行时总共出现几次缺页。(2)若每个进程在内存有4块，又将产生几次缺页。(3)如何解释所出现的现象。 例220

41、21-10-21内存管理置换算法fifo 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 5 5 2 1 1页2 4 3 2 1 4 3 3 3 5 2 2页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺页中断9次m=32021-10-21内存管理置换算法fifo 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 4 3 2 1 5页2 4 3 2 2 2 1 5 4 3 2 1页3 4 3 3 3 2 1 5 4 3 2页4 4 4 4 3 2 1 5 4 3 x x x x x x x x

42、x x共缺页中断10次m=42021-10-21内存管理置换算法m=3时，缺页中断9次m=4时，缺页中断10次fifo页面淘汰算法会产生异常现象（belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加2021-10-21内存管理置换算法(1) 分配给进程的物理块数(2) 页本身的大小(3) 程序的编制方法(4) 页淘汰算法影响缺页次数的因素2021-10-21内存管理置换算法练习程序编制方法1：for j:=1 to 128 for i:=1 to 128 ai,j:=0;程序编制方法2：for i:=1 to 128 for j:=1 to 128 ai,j:=0;内存分配

43、一页，初始时矩阵数据均不在内存；页面大小为128个整数；矩阵a128x128按行存放。这两个程序执行时分别会产生多少次缺页中断？2021-10-21磁盘调度算法2 磁盘调度算法 当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效 公平：一个i/o请求在有限时间内满足 高效：减少设备机械运动所带来的时间浪费 1) 先来先服务 2)最短寻道时间优先 3)扫描算法 4)单向扫描调度算法2021-10-21磁盘调度算法 按访问请求到达的先后次序服务 优点：简单，公平； 缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动

44、，增加了服务时间，对机械也不利2.1 先来先服务2021-10-21磁盘调度算法 假设磁盘访问序列：98，183，37，122，14，124，65，67 读写头起始位置：53 安排磁头服务序列 计算磁头移动总距离（道数）例2021-10-21磁盘调度算法图解98，183，37，122，14，124，65，67磁头走过的总道数：6402021-10-21磁盘调度算法 优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先 优点：改善了磁盘平均服务时间； 缺点：造成某些访问请求长期等待得不到服务2.2 最短寻道时间优先(ssf)2021-10-21磁盘调度算法图解65，67 ，37，14，98

45、，122，124，183磁头走过的总道数：23698，183，37，122，14，124，65，672021-10-21磁盘调度算法 克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向 具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复2.3 扫描算法（电梯算法）2021-10-21磁盘调度算法图2021-10-21磁盘调度算法图解37，14， 65，67 ， 98， 122， 124， 183磁头走过的总道数：20898，

46、183，37，122，14，124，65，672021-10-21磁盘调度算法 也称单向扫描算法。 电梯算法杜绝了饥饿，但当请求对磁道的分布是均匀时，磁头回头，近磁头端的请求很少（因为磁头刚经过），而远端请求较多，这些请求等待时间要长一些。总是从0号柱面开始向里扫描。移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描 2.4 循环扫描调度算法2021-10-21磁盘调度算法图解2021-10-21磁盘调度算法2.5 n-step-scan和fscan调度算法 1）n-step-scan算法 sstf、scan、cscan几种调度算法都可能出现磁臂停留在某处不动的情况，称为磁臂粘着(arm-stickiness)。在高密度盘上更容易出现此情况。 n-step-scan算法将磁盘请求队列分成若干个长度为n的子队列。磁盘调度将按fcfs算法依次处理这些子队列。而每处理一个队列时，又是按scan算法。这样就可避免出现粘着现象。 2021-10-21磁盘调度算法 2）fscan算法 本算法是n步scan算法的简化。它只将磁盘请求访问队列分成两个子队列： 当前所有请求磁盘io的进程形成的队列，由磁盘调度按scan算法进行处理。在扫描期间，新出现的所有请求磁盘io进程组成的等待处理的请求队列。从而使