《《操作系统原理》算法-m》由会员分享，可在线阅读，更多相关《《操作系统原理》算法-m（129页珍藏版）》请在金锄头文库上搜索。
1、2024/9/21进程同步互斥1信号量机制（ semaphore ）1965年，由荷兰学者Dijkstra提出（P、V分别是荷兰语的test(proberen)和increment(verhogen)）一种卓有成效的进程同步机制最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）P、V操作是原语2024/9/21进程同步互斥2整型信号量定义一个整数S，仅能通过两个原子操作来访问： wait(S): while S=0 then do no-op S := S 1; Signal(S): S := S + 1; 很明显，不满足让权等待。2024/9/21进程同步互斥3记录型信号量是一个
2、数据结构定义如下：structsemaphoreintvalue;pointer_PCBqueue;信号量说明：semaphores;2024/9/21进程同步互斥4Wait（P操作）wait(s)s.value=s.value-1;if(s.value0)block(S.L);/ 该进程状态置为等待状态/将PCB插入相应的等待队列s.queue;2024/9/21进程同步互斥5Signal（V操作）signal(s)s.value=s.value+1;if(s.value0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源V(S)：表示释放
3、一个资源。信号量的初值应该大于等于02024/9/21进程同步互斥102)操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要2024/9/21进程同步互斥11进程互斥用信号量实现临界区互斥:设置一信号量，信号量初值唯一，进入临界区以前对信号量执行P操作，退出临界区后对信号量执行V操作.2024/9/21进程同步互斥12进程同步 同步问题可分为两类： 保证一组合作进程按确定的次序执
4、行保证共享缓冲区的合作进程的同步。 2024/9/21进程同步互斥13合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。如图2024/9/21进程同步互斥14例如图，试用信号量实现这三个进程的同步。设有两个信号量SB、SC，初值均为Pa：Pb：Pc：P(SB);P(SC)V(SB);V(SC);2024/9/21进程同步互斥15【思考题1】如图，试用信号量实现这三个进程的同步。2024/9/21进程同步互斥16解设有两个信号量S1、S2，初值均为P1：P2：P3：
5、P(S1)V(S1);V(S2);P(S2)2024/9/21进程同步互斥17【思考题2】如图，试用信号量实现这6个进程的同步2024/9/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); 2024/9/21进程同步互斥19共享缓冲区的进程的同步 设某计算进程CP和打印进程IOP共用一个单缓冲区，CP进程负责不断地计算数据并送入缓冲区T中，IOP进程负责
6、不断地从缓冲区T中取出数据去打印。2024/9/21进程同步互斥20分析通过分析可知，CP、IOP必须遵守以下同步规则： 当CP进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印;当IOP进程把缓冲区中的数据取出打印后，CP进程才能把下一个计算结果送入缓冲区2024/9/21进程同步互斥21解为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。两个进程的同步可以描述如下：2024/9/21进程同步互斥22【思考题】操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyput2024/9/21进程同步互斥23解
7、设置四个信号量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); 2024/9/21进程同步互斥24【思考题】桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示
8、可否取桔子，一个信号量表示可否取苹果。2024/9/21进程同步互斥25解设置三个信号量S,So,Sa，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。2024/9/21进程同步互斥26Father() while(1) p(S); 将水果放入盘中将水果放入盘中; if(是桔子是桔子)v(So); else v(Sa); Son() while(1) p(So) 取桔子取桔子 v(S); 吃桔子吃桔子; Daughter() while(1) p(Sa) 取苹果取苹果 v(S); 吃苹果吃苹果; 2024/9/21进程同步互斥274 经典的进程同步问题 4.1生产者/消
9、费者问题 4.2读者/写者问题 4.3哲学家进餐问题 2024/9/21进程同步互斥284.1生产者/消费者问题生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。2024/9/21进程同步互斥29问题描述通过一个有界缓冲区可以把一群生产者P1,P2,Pm，和一群消费者Q1,Q2,Qn联系起来。如图只要缓冲区未满，生产者就可以把产品送入缓冲区;只要缓冲区未空，消费者就可以从缓冲区中取走物品。20
10、24/9/21进程同步互斥30图2024/9/21进程同步互斥31问题分析为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值为。由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。2024/9/21进程同步互斥32问题的解Q： j = 0; while (1) P(S2); P(mutex); 从Bufferj取产品; j = (j+1) % n; V(
11、mutex); V(S1); 消费产品; ;P：i = 0;while (1) 生产产品; P(S1); P(mutex); 往Buffer i放产品; i = (i+1) % n; V(mutex); V(S2); ;2024/9/21进程同步互斥33采用AND信号量集解决生产者-消费者问题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 =
12、(i+1) % n; Ssignal(s2, mutex); ;2024/9/21进程同步互斥34【思考题】有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）（2）NA产品数量B产品数量M。其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。提示：设两个信号量Sa、SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量2024/9/21进程同步互斥35解设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。2024/9/21进
13、程同步互斥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); V(Sb); ;2024/9/21进程同步互斥374.2读者/写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作2024/9/21进程同步互斥38第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有
14、其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待2024/9/21进程同步互斥39第一类读者写者问题的解法设有两个信号量w=1，mutex=1另设一个全局变量readcount=0w用于读者和写者、写者和写者之间的互斥readcount表示正在读的读者数目mutex用于对readcount这个临界资源的互斥访问2024/9/21进程同步互斥40读者： while (1) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 读 P(mutex);
15、 readcount -; if (readcount=0) V(w); V(mutex); ;写者： while (1) P(w); 写 V(w); ;2024/9/21进程同步互斥41第一类读者写者问题的解法（一般信号量集）写者：while(1)Swait(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表示“允许读者数目”，初值为R202
16、4/9/21进程同步互斥42【思考题】写优先修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。提示，增加一个信号量，用于在写者到达后封锁后续的读者2024/9/21进程同步互斥43解 增加一个信号量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
17、); 写 V(w); V(s); ;2024/9/21进程同步互斥44 哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子2024/9/21进程同步互斥45设fork5为5个信号量，初值为均1Philosopheri：while(1)思考；P(forki);P(fork(i+1)%5)；进食；V(forki);V(fork(i+1)%5)；解2024/9/21进程同步互斥46以上解法会出现死锁为防止死锁发生可采
18、取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 分析2024/9/21进程同步互斥47采用AND信号量集解决哲学家就餐问题设fork5为5个信号量，初值为均1Philosopheri：while(1)思考；Swait(forki,fork(i+1)%5)；进食；Ssignal(forki,fork(i+1)%5)；2024/9/21进程调度48调度算法先来先服务算法（FCFS：FirstComeFirstServe）有利于长作业，不利于短作业最短作业优先算法（SJF：
19、ShortestJobFirst）-提高了系统吞吐量对长作业不利未考虑作业的紧迫程度作业时间的估计时间不准2024/9/21进程调度49高优先权调度算法照顾紧迫作业，常用于批处理静态优先权依据进程类型：系统进程高于一般用户进程依据对资源的要求：要求少的高于多的依据用户要求：紧迫程度和付费情况动态优先权创建进程时赋予的优先权，遂进程的推进或随其等待时间的增加而改变，可防止某些进程无限期的等待2024/9/21进程调度50最高响应比优先算法（HRN：HighestResponseRatioNext）响应比R=作业周转时间/作业处理时间=（作业处理时间+作业等待时间）/作业处理时间=1+（作业等待时
20、间/作业处理时间）2024/9/21进程调度51调度算法应用例子1假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间2024/9/21进程调度522024/9/21进程调度53先来先服务调度算法计算结果2024/9/21进程调度54最短作业优先作业算法计算结果2024/9/21进程调度55最高响应比优先作业算法计算结果2024/9/21进程调度56多队列反馈调度算法将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越长，级别越小，时间片越短；当进
21、程第一次就绪时，进入第一级队列系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；2024/9/21进程调度57就绪队列1就绪队列2就绪队列3就绪队列4至CPU至CPU至CPU至CPU2024/9/21进程调度58 利用银行家算法避免死锁最有代表性的避免死锁算法，由Dijkstra提出。1、银行家算法中的数据结构可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如： ABC5232024/9/21进程调度59最大需求矩阵Max。n*m矩阵，表示n个
22、进程的每一个对m类资源的最大需求。ABCP1562P2331P3425P43322024/9/21进程调度60分配矩阵Allocation。n*m矩阵，表示每个进程分配的资源数。ABCP1212P2121P3222P41322024/9/21进程调度61需求矩阵Need。n*m矩阵，表示每个进程还需要各类资源数。ABCP1352P2211P3223P42322024/9/21进程调度62例设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图2024/9/21进程调度63银行家算法描述当进程Pi提出资源申请时，系统执行下列步骤：（1）若RequestiNeedi,转
23、（2）；否则错误返回（2）若RequestiAvailable,转（3）；否则进程等待2024/9/21进程调度64（3）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti（4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待2024/9/21进程调度65安全性算法为进行安全性检查，定义数据结构：Work:ARRAY0.m-1ofinteger;Finish:ARRAY0.n-1ofBoolean;m代
24、表资源的数量，n代表进程的数量2024/9/21进程调度66安全性算法步骤(1)Work:=Available;Finish:=false;(2)寻找满足下列条件的i：a).Finishi=false;b).NeediWork;如果不存在，则转(4)2024/9/21进程调度67(3)Work:=Work+Allocationi;Finishi:=true;转(2)(4)若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态2024/9/21进程调度68T0时刻的安全性检查T0时刻可以找到一个安全序列p1,p3,p4,p2,p0.系统是安全的。2024/9/21进程调度6
25、9例1：T0时刻P1请求资源P1发出请求Request(1,0,2)，执行银行家算法2024/9/21进程调度70执行安全性算法可以找到一个安全序列p1,p3,p4,p0,p2.系统是安全的，可以将P1的请求分配给它。2024/9/21进程调度71P1请求资源P1发出请求Request(1,0,2),执行银行家算法条件满足，找到安全序列p1,p3,p4,p2,p0分配2024/9/21进程调度72P4请求资源P4发出请求Request(3,3,0),执行银行家算法Available=230不能通过算法第2步（RequestiAvailable），所以P4等待。2024/9/21进程调度73P0
26、请求资源Request（0，2，0），执行银行家算法2024/9/21进程调度74进行安全性检查Available2,1,0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配2024/9/21进程调度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)，能否分配，为什么？最大需求最大
27、需求已分配已分配P15 5 92 1 2P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 42024/9/21进程调度76解：(1)T0时刻的出安全系列最大需求最大需求已分配已分配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和Work2024/9/21进程调度77WorkAllocationNeedW+AFinishP52 3 33 1 41 1 0
28、5 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 717 5 20TWork=2 3 32024/9/21进程调度78(2)P2:Request(0,3,4)因（Available=233）Request(0,3,4)所以不能分配2024/9/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 11T
29、P37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20TAvailable =2 3 3AllocationNeedAvailableP12 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 可以分配2024/9/21进程调度80(4)P1：Request(0,2,0)AllocationNeedAvailableP12 3 23 2 70 1 2P24 0 21 3 4P34 0
30、 50 0 6P44 0 50 2 0P53 1 41 1 00 1 2 已不能满足任何进程的需要，不能分配2024/9/21内存管理置换算法4.7页面淘汰算法先进先出页面淘汰算法（FIFO）选择在内存中驻留时间最长的页并淘汰之第二次机会淘汰算法(SCR)按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0理想淘汰算法最佳页面算法（OPT）淘汰以后不再需要的或最远的将来才会用到的页面2024/9/21内存管理置换算法1、最佳置换算法 最佳置换算法是一种理想化的理论上算法，具有最好的性能，但在实际上却难于实现。它选择永不使用的，或者是在最长时
31、间内不再被访问的页面作为淘汰页面。但这是无法预知的，因而该算法无法实现。它在固定分配页面方式中可保证获得最低的缺页率。 2024/9/21内存管理置换算法2、先进先出页面置换算法该算法总是淘汰最先调入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现时把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个替换指针，指向最老页面。 2024/9/21内存管理置换算法最近最久未使用页面淘汰算法（LRU）选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页 实现代价很高 软件方法或硬件方法2024/9/21内存管理置换算法LRU软件解法：设置一个页号
32、栈，当一个页面被访问时，就立即将它的页号压入页号栈，并检查页号栈中是否有与刚压入栈顶的相同的页号，若有，则从页号栈中抽出，以保证页号栈中无相同的页号。当系统要淘汰一节时，总是从页号栈底取出一个页号淘汰，即淘汰的页是最久未使用的。2024/9/21内存管理置换算法LRU近似算法：Clock算法在页表中增加一访问位，每当访问一页时，将该页的访问位由硬件置1，软件周期（T）性地将所有访问位置0。在时间T内，访问过的页其访问位为1，反之为0，淘汰为0的页。缺点：T难定。太小，访问位为0的页相当多，所选的不一定是最久未用的。太大，所有页的引用位可能都为1，找不到合适的淘汰页。2024/9/21内存管理置
33、换算法最不经常使用（LFU）选择访问次数最少的页面淘汰之与LRU的硬件解法类似。2024/9/21内存管理置换算法页面缓冲算法(PBA:PageBufferingAlgorithm)页面缓冲算法采用了可变分配和局部置换方式 页面缓冲算法中，设置了两个链表（队列）存放被淘汰的页：空闲页链表（实际上就是空闲物理块链表：页面未修改）已修改页面链表。2024/9/21内存管理置换算法当需要读入一个页面时，便利用空闲物理块链表中的第一个物理块来装入。当有一个未被修改的页要换出时，并不将它换出内存，而是直接把它所在的物理块挂在空闲页链表的末尾。换出一个已修改的页面时，则将其所在的物理块挂在修改页面链表的末
34、尾。注：换出页面时，页面在内存并不做物理上的移动，只是将页表中的表项移到上述两个链表之一中。 2024/9/21内存管理置换算法优点：可使已被修改的页面和未被修改的页面，都仍留在内存中。当进程以后再次访问这些页面时，就有可能只须花费较小的开销。只有当被修改页面达到一定数量，例如64个页面时，再将它们一起写回到磁盘，从而显著地减少了磁盘IO的操作次数。2024/9/21内存管理置换算法某程序在内存中分配三个块，访问页的顺序为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、LRU、OPT算法分别计算缺页次数假设开始时所有页均不在内存例12024/9/21内存管理置换算法FIFO 4 3
35、 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次FIFO2024/9/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次LRU2024/9/21内存管理置换算法 OPT 4 3 2 1
36、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 4 4 4 4 4 x x x x x x x 共缺页中断7次OPT2024/9/21内存管理置换算法练习某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数假设开始时所有页均不在内存2024/9/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
37、页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次2024/9/21内存管理置换算法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次2024/9/21内存管理置换算法有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为432143543215
38、(1)该进程运行时总共出现几次缺页。(2)若每个进程在内存有4块，又将产生几次缺页。(3)如何解释所出现的现象。例22024/9/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=32024/9/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页
39、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 x x共缺页中断10次m=42024/9/21内存管理置换算法m=3时，缺页中断9次m=4时，缺页中断10次FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加2024/9/21内存管理置换算法(1)分配给进程的物理块数(2)页本身的大小(3)程序的编制方法(4)页淘汰算法影响缺页次数的因素2024/9/21内存管理置换算法练习程序编制方法1：for j:=1 to 128 for i:=1 to 128 Ai,j:=0;程
40、序编制方法2：for i:=1 to 128 for j:=1 to 128 Ai,j:=0;内存分配一页，初始时矩阵数据均不在内存；页面大小为128个整数；矩阵A128X128按行存放。这两个程序执行时分别会产生多少次缺页中断？2024/9/21磁盘调度算法2磁盘调度算法当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效公平：一个I/O请求在有限时间内满足高效：减少设备机械运动所带来的时间浪费1)先来先服务2)最短寻道时间优先3)扫描算法4)单向扫描调度算法2024/9/21磁盘调度算法按访问请求到达的先后次序服务优点：简单，公平；
41、缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利2.1先来先服务2024/9/21磁盘调度算法假设磁盘访问序列：98，183，37，122，14，124，65，67读写头起始位置：53安排磁头服务序列计算磁头移动总距离（道数）例2024/9/21磁盘调度算法图解98，183，37，122，14，124，65，67磁头走过的总道数：6402024/9/21磁盘调度算法优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先优点：改善了磁盘平均服务时间；缺点：造成某些访问请求长期等待得不到服务2.2最短寻道时间优先(SSF)2024/9/2
42、1磁盘调度算法图解65，67 ，37，14，98，122，124，183磁头走过的总道数：23698，183，37，122，14，124，65，672024/9/21磁盘调度算法克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复2.3扫描算法（电梯算法）2024/9/21磁盘调度算法图2024/9/21磁盘调度算法图解37，14， 65，67 ， 98， 122， 124，
43、183磁头走过的总道数：20898，183，37，122，14，124，65，672024/9/21磁盘调度算法也称单向扫描算法。电梯算法杜绝了饥饿，但当请求对磁道的分布是均匀时，磁头回头，近磁头端的请求很少（因为磁头刚经过），而远端请求较多，这些请求等待时间要长一些。总是从0号柱面开始向里扫描。移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描2.4循环扫描调度算法2024/9/21磁盘调度算法图解2024/9/21磁盘调度算法2.5 N-Step-SCAN和FSCAN调度算法1）N-Step-SCAN算法SSTF、SCAN、
44、CSCAN几种调度算法都可能出现磁臂停留在某处不动的情况，称为磁臂粘着(Arm-Stickiness)。在高密度盘上更容易出现此情况。N-STEP-SCAN算法将磁盘请求队列分成若干个长度为N的子队列。磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时，又是按SCAN算法。这样就可避免出现粘着现象。2024/9/21磁盘调度算法2）FSCAN算法本算法是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列：当前所有请求磁盘IO的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，新出现的所有请求磁盘IO进程组成的等待处理的请求队列。从而使所有的新请求都将被推迟到下
45、一次扫描时处理。2024/9/21混合索引UNIX文件系统的索引结构在UNIX索引节点中，有一个di_addr40数组，这个数组就是一个索引表。在这个40个字节的数组中，只用了39个字节，分为13组（项），每项3个字节，记录一个块号，所以一个文件系统的数据区最多有224个块。设计为40个字节是为了让索引节点的大小刚好为64字节，那么，一个块就能放整数个索引节点。2024/9/21混合索引索 引 表 有 13个 表 目 （ 用 ADDR0ADDR12表示）。ADDRO至ADDR9，即前10个表目直接存放文件数据块的块号。如 果 文 件 的 长 度 超 过 10个 数 据 块 ，ADDR10，即第
46、11个表目登记的是一次间接索引表的块号，在一次间接索引表中存放文件数据块的块号。2024/9/21混合索引ADDR1l，即第12个表目登记的是二次间接索引表的块号，二次间接索引表存放一次间接索引块的块号。ADDR12，即第13个表目登记的是三次间接索引表的块号，三次间接索引表中存放二次间接索引表的块号。2024/9/21混合索引例1有一文件大小为16K，设一个物理块的大小为1K,为了计算方便，设索引块中的一个表项占2个字节，试画出文件索引结构图。2024/9/21混合索引例2现有三个文件，大小分别是16K，256K,128M，设一个物理块的大小为4K,为了计算方便，设索引块中的一个表项占2个字
47、节，试分别画出它们的文件索引结构图。2024/9/21混合索引解：16K文件的索引结构图分析：对16K的文件，可分为4个块，则用直接索引即可解决。2024/9/21混合索引ADDR12ADDR11ADDR10ADDR9 ADDR3 ADDR1ADDR0索引表文件第 4 块文件第 1 块.2024/9/21混合索引256K文件的索引结构图对256K的文件，可分为64个块，直接索引可索引10个块，用一次间接索引索引54个块。2024/9/21混合索引ADDR12ADDR11ADDR10ADDR9 ADDR1ADDR0索引表文件第 10 块文件第 10 块文件第 11 块文件第 64 块.。一次间接
48、索引表5320472024/9/21混合索引128M文件的索引结构图对128M的文件，可分为32K个块直接索引可索引10块，一次间接索引可索引2K个块（因为一个一次间接索引块的大小等于物理块的大小，等于4K，而一个表项2个字节，所以一个间接索引块可以索引2K个物理块）。二次索引表要用掉15个表目，每个表目指向一个一次间接索引块（共15个一次间接块），前14个一次间接块可索引28K个物理块，后一个一次间接块用掉2038个表目（1K+1014），共可索引1K+1014个物理块。把上面几项相加：10+2K+28K+1K+1014得32K。2024/9/21混合索引ADDR12ADDR11ADDR10
49、ADDR9 ADDR1ADDR0索引表10 111 10+2k 一次204710 +2K+1 10+2k+28K10+2k+28K+110+2k+28K+2038二次1420472047203720472k28k2038一次132024/9/21混合索引练习若有16K，256K,128M等文件，设一个物理块的大小为2K,索引块中的一个表项占2个字节，试分别画出它们的文件索引结构图。2024/9/21混合索引小结在UNIX系统的文件系统中，对于小于等于10个物理块的文件采用直接索引，可从i结点的索引表中直接取到文件数据块的物理块号，不需要进行任何转换和计算，加快了文件存取的速度，提高了文件系统的使用效率;
