操作系统考试题解答、算法题

填空题：1．进程从就绪到运行状态的转换由程序完成；从运行到就绪状态的转换的主要原因是。2．操作系统的三种根本类型是、和。3．程序可并发执行的条件是。4．从结构上讲，进程由、和组成。5．同步机制应遵循的准那么是、、、。6．产生死锁的四个必要条件是、、、和。。8．在页式管理系统中，地址空间是维的，而在段式管理系统中，地址空间是维的。9．操作系统的根本特征是、、。10．从用户的源程序进入系统到变成内存可执行程序，所经历的主要处理阶段有_______，_______，和_________。11．静态重定位在_______时进行，而动态重定位在_______时进行。12．虚拟存储器所具有的根本特征是______，_______，______和_______。13．一般说来，用户程序中所使用的地址是__________,而内存中各存储单元的地址是____________。14．I/O系统的结构分为两类：和。15．I/O控制方式的开展经历了四个阶段，分别是、、、和。答案：1．调度、时间片完2．批处理系统、分时系统、实时系统3．Bernstein条件4．程序段、数据段、进程控制块5．空闲让进、忙那么等待、有限等待、让权等待6．互斥条件、请求和保持条件、不可剥夺条件、环路等待条件7．页表在内存8、一、二9．并发、共享、虚拟、异步10．编译、链接、装入11．装入、运行12．离散性、屡次性、对换性、虚拟性13．逻辑地址、物理地址14．微型机I/O系统、主机I/O系统15．程序I/O方式、中断驱动I/O控制方式、直接存储器访问DMA控制方式、I/O通道控制方式选择题一：操作系统的主要功能是管理计算机系统中的。D．资源产生死锁的根本原因是和进程推进顺序非法。A．资源分配不当B．系统资源缺乏C．作业调度不当D．进程调度不当在操作系统中，是竞争和分配计算机系统资源的根本单位。A．程序B．进程C．作业D．用户动态重定位是在作业的中进行的。A．编译过程B．装入过程C．连接过程D．执行过程实时系统中的进程调度，通常采用算法。A．先来先效劳B．时间片轮转C．抢占式的优先级调度D．短作业优先个等待进程。A．2B．3C．4D．57．死锁的防止是根据采取措施实现的。A．配置足够的系统资源B．使进程的推进顺序合理C．破环死锁的四个必要条件之一D．防止系统进入不平安状态8．设有3个作业，其运行时间分别为2小时，5小时，3小时，假定它们同时到达，并在同一台处理机上以单道方式运行，那么平均周转时间最小的执行顺序是。A．J1,J2,J3B．J3,J2,J1C．J2,J1,J3D．J1,J3,J29．最正确适应算法的空白区是。A．按大小递减顺序排列B．按大小递增顺序排列C．按地址由小到大排列D．按地址由大到小排列10．分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数。A．成正比B．成反比C．无关D．成固定比值选择题一答案：1．D2．B3．B4．D5．C6．A7．D8．D9．B10．C选择题二：1．操作系统核心局部的主要特点是。A、一个程序模块B、常驻内存C、有头有尾的程序D、串行执行2．可重定位内存的分区分配目的为。A、解决碎片问题B、便于多作业共享内存C、回收空白区方便D、便于用户干预3．逻辑地址就是。A、用户地址B、相对地址C、物理地址D、绝对地址4．原语是。ABCD5．进程和程序的一个本质区别是。前者为动态的，后者为静态的；前者存储在内存，后者存储在外存；前者分时使用CPU,后者独占CPU。6．某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将。A．从就绪变为运行；B．从运行变为就绪；C．从运行变为阻塞；D．从阻塞变为就绪7．进程控制块是描述进程状态和特性的数据结构，一个进程。A．可以有多个进程控制块B．可以和其他进程共用一个进程控制块；C．可以没有进程控制块；D．只能有惟一的进程控制块。8．在一般操作系统中必不可少的调度是。A．高级调度；B．中级调度；C．作业调度；D．进程调度。9．把逻辑地址转变为内存的物理地址的过程称作。A．编译；B．连接；C．运行；D．重定位。。A、按名存取B、提高速度C、节省空间D、提高外存利用率11．UNIX操作系统是著名的。A．多道批处理系统；B．分时系统；C．实时系统；D．分布式系统12．在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将。A．从就绪变为运行；B．从运行变为就绪；C．从运行变为阻塞；D．从阻塞变为就绪选择题二答案：1．B2．A3．B4．B5．A6．C7．D8．D9．D10．A11.B12．C选择题三：1．以下进程状态的转换中，哪一个是不正确的〔〕。A.就绪运行B.运行就绪C.就绪阻塞D.阻塞就绪2．某进程由于需要从磁盘上读入数据而处于阻塞状态。当系统完成了所需的读盘操作后，此时该进程的状态将〔〕。A．从就绪变为运行B．从运行变为就绪C．从运行变为阻塞D．从阻塞变为就绪S初值为2，当前值为-1，那么表示有〔〕个等待进程。A．0个B．1个C．2个D．3个4．把逻辑地址转变为内存的物理地址的过程称作〔〕。A．编译B．连接C．运行D．重定位〕实现的。A．段表B．页表C．PCBD．JCB6．在以下存贮管理方案中，不适用于多道程序设计系统的是()。A.单用户连续分配B.固定式分区分配C.可变式分区分配D.页式存贮管理7．在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是()。无上邻空闲区，也无下邻空闲区有上邻空闲区，但无下邻空闲区有下邻空闲区，但无上邻空闲区有上邻空闲区，也有下邻空闲区8．在分段管理中,()。A以段为单位分配,每段是一个连续存储区B段与段之间必定不连续C段与段之间必定连续D每段是等长的9．消息缓冲通信是利用〔〕为根底来实现进程间的数据交换。AB．内存缓冲区C．高速缓冲存储器D．硬件10．采用最正确适应分配算法时，应将空闲区按〔〕顺序进行连接。A．地址递增B．由小到大C．地址递减D．由大到小选择题三答案：12345678910CDBDBADABB一、解答题：什么是操作系统？它有什么根本特征？答：操作系统是为了到达方便用户和提高资源利用率的目的而设计的，控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合，它具有并发、共享、虚拟、异步性四个根本特征。2．〔1〕描述进程的三种根本状态，尽可能清楚地解释处于不同状态的进程在性质上的区别。答：进程的三个根本状态有：①、就绪状态：是指进程已分配到除CPU以外的所有必要的资源，只要能再获得处理机，便可立即执行。②、执行状态：指进程已获得处理机，其程序正在执行。③、阻塞状态：进程因发生某事件〔如请求I/O、申请缓冲空间等〕而暂停执行时的状态。〔2〕画出进程状态变化图，说明进程怎样从一个状态转换到下一个状态。答：进程根本状态转换图如下：就绪→执行状态：处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态变为执行状态。执行→阻塞状态：正在执行的进程因发生某事件而无法执行。例如，进程请求访问临界资源，而该资源正被其它进程访问，那么请求该资源的进程将由执行状态转变为阻塞状态。执行→就绪状态：正在执行的进程，如因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态。又如，在抢占调度方式中，一个优先权高的进程到来后，可以抢占一个正在执行优先权低的进程的处理机，这时，该低优先权进程也将由执行状态转换为就绪状态。3．现代操作系统一般都提供多进程〔或称多任务〕运行环境，答复以下问题：为支持进程状态的变迁，系统至少应提供哪些进程控制原语？执行每一个进程控制原语时，进程状态发生什么变化？相应的数据结构发生什么变化？答：(1)为支持多进程的并发执行，系统为每个进程建立了一个数据结构——进程控制块〔PCB〕，用于进程的管理和控制。“就绪〞状态。终止进程原语：用于终止完成任务的进程，收回其所占的资源。消去该进程的PCB。阻塞原语：将进程从运行态变为阻塞状态。进程被插入等待事件的队列中，同时修改PCB中相应的表项，如进程状态和等待队列指针等。唤醒原语：将进程从阻塞态变为就绪状态。进程被从阻塞队列中移出，插入到就绪队列中，等待调度，同时修改PCB中相应的表项，如进程状态等。4．何谓临界资源、临界区？使用临界资源的诸进程间如何实现对临界区的互斥访问？“改造〞：．．．P(mutex);临界区V(mutex);．．．即将进程的临界区放置在P(mutex)和V(mutex)之间，就可以实现进程对其互斥访问。2.说明作业调度、中级调度和进程调度分别完成什么工作，并分析下述问题应由哪一级调度程序负责。〔1〕在可获得处理机时，应将它分给哪个就绪进程。〔2〕在短期繁重负载下，应将哪个进程暂时挂起。资源，然后，再将新创立的进程排在就绪队列上，准备执行。低级调度〔进程调度〕：它觉得就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。中级调度：存储器管理中的对换功能。〔1〕进程调度。〔2〕中级调度。什么是虚拟存储器？表达实现虚拟存储器的根本原理。答：虚拟存储器是指仅把作业的一局部装入内存便可运行作业的存储器系统，是具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器管理。虚拟存储器管理通过把主、辅存统一起来管理，给用户造成一种仿佛系统内具有巨大主存供用户使用的假象。在页式或段式或段页式管理的根底上，仅把作业的一局部页或段放在主存中。页表项或段表象中注明对应的页或段是在主存还是在辅存，程序执行时，当访问的页或段不在主存时，根据页表项或段表项的指引，从辅存将其调入内存，如果这时已无可用的物理空间，那么从主存淘汰假设干页或段。答：动态链接是指当程序运行到需要调用某一模块时，再去链接，对于未使用的模块，就可以不必链接。答：P操作功能是请求系统分配一个单位的资源，定义如下：①1，即S=S-1；②如果S≥0，那么该进程继续执行；如果S＜0，那么把该进程的状态置为阻塞态，把相应的PCBS上执行V操作，把它释放出来为止〕。V操作功能是释放一个单位的资源，定义如下：①S值加1，即S=S+1；②如果S＞0，那么该进程继续运行；如果S≤0PCBPCB〕所对应的进程〔把阻塞态改为就绪态〕，执行V操作的进程继续运行。6．什么是死锁？产生死锁的四个必要条件是什么？答：所谓死锁〔Deadlock〕，是指多个进程因竞争资源而造成的一种僵局，假设无外力作用，这些进程都将永远不能再向前推进。产生死锁的四个必要条件是：互斥条件、请求和保持条件、不剥夺条件、环路等待条件。7．简述死锁的预防与死锁的防止的区别。答：死锁的预防是系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。

而死锁的防止是当进程提出资源申请时系统测试资源分配，仅当能确保系统平安时才把资源分配给进程，使系统一直处于平安状态之中，从而防止死锁。8．解决生产者-消费者问题的算法中，假设将P(empty)和P(mutex)的次序互换，或将P(full)和P(mutex)的次序互换,可能会产生死锁。请问在什么情况下会产生死锁？答：解决生产者-消费者问题的算法中，假设将P(empty)和P(mutex)的次序互换，在缓冲区满的情况下〔empty=0,full=n〕，假设生产者先提出申请，获得对缓冲区的访问权，但申请不到空缓冲块，在empty处阻塞，这个时候假设再来消费者进程，申请不到对缓冲区的访问权，在mutex处阻塞，这时会产生锁死。将P(full)和P(mutex)的次序互换，在缓冲区空的情况下〔empty=n,full=0〕，假设消费者先提出申请，获得对缓冲区的访问权，但申请不到满缓冲块，在full处阻塞，这个时候假设再来生产者进程，申请不到对缓冲区的访问权，在mutex处阻塞，这时会产生锁死。9．消息缓冲通信技术是一种高级通信机制。请给出消息缓冲通信机制〔有限缓冲〕的根本工作原理。答：操作系统管理一个用于进程通信的缓冲池，其中的每个缓冲区单元可存放一条消息。欲发送消息时，发送者从中申请一个可用缓冲区,直接将消息送入内存公用消息缓冲池，并将它挂接在接收者进程的消息缓冲队列上，接收进程从消息缓冲队列中取走消息，并释放该缓冲区，每个进程均设置一条消息队列，任何发送给该进程的消息均暂存在其消息队列中。10．(1)简述处理机三级调度分别完成什么工作？(2)列举引起进程调度的时机？(3)分析下述问题应由哪一级调度程序负责。在可获得处理机时,应将它分给哪个就绪进程；在短期繁重负载下,应将哪个进程暂时挂起。中级调度：实际上就是存储器管理中的对换功能。(2)引起进程调度的时机有：正在执行进程执行完毕或因发生某事件而不能再继续执行。执行中的进程因提出I/O请求而暂停执行。在进程通信或同步过程中执行了某种原语操作，如P操作、block原语、wakeup原语等。在可剥夺式调度中，有一个比当前进程优先权更高的进程进入就绪队列。在时间片轮转法中，时间片用完。(3)进程调度；中级调度11．动态分区式管理的常用内存分配算法有哪几种？比拟它们各自的优缺点。答：(1)首次适应算法：描述算法(丛空闲分区的组织、如何找两方面描述))缺点：增加查找可用空闲分区开销；地址不断划分，致使留下许多难以利用的、很小的空闲分区。(2)循环首次适应算法：描述算法(2分)特点：减少查找开销，空闲分区分布的更均匀，但会缺乏大的空闲分区。(3)最正确适应算法：描述算法(2分)缺点：划分后剩余的空闲区最小。12．在动态分区存储管理方式中，回收内存时，可能出现哪几种情况？应怎样处理这些情况？答：在动态分区存储管理方式中，回收内存时,系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一：〔1〕回收区与插入点的前一个分区F1相邻接。此时应将回收区与插入点的前一分区合并，不再为回收分区分配新表项，而只需修改F1区的大小为两者之和；〔2〕回收分区与插入点的后一分区F2相邻接。此时也将两分区合并形成新的空闲区，但用回收区的首址作为新空闲区的首址，大小为两者之和；〔3〕回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F1的首址，取消F2的表项；〔4〕回收区既不与F1邻接，也不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址，插入到空闲链中的适当位置。13．什么是分页？什么是分段？在存储管理中，分页与分段的主要区别是什么？分页与分段两种中，哪个更易于实现共享,为什么？答：分页是将一个进程的逻辑地址空间分成假设干大小相等的局部，每一局部称作页面。内存划分成与页面大小相等的物理块，进程的任何一页可放入内存的任何一个物理块中。〔2分〕分页与分段的主要区别是：页是信息的物理单位。分页仅仅是由于系统管理的需要，而不是用户的需要；而段是信息的逻辑单位，它含有一组具有相对完整意义的信息，是出于用户的需要。分页的作业地址空间是一维的，即单一的线性地址空间；而分段的作业地址空间那么是二维的。对于分页和分段来说，分段更容易实现共享。因为段是一组有一定意义的信息集合，且由于能实现分段的动态链接。14．说明在分段系统中，如何实现信息共享？要求图示说明。答：对于分段系统，每个段都从0开始编址，并采用一段连续的地址空间，这样在实现信息共享与保护时，只需在每个进程的段表中，为所要共享和保护的程序设置一个段表项，记录共享的段在内存的基址和段长。进程1和进程2共享editor的示意图如下：15．何谓虚拟存储器？为什么说请求页式管理可以实现虚拟存储器？答：虚拟存储器是指仅把作业的一局部装入内存便可运行作业的存储器系统。具体的说，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。请求页式管理是在页式管理的根本上，仅把作业的一局部页放在主存中。页表项中注明对应的页是在主存还是在辅存，程序执行时，当访问的页不在主存时，根据页表项的指引，从辅存将其调入主存，如果这时已无可用的物理空间，那么从主存淘汰假设干页。对于这种变化，用户感觉不到，他会以为作业的所有局部都存在于主存，这样可以让更多的作业进入主存，提高系统的效率。16．虚拟存储器的根本特征是什么？虚拟存储器的容量主要受到哪两方面的限制？答：虚拟存储器的根本特征是：①离散分配，即不必占用连续的内存空间；②局部装入，即每个作业不是全部一次性地装入内存，而是只装入一局部；③屡次对换，即所需的全部程序和数据要分成屡次调入内存④虚拟扩充，即不是物理上而是逻辑上扩充了内存容量；17．为实现请求分页存储管理，请求分页系统中的每个页表项应含有哪些内容?并说明每个数据项的作用。答：：

状态位：指出该页是否已调入内存；

外存地址：假设页在外存，指出该页在外存上的地址，供调入该页时使用访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供应置换算法选择换出页面时参考；修改位：表示该页在调入内存后是否被修改正。假设为1，说明修改正，淘汰时必须写回辅存，否那么不需要写回。18．简述具有快表的页式存储管理系统的地址变换过程。注：具有快表的段式存储管理系统的地址变换过程。具有快表的段页式存储管理系统的地址变换过程。具有快表的请求页式存储管理系统的地址变换过程。与上题一样重要，请自己考虑。19、产生死锁的原因是什么？答：①竞争非剥夺性资源；

②进程推进顺序不当。S的物理含义。S．value＞0时，表示有value个可用资源；

S．value＝0时，表示资源正好用完；

S．value＜0时，表示有-value个进程正在等待此类资源。第二个为L，为等待此类资源的进程PCB表链。21、什么叫物理地址？什么叫逻辑地址？什么叫地址映射？地址映射分哪几类？换成运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。

地址映射可分为两类：静态地址映射动态地址映射装入主存的程序仍然保持原来的逻辑地址，由逻辑地址到物理地址的转换在程序真正执行时进行。22、试述段页式存储管理的根本思想

答：段页式存储管理的根本思想是：再按照划分内存页面的大小，把每一段划分成假设干大小相等的页面；用户程序的逻辑地址由三局部组成：、、页内地址内存是以页为根本单位分配给每个用户程序的，在逻辑上相邻的页面内存不一定相邻。二、考虑有六个协作的任务：S1、S2、S3、S4、S5、S6，分别完成各自的工作，它们满足以下条件：任务S1和S2领先于任务S4，任务S3领先于任务S5，任务S4和S5领先于任务S6；请画出六个协作任务合作的前趋图，并用P、V操作实现，使得在任何可能的情况下它们均能正确工作。同步关系如下：begins14=0;s24=0;s35=0;s46=0;s56=0Parbeginbegins1;v(s14);end;begins2;v(s24);end;begins3;v(s35);end;beginp(