实验二（2）进程同步 一、实验目的 1、生产者-消费者问题是很经典很具有代表性的进程同步问题，计算机中的很多同步问题都可抽象为生产者-消费者问题，通过本实验的练习，希望能加深学生对进程同步问题的认识与理解。 2、熟悉VC的使用，培养和提高学生的分析问题、解决问题的能力。 二、实验内容及其要求 1．实验内容 以生产者/消费者模型为依据，创建一个控制台进程，在该进程中创建n个线程模拟生产者和消费者，实现进程(线程)的同步与互斥。 2．实验要求 学习并理解生产者/消费者模型及其同步/互斥规则；设计程序，实现生产者/消费者进程(线程)的同步与互斥； 三、实验算法分析 1、实验程序的结构图（流程图）； 2、数据结构及信号量定义的说明； (1) CreateThread ●功能——创建一个在调用进程的地址空间中执行的线程 ●格式 HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, DWORD dwStackSize,
LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParamiter, DWORD dwCreationFlags, Lpdword lpThread ); ●参数说明 lpThreadAttributes——指向一个LPSECURITY_ATTRIBUTES(新线程的安全性描述符)。dwStackSize——定义原始堆栈大小。 lpStartAddress——指向使用LPTHRAED_START_ROUTINE类型定义的函数。 lpParamiter——定义一个给进程传递参数的指针。 dwCreationFlags——定义控制线程创建的附加标志。 lpThread——保存线程标志符(32位) (2) CreateMutex ●功能——创建一个命名或匿名的互斥量对象 ●格式 HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes, BOOL bInitialOwner, LPCTSTR lpName); bInitialOwner——指示当前线程是否马上拥有该互斥量(即马 ●参数说明 lpMutexAttributes——必须取值NULL。上加锁)。 lpName——互斥量名称。 (3) CreateSemaphore ●功能——创建一个命名或匿名的信号量对象 ●格式 HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCTSTR lpName ); ●参数说明 lpSemaphoreAttributes——必须取值NULL。
1、测量控制系统中的数据采集任务把所采集的数据送一单缓冲区；计算任务则从该缓冲区中取出数据并进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。 Var Sempty，Sfull: semaphore:= 1,0 Begin Parbegin Collection:begin repeat 采集一个数据； wait(Sempty); 数据放入缓冲区； signal(Sfull); untill false; end; Compute:begin repeat wait(Sfull); 从缓冲区取出数据; signal(Sempty); 计算; ` until false; end; Parend End 2、有一阅览室，共有100个座位。读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。读者离开时要注销掉登记内容。试用wait和signal原语描述读者进程的同步问题。 var mutex, readcount :semaphore := 1,100; Begin Parbegin Process Reader:begin repeat wait(readcount); wait(mutex); <填入座号和姓名完成登记>； signal(mutex); <阅读> wait(mutex) <删除登记表中的相关表项，完成注销> signal(mutex); signal(readcount); until false; end; parend; End; 1）、桌上有一空盘，只允许放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子；女儿专吃盘中的苹果，儿子专吃盘中的桔子；试用wait 和signal原语实现爸爸、妈妈、女儿、儿子之间的同步问题。 var Sempty, Sapple, Sorange,: semaphore:= 1,0,0; begin parbegin Father: begin repeat wait(Sempty);
计算机操作系统实验报告题目三大经典问题之生产者与消费者问题 一、课程设计的性质与任务 1、加深对并发协作进程同步与互斥概念的理解。通过编写程序实现进程同步和互斥，使学生掌握有关进程（线程）同步与互斥的原理，以及解决进程（线程）同步和互斥的算法，从而进一步巩固进程（线程）同步和互斥等有关的内容。 2、掌握进程和线程的概念，进程（线程）的控制原语或系统调用的使用。 3、了解Windows2000/XP中多线程的并发执行机制，线程间的同步和互斥。学习使用Windows2000/XP中基本的同步对象，掌握相应的 API函数。 4、培养学生能够独立进行知识综合，独立开发较大程序的能力。 5、培养提高学生软件开发能力和软件的调试技术。 6、培养学生开发大型程序的方法和相互合作的精神。 7、培养学生的创新意识。 8、培养学生的算法设计和算法分析能力。 9、培养学生对问题进行文字论述和文字表达的能力。 二、课程设计的内容及其要求 在Windows?XP、Windows?2000等操作系统下，使用的VC、VB、Java或C等编程语言，采用进程（线程）同步和互斥的技术编写程序实现生产者消费者问题或哲学家进餐问题或读者-写者问题或自己设计一个简单进程（线程）同步和互斥的实际问题。
要求：（1）经调试后程序能够正常运行。 （2）采用多进程或多线程方式运行，体现了进程（线程）同步互斥的关系。 （3）程序界面美观。 三、实验原理 本实验要求利用PV操作实现解决生产者——消费者问题中的同步问题。此问题描述的是一群生产者进程在生产产品并将这些产品提供给消费者进程去消费，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区，消费者进程可从缓冲区中取走产品去消费，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满且尚未取出的缓冲区中投放产品，并且生产者消费者互斥使用缓冲区。 四、实验原理图 五、算法实现 （1）有一个生产者线程ProduceThread，有1个消费者进程CustomerThread；缓冲区为shareList。 （2）使用线程同步：用synchonized关键字（加锁）使得一个时间内只能有一个线程得到执行，另一个线程必须等待当前线程执行完这个代码块以后才能执行该代码块；wait()让线程进入等待状态；notify（）函数唤醒一个处于等待状态的线程。 程序将一直循环运行） （3）
进程同步练习题 1.在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司机 售票员 图司机和售票员工作流程图 2.桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。 3.a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab 段外等待； （2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a 点和b点同时驶入； （3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。 请用信号量为工具，对ab段实现正确管理以保证行驶安全。 4．将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法） 5．一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。
1、有一个仓库可存放A、B两种零件，最大库容量各为m个。生产车间不断地取A和B 进行装配，每次各取一个。为避免零件锈蚀，按先入库者先出库的原则。有两组供应商分别不断地供应A和B，每次一个。为保证配套和合理库存，当某种零件比另一种零件超过n(n 进程同步练习题 1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司机 售票员 图司机和售票员工作流程图 2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。 3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab 段外等待； （2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a 点和b点同时驶入； （3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。 请用信号量为工具，对ab段实现正确管理以保证行驶安全。 4．将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法） 5．一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。 操作系统进程同步实验报告 实验三：进程同步实验 一、实验任务： （1）掌握操作系统的进程同步原理； （2）熟悉linux的进程同步原语； （3）设计程序，实现经典进程同步问题。 二、实验原理： （1）P、V操作 PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1； ②如果S30，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1； ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。（2）信号量 信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作 来改变。 一般来说，信号量S30时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S￡0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。 （3）linux的进程同步原语 ①wait()；阻塞父进程，子进程执行； ②#include 进程同步练习 1．有一阅览室，共有100个座位。读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记内容。试用P、V操作描述读者进程的同步结构。 var mutex : semaphere;信号量，用于互斥 full : semaphere; 信号量，用于同步 table : array 0..n-1 of item; 登记表 procedure reader; 读者进程 begin P(full); P(mutex); Register_name(table)； V(mutex); Reading； P(mutex); Delet_name(table); V(mutex); V(full) end; begin seminitsal,1; ,100); 初始化 cobegin reader; reader; ... coend end. 2．设公共汽车上有一位司机和一位售票员，它们的活动如下： 售票员： 动车辆售票 正常行车开车门 到站停车关车门 请分析司机与售票员之间的同步关系，如何用PV 操作实现。 答：为了安全起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下： 售票员： （S1）售票 动车辆P（S2） 正常行车开车门 到站停车关车门 V（S2）V（S1） 另外，程序中PV操作出现的顺序与信号量的初值设置有关，以本题为例，算法如下描述时，S1、S2的初值均应为0。 售票员： 1、生产者-消费者问题 问题描述是：有一群生产者进程在生产产品，此产品提供给消费者去消费。为使生产者和消费者进程能并发执行，在它们之间设置一个具有n个缓冲池，生产者进程可将它所生产的产品放入一个缓冲池中，消费者进程可从一个缓冲区取得一个产品消费。 问题分析: 设两个同步信号量:一个说明空缓冲区的数目，用empty表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用full表示，初值为0。由于在执行生产活动和消费活动中要对有界缓冲区进行操作。有界缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量mutex，其初值为１。 semaphore mutex=1,empty=n,full=0; item buffer[n]; //缓冲区 int in=out=0; //输入、输出指针 void producer() { while(1) { … 生产一个产品nextp; … wait(empty); //等待空缓冲区的数目非0 wait(mutex); //等待无进程操作缓冲区 buffer[in]= nextp; //往Buffer [in]放产品 in = (in+1) mod n; signal(mutex); //允许其它进程操作缓冲区 signal(full); //增加已用缓冲区的数目 } } void consumer() { while(1) { …… wait(full); //等待已用缓冲区的数目非0 wait(mutex); //等待无进程操作缓冲区 nextc = buffer[out]; //从Buffer [out]取产品 out = (out +1) mod n; signal(mutex); //允许其它进程操作缓冲区 signal(empty); //增加空缓冲区的数目 消费nextc产品; } } main() { cobegin{ producer(); consumer(); } } } 利用AND信号量解决生产者-消费者问题 semaphore mutex=1,empty=n,full=0; item buffer[n]; //缓冲区 int in=out=0; //输入、输出指针 void producer() **理工大学 操作系统课程设计报告 院（系）：计算机工程学院 专业：计算机科学与技术班级：计算111 学生姓名： ** 学号： 201107015 题目：用多进程同步方法演示“生产者-消费者”问题 起迄日期: 2014.07.07-2014.07.18 设计地点:现代教育中心101-103、主教学楼B505 指导教师:王** 2013—2014年度第 2 学期 完成日期: 2014 年 7 月 18 日 一、课程设计目的 本次操作系统课程设计的主要任务是通过研究Linux的进程机制和信号量，实现生产者消费者问题的并发控制。实验中需要设置多个生产者和多个消费者，生产者和消费者对同一个缓冲区进行操作，互斥的访问缓冲区。本次课程设计的目的就是加深对多进程如何正确访问临界资源的理解，同时掌握条件变量在互斥访问时应该如何正确有效地使用。掌握生产者消费者问题的解决流程和方法，能够在此基础上解决现实中的具体问题。 二、课程设计内容 课程设计内容： 1)生产者和消费者进程的数目不固定，可在程序界面上设置 2)生产者和消费者进程的数目在程序界面上可调，在运行时可随时单个增加与减少生 产者与消费者 3)生产者的生产速度与消费者的消费速度均可在程序界面调节，在运行中，该值调整 后立即生效 4)生产者生产的产品由随机函数决定 5)多个生产者或多个消费者之间必须有共享对缓冲区进行操作的函数代码 6)每个生产者和消费者对有界缓冲区进行操作后，即时显示有界缓冲区的全部内容、 当前生产者与消费者的指针位置，以及生产者和消费者线程标识符 7)采用可视化界面，可在运行过程中随时暂停，查看当前生产者、消费者以及有界缓 冲区的状态 三、系统分析与设计 1、系统分析 1.1功能需求：生产者与消费者需要对缓冲池互斥操作，其中生产者和消费者的数目可以任意改变。生产者和消费者的速度也要随机的进行修改。可以查看当前生产者和消费者以及有界缓冲区的状态。 1.2数据需求：本次试验生产者和消费者的数量要动态的增加、减少，还有缓冲区的产品数，以及生产、消费产品的指针。 rear：生产者指针； front：消费者指针； size：产品数； CONSUME_TIME：消费者速度; PRODUCE_TIME ：生产者速度; mutex：对缓冲区互斥操作的锁； empty_cond：缓冲区空的条件变量； full_cond：缓冲区满的条件变量。 XI`AN TECHNOLOGICAL UNIVERSITY 实验报告 进程同步的多种解决办法 摘要：简单介绍了进程同步的概念，分析了进程同步的多种解决办法，重点讨论了读者写者问题，更容易了解解决办法的具体机制。 关键词：进程同步；多进程；读者-写者 0 引言 Windows应用程序中消息有两种送出途径，直接和排队。Windows或某些运行的应用程序可直接发布消息给窗口过程，或消息可送达到消息列象连续不断地轮询消息队列的OS中当前执行的每一个进程都不是由事件的顺序来控制的，而是由事件的发生来控制的。在传统的操作系统中，为提高资源利用率和系统吞吐量，通常采用多道程序技术，将多个程序同时装入内存，并使之并发执行。 1 同步 在OS中引入进程后，一方面使系统中多道程序并发执行，这不仅使资源利用率改善，亦可显著提高系统吞吐量，但也使系统更为复杂，致使进程对系统资源的无序争夺，每次处理的结果存在不确定性，显现不可再现性。因此，在多道程序系统中，必须引入进程同步机制。在本文中将介绍如下几种进程同步机制——硬件同步机制，信号量机制，管程机制和Peri网。 2 进程同步解决办法 2.1 硬件同步机制 目前许多计算机已提供特殊的硬件指令，允许对一个字中的内容进行检测和改正或对两个字进行交换。可利用特殊指令解决临界的问题。对临界区管理时，可将标志看作一个锁，“锁开”进入，“锁关”等待，初始状态锁是开着的。 但当临界资源忙碌时，其他进程处于“忙等”状态，不符合“让权等待”原则，造成处理机时间的浪费，同时很难解决，解决复杂的进程同步问题。 2.2 信号量机制 信号量机制已得到广泛发展，由整形信号量经记录型信号量，发展到“信号量集机制”，已广泛应用于单处理机和多处理机系统以及计算机网络中。信号量机制通常包括整型信号量，记录型信号量，AND型信号量和信号量集。 2.2.1 整型信号量 除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。很长时间以来，这两个操作分别被称为P、V操作。wait和signal操作可描述如下：wait(S){ while(S<=0);/*do no-op*/ S--; } Signal(S) { S++; } 原子操作不可中断，因此在执行时不可中断，即是当一个进程再修改某信号量时，没有其他进程可同时对该信号量进行修改。此外，在wait操作中，对S 值的测试和做S=S-1操作时，都不可中断。 在整型信号量机制中的wait操作，只要是信号量S<=0,就不断测试，因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”状态。记录型信号量则不存在“忙等”状态。 1.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请用PV操作实现管理。 解：定义一个信号量S，初值为20 parbegin process pl(l=1,2,……) begin wait(S); 进入售票厅； 购票； 退出； signal(S) end 2.桌上有一空盘，允许存放一个水果，爸爸可向盘内放苹果，妈妈可向盘内放桔子，儿子专等吃盘内的桔子，女儿专等吃盘中的苹果，请用P、V 操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步与互斥。 int S=1;int Sa=0;int Sb=0; main() {cobegin father(); mather(); son(); daughter(); coend} father() mather() {while(1) { while(1) {p(S); {p(S) ; 将一个苹果放入盘中将一个桔子放入盘中 V(Sa);} V(Sb);} } } son() daughter() { while(1) { while(1) {p(Sb); { p(Sa); 从盘中取出桔子从盘中取出苹果 V(S);吃桔子；} V(S);吃苹果；} } 3.生产围棋的工人不小心把相等数量的黑子和白子混装在一个盒子里，现在要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程PA和PB组成，系统功能如下： （1）PA专拣黑子，PB专拣白子； （2）每个进程每次只拣一个子，当一个进程拣子时，不允许另一个进程去拣子； （3）当一个进程拣一个子（黑或白）后，必须让另一个进程去拣一个子（白或黑） 请回答：①这两个并发进程之间的关系是同步还是互斥 ②写出PV操作管理时应定义的信号量及其初值。 ③根据定义的信号量，写出用PV操作管理两个并发进程的程序 答：①两个进程之间是同步关系 ②定义两个信号量S1和S2，初值为1和0 ③process PA process PA begin begin repeat repeat wait(S1) wait(S2) 拣黑子拣白子 signal(S2) signal(S1) until false until false end end 4.有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假若阅览室共有100个座位。试用信号量和PV操作来实现用户进程的同步算法。 解：设置如下3个信号量 seat：表示阅览室中空座位数，其初值为100. 【例1】有三个进程PA 、PB 和PC 协作解决文件打印问题：PA 将文件记录从磁盘读入内存的缓冲区1中，每执行一次读一个记录；PB 将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC 将缓冲区2中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。 答：该文件打印过程的同步算法可描述如下： 【例2】进程A1、A2、…An1通过m 个缓冲区向进程B1、B2、…Bn2不断地发送消息。发送和接收工作遵循如下规则： （1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。 （2）对于每一个消息，B1、B2、…Bn2都需各接收一次，读入自己的数据区内。 （3）m 个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。 试用wait,signal 操作描述它们的同步关系。 分析：本题是生产者－消费者问题的一个变形。由于每个缓冲区都只写一次，但要读n2次，故我们可将每个缓冲区看成是由n2格组成的。只有当某个缓冲区的n2 格都空闲时，才允许写入， 而且写一次缓冲区相当于将该缓冲区的n2格全部写一遍。Bj 进程从缓冲中取消息时，它只取相应缓冲的第j 格。由于每个Bj 取消息的速度不同，故需为它们分别设置指针outj ，用来指示从哪个缓冲区的第j 格中取消息。 答：我们将每个缓冲区看成是由n2格组成的，可为本题设置下列信号量：mutex,初值为1，用来实现对缓冲区的互斥访问；empty[i](i=1,…,n2)，初值均为m ，每个empty[i]对应于缓冲池的第i 格中的所有空闲缓冲区；full[i](i=1,…,n2)，初值均为0，对应缓冲池第i 格中装有消息的缓冲区。另外还需要提供整型变量in 用来指示将消息放入哪个缓冲区，outj(j=1,…,n2)用来指示Bj 从哪个缓冲区中取消息，这些变量的初值均为0。Ai,Bj 的算法描述如下： 【例3】设有两个生产者进程A 、B 和一个销售进程C ，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库，而且要求生产A 产品和B 产品的件数满足以下关系： －n ≤A 的件数－B 的件数≤m 其中n 、m 是正整数，但对仓库中A 产品和B 产品的件数无上述要求，请用信号量机制写出A 、 B 、 C 三个进程的工作流程。 分析：本题中存在着以下的同步和互斥关系：（1）生产者A 、B 和消费者C 之间，不能同时将产品入库和出库，故仓库是一个临界资源。（2）两个生产者之间必须进行同步。当生产者的A 、B 产品的件数之差大于等于m 时，生产者A 必须等待；小于等于－n 时，生产者B 必须等待。这种关系可想象成有两种令牌，分别跟允许A 和B 生产的产品数量相关，A 和B 必须取得对应的令牌后才能生产产品，故这两类令牌也就是两种临界资源。（3）生产者和销售者之间也必有进行同步，只有当生产者生产出产品并入库后，销售者才能进行销售。 答：为了互斥地入库和出库，需为仓库设置一初值为1的互斥信号量mutex ；为了使生产的产品件数满足：－n ≤A 的件数－B 的件数≤m ，需设置两个信号量，其中SAB 表示当前允许A 生产 实验一进程同步 一、实验目的： 分析进程的同步与互斥现象，编程实现经典的进程同步问题——生产者与消费者问题的模拟，进一步加深对进程同步与互斥的理解。 二、实验内容： 用C语言实现对生产者与消费者问题的模拟。 实验原理： 生产者和消费者是经典的进程同步问题，在这个问题中，生产者不断的向缓冲区中写入数据，而消费者则从缓冲区中读取数据。生产者进程和消费者对缓冲区的操作是互斥，即当前只能有一个进程对这个缓冲区进行操作，生产者进入操作缓冲区之前，先要看缓冲区是否已满，如果缓冲区已满，则它必须等待消费者进程将数据取出才能写入数据，同样的，消费者进程从缓冲区读取数据之前，也要判断缓冲区是否为空，如果为空，则必须等待生产者进程写入数据才能读取数据。 三、实验准备： 1. 实现步骤： （1）分析计算机系统中对资源的分配与释放过程：计算机系统中的每个进程都可以消费或生产某类资源。当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。 （2）定义生产者消费者问题中的各数据结构，并初始化信号量； （3）创建生产者与消费者进程，利用信号量实现生产者与消费者之间的同步与互斥；最后编程实现。 2. 相关函数： 在实现的过程中需要用到以下API函数： （1）CreateThread（）//该函数创建一个在调用进程的地址空间中执行的线程。若线程创建成功，将返回该线程的句柄。 函数原型： HANDLE CreateThread ( LPSECURITY_ATTRIBUTES lpThreadAttributes, //描述安全性，用NULL表示使用缺省值DWORD dwStackSize, //新线程拥有自己的堆栈，0表示使用缺省值1MB，推荐LPTHREAD_START_ROUTINE lpStartAddress, //新线程的起始地址，放线程函数名称LPVOID lpParameter，//此值被传送到线程函数去作为参数 DWORD dwCreationFlags,//允许产生一个暂时挂起的线程，默认是0立即开始执行LPDWORD lpThreadld );//新线程的ID被传到这 用法举例： hHandle1 = CreateThread( (LPSECURITY_ATTRIBUTES) NULL, 3.3 经典的进程同步问题3.3.1 生产者-消费者问题3.3.2 读者-写者问题3.3.3 哲学家进餐问题3.3.4 理发师问题 1 生产者-消费者问题 生产者--消费者问题是操作系统中并发进程内在关系的一种抽象 生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等 2 生产者消费者问题 ①一个生产者、一个消费者共享一个缓冲区 ②一个生产者、一个消费者共享多个缓冲区 ③多个生产者、多个消费者共享多个缓冲区 ④多个生产者、多个消费者共享一个缓冲区 ⑤多个生产者、一个消费者共享多个缓冲区 ⑥一个生产者、多个消费者共享多个缓冲区 3 一个生产者、一个消费者 共享一个缓冲区的解（1） var B : integer； empty : semaphore； full : semaphore； empty : = 1； full := 0； 4 一个生产者、一个消费者 共享一个缓冲区的解（2） process consumer Begin L2: P(full); Product:= B; V(empty); Consume a product; Goto L2; end; Process producer begin L1: Produce product; P(empty); put B product in; V(full); Goto L1; end; 5 多个生产者、多个消费者 共享多个缓冲区的解(1) n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲池上 只要缓冲区未满，Pi生产的产品就可投入缓冲区； 只要缓冲区不空，消费者进程Cj就可从缓冲区取走并消耗产品 Pi和Cj是并发进程（i=1 n,j=1 m）,Pi作为生产者生产产品，Cj作为消费者消费产品6 多个生产者、多个消费者 共享多个缓冲区的解(2) var B:array[0..k-1] of item; empty:semaphore:=k; full:semaphore:=0; mutex:semaphore:=1; in,out:integer:= 0; cobegin 7 多个生产者、多个消费者 共享多个缓冲区的解(3) process producer_i process consumer_j Begin begin L1:produce a product; L2：P(full); P(empty); P(mutex); P(mutex); Product:= B[out]; B[in]:= product; out:=(out+1) mod k; in:=(in+1) mod k; V(mutex); V(mutex); V(empty); V(full); Consume a product; Goto L1; Goto L2; end; end; coend 9 读者-写者问题 有两组并发进程：读者和写者，共享一个文件F，要求： 允许多个读者可同时执行读操作 任一写者在完成写操作之前不允许其它读者或写者工作 当有读者执行读操作时，不允许其它写者去修改（写）文件 10 解决读者-写者问题的思路 多个读者可同时读 写者与写者之间要互斥 写者与读者之间要互斥 即： 11 解决读者-写者问题的步骤(1) 1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司机 售票员 图司机和售票员工作流程图 2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。 3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab 段外等待； （2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a 点和b点同时驶入； （3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。 请用信号量为工具，对ab段实现正确管理以保证行驶安全。 4．将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法） 5．一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。 6．有一个仓库，可以存放A和B两种产品，但要求： （1）每次只能存入一种产品（A或B）； 1.某阅览室有100个座位，读者进入阅览室时要依次登记（即同时到达的读者 应分先后次序），离去时要注销。请利用记录型信号量描述登记和注销过程的模拟算法login和logout。 答案： Semaphore seat=100，mutex=1; Login: Wait（mutex）; Wait(seat); Signal(mutex); 阅读; Logout: Wait（mutex）; Signal(seat); Signal(mutex); 离开 2.桌上有一空盘，可放置2只水果。父亲只放苹果，母亲只放香蕉。儿子专等 吃盘内苹果，女儿专等吃盘内香蕉。请用信号量机制写出代表上述四人的进程father、mother、son、daughter的模拟代码。 答案： Semaphore empty=2，apple=0，banana=0 Father： Wait(empty) 放苹果 Signal（apple） Mother： Wait(empty) 放香蕉 Signal（apple） Son： Wait(apple) 取苹果 Signal（empty） Daughter： Wait(banana) 取香蕉 Signal（empty） 3.假定有一个信箱可存放N封信，当信箱不满时发信者可把信件送入信箱；当 信箱中有信时收信者可从信箱中取走全部信件。请用P、V操作及相应的代码模拟发信者和收信者的工作。 答案： Semaphore capacity=N,mutex=1; int count=0; 发信者： Wait(capacity); Wait(mutex) 将信件放入信箱; count++; Signal(mutex); 收信者： Wait(mutex); For n=1 to count Signal(capacity); End For count=0; 取走所有信件; Signal(mutex); 4.睡眠的理发师问题：有一理发店，共有n把椅子供等候的顾客使用。当没有 顾客时，理发师在理发椅子上睡觉；当一个顾客进入理发店发现理发师在睡觉，则叫醒他并开始理发，否则（理发师正在理发）找一空座坐下，如没有空座则等待空座。请用信号量机制和P、V操作写出他们的同步关系伪代码。答案： Semaphore barber=0,customer=0,chair=n; 理发师： P(customer);//等待顾客 V(barber);//通知顾客可以理发 开始理发; Goto 理发师 顾客： P(chair);//等待椅子，无空位时等待 V(customer); P(barber);//唤醒理发师 V(chair); 理发; 离开; 5.假定系统内有三个并发进程read, move和print共享缓冲器B1。进程read 负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓冲器B1中取出一记录，加工后重新存入缓冲器B1。进程print 将B1中修改后的记录取出并打印输出。缓冲器B1每次只能存放一个记录。 要求三个进程协调完成任务，使打印出来的信息与读入记录的个数，次序完全一样。请利用P、V操作写出它们的并发程序。 semaphore SR,SM, SP:1,0,0 read: X=接收的一个记录； wait(SR)； B1=X; signal(SM); move:进程同步典型例题
操作系统进程同步
进程同步问题习题答案
经典同步进程问题
用多进程同步方法演示“生产者-消费者”问题
进程同步的多种解决办法
进程同步经典习题
经典进程同步互斥问题集
操作系统实验一-进程同步
ch3-3经典的进程同步问题.ppt.Convertor
新版进程同步典型例题
经典进程同步问题
相关主题
文本预览