计算机操作系统第四版课后部分习题讲解

操作系统课后习题部分答案目录TOC\o"1-3"\h\u2135355617第一章 第一章1.操作系统的定义。答：操作系统是计算机系统中的一个系统软件，管理和控制计算机系统中的硬件和软件资源，合理地组织计算机的工作流程，以便有效利用这些资源为用户提供一个功能强、适用方便的工作环境，从而在计算机和用户之间起到接口的作用。2、设计现代OS的主要目标是什么?答：方便性：方便用户使用计算机；有效性：有效使用操作系统，让系统的资源利用率高，吞吐量达；可扩充性：方便增加新功能和模块，以及修改老的功能和模块以适应计算机硬件、体系结构和应用发展的要求；开放性：遵循设计标准规范，让操作系统与系统兼容，满足跨平台性要求。3.OS的作用可表现在哪几个方面?答：（1）操作系统是用于计算机硬件系统之间的接口，用户并不直接与计算机硬件打交道，而是通过操作系统提供的命令、系统调用以及图形化接口来使用计算机。（2）操作系统是计算机资源的管理者。处理的分配和控制，内存的分配和回收，I/O设备的分配和操纵，文件的存取、共享和保护工作都是由操作系统来完成的。（3）、操作系统实现了对计算机资源的抽象。操作系统是辅设在裸机上的多层软件，它不仅增强了系统的功能，而且还隐藏了对硬件操作的细节，从而实现了对计算机资源的抽象。4.操作系统发展的主要动力是什么？答：（1）计算机硬件升级和新硬件的出现；（2）提供新的服务，方便使用；（3）提高计算机资源利用率；（4）更正软件错误；（5）计算机体系结构的发展。5.何谓脱机I/O和联机I/O?答：脱机I/O是指由专门的I/O设备控制完成输入输出操作的方式，不受CPU运行操作系统来控制的方式。现在的联机I/O是指I/O操作必须要受到操作系统的控制，即I/O设备工作受CPU的控制完成，早期时候的联机I/O是指在人工操作方式下，CPU和I/O设备同时被同一个任务独占的操作方式。6.实现分时系统的关键问题是什么?应如何解决?答：分时系统最关键的问题是及时接收和及时处理的问题。及时接受问题用一个多路卡实现。及时处理采用作业直接进入内存，然后采用轮转运行方式进行处理。7.什么是实时系统?什么是硬实时任务和软实时任务?答：实时系统：能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统，分为实时控制系统和实时事务处理系统。硬实时任务：系统必须满足任务对截止时间的要求，否则会出现难以预测的后果。软实时任务：它也联系着一个截止时间，但并不严格，若错过了任务的截止时间，对系统产生的影响不会太大。8.操作系统的特征。答：（1）任务共行性：宏观上，指系统中有多个任务同时运行；微观上，指单处理机系统中的任务并发，即多个任务在单处理机上交替运行；或多处理机系统中的任务并行，即多个任务在多个处理机上同时运行。（2）资源共享性：宏观上，指多个任务可以同时使用的系统资源；微观上，指多个任务可以交替互斥地使用系统中的某个资源。（3）虚拟性：指将一个物理上的实体变为若干个逻辑上的对应物。如采用分时技术，将一台处理机虚拟为若干台虚拟机。还可以虚拟存储、虚拟设备、虚拟通道、虚拟文件、虚拟用户组以及虚拟网络等。（4）不确定性：程序执行结果不确定，程序不可再现；多道程序环境下，进城以异步方式执行。9.操作系统的任务。答：管理处理机；管理存储器；管理输入/输出设备；管理数据文件；提供接口服务。10.处理机管理有哪些主要功能?其主要任务是什么?答：（1）进程控制：创建和撤销进程以及控制进程的状态转换。（2）进程同步：协调、互斥访问临界资源，协调执行进度。（3）进程通信：进程间的信息交换。（4）进程调度：按一定的算法从进程就绪队列中选出一个进程，把处理机分配给它，使之运行。11.内存管理有哪些主要功能?其主要任务是什么?答：主要任务为：对多道程序的并发执行提供良好的环境；便于用户使用存储器；提高存储器的利用率；为尽量多的用户提供足够大的存储空间。主要功能：内存分配：静态分配/动态分配、连续分配/非连续分配；内存保护：系统内存空间、用户内存空间；地址映射：逻辑地址到物理地址映射；内存扩充：采用虚拟存储技术等让用户获得一个比实际内存空间大得多的内容空间。12.设备管理有哪些主要功能?其主要任务是什么?答：主要任务：为用户程序分配I/O设备；完成用户程序请求的I/O操作；提高处理机和I/O设备的利用率；改善人机界面。主要功能：缓冲管理；设备分配；设备处理：启动设备，中断处理；虚拟设备功能；RAID技术、磁盘调度。13.文件管理有哪些主要功能?其主要任务是什么?答：主要任务：管理用户文件和系统文件；管理文件的存储空间；保证文件数据的安全；方便用户使用文件。主要功能：文件目录管理；文件的逻辑组织与访问方式；存储空间的管理：文件的物理组织、空闲磁盘空间的管理；文件的共享与安全。14.什么是操作系统内核？微内核和强内核相比较具有的优点是什么？答：操作系统内核是指大多数操作系统的核心部分，包括管理处理机、存储器、I/O设备和文件等部分的核心部分构成。微内核与强内核相比较的有点是：具有更好的灵活性、开放性、可扩充性。15.经典问题分析：有三个进程A、B、C，他们使用同一个设备进行I/O操作，并且按A、B、C的指定次序执行。进程A共计运行180ms，每隔40ms需要进行I/O操作，I/O时间是20ms。进程B共计运行150ms，每隔20ms需要进行I/O操作，I/O时间是10ms，进程C共计运行160ms，每隔20ms需要进行I/O操作，I/O时间是20ms。假设调度的时间可以忽略，且同时到达内存，请画出在单道环境和多道程序环境下运行的时间关系图，并比较两者的效率。ABABC 计算I/O （2）多道环境下的时间关系图如下：AABC 在单道情况下，运行完成三个进程所需要的时间是490ms，在多道情况下，运行完成三个进程所需要的时间是310ms，所以多道比单道的效率高。第二章简答题2．什么是并发？什么是并行？用日常生活中的例子举例说明。答：并发是指在一段时间内多个进程同时运行，宏观上同时，微观上依次执行。并行是指若干进程在同一时刻同时运行。日常生活例子：以食堂打饭为例。并行：食堂排队打饭，如果把每个窗口看做CPU，每个同学看作进程，那么在某一刻在各个窗口打饭的同学可以认为是并行的。并发：同样以打饭为例，对其中一个窗口而言，在该窗口排队的每个同学只能依次获得打饭机会，因此可以认为该队列的每个同学是并发的（在食堂开始服务的时间段内都能打到饭）。3.在操作系统中为什么要引入进程的概念？它会产生什么样的影响？答：在多道程序环境下，程序并发执行时失去了封闭性、具有间断性及运行结果不可再现等特征。特别是运行结果不可再现这一特征，决定了程序不能参与并发执行。因此，为了能够使程序并发执行，必须引入“进程”概念对并发执行的程序加以描述和控制。引入进程这一概念后，通过PCB来管理进程运行过程中需要的描述信息、控制信息、管理信息等，可以使原来不能并发执行的程序可以并发执行。4.试说明PCB的作用具体表现在那些方面？为什么说PCB是进程存在的唯一标志？答：为了便于系统描述和管理程序的运行，操作系统为每个参与执行的程序（含数据）配置了一个专门的数据结构叫做PCB（又称为进程控制块）。PCB的作用是使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。主要表现在：1）作为独立运行的标志；2）能够间断运行；3）提供进程管理需要的信息；4）提供进程调度的信息；5）实现进程间的同步与通信。5.说明进程的三个基本状态及其相互转换的典型原因？答：进程运行过程中，由于竞争资源，因此会在不同状态中转换。三种基本状态分别是：就绪状态、运行状态和阻塞状态。三种基本状态转换的典型原因是：就绪状态的进程，当进程调度获得CPU时，可从就绪状态转换为执行状态。执行状态的进程，当有I/O请求时，会从执行状态转换为阻塞状态；在分时系统中，执行状态的进程时间片用完，会从执行状态转换为就绪状态。阻塞状态的进程，当I/O请求完成，会从阻塞状态转换为就绪状态。6.试从动态性、并发性和独立性上比较进程和程序？答：从动态性看：进程是程序的执行，由创建而产生，由调度而执行，由撤销而消亡；而程序是个静态实体，不管运行与否均存在。从并发性看：程序不能并发执行，而进程可以并发执行。从独立性看：进程是独立运行，独立获取资源及独立接受调度的基本单位；未建立PCB的程序是不能作为独立运行的单位参与运行。7.什么是操作系统内核？其主要功能有哪些？答：内核：通常将一些与硬件紧密相关的模块（如中断）、各种常用设备驱动程序以及运行频率较高的模块（时钟管理、进程调度等）都安排在紧靠硬件的软件层中，将它们常驻内存。主要功能：1、支撑功能。包括中断处理、时钟管理、原语操作等。2、资源管理功能。包括进程管理、存储器管理、设备管理等。8.什么临界资源和临界区？临界区管理的基本准则是什么？答：把在一段时间内只允许一个进程访问的资源称为临界资源。在每个进程中访问临界资源的那段代码。管理临界区的准则：(1)空闲让进。如果若干进程要求进入空闲的临界区，一次仅允许一个进程进入。(2)忙则等待。任何时候，处于临界区内的进程不可多于一个。(3)有限等待。进入临界区的进程要在有限时间内退出。(4)让权等待。如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象9.为什么要在操作系统中引入线程？试从调度性、并发性、拥有资源和系统开销4个方面对进程和线程进行比较。答：在OS中引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，那么，在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。进程与线程的比较：从调度性来看：线程是调度和分派的基本单位，而进程是资源拥有的基本单位，线程共享进程的全部资源。一个进程内的线程切换到另一个进程内的线程时要引起进程的切换。从并发性来看：在引入线程的OS中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而OS具有更好的并发性，从而能更好地提高系统的资利用率及系统的吞吐量。从拥有资源来看：进程是拥有资源的基本单位，线程不拥有资源，但继承进程的资源。从系统开销来看：创建或撒消进程，系统都要为之分配或回收资源，OS的开销将大于创建线程或撒消线程的开消。类似地在进程切换时，涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。因此，进程切换的开销也远大于线程切换的开销。综合题1.画出下列语句的前趋图：并指出哪些语句可以并发执行？S1:a=x+yS2:b=z+1S3:c=a-bS4:w=c+1答：可画出如图所示的前趋关系。可以看出：S3必须在a和b被赋值后方能执行；S4必须在S3之后执行；其中，S1和S2可以并发执行，因为它们彼此互不依赖。2.假设有输入、加工和输出3个并发进程共享一个缓冲区B，输入进程负责从输入设备读入一条记录，每读一条记录后把它存放在缓冲区B中，加工进程在缓冲区B中加工输入进程存入的记录。输出进程负责把加工后的记录打印输出。缓冲区B中每次只能存放一条记录，当记录被加工输出后，缓冲区B中才可存放下—条新记录。请用P、V操作来描述它们并发执行时能正确工作的程序。答：设fullB,emptyB分别为缓冲区B装满数据和空的信号量，Work为数据加工信号量，0为未加工，1为加工后的数据。varfullB,emptyB,Work,:semaphore:=0,1,0;BeginParbeginProcedure输入:beginrepeatwait(emptyB);读一条记录放入缓冲区中signal(fullB);untilfalse;endProcedure加工:beginrepeatwait(fullB);在缓冲区B中进行加工；signal(work);untilfalse;endProcedure输出:beginrepeatwait(work);打印输出；signal(emptyB);untilfalse;endparendend3.设有一个成品仓库，总共能够存放10台成品，生产者生产产品放入仓库，消费者从仓库中取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存入和取出只能分别执行，使用wait()和signal()操作来实现该方案。答：Varmutex,full,empty:semaphore:=1,0,10;BeginParbeginprocedure:beginrepeat生产一个成品；wait(empty);wait(mutex);将产品存入仓库；signal(mutex);signal(full);untilfalse;endconsumer:beginrepeatwait(full);wait(mutex);将产品从仓库取出；signal(mutex);signal(empty);消费成品；untilfalse;endparendend4.有一窄桥每次只能过一辆车，每次为了保证正常通行，只要桥上没有车，就允许一端的车过桥，待其全部过完后才允许另一端的车过桥。请用信号量和PV操作写出过窄桥的同步算法。答：设mutex为桥的互斥信号量，rmutex,lmutex分别为向右，向左过桥的互斥信号量，设rightcount,leftcount分别为向右向左行驶的汽车数量Varmutex,rmutex,lmutex,samphore:=1,1;Rightcount,leftcount:integer:=0;Parbegin向右行驶:beginP(rmutex);Ifrightcount=0thenp(mutex);rightcount:=rightcount+1;V(rmutex);开始过桥；P(rmutex);rightcount:=rightcount－1;Ifrightcount=0thenv(mutex);V(rmutex);End向左行驶:beginP(lmutex);Ifleftcount=0thenp(mutex);leftcount:=leftcount+1;V(lmutex);开始过桥；P(lmutex);leftcount:=leftcount－1;Ifleftcount=0thenv(mutex);V(lmutex);EndParend5．某招待所有100个床位，住宿者住入要先登记(在登记表上填写姓名及床位号)，离去时要撤销登记(在登记表上删去姓名和床位号)。请给出住宿登记及撤销登记过程的算法描述。答：设mutex=1为登记信号量Empty=100为床位登记：beginRepeatWait(empty)Wait(mutex)登记表上填写姓名及床位号Signal(mutex)Untilfalseend撤销登记：BeginRepeatWait(mutex)撤销登记；Signal(mutex)Signal(empty)Untilfalse6．有3个进程PA，PB，PC合作解决文件打印问题：PA将文件记录N从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区S1的内容复制到缓冲区2，每执行一次复制—个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P，V操作来保证文件的正确打印。答：Varempty1,full1,empty2,full2:semaphore:=1,0,1,0;PA:beginrepeatwait(empty1);读出记录N，将N写入缓冲区1；signal(full1);untilfalse;endPB:beginrepeatwait(full1);wait(empty2)将记录N从缓冲区1复制到缓冲区2中；signal(empty1);signal(full2);untilfalse;endPC:beginrepeatwait(full2);从缓冲区2中取数据打印；signal(empty2);untilfalse;end第三章一、问答题1.高级调度与低级调度的主要任务是什么?为什么要引入中级调度?答：高级调度的任务是根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。进程调度的任务主要有(1)保存处理机的现场信息；(2)按某种算法选取进程；(3)把处理器分配给进程。当内存空间非常紧张时，或处理机找不到可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选取一个挂起状态的进程调度到内存（换入）。在换入和换出的过程中，发生了中程调度，只有支持进程挂起的操作系统才具有中程调度功能，目的是为了提高内存的利用率和系统的吞吐量。2.在选择调度方式和调度算法时，应遵循的准则是什么?答：满足用户对响应时间、周转时间、截止时间的要求；满足系统的需求，尽量提高系统吞吐量和处理机利用率，保证各类资源的平衡使用、公平性及优先级。3.在作业调度中应如何确定接纳多少个作业和接纳哪些作业?答：选择多少个作业进入内存，为之创建进程，取决于多道程序的度，即允许同时在内存中运行的进程数。选择哪些算法，取决于长程调度算法。4.何谓静态和动态优先级?确定静态优先级的依据是什么?答：一旦确定下来，进程在运行期间它的优先级一直不变化的优先级叫静态优先级。系统首先为一个进程赋予初始优先级，该优先级会随着进程的运行而改变，这样的优先级叫动态优先级。确定静态优先级的依据：(1)进程类型；(2)进程对资源的需求；(3)用户要求。5.试分别说明可重用资源和可消耗资源的性质。答：可重用性资源是一种可供用户重复使用多次的资源，它具有如下性质：(1)每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。(2)进程在使用可重用性资源时，须按照这样的顺序：①请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。②使用资源。进程对资源进行操作，如用打印机进行打印；③释放资源。当进程使用完后自己释放资源。(3)系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质：（1）每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0。（2）进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。③进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。6.试比较FCFS和SJF两种进程调度算法。答：FCFS按照进程到达的先后顺序排队，每次调度队首的进程，属于非剥夺调度方式，实现简单，看似公平。但对于那些后进入队列而运行时间较短的进程，或I/O型的进程而言，可能需要等待较长时间。SJF属于非剥夺方式调度算法。当需要调度作业（进程）时，通过计算判断就绪队列中哪一个进程预计执行时间最短，或后备作业队列中哪一个或几个作业预计执行时间最短，就调度谁。当某个进程获得处理机，直到其执行完成，或需要等待某个事件而阻塞时，才自动释放处理机，系统又调度新的进程或作业。与FCFS算法比较，短进程优先调度算法改善了系统的性能，降低了系统的平均等待时间，提高了系统的吞吐量。但是该算法也存在一些问题：（1）很难准确地预测进程的执行时间；（2）可能导致长进程饥饿，对长进程不利。（3）采用非剥夺方式，未考虑进程的紧迫程度，不适合于分时系统或者事务处理系统。7.在时间片轮转法中，应如何确定时间片的大小?答：T=N*Q，Q表示时间片大小，T表示响应时间，N表示就绪队列进程数。时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素，能保证80%的进程能够在一个时间片内完成就可以。8.何谓死锁?产生死锁的原因和必要条件是什么?答：可以描述为多个进程因为竞争资源，或执行时推进的顺序不当，或相互通信而永久阻塞现象，如果没有外力作用，这种现象将永远保持下去。产生死锁的原因是进程竞争资源，即资源的数量小于进程数量而引起的。死锁产生的条件：（1）互斥：竞争的资源一次只能被一个进程使用。（2）占有且等待：当一个进程占有一些资源，同时又申请新的资源。如果新资源申请失败，进程将占有资源且阻塞等待。（3）非剥夺：进程已占有的资源不能被其他进程强行剥夺。（4）循环等待：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程都占有一些资源，同时又申请环形请求链中下一个进程所占有的资源。前三个条件是产生死锁的必要条件，第四个条件是充分条件，四个条件共同构成死锁产生的充分必要条件。9.解决死锁的方法有哪些？答：（1）预防死锁，指进程申请资源必须遵循某些预先制定的限制条件，以破坏产生死锁的四个必要条件之一或几个，防止死锁发生。（2）避免死锁指，当进程申请系统资源时，需要首先判断（预测），如果满足这次资源的请求是否会导致死锁，可能会导致死锁的资源请求将会被拒绝。让请求资源进程的进程阻塞等待，直到其所需的资源可分配为止。（3）当进程申请资源时，不进行任何限制，即允许死锁发生。但要求系统定期或不定期检测是否有死锁发生。当检测到死锁时，再力求解除死锁。10.实时系统中采用的调度算法可以有如下几种：1）非抢占优先权调度算法。2）立即抢占的优先权调度算法。3）时间片轮转调度算法。4）基于时钟中断抢占的优先权调度算法。按实时要求的严格程度由低到高的顺序是什么，请写出分析过程。答：3—1—4—2。时间片轮转算法是按进程先后达到的时间排序，并且为每个进程分配时间片，只有时间片到才能切换，时间片未到不能剥夺进程的执，所以时间要求严格度低。非抢占式优先权调度算法，由于具有优先权，高优先权可以打断低优先权，只要将时间要求紧迫的任务赋予高优先权，即可满足时间要求较严格的需求。但是在低优先权进程执行过程中是不能被打断的，所以其优先权能响应的时间紧迫程度会打折扣。基于时钟中断抢占的优先权调度算法，可以让高优先权的进程抢占低优先权的进程，但是只有在时钟中段到来的时候才能抢占。立即抢占的优先权调度算法能够让高优先权的进程在任何时刻抢占CPU。二、综合题1.一个计算机系统中拥有6台打印机，现有N个进程竞争使用，每个进程要求2台打印机，试问：N的值如何选取时系统中绝对不会出现死锁?答：该问题类似于哲学家问题，让N<=资源数-1即可，即N<=6-1,有N<=5。2.多道批处理系统中配有一台处理器和两台外设(Dl、D2)，用户存储空间为100MB。已知系统采用可抢占的高优先数调度算法和不允许移动的可变分区分配策略，设备分配按照动态分配原则。今有4个作业同时提交给系统，如下表所示。作业名优先数运行时间内存需求（M）A65分钟50B34分钟10C87分钟60D45分钟20作业运行时间和I/O时间按下述顺序进行：A．CPU（1分钟），D1（2分钟），D2（2分钟）B．CPU（3分钟），D1（1分钟）C．CPU（2分钟），D1（3分钟），D2（2分钟）D．CPU（4分钟），D1（1分钟）忽略辅助操作，请给出4个作业的平均周转时间？解：按照高优先数调度算法，即优先数越高，越优先得到调度的策略，且四个作业同时提交系统，根据题意及条件，C优先被调度，为其创建进程并分配内存空间。其调度时系统状况如下表：作业名优先数CPUD1D2内存需求（M）系统剩余内存（M）C82分钟3分钟2分钟6040当其2分钟以后，由于开始I/O操作，所以按照调度策略，调入下一个高优先数的作业A，为其创建进程，并为它分配内存空间，但由于内存空间不满足需要，该进程阻塞，系统转而调度D，为其创建进程并分配存储空间。调度D执行的系统情况如下表：作业名优先数CPUD1D2内存需求（M）系统剩余内存（M）C82分钟3分钟2分钟6040D44分钟1分钟02020当D执行3分钟后，C释放D1资源，使用D2资源。当D执行4分钟后，可以使用D1资源，且进程切换，系统调度B，为其创建进程，并分配存储空间。此时系统状态如图：作业名优先数CPUD1D2内存需求（M）系统剩余内存（M）C82分钟3分钟2分钟6040D44分钟1分钟02020B33分钟1分钟01010当B执行1分钟后，C和D同时完成，系统回收其内存资源、D1和D2。系统状态如图：作业名优先数CPUD1D2内存需求（M）系统剩余内存（M）B31分钟1分钟01090由于采用可抢占式，此时内存资源满足A的需求，唤醒A执行，B进程阻塞。此时系统状态如图：作业名优先数CPUD1D2内存需求（M）系统剩余内存（M）B31分钟（阻塞）1分钟01090A61分钟2分钟2分钟5040此时A进程执行1分钟后，使用D1，然后使用D2，唤醒B执行B执行完剩余的2分钟后，A刚好使用完毕D1，B可以顺利使用D1。B使用D1的1分钟后结束进程，释放资源，再过1分钟后，A使用完D2，进程A结束，释放资源，此时所有进程结束，系统的资源状况恢复到初始状态。在这个过程中，C的周转时间为7分钟，D的周转时间为：2+5=7（分钟）；B的周转时间为：等待时间（2+4+1）分钟+执行处理时间4分钟=11分钟；A的周转时间为：等待时间（2+4+1）分钟+执行处理时间5分钟=12分钟。系统平均周转时间为：（7+7+11+12）/4=9.25（分钟）3.设有4个作业J1，J2，J3，J4．它们的到达时间和要求服务时间如下表所示。若这4个作业在—台处理机上按单道方式运行，采用响应比高者优先调度算法。1）试写出各作业的执行顺序；2）求各作业的周转时间及平均周转时间。3）求各作业的带权周转时间及平均带权周转时间。作业到达时间服务时间J18:002小时J28:3040分钟J39:0025分钟J49:3030分钟解：（1）响应比高者优先算法属于非剥夺算法。J1先到达，优先调度，服务时间120分钟，10点钟执行完毕时，此时系统其他等待进程的响应比为：RJ2=1+(10：00-8：30)/40=3.25RJ3=1+(10：00-9:00)/25=3.4RJ4=1+(10：00-9：30)/30=2根据响应比高低，优先调度J3执行。J3执行25分钟，在10：25时完成，此时计算J2和J4的响应比为：RJ2=1+(10：25-8：30)/40=6.75RJ4=1+(10：25-9：30)/30=2.83根据响应比高低，优先调度J2执行,J2执行40分钟，在11:05分完成。此时系统只剩下J4，调度J4执行，执行30分钟，于11:35分完成。所以系统调度执行顺序为：J1，J3，J2，J4。（2）J1的周转时间为：10：00-8:00=120分钟； J2的周转时间为：11:05-8:30=155分钟； J3的周转时间为：10:25-9:00=85分钟； J4的周转时间为：11:35-9:30=125分钟。系统的平均周转时间为：（120+155+85+125）/4=121.25（分钟）。（3）带权周转时间=周转时间/系统服务时间，由此可以计算； J1的带权周转时间为：120分钟/120分钟=1； J2的带权周转时间为：155分钟/40分钟=3.875； J3的带权周转时间为：85分钟/25分钟=3.4； J4的带权周转时间为：125分钟/30分钟=4.17系统平均带权周转时间为：（1+3.875+3.4+4.17）/4=3.114.在银行家算法的例子中，如果P0发出的请求向量由Request(0,2,0)改为Request(0,1,0)，问系统可否将资源分配给它?解：根据教材例子，P1申请了（1，0，2）并获得该资源后，系统资源情况如下图：此时P0申请(0,2,0)，经过分析不安全，系统不能分配给它请求的资源。如果改为申请（0，1，0），Request(0,1,0)<Need(7,4,3);Request1(0,1,0)≤Available1(2,3,0),系统可以试探地分配，分配后系统资源情况如下：由于剩下的资源已经无法满足任何一个进程的需求，所以此时不能满足P0的请求。5.在银行家算法中，若出现下述资源分配情况，试问：

(1)该状态是否安全?(2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它?解：（1）此刻能够找到一个安全序列P0，P3,P4,P1,P2,此刻系统是安全的。（2）若P2申请（1,2,2,2）后，系统判断Request(1,2,02,2)<Need(2,3,5,6);Request1(0,1,0)≤Available1(1,6,2,2),可以试着预分配。但是分配之后系统可用资源还剩0,4,0,0，已经无法满足任何一个进程的资源需求，系统不能将资源分配给它。第四章1、什么是静态链接、装入时动态链接和运行时的动态链接？答：静态链接是指在程序运行前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开的链接方式。装入时动态链接是指将用户源程序编译后得到的一组目标模块，在装入内存时采用边装入边链接的链接方式。运行时动态链接是指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接2、简述分页系统和分段系统的异同点答：相同点：都采用离散分配的方式来提高内存利用率；都通过地址变换机构来实现地址变换。区别：（1）页是信息的物理单位，分页是为了提高内存的利用率。段是信息的逻辑单位，含有一组意义相对比较完整的信息。分段是为了更好地满足用户的需求。（2）页的大小固定且由系统决定。段的长度不固定，且由用户所编写的程序决定。（3）分页的地址空间是唯一的，程序员只需要利用一个记忆符，便可以表示一个地址。分段的地址空间是二维的，程序员在标识一个地址时，既需要给出段名，又需要给出段内地址。3、什么情况下需要重定位？为什么要引入重定位？答：源程序经过编译、链接产生的装入模块一般是从0开始编制的，其中的地址都是相对于起始地址的相对地址。在将它装入内存时，其分配到的内存空间的起始地址通常不为0，因此指令和数据的实际物理地址和装入模块中的相对地址不一致，此时，为了使程序能够正确执行，必须将相对地址转换为物理地址，即进行重定位。4、在具有快表的段页式存储管理方式中，如何实现地址变换？答：在CPU给出有效地址后，由地址变换机构自动将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号比较，若找到匹配页号，表示要访问的页表项在快表中。可直接从快表读出该页对应物理块号，送到物理地址寄存器中。如快表中没有对应页表项，则再访问内存页表，找到后，把从页表项中读出物理块号送地址寄存器；同时修改快表，将此页表项存入快表。但若寄存器已满，则OS必须找到合适的页表项换出5、什么是对换技术？为什么要引入对换？对换有哪些类型？答：对换时指内存中暂时不能运行的进程或者暂时不用的程序或数据换出到外存上，以便腾出足够的内存空间，把已经具备运行条件的进程或者进程所需要的程序和数据换入内存。目的是解决内存紧张问题，带来的好处是进一步提高了处理机的利用率和系统吞吐量。对换类型：整体对换、页面（分段）对换。6、在采用首次适应算法回收内存时，可能出现哪几种情况？应怎样处理这些情况？答：在采用首次适应算法回收内存时可能出现4种情况：（1）回收区前邻空闲区。将回收区与前邻空闲区合并，将前邻空闲区大小修改为两者之和。（2）回收区后邻空闲区。将两区合并，改后邻空闲区始址为回收区始址，大小为两者之和。（3）回收区前后均邻空闲区。将三个分区合并，修改前邻空闲区大小为三者之和。（4）回收区前后均不邻空闲区。为回收区设置空闲区表项，填入回收区始址和大小并插入空闲区队列。7、给定内存空闲分区，按地址从小到大为：100K、500K、200K、300K、600K。现有用户进程依次分别212K、417K、112K、426K。（1）分别用首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法将它们装入到内存的哪个分区？（2）哪个算法最有效利用内存？答：（1）按题意地址从小到大进行分区，如图所示：分区号分区长1100K2500K3200K4300K5600K1)首次适应算法：212K选中分区2，这时分区2还剩下288KB。417K选中分区5，这时分区5还剩下183KB。112K选中分区2，这时分区2还剩下176KB。426KB无分区能满足要求，等待。2）循环首次适应算法：本题目中与首次适应算法相同。3）最佳适应算法：212K选中分区4，这时分区4还剩88KB。417K选中分区2，这时分区2还剩83KB。112K选中分区3，这时分区3还剩88K。426K选中分区5，这时分区5还剩174KB。4）最坏适应算法：212K选中分区5，这时分区5还剩388KB。417K选中分区2，这时分区2还剩83KB。112K选中分区5，这时分区5还剩176KB。426K无分区能满足，等待。（2）最佳适应算法最有效使用内存。8、某系统采用页式存储管理策略，拥有逻辑空间32页，每页2KB，拥有物理空间1MB。（1）写出逻辑地址的格式。（2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？（3）如果物理空间减少一半，页表结构应相应作怎样的改变？答：（1）该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位来描述；而每页为2KB，因此，页内地址必须用11位来描述，这样可得到它的逻辑地址格式：1511100页号页内地址（2）每个进程最多有32个页面，因此，进程的页表项最多为32项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块块号，1MB的物理空间可分为29个内存块，故每个页表项至少有9位。（3）如果物理地址空间减半，则页表中页表项数仍不变，但每项的长度可减少1位。9、已知某分页系统，主存容量为64K字节，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中，试：将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。答：逻辑地址1023。1023/1K，得到页号为0，页内地址为1023，查页表找到对应的物理块号为2，因此物理地址为2*1K+1023=3071.逻辑地址2500。2500/1K，得到页号为2，页内地址为452，查页表找到对应的物理块号为6，因此物理地址为6*1K+452=6596.逻辑地址3500。3500/1K，得到页号为3，页内地址为428，查页表找到对应的物理块号为7，因此物理地址为7*1K+428=7596.逻辑地址4500。4500/1K，得到页号为4，页内地址为404，查页表找到对应的物理块号为2，因此物理地址为2*1K+1023=3071.10、对于下表所示的段表，请将逻辑地址（0,137）,(1,4000),(2,3600),(5,239)转换成物理地址。段号内存始址段长050K10K160K3K270K5K3120K8K4150K4K答：（1）段号0小于段表长5，故段号合法；由段表的第0项可获得段的内存始址位50K，段长位10K，由于段内地址137，小于段长10K，故段内地址也是合法的，因此可以得出对应的物理地址为50K+137=51337（2）段号1小于段表长5，故段号合法；由段表的第1项可获得段的内存始址位60K，段长位3K，经检查，段内地址4000超过段长3K，因此产生越界中断。（3）段号2小于段表长5，故段号合法；由段表的第2项可获得段的内存始址位70K，段长位5K，由于段内地址3600，小于段长10K，故段内地址也是合法的，因此可以得出对应的物理地址为70K+3600=75280.（4）段号5等于段表长，故段号不合法，产生越界中断。第五章1、什么是程序局部性原理？程序局部性主要体现在哪里方面？答：程序局部性原理是指程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限在某个区域。局部性主要表现在以下2个方面：（1）时间局部性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某个数据被访问，则不久以后该数据可能被再次访问。产生局部性的典型原因是程序中存在中大量的循环操作。（2）空间局部性。一旦程序访问了某个存储单元，则不久以后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型情况是程序的顺序执行。2、什么是虚拟存储器？虚拟存储区有什么特征？答：虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本又接近于外存。虚拟存储器有以下特征：（1）多次性。一个作业中的程序和数据，无需在作业运行时一次性地全部装入内存，允许被分成多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。（2）对换性。一个作业中的程序和数据，无需在作业运行时一直常驻内存，允许在作业的运行过程中进行换进换出。即在进程运行期间，运行将那些暂时不使用的代码和数据从内存调至外存的对换去（换出），待需要时再将它们从外存调至内存（换进）。（3）虚拟性。指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性以多次性和对换性位基础。3、在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？答：页表应包括：页号、物理块号、状态位P、访问字段A、修改位M和外存地址。其中状态位P指示该页是否调入内存，供程序访问时参考；访问字段A用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考；修改位M表示该页在调入内存后是否被修改过；外存地址用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。4、在请求分页系统中，应从何处将所需页面调入内存？答：请求分页系统中的缺页从何处调入内存分三种情况：（1）系统拥有足够对换区空间时，可以全部从对换区调入所需页面，提高调页速度。在进程运行前将与该进程有关的文件从文件区拷贝到对换区。（2）系统缺少足够对换区空间时，不被修改的文件直接从文件区调入；当换出这些页面时，未被修改的不必换出，再调入时，仍从文件区直接调入。对于可能修改的，在换出时便调到对换区，以后需要时再从对换区调入。（3）UNIX方式。未运行页面从文件区调入。曾经运行过但被换出页面，下次从对换区调入。UNIX系统允许页面共享，某进程请求的页面有可能已调入内存，直接使用不再调入。5、简述产生“抖动”的原因以及“抖动”的预防方法。答：产生“抖动”的原因：同时在系统中运行的进程太多，分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺少的页面调入内存。这使得系统中排队等待页面调进/调出的进程数量增加，对磁盘的有效访问也随之增加，造成每个进程的大部分时间都用于页面的换进/换出。“抖动”预防方法：（1）采取局部置换策略；（2）把工作集算法融入到处理机调度中；（3）利用“L=S”准则调节缺页率；（4）选择暂停的进程。6、在请求分段系统中，段表项应包括哪些数据项？答：段名、段长、段基址、存储方式、访问字段A、修改位M、存在位P、增补位、外存始址。7、在一个请求分页系统中，假如一个作业的页面走向是2,3,2,1,5,2,4,5,3,2,5,2。目前没有任何页面装入内存，当分配给该作业的物理块数为3时，请分别计算采用OPT算法、FIFO算法、LRU算法、CLOCK算法时，访问过程中所发生的缺页次数和缺页率。答（1）OPT算法232152453252页框1222222444222页框233333333333页框3155555555是否缺页是是是是是是缺页6次，缺页率=6/12=50%（2）FIFO算法232152453252页框1222231552243页框233315224435页框3152443352是否缺页是是是是是是是是是缺页9次，缺页率=9/12=75%（3）LRU算法232152453252页框1232152453252页框223215245325页框3321524533是否缺页是是是是是是是缺页7次，缺页率=7/12=58.3%（4）CLOCK算法232152453252页框12*2*2*->2*5*5*->5*->5*3*3*->3*->3*页框2->3*3*3*->32*2*2*->2->2*22*页框3->->1*1->14*4*445*5*是否缺页是是是是是是是是缺页8次，缺页率=8/12=66.7%第六章一、简答题1．有几种I／O控制方式？各有何持点？答：I／O控制方式有4种，即程序直接控制方式、中断控制方式、DMA方式和通道控制方式。(1)程序直接控制方式优点是控制简单，也不需要多少硬件支持。但CPU和外设只能串行工作，且CPU的大部分时间处于循环测试状态，使CPU的利用率大大降低；CPU在一段时间内只能和一台外设交换数据信息，从而不能实现设备之间的并行工作；由于程序直接控制方式依靠测试设备状态标志来控制数据传送，因此．无法发现和处理因设备或其他硬件所产生的错误。所以，程序直接控制方式只适用于那些CPU执行速度较慢且外设较少的。(2)中断控制方式优点是能实现CPU与设备以及设备与设备间的并行操作，CPU的利用率较程序直接控制方式大大提高。但由于I／O控制器的数据缓冲寄存器装满数据后将会发出中断且数据缓冲寄存器通常较小，因此在一次数据传送过程中发生中断次数较多而耗去大量CPU时间；如果系统中配置的外设数目较多，且都以中断方式进行并行操作，则可能耗去大量CPU时间或因CPU来不及处理而造成数据丢失。(3)DMA方式与中断方式相比，DMA方式是在一批数据传送完成后中断CPU，从而大大减少了CPU进行中断处理的次数，且DMA方式下的数据传送是在DMA控制器控制下完成的。但DMA方式仍有一定的局限，如对外设的管理和某些操作仍由CPU控制，多个DMA控制器的使用也不经济。(4)通道控制方式通道是一个专管I／O控制的处理机。在通道控制方式下，CPU只需发出I／O指令，通道就能完成相应的I／O操作，并在操作结束时向CPU发出中断信号；同时一个通道还能控制多台外设。但是，通道价格较高，从经济的角度出发不宜过多使用。2．为什么要引入设备独立性？如何实现设备独立性？答：用户不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备之间分开，再通过其他途径建立逻辑设备和物理设备之间的映射，设备的这种特性就是“设备独立性”。好处：应用程序与具体物理设备无关，系统增减或变更设备时对源程序不必加以修改；易于应对I/O设备故障，提高系统可靠性；增加设备分配的灵活性，更有效地利用逻辑设备资源，实现多道程序设计。3.SPOOLing系统由哪几部分组成？以打印机为例说明如何利用SPOOLing技术实现多个进程对打印机的共享？答：SPOOLING系统由磁盘上的输入井和输出井，内存中的输入输出缓冲区以及输入输出进程构成。在用SPOOLING技术共享打印机时，对所有提出请求的用户进程，系统接受他们的请求时，并不真正八大应急分配给它们，而是给他们两件事：1、由输出进程在输出井中为他申请一个空闲缓冲区，并将要答应的数据送入其中。2、输出进程给用户进程申请一张空白的打印请求表，把用户的打印请求填入表里，再将该表挂到打印队列上。至此用户进程觉得它的打印进程已经完成，而不必等待满速的打印过程完成，当打印机空闲时，输出进程从打印表中取出一个打印请求表，将打印数据传进进程的输出井的内存缓冲区，再有打印机输出打印依次处理打印表中的缓冲数据，直到为空，系统将每个打印请求进程在输出井中分配一个存储区是的每个用户进程在逻辑上独占一个打印及，从而实现打印机共享。二、综合题4.假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。(1)先来先服务算法FCFS；(2)最短查找时间优先算法SSTF；(3)扫描算法SCAN。(4)电梯调度。答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。(2)最短查找时间优先算法SSTF为162依次为143-147-150-130-102-94-91-86-175-177。(3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。(4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-130-102-94-91-86。为148(先向地址小的方向)依次为143-130-102-94-91-86-147-150-175-177。5.旋转型设备上信息的优化分布能减少为若干个I/O服务的总时间。设磁鼓上分为20个区，每区存放一个记录，磁鼓旋转一周需20毫秒，读出每个记录平均需用1毫秒，读出后经2毫秒处理，再继续处理下一个记录。在不知当前磁鼓位置的情况下：（1）顺序存放记录1、……，记录20时，试计算读出并处理20个记录的总时间；（2）给出优先分布20个记录的一种方案，使得所花的总处理时间减少，且计算出这个方案所花的总时间。答：（1）定位第1个记录需10ms。读出第1个记录，处理花2ms，这时已到了第4个记录，再转过18个记录(花18ms)才能找到记录2，所以，读出并处理20个记录的总时间：10+3+(1+2+18)×19=13+21×19=412ms（2）如果给出优先分布20个记录的方案为：1，8，15，2，9，16，3，10，17，4，11，18，5，12，19，6，13，20，7，14。当读出第1个记录，花2ms处理后，恰好就可以处理记录2，省去了寻找下一个记录的时间，读出并处理20个记录的总时间：10+3+3×19=13+247=260ms第七章一、简答题1．什么是文件？它包含哪些类型及特点?答：文件是信息的一种组织形式，是存储在外存上的具有标识名的一组相关信息集合。文件包含的内容有：源程序、二进制代码、文本文档、数据、表格、声音和图像等。文件的特点如下：(1)文件具有保存性，它被存储在某种存储介质上，长期保存和多次使用。(2)文件是按名存取的，每个文件具有惟一的标识名，通过标识名(文件名)来存取文件中的信息，而不需了解文件在存储介质上的具体物理位置。(3)文件的内容是一组信息的集合，信息可以是源程序、二进制代码、文本文档、数据、表格、声音和图像等。2．什么是文件的逻辑结构？它有哪几种组织方式？答：文件的逻辑结构是用户可见结构。组织方式：一种是无结构的流式文件，是指对文件内信息不再划分单位，它是依次的一串字符流构成的文件。一种是有结构的记录式文件，是用户把文件内的信息按逻辑上独立的含义划分信息单位，每个单位称为一个逻辑记录（简称记录）。3．什么是文件系统，文件系统的主要功能包括哪些？答