操作系统考试题解答算法题.doc

《操作系统考试题解答算法题.doc》由会员分享，可在线阅读，更多相关《操作系统考试题解答算法题.doc（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、题型：填空，选择，简答，算法（进程同步，银行家，调度，页面置换算法，动态分区分配回收算法）第一章1什么是操作系统？操作系统在计算机系统中的位置、作用。2操作系统的类型，各自的特点及区别。3操作系统的特征：并发、共享、虚拟、异步4操作系统发展过程脱机输入输出技术 批处理 多道程序设计技术，概念、特点，好处 分时系统第二章1程序及其执行：程序并发执行的条件2进程定义、进程的组成，为什么说PCB是进程存在的唯一标志？进程和程序的区别与联系。PCB的组织方式。3进程的三种基本状态及转换4什么是挂起？为什么引入挂起？具有挂起状态的进程状态及转换原因5进程的控制：概念，实现，基本的进程控制的功能第三章1同

2、步、互斥概念2临界资源、临界区：概念，如何实现临界区的互斥访问。 临界区互斥四条准则：空闲让进、忙则等待、有限等待、让权等待。3. 互斥的加锁实现4信号量 概念 信号量的P、V操作：功能，定义 信号量的应用：描述前趋图、实现互斥、同步、生产者消费者问题，读者写者问题。5进程通信： 直接通信方式的基本思想、过程-消息缓冲通信第四章 调度与死锁1调度类型及模型；进程调度的方式、时机2调度算法3死锁问题 概念，原因，必要条件，预防及避免方法第五章1编译、链接、装入、重定位 （概念及如何实现）2连续分配单一连续、固定、动态分区分配 各自的实现方式。内存的分配、回收算法3分页分页式系统的基本原理、地址变

3、换过程（基本的和具有快表的）4分段引入的原因。分段的原理。分段共享的实现方法。5分段与分页区别与联系6段页式存储的基本原理第六章 虚拟存储器概念1虚拟存储器的概念、实现原理、特征2请求式分页式系统页表的变化 地址变换过程 页面置换算法填空题：1进程从就绪到运行状态的转换由 程序完成；从运行到就绪状态的转换的 主要原因是 。2操作系统的三种基本类型是 、 和 。3程序可并发执行的条件是 。4从结构上讲，进程由 、 和 组成。 5同步机制应遵循的准则是 、 、 、6产生死锁的四个必要条件是 、 、 、和 。7在没有快表的分页存储管理系统中，取一条指令（或操作数）需访问两次内存的原因是 。8在页式管

4、理系统中，地址空间是 维的，而在段式管理系统中，地址空间是 维的。9操作系统的基本特征是 、 、 。10从用户的源程序进入系统到变成内存可执行程序，所经历的主要处理阶段有_，_，和_。11静态重定位在_时进行，而动态重定位在_时进行。 12虚拟存储器所具有的基本特征是_，_，_和 _。 13一般说来，用户程序中所使用的地址是_,而内存中各存储单元的地址是_。14I/O系统的结构分为两类： 和 。15I/O控制方式的发展经历了四个阶段，分别是 、 、 、和 。答案：1调度、时间片完2批处理系统、分时系统、实时系统3Bernstein条件4程序段、数据段、进程控制块 5空闲让进、忙则等待、有限等待

5、、让权等待 6互斥条件、请求和保持条件、不可剥夺条件、环路等待条件7页表在内存8、一、二9并发、共享、虚拟、异步10编译、链接、装入11装入、运行12离散性、多次性、对换性、虚拟性13逻辑地址、物理地址 14微型机I/O系统 、主机I/O系统 15程序I/O方式、中断驱动I/O控制方式、直接存储器访问DMA控制方式、I/O通道控制方式选择题一：1 操作系统的主要功能是管理计算机系统中的 。A程序 B数据 C文件 D资源2 产生死锁的基本原因是 和进程推进顺序非法。 A资源分配不当 B系统资源不足 C作业调度不当 D进程调度不当3 在操作系统中， 是竞争和分配计算机系统资源的基本单位。A程序 B

6、进程 C作业 D用户4 动态重定位是在作业的 中进行的。 A编译过程 B装入过程 C连接过程 D执行过程5 实时系统中的进程调度，通常采用 算法。 A先来先服务 B时间片轮转 C抢占式的优先级调度 D短作业优先 6若信号量的初值为3，当前值为-2，则表示有 个等待进程。 A2 B3 C4 D5 7死锁的避免是根据 采取措施实现的。 A配置足够的系统资源 B使进程的推进顺序合理 C破环死锁的四个必要条件之一 D防止系统进入不安全状态8设有3个作业，其运行时间分别为2小时，5小时，3小时，假定它们同时到达，并在同一台处理机上以单道方式运行，则平均周转时间最小的执行顺序是 。 AJ1,J2,J3 B

7、J3,J2,J1 CJ2,J1,J3 DJ1,J3,J2 9最佳适应算法的空白区是 。 A按大小递减顺序排列 B按大小递增顺序排列 C按地址由小到大排列 D按地址由大到小排列10分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数 。 A成正比 B成反比 C无关 D成固定比值选择题一答案：1D 2B 3B 4D 5C 6A 7D 8D 9B 10C 选择题二：1操作系统核心部分的主要特点是 。A、一个程序模块 B、常驻内存 C、有头有尾的程序 D、串行执行2可重定位内存的分区分配目的为 。A、解决碎片问题 B、便于多作业共享内存 C、回收空白区方便 D、便于用户干预3逻辑地址就是 。A

8、、用户地址 B、相对地址 C、物理地址 D、绝对地址4原语是 。A、一条机器指令 B、若干条机器指令组成C、一条特定指令 D、中途能打断的指令5进程和程序的一个本质区别是 。A 前者为动态的，后者为静态的； B 前者存储在内存，后者存储在外存；C 前者在一个文件中，后者在多个文件中；D 前者分时使用CPU,后者独占CPU。6某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将 。A从就绪变为运行； B从运行变为就绪；C从运行变为阻塞； D从阻塞变为就绪7进程控制块是描述进程状态和特性的数据结构，一个进程 。A可以有多个进程控制块 B可以和其他进程共用一个进程控制块；C可以没有进程控制

9、块； D只能有惟一的进程控制块。8在一般操作系统中必不可少的调度是 。A高级调度； B中级调度； C作业调度； D进程调度。9把逻辑地址转变为内存的物理地址的过程称作 。A编译； B连接； C运行； D重定位。10文件目录的主要作用是 。A、按名存取 B、提高速度 C、节省空间 D、提高外存利用率11UNIX操作系统是著名的 。A多道批处理系统； B分时系统； C实时系统； D分布式系统12在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将 。A从就绪变为运行； B从运行变为就绪；C从运行变为阻塞； D从阻塞变为就绪选择题二答案：1B 2A 3B 4B 5A 6C 7D 8D 9D 10

10、A 11. B 12C选择题三：1下列进程状态的转换中，哪一个是不正确的（ ）。A.就绪运行 B.运行就绪C.就绪阻塞 D.阻塞就绪2某进程由于需要从磁盘上读入数据而处于阻塞状态。当系统完成了所需的读盘操作后，此时该进程的状态将（ ）。A从就绪变为运行 B从运行变为就绪C从运行变为阻塞 D从阻塞变为就绪3若P、V操作的信号量S初值为2，当前值为-1，则表示有（ ）个等待进程。A0个 B1个 C2个 D3个4把逻辑地址转变为内存的物理地址的过程称作（ ）。A编译 B连接 C运行 D重定位5在分页存储管理系统中，从页号到物理块号的地址映射是通过（ ）实现的。A段表 B页表 CPCB DJCB6在以

11、下存贮管理方案中，不适用于多道程序设计系统的是( )。A.单用户连续分配 B.固定式分区分配C.可变式分区分配 D.页式存贮管理7在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是( )。A. 无上邻空闲区，也无下邻空闲区 B. 有上邻空闲区，但无下邻空闲区C. 有下邻空闲区，但无上邻空闲区D. 有上邻空闲区，也有下邻空闲区8在分段管理中, ( )。A 以段为单位分配, 每段是一个连续存储区B 段与段之间必定不连续C 段与段之间必定连续D每段是等长的9消息缓冲通信是利用（ ）为基础来实现进程间的数据交换。A文件系统 B内

12、存缓冲区 C高速缓冲存储器 D硬件10采用最佳适应分配算法时，应将空闲区按（ ）顺序进行连接。A地址递增 B由小到大 C地址递减 D由大到小选择题三答案：12345678910CDBDBADABB一、解答题：1 什么是操作系统？它有什么基本特征？答：操作系统是为了达到方便用户和提高资源利用率的目的而设计的，控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合，它具有并发、共享、虚拟、异步性四个基本特征。2（1）描述进程的三种基本状态，尽可能清楚地解释处于不同状态的进程在性质上的区别。答：进程的三个基本状态有：、就绪状态：是指进程已分配到除CPU以外的所有必要的资源，只要能再获得

13、处理机，便可立即执行。、执行状态：指进程已获得处理机，其程序正在执行。、阻塞状态：进程因发生某事件（如请求I/O、申请缓冲空间等）而暂停执行时的状态。（2）画出进程状态变化图，说明进程怎样从一个状态转换到下一个状态。答：进程基本状态转换图如下：就绪执行状态：处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态变为执行状态。执行阻塞状态：正在执行的进程因发生某事件而无法执行。例如，进程请求访问临界资源，而该资源正被其它进程访问，则请求该资源的进程将由执行状态转变为阻塞状态。执行就绪状态：正在执行的进程，如因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态。又如，在抢占

14、调度方式中，一个优先权高的进程到来后，可以抢占一个正在执行优先权低的进程的处理机，这时，该低优先权进程也将由执行状态转换为就绪状态。3现代操作系统一般都提供多进程（或称多任务）运行环境，回答以下问题：(1) 为支持多进程的并发执行，系统必须建立哪些关于进程的数据结构？(2) 为支持进程状态的变迁，系统至少应提供哪些进程控制原语？(3) 执行每一个进程控制原语时，进程状态发生什么变化？相应的数据结构发生什么变化？答：(1) 为支持多进程的并发执行，系统为每个进程建立了一个数据结构进程控制块（PCB），用于进程的管理和控制。(2) 进程控制的主要职责是对系统中的所有进程实施有效的管理，它具有创建新

15、进程、撤销已有进程、实现进程的状态转换等功能。在操作系统的内核中，有一组程序专门用于完成对进程的控制，这些原语至少需要包括创建新进程原语、终止进程原语、阻塞进程原语、唤醒进程原语等操作。这些系统服务一般对用户是开放的，也就是说用户可以通过相应的接口来使用它们。(3) 进程创建原语：从PCB集合中申请一个空白PCB，将调用者参数、以及从执行进程获得的调用者内部标识填入该PCB，设置记账数据。置新进程为“就绪”状态。 终止进程原语：用于终止完成任务的进程，收回其所占的资源。消去该进程的PCB。 阻塞原语：将进程从运行态变为阻塞状态。进程被插入等待事件的队列中，同时修改PCB中相应的表项，如进程状态

16、和等待队列指针等。 唤醒原语：将进程从阻塞态变为就绪状态。进程被从阻塞队列中移出，插入到就绪队列中，等待调度，同时修改PCB中相应的表项，如进程状态等。4何谓临界资源、临界区？使用临界资源的诸进程间如何实现对临界区的互斥访问？答：一次仅允许一个进程访问的资源称为临界资源。访问临界资源的代码段称为临界区。对临界区必须互斥的访问。具体实现时，可让每个进程在进入临界区之前，先提出申请，经允许后方可进入（进入区），进程进入临界区执行完毕退出时，恢复临界区的使用标志为未被访问标志（退出区）。通常可采用专门的硬件指令或信号量机制对临界区进行管理。使用信号量机制是，可设置一个初值为1的互斥信号量，对每个进程

17、的临界区进行如下“改造”：P(mutex);临界区V(mutex);即将进程的临界区放置在P(mutex)和V(mutex)之间，就可以实现进程对其互斥访问。2.说明作业调度、中级调度和进程调度分别完成什么工作，并分析下述问题应由哪一级调度程序负责。（1）在可获得处理机时，应将它分给哪个就绪进程。（2）在短期繁重负载下，应将哪个进程暂时挂起。答：高级调度（作业调度）用于决定把外存上处于后备队列中的哪些作业调入内存，并将它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。低级调度（进程调度）：它觉得就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程

18、的操作。中级调度：存储器管理中的对换功能。（1）进程调度。（2）中级调度。什么是虚拟存储器？叙述实现虚拟存储器的基本原理。答：虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统，是具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器管理。虚拟存储器管理通过把主、辅存统一起来管理，给用户造成一种仿佛系统内具有巨大主存供用户使用的假象。在页式或段式或段页式管理的基础上，仅把作业的一部分页或段放在主存中。页表项或段表象中注明对应的页或段是在主存还是在辅存，程序执行时，当访问的页或段不在主存时，根据页表项或段表项的指引，从辅存将其调入内存，如果这时已无可用的物理空间，则从主

19、存淘汰若干页或段。什么是动态链接？用何种内存分配方法可以实现这种链接技术？答：动态链接是指当程序运行到需要调用某一模块时，再去链接，对于未使用的模块，就可以不必链接。采用段式内存分配方法可以实现这种技术。5使用信号量的P、V操作可以实现并发进程间的互斥。请写出P操作原语和V操作原语的定义？答：P操作功能是请求系统分配一个单位的资源，定义如下：信号量的值减1，即S=S-1；如果S0，则该进程继续执行；如果S0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。 V操作功能是释放一个单位的资源，定义如下：S值

20、加1，即S=S+1；如果S0，则该进程继续运行； 如果S0，则释放信号量队列上的第一个PCB（即信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。6什么是死锁？产生死锁的四个必要条件是什么？答：所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。产生死锁的四个必要条件是：互斥条件、请求和保持条件、不剥夺条件、环路等待条件。7简述死锁的预防与死锁的避免的区别。答：死锁的预防是系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。 而死锁的避免是当进

21、程提出资源申请时系统测试资源分配，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁。8解决生产者-消费者问题的算法中，若将P(empty)和P(mutex)的次序互换，或将P(full)和P(mutex)的次序互换,可能会产生死锁。请问在什么情况下会产生死锁？答：解决生产者-消费者问题的算法中，若将P(empty)和P(mutex)的次序互换，在缓冲区满的情况下（empty=0,full=n），若生产者先提出申请，获得对缓冲区的访问权，但申请不到空缓冲块，在empty处阻塞，这个时候若再来消费者进程，申请不到对缓冲区的访问权，在mutex处阻塞，这时会产生锁死。

22、将P(full)和P(mutex)的次序互换，在缓冲区空的情况下（empty=n,full=0），若消费者先提出申请，获得对缓冲区的访问权，但申请不到满缓冲块，在full处阻塞，这个时候若再来生产者进程，申请不到对缓冲区的访问权，在mutex处阻塞，这时会产生锁死。9消息缓冲通信技术是一种高级通信机制。请给出消息缓冲通信机制（有限缓冲）的基本工作原理。答：操作系统管理一个用于进程通信的缓冲池，其中的每个缓冲区单元可存放一条消息。欲发送消息时，发送者从中申请一个可用缓冲区,直接将消息送入内存公用消息缓冲池，并将它挂接在接收者进程的消息缓冲队列上，接收进程从消息缓冲队列中取走消息，并释放该缓冲区，

23、每个进程均设置一条消息队列，任何发送给该进程的消息均暂存在其消息队列中。10(1)简述处理机三级调度分别完成什么工作？(2)列举引起进程调度的时机？(3)分析下述问题应由哪一级调度程序负责。 在可获得处理机时,应将它分给哪个就绪进程； 在短期繁重负载下,应将哪个进程暂时挂起。答：(1) 高级调度：即作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。 低级调度：即进程调度，它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。 中级调度：实际上就是存储器管理中的对换功能。(

24、2) 引起进程调度的时机有：l 正在执行进程执行完毕或因发生某事件而不能再继续执行。l 执行中的进程因提出I/O请求而暂停执行。l 在进程通信或同步过程中执行了某种原语操作，如P操作、block原语、wakeup原语等。l 在可剥夺式调度中，有一个比当前进程优先权更高的进程进入就绪队列。l 在时间片轮转法中，时间片用完。 (3) 进程调度； 中级调度11动态分区式管理的常用内存分配算法有哪几种？比较它们各自的优缺点。答：(1)首次适应算法：描述算法(丛空闲分区的组织、如何找两方面描述)缺点：增加查找可用空闲分区开销； 地址不断划分，致使留下许多难以利用的、很小的空闲分区。(2)循环首次适应算法

25、：描述算法(2分)特点：减少查找开销，空闲分区分布的更均匀，但会缺乏大的空闲分区。(3)最佳适应算法：描述算法(2分)缺点：划分后剩余的空闲区最小。12在动态分区存储管理方式中，回收内存时，可能出现哪几种情况？应怎样处理这些情况？答：在动态分区存储管理方式中，回收内存时,系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一： （1）回收区与插入点的前一个分区F1相邻接。此时应将回收区与插入点的前一分区合并，不再为回收分区分配新表项，而只需修改F1区的大小为两者之和； （2）回收分区与插入点的后一分区F2相邻接。此时也将两分区合并形成新的空闲区，但用回收区的首址作为新

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

27、立的部分。多个段在内存中占有离散的内存单元，对每个段，在内存占有一连续的内存空间，其内存的分配与回收同可变分区的内存分配与回收办法。（2分） 分页与分段的主要区别是：（1） 页是信息的物理单位。分页仅仅是由于系统管理的需要，而不是用户的需要；而段是信息的逻辑单位，它含有一组具有相对完整意义的信息，是出于用户的需要。（2） 页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分的功能，由机器硬件实现；而段的长度却不固定，或由编译程序在对源程序进行编译时根据信息的性质来划分。（3） 分页的作业地址空间是一维的，即单一的线性地址空间；而分段的作业地址空间则是二维的。对于分页和分段来说，分段更

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

29、管理的基本上，仅把作业的一部分页放在主存中。页表项中注明对应的页是在主存还是在辅存，程序执行时，当访问的页不在主存时，根据页表项的指引，从辅存将其调入主存，如果这时已无可用的物理空间，则从主存淘汰若干页。对于这种变化，用户感觉不到，他会以为作业的所有部分都存在于主存，这样可以让更多的作业进入主存，提高系统的效率。16虚拟存储器的基本特征是什么？虚拟存储器的容量主要受到哪两方面的限制？答：虚拟存储器的基本特征是：离散分配，即不必占用连续的内存空间；部分装入，即每个作业不是全部一次性地装入内存，而是只装入一部分；多次对换，即所需的全部程序和数据要分成多次调入内存虚拟扩充，即不是物理上而是逻辑上扩充

30、了内存容量；虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制。17为实现请求分页存储管理，请求分页系统中的每个页表项应含有哪些内容? 并说明每个数据项的作用。答：页号： 状态位：指出该页是否已调入内存； 物理块号：若页在内存，指出该页在内存的物理块号； 外存地址：若页在外存，指出该页在外存上的地址，供调入该页时使用访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考；修改位：表示该页在调入内存后是否被修改过。若为1，表明修改过，淘汰时必须写回辅存，否则不需要写回。18简述具有快表的页式存储管理系统的地址变换过程。答：CPU给

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

32、、简述信号量S的物理含义。答：信号量是对系统中资源及其组织情况的抽象，由一个记录型(或结构体类型)数据表示。它包含两个数据项。第一个为value，表示可用资源数目：Svalue0时，表示有value个可用资源； Svalue0时，表示资源正好用完； Svalue0时，表示有-value个进程正在等待此类资源。第二个为L，为等待此类资源的进程PCB表链。21、什么叫物理地址？什么叫逻辑地址？什么叫地址映射？地址映射分哪几类？答：物理地址是内存中各存储单元的编号，即存储单元的真实地址，它是可识别、可寻址并实际存在的。 用户程序经过编译或汇编形成的目标代码，通常采用相对地址形式，其首地址为零，其余指

33、令中的地址都是相对首地址而定。这个相对地址就称为逻辑地址。 为了保证CPU执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地址转换成运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。 地址映射可分为两类： 静态地址映射在程序执行之前进行的重定位，在程序装入内存时一次性完成指令中地址的修改。 动态地址映射装入主存的程序仍然保持原来的逻辑地址，由逻辑地址到物理地址的转换在程序真正执行时进行。22、试述段页式存储管理的基本思想答：段页式存储管理的基本思想是： 用页式方法来分配和管理内存空间，即把内存划分成若干大小相等的页面； 用段式方法对用户程序按照其内在的逻辑关系划分成若

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

35、B可以开始，而进程B在开始之前先执行P操作，直到得到进程A的消息。同步关系如下：begins14=0;s24=0;s35=0;s46=0;s56=0Parbeginbegin 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三、程序顺序执行和并发执行分别有哪些特征？程序并发执行的条件是什么？对于下列语句，哪些能并发执行？哪些不能？说明

36、理由。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

37、)=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操作解决同步、互斥关系的例题五、请求分页的存储管理方式的页面置换算法。要求：课件上的例一、例二、例三必须会。六、死锁七、调度调度与死锁见课堂上给的例子。第 18 页