Beyond Physical Memory: Mechanisms如果某个进程的虚拟地址空间太大，或者整个系统所有进程的所有虚拟地址空间之和无法一次性放到物理内存中，操作系统通常需要将一些当前不常用的地址空间换出到硬盘中。 1 Swap Space磁盘中需要有一个交换区，用于和内存交换内存页。OS需要记录每个换出页的磁盘地址。 2 The Present Bit常规的地址转换过程： 进程提供虚

Paging: Smaller Tables基本的页式内存存在的一个问题就是页表占据的空间太大了。 1 Simple Solution: Bigger Pages最简单的方法就是使用更大的页，这样可以减少页表项的个数，从而减少页表的大小。但是这种方法会导致内部内存碎片。 2 Hybrid Approach: Paging and Segments段页式内存，结合段式内存和页式内存。每个段由一对ba

Paging: Faster Translations (TLBs)为了加速内存访问，OS需要硬件的帮助：translation-lookaside buffer（TLB）。TLB其实就是经常访问的PTE的硬件缓存。在每次访存之前，硬件首先去TLB中查看指定的PTE是否存在，如果存在，就不需要去内存中查找对应的PTE了。 1 TLB Basic Algorithm 2 Who Handles Th

Paging: Introduction1 Overview每个进程都有一个自己的页表(Page table)，用来进行虚拟地址到物理地址的转换。 虚拟地址分为两部分，虚拟页号（Virtual Page Number，VPN）和内页偏移（offset）。 MMU根据页表，将VPN转换为对应的物理页号（Physical Page Number，PPN），然后将PPN和offset组合，获得实际的物

Free-Space Management对于页式内存来说，空闲页管理很简单，只需要用链表来管理空闲页即可；但是对于像段式内存这种空闲内存单元大小不固定的方式来说，空闲内存管理变得更复杂。对于后者，最大的挑战是外部碎片问题。 1 Low-level MechanismsSplitting and Coalescing 管理空闲内存空间的数据结构在需要时需要进行相应的拆分或者合并。 Tracking

1 RISC-V assembly (easy) Which registers contain arguments to functions? For example, which register holds 13 in main’s call to printf? 在RISC-V中，函数的参数存放在寄存器 a0-a7 中，如果超过8个参数，可以

Introduction to the Relational Model1 Structure of Relational Databases一个关系型数据库包含一组表，每个表都有一个独特的名字。 通常来说，表中的一行代表着一组值之间的关系。 术语 tuple：一组值的序列 n个值的关系用一个n-tuple来表示（表中的一行） relation - 一张表 tuple - 表中的一行

Segmentation1 Segmentation: Generalized Base/Bounds传统的动态重定位会导致内存空间的浪费（整个用户地址空间可能只有一小部分真正使用，大部分是空闲的）。因此，可以使用分段的方式，将用户地址空间按照逻辑分为不同的segment，每个segment都有一对base/bound寄存器。需要注意的是，在进行地址转化的时候，必须将虚拟地址首

Mechanism: Address Translation1 Assumptions最初的假设很简单： 用户地址空间在物理内存中连续存放 用户地址空间不大于物理内存大小 每个用户地址空间都一样大 2 Dynamic(Hardware-based) Relocation早期，在没有硬件支持的时候，有些操作系统支持软件重定位(static relocation)。loader程序负责改写另外一个

HyperLogLog in Presto情景 想要确定一个有重复元素的很大集合的cardinality。常规方法的时间开销或者内存开销过大，无法接受。 A simple estimator 首先，生成一个理论数据集： 生成n个均匀分布在[0,1]之间的数。 随机挑选一些数，随机复制几次。 打乱顺序 因为所有数是均匀分布的，可以找出最小的数$x_{min}$，然后估计集合的$cardinali