第3章 进程管理在计算机操作系统中,进程是资源分配的基本单位,同时进程也可作为独立运行的基本单位,用户可以从进程观点来研究操作系统。显然,进程这一概念在操作系统中极为重要。本章讨论进程的基本概念、进程控制、进程互斥与同步、进程通信及相关题解。
3.1 内容辅导
3.1.1 进程的基本概念
1.程序的顺序执行一个程序通常由若干个程序段所组成,它们必须按照某种先后次序来执行,仅当前一个操作执行完后才能执行后继操作,这类计算过程就是程序的顺序执行过程。程序顺序执行时有如下特征:
（1）顺序性：处理机的操作严格按照程序所规定的顺序执行,即每一操作必须在下一操作开始之前结束。
（2）封闭性,程序运行时独占系统的各种资源,故这些资源的状态(除初始状态外)只有本程序才能改变。程序一旦开始运行,其执行结果不受外界因素影响。
（3）可再现性：只要程序执行时的初始条件和执行环境相同,当程序重复执行时,都将获得相同的结果。
2.程序的并发执行所谓程序的并发执行是指若干个程序〈或程序段〉同时在系统中运行,这些程序(或程序段)的执行在时间上是重叠的,一个程序(或程序段)的执行尚未结束,另一个程序,（或程序段）的执行已经开始。
程序的并发执行虽然提高了系统吞吐量,但也产生了下述一些与顺序执行不同的新特征：
（1） 制约性：程序在并发执行时,由于它们共享资源或为完成同一项任务而相互合作,致使并发程序之间形成了相互制约关系。制约关系有两种：
①直接制约关系=进程一进程。
②间接制约关系z进程一资源一进程。
（2）失去封闭性：程序在并发执行时,多个程序共享系统中的各种资源,因而这些资源的状态将由多个程序来改变,致使程序的运行失去封闭性。
（3）不可再现性：程序并发执行时,由于失去了封闭性,也将导致失去其可再现性。
3,进程的定义及特征进程是操作系统中最基本、最重要的概念,但直至目前还没有一个统一的定义,这里给出几种比较容易理解又能反映进程实质的定义:
(1)进程是程序的一次执行。
(2)进程是可以和别的计算并发执行的计算。
(3)进程是程序在一个数据集合上运行的过程,是系统进行资源分配和调度的一个独立单位。
(4)进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。
以上进程的定义,尽管各有侧重,但它们在本质上是相同的。
进程具有以下几个基本特征:
（1）动态性：进程是程序的一次执行过程,因而是动态的。动态特性还表现在它因创建而产生,由调度而执行,因得不到资源而暂停执行,最后由撤消而消亡。
（2）并发性：引入进程的目的就是为了使程序能与其他程序并发执行,以提高资源利用率。
（3）独立性：进程是一个能独立运行的基本单位,也是系统进行资源分配和调度的独立单位。
（4）异步性：进程以各自独立的、不可预知的速度向前推进。
（5）结构特征：为了描述和记录进程的运动变化过程,并使之能正确运行,应为每个进程配置一个进程控制块。这样,从结构上看,每个进程都由程序段、数据段和进程控制块三部分组成。
4,进程状态及其变化进程执行时的间断性,决定了进程可能具有多种状态。事实上,运行中的进程至少具有以下三种基本状态。
（1） 就绪状态 进程已获得除处理机以外的所有资源,一旦分到了处理机就可以立即执行,这时进程所处的状态为就绪状态。
（2）执行状态 执行状态又称运行状态。当一个进程获得必要的资源.并占有处理机,即在处理机上运行,此时进程所处的状态为执行状态。
（3）阻塞状态 阻塞状态又称等待状态。正在执行的进程,由于发生某事件而暂时无法执行下去(如等待输入/输出完成〉,此时进程所处的状态为阻塞状态。
进程并非固定处于某一状态,它随着自身的推进和外界条件的变化而发生变化。
5.进程的表示进程通常有三部分组成：程序数据集合和进程控制块。
（1）程序,描述了进程所要完成的功能。
（2）数据集合：程序执行时所需要的数据和工作区。
（3）进程控制块：为了描述和控制进程的运行,系统为每个进程定义了一个数据结构—进程控制块(PCB)。所谓系统创建一个进程,就是由系统为某个程序(包含数据段)设置一个PCB,用于对该进程进行控制和管理。进程执行完成时,由系统收回其PCB,该进程便消亡了。系统将根据PCB而感知进程的存在,故PCB是进程存在的惟一标志。
一般来说,根据操作系统的要求不同,进程PCB所包含的内容多少会有些不同,但通常包括下面所列的内容:进程标识符,进程当前状态,进程队列指针,程序开始地址,迸程优先级,CPU现场保护区,通信信息,家族联系,占有资源清单等。
在一个系统中,通常存在许多进程,为了对它们进行有效管理,应该用适当方法将PCB组织起来。目前常用链表或表格将PCB组织起来。
3.1.2进程控制进程控制的职责是对系统中的全部进程实施有效的管理。其功能包括进程的创建、进程的撤消、进程的阻塞与唤醒等。这些功能一般是由操作系统的内核来实现的。
操作系统的内核是基于硬件的第一次软件扩充。在现代操作系统设计中,往往把一些与硬件紧密相关的模块或运行频率较高的模块以及为许多模块所公用的一些基本操作安排在靠近硬件的软件层次中,并使它们常驻内存,以提高操作系统的运行效率。
进程控制功能是通过执行各种原语来实现的。所谓原语是由若干条机器指令构成的,用于完成某一特定功能的一段程序。原语在执行期间不可分割,所以原语操作具有原子性。
为了防止操作系统及关键数据如PCB等受到用户程序有意或无意的破坏,通常将处理机的执行状态分成两种:核心态与用户态。
核心态又称管态：是操作系统管理程序执行时机器所处的状态。它具有较高的特权,能执行一切指令,访问所有的寄存器和存储区。
用户态又称目态：是用户程序执行时机器所处的状态。这是具有较低特权的执行状态,它只能执行规定的指令,访问指定的寄存器和存储区。
1.进程创建进程创建是由创建原语实现的。当需要进程时,就可以建立一个新进程。被创建的进程称为子进程,建立进程的进程称为父进程。
创建原语的主要功能是为被创建进程形成一个PCB,并填入相应的初始值。其主要操作过程是先向系统申请一个空闲PCB结构,再根据父进程所提供的参数将子进程的PCB初始化,并将此PCB插入就绪队列,最后返回一个进程的标识号。
2,进程撤消进程撤消是由撤消原语实现的。一个进程在完成其任务后,应予以撤消,以便及时释放它所占用的各类资源。撤消原语可采用两种撤消策略:一种策略是只撤消一个具有指定标识符的进程,另一种策略是撤消指定进程及其子孙进程。
撤消原语的主要功能是收回被撤消进程占用的所有资源,并撤消它的PCB。其主要操作过程是先从PCB集合中找到被撤消进程的PCB,若被撤消进程正处于运行状态,则应立即停止该进程的执行,设置重新调度标志,以便进程撤消后将处理机分给其他进程。对后一种撤消策略,若被撤消进程有子孙进程,还应将该进程的子孙进程予以撤消。对于被撤消进程所占有的资源,或者归还给父进程,或者归还给系统。最后撤消它的PCB。
3.进程阻塞与唤醒阻塞原语的作用是将进程由执行状态转为阻塞状态,而唤醒原语的作用则是将进程由阻塞状态变为就绪状态。
当一个进程期待的某一事件尚未出现时,该进程调用阻塞原语将自己阻塞起来。阻塞原语在阻塞一个进程时,由于该进程正处于执行状态,故应先中断处理机和保存该进程的CPU现场,然后将该进程插入到等待该事件的等待队列中。再从就绪队列中选择一个新的进程投入运行。
对处于阻塞状态的进程,当该进程期待的事件出现时,由发现者进程调用唤醒原语将阻塞的进程唤醒,使其进入就绪状态。
应当注意,一个进程由执行状态转变为阻塞状态,是这个进程自己调用阻塞原语去完成的,而进程由阻塞状态到就绪状态,是另一个发现者进程调用唤醒原语实现的,一般这个发现者进程与被唤醒进程是合作的并发进程。
3.1.3 进程同步多道程序系统中进程是并发执行的,这些进程之间存在着不同的相互制约关系,为了协调进程之间的相互制约关系,就需要实现进程的同步。互斥是同步的一种特殊情况。
1.进程同步的基本概念
（1）临界资源和临界区：系统中的多个进程可以共享系统中的各种资源,然而其中许多资源一次只能为一个进程所使用。我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机、绘图机等。除物理设备外,还有许多变量、数据等都可由若干进程所共享,它们也属于临界资源。在每个进程中,访问临界资源的那段程序称为临界区。
(2)同步：一个进程到达了某些点后,除非另一进程已完成了某些操作,否则就不得不停下来等待这些操作的结束,这就是进程间的同步。
(3)互斥:两个或两个以上进程,由于不能同时使用同一临界资源,只能一个进程使用完了,另一个进程才能使用,这种现象称为进程互斥。
为禁止两个进程同时进入临界区,可采用软件解决方法或一个同步机构来协调它们。但是,不论是软件算法或同步机构都应遵循下述准则,①空闲让进；②忙则等待；③有限等待；④让权等待。
2.信号量和P、V操作一个信号量的建立必须经过说明,即应该准确说明s的意义和初值。每个信号量都有相应的一个队列,在建立信号量时,队列为空。P、V操作为两条原语,信号量的值仅能由P、V操作原语来改变。
P、V操作的定义如下：
P(s),s=s-1
若S>=0,则进程继续运行。
若S<0,则该进程被阻塞,并将它插入该信号量的等待队列中。
V操作：S =S+1
若s >0,则进程继续执行。
若S<=0,则从信号量等待队列中移出第一个进程,使其变为就绪状态,然后再返回原进程继续执行。
3.信号量的应用利用信号量可以解决进程间的同步和互斥问题，实现进程间的互斥和同步模型如下：
（1）互斥模型进程P1 进程P2
P(S) P(S)
CS1 CS2
V(s) v(s)
其中，信号量的初值：S=1;CS1,CS2分别是进程P1和P2的临界区。
（2）同步模型
进程P1 进程P2
L1:P(S) L2,V(S)
其中，信号量的初值：S=0。
（3）用P、V操作描述前趋关系若干进程为了完成一个共同任务而并发执行。然而,这些并发进程之间根据逻辑上的需要,有的操作可以没有时间上的先后次序,即不论谁先做,最后的计算结果都是正确的。但有的操作有一定的先后次序,也就是说它们必须遵循一定的同步规则,只有这样,并发执行的最后结果才是正确的。我们可以用本章前面介绍的前趋图来描述进程在执行次序上的先后关系。
（4）生产者·消费者问题生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品,它们共享一个有界缓冲区,生产者向其中投放产品,消费者从中取得产品。生产者消费者问题是许多相互合作进程的一种抽象。例如,在输入时,输入进程是生产者,计算进程是消费者;在输出时,计算进程是生产者,打印进程是消费者。因此,该问题具有很大实用价值。
我们把一个长度为n的有界缓冲区(n〉O)与一群生产者进程P1、P2、…、Pm和一群消费者进程CI、C2、…、CK联系起来。假定这些生产者和消费者是互相等效的。只要缓冲区未满,生产者就可以把产品送入缓冲区,类似地,只要缓冲区未空,消费者便可以从缓冲区中取走物品并消耗它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品,也禁止消费者从空的缓冲区中提取物品。
为解决这一类生产者-消费者问题,应该设置两个同步信号量,一个说明空缓冲单元的数目,用empty表示,其初值为有界缓冲区的大小n,另一个说明满缓冲单元的数目,用full表示,其初值为0。在本例中有P1、P2、…、Pm个生产者和C1、C2、…、CK个消费者,它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源,必须互斥使用,所以,另外还需设置一个互斥信号量mutex,其初值为1。生产者.消费者问题的同步描述如下:
int full=0; /*申满缓冲单元的数目*/
int empty=n; /*空缓冲单元的数目*/
int mutex=1; /*对有界缓冲区进行操作的互斥信号量*/
main( )
{
Parbegin
producer i( ); /*i=1,2,…,m:j=1,2,…,k*/
consumer j( );
parend
}
produceri( ) /*i=1,2,…,m*/
{
while (生产未完成)
{
生产一个产品;
p(empty);
p(mutex);
送一个产品到有界缓冲区;
V(mutex);
V(full);
}
}
consumerj( ) /*j=1,2,…,k*/
{
while (还要继续消费)
p(full);
p(mutex);
从有界缓冲区中取产品;
V〈mutex〉;
v(empty);
消费一个产品;
}
}
(5)读者与写者问题在计算机系统中,有些文件是可共享的,当若干个并发进程都要访问某个共享文件时,应区分是读还是写(修改)文件。显然可允许多个进程同时读文件但不允许在进程读文件时让另一进程去修改文件,或者有进程在修改文件时让另一进程去读,否则会造成读出的文件内容不正确。尤其是绝对不允许多个进程同时修改同一文件。这样一类问题称为"读者一写者"问题。
为了实现读者与写者的同步和互斥,我们设置一个信号量S,用于读者与写者之间或写者与写者之间的互斥,初值为"1"。用一个变量rc表示当前正在读的读者个数,当进程可以去读或读结束后都要改变rc的值,因此rc又成为若干读进程的共享变量,它们必须互斥地修改rc。故必须定义另一个用于互斥的信号量Sr,初值也是"1"。读者一写者问题可描述如下:
var S,Sr:semaphorep:=1,1;
rc:interger;
rc:=0;
Parbegin
process Reader i(i=1,2,…,m)
begin
P(Sr);
rc:=rc+1;
if rc=1 then P(S)；
V(Sr);
Read file F;
P(Sr);
rc:=rc-1;
if rc=O then V(S);
V(Sr);
end
process Writer j(j=1,2,…,k)
begin
P(S);
Write file F;
V(S);
end;
Parend;
在这个程序中,当有进程在读而使一个请求写的进程阻塞时,如果仍有进程不断地请求读则写进程将被长期地推迟运行。但在实际的系统中往往希望让写者优先,即当有进程在读文件时,如果有进程请求写,那么新的读者被拒绝,待现有读者完成读操作后立即让写者运行,只有当无写者工作时才让读者工作。下面是写者优先的程序。其中信号量S,初值为1,用于读者与写者或写者与写者之间的互斥;另一信号量Sn,初值为n,表示系统中最多有n个进程可同时进行操作:
var S,Sn:Semaphore:=1,n;
Parbegin
process Reader i(i=1.2,…,n)
begin
P(S);
P(Sn);
V(S);
read file F;
V(Sn);
Process Writer j(j=1,2,…,k)
begin
P(S);
For i=1 to n do P(Sn);
Write file F;
for i:=1 to n do V(Sn);
V(S)
end
parend
其中Process Reader i中的P(S),V(S)保证了当有写者要工作时,不让新的读者去读。Process Writer j中的第一循环语句保证让正在工作的读者完成读后再执行写,完成写操作后由第二个循环语句恢复Sn的初值,最后的V(S)用于唤醒被阻塞的读、写进程。
3.1.3管程使用信号量来处理同步问题时,同步操作P(S)和V(S)分散在各个进程中,并遍布整个程序。这不仅给系统的管理和程序的维护和修改带来了麻烦,两且还会因同步操作的使用不当造成死锁。为了解决上述问题,又产生了一种新的进程同步工具一管程。
1.管程的定义管程机制提供了与信号量机制相同的表达能力,但它更容易控制。管程是由一组局部的变量对局部变量进行操作的一组过程以及对局部变量进行初始化的语句序列构成的一个软件模块,它可用来实现进程同步。取名为monitor_name的管程,其语法如下:
type momtor_name=momtor
variable declarations;
procedue entry P1(…);
begin …end;
┆
procedure entry Pn(…);
begin …end;
begin
initialization code;
end
而且,管程具有以下特点:
(1)管程内的局部变量只能被局部于管程内的过程所访问:反之亦然,即局部于管程内的过程只能访问管程内的变量。
(2)任何进程只能通过调用管程提供的过程入口进入管程。
(3)任一时刻,最多只能有一个进程在管程中执行。
保证进程互斥地进入管程是由编译器负责的。也就是说,管程是一种编程语言的构件,它的实现需要得到编译器的支持。
2.条件变量在任何时刻,最多只有一个进程在管程中执行,因此用管程很容易实现互斥,只要将需要互斥访问的资源用数据结构来描述,并将该数据结构放入管程中便可。若要用管程来实现同步,则在相应条件不满足时(如临界资源得不到时)必须能够将在管程内执行的进程阻塞。由于阻塞的原因不同,为了将它们区分开,引入了局部于管程的条件变量。条件变量的定义格式为:VarXJ:condition。对条件变量只能执行以下两种操作:
(1)wait操作。如X.Wait用来将执行进程挂到与条件变量x相应的等待队列上。
(2)signal操作。如X.signal用来唤醒与x相应的等待队列上的一个进程。值得注意的是,若没有等待进程,则X.Signal不起任何作用。
3.利用管程解决生产者一消费者问题利用管程来解决生产者一消费者问题,首先必须为它们建立二个管程:
type p_c=momtor
Var in,out,count:integer;
Buffer:array[0,…,n-1] of item;
notfull,notempty:condition;
procedure entry put(Var product:item)
begin
if count≥n then notfull.wait; /*等待缓冲池不全满条件成立*/
buffer[in]:=product;
in:=(in+1)mod n;
count:=count+1;
notempty.signal; /*缓冲池不全空条件成立*/
end
procedure entry get(Var product:item)
begin
if count≤Othen notempty.wait; /*等待缓冲池不全空条件成立*/
product:=buffer[out];
out:=(out+1)mod n;
count:=count-1;
notfull.signal; /*缓冲池不全满条件成立*/
end
begin
in:=out:=0;
count:=0;
end
上述管程P_c中包括两个局部过程:过程put负责将产品投放到缓冲池中;过程get负责从缓冲池中取出产品。另外,整型变量count表示缓冲池中己存放的产品数目,条件变量notfull、notempty分别对应于缓冲池不全满、缓冲池不全空两个条件。
而相应的生产者和消费者可描述为：
producer:begin
repeat
produce an item in nextp;
P_c.put(nextp);
until false
end
consumer:begin
repeat
P_c.get(nextc);
consume the item in nextc;
until false
end
3.1.4 进程通信进程间的信息交换称为进程通信。进程之间的互斥与同步就是一种进程间的通信方式。由于进程互斥与同步交换的信息量较少且效率较低,因此称这两种通信方式为低级通信方式,相应地也可将P、V操作称为两条低级通信原语。所谓高级通信方式是指进程之间以较高的效率传送大量数据的通信方式。
1.进程通信的类型高级通信方式可分为三大类:共享存储器系统、消息传递系统以及管道通信系统。
(1)共享存储器系统。高级通信中的共享存储器系统是指进程之间通过对共享存储区的读写来交换数据。共享存储器系统的另一种方式是利用共享的数据结构来进行进程通信,但这种方式对共享数据结构的设置及对进程间的同步都必须由程序员来处理,且只能进行少量的数据交换,因此属于低级通信方式。
（2）消息传递系统。消息传递系统中,进程间的数据交换以格式化的消息(网络中称作报文)为单位。根据实现方式,它又可分为直接通信和间接通信两类。在直接通信方式中,源进程可直接将消息发送给目标进程,此类操作系统通常提供send(receiver,message)和receive(sender,message)两条通信命令(原语)供用户使用。在间接通信方式中,进程间需要通过某种中间实体(即信箱)来进行通信,发送进程将消息投入信箱,而接收进程则从信箱中疆取得消息,因此,它不仅能实现实时通信,还能实现非实时通信。此时,操作系统应提供若干条原语分别用于信箱的创建、撤消和消息的发送、接收等。
(3)管道通信。所谓"管道"是指连接i两个进程的一个打开的共享文件,发送进程以字符流的形式将大量的信息写入管道,接收进程则在需要时从管道中读出数据。为了协调双方的通信,管道通信机制必须对发送进程和接收进程在利用管道进行通信时实施同步和互斥,并只有在确定了对方存在时方能进行通信。
3.1.5线程
1.线程的基本概念引入线程的目的是为了减少程序在并发执行时所付出的时空开销,从而使OS具有更好的并发性。在多线程os中,将拥有资源的基本单位与调度和分派的基本单位分开处理。此时,一个进程中含有一个或多个相对独立的线程,进程只是拥有资源的基本单位,每个线程都是一个可执行的实体,即CPU调度和分派的基本单位是线程。
线程可以利用线程标识符和一组状态参数来描述,并具有下述属性:
(1)轻型实体。线程除了在运行中必不可少的资源(如线程控制块、程序计数器、一组寄存器值和堆栈)外,线程基本上不拥有系统的资源。
(2)独立调度和分派的基本单位。线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位,为此,线程中必须包含调度所必需的信息。
(3)可并发执行。同一个进程中的多个线程,以及不同进程中的多个线程均可以并发地执行。
(4)共享进程资源。同一个进程中的各线程可以共享该进程所拥有的全部资源,如进程的地址空间、己打开的文件、定时器和信号量机构等。
由于线程基本不拥有资源,创建线程时不需另行分配资源,终止时也不需要进行资源的回收,而切换时也大大减少了需保存和恢复的现场信息,因此,线程的创建、终止和切换都要比进程迅速且开销小。另外,同一进程中的各线程可以共享该进程所占用的内存空间和已打开文件,因此,线程间通信也非常简便和迅速。
2.线程的控制在多线程OS环境下,应用程序在启动时,OS将为它创建一个进程,同时为该进程创建第一个线程。以后在线程的运行过程中,它可根据需要利用线程创建函数(或系统调用)再去创建若干个线程。所以线程是由线程创建的,但线程间并不提供父子关系的支持。
每个线程被创建后,便可与其他线程一起并发地运行。如同传统的进程一样,并发运行的线程之间也存在着共享资源和相互合作的制约关系,致使线程在运行时也具有间断性。相应地,线程在运行时,也具有执行、就绪、阻塞三种基本状态,并随着自身的运行和外界环境的变换而不断地在三种状态之间转换。
当线程完成了自己的工作后,它便可正常终止。线程的终止也可能是因为运行中出现错误或某种其他原因而引起的,此时它是被强行终止的。可见,线程如同进程一样,具有一定的生命周期。
3.线程的同步在多线程os中通常提供多种同步机制,如互斥锁、条件变量、信号量机制以及多读、单写锁等,它们可支持不同频率的交互操作和不同程度的并行性。
（1)互斥锁互斥锁有开锁和关锁两种状态,并能进行关锁和开锁两种操作。当一个线程需要访问某个临界资源时,线程首先应对为该资源所设置的互斥锁mutex进行关锁操作mutex_enter:判别mutex的状态,如果它已处于关锁状态,则试图访问该资源的线程将被阻塞;而如果mutex处于开锁状态,则将mutex关上后便可访问该资源。在线程完成对共享资源的访问后,必须执行开锁操作mutex-exit:如果有线程阻塞在该互斥锁上,则唤醒其中的一个线程;而如果没有阻塞的线程,则将互斥锁的状态置成开锁状态。为了降低线程被阻塞的频率,在有的系统中还提供了一种不阻塞的关锁操作mutex_tryenter,当mutex处于关锁状态时,mutex_tryenter并不阻塞线程,而只是返回一个指示操作失败的状态码。
互斥锁是一种比较简单的同步机制,而且是严格括入的(bracketing),一个线程去打开被另一线程关闭的互斥锁将是错误的,因此它只适用于实现线程对资源的互斥访问。由于操作互斥锁的时间和空间开销都较低,因而它较适合于高频度使用的关键共享数据和程序段。
（2)条件变量条件变量必须和互斥锁配合起来使用,它用于等待,直到某一特定条件为真。对条件变量的cv_wait操作将使线程阻塞,直到所等的条件信号成立后,才能由cv_signal操作将其中的一个阻塞线程唤醒。cv_wait操作在阻塞线程前将对相应的互斥锁执行开锁操作,并在返回前重新对互斥锁进行关锁操作。条件变量可用来实现互斥或同步,它的典型使用方式为:
mutex_enter(&mutex);
┇
while(some_condition){
cv_wait(&cv,&mutex);
}
┇
mutex_exit(&mutex);
这里允许条件是一个复杂的表达式,因为它受互斥锁的保护。
（3)信号量机制信号量机制也可用于多线程os中,实现诸线程或进程之间的同步。为了提高效率,可为线程和进程分别设置相应的信号量。
当某线程利用信号量来实现同一进程中各线程之间的同步时,可调用创建信号量命令来创建一私用信号量,其数据结构被存放在应用程序的地址空间中。私用信号量属于特定的进程所有,OS并不知道私用信号量的存在,因此,一旦发生私用信号量的占用者异常结束或正常结束,但并未释放该信号量所占用的空间时，系统无法使它恢复为0(空),也不能将它传送给下一个请求它的线程。
当要实现不同进程间或不同进程中各线程之间的同步时,则可由系统为它们创建-个公用信号量,其数据结构存放在受保护的系统存储区中,并由os为它分配空间并进行管理,故也称其为系统信号量。如果信号量的占有者在结束时未释放该公用信号量,则OS会自动将该信号量空间回收,并通知下一个进程。可见,公用信号量是一种比较安全的同步机制。
4.内核支持线程和用户级线程线程己在许多系统中实现,但实现的方式并不完全相同。有些系统中,特别是一些数据库管理系统如Informix中,所实现的是用户级线程；而另一些系统（如Macintosh和OS/2)所实现的是内核支持线程；还有一些系统如Soloris,则同时实现了这两种不同类型的线程。
(1)用户级线程。用户级线程仅存在于用户空间中,而与内核无关。就内核而言,它只是管理常规的进程-单线程进程,而感知不到用户级线程的存在。每个线程的控制块都设置在用户空间中,所有对线程的操作也在用户空间中由线程库中的函数(过程)完成,而无需内核的帮助。用户级线程的优点是不需要得到内核的支持:而且,线程的切换无需陷入内核,故切换开销小,速度非常快。另外,线程库对用户线程的调度算法与os的调度算法无关,因此,线程库可提供多种调度算法供应用程序选择使用。但在纯用户级线程的系统中,对应用程序来讲,一个线程的阻塞将导致整个进程中所有线程的阻塞,并且无法享用多处理机系统中多个处理器带来的好处。
(2)内核支持线程。内核支持线程是在核心空间实现的。内核为每个线程在核心空间中设置了一个线程控制块,用来登记该线程的线程标识符、寄存器值、状态、优先级筹信息。所布对线程的操作,如创建、撤消和切换等,都是通过系统功能调用由内核中的相应处理程序完成的。内核支持线程克服了用户级线程的两个缺点:首先内核可以把同一个进程中的多个线程调度到多个处理器中:其次,如果进程中的一个线程被阻塞,内核可以调度同二个进程中的另一个线程。它的另一个优点是内核本身也可以使用多线程的方式来实现。它的主要缺点是,即使CPU在同一个进程的多个线程之间切换,也需要陷入内核,因此,其速度和效率不如用户级线程。
(3)用户级线程和核心级线程的结合。为了同时获得用户级线程和内核支持线程的便利,某些系统(如Solads)同时提供了这两种类型的线程。在Solaris中除了提供内核支持线程、用户级线程这两种线程外,还在它们之间定义了一种轻型进程LWP。其中,内核支持线程和LWP是内核实现的,而用户级线程是由用户地址空间中的线程库实现的。内核调度和分派的基本单位是内核支持线程,而内核提供给用户的却是LWP,即每个用户进程都可拥有一个或多个LWP。LWP可以看成是用户级线程与内核支持线程之间的桥梁,每个LWP都与一个内核支持线程对应,它可将一个或多个用户级线程映射到一个内核线程。但每个内核支持的线程并不一定对应于某个LWP,如那些为OS本身建立的内核支持线程便没有对应的LWP。通常,程序员可不考虑LWP,而直接使用线程库编程,此时一个用户进程只对应于一个LWP,而且可获得用户级线程的所有便利。但如果他需要优化程序的性能、获得物理上的并行,则可将自己的用户级线程连接到多个LWP上,此时,被连接到LWP上的线程便具有了内核支持线程的所有属性。
3.2重点难点学习提示由于进程是OS中最重要的基本概念,因而本章也就成为全书中最重要的一章。读者应对以下几个重点、难点问题进行深入的学习,切实掌握好进程和进程同步的基本概念。
3.2.1 进程的基本概念进程既是os中的一个重要概念,又是系统进行资源分配和独立运行的基本单位。学习
os,首先必须理解和掌握好进程的概念,为此,应认真学习和掌握下述几个方面的内容:
(1)为什么要引入进程。引入进程是为了使内存中的多道程序能够正确地并发执行。在学习时应清楚地理解为什么程序(在未为之建立进程之前)不能与其他程序并发执行,而由PCB、程序段和数据段三部分组成的进程实体却能与其他进程一起并发执行。
(2)进程具有哪些基本特征。进程具有动态性、并发性、独立性、异步性和结构特征。在学习时应较好地理解每个特征的含义和形成原因,并且要特别注意比较进程和程序这两个概念的异同之处。
(3)进程有哪些基本状态。进程具有就绪、执行和阻塞三种基本状态。在学习时必须了解在一个进程的生命周期中,它是如何随着自身的执行和外界条件的变化不断地在各种状态之间进行转换的。
(4)进程控制块。为了描述和控制进程,os必须为每个进程建立一个进程控制块PCB。在学习时应了解PCB具有哪些作用,为此,在PCB中必须包含哪些内容。
3.2.2进程同步的基本概念进程同步既是OS中的一个重要概念,又是保证系统中诸进程间能协调运行的关键,故应对它有较深入的理解,并能较熟练地运用。为此,应对下述与进程同步有关的几个基本概念有较好的理解和掌握:
(1)临界资源。临界资源是指→次仅允许一个进程访问的资源。在学习时,应了解对这种资源应采取什么样的共享方式。
(2)临界区。进程中访问临界资源的那段代码称为临界区.显然,为了实现进程互斥地访问临界资源,诸进程不能同时进入自己的临界区。在学习时,应了解用什么样的机制(称同步机制)来实现进程互斥地进入自己的临界区。
(3)同步机制应遵循的准则。用于实现进程同步的机制有多种,但它们都应遵循"空闲让进"、"忙则等待"、"有限等待"和"让权等待";四个准则。读者必须清楚,为什么要同时满足这四条准则,如违背了其中的基本准则,其后果是什么。
3.2.3 信号量机制及其应用信号量机制是一种卓有成效的进程同步机制,它已被广泛地应用于各种类型的OS中。因此,,必须对下述几个与信号量有关的内容有较深刻的理解和掌握：
(1)信号量的含义。
(2)信号量的物理意义。
(3)用信号量实现互斥。为了实现进程对临界资源的互斥访问,需为每类临界资源设置初值为1的互斥信号量mutex。在学习时,应清楚在进入临界区前或退出临界区后应对mutex分别执行什么操作,为什么对mutex的P和V操作必须成对出现,如少了其中的P操作或V操作,会对互斥算法产生什么样的影响。
(4)用信号量实现前趋关系。为实现前驱关系Pi→Pj,可为它们设置一个初值为0的信号量S。在学习时,应清楚对S的P操作和V操作应分别安排在什么位置,同时必须注意P(S)操作和V(S)操作也必须成对出现。
(5)经典进程的同步问题我们以生产者一消费者为例,来说明学习此重点问题时应了解和掌握些什么。
①生产者一消费者问题是用于解决一群生产者和消费者之间的进程互斥和进程同步问题。在学习时首先应了解哪些资源属于临界资源,并为它们设置了哪些信号量,信号量的初值应如何设置;其次,应了解哪些地方需要同步,并需为它们设置哪些信号量,信号量的初值又应如何设置等。
⑵如何实现进程互斥。为实现对缓冲池的互斥访问,应为它设置一互斥信号量mutex,读者应在生产者进程和消费者进程中都能找到成对的用于实现互斥的P(mutex)和V(mutex)操作。
③如何实现进程同步。为实现进程同步,应为缓冲池设置表示缓冲区空和满的empty和full信号量,读者应在相互合作的进程中找到成对的P(empty)和V(empty)操作,成对的P(fu11)和V(full)操作。
④对程序的阅读方式。由于生产者-消费者问题属于并发执行程序,因此在阅读时可采取交替阅读的方式。我们可以先从任一程序(如生产者)开始阅读,当它因P操作失败而阻塞时,该程序便不能继续往下运行,此时,可去阅读消费者程序;而当消费者唤醒阻塞的生产者,或者消费者因P失败而受阻时,则又可返回到生产者程序继续阅读。
3.2.4消息传递通信机制无论是单机系统、多机系统,还是计算机网络中,消息传递机制都是一种使用十分广泛的进程通信机制,必须了解以下几个问题:
(1)什么是消息传递通信机制。这是指以格式化的消息为进程间数据交换单位的进程通信方式,在学习时应了解通常在一个消息中应包含哪几方面的内容,定长格式的消息和变长格式的消息分别具有什么优缺点。
(2)消息传递通信机制有哪几种实现方式。消息传递通信机制有直接通信和间接通信两种实现方式,在学习时应注意比较它们在原语的提供、通信链路的建立、通信的实时性等方面的异同。
(3)如何协调发送进程和接收进程。为了使诸进程间能协调地进行通信,必须对进程通信的收、发双方进行进程同步,在学习时应了解常用的同步方式有哪些,它们分别适用于何种场合。
(4)消息缓冲队列通信机制。消息队列通信机制是一种常用的直接通信方式,在学习时应较好地理解它是如何在诸进程间实现互斥和同步的,其发送和接收过程又是如何完成的。
3.2.5 线程的基本概念线程在操作系统领域中是一个非常重要的机制和技术,它能有效地提高系统的性能。目前,不仅在操作系统中,而且在数据库管理系统和其他应用软件中,都普遍引入了线程的概念。应对下述几个问题有较好的理解:
(1)为什么要引入线程。在学习时,读者必须清晰地认识到,为什么进程的并发执行需要付出较大的时空开销,这对系统的并发程度又将产生什么样的影响:而线程机制是如何解决上述问题的,它带来了哪些好处。
(2)线程具有哪些特征。线程实体具有轻型、可独立运行、可共享其所隶属的进程所拥有的资源等特征。在学习时,应了解线程自己为什么还必须拥有少量的私有资源,并注意在并发性、调度性、拥有资源和系统开销等方面对多线程OS中的线程和进程进行比较。
(3)如何创建和终止线程。在学习时应了解应用程序是如何创建线程和终止线程的,还应注意比较线程的创建和终止与传统的进程的创建和终止有什么异同之处。
(4)内核支持线程和用户级线程线程按其实现方式可分为内核支持线程和用户级线程两类。在学习时应了解以下两个方面的内容：
①什么是内核支持线程。内核支持线程的TCB被保存在核心空间中,它的运行需获得内核的支持。在学习时,必须了解内核支持线程的创建、撤消和切换等功能是如何实现的,内核支持线程有哪些优点,又有哪些缺点。
②什么是用户级线程。用户级线程是在用户空间实现的。在学习时,必须了解用户级线程有哪些优点,通过用户空间的线程库(即运行时系统)来实现用户级线程有哪些不足之处,而将用户级线程和核心支持线程结合起来(即内核控制的用户线程)又能带来什么样的好处。
(5)进程和线程的关系
(1)线程是进程的一个组成部分。一个进程可以有多个线程,而且至少有一个可执行线程。
(2)进程的多个线程都在进程的地址空间内活动。
(3)资源是分给进程的,而不是分给线程的。线程需要资源时,系统从进程的资源配额中扣除并分配给它。
(4)处理机调度的基本单位是线程。线程之间竞争处理机,真正在处理机上运行的是线程。
3.3典型问题分析和解答
1.在操作系统中为什么要引入进程概念?它会产生什么样的影响?
答:在操作系统中引入进程概念,是为了实现多个程序的并发执行。传统的程序不能与其他程序并发执行,:只有在为之创建进程后,才能与其他程序(进程)并发执行。这是因为并发执行的程序(即进程)是"停停走走"地执行,只有在为它创建进程后,在它停下时,方能将其现场信息保存在它的PCB中,待下次被调度执行时,再从PCB中恢复CPU现场而继续执行,而传统的程序却无法满足上述要求。
建立进程所带来的好处是使多个程序能并发执行,这极大地提高了资源利用率和系统吞吐量。但管理进程也需付出一定的代价,包括进程控制块及协调各运行的机构所占用的内存空间开销,以及为进行进程间的切换、同步及通信等所付出的时间开销。
2.作业、进程和程序之间的区别和联系答：（1）作业、进程和程序之间的联系：一个作业通常包括程序、数据和操作说明书三部分。每一个进程由PCB、程序和数据集合组成,这说明程序是进程的一部分,是进程的实体。因此,一个作业可划分为若干个进程来完成,而每个进程又都有其实体一程序和数据集合。
（2）进程和程序的区别
①进程是程序的一次执行,属于动态概念,而程序是一组有序的指令,是一种静态概念。但进程离开了程序也就失去了存在的意义。
②一个进程可以执行一个或几个程序z反之,同一程序可能由几个进程同时执行。
③程序可作为软件资源长期保留,而进程是程序的一次执行过程,是暂时的。进程具有生命期。
④进程具有并发性,能与其它进程并发运行。而程序不具备这种特征。
⑤进程是一个独立的运行单位,也是系统进行资源分配和调度的一个独立单位。因此,进程具有独立性,但有时进程间又具有相互制约性。
注意:说进程是一个独立的运行单位,是指在不具有线程的系统中而言的,在引入线程的系统中,进程不再是运行的基本单位,只是资源分配的基本单位。
3.PCB的作用是什么?为什么说PCB是进程存在的惟一标志?
答:进程控制块的作用,是使一个在多道程序环境下,不能独立运行的程序,成为一个能独立运行的基本单位、一个能与其他进程并发执行的进程。
在创建进程时,系统将为它配置一个PCB:在进行进程调度时,系统将根据PCB中的状态和优先级等信息来选择新进程,然后将老进程的现场信息保存到它的PCB中,再根据新进程PCB中所保存的处理机状态信息来恢复运行的现场:执行中的进程,如果需要访问文件或者需要与合作进程实现同步或通信,则也都需要访问PCB:当进程因某种原因而暂停执行时,也必须将断点的现场信息保存到它的PCB中:当进程结束时,系统将回收它的PCB。可见,在进程的整个生命周期中,系统总是通过其PCB对进程进行控制和管理,亦即系统是根据其PCB而不是任何别的什么而感知到一进程的存在,所以说,PCB是进程存在的惟一标志。
4.某系统的进程状态转换图如图3.1所示,请说明:
2
1 3
4
(1)引起各种状态转换的典型事件有哪些?
(2)当我们观察系统中某些进程时,能够看到某一进程产生的一次状态转换能引起另一进程作一次状态转换。在什么情况下,当一个进程发生转换3时能立即引起另一个进程发生转换1?
(3）试说明是否会发生下述因果转换:
2→1
3→2
4→1
解:(1)在本题所给的进程状态转换图中,存在四种状态转换。当进程调度程序从就绪对列中选取一个进程投入运行时引起转换1；正在执行的进程如因时间片用完而被暂停执行就会引起转换2；正在执行的进程因等待的事件尚未发生而无法执行（如进程请求完成I/O)则会引起转换3；当进程等待的事件发生时（如I/0完成)则会引起转换4。
(2)如果就绪队列非空,则一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的进程由执行状态变为阻塞状态,这时处理机空闲,进程调度程序必然会从就绪队列中选取一个进程并将它投入运行,因此只要就绪队列非空,一个进程的转换3能立即引起另一个进程的转换1。
(3)所谓因果转换指的是有两个转换,一个转换的发生会引起另一个转换的发生,前一个转换称为因,后一个转换称为果,这两个转换称为因果转换。当然这种因果关系并不是什么时候都能发生,而是在一定条件下才会发生。
2→1：当某进程发生转换2时,就必然引起另一进程的转换1。因为当发生转换2时,正在执行的进程从执行状态变为就绪状态,进程调度程序必然会从就绪队列中选取一个进程投入运行,即发生转换1。
3→2：某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前执行进程从执行状态变为阻塞状态,不可能又从执行状态变为就绪状态。
4→1：当处理机空闲且就绪队列为空时,某一进程的转换4就会引起该进程的转换1。因为此时处理机空闲,一旦某个进程发生转换4,就意味着有一个进程从阻塞状态变为就绪状态,因而调度程序就会将就绪队列中的此进程投入运行。
5.P1、P2、P3、P4、P5、P6、P7为一组合作进程,其前趋图如图3.2所示,试用P、V操作描述这7个进程的同步。
图3.2说明任务启动后P1先执行,当它结束后P2、P3可以开始执行,P2完成后P4、P5可以开始执行，P3完成后P6可以开始执行,仅当P4、P6、P6都执行完后,P7才能开始执行。为了确保这一执行顺序,设置8个同步信号量a、b、c、d、e、f、g、h分别表示进程P1、P2、P3、P4、P5、P6是否执行完成,其初值均为0。这6个进程的同步描述如下:
Var a，b,c,d,e,f,g,h:semaphore:==0,0,0,0,0,0,0,0;
begin
parbegin
begin S1;V(a);V(b);end a b
begin P(a);S2;V(c);V(d);end
begin P(b);S3;V(e);end
begin P(c);S4;V(f);end c d e
begin P(d);S5;V(g);end
begin P(e);S6;V(h);end
begin P(f);P(g);P(h);S7;end
parend f g h
图 3-2
6.什么是优先图?什么是进程图?二者有何区别?
解：优先图是一种有向无环图,其结点对应于独立的语句(组),从结点i到结点j的有向连线表示语句i必须在语句j开始执行之前完成.进程图可看做是一种(有向)树结构,其中每个结点是一个进程.从上个结点指向另一结点的有向连线指明前者创建了后者.优先图表征语句之间的优先制约关系,而进程图则展示进程的创建关系。在一个进程图中,Pi到Pj的边并不隐含Pi只能在Pj之后执行,而是表示Pi创建Pj,Pi和pj可以并发地执行。
7.下述算法是解决两进程互斥访问临界区问题的一种方法。试从"互斥"、"空闲让进"、"有限等待"等三方面讨论它的正确性。如果它是正确的,则证明之:如果它不正确?请说明理由。
Var c1,c2:integer:=1,1;
begin
parbegin
p1:begin
repeat
remain section1;
repeat
c1:=1-c2;
until c2<>0;
Critical section; /*临界区*/
c1:=1;
until false
end
p2:begin
repeat
remain section2;
repeat;
c2:=1-c1;
until c1<>0;
Critical section; /*临界区*/
c2:=1;
until false
end
parend
end
分析：在通过对共享变量的测试来实现进程互斥时,必须注意共享交量本身也应当是临界资源,如果多个进程对它们进行同时共享,则可能会导致程序互斥算法的失败。在做这类题目时,可将检查的重点放在将条件测试指令和前面(或后面)对测试指令中所用的共享变量的修改操作相分割的情况下,该变量又刚好被其他进程修改的时候。
答:本题中,p1、p2通过共享变量c1和c2来达到资源互斥使用的目的,其中,c1=1表示p1不在临界区内,c2=1表示p2不在临界区内。通过检查可知:
(1)该算法不能保证互斥访问临界区。
①由于c1、c2的初值都为1,若p1先获得CPU并申请进入临界区,则它可以进入临界区。在p1进入临界区后,c2=1,c1=0:②此时若进行进程调度并由p2获得CPU,而p2也试图进入临界区,执行完C2:=1-C1后,C2=1,C1=0;③此时若又进行CPU调度,并且p1重新获得CPU,并在返出临界区后执行c1:=1,则c2=1,c1=1:④若再进行CPU调度,并且由p2获得CPU,因c1=1,p2进入临界区,而此时c2=1,c1=1;⑤若再进行CPU调度并由p1获得CPU,当p1再申请进入临界区时,由于C2=1,P1将顺序进入临界区。可见,在这种情况下,pl和p2将同时进入临界区。
（2）该算法能保证空闲让进。因为,c1和C2的初值均为1;而c1只有在pl申请进入自己的临界区时才可能变为0,一旦P1退出临界区,它的值又将被置为1；同样,c2只有在P2申请进入自己的临界区时才可能变为0,一旦P2退出临界区,它的值又将被置为1。所以,当临界资源空闲时,不管它是否曾经被使用过,C1和C2的值均为1；此时,若p1进程申请进入自己的临界区,则先执行C1:=1-C2,将c1置为0,并因C2<>O条件成立而结束循环测试,随后进入自己的临界区;对p2进程,情况也是如此。
(3)在该算法中,若一进程在临界区内执行,则另一进程将处于“忙等”。因此,在某些特殊的情况下,有可能不能保证“有限等待”。
8.请描述在当前运行进程状态改变时,操作系统进行进程切换的步骤。
解:进程切换的步骤如下:
(1)保存处理器内容；
(2)对当前运行进程的PCB进行更新.包括改变进程状态和其他相关信息；
(3)将这个进程的PCB移人适当的队列(就绪、因事件阻塞、就绪挂起等)；
(4)挑选其他进程执行；
(5)对挑选进程PCB进行更新,包括将其状态改为运行；
(6)对存储器管理数据结构进行更新；
(7)恢复被选择进程上次移出时的处理器状态。
9.请举例说明如何利用信号量实现进程同步。
计算进程 单缓冲区 打印进程图3.3是单缓冲的计算进程和打印远程;
答:在用信号量机制实现同步时,只要找出进程之间的同步关系,并为每种同步关系设置一信号量,然后再在需要等待某种动作的地方插入P操作,在被等待的动作完成之后插人V操作。例如,如图3.7所示的共享单缓冲的计算进程和打印进程之间存在两种同步图关系:
(1)打印进程必须等待计算进程将计算结果放入缓冲之后,才能取数打印,因此,可为它们设置一初值为0的信号量SA,表示缓冲区中是否有计算结果可供打印:并将P(SA)操作放在打印进程取数打印的动作之前,V(SA)操作放在计算进程将计算结果放入单缓冲的动作之后。
(2)计算进程必须等打印进程将缓冲区中的前一个数据取走,缓冲区变空后,才能将下一个计算结果放入缓冲区,因此,可为它们设置一初值为1的信号量SB,表示是否有空闲的缓冲区可供存放计算结果:并将P(SB)操作放在计算进程,将计算结果放入缓冲区的动作之前,而将V(SB)操作放在打印进程腾出空闲缓冲之后。具体的同步算法可描述如下:
Var SA,SB:semaphore:=0,1;
begin
parbegin
cp:begin
repeat
compute next number;
P(SB);
add the number to buffer;
V(SA);
until false;
end
PP:begin
repeat
P(SA);
take a number from buffer;
V(SB);
Print the number;
until false;
end
parend
end
10.设公共汽车上,司机和售票员的活动分别是:
司机的活动,售票员的活动:
启动车辆; 关车门;
正常行车; 售 票;
到站停车; 开车门;
在汽车不断地到站、停车、行驶过程中,这两个活动有什么同步关系?用信号量和P、V操作实现它们的同步。
解：在汽车行驶过程中,司机活动与售票员活动之间的同步关系为：售票员关车门后,向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步:售票员开车门的动作也必须与司机停车取得同步。
在本题中,应设置两个信号量:s1、s2,s1表示是否允许司机启动汽车,其初值为0;s2表示是否允许售票员开门,其初值为0。用P、V原语描述如下z
int s1=0；
int s2=0；
main( )
{
parbegin
driver( );
busman( );
parend
}
driver( )
{
while(1〉
{
p(s1);
启动车辆;
正常行车;
到站停车;
v(s2);
}
}
busman( )
{
while(1)
{
关车门;
v(sl);
售票;
p(s2);
开车门;
上下乘客;
}
}
用P、V操作来控制现实生活中的操作流程是一类常见的试题。这类试题要求解题者能将生活中的控制流程用形式化的方式表达出来。
11.嗜睡的理发师问题:一个理发店由一个有N张沙发的等候室和一个放有-张理发椅的理发室组成。没有顾客要理发时,理发师便去睡觉。当一个顾客走进理发店时,如果所有的沙发都已被占用,他便离开理发店;否则,如果理发师正在为其他顾客理发,则该顾客就找一张空沙发坐下等待;如果理发师因无顾客正在睡觉,则由新到的顾客唤醒理发师为其理发。在理发完成后,顾客必须付费,直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。
分析：本题中,顾客进程和理发师进程之间存在着多种同步关系:
(1)只有在理发椅空闲时,顾客才能坐到理发椅上等待理发师理发,否则顾客使必须等待;只有当理发椅上有顾客时,理发师才可以开始理发,否则他也必须等待.这种同步关系类似于单缓冲(对应于理发椅)的生产者一消费者问题中的同步关系,故可通过信号量empty和full来控制。
(2)理发师为顾客理发时,顾客必须等待理发的完成,并在理发完成后由理发师唤醒他,这可单独使用一个信号量cut来控制。
(3)顾客理完发后必须向理发师付费,并等理发师收费后顾客才能离开;而理发师则需等待顾客付费,并在收费后唤醒顾客以允许他离开,这可分别通过两个信号量payment和receipt来控制。
(4)等候室中的N张沙发是顾客进程竞争的资源,故还需为它们设置了一个资源信号量sofa。
(5)为了控制顾客的人数,使顾客能在所有的沙发都被占用时离开理发店,还必须设置一个整型变量count来对理发店中的顾客进行计数,该变量将被多个顾客进程互斥地访问并修改,这可通过一个互斥信号量mutex来实现。
答:为解决上述问题,需设置一个整型变量count用来对理发店中的顾客进行计数,并需设置7个信号量,其中zmutex用来实现顾客进程对count变量的互斥访问,其初值为1；sofa是对应于等候室中N张沙发的资源信号量,其初值为N；empty表示是否有空闲的理发椅,其初值为1;full表示理发椅上是否坐有等待理发的顾客,其初值为0；cut用来等待理发的完成,其初值为0:payment用来等待付费,其初值为0;receipt用来等待收费,其初值为0。具体的算法描述如下:
Var count:integer:=0;
mutex,sofa,empty,full:semaphore:=1,N,1,0;
cut,payment,receipt:semaphore:=0,0,0;
begin
parbegin
guest:begin
P(mutex);
if(count>N)
begin
V(mutex);
exit shop;
end
else
begin
count:=count+1;
if(Count>1) then
begin
P(sofa);
sin on sofa;
P(empty);
get up fromsoft;
V(sofa);
end
else /*count=1*/
P(empty);
sit on the baber_chair;
V(full);
P(cut);
Pay;
V(payment);
P(receipt);
get up from the baber_chair;
V(empty);
P(mutex);
count:=count-1;
V(mutex);
exit shop;
end
end
barber:begin
repeat
wait(full);
cut hair;
V(cut);
P(payment);
accept payment;
V(recipt);
until false;
end
parend
end
上述算法只考虑了理发店只有一个理发师的情况,如何将它改成有多个理发师并配有一收银员的算法,作为留给读者进一步思考的习题。
12.消息缓冲队列通信机制应具有哪儿方面的功能?
答:在消息缓冲队列通信机制中,应具有如下儿方面的功能：
（1）构成消息：发送进程在自己的工作区设置发送区a,将消息正文和有关控制信息填入其中。
（2）发送消息：将消息从发送区a复制到消息缓冲区,并把它插入到目标进程的消息队列中'
(3)接收消息：由目标进程从自己的消息队列中找到第一个消息缓冲区,并将其中的消息内容拷贝到本进程的接收区b中。
(4)互斥与同步：互斥是指保证在一段时间内只有一个进程对消息队列进行操作；同步是指在接收进程和发送进程之间进行协调。为此,应在接收进程的PCB中,设置用于实现互斥和同步的信号量。
13.有一单向行驶的公路桥,每次只允许一辆汽车通过。当汽车到达桥头时,若桥上无车,便可上桥，否则,需等待,直到桥上的汽车下桥为止。若每一辆汽车为一个进程,请用P、V操作编程实现。
解：汽车进程pi(i=1,2,3,…)
到达桥头
P(S)
上桥行驶到达桥另一端
V(S)
信号量的初值：S=1
14.什么是内核支持线程和用户级线程?并对它们进行比较。
答:内核支持线程是在内核支持下实现的,即每个线程的线程控制块设置在内核中,所有对线程的操作(如创建、撤消和切换等),都是通过系统功能调用由内核中的相应处理程序完成。而用户级线程仅存在于用户空间中,即每个线程的控制块设置在用户空间中,所有对线程的操作也在用户空间中完成,而无需内核的帮助。
可从以下几个方面比较内核支持线程和用户级线程:
(1)内核支持：用户级线程可在一个不支持线程的os中实现,而内核支持线程则不然,它需要得到os内核的支持。
(2)处理器的分配：在多处理机环境下,对纯粹的用户级线程来说,内核一次只为一个进程分配一个处理器,即进程无法享用多处理机带来的好处:而在设置有内核支持线程时,内核可调度一个应用中的多个线程同时在多个处理器上并行运行,从而提高程序的执行速度和效率。
(3)调度和线程执行时间：对设置有内核支持线程的系统,其调度方式和算法与进程的调度十分相似,只不过调度的单位是线程:而对只设置了用户级线程的系统,调度的单位则仍为进程。因此,在条件相同的情况下,内核支持的线程通常比用户级线程得到更多的CPU执行时间。
(4)切换速度：用户级线程的切换,通常发生在一个应用程序的诸线程之间,由于不需陷入内核,而且切换的规则也相当简单,因此切换速度比内核支持线程至少快一个数量级。
(5)系统调用：在典型的os中,许多系统调用都会引起阻塞。当一个用户级线程执行这些系统调用时,被阻塞的将是整个进程:而当一个内核支持线程执行这些系统调用时,内核只阻塞这个线程,但仍可调度其所属进程的其他线程执行。
15.利用parbegin/parend结构编写一个实现无复制的双缓冲区方案的程序。
答：
Var bufret array[0..n-1] of item;
In,out:0..n;
nextp,nexte:Item;
in:=0;
out:=0;
parbegin
producer:
begin
repeat
…
produce am item in nextp
…
while (in+1)mod n=out do skip;
bufer[in]:=nextp;
in:=(in+1)mod n;
until false;
end;
consuII1er:
begin
repeat;
while in =out do skip;
nextc:==bufer[out];
out:=(out+1)mod n;
…
consume the item in nextc
…
until false;
end;
parend;
16.试说明如果P.V操作不是不可分割执行的,就会违反互斥性.
答：假定信号量S =1,且进程PI和P2并发地执行P(S),那么,下面的执行序列就违反了互斥性:
(1)To:P1判定S之值等于1:
(2)T1:p2判定S之值等于1:
(3)T2:P1将S减1并进入临界段:
(4)T3:P2将S减1并进入临界段.
17.创建新进程有哪几种实现方式?
解:创建新进程有四种方式:
(1)父进程继续与其子进程并发地执行
(2)父进程暂停执行直至其子进程全部执行完
(3)父进程和子进程共享所有的公用变量
(4)子进程只共享父进程变量的一个子集
18.一个二元信号量是其值仅取0和1的信号量,如何用二元信号量去实现"一般的"信号量?
解:令S是一般的信号量,可用下面的程序来实现它:
var s1 binary-semaphore{初值=1}
S2 binary-semaphore {初值=0}
C:integer {初值为S之值}
P(S):P(Sl)
C,=C一1;
If C<O then
Begin
V(Sl);
P(S2);
end
else V(S1);
V(S):P(Sl);
C,=C+1·
If C<=O then V(S2);
V(Sl);
19．一个多元信号量允许P和V原语同时在若干信号量上操作,在一个不可中断的操作中就可获得和释放几个资源,这样的P原语(操作在两个信号量上)可定义如下:
P(S,R):while (S《l or R《1)do skip;
S,=S -1·
R:=R-1;
那么,如何用常规的信号量来实现这种多元信号量?
解:可用下面的编码来实现这种多元信号量:
var S1,R1,integer:
mutex:semaphore; {初值=1}
X:semaphore; {初值=0}
P(S,R),P(mutex);
Sl:=S1-1;
Rl:=R1-1;
If Sl〈O or R1<O then
begin
V(mutex);
P(X);
End
else V(mutex);
V(S,R) P(mutex);
S1:=Sl+1;
R1:=R1+1;
If S1<=O and R1《O then V(X);
V(mutex);
20.一个文件可由若干不同的进程所共享,每个进程具有唯一的编号；假定文件可由满足下列限制的若干进程同时访问；与并发访问该文件的那些进程相关的唯一编号的总和必须小于n.设计一个协调对该文件访问的管程.
答：协调对该文件访问的管程如下:
type coordinator =monitor
Var count:integer;
S:condition;
procedure acquire (id:integer);
begin
while (count+id,n) do S-Wait;
count,=count +id
end
procedure leave (id:integer);
begin
count,=count -id;
end;
begin
count,=0;
end.
21,n个进程P1,P2,…,Pn共享一个CPU，一次最多只可有一个进程使用CPU；CPU一旦有空,就可被一个进程使用,当CPU被占用时,其他进程必须等待，当多个进程同时等待使用CPU时,CPU一经释放,其中优先权最高的进程就被允许使用它；优先权规定如下:进程Pi的优先权为i(i=1,2,…,n),而优先数较小者则其优先权较高，下面是进程Pi预定(RESERVE)、使用和释放(RELEASE)CPU的一个算法:
RESERVE(i);
使用CPU;
RELEASE;
试编出其中两个过程RESERVE(i)和RELEASE的程序.
解:过程RESERVE(i)和RELEASE的程序如下:
var:shared record
free:boolean;
waiting:array[l..n]of boolean;
end;
procedure entry RESERVE(i:1..n);
begin
region V do
begin
if free then free:=false
else begin
waiting[i]:=true;
await(not(waiting[i]));
end;
end;
end;
procedure entry RELEASE;
var k:1..n
begin
region v do
begin
for k:=lto n do
if waidng[k]
then begin
waiting[k]:=false;
exit;
end;
free:=true;
end;
end;
22.有一个仓库可以存放A、B两种物品,每次只能存人一件物品(A或B).存储空间充分大,只是要求-n〈A的件数-B的件数〈m,其中n和m是正整数.试用存人A、存入B和p、V操作,描述物品A和物品B的人库过程.
解:设置三个信号量,初值分别为:So=1:SA=m-1:SB=n-1.
物品A人库过程:
P(SA)
P(SO)
存人A
V(SO)
V(SB)
物品B人库过程
P(SB)
P(SO)
存入B
V(SO)
V(SA)
23．若有一售票厅只能容纳300人,当少于300人时,可以进入；否则,需在外等候。若将每一个购票者作为一个进程,请用P、V操作编程,并写出信号量的初值。
解:购票者进程P.(i=1,2,3,…)
┇
P(S)
进入售票厅购票退出售票厅
V（S）〉
信号量的初值:S=300
24.有一只铁笼子,每次只能放入一只动物。猎手向笼中放入老虎,农民向笼中放入猪,动物园等待取笼中的老虎,饭店等待取笼中的猪,试用P、V操作写出能同步执行的程序。
解:这个问题实际上可看作是两个生产者和两个消费者共享了一个仅能存放一件产品的缓冲器。生产者各自生产不同的产品,消费者各自取自己需要的产品。利用P、V操作编程为:
猎手进程 农民进程 动物园进程 饭店进程
P(S) P(S) P(S1) P(S2)
放入虎 放入猪 买老虎 买猪
V(S1) V(S2) V(S) V(S)
信号量初值:S=1,S1=0,S2=0。
也可以将这四个进程用程序表示为:
begin
S,S1,S2:semaphoms
S=1,S1=O,S2=O;
parbegin
process hunter
begin
L1,have a tiger;
P(S);
put a tiger;
V(S1);
go to L1
end ;
process peasant
begin
L2,have a tiger;
P(S);
put a pig;
V(S2);
go to L2
end;
process hotel
begin
L3,P(S1);
get a pige;
V(S);
eat a pig;
go to L3
end ;
process zoo
begin
L4:P(S2);
get a tiger;
V(S);
eat a tiger;
goto L4;
end;
parend
end
25.有一阅览室,读者进入时必须先在一张表上进行登记。该表为每一座位列出一个表目(包括座号、姓名、阅览时间),读者离开时要撤消登记信息。阅览室有100个座位。
(1)为描述读者的动作,应编写几个程序,应设置几个进程?程序和进程之间的对应关系如何?
(2)试用P、V操作描述这些进程间的同步关系。
解:(1)在本题中,每个读者都可视为一个进程,有多少读者就有多少进程。这些进程称为读者进程,设为Pi(i=0,1,…)。读者进程Pi执行的程序包括:登记、阅览和撤消。每个读者进程的活动都相同,所以其程序也相同。进程和程序的关系是z各读者进程共用同一程序。
(2)在读者进程所执行的程序中,对登记和撤消都需互斥执行,其信号量的初值为1,而对进入阅览室也需互斥执行,其信号量为100。现用P、V操作描述如下:
读者进程Pi(i=0,1,2,…)
P(S1)
P(S2)
登记
V(S2)
阅览
P(S2)
撤消
V(S2)
V(S1)
其中信号量S1的初值为100,信号量S2的初值为1。
3.4自测题
3.4.1 基本题一、判断题(正确的在括号中记√,错误的记×)
1.进程是一段独立的程序。 ( )
2.单独的并发语句可以完成模拟所有的优先图的功能。 ( )
3,P.V操作中信号量的值，永远代表着某类可用资源的数量。 （ ）
4.管程、条件临界域和信号量三者在用它们实现同步问题的意义下是等价的。 ( )
5.在引入线程的操作系统中,线程是资源分配和调度的基本单位。 （ ）
6.在多处理机系统中,禁止中断不足以保证互斥。 ( )
7.一个进程正在临界区中间执行时,不能被中断。 （ ）
8.尽管管程确保了互斥,但其中的过程必须是再人式的。 ( )
9.在只提供用户级线程的多处理机系统中,一个进程最多仍只能获得一个CPU。 ( )
10.操作系统对进程的管理和控制主要是通过PCB来实现的。 ( )
二单项选择题，在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者该题无分。
1.在进程管理中,当________时,进程从阻塞状态变为就绪状态。
A进程被进程调度程序选中 B.等待某一事件 C.等待的事件发生 D.时间片用完
2.建立进程就是____。
A.建立进程的目标程序 B.为其建立进程控制块
C.建立进程及其子孙的进程控制块 D.将进程挂起
3.分配到必要的资源并获得处理机时的进程状态是______。
A.就绪状态 B.执行状态 C.阻塞状态 D.撤消状态
4.在操作系统中,P、V操作是一种_______。
A.机器指令 B.系统调用命令 C.作业控制命令 D.低级进程通讯原语
5.在消息缓冲通信中，消息队列属于_________资源。
A.临界 B.共享 C.永久 D.可剥夺
6.对进程的管理和控制使用__________。
A.指令 B.原语 C.信号量 D.信箱通信
7.在操作系统中,进程是一个具有一定独立功能的程序在某个数据集上的一次______。
A.等待活动 B.运行活动 C.单独操作 D.关联操作
8.若P、V操作的信号量S初值为2,当前值为-1,则表示有_______等待进程。
A.0个 B.1个 C.2个 D.3个
9.下面对进程的描述中,错误的是__________。
A.进程是动态的概念 B.进程执行需要处理机
C.进程是有生命期的 D.进程是指令的集合
10.如果有三个进程共享同一互斥段,而且每次最多允许两个进程进入该互斥段,则信号量的初值应设置为
A.3 B.1 C.2 D.0
11.下列的进程状态变化中,____________变化是不可能发生的。
A.运行→就绪 B.运行→等待
C.等待→运行 D.等待→就绪
12.一个运行的进程用完了分配给它的时间片后,它的状态变为__________。
A.就绪 B.等待 C.运行 D.由用户自己确定
13.用V操作唤醒一个等待进程时,被唤醒进程的状态变为_______。
A.等待 B.就绪 C.运行 D.完成
14.临界区是_____________。
A.一段共享数据区 B.一个缓冲区
C.一段互斥执行的程序段 D.一个互斥资源
15.进程间的同步是指进程间在逻辑上的相互__________关系。
A.联接 B.制约 C.继续 D.调用
16信箱通信是一种__________通信方式。
A.直接通信 B.间接通信 C.低级通信 D.信号量
17._______________是一种只能进行P操作和V操作的特殊变量。
A.调度 B.进程 C.同步 D.信号量
18.操作系统通过_____________对进程进行管理。
A.进程 B.进程控制块 C.进程启动程序 D.进程控制区
19.下面所述步骤中,__________不是创建进程所必需的。
A.由调度程序为进程分配CPU B.建立一个进程控制块
C.为进程分配内存 D.将进程控制块链入就绪队列
20.多道程序环境下,操作系统分配资源以__________为基本单位。
A.程序 B.指令 C.进程 D.作业三．多项选择(在每小题的五个备选答案中选出二至五个正确答案，并将其代码写在题干后面的括号内。不选、错选、多选或少选者，该题无分)。
1.进程的特征有___________。
A.动态性 B.静态性 C.并发性 D.独立性 E.异步性 F.结构特性
2.有关进程的描述中正确描述是______________。
A.进程执行的相对速度不能由进程自己来控制
B.P、V操作都是原语操作
C.利用信号量的P、V操作可以交换大量信息
D.同步是指并发进程之间存在的一种制约关系
E.并发进程在访问共享资源时,不可能出现与时间有关的错误
3.进程间的通信方式有______________。
A.共享存储器 B.事件触发 C.消息传递 D.过程调用 E.信箱通信
4.用于解决进程间互斥的方法是_________。
A.信号量及P、V操作 B.加锁与开锁 C.信箱方式 D.消息缓冲方式 E.特权指令方式
5.进程主要由_________组成.
A.程序段 B.JCB C.数据段 D.PCB E.消息
6.对临界区的正确论述是__________。
A.临界区是指进程中用于实现进程互斥的那段代码
B.临界区是指进程中用于实现进程同步的那段代码
C.临界区是指进程中用于实现进程通信的那段代码
D.临界区是指进程中用于访问共享资源的那段代码
E.临界区是指进程中访问临界资源的那段代码
F.若进程A与进程B必须互斥地进入自己的临界区,则进程A处于对应的临界区内时,仍有可能被进程B中断
7.正确的叙述是____________。
A.操作系统的一个重要概念是进程,不同进程所执行的代码也不同
B.操作系统通过PCB来控制和管理进程,用户进程可从PCB中读出与本身运行状态相关的信息
C.当进程由执行状态变为就绪状态时,CPU现场信息必须被保存在PCB中
D.当进程申请CPU得不到满足时,它将处于阻塞状态
E.进程是可与其他程序并发执行的程序在一个数据集合上的运行过程,所以程序段是进程存在的惟一标志
8.正确的叙述是________________。
A.一个进程的状态发生变化总会引起其他一些进程的状态发生变化
B.进程被挂起(suspend)后,状态变为阻塞状态
C.信号量的初值不能为负数
D.线程是CPU调度的基本单位,但不是资源分配的基本单位
E.在进程对应的代码中使用P、V操作后,可以防止系统发生死锁
F.管程每次只允许一个进程进入
G.P、V操作可以解决一切互斥问题
H.程序的顺序执行具有不可再现性
四、填空题
1.进程映象通常包括______、______、______和_______。其中,______含有进程的描述信息和控制信息,是进程映象中最关键的部分.
2.信号量的物理意义是当信号量值大于零时表示_____;当信号量值小于零时,其绝对值为__________。
3.临界资源的概念是________,而临界区是指______________。
4.系统中各进程之间逻辑上的相互制约关系称为________。
5.若一个进程已进入临界区,其他欲进入临界区的进程必须______。
6．将进程的_______链接在一起就形成了进程对列。
7.用P、V操作管理临界区时,任何一个进程在进入临界区之前应调用________操作，退出临界区时应调用____________操作。
8.用信箱实现通信时,应有__________和__________两条基本原语。
9.在多道程序系统中,进程之间存在着的不同制约关系可以划分为两类：_____与_________。___________指进程间具有的一定逻辑关系:__________是指进程间在使用方面的约束关系。
10.程序顺序执行时有顺序性、__________和可再现性的特点。
11.进程是一个__________态概念,而程序是一个__________态概念。
12.在一个单处理机系统中,若有5个用户进程,且假设当前时刻为用户态就绪状态的用户进程最多有________个,最少有________个。
13.操作系统中,对信号量S的P原语操作定义中,使进程进入相应等待队;条件是_____。
14.当处理机空闲时,进程调度程序从_____________中选出一个进程执行。
15.优先图展示了语句间的一种_________关系,而进程图展示的是进程的______关系。
五．简答题
1.在单机操作系统中,进程如何用信箱进行相互之间的通信?
2.什么是原语?原语的主要特点是什么?
3.何谓纯代码?它的主要用途是什么?
4.程序的并行执行将导致运行结果失去封闭性,这对所有的程序都成立吗?
5.什么是线程?进程和线程是什么关系?
6.如何保证进程互斥地访问临界资源?
7.何谓"忙等"?它有什么缺点?
8.为什么进程对临界资源的访问必须互斥?
3.4.2 解析题一．论述题
1.试比较进程与程序的异同
2.什么是临界段?什么是临界段问题?并列举出Dijstra在解决临界段问题时所施加的制约。
3.在生产者一消费者问题中,如果将两个P操作,即P(full)和V(mutex)互换位置,或者P(empty)和P(mutex)互换位置,其后果如何?如果将两个V操作,即V(full)和V(mutex)互换位置,或者V(empty)和V(mutex)互换位置,其后果又如何?
4.在单处理机的分时系统中,分配给进程P的时间片用完后,系统进行切换,结果调度到的仍然是进程P。有可能出现上述情形吗?如果可能请说明理由。
5.有三个进程P1,P2和P3并发工作。进程P1需用资源S3和S1;进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答:
(1)若对资源分配不加限制,会发生什么情况?为什么?
(2)为保证进程正确工作,应采用怎样的资源分配策略?为什么?
6.试比较直接通信方式和间接通信方式。
7.试从调度性、并发性、拥有资源及系统开销方面,对进程和线程进行比较。
8.试说明管程和进程有何异同点?
9.什么叫临界资源?什么是临界段?在解决临界段问题时必须遵循哪些原则?
10.一组除开信号量外不可能共享任何变量的顺序进程可以彼此通信吗?
二，算法题
1.某车站售票厅,最多可容纳20名购票者进入,当售票厅中少于20名购票者时,其厅外的购票者可立即进入,否则,需在外面等待.若把一个购票者看作一个进程,请回答下列问题:
(1)写出用P/V操作管理这些并发进程时信号量的初值以及信号量的各种取值的含义。
(2)根据所定义的信号量,把应执行的P/V操作填人下述方框中,以保证进程能够正确地并发执行。
procedure Pi (i=1,2,…);
begin
|①|
进入售票厅;
购票;
退出售票厅;
|②|
end ;
begin
parbegin
Pi (i=1,2,…)
parend
end.
(3)若欲购票者最多为n个人,试写出信号量取值的可能的变化范围(最大值和最小值).
2.设有两个生产者进程A、B和一个销售者进程C,他们共享一个无限大的仓库,生产者每次循环生产一个产品,然后入库供销售者销售:销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库,也不允许边入库边出库；而且要求生产和销售A产品和B产品的件数都满足以下关系：-n≤A的件数-B的件数≤≤m,其中n、m是正整数。请用信号量机制写出A、B、C三个进程的工作流程。
3.考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷。做-支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料,但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并抽烟,且在做完后给经销商发信号,然后经销商再拿出两种原料放在桌上,如此反复。试设计一个同步算法来描述他们的活动。
4.在测量控制系统中,数据采集任务把所采集的数据送入一单缓冲区:计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。
5．桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。
6.哲学家甲请哲学家乙、丙、丁到某处讨论问题,约定全体到齐后开始讨论:在讨论的间隙四位哲学家进餐,每人进餐时都需使用刀、叉各一把。请用信号量及P、V操作说明这四位哲学家的同步、互斥过程。
7.某数据库有一个写进程,多个读进程,它们之间读、写操作的互斥要求是:写进程正在写该数据库时不能有其他进程读该数据库,也不能有其他进程写该数据库:读进程之间不互斥,可以同时读该数据库。请用信号量及P、V操作描述这一组进程的工作过程。
8.有三个进程PA、PB和PC合作解决文件打印问题:PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录:PB将缓冲区1的内容复制到缓冲区2,每执行一次复制一个记录:PC将缓冲区2的内容打印出来,每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。
9.有一个仓库,可以存放A和B两种产品,但要求:
(1)每次只能存入一种产品(A或B);
(2)-N<A产品数量-B产品数量<M。
其中,N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。
10.进程A1,A2,…An1通过m个缓冲区向进程B1,B2,…Bn2不断地发送消息。发送和接收工作遵循如下规则：
①每个发送进程一次发送一个消息,写入一个缓冲区,缓冲区大小等于消息长度；
②对每一个消息,酌,Bp…,Bn2都须各接收一次,读入各自的数据区内；
③m个缓冲区都满时,发送进程等待;没有可读的消息时,接收进程等待。
试用P、V操作组织正确的发送和接收工作。
11.在南开大学和天津大学之间有一条弯曲的小路,其中从S到T一段路每次只允许一辆自行车通过,但其中有一个小的安全岛M(同时允许两辆自行车停留〉,可供两辆自行车己从两端进入小路情况下错车使用,如图2.14所示。试设计一个算法使来往的自行车均可顺利通过。
3.5 自测练习答案一．判断题：
1.2.3.4.5.6.7.8.9.10.
二．单项选择题
1.C 2.B 3.B 4.D 5.A 6.B 7.B 8.B 9.D 10.A
11.C 12.A 13.B 14.C 15.B 16.B 17.D 18.B 19.A 20.C
三．多项选择题
1.A C D E F 2,A B D 3,A C E 4.A B 5.A C D 6.E F 7.C
8.C D F G
四．填空题
1,用户程序 用户数据 系统栈和进程控制块 进程控制块
2.可用资源的数目 因请求该资源而被阻塞的进程数目
3,一次仅允许一个进程访问的资源 程序中访问临界资源的那段程序代码
4.进程同步
5．等待 6.PCB 7.P V 8.发送 接收 9.同步 互斥 同步 互斥
10.封闭性 11.动 静 12.4 O 13,S < O 14.就绪队列中 15,优先 家族五．简答题
1.答.在单机操作系统中,可以使用信箱实现两个进程之间的通信。
在操作系统中,一个进程要与另一个进程进行通信,接收消息的进程必须为自己创建一个信箱。
进程调用send原语发送信件前必须组织好信件，然后调用send原语,并在调用时给出参数:信箱名和信件内容或信件存放起始地址。同样,接收进程也要调用receive原语,给出参数:信箱名和信件取出后的存放地址。通信原语的形式是:
send(boxname,msg)
receive (boxname,msg)
2.答：原语是指由若干条机器指令构成的,并用以完成特定功能的一段程序。这段程序在执行期间是不可分割的。其主要特点是不可分割性。
3.答：纯代码是能够被多个进程共享的程序段,代码不因程序的执行而改变,又称为重入码。纯代码的主要作用就是可被多个程序共享。并不是所有的程序段都是可被多个进程共享的,非可重入码被多个进程共享时可能出现错误。
4.答：并不是所有程序的并行执行都会导致运行结果失去封闭性。例如,当程序中都使用内部变量,不可能被外部程序访问时,程序的运行不会受到外部环境的影响。
5.答,线程可定义为进程内的一个执行单位,或者定义为进程内的一个可调度的实体。
在具有多线程机制的操作系统中,处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程,而且至少有一个可执行线程。
进程和线程的关系是:
①线程是进程的一个组成部分;
②进程的多线程都在进程的地址空间活动z
③资源是分给进程的,而不是分给线程的。线程在执行中需要资源时,系统从进程的资源配额中扣除并分配给它;
④处理机调度的基本单位是线程,线程之间竞争处理机,真正在处理机上运行的是线程;
⑤线程在执行过程中,需要同步。
6.答:为了互斥地访问临界资源,系统必须保证进程互斥地进入临界区。为此,必须在临界区前增加一段称作进入区的代码,以检查是否有其他进程已进入临界区使用临界资源,若有,则进程必须等待:否则,允许进程进入临界区,同时设置标志表示有进程正在临界区内。同样,在临界区后必须增加一段称作退出区的代码,用于将已有进程进入临界区访问临界资源的标志改为无进程进入临界区使用临界资源。进入区、退出区具体可用多种同步机制实现,如锁、信号量机制等。
7.答:所谓"忙等"是指"不让权"的等待,即进程因某事件的发生而无法继续执行时,它仍占有CPU,并通过不断地执行循环测试指令来等待该事件的完成。
"忙等"的主要缺点是浪费CPU的时间,另外,它还可能引起预料不到的后果。考虑某个采取高优先权优先调度原则的系统,目前有两个进程A和B共享某个临界资源,A的优先权较高,B的优先权较低,且B己处于临界区内,而A欲进入自己的临界区,则A、B都不可能继续向前推进,陷入"死等"状态。
8.答:临界资源本身的特性决定了它们只能被诸进程互斥地访问,如果并发执行的多个进程同时访问临界资源,将会造成系统的混乱或程序执行结果的不确定性,这样,用户得到的便可能是不希望得到的或者是不正确的处理结果。如果多个用户同时使用同一台打印机,则将使他们的输出结果交织在一起,而难于区分:又如两个用户使用程序段:
mov ax,(counter)
inc ax
mov (counter),ax
对初值为0的共享变量counter进行计数(加1)操作,则最终counter的值可能是正确的结果2,也可能是错误的结果1,即计算结果出现了不确定性。
（一）论述题
1.答:进程和程序是紧密相关而又完全不同的两个概念。
(1)每个进程实体中包含了程序段和数据段这两个部分,因此说进程与程序是紧密相关的。但从结构上看,进程实体中除了程序段和数据段外,还必须包含一个数据结构,即进程控制块PCB。
(2)进程是程序的一次执行过程,因此是动态的:动态性还表现在进程由创建而产生、由调度而执行、由撤消而消亡,即它具有二定的生命周期。而程序则只是一组指令的有序集合,并可永久地存放在某种介质上,其本身不具有运动的含义,因此是静态的。
(3)多个进程实体可同时存放在内存中并发地执行；其实这正是引入进程的目的。而程序(在没有为它创建进程时)的并发执行具有不可再现性,因此程序不能正确地并发执行。
（4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序(在没有为它创建进程时)不具有PCB,所以它是不可能在多道程序环境下独立运行的。
（5）进程与程序不一一对应。同一个程序的多次运行,将形成多个不同的进程:同一个程序的一次执行也可以产生多个进程(如UNIX中通过fork调用):而一个进程也可以执行多个程序(如UNIX中通过exec调用)。
2.答：临界段就是一次仅允许一个进程执行的程序段.临界段问题是指设计一种算法,以允许一次至多只有一个进程进入临界段且不产生死锁。Dijkstra在解决临界段问题时所施加的制约有:
(1)进程的同时执行等价于它们按一种不知道的次序顺序执行；
(2)进程的执行速度是彼此无关的；
(3)位于非临界段的进程不可能防止其他进程进入临界段；
(4)选择并允许一个进程进入临界段的决策不可能被无限期地推迟。
3.答:在生产者一消费者问题中,如果将两个P操作,即P(full)和P(mutex)互换位置,或者P(empty)和P(mutex)互换位置,都可能引起死锁。考虑系统中缓冲区全满前时,若一生产者进程先执行了P(mutex)操作并获得成功,当再执行P(empty)操作时,它将因失败而进入阻塞状态,它期待消费者执行V(empty)来唤醒自己,在此之前,它不可能执行V(mutex)操作,从而使企图通过P(mutex)进入自己的临界区的其他生产者和所有的消费者进程全部进入阻塞状态,从而引起系统死锁。类似地,消费者进程若先执行P(mutex),后执行P(full),同样可能造成死锁。
V(full)和V(mutex)互换位置,或者V(empty)和V(mutex)互换位置,则不会引起死锁,其影响只是使临界资源的释放略为推迟一些。
4.答:有可能出现上述情况。例如,若在进程P时间片用完后,被迫回到就绪队列时,就绪队列为空,这样进程P就是就绪队列中惟一的一个进程,于是调度程序选中的进程必是进程P；又如在按优先级调度的系统中,就绪队列按进程优先级排列,在进程P时间片用完之后回到就绪队列时,若其优先级高于当前就绪队列中的其他进程程,则它将排在就绪队列之首,从而再次被调度程序选中并投入运行。
5.答：(1)可能会发生死锁现象。例如,进程P1,P2和P3分别获得资源S3,S1和S2后再继续申请资源时都要等待,这是循环等待。
(2)可有几种答案:
①采用静态分配,由于执行前已获得所需的全部资源,故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。
②采用按序分配,不会出现循环等待资源现象。
③采用银行家算法,在分配时,保证了系统处于安全状态。
6.答:可从以下几个方面来比较直接通信方式和间接通信方式:
(1)发送和接收原语。直接通信原语通常为send(receiver,mssage)、receive(sender,
message);间接通信原语通常为send(mailbox,message)、receive(mailbox,message),而且它还需要提供布关信箱创建和撤消的原语。
(2)提供对方的标识符。直接通信要求发送双方显式地提供对方的标识符,对接收进程,量如果允许它同时接收多个进程发来的消息,则接收原语中的发送进程标识符可以是通信完成后返回的值:间接通信则不要求它们显式地提供对方的标识符,而只需提供信箱标识。
(3)通信链路。直接通信时,进程只需提供对方的标识符便可进行通信,在收发双方之间建立通信链路由系统自动完成,并且在收发双方之间有且仅有一条遁信链路;间接通信时,仅当一对进程共享某个信箱时,它们之间才有通信链路,顶且一条链路可对应多个进程,每对进程间也可以有多条链路。
(4)实时性。直接通信通常只能提供实时通注1间接通信方式'则既可实现实时通信,也可实现非实时通信。
7.答:进程和线程之间在调度性、并发性、拥有资源及系统开销方面的比较如下:
(1)调度性：在传统的操作系统中,拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的os中,则把线程作为调度和分派的基本单位,而把进程作为资源拥有的基本单位。
(2)并发性：在引入线程的os中,不仅进程间可以并发执行,而且在一个进程的多个线程间也可以并发执行,因而它比传统的os具有更好的并发性。
(3)拥有资源：在这两种os中,拥有资源的基本单位都是进程。线程除了一点在运行中必不可少的资源(如线程控制块、程序计数器、一组寄存器值和堆核)外,本身基本不拥有系统资源,但它可访问其隶属进程的资源。
(4)开销：由于创建或撤消进程时,系统都要为之分配和回收资源,如内存空间和I/O设备等:进程切换时所要保存和设置的现场信息也要明显地多于线程,因此,os在创建、撤消和切换进程时所付出的开销将明显地大于线程。另外,由于隶属于同一个进程的多个线程共享同一地址空间和该进程的所有己打开文件,从而使它们之间的同步和通信的实现也比进程更方便。
8.解:管程和进程的异同点是:
(1)二者都定义了数据结构,进程定义的是私有数据结构PCB,管程定义的是公共数据结构,如消息队列；
(2)二者都在各自的数据结构上进行有意义的操作。进程是由顺序程序执行有关操作,管程主要是同步操作和初启操作；
(3)二者设置的目的不同,进程是为了更好地刻画可实现系统的并发性而设置的,管程是为了解决进程的公共变量,为了解决共享资源的互斥使用问题而设置的；
(4)进程通过调用管程中的过程对共享变量实行操作,此时该过程就如通常的子程序一样被调用而处于被动工作方式,因此称管程为被动成分.与此相对应的进程则处于主动工作方式而被称为主动成分；
(5)由于进程是主动成分,故进程之间能被并发执行,然而管程是被动成分,管程和调用它的进程不能并发；
(6)进程可由"创建"而诞生,由"撤消"而消亡,有生命期,管程是操作系统中固有成分,无需进程创建,也不能为进程所撤消,只能被进程调用。
9.解:在计算机系统中,同时有许多进程,它们共享着各种资源,然而,有许多资源一次却仅能为一个进程所使用.把一次仅允许一个进程使用的资源称为临界资源.例如,物理设备属于临界资源,如打印机、磁带机、输入机等.除了物理设备外,还有很多变量、数据、表格、队列等也都是由若干进程所共享的资源。进程访问共享临界资源的一段程序,叫做临界段.为了防止两个进程同时进入临界段内,必须互斥,即保证每次至多有一个进程进入临界段,通常应遵循下列原则:
(1)当有若干进程欲进入其临界段时,在有限时间内有一进程进入.换言之,它们不应互相阻塞而致使彼此都不能进入临界段；
(2)每次至多有一个进程处于临界段；
(3)进程仅在临界段内逗留有限的时间。
10.解:不能。一进程只可能执行P或V操作,V操作不影响执行它的进程,因此,进程不能从V操作得到任何信息。若一个P操作成功,执行该P操作的进程无法得知它是立即成功还是延迟一段时间后才成功。若该P操作从未成功(因无对应的V操作),那么,执行它的进程就挂起而且不可能做任何事。
（二）、算法题
1,答：(1)定义一个信号量S,其初值为20,s取值的含义如下:
S 〉O S的值表示可继续进入售票厅的人数
S =0 表示售票厅中已有20名顾客(购票者)
S <O |S|的值为等待进入售票厅的人数
(2)①P(S) ②V(S)
(3)S的最大值为20,S的最小值为20-n.
2.分析：本题中存在着以下的同步和互斥关系:①生产者A、B和消费者C之间,不能同时将产品入库和出库,故仓库是一个临界资源.②两个生产者之间必须进行同步,当生产的A、B产品的件数之差大于等于m时,生产者A必须等待;小于等于-n时,生产者B必须等待。③生产者和销售者之间也必须进行同步,只有当生产者生产出产品并入库后,销售者才能进行销售;而且由于销售的产品件数必须满足关系:-n≤A的件数-B的件数≤≤m,因此当销售的A、B产品的件数之差大于等于m而仓库中已无B产品时,或者销售的A、B产品的件数之差小于等于-n而仓库中已元A产品时,销售者C也都必须等待。
答:为了互斥地入库和出库,需为仓库设置一初值为1的互斥信号量mutex;为了使生产的产品件数满足:-n≤A的件数-B的件数≤m,需设置两个同步的信号量,其中SAB表示当前允许A生产的产品数量,其初值为m; SBA表示当前允许B生产的产品数量,其初值为n;另外,还需设置一个整数difference表示所销售的A、B产品的数量差,而为了同步生产者和销售者并使销售的A、B产品的件数满足关系:-n≤A的件数-B的件数≤m,还需设置三个资源信号量,其中S对应于仓库中总的产品量,SA对应于仓库中的A产品量,SB对应于仓库中的B产品量,它们的初值都为0。具体的同步算法如下:
Var difference:integer:=0:
SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,O,0,0,1;
begin
parbegin
process A:begin
repeat
P(SAB);
produce a product A;
V(SBA);
P(mutex);
add the product A to tile storehouse:
V(mutex);
V(SA);
V(S);
until false;
end
process B:begin
repeat
P(SBA);
produce a product B ;
V(SAB);
P(mutex);
add the product B to the storehouse;
V(mutex);
V(SB);
V(S);
until false;
end
process C:begin
repeat
P(S);
if difference〈=-n then begin
P(SA);
P(mutex);
take a product A from storehouse;
Vl(mutex);
difference:=difference+1;
end
else if difrerence 〉=m then begin
P(SB);
P(mutex);
take a product B from storehouse;
V(mutex);
difference:=difference-1;
end
else begin
P(mutex);
take a product A or B from storehouse;
V(mutex);
if(product_type=A) then begin /*取的是A产品*/
P(SA);
difference:=difference+1;
end
else begin /*取的是B产品*/
P(SB);
difference:=difference-1;
end
sell the product;
until false;
end
parend
end
3.答：共享数据结构是:
var a:array[0..2] of semaphore; {初值=0}
agent:semaphore; {初值=1}
关于经销商的代码段:
repeat
Set i,j to a value between O and 2;
P(agent);
V(a[i]);
V(a[j]);
Until false;
分别用整型量r和S表示每个抽烟者进程所需要的两种原料(r和S在0~2间取值),那么,抽烟者进程的代码段为:
repeat
P(a[r]);
P(a[s]);
"smoke"
V(agent);
until false;
4.分析：在本题中采集任务与计算任务共用一个单缓冲区。当采集任务采集到一个数据后,只有当缓冲区为空时才能将数据送入缓冲区中存放,否则应等待缓冲区腾空;当缓冲区中有数据时,计算任务才能从缓冲区中取出数据进行计算,否则也应等待。
本题实际上是一个生产者-消费者问题。将生产者-消费者问题抽象出来,以另外一种形式描述是一种常见的试题形式。只要对生产者-消费者问题有了深入的理解,就不难解决此类试题。
解:在本题中,应设置两个信号量S五Se,信号量Sf表示缓冲区中是否有可供打印的计算结果,其初值为0:信号量Se用于表示缓冲区有无空位置存放新的信息,其初值为1。
本题的同步描述如下:
int Se=1;
int Sf=0;
main()
{
parbegin
get ():
compute(〉:
parend
}
get ( )
{
while (采集工作未完成)
{
采集一个数据:
p(Se);
将数据送入缓冲区中;
v(Sf);
}
}
compute()
{
while (计算工作未完成)
{
p(Sf);
从缓冲区中取出数据;
v(Se);
进行数据计算;
}
}
5.分析:在本题中,爸爸、儿子、女儿共用一个盘子,且盘中一次只能放一个水果。当盘子为空时,爸爸可将一个水果放入采盘中。若放入果盘中的是桔子,则允许儿子吃,女儿必须等待;若放入果盘中的是苹果,则允许女儿吃,儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里,生产者放入缓冲区的产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。
解:在本题中,应设置三个信号量S、So、Sa,信号量S表示盘子是否为空,其初值为1；信号量So表示盘中是否有桔子,其初值为0；信号量Sa表示盘中是否有苹果,其初为0。同步描述如下：
int s=1;
int Sa=0;
int S0=0;
main( )
cobegin
father( );
son ( );
dauduer( );
coend
}
father ( )
{
while (1)
{
p(S);
将水果放入盘中:
if(放入的是桔子〉v(So);
else v(Sa);
}
}
son ( )
{
while(1)
{
p(So);
从盘中取出桔子;
v(S);
吃桔子；
}
}
daughter( )
{
while(1)
{
p(Sa);
从盘中取出苹果:
v(S);
吃苹果;
}
}
6.分析:在本题中这四位哲学家在讨论问题期间的生活方式为交替地进行讨论和进餐。由于刀、又资源均为2,而哲学家有四位,这就会出现资源竞争,为此应对他们的进餐进行同步控制。在本题解法中规定:所有哲学家先申请使用刀,申请到刀后再申请使用叉,刀、又都拿到后才能进餐.本题是标准的哲学家进餐问题。只是在哲学家人数、进餐用具方面与经典哲学家进餐问题略有不同。
解:在本题中,应设置四个信号量forkl、fork2、knife1、knife2,其初值均为1,分别表示资源叉1、叉2、刀1、刀2是否可用。同步描述如下:
int fork1=1;
int fork2=1;
int knifel=1;
int lq1ife2=1;
main( )
{
cobegin
Pa( ); /*分别用进程Pa、pb、Pc、Pd代表哲学家甲、乙、丙、丁的活动*/
Pb( );
Pc( );
Pd( );
Coend
}
Pa( )
{
while(1)
{
p(knife1);
p(fork1);
进餐;
v(knife1);
v(forkl);
讨论问题;
}
}
Pb ( )
{
while(1)
{
p(knife2);
p(fork1);
进餐;
v(knife2);
v〈forkl);
讨论问题;
}
}
Pc( )
{
while(1)
{
p(knife2);
p(fork2);
进餐;
v(knife2);
v(fork2);
讨论问题;
}
}
Pd( )
{
while(1)
{
p(knifel);
p(fork2);
进餐;
v(knife1);
v(fork2);
讨论问题;
}
}
7.答:在本题中,允许读进程同时读数据库,但写进程正在写数据库时不允许其他进程读数据库,也不允许其他进程写该数据库。为了解决读、写进程之间的同步,应设置两个信号量和一个共享变量;读互斥信号量mutex,用于使读进程互斥地访问共享变量count,其初值为1:写互斥信号量wmutex,用于实现写进程与读进程的互斥及写进程与写进程的互斥,其初值为1:共享变量count,用于记录当前正在读数据库的读进程数目,初值为0。其工作过程如下:
int mutex=1;
int wmutex=1;`
int count=0;
main()
{
cobegin
reader( );
writer( );
coend
}
reader( )
{
while(1)
{
p(mutex);
if(count==O〉p(wmutex);:/*当第一个读进程读数据库时,阻止写进程写*/
count ++;
v(mutex);
读数据库;
p(rmutex)
count - -;
if(count=0) v(wmutex); /*当最后一个读进程读完数据库时,允许写进程写*/
v(rmutex);
}
}
writer( )
{
while(1)
{
p(wmutex);
写数据库;
v(wmutex);
}
}
在本题中,要注意对信号量rmutex意义的理解。rmutex是一个互斥信号量,用于使读进程互斥地访问共享变量count。该信号量并不表示读进程的数目,表示读进程数目的是共享变量count。当一个读进程要读数据库时,应将读进程计数count增加1:如果此前(count加1以前)数据库中无读进程,还应对写互斥信号量wmutex做p操作,这样,若数据库中无写进程,则通过p操作阻止写进程写,若数据库中有写进程,则通过p操作让读进程等待。同理,当一个读进程完成读数据库操作时,应将读进程计数count减少1;如果此时(count减1以后〉数据库中已无读进程,还应对写互斥信号量wmutex做v操作,以允许写进程写。
8.答:在本题中,进程PA、PB、PC之间的关系为:PA与PB共用一个单缓冲区,而PB又与PC共用一个单缓冲区,其合作方式可用图2.12表示。当缓冲区1为空时,进程PA可将一个记录读入其中;若缓冲区1中有数据且缓冲区2为空,则进程PB可将记录从缓冲区1复制到缓冲区2中;若缓冲区2中有数据,则进程PC可以打印记录。在其他条件下,相应进程必须等待。事实上,这是一个生产者·消费者问题。
为遵循这一同步规则。应设置四个信号量empty1、empty2、full1,full2,信号量emptyl
及empty2分别表示缓冲区1及缓冲区2是否为空,其初值为1;信号量full1及full2分别表示缓冲区1及缓冲区2是否有记录可供处理,其初值为0。其同步描述如下:
int empty1=1;
int empty2=1;
int full1=0;
int full2=0;
main( )
{
cobegin
PA( );
PB( );
PC( );
Coend
}
PA( )
{
while(1)
{
从磁盘读一个记录:
p(empty1);
将记录存入缓冲区1
V(full);
}
}
PB( )
{
while(1)
p(full);
从缓冲区1中取出记录:
v(emptyl);
p(empty2);
将记录存入缓冲区2:
V(full2);
}
}
PC( )
{
while(1)
{
p(full2);
从缓冲区2中取出记录;
v(empty2);
打印记录;
本题也是一个典型的生产者·消费者问题。其中的难点在于PB既是一个生产者又是一个消费者。
}
9.分析：本题给出的第一个条件是1!各界资源的访问控制,可用一个互斥信号量解决该问题。第二个条件可以分解为:
-N<A产品数量一B产品数量
A产品数量一B产品数量<M
也就是说,A产品的数量不能比B产品的数量少N个以上,A产品的数量不能比B产品的数量多M个以上。
解:在本题中,我们可以设置两个信号量来控制A、B产品的存放数量,sa表示当前允许A产品比B产品多入库的数量,即在当前库存量和B产品不入库的情况下,还可以允许sa个A产品入库:sb表示当前允许B产品比A产品多入库的数量,即在当前库存量和A产品不入库的情况下,还可以允许sb个B产品入库。初始时,sa为M-1,sb为N一1。当往库中存放入一个A产品时,则允许存入B产品的数量也增加1:当往库中存放入一个B产品时,则允许存入A产品的数量也增加1。
产品A、B的入库过程描述如下:
int mutex=1; /*互斥信号量*/
int sa=M-1;
int sb=N-1;
main( )
{
while(1)
{
取一个产品;
if (取的是A产品)
{
p(sa);
p(mutex);
将产品入库;
v(mutex);
v(sb);
}
else /*取的产品是B*/
{
p(sb);
p(mutex);
将产品入库;
v(mutex);
v(pa);
}
}
}
从本题的解法可以看出,当有比较复杂条件出现时,可以把复杂条件分解成一组简单,这样就能很容易地写出对应的程序流程了。
10.分析：本题是生产者-消费者问题的一个变形,一组生产者A1,A2,…An1和一组消费者B1,B2,…,Bn2共用m个缓冲区,每个缓冲区只要写一次,但需要读n2次.因此,我们可以把这一组缓冲区看成n2组缓冲区,每个发送者需要同时写n2组缓冲区中相应的n2个缓冲区,而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。
解：在本题中,应设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组empty[n2]和full[n2]描述n2组缓冲区的使用情况。mutex的初值为1;数组empty中元素初值为m；数组full中的元素初值为0。其同步关系描述如下:
int mutex,empty[n2],full[n2];
int 1;
mutex=1;
for(i=O;i<=n2-1;i++)
{
empty[i]=m;
full[i]=0;
}
main( )
{
cobegin
Al( );
A2( );
An1( );
B1( );
B2( );
Bn2( );
Coend
}
send( ) /*发送消息*/
{
int i;
for (i=O;i<=n2-1; i++)
p(empty[i]);
p(mutex);
将消息放入缓冲区;
v(mutex);
for(i=0;i<=n2-1;i++)
v(full[i]);
}
receive (i) /*进程Bi接收消息*/
{
p(full[i]);
p(mutex);
将消息从缓冲区取出;
v(mutex);
v(empty[i]);
}
Ai( ) /*因发送进程A1,A2,…,An1的程序类似,这里只给出进程Ai的描述.*/
{
while(1)
{
send( );
}
}
Bi() /*因接收进程B1,B2,…,Bn2的程序类似,这里只给出进程Bi的描述.*/
{
while(1)
{
receive(i);
}
}
11.分析：在本题中,需要控制路段T到L,路段S到K及安全岛M的使用。路段T到L及路段S到K同时只允许一辆自行车通过,而安全岛M允许两辆自行车使用,因此可以用三个信号量来管理它们.另一方面,同一方向上的自行车最多只能有一辆通过这段路(两个方向上有两辆),因此还应该用两个信号量来控制.
解:在本题中,应设置5个信号量ST,TS,K,L,M,信号量ST表示是否允许自行车从南开大学去天津大学,其初值为1;信号量TS表示是否允许自行车从天津大学去南开大学,其初值为1:信号量K表示是否允许自行车通过路段S到K,其初值为1;信号量L表示是否允许自行车通过路段T到L,其初值为1;信号量M表示安全岛上还可停放自行车的数目,其初值为2。其控制过程描述如下:
int ST=1;
int TS=1;
int k=1;
int L=1;
int M=2;
totian( ) /*从南开大学去天津大学*/
{
P(ST);
P(K);
从s走到K;
P(M);
进入安全岛;
V(K);
P(L);
从L走到T;
V(M);
V(L);
V(ST);
}
tonan( ) /*从天津大学去南开大学*/
{
P(TS);
P(L);
从T走到L;
P(M);
进入安全岛;
V(L);
P(K);
从K走到S;
V(M);
V(K);
V(TS);
}
3.1 内容辅导
3.1.1 进程的基本概念
1.程序的顺序执行一个程序通常由若干个程序段所组成,它们必须按照某种先后次序来执行,仅当前一个操作执行完后才能执行后继操作,这类计算过程就是程序的顺序执行过程。程序顺序执行时有如下特征:
（1）顺序性：处理机的操作严格按照程序所规定的顺序执行,即每一操作必须在下一操作开始之前结束。
（2）封闭性,程序运行时独占系统的各种资源,故这些资源的状态(除初始状态外)只有本程序才能改变。程序一旦开始运行,其执行结果不受外界因素影响。
（3）可再现性：只要程序执行时的初始条件和执行环境相同,当程序重复执行时,都将获得相同的结果。
2.程序的并发执行所谓程序的并发执行是指若干个程序〈或程序段〉同时在系统中运行,这些程序(或程序段)的执行在时间上是重叠的,一个程序(或程序段)的执行尚未结束,另一个程序,（或程序段）的执行已经开始。
程序的并发执行虽然提高了系统吞吐量,但也产生了下述一些与顺序执行不同的新特征：
（1） 制约性：程序在并发执行时,由于它们共享资源或为完成同一项任务而相互合作,致使并发程序之间形成了相互制约关系。制约关系有两种：
①直接制约关系=进程一进程。
②间接制约关系z进程一资源一进程。
（2）失去封闭性：程序在并发执行时,多个程序共享系统中的各种资源,因而这些资源的状态将由多个程序来改变,致使程序的运行失去封闭性。
（3）不可再现性：程序并发执行时,由于失去了封闭性,也将导致失去其可再现性。
3,进程的定义及特征进程是操作系统中最基本、最重要的概念,但直至目前还没有一个统一的定义,这里给出几种比较容易理解又能反映进程实质的定义:
(1)进程是程序的一次执行。
(2)进程是可以和别的计算并发执行的计算。
(3)进程是程序在一个数据集合上运行的过程,是系统进行资源分配和调度的一个独立单位。
(4)进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。
以上进程的定义,尽管各有侧重,但它们在本质上是相同的。
进程具有以下几个基本特征:
（1）动态性：进程是程序的一次执行过程,因而是动态的。动态特性还表现在它因创建而产生,由调度而执行,因得不到资源而暂停执行,最后由撤消而消亡。
（2）并发性：引入进程的目的就是为了使程序能与其他程序并发执行,以提高资源利用率。
（3）独立性：进程是一个能独立运行的基本单位,也是系统进行资源分配和调度的独立单位。
（4）异步性：进程以各自独立的、不可预知的速度向前推进。
（5）结构特征：为了描述和记录进程的运动变化过程,并使之能正确运行,应为每个进程配置一个进程控制块。这样,从结构上看,每个进程都由程序段、数据段和进程控制块三部分组成。
4,进程状态及其变化进程执行时的间断性,决定了进程可能具有多种状态。事实上,运行中的进程至少具有以下三种基本状态。
（1） 就绪状态 进程已获得除处理机以外的所有资源,一旦分到了处理机就可以立即执行,这时进程所处的状态为就绪状态。
（2）执行状态 执行状态又称运行状态。当一个进程获得必要的资源.并占有处理机,即在处理机上运行,此时进程所处的状态为执行状态。
（3）阻塞状态 阻塞状态又称等待状态。正在执行的进程,由于发生某事件而暂时无法执行下去(如等待输入/输出完成〉,此时进程所处的状态为阻塞状态。
进程并非固定处于某一状态,它随着自身的推进和外界条件的变化而发生变化。
5.进程的表示进程通常有三部分组成：程序数据集合和进程控制块。
（1）程序,描述了进程所要完成的功能。
（2）数据集合：程序执行时所需要的数据和工作区。
（3）进程控制块：为了描述和控制进程的运行,系统为每个进程定义了一个数据结构—进程控制块(PCB)。所谓系统创建一个进程,就是由系统为某个程序(包含数据段)设置一个PCB,用于对该进程进行控制和管理。进程执行完成时,由系统收回其PCB,该进程便消亡了。系统将根据PCB而感知进程的存在,故PCB是进程存在的惟一标志。
一般来说,根据操作系统的要求不同,进程PCB所包含的内容多少会有些不同,但通常包括下面所列的内容:进程标识符,进程当前状态,进程队列指针,程序开始地址,迸程优先级,CPU现场保护区,通信信息,家族联系,占有资源清单等。
在一个系统中,通常存在许多进程,为了对它们进行有效管理,应该用适当方法将PCB组织起来。目前常用链表或表格将PCB组织起来。
3.1.2进程控制进程控制的职责是对系统中的全部进程实施有效的管理。其功能包括进程的创建、进程的撤消、进程的阻塞与唤醒等。这些功能一般是由操作系统的内核来实现的。
操作系统的内核是基于硬件的第一次软件扩充。在现代操作系统设计中,往往把一些与硬件紧密相关的模块或运行频率较高的模块以及为许多模块所公用的一些基本操作安排在靠近硬件的软件层次中,并使它们常驻内存,以提高操作系统的运行效率。
进程控制功能是通过执行各种原语来实现的。所谓原语是由若干条机器指令构成的,用于完成某一特定功能的一段程序。原语在执行期间不可分割,所以原语操作具有原子性。
为了防止操作系统及关键数据如PCB等受到用户程序有意或无意的破坏,通常将处理机的执行状态分成两种:核心态与用户态。
核心态又称管态：是操作系统管理程序执行时机器所处的状态。它具有较高的特权,能执行一切指令,访问所有的寄存器和存储区。
用户态又称目态：是用户程序执行时机器所处的状态。这是具有较低特权的执行状态,它只能执行规定的指令,访问指定的寄存器和存储区。
1.进程创建进程创建是由创建原语实现的。当需要进程时,就可以建立一个新进程。被创建的进程称为子进程,建立进程的进程称为父进程。
创建原语的主要功能是为被创建进程形成一个PCB,并填入相应的初始值。其主要操作过程是先向系统申请一个空闲PCB结构,再根据父进程所提供的参数将子进程的PCB初始化,并将此PCB插入就绪队列,最后返回一个进程的标识号。
2,进程撤消进程撤消是由撤消原语实现的。一个进程在完成其任务后,应予以撤消,以便及时释放它所占用的各类资源。撤消原语可采用两种撤消策略:一种策略是只撤消一个具有指定标识符的进程,另一种策略是撤消指定进程及其子孙进程。
撤消原语的主要功能是收回被撤消进程占用的所有资源,并撤消它的PCB。其主要操作过程是先从PCB集合中找到被撤消进程的PCB,若被撤消进程正处于运行状态,则应立即停止该进程的执行,设置重新调度标志,以便进程撤消后将处理机分给其他进程。对后一种撤消策略,若被撤消进程有子孙进程,还应将该进程的子孙进程予以撤消。对于被撤消进程所占有的资源,或者归还给父进程,或者归还给系统。最后撤消它的PCB。
3.进程阻塞与唤醒阻塞原语的作用是将进程由执行状态转为阻塞状态,而唤醒原语的作用则是将进程由阻塞状态变为就绪状态。
当一个进程期待的某一事件尚未出现时,该进程调用阻塞原语将自己阻塞起来。阻塞原语在阻塞一个进程时,由于该进程正处于执行状态,故应先中断处理机和保存该进程的CPU现场,然后将该进程插入到等待该事件的等待队列中。再从就绪队列中选择一个新的进程投入运行。
对处于阻塞状态的进程,当该进程期待的事件出现时,由发现者进程调用唤醒原语将阻塞的进程唤醒,使其进入就绪状态。
应当注意,一个进程由执行状态转变为阻塞状态,是这个进程自己调用阻塞原语去完成的,而进程由阻塞状态到就绪状态,是另一个发现者进程调用唤醒原语实现的,一般这个发现者进程与被唤醒进程是合作的并发进程。
3.1.3 进程同步多道程序系统中进程是并发执行的,这些进程之间存在着不同的相互制约关系,为了协调进程之间的相互制约关系,就需要实现进程的同步。互斥是同步的一种特殊情况。
1.进程同步的基本概念
（1）临界资源和临界区：系统中的多个进程可以共享系统中的各种资源,然而其中许多资源一次只能为一个进程所使用。我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机、绘图机等。除物理设备外,还有许多变量、数据等都可由若干进程所共享,它们也属于临界资源。在每个进程中,访问临界资源的那段程序称为临界区。
(2)同步：一个进程到达了某些点后,除非另一进程已完成了某些操作,否则就不得不停下来等待这些操作的结束,这就是进程间的同步。
(3)互斥:两个或两个以上进程,由于不能同时使用同一临界资源,只能一个进程使用完了,另一个进程才能使用,这种现象称为进程互斥。
为禁止两个进程同时进入临界区,可采用软件解决方法或一个同步机构来协调它们。但是,不论是软件算法或同步机构都应遵循下述准则,①空闲让进；②忙则等待；③有限等待；④让权等待。
2.信号量和P、V操作一个信号量的建立必须经过说明,即应该准确说明s的意义和初值。每个信号量都有相应的一个队列,在建立信号量时,队列为空。P、V操作为两条原语,信号量的值仅能由P、V操作原语来改变。
P、V操作的定义如下：
P(s),s=s-1
若S>=0,则进程继续运行。
若S<0,则该进程被阻塞,并将它插入该信号量的等待队列中。
V操作：S =S+1
若s >0,则进程继续执行。
若S<=0,则从信号量等待队列中移出第一个进程,使其变为就绪状态,然后再返回原进程继续执行。
3.信号量的应用利用信号量可以解决进程间的同步和互斥问题，实现进程间的互斥和同步模型如下：
（1）互斥模型进程P1 进程P2
P(S) P(S)
CS1 CS2
V(s) v(s)
其中，信号量的初值：S=1;CS1,CS2分别是进程P1和P2的临界区。
（2）同步模型
进程P1 进程P2
L1:P(S) L2,V(S)
其中，信号量的初值：S=0。
（3）用P、V操作描述前趋关系若干进程为了完成一个共同任务而并发执行。然而,这些并发进程之间根据逻辑上的需要,有的操作可以没有时间上的先后次序,即不论谁先做,最后的计算结果都是正确的。但有的操作有一定的先后次序,也就是说它们必须遵循一定的同步规则,只有这样,并发执行的最后结果才是正确的。我们可以用本章前面介绍的前趋图来描述进程在执行次序上的先后关系。
（4）生产者·消费者问题生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品,它们共享一个有界缓冲区,生产者向其中投放产品,消费者从中取得产品。生产者消费者问题是许多相互合作进程的一种抽象。例如,在输入时,输入进程是生产者,计算进程是消费者;在输出时,计算进程是生产者,打印进程是消费者。因此,该问题具有很大实用价值。
我们把一个长度为n的有界缓冲区(n〉O)与一群生产者进程P1、P2、…、Pm和一群消费者进程CI、C2、…、CK联系起来。假定这些生产者和消费者是互相等效的。只要缓冲区未满,生产者就可以把产品送入缓冲区,类似地,只要缓冲区未空,消费者便可以从缓冲区中取走物品并消耗它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品,也禁止消费者从空的缓冲区中提取物品。
为解决这一类生产者-消费者问题,应该设置两个同步信号量,一个说明空缓冲单元的数目,用empty表示,其初值为有界缓冲区的大小n,另一个说明满缓冲单元的数目,用full表示,其初值为0。在本例中有P1、P2、…、Pm个生产者和C1、C2、…、CK个消费者,它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源,必须互斥使用,所以,另外还需设置一个互斥信号量mutex,其初值为1。生产者.消费者问题的同步描述如下:
int full=0; /*申满缓冲单元的数目*/
int empty=n; /*空缓冲单元的数目*/
int mutex=1; /*对有界缓冲区进行操作的互斥信号量*/
main( )
{
Parbegin
producer i( ); /*i=1,2,…,m:j=1,2,…,k*/
consumer j( );
parend
}
produceri( ) /*i=1,2,…,m*/
{
while (生产未完成)
{
生产一个产品;
p(empty);
p(mutex);
送一个产品到有界缓冲区;
V(mutex);
V(full);
}
}
consumerj( ) /*j=1,2,…,k*/
{
while (还要继续消费)
p(full);
p(mutex);
从有界缓冲区中取产品;
V〈mutex〉;
v(empty);
消费一个产品;
}
}
(5)读者与写者问题在计算机系统中,有些文件是可共享的,当若干个并发进程都要访问某个共享文件时,应区分是读还是写(修改)文件。显然可允许多个进程同时读文件但不允许在进程读文件时让另一进程去修改文件,或者有进程在修改文件时让另一进程去读,否则会造成读出的文件内容不正确。尤其是绝对不允许多个进程同时修改同一文件。这样一类问题称为"读者一写者"问题。
为了实现读者与写者的同步和互斥,我们设置一个信号量S,用于读者与写者之间或写者与写者之间的互斥,初值为"1"。用一个变量rc表示当前正在读的读者个数,当进程可以去读或读结束后都要改变rc的值,因此rc又成为若干读进程的共享变量,它们必须互斥地修改rc。故必须定义另一个用于互斥的信号量Sr,初值也是"1"。读者一写者问题可描述如下:
var S,Sr:semaphorep:=1,1;
rc:interger;
rc:=0;
Parbegin
process Reader i(i=1,2,…,m)
begin
P(Sr);
rc:=rc+1;
if rc=1 then P(S)；
V(Sr);
Read file F;
P(Sr);
rc:=rc-1;
if rc=O then V(S);
V(Sr);
end
process Writer j(j=1,2,…,k)
begin
P(S);
Write file F;
V(S);
end;
Parend;
在这个程序中,当有进程在读而使一个请求写的进程阻塞时,如果仍有进程不断地请求读则写进程将被长期地推迟运行。但在实际的系统中往往希望让写者优先,即当有进程在读文件时,如果有进程请求写,那么新的读者被拒绝,待现有读者完成读操作后立即让写者运行,只有当无写者工作时才让读者工作。下面是写者优先的程序。其中信号量S,初值为1,用于读者与写者或写者与写者之间的互斥;另一信号量Sn,初值为n,表示系统中最多有n个进程可同时进行操作:
var S,Sn:Semaphore:=1,n;
Parbegin
process Reader i(i=1.2,…,n)
begin
P(S);
P(Sn);
V(S);
read file F;
V(Sn);
Process Writer j(j=1,2,…,k)
begin
P(S);
For i=1 to n do P(Sn);
Write file F;
for i:=1 to n do V(Sn);
V(S)
end
parend
其中Process Reader i中的P(S),V(S)保证了当有写者要工作时,不让新的读者去读。Process Writer j中的第一循环语句保证让正在工作的读者完成读后再执行写,完成写操作后由第二个循环语句恢复Sn的初值,最后的V(S)用于唤醒被阻塞的读、写进程。
3.1.3管程使用信号量来处理同步问题时,同步操作P(S)和V(S)分散在各个进程中,并遍布整个程序。这不仅给系统的管理和程序的维护和修改带来了麻烦,两且还会因同步操作的使用不当造成死锁。为了解决上述问题,又产生了一种新的进程同步工具一管程。
1.管程的定义管程机制提供了与信号量机制相同的表达能力,但它更容易控制。管程是由一组局部的变量对局部变量进行操作的一组过程以及对局部变量进行初始化的语句序列构成的一个软件模块,它可用来实现进程同步。取名为monitor_name的管程,其语法如下:
type momtor_name=momtor
variable declarations;
procedue entry P1(…);
begin …end;
┆
procedure entry Pn(…);
begin …end;
begin
initialization code;
end
而且,管程具有以下特点:
(1)管程内的局部变量只能被局部于管程内的过程所访问:反之亦然,即局部于管程内的过程只能访问管程内的变量。
(2)任何进程只能通过调用管程提供的过程入口进入管程。
(3)任一时刻,最多只能有一个进程在管程中执行。
保证进程互斥地进入管程是由编译器负责的。也就是说,管程是一种编程语言的构件,它的实现需要得到编译器的支持。
2.条件变量在任何时刻,最多只有一个进程在管程中执行,因此用管程很容易实现互斥,只要将需要互斥访问的资源用数据结构来描述,并将该数据结构放入管程中便可。若要用管程来实现同步,则在相应条件不满足时(如临界资源得不到时)必须能够将在管程内执行的进程阻塞。由于阻塞的原因不同,为了将它们区分开,引入了局部于管程的条件变量。条件变量的定义格式为:VarXJ:condition。对条件变量只能执行以下两种操作:
(1)wait操作。如X.Wait用来将执行进程挂到与条件变量x相应的等待队列上。
(2)signal操作。如X.signal用来唤醒与x相应的等待队列上的一个进程。值得注意的是,若没有等待进程,则X.Signal不起任何作用。
3.利用管程解决生产者一消费者问题利用管程来解决生产者一消费者问题,首先必须为它们建立二个管程:
type p_c=momtor
Var in,out,count:integer;
Buffer:array[0,…,n-1] of item;
notfull,notempty:condition;
procedure entry put(Var product:item)
begin
if count≥n then notfull.wait; /*等待缓冲池不全满条件成立*/
buffer[in]:=product;
in:=(in+1)mod n;
count:=count+1;
notempty.signal; /*缓冲池不全空条件成立*/
end
procedure entry get(Var product:item)
begin
if count≤Othen notempty.wait; /*等待缓冲池不全空条件成立*/
product:=buffer[out];
out:=(out+1)mod n;
count:=count-1;
notfull.signal; /*缓冲池不全满条件成立*/
end
begin
in:=out:=0;
count:=0;
end
上述管程P_c中包括两个局部过程:过程put负责将产品投放到缓冲池中;过程get负责从缓冲池中取出产品。另外,整型变量count表示缓冲池中己存放的产品数目,条件变量notfull、notempty分别对应于缓冲池不全满、缓冲池不全空两个条件。
而相应的生产者和消费者可描述为：
producer:begin
repeat
produce an item in nextp;
P_c.put(nextp);
until false
end
consumer:begin
repeat
P_c.get(nextc);
consume the item in nextc;
until false
end
3.1.4 进程通信进程间的信息交换称为进程通信。进程之间的互斥与同步就是一种进程间的通信方式。由于进程互斥与同步交换的信息量较少且效率较低,因此称这两种通信方式为低级通信方式,相应地也可将P、V操作称为两条低级通信原语。所谓高级通信方式是指进程之间以较高的效率传送大量数据的通信方式。
1.进程通信的类型高级通信方式可分为三大类:共享存储器系统、消息传递系统以及管道通信系统。
(1)共享存储器系统。高级通信中的共享存储器系统是指进程之间通过对共享存储区的读写来交换数据。共享存储器系统的另一种方式是利用共享的数据结构来进行进程通信,但这种方式对共享数据结构的设置及对进程间的同步都必须由程序员来处理,且只能进行少量的数据交换,因此属于低级通信方式。
（2）消息传递系统。消息传递系统中,进程间的数据交换以格式化的消息(网络中称作报文)为单位。根据实现方式,它又可分为直接通信和间接通信两类。在直接通信方式中,源进程可直接将消息发送给目标进程,此类操作系统通常提供send(receiver,message)和receive(sender,message)两条通信命令(原语)供用户使用。在间接通信方式中,进程间需要通过某种中间实体(即信箱)来进行通信,发送进程将消息投入信箱,而接收进程则从信箱中疆取得消息,因此,它不仅能实现实时通信,还能实现非实时通信。此时,操作系统应提供若干条原语分别用于信箱的创建、撤消和消息的发送、接收等。
(3)管道通信。所谓"管道"是指连接i两个进程的一个打开的共享文件,发送进程以字符流的形式将大量的信息写入管道,接收进程则在需要时从管道中读出数据。为了协调双方的通信,管道通信机制必须对发送进程和接收进程在利用管道进行通信时实施同步和互斥,并只有在确定了对方存在时方能进行通信。
3.1.5线程
1.线程的基本概念引入线程的目的是为了减少程序在并发执行时所付出的时空开销,从而使OS具有更好的并发性。在多线程os中,将拥有资源的基本单位与调度和分派的基本单位分开处理。此时,一个进程中含有一个或多个相对独立的线程,进程只是拥有资源的基本单位,每个线程都是一个可执行的实体,即CPU调度和分派的基本单位是线程。
线程可以利用线程标识符和一组状态参数来描述,并具有下述属性:
(1)轻型实体。线程除了在运行中必不可少的资源(如线程控制块、程序计数器、一组寄存器值和堆栈)外,线程基本上不拥有系统的资源。
(2)独立调度和分派的基本单位。线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位,为此,线程中必须包含调度所必需的信息。
(3)可并发执行。同一个进程中的多个线程,以及不同进程中的多个线程均可以并发地执行。
(4)共享进程资源。同一个进程中的各线程可以共享该进程所拥有的全部资源,如进程的地址空间、己打开的文件、定时器和信号量机构等。
由于线程基本不拥有资源,创建线程时不需另行分配资源,终止时也不需要进行资源的回收,而切换时也大大减少了需保存和恢复的现场信息,因此,线程的创建、终止和切换都要比进程迅速且开销小。另外,同一进程中的各线程可以共享该进程所占用的内存空间和已打开文件,因此,线程间通信也非常简便和迅速。
2.线程的控制在多线程OS环境下,应用程序在启动时,OS将为它创建一个进程,同时为该进程创建第一个线程。以后在线程的运行过程中,它可根据需要利用线程创建函数(或系统调用)再去创建若干个线程。所以线程是由线程创建的,但线程间并不提供父子关系的支持。
每个线程被创建后,便可与其他线程一起并发地运行。如同传统的进程一样,并发运行的线程之间也存在着共享资源和相互合作的制约关系,致使线程在运行时也具有间断性。相应地,线程在运行时,也具有执行、就绪、阻塞三种基本状态,并随着自身的运行和外界环境的变换而不断地在三种状态之间转换。
当线程完成了自己的工作后,它便可正常终止。线程的终止也可能是因为运行中出现错误或某种其他原因而引起的,此时它是被强行终止的。可见,线程如同进程一样,具有一定的生命周期。
3.线程的同步在多线程os中通常提供多种同步机制,如互斥锁、条件变量、信号量机制以及多读、单写锁等,它们可支持不同频率的交互操作和不同程度的并行性。
（1)互斥锁互斥锁有开锁和关锁两种状态,并能进行关锁和开锁两种操作。当一个线程需要访问某个临界资源时,线程首先应对为该资源所设置的互斥锁mutex进行关锁操作mutex_enter:判别mutex的状态,如果它已处于关锁状态,则试图访问该资源的线程将被阻塞;而如果mutex处于开锁状态,则将mutex关上后便可访问该资源。在线程完成对共享资源的访问后,必须执行开锁操作mutex-exit:如果有线程阻塞在该互斥锁上,则唤醒其中的一个线程;而如果没有阻塞的线程,则将互斥锁的状态置成开锁状态。为了降低线程被阻塞的频率,在有的系统中还提供了一种不阻塞的关锁操作mutex_tryenter,当mutex处于关锁状态时,mutex_tryenter并不阻塞线程,而只是返回一个指示操作失败的状态码。
互斥锁是一种比较简单的同步机制,而且是严格括入的(bracketing),一个线程去打开被另一线程关闭的互斥锁将是错误的,因此它只适用于实现线程对资源的互斥访问。由于操作互斥锁的时间和空间开销都较低,因而它较适合于高频度使用的关键共享数据和程序段。
（2)条件变量条件变量必须和互斥锁配合起来使用,它用于等待,直到某一特定条件为真。对条件变量的cv_wait操作将使线程阻塞,直到所等的条件信号成立后,才能由cv_signal操作将其中的一个阻塞线程唤醒。cv_wait操作在阻塞线程前将对相应的互斥锁执行开锁操作,并在返回前重新对互斥锁进行关锁操作。条件变量可用来实现互斥或同步,它的典型使用方式为:
mutex_enter(&mutex);
┇
while(some_condition){
cv_wait(&cv,&mutex);
}
┇
mutex_exit(&mutex);
这里允许条件是一个复杂的表达式,因为它受互斥锁的保护。
（3)信号量机制信号量机制也可用于多线程os中,实现诸线程或进程之间的同步。为了提高效率,可为线程和进程分别设置相应的信号量。
当某线程利用信号量来实现同一进程中各线程之间的同步时,可调用创建信号量命令来创建一私用信号量,其数据结构被存放在应用程序的地址空间中。私用信号量属于特定的进程所有,OS并不知道私用信号量的存在,因此,一旦发生私用信号量的占用者异常结束或正常结束,但并未释放该信号量所占用的空间时，系统无法使它恢复为0(空),也不能将它传送给下一个请求它的线程。
当要实现不同进程间或不同进程中各线程之间的同步时,则可由系统为它们创建-个公用信号量,其数据结构存放在受保护的系统存储区中,并由os为它分配空间并进行管理,故也称其为系统信号量。如果信号量的占有者在结束时未释放该公用信号量,则OS会自动将该信号量空间回收,并通知下一个进程。可见,公用信号量是一种比较安全的同步机制。
4.内核支持线程和用户级线程线程己在许多系统中实现,但实现的方式并不完全相同。有些系统中,特别是一些数据库管理系统如Informix中,所实现的是用户级线程；而另一些系统（如Macintosh和OS/2)所实现的是内核支持线程；还有一些系统如Soloris,则同时实现了这两种不同类型的线程。
(1)用户级线程。用户级线程仅存在于用户空间中,而与内核无关。就内核而言,它只是管理常规的进程-单线程进程,而感知不到用户级线程的存在。每个线程的控制块都设置在用户空间中,所有对线程的操作也在用户空间中由线程库中的函数(过程)完成,而无需内核的帮助。用户级线程的优点是不需要得到内核的支持:而且,线程的切换无需陷入内核,故切换开销小,速度非常快。另外,线程库对用户线程的调度算法与os的调度算法无关,因此,线程库可提供多种调度算法供应用程序选择使用。但在纯用户级线程的系统中,对应用程序来讲,一个线程的阻塞将导致整个进程中所有线程的阻塞,并且无法享用多处理机系统中多个处理器带来的好处。
(2)内核支持线程。内核支持线程是在核心空间实现的。内核为每个线程在核心空间中设置了一个线程控制块,用来登记该线程的线程标识符、寄存器值、状态、优先级筹信息。所布对线程的操作,如创建、撤消和切换等,都是通过系统功能调用由内核中的相应处理程序完成的。内核支持线程克服了用户级线程的两个缺点:首先内核可以把同一个进程中的多个线程调度到多个处理器中:其次,如果进程中的一个线程被阻塞,内核可以调度同二个进程中的另一个线程。它的另一个优点是内核本身也可以使用多线程的方式来实现。它的主要缺点是,即使CPU在同一个进程的多个线程之间切换,也需要陷入内核,因此,其速度和效率不如用户级线程。
(3)用户级线程和核心级线程的结合。为了同时获得用户级线程和内核支持线程的便利,某些系统(如Solads)同时提供了这两种类型的线程。在Solaris中除了提供内核支持线程、用户级线程这两种线程外,还在它们之间定义了一种轻型进程LWP。其中,内核支持线程和LWP是内核实现的,而用户级线程是由用户地址空间中的线程库实现的。内核调度和分派的基本单位是内核支持线程,而内核提供给用户的却是LWP,即每个用户进程都可拥有一个或多个LWP。LWP可以看成是用户级线程与内核支持线程之间的桥梁,每个LWP都与一个内核支持线程对应,它可将一个或多个用户级线程映射到一个内核线程。但每个内核支持的线程并不一定对应于某个LWP,如那些为OS本身建立的内核支持线程便没有对应的LWP。通常,程序员可不考虑LWP,而直接使用线程库编程,此时一个用户进程只对应于一个LWP,而且可获得用户级线程的所有便利。但如果他需要优化程序的性能、获得物理上的并行,则可将自己的用户级线程连接到多个LWP上,此时,被连接到LWP上的线程便具有了内核支持线程的所有属性。
3.2重点难点学习提示由于进程是OS中最重要的基本概念,因而本章也就成为全书中最重要的一章。读者应对以下几个重点、难点问题进行深入的学习,切实掌握好进程和进程同步的基本概念。
3.2.1 进程的基本概念进程既是os中的一个重要概念,又是系统进行资源分配和独立运行的基本单位。学习
os,首先必须理解和掌握好进程的概念,为此,应认真学习和掌握下述几个方面的内容:
(1)为什么要引入进程。引入进程是为了使内存中的多道程序能够正确地并发执行。在学习时应清楚地理解为什么程序(在未为之建立进程之前)不能与其他程序并发执行,而由PCB、程序段和数据段三部分组成的进程实体却能与其他进程一起并发执行。
(2)进程具有哪些基本特征。进程具有动态性、并发性、独立性、异步性和结构特征。在学习时应较好地理解每个特征的含义和形成原因,并且要特别注意比较进程和程序这两个概念的异同之处。
(3)进程有哪些基本状态。进程具有就绪、执行和阻塞三种基本状态。在学习时必须了解在一个进程的生命周期中,它是如何随着自身的执行和外界条件的变化不断地在各种状态之间进行转换的。
(4)进程控制块。为了描述和控制进程,os必须为每个进程建立一个进程控制块PCB。在学习时应了解PCB具有哪些作用,为此,在PCB中必须包含哪些内容。
3.2.2进程同步的基本概念进程同步既是OS中的一个重要概念,又是保证系统中诸进程间能协调运行的关键,故应对它有较深入的理解,并能较熟练地运用。为此,应对下述与进程同步有关的几个基本概念有较好的理解和掌握:
(1)临界资源。临界资源是指→次仅允许一个进程访问的资源。在学习时,应了解对这种资源应采取什么样的共享方式。
(2)临界区。进程中访问临界资源的那段代码称为临界区.显然,为了实现进程互斥地访问临界资源,诸进程不能同时进入自己的临界区。在学习时,应了解用什么样的机制(称同步机制)来实现进程互斥地进入自己的临界区。
(3)同步机制应遵循的准则。用于实现进程同步的机制有多种,但它们都应遵循"空闲让进"、"忙则等待"、"有限等待"和"让权等待";四个准则。读者必须清楚,为什么要同时满足这四条准则,如违背了其中的基本准则,其后果是什么。
3.2.3 信号量机制及其应用信号量机制是一种卓有成效的进程同步机制,它已被广泛地应用于各种类型的OS中。因此,,必须对下述几个与信号量有关的内容有较深刻的理解和掌握：
(1)信号量的含义。
(2)信号量的物理意义。
(3)用信号量实现互斥。为了实现进程对临界资源的互斥访问,需为每类临界资源设置初值为1的互斥信号量mutex。在学习时,应清楚在进入临界区前或退出临界区后应对mutex分别执行什么操作,为什么对mutex的P和V操作必须成对出现,如少了其中的P操作或V操作,会对互斥算法产生什么样的影响。
(4)用信号量实现前趋关系。为实现前驱关系Pi→Pj,可为它们设置一个初值为0的信号量S。在学习时,应清楚对S的P操作和V操作应分别安排在什么位置,同时必须注意P(S)操作和V(S)操作也必须成对出现。
(5)经典进程的同步问题我们以生产者一消费者为例,来说明学习此重点问题时应了解和掌握些什么。
①生产者一消费者问题是用于解决一群生产者和消费者之间的进程互斥和进程同步问题。在学习时首先应了解哪些资源属于临界资源,并为它们设置了哪些信号量,信号量的初值应如何设置;其次,应了解哪些地方需要同步,并需为它们设置哪些信号量,信号量的初值又应如何设置等。
⑵如何实现进程互斥。为实现对缓冲池的互斥访问,应为它设置一互斥信号量mutex,读者应在生产者进程和消费者进程中都能找到成对的用于实现互斥的P(mutex)和V(mutex)操作。
③如何实现进程同步。为实现进程同步,应为缓冲池设置表示缓冲区空和满的empty和full信号量,读者应在相互合作的进程中找到成对的P(empty)和V(empty)操作,成对的P(fu11)和V(full)操作。
④对程序的阅读方式。由于生产者-消费者问题属于并发执行程序,因此在阅读时可采取交替阅读的方式。我们可以先从任一程序(如生产者)开始阅读,当它因P操作失败而阻塞时,该程序便不能继续往下运行,此时,可去阅读消费者程序;而当消费者唤醒阻塞的生产者,或者消费者因P失败而受阻时,则又可返回到生产者程序继续阅读。
3.2.4消息传递通信机制无论是单机系统、多机系统,还是计算机网络中,消息传递机制都是一种使用十分广泛的进程通信机制,必须了解以下几个问题:
(1)什么是消息传递通信机制。这是指以格式化的消息为进程间数据交换单位的进程通信方式,在学习时应了解通常在一个消息中应包含哪几方面的内容,定长格式的消息和变长格式的消息分别具有什么优缺点。
(2)消息传递通信机制有哪几种实现方式。消息传递通信机制有直接通信和间接通信两种实现方式,在学习时应注意比较它们在原语的提供、通信链路的建立、通信的实时性等方面的异同。
(3)如何协调发送进程和接收进程。为了使诸进程间能协调地进行通信,必须对进程通信的收、发双方进行进程同步,在学习时应了解常用的同步方式有哪些,它们分别适用于何种场合。
(4)消息缓冲队列通信机制。消息队列通信机制是一种常用的直接通信方式,在学习时应较好地理解它是如何在诸进程间实现互斥和同步的,其发送和接收过程又是如何完成的。
3.2.5 线程的基本概念线程在操作系统领域中是一个非常重要的机制和技术,它能有效地提高系统的性能。目前,不仅在操作系统中,而且在数据库管理系统和其他应用软件中,都普遍引入了线程的概念。应对下述几个问题有较好的理解:
(1)为什么要引入线程。在学习时,读者必须清晰地认识到,为什么进程的并发执行需要付出较大的时空开销,这对系统的并发程度又将产生什么样的影响:而线程机制是如何解决上述问题的,它带来了哪些好处。
(2)线程具有哪些特征。线程实体具有轻型、可独立运行、可共享其所隶属的进程所拥有的资源等特征。在学习时,应了解线程自己为什么还必须拥有少量的私有资源,并注意在并发性、调度性、拥有资源和系统开销等方面对多线程OS中的线程和进程进行比较。
(3)如何创建和终止线程。在学习时应了解应用程序是如何创建线程和终止线程的,还应注意比较线程的创建和终止与传统的进程的创建和终止有什么异同之处。
(4)内核支持线程和用户级线程线程按其实现方式可分为内核支持线程和用户级线程两类。在学习时应了解以下两个方面的内容：
①什么是内核支持线程。内核支持线程的TCB被保存在核心空间中,它的运行需获得内核的支持。在学习时,必须了解内核支持线程的创建、撤消和切换等功能是如何实现的,内核支持线程有哪些优点,又有哪些缺点。
②什么是用户级线程。用户级线程是在用户空间实现的。在学习时,必须了解用户级线程有哪些优点,通过用户空间的线程库(即运行时系统)来实现用户级线程有哪些不足之处,而将用户级线程和核心支持线程结合起来(即内核控制的用户线程)又能带来什么样的好处。
(5)进程和线程的关系
(1)线程是进程的一个组成部分。一个进程可以有多个线程,而且至少有一个可执行线程。
(2)进程的多个线程都在进程的地址空间内活动。
(3)资源是分给进程的,而不是分给线程的。线程需要资源时,系统从进程的资源配额中扣除并分配给它。
(4)处理机调度的基本单位是线程。线程之间竞争处理机,真正在处理机上运行的是线程。
3.3典型问题分析和解答
1.在操作系统中为什么要引入进程概念?它会产生什么样的影响?
答:在操作系统中引入进程概念,是为了实现多个程序的并发执行。传统的程序不能与其他程序并发执行,:只有在为之创建进程后,才能与其他程序(进程)并发执行。这是因为并发执行的程序(即进程)是"停停走走"地执行,只有在为它创建进程后,在它停下时,方能将其现场信息保存在它的PCB中,待下次被调度执行时,再从PCB中恢复CPU现场而继续执行,而传统的程序却无法满足上述要求。
建立进程所带来的好处是使多个程序能并发执行,这极大地提高了资源利用率和系统吞吐量。但管理进程也需付出一定的代价,包括进程控制块及协调各运行的机构所占用的内存空间开销,以及为进行进程间的切换、同步及通信等所付出的时间开销。
2.作业、进程和程序之间的区别和联系答：（1）作业、进程和程序之间的联系：一个作业通常包括程序、数据和操作说明书三部分。每一个进程由PCB、程序和数据集合组成,这说明程序是进程的一部分,是进程的实体。因此,一个作业可划分为若干个进程来完成,而每个进程又都有其实体一程序和数据集合。
（2）进程和程序的区别
①进程是程序的一次执行,属于动态概念,而程序是一组有序的指令,是一种静态概念。但进程离开了程序也就失去了存在的意义。
②一个进程可以执行一个或几个程序z反之,同一程序可能由几个进程同时执行。
③程序可作为软件资源长期保留,而进程是程序的一次执行过程,是暂时的。进程具有生命期。
④进程具有并发性,能与其它进程并发运行。而程序不具备这种特征。
⑤进程是一个独立的运行单位,也是系统进行资源分配和调度的一个独立单位。因此,进程具有独立性,但有时进程间又具有相互制约性。
注意:说进程是一个独立的运行单位,是指在不具有线程的系统中而言的,在引入线程的系统中,进程不再是运行的基本单位,只是资源分配的基本单位。
3.PCB的作用是什么?为什么说PCB是进程存在的惟一标志?
答:进程控制块的作用,是使一个在多道程序环境下,不能独立运行的程序,成为一个能独立运行的基本单位、一个能与其他进程并发执行的进程。
在创建进程时,系统将为它配置一个PCB:在进行进程调度时,系统将根据PCB中的状态和优先级等信息来选择新进程,然后将老进程的现场信息保存到它的PCB中,再根据新进程PCB中所保存的处理机状态信息来恢复运行的现场:执行中的进程,如果需要访问文件或者需要与合作进程实现同步或通信,则也都需要访问PCB:当进程因某种原因而暂停执行时,也必须将断点的现场信息保存到它的PCB中:当进程结束时,系统将回收它的PCB。可见,在进程的整个生命周期中,系统总是通过其PCB对进程进行控制和管理,亦即系统是根据其PCB而不是任何别的什么而感知到一进程的存在,所以说,PCB是进程存在的惟一标志。
4.某系统的进程状态转换图如图3.1所示,请说明:
2
1 3
4
(1)引起各种状态转换的典型事件有哪些?
(2)当我们观察系统中某些进程时,能够看到某一进程产生的一次状态转换能引起另一进程作一次状态转换。在什么情况下,当一个进程发生转换3时能立即引起另一个进程发生转换1?
(3）试说明是否会发生下述因果转换:
2→1
3→2
4→1
解:(1)在本题所给的进程状态转换图中,存在四种状态转换。当进程调度程序从就绪对列中选取一个进程投入运行时引起转换1；正在执行的进程如因时间片用完而被暂停执行就会引起转换2；正在执行的进程因等待的事件尚未发生而无法执行（如进程请求完成I/O)则会引起转换3；当进程等待的事件发生时（如I/0完成)则会引起转换4。
(2)如果就绪队列非空,则一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的进程由执行状态变为阻塞状态,这时处理机空闲,进程调度程序必然会从就绪队列中选取一个进程并将它投入运行,因此只要就绪队列非空,一个进程的转换3能立即引起另一个进程的转换1。
(3)所谓因果转换指的是有两个转换,一个转换的发生会引起另一个转换的发生,前一个转换称为因,后一个转换称为果,这两个转换称为因果转换。当然这种因果关系并不是什么时候都能发生,而是在一定条件下才会发生。
2→1：当某进程发生转换2时,就必然引起另一进程的转换1。因为当发生转换2时,正在执行的进程从执行状态变为就绪状态,进程调度程序必然会从就绪队列中选取一个进程投入运行,即发生转换1。
3→2：某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前执行进程从执行状态变为阻塞状态,不可能又从执行状态变为就绪状态。
4→1：当处理机空闲且就绪队列为空时,某一进程的转换4就会引起该进程的转换1。因为此时处理机空闲,一旦某个进程发生转换4,就意味着有一个进程从阻塞状态变为就绪状态,因而调度程序就会将就绪队列中的此进程投入运行。
5.P1、P2、P3、P4、P5、P6、P7为一组合作进程,其前趋图如图3.2所示,试用P、V操作描述这7个进程的同步。
图3.2说明任务启动后P1先执行,当它结束后P2、P3可以开始执行,P2完成后P4、P5可以开始执行，P3完成后P6可以开始执行,仅当P4、P6、P6都执行完后,P7才能开始执行。为了确保这一执行顺序,设置8个同步信号量a、b、c、d、e、f、g、h分别表示进程P1、P2、P3、P4、P5、P6是否执行完成,其初值均为0。这6个进程的同步描述如下:
Var a，b,c,d,e,f,g,h:semaphore:==0,0,0,0,0,0,0,0;
begin
parbegin
begin S1;V(a);V(b);end a b
begin P(a);S2;V(c);V(d);end
begin P(b);S3;V(e);end
begin P(c);S4;V(f);end c d e
begin P(d);S5;V(g);end
begin P(e);S6;V(h);end
begin P(f);P(g);P(h);S7;end
parend f g h
图 3-2
6.什么是优先图?什么是进程图?二者有何区别?
解：优先图是一种有向无环图,其结点对应于独立的语句(组),从结点i到结点j的有向连线表示语句i必须在语句j开始执行之前完成.进程图可看做是一种(有向)树结构,其中每个结点是一个进程.从上个结点指向另一结点的有向连线指明前者创建了后者.优先图表征语句之间的优先制约关系,而进程图则展示进程的创建关系。在一个进程图中,Pi到Pj的边并不隐含Pi只能在Pj之后执行,而是表示Pi创建Pj,Pi和pj可以并发地执行。
7.下述算法是解决两进程互斥访问临界区问题的一种方法。试从"互斥"、"空闲让进"、"有限等待"等三方面讨论它的正确性。如果它是正确的,则证明之:如果它不正确?请说明理由。
Var c1,c2:integer:=1,1;
begin
parbegin
p1:begin
repeat
remain section1;
repeat
c1:=1-c2;
until c2<>0;
Critical section; /*临界区*/
c1:=1;
until false
end
p2:begin
repeat
remain section2;
repeat;
c2:=1-c1;
until c1<>0;
Critical section; /*临界区*/
c2:=1;
until false
end
parend
end
分析：在通过对共享变量的测试来实现进程互斥时,必须注意共享交量本身也应当是临界资源,如果多个进程对它们进行同时共享,则可能会导致程序互斥算法的失败。在做这类题目时,可将检查的重点放在将条件测试指令和前面(或后面)对测试指令中所用的共享变量的修改操作相分割的情况下,该变量又刚好被其他进程修改的时候。
答:本题中,p1、p2通过共享变量c1和c2来达到资源互斥使用的目的,其中,c1=1表示p1不在临界区内,c2=1表示p2不在临界区内。通过检查可知:
(1)该算法不能保证互斥访问临界区。
①由于c1、c2的初值都为1,若p1先获得CPU并申请进入临界区,则它可以进入临界区。在p1进入临界区后,c2=1,c1=0:②此时若进行进程调度并由p2获得CPU,而p2也试图进入临界区,执行完C2:=1-C1后,C2=1,C1=0;③此时若又进行CPU调度,并且p1重新获得CPU,并在返出临界区后执行c1:=1,则c2=1,c1=1:④若再进行CPU调度,并且由p2获得CPU,因c1=1,p2进入临界区,而此时c2=1,c1=1;⑤若再进行CPU调度并由p1获得CPU,当p1再申请进入临界区时,由于C2=1,P1将顺序进入临界区。可见,在这种情况下,pl和p2将同时进入临界区。
（2）该算法能保证空闲让进。因为,c1和C2的初值均为1;而c1只有在pl申请进入自己的临界区时才可能变为0,一旦P1退出临界区,它的值又将被置为1；同样,c2只有在P2申请进入自己的临界区时才可能变为0,一旦P2退出临界区,它的值又将被置为1。所以,当临界资源空闲时,不管它是否曾经被使用过,C1和C2的值均为1；此时,若p1进程申请进入自己的临界区,则先执行C1:=1-C2,将c1置为0,并因C2<>O条件成立而结束循环测试,随后进入自己的临界区;对p2进程,情况也是如此。
(3)在该算法中,若一进程在临界区内执行,则另一进程将处于“忙等”。因此,在某些特殊的情况下,有可能不能保证“有限等待”。
8.请描述在当前运行进程状态改变时,操作系统进行进程切换的步骤。
解:进程切换的步骤如下:
(1)保存处理器内容；
(2)对当前运行进程的PCB进行更新.包括改变进程状态和其他相关信息；
(3)将这个进程的PCB移人适当的队列(就绪、因事件阻塞、就绪挂起等)；
(4)挑选其他进程执行；
(5)对挑选进程PCB进行更新,包括将其状态改为运行；
(6)对存储器管理数据结构进行更新；
(7)恢复被选择进程上次移出时的处理器状态。
9.请举例说明如何利用信号量实现进程同步。
计算进程 单缓冲区 打印进程图3.3是单缓冲的计算进程和打印远程;
答:在用信号量机制实现同步时,只要找出进程之间的同步关系,并为每种同步关系设置一信号量,然后再在需要等待某种动作的地方插入P操作,在被等待的动作完成之后插人V操作。例如,如图3.7所示的共享单缓冲的计算进程和打印进程之间存在两种同步图关系:
(1)打印进程必须等待计算进程将计算结果放入缓冲之后,才能取数打印,因此,可为它们设置一初值为0的信号量SA,表示缓冲区中是否有计算结果可供打印:并将P(SA)操作放在打印进程取数打印的动作之前,V(SA)操作放在计算进程将计算结果放入单缓冲的动作之后。
(2)计算进程必须等打印进程将缓冲区中的前一个数据取走,缓冲区变空后,才能将下一个计算结果放入缓冲区,因此,可为它们设置一初值为1的信号量SB,表示是否有空闲的缓冲区可供存放计算结果:并将P(SB)操作放在计算进程,将计算结果放入缓冲区的动作之前,而将V(SB)操作放在打印进程腾出空闲缓冲之后。具体的同步算法可描述如下:
Var SA,SB:semaphore:=0,1;
begin
parbegin
cp:begin
repeat
compute next number;
P(SB);
add the number to buffer;
V(SA);
until false;
end
PP:begin
repeat
P(SA);
take a number from buffer;
V(SB);
Print the number;
until false;
end
parend
end
10.设公共汽车上,司机和售票员的活动分别是:
司机的活动,售票员的活动:
启动车辆; 关车门;
正常行车; 售 票;
到站停车; 开车门;
在汽车不断地到站、停车、行驶过程中,这两个活动有什么同步关系?用信号量和P、V操作实现它们的同步。
解：在汽车行驶过程中,司机活动与售票员活动之间的同步关系为：售票员关车门后,向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步:售票员开车门的动作也必须与司机停车取得同步。
在本题中,应设置两个信号量:s1、s2,s1表示是否允许司机启动汽车,其初值为0;s2表示是否允许售票员开门,其初值为0。用P、V原语描述如下z
int s1=0；
int s2=0；
main( )
{
parbegin
driver( );
busman( );
parend
}
driver( )
{
while(1〉
{
p(s1);
启动车辆;
正常行车;
到站停车;
v(s2);
}
}
busman( )
{
while(1)
{
关车门;
v(sl);
售票;
p(s2);
开车门;
上下乘客;
}
}
用P、V操作来控制现实生活中的操作流程是一类常见的试题。这类试题要求解题者能将生活中的控制流程用形式化的方式表达出来。
11.嗜睡的理发师问题:一个理发店由一个有N张沙发的等候室和一个放有-张理发椅的理发室组成。没有顾客要理发时,理发师便去睡觉。当一个顾客走进理发店时,如果所有的沙发都已被占用,他便离开理发店;否则,如果理发师正在为其他顾客理发,则该顾客就找一张空沙发坐下等待;如果理发师因无顾客正在睡觉,则由新到的顾客唤醒理发师为其理发。在理发完成后,顾客必须付费,直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。
分析：本题中,顾客进程和理发师进程之间存在着多种同步关系:
(1)只有在理发椅空闲时,顾客才能坐到理发椅上等待理发师理发,否则顾客使必须等待;只有当理发椅上有顾客时,理发师才可以开始理发,否则他也必须等待.这种同步关系类似于单缓冲(对应于理发椅)的生产者一消费者问题中的同步关系,故可通过信号量empty和full来控制。
(2)理发师为顾客理发时,顾客必须等待理发的完成,并在理发完成后由理发师唤醒他,这可单独使用一个信号量cut来控制。
(3)顾客理完发后必须向理发师付费,并等理发师收费后顾客才能离开;而理发师则需等待顾客付费,并在收费后唤醒顾客以允许他离开,这可分别通过两个信号量payment和receipt来控制。
(4)等候室中的N张沙发是顾客进程竞争的资源,故还需为它们设置了一个资源信号量sofa。
(5)为了控制顾客的人数,使顾客能在所有的沙发都被占用时离开理发店,还必须设置一个整型变量count来对理发店中的顾客进行计数,该变量将被多个顾客进程互斥地访问并修改,这可通过一个互斥信号量mutex来实现。
答:为解决上述问题,需设置一个整型变量count用来对理发店中的顾客进行计数,并需设置7个信号量,其中zmutex用来实现顾客进程对count变量的互斥访问,其初值为1；sofa是对应于等候室中N张沙发的资源信号量,其初值为N；empty表示是否有空闲的理发椅,其初值为1;full表示理发椅上是否坐有等待理发的顾客,其初值为0；cut用来等待理发的完成,其初值为0:payment用来等待付费,其初值为0;receipt用来等待收费,其初值为0。具体的算法描述如下:
Var count:integer:=0;
mutex,sofa,empty,full:semaphore:=1,N,1,0;
cut,payment,receipt:semaphore:=0,0,0;
begin
parbegin
guest:begin
P(mutex);
if(count>N)
begin
V(mutex);
exit shop;
end
else
begin
count:=count+1;
if(Count>1) then
begin
P(sofa);
sin on sofa;
P(empty);
get up fromsoft;
V(sofa);
end
else /*count=1*/
P(empty);
sit on the baber_chair;
V(full);
P(cut);
Pay;
V(payment);
P(receipt);
get up from the baber_chair;
V(empty);
P(mutex);
count:=count-1;
V(mutex);
exit shop;
end
end
barber:begin
repeat
wait(full);
cut hair;
V(cut);
P(payment);
accept payment;
V(recipt);
until false;
end
parend
end
上述算法只考虑了理发店只有一个理发师的情况,如何将它改成有多个理发师并配有一收银员的算法,作为留给读者进一步思考的习题。
12.消息缓冲队列通信机制应具有哪儿方面的功能?
答:在消息缓冲队列通信机制中,应具有如下儿方面的功能：
（1）构成消息：发送进程在自己的工作区设置发送区a,将消息正文和有关控制信息填入其中。
（2）发送消息：将消息从发送区a复制到消息缓冲区,并把它插入到目标进程的消息队列中'
(3)接收消息：由目标进程从自己的消息队列中找到第一个消息缓冲区,并将其中的消息内容拷贝到本进程的接收区b中。
(4)互斥与同步：互斥是指保证在一段时间内只有一个进程对消息队列进行操作；同步是指在接收进程和发送进程之间进行协调。为此,应在接收进程的PCB中,设置用于实现互斥和同步的信号量。
13.有一单向行驶的公路桥,每次只允许一辆汽车通过。当汽车到达桥头时,若桥上无车,便可上桥，否则,需等待,直到桥上的汽车下桥为止。若每一辆汽车为一个进程,请用P、V操作编程实现。
解：汽车进程pi(i=1,2,3,…)
到达桥头
P(S)
上桥行驶到达桥另一端
V(S)
信号量的初值：S=1
14.什么是内核支持线程和用户级线程?并对它们进行比较。
答:内核支持线程是在内核支持下实现的,即每个线程的线程控制块设置在内核中,所有对线程的操作(如创建、撤消和切换等),都是通过系统功能调用由内核中的相应处理程序完成。而用户级线程仅存在于用户空间中,即每个线程的控制块设置在用户空间中,所有对线程的操作也在用户空间中完成,而无需内核的帮助。
可从以下几个方面比较内核支持线程和用户级线程:
(1)内核支持：用户级线程可在一个不支持线程的os中实现,而内核支持线程则不然,它需要得到os内核的支持。
(2)处理器的分配：在多处理机环境下,对纯粹的用户级线程来说,内核一次只为一个进程分配一个处理器,即进程无法享用多处理机带来的好处:而在设置有内核支持线程时,内核可调度一个应用中的多个线程同时在多个处理器上并行运行,从而提高程序的执行速度和效率。
(3)调度和线程执行时间：对设置有内核支持线程的系统,其调度方式和算法与进程的调度十分相似,只不过调度的单位是线程:而对只设置了用户级线程的系统,调度的单位则仍为进程。因此,在条件相同的情况下,内核支持的线程通常比用户级线程得到更多的CPU执行时间。
(4)切换速度：用户级线程的切换,通常发生在一个应用程序的诸线程之间,由于不需陷入内核,而且切换的规则也相当简单,因此切换速度比内核支持线程至少快一个数量级。
(5)系统调用：在典型的os中,许多系统调用都会引起阻塞。当一个用户级线程执行这些系统调用时,被阻塞的将是整个进程:而当一个内核支持线程执行这些系统调用时,内核只阻塞这个线程,但仍可调度其所属进程的其他线程执行。
15.利用parbegin/parend结构编写一个实现无复制的双缓冲区方案的程序。
答：
Var bufret array[0..n-1] of item;
In,out:0..n;
nextp,nexte:Item;
in:=0;
out:=0;
parbegin
producer:
begin
repeat
…
produce am item in nextp
…
while (in+1)mod n=out do skip;
bufer[in]:=nextp;
in:=(in+1)mod n;
until false;
end;
consuII1er:
begin
repeat;
while in =out do skip;
nextc:==bufer[out];
out:=(out+1)mod n;
…
consume the item in nextc
…
until false;
end;
parend;
16.试说明如果P.V操作不是不可分割执行的,就会违反互斥性.
答：假定信号量S =1,且进程PI和P2并发地执行P(S),那么,下面的执行序列就违反了互斥性:
(1)To:P1判定S之值等于1:
(2)T1:p2判定S之值等于1:
(3)T2:P1将S减1并进入临界段:
(4)T3:P2将S减1并进入临界段.
17.创建新进程有哪几种实现方式?
解:创建新进程有四种方式:
(1)父进程继续与其子进程并发地执行
(2)父进程暂停执行直至其子进程全部执行完
(3)父进程和子进程共享所有的公用变量
(4)子进程只共享父进程变量的一个子集
18.一个二元信号量是其值仅取0和1的信号量,如何用二元信号量去实现"一般的"信号量?
解:令S是一般的信号量,可用下面的程序来实现它:
var s1 binary-semaphore{初值=1}
S2 binary-semaphore {初值=0}
C:integer {初值为S之值}
P(S):P(Sl)
C,=C一1;
If C<O then
Begin
V(Sl);
P(S2);
end
else V(S1);
V(S):P(Sl);
C,=C+1·
If C<=O then V(S2);
V(Sl);
19．一个多元信号量允许P和V原语同时在若干信号量上操作,在一个不可中断的操作中就可获得和释放几个资源,这样的P原语(操作在两个信号量上)可定义如下:
P(S,R):while (S《l or R《1)do skip;
S,=S -1·
R:=R-1;
那么,如何用常规的信号量来实现这种多元信号量?
解:可用下面的编码来实现这种多元信号量:
var S1,R1,integer:
mutex:semaphore; {初值=1}
X:semaphore; {初值=0}
P(S,R),P(mutex);
Sl:=S1-1;
Rl:=R1-1;
If Sl〈O or R1<O then
begin
V(mutex);
P(X);
End
else V(mutex);
V(S,R) P(mutex);
S1:=Sl+1;
R1:=R1+1;
If S1<=O and R1《O then V(X);
V(mutex);
20.一个文件可由若干不同的进程所共享,每个进程具有唯一的编号；假定文件可由满足下列限制的若干进程同时访问；与并发访问该文件的那些进程相关的唯一编号的总和必须小于n.设计一个协调对该文件访问的管程.
答：协调对该文件访问的管程如下:
type coordinator =monitor
Var count:integer;
S:condition;
procedure acquire (id:integer);
begin
while (count+id,n) do S-Wait;
count,=count +id
end
procedure leave (id:integer);
begin
count,=count -id;
end;
begin
count,=0;
end.
21,n个进程P1,P2,…,Pn共享一个CPU，一次最多只可有一个进程使用CPU；CPU一旦有空,就可被一个进程使用,当CPU被占用时,其他进程必须等待，当多个进程同时等待使用CPU时,CPU一经释放,其中优先权最高的进程就被允许使用它；优先权规定如下:进程Pi的优先权为i(i=1,2,…,n),而优先数较小者则其优先权较高，下面是进程Pi预定(RESERVE)、使用和释放(RELEASE)CPU的一个算法:
RESERVE(i);
使用CPU;
RELEASE;
试编出其中两个过程RESERVE(i)和RELEASE的程序.
解:过程RESERVE(i)和RELEASE的程序如下:
var:shared record
free:boolean;
waiting:array[l..n]of boolean;
end;
procedure entry RESERVE(i:1..n);
begin
region V do
begin
if free then free:=false
else begin
waiting[i]:=true;
await(not(waiting[i]));
end;
end;
end;
procedure entry RELEASE;
var k:1..n
begin
region v do
begin
for k:=lto n do
if waidng[k]
then begin
waiting[k]:=false;
exit;
end;
free:=true;
end;
end;
22.有一个仓库可以存放A、B两种物品,每次只能存人一件物品(A或B).存储空间充分大,只是要求-n〈A的件数-B的件数〈m,其中n和m是正整数.试用存人A、存入B和p、V操作,描述物品A和物品B的人库过程.
解:设置三个信号量,初值分别为:So=1:SA=m-1:SB=n-1.
物品A人库过程:
P(SA)
P(SO)
存人A
V(SO)
V(SB)
物品B人库过程
P(SB)
P(SO)
存入B
V(SO)
V(SA)
23．若有一售票厅只能容纳300人,当少于300人时,可以进入；否则,需在外等候。若将每一个购票者作为一个进程,请用P、V操作编程,并写出信号量的初值。
解:购票者进程P.(i=1,2,3,…)
┇
P(S)
进入售票厅购票退出售票厅
V（S）〉
信号量的初值:S=300
24.有一只铁笼子,每次只能放入一只动物。猎手向笼中放入老虎,农民向笼中放入猪,动物园等待取笼中的老虎,饭店等待取笼中的猪,试用P、V操作写出能同步执行的程序。
解:这个问题实际上可看作是两个生产者和两个消费者共享了一个仅能存放一件产品的缓冲器。生产者各自生产不同的产品,消费者各自取自己需要的产品。利用P、V操作编程为:
猎手进程 农民进程 动物园进程 饭店进程
P(S) P(S) P(S1) P(S2)
放入虎 放入猪 买老虎 买猪
V(S1) V(S2) V(S) V(S)
信号量初值:S=1,S1=0,S2=0。
也可以将这四个进程用程序表示为:
begin
S,S1,S2:semaphoms
S=1,S1=O,S2=O;
parbegin
process hunter
begin
L1,have a tiger;
P(S);
put a tiger;
V(S1);
go to L1
end ;
process peasant
begin
L2,have a tiger;
P(S);
put a pig;
V(S2);
go to L2
end;
process hotel
begin
L3,P(S1);
get a pige;
V(S);
eat a pig;
go to L3
end ;
process zoo
begin
L4:P(S2);
get a tiger;
V(S);
eat a tiger;
goto L4;
end;
parend
end
25.有一阅览室,读者进入时必须先在一张表上进行登记。该表为每一座位列出一个表目(包括座号、姓名、阅览时间),读者离开时要撤消登记信息。阅览室有100个座位。
(1)为描述读者的动作,应编写几个程序,应设置几个进程?程序和进程之间的对应关系如何?
(2)试用P、V操作描述这些进程间的同步关系。
解:(1)在本题中,每个读者都可视为一个进程,有多少读者就有多少进程。这些进程称为读者进程,设为Pi(i=0,1,…)。读者进程Pi执行的程序包括:登记、阅览和撤消。每个读者进程的活动都相同,所以其程序也相同。进程和程序的关系是z各读者进程共用同一程序。
(2)在读者进程所执行的程序中,对登记和撤消都需互斥执行,其信号量的初值为1,而对进入阅览室也需互斥执行,其信号量为100。现用P、V操作描述如下:
读者进程Pi(i=0,1,2,…)
P(S1)
P(S2)
登记
V(S2)
阅览
P(S2)
撤消
V(S2)
V(S1)
其中信号量S1的初值为100,信号量S2的初值为1。
3.4自测题
3.4.1 基本题一、判断题(正确的在括号中记√,错误的记×)
1.进程是一段独立的程序。 ( )
2.单独的并发语句可以完成模拟所有的优先图的功能。 ( )
3,P.V操作中信号量的值，永远代表着某类可用资源的数量。 （ ）
4.管程、条件临界域和信号量三者在用它们实现同步问题的意义下是等价的。 ( )
5.在引入线程的操作系统中,线程是资源分配和调度的基本单位。 （ ）
6.在多处理机系统中,禁止中断不足以保证互斥。 ( )
7.一个进程正在临界区中间执行时,不能被中断。 （ ）
8.尽管管程确保了互斥,但其中的过程必须是再人式的。 ( )
9.在只提供用户级线程的多处理机系统中,一个进程最多仍只能获得一个CPU。 ( )
10.操作系统对进程的管理和控制主要是通过PCB来实现的。 ( )
二单项选择题，在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者该题无分。
1.在进程管理中,当________时,进程从阻塞状态变为就绪状态。
A进程被进程调度程序选中 B.等待某一事件 C.等待的事件发生 D.时间片用完
2.建立进程就是____。
A.建立进程的目标程序 B.为其建立进程控制块
C.建立进程及其子孙的进程控制块 D.将进程挂起
3.分配到必要的资源并获得处理机时的进程状态是______。
A.就绪状态 B.执行状态 C.阻塞状态 D.撤消状态
4.在操作系统中,P、V操作是一种_______。
A.机器指令 B.系统调用命令 C.作业控制命令 D.低级进程通讯原语
5.在消息缓冲通信中，消息队列属于_________资源。
A.临界 B.共享 C.永久 D.可剥夺
6.对进程的管理和控制使用__________。
A.指令 B.原语 C.信号量 D.信箱通信
7.在操作系统中,进程是一个具有一定独立功能的程序在某个数据集上的一次______。
A.等待活动 B.运行活动 C.单独操作 D.关联操作
8.若P、V操作的信号量S初值为2,当前值为-1,则表示有_______等待进程。
A.0个 B.1个 C.2个 D.3个
9.下面对进程的描述中,错误的是__________。
A.进程是动态的概念 B.进程执行需要处理机
C.进程是有生命期的 D.进程是指令的集合
10.如果有三个进程共享同一互斥段,而且每次最多允许两个进程进入该互斥段,则信号量的初值应设置为
A.3 B.1 C.2 D.0
11.下列的进程状态变化中,____________变化是不可能发生的。
A.运行→就绪 B.运行→等待
C.等待→运行 D.等待→就绪
12.一个运行的进程用完了分配给它的时间片后,它的状态变为__________。
A.就绪 B.等待 C.运行 D.由用户自己确定
13.用V操作唤醒一个等待进程时,被唤醒进程的状态变为_______。
A.等待 B.就绪 C.运行 D.完成
14.临界区是_____________。
A.一段共享数据区 B.一个缓冲区
C.一段互斥执行的程序段 D.一个互斥资源
15.进程间的同步是指进程间在逻辑上的相互__________关系。
A.联接 B.制约 C.继续 D.调用
16信箱通信是一种__________通信方式。
A.直接通信 B.间接通信 C.低级通信 D.信号量
17._______________是一种只能进行P操作和V操作的特殊变量。
A.调度 B.进程 C.同步 D.信号量
18.操作系统通过_____________对进程进行管理。
A.进程 B.进程控制块 C.进程启动程序 D.进程控制区
19.下面所述步骤中,__________不是创建进程所必需的。
A.由调度程序为进程分配CPU B.建立一个进程控制块
C.为进程分配内存 D.将进程控制块链入就绪队列
20.多道程序环境下,操作系统分配资源以__________为基本单位。
A.程序 B.指令 C.进程 D.作业三．多项选择(在每小题的五个备选答案中选出二至五个正确答案，并将其代码写在题干后面的括号内。不选、错选、多选或少选者，该题无分)。
1.进程的特征有___________。
A.动态性 B.静态性 C.并发性 D.独立性 E.异步性 F.结构特性
2.有关进程的描述中正确描述是______________。
A.进程执行的相对速度不能由进程自己来控制
B.P、V操作都是原语操作
C.利用信号量的P、V操作可以交换大量信息
D.同步是指并发进程之间存在的一种制约关系
E.并发进程在访问共享资源时,不可能出现与时间有关的错误
3.进程间的通信方式有______________。
A.共享存储器 B.事件触发 C.消息传递 D.过程调用 E.信箱通信
4.用于解决进程间互斥的方法是_________。
A.信号量及P、V操作 B.加锁与开锁 C.信箱方式 D.消息缓冲方式 E.特权指令方式
5.进程主要由_________组成.
A.程序段 B.JCB C.数据段 D.PCB E.消息
6.对临界区的正确论述是__________。
A.临界区是指进程中用于实现进程互斥的那段代码
B.临界区是指进程中用于实现进程同步的那段代码
C.临界区是指进程中用于实现进程通信的那段代码
D.临界区是指进程中用于访问共享资源的那段代码
E.临界区是指进程中访问临界资源的那段代码
F.若进程A与进程B必须互斥地进入自己的临界区,则进程A处于对应的临界区内时,仍有可能被进程B中断
7.正确的叙述是____________。
A.操作系统的一个重要概念是进程,不同进程所执行的代码也不同
B.操作系统通过PCB来控制和管理进程,用户进程可从PCB中读出与本身运行状态相关的信息
C.当进程由执行状态变为就绪状态时,CPU现场信息必须被保存在PCB中
D.当进程申请CPU得不到满足时,它将处于阻塞状态
E.进程是可与其他程序并发执行的程序在一个数据集合上的运行过程,所以程序段是进程存在的惟一标志
8.正确的叙述是________________。
A.一个进程的状态发生变化总会引起其他一些进程的状态发生变化
B.进程被挂起(suspend)后,状态变为阻塞状态
C.信号量的初值不能为负数
D.线程是CPU调度的基本单位,但不是资源分配的基本单位
E.在进程对应的代码中使用P、V操作后,可以防止系统发生死锁
F.管程每次只允许一个进程进入
G.P、V操作可以解决一切互斥问题
H.程序的顺序执行具有不可再现性
四、填空题
1.进程映象通常包括______、______、______和_______。其中,______含有进程的描述信息和控制信息,是进程映象中最关键的部分.
2.信号量的物理意义是当信号量值大于零时表示_____;当信号量值小于零时,其绝对值为__________。
3.临界资源的概念是________,而临界区是指______________。
4.系统中各进程之间逻辑上的相互制约关系称为________。
5.若一个进程已进入临界区,其他欲进入临界区的进程必须______。
6．将进程的_______链接在一起就形成了进程对列。
7.用P、V操作管理临界区时,任何一个进程在进入临界区之前应调用________操作，退出临界区时应调用____________操作。
8.用信箱实现通信时,应有__________和__________两条基本原语。
9.在多道程序系统中,进程之间存在着的不同制约关系可以划分为两类：_____与_________。___________指进程间具有的一定逻辑关系:__________是指进程间在使用方面的约束关系。
10.程序顺序执行时有顺序性、__________和可再现性的特点。
11.进程是一个__________态概念,而程序是一个__________态概念。
12.在一个单处理机系统中,若有5个用户进程,且假设当前时刻为用户态就绪状态的用户进程最多有________个,最少有________个。
13.操作系统中,对信号量S的P原语操作定义中,使进程进入相应等待队;条件是_____。
14.当处理机空闲时,进程调度程序从_____________中选出一个进程执行。
15.优先图展示了语句间的一种_________关系,而进程图展示的是进程的______关系。
五．简答题
1.在单机操作系统中,进程如何用信箱进行相互之间的通信?
2.什么是原语?原语的主要特点是什么?
3.何谓纯代码?它的主要用途是什么?
4.程序的并行执行将导致运行结果失去封闭性,这对所有的程序都成立吗?
5.什么是线程?进程和线程是什么关系?
6.如何保证进程互斥地访问临界资源?
7.何谓"忙等"?它有什么缺点?
8.为什么进程对临界资源的访问必须互斥?
3.4.2 解析题一．论述题
1.试比较进程与程序的异同
2.什么是临界段?什么是临界段问题?并列举出Dijstra在解决临界段问题时所施加的制约。
3.在生产者一消费者问题中,如果将两个P操作,即P(full)和V(mutex)互换位置,或者P(empty)和P(mutex)互换位置,其后果如何?如果将两个V操作,即V(full)和V(mutex)互换位置,或者V(empty)和V(mutex)互换位置,其后果又如何?
4.在单处理机的分时系统中,分配给进程P的时间片用完后,系统进行切换,结果调度到的仍然是进程P。有可能出现上述情形吗?如果可能请说明理由。
5.有三个进程P1,P2和P3并发工作。进程P1需用资源S3和S1;进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答:
(1)若对资源分配不加限制,会发生什么情况?为什么?
(2)为保证进程正确工作,应采用怎样的资源分配策略?为什么?
6.试比较直接通信方式和间接通信方式。
7.试从调度性、并发性、拥有资源及系统开销方面,对进程和线程进行比较。
8.试说明管程和进程有何异同点?
9.什么叫临界资源?什么是临界段?在解决临界段问题时必须遵循哪些原则?
10.一组除开信号量外不可能共享任何变量的顺序进程可以彼此通信吗?
二，算法题
1.某车站售票厅,最多可容纳20名购票者进入,当售票厅中少于20名购票者时,其厅外的购票者可立即进入,否则,需在外面等待.若把一个购票者看作一个进程,请回答下列问题:
(1)写出用P/V操作管理这些并发进程时信号量的初值以及信号量的各种取值的含义。
(2)根据所定义的信号量,把应执行的P/V操作填人下述方框中,以保证进程能够正确地并发执行。
procedure Pi (i=1,2,…);
begin
|①|
进入售票厅;
购票;
退出售票厅;
|②|
end ;
begin
parbegin
Pi (i=1,2,…)
parend
end.
(3)若欲购票者最多为n个人,试写出信号量取值的可能的变化范围(最大值和最小值).
2.设有两个生产者进程A、B和一个销售者进程C,他们共享一个无限大的仓库,生产者每次循环生产一个产品,然后入库供销售者销售:销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库,也不允许边入库边出库；而且要求生产和销售A产品和B产品的件数都满足以下关系：-n≤A的件数-B的件数≤≤m,其中n、m是正整数。请用信号量机制写出A、B、C三个进程的工作流程。
3.考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷。做-支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料,但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并抽烟,且在做完后给经销商发信号,然后经销商再拿出两种原料放在桌上,如此反复。试设计一个同步算法来描述他们的活动。
4.在测量控制系统中,数据采集任务把所采集的数据送入一单缓冲区:计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。
5．桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。
6.哲学家甲请哲学家乙、丙、丁到某处讨论问题,约定全体到齐后开始讨论:在讨论的间隙四位哲学家进餐,每人进餐时都需使用刀、叉各一把。请用信号量及P、V操作说明这四位哲学家的同步、互斥过程。
7.某数据库有一个写进程,多个读进程,它们之间读、写操作的互斥要求是:写进程正在写该数据库时不能有其他进程读该数据库,也不能有其他进程写该数据库:读进程之间不互斥,可以同时读该数据库。请用信号量及P、V操作描述这一组进程的工作过程。
8.有三个进程PA、PB和PC合作解决文件打印问题:PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录:PB将缓冲区1的内容复制到缓冲区2,每执行一次复制一个记录:PC将缓冲区2的内容打印出来,每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。
9.有一个仓库,可以存放A和B两种产品,但要求:
(1)每次只能存入一种产品(A或B);
(2)-N<A产品数量-B产品数量<M。
其中,N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。
10.进程A1,A2,…An1通过m个缓冲区向进程B1,B2,…Bn2不断地发送消息。发送和接收工作遵循如下规则：
①每个发送进程一次发送一个消息,写入一个缓冲区,缓冲区大小等于消息长度；
②对每一个消息,酌,Bp…,Bn2都须各接收一次,读入各自的数据区内；
③m个缓冲区都满时,发送进程等待;没有可读的消息时,接收进程等待。
试用P、V操作组织正确的发送和接收工作。
11.在南开大学和天津大学之间有一条弯曲的小路,其中从S到T一段路每次只允许一辆自行车通过,但其中有一个小的安全岛M(同时允许两辆自行车停留〉,可供两辆自行车己从两端进入小路情况下错车使用,如图2.14所示。试设计一个算法使来往的自行车均可顺利通过。
3.5 自测练习答案一．判断题：
1.2.3.4.5.6.7.8.9.10.
二．单项选择题
1.C 2.B 3.B 4.D 5.A 6.B 7.B 8.B 9.D 10.A
11.C 12.A 13.B 14.C 15.B 16.B 17.D 18.B 19.A 20.C
三．多项选择题
1.A C D E F 2,A B D 3,A C E 4.A B 5.A C D 6.E F 7.C
8.C D F G
四．填空题
1,用户程序 用户数据 系统栈和进程控制块 进程控制块
2.可用资源的数目 因请求该资源而被阻塞的进程数目
3,一次仅允许一个进程访问的资源 程序中访问临界资源的那段程序代码
4.进程同步
5．等待 6.PCB 7.P V 8.发送 接收 9.同步 互斥 同步 互斥
10.封闭性 11.动 静 12.4 O 13,S < O 14.就绪队列中 15,优先 家族五．简答题
1.答.在单机操作系统中,可以使用信箱实现两个进程之间的通信。
在操作系统中,一个进程要与另一个进程进行通信,接收消息的进程必须为自己创建一个信箱。
进程调用send原语发送信件前必须组织好信件，然后调用send原语,并在调用时给出参数:信箱名和信件内容或信件存放起始地址。同样,接收进程也要调用receive原语,给出参数:信箱名和信件取出后的存放地址。通信原语的形式是:
send(boxname,msg)
receive (boxname,msg)
2.答：原语是指由若干条机器指令构成的,并用以完成特定功能的一段程序。这段程序在执行期间是不可分割的。其主要特点是不可分割性。
3.答：纯代码是能够被多个进程共享的程序段,代码不因程序的执行而改变,又称为重入码。纯代码的主要作用就是可被多个程序共享。并不是所有的程序段都是可被多个进程共享的,非可重入码被多个进程共享时可能出现错误。
4.答：并不是所有程序的并行执行都会导致运行结果失去封闭性。例如,当程序中都使用内部变量,不可能被外部程序访问时,程序的运行不会受到外部环境的影响。
5.答,线程可定义为进程内的一个执行单位,或者定义为进程内的一个可调度的实体。
在具有多线程机制的操作系统中,处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程,而且至少有一个可执行线程。
进程和线程的关系是:
①线程是进程的一个组成部分;
②进程的多线程都在进程的地址空间活动z
③资源是分给进程的,而不是分给线程的。线程在执行中需要资源时,系统从进程的资源配额中扣除并分配给它;
④处理机调度的基本单位是线程,线程之间竞争处理机,真正在处理机上运行的是线程;
⑤线程在执行过程中,需要同步。
6.答:为了互斥地访问临界资源,系统必须保证进程互斥地进入临界区。为此,必须在临界区前增加一段称作进入区的代码,以检查是否有其他进程已进入临界区使用临界资源,若有,则进程必须等待:否则,允许进程进入临界区,同时设置标志表示有进程正在临界区内。同样,在临界区后必须增加一段称作退出区的代码,用于将已有进程进入临界区访问临界资源的标志改为无进程进入临界区使用临界资源。进入区、退出区具体可用多种同步机制实现,如锁、信号量机制等。
7.答:所谓"忙等"是指"不让权"的等待,即进程因某事件的发生而无法继续执行时,它仍占有CPU,并通过不断地执行循环测试指令来等待该事件的完成。
"忙等"的主要缺点是浪费CPU的时间,另外,它还可能引起预料不到的后果。考虑某个采取高优先权优先调度原则的系统,目前有两个进程A和B共享某个临界资源,A的优先权较高,B的优先权较低,且B己处于临界区内,而A欲进入自己的临界区,则A、B都不可能继续向前推进,陷入"死等"状态。
8.答:临界资源本身的特性决定了它们只能被诸进程互斥地访问,如果并发执行的多个进程同时访问临界资源,将会造成系统的混乱或程序执行结果的不确定性,这样,用户得到的便可能是不希望得到的或者是不正确的处理结果。如果多个用户同时使用同一台打印机,则将使他们的输出结果交织在一起,而难于区分:又如两个用户使用程序段:
mov ax,(counter)
inc ax
mov (counter),ax
对初值为0的共享变量counter进行计数(加1)操作,则最终counter的值可能是正确的结果2,也可能是错误的结果1,即计算结果出现了不确定性。
（一）论述题
1.答:进程和程序是紧密相关而又完全不同的两个概念。
(1)每个进程实体中包含了程序段和数据段这两个部分,因此说进程与程序是紧密相关的。但从结构上看,进程实体中除了程序段和数据段外,还必须包含一个数据结构,即进程控制块PCB。
(2)进程是程序的一次执行过程,因此是动态的:动态性还表现在进程由创建而产生、由调度而执行、由撤消而消亡,即它具有二定的生命周期。而程序则只是一组指令的有序集合,并可永久地存放在某种介质上,其本身不具有运动的含义,因此是静态的。
(3)多个进程实体可同时存放在内存中并发地执行；其实这正是引入进程的目的。而程序(在没有为它创建进程时)的并发执行具有不可再现性,因此程序不能正确地并发执行。
（4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序(在没有为它创建进程时)不具有PCB,所以它是不可能在多道程序环境下独立运行的。
（5）进程与程序不一一对应。同一个程序的多次运行,将形成多个不同的进程:同一个程序的一次执行也可以产生多个进程(如UNIX中通过fork调用):而一个进程也可以执行多个程序(如UNIX中通过exec调用)。
2.答：临界段就是一次仅允许一个进程执行的程序段.临界段问题是指设计一种算法,以允许一次至多只有一个进程进入临界段且不产生死锁。Dijkstra在解决临界段问题时所施加的制约有:
(1)进程的同时执行等价于它们按一种不知道的次序顺序执行；
(2)进程的执行速度是彼此无关的；
(3)位于非临界段的进程不可能防止其他进程进入临界段；
(4)选择并允许一个进程进入临界段的决策不可能被无限期地推迟。
3.答:在生产者一消费者问题中,如果将两个P操作,即P(full)和P(mutex)互换位置,或者P(empty)和P(mutex)互换位置,都可能引起死锁。考虑系统中缓冲区全满前时,若一生产者进程先执行了P(mutex)操作并获得成功,当再执行P(empty)操作时,它将因失败而进入阻塞状态,它期待消费者执行V(empty)来唤醒自己,在此之前,它不可能执行V(mutex)操作,从而使企图通过P(mutex)进入自己的临界区的其他生产者和所有的消费者进程全部进入阻塞状态,从而引起系统死锁。类似地,消费者进程若先执行P(mutex),后执行P(full),同样可能造成死锁。
V(full)和V(mutex)互换位置,或者V(empty)和V(mutex)互换位置,则不会引起死锁,其影响只是使临界资源的释放略为推迟一些。
4.答:有可能出现上述情况。例如,若在进程P时间片用完后,被迫回到就绪队列时,就绪队列为空,这样进程P就是就绪队列中惟一的一个进程,于是调度程序选中的进程必是进程P；又如在按优先级调度的系统中,就绪队列按进程优先级排列,在进程P时间片用完之后回到就绪队列时,若其优先级高于当前就绪队列中的其他进程程,则它将排在就绪队列之首,从而再次被调度程序选中并投入运行。
5.答：(1)可能会发生死锁现象。例如,进程P1,P2和P3分别获得资源S3,S1和S2后再继续申请资源时都要等待,这是循环等待。
(2)可有几种答案:
①采用静态分配,由于执行前已获得所需的全部资源,故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。
②采用按序分配,不会出现循环等待资源现象。
③采用银行家算法,在分配时,保证了系统处于安全状态。
6.答:可从以下几个方面来比较直接通信方式和间接通信方式:
(1)发送和接收原语。直接通信原语通常为send(receiver,mssage)、receive(sender,
message);间接通信原语通常为send(mailbox,message)、receive(mailbox,message),而且它还需要提供布关信箱创建和撤消的原语。
(2)提供对方的标识符。直接通信要求发送双方显式地提供对方的标识符,对接收进程,量如果允许它同时接收多个进程发来的消息,则接收原语中的发送进程标识符可以是通信完成后返回的值:间接通信则不要求它们显式地提供对方的标识符,而只需提供信箱标识。
(3)通信链路。直接通信时,进程只需提供对方的标识符便可进行通信,在收发双方之间建立通信链路由系统自动完成,并且在收发双方之间有且仅有一条遁信链路;间接通信时,仅当一对进程共享某个信箱时,它们之间才有通信链路,顶且一条链路可对应多个进程,每对进程间也可以有多条链路。
(4)实时性。直接通信通常只能提供实时通注1间接通信方式'则既可实现实时通信,也可实现非实时通信。
7.答:进程和线程之间在调度性、并发性、拥有资源及系统开销方面的比较如下:
(1)调度性：在传统的操作系统中,拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的os中,则把线程作为调度和分派的基本单位,而把进程作为资源拥有的基本单位。
(2)并发性：在引入线程的os中,不仅进程间可以并发执行,而且在一个进程的多个线程间也可以并发执行,因而它比传统的os具有更好的并发性。
(3)拥有资源：在这两种os中,拥有资源的基本单位都是进程。线程除了一点在运行中必不可少的资源(如线程控制块、程序计数器、一组寄存器值和堆核)外,本身基本不拥有系统资源,但它可访问其隶属进程的资源。
(4)开销：由于创建或撤消进程时,系统都要为之分配和回收资源,如内存空间和I/O设备等:进程切换时所要保存和设置的现场信息也要明显地多于线程,因此,os在创建、撤消和切换进程时所付出的开销将明显地大于线程。另外,由于隶属于同一个进程的多个线程共享同一地址空间和该进程的所有己打开文件,从而使它们之间的同步和通信的实现也比进程更方便。
8.解:管程和进程的异同点是:
(1)二者都定义了数据结构,进程定义的是私有数据结构PCB,管程定义的是公共数据结构,如消息队列；
(2)二者都在各自的数据结构上进行有意义的操作。进程是由顺序程序执行有关操作,管程主要是同步操作和初启操作；
(3)二者设置的目的不同,进程是为了更好地刻画可实现系统的并发性而设置的,管程是为了解决进程的公共变量,为了解决共享资源的互斥使用问题而设置的；
(4)进程通过调用管程中的过程对共享变量实行操作,此时该过程就如通常的子程序一样被调用而处于被动工作方式,因此称管程为被动成分.与此相对应的进程则处于主动工作方式而被称为主动成分；
(5)由于进程是主动成分,故进程之间能被并发执行,然而管程是被动成分,管程和调用它的进程不能并发；
(6)进程可由"创建"而诞生,由"撤消"而消亡,有生命期,管程是操作系统中固有成分,无需进程创建,也不能为进程所撤消,只能被进程调用。
9.解:在计算机系统中,同时有许多进程,它们共享着各种资源,然而,有许多资源一次却仅能为一个进程所使用.把一次仅允许一个进程使用的资源称为临界资源.例如,物理设备属于临界资源,如打印机、磁带机、输入机等.除了物理设备外,还有很多变量、数据、表格、队列等也都是由若干进程所共享的资源。进程访问共享临界资源的一段程序,叫做临界段.为了防止两个进程同时进入临界段内,必须互斥,即保证每次至多有一个进程进入临界段,通常应遵循下列原则:
(1)当有若干进程欲进入其临界段时,在有限时间内有一进程进入.换言之,它们不应互相阻塞而致使彼此都不能进入临界段；
(2)每次至多有一个进程处于临界段；
(3)进程仅在临界段内逗留有限的时间。
10.解:不能。一进程只可能执行P或V操作,V操作不影响执行它的进程,因此,进程不能从V操作得到任何信息。若一个P操作成功,执行该P操作的进程无法得知它是立即成功还是延迟一段时间后才成功。若该P操作从未成功(因无对应的V操作),那么,执行它的进程就挂起而且不可能做任何事。
（二）、算法题
1,答：(1)定义一个信号量S,其初值为20,s取值的含义如下:
S 〉O S的值表示可继续进入售票厅的人数
S =0 表示售票厅中已有20名顾客(购票者)
S <O |S|的值为等待进入售票厅的人数
(2)①P(S) ②V(S)
(3)S的最大值为20,S的最小值为20-n.
2.分析：本题中存在着以下的同步和互斥关系:①生产者A、B和消费者C之间,不能同时将产品入库和出库,故仓库是一个临界资源.②两个生产者之间必须进行同步,当生产的A、B产品的件数之差大于等于m时,生产者A必须等待;小于等于-n时,生产者B必须等待。③生产者和销售者之间也必须进行同步,只有当生产者生产出产品并入库后,销售者才能进行销售;而且由于销售的产品件数必须满足关系:-n≤A的件数-B的件数≤≤m,因此当销售的A、B产品的件数之差大于等于m而仓库中已无B产品时,或者销售的A、B产品的件数之差小于等于-n而仓库中已元A产品时,销售者C也都必须等待。
答:为了互斥地入库和出库,需为仓库设置一初值为1的互斥信号量mutex;为了使生产的产品件数满足:-n≤A的件数-B的件数≤m,需设置两个同步的信号量,其中SAB表示当前允许A生产的产品数量,其初值为m; SBA表示当前允许B生产的产品数量,其初值为n;另外,还需设置一个整数difference表示所销售的A、B产品的数量差,而为了同步生产者和销售者并使销售的A、B产品的件数满足关系:-n≤A的件数-B的件数≤m,还需设置三个资源信号量,其中S对应于仓库中总的产品量,SA对应于仓库中的A产品量,SB对应于仓库中的B产品量,它们的初值都为0。具体的同步算法如下:
Var difference:integer:=0:
SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,O,0,0,1;
begin
parbegin
process A:begin
repeat
P(SAB);
produce a product A;
V(SBA);
P(mutex);
add the product A to tile storehouse:
V(mutex);
V(SA);
V(S);
until false;
end
process B:begin
repeat
P(SBA);
produce a product B ;
V(SAB);
P(mutex);
add the product B to the storehouse;
V(mutex);
V(SB);
V(S);
until false;
end
process C:begin
repeat
P(S);
if difference〈=-n then begin
P(SA);
P(mutex);
take a product A from storehouse;
Vl(mutex);
difference:=difference+1;
end
else if difrerence 〉=m then begin
P(SB);
P(mutex);
take a product B from storehouse;
V(mutex);
difference:=difference-1;
end
else begin
P(mutex);
take a product A or B from storehouse;
V(mutex);
if(product_type=A) then begin /*取的是A产品*/
P(SA);
difference:=difference+1;
end
else begin /*取的是B产品*/
P(SB);
difference:=difference-1;
end
sell the product;
until false;
end
parend
end
3.答：共享数据结构是:
var a:array[0..2] of semaphore; {初值=0}
agent:semaphore; {初值=1}
关于经销商的代码段:
repeat
Set i,j to a value between O and 2;
P(agent);
V(a[i]);
V(a[j]);
Until false;
分别用整型量r和S表示每个抽烟者进程所需要的两种原料(r和S在0~2间取值),那么,抽烟者进程的代码段为:
repeat
P(a[r]);
P(a[s]);
"smoke"
V(agent);
until false;
4.分析：在本题中采集任务与计算任务共用一个单缓冲区。当采集任务采集到一个数据后,只有当缓冲区为空时才能将数据送入缓冲区中存放,否则应等待缓冲区腾空;当缓冲区中有数据时,计算任务才能从缓冲区中取出数据进行计算,否则也应等待。
本题实际上是一个生产者-消费者问题。将生产者-消费者问题抽象出来,以另外一种形式描述是一种常见的试题形式。只要对生产者-消费者问题有了深入的理解,就不难解决此类试题。
解:在本题中,应设置两个信号量S五Se,信号量Sf表示缓冲区中是否有可供打印的计算结果,其初值为0:信号量Se用于表示缓冲区有无空位置存放新的信息,其初值为1。
本题的同步描述如下:
int Se=1;
int Sf=0;
main()
{
parbegin
get ():
compute(〉:
parend
}
get ( )
{
while (采集工作未完成)
{
采集一个数据:
p(Se);
将数据送入缓冲区中;
v(Sf);
}
}
compute()
{
while (计算工作未完成)
{
p(Sf);
从缓冲区中取出数据;
v(Se);
进行数据计算;
}
}
5.分析:在本题中,爸爸、儿子、女儿共用一个盘子,且盘中一次只能放一个水果。当盘子为空时,爸爸可将一个水果放入采盘中。若放入果盘中的是桔子,则允许儿子吃,女儿必须等待;若放入果盘中的是苹果,则允许女儿吃,儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里,生产者放入缓冲区的产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。
解:在本题中,应设置三个信号量S、So、Sa,信号量S表示盘子是否为空,其初值为1；信号量So表示盘中是否有桔子,其初值为0；信号量Sa表示盘中是否有苹果,其初为0。同步描述如下：
int s=1;
int Sa=0;
int S0=0;
main( )
cobegin
father( );
son ( );
dauduer( );
coend
}
father ( )
{
while (1)
{
p(S);
将水果放入盘中:
if(放入的是桔子〉v(So);
else v(Sa);
}
}
son ( )
{
while(1)
{
p(So);
从盘中取出桔子;
v(S);
吃桔子；
}
}
daughter( )
{
while(1)
{
p(Sa);
从盘中取出苹果:
v(S);
吃苹果;
}
}
6.分析:在本题中这四位哲学家在讨论问题期间的生活方式为交替地进行讨论和进餐。由于刀、又资源均为2,而哲学家有四位,这就会出现资源竞争,为此应对他们的进餐进行同步控制。在本题解法中规定:所有哲学家先申请使用刀,申请到刀后再申请使用叉,刀、又都拿到后才能进餐.本题是标准的哲学家进餐问题。只是在哲学家人数、进餐用具方面与经典哲学家进餐问题略有不同。
解:在本题中,应设置四个信号量forkl、fork2、knife1、knife2,其初值均为1,分别表示资源叉1、叉2、刀1、刀2是否可用。同步描述如下:
int fork1=1;
int fork2=1;
int knifel=1;
int lq1ife2=1;
main( )
{
cobegin
Pa( ); /*分别用进程Pa、pb、Pc、Pd代表哲学家甲、乙、丙、丁的活动*/
Pb( );
Pc( );
Pd( );
Coend
}
Pa( )
{
while(1)
{
p(knife1);
p(fork1);
进餐;
v(knife1);
v(forkl);
讨论问题;
}
}
Pb ( )
{
while(1)
{
p(knife2);
p(fork1);
进餐;
v(knife2);
v〈forkl);
讨论问题;
}
}
Pc( )
{
while(1)
{
p(knife2);
p(fork2);
进餐;
v(knife2);
v(fork2);
讨论问题;
}
}
Pd( )
{
while(1)
{
p(knifel);
p(fork2);
进餐;
v(knife1);
v(fork2);
讨论问题;
}
}
7.答:在本题中,允许读进程同时读数据库,但写进程正在写数据库时不允许其他进程读数据库,也不允许其他进程写该数据库。为了解决读、写进程之间的同步,应设置两个信号量和一个共享变量;读互斥信号量mutex,用于使读进程互斥地访问共享变量count,其初值为1:写互斥信号量wmutex,用于实现写进程与读进程的互斥及写进程与写进程的互斥,其初值为1:共享变量count,用于记录当前正在读数据库的读进程数目,初值为0。其工作过程如下:
int mutex=1;
int wmutex=1;`
int count=0;
main()
{
cobegin
reader( );
writer( );
coend
}
reader( )
{
while(1)
{
p(mutex);
if(count==O〉p(wmutex);:/*当第一个读进程读数据库时,阻止写进程写*/
count ++;
v(mutex);
读数据库;
p(rmutex)
count - -;
if(count=0) v(wmutex); /*当最后一个读进程读完数据库时,允许写进程写*/
v(rmutex);
}
}
writer( )
{
while(1)
{
p(wmutex);
写数据库;
v(wmutex);
}
}
在本题中,要注意对信号量rmutex意义的理解。rmutex是一个互斥信号量,用于使读进程互斥地访问共享变量count。该信号量并不表示读进程的数目,表示读进程数目的是共享变量count。当一个读进程要读数据库时,应将读进程计数count增加1:如果此前(count加1以前)数据库中无读进程,还应对写互斥信号量wmutex做p操作,这样,若数据库中无写进程,则通过p操作阻止写进程写,若数据库中有写进程,则通过p操作让读进程等待。同理,当一个读进程完成读数据库操作时,应将读进程计数count减少1;如果此时(count减1以后〉数据库中已无读进程,还应对写互斥信号量wmutex做v操作,以允许写进程写。
8.答:在本题中,进程PA、PB、PC之间的关系为:PA与PB共用一个单缓冲区,而PB又与PC共用一个单缓冲区,其合作方式可用图2.12表示。当缓冲区1为空时,进程PA可将一个记录读入其中;若缓冲区1中有数据且缓冲区2为空,则进程PB可将记录从缓冲区1复制到缓冲区2中;若缓冲区2中有数据,则进程PC可以打印记录。在其他条件下,相应进程必须等待。事实上,这是一个生产者·消费者问题。
为遵循这一同步规则。应设置四个信号量empty1、empty2、full1,full2,信号量emptyl
及empty2分别表示缓冲区1及缓冲区2是否为空,其初值为1;信号量full1及full2分别表示缓冲区1及缓冲区2是否有记录可供处理,其初值为0。其同步描述如下:
int empty1=1;
int empty2=1;
int full1=0;
int full2=0;
main( )
{
cobegin
PA( );
PB( );
PC( );
Coend
}
PA( )
{
while(1)
{
从磁盘读一个记录:
p(empty1);
将记录存入缓冲区1
V(full);
}
}
PB( )
{
while(1)
p(full);
从缓冲区1中取出记录:
v(emptyl);
p(empty2);
将记录存入缓冲区2:
V(full2);
}
}
PC( )
{
while(1)
{
p(full2);
从缓冲区2中取出记录;
v(empty2);
打印记录;
本题也是一个典型的生产者·消费者问题。其中的难点在于PB既是一个生产者又是一个消费者。
}
9.分析：本题给出的第一个条件是1!各界资源的访问控制,可用一个互斥信号量解决该问题。第二个条件可以分解为:
-N<A产品数量一B产品数量
A产品数量一B产品数量<M
也就是说,A产品的数量不能比B产品的数量少N个以上,A产品的数量不能比B产品的数量多M个以上。
解:在本题中,我们可以设置两个信号量来控制A、B产品的存放数量,sa表示当前允许A产品比B产品多入库的数量,即在当前库存量和B产品不入库的情况下,还可以允许sa个A产品入库:sb表示当前允许B产品比A产品多入库的数量,即在当前库存量和A产品不入库的情况下,还可以允许sb个B产品入库。初始时,sa为M-1,sb为N一1。当往库中存放入一个A产品时,则允许存入B产品的数量也增加1:当往库中存放入一个B产品时,则允许存入A产品的数量也增加1。
产品A、B的入库过程描述如下:
int mutex=1; /*互斥信号量*/
int sa=M-1;
int sb=N-1;
main( )
{
while(1)
{
取一个产品;
if (取的是A产品)
{
p(sa);
p(mutex);
将产品入库;
v(mutex);
v(sb);
}
else /*取的产品是B*/
{
p(sb);
p(mutex);
将产品入库;
v(mutex);
v(pa);
}
}
}
从本题的解法可以看出,当有比较复杂条件出现时,可以把复杂条件分解成一组简单,这样就能很容易地写出对应的程序流程了。
10.分析：本题是生产者-消费者问题的一个变形,一组生产者A1,A2,…An1和一组消费者B1,B2,…,Bn2共用m个缓冲区,每个缓冲区只要写一次,但需要读n2次.因此,我们可以把这一组缓冲区看成n2组缓冲区,每个发送者需要同时写n2组缓冲区中相应的n2个缓冲区,而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。
解：在本题中,应设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组empty[n2]和full[n2]描述n2组缓冲区的使用情况。mutex的初值为1;数组empty中元素初值为m；数组full中的元素初值为0。其同步关系描述如下:
int mutex,empty[n2],full[n2];
int 1;
mutex=1;
for(i=O;i<=n2-1;i++)
{
empty[i]=m;
full[i]=0;
}
main( )
{
cobegin
Al( );
A2( );
An1( );
B1( );
B2( );
Bn2( );
Coend
}
send( ) /*发送消息*/
{
int i;
for (i=O;i<=n2-1; i++)
p(empty[i]);
p(mutex);
将消息放入缓冲区;
v(mutex);
for(i=0;i<=n2-1;i++)
v(full[i]);
}
receive (i) /*进程Bi接收消息*/
{
p(full[i]);
p(mutex);
将消息从缓冲区取出;
v(mutex);
v(empty[i]);
}
Ai( ) /*因发送进程A1,A2,…,An1的程序类似,这里只给出进程Ai的描述.*/
{
while(1)
{
send( );
}
}
Bi() /*因接收进程B1,B2,…,Bn2的程序类似,这里只给出进程Bi的描述.*/
{
while(1)
{
receive(i);
}
}
11.分析：在本题中,需要控制路段T到L,路段S到K及安全岛M的使用。路段T到L及路段S到K同时只允许一辆自行车通过,而安全岛M允许两辆自行车使用,因此可以用三个信号量来管理它们.另一方面,同一方向上的自行车最多只能有一辆通过这段路(两个方向上有两辆),因此还应该用两个信号量来控制.
解:在本题中,应设置5个信号量ST,TS,K,L,M,信号量ST表示是否允许自行车从南开大学去天津大学,其初值为1;信号量TS表示是否允许自行车从天津大学去南开大学,其初值为1:信号量K表示是否允许自行车通过路段S到K,其初值为1;信号量L表示是否允许自行车通过路段T到L,其初值为1;信号量M表示安全岛上还可停放自行车的数目,其初值为2。其控制过程描述如下:
int ST=1;
int TS=1;
int k=1;
int L=1;
int M=2;
totian( ) /*从南开大学去天津大学*/
{
P(ST);
P(K);
从s走到K;
P(M);
进入安全岛;
V(K);
P(L);
从L走到T;
V(M);
V(L);
V(ST);
}
tonan( ) /*从天津大学去南开大学*/
{
P(TS);
P(L);
从T走到L;
P(M);
进入安全岛;
V(L);
P(K);
从K走到S;
V(M);
V(K);
V(TS);
}
