请用PV操作解决读者和写者问题

？？？信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。

参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。

V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。

PV操作的物理含义：信号量S值的大小表示某类资源的数量。

当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。

每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。

每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。

无论以上哪种情况，执行V操作的进程都可继续运行。

1、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。

设两个信号量S和C，初值为S＝0；C＝0；司机： L1：正常行车售票员： L2：售票到站停车 P（S）V（S）开车门P（C）关车门启动开车 V（C）GO TO L1 GO TO L22、请用PV操作实现他们之间的同步关系：（1）桌上一个盘子，只能放一只水果。

爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。

（2）桌上一个盘子，只能放一只水果。

PV操作在软考中的深入探讨1. 基本概念PV操作是用于进程同步的两种基本操作。

P操作通常表示为一个进程需要一个资源，而V操作表示释放一个资源。

这两种操作通常用于实现进程间的同步和互斥。

2. PV操作原理PV操作基于信号量机制。

信号量是一个整数值，通常用于表示资源的数量。

P操作会尝试获取资源，减少信号量的值；而V操作会释放资源，增加信号量的值。

如果P操作不能立即获得资源（即信号量为0），则该进程会被阻塞或等待，直到资源可用。

3. PV操作在进程同步中的应用PV操作在进程同步中有着广泛的应用。

例如，在生产者-消费者问题中，生产者用于生成数据，消费者用于消费数据。

通过PV操作，可以确保生产者在没有数据被消费之前不会继续生产，同时确保消费者在没有数据可供消费时不会继续消费。

4. PV操作和互斥量互斥量是一种特殊的信号量，其值只能为0和1。

当一个进程获得互斥量时，其他任何进程都无法获得该互斥量，直到第一个进程释放它。

这使得互斥量可以用于保护某些临界区域，以实现互斥访问。

PV操作和互斥量通常一起使用，以实现更复杂的同步问题。

5. PV操作的编程实现在大多数编程语言中，PV操作可以通过系统调用或库函数实现。

例如，在UNIX系统中，可以使用semop函数进行PV操作。

在实现PV操作时，需要注意避免死锁和饥饿等问题。

6. PV操作的复杂度分析PV操作的复杂度取决于所使用的算法和数据结构。

在一些算法中，例如二叉堆或斐波那契堆，PV操作的平均时间复杂度可以达到O(1)。

然而，在最坏的情况下，PV操作的复杂度可能会达到O(n)，其中n是信号量的值。

7. PV操作与信号量信号量是一种同步机制，用于控制多个进程对共享资源的访问。

PV操作是信号量机制中的基本操作，通过它们可以实现对共享资源的互斥访问和同步。

信号量通常用于保护临界区、实现进程间的同步和互斥等。

8. PV操作与死锁预防死锁是操作系统中的一个重要问题，它发生在两个或多个进程无限期地等待对方释放资源的情况。

有关pv操作类的题目1、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。

进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。

进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。

进程print将B2中的记录取出打印输出。

缓冲器B1和B2每次只能存放一个记录。

要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。

请用PV操作，写出它们的并发程序。

解：beginemptyB1 , fullB1, emptyB2, fullB2 : semaphoreB1,B2 : recordemptyB1 := 1,fullB1:=0,emptyB2:=1,fullB2:=0cobegin process readX : record;begin R: 接收来自输入设备上一个记录X:=接收的一个记录；P(emptyB1)；B1:=X;V(fullB1);goto R;end;Process moveY:record;beginM:P(fullB1);Y:=B1;V(emptyB1)加工YP(emptyB2)；B2:=Y;V(fullB2);goto M;end;Process printZ:record;beginP:P(fullB2);Z:=B2;V(emptyB2)打印Zgoto P;end;coend;end;2、用PV操作解决读者写者问题的正确程序如下：begin S, Sr: Semaphore; rc: integer;S:=1; Sr:=1; rc:=0;cobegin PROCESS Reader i ( i=1,2…)begin ( P(S5))P(Sr)rc:=rc+1;if rc=1 then P(S);V(Sr);read file;P(Sr);rc:=rc-1if rc=0 thenV(S);V(Sr);( V(S5) )end ;PROCESS Writer j (j=1,2…)begin P(S);Write file;V(S)end;coend ;end;请回答：（1）信号量Sr的作用；（2）程序中什么语句用于读写互斥，写写互斥；（3）若规定仅允许5个进程同时读怎样修改程序？解：（1）Sr用于读者计数变量rc的互斥信号量；（2）if rc=1 then P（S）中的P（S）用于读写互斥；写者进程中的P（S）用于写写互斥，读写互斥。

例1：某超市门口为顾客准备了100辆手推车，每位顾客在进去买东西时取一辆推车，在买完东西结完帐以后再把推车还回去。

试用P、V操作正确实现顾客进程的同步互斥关系。

分析：把手推车视为某种资源，每个顾客为一个要互斥访问该资源的进程。

因此这个例子为PV原语的第二种应用类型。

解：semaphore S_CartNum; // 空闲的手推车数量，初值为100 void consumer(void) // 顾客进程{P(S_CartNum);买东西；结帐；V(S_CartNum);}例2：桌子上有一个水果盘，每一次可以往里面放入一个水果。

爸爸专向盘子中放苹果，儿子专等吃盘子中的苹果。

把爸爸、儿子看作二个进程，试用P、V操作使这四个进程能正确地并发执行。

分析：爸爸和儿子两个进程相互制约，爸爸进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。

因此该问题为进程间的同步问题。

解：semaphore S_PlateNum; // 盘子容量，初值为1semaphore S_AppleNum; // 苹果数量，初值为0void father( ) // 父亲进程{while(1){P(S_PlateNum);往盘子中放入一个苹果；V(S_AppleNum);}}void son( ) // 儿子进程{while(1){P(S_AppleNum);从盘中取出苹果；V(S_PlateNum);吃苹果；}}另附用PV原语解决进程同步与互斥问题的例子:经典IPC问题如：生产者－消费者，读者－写者，哲学家就餐，睡着的理发师等可参考相关教材。

PA从Q2取消息，处理后往Q1发消息，PB从Q1取消息，处理后往Q2发消息，每个缓冲区长度等于传送消息长度. Q1队列长度为n，Q2队列长度为m. 假设开始时Q1中装满了消息，试用P、V操作解决上述进程间通讯问题。

解：// Q1队列当中的空闲缓冲区个数，初值为0semaphore S_BuffNum_Q1;// Q2队列当中的空闲缓冲区个数，初值为msemaphore S_BuffNum_Q2;// Q1队列当中的消息数量，初值为nsemaphore S_MessageNum_Q1;// Q2队列当中的消息数量，初值为0semaphore S_MessageNum_Q2;void PA( ){while(1){P(S_MessageNum_Q2);从Q2当中取出一条消息；V(S_BuffNum_Q2);处理消息；生成新的消息；P(S_BuffNum_Q1);把该消息发送到Q1当中；V(S_MessageNum_Q1);}}void PB( ){while(1){P(S_MessageNum_Q1);从Q1当中取出一条消息；V(S_BuffNum_Q1);处理消息；生成新的消息；P(S_BuffNum_Q2);把该消息发送到Q2当中；V(S_MessageNum_Q2);}}二、《操作系统》课程的期末考试即将举行，假设把学生和监考老师都看作进程，学生有N人，教师1人。

操作系统PV操作习题操作系统PV操作习题-----------------------------------------------------1、引言在操作系统中，PV操作（也称作P操作和V操作）是用于进程同步的一种常见机制。

P操作用于获取或申请资源，V操作用于释放资源。

本文将为您提供一些关于PV操作的习题，以帮助您巩固相关的概念和原理。

2、PV操作基本概念2.1 P操作描述P操作的基本概念和含义，以及在实际应用中的具体场景。

2.2 V操作解释V操作的基本概念和含义，并举例说明其在实际问题中的应用。

3、PV操作习题集3.1 习题一、生产者-消费者问题描述一个典型的生产者-消费者问题，并通过使用P操作和V操作对其进行解决。

3.2 习题二、读者-写者问题解释一个典型的读者-写者问题，并使用PV操作来实现对该问题的解决。

3.3 习题三、哲学家就餐问题描述哲学家就餐问题的场景，并说明如何采用PV操作来解决这一问题。

4、常见PV操作错误4.1 死锁解释什么是死锁以及为什么会发生死锁现象，同时提供一些避免死锁的方法。

4.2 饥饿描述什么是饥饿，以及一些可能导致饥饿的常见原因，并提供解决饥饿问题的一些策略。

5、附录本文档附带以下附件:- 习题的解答和详细说明- 相关的代码示例6、法律名词及注释在本文档中，涉及的法律名词及其注释如下：- PV操作：即P操作和V操作，用于进程同步的一种机制。

- 生产者-消费者问题：一种经典的并发控制问题，涉及到生产者和消费者之间的资源竞争。

- 读者-写者问题：一种并发控制问题，涉及到多个读者和写者对共享资源的访问。

- 哲学家就餐问题：一种经典的并发控制问题，涉及到多个哲学家通过共享的餐具进行就餐。

pv操作例题（原创实用版）目录1.PV 操作概述2.PV 操作的实例3.PV 操作的解题技巧4.总结正文一、PV 操作概述PV 操作是计算机编程中的一种操作，主要用于处理并发读写问题。

PV 操作是基于 C 语言的线程操作，通过 PV 操作，可以实现线程之间的同步和互斥。

PV 操作主要包括 P 操作和 V 操作两个方面。

P 操作用于线程申请资源，如果资源已经被其他线程占用，则线程需要等待。

V 操作用于线程释放资源，当有其他线程正在等待该资源时，V 操作会唤醒等待的线程。

二、PV 操作的实例下面通过一个简单的实例来介绍 PV 操作的使用方法。

假设有两个线程，线程 A 负责生产产品，线程 B 负责消费产品。

由于产品库存有限，需要通过 PV 操作来实现线程之间的同步和互斥。

1.定义一个 PV 结构体，包括 P 操作和 V 操作的 sem_t 结构体。

```ctypedef struct {sem_t p;sem_t v;} PV;```2.初始化 PV 结构体。

```cPV pv = {0};```3.线程 A 执行 P 操作申请资源。

```cpv.p = sem_wait(&pv.p);```4.线程 A 执行生产操作。

```c// 生产产品操作```5.线程 A 执行 V 操作释放资源。

```csem_post(&pv.v);```6.线程 B 执行 P 操作申请资源。

```cpv.p = sem_wait(&pv.p);```7.线程 B 执行消费操作。

```c// 消费产品操作```8.线程 B 执行 V 操作释放资源。

```csem_post(&pv.v);```三、PV 操作的解题技巧在实际编程过程中，PV 操作的解题技巧主要包括以下几点：1.根据实际需求，合理地设置 PV 操作的资源。

2.确保 PV 操作的同步和互斥性，避免死锁现象的发生。

3.在编写 PV 操作时，要注意线程之间的切换和调度。

操作系统PV操作经典例题与答案1. 推广例子中的消息缓冲问题。

消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次若有m个发送进程呢？Send：SB=k; //信号量，标记当前空余缓冲区资源。

i = 0; //标记存放消息的缓冲区位置while (true) {P(SB);往Buffer [i]放消息;V(SM);i = (i+1) % k;};Receive：j = 0; //标记取产品的缓存区位置SM=0；//信号量，标记初始没有消息ReadCount=0；//读进程计数器Mutex =1；//读进程互斥信号量SW=0; //信号量，读进程在此信号量等待while (true) {P(SM);从Buffer[j]取消息;ReadCount++If（ReadCount<n）{< p="">V(SM);P(SW)}else{V(SB);j = (j+1) % k;for(int g=1; g< ReadCount;g++)V(SW);ReadCount=0；}};2.第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）rc=0, //正在读者计数器wc, //写计数器rw, //读等计数器R //等待读信号量W //等待写信号量读者：while (true) {P(mutex);if (wc >0){rw++P (R);}rc++;If（rw>0&&wc=0）{V(R)rw--}V(mutex);读P(mutex);rc --;if (rc==0){If（wc>0）V(w)}V(mutex);};写者：while (true) {P(mutex);wc ++;if((wc >1)||(rc>0)){P(W)}V(mutex);写P(mutex);Wc --;if（wc>0）V(W);Else if(rw>0)V(R)rw--V(mutex);};3.理发师睡觉问题理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉。

1. 设有一台计算机，有两条I/O 通道，分别接一台卡片输入机和一台打印机。

卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问： ①系统要设几个进程来完成这个任务？各自的工作是什么？ ②这些进程间有什么样的相互制约关系？ ③用P 、V 操作写出这些进程的同步算法。

解：①系统可设三个进程来完成这个任务：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；（B1full ＝1表示B1满） B1empty ——缓冲区B1空，初值为1；（B1empty ＝1表示B1空） B2full —— 缓冲区B2满，初值为0；（B2full ＝1表示B21满） B2empty ——缓冲区B2空，初值为1；（B2empty ＝1表示B2空）R 进程 C 进程 P 进程2、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？ 注：括号中第一个元素为段号，第二个元素为段内地址。

解：段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址<段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。

逻辑地址（2，15）查段表得段长度为20，段内地址15<20，地址不越界，段号2查表得段首地址为480，于是绝对地址为480+15=495。

1. 有一阅览室,共有100个座位.读者进入时必须先在一张登记表上登记，该表为每个座位列一表目，包括座号和读者姓名。

读者离开时要注销掉登记内容。

试用某一种语言（或类语言）和P、V操作描述进程的同步结构。

[分析]读者首先要申请座位，首先要获得登记表以便在上面进行登记；该读者在登记过程中是不允许其他读者进行登记的；因此，需要引入一个初始值为1的信号量mutex以实现读者间对登记表的互斥使用。

读者要在登记表上进行登记，前提是登记表上要有空表目；为此需要引入一个信号量S。

其初始值为100，表示有空表目100项。

读者在完成登记后，放下登记表给其他读者使用，然后在申请到的座位上进行阅读活动。

完成阅读后，读者需删除登记表上的内容，在该读者进行删除操作的同时是不允许其他读者进行删除的。

读者进程：mutex,s:Semaphore;mutex:=1;s:=100;Process ReaderiBeginwait(s);wait(mutex);<填入座号和姓名完成登记>；signal(mutex);<阅读>;wait(mutex);<删除登记表中的相关表项>;signal(mutex);signal(s);end2.司机和售票员的同步关系[分析]在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。

因此司机启动车辆的动作必须与售票员关车门的动作取得同步：售票员开车门的动作也必须与司机停车取得同步。

设置两个信号量S1和S2，S1表示是否允许司机启动汽车，其初值为0，S2表示是否允许售票员开门，其初值为0。

Var s1,s2:integer:=0,0;BeginDriver:BeginRepeatwait(s1)启动车辆正常行车到站停车signal(s2)Until false; End3.哲学家用餐问题beginrepeatif i mod 2=0 thenwait(c[i]);Busman:BeginRepeat关车门signal(s1)售票wait(s2)开车门上下乘客Until false;EndEndwait(c[i+1] mod 5);eat;signal(c[i]);signal(c[i+1] mod 5)elsewait(c[i+1] mod 5);wait(c[i]);eat;signal(c[i+1] mod 5);signal(c[i]);until falseend4. 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。

引言概述：正文内容：一、概念介绍1.pv操作的定义及由来：pv操作是一种用于进程间同步和互斥的操作，其中p表示“pass”（等待）操作，v表示“vacate”（释放）操作。

它最早由Dijkstra在1965年提出，并被广泛应用于操作系统中的进程间通信。

2.信号量的概念及与pv操作的关系：信号量是一种计数器，用于同步和互斥。

pv操作是通过操作信号量来实现进程间的同步与互斥，其中p操作用于申请资源时的等待，v操作用于释放资源。

3.pv操作的作用：pv操作允许进程进行同步和互斥操作，保证资源的正确访问顺序，避免竞态条件和死锁问题。

二、pv操作的使用场景1.生产者消费者问题：在多线程或多进程环境下，生产者和消费者之间的数据通信和同步是一个常见的问题。

pv操作可以用来同步生产者和消费者的操作，确保生产者和消费者的操作顺序正确。

2.进程间互斥访问共享资源：当多个进程需要同时访问某个共享资源时，需要使用pv操作来进行互斥操作，避免多个进程同时访问导致数据不一致的问题。

3.进程间信号通知：pv操作也可以用于进程间的信号通知，例如一个进程等待某个事件的触发，另一个进程通过v操作来触发该事件。

4.进程管道通信：pv操作也可以用于进程之间通过管道进行通信，通过p操作来等待管道中有数据可读，通过v操作来通知管道中有新数据写入。

5.进程调度和同步：操作系统中的进程调度和同步往往需要使用pv操作来保证进程的正确执行顺序和互斥性。

三、pv操作的实现原理与方法1.pv操作的实现原理：pv操作的实现通常依赖于操作系统中的信号量机制。

当一个进程进行p操作时，它会尝试将指定的信号量值减1，若结果为负，则表示资源不可用，该进程会被阻塞。

当一个进程进行v操作时，它会将指定的信号量值加1，并唤醒一个等待中的进程。

2.pv操作的实现方法：pv操作可以通过系统调用来进行实现，例如在Unixlike系统中，可以使用semop()系统调用来进行pv操作。

实验3 读者/写者问题与进程同步3.1 实验目的理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。

3.2 实验要求在linux环境下编写一个控制台应用程序，该程序运行时能创建N个线程〔或者进程〕，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。

请用信号量和PV操作实现读者/写者问题。

读者/写者问题的描述如下：有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间〔比方一个数组或一个变量〕，甚至可以是一组处理器寄存器。

有一些只读取这个数据区的进程〔reader〕和一些只往数据区中写数据的进程〔writer〕。

以下假设共享数据区是文件。

这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。

这些条件具体来说就是：〔1〕任意多的读进程可以同时读这个文件；〔2〕一次只允许一个写进程往文件中写；〔3〕如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；〔4〕写进程执行写操作前，应让已有的写者或读者全部退出。

这说明当有读者在读文件时不允许写者写文件。

对于读者-写者问题，有三种解决方法：1、读者优先除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。

这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。

2、写者优先除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。

当一个写者声明想写文件时，不允许新的读者再访问文件。

3、无优先除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。

实验步骤算法分析有同学认为，可以将文件视为临界资源，使用临界资源的代码就构成临界区，为了对临界区进行管理，只需设置一个互斥信号量r_w_w，读或者写之前执行P(r_w_w)，之后执行V(r_w_w)即可，从而得到图3-1所示的算法描述。

经典P、V操作问题详解*****************一、基本概念1. 信号量struct semaphore{int value; // 仅且必须附初值一次，初值非负PCBtype* wait_queue; // 在此信号量上阻塞的进程队列} S; // 信号量实例为S2. P、V操作P(S){S := S-1;if (S<0)调用进程自己阻塞自己，等待在S的等待队列末尾;}V(S){S := S+1;if (S≤0)从S等待队列头释放一进程就绪在就绪队列尾;调用进程继续执行;}3. 使用方法(i). P、V操作成队出现，处理互斥时出现在同一进程中；处理同步时出现在不同进程中。

(ii). 同步P先于互斥P调用，V的顺序无关。

4. 另类P、V操作导致的问题(或信号量的栈实现方法或漏斗法)[习题P174-23]某系统如此定义P、V操作：P(S): S = S-1; 若S＜0，本进程进入S信号量等待队列的末尾；否则，继续执行。

V(S): S＝S+1; 若S≤0，释放等待队列中末尾的进程，否则继续运行。

(1)上面定义的P、V操作是否合理？有什么问题？(2)现有四个进程P1、P2、P3、P4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面定义的P、V操作正确解决P1、P2、P3、P4对该互斥资源的使用问题。

答：(1)不合理：先进后出；可能“无限等待”，即等待队列头的进程得不到释放。

(2)思路：令每个信号量上的等待队列中始终只有一个进程。

解决方案如下：(n个进程)n个进程至多有n-1个等待。

设置n-1个信号量，每个进程阻塞在不同的信号量上，使每个等待队列至多有一个进程等待。

用循环模拟队列。

Semaphore S[n-1]; // S[i]的初值为i+1Procedure_i(){int j;DO_PRE_JOB();for(j=n-2; j>=0; j--)P(S[j]);DO_JOB_IN_CRITICAL_SECTION();for(j=0;j<=n-2;j++)V(S[j]);……}二、经典进程同步问题总述：进程同步问题主要分为以下几类：一（生产者－消费者问题）；二（读者写者问题）；三（哲学家就餐问题）；四（爱睡觉的理发师问题）；五（音乐爱好者问题）；六（船闸问题）；七（红黑客问题）等。

小测验答案一、选择题（共30分，每个选项2分）1、操作系统是一组（C）。

A.文件管理程序B.中断处理程序C.资源管理程序D.设备管理程序2、从用户观点看，操作系统是（A）。

A.用户与计算机之间的接口B.控制和管理计算机资源的软件C.合理的组织计算机工作流程的软件D.由若干层次的程序按一定的结构组成的有机体3、现代OS具有并发性和共享性，是（ D ）的引入导致的。

A.单道程序B. 磁盘C. 对象D.多道程序4、在单一处理机上执行程序，多道程序的执行是在（B ）进行的。

A. 同一时刻B.同一时间间隔内C. 某一固定时刻D.某一固定时间间隔内5、批处理系统的主要缺点是（ B）。

A. CPU的利用率不高B.失去了交互性C. 不具备并行性D.以上都不是6、在下面关于并发性的叙述中正确的是（C）。

A. 并发性是指若干事件在同一时刻发生B. 并发性是指若干事件在不同时刻发生C. 并发性是指若干事件在同一时间间隔内发生D. 并发性是指若干事件在不同时间间隔内发生7、CPU状态分为系统态和用户态，从用户态转换到系统态的唯一途径是（C）。

A.运行进程修改程序状态字B.中断屏蔽C.系统调用D.进程调度程序8、进程的三个基本状态是（1）、（2）、（3）。

由（1）到（2）是由进程调度所引起；由（2）到（3）是正在执行的进程发生了某事件，使之无法执行而暂停的。

（1），（2），（3）：A、挂起；B、等待；C、就绪；D、执行。

(C) (D) (B)9、进程间的同步是指并发进程之间存在一种( D )关系A、主从B、包含C、调用D、制约10、操作系统是（ 1 ），建立在（ 2 ）之上。

1，2：A、应用软件 B、系统软件 C、软硬件 D、硬件(B)(D)11、操作系统有多种类型：（1）允许多个用户以交互方式使用计算机的操作系统，称为（ 1 ）； (B)（2）允许多用户将若干个作业提交给计算机系统集中处理的操作系统称为（2 ）；(A)（3）在（ 3 ）的控制下，计算机系统能及时处理由过程控制反馈的数据，并做出响应。

有个寺庙，庙中有个小和尚和老和尚若干人，有一只水缸，由小和尚提水入缸给老和尚饮用。

水缸可容10桶水，水取自同一口水井中。

水井径窄，每次仅能容一只水桶取水，水桶总数为3个。

若每次只能入缸一桶水和取缸中一桶水，而且还不可以同时进行。

试用一种同步工具写出小和尚和老和尚入水、取水的活动过程。

4.答：本题为两个进程共享两个缓冲区的问题。

首先考虑本题有几个进程：从井中取水后向缸中倒水此为连续动作，为一个进程；从缸中取水为另一个进程。

其次考虑信号量，有关互斥的有：水井和水缸。

水井一次仅能一个水桶进出，水缸一次入、取水为一桶。

分别设互斥信号量为：mutex1和mutex2控制互斥。

有关同步问题为：三个水桶无论从井中取水还是入出水缸都是一次一个，应为它设信号量count，抢不到水桶的进程只好等待。

水缸满时不可入水，设信号量为empty，控制水量，水缸空时不可出水，设信号量full，控制出水量。

设置信号量初值：mutex1：=mutex2：=1；count：=3；empty：=10；full：=0；Parbegin﹛小和尚打水进程：BeginP（empty）；P（count）；P（mutex1）；从井中打水；V（mutex1）；P（mutex2）；倒水入缸；V（mutex2）；V（count）；V（full）；End老和尚取水进程：BeginP（full）；P（count）；P（mutex2）；从缸中取水；V（mutex2）；V（count）；V（empty）；End｝Parend.2. 假定一个阅览室可供50个人同时阅读。

读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。

要求：（1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）；（2）指出算法中所用信号量的名称、作用及初值。

解S1:阅览室可供使用的空座位，其初值为50S: 是否可通过阅览室，其初值为1Process READ_in（i=1…50）{到达阅览室入口处;P(S1);P(S);在入口处登记座位号;V(s);进入座位并阅读;}Process READ_out（j=1…50）{结束阅读到达阅览室入口处;P(S);在入口处注销座位号;V(S1);V(S)离开入口处;}●N个并发进程公用一个公共变量Q，信号灯进程：main(){begins=1;cobeginp1();p2();…pn();coend}Pi(){P(s)…V(s)}其中i=1、2…n●用户A、B、C打印进程（间接相互制约关系）：s初值为1,假设打印机占用1时间片。

一、单选(每题5 分,共50 分)1.操作系统作业管理的主要功能是( )A、作业的调度与控制B、作业的提交C、作业准备D、编制程序答案：A2.进程间的同步与互斥，分别表示了各进程间的( )A、相互独立与互相制约B、协调与竞争C、不同状态D、动态性与独立性答案：B3.在9个生产者,6个消费者共享容量为8的缓冲区的生产者-消费者问题中,互斥使用缓冲区的信号量S的初始值为( ).A、8B、1C、9D、6答案：B4.死锁预防是保证系统不进入死锁状态的静态策略,其解决方法是破坏产生死锁的四个必要条件之一.下列方法中破坏了"循环等待"条件的是( ).A、银行家算法B、一次性分配策略C、剥夺资源法D、资源有序分配法答案：D5.作业在系统中存在与否的唯一标志是( )A、源程序B、作业说明书C、作业控制块D、目的程序答案：C6.碎片存储容量( )A、不可能比某作业申请容量大B、可能比某作业申请容量大C、在分页管理中，可能大于页D、在段页式管理中，可能大于页答案：B7.按照记录存人文件的先后次序排序并查找，排列顺序与记录的内容无关，这是指( )A、流式文件B、记录式文件C、连续结构文件D、有序结构文件答案：C8.在配有操作系统的计算机中，用户程序通过( )向操作系统指出使用外部设备的要求。

A、作业申请B、原语C、广义指令D、I／O指令答案：C9.通道是一种( )A、保存I／O信息的部件B、传输信息的电子线路C、通用处理机D、专用处理机答案：D10.作业调度算法中所提到的响应比是指( )A、作业等待时间与作业执行时间之比B、作业执行时间与作业等待时间之比C、作业执行时间与作业调度时间之比D、作业调度时间与作业执行时间之比答案：A二、多选(每题10 分,共20 分)1. 有关并发进程的下列描述中，（）是不正确的。

A、进程执行的相对速度是由进程自己来控制的B、进程执行的相对速度与进程调度策略无关C、P操作和V操作都是原语操作D、利用P、V操作可以防止死锁E、同步是指并发进程之间存在的一种制约关系答案：ABD2. 在一个具有分时兼批处理的计算机系统中，往往同时有批处理作业和终端作业请求执行，系统总是（）。