操作系统总复习及相关习题.doc

操作系统总复习及相关习题
第一章 引论
名词解释
1操作系统
操作系统是管理和控制计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。
2管态
当执行操作系统程序时，处理机所处的状态
3目态
当执行普通用户程序时，处理机所处的状态。
4多道程序设计
在这种设计技术下，内存中能同时存放多道程序，在管理程序的控制下交替的执行。这些作业共享CPU和系统中的其他资源。
5并发
是指两个或多个活动在同一给定的时间间隔中进行。它是宏观上的概念。
6并行
是指两个或多个活动在同一时刻同时执行的情况。
7吞吐量
在一段给定的时间内，计算机所能完成的总工作量。
8分时
就是对时间的共享。在分时系统中，分时主要是指若干并发程序对CPU时间的共享。
9实时
表示“及时”或“既时”。
10系统调用
是用户在程序中能以“函数调用”形式调用的、由操作系统提供的子功能的集合。每一个子功能称作一条系统调用命令。它是操作系统对外的接口，是用户级程序取得操作系统服务的唯一途径。
11特权指令
指指令系统中这样一些指令，如启动设备指令、设置时钟指令、中断屏蔽指令和清内存指令，这些指令只能由操作系统使用。
12命令解释程序
其主要功能是接收用户输入的命令，然后予以解释并且执行。
13脱机I/O
是指输入/输出工作不受主机直接控制，而由卫星机专门负责完成I/O，主机专门完成快速计算任务，从而二者可以并行操作。
14联机I/O
是指作业的输入、调入内存及结果输出都在cpu直接控制下进行。
15资源共享
是指计算机系统中的资源被多个进程所功用。例如，多个进程同时占用内存，从而对内存共享；它们并发执行时对cpu进行共享；各个进程在执行过程中提出对文件的读写请求，从而对磁盘进行共享等等。
简答题
1什么是操作系统？它的主要功能是什么？
答：操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。操作系统的主要功能有5个方面，即存储管理、处理机管理、设备管理、文件管理和用户接口。
2推动操作系统形成和发展的主要动力是什么？
答：推动操作系统发展的因素很多，主要可归结为两大方面：硬件技术更新和应用需求扩大伴随计算机器件的更新换代和计算机体系结构的发展，促使操作系统的性能和结构有了显著发展。 应用需求促进了计算机技术的发展，也促进了操作系统的不断更新升级。
3操作系统的基本特征是什么？
答：操作系统的基本特征是并发、共享和不确定。并发性是指两个或多个活动在同一给定的时间间隔中进行；共享是指计算机系统中的资源被多个进程所共用；不确定性是指系统中各种事件发生顺序的不可预测性。
4多道程序和多重处理有何区别？
答：多道程序是作业之间自动调度执行、共享系统资源，并不是真正的同时执行多个作业；而多重处理系统配置多个cpu，能真正同时执行多道程序。要有效使用多重处理，必须采用多道程序设计技术，而多道程序设计原则上不一定要求多重处理系统的支持。
5试说明多道程序设计和多任务系统之间的关系
答：多道程序设计是利用外设与cpu能够并行处理的特性，在主存同时存放多个程序，使之在系统中交叉地使用cpu，从而提高系统资源的利用率。而多任务系统主要指多进程交叉使用cpu。多道程序隐含了多任务处理，但多任务系统中不一定有多道程序。因为一个程序也可以采用多任务处理机制。
6不同类型的操作系统提供不同的功能。假定有如下的应用环境，请你为它们选择适合的操作系统。
（1）飞机的导航，（2）办公自动化系统，（3）航空订票系统，（4）复杂的科学计算，（5）图书检索系统
答：（1）飞机的导航系统，应采用硬实时操作系统
（2）办公自动化系统，应采用分时操作系统
（3）航空订票系统，应采用软实时操作系统
（4）复杂的科学计算，应采用批处理系统
（5）图书检索系统，应采用软实时操作系统
7什么是批处理系统，它有什么特征？
答：批处理系统：操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序自动依次处理。其主要特征是：用户脱机使用计算机、成批处理、多道程序运行。

8什么是分时系统，它有什么特征？
答：分时系统：把处理机的运行时间分成很短的时间片，按时间片轮转的方式，把处理机分配给各进程使用。其主要特征是：交互性、多用户同时性、独立性。

9什么是实时系统？它有什么特征？
答：实时系统：在被控对象允许时间范围内做出响应 。其主要特征是：对实时信息分析处理速度要比进入系统快、要求安全可靠、资源利用率低。

10什么是处理机的核心态和用户态？为什么要设置这两种不同的状态？
答：当执行操作系统程序时，处理机处于核心态。它有较高的特权，可以执行所有的指令，包括一般用户程序中不能使用的特权指令，从而能对所有寄存器和内存进行访问，启动i/o操作等。
用户程序是在用户态下执行，它的权限较低，只能执行指令集中非特权指令。（2分）
设置这两种不同状态的目的是为了保护操作系统程序（特别是其内核部分），防止受到用户程序的损害。

11系统调用与过程调用在功能及实现上有什么相同点和不同点？
答：相同点：两者都由程序代码构成，可直接用高级程序设计语言（如C,C++和Perl语言）来编制；使用方式相同——以函数调用的形式出现，调用时传送参数。
不同点：①代码层次不同，过程调用不属于操作系统的一部分，而系统调用是操作系统的一部分。②运行状态不同。过程调用只能在用户态下运行，不能进入核心态，而系统调用是在核心态下运行的。③进入方式不同。过程调用在用户程序中调用，并直接在用户空间内执行；而系统调用可以在用户程序中调用，但是在用户程序中执行到系统调用时，会产生异常事件。实现处理机状态从用户态到核心态的转变，从而进入操作系统核心空间去执行系统调用的代码。

12试说明特权指令和系统调用之间的区别与联系。
答：特权指令是一类只能在核心态下执行的机器指令。而系统调用不是机器指令，它往往以函数调用的形式出现，实现操作系统提供的子功能，它是操作系统与用户的编程接口 。在用户程序中可以使用系统调用来获得操作系统服务，在系统调用代码中可以使用特权指令

第二章 进程和线程
名词解释
1顺序性
是指顺序程序所规定的每个动作都在上个动作结束后才开始的特性。

2封闭性
是指只有程序本身的动作才能改变程序的运行环境。

3可再现性
是指程序的执行结果与程序运行的速度无关。

4进程
程序在并发环境中的执行过程。

5互斥
在逻辑上本来完全独立的进程，由于竞争同一个资源而产生的相互制约的关系。

6同步
是指进程间共同完成一项任务时直接发生相互作用的关系。也就是说，这些具有伙伴关系的进程在执行次序上必须遵循确定的规律。

7临界资源
一次仅允许一个进程使用的资源。

8临界区
在每个进程中访问临界资源的那段程序。

9线程
线程是进程中实施调度和分派的基本单位。

10管程
管程是一种高级同步机制，一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。

11进程控制块
进程控制块是进程存在的唯一标识，它保存了系统管理和控制进程所必须的信息，是进程动态特性的集中表现。

12原语
指操作系统中实现一些具有特定功能的程序段，这些程序段的执行过程是不可分割的，即其执行过程不允许被中断。

13就绪态
进程已经获得了除cpu之外的全部资源，等待系统分配cpu，一旦获得cpu，进程就可以变为运行态。

14运行态
正在cpu上执行的进程所处的状态。在单cpu系统中，任何时候最多只能有一个进程处于运行状态。

15阻塞态
又称等待态，指正在运行的进程因等待某个条件发生而不能运行时所处的状态。处于阻塞态的进程在逻辑上是不能运行的，即使cpu空闲，它也不能占用cpu。

16进程通信
是指进程间的信息交换。

17同步机制
同步机构是负责处理进程之间制约关系的机制，即操作系统中负责解决进程之间协调工作的同步关系（直接制约关系），以及共享临界资源的互斥关系（间接制约关系）的执行机构。

简答题
1在操作系统中为什么要引入进程概念？
答: 由于多道程序并发执行时共享系统资源，共同决定这些资源的状态，因此系统中各程序在执行过程中就出现了相互制约的新关系，程序的执行出现“走走停停”的新状态。用程序这个静态的概念已不能如实反映程序并发执行过程中的这些特征。为此，人们引入了“进程（Process）”这一概念来描述程序动态执行过程的性质。
进程和程序是两个完全不同的概念。然而，进程与程序之间存在密切关系，进程的功能是通过程序的运行得以实现的，进程活动的主体是程序。进程不能脱离开具体程序而独立存在。

2有人说，一个进程是由伪处理机执行的一个程序，这话对吗？为什么？
答：对。
因为伪处理机的概念只有在执行时才存在，它表示多个进程在单处理机上并发执行的一个调度单位。因此，尽管进程是动态概念，是程序的执行过程，但是，在多个进程并行执行时，仍然只有一个进程占据处理机执行，而其他并发进程则处于就绪或等待状态。这些并发进程就相当于由伪处理机执行的程序。

3试比较进程和程序的区别
答：（1）进程是一个动态的概念，而程序是一个静态的概念，程序是指令的有序集合，无执行含义，进程则强调执行的过程。
（2）进程具有并行特征（独立性、异步性），程序则没有。
（3）不同的进程可以包含同一个程序，同一程序在执行中也可以产生多个进程。

4进程的基本状态有哪些？试描绘进程状态转换图。
答：进程至少有三种基本状态：运行状态、就绪状态和阻塞状态（或等待状态） 。进程状态转换如下图：
运行态

进程调度
所需要的资源未被满足（如等待 I/O）

时间片到

所需资源得到满足（如I/O完成）

运行态
运行态

5并发进程间的制约有哪两种？引起制约的原因是什么？
答：并发进程所受的制约有两种：直接制约和间接制约。
直接制约是由并发进程相互共享对方的私有资源所引起的；间接制约是由竞争共有资源而引起的。

6什么是进程间的互斥？什么是进程间同步？
答：进程间的互斥是指：一组并发进程中的一个或多个程序段，因共享某一共有资源而导致它们必须以一个不许交叉执行的单位执行，即不允许两个以上的共享该资源的并发进程同时进入临界区。
进程间的同步是指：异步环境下的一组并发进程因直接制约相互发送消息而进行相互合作、相互等待，是各进程按一定的速度执行的过程。

7什么是临界区和临界资源？进程进入临界区的调度原则是什么？
答：临界资源——一次仅允许一个进程使用的资源
临界区——在每个进程中访问临界资源的那段程序
一个进程进入临界区的调度原则是：
① 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入
② 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其他所有试图进入临界区的进程必须等待
③ 进入临界区的进程要在有限的时间内退出，以便让其他进程能及时进入自己的临界区
④ 如果进程不能进入自己的临界区，则应让出cpu，避免进程出现“忙等”现象.

8简述信号量的定义和作用。P，V操作原语是如何定义的？
答：信号量一般是由两个成员组成的数据结构，其中一个成员是整型变量，表示该信号量的值，它与相应资源的使用情况有关；另一个是指向PCB的指针。当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的队首。（2分）
信号量通常可以简单反映出相应资源的使用情况，它与P、V操作原语一起使用可实现进程的同步和互斥。（1分）
P,V操作原语有如下定义。
P(S)顺序执行下述两个动作（1分）：
⑴信号量的值减1，即S=S-1;
⑵如果S>=0,则该进程继续执行。
如果S<0,则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直到其他进程在S上执行V操作，把它释放出来为止）。
V(S)顺序执行下述两个动作（1分）：
⑴S值加1，即S=S+1;
⑵如果S>0,则该进程继续运行；
如果S<=0,则释放信号量队列上的第一个PCB所对应的进程（把阻塞态改为就绪态）,执行V操作的进程继续运行。

9什么是线程？它与进程有什么关系？
答：线程是进程中实施调度和分派的基本单位。
线程和进程之间有如下关系：
① 一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。
② 资源分配给进程，同一进程的所有线程共享该进程的所有资源。
③ 处理机分给线程，即真正在处理机上运行的是线程。
④ 线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。

10什么是管程？它由哪几部分组成？有什么基本特性?
答：一个管程定义了一个数据结构和能为并发进程在其上执行的一组操作，这组操作能同步进程和改变管程中的数据。
一个管程由四个部分组成，它们是管程名称、局部与管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句。
管程具有以下特性：
① 管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问
② 进程要想进入管程，必须调用管程内的某个过程
③ 一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。就是说，管程自身能有效地实现互斥。

综合题
1如下图所示的工作模型中，有三个进程p0,p1,p2和三个缓冲区B0,B1,B2. 进程之间借助于相邻缓冲区进行消息传递：每个进程每次从缓冲区中取一条消息，经加工处理后送入另一个缓冲区中，三个缓冲区分别可存放3,2,2个消息。初始时，仅缓冲区0有一个消息。试用P、V操作写出三个进程之间的同步及互斥流程。
答：这是一个生产者/消费者问题，而且每个进程既是生产者，也是消费者。(2’)
为此，应设置6个信号量：B0S1,B0S2,B1S1,B1S2,B2S1,B2S2,分别代表B0,B1,B2中是否有空缓冲和有数据。
B0S1,B0S2,B1S1,B1S2,B2S2:semaphore;
B0S1=2;B0S2=1;B1S1=2;B1S2=0;B2S1=2;B2S2=0; (2’)
Cobegin (`6’=2’*3)
P0 P1 P2
begin begin begin
P(B0S2) P(B1S2) P(B2S2)
从B0取一个数据 从B1取一个数据 从B2取一个数据
V(B0S2) V(B1S1) V(B2S1)
加工 加工 加工
P(B1S1) P(B2S1) P(B0S1)
将加工结果送B1 将加工结果送B2 将加工结果送B0
V(B1S2) V(B2S2) V(B0S2)
end end end
coend
这道题也可以增加互斥信号量，以便P0与P1之间互斥使用B0缓冲区，P1与P2之间互斥使用B1缓冲区，P2与P0之间互斥使用B0缓冲区。这里主要描述它们之间的同步关系。若考虑互斥共享缓冲区，请自己加上。

2设用三个队列管理缓冲区池的使用情况，分别为空白缓冲队列em，输入缓冲队列in，以及输出缓冲队列out。过程add_buf(type,numb)和take_buf(type,numb)分别用来把缓冲区numb插入type队列和从type队列中取出缓冲区numb。试描述进程从任一缓冲队列中得到一个缓冲区的过程get_buf(type,numb)和释放一个缓冲区numb进入缓冲队列的过程put_buf(type,numb)。
答：假定用信号量s代表任一队列的可用缓冲区个数。假定三个队列的初值分别为n1,n2,n3。对任一队列的操作必须互斥。因此再引入一个互斥使用任一队列的信号量mutex，其初值为1。这里type代表队列的类型，它的取值为输入、输出和空白。(4’)
当有进程希望从任一队列取一个缓冲区时，过程get_buf(type,numb)的动作如下：
get_buf(type,numb) (`3’)
begin
p(s)
p(mutex)
numb=take_buf(type,numb)
v(mutex)
end
当有进程希望向任一队列送一个缓冲区时，过程put_buf(type,numb)的动作如下：
put_buf(type,numb) (`3’)
begin
p(mutex)
add_buf(type,numb)
v(mutex)
v(s)
end.

3设有一个售票厅，可容纳100人购票。如果厅内不足100人则允许进入，进入后购票，购票后退出。如果厅内已有100人，则在厅外等候。试问：
1） 购票者之间是同步还是互斥？
用P、V操作表达购票者的工作过程。
解：1）购票者之间是互斥关系。(2’)
2） 一个售票厅可容纳100人购票，说明最多允许100个购票者共享售票厅；可引入一个信号量empty，其初值为100。由于购票者必须互斥地进行购票，故应再设一个mutex，其初值为1。(4’)
用P、V操作表达购票者的工作过程如下：(`4’)
empty,mutex:semaphore;
empty:=100; mutex:=1;
begin
p(empty)
p(mutex)
进入厅内购票,购票后退出
v(empty)
v(mutex)
end.

4某招待所有100个床位，住宿者入住要先登记（在登记表上填写姓名和床位号）．离去时要注销登记（在登记表上删去姓名和床位号）．请给出住宿登记及注销过程的算法描述．
答：某招待所有100个床位，为了正确管理，引入一个信号量empty代表空床位数，初值为100；住宿者入住要先登记（在登记表上填写姓名和床位号），显然，登记表是一个临界资源，必须互斥访问，引入一个mutex，其初值为1。(4’)
住宿登记及注销过程的算法描述如下：
住宿登记：(`3’)
begin
p(empty) //检查有无床位
p(mutex) //申请登记
找出一个空床位将名字登入表中
v(mutex)
end
注销过程：(`3’)
begin
p(mutex) //申请退房
找出自己的登记项，并删除该项的登记
v(mutex)
v(empty)
end.

5有一个阅览室，共有100个座位。为了很好地利用它，读者进入时必须先在登记表上进行登记。该表表目设有座位号和读者姓名；离开时再将其登记项擦除。
试问：为描述读者的动作，应编写几个程序，应设几个进程、它们之间的关系怎样？并请用P、V操作描述进程之间的同步算法。
解：为了描述阅览室，用一个登记表来记录其使用情况。表中共有100项。每当有读者进入阅览室时，为了正确地登记，各读者应互斥使用(1’)。为此设两个信号量：mutex为互斥信号量，用来制约各读者互斥地进行登记，其初值为1；empty为同步信号量，用来制约各读者能同时进入阅览室的数量，其初值为100 (2’)。
下面用两个过程描述对表格应执行的动作：
登记过程：(`2’) 擦除过程：(`2’)
begin begin
P(empty) P(mutex)
P(mutex) 找到自己的登记项擦除
找到一个登记项登记 V(mutex)
V(mutex) V(empty)
end end
为了正确地描述读者的动作，可以将读者看成进程。若干读者希望进入阅览室时，调用登记过程，退出阅览室时，调用擦除过程(1’)。
可见，一个程序可对应多个读者。可设的进程数由读者数决定，其动作如下：(`2’)
begin
调用登记过程
进入阅览室阅读
准备退出
调用擦除过程
end.

6一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过；但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。
解：假设一座桥由N个桥墩，也即最多允许有N个人同向过河，用一个计数器R记录同时过河的人数(2’)。用S1信号量保护计数器，其初值为1，R的初值为0；互斥使用桥的信号量用S表示，其初值为1。(2’)
同步算法描述如下：
procedure goriver()
begin
L:P(S1); //为同时过河,申请对计数器计数
If R>N begin V(S1); goto L; end //同方向过河的人站满桥墩时,重新申请计数
R=R+1;
If R==1 P(S); //申请过河
V(S1); //释放计数器的使用权 (3’)
占有一个桥墩,并顺序过河到对岸;
P(S1);
R=R-1;
If R==0 V(S); //如果已经无同向的人过河,释放占用权
V(S1); (3’)
end.

7在一个飞机订票系统中，多个用户共享一个数据库。各用户可以同时查询信息，若有一个用户要订票，须更新数据库时，其余所有用户都不可以访问数据库。请用P,V操作设计一个同步算法，实现用户查询与订票功能。要求：当一个用户订票而需要更新数据库时，不能因不断有查询者到来而使其长时间等待。利用信号量机制保证其正常执行。
解：这是典型的读者——写者问题，查询信息的用户是读者，订票用户是写者，并且要求写者优先。(2’)
变量说明：(`2’)
计数变量
rc——正在运行的查询者进程数目，初值为0.
信号量
Sw——控制订票者进程的活动，初值为1.
Src——互斥使用rc变量，初值为1.
S——当订票者到达时封锁后续的读进程，初值为1.
读者进程
P(S)
P(Src)
rc=rc+1
if (rc==1) P(Sw)
V(Src)
V(S) (2’)
查询库当中的信息
P(Src)
rc=rc-1;
if (rc==0) V(Sw)
V(Src) (2’)

写者进程 (`2’)
P(S)
P(Sw)
更新数据库内容
V(Sw)
V(S)

8某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
　　(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
　　(2)根据所定义的信号量，把应执行的PV操作填入下述空格中，以保证进程能够正确地并发执行。
　　COBEGIN　PROCESS　PI(I=1，2，……)
　　　　　　　 begin　　　　　　　　
进入售票厅；

购票；

　　　　　　　　　　　退出；
　　　　　　　 end
　　　COEND
(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。

答：(1)定义一信号量S，初始值为20。　(1’)
　　意义：(`3’=1’*3)
　　S>0　S的值表示可继续进入售票厅的人数　
　　S=0　表示售票厅中已有20名顾客(购票者)　
　　S<0　|S|的值为等待进入售票厅的人数　
　(2)上空格为P(S) (2’) ；下空格为V(S)　(2’)
　(3)S的最大值为20 (1’ )；S的最小值为20－n　(1’ )

9在公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开门关门，当售票员关好车门后，驾驶员才能开车行使。试用P/V操作实现司机与售票员间的同步。
解答：semaphore mutex1=0,mutex2=0; (2’)
main(){
cobegin
driver()
busman()
coend
} (2’)
driver(){
while(true){
p(mutex1)
启动公共汽车
正常开车
到站停车
v(mutex2)
}
} (3’)
busman(){
while(true){
关车门
v(mutex1)
售票
p(mutex2)
开车门
上下乘客
}
} (3’)

10并发问题：设有两个优先级相同的进程p1, p2如下。令信号s1, s2的初值为0，已知z=2，试问p1, p2并发运行结束后x=? y=? z=?
进程p1 进程p2
y := 1 x := 1
y := y+2 x := x+1
v(s1) p(s1)
z := y+1 x := x+y
p(s2) v(s2)
y := z+y z := x+z
解答：（分析过程略 2’）从结果来看，两个进程无论谁先谁后，结果都是一样的。(2’)
x = 5; y = 12; z = 9 (6’)

11 M8
M7
M6
M5
M4
M3
M2
试用信号量机制来描述下述前趋图
M1

解答：首先定义信号量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都为0，分别表示相对应的进程是否完成：(2’)
COBEGIN (`8’=1’*8)
Process M1:
begin
V(S12)
V(S13)
V(S14)
end
Process M2:
begin
P(S12)
V(26)
end
Process M3:
begin
P(S13)
V(S36)
V(S38)
end
Process M4:
begin
P(S14)
V(S47)
end
Process M5:
begin
V(S57)
end
Process M6:
begin
P(S26)
P(S36)
end
Process M7:
begin
P(S47)
P(S57)
P(S78)
end
Process M8:
begin
P(S38)
P(S78)
end
COEND

12
M6
M4
M3
M5
M2
试用信号量机制来描述下述前趋图
M1

解答：首先定义信号量S12,S13,S24,S25,S56,S46,S36的初值都为0，分别表示相对应的进程是否完成(2’)：
COBEGIN (`6’=1’*6)
Process M1:
begin
V(S12)
V(S13)
end
Process M2:
begin
P(S12)
V(24)
V(25)
end
Process M3:
begin
P(S13)
V(S36)
end
Process M4:
begin
P(S14)
V(S46)
end
Process M5:
begin
P(S25)
V(S56)
end
Process M6:
begin
P(S36)
P(S46)
P(S56)
end
COEND

13设系统有三个并发进程R,C,P，共享一个能存放n个数据的环形缓冲区buf。进程R负责从输入设备上读数据，每读一个后把它存放在缓冲区buf的一个单元中；进程C负责从缓冲区读数据并进行处理，之后将处理结果再送入缓冲区的一个单元中；进程P负责从缓冲区读进程C处理的结果并打印。请用P、V操作为三进程的正确执行写出同步算法。
解答：解决同步问题需设一个互斥信号量mux，用于控制三个进程互斥使用缓冲区，初值为1；再设三个同步信号量，用于控制对缓冲区的空闲数量和不同数据个数的记录。S0表示缓冲区空闲个数，初值为n；S1表示缓冲区中输入数据的个数，初值为0；S2表示缓冲区中输出数据的个数，初值为0。(4’)
算法描述如下：(`6’=2’*3)
进程R 进程C 进程P
L1: L2: L3:
P(S0) P(S1) P(S2)
P(mux) P(mux) P(mux)
读一个数据 从缓冲区中取一个 从缓冲区中读
送缓冲区 数据处理后放回去 输出数据
V(mux) V(mux) V(mux)
V(S1) V(S2) V(S0) 打印
gotoL1: gotoL2: gotoL3:

第三章 死锁
名词解释
1死锁
是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。

2饥饿
在系统中，每个资源占有者都在有限时间内释放它所占有的资源，但资源中存在某些申请者由于某种原因却永远得不到资源的一种错误现象。

3死锁防止
要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。

4死锁避免
对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配。就是说，在资源分配过程中若预测有发生死锁的可能性，则加以避免。这种方法的关键是确定资源分配的安全性。

5安全序列
针对当前分配状态来说，系统至少能够按照某种次序为每个进程分配资源（直至最大需求），并且使他们依次成功地运行完毕，这种进程序列{p1,p2,…,pn}就是安全序列。

简答题
1计算机系统中产生死锁的根本原因是什么?死锁发生的四个基本条件是什么？
答: 计算机系统中产生死锁的根本原因是：资源有限且操作不当 。死锁发生的四个基本条件有互斥条件、请求保持条件（占有且等待条件）、非剥夺条件（不可抢占条件）和环路条件（循环等待条件） 。

2简述发生死锁的四个必要条件?
答： 四个必要条件是：互斥条件、占有且等待条件（请求保持条件）、不可抢占条件（非剥夺条件）和循环等待条件（环路条件）。
互斥条件——某个资源在一段时间内只能由一个进程占有，不能同时被两个及其以上的进程占有。
占有且等待条件——进程至少已经占有一个资源，但又申请新的资源。
不可抢占条件——一个进程所占有的资源再用完之前，其他进程不能强行夺走资源，只能由该进程用完之后主动释放。
循环等待条件——存在一个进程等待序列{P1,P2,…,Pn}，其中，P1等待P2所占有的某个资源，P2等待P3所占有的某个资源，……，而Pn等待P1所占有的某个资源，从而形成一个进程循环等待。

3什么是死锁？解决死锁的方法一般有那几种?
答: 死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。
解决死锁问题的一般方法为：死锁的预防、死锁的避免、死锁的检测和恢复。

4死锁预防的基本思想是什么?死锁避免的基本思想是什么?
答:死锁预防的基本思想是:要求进程申请资源是遵循某种协议,从而打破产生思索的四个必要条件中的一个或几个,保证系统不会进入死锁状态.
死锁避免的基本思想是:对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配.就是说,在资源分配过程中若预测有发生死锁的可能性,则加以避免.这种方法的关键是确定资源分配的安全性.

5什么是死锁的安全序列?何谓系统是安全的？
答：进程的安全序列{P1,P2,…,PN}是这样组成的：若对于每个进程Pi（1<=I<=n），它需要的附加资源可以被系统中当前可用资源加上所有进程Pj（j<i）当前占有资源之和所满足，则{ P1,P2,…,PN }为一个安全序列。
“系统是安全的”是指系统中的所有进程能够按照某种次序分配资源，并且依次运行完毕。即系统中的进程处于安全序列中。

6资源按序分配法为什么能够预防死锁？
证明：采用反证法来证明。
若存在循环等待，设在环路上的一组进程为{P0,P1,P2,…,Pn}，这里Pi等待进程Pi+1占有资源Ri（下角标取模运算，从而，Pn等待p0占有的资源）。由于Pi+1占有资源Ri,又申请资源Ri+1,从而一定存在F(i)<F(i+1), 该式对所有的i都成立。于是就有：
F(R0)<F(R1)