解答、算法题

《解答、算法题》由会员分享，可在线阅读，更多相关《解答、算法题（10页珍藏版）》请在装配图网上搜索。

1、一、解答题：1 什么是操作系统?它有什么基本特性？答:操作系统是为了达到以便顾客和提高资源运用率的目的而设计的,控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合,它具有并发、共享、虚拟、异步性四个基本特性。2.(1)描述进程的三种基本状态，尽量清晰地解释处在不同状态的进程在性质上的区别。答:进程的三个基本状态有:、就绪状态：是指进程已分派到除CU以外的所有必要的资源,只要能再获得解决机，便可立即执行。、执行状态:指进程已获得解决机,其程序正在执行。、阻塞状态：进程因发生某事件(如祈求I/O、申请缓冲空间等)而暂停执行时的状态。(2)画出进程状态变化图,阐明进程如何从一种状态

2、转换到下一种状态。答:进程基本状态转换图如下：就绪执行状态：处在就绪状态的进程，当进程调度程序为之分派理解决机后,该进程便由就绪状态变为执行状态。执行阻塞状态：正在执行的进程因发生某事件而无法执行。例如，进程祈求访问临界资源，而该资源正被其他进程访问，则祈求该资源的进程将由执行状态转变为阻塞状态。执行就绪状态：正在执行的进程，如因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态。又如，在抢占调度方式中，一种优先权高的进程到来后，可以抢占一种正在执行优先权低的进程的解决机,这时，该低优先权进程也将由执行状态转换为就绪状态。3现代操作系统一般都提供多进程(或称多任务)运营环境,回答如下问题

3、：(1) 为支持多进程的并发执行，系统必须建立哪些有关进程的数据构造？(2) 为支持进程状态的变迁,系统至少应提供哪些进程控制原语？(3) 执行每一种进程控制原语时,进程状态发生什么变化?相应的数据构造发生什么变化?答：(1） 为支持多进程的并发执行,系统为每个进程建立了一种数据构造进程控制块(B),用于进程的管理和控制。(2) 进程控制的重要职责是对系统中的所有进程实行有效的管理,它具有创立新进程、撤销已有进程、实现进程的状态转换等功能。在操作系统的内核中，有一组程序专门用于完毕对进程的控制,这些原语至少需要涉及创立新进程原语、终结进程原语、阻塞进程原语、唤醒进程原语等操作。这些系统服务一般

4、对顾客是开放的,也就是说顾客可以通过相应的接口来使用它们。() 进程创立原语：从PC集合中申请一种空白CB，将调用者参数、以及从执行进程获得的调用者内部标记填入该PCB，设立记账数据。置新进程为“就绪”状态。 终结进程原语:用于终结完毕任务的进程,收回其所占的资源。消去该进程的PCB。 阻塞原语:将进程从运营态变为阻塞状态。进程被插入等待事件的队列中,同步修改PCB中相应的表项,如进程状态和等待队列指针等。唤醒原语：将进程从阻塞态变为就绪状态。进程被从阻塞队列中移出,插入到就绪队列中,等待调度,同步修改PCB中相应的表项，如进程状态等。何谓临界资源、临界区?使用临界资源的诸进程间如何实现对临界

5、区的互斥访问？答:一次仅容许一种进程访问的资源称为临界资源。访问临界资源的代码段称为临界区。对临界区必须互斥的访问。具体实现时,可让每个进程在进入临界区之前,先提出申请,经容许后方可进入（进入区），进程进入临界区执行完毕退出时，恢复临界区的使用标志为未被访问标志（退出区）。一般可采用专门的硬件指令或信号量机制对临界区进行管理。使用信号量机制是,可设立一种初值为1的互斥信号量,对每个进程的临界区进行如下“改造”:.P（mu）;临界区V(uex)；.即将进程的临界区放置在P(mute)和V（mutex)之间,就可以实现进程对其互斥访问。5使用信号量的P、V操作可以实现并发进程间的互斥。请写出P操作

6、原语和V操作原语的定义？答:P操作功能是祈求系统分派一种单位的资源,定义如下: 信号量的值减1，即SS; 如果，则该进程继续执行; 如果S0,则该进程继续运营; 如果,则释放信号量队列上的第一种CB（即信号量指针项所指向的CB)所相应的进程（把阻塞态改为就绪态),执行V操作的进程继续运营。6什么是死锁?产生死锁的四个必要条件是什么？答:所谓死锁(Deadlck），是指多种进程因竞争资源而导致的一种僵局，若无外力作用,这些进程都将永远不能再向前推动。产生死锁的四个必要条件是：互斥条件、祈求和保持条件、不剥夺条件、环路等待条件。7.简述死锁的避免与死锁的避免的区别。答:死锁的避免是系统预先拟定某些

7、资源分派方略,进程按规定申请资源，系统按预先规定的方略进行分派，从而避免死锁的发生。 而死锁的避免是当进程提出资源申请时系统测试资源分派,仅当能保证系统安全时才把资源分派给进程，使系统始终处在安全状态之中,从而避免死锁。8.解决生产者-消费者问题的算法中,若将P(mpt）和P(mutex)的顺序互换,或将P(full）和P（mex）的顺序互换,也许会产生死锁。请问在什么状况下会产生死锁?答：解决生产者-消费者问题的算法中,若将P（empty)和(mtex)的顺序互换，在缓冲区满的状况下（mpy=，full=n），若生产者先提出申请,获得对缓冲区的访问权,但申请不到空缓冲块，在epty处阻塞,这

8、个时候若再来消费者进程,申请不到对缓冲区的访问权，在mx处阻塞,这时会产生锁死。将（full)和(mtx)的顺序互换，在缓冲区空的状况下（emtyn,ful0)，若消费者先提出申请，获得对缓冲区的访问权，但申请不到满缓冲块,在ful处阻塞，这个时候若再来生产者进程,申请不到对缓冲区的访问权，在mute处阻塞，这时会产生锁死。.消息缓冲通信技术是一种高档通信机制。请给出消息缓冲通信机制(有限缓冲)的基本工作原理。答:操作系统管理一种用于进程通信的缓冲池，其中的每个缓冲区单元可寄存一条消息。欲发送消息时，发送者从中申请一种可用缓冲区，直接将消息送入内存公用消息缓冲池，并将它挂接在接受者进程的消息缓

9、冲队列上，接受进程从消息缓冲队列中取走消息,并释放该缓冲区，每个进程均设立一条消息队列,任何发送给该进程的消息均暂存在其消息队列中。1.()简述解决机三级调度分别完毕什么工作?(2)列举引起进程调度的时机？(3)分析下述问题应由哪一级调度程序负责。 在可获得解决机时,应将它分给哪个就绪进程； 在短期繁重负载下,应将哪个进程临时挂起。答：(1) 高档调度：即作业调度,用于决定把外存上处在后备队列中的哪些作业调入内存,并为它们创立进程,分派必要的资源,然后,再将新创立的进程排在就绪队列上,准备执行。 低档调度:即进程调度，它决定就绪队列中的哪个进程将获得解决机,然后由分派程序执行把解决机分派给该进

10、程的操作。 中级调度:事实上就是存储器管理中的对换功能。(2) 引起进程调度的时机有:l 正在执行进程执行完毕或因发生某事件而不能再继续执行。l 执行中的进程因提出IO祈求而暂停执行。l 在进程通信或同步过程中执行了某种原语操作，如P操作、block原语、wakep原语等。l 在可剥夺式调度中，有一种比目迈进程优先权更高的进程进入就绪队列。l 在时间片轮转法中,时间片用完。 () 进程调度; 中级调度11.动态分区式管理的常用内存分派算法有哪几种?比较它们各自的优缺陷。答：(1)初次适应算法：描述算法(丛空闲分区的组织、如何找两方面描述)缺陷:增长查找可用空闲分区开销； 地址不断划分，致使留下

11、许多难以运用的、很小的空闲分区。()循环初次适应算法：描述算法(2分)特点:减少查找开销,空闲分辨别布的更均匀,但会缺少大的空闲分区。(3）最佳适应算法:描述算法(分）缺陷:划分后剩余的空闲区最小。12.在动态分区存储管理方式中，回收内存时,也许浮现哪几种状况？应如何解决这些状况？答：在动态分区存储管理方式中,回收内存时,系统根据回收区的首址，从空闲区链中找到相应的插入点，此时也许浮现如下四种状况之一： （1）回收区与插入点的前一种分区F相邻接。此时应将回收区与插入点的前一分区合并,不再为回收分辨别配新表项,而只需修改F区的大小为两者之和； （)回收分区与插入点的后一分区F2相邻接。此时也将两

12、分区合并形成新的空闲区，但用回收区的首址作为新空闲区的首址，大小为两者之和；（)回收区同步与插入点的前、后两个分区邻接。此时将三个分区合并，使用F1的首址,取消2的表项； （4）回收区既不与F1邻接,也不与2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址,插入到空闲链中的合适位置。13什么是分页?什么是分段？在存储管理中，分页与分段的重要区别是什么？分页与分段两种措施中,哪个更易于实现共享，为什么?答:分页是将一种进程的逻辑地址空间提成若干大小相等的部分，每一部分称作页面。内存划提成与页面大小相等的物理块,进程的任何一页可放入内存的任何一种物理块中。(2分) 分段是

13、一组逻辑信息的集合,即一种作业中相对独立的部分。多种段在内存中占有离散的内存单元,对每个段,在内存占有一持续的内存空间，其内存的分派与回收同可变分区的内存分派与回收措施。（分） 分页与分段的重要区别是:（1） 页是信息的物理单位。分页仅仅是由于系统管理的需要,而不是顾客的需要;而段是信息的逻辑单位,它具有一组具有相对完整意义的信息,是出于顾客的需要。（2） 页的大小固定且由系统拟定，把逻辑地址划分为页号和页内地址两部分的功能,由机器硬件实现；而段的长度却不固定,或由编译程序在对源程序进行编译时根据信息的性质来划分。（3） 分页的作业地址空间是一维的,即单一的线性地址空间;而分段的作业地址空间则

14、是二维的。对于分页和分段来说，分段更容易实现共享。由于段是一组有一定意义的信息集合，且由于能实现分段的动态链接。 1.阐明在分段系统中,如何实现信息共享?规定图示阐明。答：对于分段系统,每个段都从开始编址，并采用一段持续的地址空间,这样在实现信息共享与保护时,只需在每个进程的段表中，为所要共享和保护的程序设立一种段表项，记录共享的段在内存的基址和段长。进程1和进程2共享edior的示意图如下: 15.何谓虚拟存储器?为什么说祈求页式管理可以实现虚拟存储器?答:虚拟存储器是指仅把作业的一部分装入内存便可运营作业的存储器系统。具体的说，是指具有祈求调入功能和置换功能，能从逻辑上对内存容量进行扩大的

15、一种存储器系统。祈求页式管理是在页式管理的基本上，仅把作业的一部分页放在主存中。页表项中注明相应的页是在主存还是在辅存，程序执行时，当访问的页不在主存时，根据页表项的指引，从辅存将其调入主存,如果这时已无可用的物理空间,则从主存裁减若干页。对于这种变化，顾客感觉不到,她会觉得作业的所有部分都存在于主存，这样可以让更多的作业进入主存，提高系统的效率。虚拟存储器的基本特性是什么？虚拟存储器的容量重要受到哪两方面的限制?答：虚拟存储器的基本特性是:离散分派，即不必占用持续的内存空间；部分装入，即每个作业不是所有一次性地装入内存，而是只装入一部分;多次对换，即所需的所有程序和数据要提成多次调入内存虚拟

16、扩大，即不是物理上而是逻辑上扩大了内存容量;虚拟存储器的容量重要受到指令中表达地址的字长和外存的容量的限制。17为实现祈求分页存储管理，祈求分页系统中的每个页表项应具有哪些内容? 并阐明每个数据项的作用。答：页号: 状态位:指出该页与否已调入内存； 物理块号:若页在内存,指出该页在内存的物理块号； 外存地址：若页在外存，指出该页在外存上的地址，供调入该页时使用访问字段:用于记录本页在一段时间内被访问的次数,或近来已有多长时间未被访问，提供应置换算法选择换出页面时参照；修改位:表达该页在调入内存后与否被修改正。若为1，表白修改正,裁减时必须写回辅存,否则不需要写回。18.简述具有快表的页式存储管

17、理系统的地址变换过程。答：CPU给出有效地址后，地址变换机构将页号与快表中的所有页号进行比较，若有与此相匹配的页号,则表达所访问的页在快表中,从中读出物理块号与页内地址相拼接,得到物理地址；若访问的页不在快表中，则要访问在内存中的页表,从页表项中读出物理块号与页内地址相拼接,得到物理地址，同步，还应将此页表项写入快表中,若此时快表已满,则OS必须找到一种老的且已被觉得不再需要的页表项将它换出。注:具有快表的段式存储管理系统的地址变换过程。具有快表的段页式存储管理系统的地址变换过程。具有快表的祈求页式存储管理系统的地址变换过程。与上题同样重要,请自己考虑。19、产生死锁的因素是什么？答：竞争非剥

18、夺性资源; 进程推动顺序不当。20、简述信号量S的物理含义。答：信号量是对系统中资源及其组织状况的抽象，由一种记录型(或构造体类型）数据表达。它涉及两个数据项。第一种为value,表达可用资源数目：value0时,表达有l个可用资源; .valu=0时，表达资源正好用完； S.alue0时，表达有-ve个进程正在等待此类资源。第二个为，为等待此类资源的进程PCB表链。21、什么叫物理地址?什么叫逻辑地址?什么叫地址映射？地址映射分哪几类？答：物理地址是内存中各存储单元的编号,即存储单元的真实地址，它是可辨认、可寻址并实际存在的。 顾客程序通过编译或汇编形成的目的代码，一般采用相对地址形式，其首

19、地址为零,其他指令中的地址都是相对首地址而定。这个相对地址就称为逻辑地址。 为了保证U执行程序指令时能对的访问存储单元,需要将顾客程序中的逻辑地址转换成运营时可由机器直接寻址的物理地址,这一过程称为地址映射或地址重定位。 地址映射可分为两类: 静态地址映射在程序执行之迈进行的重定位,在程序装入内存时一次性完毕指令中地址的修改。 动态地址映射装入主存的程序仍然保持本来的逻辑地址,由逻辑地址到物理地址的转换在程序真正执行时进行。22、试述段页式存储管理的基本思想答：段页式存储管理的基本思想是: 用页式措施来分派和管理内存空间,即把内存划提成若干大小相等的页面; 用段式措施对顾客程序按照其内在的逻辑

20、关系划提成若干段; 再按照划分内存页面的大小，把每一段划提成若干大小相等的页面； 顾客程序的逻辑地址由三部分构成：段号、页号、页内地址 内存是以页为基本单位分派给每个顾客程序的,在逻辑上相邻的页面内存不一定相邻。二、考虑有六个协作的任务：S1、S、S3、S4、S5、，分别完毕各自的工作,它们满足下列条件：任务S和S2领先于任务S，任务S3领先于任务S5，任务S4和5领先于任务S6;请画出六个协作任务合伙的前趋图，并用P、V操作实现,使得在任何也许的状况下它们均能对的工作。答:本题是典型的同步问题。即进程A执行完后才可执行进程B,只需在两进程间设立信号量，当进程A执行结束后执行V操作,告知进程B

21、可以开始，而进程B在开始之前先执行操作,直到得到进程A的消息。同步关系如下：egins=0;s24=0;35=0；s46=0;s=0rbeinbin s;(s1）;end;begin s2;（4);end;bi s3;v(s3);en;beinp(s1);p(s24);s4；v（s46);end;bgi p(s5); s5;v（s6）;ed;begin p(s46)；p（5）； 6; nd；pared;n三、程序顺序执行和并发执行分别有哪些特性？程序并发执行的条件是什么?对于下列语句,哪些能并发执行?哪些不能？阐明理由。S1:a5-x; S： b=a*x; ：c4*x; S4: db+c; 5

22、: e=d+；答：程序顺序执行时的特性是:顺序性、封闭性和可在现性;并发执行的特性是间断性、失去封闭性和不可再现性。程序可以并发执行的条件是满足Brsin条件,即:若两个程序p1和p2能满足下述条件，她们便能并发执行，且具有再现性： R(1)W(p2)R(2)W(p1）W（p)W(p2)=其中,（)和( )分别表达进程的读集和写集。对于1:a=5-x；S:b=ax；S3：c =4x;S4:=b+c；S5:e=d+3,她们的读集和写集分别是：R(S)=x,W（S1)a；R(S2)=a,x,W(S2)=b；(S3)，W(3)=;R(S4)=b，,(S)=d；R(S5），(S5)=e。由于:R（S1

23、）(）R()W(S3)W(S)W(S3)=(S1）(S4)R(S1）W(S4)W(S）W(S)=R(S1)W(S5)(1)W(S5)W()W(S5)=R()W(S）R(S2)W(3)（S)W(S）=R()(S5)R（S2)()W(S2）W(S5)(3)（5)R(S3）W（S5)W()W（S5)因此S和S3、S1和S、S1和S5、S2和S3、S2和S5、S和5均可并发执行。但由于R（)W(S)=a，（S4)W(S2)=b,R(S4）W(S3)c，R(S)W(S4),因此S和S2、和4、S3和S、4和S5均不能并发执行。四、生产者、消费者问题读者、写者问题及课堂上讲的:用P、V操作解决同步、互斥关系的例题五、祈求分页的存储管理方式的页面置换算法。六、死锁七、调度