1、第 1 页 共 34 页第二章 进程管理第一部分 教材习题（P81）3、为什么程序并发执行会产生间断性特征？（P36）4、程序并发执行，为何会失去封闭性和可再现性？（P37）【解】程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。同时由于失去了封闭性，也将导致其再失去可再现性。程序在并发执行时，由于失去了封闭性，程序经过多次执行后，其计算机结果已与并发程序的执行速度有关，从而使程序的执行失去了可再现性。5、在操作系统中为什么要引入进程概念？（P37）它会产生什么样的影响？【解】在操作系统中引入进程的概念，是为了实现多个程序的并
2、发执行。传统的程序不能与其他程序并发执行，只有在为之创建进程后，才能与其他程序（进程）并发执行。这是因为并发执行的程序（即进程）是“停停走走”地执行，只有在为它创建进程后，在它停下时，方能将其现场信息保存在它的 PCB 中，待下次被调度执行是，再从 PCB 中恢复 CPU 现场并继续执行，而传统的程序却无法满足上述要求。建立进程所带来的好处是使多个程序能并发执行，这极大地提高了资源利用率和系统吞吐量。但管理进程也需付出一定的代价，包括进程控制块及协调各运行机构所占用的内存空间开销，以及为进行进程间的切换、同步及通信等所付出的时间开销。6、试从动态性、并发性和独立性上比较进程和程序？（P37）【
3、解】（1）动态性：进程既然是进程实体的执行过程，因此，动态性是进程最基本的特性。动态性还表现为：“它由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤消而消亡” 。可见，进程有一定的生命期。而程序只是一组有序指令的集合，并存放在某种介质上，本身并无运动的含义，因此，程序是个静态实体。（2）并发性：所谓进程的并发，指的是多个进程实体，同存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也成为 OS 的重要特征。引入进程的目的也正是为了使其程序能和其它进程的程序并发执行，而程序是无法并发执行的。（3）独立性：进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调
4、度的基本单位。凡未建立进程的程序，都不能作为一个独立的单位参加运行。试比较进程与程序的异同。【解】进程和程序是紧密相关而又完全不同的两个概念。（1）每个进程实体中包含了程序段和数据段这两个部分，因此说进程与程序是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含一个数据结构，即 PCB。（2）进程是程序的一次执行过程，因此是动态的；动态性还表现在进程由创建而产生、由调度而执行、由撤消而消亡，即它具有一定的生命期。而程序则只是一组指令的有序集合，并第 2 页 共 34 页可永久地存放在某种介质上，其本身不具有运动的含义，因此是静态的。（3）多个进程实体可同时存放在内存中并发地执
5、行，其实这正是引入进程的目的。程序（在没有为它创建进程时）的并发执行具有不可再现性，因此程序不能正确地并发执行。（4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。程序（在没有为它创建进程时）因其不具有 PCB，所以它是不可能在多道程序环境下独立运行的。（5）进程与程序不一一对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程；一个进程在其生命期的不同时候也可以执行不同的程序。7、试说明 PCB 的作用？为什么说 PCB 是进程存在的惟一标志？（P41）【解】PCB 是进程实体的一部分，是 OS 中最重要的记录型数据结构。它记录了 OS 所需
6、的、用于描述进程情况及控制进程运行所需的全部信息。PCB 的作用，是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。或者说，OS 是根据 PCB 来对并发执行的进程进行控制和管理的。在进程的整个生命期中，系统总是通过 PCB 对进程进行控制，也就是说，系统是根据进程的 PCB 感知到该进程的存在的，所以说，PCB 是进程存在的标志。8、试说明进程在三个基本状态之间转换的典型原因？（P38）【解】（1）处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程就由就绪状态变为执行状态（2）正在执行的进程因发生某事件而无法执行，如暂
7、时无法取得所需资源，则由执行状态转变为阻塞状态。（3）正在执行的进程，如因时间片用完或被高优先级的进程抢占处理机而被暂停执行，该进程便由执行转变为就绪状态。第 3 页 共 34 页某系统的进程状态转换图如图所示。（1）说明引起各种状态转换的典型事件。（2）分析下述状态转换是否可立即引起其他的状态转换：1,2,3,4。执行就绪 阻塞4312【解】（1）引起各种状态转换的典型事件如表所示。状态转换 引起转换的典型事件转换 1 CPU 调度转换 2 执行进程的时间片用完，或被其他优先权更高的进程抢占 CPU转换 3 等待某种事件（如 I/O 的完成，或被他人占用的临界资源变为可用状态转换 4 进程所
8、等待的事件发生（如 I/O 完成，或所等待的临界资源变为可用状态）（2）状态转换 1 不会立即引起其他状态转换。状态转换 2 必然立即引发状态转换 1：状态转换 2 发生后，进程调度程序必然要选出一个新的就绪进程投入运行，该新进程可能是其他进程，也可能是刚从执行状态转换成就绪状态的那个进程。状态转换 3 可能立即引发状态转换 1：状态转换 3 发生后，若就绪队列非空，则进程调度程序将选出一个就绪进程投入执行。状态转换 4 可能引发状态转换 1：状态转换 4 发生后，若 CPU 空闲，并且没有其他进程竞争CPU，则该进程将被立即调度。另外，状态转换 4 还可能同时引发状态转换 1 和 2：若系统
9、采用抢占调度方式，而新就绪的进程具备抢占 CPU 的条件（如其优先权很高） ，则它可立即得到 CPU 转换成执行状态，而原来正在执行的进程则转换成就绪状态。某系统的进程状态变迁图，请说明：第 4 页 共 34 页（1） 引起各种状态转换的典型事件有哪些？（2） 当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一进程作一次状态转换。在什么情况下，当一个进程发生转换 3 时能立即引起另一个进程发生转换 1？（3） 试说明是否会发生下述因果转换：a) 21b) 32c) 41解：（1） 当进程调度程序从就绪队列中选取一个进程投入运行时引起转换 1；正在执行的进程如因时间片用完而
10、被暂停执行就会引起转换 2；正在执行的进程因等待的事件尚未发生而无法执行（如进程请求完成 I/O）则会引起转换 3；当进程等待的事件发生时（如I/O 完成）则会引起转换 4。（2） 如果就绪队列非空，则一个进程的转换 3 会立即引起另一个进程的转换 1。这是因为一个进程发生转换 3 意味着正在执行的进程由执行状态变为阻塞状态，这时处理机空闲，进程调度程序必然会从就绪队列中选取一个进程并将它投入运行，因此只要就绪队列非空，一个进程的转换 3 能立即引起另一个进程的转换 1。（3） 所谓因果转换指的是有两个转换，一个转换的发生会引起另一个转换的发生，前一个转换称为因，后一个转换称为果，这两个转换称
11、为因果转换。当然这种因果关系并不是什么时候都能发生，而是在一定条件下才会发生。a) 21：当某进程发生转换 2 时，就必然引起另一进程的转换 1。因为当发生转换 2 时，正在执行的进程从执行状态变为就绪状态，进程调度程序必然会从就绪队列中选取一个进程投入运行，即发生转换 1。b) 32：某个进程的转换 3 决不可能引起另一进程发生转换 2。这是因为当前执行进程从执行状态变为阻塞状态，不可能又从执行状态变为就绪状态。c) 41：当处理机空闲且就绪队列为空时，某一进程发生转换 4，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入运行。执行就绪 阻塞2 314第 5
12、 页 共 34 页9、为什么要引入挂起状态？（P39）该状态具有哪些性质？10、在进行进程切换时，所要保存的处理机状态信息主要有那些？（P42）【解】保存的处理机状态信息主要由处理机中的各种寄存器内容组成。这些寄存器包括：通用寄存器，指令寄存器，程序状态字 PSW，用户栈指针。11、试说明引起进程创建的主要事件。 （P44）【解】（1）用户登录 在分时系统中，用户在终端键入登录命令后，若是合法用户，系统将为该终端用户建立一个进程，并插入到就绪队列中。（2）作业调度 批处理程序中，作业调度程序按一定的算法调度到某个作业时，就将该作业装入内存，为它分配必要的资源，并立即为其创建进程，插入就绪队列中
13、。（3）提供服务 运行中用户程序提出某种请求，系统专门创建一个进程来提供用户所需服务。（4）应用请求 应用进程自己创建一个进程，使自己和新进程以并发运行方式完成特定任务。12、试说明引起进程被撤消的主要事件。13、在创建一个进程时所要完成的主要工作是什么？（P44）【解】需完成的主要工作有：（1）申请空白 PCB ；（2）为新进程分配资源；（3）初始化 PCB ，其中包括： 初始化标识符信息。将系统分配的标识符、父进程标识符填入新 PCB 中； 初始化处理机状态信息。使程序计数器指向程序入口地址，使栈指针指向栈顶； 初始化处理机控制信息。将进程状态设置为就绪或静止就绪，对于优先级通常设置为最低
14、，除非用户提出高优先级要求。（4）将新进程插入就绪队列。14、在撤消一个进程时所要完成的主要工作是什么？ 15、试说明引起进程阻塞或被唤醒的主要事件是什么？（P46）16、进程在运行时，存在哪两种形式的制约？并举例说明之。17、为什么进程在进入临界区之前，应先执行“进入区”代码，在退出临界区后又执行“退出区”代码？（P50）【解】为了保证诸进程互斥进入自己的临界区，便可实现它们对临界资源的互斥访问。为此，每个进程在进入临界区之前应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻临界资源没被访问，则该进程便可进入临界区，对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进
15、程访问，则本进程不能进入临界区。因此，必须在临界区前增加一段用于上述检查的代码，把这段代码称为进入区。相应地，在临界区后面也要加上一段称为退出区的代码，用于将临界区正被访问的标志恢复为未被访问标志。18、同步机构应遵循哪些基本准则？为什么？（P50）【解】同步机构应遵循的基本准则有：（1）空闲让进 无进程处于临界区时，相应的临界资源处于空闲状态，因而可允许一个请求进入临界区的进程立即进入自己的临界区，以有效利用临界资源。第 6 页 共 34 页（2）忙则等待当已有进程进入自己的临界区时，意味着相应的临界资源正被访问，因而所有其他试图进入临界区的进程必须等待，以保证诸进程互斥地访问临界资源。（3
16、）有限等待对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区，以免陷入“死等”状态。（4）让权等待当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等” 。19、试从物理概念上来说明记录型信号量 wait 和 signal 操作？（P51）【解】在记录型信号量机制中，S.value 的初值表示系统中某类资源的数目，因而又称资源信号量，每次的 wait 操作，意味着进程请求一个单位的资源，因此描述为S.value：=S.value-1；当 S.value0 时，表示资源已分配完毕，因而进程调用 block 原语，进行自我阻塞，放弃处理机，并插入到信号量链表 S.L
17、 中。可见，该机制遵循了让权等待准则。此时 S.value 的绝对值表示在该信号量链表中已阻塞进程的数目。每次 signal 操作，表示执行进程释放一个单位资源，故 S.value：=S.value+1 操作表示资源数目加 1。若加 1 后仍是 S.value=0 则表示该信号量链表中，仍有等待该资源的进程被阻塞，故还要调用wakeup 原语，将 S.L 链表中的第一个等待进程唤醒。如果 S.value 的初值为 1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。20、你认为整型信号量机制是否完全遵循了同步机构的四条准则？（P52）【解】在整型信号量机制中的 wait 操作，只
18、要是信号量 S=0,就会不断地测试，因此，该机制并未遵循“让权等待”的准则，而是使该进程处于“忙等”的状态。21、如何利用信号量机制来实现多个进程对临界资源的互斥访问？并举例说明之。22、试写出相应的程序来描述图 2-17 所示的前趋图。S11S3S2S51S41S71S61S81S11S21S31S41S51S61S71【解】(1)Var a,b,c,d,e,f,g,h; semaphore:=0,0,0,0,0,0,0,0;beginparbegin第 7 页 共 34 页begin S1;signal(a);signal(b);end; begin wait(a);S2;signal(c
19、);signal(d);end;begin wait(b);S3;signal(e); end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);S6;singal(h);end;begin wait(f);wait(g); wait(h); S7;end;parendend (2)Var a,b,c,d,e,f,g,h,i,j; semaphore:=0,0,0,0,0,0,0,0,0,0,0;begin parbeginbegin S1;signal(a);signal(b);end;be
20、gin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);signal(f);end;begin wait(c);S4;signal(g);end;begin wait(d);S5;signal(h);end;begin wait(e);S6;singal(i);end;begin wait(f);S7;signal(j);end;begin wait(g); wait(h);wait(i);wait(j); S8;end;parendend 23、在生产者消费者问题中，如果缺少了 signal(full)或 signa
21、l(empty)，对执行结果会有什么影响？【解】在生产者消费者问题中，如果缺少了 signal(full) ，那么消费者会认为生产者没有生产而阻塞，而生产者会不断生产，直到 empty 为 0 后阻塞，然后两个进程陷入“死等”状态。如果缺少了 signal(empty)开始两进程可同步运行。但当 empty 为 0 时生产者会因此而阻塞，然后消费者进程继续运行直到 full 也为 0 阻塞，然后两个进程陷入“死等”状态。24、在生产者消费者问题中，如果将两个 wait 操作即 wait(full)和 wait(mutex)互换位置，或者将 signal(mutex)与 signal(full)
22、互换位置，结果会如何？【解】如果将 wait(full)和 wait(mutex)互换位置，则如果 consumer 先进入临界区，就会一直等待 full，但由于没有 signal(mutex) ，producer 将无法进入临界区而等待，则两个进程相互等待，陷入死锁。如果 signal(full)与 signal (mutex)互换位置,则会使 full 的值不再是等待的consumer 进程数目。var mutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1of item; in,out:integer:=0,0;Beginparbeginp
23、roducer:beginrepeat第 8 页 共 34 页producer an item in nextp;wait(mutex);/前 2 句颠倒则死锁wait(empty);buffer(in):=nextp;in:=(in+1)mod n;signal(full); /后 2 句颠倒不死锁signal(mutex);until false;endconsumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)mod n;signal(mutex);signal(empty);consume the
24、item in nextc;until false;endParendend由于 V 操作是释放资源，因此对调 V 操作的次序无关紧要。而对调 P 操作的次序则可能导致死锁。这时因为对调 P 操作后，有可能出现这样一种特殊情况：在某一时刻缓冲池中已装满了产品且缓冲池中无进程工作（这时信号量 full 的值为 n，信号量 empty 的值为 0，信号量 mutex的值为 1） ，若系统此时调度生产者进程运行，生产者进程又生产了一个产品，它执行P(mutex)并顺利进入临界区（这时 mutex 值为 0） ，随后它执行 p(empty)时因没有空闲缓冲区而受阻等待，等待消费者进程进入缓冲池取走产品
25、以释放出缓冲区；消费者进程执行 p(full)后再执行 p(mutex)时，因缓冲池被生产者进程占据而无法进入。这样就形成了生产者进程在占有临界资源的情况下，等待消费者进程取走产品，而消费者进程又无法进入临界区取走产品的僵局，此时两进程陷入死锁。25、我们为某临界资源设置一把锁 W，当 W=1 时表示关锁；当 W=0 时表示锁已打开。试写出开锁和关锁原语，并利用它们去实现互斥。【解】我们采用一个变量 W 作为“锁” ，代表某个临界资源的状态，W=0（false,锁已打开）表示该资源未用，W=1（true，关锁）表示该资源正被使用。同时，用一段程序作为开锁原语，用另一段程序作为关锁原语，要进入临
26、界区的进程首先要执行关锁原语，当它退出临界区时，要执行开锁原语。从而实现对临界区的互斥控制。两个原语的作用是：加锁原语 lock测试 W 是否为 0第 9 页 共 34 页若 W=0，让 W=1若 W=1，继续测试开锁原语 unlock使 W=0可见，加锁原语首先要判断临界区中有无进程，若 W=0，表示无进程进入临界区，它可以马上进入，并立即将 W 置为 1，同时禁止其他进程进入。若 W=1，表示已经有进程进入，它只得等待。这种机构简单方便，但存在 CPU 的时间浪费，因为等待进入临界区的进程将不断循环测试 W，等待 W 变为 0。26、试修改下面生产者-消费者问题解法中的错误：produce
27、r:beginrepeatproduce an item in nextp;wait(mutex);wait(full);buffer(in):=nextp;signal(mutex);until false;endconsumer:beginrepeatwait(mutex);wait(empty);nextc:=buffer(out);out:=out+1;signal(mutex);consume item in nextc;until false;end修改为：producer:beginrepeatproduce an item in nextp;wait (empty); wait (mutex);buffer (in): =nextp;in:=(in+1) mod n;signal (mutex);signal (full)until false;end第 10 页 共 34 页consumer：beginrepeatwait (full);wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;out:=out+1;signal(mutex);signal(empty);consume item in nextc;until falseend27、试利用记录型信号量机制写出一个不会出现死锁的哲学家进餐问题的算法。
