jasperzhong commented 3 years ago

打算系统看一遍

看这本书要注意经常出现的The curx of the problem，帮助理解这是在解决什么问题.

jasperzhong commented 3 years ago

ch02: introduction ot operator systems

OS主要做了virtualize resources (CPU, memory, disk)这件事，并且向应用提供了system calls (standard library). 本书另外两个主题是concurrency(如何写一个正确的并行程序)和persistence(如何将数据持久存储).

OS最重要的目前是提供硬件的抽象，使得程序员能直接写高级程序，而不需要和底层硬件打交道. 另外一个目标是高性能，不能带来太大的开销（虽然一定的开销是值得的）. 还有一个是提供保护，一个程序的行为不会影响其他程序执行（隔离）. 最后一个是高可靠性，OS必须是non-stop的，当OS宕了，在上面执行的所有程序也都宕了. 鉴于这种依赖性，OS必须提供高可靠性. 现代OS代码行数已经上亿，里面可能潜在大量bugs，如何减少bug是一个挑战. 另外一些目标也有道理，比如安全，移动性（移动端OS）.

Abstraction:

Process: Virtualize CPU （让每个process觉得自己都占有CPU）
Address Space: Virtualize Memory （让每个process都觉得自己占有memory）

OS历史

OS一开始只是一个standard libraries而已，提供了一些API. 后来发明了system call的概念.

system call和procedure call的区别在于，system call会把控制转移给OS，并且提高硬件权限级别. 处在user mode的应用不能直接向disk发送I/O request，也不能访问任何物理内存页，也不能向网络发送packet. 当system call被启动时(通常是通过一个特殊的硬件指令叫做trap), 硬件转移控制到一个预先设定的trap handler上，同时提高权限级别到kernel mode. 处在kernel mode时，OS拥有硬件的完整权限，可以做诸如发送I/O请求或者向程序分配更多内存. 当OS结束这个请求后，它会通过一个特殊的return-from-trap指令，把控制返回给用户，这会回到user mode，并且回到应用离开的地方.

后来OS有了multiprogramming的概念，可以同时执行多个任务. 这就需要做context switch. switching是非常重要的，因为访问I/O设备时非常慢的，一个程序在等待I/O的时候，CPU是空闲的. 所以，我们可以switch到另一个任务并且执行一会儿. multiprogramming的需求还催生了memory protection，因为我们不想让一个程序访问另一个程序的内存. 另外它还催生了如何处理concurrency的问题. 在这个时候，出现了影响深远的UNIX操作系统.

后来就进入到了现代操作系统时代. 出现了PC机，出现了Mac OS, Windows... 之后诞生了Linux, Linus Torvalds写了自己版本的Unix.

jasperzhong commented 3 years ago

ch4: the abstraction: the process

进程是运行的程序. 程序本身是没有生命的东西，躺在磁盘上，有一堆指令（也许有一些静态数据），等待被唤醒.

Challenge: OS如何提供一个拥有无限CPU供应的假象？

解决办法是time-sharing mechanism: 虽然某个时刻，一个CPU上只能运行一个进程，但是一个时间段内，可以运行多个. times-sharing就会涉及到context switch，即OS有能力去停止正在运行的程序，然后启动另一个. 而如何决定which process to run，就涉及到scheduling policy的问题.

启动进程

首先要把code和static data加载进memory. 然后需要分配stack. stack用来存放local variablies, function parameters和return addresses. OS还会用main函数的argc, argv来初始化stack. OS还会做和I/O有关的初始化工作，比如UNIX中每个进程默认有三个open file descriptors (stdin, stdout, stderr). 最后OS从main()开始执行程序. main()是这个进程的entry point.

一般来讲，进程有三个状态: running, ready, blocked. 转换如下图所示,

为了跟踪每个进程的状态，OS有一个process list的数据结构，也叫做PCB (process control block).

除了上述三个状态外，实际上还有initial状态(表示正在创建进程) 和 final state. final state是进程已经exit了，但是还没有被clean up (也叫做zombie state). 这个状态是有用的，因为他让parent进程可以去检查return code. 当parent进程调用wait()函数的时候，OS才会去做clean up.

Tip提到了Time sharing和Space sharing. 对于CPU还有network link，采用的是time-sharing. 而对于disk，采用的是space sharing——一个block分配给了一个文件，这个block就不能分配给其他文件，直到用户删除这个文件为止.

Tip还提到了区分policy和mechanism. 这个tip让我很有启发. mechanism回答的是how，比如OS到底是如何执行context switch的. 而policy回答的是which，比如OS应该选择在哪一个进程去执行. 区分policy和mechanism的好处是，改变其中一个的时候不需要改变另一个. 这就是模块化，工程上常用的设计原则.

这段话也很好解释了mechanism

Mechanisms are low-level methods or protocols that implement a needed piece of functionality. For example, we'll learn later how to implement a context switch, which gives the OS the ability to stop running one program and start running another on a give CPU; this time-sharing mechanism is employed by all modern OSes.

从这段话可以看出. time-sharing是mechanism. 而context switch是functionality. time-sharing只是实现context switch这个functionality的一个mechanism，只是里面一个piece.

On top of these mechanisms resides some of the intelligence in the OS, in the form of policies. Policies are algorithms for making some kind of decision within the OS. For example, given a number of possible programs to run on a CPU, which program should the OS run? A scheduling policy in the OS will make this decision, likely using historical information (e.g., which program has run more over the last minute?), workload knowledge (e.g., what types of programs are run), and performance metrics (e.g., is the system optimizing fo interactive performance, or throughput?) to make its decision.

所以mechanism是用来实现一些functionality的piece，是low-level的. 而policy是用来make decision的，是high-level的intelligence. 感觉一篇好的system paper两个都要有.

jasperzhong commented 3 years ago

ch5: interlude: Process API

介绍了UNIX的fork(), exec()和wait()三个system calls.

fork()是挺奇怪的: 进程首先创建一个(almost)exact copy of the calling process. 子进程不从main()开始执行，而是从fork()返回. 唯一的区别是子进程的返回值(pid)为0. 所以一般用if else让父子进程进入不同逻辑.

wait()是父进程主动等待子进程结束返回. 挺有用的，比如可以用来保证一定的执行顺序.

exec()并不会创建一个新的进程，而是直接把当前正在运行的程序转变为另一个运行程序.

问题是为什么要弄fork()和exec()这样奇怪的API? 其实fork() + exec()是一个非常powerful的组合, 是UNIX shell非常关键的部分. 这让shell能在fork()之后，exec()之前执行一些代码.

shell只是一个user program. 当输入一个命令的时候, shell首先找到executable在哪里, 然后调用fork()创建一个子进程, 然后调用exec()去执行这个命令, 然后调用wait()等待子进程结束. 当子进程结束后, shell从wait()返回然后输出prompt, 等待下一次输入命令.

$ wc p3.c > newfile.txt

这个重定向的实现方式是：在fork()后，exec()前，关闭stdout，然后打开文件newfile.txt. 为什么这样就work呢? 这是因为UNIX在分配file descriptors的时候，是首先找file descriptor为0的，而我们已经关闭了stdout，所以它的file descriptor已经为0，所以就分配给了新创建的newfile.txt. 所以子进程后面的printf等操作就直接routed到了新创建的文件.

pipe() system call也是用类似的方法实现的. 一个进程的输出连接到一个internal pipe，而另一个进程的输入连接到相同的pipe. 比如统计某个word在文件中的出现次数

$ grep -o foo file | wc -l

tip里面提到了一个黑话：RTFM - Read The Man Pages. 确实应该多看man page.

jasperzhong commented 3 years ago

Ch 6: Mechanism: Limited Direct Execution

本章主要介绍了实现CPU time-sharing的核心机制——Limited Direct Execution (LDE)

首先说说什么是Direct Execution: 直接在CPU上执行程序. 当OS希望启动一个程序时，首先在process list创建一个process entry，分配一定的内存，然后将程序load到memory，找到它的entry point，然后jump到那里，开始执行用户代码.

但这个方法带了了两个问题：1）访问权限的问题. 2）OS要如何stop这个进程，然后switch到另一个进程. 这就需要一些OS做一些限制 (所以叫limited direct execution).

Problem 1 Restricted Operations

如果让进程可以做任何它想做的事情，比如I/O等操作，这样会带来安全问题，比如一个进程可以r/w整个磁盘，仿佛拥有最高权限.

因此，需要引入一个新的processor mode——user mode. 运行在user mode的进程被限制了能做的事情. 比如，处在user mode的进程不能发送I/O请求，如果在processor这么做，会引发一个exception，OS可能会kill掉这个进程.

与user mode相反的是kernel mode，指的是OS (or kernel)运行的状态. 在这个mode下，可以运行任何代码，包括权限操作比如发送I/O请求和执行各种限制指令.

那如果一个user process想执行一些权限操作怎么办呢？通过system calls. system calls允许kernel向用户程序暴露一定的核心功能，比如访问文件系统，创建和销毁进程，与其他进程通信，分配更多的内存.

要执行一个system call，程序必须执行一个特殊的trap指令. 这个指令跳到kernel同时提高权限级别到kernel mode. 当进入kernel后，系统可以执行任何权限操作，因此执行调用进程所要求的工作. 当结束时，OS调用一个特殊的return-from-trap指令，返回到调用用户程序，同时把权限级别降低到user mode.

在执行trap的同时，硬件还会把caller的registers保存到kernel stack. 在执行return-from-trap的时候，硬件会从kernel stack pop这些值，然后继续执行用户程序.

另一个问题是，trap如何知道要执行OS的哪段代码? 这是通过在boot的时候设置trap table实现的. OS告诉硬件trap handlers的位置. 所以当发生system calls的时候，硬件是知道what to do的（即what code to jump to）.

于是有了下面这个timeline. 注意save/restore regs to/from kernel stack，以及move to user/kernel mode都是硬件完成的.

Problem 2 Switching Between Processes

有一个很重要的问题: 如果一个进程一直在CPU上运行，那么OS要如何运行呢？如果OS不能运行，它就不能做任何事情. 所以问题的就在于——OS要如何重新获得CPU control.

cooperative approach

第一种方法是OS被动的等待进程做system calls. 早期Macintosh就是这样. 一般这样的系统有一个yield的system call——即主动放弃CPU，移交控制给OS. 当进程产生异常的时候，比如除以0，也会产生trap从而转移控制权给OS.

一般正常的进程确实会经常做system calls. 但一个hack方法是：写个死循环然后啥也不做... 这种系统对付这种攻击唯一的做法就是reboot.

non-cooperative approach

于是就有了OS主动去获得控制权的方法——timer interrupt，时钟中断. 每过一定时间，就会产生一个时钟中断，然后一个interrupt handler就会执行. 这个时候OS就重新获得了CPU控制权, 然后OS可以做context switch.

context switch需要额外的保存现场的操作. 之前system calls是硬件去保存进程的regs到kernel stack上. 但如果要做context switch，还需要额外的保存当前运行进程的general purpose registers (包括PC和kernel stack pointer)到process structure上. 这个保存是由软件(OS)完成的. 然后OS从process structure restore即将要执行进程的regs，然后switch到这个进程的kernel stack.

switch stack这一步非常关键，kernel是在进程A的context下执行switch code的，但是返回的时候已经在进程B的context下了.

带时钟中断的LDE timelime如下. 注意两次不同的save/restore registers (一硬一软).

当OS处理interrupt的时候，会disable interrupts，这是为了防止嵌套的处理.

最后作者打了个比方，说OS这套限制和baby proofs很像 —— 提前设置trap handlers，启动interrupt timer，然后只让进程在限制状态运行. 通过这些，OS就可以保证进程可以高效执行，只有在需要执行权限操作的时候或者被switched out时候，才需要OS干预.

jasperzhong commented 2 years ago

补充：Interrupt

Overview

Interrupt是改变程序正常执行流程的事件，可以由硬件设备或者CPU本身产生.

Interrupt可以根据来源分成两大类:

软中断：由执行某个intruction产生，同步
硬中断：由外部设备产生，异步
- maskable: 可以被忽略，通过INT引脚发出信号
- non-maskable: 不能被忽略，通过NMI引脚发出信号

软中断，是在执行指令的过程中由CPU本身检测到的. 有两个来源:

processor detected:
- faults: 异常的一种，一般在执行指令前检测到，保存的CS:EIP指向导致异常的指令，而且一般能够纠正. 比如page fault.
- traps: 异常的一种，一般在执行指令后检测到，保存的CS:EIP指向导致异常的指令的后面一个指令，比如debug trap.
- aborts
programmed:
- int n: system call

硬中断，是由I/O设备产生的外部事件. 比如网卡在收到一个packet的时候会产生一个interrupt信号. 常见的设备有键盘、鼠标、网卡和时钟等.

x86 Interrupt Vectors

每种中断都有一个interrupt number ，也叫interrupt vector. OS在boot time会设置一个Interrupt Desciptor Table(IDT)，存放在memory. CPU有一个IDTR register，指向当前的IDT. IDT每一项都是一个interrupt handler，也叫interrupt service routine(ISR). 硬件通过interrupt vector作为IDT的index找到对应的handler.

IRQ vector layout. 前32项保留exceptions，vector 128用作system call，其他主要用于硬件中断.

Hardware Implementation

PIC: Programmable Interrupt Controller 设备在相应的IRQn引脚上引发中断. PIC将设备的Interrupt Request lines (IRQ)映射成interrupt vector. PIC在CPU INTR引脚上引发中断，并等待CPU确认中断. CPU处理中断.

注意: 在CPU确认当前中断前，PIC不会引发另一个中断.

CPU处理中断请求

背景知识: SS:ESP当前栈头位置. CS:EIP当前代码位置.

伪代码:

while (fetch next instruction) {
    run instruction
    if (interrupt) {
        check the current privilege level
        if (need to change privilege level) {
            stack switch  // kernel stack, SS ESP from TSS
            save old SS ESP on the kernel stack
        }
        save EFLAGS CS EIP on stack 
        if (abort) save error code on stack
        execute the kernel interrupt handler (CS:EIP from IDT)
        if (abort) pop error code on stack
        call IRET
    }
}

IRET是interrupt return instruction.

从stack pop values，恢复CS EIP EFLAGS寄存器
如果privilege level改变了，恢复到原来的stack和原来的privilege level

顺便参考下图帮助理解.

Linux System Calls Implementation

通过INT 0x80触发，system call identifier存在EAX，其他参数存放在EBX, ECX, EDX, ESI, EDI, EBP.

执行流程如下: 一开始的执行和interrupt一样，然后需要查syscalls table，找到对应的函数执行.

参考资料：

jasperzhong commented 2 years ago

Ch 7: Scheduling: Introduction

没啥意思. 假设知道每个job的length（有先验知识），如何做调度. 实际上OS压根儿不知道每个process要多少时间.

常见的有SJF/STCF/RR...常见的metrics有turnaround time(周转时间), response time(响应时间), 和fairness. turnaround time和fairness常常是矛盾的，需要tradeoff.

里面提到RR (round robin调度）有一个可以tune的knob是每个time slice时间.

另外CPU执行和I/O可以overlap.

这一节其实提到了不少system的idea. 很好.

jasperzhong commented 2 years ago

Ch 8: Scheduling: The Multi-Level Feedback Queue

介绍了MLFQ. 非常棒的idea. 核心idea就是feedback - 利用history predict future. 这也是system里面常见的idea.

简单来说MLFQ有很多个queue，每个queue都对应一个priority. 在同一个queue上的jobs priority相同. scheduler选择priority最高的进行调度，如果有多个priority同样最高的，则round robin. 这是multi-queue部分.

然后是最核心的feedback部分. 给了几个rules:

新来的job是最高优先级.
如果一个job用完了所在priority level的time allotment（无论中间yield多少次CPU），就会被降级
定期将所有jobs移动到最高优先级的jobs. (这个周期的长度是一个voo-doo constant.)

前两个rules的的rationale是: scheduler其实不知道新来的job是short job还是long-running job，但它会假定是一个short job. 如果真的是一个short job，那么会很快执行完. 如果不是，那么会慢慢滑落到低优先级的queue里面.

第三个rule解决的问题是starvation的问题 - 可能long-running job永远也不能make progress.

TIP提到了voo-doo constant. 这说的好像就是那种可以tune的knob. 适合放在config file里面，让用户自己给定值.

jasperzhong commented 2 years ago

Ch 9: Scheduling: Proportional Share

讨论了fair-share scheduler. 主要是两种:

lottery scheduling: 利用random number来选择process，每个process有一个tickets数量，数量越多被选中概率越大
stride scheduling: 每个process有一个stride，并且维护一个counter，每次该process被调度，counter += stride. scheduler选择counter最小的process调度.

stride scheduling是deterministic的，而lottery scheduling用了随机数，是完全随机的. 但lottery scheduling不需要维护状态（即stride scheduling里面的counter）. 这有一个好处就是如果新来了一个process，stride scheduling是无法handle的，但是lottery scheduling可以.

这种fair-share scheduler最大的问题就在于如何分配tickets. 所以基本都是conceptual的东西，应用不多. MLFQ更加通用一些.

ticket的rationale是a process's share of the CPU. 所以如果想表达a proportion of ownership，可以考虑用ticket这个概念.

jasperzhong commented 2 years ago

Ch 13: The Abstraction - Address Space

介绍了下Virtual Address Space的概念. It is the running program's view of memory in the system.

Design Goals:

Transparency: 对用户透明. OS来handle那些dirty work
Efficiency: 使得virtualization尽可能efficient. 需要一些硬件support，如TLB
Protection: 一个好处是isolation. 这非常重要. Isolation保证了一个挂了另一个不会受影响.

另外注意平时print的address都是virtual address. （比如可以run两个一模一样的program，print出来的地址是一样的）

jasperzhong commented 2 years ago

Ch14 Interlude: Memory API

C语言malloc/free的一些pitfalls. 没啥好说的.

jasperzhong commented 2 years ago

Ch15: Mechanism - Address Translation

主要通过硬件实现 - MMU (memory management unit). 准确来说是两个寄存器: base and bound (per CPU).

每个program都认为自己的address space从0开始. 创建process的时候，OS会从free list里面找一个slot分配个这个process，base寄存器的值为该slot的起始地址. 在实际running的时候，每一次的memory reference都会被translated成

physical address = virtual address + base

而bound寄存器是这个program的address space大小. 每次访存的时候会检查virtual address < bound. 这样实现了protection. 如果出现了illegal的memory access，CPU抛一个exception.

以上这个机制叫做dynamic relocation

注意:

每个进程的base和bound寄存器的值不一样，每次context switch的时候也需要save/load这两个寄存器to/from PCB.
OS可以将某个address space从一个物理位置移动到另一个物理位置. 先deschedule the process，然后OS copies the address space到新的location，最后更新该进程的base寄存器地址（在PCB里面）. 然后就可以resume了.

所以address translation的工作主要是硬件来做. 绝大多数时候OS都是不参与的. 只有少数时候OS必须要参与. 这和Limited direct execution的approach很像. 看下面这图融会贯通.

jasperzhong commented 2 years ago

Ch 16: Segmentation

将code/heap/stack三个segment每个弄一个base/bound寄存器pair.

segmentation fault: The term segmentation fault or violation arises from a memory access on a segmented machine to an illegal address.

这有一个问题是hardware在做翻译的时候，怎么知道应该用哪个base/bound寄存器pair?

一个方法是显式encode segment. 比如这里有三个segments，那么用2bits可以encode.

这样，硬件取前两位来决定应该使用哪一个段寄存器. 后面12位用作offset.

还有一个问题是stack. stack的增长是反方向的. 比如stack在physical memory中起始地址是28KB，大小两2KB，那么是反方向增长到26KB的位置. 所以硬件在做translation的时候，应该将base减去offset而不是加上.

还有个save memory的trick - sharing segment. 硬件需要额外的bits将segment标记读/写/执行. 比如code segment通常可以被多个process通过只读方式共享.

最后是内存管理问题. 很多segments大小不一樣(variable-sized segments)，会造成external fragmentation. 常用的方法是OS维护一个free-list记录available slot for allocation. 常见的算法有best-fit, worst-fit, first-fit，还有一个更复杂的叫buddy alogrithm的算法. 但不管哪一种，都只能减少但无法彻底消除external fragmentation.

jasperzhong commented 2 years ago

Ch17: Free-Space Management

内存管理里面有两种fragmentation:

external: 可以理解为块与块之间的空间
internal: 块内部可能也没有被完全使用. 比如申请10KB但返回了一个20KB的块，浪费10KB.

这节其实还挺有趣的. 讲了如何实现一个memory allocator. 用C的malloc和free举了例子.

基本数据结构是free-list. 每个node有一个header，包括这个chunk大小，和一个magic number（用来检验数据完整性），和下一个node位置. 这些node其实可以内嵌到free space里面去. 而不用单独开一块地方单独存放free-list. 如下图.

allocator有两个基本操作:

split: 当malloc请求的数据块大小小于chunk大小的时候，需要把这个chunk分成两块.
coalesce: 当free返回空闲数据块时，可能需要合并相邻的数据块.

一开始OS分配一块heap用于分配. 当heap用完之后，library会向OS继续申请更多内存（通过调整heap segment大小，如sbrk system call）. 这很有意思，对于OS来讲，只是给进程分配了一大块memory作为heap; 而在进程内部，libraray通过free list对这块free space进行管理（而OS其实并不知道）. 有意思.

当有很多chunks的时候，就需要一个policy来选择返回哪个chunk. 简单的有best-fit, worse-fit, first-fit, next-fit.

比较有趣的有:

segregated lists. idea是为一个或者一些popular-sized request单独开一个free list.
buddy algorithm: 这个更有趣，按照2^n来分配，每次recursively地二分buffer，直到找到最合适的大小（再分就放不下了）. 用图更好说明一些.

有个性质是每个buddy pair的address其实只有一个bit不同，这个bit决定了它们在buddy tree的level. buddy algorithm有个问题是internal fragmentation，因为分配的大小都是2的倍数.

啊这. :cry:

jasperzhong commented 2 years ago

Ch18: Paging

为了减少fragmentation，一个简单但是有效的办法是: paging. idea很简单，就是把memory分成一个一个固定大小的单位，每个单位叫做page.

虚拟地址空间同样也是分页的. 这就需要虚拟页表 => 物理页表. 转换是通过page table来实现. 由于虚拟地址空间是每个进程都有一个，所以page table每个进程都要有一个.

地址可以分为VPN和offset. VPN是Virtual Page Number，即虚拟页表数. 在地址转换的时候，需要将VPN转换成PFN（i.e., Physical frame number）.

每个页表条目（page table entry）包含PFN和关于该页的一些status bits，比如valid bit, present bit, read/write bit, user/supervisor bit.... 其中valid bit表示该页是否有效. 进程的虚拟地址空间虽然很大，但是一般来讲，绝大部分都没有用到. 所以并不是所有的虚拟页表都需要分配一个物理页表，没有被分配物理页表的虚拟页表就可以标记为invalid. present bit表示该页是否在内存中，因为可能被swap到磁盘上.

paging机制会引入non-trivial的时间和空间的overhead.

时间上，页表转换需要额外的一次内存访问（需要先访问页表位置），还需要转换地址. 注意，每一次内存访问（无论是load指令还是load数据），都需要额外的一次内存访问.

空间上，页表本身大小是很大的. 比如，32-bit地址空间，页大小4KB. 那么需要20-bit VPN和12-bit offset. 那么每个页表需要2^20个PTE，假设每个PTE 4Bytes. 那么每个页表需要4MB内存. 注意，每一个进程都需要一个页表. 如果有100个进程，需要400MB的页表用作地址转换. 这是non-trivial的.

后面章节会讨论如何解决这两个问题.

jasperzhong commented 2 years ago

Ch19: Paging: Faster Translations (TLBs)

满精彩的一章. TLB其实就是translation cache，将常用的VPN -> FPN翻译放在cache上，减少translation开销. 一般来讲，cache都是利用了locality. locality分两种

temporal locality: 最近被访问的地址很可能不久的将来也要被访问 (比如loop variables)
spatial locality: 被访问地址的附近地址也可能被访问 (比如traverse an array)

一般来讲，由于物理原因，cache无法同时做到big and fast，所以一般是small but fast.

hanlde TLB可以是硬件处理，也可以是软件处理. x86架构是硬件处理，CR3寄存器指向当前page table. TLB miss/replcament等处理和cache基本一样.

注意，TLB是fully-associative cache，即可以并行search the entire TLB to find the desired translation. TLB每个entry包括: VPN, PFN and other bits. other bits一般有valid bit, protection bit等等.

由于translation每个进程都不一样，当发生context switch的时候，上一个进程留在TLB里面的translations对于即将运行的进程来说是毫无意义的. 解决办法是，TLB entry包括一个address space identifier (ASID)，其实就是PID，只不过bits更少一些（只有8个，而PID有32个）.

jasperzhong commented 2 years ago

Ch20: Paging: Smaller Tables

一个思路是用segmentation，即每个segment有一个页表. 之前介绍过，每个segment有一对base和bound寄存器，base是基地址，bound是这个segment大小，如果访问超出这个bound则认为是segmentation fault. 在这里，可以把bound寄存器的值设置为最大可用的page数量. 比如，对于code segment，可能只需要3个page就行了，那么bound寄存器的值就为3. 这样大大减少了页表的大小.

另一个思路是多级页表. 直接看下图更为明显. 如果PDE中一个unit invalid，那么不需要分配这个页表. 这其实是把一个线性的空间变成了一个树状的空间，并且用valid/invalid bit进行剪枝. trade-off也很明显，当出现TLB miss的时候，需要额外的一次memory load.

还有一个更crazy的idea是用inverted page tables，即physical page -> virtual page. 一般需要一个额外的hash table来减少搜索开销.

总的来讲，page table其实就是data structures. data structure可以做很多crazy的事情，可以更大或者更小，更快或者更慢.

最后还可以swap page tables to disk.

jasperzhong commented 2 years ago

Ch21: Beyond Physical Memory: Mechanisms

讲了page fault. PTE里面有一个present bit，用来表示是否该页是否在memory上. 如果不在，那么硬件raise一个page fault，让OS来处理. OS就当作是一个中断，有一个page fault handler，用来从磁盘中读取该页. 注意这里有overlap——读取是I/O操作，该进程是block状态，OS可以执行其他事情.

所以一次memory access流程差不多是这样:

OS一般有一个background线程专门做swap out这件事情，叫做swap daemon或者page daemon，用来确保有一小部分memory free（而不是等待完全没有memory才swap out）. 一般有两个量：high watermark(HW)和low watermark(LW). 当free memory小于LW的时候，这个daemon thread会被出发swap out pages，直到有HW free pages.

jasperzhong commented 2 years ago

Ch22: Beyond Physical Memory: Policies

讲page替换策略，和cache的都差不多，无非就是那么几种: FIFO, Random, LRU. 关于LRU，讲了一个近似算法，有点意思.

How does the OS employ the use bit to approximate LRU? Well, there could be a lot of ways, but with the clock algorithm [C69], one simple approach was suggested. Imagine all the pages of the system arranged in a circular list. A clock hand points to some particular page to begin with (it doesn’t really matter which). When a replacement must occur, the OS checks if the currently-pointed to page P has a use bit of 1 or 0. If 1, this implies that page P was recently used and thus is not a good candidate for replacement. Thus, the use bit for P set to 0 (cleared), and the clock hand is incremented to the next page (P + 1). The algorithm continues until it finds a use bit that is set to 0, implying this page has not been recently used (or, in the worst case, that all pages have been and that we have now searched through the entire set of pages, clearing all the bits).

效果看上去还行

还有一个idea是区分clean page和dirty page，这是注意到clean page是不需要替换的，所以OS可以优先选择“替换”clean page（其实就是直接删除这个page）.

以上说的是swap out. swap in一般是on-demand的，有时候也会prefetch. 比如一些系统会假设如果fetch了code page P，那么code page P+1也可能会被fetch所以就可以prefetch.

jasperzhong commented 2 years ago

Ch23: The VAX/VMS Virtual Memory System

讲了一个具体的例子. 蛮经典的.

其Virtual Address Space是这样的. 一半空间都留给了OS. 用户空间再分为P0（user code + user heap）和P1（stack）. 所以一共需要三个segment (P0, P1和S，S是system).

在context switch的时候，只改P0和P1的base/bound register，S不用改. 这样同一个kernel可以map到各个不同进程的地址空间里面. 妙啊.

注意，P0的第一个page标记为invalid的，这使得dereference null pointer变成非法操作. 妙啊.

page replacement采用的是segmented FIFO策略（两级FIFO表），另外替换的时候会做batch，提高写入磁盘效率.

另外还有两个优化: demand zeroing和copy-on-write (COW).

zeroing是在进程要求分配一个新的页表的时候，OS会把这个新页表的内容清零，这是为了防止这个进程看到其他进程之前的内容. demand zeroing是指只有当这个进程真正要用到这个页表的时候，才会做zeroing，而不是一分配就做.

copy-on-write (COW)是很常见的技巧. fork()里面有用到. 页表需要被拷贝到另一个进程的地址空间的时候，OS不会立刻就做拷贝，而只是做一个map，然后设置为read only. 只有当有一个进程要对该页进行写入的时候，才会去开一个新页表，放入要写入的数据，然后重新map这个页表到要做写入操作的进程的地址空间. COW是非常有用的优化. 尤其是对于fork() + exec()这个范式，可以减少不必要的拷贝.

jasperzhong commented 2 years ago

part 2 concurrency我之前基本阅读过. 总结成了一个PPT.

https://docs.google.com/presentation/d/1ps99MB6T8YHpeAtt-lX1SnZzWCGp8Nnd02rEQg3YbLw/edit?usp=sharing

简单来说，多线程需要两种机制:

lock: 用来实现mutual exclusion for critical section. 其实现需要特殊的硬件指令(test-and-set, compare-and-swap etc.)和OS提供的system call (park() / unpark()).
condition variable: 线程间同步. wait() / signal().

jasperzhong commented 2 years ago

Ch36: I/O Devices

对I/O Devices的基本介绍. 先简单了解下IO device是什么样的. 一般可以看作两部分，一个是对外的接口，一般就是几个寄存器，另一部分是内部实现，可能包括一些软件和硬件.

基本只需要记住OS和IO devices的交互协议一般会使用poll或者interrupt. 可以用DMA传输数据. 交互具体方法有特殊的指令，比如x86里面的in/out指令，以及memory-mapped I/O.

memory-mapped I/O很有意思. 硬件将其device register 映射到memory位置上. OS如果要访问特定的device register，直接使用load/store指令就行了. 硬件会将其自动路由到device而不是memory上.

jasperzhong commented 2 years ago

Ch37: Hard Disk Drives

介绍了磁盘的工作原理. 基本需要知道seek, rotation是怎么一回事就行了.

磁盘IO时间由三部分组成.

seek和rotation一般都需要几毫秒. 所以如果写入的数据量太小，seek和rotation time会占据主要IO时间. 这就是为什么sequential write吞吐要高. 见下表.

jasperzhong commented 2 years ago

Ch38: RAID

RAID基本就是一个小型的分布式存储系统了. 蛮有意思的. 最简单的就是完全不带冗余的RAID-0，以及镜像冗余的RAID-1. RAID-4和RAID-5利用校验码来恢复数据，非常聪明. SOTA看来是RAID-5.

jasperzhong commented 2 years ago

Ch39: Interlude: Files and Directories

基本是Linux file system的interface. 比较重要的概念是inode. 每个文件对应一个inode. 但是一个inode可以对应多个文件 (通过link()). inode是file system内部的data structure. 删除一个文件（比如rm）通常只是unlink()这个文件，只有当这个文件的link reference count为零时，才会真正删除.

jasperzhong commented 2 years ago

Ch40: File System Implementation

一口气看完, 很爽啊. 讲了FS的基本实现. 首先介绍disk一般被划分为一个一个block. 一般包括一个inode table，bitmap和superblock. inode table最大能放的inode数量决定了这个文件系统所能支持的最大文件数量.

注意disk不是byte addressable的，而是有很多addressable sectors. 所以为了访问一个block，需要首先计算访问哪个sector.

FS最核心的是inode，这是file内部的metadata，比如谁拥有整个文件，文件访问模式（读写执行），文件大小，访问时间，创建时间，修改时间等等. 其中最重要的是disk pointers. disk pointer指向一个data block. 为了支持很大的文件，disk pointers可以分级，即disk pointer指向一个block，这个block里面全是disk pointers.

Directory也是文件，只不过类型是目录. 所以Directory也有inode，这个inode也存在inode table里面. Directory里面的内容一般是一个列表（entry name, inode number）（也可以是B-tree）. 如下图.

读写文件涉及的I/O操作很多. 书里面花了很多篇幅介绍细节. 大概的过程一般是要traverse整个pathname，每一次都要访问对应的inode，然后读取对应的data block. 有时候还需要更新inode和bitmap. 很麻烦. 所以一个优化是做cache in memory. 很多现代操作系统会对vertual memory pages和file system pages使用一个统一的unified page cache.

做cache有很多好处. 对于读操作来讲，第一次访问一个文件需要进行完整的读写操作. 但是第二次访问这个文件的时候，这个文件的数据都已经cache在memory里面了，所以不需要进一步做disk IO. 而对于写操作，可以batch很多update来提高throughput，而且还可以避免一些不必要的读写操作（比如创建了一个文件然后删了）. 现代操作系统一般会对写操作buffer 5-30s. 居然这么久...如果不想cache write，直接调用fsync(). 一些database system甚至会绕过FS直接调用raw disk interface.

jasperzhong commented 2 years ago

Ch41: Locality and The Fast File System

讲了如何利用locality来优化之前的说的naive FS. 最早的FS把disk当作memory一样对待，结果性能很差. 后来出现了FFS (fast file system)，提出了很多优化策略. 最核心的idea就是locality. 主要是把blocks分组. 这里分组用的是cylinder group，是一些物理上相邻的tracks. 每一个组都有一个自己superblock（每个组一样，用于reliability）bitmap，inode table和data blocks.

然后采取一些heuristics.

同一个文件夹下的文件放在一个组内
同一个文件尽量放在同一个组内. （如果不够，可以用indirect disk pointers扩展）

还有一些其他的优化. 比较有意思的是parameterization. 比如在顺序读取的时候，已经读完了block 0，即将读取block 1，但是此时head可能已经转动到其他block上去了...如果block是顺序存放的，那么需要一个完整的rotation才能读取block 1. 所以FFS将逻辑上顺序的blocks在物理上间隔排列. 如图所示.

当然，如何选择间隔大小，是需要利用磁盘的转速等信息计算的. 所以这个优化叫parameterization.

现代的FS，比如Linux ext2 ext3等都是继承了FFS很多ideas. 总之，最重要的一个lesson是: treat the disk like it's a disk.

jasperzhong commented 2 years ago

Ch42: Crash Consistency: FSCK and Journaling

挺有用的，讲了如何故障恢复. 先说说故障本身. 由于write data一般需要更新metadata (inode, bitmap)，如果crash发生在update metadata和real data之间，那么就有一致性问题 (crash-consistency problem). 书中讨论了其中所有的可能.

主要方法有两个:

FSCK. 事后扫描整个磁盘. 让metadata一致. 但缺点是很慢. 而且不能解决metadata指向garbage的问题（因为real data还没写入）.
Journaling. 也叫write-ahead logging. 这是被广为采纳的方法. 即在write data之前，先log到磁盘上. 等log commited了，才会去真正写入数据. 实现这个功能的核心是每个transcation有一个TxB/TxE Block，只有log写入成功后，才会写入TxE Block.

分两种方法. data journaling，会把real data也放入log里面.

metadata journaling，不放real data到log. 但需要先写入data.

这里面的有一个很重要的idea: write the pointed to object before the object with the pointer to it. 这是解决很多crash-consistency problem的核心. 确实如此.

jasperzhong commented 2 years ago

Ch 43: Log-Structured File Systems

终于明白了LFS. 看完想尝试下btrfs了 😄

general idea就是不会inplace更新文件，而是不断写入每次update，就像是写入log一样，所以叫做log-structured file systems. 这样写入可以buffer起来，做一次large contiguous的写入，就很高效. 细节不多说了，书里写的很详细.

jasperzhong commented 2 years ago

Ch 44: Data Integrity and Protection

之前分析的都是fail-stop model: 设备要么工作，要么完全故障. 在实际中还有其他fail modes，比如fail-partial. 具体来说有两个常见的故障：latent-sector erros (LSEs)和block corruption. fail-partial disk failure model是指磁盘看上去是工作的，但是可能有一个或者多个block是无法访问的（LSEs），或者包含了错误的内容（block corruption）. 因此，在访问一个seemingly-working的磁盘，可能返回一个error，也可能是返回错误的数据.

处理LSEs: 比较straightforward. 因为访问故障的数据块的时候磁盘会抛出一个故障，所以处理办法就是去访问replica.
处理block corruption: 需要checksum，常见的算法是CRC. 每个block都需要一个checksum. 空间开销为8byte per 4KB data block，很小. 时间开销略大，因为每次访问数据都需要验证checksum对不对. 另外FS会定期做disk scrubbing，检查磁盘每一个block的checksum是否正确. 有了checksum后，如果检验checksum失败，也是去访问replica.

看来replica很重要啊.

jasperzhong commented 2 years ago

Ch 45: Distributed Systems

分布式系统crash course. 分布式系统要解决的最重要的问题就是how to build systems that work with components fail.

首先是通信，packet loss is fundamental in networking. 解决办法很简单: timeout/retry + ack + sequence number. 这就是TCP的机制.

那么上面使用的抽象呢？有一个办法是DSM（distributed shared memory），让不同机器上的进程可以共享同一个虚拟地址空间. 具体实现一般是出现page fault的时候，会向对应的机器请求fetch page. 这种方法很不实用，因为没有处理failure. 如果一台机器挂了，那么进程上的地址空间一部分就无法访问了.

构建分布式系统最常见的抽象还是RPC. 这个比较熟了. 不多说了. 有趣的是，书中提到实现RPC一般用的是UDP，这是为了性能考虑，在RPC层利用timeout/retry + ack等机制再去实现reliability.

另外有一个概念叫做end-to-end argument. 感觉用中文不太好翻译. 大意是即便底层的网络通信已经是reliable的，最上层（一般是应用层）也得负责实现reliability（比如检查checksum）. 感觉是这个意思.

The end-to-end argument makes the case that the highest level in a system, i.e., usually the application at “the end”, is ultimately the only locale within a layered system where certain functionality can truly be implemented.

jasperzhong commented 2 years ago

Ch 46: Sun's Network File System (NFS)

有趣. NFS原来是multi-client, single-server的架构.

碰到最主要的问题是crash-consistency. 解决办法是stateless，其实就是让每个操作都是幂等(idempotency)操作. 幂等确实是非常有用的特性. 如果一个操作是幂等的，那么执行多少便这个操作造成的结果都是一样的，也就是没有副作用. 对于failure recovery来讲，经常需要需要重复做一些操作，如果这些操作是幂等的，那么failure recovery就非常straightforward，直接重做这些操作就行了. NFS是通过让每一个server request都包含了需要完成这次请求的所有信息实现了幂等操作.

其他还谈到了cache的问题. 比如如果client cache了写操作，那么server上的文件可能并不是最新的，如果这时候有另一个client去读这个文件，就有不一致的问题. 这个问题叫做update visibility. 解决办法是flush-on-close，即在client close这个文件的时候，需要把buffer里面的dirty data全部flush到server上. 另一个问题是stale cache，即读取的cache可能已经不是最新的了（有其他client更新了这个文件的数据），解决办法是每次读文件的时候会向server请求这个文件的attribute，其中包括了上次修改时间，如果修改时间比cache要更新，那么就可以判断cache是stale了. 书中说这个方法会导致NFS server was floeeded with GETATTR requests. 因为每一次写操作都要做一次GETATTR，即问一遍server这个文件有没有被update. 一个补救办法是引入attribute cache，几秒钟去做一次GETATTR操作. 但这样，这几秒钟时间内读取cache可能就是stale的.

jasperzhong commented 2 years ago

Ch 49: The Andrew File System (AFS)

还是multi-client, single-server的model. 和NFS的设计完全不一样. AFS的open操作需要把整个文件copy到local disk上...相当于做了cache. 后续的所有read/write全都是local的. 直到close文件才写回到server. 另外，利用callback来实现cache consistency，即不是client主动去询问server是否这个文件有做改动，而是当发生改动的时候，server主动告诉client这件事，使cache失效. 这个idea有点意思，用一句话概括，就是: interrupt rather than polling. 不过我不知道这个callback要怎么实现.

不过AFS已经没什么人用了. NFS用的人多.

jasperzhong commented 2 years ago

Appendix B: Virtual Machine Monitors

简单讲解了VMM(Virtual Machine Monitors)的工作原理. 一般的进程有context switch. VMM有machine-switch (我觉得叫OS switch更好). 下图是如何做system call.

另外一般OS运行在user mode. VMM需要做一些page-table保护措施.

关于如何virtualize memory. 方法比较straightforward. OS以为自己用VPN映射到的是PFN，其实不是，这只是VMM的VPN...然后VMM自己也有page table，这次映射的是真·PFN （这里叫作MFN）.

TLB也要复杂一点.

TLB miss进入的不是OS的TLB miss handler，而是VMM的TLB miss handler. TLB miss handler会调用OS的TLB miss handler，里面会查询页表，找到PFN，然后更新TLB里面的VPN -> PFN 映射. 但是，更新TLB操作是priviledge的，于是操作又转到VMM，VMM会转而更新自己的页表，建立PFN -> MFN映射，然后直接返回.

jasperzhong commented 2 years ago

算是读完了...OSTEP真的大大提高了我对OS的认知. 必读.

jasperzhong / cs-notes

OSTEP #17

ch02: introduction ot operator systems

ch4: the abstraction: the process

ch5: interlude: Process API

Ch 6: Mechanism: Limited Direct Execution

Problem 1 Restricted Operations

Problem 2 Switching Between Processes

补充：Interrupt

Overview

x86 Interrupt Vectors

Hardware Implementation

Linux System Calls Implementation

Ch 7: Scheduling: Introduction

Ch 8: Scheduling: The Multi-Level Feedback Queue

Ch 9: Scheduling: Proportional Share

Ch 13: The Abstraction - Address Space

Ch14 Interlude: Memory API

Ch15: Mechanism - Address Translation

Ch 16: Segmentation

Ch17: Free-Space Management

Ch18: Paging

Ch19: Paging: Faster Translations (TLBs)

Ch20: Paging: Smaller Tables

Ch21: Beyond Physical Memory: Mechanisms

Ch22: Beyond Physical Memory: Policies

Ch23: The VAX/VMS Virtual Memory System

Ch36: I/O Devices

Ch37: Hard Disk Drives

Ch38: RAID

Ch39: Interlude: Files and Directories

Ch40: File System Implementation

Ch41: Locality and The Fast File System

Ch42: Crash Consistency: FSCK and Journaling

Ch 43: Log-Structured File Systems

Ch 44: Data Integrity and Protection

Ch 45: Distributed Systems

Ch 46: Sun's Network File System (NFS)

Ch 49: The Andrew File System (AFS)

Appendix B: Virtual Machine Monitors