操作系统 作业题
内存管理习题
⼀、 选择题
1、设备分配问题中，算法实现时，同样要考虑安全性问题，防⽌在多个进程进⾏设备请求时，因相互等待对⽅释放所占设备所造成的（ D）现象。
A．瓶颈 B．碎⽚ C．系统抖动 D．死锁
//概念题
2、主存与辅存间频繁的页⾯置换现象被称为（C ）。
A．请求调页 B．碎⽚整理 C．系统抖动 D．输⼊输出
//概念题
3、在可变分区存储管理中，最差适应分配算法要求对空闲区表项按（C ）进⾏排列。
A．地址从⼤到⼩ B．地址从⼩到⼤ C．尺⼨从⼤到⼩ D．尺⼨从⼩到⼤
//概念题
4、段页式存储管理汲取了页式管理和段式管理的长处，其实现原理结合了页式和段式管
理的基本思想，即（B）。
A、⽤分段⽅法来分配和管理物理存储空间，⽤分页⽅法来管理⽤户地址空间。
B、⽤分段⽅法来分配和管理⽤户地址空间，⽤分页⽅法来管理物理存储空间。
C、⽤分段⽅法来分配和管理主存空间，⽤分页⽅法来管理辅存空间。
D、⽤分段⽅法来分配和管理辅存空间，⽤分页⽅法来管理主存空间。
//概念题：先分段再分页
5、下列措施中，能加快虚实地址转换的是：（C）
I. 增⼤快表（TLB） II. 让页表常驻内存 III. 增加交换区
A. 仅 I B. 仅 II C. 仅 I,II D. 仅 II,III
6、在页式存储管理系统中，采⽤某些页⾯置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加⽽增加。下列算法中，可能出现Belady异常现象的是：
I. LRU 算法 II. FIFO 算法 III. OPT 算法
A. 仅 II B.仅 I,II C. 仅 I,III D. 仅 II,III2
7、下列选项中，属于多级页表优点的是：
A.加快地址变换速度
B.减少缺页中断次数
C. 减少⼀个页表项所占字节数
D.减少页表所占的内存空间
8、下列关于虚拟存储器的叙述中，正确的是
A. 虚拟存储器只能基于连续分配技术 B. 虚拟存储器只能基于⾮连续分配技术
C. 虚拟存储器只受外存容量的限制 D. 虚拟存储器只受内存容量的限制
9、在⼀个请求分页系统中，采⽤ LRU 页⾯转换算法时，加⼊⼀个作业的页⾯⾛向为：
1，3，2，1，1，3，5，1，3，2，1，5.当分配给该作业的物理块数分别为 3 和 4 时，在
访问过程中所发⽣的缺页率为
A. 25%，33% B. 50%，25% C.50%,33% D. 50%，75%
10、 设有 8 页的逻辑空间，每页有 1024B,它们被映射到 32 块的物理存储区中。那么，
逻辑地址的有效位是_______位，物理地址⾄少是________位。
A. 10、11
B. 12、14
C. 13、15
D. 14、16
11、 某作业的逻辑地址空间为4页，页⾯⼤⼩为2048，已知页表如下所⽰，则逻辑地址
4865（⼗进制）对应的物理地址为（ ）。
A、4865 B、8961 C、13057 D、6865
12、 若⽤户进程访问内存时产⽣缺页，则下列选项中，操作系统可能执⾏的操作是
I.处理越界错
II.置换页
III.分配内存
A.仅I、II B.仅II、III C. 仅I、III D. I、II和III
13、 可以被多个进程在任意时刻共享的代码必须是________。
A. 顺序代码 B. 机器语⾔代码 C.不能⾃⾝修改的代码 D. ⽆转移指令代码
14、 假设变址寄存器 R 的内容为 1000H，指令中的形式地址为 2000 H；地址 1000H 中
的内容为 2000H，地址 2000H 中的内容为 3000H，地址 3000 H 中的内容为 4000H，则变3
址寻址⽅式下访问到的操作数是：
A. 1000H B. 2000H C. 3000H D. 4000 H
15、 有⼀个整数矩阵为 100 ⾏*200 列，即 a[100][200]。在⼀个虚拟系统中，采⽤ LRU 算
法，系统分给该进程 5 个页⾯来存储数据（不包含程序），设每页可存放 200 个整数，该
程序要对整个数组初始化，数组存储时是按⾏存放的。试计算下列两个程序各⾃的缺页
次数（假定所有页都以请求⽅式调⼊）。
A. 100,200 B. 100,20000 C. 200,100 D. 20000,100
16、 考虑页⾯置换算法，系统有 m 个物理块供调度，初始时全空，页⾯引⽤串长度为
p，包含了 n 个不同的页号，⽆论⽤什么算法，缺页次数不会少于（ ）
A、m B、p C、n D、min(m,n)
17、 总体上说，“按需调页”（Demand-Paging）是个很好的虚拟内存管理策略。但是，
有些程序设计技术并不适合于这适种环境。例如（ ）
A、堆栈 B、线性搜索 C、⽮量运算 D、⼆分法搜索
18、 把进程地址空间中使⽤的逻辑地址变成内存中物理地址的过程称为：
A、重定位 B、物理化 C、逻辑化 D、加载
19、 在可变分区存储管理中，最佳适应分配算法要求对空闲区表项按（ ）进⾏排列。
A、地址从⼤到⼩ B、地址从⼩到⼤ C、尺⼨从⼤到⼩ D、尺⼨从⼩到⼤
20、 主存与辅存间频繁的页⾯置换现象被称为（ ）。
A、请求调页 B、碎⽚整理 C、系统抖动 D、输⼊输出
21、 某作业的逻辑地址空间为 4 页，页⾯⼤⼩为 2048，已知页表如下所⽰，则逻辑地址4865（⼗进制）对应的物理地址为（ ）。
A、4865 B、8961 C、13057 D、6865
⼆、 计算题（选择）
某操作系统中，进程的逻辑地址空间和系统的物理地址空间均为 64KB，按字节编址。某进程最多需要 8 页（Page）数据存储空间，页的⼤⼩为 2KB，操作系统采⽤固定分配局部置换策略为此进程分配 6 个页框（Page Frame），采⽤⽼化算法（aging）进⾏页⾯置换，每个页⾯使⽤ 8bits 记录使⽤情况。在每个 clock tick结束时，6 个页⾯的 R 位如下所⽰：
页表存放在主存中，对主存的⼀次存取需要100ns，对TLB表的查找时间为10ns，处理
⼀次缺页中断需要10^8 ns（10的8次⽅ns，含更新TLB和慢表的时间）。
22、 如果现在程序执⾏时遇到逻辑地址1AC5H，这次访问耗费时间为______。
A. 108 +220ns B. 100ns C. 110ns D. 210ns
23、 然后，程序执⾏时遇到逻辑地址32C5H，这次访问耗费时间为______。5
A. 108 +220ns B. 100ns C. 110ns D. 210ns
24、 32C5H对应的物理地址为______。
A. 7AC5H B. 22C5H C. 3AC5H D. F2C5H
有⼀个整数矩阵为 100 ⾏*100 列，即 a[100][100]。系统分给该进程 5 个页⾯来存储此矩阵，设每页可存放 100 个整数，该程序要对整个数组初始化，数组存储时是按⾏存放的。页⾯采⽤ LRU 页⾯置换算法和局部置换策略。试计算下列两个程序各⾃的缺页次数（假定所有页都以请求⽅式调⼊）。
25、 程序⼀执⾏时产⽣的缺页中断次数为________。
A. 20 B. 100 C. 2000 D. 10000
26、 程序⼆执⾏时产⽣的缺页中断次数为________。
A. 20 B. 100 C. 2000 D. 10000
某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页⾯⼤⼩为 4KB，页表项⼤⼩为 4 字节。请回答下列问题。
27、 若使⽤⼀级页表的分页存储管理⽅式，逻辑地址结构为：
此时页表最⼤占⽤空间为_______。
A. 4KB
B. 1MB
C. 4MB
D. 32MB
28、 若使⽤⼆级页表的分页存储管理⽅式，逻辑地址结构为：
若该进程共⽤到了10000个页，则此时此⼆级页表占⽤的总空间最⼩为_______。
A. 4KB
B. 11KB
C. 44KB
D. 11MB
某操作系统的内存管理器采⽤请求式分页，页⾯⼤⼩为 1KB，逻辑地址空间为 32 位，物理地址空间⼤⼩为 4 GB，按字节编址。页表采⽤多级页表，⼀个页表项⼤⼩为 4B。TLB（快表）采⽤全相联映射，有 4 个页表项，内容如下表所⽰。
29、 该系统的页表项中，最多可以保存_______位标志位。
A．8 B．10 C．12 D．16
30、 若采⽤多级页表，要求每级页表均可以装⼊⼀个页⾯内，则应该采⽤______级页
表较合适。
A．0 B．1 C．2 D．3
31、 对逻辑地址3FFF1880H转换为物理地址的结果是______。
A. 0C153080H B. 0F035880H C. TLB 缺失 D.缺页
某请求页式存储管理，允许⽤户空间为 32 个页⾯（每页 2KB），主存为 16KB，如有⼀
个⽤户程序有 10 页长，且某时刻该⽤户进程的页表如下表所⽰
32、 如果程序执⾏时遇到逻辑地址1AC5H，则它对应的物理地址为______。
A. 7AC5H B. 4AC5H C. 3AC5H D. 缺页
33、 页表存放在主存中，对主存的⼀次存取需要100ns，对TLB表的查找时间为10ns，
这次访问耗费时间为______。
A. 10ns B. 100ns C. 110ns D. 210ns
34、 如果不考虑缺页的情况，对于已经载⼊内存的页⾯，快表命中率为80%，则访问
内存中数据的平均有效访问时间是______。7
A．120ns B．130ns C．170ns D．190ns
某操作系统的内存管理器采⽤请求式分页，页⾯⼤⼩为 4KB，逻辑地址空间为 32 位，
物理地址空间为 36 位，⼀个页表项⼤⼩为 4B。⼀次快表（TLB）的访问时间是 10ns，⼀次
内存的访问时间是 100ns，处理⼀次缺页的平均时间 10^8 ns（已含更新 TLB 和页表的时
间）。进程的驻留集⼤⼩固定为 2,采⽤最近未使⽤置换算法(NRU)和局部淘汰策略。假设（1）
TLB 初始为空;（2）地址转换时先访问 TLB,若 TLB 未命中,再访问页表(忽略访问页表之后
的 TLB 更新时间);（3）有效位为 0 表⽰页⾯不在内存,产⽣缺页中断,缺页中断处理后,返回
到产⽣缺页中断的指令处重新执⾏。进程的部分页表如下所⽰：
35、 该系统的页表项中，最多可以保存_______位标志位。
A．4 B．8 C．12 D．16
36、 若采⽤多级页表，要求每级页表均可以装⼊⼀个页⾯内，则应该采⽤______级页
表较合适。
A．0 B．1 C．2 D．3
37、 如果不考虑缺页的情况，对于已经载⼊内存的页⾯，快表命中率为90%，则访问
内存中数据的平均有效访问时间是______。
A．20ns B．110ns C．120ns D．320ns
38、 ⾸先，访问逻辑地址00001618H，则读⼊所需数据需要的总时间是______。
A．约 10^8ns B．110ns C．200ns D．210ns
39、 然后，访问逻辑地址00000FA6H，则读⼊所需数据需要的总时间是______。
A．约 10^8ns B．110ns C．200ns D．210ns
40、 最后，访问逻辑地址0000126CH，则读⼊所需数据需要的总时间是______。
A．约 10^8ns B．110ns C．200ns D．210ns
41、 在依次访问完上述三个逻辑地址后，页框101254H对应的页号为______。
A．00000H B．00001H C．00002H D．00003H
某基于动态分区存储管理的计算机,其主存容量为 55MB(初始为空闲) ,分配和释放的顺8
序为:分配 15MB,分配 30MB,释放 15MB,分配 8MB,分配 6MB。
42、 若采⽤最佳适配(Best Fit)算法，此时主存中最⼤空闲分区的⼤⼩是______。
A.7MB B.9MB C.10MB D.15MB
43、 若采⽤最差适配(Worst Fit)算法，此时主存中最⼤空闲分区的⼤⼩是______。
A.7MB B.9MB C.10MB D.15MB
三、 计算题（填空）
1、在逻辑地址转换为物理地址时，采⽤页式存储管理，两级页表，页⾯⼤⼩为 4 KB，页表
项⼤⼩为 4 字节。逻辑地址的结构为：
若该进程共⽤到了 3072 个页，则此时此⼆级页表占⽤的总空间最⼩为___(1)____。
TLB（快表）采⽤全相联映射，有 4 个页表项，内容如下表所⽰。
则逻辑地址 03FFF180H 对应的物理地址是____(2)_____，逻辑地址 02FF3036H 对应的物理
地址是____(3)_____。（如⽆对应的物理地址，则填写原因，可能为“TLB 缺失”或“缺页”）
2、某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项⼤⼩为 4 字节。请
回答下列问题。
（1）若使⽤⼀级页表的分页存储管理⽅式，逻辑地址结构为：
则页的⼤⼩是__(1)_。页表最⼤占⽤空间为(2)__。
（2）若使⽤⼆级页表的分页存储管理⽅式，逻辑地址结构为：
设逻辑地址为LA，则其对应的页⽬录号的表达式___(3)和页表索引的表达式(4)___。
若该进程共⽤到了3072个页，则此时此⼆级页表占⽤的总空间最⼩为___(5)____。
（3）采⽤（1）中的分页存储管理⽅式，⼀个代码段起始逻辑地址为 0000 8000H，其长度为8 KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所⽰（地址⼤⼩⾃下向上递增）。则该代码段对应的两个页表项，物理地址 1 是___(6)，物理地址 2 是(7)_；这两个页表项中的页框号 1 是(8)，页框号 2 是(9)；以及代码页⾯ 2 的起始物理地址 3 是(10)___。
四、计算题（简答）
- 请求分页管理系统中，假设某进程的页表内容如下表所⽰:
页⾯⼤⼩为 4KB，⼀次内存的访问时间是 100ns，⼀次快表(TLB)的访问时间是 10ns，处理
⼀次缺页的平均时间 108 ns(已含更新 TLB 和页表的时间)，进程的驻留集⼤⼩固定为 2，
采⽤最近最少使⽤置换算法(LRU)和局部淘汰策略。假设 (1) TLB 初始为空; (2) 地址转换时
先访问 TLB，若 TLB 未命中，再访问页表(忽略访问页表之后的 TLB 更新时间); (3) 有效
位为 0 表⽰页⾯不在内存，产⽣缺页中断，缺页中断处理后，返回到产⽣缺页中断的指令
处重新执⾏。设有虚地址访问序列 2362H、1565H、25A5H，请问:
\1) 依次访问上述三个虚地址，各需多少时间?给出计算过程。
\2) 基于上述访问序列，虚地址 1565H 的物理地址是多少?请说明理由。
\2. 某系统的页⾯淘汰算法采⽤⽼化(Aging)算法，每个页⾯分配⼀个8位⼆进制数的计数器。
某进程共有 6 个页⾯，在时刻 0 之前所有页⾯均未被引⽤过。下表是前 5 个 clock tick 中10
各页⾯的被引⽤情况，被引⽤者标 1，未被引⽤者标 0。
1） 在 clock tick 4 过后，需要淘汰⼀个页⾯，应选择哪个页⾯进⾏淘汰？为什么？
2） 为什么说⽼化(Aging)算法是⼀种简单有效的算法，但只是 LRU 的⼀个近似实现？
\3. 设某计算机的逻辑地址空间和物理地址空间均为 64KB,按字节编址。若某进程最多需要
6 页(Page)数据存储空间,页的⼤⼩为 1KB,操作系统采⽤固定分配局部置换策略为此进
程分配 4 个页框(Page Frame)。在时刻 260 前的该进程访问情况如下表所⽰(访问位即
使⽤位)。
当该进程执⾏到时刻 260 时,要访问逻辑地址为 17CAH 的数据。请回答下列问题:
(1) 该逻辑地址对应的页号是多少?
(2) 若采⽤最近最少使⽤(LRU)置换算法,该逻辑地址对应的物理地址是多少?要求给出计
算过程。
\4. 已知某系统页⾯长 4KB，页表项 4B，虚拟地址空间为 64 位，物理地址空间 4GB。
（1）如采⽤多层分页策略，限定各分层页表最多占 1 页⼤⼩，请问可以采⽤⼏层分页
策略？
（2）如采⽤倒排页表⽅式，请问倒排页表的⼤⼩？是每个进程⼀张倒排页表还是系统
维护⼀张倒排页表？如何解决倒排页表不便于逻辑地址向物理地址转换的问题？11
五、 简答题
1、 在虚拟存储管理中，分段式内存管理⽅式解决了分页式内存管理中的什么问题，又
带来了什么问题呢？
2、 Intel IA32体系结构中的保护模式是将逻辑地址转成线性地址再转成物理地址，这
种内存管理⽅式是段页式内存管理⽅式吗，为什么？
3、 LRU页⾯置换算法是⼀种⽐较优秀的算法但是较难实现，为什么？试给出⼀种可⾏
的近似算法作为LRU的取代⽅案。
4、 单纯的分段式和分页式内存管理各有什么缺点？为什么段页式可以避免这些缺点？
为什么段页式内存管理没有被⼴泛采⽤呢？
5、 为什么内存管理⽅式中，可变分区管理中有最差适应（worst fit)分配算法，⽽固定
分区管理中没有这个算法？分区管理中的交换技术（swap）和段式管理中的请求式
分段技术有什么区别？请求式分段与覆盖技术（overlay）又有什么区别？
6、 页⾯置换（淘汰）的时机是什么？哪种算法最理想同时也不可能实现？为什么说
LRU算法很有效但是很难实现？什么是Belady异常？哪种算法存在Belady异常现
象？
7、 请讨论⼀下页⾯置换算法中⼯作集（Working Set）置换算法的⼯作原理。
8、 在内存管理的⽅法中，分段式管理⽐分页式管理有什么优势？段页式与其他⽅式相
⽐有什么好处？
9、 为了同时抢占⾼端和中低端市场，CPU ⼚商常常在同⼀⽣产线上⽣产主频和制作⼯
艺相同的⾼端和低端 CPU，如 Intel 曾经同时⽣产相同主频和制作⼯艺的“奔腾 4”和
“赛扬”，价格上相差很⼤，据称主要区别在⼆级缓存的⼤⼩。请问缓存（Cache）有
什么⽤，什么地⽅会⽤到它？12
10、 为什么要使⽤倒排页表？倒排页表⾯临的最⼤的问题是什么？如何解决？
11、 内存分区管理中的交换技术与请求式分段技术相⽐，有什么相同点和不同点？
12、 在页⾯淘汰算法中，为什么说⽼化(Aging)算法只是 LRU 的⼀个近似实现？
进程管理习题！
一、 单项选择题
1、设与某资源关联的记录型信号量初值为 1,当前值为 -3。则当前因等待使用该资源而处于阻塞态的进程个数为______。
A.1 B.0 C.3 D.4
2、当一个进程处于（ ）状态时，称其为等待（或阻塞）状态。
A. 它正等待中央处理机 B. 它正等待合作进程的一个消息
C. 它正等待分给它一个时间片 D. 它正等待进入内存
3、下面关于线程的叙述中，正确的是（ ）。
A.不论是系统支持线程还是用户级线程，其切换都需要内核的支持。
B.线程是资源的分配单位，进程是调度和分配的单位。
C.不管系统中是否有线程，进程都是拥有资源的独立单位。
D.在引入线程的系统中，进程仍是资源分配和调度分派的基本单位。
4、资源的按序分配策略可以破坏______条件。
A. 互斥使用资源 B. 占有且等待资源 C. 非抢夺资源 D. 循环等待资源
5、下列选项中，会导致用户进程从用户态切换到内核态的操作是
I.整数除以零 II. sin()函数调用 III. read系统调用
A.仅I、II B.仅I、III C.仅II、III D. I、II和III
6、下列关于银行家算法的叙述中，正确的是
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时，系统中一定无死锁进程
C. 当系统处于不安全状态时，系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件2
7、有 5 个批处理任务 A、B、C、D、E 几乎同时到达一个计算中心。它们预计运行的时间分别是 10min、6min、2min、4min 和 8min。其优先级（由外部设定）分别为 3、5、2、1 和
4，这里 5 为最高优先级。下列各种调度算法中，其平均进程周转时间为 14min 的是
A. 时间片轮转调度算法 B. 优先级调度算法
C. 先来先服务调度算法 D. 最短作业优先算法
8、可以被多个进程在任意时刻共享的代码必须是________。
A. 顺序代码 B. 机器语言代码 C.不能自身修改的代码 D. 无转移指令代码
9、设m为同类资源数，n为系统中并发线程数。当n个进程共享m个互斥资源时，每个进程的最大需求是w；则下列情况会出现系统死锁的是：
A. m=2,n=1,w=2 B. m=2,n=2,w=1 C. m=4,n=3,w=2 D. m=4,n=2,w=3
10、 下列调度算法中，不可能导致饥饿现象的是：
A.时间片轮转 B.静态优先级调度
C.非抢占式作业优先 D.抢占式短作业优先
11、 某系统有n台互斥使用的同类设备，3个并发进程，最多分别需要3,4,5台设备，可确保系统不会发生死锁的设备数n最少为：
A. 9 B. 10 C. 11 D. 12
12、 下列指令中，不能在用户态执行的是：
A.trap 指令 B.跳转指令 C. 压栈指令 D.关中断指令
13、 一个进程调用了阻塞式系统调用read()进行读磁盘操作，操作完成后，操作系统针对该进程必须做的是：
A.修改进程状态为就绪态 B.降低进程优先级
C.进程分配用户内存空间 D.增加进程的时间片大小
设系统中有三种类型的资源（A、B、C），它们的资源数量分别是 17、5、20，五个进程（P1，
P2，P3，P4，P5）。在 T0 时刻系统状态如下表所示，系统采用银行家算法实施死锁避免策略。
14、 在T0时刻若进程P2请求资源（0,3,4），是否能实施分配？为什么？
A. 不可以，因为无足够资源完成分配。
B. 不可以，因为分配后进入不安全状态。
C. 可以，分配后存在安全序列 P4->P2->P5->P3->P1。
D. 可以，分配后存在安全序列 P2->P5->P4->P1->P3。
假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：
15、 如果应用最短作业优先的作业调度算法，则作业的平均周转时间为______分钟。
A. 50.3 B. 77.4 C. 37.2 D. 43.4
16、 某系统正在执行三个进程 P1、P2 和 P3，各进程的计算（CPU）时间和 I/O 时间比
例如下表所示。
为提高系统资源利用率，合理的进程优先级设置应为
A. P1>P2>P3 B. P3>P2>P1 C. P2>P1=P3 D. P1>P2=P3
17、 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调4用不需要保存的是
A. 程序计数器 B. 程序状态字寄存器C. 通用数据寄存器 D. 通用地址寄存器
18、 有 5 个批处理任务 A、B、C、D、E 几乎同时到达一个计算中心。它们预计运行的时间分别是 10min、6min、2min、4min 和 8min。其优先级（由外部设定）分别为 3、5、2、1 和 4，这里 5 为最高优先级。下列各种调度算法中，其平均进程周转时间为 14min 的
是
A. 时间片轮转调度算法 B. 优先级调度算法
C. 先来先服务调度算法 D. 最短作业优先算法
19、
一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5 ms到达。它们的计算和I/O操作顺序如下：
P1：计算 60 ms，I/O 80 ms，计算 20 ms
P2：计算 120 ms，I/O 40 ms，计算 40 ms
若不考虑调度和切换时间，则完成两个作业需要的时间最少是
A. 240 ms B. 260 ms C. 340 ms D. 360ms
20、 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中错误的是
A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
21、 下列关于进程和线程的叙述中，正确的是
A. 不管系统是否支持线程，进程都是资源分配的基本单位
B. 线程是资源分配的基本单位，进程是调度的基本单位
C. 系统级线程和用户级线程的切换都需要内核的支持
D. 同一进程中的各个线程拥有各自不同的地址空间
22、 下列关于银行家算法的叙述中，正确的是
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时，系统中一定无死锁进程5
C. 当系统处于不安全状态时，系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
23、 若一个用户过程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过
程的叙述中，正确的是
Ⅰ. 若该文件的数据不在内存，则该进程进入睡眠等待状态
Ⅱ. 请求 read 系统调用会导致 CPU 从用户态切换到核心态
Ⅲ. read 系统调用的参数应包含文件的名称
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
24、 假设5个进程P0、P1、P2、P3、P4的共享3类资源R1、R2、R3，这些资源总数分别
为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是
A. P0，P2，P4，P1，P3
B. P1，P0，P3，P4，P2
C. P2，P1，P0，P3，P4
D. P3，P4，P2，P1，P0
25、 设有3个进程共享一个互斥段，如果最多允许有2个进程同时进入互斥段，则所采用的信号量的初值应是（ ）：
A．2 B．3 C．1 D．0
26、 两个进程合作完成一个任务。在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的（ ）。
A．同步 B．互斥 C．调度 D．执行
27、 设备分配问题中，算法实现时，同样要考虑安全性问题，防止在多个进程进行设备请求时，因相互等待对方释放所占设备所造成的（ ）现象。6
A．瓶颈 B．碎片 C．系统抖动 D．死锁
28、 下列进程状态的转换中，哪一个是不正确的（ ）。
A．就绪->运行 B．运行->就绪 C．就绪->阻塞 D．阻塞->就绪
29、 在多进程的系统中，为了保证公共变量的完整性，各进程应互斥进入临界区。所
谓临界区是指______。
A．一个缓冲区 B．一段数据区 C．同步机制 D．一段程序
假设系统中有 4 个进程和 4 个可分配资源，当前分配和最大需求如下表所示，已知资源的最大拥有量为 E=（12，9，5，4）。系统采用银行家算法实施死锁避免策略。
30、 在当前时刻若进程2请求资源（0,1,0,0），是否能实施分配？若能，给出安全序列。
A．不能分配，因为分配后不存在安全序列。
B．不能分配，因为资源不足。
C．能分配，分配后存在安全序列 3->4->2->1
D．能分配，分配后存在安全序列 3->4->1->2
有 6 个 CPU 密集型批处理作业 A、B、C、D、E 和 F，几乎同时被提交。预计运行时间分别为 12，6，2，4，8 和 2 分钟。对于下列每种调度算法，忽略进程切换的开销，计算其平均进程周转时间。
31、 设进程A-F的优先级分别为4，6，3，2，5和1，其中1为最高优先级。则采用优先级调度算法，平均进程周转时间为______。
A. 16.33分钟 B.14.33分钟 C. 14分钟 D. 23.33分钟
32、 采用先来先服务调度算法，按照A、B、C、D、E和F的顺序运行。则平均进程周转时间为______。
A. 16.33分钟 B.14.33分钟 C. 14分钟 D. 23.33分钟7
33、 采用最短作业优先调度算法，平均进程周转时间为______。
A. 16.33分钟 B.14.33分钟 C. 14分钟 D. 23.33分钟
34、 某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是______。
A. 15ms B. 17ms C. 22ms D.27ms
35、 系统中有3个不同的临界资源R1、R2和R3，被4个进程P1、P2、P3和P4共享。各进程对资源的需求为：P1申请R1和R2，P2申请R2和R3，P3申请R1和R3，P4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是______。
A. 1 B. 2 C. 3 D.4
36、 进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示：
下列选项中，需要互斥执行的操作是______。
A. a=1 与 a=2 B. a=x 和 b=x C. x+=1 与 x+=2 D. x+=1 与 x+=3
假设系统中有 4 个进程和 1 个可分配资源，当前分配和最大需求如下表所示，已知资源的总量为 100。系统采用银行家算法实施死锁避免策略。
37、 在当前时刻若进程2请求该资源数量为10，是否能实施分配？若能，给出安全序列。
A．不能分配，因为分配后不存在安全序列。
B．不能分配，因为资源不足。
C．能分配，分配后存在安全序列 3->4->2->1
D．能分配，分配后存在安全序列 3->4->1->2
二、 简答题
1、你需要在一个很古老的 UNIX 上编写支持多线程的程序，它的内核不支持线程，内核代码也未公开，所以很难改造内核。请问如何解决这个问题？
2、在 UNIX 中父进程通过 fork()产生与自己一模一样的子进程，请问执行什么系统调用后，子进程才拥有自己独立的新代码段。这个系统调用的返回值是如何规定的？
3、当检测到死锁发生时，如果必须杀死一个进程以解除死锁，请问以什么标准来选择被杀死的进程比较合理？
4、在一单道批处理系统中，一组作业的提交时刻和运行时间如下表所示。试计算一下三种作业调度算法的平均周转时间 T 和平均带权周转时间 W。 (1) 先来先服务; (2) 短作业优先 (3) 高响应比优先。作业提交时刻和运行时间如下表
5、设系统中有 3 种类型的资源(A，B，C)和 5 个进程(P1，P2，P3，P4，P5)，A 资源的数量为 17，B 资源的数量为 5，C 资源的数量为 20。在 T0 时刻系统状态表如下表所示。
系统采用银行家算法试试死锁避免策略。
(1) T0 时刻是否为安全状态?若是，请给出安全序列。
(2) 在 T0 时刻若进程 P2 请求资源(0,3,4)，是否能实施资源分配?为什么?
(3) 在(2)的基础上，若进程 P4 请求资源(2,0,1)，是否能实施资源分配?为什么?
(4) 在(3)的基础上，若进程 P1 请求资源(0,2,0)，是否能实施资源分配?为什么?
6、某系统有 R1,R2,R3 共 3 类资源，在 T0 时刻 P1,P2,P3 和 P4 这 4 个进程对资源的占用和 需求情况见下表，此刻系统可用资源向量为(2,1,2）
问题:
(1)将系统中各种资源总量和此刻各进程对各资源的需求数目用向量或矩阵表示出来
(2)如果此时 P1,P2 均发出资源请求向量 Request(1,0,1),为了保持系统的安全性应该如 何分配资源?说明你所采用策略的原因。
(3)如果(2)中两个请求立刻得到满足后，系统此刻是否处于死锁状态?
7、设有 3 个进程 P、Q、R，它们共享 10 个同类资源，P、Q、R 进程的资源最大需求量依次为 4、7 和 8。现假定它们对资源的请示序列如下表所示:
为了避免死锁，系统分配资源时采用银行家算法。如果申请资源得不到满足，进程就转入阻塞态。根据上述信息，试描述各步骤结束时，申请资源的进程是得到满足，还是转入阻塞状 态，为什么?(起始状态:各进程均不拥有资源，无进程处于阻塞态)
8、分时操作系统中进程调度算法中对普通进程常常采用的是优先级轮转法，请问如何保证不会有进程因为优先级太低而饥饿？
9、死锁是一种对操作系统正常运行危害很大的现象，但是大多数死锁的解决方法只停留在理论探讨中，无法应用于实际的操作系统系统。请列举中哪些方法是实际操作系统中采用的应对死锁的可行方法。如果操作系统发现死锁已经发生，应如何应对使造成的损失较小？
10、 假定下面的 C 语言程序在 UNIX 系统上运行，并且所有系统调用都能成功完成。其中“pthread_create(&t, NULL, bar, NULL);”的功能是创建一个新线程来执行函数bar，并返回线程对象标识 t。“pthread_join(t,NULL);”的功能是等待线程 t 结束。试问此程序在运行过程中会打印出多少个“hello”？需要说明分析过程。
文件管理习题
共三个习题：
进程管理、内存管理、文件管理
一、 单项选择题
1、下列选项中，用于提高RAID可靠性的措施有 B
I.磁盘镜像 II.条带化 III. 奇偶校验 IV.增加Cache机制
A.仅I、II B.仅I、IIIC.仅I、III和IV D.仅II、III和IV
//提高RAID可靠性措施：eg：RAID0磁盘镜像，RAID5奇偶校验
顺便学一下：（可用容量）
2、某磁盘的转速为10000转/分，平均寻道时间是6 ms，磁盘传输速率是20 MB/s，磁盘控制器延迟为0.2 ms，读取一个4 KB的扇区所需的平均时间约为 B
A. 9 ms B. 9.4 ms C. 12 ms D. 12.4 ms
// 平均时间为 9.4ms。
第一部分 找到磁道的时间 = 平均寻道时间= 6ms
第二部分 找到扇区的时间 = 磁盘转一圈的时间÷2（平均）=（60 秒）/（2*10000 转/分）=3ms
第三部分 磁盘控制器延迟时间 = 0.2ms
第四部分 数据传输时间 = 传输字节数 / 磁盘传输速度 = 4K / 20M = 0.2ms（1K≈10 的 3 次方）
综上 6ms+3ms+0.2ms+0.2ms=9.4ms。
3、用户在删除某文件的过程中，操作系统不可能执行的操作是 A
A.删除此文件所在的目录 B.删除与此文件关联的目录项
C.删除与此文件对应的文件控制块 D.释放与此文件关联的内存缓冲区
//删除此文件所在的目录（要是我删文件，连该文件目录也删了那太过分了吧啊喂！！！
4、为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是 A
A.连续结构 B.链式结构
C.直接索引结构 D.多级索引结构
//虽然是随机播放，但毕竟还是读取文件，播放性能好->内存离得近->连续结构
5、若某文件系统索引结点（inode）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是 A
A.索引结点的总数 B.间接地址索引的级数 C.地址项的个数 D.文件块大小
//与文件长度无关->索引结点的总数，怎么索引与文件无关
6、设某文件为索引顺序文件，由 5 个逻辑记录组成，每个逻辑记录的大小与磁盘块的大小相等，均为 512B，并依次存放在 50、121、75、80、63 号磁盘块上。若要存取文件的第 1569 逻辑字节处的信息，则要访问的磁盘块号是 C
A. 3 B. 75 C. 80 D. 63
//文件大小512B，第1569字节在第1569/512=3.06->第四页，顺序在题目上，为80
7、文件系统采用两级索引分配方式。如果每个磁盘块的大小为 1KB，每个盘块号占 4B，则该系统中单个文件的最大长度是 B
A. 32MB B. 64MB C. 128MB D. 256MB
**//单个文件最大长度：被两级索引：[(1KB/4B)^2]4B=64MB*
8、一个磁盘的转速为 7200 转/分，每个磁道有 160 个扇区，每个扇区为 512B，那么理想情况下，其数据传输率为 C
A. 576000KB/s B. 7200KB/s C. 9600KB/s D. 19200KB/s
//的转速为 7200r/min=120r/s，转一圈经过 160 个扇区，每个扇区有 512B 所以数据传输率为 120×160×512/1024=9600KB/s。
9、现有容量为10GB的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4KB。若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需要簇的个数为： A
A. 80 B. 320 C. 80K D. 320K
//10GB/4KB=2.5M，共有2.5M个可分配的簇， 2.5M/8=320KB，需要320K的字节来标记可分配的簇， 320KB/4KB=80个，这320KB同样是按4KB一簇在硬盘上存储，所以需要除4K，得80个簇
10、 某磁盘阵列中包含 15 块 SAS 硬盘，单一硬盘的容量为 1TB。采用 RAID技术提供具备高可靠性和高可用性的数据存储方案。使用 4 块硬盘组成一个RAID10 硬盘组，8 块硬盘组成一个 RAID 5 硬盘组，3 块硬盘作为热备份硬盘。此磁盘阵列的总可用空间约为 B
A. 8TB B. 9TB C. 10TB D.11TB
//1题要记得那个表的最后一行，一一对应，RAID10-一半，2TB；RAID5一个-8-1=7TB，3个热备份不算，共9TB
11、 设某文件为索引顺序文件，由 5 个逻辑记录组成，每个逻辑记录的大小与磁盘块的大小相等，均为 512B，并依次存放在 50、121、75、80、63 号磁盘块上。若要存取文件的第 1569 逻辑字节处的信息，则要访问的磁盘块号是 C
A. 3 B. 75 C. 80 D. 63
//怎么重复了
12、 若磁盘转速为7200转/分，平均寻道时间为8ms,每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是 B
A．8.1ms B．12.2ms C．16.3ms D．20.5ms
**//磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms，平均等待时间与磁盘转速有关，为[60s/7200]0.5 ≈4.165ms。磁盘的存取一个扇区的时间为60s/(7200 * 1000) ≈ 0.0083ms。因此总的时间为：8 4.165 0.0083 = 12.1733ms*
13、 在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（）
A．1，2 B．1，3 C．2，3 D．2，4
//直接索引指针所在位置大小 10*1KB ；一级 (1KB/4B) *1KB=256KB; 二级 [(1KB/4B)^2] *1KB
1234B->小于10KB，磁盘块1
307400B->大于10KB+256KB->磁盘块3
14、 假设磁头当前位于第 100 道,正在向磁道序号增加的方向移动。现有一3个磁道访问请求序列为 35,68,110,180,采用 SSTF （最近寻道优先）调度算法得到的磁道访问序列是 ______。D
A. 35,68,110,180 B. 110,180,35,68 C. 110,180,68,35 D. 110,68,35,180
//学会（看大题2，3题），学最近寻道优先，很简单
在某UNIX操作系统中，文件系统给文件分配外存空间采用的是混合索引分配方式。索引节点（inode）中包含13个直接块指针、1个一级间接块指针和1个二级间接块指针，间接块指向的是一个索引块，每个索引块和数据块的大小一致，均为1KB，地址指针所占空间为4B。
15、 若某inode共有2个硬链接（hard link），分别为a和b，另有1个符号链接（symbolic link）x->a，则该inode的link counter为______。 C
A．0 B．1 C．2 D．3
//不算符号链接，所以link counter 为 2
16、 将a删除后，访问x，结果为______。 A
A．提示文件不存在 B．打开文件b C．打开一个空文件 D．x已被删除
//提示文件不存在，实践经历（
17、 假设该索引节点已经被加载进内存中，则若要读取文件的第1MB的内容，需要访问磁盘___3____次。
A．1 B．2 C．3 D．4
//直接块指针13个：13KB
*一级1个，(1KB/4B)1KB=256KB
*二级1个，[(1KB/4B)^2]1KB=64MB
所以需要3次访问磁盘，需要访问二个索引块和一个数据块
18、 该文件系统能支持的文件最大容量约为_______B
A．64KB B．64MB C．4GB ．16GB
//根据上题，最大为64MB
19、 若将数据块的大小修改为4KB，则该文件系统能支持的文件最大容量约为________。 C
A．64KB B．64MB C．4GB ．16GB
**// [(4KB/4B)^2]4KB=4GB*
20、 若保持数据块大小1KB不变，在不增加inode中的指针个数的前提下，取
消一个直接块指针，增加一个三级间接块指针，则能支持的文件最大容量约
为________。 D
A．64KB B．64MB C．4GB D．16GB
**// [(1KB/4B)^3]1KB=16GB*
二、 计算问答题
1、某操作系统中，给文件分配外存空间采用的是混合索引分配方式。索引节点（inode）中包含 12 个直接块指针和 1 个一级间接块指针，间接块指向的是一个索引块，每个索引块和数据块的大小均为一个扇区，即 512B，地址指针所占空间为 4B。
1） 该文件系统能支持的文件最大容量是____(1)____。
2） 为了支持更大的文件，在不增加 inode 中的指针个数的前提下，取消一4个直接块指针，增加一个二级间接块指针，则能支持的文件最大容量是____(2)____。
3） 在上一问的基础上，若将数据块的大小修改为 1KB，则该文件系统能支持的文件最大容量是____(3)____。
4） 在上一问的基础上，假设该索引节点已经被加载进内存中，则若要读取文件的第 10MB 的内容，需要访问磁盘____(4)____次。
*答：（1）(12+(512/4))512B=71680B=70KB
*（2）(11+(512/4)+ (512/4)^2)512B=8459776B=8261.5KB=8.068MB
*（3）(11+(1024/4)+(1024/4)^2)1024B=65803KB=64.261MB
（4）3 次．由上一问知，10MB 需要通过二级间接索引访问，故需要访问二个索引块和一个数据块。
2、在 inode 的多级索引指针中，为什么保留了直接指向数据块的指针，而不是设计成只使用一个指向多级间接索引块的指针，就可以访问到所有的数据块？数据块的大小可以影响文件系统能支持的最大文件的大小，但是数据块的大小对文件系统的性能和空间利用率之间有什么关系？为什么？
答：直接指针访问速度快，适合小文件。
数据块增大，传输数据的单位容量增大，传输效率提升，性能上升。
数据块增大，则文件存储分配单位变大，内部剩余增加，空间利用率下降。
数据块减小则情况相反。
3、若干个等待访问磁盘者依次要访问的柱面为 20,44,40,4,80,12,76，假设每移动一个柱面需要 3ms 时间，移动臂当前位于 40 号柱面，磁头正向磁道号增加的方向移动，请按 FCFS, SSTF, SCAN 算法分别计算为完成上述访问总共花费的寻找时间。
FCFS：（|20-40| + |44-20| + |40-44| + |4-40| + |80-4| + |12-80| + |76-12|） 3 =*
**(20+24+4+36+76+68+64)3 = 876ms*
SSTF： 40 - 44 - 20 - 12 – 4 - 76 – 80
（4+24+8+8+72+4） 3 = 360 ms*
SCAN：40 – 44 – 76 – 80 – 20 – 12 - 4
（4+32+4+60+8+8） 3 = 348 ms*
4、假设计算机系统采用 CSCAN(循环扫描)磁盘调度策略,使用 2KB 的内存空间记录 16384 个磁盘块的空闲状态。
(1) 请说明在上述条件下如何进行磁盘块空闲状态的管理。
(2) 设某单面磁盘旋转速度为每分钟6000 转,每个磁道有100 个扇区,相邻磁道间的平均移动时间为1ms。若在某时刻,磁头位于100 号磁道处,并沿着磁道号增大的方向移动(如下图所示),磁道号请求队列为50,90,30,120,对请求队列中的每个磁道需读取1 个随机分布的扇区,则读完这4 个扇区点共需要多少时间?要求给出计算过程。
(3) 如果将磁盘替换为随机访问的Flash 半导体存储器(如U 盘、SSD 等),是否有比CSCAN 更高效的磁盘调度策略?若有,给出磁盘调度策略的名称并说明理由;若无,说明理由。
(1) 位图法
在CSCAN磁盘调度策略下，管理磁盘块的空闲状态可以采用位图的方式进行。位图是一种数据结构，用于表示磁盘块的分配状态，每个磁盘块用一个比特位来表示其状态（已分配或空闲）。
给定16384个磁盘块，每个块用一个比特位来表示其状态，所需的比特数可以通过以下方式计算：
16384个块 ÷ 8位/字节 = 2048字节 ÷ 1024字节/KB = 2KB
因此，需要2KB的内存空间来记录这些磁盘块的空闲状态。
管理这个位图时，通过初始化所有比特位为“0”来表示所有磁盘块都是空闲的状态。当磁盘块被分配时，相应的比特位被设置为“1”表示已被占用。当磁盘块被释放时，相应的比特位重新设置为“0”以表示它变为空闲状态。
CSCAN调度算法将磁盘的访问方向限制在一个特定的范围内移动，这使得磁盘空间的管理可以更加高效地实现。
(2) CSCAN：190.4 ms
寻道时间：|120-100| + |30-120| + |50-30| + |90-50| = 170ms
旋转时间：10ms/2*4 = 20ms
读数据：10ms/100 * 4 = 0.4ms
(3) FCFS
ps：
当参加天津大学智算学部“操作系统原理”课程期末考试时
1．SCAN 算法，磁臂从磁盘的一端向另一端移动，当磁头移过每一个
柱面时，处理位于该柱面上的请求服务。当到达另一端时，改变方向
继续处理。（每次都运动到顶端）
2．C-SCAN 算法，C-SCAN 也是将磁头从磁盘一端移到另一端，随着
移动不断的处理请求。但是，当磁头移到另一端时，会马上返回到磁
盘开始，返回时不处理请求.（每次都运动到顶端）
3．LOOK 算法：是改进的 SCAN 算法，处理过程与 SCAN 相似，只是
每次都不运动到顶端，在最大磁道号和最小磁道号之间移动。
4．C-LOOK 算法：是改进的 C-SCAN 算法，处理过程与 C-SCAN 相似，
只是每次都不运动到顶端，在最大磁道号和最小磁道号之间移动。
非期末考试时（如阅读其他教参时、做作业时等）
SCAN 算法＝LOOK 算法=上面第 3 条描述（两头不到顶）
C-SCAN 算法＝C-LOOK 算法=上面第 4 条描述（两头不到顶）
整理自：Wind_9233
