操作系统理论作业 2：内存管理

#作业

1. 位图与空闲链表

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

查看我当时提交的答案

位图需要 227/n2^{27}/n 位，即 224/n2^{24}/n 字节，也就是 16/n16/n MB。链表需要 16 KB。

因此，n<1n<1 KB 时链表较好；n>1n>1 KB 时位图更好；n=1n=1 KB 时二者一样。

2. 空闲分区分配算法

一个交换系统按内存地址排列的空闲区大小为 10 KB、4 KB、20 KB、18 KB、7 KB、9 KB、12 KB 和 15 KB。对于连续的 12 KB、10 KB、9 KB 段请求，First Fit、Best Fit、Worst Fit 和 Next Fit 分别会找到哪些空闲区？

查看我当时提交的答案
  • First Fit：20 KB、10 KB、18 KB。
  • Best Fit：12 KB、10 KB、9 KB。
  • Worst Fit：20 KB、18 KB、15 KB。
  • Next Fit：20 KB、18 KB、9 KB。

3. 逻辑地址、物理地址与地址映射

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

查看我当时提交的答案
  • 逻辑地址：程序在编译和运行时使用的地址。
  • 物理地址：内存上实际的硬件地址。
  • 地址映射：把逻辑地址转换为物理地址的过程。

例如，逻辑地址为 0x1234，页大小为 4 KB，则页号为 1，页内偏移为 0x234。若页表中第 1 项对应物理页框号 0x3，则它映射到物理地址 0x3234。

4. 页表、段表与快表

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

查看我当时提交的答案

页表用于把逻辑页映射到物理页框，并维护内存隔离与保护；段表用于把逻辑段映射到物理内存；快表用于加速地址转换。

页式地址转换时，先把逻辑地址拆分为页号和页内偏移，再查页表取得物理页框号，最后把物理页框号与页内偏移组合为物理地址。

5. 缺页中断

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

查看我当时提交的答案

访问的逻辑页不在内存时触发缺页中断。若地址合法，先检查物理内存有无空闲页框：有则直接使用；没有则选择一个牺牲页。随后从外存把缺失页面装入物理页框，更新页表和 TLB，再恢复执行。

6. 二级页表的划分

假设一台机器有 38 位虚拟地址和 32 位物理地址。

  1. 与一级页表相比，多级页表的主要优点是什么？
  2. 若使用二级页表，页面大小为 16 KB，每个页表项为 4 字节，虚拟地址中的第一级和第二级页表域各应分配多少位？
查看我当时提交的答案

多级页表的核心优势是节省物理内存，并支持稀疏地址空间。

第一级、第二级页表域各分配 12 位。

7. 具有周期性的页面访问

假设页面访问存在周期性循环，周期之间会随机插入一些页面。例如：0,1,2,…,511,431,0,1,2,…,511,332,0,1,2,…,511。

  1. LRU、FIFO 和 Clock 算法的效果如何？
  2. 若有 500 个页框，能否设计一个优于它们的算法？
查看我当时提交的答案

三者均无法显著区分周期性页面和随机页面，会导致较高的缺页率。

可把 0–498 号页面映射到固定页框，每次缺页只置换第 499 号页框中的页面。

8. 内存紧缩时间

一个交换系统通过紧缩清理碎片。假设内存碎片与数据区域随机分布，读写一个 32 位内存字需要 10 ns。若要紧缩 128 MB 内存，需要多久？为简化计算，假设第 0 个字属于碎片，最高地址的字包含有效数据。

查看我当时提交的答案

约 0.671 秒。

评论