进程管理复习资料.docx
《进程管理复习资料.docx》由会员分享,可在线阅读,更多相关《进程管理复习资料.docx(54页珍藏版)》请在冰点文库上搜索。
进程管理复习资料
第二章进程管理
第一部分教材习题(P81)
1、什么是前趋图?
为什么要引入前趋图?
2、试画出下面4条语句的前趋图:
S1:
a:
=x+y;
S2:
b:
=z+1;
S3:
c:
=a-b;
S4:
w:
=c+1;
【解】前趋图如下:
3、为什么程序并发执行会产生间断性特征?
(P36)
4、程序并发执行,为何会失去封闭性和可再现性?
(P37)
【解】程序在并发执行时,是多个程序共享系统中的各种资源,因而这些资源的状态将由多个程序来改变,致使程序的运行已失去了封闭性。
同时由于失去了封闭性,也将导致其再失去可再现性。
程序在并发执行时,由于失去了封闭性,程序经过多次执行后,其计算机结果已与并发程序的执行速度有关,从而使程序的执行失去了可再现性。
5、在操作系统中为什么要引入进程概念?
(P37)它会产生什么样的影响?
【解】
在操作系统中引入进程的概念,是为了实现多个程序的并发执行。
传统的程序不能与其他程序并发执行,只有在为之创建进程后,才能与其他程序(进程)并发执行。
这是因为并发执行的程序(即进程)是“停停走走”地执行,只有在为它创建进程后,在它停下时,方能将其现场信息保存在它的PCB中,待下次被调度执行是,再从PCB中恢复CPU现场并继续执行,而传统的程序却无法满足上述要求。
建立进程所带来的好处是使多个程序能并发执行,这极大地提高了资源利用率和系统吞吐量。
但管理进程也需付出一定的代价,包括进程控制块及协调各运行机构所占用的内存空间开销,以及为进行进程间的切换、同步及通信等所付出的时间开销。
6、试从动态性、并发性和独立性上比较进程和程序?
(P37)
【解】
(1)动态性:
进程既然是进程实体的执行过程,因此,动态性是进程最基本的特性。
动态性还表现为:
“它由创建而产生,由调度而执行,因得不到资源而暂停执行,以及由撤消而消亡”。
可见,进程具有一定的生命周期。
而程序只是一组有序指令的集合,并存放在某种介质上,本身并无运动的含义,因此,程序是个静态实体。
(2)并发性:
所谓进程的并发,指的是多个进程实体,同存于内存中,能在一段时间内同时运行。
并发性是进程的重要特征,同时也成为OS的重要特征。
引入进程的目的也正是为了使其程序能和其他进程的程序并发执行,而程序是无法并发执行的。
(3)独立性:
进程实体是一个能独立运行的基本单位,也是系统中独立获得资源和独立调度的基本单位。
凡未建立进程的程序,都不能作为一个独立的单位参加运行。
7、试说明PCB的作用?
为什么说PCB是进程存在的惟一标志?
(P41)
【解】PCB是进程实体的一部分,是OS中最重要的记录型数据结构。
它记录了OS所需的、用于描述进程情况及控制进程运行所需的全部信息。
PCB的作用,是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位,一个能与其他进程并发执行的进程。
或者说,OS是根据PCB来对并发执行的进程进行控制和管理的。
在进程的整个生命周期中,系统总是通过PCB对进程进行控制,也就是说,系统是根据进程的PCB感知到该进程的存在的,所以说,PCB是进程存在的标志。
8、试说明进程在三个基本状态之间转换的典型原因?
(P38)
【解】
(1)处于就绪状态的进程,当进程调度程序为之分配了处理机后,该进程就由就绪状态变为执行状态。
(2)正在执行的进程因发生某事件而无法执行,如暂时无法取得所需资源,则由执行状态转变为阻塞状态。
(3)正在执行的进程,如因时间片用完或被高优先级的进程抢占处理机而被暂停执行,该进程便由执行状态转变为就绪状态。
9、为什么要引入挂起状态?
(P39)
【解】
(1)终端用户的请求:
当终端用户在自己的程序运行期间发现有可疑问题时,希望暂时使自己的程序静止下来。
(2)父进程请求:
父进程希望挂起自己的某个子进程,以便考查和修改该子进程,或者协调各子进程间的活动。
(3)负荷调节的需要:
当实时系统中的工作负荷较重,已可能影响到对实时任务的控制时,可由系统把一些不重要的进程挂起,以便系统能正常运行。
(4)操作系统的需要:
OS有时希望挂起某些进程,以便检查运行中的资源使用情况或进行记账。
10、在进行进程切换时,所要保存的处理机状态信息主要有哪些?
(P42)
【解】保存的处理机状态信息主要由处理机中的各种寄存器内容组成。
这些寄存器包括:
通用寄存器,指令寄存器,程序状态字PSW,用户栈指针。
11、试说明引起进程创建的主要事件。
(P44)
【解】
(1)用户登录在分时系统中,用户在终端键入登录命令后,若是合法用户,系统将为该终端用户建立一个进程,并插入到就绪队列中。
(2)作业调度批处理程序中,作业调度程序按一定的算法调度到某个作业时,就将该作业装入内存,为它分配必要的资源,并立即为其创建进程,插入到就绪队列中。
(3)提供服务运行中的用户程序提出某种请求,系统专门创建一个进程来提供用户所需服务。
(4)应用请求应用进程自己创建一个进程,使自己和新进程以并发运行方式完成特定任务。
12、试说明引起进程被撤消的主要事件。
13、在创建一个进程时所要完成的主要工作是什么?
(P44)
【解】需完成的主要工作有:
(1)申请空白PCB;
(2)为新进程分配资源;
(3)初始化PCB,其中包括:
●初始化标识符信息。
将系统分配的标识符、父进程标识符填入新PCB中;
●初始化处理机状态信息。
使程序计数器指向程序入口地址,使栈指针指向栈顶;
●初始化处理机控制信息。
将进程状态设置为就绪或静止就绪,对于优先级通常设置为最低,除非用户提出高优先级要求。
(4)将新进程插入就绪队列。
14、在撤消一个进程时所要完成的主要工作是什么?
15、试说明引起进程阻塞或被唤醒的主要事件是什么?
(P46)
16、进程在运行时,存在哪两种形式的制约?
并举例说明之。
17、为什么进程在进入临界区之前,应先执行“进入区”代码,在退出临界区后又执行“退出区”代码?
(P50)
【解】为了保证诸进程互斥进入自己的临界区,便可实现它们对临界资源的互斥访问。
为此,每个进程在进入临界区之前应先对欲访问的临界资源进行检查,看它是否正被访问。
如果此刻临界资源没被访问,则该进程便可进入临界区,对该资源进行访问,并设置它正被访问的标志;如果此刻该临界资源正被某进程访问,则本进程不能进入临界区。
因此,必须在临界区前增加一段用于上述检查的代码,把这段代码称为进入区。
相应地,在临界区后面也要加上一段称为退出区的代码,用于将临界区正被访问的标志恢复为未被访问标志。
18、同步机构应遵循哪些基本准则?
为什么?
(P50)
【解】同步机构应遵循的基本准则有:
(1)空闲让进
无进程处于临界区时,相应的临界资源处于空闲状态,因而可允许一个请求进入临界区的进程立即进入自己的临界区,以有效利用临界资源。
(2)忙则等待
当已有进程进入自己的临界区时,意味着相应的临界资源正被访问,因而所有其他试图进入临界区的进程必须等待,以保证诸进程互斥地访问临界资源。
(3)有限等待
对要求访问临界资源的进程,应保证该进程能在有限时间内进入自己的临界区,以免陷入“死等”状态。
(4)让权等待
当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”。
19、试从物理概念上来说明记录型信号量wait和signal操作?
(P51)
【解】在记录型信号量机制中,S.value的初值表示系统中某类资源的数目,因而又称资源信号量,每次的wait操作,意味着进程请求一个单位的资源,因此描述为S.value:
=S.value-1;当S.value<0时,表示资源已分配完毕,因而进程调用block原语,进行自我阻塞,放弃处理机,并插入到信号量链表S.L中。
可见,该机制遵循了让权等待准则。
此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。
每次signal操作,表示执行进程释放一个单位资源,故S.value:
=S.value+1操作表示资源数目加1。
若加1后仍是S.value<=0则表示该信号量链表中,仍有等待该资源的进程被阻塞,故还要调用wakeup原语,将S.L链表中的第一个等待进程唤醒。
如果S.value的初值为1,表示只允许一个进程访问临界资源,此时的信号量转化为互斥信号量。
20、你认为整型信号量机制是否完全遵循了同步机构的四条准则?
(P52)
【解】在整型信号量机制中的wait操作,只要是信号量S<=0,就会不断地测试,因此,该机制并未遵循“让权等待”的准则,而是使该进程处于“忙等”的状态。
21、如何利用信号量机制来实现多个进程对临界资源的互斥访问?
并举例说明之。
22、试写出相应的程序来描述图2-17所示的前趋图。
【解】
(1)
Vara,b,c,d,e,f,g,h;semaphore:
=0,0,0,0,0,0,0,0;
begin
parbegin
beginS1;signal(a);signal(b);end;
beginwait(a);S2;signal(c);signal(d);end;
beginwait(b);S3;signal(e);end;
beginwait(c);S4;signal(f);end;
beginwait(d);S5;signal(g);end;
beginwait(e);S6;singal(h);end;
beginwait(f);wait(g);wait(h);S7;end;
parend
end
(2)
Vara,b,c,d,e,f,g,h,i,j;semaphore:
=0,0,0,0,0,0,0,0,0,0,0;
begin
parbegin
beginS1;signal(a);signal(b);end;
beginwait(a);S2;signal(c);signal(d);end;
beginwait(b);S3;signal(e);signal(f);end;
beginwait(c);S4;signal(g);end;
beginwait(d);S5;signal(h);end;
beginwait(e);S6;singal(i);end;
beginwait(f);S7;signal(j);end;
beginwait(g);wait(h);wait(i);wait(j);S8;end;
parend
end
23、在生产者—消费者问题中,如果缺少了signal(full)或signal(empty),对执行结果会有什么影响?
【解】在生产者—消费者问题中,如果缺少了signal(full),那么消费者会认为生产者没有生产而阻塞,而生产者会不断生产,直到empty为0后阻塞,然后两个进程陷入“死等”状态。
如果缺少了signal(empty)开始两进程可同步运行。
但当empty为0时生产者会因此而阻塞,然后消费者进程继续运行直到full也为0阻塞,然后两个进程陷入“死等”状态。
24、在生产者—消费者问题中,如果将两个wait操作即wait(full)和wait(mutex)互换位置,或者将signal(mutex)与signal(full)互换位置,结果会如何?
【解】如果将wait(full)和wait(mutex)互换位置,则如果consumer先进入临界区,就会一直等待full,但由于没有signal(mutex),producer将无法进入临界区而等待,则两个进程相互等待,陷入死锁。
如果signal(full)与signal(mutex)互换位置,则会使full的值不再是等待的consumer进程数目。
varmutex,empty,full:
semaphore:
=1,n,0;
buffer:
array[0,…,n-1]ofitem;in,out:
integer:
=0,0;
Begin
parbegin
producer:
begin
repeat
……
produceraniteminnextp;
……
wait(mutex);//前2句颠倒则死锁
wait(empty);
buffer(in):
=nextp;
in:
=(in+1)modn;
signal(full);//后2句颠倒不死锁
signal(mutex);
untilfalse;
end
consumer:
begin
repeat
wait(full);
wait(mutex);
nextc:
=buffer(out);
out:
=(out+1)modn;
signal(mutex);
signal(empty);
consumetheiteminnextc;
untilfalse;
end
Parend
end
由于V操作是释放资源,因此对调V操作的次序无关紧要。
而对调P操作的次序则可能导致死锁。
这时因为对调P操作后,有可能出现这样一种特殊情况:
在某一时刻缓冲池中已装满了产品且缓冲池中无进程工作(这时信号量full的值为n,信号量empty的值为0,信号量mutex的值为1),若系统此时调度生产者进程运行,生产者进程又生产了一个产品,它执行P(mutex)并顺利进入临界区(这时mutex值为0),随后它执行p(empty)时因没有空闲缓冲区而受阻等待,等待消费者进程进入缓冲池取走产品以释放出缓冲区;
消费者进程执行p(full)后再执行p(mutex)时,因缓冲池被生产者进程占据而无法进入。
这样就形成了生产者进程在占有临界资源的情况下,等待消费者进程取走产品,而消费者进程又无法进入临界区取走产品的僵局,此时两进程陷入死锁。
25、我们为某临界资源设置一把锁W,当W=1时表示关锁;当W=0时表示锁已打开。
试写出开锁和关锁原语,并利用它们去实现互斥。
【解】我们采用一个变量W作为“锁”,代表某个临界资源的状态,W=0(false,锁已打开)表示该资源未用,W=1(true,关锁)表示该资源正被使用。
同时,用一段程序作为开锁原语,用另一段程序作为关锁原语,要进入临界区的进程首先要执行关锁原语,当它退出临界区时,要执行开锁原语。
从而实现对临界区的互斥控制。
两个原语的作用是:
加锁原语lock
测试W是否为0
若W=0,让W=1
若W=1,继续测试
开锁原语unlock
使W=0
可见,加锁原语首先要判断临界区中有无进程,若W=0,表示无进程进入临界区,它可以马上进入,并立即将W置为1,同时禁止其他进程进入。
若W=1,表示已经有进程进入,它只得等待。
这种机构简单方便,但存在CPU的时间浪费,因为等待进入临界区的进程将不断循环测试W,等待W变为0。
26、试修改下面生产者-消费者问题解法中的错误:
producer:
begin
repeat
…
produceaniteminnextp;
wait(mutex);
wait(full);
buffer(in):
=nextp;
signal(mutex);
untilfalse;
end
consumer:
begin
repeat
wait(mutex);
wait(empty);
nextc:
=buffer(out);
out:
=out+1;
signal(mutex);
consumeiteminnextc;
untilfalse;
end
修改为:
producer:
begin
repeat
produceaniteminnextp;
wait(empty);
wait(mutex);
buffer(in):
=nextp;
in:
=(in+1)modn;
signal(mutex);
signal(full)
untilfalse;
end
consumer:
begin
repeat
wait(full);
wait(mutex);
nextc:
=buffer(out);
out:
=(out+1)modn;
out:
=out+1;
signal(mutex);
signal(empty);
consumeiteminnextc;
untilfalse
end
27、试利用记录型信号量机制写出一个不会出现死锁的哲学家进餐问题的算法。
28、在测量控制系统中的数据采集任务时,把所采集的数据送往一单缓冲区;计算任务从该单缓冲区中取出数据进行计算。
试写出利用信号量机制实现两任务共享单缓冲区的同步算法。
【解】算法如下:
Varmutex,empty,full:
semaphore:
=1,1,0;
buffer:
item;
begin
parbegin
Receive:
begin
repeat
Wait(empty);
Wait(mutex);
buffer:
=nextp;
Signal(mutex);
Signal(full);
untilfalse
end
Get:
begin
repeat
Wait(full);
Wait(mutex);
nextp:
=buffer;
Signal(mutex);
Signal(empty);
untilfalse
end
parend
end
29、画图说明管程由哪几部分组成?
(P56)为什么要引入条件变量?
(P57)
【解】如图:
通常,由于等待的原因可能有多个,为了区别它们,因此引入条件变量。
30、如何利用管程来解决生产者—消费者问题?
(P60)
【解】首先为它们建立一个管程,描述如下:
Typeproducer-consumer=monitor
varin,out,count:
integer;
buffer:
array[0,-----,n-1]ofitem;
notfull,notempty:
condition;
procedureentryput(item)
begin
ifcount>=nthennotfull.wait;
buffer(in):
=nextp;
in:
=(in+1)modn;
count:
=count+1;
ifnotempty.queuethennotempty.signal;
end
procedureentryget(item)
begin
ifcount<=0thennotempyt.wait;
nextc:
=buffer(out);
out:
=(out+1)modn;
count:
=count-1;
ifnotfull.queuethennotfull.signal;
end
beginin:
=out:
=0;count:
=0;end
生产者和消费者可描述为:
producer:
begin
repeat
produceaniteminnextp;
PC.put(item);
untilfalse;
end
consumer:
begin
repeat
PC.get(item);
consumetheiteminnextc
untilfalse;
end
31、什么是AND信号量?
试利用AND信号量写出生产者—消费者问题的解法。
【解】AND信号量是指:
将进程在整个运行过程中所需的所有临界资源一次性地全部分配给进程,待该进程使用完后再一起释放。
只要尚有一个资源未能分配给该进程,其他所有可能为之分配的资源,也不分配给他,即:
对若干临界资源分配,采取原子操作方式,要么全部分配到进程,要么一个也不分配。
叫AND信号量。
解法如下:
varmutex,empty,full:
semaphore:
=1,n,0;
buffer:
array[0,---,n-1]ofitem;
in,out:
integer:
=0,0;
begin
parbegin
producer:
begin
repeat
produceaniteminnextp
Swait(empty,mutex);
buffer(in):
=nextp;
in:
=(in+1)modn;
Ssignal(mutex,full);
untilfalse;
end
consumer:
begin
repeat
Swait(full,mutex);
nextc:
=buffer(out);
out:
=(out+1)modn;
Ssignal(mutex,empty);
consumetheiteminnextc;
untilfalse
end;
32、什么是信号量集?
试利用信号量集写出读者-写者问题的解法。
33、试比较进程间的低级与高级通信工具。
(P65)
34、当前有哪几种高级通信机制?
(P65)
【解】共享存储器系统,消息传递系统,管道通信系统。
35、消息队列通信机制有哪几方面功能?
(P66)
【解】发送进程利用send原语,将消息直接发送给接收进程;接收进程利用receive原语接收消息。
36、为什么要在OS中引入线程?
(P72)
【解】
为了减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性。
进程的两个基本属性:
(1)进程是一个可拥有资源的独立单位;
(2)进程同时又是一个可独立调度和分派的基本单位。
将进程的上述两个属性分开,由OS分开处理,亦即对于作为调度和分派的基本单位,不同时作为拥有资源的单位;而对于拥有资源的基本单位,又不对之进行频繁的切换。
正是在这种思想的指导下,形成了线程的概念。
37、试说明线程具有哪些属性?
(P73)
38、试从调度性、并发性、拥有资源及系统开销几个方面,对进程和线程进行比较。
【解】
(1)调度性在传统的OS中,拥有资源的基本单位和独立调度、分派的基本单位都是进程。
而在引入线程的OS中,则把线程作为调度和分派的基本单位,而把进程作为资源拥有的基本单位,使传统进程的两个属性分开,线程便能轻装运行,从而显著提高系统并发程度。
在同一进程中,线程的切换不会引起进程切换,在由一个进程中的线程切换到另一个进程中的线程时,将会引起进程切换。
(2)并发性多线程的操作系统中,不仅进程可以并发执行,而且一个进程的多个线程也可并发执行。
从而能更有效地使用系统资源和提高系统吞吐量。
(3)拥有资源进程是拥有资源的独立单位。
线程自己基本不拥有系统资源,但可访问隶属进程的资源。
(4)系统开销在创建和撤消进程时,系统要为之分配或回收资源,所以系统开销要显著大于在创建和撤消线程的开销。
在进行进程切换时,涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。
而线程切换只须保存和设置少量寄存器的内容,并不涉及存储器管理方面的操作。
可见,进程切换的开销也远大于线程切换的开销。
此外,由于同一进程中的多个线程具有相同的地址空间,致使它们之间的同步和通信的实现也变得比较容易。
39、为了在多线程OS中实现进程之间的同步与通信,通常提供了哪几种同步机制?
【解】互斥锁,条件变量,计数信号量,多读、单写锁。
40、用于实现线程同步的私用信号量和公用信号量之间有何差异?