NOTICE
- 有"w3l2"标记的题是助教要提交到学堂在线上的。
- 有"w3l2"和"spoc"标记的题是要求拿清华学分的同学要在实体课上完成，并按时提交到学生对应的git repo上。
- 有"hard"标记的题有一定难度，鼓励实现。
- 有"easy"标记的题很容易实现，鼓励实现。
- 有"midd"标记的题是一般水平，鼓励实现。
- 为什么要设计非连续内存分配机制？
- 非连续内存分配中内存分块大小有哪些可能的选择？大小与大小是否可变
- 为什么在大块时要设计大小可变，而在小块时要设计成固定大小？小块时的固定大小可以提供多种选择吗？
- 什么是段、段基址和段内偏移？
- 段式存储管理机制的地址转换流程是什么？为什么在段式存储管理中，各段的存储位置可以不连续？这种做法有什么好处和麻烦？
- 什么是页（page）、帧（frame）、页表（page table）、存储管理单元（MMU）、快表（TLB, Translation Lookaside Buffer）和高速缓存（cache）？
- 页式存储管理机制的地址转换流程是什么？为什么在页式存储管理中，各段的存储位置可以不连续？这种做法有什么好处和麻烦？
多次存储访问
- 每个页表项有些什么内容？有哪些标志位？它们起什么作用？
- 页表大小受哪些因素影响？
页大小、地址空间大小、进程数目
- 快表（TLB）与高速缓存（cache）有什么不同？
- 为什么快表中查找物理地址的速度非常快？它是如何实现的？为什么它的的容量很小？
- 什么是多级页表？多级页表中的地址转换流程是什么？多组页面有什么好处和麻烦？
- 页寄存器机制的地址转换流程是什么？
- 反置页表机制的地址转换流程是什么？
- 反置页表项有些什么内容？
PID、逻辑页号、标志位
- 段页式存储管理机制的地址转换流程是什么？这种做法有什么好处和麻烦？
- 如何实现基于段式存储管理的内存共享？
- 如何实现基于页式存储管理的内存共享？
（1） (w3l2) 请简要分析64bit CPU体系结构下的分页机制是如何实现的
+ 采分点：说明64bit CPU架构的分页机制的大致特点和页表执行过程
- 答案没有涉及如下3点；（0分）
- 正确描述了64bit CPU支持的物理内存大小限制（1分）
- 正确描述了64bit CPU下的多级页表的级数和多级页表的结构或反置页表的结构（2分）
- 除上述两点外，进一步描述了在多级页表或反置页表下的虚拟地址-->物理地址的映射过程（3分）
- [x]
（1）(spoc) 某系统使用请求分页存储管理，若页在内存中，满足一个内存请求需要150ns (10^-9s)。若缺页率是10%，为使有效访问时间达到0.5us(10^-6s),求不在内存的页面的平均访问时间。请给出计算步骤。
- [x]
500=0.9*150+0.1*x
（2）(spoc) 有一台假想的计算机，页大小（page size）为32 Bytes，支持32KB的虚拟地址空间（virtual address space）,有4KB的物理内存空间（physical memory），采用二级页表，一个页目录项（page directory entry ，PDE）大小为1 Byte,一个页表项（page-table entries PTEs）大小为1 Byte，1个页目录表大小为32 Bytes，1个页表大小为32 Bytes。页目录基址寄存器（page directory base register，PDBR）保存了页目录表的物理地址（按页对齐）。
PTE格式（8 bit） :
VALID | PFN6 ... PFN0
PDE格式（8 bit） :
VALID | PT6 ... PT0
其
VALID==1表示，表示映射存在；VALID==0表示，表示映射不存在。
PFN6..0:页帧号
PT6..0:页表的物理基址>>5
在物理内存模拟数据文件中，给出了4KB物理内存空间的值，请回答下列虚地址是否有合法对应的物理内存，请给出对应的pde index, pde contents, pte index, pte contents。
1) Virtual Address 6c74
Virtual Address 6b22
2) Virtual Address 03df
Virtual Address 69dc
3) Virtual Address 317a
Virtual Address 4546
4) Virtual Address 2c03
Virtual Address 7fd7
5) Virtual Address 390e
Virtual Address 748b
比如答案可以如下表示： (注意：下面的结果是错的，你需要关注的是如何表示)
Virtual Address 7570:
--> pde index:0x1d pde contents:(valid 1, pfn 0x33)
--> pte index:0xb pte contents:(valid 0, pfn 0x7f)
--> Fault (page table entry not valid)
Virtual Address 21e1:
--> pde index:0x8 pde contents:(valid 0, pfn 0x7f)
--> Fault (page directory entry not valid)
Virtual Address 7268:
--> pde index:0x1c pde contents:(valid 1, pfn 0x5e)
--> pte index:0x13 pte contents:(valid 1, pfn 0x65)
--> Translates to Physical Address 0xca8 --> Value: 16
（3）请基于你对原理课二级页表的理解，并参考Lab2建页表的过程，设计一个应用程序（可基于python、ruby、C、C++、LISP、JavaScript等）可模拟实现(2)题中描述的抽象OS，可正确完成二级页表转换。
（4）假设你有一台支持反置页表的机器，请问你如何设计操作系统支持这种类型计算机？请给出设计方案。
(5)X86的页面结构
阅读64bit IBM Powerpc CPU架构是如何实现反置页表，给出分析报告。