1.程序并发执行,为何会失去封闭性和可再现性?
【解】程序在并发执行时,是多个程序共享系统中的各种资源,因而这些资源的状态将由多个程序来改变,致使程序的运行已失去了封闭性。同时由于失去了封闭性,也将导致其再失去可再现性。程序在并发执行时,由于失去了封闭性,程序经过多次执行后,其计算机结果已与并发程序的执行速度有关,从而使程序的执行失去了可再现性。
2.在操作系统中为什么要引入进程概念?它会产生什么样的影响?
【解】 在操作系统中引入进程的概念,是为了实现多个程序的并发执行。传统的程序不能与其他程序并发执行,只有在为之创建进程后,才能与其他程序(进程)并发执行。这是因为并发执行的程序(即进程)是“停停走走”地执行,只有在为它创建进程后,在它停下时,方能将其现场信息保存在它的PCB中,待下次被调度执行是,再从PCB中恢复CPU现场并继续执行,而传统的程序却无法满足上述要求。 建立进程所带来的好处是使多个程序能并发执行,这极大地提高了资源利用率和系统吞吐量。但管理进程也需付出一定的代价,包括进程控制块及协调各运行机构所占用的内存空间开销,以及为进行进程间的切换、同步及通信等所付出的时间开销。
3.试从动态性、并发性和独立性上比较进程和程序?
【解】 (1)动态性:进程既然是进程实体的执行过程,因此,动态性是进程最基本的特性。动态性还表现为:“它由创建而产生,由调度而执行,因得不到资源而暂停执行,以及由撤消而消亡”。可见,进程有一定的生命期。而程序只是一组有序指令的集合,并存放在某种介质上,本身并无运动的含义,因此,程序是个静态实体。 (2)并发性:所谓进程的并发,指的是多个进程实体,同存于内存中,能在一段时间内同时运行。并发性是进程的重要特征,同时也成为OS的重要特征。引入进程的目的也正是为了使其程序能和其它进程的程序并发执行,而程序是无法并发执行的。 (3)独立性:进程实体是一个能独立运行的基本单位,也是系统中独立获得资源和独立调度的基本单位。凡未建立进程的程序,都不能作为一个独立的单位参加运行。
4.试比较进程与程序的异同。
【解】进程和程序是紧密相关而又完全不同的两个概念。 (1)每个进程实体中包含了程序段和数据段这两个部分,因此说进程与程序是紧密相关的。但从结构上看,进程实体中除了程序段和数据段外,还必须包含一个数据结构,即PCB。 (2)进程是程序的一次执行过程,因此是动态的;动态性还表现在进程由创建而产生、由调度而执行、由撤消而消亡,即它具有一定的生命期。而程序则只是一组指令的有序集合,并可永久地存放在某种介质上,其本身不具有运动的含义,因此是静态的。 (3)多个进程实体可同时存放在内存中并发地执行,其实这正是引入进程的目的。程序(在没有为它创建进程时)的并发执行具有不可再现性,因此程序不能正确地并发执行。 (4)进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。程序(在没有为它创建进程时)因其不具有PCB,所以它是不可能在多道程序环境下独立运行的。 (5)进程与程序不一一对应。同一个程序的多次运行,将形成多个不同的进程;同一个程序的一次执行也可以产生多个进程;一个进程在其生命期的不同时候也可以执行不同的程序。
5.试说明PCB的作用?为什么说PCB是进程存在的惟一标志?
【解】PCB是进程实体的一部分,是OS中最重要的记录型数据结构。它记录了OS所需的、用于描述进程情况及控制进程运行所需的全部信息。PCB的作用,是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位,一个能与其他进程并发执行的进程。或者说,OS是根据PCB来对并发执行的进程进行控制和管理的。 在进程的整个生命期中,系统总是通过PCB对进程进行控制,也就是说,系统是根据进程的PCB感知到该进程的存在的,所以说,PCB是进程存在的标志。
6.
试说明进程在三个基本状态之间转换的典型原因? 【解】 (1)处于就绪状态的进程,当进程调度程序为之分配了处理机后,该进程就由就绪状态变为执行状态 (2)正在执行的进程因发生某事件而无法执行,如暂时无法取得所需资源,则由执行状态转变为阻塞状态。 (3)正在执行的进程,如因时间片用完或被高优先级的进程抢占处理机而被暂停执行,该进程便由执行转变为就绪状态。 某系统的进程状态转换图如图所示。 (1)说明引起各种状态转换的典型事件。 (2)分析下述状态转换是否可立即引起其他的状态转换:1,2,3,4。
就绪<----1---2----->执行-------3------>阻塞----4------>就绪
【解】 (1)引起各种状态转换的典型事件如表所示。
(2)状态转换1不会立即引起其他状态转换。 状态转换2必然立即引发状态转换1:状态转换2发生后,进程调度程序必然要选出一个新的就绪进程投入运行,该新进程可能是其他进程,也可能是刚从执行状态转换成就绪状态的那个进程。 状态转换3可能立即引发状态转换1:状态转换3发生后,若就绪队列非空,则进程调度程序将选出一个就绪进程投入执行。 状态转换4可能引发状态转换1:状态转换4发生后,若CPU空闲,并且没有其他进程竞争CPU,则该进程将被立即调度。 另外,状态转换4还可能同时引发状态转换1和2:若系统采用抢占调度方式,而新就绪的进程具备抢占CPU的条件(如其优先权很高),则它可立即得到CPU转换成执行状态,而原来正在执行的进程则转换成就绪状态。 操作系统为什么要引入挂起状态?挂起状态涉及到中级调度,因为当内存中的某个程序需要大的内存空间来执行,但这时内存有没有空余空间了,那么操作系统就回根据调度算法把一些进程放到外存中去,以腾出空间给正在执行的程序的数据和程序,所以引如了挂起状态。
引起挂起状态的原因有如下几方面:
(1)终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时,希望暂停使自己的程序静止下来。亦即,使正在执行的进程暂停执行;若此时用户进程正处于就绪状态而未执行,则该进程暂不接受调度,以便用户研究其执行情况或对程序进行修改。我们把这种静止状态成为“挂起状态”。
(2)父进程的请求。有时父进程希望挂起自己的某个子进程,以便考察和修改子进程,或者协调各子进程间的活动。
(3)负荷调节的需要。当实时系统中的工作负荷较重,已可能影响到对实时任务的控制时,可由系统把一些不重要的进程挂起,以保证系统能正常运行。
(4)操作系统的需要。操作系统有时希望挂起某些进程,以便检查运行中的资源使用情况或进行记账。
(5)对换的需要。为了缓和内存紧张的情况,将内存中处于阻塞状态的进程换至外存上。
8.在进行进程切换时,所要保存的处理机状态信息主要有那些?
【解】保存的处理机状态信息主要由处理机中的各种寄存器内容组成。这些寄存器包括:通用寄存器,指令寄存器,程序状态字PSW,用户栈指针。
9.试说明引起进程创建的主要事件。
【解】 (1)用户登录 在分时系统中,用户在终端键入登录命令后,若是合法用户,系统将为该终端用户建立一个进程,并插入到就绪队列中。 (2)作业调度 批处理程序中,作业调度程序按一定的算法调度到某个作业时,就将该作业装入内存,为它分配必要的资源,并立即为其创建进程,插入就绪队列中。 (3)提供服务 运行中用户程序提出某种请求,系统专门创建一个进程来提供用户所需服务。 (4)应用请求 应用进程自己创建一个进程,使自己和新进程以并发运行方式完成特定任务。
10.在创建一个进程时所要完成的主要工作是什么?
(1)申请空白PCB ; (2)为新进程分配资源; (3)初始化PCB ,其中包括: l 初始化标识符信息。将系统分配的标识符、父进程标识符填入新PCB中; l 初始化处理机状态信息。使程序计数器指向程序入口地址,使栈指针指向栈顶; l 初始化处理机控制信息。将进程状态设置为就绪或静止就绪,对于优先级通常设置为最低,除非用户提出高优先级要求。 (4)将新进程插入就绪队列。
11.为什么进程在进入临界区之前,应先执行“进入区”代码,在退出临界区后又执行“退出区”代码?
【解】为了保证诸进程互斥进入自己的临界区,便可实现它们对临界资源的互斥访问。为此,每个进程在进入临界区之前应先对欲访问的临界资源进行检查,看它是否正被访问。如果此刻临界资源没被访问,则该进程便可进入临界区,对该资源进行访问,并设置它正被访问的标志;如果此刻该临界资源正被某进程访问,则本进程不能进入临界区。因此,必须在临界区前增加一段用于上述检查的代码,把这段代码称为进入区。相应地,在临界区后面也要加上一段称为退出区的代码,用于将临界区正被访问的标志恢复为未被访问标志。
12.同步机构应遵循哪些基本准则?为什么?
【解】同步机构应遵循的基本准则有: (1)空闲让进 无进程处于临界区时,相应的临界资源处于空闲状态,因而可允许一个请求进入临界区的进程立即进入自己的临界区,以有效利用临界资源。 (2)忙则等待 当已有进程进入自己的临界区时,意味着相应的临界资源正被访问,因而所有其他试图进入临界区的进程必须等待,以保证诸进程互斥地访问临界资源。 (3)有限等待 对要求访问临界资源的进程,应保证该进程能在有限时间内进入自己的临界区,以免陷入“死等”状态。 (4)让权等待 当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”。
13.试从物理概念上来说明记录型信号量wait和signal操作?
【解】在记录型信号量机制中,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,表示只允许一个进程访问临界资源,此时的信号量转化为互斥信号量。
14.进程互斥 定义:两个或两个以上的进程,不能同时进入关于同一组共享变量的临界区域,否则可能发生与时间有关的错误,这种现象被称作进程互斥.
在多道程序环境下,存在着临界资源,它是指多进程存在时必须互斥访问的资源。也就是某一时刻不允许多个进程同时访问,只能单个进程的访问。我们把这些程序的片段称作临界区或临界段,它存在的目的是有效的防止竞争条件又能保证最大化使用共享数据。而这些并发进程必须有好的解决方案,才能防止出现以下情况:多个进程同时处于临界区,临界区外的进程阻塞其他的进程,有些进程在临界区外无休止的等待。除此以外,这些方案还不能对CPU的速度和数目做出任何的假设。只有满足了这些条件,才是一个好的解决方案。 访问临界资源的循环进程可以这样来描述: Repeat entry section Critical sections; exit section Remainder sectioni; Until false 为实现进程互斥,可以利用软件的方法,也可以在系统中设置专门的同步机制来协调多个进程,但是所有的同步机制应该遵循四大准则: 1.空闲让进 当临界资源处于空闲状态,允许一个请求进入临界区的进程立即进入临界区,从 而有效的利用资源。 2.忙则等待 已经有进程进入临界区时,意味着相应的临界资源正在被访问,所以其他准备进 入临界区的进程必须等待,来保证多进程互斥。 3.有限等待 对要求访问临界资源的进程,应该保证该进程能在有效的时间内进入临界区,防 止死等状态。 4.让权等待 当进程不能进入临界区,应该立即释放处理机,防止进程忙等待。 早期解决进程互斥问题有软件的方法和硬件的方法,如:严格轮换法,Peterson的解决方案,TSL指令,Swap指令都可以实现进程的互斥,不过它们都有一定的缺陷,这里就不一一详细说明,而后来Kijkstra提出的信号量机制则更好的解决了互斥问题。 15.在生产者—消费者问题中,如果缺少了signal(full)或 signal(empty),对执行结果会有什么影响?
【解】在生产者—消费者问题中,如果缺少了signal(full) ,那么消费者会认为生产者没有生产而阻塞,而生产者会不断生产,直到empty为0后阻塞,然后两个进程陷入“死等”状态。 如果缺少了signal(empty)开始两进程可同步运行。但当empty为0 时生产者会因此而阻塞,然后消费者进程继续运行直到full也为0阻塞,然后两个进程陷入“死等”状态。
16.在生产者—消费者问题中,如果将两个wait操作即wait(full)和wait(mutex)互换位置,或者将signal(mutex)与signal(full)互换位置,结果会如何?
【解】如果将wait(full)和wait(mutex)互换位置,则如果consumer先进入临界区,就会一直等待full,但由于没有signal(mutex) ,producer将无法进入临界区而等待,则两个进程相互等待,陷入死锁。 如果signal(full)与signal (mutex)互换位置,则会使full的值不再是等待的consumer进程数目。 var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1]of item; in,out:integer:=0,0; Begin parbegin producer: begin repeat …… 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; end consumer: begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1)mod n; signal(mutex); signal(empty); consume the item in nextc; until false; end Parend end 由于V操作是释放资源,因此对调V操作的次序无关紧要。 而对调P操作的次序则可能导致死锁。 这时因为对调P操作后,有可能出现这样一种特殊情况:在某一时刻缓冲池中已装满了产品且缓冲池中无进程工作(这时信号量full的值为n,信号量empty的值为0,信号量mutex的值为1),若系统此时调度生产者进程运行,生产者进程又生产了一个产品,它执行P(mutex)并顺利进入临界区(这时mutex值为0),随后它执行p(empty)时因没有空闲缓冲区而受阻等待,等待消费者进程进入缓冲池取走产品以释放出缓冲区; 消费者进程执行p(full)后再执行p(mutex)时,因缓冲池被生产者进程占据而无法进入。 这样就形成了生产者进程在占有临界资源的情况下,等待消费者进程取走产品,而消费者进程又无法进入临界区取走产品的僵局,此时两进程陷入死锁。 【解】我们采用一个变量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。
18.试修改下面生产者-消费者问题解法中的错误:
producer: begin repeat … produce an item in nextp; wait(mutex); wait(full); buffer(in):=nextp; signal(mutex); until false; end consumer: begin repeat wait(mutex); wait(empty); nextc:=buffer(out); out:=out+1; signal(mutex); consume item in nextc; until false; end 修改为: producer: begin repeat produce an item in nextp; wait (empty); wait (mutex); buffer (in): =nextp; in:=(in+1) mod n; signal (mutex); signal (full) until false; end consumer: begin repeat wait (full); wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; out:=out+1; signal(mutex); signal(empty); consume item in nextc; until false end
19.在测量控制系统中的数据采集任务时,把所采集的数据送往一单缓冲区;计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两任务共享单缓冲区的同步算法。
【解】算法如下: Var mutex, empty, full: semaphore: =1,1,0; buffer: item; begin parbegin Receive: begin repeat Wait(empty); Wait(mutex); buffer: =nextp; Signal(mutex); Signal(full); until false end Get: begin repeat Wait (full); Wait (mutex); nextp: =buffer; Signal (mutex); Signal (empty); until false end parend end
20.画图说明管程由哪几部分组成?为什么要引入条件变量?
系统中的各种硬件资源和软件资源,均可用数据结构抽象地描述其资源特性,即用少量信息和对资源所执行的操作来表征该资源,而忽略了它们的内部结构和实现细节。
利用共享数据结构抽象地表示系统中的共享资源,而把对该共享数据结构实施的操作定义为一组过程。
代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序,共同构成了一个操作系统的资源管理模块,我们称之为管程。
Hansan为管程所下的定义:“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据”。
有上述定义可知,管程由四部分组成:
1.管程内部的共享变量;
2.管程内部的条件变量;
3.管程内部并行执行的进程;
4.对局部于管程内部的共享数据设置初始值的语句。
局部于管程的数据结构,只能被局部于管程的过程所访问,任何管程之外的过程都不能访问它;反之,局部于管程的过程也只能访问管程内的数据结构。由此可见,管程相当于围墙,它把共享变量和对它进行操作的若干个过程围了起来,所有进程要访问临界资源时,都必须经过管程才能进入,而管程每次只允许一个进程进入管程,从而实现了进程的互斥。
管程在管式换热器中系指介质流经换热管内的通道及相贯通部分。
通常,由于等待的原因可能有多个,为了区别它们,因此引入条件变量。
21.如何利用管程来解决生产者—消费者问题?(P60)
【解】首先为它们建立一个管程,描述如下: Type producer-consumer=monitor var in, out, count: integer; buffer: array[0,-----,n-1] of item; notfull,notempty:condition; procedure entry put(item) begin if count>=n then notfull.wait; buffer(in):=nextp; in:=(in+1) mod n; count:=count+1; if notempty.queue then notempty.signal; end procedure entry get(item) begin if count<=0 then notempyt.wait; nextc:=buffer(out); out:=(out+1) mod n; count:=count-1; if notfull.queue then notfull.signal; end begin in:=out:=0; count:=0; end 生产者和消费者可描述为: repeat produce an item in nextp; PC.put(item); until false; end consumer: begin repeat PC.get(item); consume the item in nextc until false; end
22.什么是AND信号量?试利用AND信号量写出生产者—消费者问题的解法。
【解】AND信号量是指:将进程在整个运行过程中所需的所有临界资源一次性地全部分配给进程,待该进程使用完后再一起释放。只要尚有一个资源未能分配给该进程,其他所有可能为之分配的资源,也不分配给他,即:对若干临界资源分配,采取原子操作方式,要么全部分配到进程,要么一个也不分配。叫AND信号量。 解法如下: var mutex,empty,full:semaphore:=1,n,0; buffer: array[0,---,n-1]of item; in,out:integer:=0,0; begin parbegin producer: begin repeat produce an item in nextp Swait(empty,mutex); buffer(in):=nextp; in:=(in+1)mod n; Ssignal(mutex,full); until false; end consumer: begin repeat Swait(full,mutex); nextc:=buffer(out); out:=(out+1)mod n; Ssignal(mutex,empty); consume the item in nextc; until false end;
23.
【解】共享存储器系统,消息传递系统,管道通信系统。
24.消息队列通信机制有哪几方面功能?
【解】发送进程利用send原语,将消息直接发送给接收进程;接收进程利用receive原语接收消息
25.如何保证诸进程互斥地访问临界资源?
答:为了互斥地访问临界资源,系统必须保证进程互斥地进入临界区。为此,必须在临界区前增加一段称为进入区的代码,以检查是否有其他进程已进入临界区使用临界资源。若有,则进程必须等待;否则,允许进程进入临界区,同时设置标志表示有进程正在临界区内。同样地,在临界区后必须增加一段称作退出区的代码,用于将已有进程进入临界区访问临界资源的标志改为无进程进入临界区使用临界资源。进入区、退出区具体可用多种同步机制实现,如锁、信号量机制等。
答:所谓“忙等”是指“不让权”的等待,即进程因某事件的发生而无法继续执行时,它仍占有CPU,并通过不断地执行循环测试指令来等待该事件的完成。 “忙等”的主要缺点是浪费CPU的时间,另外,它还可能引起预料不到的后果。例如,考虑某个采取高优先权优先调度原则的系统,目前有2个进程A和B共享某个临界资源,A的优先权较高,B的优先权较低,且B已处于临界区内,而A欲进入自己的临界区,则A、B都不可能继续向前推进,陷入“死等”状态
27.进程之间存在着哪几种制约关系?各是什么原因引起的?下列活动分别属于哪种制约关系?
(1) 若干同学去图书馆借书; (2) 两队举行篮球比赛; (3) 流水线生产的各道工序; (4) 商品生产和社会消费。 答:进程之间存在着直接制约和间接制约两种制约关系,其中直接制约(同步)是由于进程间的相互合作而引起的,而间接制约(互斥)则是由于进程间共享临界资源而引起的。 (1) 若干同学去图书馆借书是间接制约,其中书是临界资源。 (2) 两队举行篮球比赛是间接制约,其中篮球是临界资源。 (3) 流水线生产的各道工序是直接制约,各道工序间需要相互合作,每道工序的开始都依赖于前一道工序的完成。 (4) 商品生产和社会消费是直接制约,两者也需要相互合作:商品生产出来后才可以被消费;商品被消费后才需要再生产。
28.何谓用户级线程和内核支持线程?
内核级线程依赖于内核,无论用户进程中的线程还是系统进程中的线程,其创建、撤消、切换都由内核实现。在内核中保留了一张线程控制块,内核根据控制块感知线程的存在并对其进行控制。
内核是操作系统最基本的部分。它是为众多应用程序提供对计算机硬件的安全访问的一部分软件,这种访问是有限的,并且内核决定一个程序在什么时候对某部分硬件操作多长时间。内核的分类可分为单内核和双内核以及微内核。
比较: (1)线程的调度与切换速度 内核支持线程的调度和切换与进程的调度和切换十分相似。例如,在线程调度时的调度方式,同样也是抢占方式和非抢占方式两种。在线程的调度算法上,也同样可采用时间片轮转、优先权算法等。当由线程调度选中一个线程后,再将处理机分配给它。当然,线程在调度和切换上所花费的开销要比进程的小得多。对于用户级线程的切换,通常是发生在一个应用程序的多线程之间,这时,不仅无须通过中断进入OS的内核,而且切换的规则也远比进程调度和切换的规则简单。例如,当一个线程阻塞后会自动切换到下一个具有相同功能的线程,因此,用户级线程的切换速度特别快。 (2)系统调用 当传统的用户进程调用一个系统调用时,要由用户态转入核心态,用户进程将被阻塞。当内核完成系统调用而返回时,才将该进程唤醒,继续执行。而在用户级线程调用一个系统调用时,由于内核并不知道有该用户级线程的存在,因而把系统调用看作是整个进程的行为,于是使该进程等待,而调度另一个进程执行,同样是在内核完成系统调用而返回时,进程才能继续执行。如果系统中设置的是内核支持线程,则调度是以线程为单位。当一个线程调用一个系统调用时,内核把系统调用只看作是该线程的行为,因而阻塞该线程,于是可以再调度该进程中的其他线程执行。 (3)线程执行时间 对于只设置了用户级线程的系统,调度是以进程为单位进行的。在采用轮转调度算法时,各个进程轮流执行一个时间片,这对诸进程而言,似是公平。但假如在进程A中包含了一个用户级线程,而进程B中含有100个线程,这样,进程A中线程的运行时间,将是进程B中各线程运行时间的100倍;相应地,速度就快100倍。假如系统中设置的是内核支持线程,其调度是以线程为单位进行的,这样,进程B可以获得的CPU时间是进程A的100倍,进程B可使100个系统调用并发工作。 |
|