操作系统,原理,徐宗元复习课件

操作系统

“操作系统”，徐宗元，

高等教育出版社，2005年第二版复习考试题型单项选择题计算填空题

计算题编程填空题问答题复习资料教学专栏教学课程操作系统原理课件学习操作系统原理(发布日期2004-11.29)复习测试教学专栏课程辅导材料维护“选择课程”选择“操作系统原理”下载文件“操作系统原理教学大纲和网上作业”、“复习大纲”第一章习题选2.操作系统是一种﹎﹎A﹎﹎，在操作系统中采用多道程序设计方式能提高CPU和外部设备的﹎﹎B﹎﹎。一般来说，为了实现多道程序设计，计算机需要有﹎﹎C﹎﹎。A:(1)通用软件；(2)系统软件；(3)应用软件；(4)软件包。B:(1)利用效率；(2)可靠性；(3)稳定性；(4)兼容性。C：(1)更大的内存；(2)更快的外部设备；(3)更快的CPU；(4)更先进的终端；2.A-2B-1C-1习题-1选10.分时系统中，为使多个用户能够同时与系统交互，最关键的问题是﹎﹎A﹎﹎，当用户数目为100时，为保证响应不超过2秒；此时的时间片最大应为﹎﹎B﹎﹎。A：(1)计算机具有足够的运行速度；(2)内存容量应足够大；(3)系统能及时地接收多个用户输入；(4)能在一短的时间内，使所有用户程序都能运行；(5)能快速进行内外存对换。B：(1)10ms；(2)20ms；(3)50ms；(4)100ms；(5)200ms。10.A-4B-2习题-2选8.在设计分时操作系统时，首先要考虑的是﹎﹎A﹎﹎；在设计实时操作系统时，首先要考虑的是﹎﹎B﹎﹎；在设计批处理系统时，首先要考虑的是﹎﹎C﹎﹎。A、B、C：(1)灵活性和可适应性；(2)交互性和响应时间；(3)周转时间和系统吞吐量；(4)实时性和可靠性。8.A-2B-4C-3习题-4选17．脱机用户接口是配置在﹎﹎A﹎﹎操作系统中的，它是由一组﹎﹎B﹎﹎所组成，联机用户接口是由一组﹎﹎C﹎﹎所组成，而程序接口则是由一组﹎﹎D﹎﹎所组成。A：（1）微机；（2）批处理；（3）分时；（4）实时。B、C、D：（1）系统调用；（2）库函数；（3）键盘命令；（4）作业控制语言。17.A-2B-4C-3D-1第二章习题选10：在操作系统中进程是一个具有一定独立功能程序在某个数据集合上的一次﹎﹎A﹎﹎，进程是一个﹎﹎B﹎﹎概念，而程序是一个﹎﹎C﹎﹎的概念。在一单处理机中，若有5个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有﹎﹎D﹎﹎个，最少有﹎﹎E﹎﹎个。

A：(1)并发活动；(2)运行活动；(3)单独操作；(4)关联操作。B，C：(1)组合态；(2)关联态；(3)运行态；(4)等待态；(5)静态；(6)动态。D，E：(1)1；(2)2；(3)3；(4)4；(5)5；(6)0。2.A-2B-6C-5D-4E-6习题-2选7：从静态角度看，进程由﹎﹎A﹎﹎、﹎﹎B﹎﹎和﹎﹎C﹎﹎三部分组成，用户可通过﹎﹎D﹎﹎建立和撤消进程，通常用户进程被建立后，﹎﹎E﹎﹎。A：(1)JCB；(2)DCB；(3)PCB；(4)PMT。B:(1)程序段；(2)文件体；(3)I/O；(4)子程序。C：(1)文件描述块；(2)数据空间；(3)EOF；(4)I/O缓冲区。D：(1)函数调用；(2)宏指令；(3)系统调用；(4)过程调用。E：(1)便一直存在于系统中，直到被操作人员撤消；(2)随着作业运行正常或不正常结束而撤消；(3)随着时间片轮转而撤消与建立；(4)随着进程的阻塞或唤醒而撤消与建立。4.A-3B-1C-2D-3E-2习题-4选15：对于记录型信号量，在执行一次P操作时，信号量的值应当为﹎﹎A﹎﹎；当其值为﹎﹎B﹎﹎时，进程应阻塞。在执行V操作时，信号量的值应当﹎﹎C﹎﹎；当其值为﹎﹎D﹎﹎时，应唤醒阻塞队列中的进程。A，C：(1)不变；(2)加1；(3)减1；(4)加指定数值；(5)减指定数值。B，D：(1)大于0；(2)小于0；(3)大于等于0；(4)小于等于0。1.A-3B-2C-2D-4习题-5选8：在操作系统中，解决进程间的﹎﹎A﹎﹎两种基本关系，往往运用对信号量进行﹎﹎B﹎﹎的﹎﹎C﹎﹎，例如，为保证系统数据库的完整性，可以把信号量定义为某个库文件（或记录）的锁，初值为1，任何进程存取该库文件（或记录）之前先对它作一个﹎﹎D﹎﹎，存取之后对它作一个﹎﹎E﹎﹎，从而做到对该文件（或记录）任一时刻只有一个进程可存取，但要注意使用不当引起的死锁。A：(1)同步与异步；(2)串行与并行；(3)调度与控制；(4)同步与互斥。B：(1)消息操作；(2)P-V操作；(3)开关操作；(4)读写操作。C：(1)通信原语；(2)调度算法；(3)分配策略；(4)进程控制。D、E：(1)联机操作；(2)V操作；(3)输出操作；(4)读操作；(5)写操作；(6)P操作；(7)输入操作。2.A-4B-2C-1D-6E-2

习题-6选1：在操作系统中处理机管理由作业管理和进程管理两部分组成，作业管理把作业流分成提交、后备、运行、完成四个状态，进程管理把进程分成就绪、执行、阻塞三个基本状态。作业由提交状态到后备状态由﹎﹎A﹎﹎完成，由后备状态到运行状态由﹎﹎B﹎﹎完成，进程由就绪状态到执行状态由﹎﹎C﹎﹎，用户进程的祖先进程由﹎﹎E﹎﹎建立的。A，B，C，D，E：(1)作业调度程序；(2)进程调度程序；(3)存储管理程序；(4)输入输出程序；(5)假脱机（SPOOLing）处理程序；(6)交通程序；(7)设备管理程序。选12：操作系统的主要性能参数：﹎﹎A﹎﹎指的是单位时间内系统处理的作业量。﹎﹎B﹎﹎指的是从作业或命令的输入到其结束的间隔时间，在分析性能时常用其倒数。﹎﹎C﹎﹎指的是在一个给定的时间内，系统的一个指定成份被使用的时间比例。A，B，C：(1)周转时间；(2)处理时间；(3)消逝时间；(4)利用率；(5)生产率；(6)吞吐量。1.A-5B-1C-2D-12.A-6B-1C-4习题-8选18：产生死锁的基本原因是﹎﹎A﹎﹎和﹎﹎B﹎﹎，产生死锁的四个必要条件是互斥条件﹎﹎C﹎﹎，不剥夺条件和﹎﹎D﹎﹎。A：(1)资源分配不当；(2)系统资源不足；(3)作业调度不当；(4)资源的独占性。B：(1)进程推进顺序非法；(2)进程调度不当；(3)系统中进程太多；(4)CPU运行太快。C：(1)请求和阻塞条件；(2)请求和释放条件；(3)请求和保持条件；(4)释放和阻塞条件；(5)释放和请求条件。D：(1)线性增长条件；(2)环路条件；(3)无序释放条件；(4)有序请求条件；(5)无序请求条件。5.A-2B-1C-3D-2习题-9选19：预防死锁的论述中，﹎﹎A﹎﹎条是正确的论述。(1)由于产生死锁的基本原因是系统资源不足，因而预防死锁的有效方法，是根据系统规模，配置足够的系统资源。(2)由于产生死锁的另一种基本原因是进程推进顺序不当，因而预防死锁的有效方法，是使进程的推进顺序合法。(3)因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的有效方法，是防止系统进入不安全状态。(4)可以通过破坏产生死锁的四个必要条件之一或其中几个的方法，来预防发生死锁。6.A-4第三章习题选4：静态重定位是在作业的﹎﹎A﹎﹎中进行的，动态重定位是在作业的﹎﹎B﹎﹎中进行的。A，B：（1）编译过程；（2）装入过程；（3）修改过程；（4）执行过程。选5：在首次适应算法中，要求空闲分区按﹎﹎A﹎﹎顺序链接成空闲分区链；在最佳适应算法中是按﹎﹎B﹎﹎顺序形成空闲分区链；最坏适应算法是按﹎﹎C﹎﹎顺序形成空闲分区链。A，B，C：（l）空闲区首址递增；（2）空闲区首址递减；（3）空闲区大小递增；（4）空闲区大小递减。A-2B-4A-1B-3C-4习题-3选3：由固定分区方式发展为分页存储管理方式的主要推动力是﹎﹎A﹎﹎；由分页系统发展为分段系统，进而又发展为段页式系统的主要动力分别是﹎﹎B﹎﹎和﹎﹎C﹎﹎。A，B，C：（l）提高内存利用率；（2）提高系统吞吐量；（3）满足用户需要；（4）更好地满足多道程序运行的需要。（5）既满足用户需要，又提高内存利用率。8.A-1B-3C-5习题-4选16：虚拟存贮管理系统的基础是程序的局部性理论。此理论的基本含义是﹎﹎A﹎﹎。局部性有两种表现形式：时间局限性和﹎﹎B﹎﹎。它们的意义分别为﹎﹎C﹎﹎和﹎﹎D﹎﹎。根据局部性理论，Denning提出了﹎﹎E﹎﹎。A、B，①程序执行时对主存和访问是不均匀的②代码的顺序执行③变量的连续访问④指令的局部性⑤数据的局部性⑥空间局部性C、D：①最近被访问的单元，很可能在不久的将来还要被访问②最近被访问的单元，很可能在它附近的单元也即将被访问③结构化程序设计，很少出现转移语句④程序中循环语句的执行时间一般很长⑤程序中使用的数据局部于各子程序E：①Cache结构的思想②工作集理论③最近最少使用（LRU）页面置换算法④先进先出页面置换算法1.A-1B-6C-1D-2E-2习题-5选7：在请求分页内存管理的页表表项中，其中状态位供﹎﹎A﹎﹎时参考；修改位供﹎﹎B﹎﹎时参考；访问位供﹎﹎C﹎﹎时参考；外存始址供﹎﹎D﹎﹎时参考。A，B，C，D：（l）分配页面；（2）置换算法；（3）程序访问；（4）换出页面；（5）调入页面。选9：在请求调页系统中，凡未装入过内存的页都应从﹎﹎A﹎﹎调入；已运行过的页主要是从﹎﹎B﹎﹎调入，有时也可以从﹎﹎C﹎﹎调入。A，B，C：（1）系统区；（2）文件区；（3）对换区；（4）页面缓冲池。3.A-3B-4C-2D-54.A-2B-3C-4第四章习题选1：在I/O设备控制的发展过程中，最主要的推动因素是﹎﹎A﹎﹎，提高I/O速度和设备利用率，在OS中主要依靠﹎﹎B﹎﹎功能。使用户所编制的程序与实际使用的物理设备无关是由﹎﹎C﹎﹎功能实现的。A：（1）提高资源利用率；（2）提高系统吞吐量；（3）减少主机对I/O控制的干预；（4）提高CPU与I/O设备的并行操作程度。B,C：（1）设备分配；（2）缓冲管理；（3）设备管理；（4）设备独立性；（5）虚拟设备。选8：通道是一种特殊的﹎﹎A﹎﹎，具有﹎﹎B﹎﹎能力。A：（1）I/O设备；（2）设备控制器；（3）处理机；（4）I/O控制器。B：（1）执行I/O指令集；（2）执行CPU指令集；（3）传输I/O命令；（4）运行I/O进程。

A-3B-3C-48.A-3B-1习题-1选5:假定把磁盘上一个数据块中信息输入到一单缓冲的时间T为100us，将缓冲区中数据传送到用户区的时间M为50us,而CPU对这一块数据进行计算的时间C为50us，这样，系统对每一块数据的处理时间为﹎﹎A﹎﹎；如果将单缓冲改为双缓冲，则系统对每一块数据的处理时间为﹎﹎B﹎﹎。A,B：（1）50us;(2)100us;(3)150us;(4)200us;(5)250us。5.A-3B-2习题-4（4） SPOOLing系统是建立在分时系统中。（5） SPOOLing系统是虚拟存储技术的体现。（6） SPOOLing系统是在用户程序要读取数据时起动输入进程输入数据。（7） 当输出设备忙时，SPOOLing系统中的用户程序暂停执行，待I/O空闲时再被唤醒，去执行输出操作。（8） SPOOLing系统实现了对I/O设备的虚拟，只要输入设备空闲，SPOOLing可预先将输入数据从设备传输到输入井中供用户程序随时读取。（9） 在SPOOLing系统中，用户程序可以随时将输出数据送到输出井中，待输出设备空闲时再执行数据输出操作。6.A-8B-9

第五章习题1．下列哪一项不是文件系统的功能?﹎﹎A﹎﹎A：（1）文件系统实现对文件的按名存取（2）负责实现数据的逻辑结构到物理结构的转换（3）提高磁盘的读写速度（4）提供对文件的存取方法和对文件的操作选1．(1)按逻辑结构划分，文件主要有两类：﹎﹎A﹎﹎和﹎﹎B﹎﹎。UNIX中的文件系统采用﹎﹎B﹎﹎。(2)文件系统的主要目的是﹎﹎C﹎﹎。(3)文件系统中用﹎﹎D﹎﹎管理文件。(4)为了允许不同用户的文件具有相同的文件名，通常在文件系统中采用﹎﹎E﹎﹎。A，B：(1)网状文件；(2)只读文件；(3)读写文件；⑷记录式文件；⑸索引文件；⑹流式文件；C：(1)实现对文件的按名存取；(2)实现虚拟存贮器；(3)提高外围设备的输入输出速度；(4)用于存贮系统文档。D：(1)堆栈结构；(2)指针；(3)目录；(4)页表。E：(1)重名翻译；(2)多级目录；(3)约定；(4)路径。1.A-32.A-4B-6C-1D-3E-2

习题-1选5.下面关于顺序文件和链接文件的论述中，第﹎﹎A﹎﹎条是正确的论述。(1)顺序文件适于建立在顺序存储设备上，而不适合建立在磁盘上。(2)在显式链接文件中是在每个盘块中设置一链接指针，用于将文件的所有盘块链接起来。(3)顺序文件必须采用连续分配方式，而链接文件和索引文件则都可采取离散分配方式。(4)在MS-DOS中采用的是隐式链接文件结构。选6.下面关于索引文件的论述中，第﹎﹎A﹎﹎条是正确的论述。(1)索引文件中，索引表的每个表项中含有相应记录的关键字和存放该记录的物理地址。(2)对顺序文件进行检索时，首先从FCB中读出文件的第一个盘块号；而对索引文件进行检索时，应先从FCB中读出文件索引表始址。(3)对于一个具有三级索引表的文件，存取一个记录通常要访问三次磁盘。(4)在文件较大时，无论是进行顺序存取还是随机存取，通常都是以索引文件方式为最快。

5.A-36.A-2

（二）计算填空题/计算题

（1）作业／进程调度算法—P65例2-1假定在一个处理机上执行以下五个作业：作业号ABCDE到达时间02468运行时间36452a.画出采用FCFS调度算法时调度图，并计算每个作业的周转时间和平均周转时间。b.画出采用SJF调度算法时调度图，并计算每个作业的周转时间和平均周转时间。c.写出采用HRN（响应比高者优先）调度算法时选择的作业序号和选择作业时依据（各作业响应比）。（时间的另一种表示方法－－10:20为10点20分）例解－1(1)先来先服务调度算法FCFS作业调度次序的计算：FCFS按照作业到达的先后次序来选择作业，按作业到达时间的先后次序五个作业调度次序为A、B、C、D、E。(2)

短作业优先调度算法SJF作业调度次序的计算：SJF在到达的作业中挑选所需运行时间最短的作业进入主存先运行，调度次序如下：T=0：只有作业A已到达，调度作业A运行。

T=3：作业A完成，作业B已到达，调度作业B运行。T=9：作业B完成，作业C、D、E已全部到达，比较作业C、D、E的运行时间，按运行时间短的作业先运行，则调度次序为E、C、D。例解-2(3)高响应比优先(HRRN)(作业)调度算法计算：RP＝1＋((调度时间-到达时间)／运行时间)。

T=0：只有作业A已到达，调度作业A运行。T=3：作业A完成，作业B已到达，调度作业B运行。T=9：作业B完成，作业C、D、E已到达，计算作业C、D、E响应比RP分别为：1+(9-4)/4、1+(9-6)/5、1+(9-8)/2，作业C响应比最大调度运行。T=13：作业C完成，作业D、E已到达，计算作业D、E响应比RP分别为：1+(13-6)/5、1+(13-8)/2，作业E响应比最大调度运行。T=15：作业E完成，只有作业D未完成，调度作业D运行。T=20：作业D完成。例解调度图调度图:到达|ABCDE作业|↓↓↓↓↓时间|01234567891011121314151617181920FCFS||-----A-----|-----------B-----------|-------C-------|---------D---------|---E---|SJF||-----A-----|-----------B-----------|---E---|-------C-------|---------D---------|HRN||-----A-----|-----------B-----------|-------C-------|---------D---------|---E---|

例解-3例解-5作业／进程调度算法--P102问答题12假定在一个处理机上执行以下五个作业：作业号到达时间运行时间(分)A04B13C25D32E44a.画出采用FCFS调度算法时调度图，并计算每个作业的周转时间和平均周转时间。b.画出采用SJF调度算法时调度图，并计算每个作业的周转时间和平均周转时间。c.写出采用HRN（响应比高者优先）调度算法时选择的作业序号和选择作业时依据（各作业响应比）。调度算法解－11.先来先服务调度算法FCFS作业调度次序的计算：FCFS按照作业到达的先后次序来选择作业，按作业到达时间的先后次序五个作业调度次序为A、B、C、D、E。调度图:到达|ABCDE作业|↓↓↓↓↓时间|0123456789101112131415161718FCFS||------A--------|-----B-----|---------C---------|---D---|-------E-------|调度算法解－22.

短作业优先调度算法SJF作业调度次序的计算：SJF在到达的作业中挑选所需运行时间最短的作业进入主存先运行，调度次序如下：T=0：只有作业A已到达，调度作业A运行。T=4：作业A完成，作业B、C、D、E已全部到达，比较作业B、C、D、E的运行时间，按运行时间短的作业先运行，则调度次序为D、B、E、C。调度图:

到达|ABCDE作业|↓↓↓↓↓时间|0123456789101112131415161718SJF||-------A-------|---D---|-----B-----|-------E-------|---------C---------|调度算法解-33.高响应比优先(HRRN)(作业)调度算法计算：T=0：只有作业A已到达，调度作业A运行。T=4：作业A完成，作业B、C、D、E已到达，计算作业B、C、D、E响应比RP分别为：1+3/3、1+2/5、1+1/2、1+0/4，作业B响应比最大调度运行。T=7：作业B完成，作业C、D、E已到达，计算作业C、D、E响应比RP分别为：1+5/5、1+4/2、1+3/4，作业D响应比最大调度运行。T=9：作业D完成，作业C、E已到达，计算作业C、E响应比RP分别为：1+7/5、1+5/4，作业C响应比最大调度运行。T=14：作业C完成，只有作业E未完成，调度作业E运行。(2)利用银行家算法避免死锁—P73例2-3假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C}，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。

Max AllocationAvailable ABC ABC ABC

P0753 010P1322200P2 902 302 P3222 211 P4433 002 试问：①T0时刻是否安全？②P1请求资源Request1(1,0,2)是否允许？银行家算法解-1T0时刻是否安全？从表中可找出一个序列(P1、

P3、P4、

P2、

P0）使各进程顺序地一个个地执行完成。

Max AllocationNeed WorkWork(Available)+AllocationABCABCABCABC ABC P0753010743=<1047⑤1057 P1322200 122=<332①532 P2 902302 600=<745④1047 P3 222211 011=<532②743 P4 433002 431=<743③745

安全序列为{P1、P3、P4、P2、P0}，T0时刻系统是安全的。可能有几个安全序列，只要找出一个安全序列就可以。银行家算法解-2P1请求资源Request1(1,0,2)可否允许？Request1(1,0,2)≤Need1(1,2,2)，P1请求在最大需求范围内。Request1(1,0,2)≤Available(3,3,2)，可用资源可满足P1请求需要。试探把要求的资源分配给进程P1并修改有关数据结构的数值：Available=Available(3，3，2)－Request1(1,0,2)=Available(2,3,0)；Need1=Need1(1,2,2)－Request1(1,0,2)=Need1(0,2,0)；Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法检查试探将资源分配后状态的安全性如下：银行家算法解-3

MaxAllocationNeed WorkWork(Available)+AllocationABCABCABCABCABC P0753010 743=<1047⑤ 1057 P1322302 020=<230

① 532 P2 902302 600=<745④ 1047 P3 222211 011=<532②743 P4 433002 431=<743③745

因为先分配资源给P1进程符合按安全序列{P1、P3、P4、P2、P0}分配资源，所以试探将资源分配给进程P1后的状态是安全的，可将资源分配给进程P1。P102问答题117．试描述避免死锁的银行家算法，若系统运行中出现下述资源分配情况进程ALLOCATIONNEEDAVAILABLEABCDABCDABCDP0003200121622P110001750P213542356P303320652P400140656问该系统是否安全？如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配给它？解：系统是否安全？找到一个安全序列：P0、P3、P4、P1、P2，因此系统是安全的。

进程WORKNEEDALLOCATIONWORK+AllocationABCDABCDABCDABCDP01622001200321654P1199101750100029910P229910235613543121414P31654065203321986P419860656001419910如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配给它？进程P2此时提出资源申请（1，2，2，2），按照银行家算法进行检查，Request(1,2,2,2)≤Need(2,3,5,6),且Request(1,2,2,2)≤Available(1,6,2,2),假定先将资源分配给它，重新列出如下表：从表中可以看出，已经不存在安全序列了，所以系统不能将资源分配给它，否则系统会进入不稳定状态。进程WORKNEEDALLOCATIONWORK+AllocationABCDABCDABCDABCDP0040000120032

P1

17501000

P2

23562576

P3

06520332

P4

06560014

(3)分页存储管理系统逻辑地址到物理地址地址变换的计算(P114例3-1)某系统采用页式存储器管理,页长为1K(1024)字,主存大小为10K,其中0块和1块为操作系统占用,该作业分页后分别装入到主存的2,4,5块中去,当前正在运行该作业。求逻辑地址2500所对应的物理地址为多少？

分页存储管理逻辑地址到物理地址地址变换的计算解(1)十进制－－逻辑地址2500页号=逻辑地址/页大小=2500/1024=2页内地址=逻辑地址mod页大小=2500mod1024=452查页表页号2块号5物理地址=块号*页大小+页内地址=5*1024+452=5572(2)十六进制－－逻辑地址09C4H1KB1024400H∵C00H＞09C4H＞800H页号22KB2048800H页内地址＝逻辑地址－该页头地址3KB3072C00H＝09C4H－800H＝1C4H4KB40961000H查页表页号2块号55KB51201400H物理地址＝该块头地址+页内地址6KB61441800H

=

1400H+1C4H=15C4HP150选择题14某虚拟存贮器的用户编程空间共32个页面，每页1KB，主存为16KB。假定某时刻用户页表中已调入主存的页面的虚拟页号和物理页表对照表为表一，则下表中与虚拟地址相对应的物理地址为表二（如果主存找不到，即为该页失效）。虚拟存贮存的功能是由﹎﹎C﹎﹎完成的。在虚拟存贮系统中，采用﹎﹎D﹎﹎提高﹎﹎E﹎﹎的速度。表一虚页号物理页号 051102487 表二虚地址 物理地址 0A5C（H）﹎﹎A﹎﹎ 1A5C（H）﹎﹎B﹎﹎ 例题-1供选择的答案：A，B：①页失效②1E5C（H）③2A5C（H）④165C（H）⑤125C（H）⑥1A5C（H）C：①硬件②软件③软、硬件结合D：①高速辅助存贮器②高速光盘存贮器③快速通道④高速缓冲存贮器E：①连接编辑②虚地址分配③动态地址翻译④动态连接A---(5)B---(1)C---(3)D---(4)E---(3)例题-2解：每页大小1KB，用16进制表示为400H，由虚地址通过直接映象的地址转换成物理地址步骤如下：将虚地址分离成页号p和页内地址d：页号p＝（虚地址／页大小）取整＝（0A5CH/400H）取整＝2页内地址d＝虚地址－页号p×每页大小＝0A5C(H)－2×400(H)＝25C(H)根据页号查页表，由页号p＝2查页表得物理页号为4将物理页号和页内地址构成物理地址＝物理页号×页大小＋页内地址＝4×400(H)＋25C(H)＝125C(H)同理虚拟地址1A5CH分离成页号P＝6和页内位移15CH.查页表知该页不在内存，页失效产生缺页中断调入内存。(4)分页存储管理系统CPU存取一个数据的平均时间计算（P115例3-2）一个分页系统，检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的的命中率为90%。则CPU存取一个数据的平均时间为多少？分页存储管理系统CPU存取一个数据的平均时间计算解快表命中时CPU存取一个数据的时间为T1＝检索快表时间＋访问内存数据时间＝20＋100＝120ns，快表不命中时CPU存取一个数据的时间为T2＝检索快表时间＋检索内存中的页表时间＋访问内存数据时间＝20＋100＋100＝220ns，则CPU存取一个数据的平均时间为T=命中率*T1+（1－命中率）*T2=0.90*120+0.10*220=130ns，所以访问时间只增加30%。(5)页面置换算法（P155问答题12）在一个请求分页系统中，假如一个作业的页面访问顺序为4，3，2，1，4，3，5，4，3，2，l，5，当分配给该作业的物理块数M为3时，当分别用先进先出（FIFO）调度算法和最近最久未用（LRU）调度算法时，作业执行过程中会产生多少次缺页中断？写出页面调度过程。FIFO置换算法解：页面走向432143543215物理块432143555211

43214333522

4321444355

缺页中断√√√√√√√

√√

(表中物理块的页号按调入内存先后次序排序)用FIFO置换算法产生缺页次数9次。FIFO置换算法解：页面走向432143543215物*

理块44*411*15555*5*5

*33*34*4*4*4*4222

*2223333*311

缺页中断√√√√√√√

√√

(设置一个循环替换指针)用FIFO置换算法产生缺页次数9次。LRU置换算法解：访问页序列432143543215

物理块432143543215

43214354321

4321435432

缺页中断√√√√√√√

√√√(表中物理块的页号按访问先后次序排序)用LRU置换算法产生缺页次数10次。(6)文件系统性能计算（P2075.2.5实例）一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用二级索引和UNIXSytemV分配方案时(每块大小为4096B,每块地址用4B表示)，问:1.各文件系统管理的最大的文件是多少?2.每种方案对大、小二文件各需要多少专用块来记录文件的物理地址(说明各块的用途)?3．如需要读大文件前面第5.5KB和后面（16M＋5.5KB）信息，则每个方案各需要多少次盘I/O操作?索引分配文件系统管理的最大的文件由于盘块大小为4KB，每个地址用4B表示（索引表目大小），一个盘块可存索引表目数为N＝盘块大小/索引表目大小=4KB/4B=1K二级索引可管理的最大文件容量为盘块大小×N×N=4KB×1K×1K＝4GB三级索引可管理的最大文件容量为盘块大小×N×N×N=4KB×1K×1K×1K＝4TB

UNIX文件系统管理的最大的文件由于盘块大小为4KB，每个地址用4B表示（索引表目大小），一个盘块可存索引表目数为N＝盘块大小/索引表目大小=4KB/4B=1KUNIX混合分配可管理的最大文件为：盘块大小×(10+N+N×N+N×N×N)=4KB×(10+1K+1K×1K+1K×1K×1K)=40KB＋4MB+4GB＋4TB二级索引分配文件系统专用物理块:一个盘块可存索引表目数为N＝盘块大小/索引表目大小=4KB/4B=1K对大小文件都固定要用二级索引，对20KB小文件，文件有5块物理块，需要5个索引表目。用一块作二级索引块，另用一块作主索引块，共用二块专用物理块作索引块，对于20MB大文件，文件有5K块物理块，需要5K个索引表目。用5块作第二级索引块，另用一块作主索引块，共用六块专用物理块作索引块。UNIX文件系统专用物理块:对20KB小文件只需在文件控制块FCB的i_addr[13]中使用前5个表目存放文件的物理块号，不需专用物理块。对20MB大文件，FCB的i_addr[13]中使用前10个表目存放大文件前10块物理块块号，用一级索引块一块保存大文件接着的1K块块号，还要用二级索引存大文件以后的(4K-10)块块号，用4块作第二级索引块，另用一块作主索引块。总共也需要6块专用物理块来存放文件物理地址。二级索引分配文件系统读盘次数:二级索引：为读大文件前面和后面信息的操作相同，首先进行一次盘I／O读第一级索引块，（然后根据它的相对逻辑块号计算应该读第二级索引的那块，第一级索引块表目号=相对逻辑块号／1K，对文件前面信息1／1K＝0，对文件后面信息4097／1K＝4，）第二次根据第一级索引块的相应表目内容又化一次盘I／O读第二级索引块，得到信息所在块块号，再化一次盘I／O读出信息所在盘块，这样读取大文件前面或后面信息都只需要3次盘I／O操作。UNIX文件系统读盘次数:为读文件地址<40KB的信息，先根据它的相对逻辑块号，在内存文件控制块FCB的i_addr[13]第0－9个表目中读取信息所在块块号，而只化费一次盘I／O操作即可读出该块信息。为读（40KB+4MB）＞文件地址≥40KB的信息，先根据i_addr[10]读一级索引块，以得到信息所在块块号，最后化一次盘I／O读出信息所在盘块，这样总共需要2次盘I／O操作才能读出文件后面的信息。为读（40KB+4MB+4GB）＞文件地址≥（40KB+4MB）的信息，先根据i_addr[11]内容化一次盘I／O操作读出第一级索引块，再计算信息所在块的索引块号在第一级索引块的表目号为（块号-9-1024）／1024，根据第一级索引块表目内容再化费一次盘I／O操作，读出第二级索引块，就可以得到信息所在块块号，最后化一次盘I／O读出信息所在盘块，这样总共需要3次盘I／O操作才能读出文件后面的信息。UNIX文件系统读盘次数－1为读大文件前面5.5KB信息，先根据它的相对逻辑块号，在内存文件控制块FCB的i_addr[13]第二个表目中读取信息所在块块号，而只化费一次盘I／O操作即可读出该块信息。为读大文件后在（16MB＋5。5KB）信息，先根据它的相对逻辑块号判断它是在UNIX二级索引管理范围，先根据i_addr[11]内容化一次盘I／O操作读出第一级索引块，再计算信息所在块的索引块号在第一级索引块的表目号为（4097-9-1024）／1024＝3，根据第一级索引块第3个表目内容再化费一次盘I／O操作，读出第二级索引块，就可以得到信息所在块块号，最后化一次盘I／O读出信息所在盘块，这样总共需要3次盘I／O操作才能读出文件后面的信息。P260选择题13、143．一个文件系统中有一个2MB文件,当分别采用连续、链接、二级索引和UNIXSytemV分配方案时(每块大小为2048B,每块地址用4B表示)，问:①.各文件系统管理的最大的文件是多少?（﹎A﹎、﹎B﹎、﹎D﹎、﹎E﹎）②.每种方案对大、小二文件各需要多少专用块来记录文件的物理地址?（﹎F﹎、﹎G﹎、﹎I﹎、﹎J﹎）③如需要读文件第一页信息，则每个方案各需要多少次盘I/O操作（包括读信息块盘I/O操作）?（﹎K﹎、﹎L﹎、﹎N﹎、﹎O﹎）④如需要读文件最后一页信息，则每个方案各需要多少次盘I/O操作（包括读信息块盘I/O操作）?（﹎P﹎、﹎Q﹎、﹎S﹎、﹎T﹎）习题-1A、B、C、D、E：(1)整个磁盘文件区；（2）4G；（3）2G；（4）1G；（5）0.5G；（6）40KB＋4MB+4GB＋4TB；（7）；20KB＋2MB+2GB＋2TB；（8）20KB+1MB+0.5G+0.25T；（9）10KB＋1MB+1GB＋1TB；（10）5KB＋0.5MB+0.5GB＋0.5TB；(11)不得而知；F、G、H、I、J、K、L、M、N、O、P、Q、R、S、T：（1）1；（2）2；（3）3；（4）4；（5）0；(6)以上都不是；解：-1一个盘块可存索引表目数为N＝盘块大小/索引表目大小=2KB/4B=0.5K=512二级索引可管理的最大文件容量为盘块大小×N×N=2KB×0.5K×0.5K＝0.5GB=512MB三级索引可管理的最大文件容量为盘块大小×N×N×N=2KB×0.5K×0.5K×0.5K＝0.25TB=256GBUNIX混合分配可管理的最大文件为：盘块大小×(10+N+N×N+N×N×N)=4KB×(10+0.5K+0.5K×0.5K+0.5K×0.5K×0.5K)=20KB＋1MB+0.5GB＋0.25TB解：-2对于2MB大文件，文件有2MB/2KB=1K块物理块。二级索引需要1K个索引表目，一个盘块可存索引表目数为512，用2块作第二级索引块，另用一块作主索引块，共用3块专用物理块作索引块。对UNIX，FCB的i_addr[13]中使用前10个表目存放大文件前10块物理块块号，用一级索引块一块保存大文件接着的0.5K块块号，还要用二级索引存大文件以后的(0.5K-10)块块号，用1块作第二级索引块，另用一块作主索引块。总共也需要3块专用物理块来存放文件物理地址。（三）编程填空题本书的重点—进程本书的难度--利用信号量机制实现进程互斥、同步（P1022.8.5问答题13）有三个共行进程P、Q和R以及一对供存数据的缓冲BufI和BufO，P进程把数据输入BufI，R进程输出BufO中的数据。Q地把BufI中的数据变换后送入BufO，在上述假定之下,使三个进程实现最大并行性。试在下述类PASCAL程序中虚线位置分别填上信号量、信号量初值和P、V操作实现三个进程正确的并发执行。

P

Q

BufIBufOR编程填空题-1Programito;varBufI,BufO:buffer;(信号量)﹎fulli,emptyi,﹎﹎﹎﹎﹎﹎:SEMAPHORE:=(信号量初值)﹎0,1﹎﹎﹎﹎﹎﹎﹎；beginparbeginP:beginrepeatinputfromIO;﹎﹎P(emptyi)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎AddtoBufI;﹎﹎V(fulli)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎untilfalse

end;

编程填空题-2

Q:beginrepeat﹎﹎P(fulli)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎RemovefromBufI;﹎﹎V(emptyi)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎transform;﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎AddtoBufO;﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎untilfalseend;编程填空题-3R:beginrepeat﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎RemovefromBufO;﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎Output...;untilfalseend;parendend

习题解-8Programito;varBufI,BufO:buffer;(信号量)﹎emptyI,fullI,emptyO,fullO:SEMAPHORE:=(信号量初值)﹎1,0,1,0﹎；beginparbeginP:beginrepeatinputfromIO;﹎﹎﹎P(emptyI)﹎﹎﹎﹎﹎﹎﹎AddtoBufI;﹎﹎﹎V(fullI)﹎﹎﹎﹎﹎﹎﹎untilfalse

end;

习题解-9

Q:beginrepeat﹎﹎﹎﹎P(fullI)﹎﹎﹎﹎﹎﹎﹎RemovefromBufI;﹎﹎﹎﹎V(emptyI)﹎﹎﹎﹎﹎﹎trans