信号量互斥题目

《操作系统原理》
上机作业（报告）作业：信号量机制
要求其中P1~P5代表5个代码块，每个代码块分别由1个线程运行模拟，每个代码块执行时分别可以打印输出该代码块的名称（P1~P5），每个
代码块运行时需要睡眠（sleep()）一定时间。

（2）利用多线程编程和信号量机制模拟生产者消费者问题（多生产
者和多消费者）。

（3）利用多线程编程和信号量机制模拟哲学家就餐问题，至少实现1
种不会出现死锁的方案。

（4）利用多线程编程和信号量机制模拟读写者问题。

【实验要求】可选编程语言：C/C++/Java/C#/Python；
一个小题实现在同一个程序文件中（C/C++）；
请适当注释；
报告正文（运行屏幕截图及源代码）
一．截图。

1.
2.
3.哲学家就餐。

（三种方法）
（1）只有双手都拿到筷子，才让其他人去拿。

（2）偶数号先拿左边筷子，再拿右边筷子。

奇数先拿右边筷子，再拿左边筷子。

（3）最多允许四个哲学家就餐。

4.读写者问题。

第21 页共21 页。

1.如果信号量Ｓ的初值是５，现在信号量的值是-５，那么系统中的相关进程至少执行了几个Ｐ(S)操作？与信号量S相关的处于阻塞状态的进程有几个？为使信号量S的值大于0，应进行怎样的操作？答案：1）5-(-5)=10，因此系统中的相关进程至少执行了10个Ｐ(S)操作。

因为每执行一次P(S)操作就会将信号量S减去1。

2）与信号量S相关的处于阻塞状态的进程有|-5|=5个。

3）为使信号量S的值大于0，应当有至少6个执行了P(S)但还没来得及执行V(S)的进程去执行V(S)操作。

2.一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。

若将每一个购票者作为一个进程，请用P、V操作编程，并写出信号量的初值。

答案：设置信号量NUM表示售票厅当前还可以进入的人数，初值为300.购票者进程：do{P(NUM);进入售票厅；V(NUM);} While(1);3.桌上有一空盘，只允许存放一个水果。

爸爸可向盘中放苹果，也可向盘中放桔子。

儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。

规定当盘中空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

答案：设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为1；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。

同步描述如下：int S=1; int Sa=0; int So=0;main( ){father();son();daughter();}father(){while(1){P(S );将水果放入盘中；if （放入的是桔子）V(So);else V(Sa);}} son( ){while(1){P(So);从盘中取出桔子；V(S);吃桔子；}}daughter( ){while(1){P(Sa);从盘中取出苹果；V(S);吃苹果；}}4.下面是两个并发执行的进程。

它们能正确执行吗？若不能，试改正之。

用信号量机制来解决进程的同步与互斥：PV操作首先确定进程间的关系，然后确定信号量及其值。

判断进程间是否互斥的关键：看进程间是否共享某一公有资源，一个公有资源与一个信号量相对应。

确定信号量的值是一个关键点，它代表了可用资源实体数。

举例：票大厅容纳的人数限制为20人，少于20人时购票者可以进入，否则要在厅外等候。

进程间是同步时：是否存在合作关系，是否需要互通消息首先判断进程间的关系为同步的，且为各并发进程设置私有信号量，然后为私有信号量赋初值，最后利用PV原语和私有信号量规定各进程的执行顺序。

举例：公交车上司机与售票员的行为，司机到站停车后，售票员方可开门，售票员关门后，司机方可开车。

进程同步应用示例讲解：1桌上有一个盘子，可以存放一个水果。

父亲总是把苹果放在盘子中，母亲总是把香蕉放在盘子中；一个儿子专等吃盘中的香蕉，一个女儿专等吃盘中的苹果。

1）系统要设几个进程来完成这个任务？各自的工作是什么？2）这些进程间有什么样的相互制约关系?3）用P，V操作写出这些进程的同步算法(注：标明信号量的含义)。

1）需要四个进程进程描述：Father：父亲放置苹果的进程；Mother：母亲放置香蕉的进程；Son：儿子吃香蕉的进程；Daughter：女儿吃苹果的进程。

分析：四人公用一个盘子；盘子每次只能放一个水果，当盘子为空时，父母均可尝试放水果，但一次只能有一人成功；盘中是香蕉，儿子吃，女儿等；盘中是苹果，女儿吃，儿子等。

2）进程之间既有互斥又有同步关系。

Father进程和Mother进程要互斥的向盘中放水果，应设置一互斥信号量dish，初值为1，表示盘子为空；Father进程要设置同步信号量apple，用于给Daughter进程传送消息，初值为0，表示还没有消息产生，即没有放苹果；相应Daughter进程也要向父、母进程传送盘子为空的消息。

Mother进程要设置同步信号量banana，用于给Son进程传送消息，初值为0，表示还没有消息产生，即没有放香蕉。

第四章互斥、同步与通讯一、单项选择题1.一个正在访问临界资源的进程由于申请等待I/O操作而被中断时，__________.A.可以允许其他进程进入与该进程相关的临界区B.不允许其他进程进入任何临界区C. 可以允许其他就绪进程抢占处理器，继续运行D.不允许任何进程抢占处理器2.两个并发进程之间______A 一定存在互斥关系B 一定存在同步关系C 一定彼此独立无关D 可能存在同步或互斥关系3.为了使两个进程能同步运行，最少需要_______个信号量。

A 一B 二C 三D 四4.共享变量是指__________访问的变量。

A. 只能被系统进程B. 只能被多个进程互斥C. 只能被用户进程D. 可被多个进程5.临界区是指并发进程中访问共享变量的__________.A．管理信息 B.数据 C.信息存储 D.程序段6．设有三个进程共享一个资源，如果每次只允许一个进程使用该资源，则用PV操作管理时信号量S的可能取值是___________A.1,0,-1,-2B.2,0,-1,-2C.1,0,-1D.3,2,1,07.进程的并发执行是指若干个进程__________.A. 同时执行B. 在执行的时间上是重叠的C. 在执行的时间上是不可重叠的D. 共享系统资源8.在进程通信中，__________常用信件交换信息。

A．低级通信 B.高级通信 C.消息通信 D.管道通信9.实现进程同步时，每一个消息与一个信号量对应，进程_________可把不同的消息发送出去。

A.在同一信号量上调用P操作B.在不同信号量上调用P操作C.在同一信号量上调用V操作D.在不同信号量上调用V操作10．_________是只能有P和V操作所改变的整形变量。

A.共享变量B.锁C.整型信号量D.记录型信号量11．在执行V操作时，当信号量的值_________时，应释放一个等待该信号量的进程。

A.大于0B.小于0C.大于等于0D.小于等于012．进程和程序的主要区别是__________.A.占用处理器和不占用处理器B.占用主存和不占用主存C.动态和静态D.连续执行和非连续执行13．有三个进程P1,P2,P3共享同一个程序段，而每次最多允许两个进程进入该程序段，则信号量S的初值为___________.A. 0B. 1C. 2D. 314．若P、V操作的信号量S初值为2，当前值为-1，则表示有_________等待进程。

线程同步（信号量，互斥，条件变量）收藏进行多线程编程，最头疼的就是那些共享的数据。

因为你无法知道哪个线程会在哪个时候对它进行操作，你也无法得知那个线程会先运行，哪个线程会后运行。

下面介绍一些技术，通过他们，你会合理安排你的线程之间对资源的竞争。

l 互斥量Mutexl 信号灯Semophorel 条件变量Conditions先说一下互斥量。

什么时候会用上互斥量了？比如你现在有一全局链表，你有几个工作线程。

每一个线程从该链表中取出头节点，然后对该头节点进行处理。

比如现在线程1正在取出头节点，他的操作如下：Item * p =queue_list;Queue_list=queue_list->next;Process_job(p);Free(p);当线程1处理完第一步，也就是Item *p=queue_list后，这时候系统停止线程1的运行，改而运行线程2。

线程2照样取出头节点，然后进行处理，最后释放了该节点。

过了段时间，线程1重新得到运行。

而这个时候，其实p所指向的节点已经被线程2释放掉，而线程1对此毫无知晓。

他会接着运行process_job(p)。

而这将导致无法预料的后果！对于这种情况，系统给我们提供了互斥量。

你在取出头节点前必须要等待互斥量，如果此时有其他线程已经获得该互斥量，那么线程将会阻塞在这个地方。

只有等到其他线程释放掉该互斥量后，你的线程才有可能得到该互斥量。

为什么是可能了？因为可能此时有不止你一个线程在等候该互斥量，而系统无法保证你的线程将会优先运行。

互斥量的类型为pthread_mutex_t。

你可以声明多个互斥量。

在声明该变量后，你需要调用pthread_mutex_init()来创建该变量。

pthread_mutex_init的格式如下：int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutex-attr_t *mutexattr);第一个参数，mutext，也就是你之前声明的那个互斥量，第二个参数为该互斥量的属性。

试用用信号量机制描述两人下象棋的过程。

两人下象棋的过程可以概括为：一开始只能是“红先黑后”，以后两人要循环轮流走子，直至某一方获胜或双方和棋为止。

•这是个只有一个生产者和一个消费者的生产者——消费者问题，是个典型的“你等我，我也等你”的问题。

红方是总的前趋任务——生产者进程，黑方是总的后继任务——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。

棋盘则是生产者与消费者共享的缓冲。

•要求：只描述对弈过程，对棋盘的访问不做描述。

二人对弈过程是个纯粹的同步过程①所用信号量设臵如下：Ⅰ）同步信号量hei，初值为1，表示黑方已走子,开始时可使红方先行不受阻。

Ⅱ）同步信号量hong，初值为0，表示红方尚未走子，开始时可使黑方先行受阻。

用信号量机制描述的二人下象棋过程如下有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试问：（1）为描述读者的动作，应编写几个程序，设臵几个进程？（2）试用P、V操作描述读者进程之间的同步关系。

分析：•读者的动作都是一样的：登记进入阅览室，阅读，撤消登记离开阅览室，因此可写一个程序，设n个进程。

•读者共享的资源有阅览室的座位和登记表，因此诸个读者进程之间有两种互斥制约关系，需设2个信号量来实现：• seat：用于实现诸读者对阅览室的空闲座位的互斥竞争，初值为100；• mutex：用于实现诸读者对登记表的互斥访问，初值为1(1)可写一个程序，设n个进程(2)读者进程readeri(i=1,2,3,……)描述如下：P（seat）; /*申请空座位*/P（mutex）; /*申请登记*/登记；V（mutex） /*允许其他读者登记*/阅读；P（mutex）; /*申请撤消登记*/撤消登记；V（mutex）; /*允许其他读者撤消登记*/ V（seat）; /*释放座位，允许他人进入*/。

C++中的互斥锁和信号量是多线程编程中常用的同步机制，它们可以用来解决多线程访问共享资源时可能出现的竞态条件问题。

下面是关于C++中互斥锁和信号量的一些选择题，供大家学习和参考。

1. 互斥锁和信号量的作用是什么？A. 保护共享资源，防止多个线程同时访问B. 控制线程的执行顺序C. 增加线程的并发性D. 以上都是答案：A。

互斥锁和信号量都是用来保护共享资源，防止多个线程同时访问而发生竞态条件的情况。

2. 互斥锁和信号量的区别是什么？A. 互斥锁只能由一个线程持有，而信号量可以由多个线程同时持有B. 互斥锁只能保护一个共享资源，而信号量可以保护多个共享资源C. 互斥锁是二元的，只能表示锁定和解锁两种状态，而信号量可以有多个取值D. 以上都是答案：C。

互斥锁是二元的，只能表示锁定和解锁两种状态；而信号量可以有多个取值，可以用来控制同时访问的线程数量。

3. 在C++中，互斥锁和信号量的实现方式分别是什么？A. 互斥锁使用std::mutex实现，信号量使用std::semaphore实现B. 互斥锁使用std::lock实现，信号量使用std::semaphore实现C. 互斥锁使用std::mutex实现，信号量使用std::condition_variable 实现D. 以上都不是答案：C。

在C++中，互斥锁使用std::mutex进行实现，而信号量目前并没有标准的实现，可以使用第三方库或者自行实现。

4. 以下关于互斥锁和信号量的说法中，正确的是？A. 互斥锁和信号量都可以防止死锁的发生B. 互斥锁是一种更轻量级的同步机制C. 信号量可以用于线程之间的通信D. 互斥锁和信号量在功能上是等价的答案：C。

信号量可以用于线程之间的通信，通过控制资源的数量来实现线程间的同步和互斥。

而互斥锁和信号量在功能上是有区别的，不能说它们是等价的。

5. 下面关于互斥锁和信号量的哪种说法是错误的？A. 互斥锁可以用于避免多个线程同时访问共享资源B. 信号量是一种更高级的同步机制，可以实现互斥锁的功能C. 互斥锁在尝试获取锁失败时会阻塞线程D. 信号量的值可以在不同线程之间进行传递和共享答案：B。

信号量实现进程的互斥题目：汽车司机与售票员之间必须协同工作,一方面只有售票员把车门关好后司机才能开车,因此,售票员关好车门应通知司机开车.另一方面,只有当汽车已经停下,售票员才能开门上下客,故司机停车后应通知售票员.假设某辆公共汽车有一名司机与两名售票员,汽车当前正在始发站停车上客,试设必要的信号灯及赋初值,写出他们的同步过程.(用管程或信号灯机制均可)。

下面的情况是假设 一个车有两个车门，并且两个车门分别由两个售票员分别控制：Semaphore driver_sem_A = { 0, NULL }; //司机 进程的A信号量Semaphore conductor_A_sem ={ 0, NULL }; //售票员甲 进程的信号量Semaphore conductor_B_sem ={ 0, NULL }; //售票员乙 进程的信号量code_beginprogram driver{while(1){driving; //正常行车stopping; //到站停车V(&conductor_sem_A); //唤醒售票员甲 开车门V(&conductor_sem_A); //唤醒售票员乙 开车门P(&driver_sem_A); //等待售票员甲关车门start a bus;}}program conductorA{while(1){sell tickets; //售票P(&conductor_sem); //等待司机停车open the door; //开所有的车门close the door; //关售票员甲车门V(&driver_sem_A); //向司机发送信号表示自己的(售票员甲)车门已经关闭}}program conductorB{while(1){sell tickets; //售票P(&conductor_sem); //等待司机停车}}code_end存在另外一种情况:即使一个车上有两个售票员，而且这个车有两个门，这两个门也是由其中一个售票员集中控制的（不需要请示另外一个售票员）！ 这种情况实际上比上面的情况简单：Semaphore driver_sem_A = { 0, NULL }; //司机 进程的A信号量Semaphore conductor_A_sem ={ 0, NULL }; //售票员甲 进程的信号量Semaphore conductor_B_sem ={ 0, NULL }; //售票员乙 进程的信号量code_beginprogram driver{while(1){driving; //正常行车stopping; //到站停车V(&conductor_sem_A); //唤醒售票员甲 开车门V(&conductor_sem_A); //唤醒售票员乙 开车门P(&driver_sem_A); //等待售票员甲关车门start a bus;}}program conductorA{while(1){sell tickets; //售票P(&conductor_A_sem); //等待司机停车open the door; //开售票员甲的车门close the door; //关售票员甲车门V(&driver_sem_A); //向司机发送信号表示自己的(售票员甲)车门已经关闭}}program conductorB{while(1){sell tickets; //售票P(&conductor_B_sem); //等待司机停车open the door; //开售票员乙的车门close the door; //关售票员乙的车门}}code_end实际情况是：即使一个车上有两个售票员，而且这个车有两个门，这两个门也是由其中一个售票员集中控制的，但是这个售票员不能随便关车门，必须得到另外一个售票员的同意了才能关！这种情况和的一种比较相象，但是P，V原语的位置不同。

P,V操作P(S):S=S-1;=> IF S>=0 CONTINUE; ELSE WAIT; 申请锁V(S):S=S+1;=> IF S<=0 RELEASE_A_PROCESS; 释放锁(一)图书馆有100个座位,每位进入图书馆的读者要在登记表上登记,退出时要在登记表上注销.要几个程序？有多少个进程？(答:一个程序;为每个读者设一个进程)(1)当图书馆中没有座位时,后到的读者在图书馆为等待(阻塞)(2)当图书馆中没有座位时,后到的读者不等待,立即回家.解(1)设信号量:S=100;MUTEX=1;P(S)P(MUTEX)登记V(MUTEX)阅读,复习P(MUTEX)注销V(MUTEX)V(S)解(2)设整型变量COUNT=100;信号量:MUTEX=1;P(MUTEX);IF(COUNT==0){V(MUTEX);RETURN;}COUNT=COUNT-1;登记V(MUTEX);阅读P(MUTEX);COUNT=COUNT+1;V(MUTEX);RETURN;(二)有一座东西方向的独木桥;用P,V操作实现:(1)每次只允许一个人过桥;(2)当独木桥上有行人时,同方向的行人可以同时过桥,相反方向的人必须等待.(3)当独木桥上有自东向西的行人时,同方向的行人可以同时过桥,从西向东的方向,只允许一个人单独过桥.(此问题和读者与写者问题相同,东向西的为读者,西向东的为写者).(1)解设信号量MUTEX=1;P(MUTEX);过桥V(MUTEX);(2)解设信号量:MUTEX=1(东西方互斥)MD=1(东向西使用计数变量互斥)MX=1(西向东使用计数变量互斥)设整型变量:CD=0(东向西的已上桥人数)CX=0(西向东的已上桥人数)从东向西:P(MD)IF(CD=0){P(MUTEX)}CD=CD+1V(MD)过桥P(MD)CD=CD-1IF(CD=0){V(MUTEX)}V(MD)从西向东:P(MX)IF(CX=0){P(MUTEX)}CX=CX+1V(MX)过桥P(MX)CX=CX-1IF(CX=0){V(MUTEX)}V(MX)(3)解:从东向西的,和(2)相同;从西向东的和(1)相同.(三)有一个俱乐部,有甲乙两个服务员,当顾客有请求时,甲负责送烟,乙负责送火,无顾客请求时,服务员睡眠.顾客自己不能带烟和火,当顾客要抽烟时,可请求服务员送烟和火,烟和火还未送到时,顾客必须等待.甲服务员P(SY)送烟V(CY)UNTIL FALSE乙服务员REPEATP(SH)送火V(CH)UNTIL FALSE顾客V(SY) /*（请求送烟）*/V(SH) /*（请求送火）*/P(CY) /* (等烟) */P(CH) /* (等火) */抽烟（四）一家四人父、母、儿子、女儿围桌而坐；桌上有一个水果盘；（1）当水果盘空时，父亲可以放香蕉或者母亲可以放苹果，但盘中已有水果时，就不能放，父母等待。

进程A1,A2,…,An通过一个缓冲区向进程B1,B2,…Bm不断地发送消息。

发送和接收工作遵循如下规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；（2）对每一个消息，B1,B2,…,Bm都须各接收一次，读入各自的数据区；（3）缓冲区满时，发送进程等待；没有可读的消息时，接收进程等待。

试用P,V操作组织正确的发送和接收工作。

（说明信号量的意义）分析：本题是生产者-消费者问题的一个变形。

在生产者-消费者问题中，生产者和消费者公用一组缓冲区，每一个缓冲区只需写一次、读一次；而这个问题中，每一个缓冲区只写一次，但需读m次。

在解题的过程中，可以把一组缓冲区看做m组缓冲区。

这样一来，每一个生产者需要同时写m个缓冲区组中相应的m个缓冲区，而每一个消费者只需读自己对应的那组缓冲区中对应的单元。

生产者须在m个缓冲区都为空时方可写入。

这样，就可以用m组信号量（avail,full）来实现这一流程。

设公用信号量mutex保证生产者进程和消费者进程之间的互斥，设信号量avail[1…m]为生产者进程的私用信号量，信号量full[1…m]为消费者进程的私用信号量。

信号量mutex表示可用有界缓冲区的个数，初值为1；信号量avail[i](1≤i≤m)表示有界缓冲区组中的第i个缓冲区的空单元数，初值为m；信号量full[i](1≤i≤m)表示有界缓冲区中的第i个缓冲区的非空单元数，初值为0。

send(m):beginlocal ii←1;repeatP(avail[i]);until i=mP(mutex);把数据m送入缓冲区中某个单元;i←1;repeatV(full[i]);until i=mV(mutex);endreceive(m,i):beginP(full[i]);P(mutex);取出缓冲区中某个单元的数据mV(avail[i]);V(mutex);end练习1：假定系统有3个并发进程Read，Process，Print，他们共享缓冲区B1和B2。

1、解：因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。

设三个进程分别为A、B和C。

设一个互斥信号量mutex，其初值为1。

A进程 B进程 C进程P(mutex) P(mutex) P(mutex)使用打印机使用打印机使用打印机V(mutex) V(mutex) V(mutex)2、解：①这个算法不对。

因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。

改正：A、B两进程要同步使用缓冲区Q。

为此，设立两个信号量：empty表示缓冲区Q为空，初值为1;full表示缓冲区Q为满，初值为0。

算法框图如图1所示。

②这个算法不对。

因为A、B两个进程是并发的，它们共享一个临界资源，所以二者应互斥地使用该临界资源，在进入临界区时不存在A先B后的时序关系，而是哪个进程先到一步就先进入自己的临界区。

改正：A、B两个进程应互斥地进入临界区。

为此，设立一个信号量：互斥信号量mutex，其初值为1。

算法框图如图2所示。

A进程 B进程 A进程 B进程代码CSbV(full) V(empty) V(mutex)V(mutex)图1 图 23、解：①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。

②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。

③信号量含义及初值：B1full——缓冲区B1满，初值为0；B1empty——缓冲区B1空，初值为0；B2full——缓冲区B2满，初值为0；B2empty——缓冲区B2空，初值为0；4、解：作业周转时间等待时间JOB1 7 3JOB2 5 3JOB3 4 2所有作业的平均周转时间5.335、解：(1) 非抢占式优先级算法作业1 作业3 作业2| | | | t10 13 17(2)6、解：480K+154。