Virtual Memory

[flaming-cl]

课刷到后半段，意识到没必要跟着 20fa 来刷课，20su 就可以了。一是因为 20su 把 61C 主要内容抽出来了，压缩过的课时更短、更省时间。二是因为，Garcia 虽然讲得不错，但他有时候为了把一个事解释清楚，举了挺多不必要的例子，也挺浪费时间

我觉得刷 61C 的一个好方法是

1. 先看 slides，挑出不理解的地方去读教材，找补充材料拓展知识
2. 跳看 20su 视频，实在没搞懂的地方再去看 Garcia 的版本
3. 赶紧做 lab proj

Pipelining 61C

datapath 可以 pipelining，刷课也可以 pipelining： proj1 (C programming) 和 proj2 (RISC-V) 几乎没有知识交叠的地方，完全可以同时学完。proj3 数字电路 (有些内容要以 RISC-V 为基础)，再之后才是 cache, VM, I/O, threads 这些常见的知识介绍。掌握基本的数字电路知识，过完相关 lab，其实就可以开始 proj3 之后的学习。这样能加速不少

Virtual Memory

VM 这里要讲的内容不是很多，核心内容是 1）VMA 怎么转换到 PMA 2）怎么保证转换过程安全有效 有效：layered page table，TLB（page table分级了以后，查询某个 PMA，可能要 access PM好几次，这里怎么提升效率呢？加缓存！在CPU内部加一个TLB，把转换过的 PMA 存起来备用） 安全：虽然我们给所有程序制造了独占、无限享有内存空间的假象，但它们始终 share 一个物理内存，万一有不老实的程序想窃取别人的数据呢？我们提前防范：

1. 给程序设置读写限制
2. 地址空间布局随机化 Address Space Layout Randomization（顺序存放可以被猜出存放地址 随机化程序的栈、数据、堆等区域的位置，让坏程序无从下手（没法找到想要修改的内容的位置 既然猜不出来，不如瞎猜？懵个10000次总有一次会成功？在 ASLR 策略下，如果程序随机修改，它就只会 crash 掉，没机会去执行计划外的代码（我估计这是理想状态吧，不会有啥天衣无缝的策略......
3. 可执行空间保护 控制进程内存空间的执行权限，使 CPU 只执行指令区域的代码。对于数据区域的内容，即使找到了其他漏洞想要加载成指令来执行，也会因为没有权限而被阻挡掉。

VM from 61C

1. 如果某个 process 需要更多运行空间怎么办 (>segment 扩大segment? 可如果 RAM 不够了？ 放去硬盘？（不嫌慢？放哪些，放多少数据过去？
2. 如果一共需要 500 M，但 RAM 碎片化程度很高，分不出足额的空间了，怎么办？

以上问题的答案—— Paged Memory

Page protection: Page Tables

操作系统

1. Protection 要让不同 programs 看上去同时在运行，确保每个程序有私有空间；不同 programs 还可以share address spaces 我找了一个不那么恰当的图
2. Demand Pageing 万一程序需要比主存更大的空间？

转换 VM 和 PM

1. Virtual Address 可以被分成两部分，就挺像之前提到那TIO的 Virtual Address = virtual page number + offset

size of address	log_2(virtual memory size)
size of offset	log_2(page size)
size of Virtual Page Number (VPN)	log_2(virtual pages)
size of virtual page bits	virtual address space - offset bits

Please note: VPN and PPN share the same page size and page offset

小练习

Steps for locating a physical address

1. 把地址拆分为 page number 和 offset
2. locate the page
3. locate the byte within the page

from VM address to PM address

Protection Between Processes

1. 通过 page table 能查询到 VPN 对应的 PPN
2. 跳转 PPN 之前，会检查 access rights 和 mapping 是否 valid，理论上 process 不会跳转到自己无权限的地址去

Page table 应该放在哪——主存

Cache 太小，Disc 太慢，同时用上 PT base register，用于找到当前 Page table 的物理地址

Page Table 不是线性的，是树状的（或者加cache）

假设某个 page table 只用到了第一个 page，后面的都用不到，那么就没必要去 load 一整个 page table。 但加 layers 也会导致更多的 PM access，这样降低了效率

解决办法 TLB

Please note: TLB 存的不是 memory 数据，而是 VPN 到 PPN 的映射 Translation Lookaside Buffers (TLB) Address translation is very expensive! In a single-level page table, each reference becomes two memory accesses In a two-level page table, each reference becomes three memory accesses Solution: Cache some translations in TLB TLB hit→Single-Cycle Translation TLB miss →Page-Table Walk to refill

TLB designs

Typically 32-128 entries, usually fully associative Each entry maps a large page, hence less spatial locality across pages more likely that two entries conflict Sometimes larger TLBs(256-512 entries) are 4-8 way set-associative Larger systems sometimes have multi-level (L1 and L2) TLBs Random or FIFO replacement policy “TLB Reach”: Size of largest virtual address space that can be simultaneously mapped by TLB

Which should we check first: Cache or TLB?

Can cache hold requested data if corresponding page is not in physical memory? No With TLB first, does cache receive VA or PA? Where Are TLBs Located? PA

content switching

Context switch:Changing of internal state of processor (switching between processes) Save register values (and PC) and change value in Supervisor Page Table Base register (SPTBR) What happens to the TLB? Current entries are for different process Set all entries to invalid on context switchReview: Context Switching

[sgzerolc]

我的做法是先看视频写简短的notes，在做lab前看slides补充notes，有空或者有什么不懂看discussion。现在pj2,pj3正在同时解决，以及开始做lab7之后的lab作业。

[flaming-cl]

Discussion

Pre-check

1. Page fault 什么时候发生？a page table entry 如果不在 TLB 里，算 page fault 吗？ Page fault：1）page table 中查询不到某个 page 2）该 page 有 invalid bit 出现 Page Fault 如何进一步操作？ We pull it from disk, add the page to memory (evicting another page if necessary), and add the mapping to the page table and the TLB.
2. VPN 和 PPN 必须大小一致吗？ 这俩的 page size 需要一样大，但 physical pages 会比 virtual pages 少一些

   Addressing

   TERM

3. page table entry page table 的每一行就是 page table entry，一个 page table 里有 2^ VPN bits
4. protection fault The page table entry for a virtual page has permission bits that prohibit the requested operation. This is how a segmentation fault occurs.

   当 page table 有新值载入时，TLB会发生什么？

   TLB 的 valid bits 应该全部归零

   练习

   offset: log2_(页数) VPN 位数 = address 位数 - offset 位数

   0x11f0 (Read)

   1）Read 2）处理 LRU：清零该 entry 的 LRU value (LRU 数值越大，越不常用)，以及增加其他 entries 的 LRU 数值

   0x1301 (Write)

   TLB miss 了，处理办法： 1）拿取 Free Physical Pages 里的第一个地址生成映射 2）把 TLB 中的最不常用 entry 踢掉（碰到并列第一「最不常用」的，随便取一个 3）valid -> 1 4）更新 LRU

   0x20ae (Write)

   Write + TLB hit, 改 dirty 为 1 补充： 眼镜哥说 TLB miss 是 page fault，回看第一题，这哥们应该是说错了

[sgzerolc]

exercise1

1. 4
2. [4,6,0,6]
3. Did you have any Page Hits? (Why?) Can you think of a set of ten addresses that would result in a Page Hit? Your answer should be two [yes/no]’s separated by a comma. A: no 问题：不明白page hit的过程。当需要的虚拟地址在TLB的matching entry中，就产生TLB hit。看到有说法是，在需要的虚拟地址恰好在memory中存储的时候就是page hit。 https://courses.cs.washington.edu/courses/cse351/17wi/lectures/CSE351-L22-vm-III_17wi.pdf

Q1:Explain the process by which we turn a virtual address into a physical address for the very first access (emphasizing on TLB Misses and Page Faults). First, convert address reference into binary form so that virtual page number is first three bits and the rest is offset in the page. Second, TLB would check pages according to the page number. If no matching entry was found, then it results in TLB miss.Then seach the page number in page table. If the page not found or the page table entry for this virtual page number had a valid bit of 0, then a page fault occurs. Q2: Why does the physical address only have 2 bits for the PPN while the virtual address has 3 bits for the VPN? There was 8 pages in virtual memory and 4 page frames in physical memory. Page number is set to check the page.

exercise2

1.[00,20,40,60,80,00,20,40,60,80]

exercise3

1. physical memory size gets bigger

   exercise4

   Q3:Explain why there is a much higher percentage of TLB misses in this simulation TLB size is way smaller than physical memory size.

注：等看书后再补充修改