Lab2 Report

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

Lab2 Report

思考题

Thinking 2.1

  • 请根据上述说明，回答问题：在编写的 C 程序中，指针变量中存储的地址是虚拟地址，还是物理地址？MIPS 汇编程序中 lw 和 sw 使用的是虚拟地址，还是物理地址？
    • 在编写的 C 程序中，指针变量中存储的地址是虚拟地址，MIPS 汇编程序中 lw 和 sw 使用的也是虚拟地址
      • 虚拟地址是由操作系统分配给程序使用的地址，程序无法访问物理地址。
      • MIPS 架构中，访问内存时使用的是虚拟地址，由硬件转换为物理地址。这种方式称为虚拟内存管理。操作系统负责将虚拟地址映射到物理地址，这样每个程序都可以访问自己的地址空间，而不会干扰其他程序的内存。

Thinking 2.2

  • 从可重用性的角度，阐述用宏来实现链表的好处。
    • 宏定义可以抽象出链表操作中的公共部分，将具体的实现细节封装在宏定义内部，并且抽象出链表元素类型为 type，实现泛型的效果，在不同元素类型的链表相关代码中都可以重用这些宏定义
  • 查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。
    • 单向链表、循环链表和双向链表在插入与删除操作上的性能差异：
      • 因为单向链表只能从前往后遍历，插入或删除节点时需要找到节点的前驱节点，需要从头开始遍历，时间复杂度为 O(n)
      • 循环链表可以从任意一个节点开始遍历，因此在插入和删除节点时只需要更新相邻节点的指针即可，时间复杂度为 O(1)
      • 双向链表在这方面更加高效，因为它既可以从前往后遍历，也可以从后往前遍历，因此在插入和删除节点时都比单向链表更加高效，时间复杂度为 O(1)

Thinking 2.3

  • 查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。
    • Page_list 由一个 *list_head 的链表构成，每个元素对应一个 list 的头节点地址，进入每个 list 中后，其中由一个 Page_LIST_entry_t pp_link 和 u_short pp_ref 构成，所以选择 C。

Thinking 2.4

  • 请阅读上面有关 R3000-TLB 的描述，从虚拟内存的实现角度，阐述 ASID 的必要性。
    • 多个进程可能通过不同的虚拟内存映射到相同的物理内存，所以在 TLB 映射时，需要添加 ASID 用以标识每个进程，当 TLB 尝试解析虚拟页码时，它对正在访问该条目的进程检查，确保当前正在运行的进程的 ASID 与与虚拟页面关联的 ASID 匹配。如果不匹配，则 TLB 将忽略该条目，而不是将其映射到物理内存中的页面，保护各个进程中的数据。
  • 请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID 段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。
    • 可容纳不同地址空间的最大数量为 64 个 > “Instead, the OS assigns a 6-bit unique code to each task’s distinct address space. Since the ASID is only 6 bits long, OS software does have to lend a hand if there are ever more than 64 address spaces in concurrent use; but it probably won’t happen too often.”

Thinking 2.5

  • tlb_invalidate 和 tlb_out 的调用关系？

    • ```c void tlb_invalidate(u_int asid, u_long va) {tlb_out(PTE_ADDR(va) | (asid << 6)); } 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36

        - tlb_invalidate 调用 tlb_out
      - 请用一句话概括 tlb_invalidate 的作用。
        - tlb_invalidate 函数就是用 tlb_out()把 asid 进程中的虚拟地址 va 对应的 tlb 页表项清空 

      - 逐行解释 tlb_out 中的汇编代码。

        ``` asm
        LEAF(tlb_out)
        .set noreorder
        mfc0    t0, CP0_ENTRYHI  #CP0_ENTRYHI 写入 t0
        mtc0    a0, CP0_ENTRYHI  #a0(传入的参数, 待清空表项的 entryhi) 写入 CP0_ENTRYHI
        nop
        /* Step 1: Use 'tlbp' to probe TLB entry */
        /* Exercise 2.8: Your code here. (1/2) */
        tlbp # 根据 EntryHi 中的 Key（包含 VPN 与 ASID），查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器（若未找到匹配项，则 Index 最高位被置 1）

        nop
        /* Step 2: Fetch the probe result from CP0.Index */
        mfc0    t1, CP0_INDEX # 表项的索引取出到 t1
        .set reorder
        bltz    t1, NO_SUCH_ENTRY # 如果最高项是 1，则表明未找到匹配项，跳到 NO_SUCH_ENTRY
        .set noreorder
        mtc0    zero, CP0_ENTRYHI    # 如果找到匹配项，则清空 CP0_ENTRYHI，CP0_ENTRYLO，为写入做准备
        mtc0    zero, CP0_ENTRYLO
        nop
        /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
        /* Exercise 2.8: Your code here. (2/2) */
        tlbwi # 以 Index 寄存器中的值为索引，将此时 EntryHi 与 EntryLo 的值写到索引指定的 TLB 表项中

        .set reorder

        NO_SUCH_ENTRY:
        mtc0    t0, CP0_ENTRYHI    #t0 写回给 CP0_ENTRYHI
        j       ra     # 跳回被调用的地方
        END(tlb_out)

Thinking A.1

  • 在现代的 64 位系统中，提供了 64 位的字长，但实际上不是 64 位页式存储系统。假设在 64 位系统中采用三级页表机制，页面大小 4KB。由于 64 位系统中字长为 8B，且页目录也占用一页，因此页目录中有 512 个页目录项，因此每级页表都需要 9 位。因此在 64 位系统下，总共需要 3 × 9 + 12 = 39 位就可以实现三级页表机制，并不需要 64 位。
  • 现考虑上述 39 位的三级页式存储系统，虚拟地址空间为 512 GB，若三级页表的基地址为 PTbase，请计算：
    • 三级页表页目录的基地址: PTBase + PTBase >> 9 + PTBase >> 18
    • 三级页表页目录的基地址: PTBase + PTBase >> 9 + PTBase >> 18 + PTBase >> 27

Thinking 2.6

  • 简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别。
    • X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别
      • X86 用到三个地址空间的概念：物理地址、线性地址和逻辑地址。而 MIPS 只有物理地址和虚拟地址两个概念。相对而言，段机制对大量应用程序分散地使用大内存的支持能力较弱。所以 Intel 公司又加入了页机制，每个页的大小是固定的（一般为 4KB），也可完成对内存单元的安全保护，隔离，且可有效支持大量应用程序分散地使用大内存的情况。x86 体系中，TLB 表项更新能够由硬件自己主动发起，也能够有软件主动更新

难点分析

  • 对各处宏的寻找和理解

Exercise 2.2

  • 完成 include/queue.h 中空缺的函数 LIST_INSERT_AFTER。
  • 指针 宏定义的语法
  • 双向链表，在某一元素前后加元素

Exercise 2.3

  • 通过宏将虚拟地址转换为物理地址以取得 freemem 以下页面对应的页控制块号（物理块号）：
    • int npage_unavailable = PPN(PADDR(freemem));
    • // PADDR(freemen): freemen-80000000 (ULIM) 去掉最高位，从虚拟地址找到物理地址
    • // PPN(va): va >> 12 address / size of a page (2^12)

Exercise 2.4

  • LIST_EMPTY 返回值注意，#define E_NO_MEM 4
  • Initialize this page with zero:
    • memset((void *)page2kva(pp), 0, BY2PG);
    • // 由页控制块地址得到虚拟地址，不是 page2pa，因为 alloc 出来的是要用的虚拟地址

Exercise 2.6

  • pgdir_walk: 给定一个虚拟地址，在给定的页目录中查找这个虚拟地址对应的页表项，将其地址写入 *ppte
    • if (!(*pgdir_entryp & PTE_V)) if(create) // 注意目标页表地址不存在或者无效和需要新建的两层逻辑
    • *pgdir_entryp = page2pa(pp) | PTE_D | PTE_V; // 新建之后配置页表内容 (高 20 位物理地址，低 12 位为其他标志位)
    • EntryLo 的位结构： PFN N D V G 0
    • Assign the kernel virtual address of the page table entry to '*ppte'
      • *ppte = (Pte)KADDR(PTE_ADDR(pgdir_entryp)) + PTX(va);
      • PTE_ADDR(pte): ((pte)& ~0xFFF) 将低 12 位置 0，（第一层页表项）将低 12 位变 0，得到物理⻚表基地址
      • 将物理地址转为虚拟地址，最后加上第二级偏移，找到目标页在页表中地址

Exercise 2.7

  • 插入页面时需要先检查 va 地址是否已经存在了映射，映射是否有效，映射的页和插入的页是否相同
  • 如果不存在了映射，或映射无效则需要调用 pgdir_walk，设置 create 为 1 来新建
    • if(pgdir_walk(pgdir, va, 1, &pte)){return -E_NO_MEM;}
  • 每当页表被修改，就需要调用该函数以保证下次访问该虚拟地址时诱发 TLB 重填以保证访存的正确性

实验体会

  • 理论知识需要再熟悉，比如对两级页表的地址与页表项的关系和内容，虚拟地址和物理地址的映射，两次页表查找的过程，TLB 的重填
  • 对所有宏含义需要再理解
  • 对 C 语言指针的理解和运用还需要再加强