第一题

1. 动态内存分配需要对内存分区进行管理，一般使用位图和空闲链表两种方法。128MB的内存以n字节为单元分配，对于链表，假设内存中数据段和空闲区交替排列，长度均为64KB。并假设链表中的每个节点需要记录32位的内存地址信息、16位长度信息和16位下一节点域信息。这两种方法分别需要多少字节的存储空间？哪种方法更好？

内存：$128MB = 2^{27}B$

  • 位图法（一个位来表示其状态（空闲或已分配））

储存空间：$\frac{2^{27}}{n*8}B$

  • 链表法（每个空闲区都有一个节点来记录信息）

数据段和空闲区个数：$\frac{2^{27}}{2^{16}*2}=2^{10}$

储存空间：$2^{10}*2^3=2^{13}B$

两种方法需在不同要求下进行选择，没有绝对的更好。

位图法：

  • 时间成本低：操作简单，直接修改其位图值即可

  • 空间成本固定：不依赖于内存中的程序数量

  • 没有容错能力：如果一个分配单元为1，不能肯定应该为1还是因错误变成1。

空闲链表法：

  • 空间成本：取决于程序的数量。
  • 时间成本：链表扫描通常速度较慢，还要进行链表项的插入、删除和修改。
  • 有一定容错能力：因为链表有被占空间和闲置空间的表项，可以相互验证。

第二题

2.在一个交换系统中，按内存地址排列的空闲区大小是: 10KB、4KB、20KB、18KB、7KB、9KB、12KB和15KB。对于连续的段请求：12KB、10KB、9KB。使用FirstFit、BestFit、WorstFit和NextFit将找出哪些空闲区？

微信图片_20240403144435

第三题

3.解释逻辑地址、物理地址、地址映射，并举例说明。

逻辑地址：程序在编译和链接阶段所生成的地址，可以通过该地址在页表中得到物理地址。其代表程序中的指令和数据在逻辑上的位置。

物理地址：内存单元中实际存在的位置，用于在物理内存中定位数据和指令。每个物理地址唯一地标识内存中的一个字节单元，确保CPU可以正确地访问和操作这些单元。

地址映射：由于逻辑地址和物理地址之间存在差异，因此需要进行地址映射。地址变换结构通过访问页表结构，将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址的过程。当程序装入内存时，操作系统会为该程序分配一个合适的内存空间。由于程序的逻辑地址与分配到内存的物理地址不一致，而CPU执行指令时是按物理地址进行的，所以需要进行地址转换。

举例说明：

image-20240402125347902

第四题

4.解释页式（段式）存储管理中为什么要设置页（段）表和快表，简述页式（段式）地址转换过程。

页式存储管理

在页式存储管理中，主存被分成大小相等的若干块，同时程序逻辑地址也分成与块大小一致的若干页。这样，作业的信息可以按页面为单位放入主存，并且可以不连续存放。

页表的作用：

  • 页表的主要作用是记录逻辑地址中的页号与主存中块号的对应关系。由于作业的信息可能不连续地存放在主存的不同块中，因此需要一个机制来跟踪每一页在物理内存中的位置。页表就是这样一个机制，它为每个逻辑页号提供了对应的物理块号。

快表的作用：

  • 当CPU需要访问某个逻辑地址时，首先需要查找页表以获取对应的物理地址。然而，直接访问主存中的页表可能会导致较长的延迟，因为主存的访问速度相对较慢。为了提高地址转换的速度，引入了快表（也称为TLB）。
  • 快表是页表的一个缓存，它存储了最近访问过的页表项。当CPU需要访问某个逻辑地址时，首先会检查快表中是否有对应的页表项。如果找到，CPU就可以直接获取物理地址，无需访问主存中的页表，从而大大减少了地址转换的延迟。

页式地址转换过程：

  1. CPU接收逻辑地址：CPU接收到一个逻辑地址，这个地址通常包括页号和页内偏移量两部分。
  2. 检查快表（TLB）：CPU首先检查快表（TLB），查看是否有该逻辑页面对应的物理页面信息。
  3. 快表命中：如果快表中存在该逻辑页面的页表项，CPU直接从快表中获取物理页面的帧号（物理地址），并结合页内偏移量形成最终的物理地址，然后进行访存操作。
  4. 快表未命中：如果快表中不存在该逻辑页面的页表项，CPU需要访问主存中的页表。此时，CPU根据页表的基址寄存器和页号，计算出页表在主存中的位置。
  5. 访问主存中的页表：CPU读取主存中对应位置的页表项。页表项中包含了逻辑页面到物理页面的映射信息，即物理页面的帧号。
  6. 检查页表项有效性：在读取页表项后，CPU需要检查该页表项是否有效。这可能涉及到检查页表项中的标志位，比如是否存在（存在位）、是否可读/写/执行（保护位）等。
  7. 页表项不存在：如果主存中不存在对应的页表项（可能是因为该页面尚未被分配物理内存，或者发生了页面错误），CPU会触发一个页面错误异常。操作系统会捕获这个异常，并根据其页面置换算法选择一个物理页面来替换，或者为新的页面分配一个物理页面。然后，操作系统会更新页表，并将新的页表项写回主存。之后，CPU会重新尝试地址转换。
  8. 页表项有效：如果页表项有效，CPU将页表项中的物理帧号与页内偏移量组合，形成最终的物理地址。
  9. 缓存页表项到快表：为了提高后续地址转换的速度，CPU通常会将新访问的页表项缓存到快表中（如果快表未满或该页表项未被替换）。
  10. 进行访存操作：使用最终形成的物理地址，CPU执行访存操作，读取或写入数据。

段式存储管理

在段式存储管理中，程序的逻辑地址空间被划分为若干个段，每个段包含了一组逻辑上相关的信息。每一段都有自己的段名（或段号）和长度，并且可以独立地占用主存空间。

段表的作用：

  • 段表用于记录每个段的起始地址、长度和存储保护等信息。当CPU需要访问某个逻辑地址时，它首先需要根据段号在段表中查找该段在物理内存中的起始地址和长度。这样，CPU就能确定逻辑地址所属的段以及该段在物理内存中的位置。

地址转换过程（以段页式存储管理为例）：

  1. CPU接收逻辑地址：CPU接收到一个逻辑地址，该地址由段号、段内页号以及页内偏移量三部分组成。
  2. 检查段表：CPU首先根据段号在段表中查找对应的段表项。段表通常存放在主存中，并由段表基址寄存器和段表长度寄存器来确定其位置和大小。
  3. 段表项有效性检查：CPU检查找到的段表项是否有效，包括检查段是否存在（存在位）、段的长度是否足够（长度位）、以及段的保护属性（如可读、可写、可执行等）。
  4. 获取段基址：如果段表项有效，CPU从段表项中获取该段的基址，即该段在物理内存中的起始地址。
  5. 计算页表地址：基于段的基址和段内页号，CPU可以计算出该页面在页表中的位置。这通常是通过将段基址与页号相乘（或者通过某种方式加上页号的偏移）来完成的，具体取决于页表的组织方式。
  6. 检查页表：CPU读取计算出的页表地址处的页表项。页表项中包含了逻辑页面到物理页面的映射信息，即物理页面的帧号。
  7. 页表项有效性检查：与段表项类似，CPU检查页表项的有效性，包括检查页面是否存在、页面的保护属性等。
  8. 处理页表项不存在的情况：如果页表项不存在，即页面尚未分配物理内存或发生了页面错误，CPU会触发一个页面错误异常。操作系统会捕获这个异常，并根据其页面置换算法选择一个物理页面来替换或为新页面分配物理内存。然后，操作系统更新页表和段表，将新的页表项写回主存，并通知CPU页面已准备好。CPU重新执行地址转换。
  9. 获取物理帧号：如果页表项有效，CPU从页表项中获取物理帧号。
  10. 形成物理地址：CPU将物理帧号与页内偏移量组合，形成最终的物理地址。
  11. 进行访存操作：使用最终形成的物理地址，CPU执行访存操作，读取或写入数据。

第五题

5. 叙述缺页中断的处理流程。

  1. CPU提交请求：CPU向主存储器提交请求，尝试访问某一页的内容。
  2. 检查缓存：主存储器首先检查请求的页面是否已在缓存中。
  3. 缺页中断：
  • 如果页面在缓存中，则直接访问该页的内容，无需进一步操作。
  • 如果页面不在缓存中，则发生缺页中断。
  1. 保存状态并转交控制权：
  • 操作系统保存当前进程的寄存器状态，以便在中断处理完成后恢复执行。
  • 将CPU的控制权交给操作系统，以便操作系统处理缺页中断。
  1. 页面调入与更新：
  • 操作系统根据缺页中断的页号，从辅存储器（如硬盘）中将该页调入主存储器中。
  • 操作系统更新页表，以反映新的页面与物理内存页的对应关系。

  1. 恢复控制权：操作系统将控制权交还给CPU，以便CPU继续执行程序。

  2. 重新访问：程序再次请求访问该页的内容时，由于页面已经在主存储器中，CPU可以直接访问。(重新执行中断指令)

第六题

6.假设一个机器有38位的虚拟地址和32位的物理地址。

(1) 与一级页表相比，多级页表的主要优点是什么?

(2) 如果使用二级页表，页面大小为16KB，每个页表项有4个字节。应该为虚拟地址中的第一级和第二级页表域各分配多少位？

（1）

  1. 内存利用率高：一级页表通常需要连续的大块内存来存放每个进程的页表，这在虚拟内存空间很大时会导致大量的内存浪费。而多级页表则采用分级的方式，每一级页表都相对较小，可以离散地存储在内存中，这样可以更加灵活地管理内存，避免内存的碎片化，并提高内存的利用率。
  2. 按需分配内存：一级页表在进程创建时就需要为所有可能的页表项分配空间，而无论这些页表项是否真正被使用。而多级页表则可以根据进程的实际需求来动态地分配各级页表，这不仅可以节省内存，还可以更好地适应不同进程对内存的不同需求。

（2）为虚拟地址的第一级和第二级表域各分配12位

第七题

7.假设页面的访问存在一定的周期性循环，但周期之间会随机出现一些页面的访问。例如：0,1,2…,511,431,0,1,2…511,332,0,1,2,…,511等。请思考：

(1) LRU、FIFO和Clock算法的效果如何？

(2) 如果有500个页框，能否设计一个优于LRU、FIFO和Clock的算法？

（1）

若页框数小于512，LRU，FIFO，Clock算法的均不会出现页面缺失的情况。

若页框数大于等于512，LRU，FIFO，Clock算法在周期间的页面的随机访问可能不会出现页面缺失，在每个周期内的每个页面访问除了周期间的随机访问页面可能不出现页面缺失外，其余界面均产生页面缺失。

（2）

可以。

不对0，1，2…，498这499个页面进行页面置换，当需要读入其他页面时，使用第499个页框进行页面置换，从缓存读入相应页面，该算法优于LRU、FIFO和Clock的算法。

第八题

8.一个交换系统通过紧缩技术来清理碎片。如果内存碎片和数据区域是随机分配的。而且假设读写32位内存字需要10nsec. 那么如果紧缩128MB的内存需要多久？简单起见，假设第0个字是碎片的一部分而最高位的字包含了有效的数据。

$\frac{128MB}{4}10nsec = 52^{26}nsec$