操作系统第2章第二节课件

2.3进程同步进程同步是指对多个相关进程在执行次序上进行协调，目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的—互斥）。用来实现同步的机制称为同步机制。如：信号量机制；管程机制。紊己吕彭钧诸奢编搬锌雨未涉泵倚尔戏溺返碱壶陀辣细里藏羞隐湿慑话竹操作系统第2章第二节操作系统第2章第二节2.3进程同步进程同步是指对多个相关进程在执行次序上进行协1一.进程同步的基本概念1.两种形式的制约关系2.临界资源、临界区3.同步机制应遵循的规则二.信号量机制1.整型信号量2.记录型信号量3.AND型信号量集、一般信号量集三.信号量的应用1.信号量实现进程互斥2.信号量描述进程间的前趋关系2.3进程同步旋逼祷藐君丙倍刑侦郑琳董狙畅秦奴罪腿蹬传胶诡撒质槐衔各婪氧壁盖搁操作系统第2章第二节操作系统第2章第二节一.进程同步的基本概念2.3进程同步旋逼祷藐君丙倍刑侦郑琳2一、进程同步的基本概念1、两种进程关系系统中诸进程之间在逻辑上存在着两种制约系：进程同步：直接制约关系，进程之间为了协作完成某项任务而有意识地相互“交换信息”。如前分别将I、C和P都看成是进程。进程互斥：间接制约关系，进程之间通过竞争系统某些资源产生的关系。原因是某些资源不能同时被多个进程使用六庄哪荚损吮娇奶戚锨笑驭挛欠拘曾蔡苦侦征叶厦苟匝恐仓褥峙兵耍熄凡操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念1、两种进程关系进程同步：直接制约关系3间接制约关系示例用户ACPU打印机(系统负责打印)打印请求CPU空闲用户B打印请求A打印完A完成B打印完CPU空闲B完成A打印B打印A进入等待打印完成阻塞队列B进入申请打印机阻塞队列A被唤醒从阻塞进入就绪队列,后投入运行;B分配打印机B被唤醒从阻塞进入就绪队列,后投入运行砧打震盆舔咆河逊僻异吕脊宁绳傣店臂镣搐怯奔益好敌词落概唾琉均赣孰操作系统第2章第二节操作系统第2章第二节间接制约关系示例用户ACPU4一、进程同步的基本概念同步互斥进程-进程进程-资源-进程时间次序上受到某种限制竞争不到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间通讯制约例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间例：交通十字路口，单轨火车的拨道岔丸泡绰涤美伟轮碍噎舆虑妻宇惫受较骚滋严跨槛阁戎凋逊波升嚼肤突简荫操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念同步互斥进程-进程进程-资源52、临界资源、临界区一、进程同步的基本概念临界资源(criticalresource）

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。临界区（互斥区，criticalsection）在进程中涉及到临界资源的程序段叫临界区，多个进程的临界区称为相关临界区。肮徘埔寄童接封笨贪潦聘肄瓦圾瞳浪裁衣变痪浙轿呻断胰钳寥艰荔琐姑邵操作系统第2章第二节操作系统第2章第二节2、临界资源、临界区一、进程同步的基本概念临界资源(cri6一、进程同步的基本概念2、临界资源、临界区程序段1共享变量程序段2程序段3临界区示意图汪妙堰积耀鸟阅傍碾簿殴败搏职蹦痴层午祭食地豢允眩溢郎季惩玉武态窒操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念2、临界资源、临界区程序共享变量程序程7例：生产者-消费者(producer-consumer)问题。varn:integer；typeitem=…；varbuffer:array［0，1，…，n-1］ofitem；in，out:0，1，…，n-1；counter:0，1，…，n；一、进程同步的基本概念2、临界资源、临界区柄洗晒劝刁幅邹疼壶蓟州鸿然宜曲茫申畸瘦抠捣既弹帽诞麻羞排刷橇堪潜操作系统第2章第二节操作系统第2章第二节例：生产者-消费者(producer-consumer)问题8producer:repeatproduceaniteminnextp；whilecounter=ndono-op；Buffer[in]:=nextp；in:=(in+1)modn；counter:=counter+1；untilfalse；consumer:repeatwhilecounter=0dono-op；nextc:=buffer[out]；out:=(out+1)modn；counter:=counter-1；consumertheiteminnextc；untilfalse；一、进程同步的基本概念2、临界资源、临界区刊怀犁周陪朵斤商厢忌你更呼狠饱耕虱秉壹闻奉躬捻豺凯柒询梳站昭镁窍操作系统第2章第二节操作系统第2章第二节producer:consumer:一、进程同步的基本概念9生产者对counter做加1操作，消费者对counter做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；一、进程同步的基本概念2、临界资源、临界区某渤限认曾亨芦率哑瑚眯葱铝庇靖域圭墙婉插纽削轧革研拴厕住持退搔颠操作系统第2章第二节操作系统第2章第二节生产者对counter做加1操作，消费者对counter做减10register1:=counter； (register1=5)register1:=register1+1； (register1=6)register2:=counter； (register2=5)register2:=register2-1；(register2=4)counter:=register1； (counter=6)counter:=register2； (counter=4)一、进程同步的基本概念2、临界资源、临界区蹦铃陌它揭渴坛翘挡损祈胸呜覆蹿赐垣友葡结秀斡涸霍趾绞炯扯丘主昭忆操作系统第2章第二节操作系统第2章第二节register1:=counter； (re11一、进程同步的基本概念register2:=counter；register2:=register2-1；register1:=counter；counter:=register2；register1:=register1+1；counter:=register1；2、临界资源、临界区厉刨绩榆摇瘪埠汲祭葛贿篡稗珍那徒窑戳班启库锹悍毒拈融弧凌婿沁当此操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念register2:=counter；122、临界资源、临界区一、进程同步的基本概念实现各进程互斥进入临界区进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entrysection)。在临界区后面加上一段称为退出区(exitsection)的代码。while(1){进入区代码;临界区代码;退出区代码;其余代码;}进入区临界区退出区剩余区烘注迭粉卫伦崇鹃密锋檄榜锹奴橱统黔逞汞对驱饮篷师彭缎茁尸彤离力棚操作系统第2章第二节操作系统第2章第二节2、临界资源、临界区一、进程同步的基本概念实现各进程互斥进入13进程中访问临界资源的代码段在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志用于将“正在访问临界区”标志清除代码中的其余部分进程同步研究如何编写进入区和退出区代码并发进程代码示意图呛胞署爬螺淀互兼颂坪头复命溪湍从立竟毅棱伙崩癸厌嗅滁煤沉察绵踩泉操作系统第2章第二节操作系统第2章第二节进程中访问临界资源的代码段在进入临界区之前，检查可否进入临界143、同步机制应遵循的规则

各进程需要互斥访问临界资源，即不能同时进入各自的临界区。应遵守的原则：有空让进:无进程在临界区时，要求进入临界区的进程可进入。互斥（忙则等待）:不允许两个以上的进程同时进入临界区。有限等待：要求进入临界区的进程不能无限等待,以免陷入“死等(饥饿)”。让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。一、进程同步的基本概念刨竞师狱搀遵隔州氮互画脖裕弗瑰沈锅羡轮拌犀在怀蛋扬披嫡星瞥据绎涂操作系统第2章第二节操作系统第2章第二节3、同步机制应遵循的规则

各进程需要互斥访问15二、信号量机制信号量机制是荷兰科学家E.W.Dijkstra在1965年提出的一种同步机制，由最初的整型信号量发展为记录型信号量，进而发展为信号量集。基本原则在多个相互制约的进程之间使用简单的信号来同步，一个进程被强制停止在一个特定的地方直到收到一个专门的信号。公屎戳分骋函甘愉婴钙粪瓦茨埠改扎控静尿参数淤歼斧架雾攘抵尽跺祸姐操作系统第2章第二节操作系统第2章第二节二、信号量机制信号量机制是荷兰科学家E.W.Dijkstra161、整型信号量整型信号量——非负整数，除了初始化外，只能通过两个原子操作wait和signal来访问。wait和signal操作描述：wait(S)：whileS0donoop;//测试有无可用资源

S:=S-1;//可用资源数减一个单位signal(S)：S:=S+1;主要问题：只要S0，wait操作就不断地测试(忙等)，因而，未做到“让权等待”。

杉羡层福足痛檄臼尔肿醛剑蚂醒汤哥杀症迂辟铃羊萨隙抒凭砧吃昼逗俞驾操作系统第2章第二节操作系统第2章第二节1、整型信号量整型信号量——非负整数，除了初始化外，只能通过172、记录型信号量基本思想1、设置一个整型变量value代表资源数目2、设置一个链接所有等待进程的链表3、初始化一次后，仅能被wait(S)和signal(S)两个原语操作(同步原语，也称为P、V操作)访问记录型信号量的数据结构strucsemaphore{value:integer;//可用资源个数，初值>=0L:listofprocess；//等待该资源的进程队列，初值为空}琵芹独谱悦遏和酪白摇萧序橙箔篱替莱杰警簿饵恐瘸煌杰咕丫肄躲沛喝懂操作系统第2章第二节操作系统第2章第二节2、记录型信号量基本思想琵芹独谱悦遏和酪白摇萧序橙箔篱替莱杰182、记录型信号量信号量的一般结构及PCB队列信号量的声明：semaphoreS;是娄店夫脑鸯酶呼地想钠垣洁螺瓤卞懈猿头秸履匣搂恩赁揉让晒寐屯加撼操作系统第2章第二节操作系统第2章第二节2、记录型信号量信号量的一般结构及PCB队列信号量的声明：s192、记录型信号量P、V操作定义P(S)//=wait(S){S.value=S.value-1;if(S.value<0)block(S.L);}若申请资源不成功，则该进程阻塞，将该进程的PCB插入等待队列S.L的末尾；若申请成功，则进程继续。矛锥溅遏焊江溶晒脑符棠此容堂酿棍蒂狭厨桥娩滥毕黍掏珠交矛坝肉倦咳操作系统第2章第二节操作系统第2章第二节2、记录型信号量P、V操作定义P(S)//=202、记录型信号量V(S)//signal(S){S.value=S.value+1;if(S.value<=0)wakeup(S.L);}P、V操作定义唤醒等待队列S.L中等待的一个进程。该进程继续。扒啊呀蹲朱慢皱拉纂剩犹丘催皆剪扁烬聚棉扒寂嫌邢祷次桃德庞寻颖棕憨操作系统第2章第二节操作系统第2章第二节2、记录型信号量V(S)//signal(S)P、V操212、记录型信号量S.value的物理含义>0：表示有S.value个资源可用。S.value的初值应≥0=0：表示无资源可用且无进程在等待该资源<0：表示有|S.value|个进程在等待该资源P、V操作的含义 P(S)：表示申请一个资源(结果成功或不成功) V(S)：表示释放一个资源祥数眷煽懈拖圣壁磨另沸泣骂峡物拎淬违寻站涯挑嗓谊岛束匪曰膏乓熬讫操作系统第2章第二节操作系统第2章第二节2、记录型信号量S.value的物理含义祥数眷煽懈拖圣壁磨另22AND型信号量的基本思想将进程在整个运行过程中所需要的所有临界资源一次性全部分配给进程，待进程使用完后再一起释放。只要有一个资源未能分配给进程，其它所有可能分配的资源也不分配给该进程。从而可避免死锁发生。在wait操作中，增加了一个“AND”条件，故称为AND同步。3、信号量集---AND型信号量笑葵积温船朱相角帧废断棉贤寻善家绣仓述卯慕效毛靡浆啤揣芯棋额蒂啼操作系统第2章第二节操作系统第2章第二节AND型信号量的基本思想3、信号量集---AND型信号量笑葵233、信号量集---AND型信号量

Swait(S1,S2,…,Sn) //P原语{while(1){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时for(i=1;i<=n;++i)--Si;}else{//某些资源不够时block(S.L);}}Ssignal(S1,S2,…,Sn) //V原语略；见书惺爪乳庭摩最饲丰准研薪梨澡谤瓦遵仟氦慈哉恳莽躇莎磐扬蔚友备叼雾获操作系统第2章第二节操作系统第2章第二节3、信号量集---AND型信号量

Swait(S1,S243、信号量集---一般信号量一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。波回懂浦亢导辛升答亢寻得告绑户险观阿圣扒院料迟题前眺溃濒征壳滇痪操作系统第2章第二节操作系统第2章第二节3、信号量集---一般信号量一般信号量集是指同时需要多种资源25三、信号量的应用利用信号量实现进程互斥：互斥信号量(公用信号量)利用信号量实现进程同步：同步信号量(私有信号量，资源信号量)弥膊杰建妖菊梯毁苯猾津荡谦虫守旱赚把叛钧演彩赏都申撅辣众榴堑曝拦操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现进程互斥：互斥信号量(公用信号26三、信号量的应用利用信号量实现进程互斥有多个进程互斥访问某类资源，则互斥进程Pi的代码如图所示(mutex初值为该类资源初始可用个数)摊曝设惨站恒锈片贞瞅干许杜翅辕栏鬼拖宰审宛萤怨墟煌洪迷焙借粮誓入操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现进程互斥有多个进程互斥访问某类27P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)三、信号量的应用寓谬支嘎档得配怎锹克虞梧翁诞镀噶公敷项隙忽珊类蛙乙士桩院红赶鸳告操作系统第2章第二节操作系统第2章第二节P(mutex)V(mutex)P1P2P3互斥区P(mut28三、信号量的应用例：三个进程共用两个I/O缓冲区。解：为缓冲区设置一个互斥信号量S，S.value=2，表示可用缓冲区有2个。办瞪牛寸漂伏拔哗脱卉挑京拂三燃疾条嘿沤达厉惋柱宏怒吻现艾粒冠喇祷操作系统第2章第二节操作系统第2章第二节三、信号量的应用例：三个进程共用两个I/O缓冲区。办瞪牛寸漂29三、信号量的应用进程互斥问题解题思路一类临界资源设置一个互斥信号量mutex，初值为其可用个数(如打印机台数)，一般为1所有互斥进程在进入区执行P(mutex)，退出区执行V(mutex)；次序不能颠倒P和V操作成对出现。遗漏P操作则不能保证互斥访问，遗漏V操作则可能造成死锁癣韩膏派浪胳笛倒署峦碰拉赢堆蚕凉翁佐睡起强翱酱左狱终肃矽拳抚模决操作系统第2章第二节操作系统第2章第二节三、信号量的应用进程互斥问题解题思路癣韩膏派浪胳笛倒署峦碰拉30利用信号量实现前驱关系P1P2三、信号量的应用设置一个信号量S，S=0P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2为每个前趋关系设置一个同步信号量，其初值为0胞编拇窍毁映鸳相抖嫂朋仟苔皆瘴街知寂方类克酣险庇皆约亢警盔痔婴齐操作系统第2章第二节操作系统第2章第二节利用信号量实现前驱关系P1P2三、信号量的应用设置一个信号量31三、信号量的应用例:程序前趋图如图所示，试用P、V操作实现其同步。vara,b,c,d:semaphore:=0,0,0,0;begincobegins1;s2;s3;s4;coend;end;s1s2s3s4abcds1:begin…;v(a);end;

s2:begin…v(b);v(c);end;

s3:beginp(a);p(b);

…v(d);end;s4:beginp(c);p(d);

...end;利用信号量实现前驱关系壕轨纹抿喧台切籍瓣概钎丰童肮靳下油型级销菠律苹企深联巡付翟操慷朋操作系统第2章第二节操作系统第2章第二节三、信号量的应用例:程序前趋图如图所示，试用P、V操作实现32三、信号量的应用思考：已知一个求值公式（A2+3*B）/（B+5*A），若A、B已赋值，画出该公式求值过程的前趋图利用信号量实现前驱关系堵番祟央肮荚擎此拳裳拟你鹤介栋骑呢旱成缝宗持疫势鳞追娶咎盐耀忙娠操作系统第2章第二节操作系统第2章第二节三、信号量的应用思考：已知一个求值公式（A2+3*B）/（B33三、信号量的应用利用信号量实现同步生产者-消费者问题的单缓冲区情况：有A、B两个进程和一个缓冲区，A负责将信息存入缓冲区，B负责取走缓冲区中的信息进行加工。如何利用信号量实现进程同步？消费者生产者讼饼迈颈疹鸟腮屹争揭督瓜疙口迁践案用蛇赵侯奸眯音晒吩瞳逝河无溺球操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现同步生产者-消费者问题的单缓冲34三、信号量的应用利用信号量实现同步解：设两个同步信号量。S1：缓冲区是否满，初值为0；S2：缓冲区是否空，初值为1淖衣参趾瓣毫咨般窒捉娱铬俏传雍毖甘瑚氏挟荐霹芽快纽刷位宙菌献筐剧操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现同步淖衣参趾瓣毫咨般窒捉娱铬俏35三、信号量的应用进程同步问题的解题思路有几类同步进程，就设几个同步信号量。设定信号量初值。同一信号量的P、V操作要成对出现，但分别在不同进程的代码中。顽凑法餐损褒购补辰丘牵矽卵沏谭嗡抨藩凤人状谨糊末友猫阂跺妆赤穆问操作系统第2章第二节操作系统第2章第二节三、信号量的应用进程同步问题的解题思路顽凑法餐损褒购补辰丘牵362.4经典进程的同步问题生产者—消费者问题生产者与消费者互斥访问公用数据缓冲区生产者生产“数据”，消费者消费“数据”哲学进家餐问题读者—写者问题持撂雏补爽崖祟送疤胁吾发忍储网蛰卖砚钮傍碌刊隧卑泌师胖似咳掩谣蔫操作系统第2章第二节操作系统第2章第二节2.4经典进程的同步问题生产者—消费者问题持撂雏补爽崖祟送371、“生产者—消费者”问题多缓冲区的生产者—消费者问题描述一组生产者向一组消费者提供消息，它们共享一个有界(k个)缓冲池，生产者向其中投放消息，消费者从中取得消息。任何时刻只能有一个进程可对共享缓冲池进行操作。烦皂坐拯麦陀唬届柳沫后大匪辑钙睬溯滞缘费蒜沁询疵长而牌镁尝纫遂桅操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题多缓冲区的生产者—消费者问题描述烦381、“生产者—消费者”问题PCCPPCPC锌演豺拥汀林皇堡靳帛弓咏缔眶冗洋赵已继嫉蝶芬征鞭自锋乌燕劣那谩颧操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题PCCPPCPC锌演豺拥汀林皇堡靳391、“生产者—消费者”问题多缓冲区的同步互斥问题

同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：所有进程应互斥使用缓冲池这一临界资源。吨涉且挑娠肮章镜孺裕茅悼滩碴瞩彤粳灸患彩壹戴钦桐坊湘匙迁辆扒蛮真操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题多缓冲区的同步互斥问题吨涉且挑娠40多缓冲区的生产者─消费者问题解法1、“生产者—消费者”问题设置两个同步信号量及一个互斥信号量empty：空缓冲单元的数目，其初值为k。full：满缓冲单元的数目（即产品数目），其初值为0。mutex:

所有进程都是互斥访问缓冲池的，所以设一个互斥信号量mutex，初值是1，表示缓冲池的访问权，整个缓冲池是一个临界资源。打灶包湛颂恫壮摊慢青逮遍藕拯狠左灸绣甚车剿曹榔炊球治礁全挟绘柄玻操作系统第2章第二节操作系统第2章第二节多缓冲区的生产者─消费者问题解法1、“生产者—消费者”问题411、“生产者—消费者”问题多缓冲区的生产者─消费者问题解法思考：P操作的顺序可换吗？“生产者—消费者”问题的算法描述：梅匈傀恼悦睫杖经躲壳诵乾毋孕攘放郡当窍奄酒屈喳非习凭戚烬殊意楚终操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题多缓冲区的生产者─消费者问题解法思42Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,k-1]ofitem; in,out:integer:=0,0;begincobegin

producer:begin repeatproduceanitemnextp;

P(empty);

P(mutex); buffer(in):=nextp; in:=(in+1)modn;

V(mutex); V(full); untilfalse;

end

consumer:begin repeat P(full);

P(mutex); nextc:=buffer(out); out:=(out+1)modn;

V(mutex);

V(empty); consumetheiteminnextc; untilfalse;

endcoendend氟乎翰七雨奔再鸽男褪误戌税捏森拿粒消袒地撒岭扦拨莽蹲貉辖敌釜肃版操作系统第2章第二节操作系统第2章第二节Varmutex,empty,full:semap43注意1.互斥信号量的P、V操作在每一程序中必须成对出现1、“生产者—消费者”问题2.资源信号量(full,empty)的P、V操作也必须成对出现，但分别处于不同的程序中3.P操作的次序不能颠倒：先检查同步信号量，再检查互斥信号量。否则可能死锁横氧懈撤经羊粒掇此孔著带瓜殉常曾逾镊矾悍左腑索耀皆椎皇侠趋示吏读操作系统第2章第二节操作系统第2章第二节注意1.互斥信号量的P、V操作在每一程序中必须成对出现1、“442、“哲学家进餐”问题5个哲学家围圆桌而坐，每人面前有一只空盘子，每2人之间放一只筷子；哲学家的动作包括思考和进餐，进餐时需要拿起他左右两边的两只筷子，思考时则将两只筷子放回原处。如何保证哲学家们的动作有序进行？问题描述个租姆满矾龋厅嚎蠕延贬墒圆胶鸣些悟蚤窄全偿杯宴融世算臂加涸丫圆赂操作系统第2章第二节操作系统第2章第二节2、“哲学家进餐”问题5个哲学家围圆桌而坐，每人面前有一只空45求解进程同步与互斥问题注意事项进程应该先申请同步信号量，再申请互斥信号量；释放顺序不要求，但建议嵌套出现任何信号量的P和V操作都必须成对出现对互斥信号量的操作成对出现在同一进程中对同步信号量的操作成对出现在不同进程中在生产者消费者问题中，若只有一个缓冲区，则不需要互斥信号量叫厚参课存笼尚前清券公帛颇呐蓟铬请欣苗瓢执墙防予诌捅萍岸芦坚座奉操作系统第2章第二节操作系统第2章第二节求解进程同步与互斥问题注意事项进程应该先申请同步信号量，再申46进程同步与互斥问题解题思路分清哪些是互斥问题(互斥访问临界资源)，哪些是同步问题(具有前后执行顺序要求，一个进程的操作结果影响另一个进程的操作)。一类临界资源设置一个互斥信号量，初值为其可用个数，一般为1，代表一次只允许一个进程访问临界资源。有几类同步进程，就设几个同步信号量。一个同步信号量表示一类同步进程是否可以开始或已经结束。旁狂坦祟匪袱溺值面凛牛浇现夷硫符拌污栅测昨矮滁蹄胆犯朴谎辅抄考烤操作系统第2章第二节操作系统第2章第二节进程同步与互斥问题解题思路分清哪些是互斥问题(互斥访问临界资47同步与互斥的解题步骤确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。确定同步互斥关系。根据使用的是临界资源还是处理的前后关系，确定同步与互斥，然后确定信号量的个数、含义及对信号量的P、V操作。用类C语言描述同步或互斥算法。悍拌卓凰随受暗胳野孤束牢酶莉著坚赔疡助屉戌祈愚谩液旱保衫岩绘涨面操作系统第2章第二节操作系统第2章第二节同步与互斥的解题步骤确定进程。包括进程的数量、进程的工作内容48读者写者问题有两组并发进程:读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作咙蠢韭痒了器举穷吻纵施尚惭鄙数移猴况暖尚亮呜落椎账钟漓擦劫获狡固操作系统第2章第二节操作系统第2章第二节读者写者问题有两组并发进程:咙蠢韭痒了器举穷吻纵施尚惭鄙数49如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待券室羔毁挝估讥笨烹牡熬炙韦蛆雨筏尘准菜案睹矽奇奔弃加裕禄反尾蠢听操作系统第2章第二节操作系统第2章第二节如果读者来：券室羔毁挝估讥笨烹牡熬炙韦蛆雨筏尘准菜案睹矽奇奔50读者写者问题的解法读者：while(true){P(rmutex);if(readcount==0)P(w); readcount++;V(rmutex);读P(rmutex);readcount--;if(readcount==0)V(w);V(rmutex);};写者：while(true){P(w);写V(w);};Mutex=1,readcount=0,w=1嫉埂蹭憨细陛皮樱凹盔螺郸毅雕祟殿申闪茫桂硕娃组童煎讽蛛倪潮德乔傈操作系统第2章第二节操作系统第2章第二节读者写者问题的解法读者：写者：Mutex=1,readcou51

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。第一个顾客到来时，它必须叫醒理发师。如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。如何用信号量解决理发师问题？思考题吹祖勒琵惨狗游偿贮批煽茵蝴壕芋汉嘘盆喧丸烦紊藕腺畅扣宜疥井氖坏巢操作系统第2章第二节操作系统第2章第二节理发店里有一位理发师、一把理发椅和n52varwaiting:integer;/*等候理发的顾客数*/

CHAIRS:integer;/*为顾客准备的椅子数*/

customers,barbers，mutex:semaphore;

waiting:=0;

CHAIRS:=n;

customers:=0;barbers:=0;waiting:=0;mutex:=1;

Procedurebarber;

begin

P(cutomers);/*若无顾客,理发师睡眠*/

P(mutex);/*进程互斥*/

waiting:=waiting–1;/*等候顾客数少一个*/

V(barbers);/*理发师去为一个顾客理发*/

V(mutex);/*开放临界区*/

cut-hair();/*正在理发*/

end;

积莲湛耿龟问剖箭忿鸽密柯凌类辆慢粗吨堰书衙咯条各延管谆溯千什灾趋操作系统第2章第二节操作系统第2章第二节varwaiting:integer;/*等候理发的53procedurecustomer

begin

P(mutex);/*进程互斥*/

ifcustomers<nthen

waitingwaiting:=waiting+1;/*等候顾客数加1*/

V(customers);/*必要的话唤醒理发师*/

V(mutex);/*开放临界区*/

P(barbers);/*无理发师,顾客坐着养神*/

get-haircut();/*一个顾客坐下等理发*/

else

V(mutex);/*人满了,走吧!*/

end;奸健绘狄咨窄菇试盼氧差阻有祖资一贤硒拼瑟垮稍菊阑阔缮歪蚁嫌搓温乓操作系统第2章第二节操作系统第2章第二节procedurecustomer

begin

P(m542.3进程同步进程同步是指对多个相关进程在执行次序上进行协调，目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的—互斥）。用来实现同步的机制称为同步机制。如：信号量机制；管程机制。紊己吕彭钧诸奢编搬锌雨未涉泵倚尔戏溺返碱壶陀辣细里藏羞隐湿慑话竹操作系统第2章第二节操作系统第2章第二节2.3进程同步进程同步是指对多个相关进程在执行次序上进行协55一.进程同步的基本概念1.两种形式的制约关系2.临界资源、临界区3.同步机制应遵循的规则二.信号量机制1.整型信号量2.记录型信号量3.AND型信号量集、一般信号量集三.信号量的应用1.信号量实现进程互斥2.信号量描述进程间的前趋关系2.3进程同步旋逼祷藐君丙倍刑侦郑琳董狙畅秦奴罪腿蹬传胶诡撒质槐衔各婪氧壁盖搁操作系统第2章第二节操作系统第2章第二节一.进程同步的基本概念2.3进程同步旋逼祷藐君丙倍刑侦郑琳56一、进程同步的基本概念1、两种进程关系系统中诸进程之间在逻辑上存在着两种制约系：进程同步：直接制约关系，进程之间为了协作完成某项任务而有意识地相互“交换信息”。如前分别将I、C和P都看成是进程。进程互斥：间接制约关系，进程之间通过竞争系统某些资源产生的关系。原因是某些资源不能同时被多个进程使用六庄哪荚损吮娇奶戚锨笑驭挛欠拘曾蔡苦侦征叶厦苟匝恐仓褥峙兵耍熄凡操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念1、两种进程关系进程同步：直接制约关系57间接制约关系示例用户ACPU打印机(系统负责打印)打印请求CPU空闲用户B打印请求A打印完A完成B打印完CPU空闲B完成A打印B打印A进入等待打印完成阻塞队列B进入申请打印机阻塞队列A被唤醒从阻塞进入就绪队列,后投入运行;B分配打印机B被唤醒从阻塞进入就绪队列,后投入运行砧打震盆舔咆河逊僻异吕脊宁绳傣店臂镣搐怯奔益好敌词落概唾琉均赣孰操作系统第2章第二节操作系统第2章第二节间接制约关系示例用户ACPU58一、进程同步的基本概念同步互斥进程-进程进程-资源-进程时间次序上受到某种限制竞争不到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间通讯制约例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间例：交通十字路口，单轨火车的拨道岔丸泡绰涤美伟轮碍噎舆虑妻宇惫受较骚滋严跨槛阁戎凋逊波升嚼肤突简荫操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念同步互斥进程-进程进程-资源592、临界资源、临界区一、进程同步的基本概念临界资源(criticalresource）

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。临界区（互斥区，criticalsection）在进程中涉及到临界资源的程序段叫临界区，多个进程的临界区称为相关临界区。肮徘埔寄童接封笨贪潦聘肄瓦圾瞳浪裁衣变痪浙轿呻断胰钳寥艰荔琐姑邵操作系统第2章第二节操作系统第2章第二节2、临界资源、临界区一、进程同步的基本概念临界资源(cri60一、进程同步的基本概念2、临界资源、临界区程序段1共享变量程序段2程序段3临界区示意图汪妙堰积耀鸟阅傍碾簿殴败搏职蹦痴层午祭食地豢允眩溢郎季惩玉武态窒操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念2、临界资源、临界区程序共享变量程序程61例：生产者-消费者(producer-consumer)问题。varn:integer；typeitem=…；varbuffer:array［0，1，…，n-1］ofitem；in，out:0，1，…，n-1；counter:0，1，…，n；一、进程同步的基本概念2、临界资源、临界区柄洗晒劝刁幅邹疼壶蓟州鸿然宜曲茫申畸瘦抠捣既弹帽诞麻羞排刷橇堪潜操作系统第2章第二节操作系统第2章第二节例：生产者-消费者(producer-consumer)问题62producer:repeatproduceaniteminnextp；whilecounter=ndono-op；Buffer[in]:=nextp；in:=(in+1)modn；counter:=counter+1；untilfalse；consumer:repeatwhilecounter=0dono-op；nextc:=buffer[out]；out:=(out+1)modn；counter:=counter-1；consumertheiteminnextc；untilfalse；一、进程同步的基本概念2、临界资源、临界区刊怀犁周陪朵斤商厢忌你更呼狠饱耕虱秉壹闻奉躬捻豺凯柒询梳站昭镁窍操作系统第2章第二节操作系统第2章第二节producer:consumer:一、进程同步的基本概念63生产者对counter做加1操作，消费者对counter做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；一、进程同步的基本概念2、临界资源、临界区某渤限认曾亨芦率哑瑚眯葱铝庇靖域圭墙婉插纽削轧革研拴厕住持退搔颠操作系统第2章第二节操作系统第2章第二节生产者对counter做加1操作，消费者对counter做减64register1:=counter； (register1=5)register1:=register1+1； (register1=6)register2:=counter； (register2=5)register2:=register2-1；(register2=4)counter:=register1； (counter=6)counter:=register2； (counter=4)一、进程同步的基本概念2、临界资源、临界区蹦铃陌它揭渴坛翘挡损祈胸呜覆蹿赐垣友葡结秀斡涸霍趾绞炯扯丘主昭忆操作系统第2章第二节操作系统第2章第二节register1:=counter； (re65一、进程同步的基本概念register2:=counter；register2:=register2-1；register1:=counter；counter:=register2；register1:=register1+1；counter:=register1；2、临界资源、临界区厉刨绩榆摇瘪埠汲祭葛贿篡稗珍那徒窑戳班启库锹悍毒拈融弧凌婿沁当此操作系统第2章第二节操作系统第2章第二节一、进程同步的基本概念register2:=counter；662、临界资源、临界区一、进程同步的基本概念实现各进程互斥进入临界区进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entrysection)。在临界区后面加上一段称为退出区(exitsection)的代码。while(1){进入区代码;临界区代码;退出区代码;其余代码;}进入区临界区退出区剩余区烘注迭粉卫伦崇鹃密锋檄榜锹奴橱统黔逞汞对驱饮篷师彭缎茁尸彤离力棚操作系统第2章第二节操作系统第2章第二节2、临界资源、临界区一、进程同步的基本概念实现各进程互斥进入67进程中访问临界资源的代码段在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志用于将“正在访问临界区”标志清除代码中的其余部分进程同步研究如何编写进入区和退出区代码并发进程代码示意图呛胞署爬螺淀互兼颂坪头复命溪湍从立竟毅棱伙崩癸厌嗅滁煤沉察绵踩泉操作系统第2章第二节操作系统第2章第二节进程中访问临界资源的代码段在进入临界区之前，检查可否进入临界683、同步机制应遵循的规则

各进程需要互斥访问临界资源，即不能同时进入各自的临界区。应遵守的原则：有空让进:无进程在临界区时，要求进入临界区的进程可进入。互斥（忙则等待）:不允许两个以上的进程同时进入临界区。有限等待：要求进入临界区的进程不能无限等待,以免陷入“死等(饥饿)”。让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。一、进程同步的基本概念刨竞师狱搀遵隔州氮互画脖裕弗瑰沈锅羡轮拌犀在怀蛋扬披嫡星瞥据绎涂操作系统第2章第二节操作系统第2章第二节3、同步机制应遵循的规则

各进程需要互斥访问69二、信号量机制信号量机制是荷兰科学家E.W.Dijkstra在1965年提出的一种同步机制，由最初的整型信号量发展为记录型信号量，进而发展为信号量集。基本原则在多个相互制约的进程之间使用简单的信号来同步，一个进程被强制停止在一个特定的地方直到收到一个专门的信号。公屎戳分骋函甘愉婴钙粪瓦茨埠改扎控静尿参数淤歼斧架雾攘抵尽跺祸姐操作系统第2章第二节操作系统第2章第二节二、信号量机制信号量机制是荷兰科学家E.W.Dijkstra701、整型信号量整型信号量——非负整数，除了初始化外，只能通过两个原子操作wait和signal来访问。wait和signal操作描述：wait(S)：whileS0donoop;//测试有无可用资源

S:=S-1;//可用资源数减一个单位signal(S)：S:=S+1;主要问题：只要S0，wait操作就不断地测试(忙等)，因而，未做到“让权等待”。

杉羡层福足痛檄臼尔肿醛剑蚂醒汤哥杀症迂辟铃羊萨隙抒凭砧吃昼逗俞驾操作系统第2章第二节操作系统第2章第二节1、整型信号量整型信号量——非负整数，除了初始化外，只能通过712、记录型信号量基本思想1、设置一个整型变量value代表资源数目2、设置一个链接所有等待进程的链表3、初始化一次后，仅能被wait(S)和signal(S)两个原语操作(同步原语，也称为P、V操作)访问记录型信号量的数据结构strucsemaphore{value:integer;//可用资源个数，初值>=0L:listofprocess；//等待该资源的进程队列，初值为空}琵芹独谱悦遏和酪白摇萧序橙箔篱替莱杰警簿饵恐瘸煌杰咕丫肄躲沛喝懂操作系统第2章第二节操作系统第2章第二节2、记录型信号量基本思想琵芹独谱悦遏和酪白摇萧序橙箔篱替莱杰722、记录型信号量信号量的一般结构及PCB队列信号量的声明：semaphoreS;是娄店夫脑鸯酶呼地想钠垣洁螺瓤卞懈猿头秸履匣搂恩赁揉让晒寐屯加撼操作系统第2章第二节操作系统第2章第二节2、记录型信号量信号量的一般结构及PCB队列信号量的声明：s732、记录型信号量P、V操作定义P(S)//=wait(S){S.value=S.value-1;if(S.value<0)block(S.L);}若申请资源不成功，则该进程阻塞，将该进程的PCB插入等待队列S.L的末尾；若申请成功，则进程继续。矛锥溅遏焊江溶晒脑符棠此容堂酿棍蒂狭厨桥娩滥毕黍掏珠交矛坝肉倦咳操作系统第2章第二节操作系统第2章第二节2、记录型信号量P、V操作定义P(S)//=742、记录型信号量V(S)//signal(S){S.value=S.value+1;if(S.value<=0)wakeup(S.L);}P、V操作定义唤醒等待队列S.L中等待的一个进程。该进程继续。扒啊呀蹲朱慢皱拉纂剩犹丘催皆剪扁烬聚棉扒寂嫌邢祷次桃德庞寻颖棕憨操作系统第2章第二节操作系统第2章第二节2、记录型信号量V(S)//signal(S)P、V操752、记录型信号量S.value的物理含义>0：表示有S.value个资源可用。S.value的初值应≥0=0：表示无资源可用且无进程在等待该资源<0：表示有|S.value|个进程在等待该资源P、V操作的含义 P(S)：表示申请一个资源(结果成功或不成功) V(S)：表示释放一个资源祥数眷煽懈拖圣壁磨另沸泣骂峡物拎淬违寻站涯挑嗓谊岛束匪曰膏乓熬讫操作系统第2章第二节操作系统第2章第二节2、记录型信号量S.value的物理含义祥数眷煽懈拖圣壁磨另76AND型信号量的基本思想将进程在整个运行过程中所需要的所有临界资源一次性全部分配给进程，待进程使用完后再一起释放。只要有一个资源未能分配给进程，其它所有可能分配的资源也不分配给该进程。从而可避免死锁发生。在wait操作中，增加了一个“AND”条件，故称为AND同步。3、信号量集---AND型信号量笑葵积温船朱相角帧废断棉贤寻善家绣仓述卯慕效毛靡浆啤揣芯棋额蒂啼操作系统第2章第二节操作系统第2章第二节AND型信号量的基本思想3、信号量集---AND型信号量笑葵773、信号量集---AND型信号量

Swait(S1,S2,…,Sn) //P原语{while(1){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时for(i=1;i<=n;++i)--Si;}else{//某些资源不够时block(S.L);}}Ssignal(S1,S2,…,Sn) //V原语略；见书惺爪乳庭摩最饲丰准研薪梨澡谤瓦遵仟氦慈哉恳莽躇莎磐扬蔚友备叼雾获操作系统第2章第二节操作系统第2章第二节3、信号量集---AND型信号量

Swait(S1,S783、信号量集---一般信号量一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。波回懂浦亢导辛升答亢寻得告绑户险观阿圣扒院料迟题前眺溃濒征壳滇痪操作系统第2章第二节操作系统第2章第二节3、信号量集---一般信号量一般信号量集是指同时需要多种资源79三、信号量的应用利用信号量实现进程互斥：互斥信号量(公用信号量)利用信号量实现进程同步：同步信号量(私有信号量，资源信号量)弥膊杰建妖菊梯毁苯猾津荡谦虫守旱赚把叛钧演彩赏都申撅辣众榴堑曝拦操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现进程互斥：互斥信号量(公用信号80三、信号量的应用利用信号量实现进程互斥有多个进程互斥访问某类资源，则互斥进程Pi的代码如图所示(mutex初值为该类资源初始可用个数)摊曝设惨站恒锈片贞瞅干许杜翅辕栏鬼拖宰审宛萤怨墟煌洪迷焙借粮誓入操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现进程互斥有多个进程互斥访问某类81P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)三、信号量的应用寓谬支嘎档得配怎锹克虞梧翁诞镀噶公敷项隙忽珊类蛙乙士桩院红赶鸳告操作系统第2章第二节操作系统第2章第二节P(mutex)V(mutex)P1P2P3互斥区P(mut82三、信号量的应用例：三个进程共用两个I/O缓冲区。解：为缓冲区设置一个互斥信号量S，S.value=2，表示可用缓冲区有2个。办瞪牛寸漂伏拔哗脱卉挑京拂三燃疾条嘿沤达厉惋柱宏怒吻现艾粒冠喇祷操作系统第2章第二节操作系统第2章第二节三、信号量的应用例：三个进程共用两个I/O缓冲区。办瞪牛寸漂83三、信号量的应用进程互斥问题解题思路一类临界资源设置一个互斥信号量mutex，初值为其可用个数(如打印机台数)，一般为1所有互斥进程在进入区执行P(mutex)，退出区执行V(mutex)；次序不能颠倒P和V操作成对出现。遗漏P操作则不能保证互斥访问，遗漏V操作则可能造成死锁癣韩膏派浪胳笛倒署峦碰拉赢堆蚕凉翁佐睡起强翱酱左狱终肃矽拳抚模决操作系统第2章第二节操作系统第2章第二节三、信号量的应用进程互斥问题解题思路癣韩膏派浪胳笛倒署峦碰拉84利用信号量实现前驱关系P1P2三、信号量的应用设置一个信号量S，S=0P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2为每个前趋关系设置一个同步信号量，其初值为0胞编拇窍毁映鸳相抖嫂朋仟苔皆瘴街知寂方类克酣险庇皆约亢警盔痔婴齐操作系统第2章第二节操作系统第2章第二节利用信号量实现前驱关系P1P2三、信号量的应用设置一个信号量85三、信号量的应用例:程序前趋图如图所示，试用P、V操作实现其同步。vara,b,c,d:semaphore:=0,0,0,0;begincobegins1;s2;s3;s4;coend;end;s1s2s3s4abcds1:begin…;v(a);end;

s2:begin…v(b);v(c);end;

s3:beginp(a);p(b);

…v(d);end;s4:beginp(c);p(d);

...end;利用信号量实现前驱关系壕轨纹抿喧台切籍瓣概钎丰童肮靳下油型级销菠律苹企深联巡付翟操慷朋操作系统第2章第二节操作系统第2章第二节三、信号量的应用例:程序前趋图如图所示，试用P、V操作实现86三、信号量的应用思考：已知一个求值公式（A2+3*B）/（B+5*A），若A、B已赋值，画出该公式求值过程的前趋图利用信号量实现前驱关系堵番祟央肮荚擎此拳裳拟你鹤介栋骑呢旱成缝宗持疫势鳞追娶咎盐耀忙娠操作系统第2章第二节操作系统第2章第二节三、信号量的应用思考：已知一个求值公式（A2+3*B）/（B87三、信号量的应用利用信号量实现同步生产者-消费者问题的单缓冲区情况：有A、B两个进程和一个缓冲区，A负责将信息存入缓冲区，B负责取走缓冲区中的信息进行加工。如何利用信号量实现进程同步？消费者生产者讼饼迈颈疹鸟腮屹争揭督瓜疙口迁践案用蛇赵侯奸眯音晒吩瞳逝河无溺球操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现同步生产者-消费者问题的单缓冲88三、信号量的应用利用信号量实现同步解：设两个同步信号量。S1：缓冲区是否满，初值为0；S2：缓冲区是否空，初值为1淖衣参趾瓣毫咨般窒捉娱铬俏传雍毖甘瑚氏挟荐霹芽快纽刷位宙菌献筐剧操作系统第2章第二节操作系统第2章第二节三、信号量的应用利用信号量实现同步淖衣参趾瓣毫咨般窒捉娱铬俏89三、信号量的应用进程同步问题的解题思路有几类同步进程，就设几个同步信号量。设定信号量初值。同一信号量的P、V操作要成对出现，但分别在不同进程的代码中。顽凑法餐损褒购补辰丘牵矽卵沏谭嗡抨藩凤人状谨糊末友猫阂跺妆赤穆问操作系统第2章第二节操作系统第2章第二节三、信号量的应用进程同步问题的解题思路顽凑法餐损褒购补辰丘牵902.4经典进程的同步问题生产者—消费者问题生产者与消费者互斥访问公用数据缓冲区生产者生产“数据”，消费者消费“数据”哲学进家餐问题读者—写者问题持撂雏补爽崖祟送疤胁吾发忍储网蛰卖砚钮傍碌刊隧卑泌师胖似咳掩谣蔫操作系统第2章第二节操作系统第2章第二节2.4经典进程的同步问题生产者—消费者问题持撂雏补爽崖祟送911、“生产者—消费者”问题多缓冲区的生产者—消费者问题描述一组生产者向一组消费者提供消息，它们共享一个有界(k个)缓冲池，生产者向其中投放消息，消费者从中取得消息。任何时刻只能有一个进程可对共享缓冲池进行操作。烦皂坐拯麦陀唬届柳沫后大匪辑钙睬溯滞缘费蒜沁询疵长而牌镁尝纫遂桅操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题多缓冲区的生产者—消费者问题描述烦921、“生产者—消费者”问题PCCPPCPC锌演豺拥汀林皇堡靳帛弓咏缔眶冗洋赵已继嫉蝶芬征鞭自锋乌燕劣那谩颧操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题PCCPPCPC锌演豺拥汀林皇堡靳931、“生产者—消费者”问题多缓冲区的同步互斥问题

同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：所有进程应互斥使用缓冲池这一临界资源。吨涉且挑娠肮章镜孺裕茅悼滩碴瞩彤粳灸患彩壹戴钦桐坊湘匙迁辆扒蛮真操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题多缓冲区的同步互斥问题吨涉且挑娠94多缓冲区的生产者─消费者问题解法1、“生产者—消费者”问题设置两个同步信号量及一个互斥信号量empty：空缓冲单元的数目，其初值为k。full：满缓冲单元的数目（即产品数目），其初值为0。mutex:

所有进程都是互斥访问缓冲池的，所以设一个互斥信号量mutex，初值是1，表示缓冲池的访问权，整个缓冲池是一个临界资源。打灶包湛颂恫壮摊慢青逮遍藕拯狠左灸绣甚车剿曹榔炊球治礁全挟绘柄玻操作系统第2章第二节操作系统第2章第二节多缓冲区的生产者─消费者问题解法1、“生产者—消费者”问题951、“生产者—消费者”问题多缓冲区的生产者─消费者问题解法思考：P操作的顺序可换吗？“生产者—消费者”问题的算法描述：梅匈傀恼悦睫杖经躲壳诵乾毋孕攘放郡当窍奄酒屈喳非习凭戚烬殊意楚终操作系统第2章第二节操作系统第2章第二节1、“生产者—消费者”问题多缓冲区的生产者─消费者问题解法思96Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,k-1]ofitem; in,out:integer:=0,0;begincobegin

producer:begin repeatproduceanitemnextp;

P(empty);

P(mutex); buffer(in):=nextp; in:=(in+1)modn;

V(mutex); V(full); untilfalse;

end

consumer:begin repeat P(full);

P(mutex); nextc:=buffer(out); out:=(out+1)modn;

V(mutex);

V(empty); consumetheiteminnextc; untilfalse;

endcoendend氟乎翰七雨奔再鸽男褪误戌税捏森拿粒消袒地撒岭扦拨莽蹲貉辖敌釜肃版操作系统第2章第二节操作系统第2章第二节Varmutex,empty,full:semap97注意1.互斥信号量的P、V操作在每一程序中必须成对出现1、“生产者—消费者”问题2.资源信号量(full,empty)的P、V操作也必须成对出现，但分别处于不同的程序中3.P操作的次序不能颠倒：先检查同步信号量，再检查互斥信号量。否则可能死锁横氧懈撤经羊粒掇此孔著带瓜殉常曾逾镊矾悍左腑索耀皆椎皇侠趋示吏读操作系统第2章第二节操作系统第2章第二节注意1.互斥信号量的P、V操作在每一程序中必须成对出现1、“982、“哲学家进餐”问题5个哲学家围圆桌而坐，每人面前有一只空盘子，每2人之间放一只筷子；哲学家的动作包括思考和进餐，进餐时需要拿起他左右两边的两只筷子，思考时则将两只筷子放回原处。如何保证哲学家们的动作有序进行？问题描述个租姆满矾龋厅嚎蠕延贬墒圆胶鸣些悟蚤窄全偿杯宴融世算臂加涸丫圆赂操