《经典的进程同步问题》由会员分享，可在线阅读，更多相关《经典的进程同步问题（39页珍藏版）》请在金锄头文库上搜索。
1、2.4 经典的进程同步问题 n2.4.1 生产者/消费者问题 n2.4.2 哲学家进餐问题n2.4.3 读者/写者问题 Date1第三章 进程的描述与控制2.4.1 生产者/消费者问题n生产者消费者问题是一种同步问题的抽象 描述。计算机系统中的每个进程都可以消 费（使用）或生产（释放）某类资源。这 些资源可以是硬件资源，也可以是软件资 源。n当某一进程使用某一资源时，可以看作是 消费，称该进程为消费者。而当某一进程 释放某一资源时，它就相当于生产者。Date2第三章 进程的描述与控制问题描述通过一个有界缓冲区可以把一群生产者 p1,p2,pm，和一群消费者Q1,Q2,Qn 联系起来。如图n 只
2、要缓冲区未满，生产者就可以把产品 送入缓冲区;n 只要缓冲区未空，消费者就可以从缓冲 区中取走物品。Date3第三章 进程的描述与控制有n个缓冲区的缓冲池放产品取产品Date4第三章 进程的描述与控制问题分析n为解决生产者消费者问题，应该设两个同步 信号量:一个说明空缓冲区的数目，用empty 表示，初值为有界缓冲区的大小N，另一个说 明已用缓冲区的数目，用full表示，初值为 。n由于在此问题中有M个生产者和N个消费者， 它们在执行生产活动和消费活动中要对有界 缓冲区进行操作。由于有界缓冲区是一个临 界资源，必须互斥使用，所以，另外还需要 设置一个互斥信号量mutex，其初值为。Date5第
3、三章 进程的描述与控制问题的解Var mutex,empty,full: semaphore :=1,n,0;buffer: array0, , n-1 of item; /缓冲区in,out: integer :=0,0; /输入、输出指针beginparbeginproducer：beginrepeat 生产一个产品nextp; wait(empty); /等待空缓冲区的数目非0 wait(mutex); /等待无进程操作缓冲区 Buffer(in):= nextp; /往Buffer in放产品 in = (in+1) mod n; signal(mutex); /允许其它进程操作缓冲区
4、 signal(full); /增加已用缓冲区的数目until falseendDate6第三章 进程的描述与控制consumer：beginrepeatwait(full); /等待已用缓冲区的数目非0wait(mutex); /等待无进程操作缓冲区nextc := Buffer(out) /从Buffer out取产品out = (out +1) mod n;signal(mutex); /允许其它进程操作缓冲区signal(empty); /增加空缓冲区的数目消费nextc产品;until falseendparendendDate7第三章 进程的描述与控制采用AND信号量集解决生产者-
5、消费者问题Var mutex,empty,full: semaphore :=1,n,0;buffer: array0, , n-1 of item; /缓冲区in,out: integer :=0,0; /输入、输出指针beginparbeginproducer：begin repeat 生产一个产品nextp; swait(empty, mutex); Buffer(in):= nextp; /往Buffer in放产品 in = (in+1) mod n; ssignal(mutex, full); until falseend等待空缓冲区的数 目非0; 等待无进程操作缓 冲区;允许其它
6、进程操作 缓冲区; 增加已用缓冲区的 数目;Date8第三章 进程的描述与控制consumer：beginrepeatswait(full, mutex);nextc := Buffer(out) /从Buffer out取产品out = (out +1) mod n;signal(mutex, empty);消费nextc产品;until falseendparendend等待已用缓冲区的 数目非0; 等待无进程操作缓 冲区;允许其它进程操作 缓冲区; 增加空缓冲区的数 目;Date9第三章 进程的描述与控制【思考题】n如果生产者消费者问题中的缓冲区是无界的 ，又该如何解呢？Date10第三
7、章 进程的描述与控制思考题的解Var mutex, full: semaphore :=1, 0; /因无界，无需 empty信号量buffer: array0, of item; /无界缓冲区in,out: integer :=0,0; /输入、输出指针beginparbeginproducer：begin repeat 生产一个产品nextp; /因无界，不必等待空缓冲区的数目非0 ！ wait(mutex); /等待无进程操作缓冲区 Buffer(in):= nextp; /往Buffer in放产品 in = in+1; /因无界，无需考虑输入指针出界 signal(mutex); /
8、允许其它进程操作缓冲区 signal(full); /增加已用缓冲区的数目 until falseendDate11第三章 进程的描述与控制consumer：beginrepeatwait(full); /等待已用缓冲区的数目非0wait(mutex); /等待无进程操作缓冲区nextc := Buffer(out) /从Buffer out取产品out = out +1; /因无界，无需考虑输出指针出界signal(mutex); /允许其它进程操作缓冲区/因无界，不必增加空缓冲区的数目消费nextc产品;until falseendparendendDate12第三章 进程的描述与控制【思
9、考题】n桌上有一空盘，最多允许存放一只水果。爸 爸可向盘中放一个苹果或放一个桔子，儿子 专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并 发进程的同步。n提示：设置一个信号量表示可否向盘中放水 果，一个信号量表示可否取桔子，一个信号 量表示可否取苹果。Date13第三章 进程的描述与控制解:n设置三个信号量S,So,Sa ，初值分别为1，0，0。S 表示可否向盘中放水果; So可否取桔子; Sa可否取 苹果;Var S,So,Sa: semaphore := 1,0,0;beginparbeginFather ：beginrepeatwait(S); /等待水果盘中
10、有空位置将水果放入盘中;if(是桔子) then signal(So); /置盘中放了桔子标志else signal(Sa); /置盘中放了苹果标志until falseendDate14第三章 进程的描述与控制Son： beginrepeatwait(So); /等待水果盘中放了桔子取盘中桔子;signal(S); /置盘中已无水果标志吃桔子;until falseendDaughter ：beginrepeatwait(Sa); /等待水果盘中放了苹果取盘中苹果;signal(S); /置盘中已无水果标志吃苹果;until falseendparend endDate15第三章 进程的描述
11、与控制【思考题】n若把问题改为: 爸爸只向盘中放苹果，妈妈只 向盘中放桔子，儿子专等吃盘中的桔子，女 儿专等吃苹果。 如何用P、V操作实现爸爸、儿子、女儿4个 并发进程的同步?Date16第三章 进程的描述与控制解:n信号量设置、儿子、女儿进程不变。只需修改父亲进程，并增加母亲进程。Father ：beginrepeatwait(S); /等待水果盘中有空位置将苹果放入盘中;signal(Sa); /置盘中放了苹果标志until falseendMother ：beginrepeatwait(S); /等待水果盘中有空位置将桔子放入盘中;signal(So); /置盘中放了桔子标志until
12、falseend Date17第三章 进程的描述与控制【思考题】n银行的人民币存取业务问题n某银行的人民币存取业务由 n 个柜台工作人 员负责。每个顾客进入银行后先从抽号机中 取一个号，并且等着叫号。当一个柜台工作 人员空闲下来，就叫下一个号。 试用P，V 操作编写柜台工作人员进程和顾客进程的程 序。Date18第三章 进程的描述与控制问题分析1n可把“顾客号数”看成是一个单缓冲区，顾客和柜员必须 互斥访问;nCUSTOMER_NUM -单缓冲区n Semaphore counter; /柜台人员数，初值为nSemaphore customer; /当前等待的顾客数；初值为0；Semaphor
13、e mutex; /互斥对顾客号数的访问。初值为1 Date19第三章 进程的描述与控制思考题的解1Semaphore counter; /柜台人员数，初值为nSemaphore customer ; /当前等待的顾客数；初值为0；Semaphore mutex; /互斥对顾客号数的访问。初值为1 顾客进程： int num;/取号码P(mutex);num = CUSTOMER_NUM+;V(mutex);/等待叫号V(customer); /请求服务P(counter); /等待号接受服务；离开；P(mutex);COSTOMER_NUM-;V(mutex); 柜台人员进程： int nu
14、m;REPEAT/叫号P(customer); /等待顾客请求服务叫号为顾客服务;V(counter); /服务完成UNTIL false; Date20第三章 进程的描述与控制问题分析2n可把“顾客号数”看成是一个单缓冲区，顾客和柜员必须 互斥访问;nCUSTOMER_NUM -单缓冲区 顾客号数nCOUNTER_NUM -单缓冲区 柜台人员编号n Semaphore counter; /柜台人员数，初值为nSemaphore customer; /当前等待的顾客数；初值为0；Semaphore mutex; /互斥对顾客号数的访问。初值为1 Semaphore mutex2; /互斥对柜台
15、人员编号的访问。初值 为1Date21第三章 进程的描述与控制思考题的解2Semaphore counter; /柜台人员数，初值为nSemaphore customer ; /当前等待的顾客数；初值为0；Semaphore mutex,mutex2; /互斥对顾客号数,柜台人员编号的访问。初值为1 顾客进程： int x;/取号码P(mutex);x = CUSTOMER_NUM+;V(mutex);/等待叫号V(customer); /请求服务P(counter); /等待叫号ACTION_CUSTOMER(x); /接受服务； 柜台人员进程： int x;REPEAT/叫号P(customer); /等待顾客请求服务P(mutex2);x = COUNTER_NUM;V(mutex2);ACTION_COUNTER(x); /为顾客服务V(counter); /服务完成UNTIL false; Date22第三章 进程的描述与控制问题分析3n可把抽号机中记录顾客抽号信息的内存区域看成 是一个共享缓冲区，顾客抽取一个号,就如同在 缓冲区中占了一个位子（放了一个“产品”），柜 员叫一个号，就如同从缓冲区中空了一个位子（ 取走一个“产品”），n如果抽号数目不限，则可把该缓冲区看做是一个 无界缓冲区；如果抽号数目有限(如50个)，则可
