1.1 选择题
1.（考研真题，单项选择题）单道批处理系统的主要缺点是（ ）。
A. CPU利用率不高
2.（考研真题，单项选择题）提高单机资源利用率的关键技术是（ ）。
D.多道程序设计技术
3.（考研真题，单项选择题）并发性是指若干事件在（ ）发生。
A C.同一时间间隔内
4.（单项选择题）批处理系统的主要缺点是（ ）。
D.无交互能力
10.（考研真题，单项选择题）进程和程序的本质区别是（ ）。
A.前者是动态的，后者是静态的
11.（单项选择题）进程的基本状态（ ）可以由其他两种基本状态转变而来。
A.就绪状态
12.（单项选择题）进程处于（ ）时，它处于非阻塞态
C.等待操作系统分配CPU时间
15.（名校考研题，单项选择题）进程和程序的本质区别在于（ ）。
D.前者可以并发执行，后者不能并发执行
16.（考研真题，单项选择题）进程的状态和优先级信息存放在（ ）。
PCB PCB是进程存在的唯一标识，它存储着进程的状态和优先级等信息。
19.（考研真题，单项选择题）用信箱实现进程间互通信息的通信机制要有两个通信原语，它们是（ ）。
C.发送原语和接收原语
20.（单项选择题）死锁的4个必要条件中，无法破坏的是（ ）。
A.环路等待资源 B.互斥使用资源 C.占有且等待资源 D.非抢夺式分配
21.（单项选择题）死锁与安全状态的关系是（ ）。
D.死锁状态一定是不安全状态
。
|
不安全状态 |
|
死锁状态 |
26.（单项选择题）一个作业8:00到达系统，估计运行时间为1小时。若10:00开始执行该作业，其响应比是（ ）
【解析】响应比==服务/执行+1=响应时间/要求服务时间=(等待时间+要求服务时间)/要求服务时间=(2+1)/1=3。
27.（考研真题，单项选择题）下列调度算法中，不会导致饥饿现象的是（ ）。
A.时间片轮转 B.静态优先数调度
C.非抢占式短任务优先 D. 抢占式短任务优先
【解析】采用静态优先级调度且系统总是出现优先级高的任务时，优先级低的任务总是得不到处理机而产生饥饿现象。短任务优先调度当系统总是出现新来的短任务时，长任务总是得不到处理机，会产生饥饿现象。
28.（考研真题，单项选择题）系统中有4个进程都要使用某类资源。若每个进程最多需要3个该类资源，为保证系统不发生死锁，系统应提供该类资源至少是（ ）。
C.9个
【解析】系统中有4个进程，每个进程最多需要3个资源，先给每个进程分配2个资源，共需要8个资源，此时需要系统中还有1个空闲资源，分配给任一进程，才不会发生死锁，故至少需要9个资源。
31.（单项选择题）采用资源剥夺法可以解除死锁，还可以采用（ ）方法解除死锁。
B.撒销进程
35.（考研真题，单项选择题）若记录型信号量S的初值为15，当前值为-15，则表示有（ ）等待进程。
A. 15个
【解析】当S值小于0时，绝对值表示阻塞队列中进程的个数。
37.（单项选择题）从下面对临界区的论述中，选出一条正确的论述。（ ）
D.临界区是指进程中访问临界资源的那段代码
39.（考研真题，单项选择题）设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待资源的进程数，则M、N分别是（ ）。
B. 1、0
【解析】根据信号量的物理含义：S.value＞0时表示有S.value个资源可用；S.value=0表示无资源可用；S.value＜0则S.value的绝对值表示等待队列中的进程个数。信号量的当前值为1，则表示该资源的可用个数为1，没有等待该资源的进程。
40.（考研真题，单项选择题）若记录型信号量S的初值是3，则当前值为1时表示有（ ）个阻塞等待进程。
C. 0个
【解析】S为1，值大于0，说明允许进程访问资源，进入临界区，当前没有阻塞等待
41. （考研真题，单项选择题）在对记录型信号量的P操作的定义中，当信号量的值（ ）时，执行P操作的进程变为阻塞状态。
B.小于0 C.等于0 D.小于或等于0
41.【参考答案】B
【解析】对于记录型信号量，每执行一次P操作，信号量的值都会减1，当信号量的值小于0的时候，说明系统中无可用临界资源，进程变为阻塞状态
42.（考研真题，单项选择题）如果3个进程共享一个互斥段，每次最多可以允许2个进程进入互斥段，则信号量的变化范围是（ ）。
A. 2、1、0、-1
【解析】最多允许2个进程进入互斥段，初始值则为2，因为每个进程进去时都先要行P操作，然后判断信号量的值是否大于0，不是则表示当前互斥段内已经有2个进程，当第3个进程再执行P操作时，信号量值为-1，该进程阻塞。
45.（考研真题，单项选择题）采用（ ）不会产生内部碎片。
A.分页式存储管理 B.分段式存储管理
C.随机存储管理 D.段页式存储管理
【解析】在页式存储管理的方式中，最后1个页面往往会出现不足1页大小的情况，产生页内碎片。
48.（考研真题，单项选择题）在页式存储管理系统中，页表内容如表所示（均从0开始编号）。
| 页号 |
块号 |
| 0 |
2 |
| 1 |
1 |
| 2 |
6 |
| 3 |
3 |
| 4 |
7 |
若页面大小为4KB，则地址变换机构将逻辑地址0转换成物理地址为（ ）。
A. 8192
【解析】逻辑地址0，对应页号为0，查页表可知块号为2，物理地址为2´4K=8K=8192。
所示。
| 访问串 |
2 |
0 |
2 |
9 |
3 |
4 |
2 |
8 |
2 |
4 |
8 |
4 |
5 |
7 |
| 内存 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
7 |
| 0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
||
| 9 |
9 |
9 |
9 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
||||
| 3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
5 |
5 |
54.（考研真题，单项选择题）在请求页式存储管理中，若所需页面不在内存中，则会引起（ ）。
D.页故障
【解析】在请求页式存储管理中，若所需页面不在内存中，则会引起页故障，即缺页中断。
56.（考研真题，单项选择题）在页式存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（ ）。
A. FIFO算法
【解析】Belady现象是系统为进程分配的页数增多（未分配进程所需的全部页），但缺页率反而提高的异常现象。只有FIFO算法才会出现Belady现象。FIFO算法将最早调入的页调出，而调出的页在不久可能会被重新使用出现反复调入调出，缺页率反而上升。
63.（单项选择题）请求分段系统在分段系统的基础上，增加了（ ）及分段置换软件功能。
A.请求调段 B.段表 C.缺段中断 D.地址变换
65.（单项选择题） 通道是一种（ ）。
D. 专用处理机A. 保存 I/O 信息的部件
【解析】通道是一种特殊的I/O专用处理机。引入通道是为了建立独立的I/O操作，这不仅指数据的传送能独立于CPU，而且有关I/O操作的组织，管理及结束也尽量独立，以保证CPU有更多的时间去进行数据处理。
68.（考研真题，单项选择题）程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A.逻辑设备名
【解析】用户程序对I/O设备的请求采用逻辑设备名，而在程序实际执行时使用物理设备名。
71.（考研真题，单项选择题）操作系统中的SPOOLing技术，实质是将（ ）转化为共享设备的技术。
B.独占设备
【解析】SPOOLing的核心思想是利用磁盘（输入井、输出井）来模拟独占设备的操作，使一台独占设备变成多台可并行的虚拟设备。用户向独占设备提交的请求实际上被提交到输入或输出井里面。从输入/输出井到实际物理独占设备的数据传输由SPOOLing进程统一控制和调度。
72.（考研真题，单项选择题）为了缓和CPU和I/O设备间速度不匹配的矛盾，提高CPU和I/O设备的并行性，现代操作系统关于I/O设备与处理机之间的数据交换几乎都用到了（ ）。
B.缓冲区
【解析】引入缓冲区可以在高速和低速设备之间起一个速度平滑作用，用于暂时存储数据，经常访问的数据可以放进缓冲区，减少对慢速设备的访问等待，以提高系统效率。
74.（考研真题，单项选择题）假设磁头当前位于第105道，正在向磁道号增加的方向移动。现有一个磁道访问请求序列为35、45、12、68、110、180、170、195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是（ ）。
A. 110、170、180、195、68、45、35、12
【解析】SCAN调度算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务对象。当前磁道向序号增加的方向移动，当前位于第105道，则距离最近的下一个应该是第110磁道，依次递增到最高195，再向序号减少的方向移动，离当前195磁道最近的是68号磁道，依次递增到所有的请求完成，所以磁道访问序列为110、170、180、195、68、45、35、12。
76.（考研真题，单项选择题）从用户的角度看，文件系统主要是实现（ ）。
A. 数据存储 B. 数据保护 C. 数据共享 D. 按名存取
【解析】用户只需要向系统提供所需要访问的文件名称，就可以快速准确的找到指定文件在外存上的存储位置，这是文件系统向用户提供的最基本服务。
79.（考研真题，单项选择题）使用绝对路径名访问文件是从（ ）开始按目录结构访问某个文件。
A. 当前目录 B. 用户主目录 C. 根目录 D. 父目录
88.（考研真题，单项选择题）按文件的物理组织结构可将文件分成（ ）等。
C. 连续文件、链式文件、索引文件
【解析】按文件的物理组织结构可将文件分成顺序文件（连续文件）、链接文件（链式文件）、索引文件和直接文件
92.（单项选择题）下列方式中，（ ）不能改善磁盘系统的可靠性。
A. 廉价磁盘冗余阵列 B. 磁盘容错技术 C. 磁盘高速缓存 D. 后备系统
【解析】磁盘高速缓存是提高磁盘I/O速度的途径。
96.（考研真题，单项选择题）磁盘高速缓存设在（ ）中。
A.内存 C. Cache D.磁盘
【解析】磁盘高速缓存是指在内存中为磁盘盘块设置的缓冲区，在缓冲区中保存了某些盘块的副本。
1.1.2 填空题（课上选讲）
1.实时系统应具有的两个基本特征是（及时性 ）和（可靠性 ）。。。
【解析】各并发进程按各自独立的、不可预知的速度向前推进。这种特性称为进程的异步性。
2.为实现CPU与外部设备的并行工作，（ 中断机制 ）是系统必须引入的一种机制。
3.多道批处理系统的硬件支持是20世纪60年代发展起来的（ 通道）和（ 中断机制 ）。
4.操作系统为用户提供了两种类型的接口，分别是（ 命令接口 ）和（ 程序接口）。
5.用户为阻止进程继续执行，应利用（ 阻塞 ）原语，若进程正在执行，应转变为（ 阻塞）状态；以后，若用户要恢复其运行，应利用（ 唤醒 ）原语，此时进程应转变为（ 就绪 ）状态。
6. PCB的初始化包括（ 进程标识符信息；处理机状态信息和处理机控制信息 ）。
7.进程的并发性是指多个进程在（ 同一时间间隔 ）内同时发生。
8.进程的执行并不是“一气呵成”，而是走走停停的，这种特征称为进程的（ 异步性 ）。
9.下列作业调度算法中，（ 短作业优先调度算法 ）具有最短的作业平均周转时间。
10.在多进程并发执行中，肯定不会因竞争（ CPU ）而发生死锁。
【解析】CPU为可剥夺资源，竞争可剥夺资源不会发生死锁。
11.死锁的产生有4个必要条件，在死锁的预防策略中，资源的有序分配策略可以破坏（环路等待 ）条件。
12.银行家算法在解决死锁问题中是用于（ 避免死锁 ）的。
13.在利用信号量实现进程互斥时，应将（ 临界区 ）置于（ P操作（wait操作） ）和（ V操作（signal操作））之间。
14.在每个进程中访问（临界资源 ）的那段代码称为临界区。
15.计算机系统中，一次仅允许一个进程使用的资源，称为（临界资源）。
16.（考研真题）15个进程共享同一程序段，而每次最多允许4个进程进入该程序段，若用P、V操作同步机制，则记录型信号量S的取值范围为（-11≤S≤4 ）。
17.把程序地址空间中使用的逻辑地址变成内存中物理地址称为（重定位 ）。
18.在分页管理系统中，为实现地址转换设置了寄存器，其中存放的是（ 页表 ）在内存中的起始地址。
19.（考研真题）分页存储管理系统具有快表，内存访问时间为2μs，检索快表时间为0.5μs。若快表的命中率为80%，且忽略快表更新时间，则有效访问时间是（ ）μs。
2.9μs
【解析】在引入快表的分页存储管理系统中，有效访问时间的计算公式为：
EAT=a×λ+(t+λ) ×(1-a)+t=2t+λ-t×a
=命*快表t+未命*（内访t+快表t）+内访t
=命中率*检索快表时间+未命中率*（内存访问时间+检索快表时间）+内存访问时间
其中，t为内存访问时间，t=2μs；λ为检索快表的时间，λ=0.5μs；a为快表的命中率，a=80%。代入数据，得有效访问时间EAT=2.9μs。
20.在具有两级页表的分页存储管理系统中，CPU每次要存取一个数据时，必须访问（ 3 ）次内存。
【解析】两级页表中，CPU存取一个数据要访问3次内存。第1次访问一级页表，第2次获得二级页表，第3次存取数据。
21.某段式存储管理系统中，地址长度为32位，若允许的最大段长为64KB，则段号占（ 16 ）位。
【解析】分段地址结构由段号和段内地址组成，由于允许的最大段长是64KB=216B，那么段内地址占16位，则段号占32-16=16位。
22.虚拟存储器的基本特征是（ 多次性 、对换性 、虚拟性 ），因而决定了实现虚拟存储器的关键技术是（ 请求调页（段））和（页（段）置换 ）。
23.实现页式虚拟存储器，除了需要有一定容量的内存和相当容量的外存外，还需要有页表机制；地址变换机构；缺页中断机构的硬件支持。
24.（考研真题）在请求分页存储管理中，逻辑地址长度为16位，每页为2KB，部分页表如表所示。
| 页号 |
物理块号 |
| 0 |
4 |
| 1 |
10 |
| 2 |
6 |
| 3 |
2 |
则逻辑地址0EC5H所对应的物理地址为（ 56C5 ）H。
【解析】请求分页存储管理方式中分页地址结构，由页号和偏移量（页内地址）构成。由每页2KB的页面大小可以得出，页内地址占分页地址的低地址开始11位。由0EC5（H）得其二进制地址为00001 110 1100 0101，则页内地址为110 1100 0101，高地址部分表示页号为00001，得页号为1，查表可得对应的物理块号为10（十进制）。10转化为二进制为1010，由物理地址=块号×页面大小+偏移量（页内地址）得：1010×211+110 1100 0101=0101 0110 1100 0101=56C5 H。
25.为实现请求分页管理，应在基本分页的页表基础上增加状态位；访问字段；修改位；外存地址等数据项。
26.磁盘属于（ 块 ）设备，其信息的存取是以（数据块 ）为单位的；磁盘的I/O控制主要采取（中断驱动方式 ）；打印机的I/O控制主要采取( DMA控制方式 )
27.独占设备是指在一个作业的整个执行期间独自占用的设备，它一般采用（ 静态 ）分配。共享设备是指在某个时间段内可由多个作业同时使用的设备，一般采用（动态）分配。
28.在利用RS-232接口进行通信时，其通信速率为9.6KB/S(B为Bit)。如果在通信接口中仅设置了一个8位寄存器作为缓冲寄存器，这意味着大约每隔（ ）的时间便要中断一次CPU，且要求CPU必须在（ ）时间内予以响应。
【参考答案】0.8ms；0.1ms
【解析】8位寄存器作为缓冲寄存器就要传输8bit数据中断一次，所需时间为8/9.6»0.8ms。CPU响应时间为1/9.6»0.1ms
29.转速为7200转/分钟，平均旋转延迟时间约为（4.17 ）。
【解析】平均旋转延迟时间为1/2r，其中r为转速。60000/(2´7200)ms»4.17ms
转半周所用的时间
30.（考研真题）操作系统中采用缓存技术的主要目的是提高CPU和设备之间的（并行）程度。
31.在UNIX系统中，所有的（I/O设备）都被看成是特殊文件，它们在使用形式上与普通文件相同，但它们使用是和（ 设备管理程序 ）紧密相连的。
【解析】UNIX系统中的特殊文件也称设备文件。UNIX利用特殊文件作为用户与设备文件的接口，使用户访问外部设备，能像访问普通文件一样，无须知道各种设备的具体操作。特殊文件不包含任何数据，它只是在文件系统中建立了物理设备与文件名之间的映射，并提供相关的驱动程序，因此使用它们要和设备管理程序紧密相连。
32.对文件的访问有（顺序访问；随机访问/直接访问）两种方式。
33.鉴于文件查找过程中，只有文件名对目录检索有用，所以可把文件名与文件的其它属性分离开来分别存放，把有关文件的文件名组织在一起形成符号名文件目录，而文件的其它属性则以所谓（索引结点）的数据结构方式集中组织在一起。
34.（考研真题）在操作系统中，FCB是指（ 文件控制块 ）。file control lock
35.（考研真题）由字符序列组成，文件内的信息不再划分结构，这是指（流式文件 ）。
【解析】字符流的无结构文件，其长度以字节为单位。对流式文件的访问是利用读写指针指示下一个要访问的字符。大量的源程序，可执行程序，库函数等均为无结构文件。
36. 文件目录是（文件控制块 ）的有序集合。
【解析】文件与文件控制块一一对应，为了提高文件检索效率，操作系统常将文件控制块集中管理。这种文件控制块的有序集合称为文件目录，一个文件控制块就是其中的一个文件目录项。
37.文件存储空间管理实质上是对（外存空闲空间 ）的组织和管理。
38.可将链接式文件中的文件内容装入到（ 离散 ）的多个盘块中，并通过（链接指针 ）将它们构成一个队列，（ 显式 ）链接文件具有较高的检索速度。
39.（考研真题）使用位示图（30行，50列）表示空闲盘块状态。如当分配一个盘块号为174时，其在位示图中的行列数为（ ）。（注：行列始下标为0）
【参考答案】3，23
【解析】行号为174 DIV 50=3，列号为174 MOD 50-1=23，则行列数分别是3，23。
下标从1开始块数=n*（i-1）+j n列数,()
40.假定某盘组共有100个柱面，每个柱面上有16个磁道，每个磁道分成4个扇区。那么整个磁盘空间的存储块数共有（ ）个。若用字长32位单元构造位示图，需要（ ）个字。
【解析】整个磁盘空间的存储块数为4´16´100=6400个。位示图中应有6400个位，如果字长32位，则每行32位，共可以构造6400 /32=200个字，即200行。
1.1.3 判断题
2.操作系统的所有程序不都必须常驻内存。
（只有OS的部分内核程序才须要常驻内存。
11.不同的进程bu必然对应不同的程序X
进程是程序的一次执行，不同的进程可以包含同一个程序，同一个程序在执行中也可以产生多个进程
12.并发不是并行的不同表述，其原理不相同。（ ）
16.（考研真题）进程的3种基本状态：就绪、运行和阻塞，任意两种状态之间不都可以相互转换。（）进程从阻塞状态不能转换为运行状态，阻塞态当等待的事件发生时，会转为就绪态。
18.当条件满足时，进程不可以由阻塞态直接转换为运行态。
21.作业一旦被作业调度选中，系统就给它分配CPU。（X）
【解析】作业被作业调度程序选中，说明作业进入内存并创建了进程。但属于该作业的进程可能处于运行、就绪或等待状态，只有处于运行状态的进程才能占有处理机CPU
31.临界区是指进程中用于实现进程互斥的那段代码。（X）
【解析】临界区是指访问临界资源的那段代码，不是实现进程互斥的那段代码。
36.记录型信号量在使用过程中不存在“忙等”现象。
【解析】整型信号量存在“忙等”现象，为了解决这个问题，
提出了记录型信号量，记录信号量中不存在“忙等”现象。
40.页是信息的物理单位，段是信息的逻辑单位。
分页存储管理方式，能消减内存的外零头，提高内存的利用率
43.（考研真题）在现代操作系统的支持下，允许程序装入一部分即可运行
【解析】部分程序装入即可运行，是实现虚拟存储器的前提
54.（考研真题）通道所执行的通道程序存放在主机的内存中。（ ）
【解析】通道没有自己的内存，通道所执行的通道程序放在主机的内存中，即通道与CPU共享内存。
60. SPOOLing技术不可以提高慢速外设的速度。（X ）让系统内不能多道并行的独占变成共享
【解析】SPOOLing技术不能提高设备速度，只能通过暂时接收慢速外设的数据到输入/输出井，当设备空闲时再进行传输，缓解低速设备和高速设备速度不匹配矛盾。
66.（考研真题）多级文件目录可以提高文件的查询速度。（ ）
67.树状目录结构清晰，有利于文件的共享和保护。（ X ）
【解析】树状目录结构不支持文件共享，有向无环图目录结构支持文件共享
69.（考研真题）利用符号链可以实现文件共享。
【解析】文件共享常用两种方式：一种是基于索引结点的共享方式，称为硬链接；另一种基于符号链实现文件共享，称为软链接，也称为符号链接。
1.1.4 简答题
1.批处理操作系统、分时操作系统和实时操作系统各有什么特点？
1.（1）批处理OS的用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行，交互能力差。
（2）分时OS可让多个用户同时使用计算机，人机交互性较强，具有每个用户独立使用计算机的独占性，系统响应及时。
（3）实时OS能对控制对象做出及时反应，可靠性高，响应及时，但资源利用率低。
2.简述操作系统内核及其功能。
内核是OS最核心的部分，它是一组程序模块，作为安全软件来提供支持进程并发执行的基本功能和基本操作。内核程序通常驻留在内核空间且运行于内核态，具有访问硬件设备和所有内存空间的权限，是仅有的能够执行特权指令的程序。
内核的主要功能如下：
（1）资源抽象。用软件抽象硬件资源，简化对其所执行的操作，犀蔽低层的物理细节，如提供设备驱动程序、创建虚拟设备等；
（2）资源分配。把所抽象的各种资源分配给多个应用程序使用，并负责回收资源；
（3）资源共享。根据资源的类型和特性，提供不同的机制以确保进程获得所需资源，允许进程共享资源并提供资源的互斥与同步机制。
6.什么是多道程序设计技术？多道程序设计的优点是什么？为什么说直到出现中断和通道技术后，多道程序概念才变为有用的?
现代计算机系统一般都采用基于多道程序设计的技术。通常多道程序设计是指在主存中同时存放多道用户作业,使它们都处于执行的开始点和结束点之间。
多道程序设计的特点如下：
（1）多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一；
（3）宏观上并行。从宏观上看,它们在同时执行；
（4）微观上串行。从微观上看,它们在交替、穿插地执行。
因为中断是激活操作系统的手段，只有通过中断技术才能使CPU从一个作业的处理转到另一个作业的处理，而通道使主机与外设可以并行工作，所以直到出现中断和通道技术后，多道程序概念才变为有用。
7.分时系统和实时系统有什么区别？设计适用于实时环境的操作系统的主要困难是什么？
实时系统与分时系统的主要区别如下。
（1）系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统，而实时系统则大多数都是具有某种特殊用途的专用系统。
（2）响应时间的长短不同。分时系统的响应时间通常为秒级，而实时系统的响应时间通常为毫秒级甚至微秒级。
（3）交互性的强弱不同。分时系统的交互性强,而实时系统的交互性弱。
设计适用于实时环境的操作系统的主要困难有：①需要高精度的实时时钟管理；②需要高可靠性和安全性做保证；③需要连续的人机对话功能及快速的中断响应、中断处理能力；④过载的防护等问题。
9.（考研真题）画出进程三种状态——运行、就绪和阻塞之间的状态转换图，并写出转换原因。
。 
11.（考研真题）从操作系统设计角度，谈谈PCB的作用。
PCB是OS为每个进程定义的数据结构，能使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。OS通过PCB感知进程的存在，并根据PCB实施对进程的控制和管理，因此PCB是为了保证程序并发执行而创建的。\
12.在一个单CPU的多道程序设计系统中，若在某一时刻有N个进程同时存在，那么处于运行态、阻塞态和就绪态进程个数的最小值和最大值分别可能是多少？
【参考答案】各状态最值如表所示。
| 最小值 |
最大值 |
|
| 运行态 |
0 |
1 |
| 阻塞态 |
0 |
N |
| 就绪态 |
0 |
N-1 |
只要有一个就绪态，CPU就不会空闲，就会有运行态进程，因此，就绪态最大值为N-1
15.（考研真题）请简要阐明时间片轮转调度算法的基本思想。请分析：（1）假设时间片的长度无限长，这时的时间片轮转调度算法具有什么样的特点？（2）假设时间片的长度无限缩短，这时的时间片轮转调度算法又具有什么样的特点？
（1）如果时间片的长度无限长，即所有的算法在分配的时间片内都能完成，这时的时间片轮转调度算法会简化成先来先服务算法，对于短作业可能不利。
（2）假设时间片的长度无限缩短，这时的时间片轮转调度算法中，进程切换和进程调度会频繁发生，导致系统开销增大。
16.（考研真题）死锁预防中采用什么方法来破坏“循环等待”条件？并证明该方法。
在死锁预防中，采用“有序资源分配法”来破坏“循环等待”条件。有序资源分法是将系统中的所有资源按照类型进行排序编号，每个进程必须按照编号递增次序请求资源，同类资源一次性申请完。
证明：如果某进程请求资源Ri（i为编号），则其后面的进程只能请求排在资源Ri后面的资源，无法请求排在Ri前面的资源。对申请资源做这样的限制后，系统中不会出现资源请求环路现象，因此破坏了死锁产生必要条件中的“环路等待”条件。
17.进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？
（1）若干同学去图书馆借书；
（2）两队举行篮球比赛；
（3）流水线生产的各道工序；
（4）商品生产和社会消费。
进程之间存在着直接制约和间接制约这两种制约关系，其中直接制约（同步）是由于进程间的相互合作而引起的；而间接制约（互斥）则是由于进程间共享临界资源而引起的。
（1）若干同学去图书馆借书是间接制约，其中书是临界资源。
（2）两队举行篮球比赛是间接制约，其中篮球是临界资源。
（3）流水线生产的各道工序是直接制约，各道工序间须要相互合作，每道工序的开始都依赖于前一道工序的完成。
（4）商品生产和社会消费是直接制约，两者须要相互合作。商品生产出来后才可以被消费，商品被消费后才须要再生产。
19.什么是临界资源？什么是临界区？
在计算机中有许多资源一次只能允许一个进程使用，我们把一次仅允许一个进程使用的资源称为临界资源，如打印机和一些共享变量等。
进程中访问临界资源的那段代码称为临界区。
23.什么叫重定位？采用内存分区管理时，如何实现程序运行时的动态重定位？
所谓地址重定位，就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程，即将地址空间给出的逻辑地址映射到内存的物理地址上。地址重定位有静态重定位和动态重定位两种方式。
采用内存分区管理时，在硬件上设置一个“重定位寄存器”可以实现程序运行时的动态重定位。这种情况下地址重定位是在程序执行期间由地址变换机构动态实现的，主要的计算依据是：物理地址=逻辑地址+重定位寄存器的内容。
27.什么是虚拟存储器，主要特征是什么？
所谓虚拟存储器,就是指具有请求调入功能与置换功能,把内存与外存结合起来使用,能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量与内存大小无直接关系,主要由内存容量与外存容量之与所决定,其运行速度接近于内存速度,而成本却又接近于外存。
虚拟存储器的特征可以概括为以下4点:
(1)离散性:装入虚拟存储器的进程都就是离散存放的,这就是虚拟存储器的基础。
(2)多次性:一个作业被分成多次调入内存运行,即在作业运行时没必要将其全部装入,只需将当前要运行的那部分程序与数据装入内存,以后每当运行到尚未调入的那部分程序时,再将它调入。
(3)对换性:允许在作业的运行过程中进行换进、换出。在进程运行期间,允许将那些暂不使用的程序与数据,从内存调至外存的对换区(换出),待以后需要时再将它们从外存调至内存(换进)。
(4)虚拟性:指能够从逻辑上扩充内存容量,虚拟出一个较大的逻辑空间,使用户所瞧到的内存容量远大于实际内存容量。
3.（考研真题）画出下面4条语句所对应的前驱图。
P1：a=x+2y； P2：b=a+6； P3：c=4a-9； P4：d=2b+5c
【参考答案】P2和P3都必须在a被赋值之后才能执行；但P2、P3可以并发执行，因此它们彼此互不依赖；P4必须在b和c被赋值后才能执行。因此前趋图如图所示。
5.（考研真题）5个进程P1、P2、P3、P4、P5几乎同时到达，预期运行时间分别为10、6、2、4、8个时间单位。各进程的优先级分别为3、5、2、1、4（数值越大，优先级越高）。请按下列调度算法计算任务的平均周转时间（进程切换开销可忽略不计）。
（1）先来先服务（按P1、P2、P3、P4、P5顺序）算法。
（2）时间片轮转算法，假定时间片大小为2个时间单位。
（3）优先权调度算法。
5. 【参考答案】根据算法思想，确定调度先后顺序。
（1）FCFS调度顺序如图所示。
（2）时间片轮转调度顺序如图所示。
（3）优先权调度算法的调度顺序如图所示。
于是，可以得到如表所示的结果。
| 算法 |
时间类型 |
P1 |
P2 |
P3 |
P4 |
P5 |
平均 |
| 运行时间 |
10 |
6 |
2 |
4 |
8 |
||
| FCFS |
周转时间 |
10 |
16 |
18 |
22 |
30 |
19.2 |
| 带权周转时间 |
1 |
2.67 |
9 |
5.5 |
3.75 |
4.384 |
|
| RR |
周转时间 |
30 |
22 |
6 |
16 |
28 |
20.4 |
| 带权周转时间 |
3 |
3.67 |
3 |
4 |
3.5 |
3.434 |
|
| 优先权 |
周转时间 |
24 |
6 |
26 |
30 |
14 |
20 |
| 带权周转时间 |
2.4 |
1 |
13 |
7.5 |
1.75 |
5.13 |
7.单道批处理系统中有4个作业，其有关情况如下表所示。在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。
| 作业 |
提交时间/h |
运行时间/h |
| J1 |
8.0 |
2 |
| J2 |
8.6 |
0.6 |
| J3 |
8.8 |
0.2 |
| J4 |
9.0 |
0.5 |
【参考答案】在8.0只有作业J1到达，系统先将作业J1投入运行。作业J1运行2个小时后完成。这时3个作业都已到达，要计算3个作业的响应比，然后使响应比最高的投入运行。3个作业的响应比为：
作业J2的响应比=1+(10.0-86)/0.6=3.33
作业J3的响应比=1+(10.0-8.8)/0.2=7
作业J4的响应比=1+(10.0-9.0)/0.5=3
从计算的结果来看，作业J3的响应比最高，所以让作业J3先执行。作业J3执行0.2小时后完成。此时作业J2和作业J4的响应比为：
作业J2的响应比=1+(10.2-8.6)/0.6=3.67
作业J4的响应比=1+(10.2-9.0)/0.5=3.4
从计算的结果来看，作业J2的响应比最高，所以再让作业J2执行。
可见，4个作业的执行次序为：作业J1，作业J3，作业J2，作业J4。
计算结果如下表：
| 作业号 |
到达时间 |
运行时间 |
开始时间 |
完成时间 |
周转时间 |
带权周转时间 |
| 1 |
8.0 |
2.0 |
8.0 |
10.0 |
2.0 |
1.0 |
| 2 |
8.6 |
0.6 |
10.2 |
10.8 |
2.2 |
3．67 |
| 3 |
8.8 |
0.2 |
10.0 |
10.2 |
1.4 |
7 |
| 4 |
9.0 |
0.5 |
10.8 |
11.3 |
2.3 |
4.6 |
平均周转时间为T=(2.0+2.2+1.4+2.3)/4=1.975
平均带权周转时间为W=(1.0+3.67+7+4.6)/4=3.98
9.（考研真题）假定系统中有5个进程P0、P1、P2、P3、P4和4种资源A、B、C、D，若出现如表所示资源分配情况。
| 进程 |
已分配到资源 |
尚需资源需求 |
当前可用资源数 |
| P0 |
（1，1，1，0） |
（0，3，3，1） |
（0，3，2，2） |
| P1 |
（0，2，3，1） |
（0，3，4，2） |
|
| P2 |
（0，2，1，2） |
（1，0，3，4） |
|
| P3 |
（0，3，1，0） |
（0，3，2，0） |
|
| P4 |
（1，0，2，1） |
（0，4，2，3） |
问：（1）该状态是否安全？为什么？
（2）如果进程P0提出资源请求（0，0，0，1），系统能否将资源分配给它？为什么？
9. 【参考答案】严格按照银行家算法及安全检查子算法进行。
（1）初始状态如表所示。
| 进程 |
Work |
Need |
Allocation |
Work + Allocation |
Finish |
| P3 |
0，3，2，2 |
0，3，2，0 |
0，3，1，0 |
0，6，3，2 |
True |
| P0 |
0，6，3，2 |
0，3，3，1 |
1，1，1，0 |
1，7，4，2 |
True |
| P1 |
1，7，4，2 |
0，3，4，2 |
0，2，3，1 |
1，9，7，3 |
True |
| P4 |
1，9，7，3 |
0，4，2，3 |
1，0，2，1 |
2，9，9，4 |
True |
| P2 |
2，9，9，4 |
1，0，3，4 |
0，2，1，2 |
2，11，10，6 |
True |
存在一个安全序列P3，P0，P1，P4，P2，所以，该状态是安全的。
（2）Request0(0，0，0，1)<Need0(0，3，3，1)
Request0(0，0，0，1)<Available(0，3，2，2)
故尝试将资源分配给P0，修改P0对应资源，P0对应的Need（0，3，3，0），Allocation（1，1，1，1），系统的Available为（0，3，2，1）。进程资源分配情况如表所示。
| 进程 |
Work |
Need |
Allocation |
Work + Allocation |
Finish |
| P3 |
0，3，2，1 |
0，3，2，0 |
0，3，1，0 |
0，6，3，1 |
True |
| P0 |
0，6，3，1 |
0，3，3，0 |
1，1，1，1 |
1，7，4，2 |
True |
| P1 |
1，7，4，2 |
0，3，4，2 |
0，2，3，1 |
1，9，7，3 |
True |
| P4 |
1，9，7，3 |
0，4，2，3 |
1，0，2，1 |
2，9，9，4 |
True |
| P2 |
2，9，9，4 |
1，0，3，4 |
0，2，1，2 |
2，11，10，6 |
True |
存在一个安全序列P3、P0、P1、P4、P2，该状态是安全的，所以，可以实施分配。
15.在一个分页存储管理系统中，页面大小为4KB，系统中的地址占24位，给定页面变换表如下表所示。
（1）计算逻辑地址（页号为3，页内地址为100）的物理地址。
（2）说明地址变换过程。
| 页号P |
块号B |
| 0 |
3 |
| 1 |
4 |
| 2 |
9 |
| 3 |
7 |
15.【参考答案】（1）逻辑地址（页号3，页内地址100）的物理地址为：
7×4KB+100=28KB+100=28772
（2）在请求分页存储管理中，系统是通过页表进行地址转换。先将逻辑地址分解成页号P和页内地址W两部分，然后查页表，可得页号P对应的物理块号为B，从而变换出对应的物理地址为：物理地址=块号×页面大小+页内地址
17.设作业的虚拟地址为24位，其中高8位为段号，低16位为段内相对地址。试问：
（1）一个作业最多可以有多少段？
（3）每段的最大长度为多少字节？
（3）某段式存储管理采用如下段表,试计算[0,430]、[1,50]、[2,30]、[3,70]的主存地址。其中方括号内的前一元素为段号，后一元素为段内地址。当无法进行地址变换时，应说明产生何种中断。
| 段号 |
段长 |
主存起始地址 |
是否在主存 |
| 0 |
600 |
2100 |
是 |
| 1 |
40 |
2800 |
是 |
| 2 |
100 |
否 |
|
| 3 |
80 |
4000 |
是 |
17. 【参考答案】（1）一个作业最多可以有28=256个段。
（2）每段的最大长度为216=64KB=65536字节。
（3）逻辑地址（0，430）的主存地址为2100+430=2530；
逻辑地址（1，50）无法进行地址变换，因为产生了越界中断；
逻辑地址（2，30）无法进行地址变换，因为产生了缺段中断；
逻辑地址（3，70）的主存地址为4000+70=4070。
19.对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5。当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）
【参考答案】（1）FIFO 淘汰算法：内存块为3 时，缺页中断（或称缺页次数、页面故障）为9；内存块为4 时，缺页中断为10。（Bleady现象）
（2）LRU淘汰算法：内存块为3时，缺页中断为10；内存块为4 时，缺页中断为8。
25.已知某程序访问以下页面：0，1，4，2，0，2，6，5，1，2，3，2，1，2，6，2，1，3，6，2。如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。
（1）FIFO替换算法（2）LRU替换算法
25. 【参考答案】（1）FIFO 算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：
缺页率13/20=65%
（2）LRU 算法是最近最久未使用的页面予以淘汰。算法如图所示：
缺页率14/20=70%
32.（考研真题）磁盘请求服务队列中要访问的磁道分别为38、6、37、100、14、124、65、67，磁头上次访问了20磁道，当前处于30磁道上，试按先来先服务、最短寻道时间优先和扫描算法，分别计算磁头移动的磁道数。
参考答案】该题分步解答如下。
（1）先来先服务算法。磁盘磁头移动顺序为30、38、6、37、100、14、124、65、67。磁头移动磁道数为8+32+31+63+86+10+59+2=391。
（2）LRU算法。磁盘磁头移动顺序为30、37、38、14、6、65、67、100、124。移动磁道数为7+1+24+8+59+2+33+24=158。
（3）扫描算法。磁盘磁头移动顺序为30、37、38、65、67、100、124、14、6。磁头移动道数为7+1+27+2+33+24+110+8=212。
33.（考研真题）对于移动头磁盘，假设磁头现在位于25号磁道上（并向磁道号变小的方向移动），且基于磁道号的磁盘访问请求序列（按提出时间的先后次序排列）为39、62、18、28、100、130、90。 试采用最短寻道时间优先调度算法和电梯调度算法，分别给出相关磁盘访问请求处理的先后次序，并计算相应的平均寻道时间。
【参考答案】依据SSTF算法，磁盘访问请求处理的先后次序为25、28、18、39、62、90、100、130。平均寻道时间为(3+10+21+23+28+10+30)/7=125/7=17.86。
根据SCAN算法的思想，磁盘访问请求处理的先后次序为25、18、28、39、62、90、100、130。平均寻道时间为(7+10+11+23+28+10+300)/7=119/7=17。
1.1 选择题
1.（考研真题，单项选择题）单道批处理系统的主要缺点是（ ）。
A. CPU利用率不高
2.（考研真题，单项选择题）提高单机资源利用率的关键技术是（ ）。
D.多道程序设计技术
3.（考研真题，单项选择题）并发性是指若干事件在（ ）发生。
A C.同一时间间隔内
4.（单项选择题）批处理系统的主要缺点是（ ）。
D.无交互能力
10.（考研真题，单项选择题）进程和程序的本质区别是（ ）。
A.前者是动态的，后者是静态的
11.（单项选择题）进程的基本状态（ ）可以由其他两种基本状态转变而来。
A.就绪状态
12.（单项选择题）进程处于（ ）时，它处于非阻塞态
C.等待操作系统分配CPU时间
15.（名校考研题，单项选择题）进程和程序的本质区别在于（ ）。
D.前者可以并发执行，后者不能并发执行
16.（考研真题，单项选择题）进程的状态和优先级信息存放在（ ）。
PCB PCB是进程存在的唯一标识，它存储着进程的状态和优先级等信息。
19.（考研真题，单项选择题）用信箱实现进程间互通信息的通信机制要有两个通信原语，它们是（ ）。
C.发送原语和接收原语
20.（单项选择题）死锁的4个必要条件中，无法破坏的是（ ）。
A.环路等待资源 B.互斥使用资源 C.占有且等待资源 D.非抢夺式分配
21.（单项选择题）死锁与安全状态的关系是（ ）。
B.安全状态有可能成为死锁状态
D.死锁状态一定是不安全状态
。
|
不安全状态 |
|
死锁状态 |
26.（单项选择题）一个作业8:00到达系统，估计运行时间为1小时。若10:00开始执行该作业，其响应比是（ ）
【解析】响应比==服务/执行+1=响应时间/要求服务时间=(等待时间+要求服务时间)/要求服务时间=(2+1)/1=3。
27.（考研真题，单项选择题）下列调度算法中，不会导致饥饿现象的是（ ）。
A.时间片轮转 B.静态优先数调度
C.非抢占式短任务优先 D. 抢占式短任务优先
【解析】采用静态优先级调度且系统总是出现优先级高的任务时，优先级低的任务总是得不到处理机而产生饥饿现象。短任务优先调度当系统总是出现新来的短任务时，长任务总是得不到处理机，会产生饥饿现象。
28.（考研真题，单项选择题）系统中有4个进程都要使用某类资源。若每个进程最多需要3个该类资源，为保证系统不发生死锁，系统应提供该类资源至少是（ ）。
C.9个
【解析】系统中有4个进程，每个进程最多需要3个资源，先给每个进程分配2个资源，共需要8个资源，此时需要系统中还有1个空闲资源，分配给任一进程，才不会发生死锁，故至少需要9个资源。
31.（单项选择题）采用资源剥夺法可以解除死锁，还可以采用（ ）方法解除死锁。
B.撒销进程
35.（考研真题，单项选择题）若记录型信号量S的初值为15，当前值为-15，则表示有（ ）等待进程。
A. 15个
【解析】当S值小于0时，绝对值表示阻塞队列中进程的个数。
37.（单项选择题）从下面对临界区的论述中，选出一条正确的论述。（ ）
D.临界区是指进程中访问临界资源的那段代码
39.（考研真题，单项选择题）设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待资源的进程数，则M、N分别是（ ）。
B. 1、0
【解析】根据信号量的物理含义：S.value＞0时表示有S.value个资源可用；S.value=0表示无资源可用；S.value＜0则S.value的绝对值表示等待队列中的进程个数。信号量的当前值为1，则表示该资源的可用个数为1，没有等待该资源的进程。
40.（考研真题，单项选择题）若记录型信号量S的初值是3，则当前值为1时表示有（ ）个阻塞等待进程。
C. 0个
【解析】S为1，值大于0，说明允许进程访问资源，进入临界区，当前没有阻塞等待
41. （考研真题，单项选择题）在对记录型信号量的P操作的定义中，当信号量的值（ ）时，执行P操作的进程变为阻塞状态。
B.小于0 C.等于0 D.小于或等于0
41.【参考答案】B
【解析】对于记录型信号量，每执行一次P操作，信号量的值都会减1，当信号量的值小于0的时候，说明系统中无可用临界资源，进程变为阻塞状态
42.（考研真题，单项选择题）如果3个进程共享一个互斥段，每次最多可以允许2个进程进入互斥段，则信号量的变化范围是（ ）。
A. 2、1、0、-1
【解析】最多允许2个进程进入互斥段，初始值则为2，因为每个进程进去时都先要行P操作，然后判断信号量的值是否大于0，不是则表示当前互斥段内已经有2个进程，当第3个进程再执行P操作时，信号量值为-1，该进程阻塞。
45.（考研真题，单项选择题）采用（ ）不会产生内部碎片。
A.分页式存储管理 B.分段式存储管理
C.随机存储管理 D.段页式存储管理
【解析】在页式存储管理的方式中，最后1个页面往往会出现不足1页大小的情况，产生页内碎片。
48.（考研真题，单项选择题）在页式存储管理系统中，页表内容如表所示（均从0开始编号）。
| 页号 |
块号 |
| 0 |
2 |
| 1 |
1 |
| 2 |
6 |
| 3 |
3 |
| 4 |
7 |
若页面大小为4KB，则地址变换机构将逻辑地址0转换成物理地址为（ ）。
A. 8192
【解析】逻辑地址0，对应页号为0，查页表可知块号为2，物理地址为2´4K=8K=8192。
所示。
| 访问串 |
2 |
0 |
2 |
9 |
3 |
4 |
2 |
8 |
2 |
4 |
8 |
4 |
5 |
7 |
| 内存 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
7 |
| 0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
||
| 9 |
9 |
9 |
9 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
||||
| 3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
5 |
5 |
54.（考研真题，单项选择题）在请求页式存储管理中，若所需页面不在内存中，则会引起（ ）。
D.页故障
【解析】在请求页式存储管理中，若所需页面不在内存中，则会引起页故障，即缺页中断。
56.（考研真题，单项选择题）在页式存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（ ）。
A. FIFO算法
【解析】Belady现象是系统为进程分配的页数增多（未分配进程所需的全部页），但缺页率反而提高的异常现象。只有FIFO算法才会出现Belady现象。FIFO算法将最早调入的页调出，而调出的页在不久可能会被重新使用出现反复调入调出，缺页率反而上升。
63.（单项选择题）请求分段系统在分段系统的基础上，增加了（ ）及分段置换软件功能。
A.请求调段 B.段表 C.缺段中断 D.地址变换
65.（单项选择题） 通道是一种（ ）。
D. 专用处理机A. 保存 I/O 信息的部件
【解析】通道是一种特殊的I/O专用处理机。引入通道是为了建立独立的I/O操作，这不仅指数据的传送能独立于CPU，而且有关I/O操作的组织，管理及结束也尽量独立，以保证CPU有更多的时间去进行数据处理。
68.（考研真题，单项选择题）程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A.逻辑设备名
【解析】用户程序对I/O设备的请求采用逻辑设备名，而在程序实际执行时使用物理设备名。
71.（考研真题，单项选择题）操作系统中的SPOOLing技术，实质是将（ ）转化为共享设备的技术。
B.独占设备
【解析】SPOOLing的核心思想是利用磁盘（输入井、输出井）来模拟独占设备的操作，使一台独占设备变成多台可并行的虚拟设备。用户向独占设备提交的请求实际上被提交到输入或输出井里面。从输入/输出井到实际物理独占设备的数据传输由SPOOLing进程统一控制和调度。
72.（考研真题，单项选择题）为了缓和CPU和I/O设备间速度不匹配的矛盾，提高CPU和I/O设备的并行性，现代操作系统关于I/O设备与处理机之间的数据交换几乎都用到了（ ）。
B.缓冲区
【解析】引入缓冲区可以在高速和低速设备之间起一个速度平滑作用，用于暂时存储数据，经常访问的数据可以放进缓冲区，减少对慢速设备的访问等待，以提高系统效率。
74.（考研真题，单项选择题）假设磁头当前位于第105道，正在向磁道号增加的方向移动。现有一个磁道访问请求序列为35、45、12、68、110、180、170、195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是（ ）。
A. 110、170、180、195、68、45、35、12
【解析】SCAN调度算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务对象。当前磁道向序号增加的方向移动，当前位于第105道，则距离最近的下一个应该是第110磁道，依次递增到最高195，再向序号减少的方向移动，离当前195磁道最近的是68号磁道，依次递增到所有的请求完成，所以磁道访问序列为110、170、180、195、68、45、35、12。
76.（考研真题，单项选择题）从用户的角度看，文件系统主要是实现（ ）。
A. 数据存储 B. 数据保护 C. 数据共享 D. 按名存取
【解析】用户只需要向系统提供所需要访问的文件名称，就可以快速准确的找到指定文件在外存上的存储位置，这是文件系统向用户提供的最基本服务。
79.（考研真题，单项选择题）使用绝对路径名访问文件是从（ ）开始按目录结构访问某个文件。
A. 当前目录 B. 用户主目录 C. 根目录 D. 父目录
88.（考研真题，单项选择题）按文件的物理组织结构可将文件分成（ ）等。
C. 连续文件、链式文件、索引文件
【解析】按文件的物理组织结构可将文件分成顺序文件（连续文件）、链接文件（链式文件）、索引文件和直接文件
92.（单项选择题）下列方式中，（ ）不能改善磁盘系统的可靠性。
A. 廉价磁盘冗余阵列 B. 磁盘容错技术 C. 磁盘高速缓存 D. 后备系统
【解析】磁盘高速缓存是提高磁盘I/O速度的途径。
96.（考研真题，单项选择题）磁盘高速缓存设在（ ）中。
A.内存 C. Cache D.磁盘
【解析】磁盘高速缓存是指在内存中为磁盘盘块设置的缓冲区，在缓冲区中保存了某些盘块的副本。
1.1.2 填空题（课上选讲）
1.实时系统应具有的两个基本特征是（及时性 ）和（可靠性 ）。。。
【解析】各并发进程按各自独立的、不可预知的速度向前推进。这种特性称为进程的异步性。
2.为实现CPU与外部设备的并行工作，（ 中断机制 ）是系统必须引入的一种机制。
3.多道批处理系统的硬件支持是20世纪60年代发展起来的（ 通道）和（ 中断机制 ）。
4.操作系统为用户提供了两种类型的接口，分别是（ 命令接口 ）和（ 程序接口）。
5.用户为阻止进程继续执行，应利用（ 阻塞 ）原语，若进程正在执行，应转变为（ 阻塞）状态；以后，若用户要恢复其运行，应利用（ 唤醒 ）原语，此时进程应转变为（ 就绪 ）状态。
6. PCB的初始化包括（ 进程标识符信息；处理机状态信息和处理机控制信息 ）。
7.进程的并发性是指多个进程在（ 同一时间间隔 ）内同时发生。
8.进程的执行并不是“一气呵成”，而是走走停停的，这种特征称为进程的（ 异步性 ）。
9.下列作业调度算法中，（ 短作业优先调度算法 ）具有最短的作业平均周转时间。
10.在多进程并发执行中，肯定不会因竞争（ CPU ）而发生死锁。
【解析】CPU为可剥夺资源，竞争可剥夺资源不会发生死锁。
11.死锁的产生有4个必要条件，在死锁的预防策略中，资源的有序分配策略可以破坏（环路等待 ）条件。
12.银行家算法在解决死锁问题中是用于（ 避免死锁 ）的。
13.在利用信号量实现进程互斥时，应将（ 临界区 ）置于（ P操作（wait操作） ）和（ V操作（signal操作））之间。
14.在每个进程中访问（临界资源 ）的那段代码称为临界区。
15.计算机系统中，一次仅允许一个进程使用的资源，称为（临界资源）。
16.（考研真题）15个进程共享同一程序段，而每次最多允许4个进程进入该程序段，若用P、V操作同步机制，则记录型信号量S的取值范围为（-11≤S≤4 ）。
17.把程序地址空间中使用的逻辑地址变成内存中物理地址称为（重定位 ）。
18.在分页管理系统中，为实现地址转换设置了寄存器，其中存放的是（ 页表 ）在内存中的起始地址。
19.（考研真题）分页存储管理系统具有快表，内存访问时间为2μs，检索快表时间为0.5μs。若快表的命中率为80%，且忽略快表更新时间，则有效访问时间是（ ）μs。
2.9μs
【解析】在引入快表的分页存储管理系统中，有效访问时间的计算公式为：
EAT=a×λ+(t+λ) ×(1-a)+t=2t+λ-t×a
=命*快表t+未命*（内访t+快表t）+内访t
=命中率*检索快表时间+未命中率*（内存访问时间+检索快表时间）+内存访问时间
其中，t为内存访问时间，t=2μs；λ为检索快表的时间，λ=0.5μs；a为快表的命中率，a=80%。代入数据，得有效访问时间EAT=2.9μs。
20.在具有两级页表的分页存储管理系统中，CPU每次要存取一个数据时，必须访问（ 3 ）次内存。
【解析】两级页表中，CPU存取一个数据要访问3次内存。第1次访问一级页表，第2次获得二级页表，第3次存取数据。
21.某段式存储管理系统中，地址长度为32位，若允许的最大段长为64KB，则段号占（ 16 ）位。
【解析】分段地址结构由段号和段内地址组成，由于允许的最大段长是64KB=216B，那么段内地址占16位，则段号占32-16=16位。
22.虚拟存储器的基本特征是（ 多次性 、对换性 、虚拟性 ），因而决定了实现虚拟存储器的关键技术是（ 请求调页（段））和（页（段）置换 ）。
23.实现页式虚拟存储器，除了需要有一定容量的内存和相当容量的外存外，还需要有页表机制；地址变换机构；缺页中断机构的硬件支持。
24.（考研真题）在请求分页存储管理中，逻辑地址长度为16位，每页为2KB，部分页表如表所示。
| 页号 |
物理块号 |
| 0 |
4 |
| 1 |
10 |
| 2 |
6 |
| 3 |
2 |
则逻辑地址0EC5H所对应的物理地址为（ 56C5 ）H。
【解析】请求分页存储管理方式中分页地址结构，由页号和偏移量（页内地址）构成。由每页2KB的页面大小可以得出，页内地址占分页地址的低地址开始11位。由0EC5（H）得其二进制地址为00001 110 1100 0101，则页内地址为110 1100 0101，高地址部分表示页号为00001，得页号为1，查表可得对应的物理块号为10（十进制）。10转化为二进制为1010，由物理地址=块号×页面大小+偏移量（页内地址）得：1010×211+110 1100 0101=0101 0110 1100 0101=56C5 H。
25.为实现请求分页管理，应在基本分页的页表基础上增加状态位；访问字段；修改位；外存地址等数据项。
26.磁盘属于（ 块 ）设备，其信息的存取是以（数据块 ）为单位的；磁盘的I/O控制主要采取（中断驱动方式 ）；打印机的I/O控制主要采取( DMA控制方式 )
27.独占设备是指在一个作业的整个执行期间独自占用的设备，它一般采用（ 静态 ）分配。共享设备是指在某个时间段内可由多个作业同时使用的设备，一般采用（动态）分配。
28.在利用RS-232接口进行通信时，其通信速率为9.6KB/S(B为Bit)。如果在通信接口中仅设置了一个8位寄存器作为缓冲寄存器，这意味着大约每隔（ ）的时间便要中断一次CPU，且要求CPU必须在（ ）时间内予以响应。
【参考答案】0.8ms；0.1ms
【解析】8位寄存器作为缓冲寄存器就要传输8bit数据中断一次，所需时间为8/9.6»0.8ms。CPU响应时间为1/9.6»0.1ms
29.转速为7200转/分钟，平均旋转延迟时间约为（4.17 ）。
【解析】平均旋转延迟时间为1/2r，其中r为转速。60000/(2´7200)ms»4.17ms
转半周所用的时间
30.（考研真题）操作系统中采用缓存技术的主要目的是提高CPU和设备之间的（并行）程度。
31.在UNIX系统中，所有的（I/O设备）都被看成是特殊文件，它们在使用形式上与普通文件相同，但它们使用是和（ 设备管理程序 ）紧密相连的。
【解析】UNIX系统中的特殊文件也称设备文件。UNIX利用特殊文件作为用户与设备文件的接口，使用户访问外部设备，能像访问普通文件一样，无须知道各种设备的具体操作。特殊文件不包含任何数据，它只是在文件系统中建立了物理设备与文件名之间的映射，并提供相关的驱动程序，因此使用它们要和设备管理程序紧密相连。
32.对文件的访问有（顺序访问；随机访问/直接访问）两种方式。
33.鉴于文件查找过程中，只有文件名对目录检索有用，所以可把文件名与文件的其它属性分离开来分别存放，把有关文件的文件名组织在一起形成符号名文件目录，而文件的其它属性则以所谓（索引结点）的数据结构方式集中组织在一起。
34.（考研真题）在操作系统中，FCB是指（ 文件控制块 ）。file control lock
35.（考研真题）由字符序列组成，文件内的信息不再划分结构，这是指（流式文件 ）。
【解析】字符流的无结构文件，其长度以字节为单位。对流式文件的访问是利用读写指针指示下一个要访问的字符。大量的源程序，可执行程序，库函数等均为无结构文件。
36. 文件目录是（文件控制块 ）的有序集合。
【解析】文件与文件控制块一一对应，为了提高文件检索效率，操作系统常将文件控制块集中管理。这种文件控制块的有序集合称为文件目录，一个文件控制块就是其中的一个文件目录项。
37.文件存储空间管理实质上是对（外存空闲空间 ）的组织和管理。
38.可将链接式文件中的文件内容装入到（ 离散 ）的多个盘块中，并通过（链接指针 ）将它们构成一个队列，（ 显式 ）链接文件具有较高的检索速度。
39.（考研真题）使用位示图（30行，50列）表示空闲盘块状态。如当分配一个盘块号为174时，其在位示图中的行列数为（ ）。（注：行列始下标为0）
【参考答案】3，23
【解析】行号为174 DIV 50=3，列号为174 MOD 50-1=23，则行列数分别是3，23。
下标从1开始块数=n*（i-1）+j n列数,()
40.假定某盘组共有100个柱面，每个柱面上有16个磁道，每个磁道分成4个扇区。那么整个磁盘空间的存储块数共有（ ）个。若用字长32位单元构造位示图，需要（ ）个字。
【解析】整个磁盘空间的存储块数为4´16´100=6400个。位示图中应有6400个位，如果字长32位，则每行32位，共可以构造6400 /32=200个字，即200行。
1.1.3 判断题
2.操作系统的所有程序不都必须常驻内存。
（只有OS的部分内核程序才须要常驻内存。
11.不同的进程bu必然对应不同的程序X
进程是程序的一次执行，不同的进程可以包含同一个程序，同一个程序在执行中也可以产生多个进程
12.并发不是并行的不同表述，其原理不相同。（ ）
16.（考研真题）进程的3种基本状态：就绪、运行和阻塞，任意两种状态之间不都可以相互转换。（）进程从阻塞状态不能转换为运行状态，阻塞态当等待的事件发生时，会转为就绪态。
18.当条件满足时，进程不可以由阻塞态直接转换为运行态。
21.作业一旦被作业调度选中，系统就给它分配CPU。（X）
【解析】作业被作业调度程序选中，说明作业进入内存并创建了进程。但属于该作业的进程可能处于运行、就绪或等待状态，只有处于运行状态的进程才能占有处理机CPU
31.临界区是指进程中用于实现进程互斥的那段代码。（X）
【解析】临界区是指访问临界资源的那段代码，不是实现进程互斥的那段代码。
36.记录型信号量在使用过程中不存在“忙等”现象。
【解析】整型信号量存在“忙等”现象，为了解决这个问题，
提出了记录型信号量，记录信号量中不存在“忙等”现象。
40.页是信息的物理单位，段是信息的逻辑单位。
分页存储管理方式，能消减内存的外零头，提高内存的利用率
43.（考研真题）在现代操作系统的支持下，允许程序装入一部分即可运行
【解析】部分程序装入即可运行，是实现虚拟存储器的前提
54.（考研真题）通道所执行的通道程序存放在主机的内存中。（ ）
【解析】通道没有自己的内存，通道所执行的通道程序放在主机的内存中，即通道与CPU共享内存。
60. SPOOLing技术不可以提高慢速外设的速度。（X ）让系统内不能多道并行的独占变成共享
【解析】SPOOLing技术不能提高设备速度，只能通过暂时接收慢速外设的数据到输入/输出井，当设备空闲时再进行传输，缓解低速设备和高速设备速度不匹配矛盾。
66.（考研真题）多级文件目录可以提高文件的查询速度。（ ）
67.树状目录结构清晰，有利于文件的共享和保护。（ X ）
【解析】树状目录结构不支持文件共享，有向无环图目录结构支持文件共享
69.（考研真题）利用符号链可以实现文件共享。
【解析】文件共享常用两种方式：一种是基于索引结点的共享方式，称为硬链接；另一种基于符号链实现文件共享，称为软链接，也称为符号链接。
1.1.4 简答题
1.批处理操作系统、分时操作系统和实时操作系统各有什么特点？
1.（1）批处理OS的用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行，交互能力差。
（2）分时OS可让多个用户同时使用计算机，人机交互性较强，具有每个用户独立使用计算机的独占性，系统响应及时。
（3）实时OS能对控制对象做出及时反应，可靠性高，响应及时，但资源利用率低。
2.简述操作系统内核及其功能。
内核是OS最核心的部分，它是一组程序模块，作为安全软件来提供支持进程并发执行的基本功能和基本操作。内核程序通常驻留在内核空间且运行于内核态，具有访问硬件设备和所有内存空间的权限，是仅有的能够执行特权指令的程序。
内核的主要功能如下：
（1）资源抽象。用软件抽象硬件资源，简化对其所执行的操作，犀蔽低层的物理细节，如提供设备驱动程序、创建虚拟设备等；
（2）资源分配。把所抽象的各种资源分配给多个应用程序使用，并负责回收资源；
（3）资源共享。根据资源的类型和特性，提供不同的机制以确保进程获得所需资源，允许进程共享资源并提供资源的互斥与同步机制。
6.什么是多道程序设计技术？多道程序设计的优点是什么？为什么说直到出现中断和通道技术后，多道程序概念才变为有用的?
现代计算机系统一般都采用基于多道程序设计的技术。通常多道程序设计是指在主存中同时存放多道用户作业,使它们都处于执行的开始点和结束点之间。
多道程序设计的特点如下：
（1）多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一；
（3）宏观上并行。从宏观上看,它们在同时执行；
（4）微观上串行。从微观上看,它们在交替、穿插地执行。
因为中断是激活操作系统的手段，只有通过中断技术才能使CPU从一个作业的处理转到另一个作业的处理，而通道使主机与外设可以并行工作，所以直到出现中断和通道技术后，多道程序概念才变为有用。
7.分时系统和实时系统有什么区别？设计适用于实时环境的操作系统的主要困难是什么？
实时系统与分时系统的主要区别如下。
（1）系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统，而实时系统则大多数都是具有某种特殊用途的专用系统。
（2）响应时间的长短不同。分时系统的响应时间通常为秒级，而实时系统的响应时间通常为毫秒级甚至微秒级。
（3）交互性的强弱不同。分时系统的交互性强,而实时系统的交互性弱。
设计适用于实时环境的操作系统的主要困难有：①需要高精度的实时时钟管理；②需要高可靠性和安全性做保证；③需要连续的人机对话功能及快速的中断响应、中断处理能力；④过载的防护等问题。
9.（考研真题）画出进程三种状态——运行、就绪和阻塞之间的状态转换图，并写出转换原因。
。 
11.（考研真题）从操作系统设计角度，谈谈PCB的作用。
PCB是OS为每个进程定义的数据结构，能使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。OS通过PCB感知进程的存在，并根据PCB实施对进程的控制和管理，因此PCB是为了保证程序并发执行而创建的。\
12.在一个单CPU的多道程序设计系统中，若在某一时刻有N个进程同时存在，那么处于运行态、阻塞态和就绪态进程个数的最小值和最大值分别可能是多少？
【参考答案】各状态最值如表所示。
| 最小值 |
最大值 |
|
| 运行态 |
0 |
1 |
| 阻塞态 |
0 |
N |
| 就绪态 |
0 |
N-1 |
只要有一个就绪态，CPU就不会空闲，就会有运行态进程，因此，就绪态最大值为N-1
15.（考研真题）请简要阐明时间片轮转调度算法的基本思想。请分析：（1）假设时间片的长度无限长，这时的时间片轮转调度算法具有什么样的特点？（2）假设时间片的长度无限缩短，这时的时间片轮转调度算法又具有什么样的特点？
（1）如果时间片的长度无限长，即所有的算法在分配的时间片内都能完成，这时的时间片轮转调度算法会简化成先来先服务算法，对于短作业可能不利。
（2）假设时间片的长度无限缩短，这时的时间片轮转调度算法中，进程切换和进程调度会频繁发生，导致系统开销增大。
16.（考研真题）死锁预防中采用什么方法来破坏“循环等待”条件？并证明该方法。
在死锁预防中，采用“有序资源分配法”来破坏“循环等待”条件。有序资源分法是将系统中的所有资源按照类型进行排序编号，每个进程必须按照编号递增次序请求资源，同类资源一次性申请完。
证明：如果某进程请求资源Ri（i为编号），则其后面的进程只能请求排在资源Ri后面的资源，无法请求排在Ri前面的资源。对申请资源做这样的限制后，系统中不会出现资源请求环路现象，因此破坏了死锁产生必要条件中的“环路等待”条件。
17.进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？
（1）若干同学去图书馆借书；
（2）两队举行篮球比赛；
（3）流水线生产的各道工序；
（4）商品生产和社会消费。
进程之间存在着直接制约和间接制约这两种制约关系，其中直接制约（同步）是由于进程间的相互合作而引起的；而间接制约（互斥）则是由于进程间共享临界资源而引起的。
（1）若干同学去图书馆借书是间接制约，其中书是临界资源。
（2）两队举行篮球比赛是间接制约，其中篮球是临界资源。
（3）流水线生产的各道工序是直接制约，各道工序间须要相互合作，每道工序的开始都依赖于前一道工序的完成。
（4）商品生产和社会消费是直接制约，两者须要相互合作。商品生产出来后才可以被消费，商品被消费后才须要再生产。
19.什么是临界资源？什么是临界区？
在计算机中有许多资源一次只能允许一个进程使用，我们把一次仅允许一个进程使用的资源称为临界资源，如打印机和一些共享变量等。
进程中访问临界资源的那段代码称为临界区。
23.什么叫重定位？采用内存分区管理时，如何实现程序运行时的动态重定位？
所谓地址重定位，就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程，即将地址空间给出的逻辑地址映射到内存的物理地址上。地址重定位有静态重定位和动态重定位两种方式。
采用内存分区管理时，在硬件上设置一个“重定位寄存器”可以实现程序运行时的动态重定位。这种情况下地址重定位是在程序执行期间由地址变换机构动态实现的，主要的计算依据是：物理地址=逻辑地址+重定位寄存器的内容。
27.什么是虚拟存储器，主要特征是什么？
所谓虚拟存储器,就是指具有请求调入功能与置换功能,把内存与外存结合起来使用,能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量与内存大小无直接关系,主要由内存容量与外存容量之与所决定,其运行速度接近于内存速度,而成本却又接近于外存。
虚拟存储器的特征可以概括为以下4点:
(1)离散性:装入虚拟存储器的进程都就是离散存放的,这就是虚拟存储器的基础。
(2)多次性:一个作业被分成多次调入内存运行,即在作业运行时没必要将其全部装入,只需将当前要运行的那部分程序与数据装入内存,以后每当运行到尚未调入的那部分程序时,再将它调入。
(3)对换性:允许在作业的运行过程中进行换进、换出。在进程运行期间,允许将那些暂不使用的程序与数据,从内存调至外存的对换区(换出),待以后需要时再将它们从外存调至内存(换进)。
(4)虚拟性:指能够从逻辑上扩充内存容量,虚拟出一个较大的逻辑空间,使用户所瞧到的内存容量远大于实际内存容量。
3.（考研真题）画出下面4条语句所对应的前驱图。
P1：a=x+2y； P2：b=a+6； P3：c=4a-9； P4：d=2b+5c
【参考答案】P2和P3都必须在a被赋值之后才能执行；但P2、P3可以并发执行，因此它们彼此互不依赖；P4必须在b和c被赋值后才能执行。因此前趋图如图所示。
5.（考研真题）5个进程P1、P2、P3、P4、P5几乎同时到达，预期运行时间分别为10、6、2、4、8个时间单位。各进程的优先级分别为3、5、2、1、4（数值越大，优先级越高）。请按下列调度算法计算任务的平均周转时间（进程切换开销可忽略不计）。
（1）先来先服务（按P1、P2、P3、P4、P5顺序）算法。
（2）时间片轮转算法，假定时间片大小为2个时间单位。
（3）优先权调度算法。
5. 【参考答案】根据算法思想，确定调度先后顺序。
（1）FCFS调度顺序如图所示。
（2）时间片轮转调度顺序如图所示。
（3）优先权调度算法的调度顺序如图所示。
于是，可以得到如表所示的结果。
| 算法 |
时间类型 |
P1 |
P2 |
P3 |
P4 |
P5 |
平均 |
| 运行时间 |
10 |
6 |
2 |
4 |
8 |
||
| FCFS |
周转时间 |
10 |
16 |
18 |
22 |
30 |
19.2 |
| 带权周转时间 |
1 |
2.67 |
9 |
5.5 |
3.75 |
4.384 |
|
| RR |
周转时间 |
30 |
22 |
6 |
16 |
28 |
20.4 |
| 带权周转时间 |
3 |
3.67 |
3 |
4 |
3.5 |
3.434 |
|
| 优先权 |
周转时间 |
24 |
6 |
26 |
30 |
14 |
20 |
| 带权周转时间 |
2.4 |
1 |
13 |
7.5 |
1.75 |
5.13 |
7.单道批处理系统中有4个作业，其有关情况如下表所示。在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。
| 作业 |
提交时间/h |
运行时间/h |
| J1 |
8.0 |
2 |
| J2 |
8.6 |
0.6 |
| J3 |
8.8 |
0.2 |
| J4 |
9.0 |
0.5 |
【参考答案】在8.0只有作业J1到达，系统先将作业J1投入运行。作业J1运行2个小时后完成。这时3个作业都已到达，要计算3个作业的响应比，然后使响应比最高的投入运行。3个作业的响应比为：
作业J2的响应比=1+(10.0-86)/0.6=3.33
作业J3的响应比=1+(10.0-8.8)/0.2=7
作业J4的响应比=1+(10.0-9.0)/0.5=3
从计算的结果来看，作业J3的响应比最高，所以让作业J3先执行。作业J3执行0.2小时后完成。此时作业J2和作业J4的响应比为：
作业J2的响应比=1+(10.2-8.6)/0.6=3.67
作业J4的响应比=1+(10.2-9.0)/0.5=3.4
从计算的结果来看，作业J2的响应比最高，所以再让作业J2执行。
可见，4个作业的执行次序为：作业J1，作业J3，作业J2，作业J4。
计算结果如下表：
| 作业号 |
到达时间 |
运行时间 |
开始时间 |
完成时间 |
周转时间 |
带权周转时间 |
| 1 |
8.0 |
2.0 |
8.0 |
10.0 |
2.0 |
1.0 |
| 2 |
8.6 |
0.6 |
10.2 |
10.8 |
2.2 |
3．67 |
| 3 |
8.8 |
0.2 |
10.0 |
10.2 |
1.4 |
7 |
| 4 |
9.0 |
0.5 |
10.8 |
11.3 |
2.3 |
4.6 |
平均周转时间为T=(2.0+2.2+1.4+2.3)/4=1.975
平均带权周转时间为W=(1.0+3.67+7+4.6)/4=3.98
9.（考研真题）假定系统中有5个进程P0、P1、P2、P3、P4和4种资源A、B、C、D，若出现如表所示资源分配情况。
| 进程 |
已分配到资源 |
尚需资源需求 |
当前可用资源数 |
| P0 |
（1，1，1，0） |
（0，3，3，1） |
（0，3，2，2） |
| P1 |
（0，2，3，1） |
（0，3，4，2） |
|
| P2 |
（0，2，1，2） |
（1，0，3，4） |
|
| P3 |
（0，3，1，0） |
（0，3，2，0） |
|
| P4 |
（1，0，2，1） |
（0，4，2，3） |
问：（1）该状态是否安全？为什么？
（2）如果进程P0提出资源请求（0，0，0，1），系统能否将资源分配给它？为什么？
9. 【参考答案】严格按照银行家算法及安全检查子算法进行。
（1）初始状态如表所示。
| 进程 |
Work |
Need |
Allocation |
Work + Allocation |
Finish |
| P3 |
0，3，2，2 |
0，3，2，0 |
0，3，1，0 |
0，6，3，2 |
True |
| P0 |
0，6，3，2 |
0，3，3，1 |
1，1，1，0 |
1，7，4，2 |
True |
| P1 |
1，7，4，2 |
0，3，4，2 |
0，2，3，1 |
1，9，7，3 |
True |
| P4 |
1，9，7，3 |
0，4，2，3 |
1，0，2，1 |
2，9，9，4 |
True |
| P2 |
2，9，9，4 |
1，0，3，4 |
0，2，1，2 |
2，11，10，6 |
True |
存在一个安全序列P3，P0，P1，P4，P2，所以，该状态是安全的。
（2）Request0(0，0，0，1)<Need0(0，3，3，1)
Request0(0，0，0，1)<Available(0，3，2，2)
故尝试将资源分配给P0，修改P0对应资源，P0对应的Need（0，3，3，0），Allocation（1，1，1，1），系统的Available为（0，3，2，1）。进程资源分配情况如表所示。
| 进程 |
Work |
Need |
Allocation |
Work + Allocation |
Finish |
| P3 |
0，3，2，1 |
0，3，2，0 |
0，3，1，0 |
0，6，3，1 |
True |
| P0 |
0，6，3，1 |
0，3，3，0 |
1，1，1，1 |
1，7，4，2 |
True |
| P1 |
1，7，4，2 |
0，3，4，2 |
0，2，3，1 |
1，9，7，3 |
True |
| P4 |
1，9，7，3 |
0，4，2，3 |
1，0，2，1 |
2，9，9，4 |
True |
| P2 |
2，9，9，4 |
1，0，3，4 |
0，2，1，2 |
2，11，10，6 |
True |
存在一个安全序列P3、P0、P1、P4、P2，该状态是安全的，所以，可以实施分配。
15.在一个分页存储管理系统中，页面大小为4KB，系统中的地址占24位，给定页面变换表如下表所示。
（1）计算逻辑地址（页号为3，页内地址为100）的物理地址。
（2）说明地址变换过程。
| 页号P |
块号B |
| 0 |
3 |
| 1 |
4 |
| 2 |
9 |
| 3 |
7 |
15.【参考答案】（1）逻辑地址（页号3，页内地址100）的物理地址为：
7×4KB+100=28KB+100=28772
（2）在请求分页存储管理中，系统是通过页表进行地址转换。先将逻辑地址分解成页号P和页内地址W两部分，然后查页表，可得页号P对应的物理块号为B，从而变换出对应的物理地址为：物理地址=块号×页面大小+页内地址
17.设作业的虚拟地址为24位，其中高8位为段号，低16位为段内相对地址。试问：
（1）一个作业最多可以有多少段？
（3）每段的最大长度为多少字节？
（3）某段式存储管理采用如下段表,试计算[0,430]、[1,50]、[2,30]、[3,70]的主存地址。其中方括号内的前一元素为段号，后一元素为段内地址。当无法进行地址变换时，应说明产生何种中断。
| 段号 |
段长 |
主存起始地址 |
是否在主存 |
| 0 |
600 |
2100 |
是 |
| 1 |
40 |
2800 |
是 |
| 2 |
100 |
否 |
|
| 3 |
80 |
4000 |
是 |
17. 【参考答案】（1）一个作业最多可以有28=256个段。
（2）每段的最大长度为216=64KB=65536字节。
（3）逻辑地址（0，430）的主存地址为2100+430=2530；
逻辑地址（1，50）无法进行地址变换，因为产生了越界中断；
逻辑地址（2，30）无法进行地址变换，因为产生了缺段中断；
逻辑地址（3，70）的主存地址为4000+70=4070。
19.对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5。当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）
【参考答案】（1）FIFO 淘汰算法：内存块为3 时，缺页中断（或称缺页次数、页面故障）为9；内存块为4 时，缺页中断为10。（Bleady现象）
（2）LRU淘汰算法：内存块为3时，缺页中断为10；内存块为4 时，缺页中断为8。
25.已知某程序访问以下页面：0，1，4，2，0，2，6，5，1，2，3，2，1，2，6，2，1，3，6，2。如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。
（1）FIFO替换算法（2）LRU替换算法
25. 【参考答案】（1）FIFO 算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：
缺页率13/20=65%
（2）LRU 算法是最近最久未使用的页面予以淘汰。算法如图所示：
缺页率14/20=70%
32.（考研真题）磁盘请求服务队列中要访问的磁道分别为38、6、37、100、14、124、65、67，磁头上次访问了20磁道，当前处于30磁道上，试按先来先服务、最短寻道时间优先和扫描算法，分别计算磁头移动的磁道数。
参考答案】该题分步解答如下。
（1）先来先服务算法。磁盘磁头移动顺序为30、38、6、37、100、14、124、65、67。磁头移动磁道数为8+32+31+63+86+10+59+2=391。
（2）LRU算法。磁盘磁头移动顺序为30、37、38、14、6、65、67、100、124。移动磁道数为7+1+24+8+59+2+33+24=158。
（3）扫描算法。磁盘磁头移动顺序为30、37、38、65、67、100、124、14、6。磁头移动道数为7+1+27+2+33+24+110+8=212。
33.（考研真题）对于移动头磁盘，假设磁头现在位于25号磁道上（并向磁道号变小的方向移动），且基于磁道号的磁盘访问请求序列（按提出时间的先后次序排列）为39、62、18、28、100、130、90。 试采用最短寻道时间优先调度算法和电梯调度算法，分别给出相关磁盘访问请求处理的先后次序，并计算相应的平均寻道时间。
【参考答案】依据SSTF算法，磁盘访问请求处理的先后次序为25、28、18、39、62、90、100、130。平均寻道时间为(3+10+21+23+28+10+30)/7=125/7=17.86。
根据SCAN算法的思想，磁盘访问请求处理的先后次序为25、18、28、39、62、90、100、130。平均寻道时间为(7+10+11+23+28+10+300)/7=119/7=17。
