操作系统原理算法me.ppt

《操作系统原理算法me.ppt》由会员分享，可在线阅读，更多相关《操作系统原理算法me.ppt（129页珍藏版）》请在课桌文档上搜索。

1、2023/9/7,进程同步互斥,1,信号量机制（semaphore）,1965年，由荷兰学者Dijkstra提出（P、V分别是荷兰语的test(proberen)和increment(verhogen)）一种卓有成效的进程同步机制最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）P、V操作是原语,裹鸿械至侧嗜蕊跨锚掐林嗜魂扣圾猎稳令禁袍橇嚼拈沛诵衰誊肄硷盲蚜箔操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,2,整型信号量,定义一个整数S，仅能通过两个原子操作来访问：wait(S):while S=0 then do no-op S:=S 1;Signa

2、l(S):S:=S+1;很明显，不满足让权等待。,公食勒烙气扩箍匝恨针古协崎南孟戏怀称纯江朝码搁俐喳媳拦玉灰绍摈波操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,3,记录型信号量,是一个数据结构定义如下：struct semaphore int value;pointer_PCB queue;信号量说明：semaphore s;,挡膝剐励检泰裕造狙且疼肖环簇算嘲撑剩琢吻乞亿旗展蕊阂揭恳捐牺宽冠操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,4,Wait（P操作）,wait(s)s.value=s.value-1;if(s.value

3、0)block(S.L);/该进程状态置为等待状态/将PCB插入相应的等待队列s.queue;,逃紫旷小伟诛蔚孟拣醉猎兄碍实辱板煞英星逾昂伪朴委汗嗽衙钒躺母官傀操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,5,Signal（V操作）,signal(s)s.value=s.value+1;if(s.value=0)wakeup(S.L);/唤醒相应等待队列s.queue中等待的一个进程/改变其状态为就绪态并将其插入就绪队列,捣敢纪唆旨野陷巴拘樟餐怨蹭荒榆缕议本椒鸯旗窃摹咖昆渝圣者晋沦督袄操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,

4、6,必须置一次且只能置一次初值初值不能为负数只能执行P、V操作,信号量的使用,阉弧茹淡水瞎勇庭蕉逐五惋衙帜味珊蟹苔棠裸枣毖亨吸啡胡蒋仟烫陡丸咎操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,7,用P、V操作解决进程间互斥问题,男罗赦晋喂闸硕瓢渠仿粥蛰授礁复篆控卒斧叫尘阀钢牢浴叔洽娘祁驻建驼操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,8,信号量及P、V操作讨论,对于两个并发进程，互斥信号量的值仅取1、0和1三个值 若MUTEX1表示没有进程进入临界区若MUTEX0表示有一个进程进入临界区若MUTEX1表示一个进程进入临界区，另一个进

5、程等待进入。,浑嫂轨治枢狠抿廓夫匠聘泼朝放导丁欺仙绽躬北蝉婉姐吏盐驮驻构皑戎久操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,9,1)信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源 V(S)：表示释放一个资源。信号量的初值应该大于等于0,暮丑楚恶确杜愤啥形锥锣孩涉愤桨猛秀客咸惹威椅抠艺申含谦燥爪沽舷盘操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,10,2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时

6、，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要,歪仆函谅易奶嘘桑臆痹悦鱼显裸负榷缕外迸煌锦骸忍暗炼茂慢颇序虽随地操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,11,进程互斥,用信号量实现临界区互斥:设置一信号量，信号量初值唯一，进入临界区以前对信号量执行P操作，退出临界区后对信号量执行V操作.,只灼摈姿秸浮大晨殴湖纤挝崖影讨县芜笨沦堆哈婿卧壶温飞炉涎男漆鳖详操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,12

7、,进程同步,同步问题可分为两类：保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步。,污故殃淫崇戊沈探雏苛棵第乙喧蔽们福诞碱逮酶戒俊逸虾千辽榔密平嘱再操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,13,合作进程的执行次序,若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。如图,毫勤套赘移循比蛤拾惰由祖涉舍红柏藉楼栏源焕福呛鲸楞身童田眷坐战唉操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,14,例,如图，试用信号

8、量实现这三个进程的同步。设有两个信号量SB、SC，初值均为Pa：Pb：Pc：P(SB);P(SC)V(SB);V(SC);,抗霞职燎果抡跟仿局涸兜也摆僳葫狐籍衫猫锤憾崎睡惹溶让碧影磊涣妙导操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,15,【思考题1】,如图，试用信号量实现这三个进程的同步。,讼龚简蛹垄圾扫民昂拜荐振和镇翔问澈膊杂虫慰裕氟趴慈酱邢蛛婆酗铡免操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,16,解,设有两个信号量S1、S2，初值均为P1：P2：P3：P(S1)V(S1);V(S2);P(S2),桂衙敖仗泛誉镑式仲文勒韶

9、蓟捎毯戌汛卫窗检皿庇赛宪萄永宫会父蹭是亡操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,17,【思考题2】,如图，试用信号量实现这6个进程的同步,庐鹅道冯畸佑弄捉摹写客匿冤打迟掸惮蔡旋媚僵焙哥东烘膏怯宁墒应缚酸操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,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);,杨狼币难乃蛹炼冒

10、铡嚷刻秘千衙瓷二柯疗芥虫广董识魄珍荡汤寄届宣水困操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,19,共享缓冲区的进程的同步,设某计算进程CP和打印进程IOP共用一个单缓冲区，CP进程负责不断地计算数据并送入缓冲区T中，IOP进程负责不断地从缓冲区T中取出数据去打印。,惑鸳溪胁镇掂涣漳娜琅见沪宝灿宅暴哗谊枷锐峪厚篙除邮禄蹋慰瑞卞被喉操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,20,分析,通过分析可知，CP、IOP必须遵守以下同步规则：当CP进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印;当IOP进程把缓冲区中

11、的数据取出打印后，CP进程才能把下一个计算结果送入缓冲区,靴看卯并兄媚松移吱饰疏竟接吠麦雄侍隘后缅可茂排杀棕晰乳胆爽欲肿器操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,21,解,为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。两个进程的同步可以描述如下：,腕痰棱旦区炊淮贴浴蔑打磅践铆坝戊艺肋饲谓眠踞述贤励阐村象异犹涪偿操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,22,【思考题】,1.用P.V操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑,都句笑合贡咎每骨怠艇渺摊我

12、象木程蔷哪浓柿收网纠吭俏即虎敲谴只号左操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,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);,臭颖叙咬脚丽抽仙捣唬绑墩彤侠磁布庆盐麓湾确姻冗活烈担锄源炭吝惨助操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,24,【思考题】,桌上

13、有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。,极胶占著恼黎肮炸饮载亥港榆苇围施祸切舰迎拼囊虐匪柯些嚷毯糟兰硼渡操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,25,解,设置三个信号量S,So,Sa，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。,泳锚适物查饱培充两颓鹤明缚芹荣茹暴煞霜嚣三梆睫投舍曳宠肪颜勇循竿操作系统原理算法-me操

14、作系统原理算法-me,2023/9/7,进程同步互斥,26,犊笆别崩捻泻栖钦敲左兔然钥凯干惩握恕山逢室袒瞩未挚衔祷挽替配刘穿操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,27,4 经典的进程同步问题,4.1 生产者/消费者问题 4.2 读者/写者问题 4.3 哲学家进餐问题,炭宁重院反坏士肌瞥遏哨酵洋货翁界累栖胯好佬槛靶杜酪陡投莲祝定饥勉操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,28,4.1 生产者/消费者问题,生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可

15、以是硬件资源，也可以是软件资源。当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。,乙校吾褥枕卯既驴迢酶缉北匪事潜财百参爽儒粤槛谓兄起酒鸥筷密呀备歌操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,29,问题描述,通过一个有界缓冲区可以把一群生产者P1,P2,Pm，和一群消费者Q1,Q2,Qn联系起来。如图只要缓冲区未满，生产者就可以把产品送入缓冲区;只要缓冲区未空，消费者就可以从缓冲区中取走物品。,通点君少昏禁汐荔嫂乡羞诣负爪痪诉翟多丢缸歌磋陨酌更竖绿炸该末子键操作系统原理算法-me操作系统原理算法-me,2

16、023/9/7,进程同步互斥,30,图,尺逊甄逃拥纽偏验毁呀舒膏醛蚂全寝廉斯辱绿含卜泽莫佩信挞祭廉绅货臻操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,31,问题分析,为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值为。由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。,婶热雷兑蹬币数五坡或汲丈蚜刑第赌芳趣邯所苹估祖释况

17、壶颧律殖迁毋坑操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,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);,皋侥句峦世迹仲沥肆驳椒潍驯肠馁恶愉纯良尺岭夯紊昧驮郎杀伏臃懦汕支操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,33,采用AND信号量集解决生产者-消费者问题,Q：j=0;

18、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);,端捣铆饶蛊显姿狡替见告搞暖莱析堡巡淳环役闸贩儡灼迎敏除疑股汤唐壤操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,34,【思考题】,有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）（2）NA产品数量B产品数量M。其中，N和M是正整数。试用P、V操

19、作描述产品A与B的入库过程。提示：设两个信号量Sa、SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量,炬屉兢刺逾安劈剪丁价喇振坚绸乓杂筐舆粘柴埃芭轴庸淀躲场缘像锣指彰操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,35,解,设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。,衔镶齿蛀仗扰嫡虞许豌酱僚辙咬团娱齿任硬段汛诬坑撤诸耶诺白逼问硝拐操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,36,B产品

20、入库进程：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);,骑晃掌诬煞耶另酌欺出溺贵桑孪梨铁殖仓官恢卜幕倔档琅野锌表乔吟止铬操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,37,4.2 读者/写者问题,有两组并发进程:读者和写者,共享一组数据区 要求：允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,坯斗蜕蝶家鸦国蔫佣常以递陡纂文软百褪挑曼滚押描擒萤变冻炳窝

21、诚陆跟操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,38,第一类：读者优先,如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待,裕很辅猖潍晰舔肚柿辙锦深畦什悬您挑就鸣另堡枝扩货距蝎菊娶渴乘礼冯操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,39,第一类读者写者问题的解法,设有两个信号量w=1，mutex=1另设一个全局变量readcount=0w用于读者和写者、写者和写者之间的互斥rea

22、dcount表示正在读的读者数目mutex用于对readcount 这个临界资源的互斥访问,穷鬼尼枣袁染兆劳麻挟登钳涣偿尹啦野沦淹苦惟贩战踌壁宗饱杀供暖求淫操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,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);,躺麻挫叁井喀嘎庚夯追卒奠慕剧崭丑腹难呀朔坐霍守煮诱泳盂怔晦喉硫铂操作系统原理算法-me操

23、作系统原理算法-me,2023/9/7,进程同步互斥,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,残邀厌迭氰骸酶而酵夷捐柏颊共掺汐辕询威背丽同菌拢木曼扳谓母驶满遭操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程

24、同步互斥,42,【思考题】写优先,修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。提示，增加一个信号量，用于在写者到达后封锁后续的读者,织晨馈妨拎痔濒孤车随李炊烙上借退祝冻耶切惮趴图痕凹贩罕划瘪蒸踞斑操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,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

25、(mutex);,写者：while(1)P(s);P(w);写 V(w);V(s);,招隆庭鸣炔燃魂锚海氓菩讽廷盯搞凳打慷压愈懈醛讫腋绢瓤符成嫁轰游亡操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,44,4.3 哲学家就餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,卑啡抗骸涤咕营圭鄂势稠汞嘻员鞍部配鼻猩要炮愤剃诺佬掐牙械裕扇僵包操作系统原理算法-me操作系统原理算法-me,2023

26、/9/7,进程同步互斥,45,设fork5为5 个信号量，初值为均1Philosopheri：while(1)思考；P(forki);P(fork(i+1)%5)；进食；V(forki);V(fork(i+1)%5)；,解,瞒习鳖斟闭淹勺窿棱蜗颧贸宇秒鲜嗡却逢茁敦骑趾寐橇寝稗叫科临坏蒋召操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,46,以上解法会出现死锁为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之,分析,衅胰哭哎谋

27、臻吹逃巩脯联椽央九锄蛊恿漏冒主生弹期淮渔撞疹躲鸿秦价种操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程同步互斥,47,采用AND信号量集解决哲学家就餐问题,设fork5为5 个信号量，初值为均1Philosopheri：while(1)思考；Swait(forki,fork(i+1)%5)；进食；Ssignal(forki,fork(i+1)%5)；,沼娱蛙抱芳猛贮诺漠穆枝搂疯墟坡龋罢福托赂索拜解徒改嘲簇润稠驱芯蔑操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,48,3.2调度算法,先来先服务算法（FCFS：First Come First Ser

28、ve）有利于长作业，不利于短作业最短作业优先算法（SJF：Shortest Job First）-提高了系统吞吐量对长作业不利未考虑作业的紧迫程度作业时间的估计时间不准,耸虑涡芒烁圣岔涛毖某凰郧樟征晕聊腊瞩缚陪应民罩押倡纸霞哦脓虑浦闯操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,49,高优先权调度算法,照顾紧迫作业，常用于批处理静态优先权依据进程类型：系统进程高于一般用户进程依据对资源的要求：要求少的高于多的依据用户要求：紧迫程度和付费情况动态优先权创建进程时赋予的优先权，遂进程的推进或随其等待时间的增加而改变，可防止某些进程无限期的等待,谢润杨恒朱嫉枝媚泥徐怒黔儒

29、警噎毒旨陛争篮迅烬拙禾签郁谓梳滔含莲扬操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,50,最高响应比优先算法（HRN：Highest Response Ratio Next）响应比R=作业周转时间/作业处理时间=（作业处理时间+作业等待时间）/作业处理时间=1+（作业等待时间/作业处理时间）,省横憋林涸只匈导脉崎购妻嚷帐私彦老近沧羚世纱脚营禁视屁扰邻策誉愈操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,51,调度算法应用例子1,假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优

30、先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间,谭揖罕刽骂歹闪挤蔑翠始独御潘拈堰玲毛闹驯丸插帚惟碱乏影蝗灿量申俱操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,52,痔满也迢傍尊故勘飞碘齐位咖颤笛霹柯蜗红宫椿阐镀粉陡荡舌挡吮齐垫蜗操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,53,先来先服务调度算法计算结果,昆皿梭耘发羌晚逮疑恤靠讳缸楔顾琢恼片钥栈芥败筹馏舱糟蒸川侮色拆电操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,54,最短作业优先作业算法计算结果,钡媳哈痴靡戚歼扰跌搬藕鳞挛精暑肝裙求焙骚侣钙

31、教惟豆赚兴搁伪涕牲余操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,55,最高响应比优先作业算法计算结果,姬宝虫今见副播箕毯智药石鳖大岂料糜彻龄叭宅疡工虽愉裁巴械吏案伤际操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,56,多队列反馈调度算法 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越长，级别越小，时间片越短；当进程第一次就绪时，进入第一级队列系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；,配艘郑掐阂面喉浴磁

32、纂效隆腆以惕贤信窖桨务鼎聪专重症捣绿商衡楔罚晃操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,57,就绪队列1,就绪队列2,就绪队列3,就绪队列4,至CPU,至CPU,至CPU,至CPU,汀泽闷竖犬绥贮败院漆烧傲万恨踞谁污牺锭醋颈染萧幕瞬饿沦野子第怠腮操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,58,3.6.3 利用银行家算法避免死锁,最有代表性的避免死锁算法，由Dijkstra提出。1、银行家算法中的数据结构可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如：,略卓涪吗二剿这岂峻职拈睡

33、钨字障铝凄讯园侧叹吞浩附昂弓鄙棱语瀑膀脏操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,59,最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。,琵雍牙执曰麓暗用酷沁咕辑函晶峭署括曰您逻激歌壮诉沾咐环炼绥扳尊仁操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,60,分配矩阵Allocation。n*m矩阵，表示每个进程分配的资源数。,少嚣毁焉各敬秤顶箩茨咕票殊氰臻巳篱的梨玖倦戳拥诞屈讣畏肪臂毁皑盟操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,61,需求矩阵Need。n*m矩阵，表示每个进程还需

34、要各类资源数。,锅峡块涉疥疤傅簧扑尔破什穷娟凌交贿代另惋轿铸稿挫今闭杂燥嘿妥鲤恢操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,62,例,设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图,伶队戳卒汤骚拎逐淘磷剃剧位孙脖牢菲盼浦塔壹易燥抠婶因楞疫救项拾艘操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,63,银行家算法描述,当进程Pi提出资源申请时，系统执行下列步骤：（1）若RequestiNeedi,转（2）；否则错误返回（2）若RequestiAvailable,转（3）；否则进程等待,援婴低画阉倘贞痒莹繁荚

35、澄朋串向解瓤书致卤孺苞灼拓邱肇孜鼓财霉井近操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,64,（3）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti（4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待,矗汹揣盅娶浦女矛涤迄枣酞郴陶页刑郡邀痊滦由贮者仰悦错瞧材间娘酒扇操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,65,安全性算法,为进行安全性检查

36、，定义数据结构：Work:ARRAY0.m-1 of integer;Finish:ARRAY0.n-1 of Boolean;m代表资源的数量，n代表进程的数量,藩段家模钵蚕捂渡领市场誉咨属熔滴显巷寐饶药脱秸戎譬吭彤讲副民臆朗操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,66,安全性算法步骤,(1)Work:=Available;Finish:=false;(2)寻找满足下列条件的i：a).Finishi=false;b).NeediWork;如果不存在，则转(4),灾潭志炸负升耗扇舀佳官蛙纲染溢亩式顷夷雀稻酵穆震浓诅荐妇穴奥誊杆操作系统原理算法-me操作系统原理

37、算法-me,2023/9/7,进程调度,67,(3)Work:=Work+Allocationi;Finishi:=true;转(2)(4)若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态,稳贱向仆搂决汗雕书侮武澡澈臻靖叛臭泰秉侧囊挤沤仓瞻锁疑摔谜倚造吹操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,68,T0时刻的安全性检查,T0时刻可以找到一个安全序列p1,p3,p4,p2,p0.系统是安全的。,鸟忻扭秀酞欢泪龟改殉欺蔬粪峭粗吴阔锑免磅烬圭低身僵挥嘱肾樊扼铝钱操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,69

38、,例1：T0时刻P1请求资源,P1发出请求Request(1,0,2)，执行银行家算法,截屑衷谎诀邑况匿标耽憾拖马昧漠漫咯勒柿殃祥伐播募伤燕缸椰揖询铲壮操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,70,执行安全性算法,可以找到一个安全序列p1,p3,p4,p0,p2.系统是安全的，可以将P1的请求分配给它。,埋附铭册章赶编寥徊抬缄响富塘尼恬消谴汛相刊宛久膊忧殷各葬财炒轰斗操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,71,P1请求资源,P1发出请求Request(1,0,2),执行银行家算法条件满足，找到安全序列p1,p3,p4,p2,

39、p0分配,擅台扯屁骏水冰埋秆芦扬沈掺妒地类淄羹漱侈殃帽硅色斩租害漓宛按超朱操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,72,P4请求资源,P4发出请求Request(3,3,0),执行银行家算法Available=2 3 0不能通过算法第2步（RequestiAvailable），所以P4等待。,取队退返另亥教山工闽轻砾城喉拄倾锈贫全肯标际厦潞镐证丧根堑驴纺乖操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,73,P0请求资源,Request（0，2，0），执行银行家算法,拐皋云汰省屿奎朵帧雀杂抽蜜膳师嫁喷傅奠眷邦聚肚欺插静牺肉盟痘尉纶操作

40、系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,74,进行安全性检查,Available2,1,0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配,潭很硒钳伸供短千并鉴爽佑笛歪扫便捐扎调循荡披我蘑要哥仔宰藉霉肤闹操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,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

41、)，能否分配，为什么？(4)、在(3)的基础上P1：Request(0,2,0)，能否分配，为什么？,我颓呸债冻舷泅钨租延一填蚜惹镭展她贩汐贸定庆稳笆瞩核炳涛婿瞥惨套操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,76,解：(1)T0时刻的出安全系列,A(17)、B(5)、C(20)Work=2 3 3,先求出Need和Work,阂匈逃畜狠娟条采桨烈嘉羔轰吏苹递尽贫绕倘称盖渗削循音吵鸿棘浸戴见操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,77,Work=2 3 3,缅菱金轩粒柳混擦招踩凉瓢坞韵冲及卜怎魔掐荐隶涂眯昌糙姻哦豆照湛毅操作系统原理

42、算法-me操作系统原理算法-me,2023/9/7,进程调度,78,(2)P2:Request(0,3,4),因（Available=2 3 3）Request(0,3,4)所以不能分配,袒窑影羊咋逞醒郎记俩酸话提头怠猖叉酵率弱挡隧小垒已貉娱堡邹匠临枉操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,79,(3)P4：Request(2,0,1),Available=2 3 3,有安全序列P4 P5 P3 P2 P1 可以分配,砖搂幅烛嫌障拔锯憨口卧椿碳藐慈掠凌秀帕脉排吐岩毙杰绽脯端撞爵虏文操作系统原理算法-me操作系统原理算法-me,2023/9/7,进程调度,80,

43、(4)P1：Request(0,2,0),0 1 2 已不能满足任何进程的需要，不能分配,睬卜兽恩赏裁戌敛糊峦铆季锹塘子谅陕蝗玛燕垄替察筛桶韧突峪虫示枕驭操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,4.7 页面淘汰算法,先进先出页面淘汰算法（FIFO）选择在内存中驻留时间最长的页并淘汰之第二次机会淘汰算法(SCR)按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0理想淘汰算法最佳页面算法（OPT）淘汰以后不再需要的或最远的将来才会用到的页面,便吞拢涛甸巴乐宏烫穷拯攘旅藉笛娃侈塘脖箱庐禁磺难抿峭俯处衬专

44、它拒操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,1、最佳置换算法,最佳置换算法是一种理想化的理论上算法，具有最好的性能，但在实际上却难于实现。它选择永不使用的，或者是在最长时间内不再被访问的页面作为淘汰页面。但这是无法预知的，因而该算法无法实现。它在固定分配页面方式中可保证获得最低的缺页率。,绷块姻淘鼠卷赊拨翌购蘸窿呸横朵蓖香争版首顶欣碳朗践跪通惕云赋剩菌操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,2、先进先出页面置换算法,该算法总是淘汰最先调入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现时把一个进

45、程已调入内存的页面按先后次序链接成一个队列，并设置一个替换指针，指向最老页面。,阴谤铜鲍多大陋焊鬼慷茂豌庄臂奶袁蜀蔑何滩垣苔诸检蝶逐僧骡稻罩橙氢操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,最近最久未使用页面淘汰算法（LRU）,选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页 实现代价很高 软件方法或硬件方法,锡岗仁卒闯矫玲捅叶迷抹靡侩他怒澄摹键柔封撞退歇固氰舔榨粪泥诡微更操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,LRU软件解法：,设置一个页号栈，当一个页面被访问时，就立即将它的页号压入

46、页号栈，并检查页号栈中是否有与刚压入栈顶的相同的页号，若有，则从页号栈中抽出，以保证页号栈中无相同的页号。当系统要淘汰一节时，总是从页号栈底取出一个页号淘汰，即淘汰的页是最久未使用的。,瘩疑胯票彪凭剑袒哦筷链仆雄蛮旅整族禁喉岔赣循敏轿助灰墒捧荒辱悔锑操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,LRU近似算法：Clock算法,在页表中增加一访问位，每当访问一页时，将该页的访问位由硬件置1，软件周期（T）性地将所有访问位置0。在时间T内，访问过的页其访问位为1，反之为0，淘汰为0 的页。缺点：T难定。太小，访问位为0的页相当多，所选的不一定是最久未用的。太大，

47、所有页的引用位可能都为1，找不到合适的淘汰页。,屹阶髓卞吨酋咳左积淄城接甘鼠肪呢挟霍畦胁赵晶逸捏库戮啥鞘弘痉疮硼操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,最不经常使用（LFU）,选择访问次数最少的页面淘汰之 与LRU的硬件解法类似。,饼撤但疽峨朴惫俗贞孟汛重棚辱乐抽耙斌坪秃践碉师馈撮伎圣帮跋司泌促操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,页面缓冲算法(PBA:Page Buffering Algorithm),页面缓冲算法采用了可变分配和局部置换方式 页面缓冲算法中，设置了两个链表（队列）存放被淘汰的页：空闲页链表

48、（实际上就是空闲物理块链表：页面未修改）已修改页面链表。,屉男轨斑贝鄂铂瘴邻绍鸿贷懦咬侨香杏打捧谓屋凰要熙拼芋治晋苏驻柱驰操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,当需要读入一个页面时，便利用空闲物理块链表中的第一个物理块来装入。当有一个未被修改的页要换出时，并不将它换出内存，而是直接把它所在的物理块挂在空闲页链表的末尾。换出一个已修改的页面时，则将其所在的物理块挂在修改页面链表的末尾。注：换出页面时，页面在内存并不做物理上的移动，只是将页表中的表项移到上述两个链表之一中。,撂秤唉沼蚜臆罗橙龙哪捧屠副俘藻卷七鼻钡有毫臂肉茫抡叁零骋替筋饮泉操作系统原理算法

49、-me操作系统原理算法-me,2023/9/7,内存管理置换算法,优点：可使已被修改的页面和未被修改的页面，都仍留在内存中。当进程以后再次访问这些页面时，就有可能只须花费较小的开销。只有当被修改页面达到一定数量，例如64个页面时，再将它们一起写回到磁盘，从而显著地减少了磁盘IO的操作次数。,爪踌舍康猖闯椰绦税穆德筐切思缨杉贴烧冗篱杜帐求寿邦典梁踪硕脯蔼浸操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,某程序在内存中分配三个块，访问页的顺序为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、LRU、OPT算法分别计算缺页次数假设开始时所有页均不在内存,

50、例1,绢脉冒婴午锋励广雪害征宜帧遗粱围铲查黎瘩摘肘撤哥孜击押菜症治恍俏操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,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,撰宋彝花秩叼织句犀岿嘴闺盂衅熊粕奶帖棋友傅涨档庙煞吮摧铆郁欠术豪操作系统原理算法-me操作系统原理算法-me,2023/9/7,内存管理置换算法,LRU 4 3 2 1 4 3 5 4