操作系统原理试题库(最全)

admin管理员组

文章数量:1536061

2024年5月18日发(作者：)

il操作系统原理试题库1.0

第一章 操作系统引论 ...................................................................................... 1

1.1 操作系统的目标与作用 ........................................................................................... 1

1.2 操作系统的发展过程 ............................................................................................... 3

1.3 操作系统的基本特征 ............................................................................................... 6

1.4 操作系统的主要功能 ............................................................................................... 6

1.5 操作系统的结构设计 ............................................................................................... 7

第二章 进程管理 ............................................................................................ 11

2.1 进程的基本概念 ..................................................................................................... 11

2.2 进程控制 ................................................................................................................. 16

2.3 进程同步 ................................................................................................................. 16

2.4 经典进程同步问题(P、V操作解决进程同步问题) ............................................ 22

2.5 进程通信 ................................................................................................................. 73

2.6 线程的基本概念 ..................................................................................................... 74

第三章 处理机调度与死锁 ............................................................................ 75

3.1 处理机调度的基本概念 ......................................................................................... 75

3.2 调度算法 ................................................................................................................. 76

3.5 死锁 ......................................................................................................................... 96

第四章 存储器管理 ...................................................................................... 109

4.1 存储器管理的基本概念 ....................................................................................... 109

4.2 连续分配(分区管理)方式 .................................................................................... 110

4.3 基本分页存储管理方式 ....................................................................................... 113

4.4 基本分段存储管理方式 ....................................................................................... 118

4.5 段页式存储管理方式 ........................................................................................... 119

4.6 虚拟存储管理 ....................................................................................................... 121

第五章 设备管理 .......................................................................................... 135

5.1 I/O系统 ................................................................................................................. 135

5.2 I/O控制方式 ......................................................................................................... 135

5.3 缓冲管理 ............................................................................................................... 136

5.4 设备分配和设备处理 ........................................................................................... 136

5.5 磁盘存储器管理 ................................................................................................... 139

第六章 文件管理 .......................................................................................... 147

6.1 文件和文件系统基本概念 ................................................................................... 147

6.2 文件的物理结构(存储结构) ................................................................................ 151

6.3 目录管理 ............................................................................................................... 159

6.4 文件保护 ............................................................................................................... 166

6.5 文件存储空间管理 ............................................................................................... 167

第七章 操作系统接口 .................................................................................. 172

7.1 联机命令接口 ....................................................................................................... 172

7.2 Shell命令接口 ...................................................................................................... 173

7.3 系统调用 ............................................................................................................... 173

【注】试题标识(流水号)中的节号仅供参考，可依照汤小丹等编著的《计算机操作系统》(第三版)

作调整。

第一章 操作系统引论

1.1 操作系统的目标与作用

``101

计算机操作系统的功能是 。

A．把源程序代码转换为目标代码

B．实现计算机用户之间的相互交流

C．完成计算机硬件与软件之间的转换

D．控制、管理计算机系统的资源和程序的执行

``100

D

``101

操作系统是一组 。

A．文件管理程序

``100

C

``101

在操作系统中，用户界面指的是 。

A．硬件接口、软件接口和操作环境

C．硬件接口、命令接口和操作环境

``100

B

``101

以下描述与操作系统无关的是 。

A．方便用户的程序集合

B．控制和管理计算机系统的硬件和软件资源

C．计算机系统的硬件和软件资源的集合

D．合理地组织计算机工作流程

``100

C

``101

以下关于操作系统作用的叙述中，不正确的是 。

A．管理系统资源

C．改善人机界面

``100

D

1

B．中断处理程序 C．资源管理程序 D．设备管理程序

B．命令接口、程序接口和操作环境

D．硬件接口、命令接口和程序接口

B．控制程序执行

D．提高用户软件运行速度

``101

从用户的观点看，操作系统是 。

A．用户与计算机之间的接口

B．控制和管理计算机资源的软件

C．合理地组织计算机工作流程的软件

D．由若干层次的程序按一定的结构组成的有机体

``100

A

``101

下面各项中， 不是引入操作系统的最主要目的。

A．方便用户使用 B．更有效地利用软、硬件资源

D．改善系统性能 C．及时响应用户请求

``100

C

``101

操作系统在计算机系统中处于 之间的位置。

A．计算机硬件和软件

C．处理机和用户

``100

C

``101

操作系统提供给用户程序的接口是 。

A．命令解释程序 B．系统调用 C．P、V操作 D．对话框

``100

B

``101

操作系统的最主要设计目标是___________。

A．方便性和有效性 B．方便性和可扩展性

D．有效性和开放性 C．有效性和可扩展性

B．计算机硬件和用户

D．外部设备和处理机

``100

A

``101

配置了操作系统的计算机是一台比原来的物理计算机功能更强大的计算机，这样的计算机只是一台

逻辑上的计算机．称为 计算机。

A．虚拟

``100

A

2

B．物理 C．并行 D．共享

``101

操作系统是对 进行管理的软件。

A．系统软件 B．系统硬件 C．计算机资源 D．计算机程序

``100

C

``101

从用户的观点看，操作系统是 。

A．用户与计算机之间的接口

C．合理组织计算机工作流程

``100

A

``101

操作系统为用户程序完成与 的工作。

A．硬件无关和应用无关

C．硬件无关和应用相关

B．硬件相关和应用无关

D．硬件相关和应用相关

B．控制和管理计算机系统的资源

D．一个大型的工具软件

``100

B

``401

有甲、乙两道算题，每道需执行1小时（其中处理器的工作时间为12分钟）。若它们在多道系统中

执行，甲、乙两道题总共需执行80分钟，则处理器的利用率为 。

A．50% B．40% C．30% D．20%

``400

C

1.2 操作系统的发展过程

``101

_________不是分时系统的特点。

A．多个用户是经过网络连接，同时使用计算机系统

B．各用户可同时请求系统服务

C．各用户的请求彼此独立，互不干扰

D．用户以会话方式控制自己的程序运行

``100

A

``101

在 的控制下，计算机系统能及时处理由过程控制反馈的数据，并作出响应。

A．批处理操作系统

C．分时操作系统

B．实时操作系统

D．多处理机操作系统

3

``100

B

``101

分时操作系统的主要目的是 。

A．计算机系统的交互性

C．计算机系统的可靠性

``100

``101

多道批处理系统的主要缺点是 。

A．CPU利用率低

``100

``101

分时操作系统的特点是 。

A．交互性、同时性(多路性)、独立性、及时性

B．可靠性、交互性、独立性、及时性

C．可靠性、交互性、独立性、及时性

D．交互性、同时性(多路性)、独立性、动态性

``100

``101

操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互

地使用计算机。

A．网络

``100

``101

在下列操作系统中，对响应时间要求最高的是 。

A．批处理系统

``100

``101

如果分时系统的时间片一定，那么 ，则响应时间越长。

A．内存越大 B．内存越少

4

B．计算机系统的实时性

D．提高软件的运行速度

A

B．不能并发执行 C．缺少交互性 D．以上都不是

C

A

B．分布式 C．分时 D．实时

C

B．分时系统 C．实时系统 D．网络操作系统

C

C．用户数越少 D．用户数越多

``100

``101

在下列性质中，哪一个不是分时系统的特征 。

A．多路性

``100

``101

设计实时操作系统时，首先要考虑系统的 。

A．实时性和可靠性

``100

``101

UNIX操作系统是一种多用户的、人机交互的 。

A．多道批处理系统

``100

``101

实时操作系统必须在 的时间内响应一个新任务。

A．一个机器周期

``100

``101

分时系统响应时间与 有关。

A．每个应用进程分配的时间片长度

C．就绪进程数目

``100

``101

在分时系统中，下列描述中， 不属于响应时间的一部分。

A．处理机对请求信息进行处理的时间

B．从键盘输入的请求信息传送到处理机的时间

C．请求信息在外存队列上排队等待的时间

D．所形成的响应回送到终端显示器的时间

``100

5

D

B．交互性 C．独占性 D．成批性

D

B．实时性和灵活性 C．灵活性和可靠性 D．灵活性和可移植性

A

B．实时系统 C．分时系统 D．分布式系统

C

B．被控对象规定 C．任意周期 D．时间片

B

B．进程大小

D．就绪进程数目和时间片长度

D

C

1.3 操作系统的基本特征

``101

操作系统的两个最主要的特征是 。

A．并发性和虚拟性

C．共享性和异步性

``100

``101

下面各项中， 不是操作系统的基本特征。

A．并发和共享

``100

``101

下列各项中， 不是现代操作系统的主要特征。

A．并发性

``100

C

B．共享性 C．确定性 D．虚拟性

C

B．虚拟 C．交互性 D．异步

B

B．并发性和共享性

D．共享性和虚拟性

1.4 操作系统的主要功能

``101

操作系统的功能是进行处理机管理、 管理、设备管理、文件管理和作业管理等。

A．进程

``100

B

``101

下列管理功能中， 不属于操作系统的功能。

A．处理器管理 B．软件管理 C．作业管理 D．设备管理

``100

B

``101

若把操作系统看作计算机系统资源的管理者，下列的 不属于操作系统管理的资源。

A．程序

``100

B．内存 C．CPU D．中断

B．存储器 C．硬件 D．软件

6

D

``101

下列选项中， 不属于操作系统提供给用户的可使用资源。

A．中断机制

``100

A

B．处理机 C．存储器 D．I/O设备

1.5 操作系统的结构设计

``101

在操作系统中， 部分属于微内核。

A．作业调度软件 B．用户命令解释程序

D．进程通信服务例程 C．磁盘文件目录管理软件

``100

D

``101

特权指令 执行。

A．只能在目态下 B．只能在管态下

D．在目态或管态下均不能 C．在目态或管态下均能

``100

B

``101

当CPU执行操作系统代码时，称处理机处于 。

A．执行态 B．目态 C．管态 D．就绪态

``100

C

``101

指令是非特权指令。

A．启动I／O B．设置中断屏敝 C．修改PSW D．trap

``100

D

``101

“中断”的概念是指 。

A．暂停处理机执行

``100

B

7

B．暂停处理机对现行程序的执行

D．使处理机空转 C．停止整个系统运行

``101

下列中断不属于强迫性中断的是 。

A．传输结束(I/O中断)

C．运行的程序请求分配一块内存

``100

C

``101

计算机系统中设置的访管指令， 执行。

A．只能在目态 B．只能在管态

D．在目态和管态下都不能 C．既可在目态又可在管态

B．断电

D．目态程序执行特权指令

``100

C

``101

用户程序在目态下使用特权指令将引起的中断是属于 。

A．硬件故障中断 B．程序中断 C．外部中断 D．访管中断

``100

B

``101

对出现的中断事件是由 进行处理的。

A．硬件 B．操作系统 C．用户程序 D．解释程序

``100

B

``101

命令应该只在核心态下执行。

A.读时钟日期 B.计算圆周率π C.屏蔽所有中断 D.调用过程(procedure)

``100

C

``101

下列选项中，在用户态执行的是 。

A．命令解释程序 B．缺页处理程序

C．进程调度程序 D．时钟中断处理程序

``100

A

``101

下列选项中，不可能在用户态发生的事件是 。

A．系统调用 B．外部中断 C．进程切换 D．缺页

``100

C

8

``101

中断处理和子程序调用都需要压栈以保护现场，中断处理一定要保存而子程序调用不需要保存其内

容的是 。

A．程序计数器 B．程序状态字寄存器

C．通用数据寄存器 D．通用地址寄存器

``100

B

``101

在下列操作系统的各个功能组成部分中， 不需要硬件的支持。

A．进程调度 B．时钟管理 C．地址影射 D．中断系统

``100

A

``101

有关原语的说法中， 是正确的。

A．原语是不可中断执行的用户过程

C．原语是可中断执行的用户过程

B．原语是不可中断执行的操作系统过程

D．原语是可中断执行的操作系统过程

``100

B

``101

下列关于Windows NT的说法中， 是错误的。

A．Windows NT中的每一个进程都是对象，有些进程也是可以共享的资源

B．Windows NT中，进程是资源分配和处理机调度的基本单位

C．Windows NT 5.0就是Windows 2000

D．Windows NT的内核采用微内核的形式

``100

B

``101

原语应是 。

A．操作系统中的一个函数

B．操作系统中的一个过程

C．操作系统中的一个执行不可中断的过程

D．操作系统中的一个执行可中断的函数

``100

C

``101

主要由于 原因，使UNIX易于移植。

A、UNIX是由机器指令书写的 B、UNIX大部分由汇编少部分用C语言编写

C、UNIX是用汇编语言编写的 D、UNIX小部分由汇编大部分用C语言编写

9

``100

D

10

第二章 进程管理

2.1 进程的基本概念

``101

多道程序设计是指 。

A．在多台处理机上同时执行多道程序

C．在一台处理机上同时执行多道程序

B．在多台处理机上同一时刻执行多道程序

D．在一台处理机上同一时刻执行多道程序

``100

C

``101

有关进程的下列叙述中， 是正确的。

A．进程是静态的文本 B．进程与程序是一一对应的

C．进程与作业是一一对应的 D．多个进程可以在单个CPU上同时执行

``100

D

``101

进程和程序的本质区别是 。

A．存储在内存和外存 B．顺序和非顺序执行机器指令

C．分时使用和独占使用计算机资源 D．动态和静态特征

``100

D

``101

下列的进程状态变化中， 的变化是不可能发生的。

A．运行→就绪 B．运行→等待 C．等待→运行 D．等待→就绪

``100

C

``101

已获得除CPU以外的所有所需资源的进程处于 状态。

A．运行 B．就绪 C．自由 D．等待

``100

B

``101

一个进程是 。

A．由协处理器执行的一个程序 B．一个独立的程序 + 数据集

C．PCB结构、程序和数据的集合 D．一个独立的程序

11

``100

C

``101

某进程所要求的一次打印输出结束，该进程被唤醒，其进程状态将从 。

A．就绪状态到运行状态 B．等待状态到就绪状态

C．运行状态到等待状态 D．运行状态到就绪状态

``100

B

``101

进程从等待状态转到就绪状态的原因可能是 。

A．请求I/O B．I/O完成

C．被进程调度程序选中 D．另一个进程运行结束

``100

B

``101

某个进程从等待状态进入就绪状态可能是由于 。

A．现运行进程执行了启动I/O指令 B．现运行进程执行了P操作

C．现运行进程执行了V操作 D．现运行进程时间片用完

``100

C

``101

采用多道程序设计能 。

A．增加平均周转时间 B．发挥并提高并行工作能力

C．缩短每道程序的执行时间 D．降低对处理器调度的要求

``100

B

``101

在计算机系统中，允许多个程序同时进入内存并运行，这种方法称为 。

A．SPOOLing技术 B．虚拟存储技术

C．缓冲技术 D．多道程序设计技术

``100

D

``101

多道程序的引入主要是为了 。

A．提高CPU的速度 B．提高内存的存取速度

C．提高计算机的使用效率 D．减少CPU处理作业时间

``100

C

12

``101

多道程序系统中，当 时，进程从执行状态转变为就绪状态。

A．进程被进程调度程序选中 B．时间片到

C．等待某一事件 D．等待的事件发生

``100

B

``101

进程具有并发性和 两大重要属性。

A．动态性 B．静态性 C．易用性 D．封闭性

``100

A

``101

并发性是指若干事件在 发生。

A．同一时刻 B．同一时间间隔内 C．不同时刻 D．不同时间间隔内

``100

B

``101

当一个进程 就要退出等待队列而进入就绪队列。

A．启动了外设 B．用完了规定的时间片

C．获得了所等待的资源 D．能得到所等待的处理器

``100

C

``101

当输入输出操作正常结束时，操作系统将请求该操作的进程的状态设置成 。

A．等待状态 B．运行状态 C．就绪状态 D．挂起状态

``100

C

``101

进程控制块中的现场信息是在 保存的。

A．创建进程时 B．处理器执行指令时

C．中断源申请中断时 D．中断处理程序处理中断前

``100

D

``101

进程所请求的一次打印输出结束后，将使该进程状态从 。

A．运行态变为就绪态 B．运行态变为等待态

C．就绪态变为运行态 D．等待态变为就绪态

13

``100

D

``101

进程从就绪状态进入运行状态的原因可能是 。

A．等待某一事件 B．被选中占有处理器

C．时间片用完 D．等待的事件已发生

``100

B

``101

在下述进程状态的转换中， 是不可能的。

A．运行态→就绪态 B．运行态→等待态

C．等待态→就绪态 D．就绪态→等待态

``100

D

``101

单CPU系统中，关于进程的叙述正确的是 。

A．一个处于等待状态的进程一旦分配了CPU，即进入运行状态

B．只能有一个进程处于就绪状态

C．一个进程可以同时处于就绪状态和等待状态

D．最多只有一个进程处于运行状态

``100

D

``101

多道程序设计能充分发挥 之间的并行工作能力。

A．CPU与外设 B．进程与进程 C．内存与进程 D．内存与外设

``100

A

``101

一个进程的基本状态可以从其它两种基本状态转变过去，这个基本状态一定是 。

A．执行状态 B．阻塞状态 C．就绪状态 D．完成状态

``100

C

``101

进程具有的特性包括： 。

①动态性 ②共享性 ③并发性 ④相互制约性 ⑤独立性 ⑥静态性

A．①③④⑤ B．①②④⑤ C．②④⑤⑥ D．①②④⑥

``100

A

14

``101

进程控制块记录了进程执行时的情况，它的内容可由 进行修改。

A．操作系统 B．进程自己 C．中断装置 D．用户

``100

A

``101

当一个进程正等待着 时，称其为等待状态。

A．合作进程的一个消息 B．分配给它一个时间片

C．调度程序选中它 D．进入内存

``100

A

``101

下列说法中，正确的是 。

A．一般来说，用户进程的PCB存放在用户区，系统进程的PCB存放在系统区

B．某进程的一个线程处于阻塞状态，则该进程必然处于阻塞状态

C．在多道程序设计环境中，为了提高CPU效率，内存中的进程越多越好

D．同步是指并发进程之间存在的一种制约关系

``100

D

``101

下列叙述中，正确的叙述是 。

A. 实现多道程序设计的目的是提高程序员编程的效率

B. 在有虚拟存储器的系统中，可以运行比主存容量还大的程序

C. 操作系统的目的是为了提高计算精度

D. 操作系统必须具备分时系统

``100

B

``101

操作系统中，资源分配的基本单位是 。

A．进程 B．线程 C．作业 D．程序

``100

A

``001

若进程Pa、Pb和Pc单独执行时间分别是1小时、1.5小时和2小时，其中处理机工作时间分别为

10分钟、15分钟和35分钟。如果采用多道程序设计方法，让Pa、Pb和Pc并行工作，假定处理机

利用率达到50%，请问系统效率能提高百分之几？

``000

答：Pa、Pb和Pc并行工作时总共使用CPU时间为：

15

(10+15+35)/50%=120 (分钟)

单道方式执行时总时间为60+90+120=270分钟

故系统效率提高：(270-120)/270*100%=55.56%

3分

6分

10分

2.2 进程控制

``101

下列选项中，导致创建新进程的操作是 。

I．用户登录成功 II．设备分配 III．启动程序执行

A．仅I和II B．仅II和III C．仅I和III D．I、II和III

``100

C

``101

通常，用户进程被建立后， 。

A．便一直存在于系统中，直到被操作人员撤消

B．随着程序运行正常或异常结束而撤消

C．随着时间片轮转而撤消与建立

D．随着进程的阻塞或唤醒而撤消与建立

``100

B

``101

在具有挂起状态的系统中，若当前内存空间高度吃紧，系统将使一个正在等待I/O的进程进入

__________状态。

A．活动就绪 B．静止就绪 C．活动阻塞 D．静止阻塞

``100

D

``101

在下述关于父进程和子进程的叙述中，正确的是 。

A．父进程创建了子进程，因此父进程执行完了，子进程才能运行

B．子进程执行完了，父进程才能运行

C．撤消子进程时，应该同时撤消父进程

D．一个子进程只有一个父进程，但一个父进程可以有多个子进程

``100

D

2.3 进程同步

``101

进程之间的制约关系可以归结为 。

A．同步与互斥 B．并发与异步

``100

16

C．同步与并发 D．同步与异步

A

``101

在多道程序系统中，为了保证公共变量的完整性，各进程应互斥进入相关临界区。所谓临界区是

指 。

A．一个缓冲区 B．一段数据区 C．同步机制 D．一段程序

``100

D

``101

两个进程合作完成一个任务，在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个

条件后再向前执行，这种关系称为进程间的 。

A．同步 B．互斥 C．竞争 D．合作

``100

A

``101

使若干并发进程共享一临界资源而不发生与进程推进速度有关错误，涉及相关临界区的错误说法

是 。

A.“一次最多让一个进程在临界区执行”

B.“任何一个进入临界区执行的进程必须在有限时间内退出临界区”

C.“可以强迫一个进程无限地等待进入它的临界区”

D.“可能没有任何进程在临界区执行”

``100

C

``101

下面叙述中正确的是 。

A．操作系统的一个重要概念是进程，因此不同进程所执行的代码也一定不同

B．为了避免发生死锁，各进程只能逐个申请资源

C．操作系统用PCB管理进程，用户进程可以从PCB中读出与本身运行状态有关的信息

D．进程同步是指某些进程之间在逻辑上的相互制约关系

``100

D

``101

有关并发进程相互之间的关系，正确的说法是 。

A．肯定是无关的 B．肯定是有交往的

C．可能是无关的，也可能是有交往的 D．一定要互斥执行

``100

C

``101

并发进程执行时可能会出现与时间有关的错误，这种错误是与 无关的。

17

A．使用共享资源 B．进程被打断的时间

C．进程占用处理器的总时间 D．进程交替执行的次序

``100

C

``101

若信号量S的初值为2，当前值为-1，则表示有 个等待进程。

A．0 B．1 C．2 D．3

``100

B

``101

设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源

的进程数，则M、N分别是 。

A．0、1 B．1、0 C．1、2 D．2、0

``100

B

``101

操作系统中，对信号量S的P原语操作定义中，使进程进入相应等待队列的条件是 。

A．S≠0 B．S<0 C．S=0 D．S>0

``100

B

``101

有关PV操作的说法中 是错误的。

A.“PV操作不仅是进程互斥的有效工具，而且是简单方便的同步工具”

B.“PV操作不能实现进程间通信”

C.“进程调用P操作测试自己所需的消息是否到达”

D.“进程调用V操作向其它进程发送消息”

``100

B

``101

有n个并发进程竞争必须互斥使用的共享资源时，若某进程调用P操作后成为第一个等待使用该资

源者，则这时信号量的值为 。

A．0 B．1 C．-1 D．n-1

``100

C

``101

、是信号量S的两个组成部分，当为空时，的值是 。

A、≤0 B、=0 C、=1 D、Svalue≥0

``100

18

D

``101

设有三个进程共享一个资源，如果每次只允许一个进程使用该资源，则用PV操作管理时信号量S

的可能取值是 。

A、1,0,-1,-2 B、2,0,-1,-2 C、1,0,-1 D、3,2,1,0

``100

A

``101

多个进程间可通过P、V操作交换信息实现进程同步和互斥，因此信号量机制是进程间的一种

_________通信方式。

A．高级 B．低级 C．消息缓冲 D．间接

``100

B

``101

某计算机系统中若同时存在5个进程，则处于等待状态的进程最多可有 个。

A．0 B．1 C．4 D．5

``100

C

``101

若系统中有5个并发进程都涉及某个共享变量A，则A的相关临界区是由 临界区构成。

A．2个 B．3个 C．4个 D．5个

``100

D

``101

设有n个进程使用同一个共享变量，如果最多允许m（m < n）个进程同时进入相关临界区，则信号

量的变化范围是 。

A．n,n-1,...,n-m B．m,m-1,...1,0,-1,...m-n

C．m,m-1,...1,0,-1,...m-n-1 D．m,m-1,...1,0,-1,...m-n+1

``100

B

``101

对于有两个并发进程的系统，设互斥信号量为mutex，若mutex=0，则 。

A．表示没有进程进入与mutex相关的临界区

B．表示有一个进程进入与mutex相关的临界区

C．表示有一个进程进入与mutex相关的临界区，另一个进程等待进入

D．表示有两个进程进入与mutex相关的临界区

``100

B

19

``101

在有m个进程的系统中出现死锁时，死锁进程的个数k应满足的条件是 。

A．k≥2 B．1＜k＜m C．1＜k≤m D．k≥1

``100

B

``101

在一个单处理机系统中，若有4个用户进程，且假设当前时刻为用户态，则处于就绪状态的用户进

程至少有 个。

A．0 B．1 C．2 D．3

``100

A

``101

如果单CPU系统中有n个并发进程，则就绪队列中进程个数最多可达 个。

A．n B．n-1 C．n-2 D．1

``100

B

``101

为了使两个进程能同步运行，最少需要 个信号量。

A．1 B．2 C．3 D．4

``100

B

``101

对具有相关临界区的n个并发进程采用P、V操作实现进程互斥时，信号量的初值应定义为 。

A．0 B．1 C．n D．n-1

``100

B

``101

涉及PV操作的正确说法是 。

A．PV操作只能解决进程互斥问题

B．PV操作只能解决进程同步问题

C．PV操作能用于解决进程互斥问题，也能解决进程同步问题

D．PV操作是一种高级通信方式

``100

D

``101

在同一系统中，假设同时存在为两个相互独立的C++源程序进行编译的两个进程(它们使用同一个编

译程序)，它们之间的关系正确的是： 。

20

A．它们可以并发执行，两者逻辑上有依赖关系

B．它们可以并发执行，两者逻辑上无依赖关系

C．它们不可以并发执行，但两者逻辑上有依赖关系

D．它们不可以并发执行，因为两个进程运行的是同一个编译程序

``100

B

``201

进程P0和P1的共享变量定义及其初值为：

boolean flag[2];

int turn=0;

flag[0]=FALASE; flag[1]=FALSE;

若进程P0和P1访问临界资源的类C伪代码实现如下：

void P0( ) //进程P0

{ while(TRUE) {

flag[0]=TRUE; turn=1;

while(flag[1] && (turn==1)) ;

临界区;

flag[0]=FALSE;

}

}

void P1( ) //进程P1

{ while(TRUE) {

flag[1]=TRUE; turn=0;

while(flag[0] && (turn==0)) ;

临界区;

flag[1]=FALSE;

}

}

则并发执行进程P0和P1时产生的情形是 。

A．不能保证进程互斥进入临界区，会出现“饿死”现象

B．不能保证进程互斥进入临界区，不会出现“饿死”现象

C．能保证进程互斥进入临界区，会出现“饿死”现象

D．能保证进程互斥进入临界区，不会出现“饿死”现象

``200

D

``201

有两个并发进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的

指令序列分别如下所示。

//加1操作 //减1操作

load R1, x //取x到寄存器R1中 load R2, x

inc R1 dec R2

store x, R1 //将R1的内容存入x store x, R2

两个操作完成后，x的值 。

A．可能为-1或3 B．只能为1

C．可能为0、1或2 D．可能为-1、0、1或2

``200

C

21

2.4 经典进程同步问题(P、V操作解决进程同步问题)

``101

有三个进程，Reader进程读入数据number1，将其放入缓冲器B

1

，Executor进程将B

1

中数据取出，

处理成数据number2，将其放入缓冲器B

2

，Printer进程将number2数据取出打印，假设B

1

和B

2

只能存放一个数据，用P、V操作管理这三个进程的执行。

``100

BEGIN

semaphore empty1, full1, empty2, full2 ;

= = 1 ;

= = 0 ; 4分

PARBEGIN

Reader：BEGIN

L1：read number1 ;

P(empty1) ;

B1=number1 ;

V(full1) ;

goto L1；

END 6分

Executor：BEGIN

L2：P(full1) ;

take number1 from B1 ;

V(empty1) ;

Process number1-->number2 ;

P(empty2) ;

B2=number2 ;

V(full2) ;

goto L2；

END 8分

Printer：BEGIN

L3：P（full2）；

take number2 from B2 ;

V(empty2) ;

Print(number2) ;

goto L3；

END 10分

PAREND

END

``101

若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D

只从盘中取梨子。试用信号量和P、V操作写出同步算法。

``100

semaphore SAB=1; //A、B的资源信号量，同时又是它们的互斥信号量

22

semaphore SC=0; //C的资源信号量(用于与A同步)

semaphore SD=0; //D的资源信号量(用于与B同步)

begin

parbegin

process A: //进程A的算法描述

{

while(true) {

取一个苹果；

wait(SAB); //测试盘子是否为空

将一苹果放入盘中；

signal(SC) //通知C盘中已有苹果(可能唤醒C)

}

}

process C:

{

while(true) {

wait(SC); //测试盘子是否有苹果

从盘中取出苹果;

signal(SAB); //通知A(或B)盘子一空(可能唤醒A或B)

消费该苹果;

}

}

process B: //进程B的算法描述

{

while(true) {

取一个梨子；

wait(SAB); //测试盘子是否为空

将一梨子放入盘中；

signal(SD) //通知D盘中已有梨子(可能唤醒D)

}

}

process D:

{

while(true) {

wait(SD); //测试盘子是否有梨子

从盘中取出梨子;

signal(SAB); //通知A(或B)盘子一空(可能唤醒A或B)

消费该梨子;

}

}

parend

end

``201

23

2分

4分

6分

8分

10分

设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4

个工人，他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3分别加

工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取

两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作。

``200

BEGIN

semaphore Aempty，Bempty，Afull，Bfull，mutex；

Aempty ：= 8；Bempty ：= 20；Afull ：= 0；Bfull ：= 0；mutex ：=1； 4分

PARBEGIN

Worker1：BEGIN

L1：生产1个车架；

P（Aempty）； //测试货架A是否有空位置

P（mutex）； //互斥使用货架A

车架放到货架A；

V（Afull）； //货架A上的车架数增1，必要时唤醒等待的进程

V（mutex）；

goto L1；

END 6分

Worker2、3：BEGIN

L2：生产1个车轮；

P（Bempty）； //测试货架B是否有空位置

P（mutex）； //互斥使用货架B

车轮放到货架B；

V（Bfull）； //货架B上的车轮数增1，必要时唤醒等待的进程

V（mutex）；

goto L2；

END 8分

Worker4：BEGIN

L3：P（Afull）； //测试货架A上是否有车架

P（Bfull）；P（Bfull）； //测试货架B上是否有2个车轮

P（mutex）；

取1个车架；取2个车轮；

V（Aempty）； //货架A空位置增1

V（Bempty）；V（Bempty）；//货架B空位置增2

V（mutex）；

组装成一辆自行车；

goto L3；

END 10分

PAREND

END

``201

假定有一个成品仓库，总共能存放8台成品，生产者进程把生产成品放入仓库，消费者进程从仓库

中取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存

24

入和取出只能分别进行，试用P、V操作来实现该方案。

``200

semaphore mutex, empty, full ;

mutex=1; //互斥信号量

empty=8; //生产者进程的同步信号量

full=0; //消费者进程的同步信号量 4分

parbegin

process Pi //生产者进程

{

while (1) {

生产一个成品x;

P(empty) //看看仓库是否还有空间可放成品

P(mutex); //互斥使用搬运设备

用搬运设备将成品放入仓库;

V(full); //仓库中成品数增1(可能唤醒一个消费者)

V(mutex); 7分

}

}

process Cj //消费者进程

{

while (1) {

P(full) //看看仓库是否有成品

P(mutex); //互斥使用搬运设备

用搬运设备将成品从仓库取出;

V(emtpy); //仓库中可放成品数增1(可能唤醒一个生产者)

V(mutex); 10分

}

}

parend

``201

有三个进程R、W1、W2共享一个缓冲器Ｂ，而B中每次只能存放一个数。当B中无数时，进程R

可将从输入设备上读入的数存放到缓冲器B中；若存放到B中的是奇数，则允许进程W1将其取出

打印；若存放到B中的是偶数，则允许进程Ｗ2将其取出打印；同时规定：进程R必须等缓冲器中

的数被取出后才能再存放下一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；Ｗ1和

Ｗ2都不能从空的缓冲器中取数。用P、V操作作为同步机制写出三个并发进程的同步算法。(动作

部分可用文字描述)

``200

semaphore S,S1,S2;

S=1; S1=S2=0; 4分

parbegin

Process R

{

while (1) {

25

从输入设备上读入的数x;

P(S);

B=x;

if (x%2==1) V(S1); //若是奇数，则通知W1

else V(S2); //若是偶数，则通知W2

}

}

Process W1

{

while (1) {

P(S1);

y=B;

V(S);

Print(y);

}

}

Process W2

{

while (1) {

P(S2);

y=B;

V(S);

Print(y);

}

}

parend

6分

//看看缓冲器B中是否有奇数

//从缓冲器B中取奇数存于y

//通知R，缓冲器已空，可以在往里存数了

//打印 8分

//看看缓冲器B中是否有偶数

//从缓冲器B中取偶数存于y

//通知R，缓冲器已空，可以在往里存数了

10分

``201

进程P1使用缓冲区buffer向进程P2，P3，P4发送消息，要求每当Pl向buffer中发消息时，只有当

P2，P3，P4进程都读取这条消息后P1才可向buffer中发送新的消息。试用信号量机制描述各进程

的动作过程。

``200

解法一：

semaphore S1,S2,S3,S4;

=3;===0; 4分

parbegin

process P1

{

while (condition)

{

P1生成一个消息；

P（S1）；P（S1）；P（S1）；

P1将消息存入缓冲区buffer；

V（S2）；V（S3）；V（S4）； 7分

26

}

}

process Pi(i=2,3,4)

{

while （condition）

{

P（Si）；

Pi从buffer中取出消息；

V（S1）；

Pi消费（使用）该消息；

}

}

parend

解法二：

semphore S1[3], S[3];

for (i=0;i<3;i++) {

S1[i]=1;

S[i]=0;

}

parbegin

process P1

{

while (1) {

P1生成一个消息；

for (i=0;i<3;i++) P(S1[i]); //看看P2～P4是否将消息取走

P1将消息存入缓冲区buffer；

for (i=0;i<3;i++) V(S[i]); //通知P2～P4缓冲区buffer中已有消息

}

}

Process P2

{

while(1) {

P(S[0]); //看看buffer中是否已有消息

从buffer中取出消息;

V(S1[0]); //通知P1, P2已从缓冲区buffer中取走消息

消费（使用）该消息;

}

}

Process P3

{

while(1) {

P(S[1]); //看看buffer中是否已有消息

从buffer中取出消息;

V(S1[1]); //通知P1, P3已从缓冲区buffer中取走消息

27

10分

消费（使用）该消息;

}

}

Process P4

{

while(1) {

P(S[2]); //看看buffer中是否已有消息

从buffer中取出消息;

V(S1[2]); //通知P1, P4已从缓冲区buffer中取走消息

消费（使用）该消息;

}

}

parend

``201

三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce( )生成一个正

整数并用put( )送入缓冲区某个单元中；P2每次用getodd( )从缓冲区中取出一个奇数并用countodd( )

统计奇数个数；P3每次用geteven( )从缓冲区中取出一个偶数并用counteven( )统计偶数个数。请用

信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

``200

定义P1的资源信号量empty来表示缓冲区中空单元个数，用于P1与P2、P3的同步；定义P2

的资源信号量S1来表示缓冲区中奇数的个数，用于P2和P1的同步；定义P3的资源信号量

S2来表示缓冲区中偶数的个数，用于P3和P1的同步；定义互斥信号量mutex，用于三个进程

互斥访问缓冲区。算法描述如下：

var empty,s1,s2,mutex: semaphore := N,0,0,1; 4分

Parbegin

P1: begin

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

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

P(mutex); /* 是否有进程访问缓冲区 */

put( ); /* 将生成的数送入缓冲区的某个单元 */

if x mod 2=0 then

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

else

V(S1); /*如果是奇数，向P2发出信号 */

V(mutex); 6分

end

P2: begin

P(S1); /* 缓冲区中是否有奇数 */

P(mutex);

getodd( );

V(empty); /* 向P1发出信号 */

V(mutex);

countodd( ); 8分

28

end

P3: begin

P(S2);

P(mutex);

geteven( );

V(empty);

V(mutex);

counteven( );

end

Parend

``201

10分

设有n个缓冲区构成的循环缓冲区，每个缓冲区能容纳一个整数。写进程Writer把整数逐个存入缓冲

区，读进程Reader则逐个从缓冲区中读出并打印输出，要求打印的与输入的完全一样，即个数、次

序、数值一样。试问：

（1）写进程与读进程间具体的制约关系如何？

（2）用PV操作写出这两个进程的同步算法程序。

``200

解：(1) 写进程与读进程间具体的制约关系是同步和互斥关系。 2分

(2) 采用PV操作的同步算法程序如下：

semaphore mutex, empty, full;

mutex=1; //互斥信号量，用于两个进程互斥访问缓冲区

empty=n; //同步信号量，表示空闲缓冲区的数量

full=0; //同步信号量，表示放有整数的缓冲区个数 4分

parbegin

process Writer( )

{

while (1) {

produce_an_integer( );

P(empty);

P(mutex);

write_an_integer_to_buffer( );

V(mutex);

V(full); 7分

}

}

process Reader( )

{

while (1) {

P(full);

P(mutex);

get_an_integer_from_buffer( );

V(mutex);

V(empty);

29

print_an_integer( );

}

}

parend

10分

``201

某庙寺有小和尚、老和尚若干。有一水井和一个水缸，由小和尚提水入缸供老和尚饮用。水缸可容

纳10桶水，水取自同一井中。水井很窄，每次只能容一个水桶打水。水桶总数为3个。每次入水、

取水仅为1桶水，且不可同时进行。试用信号量同步机制，写出小和尚和老和尚入水、取水的活动

过程。

``200

semaphore mutex, empty, full, S;

mutex=1; //互斥信号量

empty=10; //小和尚的资源信号量，用于与老和尚同步，假设开始时水缸为空

full=0; //老和尚的资源信号量，用于与小和尚同步

S=3; //水桶资源信号量

parbegin

小和尚i (i=1, 2, ... , m) //m个小和尚进程

{

while (1) {

P(S); //取一水桶，准备入水

P(empty); //看看水缸是否还有空间入水

P(mutex); //互斥

从水井取水，倒入水缸中;

V(mutex);

V(full); //通知老和尚，水缸中已增加了一桶水

V(S); //释放水桶

}

}

老和尚j (J-1, 2, ... , n) //n个老和尚进程

{

while (1) {

P(S); //取一水桶，准备取水

P(full); //看看水缸中是否有水

P(mutex);

从水缸中取一桶水;

V(mutex);

V(empty); //水缸增加一个桶空间

V(S); //释放水桶

饮用水;

}

}

parend

30

4分

7分

10分

``501

现有3个生产者P1、P2、P3，他们都要生产桔子水，每个生产者都已分别购得两种不同原料，待购

得第三种原料后就可配制成桔子水，装瓶出售。有一供应商能源源不断地供应糖、水、桔子精，但

每次只拿出一种原料放入容器中供给生产者。当容器中有原料时需要该原料的生产者可取走，当容

器空时供应商又可以放入一种原料。假定：

生产者P1已购得糖和水；

生产者P2已购得水和桔子精；

生产者P3已购得糖和桔子精。

试用信号量和P、V操作，写出供应商和3个生产者之间能正确同步的算法。

``500

semaphore empty, ful1a, fullb, fullc;

empty=1; //开始时容器是空的，可以放一种原料

fulla=0; //开始时容器中无桔子精，用于阻塞P1

fullb=0; //开始时容器中无糖，用于阻塞P2

fullc=0; //开始时容器中无水，用于阻塞P3 2分

parbegin

process 供应商

{

while (true) {

随机地取一种原料x;

P(empty); //看看容器是否空，不空则等待

将x放入容器中;

if (x是桔子精) V(fulla); //通知（或唤醒）P1

else if (x是糖) V(fullb); //通知（或唤醒）P2

else V(fullc); //通知（或唤醒）P3 4分

}

}

process P1

{

while (true) {

P(fulla); //看看容器中是否有桔子精，若无则阻塞

从容器中取出桔子精;

V(empty); //通知供应商，容器空了。若供应商因容器不空而阻塞，则唤醒之

用三种原料配制成桔子水，装瓶出售; 6分

}

}

process P2

{

while (true) {

P(fullb); //看看容器中是否有糖，若无则阻塞

从容器中取出糖;

V(empty); //通知供应商，容器空了。若供应商因容器不空而阻塞，则唤醒之

用三种原料配制成桔子水，装瓶出售; 8分

}

31

}

process P3

{

while (true) {

P(fullc); //看看容器中是否有水，若无则阻塞

从容器中取出糖;

V(empty); //通知供应商，容器空了。若供应商因容器不空而阻塞，则唤醒之

用三种原料配制成桔子水，装瓶出售; 10分

}

}

parend

``501

某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A、B两种零件，装配车间的任务

是把A、B两种零件装配成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的

货架F1、F2上，F1存放零件A，F2存放零件B，F1与F2的容量均为可以存放10个零件。装配

工人每次从货架上取一个A零件和一个B零件，然后组装成产品。请用信号量和P、V操作进行正

确的管理。

``500

semaphore mutex, empty1, empty2, full1, full2;

mutex=1; //互斥信号量，用于互斥使用货架

empty1=10; //同步信号量，表示货架F1可容纳的零件数

empty2=10; //同步信号量，表示货架F2可容纳的零件数

full1=0; //同步信号量，表示货架F1已放的零件数

full2=0; //同步信号量，表示货架F1已放的零件数 4分

parbegin

process workerAi ( ) //第一个生产车间的工人进程，i=1, 2, ... , n

{

while (1) {

生产一个零件A;

P(empty1); //测试货架F1是否可放零件A

P(mutex);

将一个零件A放到货架F1上;

V(mutex);

V(full1); 6分

}

}

process workerBj ( ) //第二个生产车间的工人进程，j=1, 2, ... , m

{

while (1) {

生产一个零件B;

P(empty2); //测试货架F2是否可放零件B

P(mutex);

将一个零件B放到货架F2上

32

V(mutex);

V(full2);

}

8分

}

process workerC

i

( ) //装配车间的工人进程，i=1, 2, ... , k

{

while (1) {

P(full1); //测试货架F1是否可放零件A

P(mutex);

从货架F1上取一个零件A

V(mutex);

V(empty);

P(full2);

P(mutex);

从货架F2上取一个零件B

V(mutex);

V(empty);

用零件A、B组装成一个产品;

}

}

parend

10分

``201

有三个并发进程A、B和C，共享一个缓冲器F。F中每次只能存放一个数。进程A每次产生一个

随机数R，将其存入F中。若存放到F中的数是5的倍数，则由进程B将其取出并打印，否则由进

程C将被5除后的余数打印出来。为防止数的丢失和重复取同一个数，请用信号量和P、V操作进

行正确的管理。

``200

begin

S1,S2,S3:semaphore;

F : integer;

S1:=1; S2:=0; S3:=0; 4分

cobegin

process A

begin

L1: 产生随机数R;

P(S1) ;

F:= R;

if R mod 5=0 then

V(S2);

else V(S3); 6分

goto L1;

end;

process B

33

begin

L2: P(S2);

x := F;

V(S1);

print x;

goto L2;

end;

process C

begin

L3: P(S3);

y := F;

V(S1) ;

y := y mod 5;

print y;

goto L3;

end;

coend;

end;

8分

10分

``201

今有一个文件F供进程共享，现把这些进程分成A、B两组，规定同组的进程可以同时读文件F；

但当有A组（或B组）的进程在读文件F时就不允许B组（或A组）的进程读文件F。试用P、V

操作来进行管理。

``200

begin

S1，S2，SAB：semaphore；

C1，C2：integer；

S1 := 1；S2 := 1；SAB := 1；C1 := 0；C2 := 0； 4分

parbegin

Process A

i

（i = 1，2，3，...）

begin

P（S1）；

C1 := C1 + 1 ；

if C1 = 1 then P（SAB）；

V（S1）；

Read file F ；

P（S1）；

C1 := C1 – 1 ；

if C1 = 0 then V（SAB） ；

V（S1）； 7分

end；

Process B

i

（i = 1，2，3，...）

begin

P（S2）；

34

C2 := C2 + 1 ；

if C2 = 1 then P（SAB）；

V（S2）；

Read file F ；

P（S2）；

C2 := C2 – 1 ；

if C2 = 0 then V（SAB） ；

V（S2）；

end；

parend；

end；

10分

``501

有P1、P2、P3三个进程共享一个表格F，P1对F只读不写，P2对F只写不读，P3对F先读后写。

进程可同时读F，但有进程写时，其他进程不能读和写。请用信号量和P、V操作，编写三个进程

能正确工作的算法程序。

``500

semaphore Rmutex, mutex;

Rmutex=mutex=1; //前者用于互斥访问共享变量Rcount，后者用于写互斥

int Rcount=0; //读者计数变量 4分

parbegin

process P1

{

P(Rmutex); //互斥访问共享变量Rcount

Rcount=Rcount+1; //读者数增1

if (Rcount==1) P(mutex); //第一个读者应与写者互斥

V(Rmutex);

read F;

P(Rmutex);

Rcount=Rcount-1; //读者离开，读者数减1

if (Rcount==0) V(mutex); //最后一个写者离开时应允许写者写

V(Rmutex); 6分

}

process P2

{

P(mutex);

write F;

V(mutex); 8分

}

process P3

{

P(Rmutex); //前半部分与P1相同

Rcount=Rcount+1;

if (Rcount==1) P(mutex);

35

V(Rmutex);

read F;

P(Rmutex);

Rcount=Rcount-1;

if (Rcount==0) V(mutex);

V(Rmutex);

P(mutex); //后半部分与P2相同

write F;

V(mutex);

}

parend

10分

``501

假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记

表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。

要求：（1）用PV操作描述读者进程的同步算法（登记、注销可用自然语言描述）；

（2）指出算法中所用信号量的名称、作用及初值。

``500

解：（1）用PV操作描述读者进程的同步算法如下：

semaphore mutex=1, seat=50; 2分

parbigin

process reader

i

(i=1, 2, 3, …)

begin

读者来到阅览室;

P(seat); //看看阅览室是否有空位置 4分

P(mutex); //登记需互斥

在登记表上登记;

V(mutex); 6分

在阅览室阅览资料;

P(mutex);

在登记表上注销;

V(mutex);

V(seat); //阅览室空座位数增1，必要时唤醒等待进入阅览室的读者 8分

该读者离开;

end

parend

（2）互斥信号量mutex，其初值为1，用于互斥使用登记表；资源信号量seat，其初值为50，

用于表示阅览室空座位的数量。 10分

``501

在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系

统有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次拣一子；当进程在拣时，

不允许另一个进程取拣；当一个进程拣了一子时，必须让另一进程去捡。假设从拣白子开始。试写

出量进程能正确并发执行的算法程序。

36

``500

semaphore mutex, S1, S2;

mutex=1; //互斥信号量

S1=1; //P1的同步信号量，用于与P2同步，从P1拣第一个白子开始

S2=0; // P2的同步信号量，用于与P1同步 4分

parbegin

Process P1

{

while (1) {

P(S1);

P(mutex); //拣子必须互斥

拣一白子;

V(mutex);

V(S2); //通知P2可以拣一黑子了 7分

}

}

Process P2

{

while (1) {

P(S2); //看看P1是否已捡完一个白子

P(mutex); //拣子必须互斥

拣一黑子;

V(mutex);

V(S1); //通知P1可以拣一白子了 10分

}

}

parend

``501

仅有k个进程，它们的标号依次为1，2，…，k，允许它们同时读文件file，但必须满足条件：参加

同时读文件的进程的标号之和需小于或等于k，请使用：(1) 信号量与P、V操作，编写协调多进程

读文件的算法程序。

``500

semaphore mutex=1; //互斥信号量，用于互斥访问共享变量sum

semaphore S=0; //用于阻塞不能读文件的进程

int sum=0; //用于记录和的值，若和大于k，则在S上阻塞

int count=0; //用于记录在S上阻塞的进程数 4分

Parbegin

process Pi (i=1,2,3, ..., k)

{

L1: P(mutex);

if (i+sum>k)

{

count ++; //阻塞进程数增1

37

V(mutex);

P(S);

goto L1;

}

else

{

sum=sum+i;

V(mutex);

}

Read File;

P(mutex);

sum=sum-i;

while (count>0)

{

V(S);

count --;

}

V(mutex);

}

Parend

//允许其它进程读

//本进程阻塞

//进程被唤醒后从L1重新开始执行

//唤醒所有在S上阻塞的进程

//也可只唤醒一个阻塞进程，但并发度降低

10分

``401

有三个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区buffer1，

每执行一次读一个记录；PB将缓冲区1的记录复制到缓冲区buffer2，每执行一次复制一个记录；

PC将缓冲区buffer2的内容打印出来，每执行一次打印一个记录。缓冲区的大小和一个记录大小一

样。试用P、V操作来保证文件的正确打印。

``400

解：BEGIN

semaphore mutex1，mutex2，avail1，avail2，full1，full2；

mutex1 ：= 1；mutex2 ：= 1；

avail1 ：= 1；avail2 ：= 1；

full1 ：= 0；full2 ：= 0； 4分

PARBEGIN

PA：BEGIN

L1：read from disk；

P（avail1）；

P（mutex1）；

put to buffer 1；

V（full1）；

V（mutex1）；

goto L1； 6分

END

PB：BEGIN

L2：P（full1）；

38

P（mutex1）；

get from buffer 1；

V（avail1）；

V（mutex1）；

P（avail2）；

P（mutex2）；

put to buffer 2；

V（full2）；

V（mutex2）；

goto L2 ；

END

PC：BEGIN

L3：P（full2）；

P（mutex2）；

get from buffer 2；

V（avail2）；

V（mutex2）；

print RECORD

goto L3 ；

END

PAREND

END

8分

10分

``501

由三个进程get，copy和put以及两个缓冲区buffer1和buffer2完成一项输入/输出操作。进程get

的功能是把一张卡片上的信息从读卡机上读进buffer1；进程copy的功能是把buffer1中的信息复制

到buffer2；进程put的功能是取出buffer2中的信息并从打印机上打印输出。试用P、V操作完成这

三个进程间的尽可能并发正确执行的关系(用程序或框图表示)，并指明信号量的作用和初值。

``500

解：可设置6个信号量mutex1，mutex2，empty1，empty2，full1，full2。其中：

mutex1和mutex2是互斥信号量，初值为1，分别用于对buffer1和buffer2的互斥访问；

empty1和empty2为同步信号量，初值为1，分别表示buffer1和buffer2是否空闲，1表示空闲，

0表示不空闲；

full1和full2为同步信号量，初值为0，分别表示buffer1和buffer2中是否有可取用的信息，1

表示有可取用的信息，0表示无可取用的信息。 2分

semaphore mutex1, mutex2, empty1, empty2, full1, full2 ;

mutex1=mutex2=1; //互斥信号量

empty1=empty2=1; //生产者进程的同步信号量

full1=full2=0; //消费者进程的同步信号量 5分

parbegin

process get( ) //读进程(生产者进程)

{

39

while (1) {

从读卡机读入一张卡片的信息;

P(empty1) //看看buffer1是否空闲

P(mutex1); //互斥访问buffer1

将信息放入buffer1;

V(mutex1);

V(full1);

}

7分

}

process copy( ) //复制进程(既是消费者又是生产者进程)

{

while (1) {

P(full1) //看看buffer1是否有信息可取

P(mutex1); //互斥访问buffer1

从buffer1中复制出信息;

V(mutex1);

V(emtpy1); //通知get，buffer1中的信息已取走(可能唤醒get)

P(empty2); //看看buffer2是否空闲

P(mutex2); //互斥访问buffer2

将复制的信息放入buffer2;

V(mutex2);

V(full2); //通知put，buffer2中已有信息

}

}

process put( ) //输出进程(消费者进程)

{

while (1) {

P(full2); //测试buffer2中是否有信息

P(mutex2); //互斥访问buffer2

从buffer2中取出信息;

V(mutex2);

V(empty2); //通知copy，buffer2中的信息已取走

}

}

parend

9分

10分

``401

今有3个并发进程R、M、P，它们共享一个缓冲器B。进程R负责从输入设备读入信息，每读一

个记录后把它存放在缓冲器B中。进程M在缓冲器B中加工进程R存入的记录。进程P把加工后

的记录打印出来。缓冲器B中每次只能存放一个记录，当记录被加工输出后，缓冲器B中又可以存

放一个新的记录。为协调它们的工作，采用PV操作进行管理。

``400

40

解：semaphore SR,SM,SP;

SR=1; SM=0; SP=0;

parbegin

Process R

{

while (1) {

从输入设备读入信息X;

P(SR); //看看缓冲区B是否是空的

B=X; //信息存入缓冲区B

V(SM); //通知M，缓冲区B中已有记录

}

}

Process M

{

while (1) {

P(SM); //测试R是否已在B中存放信息

在缓冲器B中加工进程R存入的记录;

V(SP); //通知P缓冲区B中的信息已可打印

}

}

Process P

{

while (1) {

P(SP); //测试M是否已将信息加工好

从B中取M加工后的信息Y;

V(SR); //通知R，缓冲区B已可房信息

Print(Y); //打印信息Y

}

}

parend

3分

6分

8分

10分

``601

进程A1，A2，...，An1通过m个缓冲区向进程B1，B2，...，Bn2不断地发送消息。发送和接收

工作遵循如下规则：

① 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样；

② 对每个消息，B1，B2，...，Bn2都需各接收一次，读入到各自的数据区内；

③ m个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。

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

提示：这是P-C问题变形。把这一组缓冲区看成n2组缓冲区。

``600

解：设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组empty[n2]和full[n2]

描述n2组缓冲区的使用情况。mutex初值为1，数组empty的元素初值为m，数组full的元素初值

41

0。

var mutex: semaphore :=1;

empty,full: 2-1] of semaphore;

i: integer;

for (i=0;i

{

empty[i]=m;full[i]=0;

}

Aj ( ) //j=1,2,...,n1

{

while (1) {

......

for (int i=0;i

P(empty[i]);

P(mutex);

将消息放入缓冲区；

V(mutex);

for (i=0;i

V(full[i]);

......

}

}

Bi ( ) //i=1,2,...,n2

{

while (1)

{

......

P(full[i]);

P(mutex);

将消息从缓冲区取出；

V(mutex);

V(empty[i]);

......

}

}

parbegin

A1( );

A2( );

......

An1( );

B1( );

B2( );

42

为

......

Bn2( );

parend

``501

一组生产者进程和一组消费者进程共享9个缓冲区，每个缓冲区可以存放一个整数。生产者进程每

次一次性向3个缓冲区写入整数，消费者进程每次从缓冲区取出一个整数。请用信号量和P、V操

作写出并发进程能正确执行的算法程序。

``500

解：semaphore empty=9; //生产者的资源信号量，表示空缓冲区个数

seamphore full=0; //消费者的资源信号量，表示满缓冲区个数

seamphore mutex=1; //互斥信号量，用于互斥访问缓冲区(或共享变量i或j)

int i=0; //生产者使用是缓冲区下标

int j=0; //消费者使用是缓冲区下标

parbegin

process producer

m

(m=1, 2, 3, …)

begin

int a,b,c; //该生产者使用的局部变量

repeat

生产者获得3个整数a, b, c ;

P(empty); P(empty); P(empty); //得到3个空缓冲区

P(mutex); //生产者互斥访问共享变量i

buffer[i]=a; //整数a存入缓冲区

i=(i+1) mod 9;

buffer[i]=b; //整数b存入缓冲区

i=(i+1) mod 9;

buffer[i]=c; //整数c存入缓冲区

i=(i+1) mod 9;

V(mutex);

V(full); V(full); V(full);

until false

end

process consumer

k

(k=1, 2, 3, …)

begin

int x;

repeat

P(full); //看看缓冲区是否有整数

P(mutex); //消费者互斥访问共享变量j

x=buffer[j]; //从缓冲区取整数到x中

j=(j+1) mod 9

V(mutex);

V(empty); //空缓冲区数增1

consume x;

until false

43

4分

7分

10分

end

parend

``801

有n个输入进程、m个计算进程和p个输出进程，通过循环缓冲区A和循环缓冲区B进行数据传送，

如下图所示。

输入进程1

输入进程2

计算进程1

计算进程2

输出进程1

输出进程2

…

输入进程n

缓冲区A

…

计算进程m

缓冲区B

…

输出进程p

已知缓冲区A有N个缓冲块，缓冲区B有M个缓冲块。输入进程每次输入1个数据块存入缓

冲区A的1个缓冲块中；计算进程每次从缓冲区A取出1个数据块，处理后的数据块存入缓冲区B

的1个缓冲块中；输出进程每次从缓冲区B中取出1个数据块进行输出操作。试用P、V操作实现

进程间的同步与互斥。

``800

解：semaphore mutex1, mutex2, empty1, full1, empty2, full2;

int in1, out1, in2, out2;

mutex1=1; //互斥信号量，用于互斥访问共享变量in1和out1

mutex2=1; //互斥信号量，用于互斥访问共享变量in2和out2

empty1=N; //同步信号量，表示缓冲区A的空缓冲区个数

empty2=M; //同步信号量，表示缓冲区B的空缓冲区个数

full1=0; //同步信号量，表示缓冲区A的满缓冲区个数

full2=0; //同步信号量，表示缓冲区B的满缓冲区个数

in1=out1=in2=out2=0; //共享变量，表示缓冲区的下标变量 3分

parbegin

process input

i

( ) //n个输入进程，i=1, 2, ... , n

{

while (1) {

读入一个数据块X;

P(empty1); //判断缓冲区A是否有空闲位置放数据块，若无则等待

P(mutex1); //互斥访问共享变量in1和缓冲区A

bufferA[in1]=X;

in1=(in1+1)%M;

V(mutex1);

V(full1); 5分

}

}

process compute

j

( ) //m个计算进程，j=1, 2, ... , m

{

while (1) {

P(full1); //判断缓冲区A中是否有可取的数据块，若无则等待

44

P(mutex1); //互斥访问out1和缓冲区A

Y=bufferA[out1];

out1=(out1+1)%M;

V(mutex1);

V(empty1); //通知输入进程，缓冲区A中已被取走一个数据块

处理数据块Y;

P(empty2); //判断缓冲区B是否有空位置存放数据块，若无则等待

P(mutex2); //互斥访问共享变量in2和缓冲区B

bufferB[in2]=处理后的数据块Y;

in2=(in2+1)%N;

V(mutex2);

V(full2);

}

}

process output

k

( ) //p个输出进程，k=1, 2, ... , p

{

while (1) {

P(full2); //判断缓冲区B中是否有可取的数据块，若无则等

P(mutex2); //互斥访问共享变量out2和缓冲区B

Z=bufferB[out2];

out2=(out2+1)%N;

V(mutex2);

V(empty2);

}

}

parend

8分

10分

``701

设自行车生产线上有一只箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮；又

设有三个工人，其活动分别为：

工人1活动 工人2活动 工人3活动

↓ ↓ ↓

加工一个车架 加工一个车轮 箱中取一个车架

↓ ↓ ↓

车架放入箱中 车轮放入箱中 箱中取两个车轮

↓

组装为一台车

试用PV操作实现三个工人的合作。

【提示】工人1和工人2向箱子中放车架或车轮的活动，除了受到箱子容量的限制外，还应考虑车

架和车轮的数量差，即不允许只放车架或只放车轮，因为那样可能会引起死锁。显然，工人1

放车架时最好应留出2个放车轮的空位；同样，工人2放车轮时至少应留出1个空位放车架。

因此，若count1和count2分别代表车架数和车轮数，则不妨规定-(N-1)≤count1－count2≤N-2

``700

解：semaphore mutex, avail, availa, availb, fulla, fullb;

45

mutex=1; //互斥信号量，用于访问共享变量count1和count2

avail=N; //同步信号量，用于表示箱子中空闲位置数

availa=N-2; //同步信号量，用于表示箱子中可放车架的数量

availb=N-1; //同步信号量，用于表示箱子中可放车轮的数量

fulla=0; //同步信号量，用于表示箱子中已放的车架数量

fullb=0; //同步信号量，用于表示箱子中已放的车轮数量

parbegin

process worker1( )

{

while (1) {

加工一个车架;

P(availa); //看看箱子中是否还允许放车架

P(avail); //看看箱子中是否还有放车架的位置

P(mutex);

车架放入箱中;

V(mutex);

V(fulla); //通知工人3，箱子中多了个车架

V(availb); //箱子中允许放的车轮数增1

}

}

process worker2( )

{

while (1) {

加工一个车轮;

P(availb);

P(avail); //看看箱子中是否还有放车架的位置

P(mutex);

车轮放入箱中;

V(mutex);

V(fullb); //通知工人3，箱子中多了个车架

V(availa);

}

}

process worker3( )

{

while (1) {

P(availa);

P(mutex);

从箱中取一个车架;

V(mutex);

V(avail);

P(availb);

P(mutex);

从箱中取一个车轮;

46

3分

5分

7分

P(mutex);

V(avail);

P(availb);

P(mutex);

从箱中再取一个车轮;

V(mutex);

V(avail);

组装为一台车;

}

}

parend

10分

``601

有如图所示的工作模型：

三个进程P

0

、P

1

、P

2

和三个缓冲区B

0

、B

1

、B

2

，进程间借助相邻缓冲区传递消息：P

0

每次从

B

0

中取出一条消息经加工后送入B

1

中，P

1

每次从B

1

中取出一条消息经加工后送入B

2

中，P

2

每次

B

0

P

0

P

2

B

2

P

1

从B

2

中取出一条消息经加工后送入B

0

中。B

0

，B

1

，B

2

分别可存放3，2，2个消息。初始时B

0

中有

2个消息，B

1

，B

2

中各有1个消息。用P、V操作写出P

0

，P

1

，P

2

的同步及互斥流程。

``600

解：semaphore empty0,full0,empty1,full1,empty2,full2,mutex;

empty0=1;full0=2; //冲区B

0

有2个消息，还可放1个消息

empty1=1; full1=1; //冲区B

1

有1个消息，还可放1个消息

empty2=1; full2=1; //冲区B

2

有1个消息，还可放1个消息

mutex=1; //互斥信号量 3分

parbegin

Process P

0

{

while (1) {

P(full0); //看看B

0

中是否有消息

P(mutex); //互斥访问B

0

从缓冲区B

0

中取一个消息x;

V(mutex);

V(empty0); //B

0

中空出一个存放消息的位置

加工消息x;

P(empty1); //看看B

1

中是否可放一个消息

47

B

1

P(mutex); //互斥访问B

1

将加工后的x存入缓冲区B

1

;

V(mutex);

V(full1); //B

1

中增加一个消息

}

6分

}

Process P

1

{

while (1) {

P(full1); //看看B

1

中是否有消息

P(mutex); //互斥访问B

1

从缓冲区B

1

中取一个消息y;

V(mutex);

V(empty1); //B

1

中空出一个存放消息的位置

加工消息y;

P(empty2); //看看B

2

中是否可放一个消息

P(mutex); //互斥访问B

2

将加工后的x存入缓冲区B

2

;

V(mutex);

V(full2); //B

2

中增加一个消息

}

}

Process P

2

{

while (1) {

P(full2); //看看B

2

中是否有消息

P(mutex); //互斥访问B

2

从缓冲区B

2

中取一个消息z;

V(mutex);

V(empty2); //B

2

中空出一个存放消息的位置

加工消息z;

P(empty0); //看看B

0

中是否可放一个消息

P(mutex); //互斥访问B

0

将加工后的z存入缓冲区B

0

;

V(mutex);

V(full0); //B

0

中增加一个消息

}

}

parend

8分

10分

``501

有一材料保管员，他保管笔和纸若干。有A、B两组学生，A组学生每人都备有纸，B组学生每人

备有笔。任一学生只要能得到另一种材料就可以写信。有一个可以放一张纸或一支笔的小盒，当小

48

盒中无物品时，保管员就可任意放一张纸或一支笔共学生取用，每次允许一个学生从中取出自己所

需要的材料，当学生从盒子中取走材料后允许保管员再放一件材料，请用信号量和P、V操作，写

出他们并发执行时能正确工作的算法程序。

``500

解：semaphore empty, fulla, fullb;

empty=1; fulla=fullb=0; 3分

parbegin

process 保管员

{

while (true) {

任取一种物品x;

P(empty); //准备往小盒中放物品，若小盒不空则阻塞

将x放入小盒中;

if (x是笔) V(fulla);//通知A组学生小盒中放了笔(可能唤醒一个A组学生)

else V(fullb); //通知B组学生小盒中放了纸 6分

}

}

process Ai ( i = 1, 2, ... ) //A组学生进程

{

P(fulla); //看看小盒中是否有笔，若无则阻塞

从小盒中取出笔;

V(empty); //通知保管员，小盒已空。若保管员因小盒不空而阻塞，则唤醒之

用笔盒纸写信; 8分

}

process Bj ( j = 1, 2, ... ) //A组学生进程

{

P(fullb); //看看小盒中是否有纸，若无则阻塞

从小盒中取出纸;

V(empty); //通知保管员，小盒已空。若保管员因小盒不空而阻塞，则唤醒之

用笔盒纸写信; 10分

}

parend

``801

另一个经典同步问题(patil, 1971)：三个吸烟者在一个房间内，还有一个香烟供应者。为了制造和抽

掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富的货物提供。三个吸烟者中，

第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者随机地将两样东西放在桌

子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样

东西放在桌子上，唤醒一个吸烟者。试采用信号量和P、V操作，编写他们同步工作的算法程序。

``800

解：定义4个信号量用于供应者与3个吸烟者的同步：S0为供应者的同步信号量；S1、S2和S3分

别为第一个吸烟者、第二个吸烟者和第三个吸烟者的资源信号量。供应者随机取的两样东西是

纸和火柴，则执行V(S1)通知第一个吸烟者；两样东西是烟草和火柴，则执行V(S2)通知第二个

吸烟者；两样东西是烟草和纸，则执行V(S3)通知第三个吸烟者。算法描述如下：

49

semaphore S0, S1, S2, S3;

S0=S1=S2=S3=0;

parbegin

供应者：begin

L0:

随机地取两样东西x, y放在桌子上;

if (x, y是纸和火柴) V(S1); //通知第一个吸烟者

else if (x, y是烟草和火柴) Vl(S2); //通知第二个吸烟者

else V(S3); //通知第三个吸烟者

P(S0) ; //供应者阻塞，等待吸烟者唤醒

goto L0;

end

第一个吸烟者：begin

L1: P(S1); //看看供应者是否在桌上放了纸和火柴

从桌上取纸和火柴;

加工香烟;

抽烟;

V(S0); // 唤醒供应者

goto L1;

end

第二个吸烟者：begin

L2: P(S2); //看看供应者是否在桌上放了烟草和火柴

从桌上取烟草和火柴;

加工香烟;

抽烟;

V(S0); // 唤醒供应者

goto L2;

end

第三个吸烟者：begin

L3: P(S1); //看看供应者是否在桌上放了烟草和纸

从桌上取烟草和纸;

加工香烟;

抽烟;

V(S0); // 唤醒供应者

goto L3;

end

parend

2分

4分

6分

8分

10分

``601

设有三组进程P

i

、Q

j

、R

k

，其中P

i

、Q

j

构成一对生产者-消费者，共享一个由M1个缓冲区构成的循

环缓冲buf1。Q

j

、R

k

构成另一对生产者-消费者，共享一个由M2个缓冲区构成的循环缓冲buf2。

如果P

i

每次生产一个零件投入buf1，Q

j

每次从buf1中取两个零件组装成一个产品后投入buf2，R

k

每次从buf2中取出三个产品包装出厂。试采用信号量和P、V操作编写他们同步工作的算法程序。

``600

50

解：对于P

i

、Q

j

，设置资源信号量empty1、full1用于它们的同步，互斥信号量mutex1用于它们对

下标变量的互斥访问；对于Q

j

、R

k

，设置资源信号量empty2、full2用于它们的同步，互斥信

号量mutex2用于它们对下标变量的互斥访问。同步算法描述如下：

semaphore empty1, full1, mutex1, empty2, full2, mutex2;

int in1, out1, in2, out2 ;

empty1=M1; empty2=M2; mutex1=mutex2=1; full1=full2=0;

in1=out1=in2=out2=0; 3分

parbegin

process P

i

(i=1, 2, 3, ... )

{

while(1) {

生产一个产品x;

P(empty1);

P(mutex1);

buf1[in1]=x;

in1=(in1+1) mod M1;

V(mutex1);

V(full1);

}

}

process Q

j

( j=1, 2, 3, ... )

{

while (1) {

for (m=0; m<2; m++) {

P(full1);

P(mutex1);

y[m]=buf1[out1];

out1=(out1+1) mod M1;

V(mutex1);

V(empty1);

}

把y[0]和y[1]组装成一个产品y;

P(empty2);

P(mutex2);

buf2[in2]=y;

in2=(in2+1) mod M2;

V(mutex2);

V(full2);

}

}

process R

k

( k=1, 2, 3, ... )

{

while (1) {

for (n=0; n<3; n++) {

51

5分

8分

P(full2);

P(mutex2)

z[n]=buf2[out2];

out2=(out2+1) mod M2;

V(mutex2);

V(empty2);

}

将z[0], z[1], z[2]包装准备出厂;

}

}

parend

``501

在一个实时系统中，有两个进程P和Q，它们循环工作。P每隔1秒由脉冲寄存器获得输入，并把

它累加到整型变量W上，同时清除脉冲寄存器。Q每隔1小时输出整型变量W的值并把它复位。

系统提供了标准例程INPUT和OUTPUT供I/O，提供了延时系统调用Delay(seconds)。试采用信号

量和P、V操作写出两个并发进程循环工作的算法。

``500

解：semaphore mutex = 1;

int W = 0; 2分

parbegin

process P

{

while (1) {

Delay(1);

x = INPUT( );

P(mutex);

W = W+x;

V(mutex);

清除脉冲寄存器; 6分

}

}

process Q

{

while (1) {

Delay(3600);

P(mutex);

OUTPUT(W);

W = 0;

V(mutex); 10分

}

}

parend

52

10分

``601

用信号量和P、V操作解决进程之间的同步互斥问题。有n(n>1)个进程将字符读入到一个容量为80

的缓冲区中，当缓冲区满后，有另一个进程P

b

负责一次取走这80个字符。这种过程循环往复，请

写出n个读入进程(P

1

，P

2

，P

3

，...，P

n

)和P

b

的动作序列。（设每个读入进程每次读入1个字符到

缓冲区）

``600

解：semaphore mutex, empty, full;

mutex=1; //互斥信号量，用于互斥访问共享变量count

empty=80; //同步信号量，表示当前缓冲区可容纳的字符个数

full=0; //同步信号量，1表示缓冲区满，0表示缓冲区未满

int count=0; //计数变量 4分

parbegin

process Pi ( ) // i=1, 2, 3, ... , n

{

while (1) {

读入一个字符;

P(empty);

P(mutex);

将读入的字符存入缓冲区;

count++;

if (count==80) V(full);

V(mutex); 7分

}

}

process P

b

( )

{

while (1) {

P(full);

P(mutex);

从缓冲区取走80个字符;

count=0;

V(mutex);

for (int i=0; i<80; i++)

V(empty);

} 10分

}

parend

``501

某银行提供1个服务窗口和10个顾客等待座位。顾客到达银行时，若有空座位，则到取号机领取

一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，

并为其服务。顾客和营业员的活动过程描述如下：

cobegin

{

53

process 顾客i

{

从取号机获得一个号码;

等待叫号;

获得服务;

}

process 营业员

{

while (TRUE)

{

叫号;

为顾客服务;

}

}

}

coend

请添加必要的信号量和P、V（或wait( )、signal( )）操作实现上述过程的互斥和同步。要求写

出完整的过程，说明信号量的含义并赋初值。

``500

解：begin

semaphore mutex=1; //用于顾客取号的互斥信号量

semaphore seat=10; //顾客等待座位的资源信号量，当没有空座位时顾客在其上阻塞

semaphore S1=0; //营业员与顾客的同步信号量，当没有顾客时营业员在其上阻塞

semaphore S2=0; //顾客与营业员的同步信号量，等待叫号时顾客在其上阻塞

4分

cobegin

{

process 顾客i

{

P(seat); //若没有空座位，顾客等待

P(mutex); //取号互斥

从取号机获得一个号码;

V(mutex);

V(S1); //通知营业员，已有顾客

P(S2);

等待叫号;

获得服务; 7分

}

process 营业员

{

while (TRUE)

{

P(S1); //若无顾客则等待

V(S2); //唤醒等待叫号的顾客

54

叫号;

V(seat); //空出一个座位(此行放在顾客进程的等待叫号后面也可)

为顾客服务;

}

}

}

coend

end

10分

``501

过独木桥问题：一条小河上有一座独木桥，假设河东、河西都有人要过桥，为了保证安全，规定只

要桥上无人，则允许一方的人过桥，待一方的人全部过完后，另一方的人才允许过桥。如果把每个

过桥者看做一个进程，请用P、V操作实现正确管理。

``500

解：semaphore mutexAB, mutexA, mutexB;

mutexAB=1; //互斥信号量，用于两个方向过桥者之间的互斥

mutexA=1; //互斥信号量，用于访问共享变量countA的互斥

mutexB=1; //互斥信号量，用于访问共享变量countB的互斥

int countA, countB;

countA=0; //用于自东向西过桥者计数

countB=0; //用于自西向东过桥者计数 4分

parbegin

process E_to_Wi ( ) //自东向西过桥者进程，i=1, 2, ... , n

{

P(mutexA);

if (countA==0) P(mutexAB);

countA++;

V(mutexA);

通过独木桥;

P(mutexA);

countA--;

if (countA==0) V(mutexAB);

V(mutexA); 7分

}

process W_to_Ej ( ) //自西向东过桥者进程，j=1, 2, ... , m

{

P(mutexB);

if (countB==0) P(mutexAB);

countB++;

V(mutexB);

通过独木桥;

P(mutexB);

countB--;

if (countB==0) V(mutexAB);

55

V(mutexB);

}

parend

10分

``701

哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论；在讨论的间隙四位哲学

家进餐，每人进餐都需使用刀、叉各一把(假设每个哲学家进餐时都是先拿刀，再拿叉)，餐桌上的

布置如图Z所示。请用信号量及P、V操作说明这四位哲学家的同步、互斥过程。

丁

叉2

ψ

刀1

b

食品

甲

丙

b

刀2

乙

ψ

叉1

图Z 哲学家进餐问题(b表示刀，ψ表示叉)

``700

解：设置四个互斥信号量fork1、fork2、knife1、knife2，其初值均为1，分别表示资源叉1、叉2、

刀1、刀2是否可用。同步算法描述如下：

semaphore fork1, fork2, knife1, knife2;

fork1=fork2=knife1=knife2=1; 2分

process Pa( ) //哲学家甲

{

while (1)

{

讨论问题;

P(knife1); //拿起右边的刀子

P(fork1); //拿起左边的叉子

进餐;

V(knife1); //放下右边的刀子

V(firk1); //放下左边的叉子 4分

}

}

process Pb( ) //哲学家乙

{

while (1)

{

讨论问题;

P(knife2); //拿起左边的刀子

P(fork1); //拿起右边的叉子

56

进餐;

V(knife2); //放下左边的刀子

V(firk1); //放下右边的叉子

}

}

process Pc( ) //哲学家丙

{

while (1)

{

讨论问题;

P(knife2); //拿起右边的刀子

P(fork2); //拿起左边的叉子

进餐;

V(knife2); //放下右边的刀子

V(firk2); //放下左边的叉子

}

}

process Pd( ) //哲学家丁

{

while (1)

{

讨论问题;

P(knife1); //拿起左边的刀子

P(fork2); //拿起右边的叉子

进餐;

V(knife1); //放下左边的刀子

V(firk2); //放下右边的叉子

}

}

parbegin

Pa( );

Pb( );

Pc()；

Pd( );

parend

6分

8分

10分

``401

四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F，但限制是进程A

和进程C不能同时读文件F，进程B和进程D也不能同时读文件F，为了使这四个进程并发执行时

能按系统要求使用文件，现用PV操作进行管理，并给出应定义的信号量及初值。

``400

解：应定义的信号量是S1，S2，初值为1，1。其中S1用于进程A、C间互斥，S2用于B、D间互

斥。算法描述如下：

semaphore S1,S2;

57

S1=1;S2=1;

Parbegin

Process A

begin

P(S1);

read F;

V(S1);

end;

Process B

begin

P(S2);

read F;

V(S2);

end;

Process C

begin

P(S1);

read F;

V(S1);

end;

Process D

begin

P(S2);

read F;

V(S2);

end;

Parend

2分

4分

6分

8分

10分

``601

设公共汽车上，司机和售票员的活动分别是：

司机的活动： 启动车辆；

正常行驶；

到达停车；

售票员的活动：关车门；

售票；

开车门；

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作

实现它们的同步。

``600

解：司机和售票员活动的同步关系为：售票员关门后，向司机发开车信号，司机接到开车信号后启

动车辆，在汽车行驶过程中售票员售票，到站时司机停车，售票员在停车后开车门让乘客上下

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

与司机停车的动作同步。

设置2个信号量S1、S2，信号量S1表示是否允许司机启动汽车，其初值为0；信号量S2表示

58

是否允许售票员开门，其初值为0。

用P、V操作描述的同步算法如下：

BEGIN

semaphore S1, S2;

S1=S2=0;

parbegin

process driver ( ) //司机进程

begin

repeat

P(S1); //司机判断是否可以启动汽车

启动车辆;

正常行驶;

到站停车;

V(S2); //告诉售票员可以开门了

until false

end

begin

repeat

关车门;

V(S1); //告诉司机可以启动汽车了

售票;

P(S2); //看看是否可以开车门

开车门;

上下乘客;

until false

end

parend

END

4分

7分

10分

``601

有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：

（1）每次只能存入一种产品（A或B）；

（2）-N < A产品数量 - B产品数量 < M 。

其中，N，M是正整数。试用“存放A”和“存放B”和P、V操作描述产品A与产品B的入

库过程。

【提示】由题目条件(2)可知，若不放A产品，B产品放最多能放N-1个，此后“存放B”应该阻塞；

若不放B产品，A产品放最多能放M-1个，此后“存放A”应该阻塞。故“存放A”和“存放B”

的资源信号量sa与sb的初始值分别为M-1和N-1。

``600

解：semaphore mutex,sa,sb;

=1;=M-1;=N-1; 4分

parbegin

存放A：

{

59

while (true)

{

get product A；

P(sa);

P(mutex);

put product A;

V(mutex);

V(sb);

}

}

存放B：

{

while (true) {

get product B;

P(sb);

P(mutex);

put product B;

V(sa);

V(mutex);

}

}

parend

7分

10分

``601

有一个仓库存放两种零件A和B，最大库容量为可存放1000个零件A或B。有一车间不断地取A

和B进行装配，每次各取一个。有两组供应商分别不断地供应A和B（每次一个）。为保证齐套和

合理库存，当某种零件的数量比另一种数量超过100个时，暂停对数量大的零件的进货，集中补充

数量少的零件。试用P、V操作正确地实现之。

``600

解：采用P、V操作的同步算法如下：

BEGIN

semaphore mutex，availab，full1，full2，sa，sb；

= 1；

= 1000； = = 0；

= 100； = 100； 4分

PARBEGIN

store_A：BEGIN

L1：P（availab）；

P（sa）；

P（mutex）：

store A；

V（fulla）；

V（sb）；

V（mutex）；

60

goto L1；

END

store_B：BEGIN（2分）

L2：P（availab）；

P（sb）；

P（mutex）；

store B；

V（fullb）；

V（sa）；

V（mutex）；

goto L2；

END

take：BEGIN

L3：P（fulla）；

P（fullb）；

P（mutex）；

take A and B；

V（availab）；

V（availab）；

V（mutex）；

goto L3；

END

PAREND

END

6分

8分

10分

``601

有一个仓库存放两种零件A和B，最大库容量为m个。有一车间不断地取A和B进行装配，每次

各取一个。为避免零件锈蚀，遵循先入库者先出库的原则。有两组供应商分别不断地供应A和B（每

次一个）。为保证齐套和合理库存，当某种零件的数量比另一种数量超过n（n

量大的零件的进货，集中补充数量少的零件。试用P、V操作正确地实现之。

``600

解：BEGIN

semaphore mutex，availa，full1，availb，full2，sa，sb；

mutex ：= 1；

availa ：= m；fulla ：= 0；

availb ：= m；fullb ：= 0

sa ：= n；sb ：= n； 4分

PARBEGIN

store_A：BEGIN

L1：P（availa）；

P（sa）；

P（mutex）：

store A；

V（fulla）；

61

V（sb）；

V（mutex）；

goto L1；

END

store_B：BEGIN

L2：P（availb）；

P（sb）；

P（mutex）；

store B；

V（fullb）；

V（sa）；

V（mutex）；

goto L2；

END

take：BEGIN

L3：P（fulla）；

P（fullb）；

P（mutex）；

take A and B；

V（availa）；

V（availb）；

V（mutex）；

goto L3；

END

PAREND

END

6分

8分

10分

``001

讨论下图所示的交通管理例子（各方向上的汽车是单行、直线行驶），试用P、V操作实现各方向上

汽车行驶的同步。假设开始时路口A、B之间的马路上无车辆。

路口A

路口B

马路可停n辆车

``000

解：假设自西向东进入路口A的汽车为Xi，自北向南进入路口A的汽车为Yj，自北向南进入路口

B的汽车为Z

k

。显然，同方向的汽车可共享路口A(或路口B)，非同方向的汽车应互斥经过路

口。对于自西向东的汽车，除了考虑2个路口与另一方向汽车的互斥问题外，还应考虑路口A、

B之间路面可停n辆车的问题，当该段路面满时，自西向东的汽车不再允许进入路口A。

semaphore mutex1,mutex2,S1,S2,S3,S4,count;

int Cx1, Cy, Cz, Cx2;

mutex1=1; //用于Xi和Yj互斥进入路口A

62

mutex2=1; //用于Xi和Z

k

互斥进入路口B

S1=1; //用于Xi访问共享计数变量Cx1的互斥

S2=1; //用于Yj访问共享计数变量Cy的互斥

S3=1; //用于Xi访问共享计数变量Cx2的互斥

S4=1; //用于Z

k

访问共享计数变量Cz的互斥

count=9; //路口A、B之间可容纳的汽车数

Cx1=0; //用于Xi通过路口A的计数

Cx2=0; //用于Xi通过路口B的计数

Cy=0; //用于Yj通过路口A的计数

Cz=0; //用于Z

k

通过路口B的计数

parbegin

process Xi (i=1,2,3, ... )

{

P(count); //看看路口A、B之间是否还有空间

P(S1); //准备进入路口A

Cx1=Cx1+1;

if (Cx1==1) P(mutex1); //与Yj互斥通过路口A

V(S1); //允许后续Xi进入路口A

通过路口A;

P(S1);

Cx1=Cx1-1;

if (Cx1==0) V(mutex1); //允许Yj通过路口A

V(S1);

在A、B段路面行驶;

P(S3); //准备进入路口B。互斥访问Cx2

Cx2=Cx2+1;

if (Cx2==1) P(mutex2);

V(S3);

V(count); //AB段可容纳汽车数增1(唤醒因A、B段满员而阻塞的Xi)

通过路口B;

P(S3); //互斥使用Cx2

Cx2=Cx2-1;

if (Cx2==0) V(mutex2); //允许Z

k

通过路口B

V(S3);

}

process Yj (j=1,2,3, ... )

{

P(S2);

Cy=Cy+1;

if (Cy==1) P(mutex1);

V(S2)

通过路口A;

P(S2);

Cy=Cy-1;

63

4分

6分

if (Cy==0) V(mutex1);

V(S2);

}

process Zk (k=1,2,3, ... )

{

P(S4);

Cz=Cz+1;

if (Cz==1) P(mutex2);

V(S4)

通过路口B;

P(S4);

Cz=Cz-1;

if (Cz==0) V(mutex2);

V(S4);

}

parend

8分

10分

``601

有一个阅览室，读者进入时必须先在一张登记表上登记，该表位每一座位列出一个表目，包括座号、

姓名，读者离开时要注销登记信息。假如阅览室有100个座位。试用信号量和P、V操作，来实现

读者进程的同步算法。

``601

解：semaphore seat, mutex ;

seat = 100; //座位资源信号量

mutex = 1; //用于互斥访问登记表 3分

parbegin

process STi (i=1, 2, ... ) //学生进出

{

P(seat); //学生到达后，若已无座位，则等待 4分

P(mutex); //登记互斥 5分

在登记表上登记;

V(mutex); 6分

在阅览室阅览;

P(mutex); 7分

注销登记信息;

V(mutex); 8分

V(seat); //空出一个座位，可能唤醒一个等待座位的学生 10分

}

parend

``601

有一阅览室，读者进入阅览室必须先在一张登记表(TB)上登记，该表为每一座位设一个表目，读者

离开时要消掉其登记信息。阅览室共有100个座位，为了描述读者的动作，请用信号量和P、V操

作写出进程间的同步算法。

64

约定：

1） flag的值：0——座位空闲；1——座位被占用。

2） 用语句i=getflag(0)可搜索到一个空座位i。用语句=0或1，可给标志位赋值。

3） 用i=getname(reader_name)可搜索到某读者所登记的座位号i。用=0或

=reader_name可给姓名字段赋值，0表示清除读者姓名。

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

座号 ( i )

1

2

姓名(name)

Wang

Zhang

标志(flag)

1

1

…

0

0

…

99

100

…

0

0

``600

解：semaphore seat= 100, mutex=1; 2分

Reader

i

( ) { ( i=1, 2, ... , n ) }

begin

P(seat); { 读者到来，先看看有无空座位 } 3分

P(mutex); { 互斥访问登记表 } 4分

i := getflag(0); { 在TB中搜索到空座位i }

:= 1; { 置座位被占用的标志 }

=reader_name

i

; { 登记姓名 } 5分

V(mutex); 6分

在阅览室阅览;

P(mutex); { 准备消掉登记信息 }

i = getname(reader_name

i

); { 在登记表中搜索自己的名字 }

:= 0; { 注销登记信息 }

:= 0; 7分

V(mutex); 8分

V(seat); { 座位数增1。若有读者等待，则唤醒之 } 9分

end

parbegin

Reader

1

( );

Reader

2

( );

………

Reader

n

( ); 10分

parend

``401

某杂技团进行走钢丝表演。在钢丝的A、B两端各有n名演员(n>1)在等待表演。只要钢丝上无人时

便允许一名演员从钢丝的一端走到另一端。现要求两端的演员交替地走钢丝，且从A端的一名演员

先开始。请问，把一名演员看作一个进程时，怎样用PV操作来进行控制？请写出能正确管理的程

序。

``400

65

解：begin

S1, S2 : semaphore;

S1:=1; S2:=0; 4分

cobegin

process A_to_Bi (i=1,2, …, n)

begin

P(S1); 5分

{表演};

V(S2); 7分

end;

process B_to_Aj (j=1, 2, …, n)

begin

P(S2); 8分

{表演};

V(S1); 10分

end;

coend;

end;

``401

某自动质量检测系统有三个进程Q、A、B组成。进程Q每次取一件产品检测，把检测后的产品存

放在货架F上，F的容量为每次只能存放一件产品。若货架上存放的是合格产品则让进程A取出，

并在产品上贴标签后包装；若货架上存放的是不合格产品则让进程B取出后，将其丢入废物箱。写

出用PV操作管理时的算法程序以及应定义的信号量及初值。

``400

解：应定义信号量empty，fulla，fullb，初值分别为1，0，0。empty=1，表示货架F是空的，empty=0

表示货架F上已存放产品；fulla=1表示货架F已存放一件合格产品，fulla=0表示货架F上无合格

产品；fullb=1表示货架F已存放一件不合格产品，fullb=0表示货架F上无不合格产品。 2分

semaphore empty,fulla,fullb;

empty=1; fulla=0; fullb=0; 3分

parbegin

process Q

{

while (true)

{

取一件产品检测;

P(empty);

F=检测后的产品; //把检测后的产品存放在货架F上

if (F==合格产品) V(fulla);

else V(fullb); 6分

}

}

process A

{

66

while (true)

{

P(fulla);

y=F中产品; //取货架F上的合格产品

V(empty);

对产品贴标签且包装;

}

8分

}

process B

{

while (true)

{

P(fullb);

z=F中产品; //取货架F上的不合格产品

V(empty);

把产品丢入废物箱;

}

}

parend

10分

``201

系统有三个进程Read,Write1,Write2共享一个整数缓冲器B，B中每次只能存放一个整数。Read进

程每次启动输入设备输入一个整数到n。若n中是奇数，则由进程Write1将其取出打印；若n中是

偶数，则由进程Write2将其取出打印。规定输入与打印整数的个数和次序完全一致。

要求：（1）完善如下程序，在下列A、B空白处填入有关语句，并说明物理意义。

begin S, SO, SE: semaphore;

n: integer;

S:=1;

SO:=0;

SE:=0;

Parbegin

process Read

Begin

L

1

:从输入设备读一整数到n；

P(S);

B:=n;

if n mod 2=1 then V(SO)

else V(SE);

goto L

1

end;

process Write1

begin

L

2

: P(SO);

Y:=B;

67

(A) ;

print Y;

goto L

2

end;

process Write2

begin

L

3

: (B) ;

Z:=B;

V(S);

Print Z;

goto L

3

end;

Parend;

end;

（2）说明信号量S，SO，SE作用及它们的初值的物理意义。

（3）Read进程中V(SO)与V(SE)对调，程序功能将发生什么变化。

``200

解：(1) (A) V(S) (B) P(SE) 3分

(2) 信号量S，SO，SE作用是实现进程Read、Write1和Write2之间的同步。信号量S的初值

为1，表示开始时缓冲器B是空的，可以存放一个整数，当缓冲器B中存有整数时，其值

变为0；信号量SO的初值为0，表示开始时缓冲器B中没有奇数，当缓冲器B中存有一个

奇数时，SO的值变为1；信号量SE的初值为0，表示开始时缓冲器B中没有偶数，当缓

冲器B中存有一个偶数时，SE的值变为1。 7分

(3) Read进程中V(SO)与V(SE)对调，程序功能将变为：若缓冲器中存放的整数n为奇数时，

则由进程Write2将其取出打印；若n中是偶数，则由进程Write1将其取出打印。

10分

``401

用PV操作解决读者-写者问题的算法描述程序如下：

semaphore S, Sr;

int rc;

S=1; Sr=1; rc=0;

parbegin

PROCESS Reader i ( i = 1, 2…)

{

P(Sr) ;

rc=rc+1;

if (rc==1) P(S);

V(Sr）;

read file;

P(Sr）;

rc=rc-1

if (rc==0) V(S);

V(Sr);

68

}

PROCESS Writer j ( j = 1, 2 … )

{

P(S);

Write file;

V(S)

}

parend

请回答：

（1）信号量S

r

的作用；

（2）程序中什么语句用于读写互斥，写写互斥；

（3）若规定仅允许5个进程同时读怎样修改程序？

``400

解：(1) 信号量

Sr

的作用的作用是保证读者互斥访问共享变量rc。 2分

(2) 程序中语句if (rc==1) P(S);用于读写互斥；语句P(S); 用于写写互斥。 6分

(3) 若规定仅允许5个进程同时读，可增加一个信号量S1，其初值为5，修改程序如下：

semaphore S, Sr;

int rc;

S=1; Sr=1; rc=0;

semaphore S1= 5; 8分

parbegin

PROCESS Reader i ( i = 1, 2…)

{

P(S1); 9分

P(Sr) ;

rc=rc+1;

if (rc==1) P(S);

V(Sr）;

read file;

P(Sr）;

rc=rc-1

if (rc==0) V(S);

V(Sr);

V(S1); 10分

}

parend

``501

两个并发进程的伪代码程序如下：

begin

N:integer;

N:=1;

parbegin

process A

69

begin

L1: N:=N+1;

go to L1;

end;

process B

begin

L2: print(N);

N:=0;

go to L2;

end;

parend;

end;

请回答：

(1)指出这两个并发进程的临界区。

(2)指出它们并发执行时可能出现的“与时间有关的错误”。

(3)用PV操作进行管理，写出使它们能正确并发执行的程序。

``500

解：(1) 进程A的临界区是“N:=N+1;”，进程B的临界区是“print(N); N:=0;” 2分

(2) 为叙述方便，不妨假设某时刻共享变量N=10。可能出现的“与时间有关的错误”如下：

① 进程B执行了print（N）打印10后被中断；系统切换到进程A，进程A执行N:=N+1，将

N的值增至11后，又切换到进程B，进程B执行语句N:=0; 将N清零，最终N的值为0，而

此时N正确的值应该是1，即出现“与时间有关的错误”。 4分

② 进程A执行N := N+1时，求出N+1的值为11，刚想赋值给N时，正好发生进程切换到B，

B执行print(N);语句，打印的值是10，再执行N:=0;，将N清零。此后进程又切换到A，A完

成被打断的赋值操作，将N的值赋值为11，而此时N正确的值应该是1。 6分

(3) 定义一个互斥信号量mutex，其初值为1，采用PV操作使它们能正确并发执行的伪代码程

序如下：

begin

mutex : semaphore := 1;

N:integer :=1;

parbegin

process A

begin

L1: P(mutex);

N:=N+1;

V(mutex);

go to L1;

end;

process B

begin

L2: P(mutex);

print(N);

N:=0;

V(mutex);

70

go to L2;

end;

parend;

end; 10分

``701

假设缓冲区buf1和buf2都无限大，进程P1向buf1写数据，进程P2向buf2写数据。现要求buf1

数据个数与buf2数据个数的差保持在[m,n]之间(m,n皆为整数，m小于n)，请用信号量描述此同步

关系。

【提示】设buf1中数据个数为count1，buf2中数据个数为count2，则由题意，count1和count2应

满足m<=count1-count2<=n。

``700

semaphore mutex=1, S1=0, S2=0 ;

int count1=0, count2=0 ;

parbegin

process P1( )

{

while (true) {

获取一数据;

P(mutex) ;

if (count1-count2 > n) {

V(mutex);

P(S1); //P1阻塞

}

else V(mutex) ;

将数据写入buf1 ;

P(mutex);

count1 = count1+1 ;

V(S2);

V(mutex);

}

}

process P2( )

{

while (true) {

获取一数据;

P(mutex);

if (count1-count2< m) {

V(mutex);

P(S2); //P2阻塞

}

else V(mutex);

将数据写入buf2;

P(mutex);

71

count2 := count2+1;

V(S1);

V(mutex);

}

}

parend

``701

青岛崂山有一处景点称作上清宫，游客在宫内游玩后可以在宫门口免费搭乘轿车游览崂山的风景

区，游览完毕再返回宫门口（如下图所示）

览

路

游

上清宫

乘车点

线

图2-8 崂山风景区

已知风景区内游览轿车总量有M辆，游客总数为N，约定：

a) 每辆轿车限乘一位游客；

b) 如果有空闲的轿车，应当允许想游览的游客乘坐；

c) 无空闲的轿车时，游客应该等待；

d) 若没有想游览的乘客，轿车也应等待。

试利用P、V操作实现N个游客进程和M辆轿车进程的同步操作过程。

``700

解：定义4个信号量car_avail、car_taken、finished和take_off。car_avail初值为M，它表示空闲轿

车数量；car_taken表示是否有游客乘车，用于阻塞轿车进程；finished用于游览是否结束；take_off

用于同步游客是否已下车，后3个信号量初值都为0。

semaphore car_avail=M,car_taken=0,finished=0,take_off=0; 4分

parbegin

process passenger_ i( ) //游客进程, i=1,2,…, N

begin

游上清宫;

P(car_avail); //看看是否有轿车可乘，若无则等待

V(car_taken); //唤醒一等待的轿车进程

游客上车;

P(finished); //游客等待游览结束

游客下车；

72

V(take_off); //通知轿车进程，游客已下车 7分

end

process car _ j( ) j=1,2,…, M

begin

repeat

P(car_taken); //若无游客，轿车进程等待

带一游客游览风景区;

V(finished); //通知游客游览已结束

P(take_off); //等待游客下车

V(car_avail); //空闲轿车数增1：若有等待的游客则唤醒之

until false

end

parend

10分

2.5 进程通信

``101

信箱通信是一种 通信方式。

A．直接 B．间接 C．低级

``100

B

``101

如下选项中，不能用于进程间通信的是 。

A．消息 B．信件 C．信号量

``100

D

``101

属于进程通信原语的有 。

A．P操作原语 B．V操作原语

D．send原语

``100

C

``101

构成网络操作系统通信机制的是 。

A．进程 B．线程 C．通信原语

``100

C

``101

下面的描述中， 是错误的。

A．进程执行的相对速度不能有进程自己来控制

73

D．信号量

D．口令

C．创建进程原语

D．对象

B．P、V操作是原语操作

C．利用信号量的P、V操作可以交换大量信息

D．同步是指并发进程之间存在的一种制约关系

``100

C

2.6 线程的基本概念

``101

线程是操作系统的重要概念，不具有线程管理的操作系统有 。

A．Windows 3.2 B．Linux C．Windows NT D．Windows XP

``100

A

``101

在引入线程的操作系统中，把 作为调度和分派的基本单位，而把 作为资源

拥有的基本单位。

A．进程 线程 B．程序 线程 C．程序 进程 D．线程 进程

``100

D

``101

在支持多线程的系统中，进程P创建的若干线程不能共享的是 。

．

A．进程P的代码段 B．进程P中打开的文件

C．进程P的全局变量 D．进程P中某线程的栈指针

``100

D

``101

下列关于进程和线程的叙述中，正确的是 。

A．不管系统是否支持线程，进程都是资源分配的基本单位

B．线程是资源分配的基本单位，进程是调度的基本单位

C．系统级线程和用户级线程的切换都需要内核的支持

D．同一进程的各个线程拥有各自不同的地址空间

``101

A

74

第三章 处理机调度与死锁

3.1 处理机调度的基本概念

``101

进程调度是从 选择一个进程投入运行。

A．就绪队列 B．等待队列 C．作业后备队列 D．提交队列

``100

A

``101

支持多道程序设计的操作系统在运行过程中，不断地选择新进程运行来实现CPU的共享，下列选

项中， 不是引起操作系统选择新进程的直接原因。

A．运行进程的时间片用完 B．运行进程出错

C．运行进程要等待某一时件发生 D．有新进程进入就绪状态

``100

D

``101

下列因素中， 不一定是引起进程调度的因素。

A．一个进程运行完毕 B．运行进程被阻塞

C．一个高优先级进程被创建 D．实时调度中，一个

紧迫的任务到来

``100

C

``101

若进程P一旦被唤醒就能投入运行，则系统可能是 。

A．非抢占式调度方式，进程P的优先级最高

B．抢占式调度方式，就绪队列上的所有进程的优先级皆比P低

C．就绪队列为空队列

D．抢占式调度方式，P的优先级高于当前运行的进程

``100

D

``101

在批处理系统中，周转时间是指 。

A．作业运行时间 B．作业等待时间和运行时间之和

C．作业的相对等待时间 D．作业被调度进入内存到运行完毕的时间

``100

B

75

``101

下列各项中，不是进程调度时机的是 。

A．现运行的进程正常结束或异常结束 B．现运行的进程从运行态进入就绪态

C．现运行的进程从运行态进入等待态 D．有一进程从等待态进入就绪态

``100

D

3.2 调度算法

``201

现有3个同时到达的作业J1、J2、J3，它们的执行时间分别为T1、T2和T3，且T1

按单道方式运行且采用短作业优先算法，则平均周转时间为 。

A．T1+T2+T3 B．(T1+T2+T3)/3 C．(3T1+2T2+T3)/3 D．(T1+2T2+3T3)/3

``200

C

``101

下列算法中，操作系统用于作业调度的算法是 。

A．先来先服务算法 B．先进先出算法

C．最先适应算法 D．时间片轮转算法

``100

A

``101

在作业调度中，排队等待时间最长的作业被优先调度，这是指 调度算法。

A．先来先服务 B．短作业优先

C．响应比高优先 D．优先级

``100

A

``101

下列算法中，用于进程调度的算法是 。

A．最先适应 B．最高响应比优先

C．均衡资源调度 D．优先数调度

``100

D

``101

进程调度算法有多种， 不是进程调度算法。

A．先来先服务调度算法 B．最短查找时间优先调度算法

C．静态优先数调度算法 D．时间片轮转调度算法

``100

B

76

``101

作业调度程序从 状态的队列中选取适当的作业投入运行。

A．就绪 B．提交 C．等待 D．后备

``100

D

``101

在实时操作系统中，经常采用 调度算法来分配处理器。

A.先来先服务 B.时间片轮转 C.最高优先级 D.可抢占的优先级

``100

D

``101

采用时间片轮转调度算法主要是为了 。

A．多个终端都能得到系统的及时响应

B．先来先服务

C．优先权高的进程及时得到调度

D．需要CPU时间最短的进程先做

``100

A

``101

下面关于优先权大小的论述中，不正确的论述是 。

A．计算型作业的优先权，应低于I/O型作业的优先权

B．系统进程的优先权应高于用户进程的优先权

C．资源要求多的作业，其优先权应高于资源要求少的作业

D．在动态优先权时，随着进程运行时间的增加，其优先权降低

``100

C

``101

考虑到公平对待进程和提高系统资源工作的并行度，操作系统会经常调整进程的优先级，通常应提

高 的进程优先级。

A．需计算时间长 B．很少使用外设

C．使用CPU时间长 D．启动外设次数多

``100

D

``101

UNIX操作系统采用的进程调度算法为 。

A．不可强占处理机的动态化先数调度算法

B．可强占处理机的动态化先数调度算法

C．不可强占处理机的静态优先数调度算法

77

D．可强占处理机的静态化先数调度算法

``100

B

``101

当进程调度采用最高优先级调度算法时，从保证系统效率的角度来看，应提高 进程的优先

级。

A．连续占用处理器时间长的 B．在就绪队列中等待时间长的

C．以计算为主的 D．用户

``100

B

``101

采用时间片轮转调度算法时，对不同的进程可以规定不同的时间片。一般来说，对 进程给

一个较小的时间片比较合适。

A．需运算时间长的 B．需经常启动外设的

C．不需使用外设的 D．排在就绪队列末尾的

``100

B

``101

一种既有利于短小作业又兼顾到长作业的作业调度算法是 。

A．先来先服务 B．轮转 C．最高响应比优先 D．均衡调度

``100

C

``101

在单处理器的多进程系统中，进程什么时候占用处理器和能占用多长时间，取决于 。

A．进程相应的程序段的长度 B．进程总共需要运行时间多少

C．进程自身和进程调度策略 D．进程完成什么功能

``100

C

``101

分时系统中进程调度算法通常采用 。

A．响应比高者优先 B．时间片轮转法

C．先来先服务 D．短作业优先

``100

B

``501

设有三个作业J1、J2、J3，它们的到达时间和执行时间如下表：

作业名

J1

到达时间

8:00

执行时间

2小时

78

J2

J3

8:45

9:30

1小时

0.25小时

它们在一台处理器上按单道运行，若采用短作业优先调度算法，则此三作业的执行次序是 。

A．J3,J2,J1 B．J1,J2,J3

C．J1,J3,J2 D．J3,J1,J2

``500

C

``101

在下列作业调度算法中，可能引起作业长时间不能被装入执行的算法是 。

A．FCFS算法 B．计算时间短的作业优先算法

C．最高响应比优先算法 D．动态优先数调度算法

``100

B

``101

在非抢占调度方式下，运行进程执行V原语后，其状态 。

A．不变 B．要变 C．可能要变 D．可能不变

``100

A

``101

UNIX System V的进程调度原理基于 算法。

A．先来先服务 B．短作业优先

C．时间片轮转 D．时间片+优先级

``100

D

``501

设系统中有P1、P2、P3三个进程，并按P1、P2、P3的优先次序调度运行，它们的内部计算和I/O

操作时间如下：

P1：计算60 ms—I/O 80 ms—计算20 ms

P2：计算120 ms—I/O 40ms—计算40ms

P3：计算40 ms—I/O 80ms—计算40ms

设调度程序执行时间忽略不计，完成这三个进程比单道运行节省的时间是 。

A．140ms B．160ms C．170ms D．180ms

``500

B

``401

有三个作业A、B、C，它们的到达时间和执行时间依次为(8:50和1.5小时)、(9:00和0.4小时)、(9:30

和1小时)。当作业全部到达后，批处理单道系统按响应比高者优先算法进行调度，则作业被选中的

次序为 。

A．(ABC) B．(BAC) C．(BCA) D．(CAB)

79

``400

B

``101

下列选项中，降低进程优先级的合理时机是 。

A．进程的时间片用完 B．进程刚完成I/O，进入就绪队列

C．进程长期处于就绪队列中 D．进程从就绪队列转为运行状态

``100

A

``101

下列进程调度算法中，综合考虑进程等待时间和执行时间的是__________。

A．时间片轮转调度算法 B．短进程优先调度算法

C．先来先服务调度算法 D．高响应比优先调度算法

``100

D

``101

进程调度的关键问题是 。

A．内存的分配 B．时间片的确定 C．调度算法的确定 D．I/O设备的分配

``101

C

``101

下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是 。

A．先来先服务 B．高响应比优先

C．时间片轮转 D．非抢占式短任务优先

``100

B

``101

某单处理器多进程系统中有多个就绪进程，则下列关于处理机调度的叙述中，错误的是 。

A．在进程结束时能进行处理机调度

B．创建新进程后能进行处理机调度

C．在进程处于临界区时不能进行处理机调度

D．在系统调用完成并返回用户态时能进行处理机调度

``100

C

``501

一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序

如下：

P1：计算60ms，I/O80ms，计算20ms

P2：计算120ms，I/O40ms，计算40ms

80

若不考虑调度和切换时间，则完成两个作业需要的时间最少是 。

A．240ms B．260ms C．340ms D．360ms

``500

B

``101

分时操作系统通常采用 策略为用户服务。

A．先来先服务 B．短作业优先 C．时间片轮转 D．最高响应比

``100

C

``801

有两个作业A和B，分别在7:00和8:30到达系统，它们估计的计算时间分别为0.8小时和0.1小时，

系统在9:00开始以响应比高者优先算法进行调度。在单道系统中该两个作业被选中时的响应比各为

多少？

``800

9:00时，作业A的响应比=1+2/0.8=3.5 2分

作业B的响应比=1+0.5/0.1=6 4分

所以9:00时作业调度程序选中作业B 6分

9:06作业B结束，调度作业A，此时作业A的响应比=1+2.1/0.8=3.625 8分

综上可知，在单道系统中A、B两个作业被选中时的响应比分别为3.625和6 10分

``501

有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时

间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，今有如下作业序列，

作业优先数即为进程优先数，优先数越小优先级越高：

作业名

J1

J2

J3

J4

到达时间

10 : 10

10 : 20

10 : 30

10 : 50

估计运行时间

20分钟

30分钟

25分钟

20分钟

优先数

5

3

4

6

(1) 列出所有作业进入内存时间及结束时间。

(2) 计算平均周转时间。

``500

（1）各个作业进入主存时间、结束时间和周转时间如下表所示：

作业名

J1

J2

J3

J4

提交时间

10：10

10：20

10：30

10：50

进入时间

10：10

10：20

11：00

10：50

结束时间

11：00

10：50

11：25

11：45

50

30

55

55

6分

周转时间

（2）平均周转时间：（50+30+55+55）/4=47.5（min） 10分

``501

有一个多道程序设计系统，采用不可移动的可变分区方式管理主存空间，设主存空间为100K，采

81

用最先适应分配算法分配主存，作业调度采用响应比高者优先算法，进程调度采用时间片轮转算法

（即内存中的作业均分CPU时间），今有如下作业序列：

作业名

J1

J2

J3

J4

J5

提交时间

10 : 00

10 : 15

10 : 30

10 : 35

10 : 40

需要执行时间

40分钟

30分钟

20分钟

25分钟

15分钟

要求主存量

25K

60K

50K

18K

20K

假定所有作业都是计算型作业且忽略系统调度时间。回答下列问题：

(1) 列表说明各个作业被装入主存的时间、完成时间和周转时间；

(2) 写出各作业被调入主存的顺序；

(3) 计算5个作业的平均周转时间。

``500

（1）各个作业被装入主存的时间、完成时间和周转时间如下表所示：

作业名

J1

J2

J3

J4

J5

装入主存时间

10：00

10：15

11：15

11：35

11：05

作业完成时间

11：05

11：15

11：55

12：10

11：35

周转时间

65

60

85

95

55

6分

（2）作业被调入主存的顺序为J1，J2，J5，J3，J4。

（3）平均周转时间=（65+60+85+95+55）/5=72（分钟）。

8分

10分

``501

有5个批处理作业（A，B，C，D，E）几乎同时到达一个计算中心，估计的运行时间分别为10，6，

2，4，8分钟，他们的优先数分别为1，2，3，4，5（1为最低优先数）。对下面的各种调度算法，

分别计算作业的平均周期时间。

（1）最高优先级优先

（2）短作业优先

``500

解：(1) 采用最高优先级优先调度算法，各进程开始运行时间、完成时间以及周转时间如下表：

进程 开始运行时间 完成时间 周转时间

A

B

C

D

E

20

14

12

8

0

30

20

14

12

8

30

20

14

12

8

平均周转时间为(30+20+14+12+8)/5=84/5=16.8(ms) 5分

(2) 采用短作业优先调度算法，各进程开始运行的时间、完成时间以及周转时间如下表：

进程 开始运行时间 完成时间 周转时间

A

B

20

6

30

12

30

12

82

C

D

E

0

2

12

2

6

20

2

6

20

10分 平均周转时间为(30+12+2+6+20)/5=70/5=14 (ms)

``501

某多道程序设计系统供用户使用的主存为100KB，磁带机2台，打印机1台。采用可变分区内存管

理，采用静态方式分配外围设备，忽略用户作业的I/O时间。现有如下作业序列：

作业名 提交时间 需运行时间 主存需求量 磁带机需求 打印机需求

J1

J2

J3

J4

J5

8:00

8:20

8:20

8:30

8:35

25分钟

10分钟

20分钟

20分钟

15分钟

15KB

30KB

60KB

20KB

10KB

1

0

1

1

1

1

1

0

0

1

作业调度采用FCFS策略，优先分配主存低地址区域且不准移动已在主存中的作业，在主存中的作

业均分CPU时间。现求：

(1) 作业被调度的先后次序；

(2) 全部作业运行结束的时间；

(3) 作业的平均周转时间；

(4) 最大作业周转时间。

``500

答：(1) 作业被调度的先后次序为J1, J3, J4, J2, J5 3分

(2) 全部作业运行结束的时间为9:30 5分

(3) 作业的平均周转时间为(30+55+40+40+55)÷5=44 (分钟) 8分

(4) 最大作业周转时间为55分钟。 10分

``501

多道批处理系统中配有一个处理器和2台外设(D1和D2)，用户存储空间为100MB。已知系统采用

可抢占式的高优先数调度算法(优先数越大优先级越高)和不允许移动的可变分区分配策略，设备分

配按照动态分配原则。今有4个作业同时提交给系统，如下表所示。

作业名

A

B

C

D

优先数

6

3

8

4

运行时间

5分钟

4分钟

7分钟

6分钟

内存需求

50M

10M

60M

20M

作业运行时间和I/O时间按下述顺序进行：

A． CPU (1分钟)，D1(2分钟)，D2(2分钟)

B． CPU (3分钟)，D1(1分钟)

C． CPU (2分钟)，D1(3分钟)，CPU(2分钟)

D． CPU (4分钟)，D1(2分钟)

忽略其他辅助操作，求4个作业的平均周转时间是多少分钟。

``500

各个作业的完成时间和周转时间如下表所示：

83

6分

作业名

A

B

C

D

完成时间

8：12

8：13

8：07

8：12

周转时间

12分钟

13分钟

7分钟

12分钟

10分 故平均周转时间 = (12+13+7+12) / 5 = 11（分钟）。

``501

某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200KB，磁带机5台。采用静态

方式分配外围设备，且不能够移动在主存中的作业，忽略用户作业的I/O时间、调度时间和移动作

业时间。现有如下作业序列：

作业名

A

B

C

D

E

进入后备队列时间

8:30

8:50

9:00

9:05

9:10

运行时间

40分钟

25分钟

35分钟

20分钟

10分钟

主存需求量

30KB

120KB

100KB

20KB

60KB

磁带机需求

3

1

2

3

1

作业调度采用最高响应比优先算法、进程调度采用SPF算法时，求作业调度选中作业的次序及

作业平均周转时间。

``500

解：(1) 作业调度选中作业的次序为A、B、D、E、C。 4分

(2) 作业A在9:10结束，其周转时间为40分钟；

作业B在9:55结束，其周转时间为65分钟；

作业C在10:40结束，其周转时间为100分钟；

作业D在9:30结束，其周转时间为25分钟；

作业E在10:05结束，其周转时间为55分钟；

故平均周转时间为(40+65+100+25+55)/5=57（分钟） 10分

``501

某多道程序设计系统采用可重定位分区内存管理(即允许移动在主存中的作业)，供用户使用的主存

为200KB，磁带机5台。采用静态方式分配外围设备，忽略用户作业的I/O时间、调度时间和移动

作业时间。现有如下作业序列：

作业名

A

B

C

D

E

进入后备队列时间

8:30

8:50

9:00

9:05

9:10

运行时间

40分钟

25分钟

35分钟

20分钟

10分钟

主存需求量

30KB

120KB

100KB

20KB

60KB

磁带机需求

3

1

2

3

1

假设作业调度采用最高响应比优先算法，进程调度采用时间片轮转算法(均分CPU时间)。请回

答下列问题：

(1) 写出作业调度选中作业的次序。

84

(2) 作业平均周转时间是多少分钟？

``500

解：(1) 作业调度选中作业的次序为A、B、E、D、C。 4分

(2) 作业A在9:30结束，其周转时间为60分钟；

作业B在9:45结束，其周转时间为55分钟；

作业C在10:40结束，其周转时间为100分钟；

作业D在10:15结束，其周转时间为70分钟；

作业E在9:55结束，其周转时间为45分钟；

故平均周转时间为(60+55+100+70+45)/5=66（分钟） 10分

``501

假设某个系统中有以下几个进程，每个进程的执行时间(单位：ms)和优先数如下(优先数越小，其优

先级越高)：

进程

P1

P2

P3

P4

P5

执行时间

10

1

2

1

5

优先数

3

1

5

4

2

如果在0时刻，各进程按P1、P2、P3、P4、P5 的顺序同时到达，忽略进程调度切换等辅助时

间，试回答下列问题：当系统分别采用

(1)先来先服务调度算法；

(2)抢占式优先级调度算法；

(3)时间片轮转算法(时间片为1ms)。

在使用以上各种算法的情况下，分别求各进程的开始运行时间、完成时间以及平均周转时间。

``500

解：(1)采用先来先服务调度算法，各进程开始运行的时间、完成时间以及周转时间如下表：

进程 开始运行时间 完成时间 周转时间

P1

P2

P3

P4

P5

0

10

11

13

14

10

11

13

14

19

10

11

13

14

19

平均周转时间为(10+11+13+14+19)/5=67/5=13.5(ms) 3分

(2) 采用抢占式优先级调度算法，各进程开始运行的时间、完成时间以及周转时间如下表：

进程 开始运行时间 完成时间 周转时间

P1

P2

P3

P4

P5

6

0

17

16

1

16

1

19

17

6

16

1

19

17

6

7分 平均周转时间为(16+1+19+17+6)/5=59/5=11.8(ms)

85

(3) 采用时间片轮转算法，各进程开始运行的时间、完成时间以及周转时间如下表：

进程 开始运行时间 完成时间 周转时间

P1

P2

P3

P4

P5

``501

有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其

优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周

转时间（进程切换开销不考虑）。

(1) 先来先服务(按A,B,C,D,E顺序)算法；

(2) 优先级调度算法；

(3) 时间片轮转算法(设时间片为1min)。

``500

(1) 采用先来先服务算法，5个任务的执行顺序、完成时间及周转时间如下表所示。

执行顺序 预计运行时间 开始执行时间 完成时间 周转时间

A

B

C

D

E

10

6

2

4

8

0

10

16

18

22

10

16

18

22

30

10

16

18

22

30

0

1

2

3

4

19

2

7

4

14

19

2

7

4

14

10分 平均周转时间为(19+2+7+4+14)/5=46/5=9.2(ms)

5个进程的平均周转时间为：(10+16+18+22+30)/5=19.2 (min) 3分

(2) 采用最高优先级调度算法，5个任务的执行顺序、完成时间及周转时间如下表所示。

执行顺序 预计运行时间 优先数 开始执行时间 完成时间 周转时间

B

E

A

C

D

6

8

10

2

4

5

4

3

2

1

0

6

14

24

26

6

14

24

26

30

6

14

24

26

30

6分 5个进程的平均周转时间为：(6+14+24+26+30)/5=20 (min)

(3) 采用时间片轮转调度算法，可以认为5个进程均分CPU时间，它们在系统中的执行情况如下：

第一轮：A，B，C，D，E （5min）

第二轮：A，B，C(C完成，即C的周转时间为8min)，D，E （5min）

第三轮：A，B，D，E （4min）

第四轮：A，B，D(D完成，即D的周转时间为17min)，E （4min）

第五轮：A，B，E （3min）

第六轮：A，B(B完成，即B的周转时间为23min)，E （3min）

第七轮：A，E （2min）

第八轮：A，E(E完成，即E的周转时间为28min) （2min）

86

本文标签： 进程时间调度信号量