计算机操作系统期末练习整理，考试神器，期末包过，做完不过直接来打我——计算机操作系统习题

1. 文件系统采用多级目录结构后，对于不同用户的文件，其文件名（ ）

A. 应该相同 B. 应该不同 C. 可以相同，也可以不同 D. 受系统约束

正确答案：C

2. 虚拟存储器的大小（ ）。

A. 受到内存容量的限制 B. 受到作业的地址空间限制 C. 受到外存空间及 CPU 地址所能表示范围的限制 D. 受到程序大小的限制

正确答案：C

3. 当发生缺页中断时，（ ）。

A. 应淘汰一页 B. 应淘汰多页 C. 应装入一页 D. 将淘汰页写盘

正确答案：C

4. 程序访问内存时页不在页表中导致的中断属于（ ）

A. 硬件中断 B. 软件中断 C. 指令异常中断 D. 其他中断

正确答案：C

5. 多道程序设计是指（ ）

A. 在实时系统中并发运行多个程序 B. 在分布系统中同一时刻运行多个程序 C. 在一台处理机上同一时刻运行多个程序 D. 在一台处理机上并发运行多个程序

正确答案：D

6. LINUX 属于哪一类操作系统？（ ）

A. 单用户单任务 B. 单用户多任务 C. 单道批处理 D. 多用户

正确答案：D

7. 用户程序通过使用 int 指令将引起的中断是属于（ ）

A. 硬件中断 B. 软件中断 C. 指令异常中断 D. 其他中断

正确答案：B

8. 临界区是（ ）。

A. 一个进程 B. 一种资源 C. 一段代码 D. 存储区

正确答案：C

9. 把逻辑地址转变为内存的物理地址的过程称做（ ）。

A. 编译 B. 连接 C. 运行 D. 重定位

正确答案：D

10. 文件的二级目录结构由（ ）和用户文件目录组成。

A. 根目录 B. 子目录 C. 主文件目录 D. 用户文件目录

正确答案：C

11. 现代操作系统的两个基本特征是（ ）和资源共享。

A. 多道程序设计 B. 中断处理 C. 程序的并发执行 D. 实现分时与实时

正确答案：C

12. 已经获得除（ ）以外的所有运行所需资源的进程处于就绪状态。

A. CPU B. I/O 设备 C. 内存 D. 磁盘空间

正确答案：A

13. 根据死锁产生的四个必要条件，可采取几种措施预防死锁，采取资源的静态预分配策略，是破坏了哪一个条件?（ ）

A. 互斥条件 B. 占有并等待 C. 不可抢占 D. 循环等待

正确答案：B

14. 设基址寄存器的内容为 1000，偏移为 2000，物理地址是（ ）

A. 1000 B. 2000 C. 3000 D. 4000

正确答案：C

15. 内存碎片是指（ ）

A. 存储分配完后所剩的空闲区 B. 没有被使用的存储区 C. 不能被使用的存储区 D. 未被使用，而又暂时不能使用的存储区

正确答案：C

16. 页式虚拟存储管理的主要特点是（ ）。

A. 不要求将作业装入到主存的连续区域 B. 不要求进行缺页中断处理 C. 不要求将作业同时全部装入到主存的连续区域 D. 不要求进行页面置换

正确答案：C

17. 进程和程序的一个本质区别是（ ）。

A. 进程分时使用 CPU，程序独占 CPU B. 进程存储在内存，程序存储在外存 C. 进程在一个文件中，程序在多个文件中 D. 进程为动态的，程序为静态的

正确答案：D

18. 用信号量实现互斥，则信号量的初值应设置为（ ）

A. 0 B. 1 C. 2 D. 3

正确答案：B

19. 文件系统中文件的逻辑结构，索引文件结构中的索引表是用来（ ）

A. 指示逻辑记录逻辑地址的 B. 存放部分数据信息的 C. 存放查找关键字项内容的 D. 指示逻辑记录和物理块之间对应关系的

正确答案：D

20. 在文件系统中，要求物理块必须连续的物理文件是（ ）

A. 顺序文件 B. 链接文件 C. 索引文件 D. Hash 文件

正确答案：A

21. 文件系统采用多级目录结构后，对于不同用户的文件，其文件名（ ）

A. 应该相同 B. 应该不同 C. 可以相同，也可以不同 D. 受系统约束

正确答案：C

22. 虚拟存储器的大小（ ）。

A. 受到内存容量的限制 B. 受到作业的地址空间限制 C. 受到外存空间及 CPU 地址所能表示范围的限制 D. 受到程序大小的限制

正确答案：C

23. 当发生缺页中断时，（ ）。

A. 应淘汰一页 B. 应淘汰多页 C. 应装入一页 D. 将淘汰页写盘

正确答案：C

24. 程序访问内存时页不在页表中导致的中断属于（ ）

A. 硬件中断 B. 软件中断 C. 指令异常中断 D. 其他中断

正确答案：C

25. 多道程序设计是指（ ）

A. 在实时系统中并发运行多个程序 B. 在分布系统中同一时刻运行多个程序 C. 在一台处理机上同一时刻运行多个程序 D. 在一台处理机上并发运行多个程序

正确答案：D

26. LINUX 属于哪一类操作系统？（ ）

A. 单用户单任务 B. 单用户多任务 C. 单道批处理 D. 多用户

正确答案：D

27. 用户程序通过使用 int 指令将引起的中断是属于（ ）

A. 硬件中断 B. 软件中断 C. 指令异常中断 D. 其他中断

正确答案：B

28. 临界区是（ ）。

A. 一个进程 B. 一种资源 C. 一段代码 D. 存储区

正确答案：C

29. 把逻辑地址转变为内存的物理地址的过程称做（ ）。

A. 编译 B. 连接 C. 运行 D. 重定位

正确答案：D

30. 文件的二级目录结构由（ ）和用户文件目录组成。

A. 根目录 B. 子目录 C. 主文件目录 D. 用户文件目录

正确答案：C

31. 文件系统采用单级目录结构，对于不同用户的文件，其文件名（ ）

A. 应该相同 B. 应该不同 C. 可以相同，也可以不同 D. 受系统约束

正确答案：B

32. 下面关于安全状态和非安全状态说法正确的是（ ）

A. 安全状态是没有死锁的状态而非安全状态是有死锁的状态 B. 安全状态是可能有死锁的状态而非安全状态也可能有死锁状态 C. 安全状态是可能没有死锁的状态而非安装状态是有死锁的状态 D. 安全状态是没有死锁的状态而非安全状态是可能有死锁的状态

正确答案：D

33. 分页管理里一次有效内存数据访问，需要多次内存访问，为了提高数据访问速度，可采用的办法是（ ）。

A. 反向页表 B. 联想寄存器（TLB） C. 两级分页 D. 多级分页

正确答案：B

34. V 原语对信号量做运算后，（ ）

A. 当 S > 0 时要唤醒一个等待进程 B. 当 S < 0 时要唤醒一个就绪进程 C. 当 S ≤ 0 时要唤醒一个等待进程 D. 当 S = 0 时要唤醒一个就绪进程

正确答案：C

35. 索引文件结构中的索引表是用来（ ）

A. 指示逻辑记录逻辑地址的 B. 存放部分数据信息的 C. 存放查找关键字项内容的 D. 指示逻辑记录和物理块之间对应关系的

正确答案：D

36. 一个进程被唤醒意味着（ ）

A. 该进程重新占有 CPU B. 进程状态变为就绪 C. 它的优先权变为最大 D. 该进程会立即执行

正确答案：B

37. 用户单击鼠标产生的中断属于（ ）

A. 硬件中断 B. 软件中断 C. 指令异常中断 D. 其他中断

正确答案：A

38. 进程被中断可能导致哪种进程状态演变？（ ）

A. 就绪 → 运行 B. 退出 → 就绪 C. 阻塞 → 运行 D. 运行 → 阻塞

正确答案：D

39. 若处理器可进行 32 位相对地址寻址，则它的虚拟地址空间为（ ）字节。

A. 2GB B. 4GB C. 100KB D. 640KB

正确答案：B

40. Linux 属于下列哪一类操作系统？（ ）

A. 单用户单任务 B. 单用户多任务 C. 多用户 D. 批处理

正确答案：C

41. 与计算机硬件关系最密切的软件是（ ）

A. 编译程序 B. 数据库管理系统 C. 游戏程序 D. OS

正确答案：D

42. 当 CPU 执行操作系统代码时，称 CPU 处于（ ）。

A. 用户态 B. 休眠态 C. 管态 D. 就绪态

正确答案：C

43. 软件向 CPU 请求的中断是属于（ ）

A. 硬件中断 B. 软件中断 C. 指令异常中断 D. 其他中断

正确答案：B

44. 进程的控制信息和描述信息存放在（ ）。

A. JCB B. PCB C. AFT D. SFT

正确答案：B

45. （ ）调度算法可减少平均等待时间。

A. 先来先服务 B. 轮转 C. 短进程优先 D. 长进程优先

正确答案：C

46. 临界区是指（ ）。

A. 正在被占用的资源 B. 不可共享的资源 C. 一次只能被一个进程使用的代码 D. 可同时使用的资源

正确答案：C

47. 不使用共享资源是破坏了死锁必要条件中的（ ）？

A. 互斥 B. 请求与保持 C. 不剥夺 D. 循环等待

正确答案：A

48. 用磁带作为文件存贮介质时，文件只能组织成（ ）

A. 顺序文件 B. 链接文件 C. 索引文件 D. 目录文件

正确答案：A

49. 文件系统的多级目录结构是一种（ ）。

A. 线性结构 B. 树形结构 C. 散列结构 D. 双链表结构

正确答案：B

50. 在文件系统中，采用位示图主要是实现（ ）。

A. 磁盘的驱动调度 B. 页面置换 C. 文件目录的查找 D. 磁盘空间分配

正确答案：D

51. 通过破坏死锁必要条件之一来防止死锁产生，这种策略属于（ ）

A. 预防死锁 B. 避免死锁 C. 检测死锁 D. 解除死锁

正确答案：A

52. I/O 请求完成会导致哪种进程状态演变？（ ）

A. 就绪 → 执行 B. 阻塞 → 就绪 C. 阻塞 → 执行 D. 执行 → 阻塞

正确答案：B

53. UNIX 属于下列哪一类操作系统？（ ）

A. 单用户单任务 B. 单用户多任务 C. 多用户 D. 批处理

正确答案：C

54. 分页管理里一次有效内存数据访问，需要多次内存访问，为了提高数据访问速度，可采用的办法是（ ）。

A. 反向页表 B. 联想寄存器（TLB） C. 两级分页 D. 多级分页

正确答案：B

55. 操作系统是一种（ ）

A. 系统软件 B. 系统硬件 C. 应用软件 D. 支援软件

正确答案：A

56. 银行家算法用于（ ）。

A. 预防死锁 B. 解除死锁 C. 避免死锁 D. 检测死锁

正确答案：C

57. 文件系统采用二级目录结构的目的是（ ）。

A. 缩短访问文件存储器的时间 B. 实现文件共享 C. 节省主存空间 D. 解决不同用户之间的文件名的冲突问题

正确答案：D

58. 进程从运行状态进入就绪状态的原因可能是（ ）

A. 被选中占有 CPU B. 等待某一事件 C. 等待的事件已发生 D. 时间片用完

正确答案：D

59. 两个旅行社甲和乙为旅客到某航空公司订飞机票，形成互斥的资源是（ ）。

A. 飞机票 B. 旅行社 C. 航空公司 D. 旅行社和航空公司

正确答案：A

60. 以下哪种调度算法不可能是抢占式的？（ ）

A. 先来先服务 B. 最短 CPU 执行期优先 C. 最高优先权 D. 轮转法

正确答案：A

61. 通过破坏死锁必要条件之一来防止死锁产生，这种策略属于（ ）

A. 预防死锁 B. 避免死锁 C. 检测死锁 D. 解除死锁

正确答案：A

62. I/O 请求完成会导致哪种进程状态演变？（ ）

A. 就绪 → 执行 B. 阻塞 → 就绪 C. 阻塞 → 执行 D. 执行 → 阻塞

正确答案：B

63. UNIX 属于下列哪一类操作系统？（ ）

A. 单用户单任务 B. 单用户多任务 C. 多用户 D. 批处理

正确答案：C

64. 分页管理里一次有效内存数据访问，需要多次内存访问，为了提高数据访问速度，可采用的办法是（ ）。

A. 反向页表 B. 联想寄存器（TLB） C. 两级分页 D. 多级分页

正确答案：B

65. 操作系统是一种（ ）

A. 系统软件 B. 系统硬件 C. 应用软件 D. 支援软件

正确答案：A

66. 银行家算法用于（ ）。

A. 预防死锁 B. 解除死锁 C. 避免死锁 D. 检测死锁

正确答案：C

67. 文件系统采用二级目录结构的目的是（ ）。

A. 缩短访问文件存储器的时间 B. 实现文件共享 C. 节省主存空间 D. 解决不同用户之间的文件名的冲突问题

正确答案：D

68. 进程从运行状态进入就绪状态的原因可能是（ ）

A. 被选中占有 CPU B. 等待某一事件 C. 等待的事件已发生 D. 时间片用完

正确答案：D

69. 两个旅行社甲和乙为旅客到某航空公司订飞机票，形成互斥的资源是（ ）。

A. 飞机票 B. 旅行社 C. 航空公司 D. 旅行社和航空公司

正确答案：A

70. 以下哪种调度算法不可能是抢占式的？（ ）

A. 先来先服务 B. 最短 CPU 执行期优先 C. 最高优先权 D. 轮转法

正确答案：A

71. 用户在程序设计过程中，可通过（ ）获得操作系统的服务。

A. 库函数 B. 键盘命令 C. 系统调用 D. 内部命令

正确答案：C

72. 下列进程状态转换中，不可能发生的状态转换是（ ）。

A. 就绪 → 执行 B. 就绪 → 阻塞 C. 执行 → 阻塞 D. 阻塞 → 就绪

正确答案：B

73. 进程 A 和 B 共享同一临界资源，并且进程 A 正处于对应的临界区内执行。下列描述正确的是（ ）。

A. 进程 A 的执行不能被中断，即临界区的代码具有原子性。 B. 进程 A 的执行能被中断，但中断进程 A 后，不能将 CPU 分配给进程 B。 C. 进程 A 的执行能被中断，而且只要进程 B 就绪，就必定将 CPU 分配给进程 B。 D. 进程 A 的执行能被中断，而且只要进程 B 就绪，就可以将 CPU 分配给进程 B。

正确答案：D

74. 在分页存储管理系统中，若地址用 16 位表示，页的大小为 1K，则每个进程最多允许有（ ）页。

A. 1024 B. 16 C. 64 D. 32

正确答案：A

75. 某段表的内容如下：

逻辑地址为（2，154），它对应的物理地址为（ ）。 A. 120K + 2 B. 480K + 154 C. 30K + 154 D. 2 + 480K

正确答案：B

76. 在请求分页存储管理中，若采用 FIFO 页面淘汰算法，则当分配的页面数增加时，缺页中断的次数（ ）。

A. 减少 B. 增加 C. 无影响 D. 可能增加也可能减少

正确答案：D

77. 如果 I/O 设备与存储设备进行数据交换不经过 CPU 来完成，这种数据交换方式是（ ）。

A. DMA 方式 B. 中断方式 C. 轮询方式 D. 无条件存取方式

正确答案：A

78. 下列说法中正确的论述是（ ）。

A. 在现代计算机系统中，只有 I/O 设备才是有效的中断源。 B. 在中断处理过程中，必须屏蔽中断。 C. 同一用户所使用的 I/O 设备也可以并行工作。 D. SPOOLing 是脱机 I/O 系统。

正确答案：C

79. 文件系统采用两级索引分配方式，如果每个磁盘块的大小为 2KB，每个盘号占 4B，则在该系统中，文件的最大长度是（ ）。

A. 1GB B. 128MB C. 512MB D. 以上都不对

正确答案：C

80. 在以下的文件物理结构中，不利于经常改动用户文件的是（ ）。

A. 连续结构 B. 链接结构 C. 索引结构 D. 以上都不对

正确答案：A

81. CPU 处理数据的速度远高于外设的处理速度，为此可采用（ ）。

A. 并用技术 B. 缓冲技术 C. 通道技术 D. 中断技术

正确答案：B

82. 设有五个并发进程通过 PV 操作共享同一临界资源，若该临界资源的互斥信号量为 mutex，则 mutex 值域为（ ）。

A. [-5,0] B. [0,5] C. [-1,4] D. [-4,1]

正确答案：D

83. 从下面对临界区的论述中，描述正确的是（ ）。

A. 临界区是指进程中用于实现进程互斥的那段代码。 B. 临界区是指进程中用于实现进程通信的那段代码。 C. 临界区是指进程中用于访问共享资源的那段代码。 D. 临界区是指进程中用于访问临界资源的那段代码。

正确答案：D

84. 在分段存储管理系统中，若地址用32位表示，其中8位表示段号，则允许每段的最大长度是（ ）。

• A. 2^{16}
• B. 2^8
• C. 2^{24}
• D. 2^{32}
• 正确答案：C
• 解析：32位地址中，8位表示段号，剩下的24位用于段内地址，因此每段的最大长度是 242^{24}。

85. 在一个分页管理系统中，页表的内容如下：若页的大小为4K，则地址转换机构将逻辑地址0转换成的物理地址为（ ）。

• A. 8192
• B. 4096
• C. 2048
• D. 0
• 正确答案：A
• 解析：页大小为4K（2122^{12}），逻辑地址0对应第0页，起始物理地址为页表中第0页的物理地址8192。

86. 系统“抖动”现象的发生是由（ ）引起的。

• A. 置换算法选择不当
• B. 交换的信息量过大
• C. 内存容量不足
• D. 请求页式管理方案
• 正确答案：A
• 解析：“抖动”现象是由于页面频繁置换导致的，通常与置换算法选择不当相关。

87. 为了使多个进程能有效的同时处理输入和输出，最好使用（ ）结构的缓冲技术。

• A. 单缓冲区
• B. 环形缓冲区
• C. 缓冲池
• D. 双缓冲区
• 正确答案：C
• 解析：缓冲池可以存储多个输入输出数据，提高多个进程并发处理效率。

88. 下列关于Shell论述中，说法错误的是（ ）。

• A. Shell是一种编程语言，它提供了循环、选择等控制结构。
• B. Shell是一个命令解释器，它对用户输入的命令进行解释执行。
• C. Shell命令就是由Shell实现的命令，它们的代码包含在Shell内部。
• D. 在UNIX系统中，有多种不同的Shell供用户选择。
• 正确答案：C
• 解析：Shell命令并非都包含在Shell内部，许多是外部程序。

89. 在Windows、Linux和UNIX等操作系统中，都采用（ ）。

• A. 单级目录
• B. 多级树形目录
• C. 双级目录
• D. 以上都不是
• 正确答案：B
• 解析：现代操作系统采用多级树形目录结构组织文件系统。

90. UNIX对空闲盘块的管理采用的是（ ）。

• A. 位示图
• B. 空闲块链
• C. 空闲块表
• D. 成组链接法
• 正确答案：D
• 解析：UNIX系统常采用成组链接法管理空闲盘块。

91. 配置了操作系统的机器是一台比原来的物理机器功能更强的计算机。这样的计算机只是一台逻辑上的计算机，称为（ ）计算机。

• A. 并行
• B. 真实
• C. 虚拟
• D. 共享
• 正确答案：C
• 解析：操作系统使物理机变为更强大的虚拟计算机。

92. 设有三个并发进程通过PV操作共享同一临界资源，若该临界资源的互斥信号量为mutex，则mutex值域为（ ）。

• A. [-3, 0]
• B. [0, 3]
• C. [-1, 2]
• D. [-2, 1]
• 正确答案：D
• 解析：若共有3个进程共享资源，信号量的值域为 [−2,1]。

93. 下列进程状态转换中，不可能发生的状态转换是（ ）。

• A. 就绪 → 执行
• B. 阻塞 → 执行
• C. 执行 → 阻塞
• D. 阻塞 → 就绪
• 正确答案：B
• 解析：进程必须先从阻塞变为就绪，再由就绪变为执行。

95. CPU处理数据的速度远高于外设的处理速度，为此可采用（ ）。

• A. 并用技术
• B. 缓冲技术
• C. 通道技术
• D. 中断技术
• 正确答案：B
• 解析：缓冲技术通过临时存储，缓解CPU与外设速度差异。

96. 下列关于Shell论述中，说法错误的是（ ）。

• A. Shell是一种编程语言，它提供了循环、选择等控制结构。
• B. Shell是一个命令解释器，它对用户输入的命令进行解释执行。
• C. Shell命令就是由Shell实现的命令，它们的代码包含在Shell内部。
• D. 在UNIX系统中，有多种不同的Shell供用户选择。
• 正确答案：C
• 解析：Shell命令不一定包含在Shell内部，许多是外部程序。

97. 假如一个FCB为64B，盘块大小为1KB，则在每个盘块中只能存放（ ）个FCB。

• A. 64
• B. 1024
• C. 32
• D. 16
• 正确答案：D
• 解析：盘块大小为1KB（1024B），每个FCB为64B，因此可存放 1024/64=16 个FCB。

98. 三个进程共享四个同类资源，这些资源的分配与释放只能一次一个。已知每一个进程最多需要2个该类资源，则该系统（ ）。

• A. 有某进程可能永远得不到该类资源
• B. 必然死锁
• C. 进程请求该类资源立刻能得到
• D. 必然无死锁
• 正确答案：D
• 解析：按照银行家算法，系统中总资源数 ≥\geq 已分配资源 + 最多需求，故不会死锁。

99. UNIX对空闲盘块的管理采用的是（ ）。

• A. 位示图
• B. 空闲块链
• C. 空闲块表
• D. 成组链接法
• 正确答案：D
• 解析：UNIX文件系统中采用成组链接法进行空闲块管理。

100. 如果I/O设备与存储设备进行数据交换不经过CPU来完成，这种数据交换方式是（ ）。

• A. DMA方式
• B. 中断方式
• C. 轮询方式
• D. 无条件存取方式
• 正确答案：A
• 解析：DMA（Direct Memory Access）允许I/O设备与内存直接交换数据，绕过CPU。

需要继续整理其他选项，请告诉我！

判断

1. 一般来说，先进先出页面置换算法比最近最少使用页面置换算法有较少的缺页率。（✘）

• 正确答案：错误
• 解释：FIFO（先进先出）页面置换算法可能导致“Belady异常”，即页面数增加反而缺页率升高。而LRU（最近最少使用）算法通常比FIFO更能减少缺页率。

2. 进程调度算法各种各样，如果选择不当，有的进程可能不能获得执行的机会。（✔）

• 正确答案：正确
• 解释：某些调度算法（如简单的优先级调度）可能会导致低优先级进程长期得不到CPU时间，产生“饥饿”现象。

3. 虚拟存储器可以解决内存不足的问题。（✔）

• 正确答案：正确
• 解释：虚拟存储器通过将部分数据交换到硬盘上，可以扩展有效内存容量，从而解决内存不足的问题。

4. 在银行家算法中，对某时刻的资源分配情况进行安全分析，如果该时刻的状态是安全的，则存在一个安全序列，且这个安全序列是唯一的。（✘）

• 正确答案：错误
• 解释：在银行家算法中，一个安全状态可能对应多个安全序列，不一定是唯一的。

5. 采用链表结构的文件，存放文件的磁盘块必须是连续的。（✘）

• 正确答案：错误
• 解释：链表结构文件的磁盘块不需要连续，链表记录了每个块的指针。

6. 虚拟存储器中，必须允许页面能够被换入和换出。（✔）

• 正确答案：正确
• 解释：虚拟存储器的基本原理是页面置换，因此页面必须支持换入换出。

7. 批处理系统不允许用户随时干预自己程序的执行。（✔）

• 正确答案：正确
• 解释：批处理系统的特点是任务按批次执行，用户不能实时干预程序运行。

8. PV原语可以不是原子操作。（✘）

• 正确答案：错误
• 解释：PV操作必须是原子操作，否则会导致并发控制失效。

9. 目录是一种特殊的文件。（✔）

• 正确答案：正确
• 解释：目录是操作系统中特殊的文件，用于存储文件信息及其层级结构。

10. 文件的基本信息存放在FCB中。（✔）

• 正确答案：正确
• 解释：文件控制块（FCB）用于存储文件的基本信息，如文件名、大小、权限等。

11. 并发性是指若干事件在同一时刻发生。（✘）

• 正确答案：错误
• 解释：并发性是指若干事件在一段时间内交替执行，并不一定是在同一时刻发生。

12. 虚存容量的扩大是以牺牲CPU工作时间以及内存与外存交换时间为代价的。（✔）

• 正确答案：正确
• 解释：虚拟存储需要频繁的页面换入换出，这会消耗CPU和I/O时间。

13. 操作系统为每个自己的进程创建PCB，并控制进程的执行过程。（✔）

• 正确答案：正确
• 解释：PCB（进程控制块）记录了进程的状态，是操作系统管理进程的核心数据结构。

14. 树型目录结构能够解决文件重名问题。（✔）

• 正确答案：正确
• 解释：树型目录结构通过引入多级目录，允许不同目录下的文件重名。

15. 原语是一种不可分割的操作。（✔）

• 正确答案：正确
• 解释：原语是指在执行过程中不可被中断的操作。

16. 采用动态重定位技术的系统，目标程序可以不经任何改动，而装入物理内存。（✔）

• 正确答案：正确
• 解释：动态重定位由硬件地址映射实现，目标程序无需改动即可装入内存。

17. 页式的地址是一维的，段式的地址是二维的。（✔）

• 正确答案：正确
• 解释：页式地址是一维的逻辑地址；段式地址包括段号和段内偏移，体现了二维特性。

18. 位示图方法可用于磁盘的调度管理。（✘）

• 正确答案：错误
• 解释：位示图用于磁盘空间管理，而非磁盘调度管理。

19. 虚拟设备是指把一个物理设备变换成多个对应的逻辑设备，它通过逻辑设备表来实现的。（✔）

• 正确答案：正确
• 解释：虚拟设备通过逻辑设备表将一个物理设备虚拟化为多个逻辑设备。

20. 页式管理易于实现不同进程间的信息共享。（✔）

• 正确答案：正确
• 解释：页式管理通过共享页表项，可以实现不同进程的页面共享。

21. 操作系统中调度和资源分配以进程为单位而不是以程序为单位。（✔）

• 正确答案：正确
• 解释：进程是操作系统分配资源的基本单位，而非程序。

22. 实时操作系统中会出现某个进程的工作请求不能及时完成的情况。（✔）

• 正确答案：正确
• 解释：即使是实时操作系统，在资源紧张时也可能无法及时满足某些请求。

23. 多级反馈队列调度算法是一种动态优先权优先算法。（✔）

• 正确答案：正确
• 解释：多级反馈队列通过动态调整优先级实现对进程的调度。

24. 若系统中存在一个循环等待的进程集合，则必会死锁。（✘）

• 正确答案：错误
• 解释：循环等待是死锁的必要条件之一，但还需要其他条件同时满足才会导致死锁。

25. 信号量的数值往往用于代表某种资源的数量。（✔）

• 正确答案：正确
• 解释：信号量通常用来表示资源的可用数量，特别是在并发环境中。

26. 页表本身可能很大，因此可采用多级页表来实现。（✔）

• 正确答案：正确
• 解释：多级页表通过分级结构减少单级页表的存储需求。

27. 请求的页不在页表中不会导致缺页中断。（✘）

• 正确答案：错误
• 解释：如果请求的页不在页表中，会触发缺页中断。

28. 索引文件的索引表实际上就是一个定长记录的顺序文件。（✔）

• 正确答案：正确
• 解释：索引文件的索引表本质上是一个定长顺序文件，记录指向文件块的地址。

29. 目录结构中引入索引结点可提高文件检索速度。（✔）

• 正确答案：正确
• 解释：索引结点记录了文件的基本信息及物理位置，大大提高了检索效率。

30. 虚拟内存允许逻辑地址空间比物理地址空间大。（✔）

• 正确答案：正确
• 解释：虚拟内存通过页面置换机制实现逻辑地址空间大于物理地址空间。

填空

1. ___ 模块负责将对CPU的控制权转交给由CPU调度程序，包括：切换上下文、切换到用户态、跳转到用户程序的适当位置并重新运行之。

• 参考答案：进程调度

2. 文件分配磁盘块的方法有：连续分配、 ___ 、索引分配。

• 参考答案：链接分配

3. 程序必须放入一个进程，并且送入 ___ 才能被CPU执行。

• 参考答案：内存 | 主存 | 存储

4. 进程和程序的区别之一是进程是 ___ 的一个实例，是程序的一次执行。

• 参考答案：程序

5. 文件访问的用户类型有：拥有者、 ___ 和其他。

• 参考答案：组

6. 指令和数据绑定到内存地址可以在三个不同的阶段发生： ___ 时期、加载时期和执行时期。

• 参考答案：编译

7. 二进制信号量其变化范围仅限于0和 ___ 的信号量，也称为互斥信号量。

• 参考答案：1

8. 互斥是一次只有 ___ 个进程可以使用一个资源。

• 参考答案：一

9. 死锁的必要条件包括： ___ 、占有并等待、不可抢占、循环等待。

• 参考答案：互斥

10. 常用的页面置换算法有： ___ 、最优置换和最近最少使用。

• 参考答案：先进先出 | FIFO

11. 在执行中的程序被称为 ___ 。

• 参考答案：进程

12. ___ 进程间通信机制主要有：消息传递、管道和内存共享。

• 参考答案：消息传递 | 管道

13. ___ 计算机系统中，操作系统管理计算机硬件的程序，在计算机用户和计算机硬件之间充当中介。

• 参考答案：操作系统

14. 文件的访问方法有： ___ 访问、直接访问。

• 参考答案：顺序

15. 常见的内存管理方式有： ___ 式、分段式和段页结合式。

• 参考答案：分页

16. 计算机系统中， ___ 负责资源分配。

• 答案：操作系统

17. 操作系统的主要功能包括：进程管理、 ___ 管理、文件系统管理、安全和保护。

• 答案：内存

18. 一个进程的内存空间一般包括代码、 ___ 、数据和堆四部分。

• 答案：堆栈

19. 主要的CPU进程调度算法有先来先服务、 ___ 优先、优先级调度、时间片轮转。

• 答案：短作业

20. 写时复制 (COW) 允许父进程和 ___ 开始时共享同一页面。

• 答案：子进程

21. 现代操作系统的两个最基本的特征是 ___ 和 ___ 。

• 答案：并发，共享

22. 当前比较流行的微内核的操作系统结构，是建立在层次化结构的基础上，采用了 ___ 模式 ___ 技术。

• 答案：B/S模式，面向对象

23. 引入线程概念后，操作系统以 ___ 作为资源分配的基本单位，以 ___ 作为CPU调度和分派的基本单位。

• 答案：进程，线程

24. 在利用信号量进行进程互斥时，应将 ___ 置于 ___ 和 ___ 之间。

• 答案：临界区，P操作，V操作

25. 程序的链接方式有静态链接、 ___ 和 ___ 。

• 答案：装入时动态链接，运行时动态链接

26. 在首次适应算法中，空闲分区以 ___ 的次序拉链；在最佳适应算法中，空闲分区以 ___ 的次序拉链。

• 答案：空闲区起始地址递增，空闲区大小递增

27. 在请求调页系统中，反复进行页面换进和换出的现象称为 ___ 。

• 答案：抖动

28. 磁盘的访问时间由 ___ 、 ___ 和传输时间三部分组成。

• 答案：寻道，旋转延迟

29. ___ 是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏。

• 答案：文件保护

30. 在利用空闲链表来管理外存空间时，可以有两种方式：一种以 ___ 为单位拉成一条链；另一种以 ___ 为单位拉成一条链。

• 答案：空闲盘块，空闲盘区

31. MS-DOS中的COMMAND.COM或UNIX中的Shell通常被称为 ___ 。

• 参考答案：命令解释程序

32. 设计现代操作系统的主要目标是 ___ 和 ___ 。

• 参考答案：提高资源利用率，方便用户

33. 操作系统的基本类型有批处理、 ___ 和 ___ 。

• 参考答案：分时系统，实时系统

34. 当前正在执行的进程由于时间片用完而暂停运行，该进程应转变为 ___ 状态；若因发生某种事件而不能继续执行时，应转变为 ___ 状态。

• 参考答案：就绪，阻塞

35. 程序并发执行与顺序执行时相比产生了一些新特征，分别是 ___ 、 ___ 和 ___ 。

• 参考答案：间断性，失去封闭性，不可再现性

36. 地址变换机构的基本任务是将作业地址空间的 ___ 变换为内存空间中的 ___ 。

• 参考答案：逻辑地址，物理地址

37. 在段页式系统中，为获得一条指令或数据，需访问三次内存，第一次从内存中取得 ___ ；第二次从内存中取得 ___ ；第三次从内存中取得 ___ 。

• 参考答案：段基址，页号，指令或数据

38. 在磁盘调度中，选择优先为离当前磁头最近的磁道上的请求服务的算法为 ___ 算法；选择优先为当前磁头移动方向、离当前磁头最近的磁道上的请求服务的算法为 ___ 算法。

• 参考答案：最短寻道优先，扫描

39. 在成组链接法中，将每一组的 ___ 和该组的 ___ 记入前一组的最后一个盘块中。

• 参考答案：盘块数，所有盘块号

40. 文件在使用前必须执行 ___ 操作，其主要功能是把文件的 ___ 复制到内存中，并在用户和文件之间建立一个连接。

• 参考答案：打开，FCB | 索引结点

41. 实时系统可分为 ___ 和 ___ 两种类型，民航售票系统属于 ___ 。

• 参考答案：实时信息处理，实时控制，实时信息处理

42. 虚拟存储器最基本的特征是 ___ 、 ___ 和虚拟性。

• 参考答案：多次性，对换性

43. 设备控制器是 ___ 和 ___ 之间的接口，它接收来自 ___ 的I/O命令，并用于控制外设的工作。

• 参考答案：CPU，I/O设备，CPU

44. 现代操作系统的两个最基本的特征是并发和共享，除此之外，它还具有 ___ 和 ___ 的特征。

• 参考答案：虚拟，异步

45. 用户为阻止进程继续执行，应利用 ___ 原语，若进程正在执行，应转变为 ___ 状态；若用户要恢复其运行，应利用 ___ 原语，此时进程应转变为 ___ 状态。

• 参考答案：挂起，静止就绪，激活，活动就绪

46. 死锁产生的原因是 ___ 和 ___ 。

• 参考答案：竞争资源，进程推进顺序不当

47. 在分页系统中，页表的作用是实现 ___ 到 ___ 的转换。

• 参考答案：逻辑地址，物理地址

48. ___ 是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏； ___ 是指允许多个用户共同使用同一个文件。

• 参考答案：文件保护，文件共享

49. 操作系统的最基本的特征是 ___ 和 ___ ，最主要的任务是 ___ 。

• 参考答案：并发，共享，管理资源

50. 引入进程的主要目的是 ___ ，进程存在的唯一标志是 ___ 。

• 参考答案：使程序能并发执行，进程控制块

51. 设备驱动程序是 ___ 与 ___ 之间的通信程序。

• 参考答案：I/O系统高层，设备控制器

52. 在段页式系统中，为获得一条指令或数据，需访问三次内存，第一次从内存中取得 ___ ；第二次从内存中取得 ___ ；第三次从内存中取得 ___ 。

• 参考答案：段基址，页号，指令或数据

53. 在I/O控制方式中，中断驱动方式下CPU是以 ___ 为单位进行干预的，DMA方式下CPU是以 ___ 为单位进行干预的，通道方式下CPU是以 ___ 为单位进行干预的。

• 参考答案：字节，数据块，一组数据块

54. 在采用树形目录结构的文件系统中，树的结点分为三类：根结点表示根目录，枝结点表示 ___ ，叶结点表示 ___ 。

• 参考答案：子目录，文件

55. 可将顺序文件中的文件内容装入到 ___ 的多个盘块中，此时，文件目录项的地址部分给出的是文件的 ___ 。为了访问文件的所有内容，目录项中还必须有 ___ 信息。

• 参考答案：连续，起始地址，长度

56. 操作系统的基本类型有 ___ 、 ___ 和 ___ 。

• 参考答案：批处理系统，分时系统，实时系统

57. 用来实现互斥地进入自己的临界区，同步机制应该遵循 ___ 、 ___ 、 ___ 和 ___ 四条准则。

• 参考答案：空闲让进，忙则等待，有限等待，让权等待

58. 可以通过 ___ 和 ___ 两种方式来实现访问控制矩阵。

• 参考答案：访问控制表，访问权限表

59. OS提供给用户的接口主要有 ___ 、 ___ 和 ___ 。

• 参考答案：命令接口，程序接口，图形接口

60. 设备控制器是CPU和I/O外设之间的接口，它接收来自 ___ 的I/O命令，并用于控制外设的工作。

• 参考答案：CPU

61. 文件存储空间的分配可采用多种方式，其中， ___ 方式可使文件顺序访问的效率最高， ___ 方式则可解决存储空间中的碎片问题，但不支持对文件的随机访问；而UNIX采用的是 ___ 方式。

• 参考答案：连续分配，隐式链接，混合索引

62. 引入线程的目的是 ___ ，线程存在的唯一标志是 ___ 。

• 参考答案：减少时空开销，TCB

63. 当前正在执行的进程由于时间片用完而暂停运行，该进程应转变为 ___ 状态；若因发生某种事件而不能继续执行时，应转变为状态 ___ 。

• 参考答案：就绪，阻塞

64. 文件的逻辑结构按文件的组织方式分为顺序文件、 ___ 和 ___ 。

• 参考答案：索引文件，索引顺序文件

65. 从资源管理的角度看，操作系统具有四大功能： ___ 、 ___ 、 ___ 和 ___ 。

• 参考答案：处理机管理，存储器管理，设备管理，文件管理

66. 用户为阻止进程继续执行，应使用 ___ 原语；若用户要恢复其运行，应使用 ___ 原语。

• 参考答案：阻塞，唤醒

67. 在记录型信号量机制中，每次执行P操作意味着 ___ ，因此应将S.value ___ ，如果S.value<0时，进程应 ___ 。

• 参考答案：申请一个临界资源，减1，阻塞

68. 在设备管理中，DMA控制方式允许 ___ 和 ___ 直接交换数据。

• 参考答案：I/O设备，内存

问答题

1. 描述分段内存管理机制。

• 参考答案： 逻辑地址是两个向量的集合：<segment-number, offset>。 段表用于映射二维物理地址。每个段表项包括：
  1. 基址：指向内存中段的起始物理地址。
  2. 限长：指定段的长度。

2. 解释文件分配磁盘块链接分配方法的优点和缺点。

• 参考答案： 优点：
  1. 提高了磁盘空间利用率，无需为每个文件预留固定大小的物理块。
  2. 支持文件的动态扩充。
  3. 便于文件的插入和删除操作。

  缺点：

  1. 存取速度较慢，不适合随机访问。
  2. 当物理块间的连接指针损坏时，可能会导致数据丢失。

3. 进程的状态有哪些？

• 参考答案：
  1. 新建：进程正在被创建中。
  2. 运行：进程的指令正在执行。
  3. 等待：进程在等待某些事件的发生。
  4. 就绪：进程已准备好执行，等待分配CPU。
  5. 终止：进程的执行已完成。

4. 一个进程的空间包括哪些部分？

• 参考答案：
  1. 代码部分（文本部分）：存储程序的指令。
  2. 堆：动态分配的内存区域。
  3. 堆栈：用于存储函数调用相关信息。
  4. 数据部分：存储程序的全局变量和已初始化数据。

5. 进程和程序的区别？

• 参考答案：
  1. 进程是程序的一个实例，是程序的一次执行。
  2. 进程是动态的，而程序是静态的。
  3. 程序是进程的代码部分。
  4. 进程存在于内存中，程序存在于外存中。

6. CPU调度可能发生在当一个进程：

• 参考答案：
  1. 从运行状态转到等待状态。
  2. 从运行状态转到就绪状态。
  3. 从等待状态转到就绪状态。
  4. 进程终止。
  • 第1和第4种情况发生的调度称为非抢占式调度（nonpreemptive）。
  • 其他情况下发生的调度称为抢占式调度（preemptive）。

7. 哪些条件同时出现，死锁将会发生？

• 参考答案：
  1. 互斥：一次只能有一个进程使用资源。
  2. 占有并等待：进程持有一个资源，同时等待其他资源。
  3. 不可抢占：资源只能由持有它的进程主动释放。
  4. 循环等待：等待资源的进程之间形成一个闭环，例如 P0→P1→...→Pn→P0P_0 \rightarrow P_1 \rightarrow ... \rightarrow P_n \rightarrow P_0。

8. 常见的调度方法有哪些？列出5种。

• 参考答案：
  1. FCFS（先来先服务）
  2. SJF（最短作业优先）
  3. Priority（优先级调度）
  4. RR（时间片轮转）
  5. 多级队列
  6. 多级反馈队列

9. 如何用互斥锁来解决临界区问题？

参考答案：

do {
    请求锁
    // critical section
    释放锁
    // remainder section
} while (TRUE);

10. 如何用信号量来解决临界区问题？

参考答案：

Semaphore S; 
// 初始化为 1
do {
    P(S) 或 wait(S);
    // 临界区
    V(S) 或 signal(S);
    // 剩余区
} while (true);

11. 如何用swap指令实现互斥？

参考答案：

共享数据 (初始化为 false):
boolean lock; 
boolean waiting[n];
进程 Pi do {
    key = true;
    while (key == true) 
        swap(lock, key);
    // critical section
    lock = false;
    // remainder section
}

12. 文件的基本属性有哪些？

• 参考答案：
  1. 文件标志
  2. 文件逻辑结构：信息大小等
  3. 文件物理结构信息：数据块等
  4. 文件使用信息：如访问时间、创建时间等
  5. 文件许可信息：如文件拥有者、权限等

13. 端口寄存器共有几种类型？分别是哪些类型？

• 参考答案： 4种类型：
  1. 数据输入
  2. 数据输出
  3. 控制
  4. 状态

14. 计算机系统有哪些部分构成？

• 参考答案：
  1. 硬件 (Hardware)：提供基本的计算资源。
  2. 操作系统 (Operating System)：控制和协调各用户的应用程序对硬件的使用。
  3. 应用程序 (Application programs)：规定用户按何种方式使用系统资源。
  4. 用户 (Users)：包括人、机器、其他计算机。

15. 简述分页管理。

• 参考答案：
  1. 把物理内存分成大小固定的块，称为帧。
  2. 把逻辑内存也分成大小固定的块，称为页。
  3. 保留所有空闲帧的记录。
  4. 运行一个有N页大小的程序时，需要找到N个空的帧来装入程序。
  5. 建立一个页表，把逻辑地址转换为物理地址。

16. 如何预防死锁？

• 参考答案： 通过抑制死锁发生的必要条件来预防死锁：
  1. 互斥：避免资源必须被独占使用。
  2. 占有并等待：必须保证进程申请资源时未占有其他资源。
  3. 不可抢占：允许资源在未完成时被抢占。
  4. 循环等待：对资源类型进行总排序，按顺序申请资源，避免形成环。

17. 描述安全状态算法。

• 参考答案：
  1. 初始化向量 Work 和数组 Finish。
     • Work := Available
     • Finish[i] = false (对所有进程 ii)
  2. 查找满足条件的进程 ii：
     • Finish[i]=falseFinish[i] = false
     • Need[i]≤WorkNeed[i] \leq Work。 如果不存在这样的 ii，转到步骤4。
  3. Work:=Work+Allocation[i]Work := Work + Allocation[i]，设置 Finish[i]=trueFinish[i] = true，返回步骤2。
  4. 如果所有 Finish[i]=trueFinish[i] = true，则系统处于安全状态；否则不安全。

18. 描述是否满足进程 Pi 的资源请求算法。

• 参考答案：
  1. RequestiRequest_i 是进程 PiP_i 的资源请求向量。如果 Requesti[m]=kRequest_i[m] = k，则进程 PiP_i 需要 RjmR_jm 的k个实例。 如果 Requesti≤NeediRequest_i \leq Need_i，转到步骤2；否则报错，因请求超过声明的最大值。
  2. 如果 Requesti≤AvailableRequest_i \leq Available，转到步骤3；否则 PiP_i 必须等待，因为资源不可用。
  3. 假设分配资源：
     • Available:=Available−RequestiAvailable := Available - Request_i
     • Allocationi:=Allocationi+RequestiAllocation_i := Allocation_i + Request_i
     • Needi:=Needi−RequestiNeed_i := Need_i - Request_i。
  4. 如果系统安全，则资源分配给 PiP_i；否则 PiP_i 必须等待，恢复原有资源分配状态。

19. 描述死锁检测算法。

• 参考答案：
  1. 初始化向量 Work 和数组 Finish。
     • Work:=AvailableWork := Available。
     • 对于每个进程 ii，如果 Allocation[i]≠0Allocation[i] \neq 0，设置 Finish[i]=falseFinish[i] = false；否则 Finish[i]=trueFinish[i] = true。
  2. 查找满足条件的进程 ii：
     • Finish[i]=falseFinish[i] = false
     • Request[i]≤WorkRequest[i] \leq Work。 如果不存在这样的 ii，转到步骤4。
  3. Work:=Work+Allocation[i]Work := Work + Allocation[i]，设置 Finish[i]=trueFinish[i] = true，返回步骤2。
  4. 如果存在 Finish[i]=falseFinish[i] = false，则系统处于死锁状态，且进程 PiP_i 是死锁的。

20. 描述指令和数据绑定到内存地址可以在三个不同的阶段。

• 参考答案：
  1. 编译时期 (Compile time)：如果内存位置已知，可生成绝对代码；若开始位置改变，则需重新编译代码。
  2. 加载时期 (Load time)：若存储位置在编译时未知，则必须生成可重定位（relocatable）代码。
  3. 执行时期 (Execution time)：若进程在执行时可以在内存中移动，则地址绑定延迟到运行时，需要硬件支持地址映射（如基址和限长寄存器）。

21. 用Test-and-Set指令实现互斥。

参考答案：

boolean lock = false;
do {
    while (TestAndSet(lock)) ;
    // critical section
    lock = false;
    // remainder section
} while (true);

22. 描述缺页错误的处理过程。

• 参考答案：
  1. 查看进程页表，确定访问是否为无效引用：若是，则终止；否则继续。
  2. 获取空的页框。
  3. 将缺页加载到页框中。
  4. 更新页表，将有效位设为V。
  5. 重启指令。

23. 解释文件分配磁盘块顺序分配方法及优点缺点。

• 参考答案： 优点：
  1. 支持顺序存取和随机存取。
  2. 顺序存取速度快。
  3. 磁盘寻道次数和寻道时间最少。

  缺点：

  1. 需要预留物理块以满足文件增长需求。
  2. 不利于文件的插入和删除。

24. 操作系统的主要功能有哪些？

• 参考答案：
  1. 存储管理
  2. 进程管理
  3. 文件系统管理
  4. 安全和保护

25. 文件的属性主要有哪些？

• 参考答案：
  1. 文件名：唯一，以可读形式表示。
  2. 类型：支持不同类型文件的文件系统使用。
  3. 位置：指向设备上文件位置的指针。
  4. 大小：文件当前大小。
  5. 保护：访问控制信息，如读、写、执行权限。
  6. 时间、日期、用户标识：用于保护、安全和使用跟踪的数据。

  所有文件信息存储在目录结构中，该结构位于磁盘上。

26. 对文件的基本操作主要有哪些？

• 参考答案：
  1. 创建文件
  2. 写文件
  3. 读文件
  4. 在文件内重定位
  5. 删除文件
  6. 截断文件
  7. 打开文件 (Open(Fi))：在磁盘的目录结构中查找文件Fi的表项，将表项内容加载到内存。
  8. 关闭文件 (Close(Fi))：将内存中的表项内容移回磁盘的目录结构中。

27. 目录的基本操作有哪些？

• 参考答案：
  1. 搜索文件
  2. 创建文件
  3. 删除文件
  4. 列出目录
  5. 重命名文件
  6. 跟踪文件系统

28. 目录的逻辑结构有哪些种？

• 参考答案：
  1. 单级目录
  2. 两级目录
  3. 树状目录
  4. 无环图目录
  5. 通用图目录

29. 简述银行家算法的Available、Max、Allocation、Need和Request的意义。

• 参考答案：
  1. Available：长度为 mm 的向量，若 Available[j]=kAvailable[j] = k，表示资源 RjR_j 有 kk 个实例可用。
  2. Max：n×mn \times m 矩阵，若 Max[i,j]=kMax[i,j] = k，表示进程 PiP_i 最多可请求 RjR_j 的 kk 个实例。
  3. Allocation：n×mn \times m 矩阵，若 Allocation[i,j]=kAllocation[i,j] = k，表示 PiP_i 当前已分配了 RjR_j 的 kk 个实例。
  4. Need：n×mn \times m 矩阵，若 Need[i,j]=kNeed[i,j] = k，表示 PiP_i 还需 RjR_j 的 kk 个实例。 Need[i,j]=Max[i,j]−Allocation[i,j]Need[i,j] = Max[i,j] - Allocation[i,j]。
  5. Request：若 Requesti[m]=kRequest_i[m] = k，表示 PiP_i 想请求 RjmR_jm 的 kk 个实例。

30. I/O设备在哪些方面存在差异？

• 参考答案：
  1. 数据传输方式：字符流或块传输。
  2. 访问方式：顺序访问或随机访问。
  3. 共享方式：专用设备或共享设备。
  4. 设备速度：设备的处理速度不同。
  5. I/O方向：可读写、只读、只写。

31. 进程控制块主要包括哪些信息？

• 参考答案：
  1. 进程状态
  2. 程序计数器
  3. CPU寄存器
  4. CPU调度信息
  5. 内存管理信息
  6. 计账信息
  7. I/O状态信息

32. 描述基本页面置换算法。

• 参考答案：
  1. 查找所需页面在磁盘上的位置。
  2. 查找空闲页框：
     • 若有空闲页框，则直接使用。
     • 若无空闲页框，则使用页面置换算法选择一个“牺牲”页框。
  3. 将“牺牲”页框的内容写到磁盘，更新页表和帧表。
  4. 将所需页加载到新的页框中，更新页表和帧表。
  5. 重启用户进程。

33. 进程的调度主要考虑哪些因素？

• 参考答案：
  1. CPU利用率：尽可能提高CPU的使用率。
  2. 吞吐量：单位时间内完成的进程数。
  3. 周转时间：进程从提交到完成的时间。
  4. 等待时间：进程在就绪队列中等待调度的总时间。
  5. 响应时间：从进程请求到首次被响应的时间（而不是最终输出结果的时间）。

34. 描述缺页错误的处理过程。

• 参考答案：
  1. 查看进程页表，确定是否为无效引用：
     • 若是无效引用，则终止进程。
     • 若仅是不在内存，则继续处理。
  2. 获取空闲页框。
  3. 将所需页加载到页框中。
  4. 更新页表，将有效位设为“V”。
  5. 重启指令。

35. 描述Pentium 4KB分页情况下，32位线性地址到物理地址的转换过程。

• 参考答案：
  1. 逻辑地址由页目录索引、页表索引和偏移构成。
  2. IA32中线性地址的高10位为页目录索引，用于找到页表。
  3. 中间10位为页表项索引，用于从页表中找到页框号。
  4. 页框号加上线性地址低12位（页内偏移）即可生成物理地址。

36. 程序并发执行为什么会失去封闭性和可再现性？

• 参考答案：
  1. 失去封闭性： 并发程序共享系统资源，资源状态可能被其他程序改变，导致程序的运行环境受到影响。
  2. 失去可再现性： 程序运行结果可能受到其他程序运行速度的影响，即使初始条件相同，多次执行的结果也可能不同。

37. 何谓死锁？产生死锁的原因和必要条件是什么？

• 参考答案：
  • 死锁：如果一组进程中的每个进程都在等待由该组中其他进程才能引发的事件，则该组进程处于死锁状态。
  • 产生死锁的原因：
    1. 竞争不可抢占资源。
    2. 竞争可消耗资源。
    3. 进程推进顺序不当。
  • 必要条件：
    1. 互斥条件：资源只能由一个进程独占使用。
    2. 请求和保持条件：进程持有资源，同时申请其他资源。
    3. 不可抢占条件：资源不能被强行抢占。
    4. 循环等待条件：进程间形成资源等待的环路。

38. 分页和分段存储管理有何区别？

• 参考答案：
  1. 分页是信息的物理单位，分段是信息的逻辑单位。
  2. 页的大小固定，段的大小可变。
  3. 分页的地址空间是一维的，分段的地址空间是二维的。

39. 简要说明I/O软件的四个层次的基本功能。

• 参考答案：
  1. 用户层I/O软件：提供用户交互接口，支持库函数调用。
  2. 设备独立性软件：实现设备无关性，包括缓冲、映射等功能。
  3. 设备驱动程序：直接控制硬件设备，执行设备操作指令。
  4. 中断处理程序：处理中断请求，保护和恢复现场。

40. 假定盘块的大小为1K，硬盘的大小为500MB，采用显示链接分配方式时，其FAT共有多少个表项？

• 参考答案： 硬盘有500K个盘块，因此FAT中共有500K个表项。

41. OS有哪几大特征？其最基本的特征是什么？

• 参考答案： OS的主要特征包括：并发、共享、虚拟和异步。 其最基本的特征是并发和共享。

42. 为什么要在操作系统中引入线程？

• 参考答案： 引入进程的目的是为了使多个程序能并发执行，提高资源利用率和系统吞吐量；而引入线程则是为了减少程序在并发执行时的时空开销，从而使操作系统具有更好的并发性。

43. 已知某分页系统，主存容量为64KB，页面大小为1KB。对于一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、3500、4500转换成物理地址：

1. 1023：2×1K+1023=30712 \times 1K + 1023 = 3071
2. 2500：6×1K+452=65966 \times 1K + 452 = 6596
3. 3500：7×1K+428=75967 \times 1K + 428 = 7596
4. 4500：页号为4，产生越界中断。

44. I/O软件的四个层次及对应功能：

1. 向设备寄存器写命令：设备驱动程序。
2. 检查用户是否有权使用设备：设备独立性软件。
3. 将二进制整数转换成ASCII码格式打印：用户层软件。
4. 缓冲管理：设备独立性软件。

45. 在链接式文件中常用哪种链接方式？为什么？

• 参考答案： 显式链接方式：
  • 隐式链接方式只适用于顺序访问，对随机访问效率低下。
  • 显式链接方式在内存中查找记录，显著提高检索速度，并减少磁盘访问次数。

46. 在基于微内核结构的操作系统中，应用了哪些新技术？

• 参考答案：
  1. 足够小的内核。
  2. 基于B/S模式。
  3. 应用“机制与策略分离”原理。
  4. 采用面向对象技术。

47. 已知某分页系统，页面大小为1KB。对于一个4页大的作业，其0、1、2、3页分别被分配到主存的3、2、5、1块中。将逻辑地址1023、2500、3500、4500转换成物理地址：

1. 1023：3×1K+1023=40953 \times 1K + 1023 = 4095
2. 2500：5×1K+452=55725 \times 1K + 452 = 5572
3. 3500：1×1K+428=14521 \times 1K + 428 = 1452
4. 4500：页号为4，产生越界中断。

48. PCB提供了进程管理和进程调度所需的哪些信息？

• 参考答案：
  1. 进程标识符。
  2. 处理机状态信息。
  3. 进程状态、进程优先级、等待CPU时间和阻塞原因等。

49. 什么是WIMP技术？它被应用到何种场合？

• 参考答案： WIMP技术包括：窗口（Windows）、图标（Icon）、菜单（Menu）、鼠标（Pointing device），以及面向对象技术。 它被应用于图形用户界面（GUI）的操作环境中，提供图文并茂的交互方式。

50. 什么是微内核OS？

• 参考答案： 微内核结构将操作系统划分为微内核和多个服务器两部分：
  1. 足够小的内核。
  2. 基于客户/服务器模式。
  3. 应用“机制与策略分离”原理。
  4. 采用面向对象技术。

51. 为什么要在OS中引入线程？

• 参考答案： 引入进程是为了使多个程序能并发执行，提高资源利用率和系统吞吐量；而引入线程则是为了减少程序在并发执行时的时空开销，从而提升操作系统的并发性能。

52. 已知某分页系统，页面大小为1KB。对于一个4页大的作业，其0、1、2、3页分别被分配到主存的2、3、6、1块中。将十进制的逻辑地址1023、2200、3300、4400转换成物理地址？

正确答案：

1. 1023：2*1K+1023=3071
2. 2200：6*1K+152=6296
3. 3300：1*1K+228=1252
4. 4400：页号为4，产生越界中断。

53. 在单缓冲情况下，为什么对一块数据的处理时间为MAX(C，T)+M？

正确答案：

在单缓冲情况下，数据从I/O控制器到缓冲区，数据从缓冲区到用户进程的工作区，必须串行操作；同样，数据从缓冲区到工作区和CPU从工作区取出数据处理，也需要串行；但CPU在处理一块数据的同时，可以从I/O设备读入下一块数据，因此，系统对一块数据的处理时间为MAX(C，T)+M。

54. 什么是文件的逻辑结构？什么是文件的物理结构？

正确答案：

1. 文件的逻辑结构是从用户的观点出发所观察到的文件的组织形式。
2. 文件的物理结构是指系统将文件存储在外存上所形成的一种存储组织形式。

55. 假定盘块的大小为4KB，硬盘的大小为512MB，采用显示链接分配方式时，其FAT共有多少个表项？如果文件A占用硬盘的9、10、14、12四个盘块，试画出文件A中各盘块间的链接情况及FAT的情况。

正确答案：

硬盘有512M/4K=128K个盘块，故FAT中共有128K个表项。

56. 试从交互性、及时性和可靠性等方面将分时系统与实时系统进行比较？

正确答案：

1. 交互性： 分时系统中，用户可以与系统进行充分的人机交互，而实时系统中的交互性仅限于访问系统中某些特定的服务程序，具有很大的局限性。
2. 及时性： 分时系统的及时性指用户能在很短的时间内获得系统的响应，一般为秒级。而对实时系统来说，及时性是它的关键问题，及时性对时间的要求更严格，一般为毫秒级。
3. 可靠性： 可靠性对实时系统来说是另一个关键问题，实时系统往往采用多级容错措施来保证系统的高度可靠。分时系统虽然也要求可靠性，但比实时系统的要求要低。

57. 试画出下面四条语句的前驱图：

S1：a=x+y; S2：b=z+2; S3：c=a-b; S4：d=c+2;

正确答案：

根据语句的依赖关系：

• S1 和 S2 没有依赖，属于并行；
• S3 依赖于 S1 和 S2；
• S4 依赖于 S3。

前驱图：

   S1     S2
    ↓      ↓
      →  S3
         ↓
        S4

58. 某系统采用页式存储管理策略，拥有逻辑空间32页，每页2KB，拥有物理空间1MB。

1. 写出逻辑地址格式。
2. 若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？

正确答案：

1. 逻辑地址格式： 逻辑空间32页，故页号用5位表示；每页2KB，页内地址用11位表示。 逻辑地址格式：页号（5位） + 页内地址（11位）。
2. 页表项及位数：
   • 每个进程最多有32页，页表最多32项。
   • 物理空间1MB = 2²⁰B，页面大小为2KB = 2¹¹B，物理块数为2⁹个，需要9位表示。
   • 每页表项至少需要9位。

59. 为什么在大多数OS中都引入了“打开”这一文件系统调用？打开的含义是什么？

正确答案：

“打开”文件的主要功能是将指定文件的属性信息复制到内存中，并返回指向内存中该文件属性信息的指针。以后，用户需要对文件进行操作时，即可直接在内存中找到文件的外存地址等属性，从而显著地提高对文件的操作速度。

60. 目前常用的外存有哪几种组织方式？

正确答案：

1. 连续组织方式。
2. 链接组织方式。
3. 索引组织方式。

61. 设计现代操作系统的主要目标是什么?

正确答案：

1. 方便性。
2. 有效性。
3. 可扩充性。
4. 开放性。

62. 产生死锁的原因和必要条件是什么？

正确答案：

产生死锁的原因：

1. 竞争不可抢占性资源引起死锁。
2. 竞争可消耗资源引起死锁。
3. 进程推进顺序不当引起死锁。

产生死锁的必要条件：

1. 互斥条件：资源不能被多个进程同时占用。
2. 请求和保持条件：进程已占有资源，同时又申请其他资源。
3. 不可抢占条件：已分配的资源不能被强制剥夺。
4. 循环等待条件：进程之间形成循环等待链。

63. 什么是程序运行时的时间局限性和空间局限性？

正确答案：

1. 时间局限性：如果程序中的某条指令或某数据刚被访问过，则不久以后该指令或数据可能会被再次访问。
2. 空间局限性：一旦程序访问了某个存储单元，在不久以后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围内。

64. 目前广泛采用的目录结构形式是哪种？它有什么优点？

正确答案：

目录结构形式：多级树形目录结构。 优点：

1. 能有效地提高对目录的检索速度。
2. 允许文件重名。
3. 方便实现文件共享。
4. 能够实现按名存取，更有效地进行文件的管理和保护。

65. 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为4、6、3、2，而该用户作业的长度为6页，试将十六进制的逻辑地址0A5C、103C、1A5C转换成物理地址。

正确答案：

1. 0A5C：逻辑地址0A5C的页号为2，2号页装入3号块，物理地址为000111001011100，转换成十六进制为0E5C。
2. 103C：逻辑地址103C的页号为4，页号合法，但该页未装入内存，故产生缺页中断。
3. 1A5C：逻辑地址1A5C的页号为6，页号非法，故产生越界中断。

66. 为什么在双缓冲情况下，系统对一块数据的处理时间为max(T，C)？

正确答案：

双缓冲的数据由I/O控制器到双缓冲，以及数据由双缓冲到工作区可以并行工作，因此，系统对一块数据的处理时间为max(T，M+C)。由于M是在内存中传输数据，时间很短，可以忽略，此时，系统对块数据的处理时间约等于max(T，C)。

67. 系统如何利用访问控制表和访问权限表来实现对文件的保护？

正确答案：

1. 访问控制表（ACL）：
   • 按访问矩阵的列（对象）划分，为每个对象建立访问控制表。
   • 表中每项是一个有序对(域，权集)，记录哪些域对该对象具有何种权限。
   • 由于空项远多于非空项，使用访问控制表可以显著减少存储空间，并提高查找速度。
2. 访问权限表：
   • 按访问矩阵的行（域）划分，为每个域建立访问权限表。
   • 每项记录该域对某对象的权限，描述一个用户对每个文件的可执行操作。

68. 假定盘块的大小为2KB，硬盘的大小为256MB，采用显示链接分配方式时，其FAT共有多少个表项？如果文件A占用硬盘的8、10、14、12四个盘块，试画出文件A中各盘块间的链接情况及FAT的情况。

正确答案：

1. 硬盘有 256MB/2KB = 128K 个盘块，故 FAT 中共有 128K 个表项。

69. 文件系统的模型可分为三层，试说明其每一层所包含的基本内容。

正确答案：

1. 最底层：对象及其属性
   • 包括文件、目录、磁盘（磁带）存储空间等。
2. 中间层：对对象进行操纵和管理的软件集合
   • 管理文件存储空间。
   • 管理文件目录。
   • 实现逻辑地址到物理地址的转换机制。
   • 管理文件的读写操作、共享与保护等功能。
3. 最高层：文件系统的用户接口
   • 包括命令接口和程序接口。

70. 什么是基于顺序搜索的动态分区分配算法？它可以分为哪几种？

正确答案：

基于顺序搜索的动态分区分配算法： 将系统中的空闲分区链接成一个链，依次搜索空闲分区链上满足要求的分区分配给作业。

分类：

1. 首次适应算法。
2. 循环首次适应算法。
3. 最佳适应算法。
4. 最坏适应算法。

71. 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为4、5、3、2，而该用户作业的长度为6页，试将以下逻辑地址0、2500、3500、4500转换成物理地址。

正确答案：

1. 0：页号为0，0号页装入4号块，物理地址为4*1K = 4096。
2. 2500：页号为2，2号页装入3号块，物理地址为3*1K + 452 = 3524。
3. 3500：页号为3，3号页装入2号块，物理地址为2*1K + 428 = 2476。
4. 4500：页号为4，产生缺页中断。

72. 在进程调度中，何谓静态和动态优先级?确定静态优先级的依据是什么?

正确答案：

1. 静态优先级：在创建进程时确定，运行期间保持不变。
2. 动态优先级：在创建进程时赋予初始优先级，运行中可根据等待时间、资源占用等动态调整。

确定静态优先级的依据：

1. 进程类型。
2. 进程对资源的需求。
3. 用户要求。

73.为何要引入与设备的无关性？如何实现设备的独立性？

参考答案： 为了方便用户和提高OS的可适应性与可扩展性，在现代OS的I/O系统中，都无一例外地增加了与设备无关的I/O软件，以实现设备独立性，也称为设备无关性。其基本含义是：应用程序中所用的设备，不局限于使用某个具体的物理设备。为每个设备所配置的设备驱动程序是与硬件紧密相关的软件。为了实现设备独立性，必须再在设备驱动程序之上设置一层软件，称为与设备无关的I/O软件，或设备独立性软件。

计算分析题

1. 为何要引入与设备的无关性？如何实现设备的独立性？

题目： 为何要引入与设备的无关性？如何实现设备的独立性？

参考答案： 为了方便用户和提高OS的可适应性与可扩展性，在现代OS的I/O系统中，都无一例外地增加了与设备无关的I/O软件，以实现设备独立性，也称为设备无关性。其基本含义是：应用程序中所用的设备，不局限于使用某个具体的物理设备。为每个设备所配置的设备驱动程序是与硬件紧密相关的软件。为了实现设备独立性，必须再在设备驱动程序之上设置一层软件，称为与设备无关的I/O软件，或设备独立性软件。

2. 页面置换先进先出算法，引用以下页面: 1,2,3,4,1,2,5,1,2,3,4,5，共有3个页框，确定每次引用装入哪个页框？

题目： 页面置换先进先出算法，引用以下页面: 1,2,3,4,1,2,5,1,2,3,4,5，共有3个页框，确定每次引用装入哪个页框？

参考答案： 页面：1 2 3 4 1 2 5 1 2 3 4 5 页框：1 2 3 4 1 2 5 1 2 3 4 5

3. 页面置换先进先出算法，引用串: 1,2,3,4,1,2,5,1,2,3,4,5，共有4个页框，分析会发生哪些次页面替换？

题目： 页面置换先进先出算法，引用串: 1,2,3,4,1,2,5,1,2,3,4,5，共有4个页框，分析会发生哪些次页面替换？

参考答案： 引用串: 1,2,3,4,1,2,5,1,2,3,4,5 替换的页面为：5，1，3，4，5

4. 进程优先级调度算法，非抢占式调度，求进程执行顺序和开始时间

题目： 进程 P1, P2, P3, P4, P5 的优先级和运行时间如下： 请使用非抢占式优先级调度算法，假设从 0 时刻开始执行，给出各进程的执行顺序及开始时间。

参考答案：

5. 短作业优先调度策略，求作业的开始时间、完成时间、周转时间和平均周转时间

题目： 设有三个作业，它们的提交时间及运行时间如下表： 若采用短作业优先调度策略，试求各个作业的开始时间、完成时间、周转时间，并计算平均周转时间。

参考答案：

平均周转时间 = (4 + 7 + 14) / 3 = 8.33

6. 平均内存访问时间计算

题目： 已知：

• 存取内存时间 = 200 纳秒
• 平均缺页处理时间 = 8 毫秒
• 每 1,000 次访问中有 1 次页错误

求：平均内存访问时间（EAT）。

参考答案： EAT = (1-p) × 200 + p × 8,000,000 p = 0.001 EAT = 0.999 × 200 + 0.001 × 8,000,000 = 200 + 7,999.8 = 8,200 ns

7. 页式存储和段式存储的物理地址计算

题目： (1) 某页式存储系统页表如下，设每页大小为 1KB，逻辑地址为 8300 时，求对应的页号和页内地址，以及内存中的物理地址。 页表：

(2) 已知如下段表： 在分段存储管理下，求以下逻辑地址的物理地址，若越界则说明。

• (a) (1,10)
• (b) (4,112)

参考答案： (1) 页式存储： 页号 P = INT[8300 / 1024] = 8 页内地址 d = 8300 MOD 1024 = 108 物理地址 = 4 × 1024 + 108 = 4204

(2) 段式存储：

• (a) 地址 (1,10): 基址 = 2300, 段内位移 = 10 物理地址 = 2300 + 10 = 2310
• (b) 地址 (4,112): 基址 = 1952, 段长 = 96 段内位移 = 112 > 段长 = 越界中断

8. 进程调度下等待时间的计算

题目： 考虑以下进程集：

假设进程按照顺序 P1, P2, P3, P4, P5 到达，求 P3 和 P4 在以下调度算法下的等待时间：

• FCFS（先来先服务）
• SJF（短作业优先）
• 优先级调度（数字小代表优先级高）

参考答案：

9. 银行家算法的安全性检查

题目： 银行家算法中，已知 5 个进程 P0 到 P4 和 3 类资源 (A: 10 实例，B: 5 实例，C: 7 实例)，在时刻 Tn 的快照如下：

(1) 判断系统是否处于安全状态。 (2) 检查 Request1=(1,0,2) 是否可以满足。

参考答案：

(1) 系统处于安全状态，安全序列为：<P1, P3, P4, P0, P2>

(2) Request1=(1,0,2) ≤ Available (3,3,2)，可以满足，执行后仍满足安全状态，安全序列为：<P1, P3, P4, P0, P2>

10. 考虑一个分页系统在内存中存储着一张页表

题目： a. 如果内存的查询需要 200 毫秒，那么一个分页内存的查询需要多长时间？ b. 如果我们加上相关联的寄存器 TLB，75% 的页表查询可以在相关联的寄存器中找到，那么有效的查询时间是多少？（假设如果入口存在的话，在相关的寄存器中找到页表入口不花费时间）

参考答案： a. 分页内存查询需要两次内存访问：一次访问页表，另一次访问数据。因此，分页查询时间 = 200 + 200 = 400 毫秒。

b. 有效查询时间 = 0.75 × 200 + 0.25 × 400 = 250 毫秒。

11. 页结构的地址转换机制

题目： 页结构的地址转换机制如下图所示：其中，logical address 为逻辑地址，outer pagetable 为外页表，page of pagetable 为页表的页。描述逻辑地址转换为物理地址的过程。

参考答案： 逻辑地址由 p1、p2 和 d 构成：

1. 通过 p1 在外页表中检索页 p2；
2. 通过 p2 在页表中检索页框基址 base；
3. 通过 d 得到页内偏移量；
4. 最终物理地址为 base + d。

12. 最近最少使用（LRU）页面置换算法

题目： 页面引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，分配 4 个页框，给出每个页面会被放到哪个页框，计算缺页次数。

参考答案： 页框变化如下：

缺页次数： 8 次。

13. 银行家算法安全性检查

题目： 五个进程 P0 到 P4，三个资源类型 A（7 个实例），B（2 个实例），C（6 个实例）时刻 Tn 的状态如下：

P1 请求资源 Request1 = (1, 0, 2)，能否满足？给出详细过程。

参考答案： Request1 ≤ Available = (1, 0, 2) ≤ (3, 3, 2)，请求可以满足。

调整后的状态： Available = (2, 3, 0)

安全序列为：P1 → P3 → P4 → P0 → P2，故请求可以满足。

14. 银行家算法死锁检测

题目： 五个进程 P0 到 P4，三个资源类型 A（7 个实例），B（2 个实例），C（6 个实例），时刻 Tn 的状态如下：

Available = (0, 0, 0)。检测是否发生死锁，并给出详细过程。

参考答案： P0 和 P2 不需要资源，完成后释放资源，Available = (3, 1, 3)。 接着，P3 可完成，释放资源后 Available = (5, 2, 4)。 随后，P1 可完成，释放资源后 Available = (7, 2, 6)。 最后，P4 可完成，释放资源后所有进程完成。 结论：无死锁。

15. 用 P、V 操作实现并发同步

题目： 有三个进程：

• 爸爸（Dad）：向盘中放入苹果或桔子；
• 儿子（Son）：从盘中取出桔子；
• 女儿（Daughter）：从盘中取出苹果；

盘子最多能容纳 5 个水果，三人不能同时操作。用 P、V 操作实现同步。

参考答案：

semaphore Empty = 5, Orange = 0, Apple = 0, Mutex = 1;

Dad() {
    while (1) {
        P(Empty);
        P(Mutex);
        将水果放入盘中；
        V(Mutex);
        if (放入的是桔子) V(Orange);
        else V(Apple);
    }
}

Son() {
    while (1) {
        P(Orange);
        P(Mutex);
        从盘中取出一个桔子；
        V(Mutex);
        V(Empty);
        享用桔子；
    }
}

Daughter() {
    while (1) {
        P(Apple);
        P(Mutex);
        从盘中取出一个苹果；
        V(Mutex);
        V(Empty);
        享用苹果；
    }
}

16. 短作业优先（SJF）和最高响应比优先（HRRN）调度算法

题目： 四个作业的到达时间和运行时间如下：

求： a. SJF 调度顺序和平均周转时间； b. HRRN 调度顺序和平均周转时间。

参考答案： (a) SJF 调度 调度顺序：J1 → J4 → J2 → J3 平均周转时间 = (2 + 1.6 + 5 + 7.5) / 4 = 4.025

(b) HRRN 调度 调度顺序：J1 → J2 → J4 → J3 平均周转时间 = (2 + 4 + 4.1 + 7.5) / 4 = 4.4

17. 页面置换算法缺页率计算

题目： 页面走向：4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5。 块数分别为 3 和 4，采用以下算法计算缺页率： a. FIFO（先进先出）； b. LRU（最近最少使用）。

参考答案： (a) FIFO 算法：

• 块数为 3，缺页次数：9，缺页率 = 9/12 = 75%；
• 块数为 4，缺页次数：10，缺页率 = 10/12 = 83.3%。

(b) LRU 算法：

• 块数为 3，缺页次数：10，缺页率 = 10/12 = 83.3%；
• 块数为 4，缺页次数：8，缺页率 = 8/12 = 66.7%。

现象： FIFO 会出现Belady 异常，即增加内存块后缺页次数反而增加。

18. 爸爸、儿子、女儿取放水果的同步实现

题目： 桌上有一个能盛得下五个水果的空盘。爸爸不停地向盘中放苹果或桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。规定三人不能同时从盘中取放水果。试用 P、V 原语实现爸爸、儿子、女儿三个并发进程的同步。

参考答案：

semaphore Empty = 5, Orange = 0, Apple = 0, Mutex = 1;

Dad() {
    while (1) {
        P(Empty);            // 等待有空位
        P(Mutex);            // 获取操作盘子的互斥锁
        将水果放入盘中；     // 放入苹果或桔子
        V(Mutex);            // 释放锁
        if (放入的是桔子) {
            V(Orange);        // 增加桔子的计数
        } else {
            V(Apple);         // 增加苹果的计数
        }
    }
}

Son() {
    while (1) {
        P(Orange);           // 等待桔子
        P(Mutex);            // 获取操作盘子的互斥锁
        从盘中取出一个桔子； // 取出桔子
        V(Mutex);            // 释放锁
        V(Empty);            // 增加空位计数
        享用桔子；
    }
}

Daughter() {
    while (1) {
        P(Apple);            // 等待苹果
        P(Mutex);            // 获取操作盘子的互斥锁
        从盘中取出一个苹果； // 取出苹果
        V(Mutex);            // 释放锁
        V(Empty);            // 增加空位计数
        享用苹果；
    }
}

19. 银行家算法：需求矩阵计算与资源分配安全性分析

题目： 假定系统中有四种类型资源（A、B、C、D）和五个进程 P1、P2、P3、P4、P5。T0 时刻系统状态如下表所示，请回答：

1. 计算 T0 时刻的需求矩阵（Need）；
2. 判断 T0 时刻是否为安全状态？若是，请给出安全序列；
3. 在 T0 时刻，若 P3 请求资源 Request3 = (1, 1, 1, 1)，是否能实施分配？为什么？
4. 在 (3) 的基础上，若 P4 请求资源 Request4 = (1, 0, 1, 0)，是否能实施分配？为什么？

参考答案：

1. 计算需求矩阵（Need） Need = Max - Allocation： 进程NeedP11 2 2 1P21 2 2 2P32 3 5 6P40 6 5 2P54 4 2 2

1. 判断 T0 时刻是否为安全状态
   • Available = (1, 7, 3, 3)
   • 按银行家算法的安全性检查：
     • P1：Need1 (1, 2, 2, 1) ≤ Available (1, 7, 3, 3)，分配后 Available = (1+0, 7+1, 3+0, 3+1) = (1, 8, 3, 4)。
     • P2：Need2 (1, 2, 2, 2) ≤ Available (1, 8, 3, 4)，分配后 Available = (1+2, 8+0, 3+0, 4+0) = (3, 8, 3, 4)。
     • P4：Need4 (0, 6, 5, 2) ≤ Available (3, 8, 3, 4)，分配后 Available = (3+1, 8+2, 3+2, 4+1) = (4, 10, 5, 5)。
     • P5：Need5 (4, 4, 2, 2) ≤ Available (4, 10, 5, 5)，分配后 Available = (4+0, 10+0, 5+2, 5+2) = (4, 10, 7, 7)。
     • P3：Need3 (2, 3, 5, 6) ≤ Available (4, 10, 7, 7)，分配后 Available = (4+3, 10+0, 7+2, 7+1) = (7, 10, 9, 8)。

   安全序列： P1 → P2 → P4 → P5 → P3

1. P3 请求资源 Request3 = (1, 1, 1, 1)
   • 检查条件：
     • Request3 (1, 1, 1, 1) ≤ Need3 (2, 3, 5, 6)：满足
     • Request3 (1, 1, 1, 1) ≤ Available (1, 7, 3, 3)：满足
   • 分配后资源状态：
     • Available = Available - Request3 = (1, 7, 3, 3) - (1, 1, 1, 1) = (0, 6, 2, 2)
     • Allocation3 = Allocation3 + Request3 = (3, 0, 2, 1) + (1, 1, 1, 1) = (4, 1, 3, 2)
     • Need3 = Need3 - Request3 = (2, 3, 5, 6) - (1, 1, 1, 1) = (1, 2, 4, 5)
   • 执行安全性算法：
     • 对所有进程，条件 Need[i] ≤ Available 不满足，找不到安全序列，系统进入不安全状态。

   结论： 不为 P3 分配资源。

1. P4 请求资源 Request4 = (1, 0, 1, 0)
   • 检查条件：
     • Request4 (1, 0, 1, 0) ≤ Need4 (0, 6, 5, 2)：不满足

   结论： 直接报错，不能分配资源。

20. 请求页式存储管理系统缺页率计算

题目： 在一个请求页式存储管理系统中，假如一个作业的页面走向为 1、2、3、4、1、2、5、1、2、3、4、5。当分配给该作业的物理块数分别为 3 和 4 时，试计算采用下述页面置换算法时的缺页率（假设开始时主存中没有页面），并比较所得结果，同时指出使用 FIFO 算法时可能产生什么现象： (1) 先进先出（FIFO）置换算法 (2) 最近最久未使用（LRU）置换算法

参考答案： (1) FIFO 算法：

• 块数为 3：缺页次数 = 9，缺页率 = 9/12 = 75%
• 块数为 4：缺页次数 = 10，缺页率 = 10/12 = 83.3%

(2) LRU 算法：

• 块数为 3：缺页次数 = 10，缺页率 = 10/12 = 83.3%
• 块数为 4：缺页次数 = 8，缺页率 = 8/12 = 66.7%

现象： FIFO 算法可能会出现 Belady 异常，即增加内存块数后缺页次数反而增加。

21. 并发同步问题：父亲、儿子、女儿取放水果

题目： 桌上有一空盘，允许存放一只水果。父亲（father）可以向盘中放一个香蕉或一个桔子，儿子（son）专等吃盘中的香蕉，女儿（daughter）专等吃盘中的桔子。规定当盘空时，父亲一次只能放一只水果供儿子或女儿取用。要求用 P、V 原语实现 father、son、daughter 三个并发进程的同步。

参考答案：

semaphore empty = 1, banana = 0, orange = 0;

father() {
    while (1) {
        P(empty);
        if (放入的是香蕉) {
            V(banana);
        } else {
            V(orange);
        }
    }
}

son() {
    while (1) {
        P(banana);
        从盘中取出香蕉；
        V(empty);
        吃香蕉；
    }
}

daughter() {
    while (1) {
        P(orange);
        从盘中取出桔子；
        V(empty);
        吃桔子；
    }
}

22. 作业调度算法：短作业优先（SJF）和先来先服务（FCFS）

题目： 下表给出作业 1、2、3、4 的到达时间和运行时间，分别采用短作业优先调度算法和先来先服务算法，试问平均周转时间各为多少？（时间单位：小时，以十进制计算）

参考答案： (1) SJF 调度算法： 调度顺序：J1 → J3 → J4 → J2

平均周转时间 = (3 + 4 + 7 + 17) / 4 = 7.75

(2) FCFS 调度算法： 调度顺序：J1 → J2 → J3 → J4

平均周转时间 = (3 + 7 + 9 + 12) / 4 = 7.75

23. 磁盘调度算法及平均寻道长度计算

题目： 假设磁盘有 200 个磁道，磁盘请求队列中是一些随机请求，按照到达的次序分别处于 190、10、160、80、90、125、30、20、140、25 号磁道上，当前磁头在 100 号磁道上，并正由外向里移动。

试给出按以下调度算法进行磁盘调度时满足请求的次序，并计算它们的平均寻道长度：

1. 先来先服务（FCFS）
2. 最短寻道时间优先（SSTF）
3. 扫描算法（SCAN）
4. 循环扫描算法（C-SCAN）

参考答案：

1. FCFS 调度顺序： 190 → 10 → 160 → 80 → 90 → 125 → 30 → 20 → 140 → 25 总寻道长度： |190-100| + |10-190| + ... = 640 平均寻道长度： 640 / 10 = 64
2. SSTF 调度顺序： 根据当前磁头最近优先访问：100 → 90 → 80 → 125 → 140 → 160 → 190 → 30 → 25 → 20 总寻道长度： |90-100| + |80-90| + ... = 285 平均寻道长度： 285 / 10 = 28.5
3. SCAN 调度顺序： 从 100 开始向内移动，访问：90 → 80 → 30 → 25 → 20，然后反向访问：125 → 140 → 160 → 190 总寻道长度： |90-100| + |80-90| + ... = 270 平均寻道长度： 270 / 10 = 27
4. C-SCAN 调度顺序： 从 100 开始向内移动，访问：90 → 80 → 30 → 25 → 20，然后从最外轨开始反向访问：125 → 140 → 160 → 190 总寻道长度： |90-100| + |80-90| + ... = 300 平均寻道长度： 300 / 10 = 30

24. 银行家算法资源分配和安全性分析

题目： 假定系统中有四种资源（A、B、C、D）和五个进程 P1、P2、P3、P4、P5，在时刻 T0 时系统资源分配情况如下：

(1) 计算分配矩阵 Allocation 的值； (2) 判断 T0 时刻是否为安全状态；若是，请给出安全序列； (3) 若 P3 请求资源 (1,2,2,1)，是否能实施分配，为什么？ (4) 在 (3) 的基础上，若 P4 请求资源 (1,2,1,2)，是否能实施分配，为什么？

参考答案： (1) Allocation = Max - Need。

(2) T0 时刻是安全状态，安全序列为：P1 → P4 → P5 → P2 → P3。

(3) 检查 Request3 (1,2,2,1)：

• Request3 ≤ Need3，Request3 ≤ Available，满足条件。
• 但分配后执行安全性算法无法找到安全序列，故系统处于不安全状态，不能分配。

(4) 检查 Request4 (1,2,1,2)：

• Request4 > Need4，报错，不能分配。

25. 作业调度算法：SJF 和 FCFS 的平均周转时间计算

题目： 下表给出作业 1、2、3、4 的到达时间和运行时间，分别采用短作业优先调度算法（SJF）和先来先服务算法（FCFS），试问平均周转时间各为多少？（时间单位：小时，以十进制计算。）

参考答案：

(1) 短作业优先调度算法（SJF）：

• 调度顺序：J1 → J3 → J2 → J4

平均周转时间 = (3 + 2 + 9 + 10) / 4 = 6

(2) 先来先服务调度算法（FCFS）：

• 调度顺序：J1 → J2 → J3 → J4

平均周转时间 = (3 + 7 + 7 + 10) / 4 = 6.75

26. 混合索引分配文件系统的计算

题目： 存放在某个磁盘上的文件系统采用混合索引分配方式，其 FCB 中共有 13 个地址项：

• 第 0-9 项为直接地址，
• 第 10 项为一次间接地址，
• 第 11 项为二次间接地址，
• 第 12 项为三次间接地址。

如果每个盘块为 512 字节，盘块号需要用 3 个字节来描述，试问：

1. 该文件系统允许文件的最大长度是多少？
2. 将文件的字节偏移量 5000、15000 转换为物理块号和块内偏移量。

参考答案：

(1) 最大文件长度：

• 每个盘块存储数据大小为 512 字节，盘块号需要 3 个字节描述，因此：
  • 一次间接地址最多指向 ⌊512/3⌋ = 170 个盘块；
  • 二次间接地址最多指向 170 × 170 个盘块；
  • 三次间接地址最多指向 170 × 170 × 170 个盘块。

最大文件长度 = (10 + 170 + 170² + 170³) × 512 字节 = 4942080 × 512 字节 = 2,531,246,080 字节 ≈ 2.53 GB

(2) 字节偏移量的转换：

a. 偏移量 5000： 逻辑块号 = ⌊5000 / 512⌋ = 9，块内偏移量 = 5000 % 512 = 392

• 因为 9 < 10（小于直接地址数量），直接从 FCB 的第 9 个直接地址项中获取物理块号。

b. 偏移量 15000： 逻辑块号 = ⌊15000 / 512⌋ = 29，块内偏移量 = 15000 % 512 = 152

• 因为 29 > 10（超出直接地址），需要从一次间接地址项获取。
• 逻辑块号 29 - 10 = 19，因此需要访问一次间接地址块中的第 19 个地址项以获取物理块号。

27. 磁盘调度算法及平均寻道长度计算

题目： 假设磁盘有 200 个磁道，磁盘请求队列为：180、20、160、60、70、135、40 号磁道。当前磁头在 100 号磁道上，并正由外向里移动。

试用以下算法调度，并计算平均寻道长度：

1. 先来先服务（FCFS）
2. 最短寻道时间优先（SSTF）
3. 扫描算法（SCAN）
4. 循环扫描算法（C-SCAN）

参考答案：

(1) FCFS 调度： 按请求队列顺序：100 → 180 → 20 → 160 → 60 → 70 → 135 → 40 总寻道长度： |180-100| + |20-180| + ... = 640 平均寻道长度： 640 / 7 = 91.43

(2) SSTF 调度： 按照距离当前磁头最近优先：100 → 135 → 160 → 180 → 70 → 60 → 40 → 20 总寻道长度： |135-100| + |160-135| + ... = 310 平均寻道长度： 310 / 7 = 44.29

(3) SCAN 调度： 从当前磁头向内移动：100 → 70 → 60 → 40 → 20，然后反向：135 → 160 → 180 总寻道长度： |70-100| + |60-70| + ... = 260 平均寻道长度： 260 / 7 = 37.14

(4) C-SCAN 调度： 从当前磁头向内移动到最里端，然后从最外轨开始：100 → 70 → 60 → 40 → 20 → 135 → 160 → 180 总寻道长度： |70-100| + |60-70| + ... = 320 平均寻道长度： 320 / 7 = 45.71

29. 可变分区分配的最先适应和最佳适应算法

题目： 某操作系统采用可变分区分配管理方法，用户区地址为 0--512K-1。假设采用以下分区管理：

• 申请序列： 申请 300K → 申请 100K → 释放 300K → 申请 150K → 申请 30K → 申请 40K → 申请 60K → 释放 30K

问题：

1. 用最先适应算法画出分配情况及空闲分区表；
2. 用最佳适应算法画出分配情况及空闲分区表；
3. 如果再申请 100K 空间，则两种算法的结果如何？

参考答案：

(1) 最先适应算法：

• 分区表按照地址从低到高依次分配。
• 空闲分区分裂时，优先分配低地址空闲区。

分配结果图示及表格略。

再申请 100K 空间： 空间足够，可以成功分配。

(2) 最佳适应算法：

• 分区表按照大小从小到大分配，优先选最小空闲区。

分配结果图示及表格略。

再申请 100K 空间： 若无合适大小的空闲分区，无法完成分配。

编程题

1. Peterson 算法伪代码

题目： 写出 Peterson 算法的伪代码。

参考答案：

// 定义变量
boolean flag[2];     // 表示每个线程是否希望进入临界区
int turn;            // 表示轮到哪个线程进入临界区

// 线程 i 的代码
do {
    flag[i] = true;  // 表示线程 i 希望进入临界区
    turn = j;        // 将权利让给线程 j
    while (flag[j] && turn == j) {
        // 等待线程 j 完成临界区
    }
    // 临界区
    // ...
    flag[i] = false; // 离开临界区
    // 剩余区
    // ...
} while (true);

说明：

• Peterson 算法是用于两个线程的同步算法，保证了互斥和死锁避免。
• 变量 flag[i] 表示线程是否希望进入临界区；turn 表示优先级顺序。

2. 信号量生产者消费者问题分析

题目： 注释以下代码，并说明三个信号量的含义，以及 A 和 B 哪个是生产者进程，哪个是消费者进程。

semaphore full = 0, empty = n, mutex = 1;

A: 
do {
    … produce an item in nextp …
    wait(empty);
    wait(mutex);
    add nextp to buffer;
    signal(mutex);
    signal(full);
} while (1);

B: 
do {
    wait(full);
    wait(mutex);
    … remove an item from buffer to nextc …
    signal(mutex);
    signal(empty);
    … consume the item in nextc …
} while (1);

参考答案： 注释代码：

1. semaphore full：表示缓冲区中的产品数，初始值为 0。
2. semaphore empty：表示缓冲区的空位数，初始值为 n（缓冲区大小）。
3. semaphore mutex：用于实现对缓冲区操作的互斥访问，初始值为 1。

进程 A 是生产者：

1. 生产一个产品到 nextp。
2. 使用 wait(empty) 确保缓冲区有空位。
3. 使用 wait(mutex) 确保对缓冲区的互斥访问。
4. 将产品添加到缓冲区。
5. 使用 signal(mutex) 释放互斥访问。
6. 使用 signal(full) 增加缓冲区中产品的计数。

进程 B 是消费者：

1. 使用 wait(full) 确保缓冲区中有产品。
2. 使用 wait(mutex) 确保对缓冲区的互斥访问。
3. 从缓冲区中取出产品到 nextc。
4. 使用 signal(mutex) 释放互斥访问。
5. 使用 signal(empty) 增加缓冲区的空位计数。
6. 消费产品。

3. 注释 Peterson 主函数并分析输出结果

题目： 注释以下 Peterson 主函数的每行程序，并分析程序可能的输出结果。

boolean flag[2];
flag[0] = false;
flag[1] = false;
int turn;

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j) {}
    // 临界区
    flag[i] = false;
    // 剩余区
} while (1);

参考答案： 注释代码：

1. boolean flag[2];：定义两个标志位，用于表示线程是否希望进入临界区。
2. flag[0] = false; flag[1] = false;：初始化标志位，表示两个线程初始时都不希望进入临界区。
3. int turn;：定义变量，用于指示当前轮到哪个线程进入临界区。
4. flag[i] = true;：线程 i 表示希望进入临界区。
5. turn = j;：将优先级转交给线程 j。
6. while (flag[j] && turn == j) {}：如果线程 j 也希望进入临界区且优先级是 j，则等待。
7. // 临界区：执行线程 i 的临界区代码。
8. flag[i] = false;：线程 i 退出临界区。
9. // 剩余区：线程 i 执行非临界区代码。

程序输出分析：

• Peterson 算法保证了两个线程在同一时间不会同时进入临界区（互斥）。
• 由于 turn 变量的引入，它也避免了死锁和饥饿问题。

4. 用 fork 创建子进程的程序

题目： 写一个程序，完成以下功能：用 fork 创建子进程，若失败，输出 “failed”，程序退出；在子进程中输出 “child”；在父进程中等待子进程返回后，输出 “parent”。

参考答案：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main() {
    pid_t fpid;  // 定义进程号变量
    fpid = fork();  // 创建子进程

    if (fpid < 0) {  // fork 返回值小于 0 表示创建失败
        printf("failed\n");
        exit(-1);  // 退出程序
    } else if (fpid == 0) {  // fork 返回值等于 0 表示当前是子进程
        printf("child\n");
    } else {  // fork 返回值大于 0 表示当前是父进程
        wait(NULL);  // 等待子进程结束
        printf("parent\n");
    }

    return 0;
}

程序运行结果：

如果 fork() 成功，则会输出：

child
parent

如果 fork() 失败，则会输出：

failed

说明：

1. fork() 用于创建子进程，子进程从 fork() 返回点开始执行。
2. 父进程和子进程的区别是 fork() 的返回值不同。
3. wait() 使父进程等待子进程结束后再继续执行。