《操作系统原理》算法-m.ppt

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