答：空闲页面链是将所有的空闲页面连成一个链，分配时可取链头的页面，去配时可将被释放的页面连入链头。此种方法适用于内存页面的分配，但对于外存页面的分配因分配和去配均需执行一次I/O传输，速度较慢。特别是当要申请多个页面时，需要进行多次I/O传输，分配效率太低。
5．在某些虚拟页式存储管理系统中，内存永远保持一个空闲页面，这样做有什么好处？
答：在内存没有空闲页架的情况下，需要按照置换算法淘汰一个内存页架，然后读入所缺页面，缺页进程一般需要等待两次I/O传输。若内存总保持一个空闲页架，当发生页故障时，所缺页面可以被立即调入内存，缺页进程只需等待一次I/O传输时间。读入后立即淘汰一个内存页面，此时可能也需执行一次I/O传输，但对缺页进程来说不需等待，因而提高了响应速度。
6．为何引入多级页表？多级页表是否影响速度？
答：早期的内存空间和进程空间都比较小，一个进程的页表长度也较小，可以在内存分配一个连续的存储区域保存进程的页表。但随着内存空间和进程空间的快速增长，页表越来越大，单级页表的存放遇到困难。 例如: 对于长度为232的逻辑地址空间，页面长度定义为212(4kB),则一个进程最多可以拥有220个页面，也就是说系统需要提供长度为220的连续页表存储区，这是困难的。 为此常将页表分为多级进行存放，例如对于上述例子，将220分为210′210两级，一级称为外页表，另一级称为内页表，此时外页表和内页表的长度都在210以内。可以很自然地把二级页表扩展为多级页表．显然，多级页表会降低地址映射的速度，但通过快表仍可以将效率保持在合理的范畴内．例如对于四级页表，假定快表的命中率为98%，快表与内存的访问时间分别为20(ns)和100(ns)，有效访问时间为： EAT= 98%′(20+100)+2%′(20+500) = 128(ns) 额外的开销是（128-100）=28ns。
7．与传统页表相比，倒置页表有什么优势？
答：传统页表是面向进程虚拟空间的，即对应进程的每个逻辑页面设置一个表项，当进程的地址空间很大时，页表需占用很多的存储空间，造成浪费。与经典页表不同，反置页表是面向内存物理页架的，即对应内存的每个物理页架设置一个表项，表项的序号就是物理页架号f，表项的内容则为进程标识pid与逻辑页号p的有序对。系统只需设置一个反置页表，为所有进程所共用。
8．允许进程空间逻辑页号不连续带来的好处是什么？
答：可以给同一进程内的多个线程预留足够的栈空间，而又不浪费实际内存页架。
9．比较段式存储管理与页式存储管理的优点和缺点．
答：页式存储管理优缺点：(1)静态等长存储分配简单，有效地解决了内存碎片问题；(2)共享和保护不够方便。段式存储管理优缺点：(1)动态异长存储分配复杂，存在碎片问题；(2)共享与保护方便；(3)可以实现动态链接和动态扩展。
36
10．举例说明段长动态增长的实际意义．
答：允许段长动态增长对于那些需要不断增加或改变新数据或子程序的段来说很有好处。例如，分配给进程的栈空间大小，通常预先无法准确估计，若分配过少可能不够用，分配过多则造成浪费。在栈可以动态增长的情况下，系统开始可以为进程分配一个基本长度的栈空间，这个长度浪费很小。若进程运行时发生栈溢出，通过中断可以进行动态扩展。
11．在段式存储管理中，段的长度可否大于内存的长度？在段页式存储管理中呢？
答：在段式存储管理中，段的长度不能大于内存的长度，因为一个独立的段占用一段连续的内存空间，内存分配是以段为单位进行的，如果一个段的长度大于内存的长度，那么该段将无法调入内存。在段页式存储管理中，段的长度可以大于内存的长度，因为内存分配的单位是页，一个段内逻辑上连续的页面，可以分配到不连续的内存页面中，不要求一个段的所有逻辑页都进入内存。
12．共享段表的用途何在？
答：共享段表的用途主要有如下两个：(1)用来寻找共享段：根据进程首次访问某段的名称在共享段表中查找，可以得知该段是否已在内存；(2)确保一个共享段只有一组描述信息：共享段的地址、长度等信息在共享段表中仅记录一次，防止在多个进程段表中重复登记所带来的维护困难。共享段表用来实现段的共享和保护，该表中记录所有共享段。多个进程共享同一段时，这些进程段表中的相应表目指向共享段表中的同一个表目，共享段表形式如下。 段名 共享记数 段长度 段首址 其它 表中“段名”用来识别和查找共享段，“共享计数”记录当前有多少个进程正在使用该段，当其值为0时为空闲表项。当一个共享段最初被使用时，它被登记在共享段表中，共享计数置为1。以后其它进程访问此段时，其共享计数加1。当一个进程结束对于某一共享段的访问时，其共享计数减1，当减到0时表示没有进程再使用该段，可释放所占用的存储空间。
13．具有两级页表的页式存储管理与段页式存储管理有何差别？
答：具有两级页表的页式存储管理的地址空间依然是一维的，两级页的划分对于进程来说都是透明的。而段页式存储管理的地址空间是二维的，段的划分用户能感觉到。
14．何谓请调？何谓预调？为何在预调系统中必须辅以请调？
答：所谓请调是当页故障发生时进行调度，即当被访问页面不在内存时由动态调页系统将其调入内存。显然，采用纯请调策略，被移入内存的页面一定会被用到，即不会发生无意义的页面调度。但是，请调也有一个缺点：从缺页中断发生到所需页面被调入内存，这期间对应的进程必须等待，如此将会影响进程的推进速度。预调也称先行调度。是当页故障发生前进行调度，即当一个页面即将被访问之前就由动态调页系统将其调入内存。易见，预调可以节省进程因页故障而等待的时间。预调通常根据程序的顺序行为特性而作出：如某进程当前正访问第12页，则接下来很可能会访问第13页、第14页，此时可将第13页甚至第14页预先调入内存。这样当该进程访问第13页以至第14页时它们已经在内存中，不会发生缺页故
37
障，从而提高进程的推进速度。预调不一定是百分之百准确的：由于程序中存在转移语句，第13页用完后可能需要访问第10页，而该页目前可能不在内存。也就是说，预先调入的页面可能有的未被用到，预先未调入的页面可能有的会被用到。当访问到预先未调入内存的页面时，仍会发生缺页中断。因而，在采用预调的系统中，必须辅以请调的功能。 15．段的动态连接给共享带来什么问题？如何解决？
答：动态连接提高了系统的效率，但也带来一些问题，主要是对于段共享的影响。代码段共享的必要条件是该段在运行过程中不修改自身，即要求是“纯代码”(pure code)，而动态连接需要修改连接字，这与共享的要求相矛盾。解决这个问题的一种方法是将代码段分为“纯段”和“杂段”两个部分，即将连接字等可修改的内容存放在“杂段”中，而将其它内容放在“纯段”中。“杂段”不共享，“纯段”可共享。
16．在虚拟段页式存储管理中，考虑段的共享与段长度的动态变化，连接中断如何处理？
答：由段名查本进程的段名—段号对照表及共享段表，经判断可分为如下三种情形: (1) 所有进程都未连接过（共享段表、段名-段号对照表均无）: 查文件目录找到该段； 为该段建立页表，将该段由文件全部读入swap空间，部分读入内存，填写页表；为该段分配段号，填写段名-段号对照表；如该段可共享，填写共享段表，共享记数置1；填写段表；根据段号及段内地址形成无障碍指示位的一般间接地址。(2) 其它进程连接过但本进程未连接过(共享段表有，段名-段号对照表无): 为该段分配段号；填写段名-段号对照表，填写段表(指向共享段表)，共享段表中共享记数加1；根据段号及段内地址形成无障碍指示位的一般间接地址。(3) 本进程已连接过(共享段表无，段名-段号对照表有): 根据段号及段内地址形成无障碍指示位的一般间接地址。这里，段内地址由两部分构成，即逻辑页号和页内地址。
17．伙伴堆内存分配算法的特点是将连续的物理页架分给进程，这样做的动机是什么？为
何能提高效率？
答：尽管从地址映射的角度来看，页式存储管理并不要求一个进程所分得的页面在物理上连续，但DMA传输是在没有地址映射的条件下进行的，因而跨页的DMA传输要求页面在物理上是连续的，而连续物理页面分配要求所带来的问题是可能产生外碎片(external
fragmentation)。伙伴算法是针对外碎片问题而提出的一种稳定、高效的分配策略。它将所有空闲页面分为10个块组，块组编号为i (i=0~9)，块组i中记载长度为2i个页面的连续区域，即第1组中块的大小均为20(1页)，第2组中块的大小均为21(2页)，?，第10组中块的大小均为29(512页)。这样每一组中块的大小是相同的，并且勾成一个双向链表。 对于长度为128页的请求，在第8组中取一块。若第8组已空，取第9组中一块，分配其中的128页，并将剩余的128页记入第8组。若第9组也空，取第10组中一块，进行两次分割，分配128块，将剩余的128块和256块分别记入第8组和第9组。
释放是上述操作的逆过程，此时需要考虑与伙伴的合并，两个块为伙伴的条件是：(1)两个块的大小相同，如b个页面；(2)两个块的物理地址连续；(3)位于后面块的最后页面编号必
38
须是2b的整数倍。与传统的非连续多页面分配算法相比，Buddy heap算法具有速度快的明显特点，同时解决了外碎片问题。 七、 文件系统习题及解答:
1．举例说明何种文件长度是固定不变的，何种文件长度是动态变化的。
答：某些系统可执行程序，如shell、vi的长度通常是固定不变的；而用户正在编辑的文本文件或源代码文件的长度通常是动态变化的。
2．比较文件名、文件号、文件描述符之间的关系。
答：文件名是文件的外部名字，通常是一个符号名(字符串)，同一文件可以有多个文件名(如通过link)。文件号是文件的内部名字，通常是一个整数，文件号与文件具有一对一的关系。文件描述符是文件打开时返回的整数(入口地址)，对应用户打开文件表(如UNIX中的u_ofile)中的一个入口。同一文件可以被多个用户同时打开，此时返回的文件描述符一般不同。同一文件也可以被同一用户多次打开，每次打开时返回的文件描述符一般也不同。
3．将文件控制块分为两部分有何好处？此时目录项中包含那些成分？
答：将文件的FCB划分为次部和主部两部分具有如下两个主要的优点:
(1) 提高查找速度：查找文件时，需用欲查找的文件名与文件目录中的文件名字相比较。 由于文件目录是存于外存的，比较时需要将其以块为单位读入内存。由于一个FCB包括许多信息，一个外存块中所能保存的FCB个数较少，这样查找速度较慢。将FCB分为两部分之后，文件目录中仅保存FCB的次部，一个外存块中可容纳较多的FCB，从而大大地提高了文件的检索速度。
(2) 实现文件连接：所谓连接就是给文件起多个名字，这些名字都是路径名，可为不同的用户所使用。次部仅包括一个文件名字和一个标识文件主部的文件号，主部则包括除文件名字之外的所有信息和一个标识该主部与多少个次部相对应的连接计数。 当连接计数的值为0时，表示一个空闲未用的FCB主部。
4．文件在使用之前为何需要打开？多个进程共享同一文件时，其FCB为何在内存中只能
保持一个副本？
答：当一个文件被打开使用时，其FCB中的信息需要经常地被访问。 如果每次访问FCB都去读写外存，则速度会大大地降低。为了解决这一问题，在内存中设立系统打开文件表，将文件对应的FCB读入内存并保存在该表中,以备需要时使用由于文件是可共享的，多个进程可能会同时打开同一文件，而其打开方式可能是不同的，当前的读写位置通常也是不一样的。为了防止信息冗余，将这些个性化信息记录在另外一个表中，该表称作用户打开文件表，每个进程有一个，表中包含以下内容：
文件描述符 打开方式 读写指针 系统打开文件表入口 39
表中的系统打开文件表入口为一指针，指向该文件FCB 在系统打开文件表中的入口地址。当多个进程共用同一个文件时，不同进程的用户打开文件表中会有相同的系统打开文件表入口。这样做的好处是FCB在内存中只有一个副本，当任何一个进程对文件的操作导致FCB内容变化时，内存中的FCB内容及时得到更新，当所有进程都不再需要该文件时，即当最后一个进程关闭该文件时，才将FCB的内容回写到外存上。这样做可以减少I/O交换次数，提高系统效率。
5．使用文件描述符存取打开文件与直接使用文件名相比有何优点？
答：首先，文件名是一个字符串，操作速度慢且占空间大，而文件描述符为一整数，其处理效率明显高于字符串。其次，文件被打开后其控制信息(FCB)被缓冲到内存系统空间，文件描述符作为用户打开文件表中的入口地址直接与内存FCB建立起联系，而文件名无法做到这一点。
6．用户打开文件表中包含那些内容？为何不能将其合并到系统打开表中？
答：用户打开文件表中包含以下内容：
文件描述符 打开方式 读写指针 系统打开文件表入口 由于文件是可共享的，多个进程可能会同时打开同一文件，而其打开方式可能是不同的，当前的读写位置通常也是不一样的。如果将这些信息合并到系统打开文件表中，就会导致一个共享文件占用多个系统打开文件表表目，这些表目的大部分内容是重复的。当一个进程对文件的操作导致FCB内容变化时，该进程关闭文件时就要将FCB回写到外存。增加了内外存传输的次数，也容易导致FCB内容的不一致。因此，通常将打开方式和读写指针记录在另外一个表，即用户打开文件表中。
7．说明对于如下文件操作命令，文件管理系统如何进行合法性检查。
（1）打开文件（2）读写文件（3）删除文件
答：（1）打开文件 ：根据打开方式、共享说明和用户身份检查访问合法性；（2）读写文件：根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性；（3）删除文件：根据共享说明和用户身份检查访问合法性。
8．采用文件连接技术后，文件名与文件是否一对一？文件号与文件是否一对一？文件描
述符与文件是否一对一？
答：采用文件连接技术后，文件名与文件是多对一；文件号与文件是一对一；文件描述符与文件是多对一。
9．对于Hash文件结构，回答下述顺序探查法解决冲突方面的问题。
(1) 对于一个非空闲记录来说，其键值key的杂凑值hash(key)是否一定与该记录地址addr相同？
40