例1在一个有1MB程序可用内存的系统中,如果采用伙伴系统来进行管理分配内存,请画出下列每次事件出现后的内存使用情况图(A代表进程A,128K等代表物理起始地址，虚线用于划分每k间隔的内存起始位置，内存使用情况请画实线准确分割) 

进程行为  0k      128k    256k            512k                        1024k

答：在动态分区分配方式中可用的分配算法有4种：

①首次适应算法(PP)  ②循环首次适应算法。

③最佳适应算法。    ④最坏适应算法。

例3在动态分区分配方式中,当回收内存时，可能出现哪几种情况?应怎样处理?

答：有4种情况。

①回收区与前一个分区相邻接。此时将回收区与前一个分区合并，将前一分区大小加上回收区的大小。

②回收区与后一个分区相邻接。此时将回收区与后一个分区合并，将后一个回收区的首地址改为回收区的首地址，其大小是二者之和。

③回收区与前后各一个分区相邻接。将回收区与这两个分区合并，其首地址保留为前一个分区的首地址，大小是三者大小之和，而且将后一个分区的表项删除。

④回收区不与任何分区相邻接。为回收区分配一个新表项，将回收区的首地址和大小填入其中。

例4 段页式存储系统中，为了获得一条指令或数据，需几次访问内存？分别是那几次？

答：在段页式系统中，为了获得一条指令或数据，需三次访问内存。第一次访问，是访问内存中的段表，从中取得页表始址；第二次访问，是访问内存中的页表，从中取出逻辑页面对应的内存物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问，才是真正从第二次访问所得的地址中，取出指令或数据。

例5 为什么在分页和分段管理下取一条指令或一个操作数通常需两次访存？如何解决这一问题？

答：这是因为用于地址变换的页表或段表也是存放在内存的，为了将CPU给出的逻辑地址变成物理地址，首先就要访问内存的页表和段表，然后，根据形成的物理地址再取指令或数据，这就要两次访存。解决这一问题的办法是提供一个称之为“快表”的硬件，用以存放当前运行进程的页表或段表的部分内容，“快表”的访问时间很快，因此可以节约访问页表和段表的时间。 

例6在具有快表的段页式存储管理方式中，如何实现地址变换?

答：系统将有效地址(逻辑地址)中的页号与页表寄存器中的内容比较，若页号太大，表示访问越界，于是产生越界中断；若未出现越界情况，地址变换机构自动地将页号P送入高速缓存，再确定所需要的页是否在快表(高速缓存)中。若在则直接读出该页所对应的物理块号，并送物理地址寄存器；若在快表中未找到对应的页表项，需再访问内存中页表，找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个老的、已被认为不再需要的页表项。与此同时，再将有效地址寄存器中的页内地址直接送入物理地址寄存器，从而完成了从有效地址(逻辑地址)到物理地址的转换。

例7实现虚拟存储器系统必须提供哪些硬件和软件？

例8 你学过的存储管理方法有那些？其中那些可以实现虚拟存储器，为什么？

答：单一分区、固定分区、可变分区、基本分页、基本分段、基本段页、请求基本分页、请求基本分段、请求基本段页

其中请求基本分页、请求基本分段、请求基本段页可以实现虚拟存储器，因为它们都可以在程序的一部分装入内存时就可以运行。

CHP5

例1. 试说明Spooling系统的组成。

答：Spooling系统主要由4部分组成。

①输出／输出井。这是在磁盘上开辟的两个大空间，一个是输入井，用来收容输入设备上的数据(模拟脱机输入的磁盘)；另一个是输出井，用来收容用户进程的输出数据(模拟脱机输出的磁盘)。

②输入缓冲区和输出缓冲区。这是内存中开辟的两个缓冲区，一个是输入缓冲区，暂存输入设备传送来的数据，以后再传送到输入井；另一个是输出缓冲区，暂存输出井送来的数据，以后传送到输出设备。

③输入进程和输出进程。输入进程实现的是收容输入和提取输入。在收容输入时，负责将输入设备的数据通过内存输入缓冲区转存到磁盘的输入井中；提取输入时，负责将磁盘输入井的数据送入内存用户区。输出进程实现的是收容输出和提取输出，过程与输入过程相反。

例2.引入缓冲的主要原因是什么?

答：引入缓冲的主要原因主要归结为以下3个方面：

    ①缓和CPU与I/O设备之间的速度不匹配问题。

    ②减少对CPU的中断频率，放宽对中断响应时间的。

    ③提高CPU和I/O设备之间的并行性。

例3我们学过的I/O控制方式有哪几种？分别适用何种场合？

答：共有四种I/O方式：

① 程序I/O方式。该方式执行一个循环程序，反复查询外设状态，如果外设“忙碌”则循环查询，直到查得外设状态为“闲置”时止。适用于机器没有中断机构的场合。

② 中断控制I/O方式。该方式在进行I/O时，CPU向控制器发出I/O命令后，由控制器控制外设操作，CPU转其他任务的处理，即，CPU与外设并行工作。当外设完成I/O后向CPU发中断信号，CPU只需花费很少的时间进行I/O的善后处理，此前毋须进行干预。该方式可适于低速外设I/O。

③ DMA（直接内存访问）方式。该方式适于高速外设I/O，一次可以在外设与内存之间传输一个或多个数据块。传输完毕后才需CPU干预。

④ 通道方式。该方式中，系统预先要将I/O的过程实现为一段通道程序，置于内存的特定位置，而后启动通道。由通道负责执行通道程序对外设进行I/O控制，CPU转其他程序运行。I/O完成后通道向CPU发中断信号，CPU花很少时间作善后处理。

例4在层次式结构的I/O软件中，通常把I/O软件组织成4个层次，请给出是那4个层次？分别的作用是什么？

例5 在进行设备分配时需要的4个数据结构是什么？它们的作用各又是什么？在进行基本的设备分配时是如何操作的？

例6 请简要描述磁盘的访问时间由那几部分构成。

CHP6

例1文件系统的模型可分为三层，试说明每一层所包含的基本内容/  画出文件系统的层次结构模型。

例2按文件的物理结构可将文件分为哪几类?并给出简要说明。

答：按物理结构可将文件划分为以下3类：

    ①顺序文件。文件中的记录被顺序地存放到连续的物理盘块中。

    ②链接文件。文件中的记录可以被存放到不连续的物理盘块中，通过物理块中的指针将物理块连接成一个链表。

③索引文件。文件中的记录可以被存放到不连续的物理盘块中，通过索引表实现记录和物理块之间的映射。

例3．什么是文件的物理结构?在文件存储器中，文件可组织成哪几种基本的物理结构? 并给出各物理结构的简要说明。

例4．文件控制块的作用是什么？目录文件与文件控制块是怎样的关系？目录结构有那几种形式？

例5．请描述成组链表法的基本原理。

Chp10

1．在UNIX System V中，当一个进程所访问的一页既不在内存又不在文件系统中时，该页面可能在什么地方?存储管理模块是如何把它调入内存的?

答：一个进程所访问的一页既不在内存又不在文件系统中时，该页面可能在对换设备上。此时由核心调用有效性错处理程序(即缺页中断处理程序)加以处理。

为从对换设备上调入该页面，核心从磁盘块描述项中找到存放该页面的对换设备和块号，然后为缺页分配一内存页，修改此进程的相应页表项，使之指向该内存页，并将页面数据表放入相应的散列队列中，再把该页从对换设备上调入内存

2. 在UNIX系统中，如何将文件的字节偏移量转换为物理地址?

答：UNIX系统将文件的字节偏移量转换为文件物理块号的过程分两步实现：

第一步：将字节偏移量转换为文件逻辑块号，及块内偏移量：

将字节偏移量除以盘块大小的字节数，其商是文件逻辑块号，余数是块内位移量。

第二步：把逻辑块号转换为文件的物理块号。其转换方法如下：

逻辑块号可知对应的文件地址是直接地址还是间接地址，若为直接地址(块号<10时)，将文件逻辑块号转换为索引节点的地址项下标，从该地址项中即可获得物理盘块号；若为一次间接寻址，即当文件块号大于或等于10且小于266时，从索引节点的一次间接项中得到一次间接的盘块号；再将计算一次间接块中的地址下标，即将文件的逻辑块号减10，从相应下标的地址项中得到物理块号；若为多次间接寻址，即当文件的逻辑块号大于或等于266而小于65802时，应采用二次间接寻址，而当逻辑块号大于或等于65802时，应采用3次间接寻址，多次间接寻址的转换方法和一次间接寻址相类似，但要多次循环。

3．如果一个盘块的大小为1KB，每个盘块号占4个字节，那么，一个进程要访问偏移量为263168字节处的数据时，需要经过几次间接寻址?  

答：对于给定的偏移量263268，其逻辑块号为：263168／1024=257

块内偏移量为：263168-1024×257=100。

因为10<257<266，所以偏移地址263268的块号在一次间接块内，故一个进程要访问偏移量为263268字节处的数据时，只需经过一次间接。

4．假定一个索引节点为128字节，指针为4字节长，而状态信息占用了68个字节。假定每块的大小为8K。问在索引节点中有多大的空间给指针?使用直接指针、间接指针、二次间接指针、三次间接指针分别可以表示多大的文件?  

答：

●由于索引节点为128B，而状态信息占用68B，用于指针的空间大小为60B。

●一次间接指针、二次间接指针和三次间接指针将占用索引节点中的3个指针项，因此直接指针项数为：60／4-3=12

◆使用直接指针时：12*8KB=96KB=98304B；即大小不超过96KB的文件使用直接指针即可表示。

◆使用一次间接指针时：8K/4=2048(即一个盘块中可以装入2048个指针项)；    2048*8KB=16MB；即大小在96KB～16MB的文件使用一次间接指针即可表示。

◆使用二次间接指针时： 2048*2048=4MB(即二次间接可以提供4M个指针项)； 4M*8KB=32G；即大小在16MB～32G的文件使用二次间接指针即可表示。

◆使用三次间接指针时：2048*2048*2048=8GB(即三次间接可以提供8G个指针项)；  8G*8KB=T；即大小在32G～T的文件使用三次间接指针即可表示。

5    UNIX进程映像由哪3部分组成？各部分的主要包含内容是什么？

答：1) 用户级上下文　　主要成分是用户程序。 

2) 寄存器上下文　　主要是由CPU中的一些寄存器的内容所组成的。

3) 系统级上下文　　可分为静态和动态两部分：

(1) 静态部分。进程表项、U区及进程区表项、系统区表项和页表。

(2) 动态部分。在包括：① 核心栈；② 若干层寄存器上下文 

6在UNIX系统中，将进程控制块(PCB)和文件控制块(FCB)各分解成哪两个部分? 为什么?

答：在UNIX系统中，将进程控制块(PCB)分解为proc结构和U区（user结构），proc结构包括进程的常用信息，常驻内存；U区（user结构）包括进程运行时所用的信息，可以调入／调出内存，其目的是节省内存空间。

在UNIX系统中，将文件控制块(FCB)分解为文件名和索引节点号组成的文件目录和由文件属性信息组成的索引节点两部分。其目的是加快检索速度，便于文件的共享。

7.  UNIX的i节点是文件内容的一部分，对吗?请说明理由。

答：在UNIX系统中，文件名与文件说明是分开存放的。由文件说明信息组成的据结构称为索引节点，而相应的文件目录则只由文件名及其索引节点号构成。   索引节点又称i节点，其中存放文件的说明信息。索引节点以静态形式存放于磁盘上，故又称为磁盘索引节点。它不是文件内容的一部分，而是用于文件管理的数据结构。

8  UNIX请求调页管理的4个数据结构是什么？它们各起什么作用？绘出它们间的关系图。

9  UNIX在将一页换出时，可分成那几种情况？分别应该如何处理这些情况？

10  UNIX文件系统中的一个未打开的文件占有那些资源？各资源的作用是什么？一个打开的文件又多占有那些资源？

11  UNIX消息机制中的数据结构有几个？它们各自的作用是什么？绘出它们间的关系图。下载本文