考研-操作系统基础知识归纳和总结

考研基础知识总结

•什么是操作系统？它有什么基本特征？（哈工大2000年试题）

【解答】

操作系统：操作系统是计算机系统中的一个系统软件。它是一些程序模块的集合，

这些程序模块管理和限制计算机中的硬件和软件资源，合理地组织计算机工作流程，以

便有效地利用这些资源为用户供应一个功能强，运用便利的工作环境，从而在用户及计

算机之间起到接口的作用。

操作系统的基本特征是并行性，共享性，不确定性。

•推断：操作系统程序都是在核心态下才能运行。（大连理工大学2000年试题）

【分析】

操作系统是一组限制和管理计算机硬件和软件资源，合理地对各类作业进行调度

以及便利用户的程序的集合。操作系统供应的服务，一部分必需在核心态下才能运行，

如进程调度，目录服务等。还有一些功能，如DOS下的外部命令，则可以由用户调用，

运行在用户态下。

【解答】

错误。

・批处理系统的主要缺点是：（清华大学1996年试题）

A.CPU利用率低。B.不能并发执行。

C.缺少交互性。D.以上都不是。

【解答】

选择C。

•填空：多道运行的特征之一是宏观上并行，它的含义是（（华中科技大学2000

年试题）

【分析】

多道运行的特征是多道性，宏观上并行，彳散观上串行。多道性是指计算机主存中同

时存放几道相互独立的程序。宏观上并行是指同时进入系统的几道程序都处于运行过程

中，即它们先后开始了各自的运行，但都未运行完毕。微观上串行是指主存中的多道程

序轮番或分时地占有处理机交替执行。

【解答】

并发程序都已经开始执行，但都未结束。

•推断：在分时系统中，响应时间X时间片X用户数，因此为改善响应时间，常用的

原则是使时间片越小越好。（东南大学1996年试题）

【分析】

时间片越小，进程切换所用的开销就相对越大。因此时间片不是越小越好，一般运

用户键入的常用命令能在一个时间片内处理完毕即可。

【解答】

错误。

・实时系统应具备的两个基本特性是（）和（）。（北京理工大学2000年试题）

【分析】

实时系统是顺应实时限制和实时信息处理的须要而产生的。所谓"实时"是表示"及时

"，"即时"，而实时系统是指系统能及时（或即时）响应外部事务的恳求，在规定的时间

内完成对该事务的处理，并限制全部实时任务协调一样地运行。实时系统的应用领域确

定了它的特性是：①具有实时时钟管理功能；②能进行过载爱护；③高牢靠性。

【解答】

及时性高牢靠性

・实时信息处理是实时应用的一种，例如（）和（）都是实时信息处理的例子。

（华中科技大学2000年试题）

【解答】

飞机订票系统，图书资料查询系统

•现代操作系统的基本功能是管理计算机系统的硬件，软件资源，这些管理工作分

为A管理，B管理，C管理，D管理，E和通信事务管理。（东南大学2000年试题）

【解答】

A.处理机B.存储器管理C.设备D.文件E.作业

【扩展】

选择：操作系统的（）管理部分负责对进程调度。

A.主存储器B.限制器C.运算器D.处理机这里要防止把处理机与系统结

构中所说的处理机的组成混淆起来。选择D。

•为了支持多道程序运行，存储管理必须要实现的主要功能有（），（）和主存

扩充。（华中科技大学1997年试题）

【分析】

在多道程序运行环境下，程序员无法预知存储管理模块将把他们的程序安排到主存

的什么地方，而且程序员也盼望摆脱存储地址，存储空间大小等细微环节问题。因此存

储管理模块应当供应地址重定位实力。另外，由于主存中可同时存放多道程序，为了防

止程序间相互干扰，存储管理模块必需供应存储爱护手段。

【解答】

存储无关性，存储爱护

・选择：衡量整个计算机性能指标的参数有：（北京理工大学1999年试题）

A.用户接口。B.资源利用率。C.作业步的多少。D.吞吐量。E.周

转时间。

【分析】

操作系统的性能与计算机系统工作的优劣有着亲密的联系。评价操作系统的性能指

标一般有：

系统的牢靠性；系统的吞吐率（量），是指系统在单位时间内所处理的信息量，以每

小时或每天所处理的各类作业的数量来度量；系统响应时间，是指用户从提交作业到得

到计算结果这段时间，又称周转时间；系统资源利用率，指系统中各个部件，各种设备

的运用程度。它用在给定时间内，某一设备实际运用时间所占的比例来度量；可移植性。

【解答】选择B,D,Eo

【扩展】

推断：资源的利用率高和系统的工作效率高是一回事O。（东南大学试题）

解答：系统的工作效率，也就是吞吐率。从上述分析可知，此题应判错误。

3.2逻辑结构

•推断：数据库管理程序须要调用操作系统程序，操作系统程序的实现也须要数据

库系统的支持。O（大连理工大学2000年试题）

【分析】

从操作系统虚拟机的结构来看，最核心层是裸机，紧挨着的一层是操作系统，这一

层把应用程序和裸机隔离开来，使得应用程序看起来似乎运行在一个虚拟机器上。题中

说法没有正确反映应用程序与操作系统的关系。

【解答】

错误。

•简答：操作系统有哪几种结构设计方法？简述其中之一的特点。（武汉大学2000

年试题）

【解答】

操作系统有无结构，层次结构和客户/服务器模型等3种结构设计方法。

现今大多数操作系统采纳的是层次结构。层次结构是结构设计方法的一种，运用这

种方法进行设计时，可以形成正确，结构清晰的软件系统，从而达到牢靠，可适应，可

移植的设计目标。在层次式结构下，操作系统的各模块应处于什么位置，各模块之间的

关系特别清晰。

・一个分层结构操作系统由裸机，用户，CPU调度和P,V操作，文件管理，作业

管理，内存管理，设备管理，命令管理等部分组成。试按层次结构的原则从内到外将各

部分重新排列。（中国科学院计算技术探讨所1997年试题）

【解答】

按层次结构的原则从内到外依次为：裸机，CPU调度和P,V操作，内存管理，作

业管理，设备管理，文件管理，命令管理，用户。

・在计算机系统中，为什么要区分管态与目态？操作系统为什么能为用户程序供应

各种服务？（西安电子科技大学1999年试题）

【解答】

操作系统是计算机系统中最重要的系统软件，为了能正确地进行管理和限制，其本

身是不能被破坏的。因此，系统采纳了区分处理机状态的方法，为操作系统程序建立一

个爱护环境。这样，用户程序只能在管态下运行，只能执行非特权指令，只能访问自己

的存储区，从而爱护了操作系统程序的正常运行。

操作系统虚拟机为用户供应了一个帮助解决问题的装置。操作系统为用户供应两种

类型的用户界面,其一是命令接口，包括键盘命令，作业限制语言，图形化用户界面等;

其二是系统调用，又称程序接口。通过这两种界面，操作系统把它的全部操作命令的集

合呈现给用户（或用户程序），从而实现了为用户服务。

•推断:用户程序通常可以直接访问系统缓冲区中的数据。（）（大连理工大学2000

年试题）

【分析】

由前面叙述可知，用户程序工作在目态下，只能直接访问自己的存储区，访问系统

缓冲区必需通过操作系统的服务。

【解答】

错误。

・选择：你认为下列哪几种指令应当在核心状态下执行。（（上海交通大学1999年

试题,10分）

1.屏蔽全部中断；2.读时钟周期；3.设置时钟日期；4.改变存储映像图；5.存

取某地址单元的内容；6.停机。

【解答】

1,2,4,6必需在核心状态下执行。

•简答：试说明中断在进程限制中的推动作用。（南开大学2000年试题）（8分）

【解答】

中断是实现操作系统功能的基础，是构成多道程序运行环境的根本措施，是进程限

制中的推动力气。例如，外设完成中断或恳求运用外设的访管中断的出现，将导致I/O

管理进程投入运行；申请或释放主存而发出的访管中断，将导致在主存中创建一个进程

而且开始运行；时钟中断或I/O完成中断，可导致处理机调度工作的执行；操作员从键

盘发出终止执行的命令，可以终止当前进程的运行。所以，中断是进程运行的引导，是

它们被激活的驱动源。

•选择：中断发生时，由硬件爱护并更新程序指令计数器PC,而不是由软件完成,

主要是为了（）（华中科技大学1998年试题）

A.提高处理速度。B.使中断程序易于编制。C.节约内存。D.能进入

中断处理程序并能正确返回。

【分析】

一次中断过程分为中断进入（由硬件负责）和中断处理过程（由软件负责）。在中

断进入过程中，首先保存PC,PS值，然后从中断向量地址中得到PC,PS值放入寄存

器。软件的中断处理过程是，先保存现场信息和参数传递，再执行中断处理程序，最终

复原和退出中断。简要地说，一次中断，两次爱护现场。分步爱护现场的缘由是，进入

软件的中断处理后，PC,PS寄存器里被填上了新内容，因此，PC,PS的爱护只能由

硬件完成。

【解答】

答案是D。

【扩展】

中断响应的实质是什么？

从上述分析可知，中断响应的实质是交换指令执行地址和处理器状态信息。

•填空：中断优先级是由硬件规定的，若要调整中断的响应次序，可通过。

（北京大学1997年试题）

【分析】

中断优先级是由硬件规定的,其次序是不能由软件更改的。要调整中断的响应次序,

只能通过中断屏蔽。

【解答】

中断屏蔽

3.3用户界面与OS实例

•在答卷上用连线把下面左右两列词连起来形成最恰当的5对。（东南大学2000年

试题）

左列：右列：

(1)Linux（1）面对对象

(2)UNIX（2）网络操作系统

(3)WindowsNT（3）微内核

(4)Mach3.0（4）自由软件

(5)OS/2（5）C语言

【分析】

UNIX的核心代码大部分是用C语言写的。WindowsNT是当然的网络操作系统。

Linux是UNIX的一种，详细讲Linux是一套兼容于SystemV以及BSDUNIX的操作系

统,也是遵循POSIX规范的一个操作系统。Linux于1991年4月由芬兰人LinusBenedict

Torvalds在赫尔辛基大学独立开发，并由此开创了自由软件的先河。当UNIX日渐庞大

困难而难以驾驭时，人们提出了Microkernel的概念，就是把Kernel去芜存菁，仅留下

重要的部分，以此减低Kernel的困难度。Mach就是在Camegie-Mellon（卡耐基-梅隆

CMU）大学诞生的一个Microkernel（微核心）操作系统（1980年）。Mach最普遍的版

本是Mach2.5。它是很多商业UNIX如DECOSF/1,NextStep的基础。Mach3.0才是真

正纯粹的完全Microkernel化版本。

OS/2采纳32位抢先多任务体系结构，采纳客户机一服务器策略，在对等层环境既

是一个客户机又是一个服务器。OS/2可以同时运行Windows3.1,DOS和OS/2的应用

软件。

OS/2的图形用户界面称为WorkplaceShell。它运用面对对象的标记和拖放界面（在

这一点上，WindowsNT也是）。用户可以对工具和文件夹进行个人化以简化对重要信息

的访问。

【解答】

连线见下图：

充图I：

（1）面向对象

（2）掰络操作系统

（3）微内核

（4）自由软件

（5）C语言

3.4进程的描述与限制

・什么是进程限制块？试从进程管理，进程通信，中断处理，文件管理，存储

管理，设备管理的角度设计进程限制块应包含的项目。（北京大学1999年试题）

【分析】

北京大学1990年，1992年，1995年，1997年都以名词说明的形式考查了PCB

这一知识点。1999年再次考查这一知识点，并提高了考试要求，即要求理解PCB结构

中各重量的含义。

熟记我们在前面列出的进程限制原语的形式描述有助于加深对这个题的理解。

【解答】

进程限制块（PCB）是为描述进程的运动变化过程而采纳的一个与进程相联系的数

据结构，用于记录系统管理进程所需的信息，描述进程的瞬间特征。它是进程的唯一实

体，操作系统通过PCB而感知进程的存在。

为了完成进程管理，进程通信，中断处理，文件管理，存储管理，设备管理等

各项任务，进程PCB结构必需如下项目：

①进程的标识符name：每个进程都必需有唯一的标识符，可以用字符或编号表示。

在创建一个进程时，由创建者给出进程的标识，唯一地标识进程，与其他进程区分。

②进程当前运行状态status：说明本进程目前处于何种状态（运行，就绪，等待）,

作为进程调度时安排处理机的主要依据。

③当前队列指针next：登记了处于同一状态的下一个PCB的地址，以此将处于同

一状态的全部进程链接起来。比如在一个就绪队列中，当前活动进程堵塞，则须要依据

当前队列指针调度下一个就绪进程进入运行。

④总链指针all_q_next：将全部的进程链接起来，进程PCB中的该项内容总是指向

总链中的下一个PCB地址。这在有的场合是很便利的，比如当创建一个进程时，须要推

断创建者给出的标识符名是否唯一，此时沿总链往下查找就比较便利。

⑤程序开始地址start_addi-：进程开始的地址。当一个进程被调度进入运行时，须

要从今处获得进程开始地址。

⑥CPU现场爱护区cpustatus：通常爱护的信息有工作寄存器，指令计数器以及程

序状态字等，供进程调度时运用。当一个进程由运行转入其他状态时，须要把这些信息

保存起来。当一个进程投入运行时，又须要把这些内容写入相应的寄存器。同时进行中

断处理也须要保存CPU现场。

⑦通信信息communicationinformation：是指每个进程在运行过程中与别的进程进

行通信时所记录的有关信息。

⑧家庭联系processfamily：有的系统允许一个进程创建自己的子进程，这样，会组

成一个进程家庭。在pcb中必需指明本进程与家庭的联系，如它的子进程和父进程的标

识符。

⑨占有资源清单own_resource,用于设备管理。

⑩进程优先级priority,在中断处理，进程调度过程中都须要比较进程之间的优先

级。

上述项目是一般PCB结构应包含最基本内容。不同的操作系统所运用的PCB结构

是不同的。在UNIX系统中，为完成存储管理，文件管理，还在PCB结构中设有i结点

指针，主存地址，当前中断爱护区内⑷等内容。

•推断:进程是基于多道程序技术而提出来的。其最基本的特性是并发性和动态性;

进程的执行也即在各种基本状态之间多次转换的过程。但只有处于就绪，堵塞，执行这

3种状态的进程位于内存。（中科院软件所2000年试题）

【解答】

错误。①去掉并发性；②进程在新，死状态上只经过一次；③进程都在内存中。

・一个单CPU的操作系统共有n个进程，不考虑进程状态过渡的状况：（北京大学

1995年试题）

①给出运行进程的个数。

②给出就绪进程的个数。

③给出等待进程的个数。

【分析】

单处理机在任一时刻只能处理一道程序，在不考虑状态过渡的状况下，任一进程只

有3种状态，即运行，就绪和等待。但此时该系统其他条件未知（如资源安排状况），

故无法确定就绪进程和等待进程的数目。

【解答】

①1。

②不肯定。

③不肯定。

•填空：为了实现进程由等待状态转换成就绪状态的状态变化，操作系统应供应

原语。(华中科技大学2001年试题)

【解答】

唤醒原语。

・什么是线程？试说明线程与进程的关系。(南京大学2000年试题)

【解答】

在引入线程的OS中，线程是进程中的一个实体，是被系统调度和分派的基本单位。

进程与线程既区分，又联系。进程是任务调度的单位，也是系统资源的安排单位;

而线程是进程中的一条执行路径，当系统支持多线程处理时，线程是任务调度的单位，

但不是系统资源的安排单位。每个进程至少有一个执行线程。

3.5同步，互斥与通信

・何谓临界区？下面给出的实现两个进程互斥的算法是平安的吗？为什么？(中国

科学技术大学1998年试题)

#defineTRUE;#defineFALSE;

intflag[2];

flag[0]=flag[l]=FALSE;

entei^crtsec(i)inti;{

WHILE(flag[l-i]);

flag[i]=TRUE;}

leave-crtsec(i)inti;{

flag[i]=FALSE;}

processi:/*i=0ORi=1*/

enter-crtsec(i);/*进入临界区*/

INCRTICALSECTION

Leave-crtsec(i);/*离开临界区*/

【解答】

一次仅允许一个进程运用的资源称为临界资源，在进程中对于临界资源访问的程序

段称为临界区。

从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自独立的速度向前推

动。但由于它们共享某些临界资源，而产生了临界区问题。对于具有临界区问题的共行

进程，它们之间必需互斥，以保证不会同时进入临界区。

这种算法是不平安的。因为，在进入临界区的操作enter-crtsec()不是一个原子操作,

假如两个进程同时执行完其循环(此前两个flag均为False),则这两个进程可以同时进

入临界区。

•举例说明P,V操作为什么要求设计成原语(即对同一信号量上的操作必需互

斥)。(北京大学1993年试题)

【分析】

这是一个概念题，要求考生对P,V操作有较深刻的理解。

【解答】

P操作的流程如下所示。

PROCEDUREP(S)BEGIN

lockoutinterrupts;

S:=S-l;

IFS<0THEN

BEGIN

status(q):=blockeda;

insert(Q,q);

unlockinterrupts;

scheduler;

END;

ELSEunlockinterruptsEND;

设信号量S的初值为1,当一个P操作执行完"S:=S-1"后，S的值为0,该P操作

不应被堵塞。但若P操作不是一个原语，也就是说在一个P操作执行的过程中可以有另

一个P操作同时在执行，假如第2个P操作在第1个P操作执行推断语句“IFS<0”前也

执行了"S:=S-1”操作，则这时的S值为-1。这时第一个P操作将会被堵塞。这样的P操

作不符合P操作的语义。

同样地，对于V操作，其流程为：

PROCEDUREV(S)BEGIN

lockoutinterrupts;

S:=S+1;

IFS<=0THEN

BEGIN

remove(Q,R);

status(R):=readya;

insert(RL,R);

length(RL):=length(RL)+1;

END;

unlockinterrupts;END;

设信号量s的初值为-1,当一个V操作执行完"S:=S+1”后，S的值为0,该V操

作应当唤醒一个被P操作堵塞的进程。但若V操作不是一个原语，也就是说在一个V

操作执行的过程中可以有另一个V操作同时在执行。假如第2个V操作在第1个V操

作执行推断语句"IFSN"前也执行了"S:=S+1"操作，则这时的S值为1。这时第1个V

操作将不再去唤醒被堵塞的进程。这样的V操作不符合V操作的语义。

同样地，当P操作的执行过程中插入了V操作，也会出现不符合原语语义的状况。

例如，在P操作执行完"S:=S-1”后，S的值为-1,经推断，该进程应当被堵塞。但若在

进行推断后堵塞进程前执行完另外一个V操作，则该V操作并没有可以唤醒的被堵塞的

进程。而当V操作执行完后接着执行P操作时，该P操作仍将堵塞该进程，这一进程将

不被唤醒。

对于V操作的执行过程中插入了P操作，也会出现不符合原语语义的状况。例如，

在V操作执行完"S:=S+1”后，S的值为1,该进程无需唤醒其他进程。但若在进行推

断前执行了一个P操作，则在后续操作中须要唤醒一个堵塞进程。

【扩展】

类似这一类有关概念的探讨，首先须要明确概念的定义，然后再进行探讨。在探讨

的过程中，对可能发生的状况应分类探讨。论述要清晰。

・一个系统有多个进程(>5)共同存在并同时工作，但只有5台磁带机。每个进

程最多可以申请一台磁带机工作。编制了下列程序来管理磁带机：(北京大学1993年试

题)

申请：

PROCEDUREget_tape(VARx:integer);

VARi:integer;

tape_units:sharedinteger;

wait_tape:sharedboolean;

tape:sharedARRAY[0..4]OFinteger;

BEGIN

wait_tape:=true;

P(S)；

WHILE(wait_tape二true)DO

BEGIN

IFtape_units>0THEN

BEGIN

tape_units:=tape_units-l;

i:=0;

WHILE(i<=4)DO

BEGIN

IFtape[i]=0THEN

BEGIN

x:=i;

tape[i]:=1;

exit

END;

i：=i+1;

END;

wait_tape:二false;

END;

END;

V(S);

END;释放：

PROCEDURErelease_tape(x:integer);

VARtape_units:sharedinteger;

tape:sharedARRAY[0..4]OFinteger;

BEGIN

P(S)；

tape_units:二tape_units+1;

tape[x]:=0;

V(S);

END;

说明：

shared表示该变量为多个进程共享。

S为信号量，初值为lo

其他变量初值为：

tape[i]=0(0<i<4)

tape_units=5

wait_tape=false

问：

①上述程序的问题在什么地方？

②改正它。

【分析】本题考查了临界资源的属性。临界资源可以为多个进程共享，访问，必需

是全部变量。

【解答】

程序的问题有：

(1)全部的共享变量应是全局变量，而非局部变量。

(2)wait_tape也应互斥共享，但在题中并未实现这一点。

改后的程序如下：

BEGIN

Vartape_units:sharedinteger;

tape:sharedARRAY[0..4]OFinteger;

wait_tape:sharedinteger;

S:integer;

PROCEDUREget_tape(varx:integer);

BEGIN

vari:integer;

P(S)；

wait_tape:=true;

WHILE(wait_tape二true)DO

BEGIN

IFtape_units>0THEN

BEGIN

tape_units:二tape_units-1;

i=0;

WHILE(i<=4)DO

BEGIN

x:=i;

tape[i]:=1;

exit

END;

i:=i+1;

END;

wait_tape:=folse;

END;

END;

V(S);

END;

PROCEDURErelease_tape(x:integer);

BEGIN

P(S)；

tape_units:=tape_units+1;

tape[x]:=0;

V(S);

End;

3.6算法设计题

•进程A和B利用公共缓冲池交换数据。设缓冲池有N个缓冲块，进程A每次生

成一个数据块存入一空缓冲区，进程B每次从缓冲池中取出一个满的缓冲块。试用信号

量及P,V操作实现进程A和B的同步。(中山大学1996年试题)

【分析】

本题是标准的生产者一消费者问题。与上题相比，运用了多缓冲区，须要增加一个

信号量。另外，环形缓冲池和环形队列管理也是考点之一。

【解答】

Varmutex,empty,full:semaphore:1,n,0;

buffer:ARRAY[0..n-l]ofitem;

in,out:integer:=0,0;

BEGIN

COBEGIN:

A:BEGIN

LI:

produceadateblock;

P(empty);

P(mutex);

Buffer[in]:=nextp;

in:=(in+1)modn

V(mutex);

V(full);

GOTOLI;

END;

B:BEGIN

L2:

P(fuU);

P(mutex);

Nextpc:=Bufler[out];

out:二(out+1)modn

V(mutex);

V(empty);

consumetheiteminnextc

GOTOL2;

END;

GOTOL2;END;

【扩展】

此题应留意以下几点：

(1)在全部的程序中P(mutex)和V(mutex)应成对出现。

⑵对资源信号量empty和foil的P,V操作也必需成对出现，但它们是处于不

同的程序中，正是这一点保证了互斥共享。

(3)在每个程序中的P操作依次不能颠倒，应先执行对资源信号量的操作，再执

行对互斥信号量的操作，否则可能引起进程死锁。

・设有一个具有N个信息元素的环形缓冲区，A进程依次地把信息写入缓冲区，B

进程依次地从缓冲区读出信息。回答下列问题：(中国科学院软件探讨所1996年试题)

①叙述A,B两进程的相互制约关系;②判别下列用RV操作表示的同步算法是

否正确？如不正确，试说明理由，并修改成正确算法。

VARbuffer:ARRAY0..N-1OFT;

in,out:O..N-1;VARSLS2:Semaphore;

SI:=0;S2:=N;in:=out:=0;

PROCEDUREA:

BEGIN

REPEAT

生产数据m;

P(S2);

Buffer(in):二m;

in:=(in+l)MODN;

V(S1);

forever

END;

PROCEDUREB:

BEGIN

REPEAT

V(S2);

m:=buffer(out);

消费m;

out:=(out+1)MODN;

P(S1)；

forever

END;

【分析】

本题是一个标准的生产者-消费者问题。题中所给的算法与标准算法不同，但考生

不能因此就说这个算法不正确。考生须细致分析试题中所给出的算法。

在本题中，进程B在运用缓冲区前(读缓冲区)无需进行任何P操作，即进程B

不会因任何缘由被堵塞。这与题目中的限制要求不相符。因此这个算法实现是错误的。

此外，对缓冲区的访问也没有用互斥信号量进行限制。

【解答】

①A和B两进程的相互制约关系如下：

当缓冲区满时，A进程不可以写，必需等待；当缓冲区空时，B进程不可以读，必

需等待。

②该算法有错，它对读进程进入临界区未加限制。当缓冲区为空时，也可以进入临

界区读信息。当存在多个读进程和多个写进程时，还须要引入一个信号量SO以防止同

时读或同时写。

改进后的算法如下：

VARbuffer:ARRAY0..N-1OFT;

in,out:O..N-1;VARSO,SI,S2:Semaphore;

SO:=1;S1:=0;S2:=N;in:=out:=0;

PROCEDUREA:

BEGIN

REPEAT

生产数据m;

P(S2);

P(S0);

Buffer(in):=m;

in:=(in+1)MODN;

V(S0);

V(S1);

forever

END;

PROCEDUREB:

BEGIN

REPEAT

P(S1)；

P(so)；

m:=bufier(out);

out:=(out+1)MODN;

V(S0);

V(S2);

消费m;

forever

END;

【扩展】

本题是一类判别错误和改错题。这类题目一般是用来检查考生对一些典型算法的驾

驭程度的。在本题中，是考查考生对生产者一消费者问题的驾驭。解答这类问题时，首

先须要对标准算法娴熟驾驭，其次，还需对算法的变化做到心中有数。不要把正确的变

化列为出错点。例如本例中，假如题目中的算法给出的V操作依次与标准算法不同，考

生则不能认为其解答是错误的。因为在限制算法中，V操作的依次不会影响算法的正确

性。

•今有3个并发进程R,M和P,它们共享了一个可循环运用的缓冲区B,缓冲区

B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区

B的一个单元中；进程M负责处理读入的字符，若发觉读入的字符中有空格符，则把它

改成“，“；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程

P取出后，则又可用来存放下一次读入的字符。请用P,V操作为同步机制写出它们能

正确并发执行的程序。(南京大学1997年试题)

【分析】

此题是3个进程之间的同步问题。明显R与M,R与P,P与M之间均应有一缓

冲区指针。与之对应有3个信号量。

【解答】

Varfull,changed,empty,mutex:integer;

VarfullP,changedP,emptyP:integer;

Varch:char;

VarcharrayARRAY[0..n]ofchar;

fullP:=0;

emptyP:=0;

changedP:=0;

fidl:=0;

empty:二n;

changed:=0;

mutex:=0;R:

BEGIN

getchar(ch);

P(Empty);

P(mutex);

charray[fullP]:=ch;

fullP:=(fullP+1)modn;

V(mutex);

V(changed);

END;

M:

BEGIN

P(changed);

P(mutex);

ch:=charray[changedP];

ifch=*'then

ch=','；

changedP:=(changedP+1)modn;

V(fuU);

V(changed);

END;

P:

BEGIN

P(fuU);

P(mutex);

ch:=charray[emptyP];

putchar(ch);

emptyP:二(emptyP+1)modn;

V(mutex);

V(empty);

END;

【扩展】

本题在进程同步之外，还考查了考生基本编程实力及环形队列操作。考生应当留意

这个信号。尽管P,V操作本身已有肯定难度，但仍旧存在结合其他知识点命题，以进

一步增加难度的可能。

我们可以列举一些知识点综合的方向。比如说，在读者一写者问题中，可以结合

UNIX文件系统附带考查文件打开，关闭等操作；可以把P,V操作和实际的资源管理

问题结合起来，等等。

•多个进程共享一个文件，其中只读文件的称之为读者，其余只写文件的称为写者。

读者可以同时读，但是写者只能独立地写。(中科院软件所1995年试题)

①说明进程间的相互制约关系，应设哪些信号量？

②用P,V操作写出其同步算法。

③修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者都必

需等待，而无论是否有读者在读文件。

【分析】

本题要求写出的算法与前面的题目略有不同。这里的两类进程(读者和写者进程)

的限制是不相同的。对于写者进程，只能独占文件，即当有写者进程时不能有其他进程

运行；对于读者进程，可以与其他的读者进程共享文件，即当有读者进程的，只允许其

他的读者进程运行，而不允许写者进程运行。此外，当全部正在运行的读者进程运行完

毕后，才允许其他的写者进程进入。

为了达到这一限制效果，我们引入了一个变量rc,用于记录当前正在运行的读者进

程数。每个读者进程进入系统后须对rc值加1。当rc值由0变为1时，说明是第一个读

者进程进入，因此须要该读者进程对限制写者进程的信号量进行P操作，以便与写者进

程互斥运行；当rc值由非。值增加时，说明不是第一个读者进程，此时限制写者进程的

信号量已经过P操作限制禁止写者进程进入，因此不须要再次对该信号量进行P操作。

当读者进程退出时，须对rc做减1操作。如发觉减1后rc值变为0,说明是最终一

个读者进程退出，因此须要该读者进程对限制写者进程的信号量进行V操作，以便使写

者进程能够进入。

【解答】

①进程间的相互制约关系有三类。一是读者之间允许同时读；二是读者与写者之间

须互斥进行；三是写者之间须互斥写。

②进程间的限制算法如下所示。

BEGIN

integermutexl,mutex2,rc;

mutex1:=1;

mutex2:二1;

rc:=0;

COBEGIN

reader:BEGIN

P(mutexl);

rc:=rc+1;

IFrc=1THENP(mutex2);

V(mutexl);

Readingthefile;

P(mutexl);

rc:=rc-l;

IFrc=0THENV(mutex2);

V(mutexl);

END;

writer:BEGIN

P(mutex2);

Writeingthefile;

V(mutex2);

END;

COENDEND;

③为了提高写者的优先级，我们增加一个信号量W,用以在写进程到达时封锁后续

的读者进程。相应的限制算法如下：

BEGIN

integermutex1,mutex2,rc,w;

mutex1:=1;

mutex2:=1;

rc:=0;

w:二1;

COBEGIN

reader:BEGIN

P(w);

P(mutexl);

rc:=rc+1;

IFrc=1THENP(mutex2);

V(mutexl);

V(w);

ReadingtheFILE;

P(mutexl);

rc:=rc-l;

IFrc=0THENV(mutex2);

V(mutexl);

END;

writer:BEGIN

P(w);

P(mutex2);

WriteingtheFILE;

V(mutex2);

V(w);

END;

COENDEND;

【扩展】

对于可由一类进程多次访问，而不同类的进程必需互斥访问的资源的限制，是进程

限制中常见的一类问题。本题是这类问题中的一个典型，它给出了对于这类资源的限制

方法，即采纳一个资源计数变量rc进行限制。把对于该资源的访问限制变成对变量rc

的访问。这时，资源计数变量rc是一个临界资源，须要用信号量对其进行访问限制。

•有桥如图所示。（北京大学1992年试题）

车流如箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可

以有多个同方向的车）。用P,V操作实现交通管理以防止桥上堵塞。

【分析】

由于桥上不允许两车会面，故桥应被互斥访问，而同一方向上允很多辆车依次通过,

即临界区允很多个实例访问。用一个信号量来互斥访问临界区。由于不能允许某一方向

的车完全“限制"桥，应保证最多某一方向上连续通过肯定数量的车后，必需让另一方向

上的车通过。用另两个信号量来实现这一点。

【解答】

BEGIN

Varintegermutex，availn,avails;

availn=m;

avails=m;

mutex=0;

COBEGIN

South:BEGIN

LI:

P(avails);

P(mutex);

Crossthebridge;

V(mutex);

V(availn);

END;

North:BEGIN

LI:

P(availn);

P(mutex);

Crossthebridge;

V(mutex);

V(avails);

END;

COEND;

END;

【扩展】

在解此类题目时，首先应分析清晰此题的临界区是什么，题目对临界区的共享的约

束条件是什么，再分析应设几个信号量，各信号量的作用是什么。当全部问题都分析清

晰之后再做题。另外当遇到实际问题时，依据实际状况，留意分析是否应补充约束条件。

在实际考试中最好把全部分析过程，补充的约束条件写出，一方面扶植解题，一方面扶

植老师阅卷。

3.7进程通信

•图所示的是高级通信原语SEND和RECEIVE不完整的框图。请填充适当的P,V

操作，并说明所用信号量的意义和初值。(中国科学院软件探讨所1994年试题)

申询一科总区

消且义消g区

从消鸟池上摘下一消总

消息区挖人落自於

消自浅楼恢区

将放消总区

【分析】

本题是一个生产者一消费者问题，与标准的生产者一消费者问题的不同之处在于本

题的消息缓冲区的个数是无限制的，因此，不须要生产者一消费者问题解答中的信号量

availo在框图中所给出的信号量就是限制消息个数的信号量fiill。为了正确地限制程序流

程，我们还要加入对应于生产者一消费者问题中的信号量mutex,以限制对消息链的互

斥访问。

【解答】

框图中所缺的步骤如下：

①P(S1)

②V(S1)

③P(S2)

@P(S1)

⑤V(S1)

其中，S1是用于限制互斥访问消息链的互斥信号量，其初值为1；S2是用于记录消

息个数的同步信号量，其初值为0。

・消息缓冲通信技术是一种高级通信机制，由Hansen首先提出。（北京大学1997

年试题）

①试叙述高级通信机制与低级通信机制P,V原语操作的主要区分。

②请给出消息缓冲机制（有界缓冲）的基本原理。

③消息缓冲通信机制（有界缓冲）中供应发送原语Send（receiver,a）,调用参数

a表示发送消息的内存区首地址,试设计相应的数据结构,并用P,V原语操作实现Send

原语。

【解答】

①P,V操作是一种低级通信机制，它们作为同步工具用在进程同步和互斥上是特

别有效的，但是作为通信工具，则不够志向。而高级通信机制是指用户可直接利用操作

系统所供应的一组通信命令，高效传送大量数据的一种通信方式。二者的主要区分如下:

P,V操作效率较低。

通信对用户不透亮。

②消息缓冲通信机制，首先由美国的Hansan提出，并在RC4000上实现。在这种

通信机制中，发送进程利用Send原语，将消息直接发送给接收进程。接收进程利用

Receive原语接受消息。该机制主要利用的数据结构是消息缓冲区。

发送进程在利用发送原语发送消息前，在自己的内存空间里设置一发送区，把待发

送的正文，发送进程标记符，消息长度等信息填入，然后调用发送原语，把消息发送给

目标进程。发送原语首先依据发送区中设置的长度来申请一个缓冲区i,接着把发送区中

的正文信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列上，应先获得接收进

程的内部标记符。由于该队列属于临界资源，应执行同步操作。

接收进程调用接收原语receive。，从自己的消息缓冲队列中，摘下第一个消息缓冲

区i,并将其中的消息正文拷贝到指定的消息接收区内。

③消息缓冲区可描述为：

typemessagebuffer=record

sender;发送者进程标记符

size;消息长度

text;消息正文

next;指向下一个消息缓冲区的指针

end;

发送原语：

PROCEDUREsend（receive,a）

〃接收进程标记receive,发送区a

BEGIN

getbufi(a.size,i);

i.sender:=a.sender;

i.size:二a.size;

i.text:二a.text;

i.next:=0;

getid(PCB.set,receive.j);

P(j.mutex);

insert(j.mq,i);

V(j.mutex);

V(j.sm);

END;

接收原语：

PROCEDUREreceive(b)

〃发送区b

BEGIN

j:二internalname;

P(j.sm);

P(j.mutex);

remove(j.mq,i);

V(j.mutex);

b.sender:=i.sender;

b.size:二i.size;

b.text:=i.text;

END;

3.8进程调度

・设某系统进程的状态除了最基本的三种状态外，还增加了创建状态，延迟状态和

完成状态。试画出系统的进程状态变迁图，并标明状态变迁可能的缘由。（华中科技大学

2001年试题）

【解答】

进程状态变迁图及可能的缘由如图所示:

3.9死锁

•用信号量及p,v操作解生产者-消费者问题，并改动操作使之产生死锁。（南开

大学1995年试题）

【分析】

本题是关于P,V操作及生产者一消费者问题的一个基本问题。在这里主要考查考

生对生产者一消费者问题的理解和对死锁问题的理解。

【解答】

生产者-消费者问题的流程如下：

BEGINintegermutex,avail,full;

mutex:=1;

avail:=n;

fuU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(avail);

P(mutex);

addTObuffer;

V(foU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(fuU);

P(mutex);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

要使该操作产生死锁，只需改动P操作的依次。能产生死锁的操作流程如下:

BEGINintegermutex,avail,full;

mutex:=1;

avail:=n;

faU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(mutex);

P(avail);

addTObuffer;

V(fuU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(mutex);

P(fiiU);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

在这个流程里，由于生产者和消费者在生产和消费之前都要对信号量mutex进行P

操作，所以，会导致生产者进入临界区后(对mutex进行P操作后)，因无缓冲区而被

堵塞；消费者由于无法进入临界区，无法释放缓冲区，从而导致死锁。同样地，当消费

者进入临界区后(对mutex进行P操作后)，由于无产品可供运用被堵塞；而生产者由

于无法进入临界区，无法生产产品，从而导致死锁。

【扩展】

产生死锁是在用信号量进行流程限制过程中常会遇到的一个问题。何时会发生死

锁。如何避开死锁，是在考研中常考的问题。在本题中，要求用经典的生产者-消费者问

题构造出死锁现象，是一种常见的题型。此外，还会有要求分析给定流程限制是否会产

生死锁等类似的问题。

•用信号量及P,V操作解生产者-消费者问题，并改动操作使之产生死锁。(南开

大学1995年试题)

【分析】

本题是关于P,V操作及生产者一消费者问题的一个基本问题。在这里主要考查考

生对生产者一消费者问题的理解和对死锁问题的理解。

【解答】

生产者-消费者问题的流程如下：

BEGINintegermutex,avail,full;

mutex:=1;

avail:二n;

fuU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(avail);

P(mutex);

addTObuffer;

V(fuU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(fon);

P(mutex);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

要使该操作产生死锁，只需改动P操作的依次。能产生死锁的操作流程如下:

BEGINintegermutex,avail,full;

mutex:=1;

avail:二n;

fuU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(mutex);

P(avail);

addTObuffer;

V(fuU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(mutex);

P(fuU);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

在这个流程里，由于生产者和消费者在生产和消费之前都要对信号量mutex进行P

操作，所以，会导致生产者进入临界区后（对mutex进行P操作后），因无缓冲区而被

堵塞；消费者由于无法进入临界区，无法释放缓冲区，从而导致死锁。同样地，当消费

者进入临界区后（对mutex进行P操作后），由于无产品可供运用被堵塞；而生产者由

于无法进入临界区，无法生产产品，从而导致死锁。

【扩展】

产生死锁是在用信号量进行流程限制过程中常会遇到的一个问题。何时会发生死

锁。如何避开死锁，是在考研中常考的问题。在本题中，要求用经典的生产者-消费者问

题构造出死锁现象，是一种常见的题型。此外，还会有要求分析给定流程限制是否会产

生死锁等类似的问题。

•分析下面信号量解决哲学家进餐问题的同步算法是否满意同步机制的准则。若不

满意，说明为什么，并给出满意同步机制准则的同步算法。(中科院软件所1998年试题)

VARfork:ARRAY[0..4]OFsemaphore;

fork[0]:=fork[l]:=fork[2]:二fbrk[3]:=fork[4]:=1;

PARBEGIN

Pi:REPEAT/*第i个哲学家的生活过程*/

ThinkFORWhile;

P(fork[i]);

P(FOR[(i+l)MOD5]);

EatFORWHILE;

V(fork[i]);

V(fbrk[(i+1)MOD5]);

UNTILfalse

BXREND

【分析】

哲学家进餐问题是进程同步与互斥中的一个典型问题。本题要求分析算法是否满意

同步机制的准则，即每次至多有一个进程进入临界区，进程应在有限时间内进入临界区,

进程在临界区内停留有限时间。本题所给出的算法会在特定状况下产生死锁，因此无法

满意同步机制的准则中的“有限等待‘准则。为了解决这一问题，我们可以用额外的信号

量来限制对临界资源的访问，避开死锁。

【解答】

上述同步算法不满意同步机制的准则中的“有限等待”准则。当每个哲学家都只拿到

一把叉子时，发生死锁。

一种改进的算法如下：

VARfork:ARRAY[0..4]OFsemaphore;

VARmutex:semaphore;

fork[0]:=fork[l]:=fork[2]:=fork[3]:=fork[4]:=1;

mutex:=1;

PARBEGIN

Pi:REPEAT/*第i个哲学家的生活过程*/

ThinkFo