操作系统简答题、算法题

一、解答： 1． 什么是操作系统？它有什么基本特征？ 答：操作系统是为了达到方便用户和提高资源利用率的目的而的，控制和管理计算机硬件和软件资源，合理的组织计算机工作的程序的集合，它具有并发、共享、虚拟、异步性四个基本特征。 2．（1）描述进程的三种基本状态，尽可能清楚地解释处于不同状态的进程在性质上的区别。 答：进程的三个基本状态有：①、就绪状态：是指进程已分配到除CPU以外的所有必要的资源，只要能再获得处理机，便可立即执行②、执行状态：指进程已获得处理机，其程序正在执行。③、阻塞状态：进程因发生某事件（如请求I/O、申请缓冲空间等）而暂停执行时的状态。 （2）画出进程状态变化图，说明进程怎样从一个状态转换到下一个状态。 答：进程基本状态转换图如下： 就绪→执行状态：处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态变为执行状态。 执行→阻塞状态：正在执行的进程因发生某事件而无法执行。例如，进程请求访问临界资源，而该资源正被其它进程访问，则请求该资源的进程将由执行状态转变为阻塞状态。 执行→就绪状态：正在执行的进程，如因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态。又如，在抢占调度方式中，一个优先权高的进程到来后，可以抢占一个正在执行优先权低的进程的处理机，这时，该低优先权进程也将由执行状态转换为就绪状态。 3．现代操作系统一般都提供多进程（或称多任务）运行环境，回答以下问题： (1) 为支持多进程的并发执行，系统必须建立哪些关于进程的数据结构？ (2) 为支持进程状态的变迁，系统至少应提供哪些进程控制原语？ (3) 执行每一个进程控制原语时，进程状态发生什么变化？相应的数据结构发生什么变化？ 答：(1) 为支持多进程的并发执行，系统为每个进程建立了一个数据结构——进程控制块（PCB），用于进程的管理和控制。 (2) 进程控制的主要职责是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程的状态转换等功能。在操作系统的内核中，有一组程序专门用于完成对进程的控制，这些原语至少需要包括创建新进程原语、终止进程原语、阻塞进程原语、唤醒进程原语等操作。这些系统服务一般对用户是开放的，也就是说用户可以通过相应的接口来使用它们。(3) 进程创建原语：从PCB集合中申请一个空白PCB，将调用者参数、以及从执行进程获得的调用者内部标识填入该PCB，设置记账数据。置新进程为“就绪”状态。 终止进程原语：用于终止完成任务的进程，收回其所占的资源。消去该进程的PCB。 阻塞原语：将进程从运行态变为阻塞状态。进程被插入等待事件的队列中，同时修改PCB中相应的项，如进程状态和等待队列指针等。 唤醒原语：将进程从阻塞态变为就绪状态。进程被从阻塞队列中移出，插入到就绪队列中，等待调度，同时修改PCB中相应的表项，如进程状态等。 4．何谓临界资源、临界区？使用临界资源的诸进程间如何实现对临界区的互斥访问？ 答：一次仅允许一个进程访问的资源称为临界资源。访问临界资源的代码段称为临界区。对临界区必须互斥的访问。具体实现时，可让每个进程在进入临界区之前，先提出申请，经允许后方可进入（进入区），进程进入临界区执行完毕退出时，恢复临界区的使用标志为未被访问标志（退出区）。通常可采用专门的硬件指令或信号量机制对临界区进行管理。使用信号量机制是，可设置一个初值为1的互斥信号量，对每个进程的临界区进行如下“改造”： ． ． ． P(mutex); 临界区 V(mutex); ． ． ． 即将进程的临界区放置在P(mutex)和V(mutex)之间，就可以实现进程对其互斥访问。 5．使用信号量的P、V操作可以实现并发进程间的互斥。请写出P操作原语和V操作原语的定义？ 答：P操作功能是请求系统分配一个单位的资源，定义如下：　①信号量的值减1，即S=S-1；②如果S≥0，则该进程继续执行；　如果S＜0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。 V操作功能是释放一个单位的资源，定义如下：　①S值加1，即S=S+1； ②如果S＞0，则该进程继续运行；如果S≤0，则释放信号量队列上的第一个PCB（即信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行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)分析下述问题应由哪一级调度程序负责。 在可获得处理机时,应将它分给哪个就绪进程；在短期繁重负载下,应将哪个进程暂时挂起。 答：(1) 高级调度：即作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。 低级调度：即进程调度，它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。中级调度：实际上就是存储器管理中的对换功能。 (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分） 分页与分段的主要区别是： （1） 页是信息的物理单位。分页仅仅是由于系统管理的需要，而不是用户的需要；而段是信息的逻辑单位，它含有一组具有相对完整意义的信息，是出于用户的需要。 （2） 页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分的功能，由机器硬件实现；而段的长度却不固定，或由编译程序在对源程序进行编译时根据信息的性质来划分。 （3） 分页的作业地址空间是一维的，即单一的线性地址空间；而分段的作业地址空间则是二维的。 对于分页和分段来说，分段更容易实现共享。因为段是一组有一定意义的信息集合，且由于能实现分段的动态链接。 14．说明在分段系统中，如何实现信息共享？要求图示说明。 答：对于分段系统，每个段都从0开始编址，并采用一段连续的地址空间，这样在实现信息共享与保护时，只需在每个进程的段表中，为所要共享和保护的程序设置一个段表 项，共享的段在内存的基址和段长。进程1和进程2共享editor的示意图如下： 15．何谓虚拟存储器？为什么说请求页式管理可以实现虚拟存储器？ 答：虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体的说，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。请求页式管理是在页式管理的基本上，仅把作业的一部分页放在主存中。页表项中注明对应的页是在主存还是在辅存，程序执行时，当访问的页不在主存时，根据页表项的指引，从辅存将其调入主存，如果这时已无可用的物理空间，则从主存淘汰若干页。对于这种变化，用户感觉不到，他会以为作业的所有部分都存在于主存，这样可以让更多的作业进入主存，提高系统的效率。 16．虚拟存储器的基本特征是什么？虚拟存储器的容量主要受到哪两方面的限制？ 答：虚拟存储器的基本特征是： ①离散分配，即不必占用连续的内存空间；②部分装入，即每个作业不是全部一次性地装入内存，而是只装入一部分；③多次对换，即所需的全部程序和数据要分成多次调入内存④虚拟扩充，即不是物理上而是逻辑上扩充了内存容量； 虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制。 17．为实现请求分页存储管理，请求分页系统中的每个页表项应含有哪些内容? 并说明每个数据项的作用。 答：页号： 状态位：指出该页是否已调入内存； 物理块号：若页在内存，指出该页在内存的物理块号； 外存地址：若页在外存，指出该页在外存上的地址，供调入该页时使用。访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考； 修改位：表示该页在调入内存后是否被修改过。若为1，表明修改过，淘汰时必须写回辅存，否则不需要写回。 18．简述具有快表的页式存储管理系统的地址变换过程。 答：CPU给出有效地址后，地址变换机构将页号与快表中的所有页号进行比较，若有与此相匹配的页号，则表示所访问的页在快表中，从中读出物理块号与页内地址相拼接，得到物理地址；若访问的页不在快表中，则要访问在内存中的页表，从页表项中读出物理块号与页内地址相拼接，得到物理地址，同时，还应将此页表项写入快表中，若此时快表已满，则OS必须找到一个老的且已被认为不再需要的页表项将它换出。 注：具有快表的段式存储管理系统的地址变换过程。具有快表的段页式存储管理系统的地址变换过程。 具有快表的请求页式存储管理系统的地址变换过程。与上题一样重要，请自己考虑。 19、产生死锁的原因是什么？ 答：①竞争非剥夺性资源；②进程推进顺序不当。 20、简述信号量S的物理含义。 答：信号量是对系统中资源及其组织情况的抽象，由一个记录型(或结构体类型)数据表示。它包含两个数据项。第一个为value，表示可用资源数目：S．value＞0时，表示有value个可用资源；S．value＝0时，表示资源正好用完； S．value＜0时，表示有-value个进程正在等待此类资源。第二个为L，为等待此类资源的进程PCB表链。 21、什么叫物理地址？什么叫逻辑地址？什么叫地址映射？地址映射分哪几类？ 答：物理地址是内存中各存储单元的编号，即存储单元的真实地址，它是可识别、可寻址并实际存在的。 用户程序经过编译或汇编形成的目标代码，通常采用相对地址形式，其首地址为零，其余指令中的地址都是相对首地址而定。这个相对地址就称为逻辑地址。为了保证CPU执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地址转换成运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。 地址映射可分为两类： ? 静态地址映射 在程序执行之前进行的重定位，在程序装入内存时一次性完成指令中地址的修改。 ? 动态地址映射 装入主存的程序仍然保持原来的逻辑地址，由逻辑地址到物理地址的转换在程序真正执行时进行。 22、 试述段页式存储管理的基本思想 答：段页式存储管理的基本思想是：用页式方法来分配和管理内存空间，即把内存划分成若干大小相等的页面；用段式方法对用户程序按照其内在的逻辑关系划分成若干段；再按照划分内存页面的大小，把每一段划分成若干大小相等的页面；用户程序的逻辑地址由三部分组成：段号、页号、页内地址 。内存是以页为基本单位分配给每个用户程序的，在逻辑上相邻的页面内存不一定相邻。 二、考虑有六个协作的任务：S1、S2、S3、S4、S5、S6，分别完成各自的工作，它们满足下列条件： 任务S1和S2领先于任务S4，任务S3领先于任务S5，任务S4和S5领先于任务S6；请画出六个协作任务合作的前趋图，并用P、V操作实现，使得在任何可能的情况下它们均能正确工作。 答：本题是典型的同步问题。即进程A执行完后才可执行进程B，只需在两进程间设置信号量，当进程A执行结束后执行V操作，通知进程B可以开始，而进程B在开始之前先执行P操作，直到得到进程A的消息。 同步关系如下： begin s14=0;s24=0;s35=0;s46=0;s56=0 Parbegin begin          s1;v(s14);end; begin          s2;v(s24);end; begin          s3;v(s35);end; begin p(s14);p(s24); s4;v(s46);end; begin p(s35);      s5;v(s56);end; begin p(s46);p(s56); s6; end; parend; end 三、程序顺序执行和并发执行分别有哪些特征？程序并发执行的条件是什么？对于下列语句，哪些能并发执行？哪些不能？说明理由。S1: a=5-x;  S2: b=a*x;  S3: c=4*x;  S4: d=b+c;  S5: e=d+3; 答：程序顺序执行时的特征是：顺序性、封闭性和可在现性；并发执行的特征是间断性、失去封闭性和不可再现性。程序能够并发执行的条件是满足Bernstein条件，即：若两个程序p1和p2能满足下述条件，他们便能并发执行，且具有再现性： R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}其中，R( )和W( )分别表示进程的读集和写集。 对于S1:a=5-x；S2:b=a*x ；S3:c =4*x；S4:d=b+c；S5:e=d+3，他们的读集和写集分别是：R(S1)={x}，W(S1)={a}；R(S2)={a,x}，W(S2)={b}；R(S3)={x}，W(S3)={c}；R(S4)={b,c}，W(S4)={d}；R(S5)={d}，W(S5)={e}。 因为：R(S1)∩W(S3)∪R(S1)∩W(S3)∪W(S1)∩W(S3)={}    R(S1)∩W(S4)∪R(S1)∩W(S4)∪W(S1)∩W(S4)={} R(S1)∩W(S5)∪R(S1)∩W(S5)∪W(S1)∩W(S5)={}      R(S2)∩W(S3)∪R(S2)∩W(S3)∪W(S2)∩W(S3)={} R(S2)∩W(S5)∪R(S2)∩W(S5)∪W(S2)∩W(S5)={}      R(S3)∩W(S5)∪R(S3)∩W(S5)∪W(S3)∩W(S5)={} 所以S1和S3、S1和S4、S1和S5、S2和S3、S2和S5、S3和S5均可并发执行。但因为R(S2)∩W(S1)={a}，R(S4)∩W(S2)={b}，R(S4)∩W(S3)={c}，R(S5) ∩W(S4)={d}，所以S1和S2、S2和S4、S3和S4、S4和S5均不能并发执行。 四、生产者、消费者问题读者、写者问题及课堂上讲的：用P、V操作解决同步、互斥关系的例题 五、请求分页的存储管理方式的页面置换算法。要求：课件上的例一、例二、例三必须会。 六、死锁  七、调度  调度与死锁见课堂上给的例子。死锁注意要写求安全序列的步骤。