当前位置：文档之家› 信号量习题

信号量习题

操作系统信号量习题

第三章进程的同步与通信

1.3 临界资源（critical resource ）系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。如磁带机，打印机等。 1.4 临界区(critical section) 一个程序片段的集合，我们把在每个进程中访问临界资源的那段代码称为临界区。 1.5进程的同步（直接作用）指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。

1.6 进程的互斥（间接作用）由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。

2.进程的互斥

2.1临界区的使用原则

1）空闲让进：当无进程在临界区时，任何有权使用临界区的进程可进入。

2）忙则等待：不允许两个以上的进程同时进入临界区。

3）有限等待：任何进入互斥区的要求应在有限的时间内得到满足，以免陷入“死等”。

4）让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进入“忙等”。

2.2解决互斥问题的方法

?有两个进程Pi, Pj ，其中的Pi

软件方法：

算法1：单标志while (turn != i);critical section turn = j;

remainder section

?设立一个公用整型变量turn ：描述允许进入临界区的进程标识

–在进入区循环检查是否允许本进程进入：turn 为i 时，进程Pi 可进入；

–在退出区修改允许进入进程标识：进程Pi 退出时，改turn 为进程Pj 的标识j ；

? 缺点：强制轮流进入临界区，没有考虑

进程的实际需要。容易造成资源利用不充分：在Pi 出让临界区之后，Pj 使用临界区之前，Pi 不可能再次使用临界区；

算法2：双标志、先检查?设立一个标志数组flag[]：描述进程是否在临界区，初值均为FALSE 。

–先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；–在退出区修改本进程在临界区的标志；

while (flag[j]);flag[i] = TRUE;

critical section flag[i] = FALSE;remainder section

Pi:

? 优点：不用交替进入，可连续使用；

? 缺点：Pi 和 Pj 可能同时进入临界区。在

Pi 和 Pj 都不在临界区时，假设按下面序列执行时，会同时进入：“Pi; Pj ; Pi; Pj”。即在检查对方flag 之后和切换自己 flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能连续进行。

算法3：双标志、后检查

?类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。

flag[i] = TRUE;while (flag[j]);

critical section flag[i] = FALSE;remainder section

? 缺点：Pi 和Pj 可能都进入不了临界区。

在Pi 和Pj 都不在临界区时，假设按下面序列执行时，会都进不了临界区："Pi Pj Pi Pj"。即在切换自己flag 之后和检查对方flag 之前有一段时间，结果都切换flag ，都检查不通过。

算法4 (Peterson ’s Algorithm)：先修改、后检查、后修改者等待

?结合算法1和算法3，是正确的算法

?turn=j;描述可进入的进程（同时修改标志时）?在进入区先修改后检查，并检查并发修改的先后：

–检查对方flag ，如果不在临界区则自己进入－－空闲则入–否则再检查turn ：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入－－先到先入，后到等待

flag[i] = TRUE; turn = j;while (flag[j] && turn == j);critical section flag[i] = FALSE;remainder section

??分析算法4，能否出现算法3和算法2中的问题

硬件方法

?完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。

?可以利用某些硬件指令－－其读写操作由一条指令完成，因而保证读操作与写操作不被打断；

Test-and-Set 指令

该指令读出标志后设置为TRUE ：

boolean TS(boolean *lock) {boolean old;

old = *lock; *lock = TRUE;return old;}

lock 表示资源的两种状态：TRUE 表示正被占用，FALSE 表示空闲

Test-and-Set 指令, 可保证在一个指令周期内对一个存储单元的读和写，其功能如右：

互斥算法（TS 指令）

?利用TS 实现进程互斥：每个临界资源设置一个公共布尔变量lock ，初值为FALSE

?在进入区利用TS 进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；

while TS(&lock);lock = FALSE;critical section remainder section

相当于测试并加锁

相当于解锁

测试并加锁：lock (int *lock) {

while TS(&lock);}

解锁：

unlock (int *lock) {

* lock = FALSE;}

Swap 指令（或Exchange 指令）

交换两个字（字节）的内容

void SWAP(int *a, int *b) {int temp;

temp = *a; *a = *b; *b = temp;}

Swap 指令（或Exchange 指令）, 可保证在一个指令周期内交换一个寄存器和一个存储单元内容，其工作原理如下：

互斥算法（Swap 指令）

?利用Swap 实现进程互斥：每个临界资源设置一个公共布尔变量lock ，初值为FALSE 。每个进程设置一个私有布尔变量key

key = TRUE;do {

SWAP(&lock, &key);} while (key);lock = FALSE;

critical section remainder section

进入临界区前执行：

执行“关中断”指令离开临界区后执行：

?不能用于多处理机结构，因为关中断只能屏蔽本机的中断

区，只需为每个临界区设立一个布尔变量

硬件方法的缺点[WS]

– 等待要耗费CPU 时间，不能实现

"让权等待" – 可能“饥饿”（不公平）：从等待进

程中随机选择一个进入临界区，有的进程可能一直选不上

– 可能死锁：进程P1执行TS 或

Exchange 指令并进入临界区，然后P1被P2中断并把CPU 给具有更高优先级的P2, 若P2试图使用与P1相同的资源，由于互斥机制，它被拒绝访问，因此进入忙等待循环，又因P2先级高于P1，所以P1总得不到调度执行。

3.信号量机制 3.1信号量简介

1965年，由荷兰学者Dijkstra 提出（所以P 、V 分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。

P 原语--P(s) 或wait(s)

{

--s.count;//表示申请一个资源;if (s.count <0)//表示没有空闲资源;{

调用进程进入等待队列s.queue;阻塞调用进程;}}

P(Semaphore s)

在互斥问题中，申请使用临界资源时调用它

V 原语—V(s) 或signal(s)

{

++s.count;//表示释放一个资源；if (s.count <= 0) //表示有进程处于阻塞状态；{

从等待队列s.queue 中取出一个进程P;进程P 进入就绪队列;

}

V 原语通常唤醒进程等待队列中的头一个进程V(Semaphore s )

功能：释放资源，或唤醒进程

使用时机：进程退出临界区之后

P.V 操作讨论

1) 信号量的物理含义： S>0表示有S 个资源可用 S=0表示无资源可用

S<0则| S |表示S 等待队列中的进程个数 P(S):表示申请一个资源

V(S)表示释放一个资源。信号量的初值应该大于 3.2利用信号量实现互斥

?为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间

?必须成对使用P 和V 原语：遗漏P 原语则不能保证互斥访问，遗漏V 原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P 、V 原语不能次序错误、重复或遗漏

V(mutex);

critical section remainder section

P(mutex);

4. 进程的同步机制──管程 4.1管程的提出

采用PV 同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中缺点：

（１）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序２）不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局

（３）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的管程：一种同步机制 (管程-类程-进程) 4.2 管程定义:

指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作

系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用

资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性

管程：集中式同步机制，它的基本思想是将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，一个操作系统或并发程序由若干个这样的模块所构成，由于一个模块通常较短，模块之间关系清晰，提高了可读性，便于修改和维护，正确性易于保证管程的形式

TYPE monitor_name = MONITOR; 共享变量说明

define 本管程内所定义、本管程外可调用的过程（函数）名字表

use 本管程外所定义、本管程内将调用的过程（函数）名字表

PROCEDURE 过程名（形参表）；过程局部变量说明； BEGIN 语句序列； END; ......

FUNCTION 函数名（形参表）：值类型；函数局部变量说明； BEGIN 语句序列； END; ...... BEGIN 共享变量初始化语句序列； END;

? 5. 高级通信方式

一、共享存储器系统（Shared-memory system ）相互通信的进程共享某些数据结构或共享存储区。一组进程向该公共区中写，另一组进程从公共区中读，通过这种方式实现两组进程间的信息交换。因此又分为：

1基于共享数据结构的通信方式：进程之间能够通过某种类型的数据结构（如有界缓冲区）交换信息，如生产者和消费者问题。操作系统只负责提供共享存储区，而共享数据结构和对进程间的同步处理都是程序员的事。因而，通信效率低，只适合于传递少量信息。

一、共享存储器系统（续）

2.基于共享存储区的通信方式：

–系统在存储中划出一块共享存储区，各进程间可通

过对共享存储区中的数据进行读或写来实现通信。

–进程在通信之前应向系统申请共享存储区中的一个

分区，并指定该分区的关键字，若系统已经给其他

进程分配了这样的分区，则将该分区的描述符返回

给申请者.

–接着，申请者把获得的共享存储区连接到本进程

上，此后就像读写普通存储器一样。

–主要用于UNIX System V中。

?二、消息系统（Message System）

进程间的信息交换以消息或报文为单位，程序员利用系统提供的一组通信命令（原语）实现通信。操作系统隐藏了通信的实现细节，简化了编程的复杂性。分为两种：

?直接通信方式：发送进程发消息时要指定接收进程的名字，反过来，接收时要

指明发送进程的名字。系统提纲两条原

语：

Send(receiver,message)

Receiver(sender,message

二、消息系统（Message

System）

间接通信方式：

?收发双方进程通过某种中间实体，作为通信进程间的

媒介，即信箱（MailBox）。

?发送进程发消息时不指定接收进程的名字，而是指定

一个中间媒介。

?通常收方和发方的数目可以是任意的。这种方式广泛

应用于多机系统和计算机网络中

发送原语：send(MB,Message)

接收原语：receive(MB,Message)

?基于原有的文件系统形成的一种通信方式，即利用

共享文件实现进程间通信。如UNIX中的管道

2信号量机制和P、V操作，并能解决实际问

题。

?三、典型例题分析

?解决互斥同步问题的主要步骤：1）分析清楚题目涉及的进程间制约关系。

2）设置信号量（包括信号量的个数和初值，

对同步问题还要写出信号量物理含义）

3）给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序适当之处。

设阅览室有100 个座位，最多可以同时容纳

100 个读者，当读者进入或离开阅览室时都

必须在登记表上登记，试用

P ，V 操作编

写读者进程的同步算法。（同济大学1998

年硕士研究生入学考试试题）

例题1（北京大学1999年）

有一个仓库，可以存放A和B两种产品，仓库的存

储空间足够大，但要求：

(1)一次只能存人一种产品（(A或B);

(2)一N< A产品数量一B产品数量＜M

其中，N和M是正整数。

试用“存放A’和‘存放B’以及P操作和V操作

描述产品A和产品B的人库过程。

解答：

应先将表达式转换成制约条件，不可在程序中直接

(1)若只放人A产品，而不放入B产品，则A产品最

多可放M—1次便被阻塞，即A进程每操作一次就

应当将计数器减1（计数器初值为M —1），当计数器值为0时，进程程A 被阻塞；每当放入一个B 产品，则可令A 产品的计数器增加1，表明A 产品可以多一次放入产品的机会；同理，

(2) 若只放人B 产品，而不放入A 产品，则B 产品最

多可；放N 一1次便被阻塞，即A 进程每操作一次就应当将计数器减1（计数器初值为N —1）。当计数器值为0时，进程B 被阻塞；每当放人一个A 产品，则可令B 产品的计数器增加1，表明B 产品可以多一次放入产品的机会。

由此可见，该问题是一个同步控制问题。又因为一次仅允许一种产品人库，设置信号量mutex 控制粮进程互斥访问临界资源（仓库）。过程如下： begin

mutex:＝1; Sa := M-1; Sb := N-1； Parbegin A 产品 begin repeat P (Sa)； P (mutex)； A 人库； V (mutex)； V (Sb)； Until false; End;

B 产品 begin repeat

P (Sb)； P (mutex)； B 人库； V (mutex)； V (Sa)； Until false; End; rend;

例题2（华中理工大学1999年试题）

设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门

到站停车售票开车门下乘客

在汽车不断地到站，停车，行驶过程中，这两个活动有什么同步关系？并用信号灯的P, V 操作实现它们的同步。解答：

该题没有给出具体的控制关系，可根据常识自己定。如（1）售票员关车门后司机才可以启动车辆。（2）司机到站停车后，票员方可开车门。由此可见本题的控制关系较为简单。过程如下：

定义信号量run, stop ； Stop := 0 ; run :=0； Purbegin 司机：begin

L1：P (run); 启动车辆；正常行车；到站停车；

V (stop)；

Goto Ll ； End; 售票员：begin

L2：上乘客；关车门； V (run)；售票； P (stop)；开车门；下乘客； gotoL2 ; end; parend.

例题3（南开大学1997年试题）

在南开大学和天津大学之间有一条弯曲的小路，其中从S 到T 一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M （同时允许两辆自行车停留），可供两辆自行车已从两端进人小路情况下错车使用，如图4.3所示。试设计一个算法使来往的自行车均可顺利通过。

解答:

本题临界资源较多，需仔细考虑。首先中间的安全岛M 仅允许两辆自行车通过，应作为临界资源设置信号量。但仔细分析发现，在任何时刻进人小路的自行车最多不会超过两辆（南开和天大方向各一辆），因此不需为安全岛M 设置信号量。在路口S 处，南开出发的若干辆自行车应进行路口资源的争夺，以决定谁先进人小路SK 段，为此设置信号量S ，用以控制路口资源的争夺；同理，

T 的争夺。又小路SK 段仅允许一辆车通过，设置信号量SK 初值为1，同理设置小路LT 段信号量LT 初值为1。

程序如下：

S ：= l; T ：=1; SK ：＝1; LT ：=1； Parbegin

进程P:（南开方向自行车）

begin

天大

P(S) ; {与其它同方向的自行车争夺路口S}

P(SK); ｛同对面自行车争夺路段SK｝

通过SK;

进人M；**

V (SK);｛一旦进人M，便可释放路段SK｝

P (LT) ; {同对面的自行车争夺路段LT}

通过LT;

V (LT)；｛将路段LT释放｝

V(S); ｛将路口S释放给同方向的正在路口S 处等待的自行车｝

P进程进人安全岛M后，释放了路段SK，但没有释放路口S，原因在于它是向对面的4进程释放路段资源SK，而在P进程离开小路LT后，才会将路口S释放给其他P进程，如不这样，就会死锁。请考虑如下情况：两个方向各有一辆车前进，若在P进程到达安全岛M后，执行V (S)及V (SK)操作，则有可能使得同方向的其它P 进程得到路段SK的使用权，而进人小路；同理，Q进程到达安全岛后执行V (LT)及V (T)操作，有可能使得同方向的其它Q进程得到路段LT而进人小路。此时共有四辆车在整个路径中，最终出现死锁状态。

例题4（北京理工大学1996年试题）

进程之间存在哪几种相互制约关系？各是什么原因引起的？下列活动分别属于哪种

有直接制约关系（即同步问题）和间接制约关系（即互斥问题）；同步问题是存在逻辑关系的进程之间相互等待所产生的制约关系，互斥问题是相互无逻辑关系的进程间竞争使用资源所发生的制约关系。

（1）约属于互斥关系，因为书的个数是有限

的，一本书只能借给一个同学；

（2）属于互斥关系，篮球只有一个，两队都要

争夺；

（3）属于同步关系，各道工序的开始都依赖前

道工序的完成；

（4）属于同步关系，商品没生产出来，消费无

法进行，商品未消费完，生产也无须

进行。

例题5。（北京邮电大学1999年试题）

某招待所有100个床位，住宿者住人要先登记（在登记表上填写姓名及床位号），离去时要撤消登记（在登记表上删去姓名和床位号）。请给出住宿登记及撤消登记(退宿)过程的算法描述。

解答：

该题同有限缓冲区的生产者／消费者问题一致，缓冲单元为100个，顾客人住时执行生产者操作，登记过程对应于放产品过程，故对登记表的修改须互斥执行，当床位客满时便不可人住（即放产品）. 顾客离开时执行消费者操作, 退宿过程对应于取产品过程，包括修改登记表，删去姓名（即取产品），并将床位归还（空出一个单元）。

过程: 略

例题6。（南京大学2000年试题）

桌子上有一只盘子，最多可容纳两个水果，每次只能放人或取出一个水果。爸爸专向盘子中放苹果（apple），妈妈专向盘子中放橘子（orange），两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用P, V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

解答：

盘子为互斥资源，因可以放两个水果，empty初值为2; father放苹果前先看看有无空间，若有则抢盘子，放人apple。后向女儿发信号（V (apple)）; mother放橘子前先看看有无空间，若有则抢盘子，放人橘子后向儿子发信号（V (orange)）；女儿先看有无苹果，若有则抢盘子，取走苹果后将盘子置空（V (empty)）；儿子先看有无橘子，若有则抢盘子，取走橘子后将盘子置空。

该题是生产者／消费者问题的变形，有两对生产者和消费者。生产者需指明是给哪个消费者的产品，但消费者取走产品后无须特别通知某个生产者，因为空出的缓冲区（盘子）可由两个生产者随意争夺。

设信号量mutex初值为1，控制对盘子的互斥访问；apple表示盘中苹果个数，orange表示盘中橘子个数，初值均为0.

某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A, B两种零件，装配车间的任务是把A, B 两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车向的货架F1, F2上，Fl存放零件A, F2存放零件B, Fl和F2的容量均为可以存放10个零件。装配工人每次从货架上取一个A零件和一个B 零件然后组装成产品。请用PV操作进行正确管理。

解答：

该题是生产者／消费者问题的变形，可认为一个消费者（装配工人）同两个生产者(A, B车间)互斥使用两个缓冲区（Fl, F2），可设mutexl，mutex2（初值为1）控制进程对Fl, F2的互斥操作，另设一emptyl, empty2（初值均为10）, fulll, full2（初值均为0）。

Parend. 例题8（北京邮电大学1998年试题）

某寺庙，有小、老和尚若干，有一水缸，由小和尚提水人缸（向缸中倒水）供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个捅取水。水桶总数为3个。每次人、取缸水仅为1桶，且不可同时进行。试给出有关从缸中取水和向缸中倒水的算法描述。

解答：

应首先考虑清楚本题需要几个进程。从井中取水后向缸中倒水为连续动作，可算同一进程，从缸中取水为另一进程。

再考虑信号量．有关互斥的资源有水井（一次仅一个水桶进出）和水缸（一次入、取水为一桶），分别为之设信号量mutexl , mutex2控制互斥；

另有同步问题存在：三个水桶无论从井中取水还是人出水缸都是一次一个，应为之设信号量count，抢不到水桶的进程只好等待；还有水缸满时，不可人水，设信号量empty控制人水量．水缸空时不可出水，设信号量full，控制出水量。

mutexl：＝1；mutex２:＝1; empty:＝10; full：＝0 ; count：＝3;

例题9（北方交通大学1999年试题）

有一阅览室，读者进人阅览室必须先在一张登记表（(TB)上登记，该表为每一座位设一个表目，读者离开时要消掉其登记信息，阅览室共有100个座位，为了描述读者的动作，请用类Pascal语言和P, V操作写出进程间的同步算法。

约定：

1) flag的值：0座位空闲，1座位被占用。

2)用语句I=getflag (0)可搜索到一个空座位i，用语句

i.flag =0或1，可给标志位赋值。

3）用i = getname (readername)可搜索到某读者所登记的座位号i;

用https://www.doczj.com/doc/b43658193.html,=0 或https://www.doczj.com/doc/b43658193.html, = readrname。可给姓名字段

赋值，0表示清除读者姓名。

4）计数信号量用count，互斥信号量用mutex .

解答：

该题所提供的已知条件和语句过多，容易给考生造成混乱，因此看到此题应先理清思路，先不要考虑约定中提供的各种语句。首先，按照惯常的同步互斥问题思路来思考。

读者进程：

讲入阅览室首先应检杳是否有空位子。若没有则等待，若有则登记，可设信号量count，控制各进程对座位的争夺；读者离去时，便可释放该座位。登记时要对表中各量进行修改，该过程相对于各进程而言为互斥操作，因此设信号量mutex，控制读者进人和离去时对表的互斥修改，题目所提供的各种语句只是用在修改登记表时所进行的具体操作，对本题的同步互斥问题无任何影响，照抄即可。

count：=100; mutex : = 1；

i. name=readername;

V (mutex )；

P(mutex) ;

i = getname(readername)；

i. name=0; i.flag=0;

例题10。用信号量描述4乘100米接力过程

解答：

P1: P2: P(Sl); P3: P(S2); P4: P(S3);

起跑，前进l00m; 起跑，前进l00m; 起跑，前进l00m; 起跑，前进l00m;

V(S1); V(S2); V(S3)；到达终点。

例题11（北京大学1992年试题）

有桥如图4.15所示。车流如箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。用P, V操作实现交通管理以防桥上堵塞。

解答：

设置: 信号量mutex 1, murex 2，初值为1; bridge初值为1; 计数器count 1, count 2，初值为0。

北方: 南方：

P(mutex 1)；P(mutex 2) ;

count 1: =count 1 + 1; count2: = count 2＋1;

if count 1=1 then P(bridge) ; if count 2=1 then P(bridge) ;

V(mutexl); V(mutex2);

过桥；过桥；

P(mutexl); P(mutex2);

count 1: = count 1一1; count 2: = count 2一1; if count 1=0 then V(bridge) ; if count 2=0 then V(bridge) ;

V(mutex1); V(mutex2);

例题12。“吸烟者”问题：假设一个系统有三个吸烟者（Smoker）进程和一个供货商（(Agent)进程。每个吸烟者连续不断地制造香烟并吸掉它。但是，制造一支香烟需要三种材料；烟丝、纸、火柴。第一个吸烟者进程有纸，第二个有烟丝，第三个有火柴。供货商进程可以无限地提供这三种材料。供货商将两种材料一起放在桌上，持有另一种材料的吸烟者即可以制造一支香烟并吸掉它。供货商一次只能处理一个吸烟者的请求。当此吸烟者抽香烟时，它发出一个信号通知供货商进程，供货商进程马上给出另外两种材料，如此循环往复。试编写一个程序使供货商与吸烟者同步执行。

解答：

var smoker1, smoker2, smoker3 : Boolean; /*表明smoker i 是否需要抽烟*/

semaphore t, w, m; /* t —烟丝信号量，w—纸信号量，m—火柴信号量*/

binary semaphore mutex1, mutex2, mutex3,

/*控制agent每次只能为一个吸烟者按顺序服务*/

binary semaphore smoker_mutex;

/*控制三个吸烟者每次只能有一

个提出申请并从桌子上取材料

begin

smoker1:= false ; smoker2:= false; smoker3:= false;

t:=0; w:=0; m:=0;

mutex1 :=1; mutex2 :=1; mutex3 :=1; smoker_mutex :=1;

Agent:

Loop

P(mutex1);

If somker1 =true /*第一个拥有纸的吸烟者想吸烟*/

then V(t); /*提供烟丝*/

If somker2 =true /*第二个拥有烟丝的吸烟者想吸烟*/

then V(w); /*提供纸*/

If somker3 =true /*第三个拥有火柴的吸烟者想吸烟*/

then V(w); /*提供纸*/

Loop P(smoker_mutex) /*判断是否有其它吸烟者正在向供货商提出申请*/

P(mutex1) /*判断所需的烟丝和火柴是否已经放在桌子上*/

Smoker2 和Smoker3 与Smoker1类似。

【09真题】

三个进程P1、P2、P3 互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd （）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

1.定义信号量 S1 控制 P1 与 P2 之间的同步；S2 控制P1 与 P3 之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区。程序如下：Var s1=0,s2=0,empty=N,mutex=1;

Parbegin

P1:begin

X=produce(); /*生成一个数*/

P(empty); /*判断缓冲区是否有空单元*/ P(mutex); /*缓冲区是否被占用*/

Put();

If x%2==0

V(s2); /*如果是偶数，向 P3 发出信号*/ else

V(s1); /*如果是奇数，向 P2 发出信号*/ V(mutex); /*使用完缓冲区，释放*/

end.

P2:begin

P(s1); /*收到 P1 发来的信号，已产生一个奇数*/ P(mutex); /*缓冲区是否被占用*/

Getodd(); Countodd():=countodd()+1;

V(mutex); /*释放缓冲区*/

V(empty); /*向 P1 发信号，多出一个空单元*/ end.

P3:begin

P(s2) /*收到 P1 发来的信号，已产生一个偶数*/

P(mutex); /*缓冲区是否被占用*/

Geteven(); Counteven():=counteven()+1;

V(mutex); /*释放缓冲区*/

V(empty); /*向 P1 发信号，多出一个空单元*/ end.

Parend.

【11真题】

（一）图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）

（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）

（2）当图书馆中没有座位时，后到的读者不等待，立即回家。

设信号量S=200；MUTEX=1;

设信号量：S=100; MUTEX=1

（二）有一座东西方向的独木桥；用P,V操作实现：

（1）每次只允许一个人过桥；

（2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。（3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。

设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥)

MX=1 (西向东使用计数变量互斥)

设整型变量：CD=0 (东向西的已上桥人数) CX=0 (西向东的已上桥人数)

(3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。

（三）有一个俱乐部，有甲乙两个服务员，当顾客有请求时，甲负责送烟，乙负责送火，无顾客请求时，服务员睡眠。顾客自己不能带烟和火，当顾客要抽烟时，可请求服务员送烟和火，烟和火还未送到时，顾客必须等待。

设置信号量SY=0;SH=0;DY=0;DH=0;

设信号量：SY, SH,CY,CH:初值都为0

（四）一家四人父、母、儿子、女儿围桌而坐；桌上有一个水果盘；

（1）当水果盘空时，父亲可以放香蕉或者母亲可以放苹果，但盘中已有水果时，就不能放，父母等待。当盘中有香蕉时，女儿可吃香蕉，否则，女儿等待；当盘中有苹果时，儿子可吃，否则，儿子等待。

解设信号量：SE=1 (空盘子)；SA＝0 （放了苹果的盘子）；SB=0 (放了香蕉的盘子)

（2）把（1）改为：儿子要吃苹果时，请母亲放苹果，女儿要吃香蕉时，请父亲放香蕉，（还是盘子为空时才可以放）。

设信号量S=1;SA=0;SB=0;CA=0;CB=0;

（2）解：再增加两个信号量：SF=0, SM=0

（五）有一个超市，最多可容纳N个人进入购物，当N个顾客满员时，后到的顾客在超市外等待；超市中只有一个收银员。可以把顾客和收银员看作两类进程，两类进程间存在同步关系。写出用P;V操作实现的两类进程的算法（2003年系统设计员考试的题目）

第3章部分习题测验答案

第3章部分习题答案 3.2. 为什么进程在进入临界区之前，应先执行"进入区"代码，在退出临界区后又执行"退出区"代码? 为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为"进入区"代码；在退出临界区后，必须执行"退出区"代码，用于恢复未被访问标志. 3.3 同步机构应遵循哪些基本准则?为什么? a. 空闲让进. b. 忙则等待. c. 有限等待. d. 让权等待. 3.6你认为整型信号量机制和记录型信号量机制，是否完全遵循了同步机构的四条准则? a. 在整型信号量机制中，未遵循"让权等待"的准则. b. 记录型信号量机制完全遵循了同步机构的"空闲让进,忙则等待,有限等待,让权等待"四条准则. 3.9在生产者－消费者问题中，如果缺少了signal(full)或signal(empty),对执行结果会有何影响? 生产者－消费者问题可描述如下: var mutex,empty,full: semaphore:=1,n,0; buffer: array[0,...,n-1] of item; in,out: integer:=0,0; begin parbegin producer: begin repeat . . produce an item in nextp; . . wait(empty); wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); /* ************** */ signal(full); /* ************** */ until false; end consumer: begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); /* ************** */

PV操作题解

（一）图书馆有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+1 V (MD) 过桥 P (MD) CD=CD-1 IF (CD=0) {V (MUTEX) } V (MD) 从西向东： P (MX) IF (CX=0) {P (MUTEX) } CX=CX+1 V (MX) 过桥 P (MX) CX=CX-1 IF (CX=0) {V (MUTEX) } V (MX) (3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。

机制习题解答(DOC)

第1章习题及解答略第2&6章习题及解答 1.判断正误 (1)凡频谱是离散的信号必然是周期信号。( ×)准周期信号 (2)任何周期信号都由频率不同，但成整倍数比的离散的谐波叠加而成。( ×) (3)周期信号的频谱是离散的，非周期信号的频谱也是离散的。( ×) (4)周期单位脉冲序列的频谱仍为周期单位脉冲序列。( √) (5)非周期变化的信号就是随机信号。( ×)准周期信号 (6)非周期信号的幅值谱表示的是其幅值谱密度与时间的函数关系。( ×) (7)信号在时域上波形有所变化，必然引起频谱的相应变化。( ×) (8)各态历经随机过程是平稳随机过程。( √) (9)平稳随机过程的时间平均统计特征等于该过程的集合平均统计特征。( √) (10)非周期信号的频谱都是连续的。( ×) 准周期信号 (11)单位脉冲信号的频谱是无限带宽谱（√） (12)直流信号的频谱是冲击谱（√） 2.选择正确答案填空 (1)描述周期信号的数学工具是(B )。 A.相关函数 B. 傅里叶级数 C. 拉普拉斯变换 D. 傅里叶变换 (2)描述非周期信号的数学工具是( C)。 A.三角函数 B. 拉普拉斯变换 C. 傅里叶变换 D. 傅里叶级数

(3) 将时域信号进行时移，则频域信号将会( D ) A.扩展 B. 压缩 C. 不变 D. 仅有相移 (4) 瞬变信号的傅里叶变换的模的平方的意义为( C ) A.信号的一个频率分量的能量 B. 在f 处的微笑频宽内，频率分量的能量与频宽之比 C. 在f 处单位频宽中所具有的功率 (5) 概率密度函数是在（C ）域，相关函数是在（A ）域，功率谱密度函数是在（ D ）域描述随机信号。 A.时间 B. 空间 C. 幅值 D. 频率 (6) 白噪声信号的自相关函数是（C ） A.相关函数 B. 奇函数 C. 偶函数 D. 不存在 6.4已知被测模拟量最大输出幅值为±5V ，要求AD 转换输出最大误差不大于5mv ，应选用多少位的AD 转换器？解：量化误差5mv=±0.5LSB=125*5.012* 5.0-±=-±n n V FS 解得n=9 6.6 模拟信号DFT ，请问采样时间间隔Δt 、采样点数N 、频率分辨率Δf 三者之间的关系？并回答如下问题： (1) 为什么采样频率Δf 必须至少为被分析信号中最高频率成分的2倍才能避免混淆？ (2) 当采样频率确定后，频谱中应该出现的最高频率是多少？ (3) 频谱中的谱线根数是否与时域中的采样点数相同？对于频谱分析来说有用的谱线根数是多少？

信号量,中断和时间

第6章信号量，中断和时间信号量（Signal）是进程间通讯（IPC）的一种形式——是一个进程给另一个进程发送信息的方法。但是信息不可能很多——一个信号量不可能携带详细的信息，即使是传送者的身份也不能被传递；唯一能够确定的事实是信号量的确被发送了。（然而和经典信号量不同，POSIX实时信号量允许传送稍微多一点的信息。）实际上，信号量对于双向通讯是没有用处的。还有，根据某些限定，信号量的接受者不必以任何方式作出响应，甚至可以直接忽略大部分信号量。虽然有这么多的限制，然而信号量仍然是一种功能强大的十分有用的机制——勿庸置疑，这是Unix IPC中使用最频繁的机制。每当进程退出或者废弃一个空指针时，每当使用Ctrl+C键终止程序运行时，都要传递信号量。第9章会更详细的讨论IPC机制。对于本章的讨论来说，信号量的内容就足够讨论了。正如在Linux内核本身的代码注释中所说明的一样，中断（Interrupt）对于内核来说和信号量是类似的。中断一般都是从磁盘之类的硬件设备送往内核，用以提示内核该设备需要加以注意。一个重要的硬件中断源就是定时器设备，它周期性地通知内核已经通过的时间。如同第5章中阐述的一样，中断也可以由用户进程通过软件产生。在本章中，我们首先讨论一下Linux中信号量和中断的实现，最后再浏览一下Linux的时间处理方式。虽然内核对代码的要求标准非常严格，本章所涉及的代码仍然特别清晰明白。本章使用的一般方法是首先介绍相关的数据结构和它们之间的关系，接下来讨论操纵和查询它们的函数。锁的概述锁的基本思想是限制对共享资源的访问——共享资源包括共享的文件，共享的内存片，以及在一次只能由一个CPU执行的代码段。概括的说，在单处理器上运行的Linux内核并不需要锁，这是因为在编写Linux内核时就已经注意到要尽量避免各种可能需要锁的情况了。但是，在多处理器机器上，一个处理器有时需要防止其它处理器对它的有害的介入。 include/asm-i386/spinlock.h文件（从12582行开始）并不使用难看的#ifdef把所有对锁函数的调用封装起来，它包含一系列对单处理器平台（UP）基本为空的宏，然而在多处理器平台（SMP）上这些宏将展开成为实际代码。因而内核的其它代码对UP和SMP（当涉及到这种特性时）都是相同的，但是它们两个的效果却是迥然不同的。第10章中涉及SMP的部分会对锁做深入的介绍。但是，由于你在代码中将到处都能够看到对锁宏的调用，特别是在本章所讨论到的代码中这一点尤为明显，所以你应该首先对宏的用途有初步了解——以及为什么现在在大多数情况下我们都可以安全地将其忽略（我们将在讨论的过程中对其中的异常情况进行说明）。信号量 Linux内核将信号量分为两类：非实时的（Nonrealtime）——大部分是些传统的信号量，例如SIGSEGV，SIGHUP

1-4章习题

高回扣习题第一章习题一、单选题 (1)当CPU执行操作系统代码时，称处理机处于( )。 A.执行态 B.目态 C.管态 D.就绪态 (2)在下列性质中，( )不是分时系统的特征。 A.多路性 B.交互性 C.独立性 D.成批性 (3)下列仅一条指令( )只能在管态下执行。 A.读取时钟指令 B.访管指令 C.屏蔽中断指令 D.取数指令二、填空题 (1) 在计算机系统中配置操作系统的主要目的是协助和管理计算机的硬件和软件资源，操作系统的主要功能是管理计算机系统中的硬件和资源，其中包括处理机管理、存储器管理，以及设备管理和文件管理，这里的处理机管理主要是对进程进行管理。 (2) 利用缓冲区能有效地缓和CPU 和I/O设备之间速度不匹配的矛盾，虚拟设备的功能是使一个物理实体变成能被多个进程同时使用的逻辑上的对应物。第二章习题一、填空题 (1)对于一个可执行程序文件，该程序与执行它的进程是一对多的关系。 (2)在单CPU系统中实现并发技术后。 A.进程在一个时间段内并行执行，CPU与外设并行工作。 B.进程在一个时刻并行执行，CPU与外设并行工作。 C.进程在一个时间段内并行执行，CPU与外设串行工作。 D.进程在一个时刻并行执行，CPU与外设串行工作。 (3)从静态角度上看，进程是由PCB、程序段，数据段三部分组成。 (4)正在执行的进程由于用完其时间片而被暂停执行，此时进程应从执行状态变成为就绪状态。

(5)引入进程，可带来资源利用率的提高和系统吞吐量的增加的好处，但却增加了系统的空间和时间开销。 (6)临界区是指进程中用于访问临界资源的那段代码。 (7) ①控制变量是一种只能由P和V操作所改变的整型变量，①可用于实现进程的②互斥和③同步。互斥是指排他性地访问临界资源。 ①：A.控制变量B.锁 C.整型信号量 D.记录型信号量 ②,③：A.同步 B.通信 C.调度 D.互斥 (8)设有6个进程共享同一互斥段，若最多允许有3个进程进入互斥段，则所采用的互斥信号量的初值为 3 。 (9)有3个进程共享同一程序段，而每次最多允许两个进程进入该程序段，若用P、V操作作同步机制，则记录型信号量S的取值范围为2，1，0 ，-1。 (10)为实现消息缓冲通信，在PCB中应增加消息队列首指针、消息队列互斥信号量和消息队列资源信号量三个数据项。 (11)若记录型信号量S的初值为2，当前值为-1，则表示有 B 等待进程。 A.0个 B.1个 C.2个 D.3个 (12)当 B 时，进程从执行状态转变为就绪状态。 A.进程被调度程序选中 B.有高优先级进程到来 C.等待某一事件 D.等待的事件发生 (13)在进程转换时，下列 D 转换是不可能发生的。 A.就绪态→执行态 B.执行态→就绪态 C.执行态→阻塞态 D.阻塞态→执行态 (14)下列各项工作步骤中， B 不是创建进程所必须的步骤。 A.建立一个PCB B.阻塞进程 C.为进程分配内存等必要资源 D.将PCB连接入进程就绪队列 (15)在操作系统中，死锁出现指的是 C 。 A.计算机发生了重大故障 B.资源数远远少于进程数 C.若干进程因竞争资源而无限等待其他进程释放已占有的资源

pv操作的一些习题

1、进程P0和P1的共享变量定义及其初值为： boolean falg[2]; int turn=0; falg[0]=FALSE; falg[1]=FALSE; 若进程P0和P1访问临界资源的类C伪代码实现如下：则并发执行进程P0和P1时产生的情形是【全国联考2010】 A. 不能保证进程互斥进入临界区、会出现“饥饿”现象 B. 不能保证进程互斥进入临界区、不会出现“饥饿”现象 C. 能保证进程互斥进入临界区、会出现“饥饿”现象 D. 能保证进程互斥进入临界区、不会出现“饥饿”现象分析进程的执行过程：一开始，没有进程处于临界区中，现在进程P0开始执行，通过设置其数组元素和将turn置1来标识它希望进入临界区，由于进程P1并不想进入临界区，所以P0跳出while循环，进入临界区。如果进程P1现在开始执行，进程P1将阻塞在while循环直到flag[0]变为false，而该事件只有进程P0退出临界区时才会发生。现在考虑两个进程几乎同时执行到while循环的情况，它们分别在turn中存入1和0，但只有后被保存进去的进程号才有效，前一个被重写而丢失。假设进程P1是后存入的，则turn为0。进程P0将循环0次而进入临界区，而进程P1则将不停地循环且不能进入临界区，直到进程退出临界区为止。因此，该算法实现了临界区互斥。 “饥饿”出现的时机：使用忙等待实现互斥，当一个进程离开临界区时，如果有多个进程等待进入临界区，系统会随机选择一个进程执行，因为这种随机性，会导致有些进程长期得不到执行，因而导致“饥饿”。本题中，如果P1已经等在while上的时候，P0至多执行一次临界区，否则下次执行的时候，即便它在P1测试条件前出了临界区并重新设定了flag，但由于它必须要设定turn=1（此时P1不会再设置turn了），因此这样P0必然卡在while上，从而换到P1执行。所以不会出现“饥饿”现象。 2、在一间酒吧里有三个音乐爱好者队列，第一个音乐爱好者只有随身听，第二个只有音乐磁带，第三个只有电池，而要听音乐就必须有随身听，音乐磁

计算机操作系统典型例题解析之三

计算机操作系统典型例题解析之三【例1】分配到必要的资源并获得处理机时的进程状态是（B ）。A、就绪状态B、执行状态 C、阻塞状态D、新状态分析：进程有三种基本状态：就绪状态、执行状态和阻塞状态。当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机便可立即执行，这时的状态称为就绪状态；处于就绪状态的进程如果获得了处理机，其状态转换为执行状态；进程因发生某种事件（如I/O请求、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种状态为阻塞状态；而新状态是指创建了进程但尚未把它插入到就绪队列前的状态。所以本题的答案是B。【例2】挂起的进程被激活，应该使用（C）原语。 A、Create B、Suspend C、Active D、Wakeup 分析：在不少系统中，进程除了三种基本状态外，又增加了一些新的状态，其中最重要的是挂起状态。“挂起”的实质是使进程不能继续执行，即使挂起后的进程处于就绪状态，它也不能参加对CPU的竞争，进程的挂起调用Suspend（）原语。因此，被挂起的进程处于静止状态，相反，没有挂起的进程则处于活动状态。而且，处于静止状态的进程，只有通过“激活”动作，调用Active（）原语，才能转换成活动状态，调入内存。所以本题的答案是C。【例3】任何时刻总是让具有最高优先数的进程占用处理器，此时采用的进程调度算法是（D）。A非抢占式的优先数调度算法B、时间片轮转调度算法C、先来先服务调度算法D、抢占式的优先

数调度算法分析：“让具有最高优先数的进程占用处理器”，我们可以知道，采用的进程调度算法是优先数调度算法，但是我们还要进一步分析是抢占式的还是非抢占式的。“任何时刻总让”，通过这句话我们知道采用的是抢占式的，所以本题的答案是D。【例4】若P、V操作的信号量S初值为2，当前值为－1，则表示有（B）等待进程。A、0个B、1个C、2个D、3个分析：信号量的初始值表示系统中资源的数目，每次的Wait操作意味着进程请求一个单位的资源，信号量进行减1的操作，当信号量小于0时，表示资源已分配完毕，进程自我阻塞。因此，如果信号量小于0，那么信号量的绝对值就代表当前阻塞进程的个数。所以本题的答案是B。【例5】发生死锁的必要条件有四个，要预防死锁的发生，可以破坏这四个必要条件，但破坏（A）条件是不太实际的。 A、互斥 B、请求和保 C、不剥夺 D、环路等待分析：预防死锁是指通过破坏死锁的某个必要条件来防止死锁的发生。四个必要条件中，后三个条件都可以被破坏，而第一个条件，即“互斥”条件，对某些像打印机这样的设备，可通过SPOOLing技术予以破坏，但其他资源，因受它们的固有特性的限制，该条件不仅不能被破坏，反而应加以保证。所以本题的答案是A。【例6】有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是1 至1－m。

Linux之信号量,比较全面,个人总结。

信号量一．什么是信号量信号量的使用主要是用来保护共享资源，使得资源在一个时刻只有一个进程（线程）所拥有。信号量的值为正的时候，说明它空闲。所测试的线程可以锁定而使用它。若为0，说明它被占用，测试的线程要进入睡眠队列中，等待被唤醒。二．信号量的分类在学习信号量之前，我们必须先知道——Linux提供两种信号量： POSIX信号量又分为有名信号量和无名信号量。有名信号量，其值保存在文件中, 所以它可以用于线程也可以用于进程间的同步。无名信号量，其值保存在内存中。倘若对信号量没有以上的全面认识的话，你就会很快发现自己在信号量的森林里迷失了方向。三．内核信号量 1．内核信号量的构成内核信号量类似于自旋锁，因为当锁关闭着时，它不允许内核控制路径继续进行。然而，当内核控制路径试图获取内核信号量锁保护的忙资源时，相应的进程就被挂起。只有在资源被释放时，进程才再次变为可运行。只有可以睡眠的函数才能获取内核信号量；中断处理程序和可延迟函数都不能使用内核信号量。

count：相当于信号量的值，大于0，资源空闲；等于0，资源忙，但没有进程等待这个保护的资源；小于0，资源不可用，并至少有一个进程等待资源。 wait：存放等待队列链表的地址，当前等待资源的所有睡眠进程都会放在这个链表中。 sleepers：存放一个标志，表示是否有一些进程在信号量上睡眠。 2．内核信号量中的等待队列（删除，没有联系）上面已经提到了内核信号量使用了等待队列wait_queue来实现阻塞操作。当某任务由于没有某种条件没有得到满足时，它就被挂到等待队列中睡眠。当条件得到满足时，该任务就被移出等待队列，此时并不意味着该任务就被马上执行，因为它又被移进工作队列中等待CPU资源，在适当的时机被调度。内核信号量是在内部使用等待队列的，也就是说该等待队列对用户是隐藏的，无须用户干涉。由用户真正使用的等待队列我们将在另外的篇章进行详解。 3．内核信号量的相关函数（2）申请内核信号量所保护的资源： 4．内核信号量的使用例程在驱动程序中，当多个线程同时访问相同的资源时（驱动中的全局变量时一种典型的共享资源），可能会引发“竞态“，因此我们必须对共享资源进行并发控制。Linux内核中解决并发控制的最常用方法是自旋锁与信号量（绝大多数时候作为互斥锁使用）。

操作系统第二章练习答案

1．P、V 操作是 A 。
A.两条低级进程通信原语
B.两组不同的机器指令
C.两条系统调用命令
D.两条高级进程通信原语
2．设系统中有 n（n>2）个进程，且当前不在执行进程调度程序，试考虑下述4
种情况，
不可能发生的情况是 A 。
A．没有运行进程，有2个就绪进程，n 个进程处于等待状态。
B．有1个运行进程，没有就绪进程，n-1个进程处于等待状态。
C．有1个运行进程，有1个就绪进程，n-2个进程处理等待状态。
D．有1个运行进程，n-1个就绪进程，没有进程处于等待状态。
3．若 P、V 操作的信号量 S 初值为2，当前值为-1，则表示有 B 等待进程。
A. 0个
B. 1个
C. 2个
D. 3个
4．用 V 操作唤醒一个等待进程时，被唤醒进程的状态变为 B 。
A.等待
B.就绪
C.运行
D.完成
5．用 P、V 操作可以解决 A 互斥问题。
A.一切
B.某些
C.正确
D.错误
6．多道程序环境下，操作系统分配资源以 C 为基本单位。
A.程序
B.指令
C.进程
D.作业
7.从下面对临界区的论述中，选出一条正确的论述。
（1）临界区是指进程中用于实现进程互斥的那段代码。
（2）临界区是指进程中用于实现进程同步的那段代码。
（3）临界区是指进程中用于实现进程通信的那段代码。
（4）临界区是指进程中用于访问共享资源的那段代码。
（5）临界区是指进程中访问临界资源的那段代码。
8.（A）是一种只能由 wait 和 signal 操作所改变的整型变量，（A）可用于实现
进程的（B）和（C），（B）是排他性访问临界资源。
A：（1）控制变量；（2）锁；（3）整型信号量；（4）记录型信号量。
B：（1）同步；（2）通信；（3）调度；（4）互斥。
C：（1）同步；（2）通信；（3）调度；（4）互斥。
9.对于记录型信号量，在执行一次 wait 操作时，信号量的值应当（A），当其值
为（B）时，进程阻塞。在执行 signal 操作时，信号量的值应当为（C），当其
值为（D）时，应唤醒阻塞队列中的进程。
A：（1）不变；（2）加1；（3）减1；（4）加指定数值；（5）减指定数值。
B：（1）大于0；（2）小于0；（3）大于等于0；（4）小于等于0.
C：（1）不变；（2）加1；（3）减1；（4）加指定数值；（5）减指定数值。
D：（1）大于0；（2）小于0；（3）大于等于0；（4）小于等于0.
10.用信号量 S 实现对系统中4台打印机的互斥使用，S.value 的初值应设置为
（A），若 S.value 的初值为-1，则表示 S.L 队列中有（B）个等待进程。
A：（1）1；（2）0；（3）-1；（4）4；（5）-4
B：（1）1；（2）2；（3）3；（4）4；（5）5；（6）6；（7）0。
11.试选择（A）~（D），以便能正确地描述图2.12所示的前趋关系。
最新范本,供参考！

PV操作的例题

PV操作的例题一、线程是进程的一个组成部分，一个进程可以有多个线程，而且至少有一个可执行线程。进程的多个线程都在进程的地址空间内活动。资源是分给进程的，而不是分给线程的，线程需要资源时，系统从进程的资源配额中扣除并分配给它。处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。线程在执行过程中，需要同步。二、在计算机操作系统中，PV操作是进程管理中的难点。首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1； ②如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1； ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。 PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。一般来说，信号量S>=0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S 的值加1；若S?0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。利用信号量和PV操作实现进程互斥的一般模型是：进程P1 进程P2 ……进程Pn ……………… P（S）；P（S）；P（S）；临界区；临界区；临界区； V（S）；V（S）；V（S）； …………………… 其中信号量S用于互斥，初值为1。使用PV操作实现进程互斥时应该注意的是：（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。使用PV操作实现进程同步时应该注意的是：

操作系统-进程同步-信号量练习题

1【单选题】用P、V操作管理临界区时,互斥信号量的初值应定义为( A)。 ?A，1 ?B，0 ?C，-1 ?D，任意值 2【单选题】在操作系统中,对信号量S的P原语操作定义中,使进程进入相应等待队列等待的条件是( )。 ?A，S>0 ?B，S = 0 ?C，S<0 ?D，S<>0 我的答案：C 3【单选题】信号量S的初值为8,在S上执行了10次wait 操作,6次signal操作后,S的值为(D )。 ?A，10 ?B，8 ?C，6 ?D，4 P操作每执行一次,信号量减1；V操作每执行一次,信号量加1.所以答案为8-10+6 = 4

4【单选题】用V操作唤醒一个等待进程时,被唤醒进程的状态应变成( B)状态。 ?A，执行 ?B，就绪 ?C，阻塞 ?D，挂起被唤醒的进程由等待状态变为就绪状态。 5【单选题】利用Wait和signal操作可以( )。 ?A，实现进程互斥和同步 ?B，检测死锁 ?C，解除死锁 ?D，防止死锁我的答案：A 6【单选题】两个并发进程,设互斥信号量mutex(初值为1),若信号量=0;则(B ) ?A，表示没有进程进入临界区 ?B，表示有一个进程进入临界区 ?C，表示有一个进程进入临界区,另一个进程等待进入 ?D，表示两个进程进入临界区临界区不允许两个进程同时进入，D选项明显错误。mutex初值为1，表示允许一个进程进入临界区，当有一个进程进入临界区且没有进程等待进入时，mutex值减1，变为0。

7【单选题】V操作是对信号量执行加1操作,意味着释放一个单位资源,加1后如果信号量的值等于零,则从等待队列中唤醒一个进程,现进程变为等待状态,否则现进程继续进行。?A，对 ?B，错我的答案：B 8【单选题】有3个进程,两台打印机,用wait和sigual操作来实现互斥访问打印机,则信号量S的取值范围是( ) ?A，2,1,0,-1 ?B，3,2,1,0 ?C，2,1,0,-1,-2 ?D，1,0,-1,-2 我的答案：如果n个进程共享两个打印机，信号量取值范围：-(n-2)~2; 9【单选题】设与某资源相关的资源信号量K,初值为3,当前值为1,则可用资源个数为( ),等待资源的进程数为( )。 ?A，0,1 ?B，1,0 ?C，1,2 ?D，2,0 我的答案：B

操作系统期末复习题

一、填空题（每空1分，共10分）得分：分1．计算机操作系统是方便用户、管理和控制计算机的系统软件。 2．采用多道程序设计技术能充分发挥与外围设备并行工作的能力。3．程序的执行事现代操作系统的基本特征之一。 4．避免死锁的一个著名的算法时。 5．将程序中的逻辑地址转换为物理地址，这种地址转换工作称为。6．一个号的页面调度算法应该避免和减少现象的发生。 7．文件系统为每个文件另建立一张指示逻辑记录和物理块之间的对应表，有此表和文件本身构成的文件是。 8．UNIX文件系统对空闲磁盘空间的管理方法是。 9．在设备管理中，为了克服独占设备速度较慢、降低设备资源利用率的缺点，引入了___ ___，即用共享设备模拟独占设备。 10．常用的I/O控制方式有：程序直接控制方式、中断方式、和通道方式。二、单项选择题（每小题1分，共10分）得分：分1．操作系统是一种（）。 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．现有三个同时到达的作业J1、J2和J3，它们的执行时间分别是T1、T2和T3，且 T1

pv操作练习题

用P，V操作实现下述问题的解。一、桌上有一个盘子，可以放一个水果；父亲总是放苹果到盘子中；母亲总是放香蕉到盘子中。一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。父母只放水果不吃，儿女只吃水果不放。实现父亲，母亲，儿子，女儿的进程同步。二、在公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆，正常行车，到站停车。售票员的活动：上下乘客，关车门，售票，开车门，上下乘客。在汽车不停的到站，停站，行驶过程中，这两个活动有什么同步关系？用信号量和P，V操作实现它们的同步。三、某寺庙，有小，老和尚若干，有一个水缸，有小和尚提水入缸供老和尚饮用。水缸可以放10桶水，水从一个井里面提。水井狭窄，每次只能容纳一个桶取水。水桶总数为3个。每次入、取缸水只能是1桶，且不可以同时进行。试给出取水，入水的算法描述。四、一个快餐厅有4类职员：（1）领班：接受顾客点菜，出菜单；（2）厨师：根据菜单，准备顾客的饭菜；（3）打包工：将做好的饭菜打包；（4）出纳员：收款并提交食品。每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序。五、假设有一个作业由四个进程组成，这四个进程在运行时必须按如图所示的次序依次执行，试用P,V原语表达四个进程的同步关系：六、观察者和报告者是两个并发执行的进程，观察者不断观察并对通过的卡车计数，报告者定时的将观察者的计数值打印，打印完毕，将计数值清零。七、假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。

经典PV操作讲解和练习题

在计算机操作系统中，PV操作是进程管理中的难点。首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1； ②如果S30，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1； ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。 PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。一般来说，信号量S30时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S 的值加1；若S￡0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。利用信号量和PV操作实现进程互斥的一般模型是：进程P1 进程P2 ……进程Pn ……………… P（S）； P（S）； P（S）；临界区；临界区；临界区； V（S）； V（S）； V（S）； …………………… 其中信号量S用于互斥，初值为1。使用PV操作实现进程互斥时应该注意的是：（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。使用PV操作实现进程同步时应该注意的是：（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。

信号量互斥题目

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

止。? 这是个只有一个生产者和一个消费者的生产者——消费者问题，是个典型的“你等我，我也等你”的问题。红方是总的前趋任务——生产者进程，黑方是总的后继任务——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。棋盘则是生产者与消费者共享的缓冲。?要求：只描述对弈过程，对棋盘的访问不做描述。二人对弈过程是个纯粹的同步过程 ①所用信号量设臵如下： Ⅰ）同步信号量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）; /*释放座位，允许他人进入*/

操作系统(进程管理)习题与答案1

一、单选题 1、关于进程控制块的描述，如下存在问题的选项是（）。 A.操作系统控制和管理并发执行进程的依据 B.进程存在的惟一标志，离散存放于内存空间或对应程序的文件目录项中 C.进程实体的一部分，是拥有描述进程情况及控制进程运行所需的全部信息的记录性数据结构 D.使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程正确答案：B 2、进程标识符和进程控制块的分配可能发生在进程的（）阶段。 A.阻塞 B.挂起 C.创建 D.终止正确答案：C 3、当一个进程被（）时，可能会发生处理器的调度。 ①终止；②挂起；③唤醒；④阻塞 A.①②④ B.①③④ C.①②③④ D.①④ 正确答案：C

4、对于系统服务进程而言，如果当前没有任务，便会引发自身的（）事件。 A.进程阻塞 B.进程唤醒 C.进程终止 D.进程挂起正确答案：A 5、引起进程重新调度的原因不包括（）。 A.进程放弃处理器 B.进程从核心态返回用户态 C.进程执行系统调用和陷入内核态 D.时钟中断正确答案：C 6、关于进程同步机制基本准则：当无进程处于某临界资源所对应的临界区时，可允许一个请求进入（该临界资源所对应的）临界区的进程立即进入自己的临界区，这称之为（）。 A.忙则等待 B.有限等待 C.空闲让进 D.让权等待正确答案：C 7、关于进程同步机制基本准则：当已有进程进入自己的对应于某临界资源的临界区时，所有企图进入该临界资源所对应临界区的进程必须等待，这称之为（）。 A.循环等待

B.忙则等待 C.有限等待 D.让权等待正确答案：B 8、关于进程同步机制基本准则：对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区，这称之为（）。 A.忙则等待 B.循环等待 C.有限等待 D.让权等待正确答案：C 9、进程同步机制应遵循让权等待准则，故而当一个进程不能进入自己的临界区时，其应当释放（）。 A.处理器 B.I/O设备 C.内存空间 D.外存空间正确答案：A 10、利用硬件指令能有效地实现进程互斥，但它却不能满足（）的准则，造成了处理器时间的浪费，而且也很难将它用于解决较复杂的进程同步问题。 A.忙则等待 B.空闲让进 C.让权等待 D.有限等待

计算机操作系统算法题(最全)

6. 算法题（共32个题目） 200348. 在信号量机制中，若P（S）操作是可中断的，则会有什么问题？此题答案为：答： P（S）的操作如下： Begin S.Value:= S.Value-1; ① If S.Value<0 Then ② Begin Insert(*,S.L); Block(*) ③ End End. 若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value 的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误：本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。 200350. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？

＃define true; # define false; Int flag[2]; flag[1]=flag[2]=false; enter-crtsec(i) int i; { While(flag[1-i]) flag[i]=true; } feave-crtsec(i) Int i; { flag[i]=false; } process I; … Enter-crtsec(i); In critical section; Leave-crtsec(i);

此题答案为：答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。 200353. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 Cobegin PROCESS Pi(i=1,2,…) Begin 进入售票厅；购票；退出； End;

相关主题

 记录型信号量

信号量机制例题

信号量机制

中信号量

系统信号量

pv操作例题

文本预览

相关文档

第二章习题1

操作系统复习资料全第二章进程管理(3)-经典同步问题

第3章-部分习题答案

操作系统复习题

《操作系统》复习题

第二章课后习题解答

《操作系统》期末复习题

操作系统第二章课后答案

操作系统期末复习资料

西安交大网络教育2017年秋《操作系统原理》在线作业习题答案100分

操作系统期末复习题

操作系统第二章练习2 答案

第二章习题65764

吉大15秋学期《操作系统》在线作业一100分答案

进程控制--记录型信号量-教案

《记录型信号量》说课稿

《操作系统》期末复习题

记录型信号量

第3章部分习题答案

操作系统第二章练习答案

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)