os-homework2

发表于 更新于 分类于 阅读次数：

OS homework2

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

    • 128MB=2 ^ 27B，n 字节位单元，所以 2 ^ 27/n 个单元，使用位图需 2 ^ 27/n 位，即 2 ^ 24/n 字节
    • 使用链表需 128MB/64KB=2K 个节点，每个节点 8 字节（64）位，所以 16KB=2^14 字节。
    • 当 n 小于 1024 时，链表较好；反之，位图更好。

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

    • FirstFit: 20KB,10KB,18KB
    • BestFit: 12KB,10KB,9KB
    • WorstFit: 20KB,18KB,15KB
    • NextFit: 20KB,18KB,9KB

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

    • 逻辑地址：应用程序角度看到的内存单元、储存单元、网络主机的地址。比如 CPU 访问储存单元时用的就是逻辑地址
    • 物理地址：就是实地址，它在地址总线上真实存在，使数据总线可以访问主存某个特定的储存单元的内存地址。由逻辑地址经过地址映射之后得到的就是物理地址
    • 地址映射：指将逻辑地址与物理地址相转换的过程。比如 MMU 就可以实现地址映射

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

    • 设置页表：为了便于在内存中找到每个页面所对应的页框，分页系统为每个进程分配一张页表，进程逻辑的每一页，在页表中都有一个对应的页表项。
    • 设置快表 (TLB)：应用程序的空间局部性，来提高程序的内存访问效率。
    • 页式地址转换过程：逻辑地址分为页号和偏移两个部分，根据页号找到页表中对应的页表项，由该页表项获得页框号，页框号与原逻辑地址的偏移拼接得到物理地址

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

    • 当进程执行中需访问的页面不在物理内存中时，会引发发生缺页中断（也称缺页异常），进行所需页面换入，步骤如下：
      • 陷入内核态，保存必要的信息（OS 及用户进程状态相关的信息）。（现场保护）
      • 查找出发生缺页中断的虚拟页面（进程地址空间中的页面）。这个虚拟页面的信息通常会保存在一个硬件寄存器中，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析该指令，通过分析找出发生页面中断的虚拟页面。（页面定位）
      • 检查虚拟地址的有效性及安全保护位。如果发生保护错误，则杀死该进程。（权限检查）
      • 查找一个空闲的页框（物理内存中的页面），如果没有空闲页框则需要通过页面置换算法找到一个需要换出 的页框。（新页面调入（1））
      • 如果找的页框中的内容被修改了，则需要将修改的内容保存到磁盘上。（注：此时需要将页框置为忙状态，以防页框被其它进程抢占掉）（旧页面写回）
      • 页框“干净”后，操作系统将保持在磁盘上的页面内容复制到该页框中。（新页面调入（2））
      • 步骤 5，6 会引起写磁盘调用，发生上下文切换（在等待磁盘写的过程中让其它进程运行）。
      • 当磁盘中的页面内容全部装入页框后，向 CPU 发送一个中断。操作系统更新内存中的页表项，将虚拟页面映射的页框号更新为写入的页框，并将页框标记为正常状态。（更新页表）
      • 恢复缺页中断发生前的状态，将程序指针重新指向引起缺页中断的指令。（恢复现场）
      • 程序重新执行引发缺页中断的指令，进行存储访问。（继续执行）

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

    1. 与一级页表相比，多级页表的主要优点是什么？
      • 多级页表解决了一级页表需要占用较大的连续存储空间来存储页表的问题。
    2. 如果使用二级页表，页面大小为 16KB，每个页表项有 4 个字节。应该为虚拟地址中的第一级和第二级页表域各分配多少位？
      • 页面 16KB，页内偏移需要 14 位。由于二级页表的大小和页面大小相同为 16KB，且每个页表项有 4 个字节，所以需要有一个二级页表中有 2^12 个页表项，因此二级页表域需要 12 位。则一级页表域需要 38-14-12=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 的算法？
      • 尽量把工作集装入内存。将 0-498 页面映射到固定的页框，每次只置换第 499 个页面

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

    • 每字节 10/4=2.5ns 128MB=128*220=227Byte 对每个字节既要读又要写，2*2.5*2^27=671ms