点此查看作业源文件

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

  • 若使用位图方法：
$$单元数 = \frac{128MB}{nB} = \frac{2^{27}}{n}块$$$$所需存储空间 = \frac{2^{27}}{n}b = \frac{16}{n}MB$$
  • 若使用空闲链表方法：
$$段数=\frac{128MB}{64KB+64KB} = 2^{10}段$$$$所需存储空间 = 2^{10} \times (32 + 16 + 16)b = 8KB$$
  • 哪种方法更好：
    • 当n<2048时，空闲链表所需存储空间更小，空闲链表方法更好；
    • 当n>2048时，位图所需存储空间更小，位图方法更好。

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

段请求FirstFitBestFitWorstFitNextFit
12KB20KB12KB20KB20KB
10KB10KB10KB18KB18KB
9KB18KB9KB15KB9KB

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

  1. 逻辑地址（Logical Address）： 逻辑地址是程序运行时由 CPU 生成的地址，也称为虚拟地址。用户进程只能访问逻辑地址，不能直接访问物理内存。
    例如某程序访问地址 0x1234，但该地址只是进程的逻辑地址空间中的一部分。

  2. 物理地址（Physical Address）：
    物理地址是实际存在于内存（RAM）中的地址，由操作系统和硬件管理。
    例子： 逻辑地址 0x1234 可能被映射到物理内存的 0xABCD1234。

  3. 地址映射（Address Mapping）：
    地址映射是逻辑地址到物理地址的转换过程，通常由MMU通过分页、分段、段页结合等方式完成。 例子： 在分页系统中，逻辑地址 0x1234 可能属于页号2，页内偏移 0x034，MMU 通过页表找到物理页框5，映射后的物理地址为 0x5034。

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

  1. 为什么要设置页（段）表和快表

    • 页表（段表）：用于记录逻辑地址到物理地址的映射关系，存储完整的映射信息，保证进程可以正确访问物理内存。
    • 快表：是一种高速缓存，用于存储最近访问的页（段）表项，加速地址转换，提高地址转换效率，减少访问内存的开销。

  2. 页式存储管理的地址转换过程

    1. CPU 生成逻辑地址，包含页号和页内偏移。
    2. 查询 TLB，如果页号在 TLB 中，则直接获取对应的物理页框号，得到物理地址。
    3. 若TLB 未命中（缺页表项），需要访问页表，通过页号查找对应的物理页框号。
    4. 组合物理页框号和页内偏移，形成物理地址，访问数据。
    5. 更新 TLB（如果 TLB 未命中，则将新查找的页表项加入 TLB）。

  3. 段式存储管理的地址转换过程

    1. CPU 生成逻辑地址，包含段号和段内偏移。
    2. 查询 TLB，如果段号在 TLB 中，则直接获取段的基址，计算物理地址。
    3. 若TLB 未命中，访问段表，查找段号对应的段基址和段界限。
    4. 检查越界，如果段内偏移>段界限，发生段越界异常，否则继续计算。
    5. 物理地址 = 段基址 + 段内偏移，然后访问数据。
    6. 更新 TLB（如果 TLB 未命中，则将新的段表项加入 TLB）。

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

缺页中断发生在进程访问的页面不在内存时，系统需要从外存加载该页面到内存。处理流程如下：

  1. 产生缺页中断

    • 进程访问某个逻辑地址，CPU 通过页表查找对应的物理页框。
    • 如果该页表项无效（页不在内存），则触发缺页中断。

  2. 保存进程状态

    • CPU 保存当前进程的上下文，包括程序计数器（PC）和寄存器等，确保中断后能恢复执行。

  3. 操作系统处理缺页

    • 查找页表：操作系统检查该页是否有效。
      • 有效但不在内存 → 继续处理。
      • 非法访问 → 触发异常（如段错误），终止进程。
    • 选择物理页框：
      • 若有空闲页框，直接使用。
      • 若内存已满，使用页面置换算法（如 FIFO、LRU）淘汰一个旧页面。

  4. 读取页面到内存

    • 从外存（如磁盘）读取所需页面，拷贝到选定的物理页框。

  5. 更新页表和 TLB

    • 修改页表项，标记该页已在内存，并更新页框号。
    • 若该页表项在 TLB（快表）中，需更新或清除 TLB 旧项，保证地址转换正确。

  6. 恢复进程执行

    • 恢复进程上下文，重新执行触发缺页的指令。
    • 由于该页已加载到内存，不会再次触发缺页中断。

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

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

  • 空间利用率高。多级页表只在需要时分配低层页表，从而避免为整个虚拟地址空间都预留大量连续的页表空间，节省内存空间。

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

页面大小为 16KB，即

$$16\,\text{KB} = 16 \times 1024 = 2^{14}\,\text{字节}$$

因此页内偏移需要 14 位，虚拟地址结构如下：

$$\underbrace{\text{第一级页表域}}_{x\,\text{位}}\,\,\underbrace{\text{第二级页表域}}_{y\,\text{位}}\,\,\underbrace{\text{页内偏移}}_{14\,\text{位}}$$

虚拟地址为38位，因此$x + y + 14 = 38位$，所以$x + y = 24,\text{位}$。

每个页表项为4B，页表页的大小与页面大小相同，即16KB。一个页表页能容纳的页表项个数为

$$\frac{16\,\text{KB}}{4\,\text{B}} = 4096 = 2^{12}\,\text{项}$$

因此第二级页表的索引域需要12位，即$y=12$。

由$x+y=24$可得$x=12$。即：

$$\underbrace{\text{第一级页表域}}_{12\,\text{位}}\,\,\underbrace{\text{第二级页表域}}_{12\,\text{位}}\,\,\underbrace{\text{页内偏移}}_{14\,\text{位}}$$

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

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

如果物理页框数不足512个，三种算法会发生相同的几乎全部缺页问题。

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

其中499个页框对应存储0-498页，第500个页框用于置换。

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

$$128MB=\frac{128\times 2^{23}b}{32b/word} = 2^{25}words$$$$T=2^{25}words \times (10ns/word + 10ns/word) = 6.711\times 10^8ns = 0.6711s$$

需要约$0.6711s$。