* 1 * 2 1 2 1 * 0 2 1 * 4 0 2 * 1 4 0 * 3 1 4 0 3 1 4 * 2 3 1 4 2 3 1 * 4 2 3 1 * 1 4 2 3 1 2 依次被淘汰的页为：1、2、0、4、1、3 LRU 共发生7次缺页 1 2 1 0 4 1 * 1 * 1 2 1 2 * 1 2 0 * 1 4 0 1 4 0 3 * 1 4 3 4 1 4 3 2 * 2 4 3 1 * 2 4 1 4 2 4 1 1 2 4 1 2 0 1 3 依次被淘汰的页为：2、0、1、3 （2）
（a）0A4EH对应的二进制为 0000 10,10 0100 1110
该地址表明它对应第2页,根据已知该页在内存,对应物理块为10,所以,物理地址为: 0010 10,10 0100 1110 (十六进制为2A4EH)
（b）122AH对应的二进制为 0001 00,10 0010 1010 该地址表明它对应第4页, 根据已知该页不在内存中。
3．分页式存储空间的分配由于块的大小是固定的，可以用一张位示图来构成主存分配表。现设主存有8192块，则可用字长为32位的256个字作为位示图。若块号、字号、位号（从高位到低位）都是从0开始，试问4999块对应的字号和位号；129字的29位对应哪一块？
【参考答案】
依题目所给条件，已知位示图如下所示：
0 1 2 … 31 0 2 255
4999÷32=156,余1。所以4999块对应的字号为156，位号为1。
129字的29位对应的块号为：129*32+29=4157（块），即对应内存的第4157块。
4．某进程，若它对页面的访问串为： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
???设运行开始时，内存中没有属于该进程的页面。当分别用最近最少用（ＬＲＵ）调度算法、先进先出（ＦＩＦＯ）调度算法实现页面更换时，写出相应的淘汰过程并给出各自依次淘汰页及缺页次数。（设允许进程在内存中最多占三个页面）
【参考答案】
LRU更换算法： 是否缺页 内存中包含的页 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 * * * * * * * * * * * * 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 33 2 34 … … … 8191 31 1 32 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 被淘汰的页 7 1 2 3 0 4 0 3 2 共发生12次缺页，依次淘汰页为：7 1 2 3 0 4 0 3 2 FIFO更换算法： 是否缺页 内存中包含的页 被淘汰的页 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 * * * * * * * * * * * * * * 7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 7 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7 0 1 2 3 0 4 2 3 0 1 共发生14次缺页，依次淘汰页为：7 0 1 2 3 0 4 2 3 0 1
5．描述采用虚拟页式存储管理机制的系统，当发生缺页中断时系统的处理过程。
T 有空闲页吗？该页修改过吗？ 写回外存修改页表 T 将该页调入内存，修改页表相应表目保护现场恢复现场，返回 F F 选择一页淘汰 【参考答案】 缺页中断
6．某进程，若它对页面的访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 试用LRU、FIFO两种算法实现页面更换，并给出各自的缺页次数。（设该进程在内存中占四个页架）
【参考答案】
M=4时，采用LRU算法，系统的淘汰过程： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 是否缺* * * * 页： 内存中包含的页面：
* * * * 7 7 7 7 7 3 3 3 3 3 3 3 3 3 3 3 3 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 被淘汰 7 1 4 3 页
即F=8（次缺页） M=4时，采用FIFO算法，系统的淘汰过程： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 是否缺
* * * * * * * * * * 页： 内存中包含的页面： 被淘汰页
第四章 习题及答案 一、填空题
1．文件系统主要管理计算机系统的软件资源，即对于各种 的管理。 【答案】文件
【解析】用户使用计算机来完成自己的某项任务时，总会碰到这样一些问题：其一，使用现有的软件资源来协助自己工作。例如，利用系统调用和利用库函数与实用程序等来减少编程的工作量，避开与硬件有关的部分。其二，编制完成的或未完成的程序存放在什么地方，需要访问的数据存放在什么地方。这实际上是怎样对软件资源进行透明的存放，并能透明地存取，文件系统也就应运而生了。
2．从用户的角度看，文件系统的功能是要实现 ① 。为了达到这一目的，一般要建立 ②
【答案】①按名存取，②文件目录 【解析】文件系统的建立就是要让用户透明地对文件进行存取，这就要求文件系统要解决把每个文件的符号名与其所在的文件存储空间中的物理地址联系起来的问题，这也是文件系统最基本的功能。实现符号名与具体物理地址的转换，其主要环节是查目录。所以，文件目录的组织是文件系统研究的主要问题之一。
3．UNIX系统中，一般把文件分为 ① 、 ② 和 ③ 三种类型。 【答案】①普通文件、②目录文件、③特殊文件
【解析】普通文件既包括系统文件，也包括用户文件、库函数文件和实用程序文件。它主要指组织格式是无结构、无记录概念的字符流式文件。 目录文件则是由文件系统中的各个目录所形成的文件。
特殊文件（或设备文件）在UNIX系统中，每台设备都被看作为一个特殊文件。 4．串联文件是文件 ① 组织的方式之一，其特点是用 ② 来存放文件信息。 【答案】①物理，②非连续的物理块 【解析】串联文件结构中，每个物理块设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。
5．文件存储器一般都被分成若干大小相等的 ① ，并以它为单位进行 ② 。 【答案】①物理块，②信息交换
【解析】文件存储空间的管理是文件系统的重要任务之一，磁盘、磁带是常见的文件存储器。
6．文件存储空间管理的基本方法有 ① 、 ② 。 【答案】位示图法、空闲块链接法。 【解析】文件存储空间的管理实质上是空闲块的组织和管理问题，它包括空闲块的分配与空闲块的回收等问题，这就要求对文件存储空间的空闲块进行有效的组织和管理。
7．目录文件是由 ① 组成的，文件系统利用 ② 完成“按名存取”和对文件信息的共享和保护。
【答案】①文件说明，②目录文件
7 0 1 2 2 3 3 4 4 4 0 0 0 1 2 2 2 7 7 7 0 1 1 2 2 3 3 3 4 4 4 0 1 1 1 2 2 7 0 0 1 1 2 2 2 3 3 3 4 0 0 0 1 1 7 7 0 0 1 1 1 2 2 2 3 4 4 4 0 0 7 0 1 2 3 4 即F=10（次缺页） 【解析】从文件管理的角度看，一个文件包括两部分：文件说明和文件体。文件说明又称为文件控制块，它至少包括文件名和文件在文件存储器上的物理地址。这样一些文件说明就组成了目录文件。目录文件是实现按名存取的关键。
8．单级（一级）文件目录不能解决 的问题。多用户系统所用的文件目录结构至少应是二级文件目录。 【答案】文件重名
【解析】因为单级文件目录表中，各文件说明项处于平等地位，只能按连续结构或顺序结构存放，因此，文件名与文件必须—一对应。如果两个不同的文件重名，则系统将把它们视为同一文件。在二级文件目录结构中，各文件的说明信息被组织成目录文件，且以用户为单位把各自的文件说明划分为不同的组，而把不同的、组名有关的存取控制信息存放在用户的主目录的目录项中。
9．大多数文件系统为了进行有效的管理，为用户提供了两种特殊操作，即在使用文件前应先 ① ，文件使用完应 ② 。
【答案】①打开文件，②关闭文件
【解析】打开文件就是把该文件有关的目录表复制到内存中约定的区域，使用户能实现按名存取。所谓关闭文件，就是当用户宣布这个文件当前不再使用时，系统将此文件在内存中的相应的目录表删除，因而也就断开了用户与这个文件的联系。
10．对于索引结构的文件，其索引表中主要应包含 ① 和 ② 两项内容。 【答案】①记录号、②该记录存放地址
【解析】索引结构的文件，其索引表中主要应包含“记录号”和“该记录存放地址”两项内容，对这种结构的文件既可按顺序访问，又可按随机方式访问。
11．对磁盘上一个物理块的访问要提供三个参数，分别是 ① ， ② 和 ③ 。
【答案】①柱面号、②磁头号、③扇区号
【解析】对磁盘上一个物理块的访问要提供：柱面号、磁头号、扇区号三个参数，磁盘驱动器可按参数完成对物理块的定位。
12．文件的物理存储结构有三种方式，即 ① ， ② 和 ③ 。 【答案】①顺序文件、②链接文件、③索引文件
【解析】顺序文件、链接文件适合顺序访问，而索引文件既适合顺序访问又适合随机访问。
二、单项选择题
1．在文件系统中，用户以 方式直接使用外存。 （A）逻辑地址 （B）物理地址 （C）名字空间 （D）虚拟地址 【答案】（C）
【解析】用户给出文件名，文件系统根据文件名找到在外存的地址。 2．根据文件的逻辑结构，文件可以分为 和 两类。 （A）字符串文件/页面文件 （B）记录式文件/流式文件 （C）索引文件/串联文件 （D）顺序文件/索引文件 【答案】（B）
3．文件信息的逻辑块号到物理块号的变换是由 决定的。 （A）逻辑结构 （B）页表 （C）物理结构 （D）分配算法 【答案】（C） 【解析】文件的物理结构是指文件在存储设备上的存放方法。它决定了文件信息在存储设备上的存储位置，从而也决定了逻辑地址到物理地址的变换。 4．文件由 a 组成，磁带上的文件一般只能 b ，磁盘上的文件以 c 为单位读写，使用文件前必须 d 文件，使用完毕后应该 e 文件。则a、c可能是 。 ①数组 ②块 ③记录 ④磁盘 ⑤柱面 b可能是
①顺序存取 ②随机存取 ③以字节为单位存取 ④直接存取 d、e可能是
①命名 ②删除 ③打开 ④关闭 ⑤复制 ⑥卸下 【答案】a：③，b：①，c：②，d：③，e：④
【解析】文件是一组赋名的相关的字符流的集合，或是相关联记录的集合。磁带是一种顺序存取设备，它适合的存取方法是顺序存取，而磁盘是一种可以随机访问的设备。 5．文件系统实现按名存取主要是通过 来实现的。 （A）查找位示图 （B）查找文件目录 （C）查找作业表 （D）内存地址转换 【答案】（B） 【解析】为了有效地利用文件存储空间，以及迅速准确地完成文件名到文件物理块的转换，必须把文件名及其结构信息等按一定的组织结构排列，以方便文件的搜索。文件名中对该文件实施管理的控制信息称为该文件的文件说明，并把一个文件说明按一定的逻辑结构存放到物理存储块的一个表目中。利用文件说明信息，可以完成对文件的创建、检索以及维护。我们把一个文件的文件说明称为该文件的目录项，每个文件都有其目录项，它们共同组成文件目录。
6．文件系统采用二级文件目录，主要是为 。 （A）缩短访问存储器的时间 （B）实现文件共享
（C）节省内存空间 （D）解决不同用户间文件命名冲突 【答案】（D）
【解析】在二级文件目录中，各文件的说明信息被组织成目录文件，且以用户为单位把各自的文件说明划分为不同的组。这样，不同的用户可以使用相同的文件名，从而解决了文件的重名问题。
7．磁盘上的文件是以 为单位读写的。 （A）块 （B）记录 （C）区段 （D）页面 【答案】（A）
【解析】磁盘是一种块设备，通常每一块的容量是512Byte，对磁盘上的文件是以块为单位访问的。
8．文件索引表的主要内容包括关键字（记录号）和 。 （A）内存绝对地址 （B）记录相对位置 （C）记录所在的磁盘地址 （D）记录逻辑地址 【答案】（C）
【解析】索引结构的文件，其索引表中主要应包含“记录号”和“该记录存放的磁盘地址”两项内容，对这种结构的文件既可按顺序访问，又可按随机方式访问。 三、多项选择题
1．文件系统应具有的功能包括_________。
（A）实现“按名存取”外存上的文件 （B）分配文件的存储空间 （C）实现文件目录管理
（D）提供合适的存取方法以适应各种不同的应用 （E）实现文件的共享、保护和保密
【答案】ABCDE
【解析】从用户角度看，文件系统主要是实现“按名存取”。实际上文件系统应具有如下功能：
（1）实现从逻辑文件到物理文件间的转换，即“按名存取”外存上的文件。 （2）分配文件的存储空间。
（3）建立文件目录。文件目录是实现按名存取的有效手段，也是保证文件安全的机构。 （4）提供合适的存取方法以适应各种不同的应用。
（5）实现文件的共享、保护和保密。不同用户能在系统的控制下共享其他用户的文件。