Intro to Operating System

Virtualization

1. 虚拟化最重要的两个部分就是CPU虚拟化和内存虚拟化，通过对这两者进行抽象和虚拟化，即使我们的电脑只有一个CPU和一个物理内存，对于电脑上运行的多个进程来说，它们仿佛在使用自己独立的CPU和内存。其中CPU虚拟化使用的是time-sharing的方法，内存虚拟化使用的是space-sharing的方法。

The Abstraction: The Process

1. 进程就是操作系统对一个正在运行的程序的抽象。简单来看，进程可以分为三种状态：running，ready，blocked，同一时间只能有一个进程正在运行；ready状态表示一个进程已经准备好被运行了，但是还没有轮到它运行；blocked状态表示进程正在进行某些其他操作，所以没有准备好被运行(比如正在进行I/O操作)。

Mechanism: Limited Direct Execution

1. 我们知道操作系统分为用户态和内核态，我们的进程想要访问某些系统级别的操作，就需要使用系统调用(system call或者trap)进入内核态，但是系统调用是如何知道该运行的程序在什么位置呢？答案是内核会在操作系统启动(booting)的时候建立一个trap table，trap table中不同的system call number对应trap handler所在的地址，这样我们的进程在进行系统调用的时候只需要提供system call number就好了，而不需要直接访问我们没有权限的trap handler所在的地址(trap handler属于内核的代码)。图中6.2展示了这种通过系统调用实现的Limited Direct Execution，需要注意的是进程的寄存器信息会被保存在kernel virtual memory的kernel stack处。
2. 前面我们提到CPU虚拟化使用的是time-sharing的方法，也就是每个进程轮流使用CPU，那么一个问题出现了：如何确保某个恶意进程不会一直占用CPU？也就是说如何让操作系统重新获得控制权并决定接下来运行的进程？早期的操作系统选择相信进程，进程会主动把控制权交还操作系统(通过yield system call)，也称作非抢占式(协作)调度;现代的操作系统通过定时中断来收回操作系统的控制权，也称作抢占式调度。不管使用哪种方法，我们都需要一种上下文切换机制，即保留被中断的进程的上下文，并切换到继续运行的新进程的上下文。
3. 书中图6.3展示了上下文切换机制，同时我觉得CSAPP的图8.14也有助于对于上下文切换的理解。首先，我们要清楚的是操作系统内核只是一段可执行代码和数据而已，大多数时候内核代码都是不执行的，而是在运行我们的用户进程代码，只有在遇到trap或者timer interupt的时候，CPU才会切换到内核态并执行内核代码中对应的trap handler。假设我们正在以用户态运行进程A，当遇到定时中断的时候，首先CPU会把当前用户进程的寄存器保存在进程A的kernel virtual memory的kernel stack处；然后切换成内核态并且执行内核代码的switch trap handler，在这个switch trap handler中会进行进程的切换(先保存当前内核态下进程A的寄存器，然后加载以前保存的内核态下进程B的寄存器)；剩下的步骤是前面的镜像。
4. 需要注意的是，上下文切换的过程中有两次寄存器的保存与恢复，第一次在定时中断发生的时候，CPU会把寄存器保存在当前进程的kernel stack上，这是通过硬件实现的；第二次发生在执行内核代码的switch trap handler的时候，当需要从进程A切换到进程B的时候，我们也需要保存当前的寄存器到process control block，这是通过内核代码，也就是软件实现的。
5. 在CSAPP中我们学习过，每个进程都有自己独立的虚拟地址空间，这个虚拟地址空间分为用户虚拟地址和内核虚拟地址，内核虚拟地址空间是内核代码在运行的时候使用的地址空间。在上下文切换的时候，内核代码先使用进程A的kernel virtual memory运行，然后再切换到进程B的kernel virtual memory运行，也就是说内核代码没有自己独立的进程，他只是在进行上下文切换的时候“依附”于A和B进程来运行。所以我觉得CSAPP的这段话说的很好：During the first part of the switch, the kernel is executing instructions in kernel mode on behalf of process A(i.e. there is no seperate kernel process), then at some point it begins executing instructions(still in kernel mode) on behalf of process B
6. 上下文切换的决策，比如下一个该运行系统的哪一个进程是由scheduler决定的，这个会在后面介绍。

Scheduling

1. 进程调度的评价指标包括周转时间（turnaround time）和响应时间（response time）。周转时间是性能指标，评价一个任务从到达到完成的耗时；响应时间是公平性指标，评价一个任务从到达到开始执行的耗时。
2. 进程调度策略的发展线索

   策略	内容	演化	缺点
   FIFO	先到达的任务先执行	最符合直觉的策略	先到达的长任务让后到达的短任务饿死
   SJF (1954)	最短的任务先执行	比FIFO优化了周转时间	任务会随时到达，而在长任务执行时到达的短任务饿死
   STCF	能够以最短完成时间可以抢占其他任务	比SJF增加了抢占机制	无法确定任务的完成时间
   Round Robin	所有进程轮番使用时间片	优化了响应时间	并不是所有的程序都能用完整个时间片，例如IO密集任务
   （重叠式）RR	需要IO的任务让出时间片并在完成前不参与调度	比RR多了对IO考虑	周转时间差于SJF（但总体来说是有效的）
   MLFQ (1962)	见3	在没有任务长短的先验知识下，同时优化了周转时间和响应时间	比前面的算法都复杂（但被Unix，Windows，MacOS系统采用）
   Lottery (1994)	给每个进程分发一定量的彩票，每次调度时随机抽出一个号码，被抽中的进程获得CPU	在给定优先级的环境下优化了公平性	只能在互信环境中使用，需要提前给定彩票数
   Stride (1995)	给每个进程分发一定量的彩票，按彩票数的倒数计算步长，程序被调度一次则累计一次步长值，每次调度已经走过步长值最小的那一个	在给定优先级的环境下到达绝对公平，比Lottery优化了确定性	只能在互信环境中使用，需要提前给定彩票数
   CFS (2007)	见4	在给定优先级的情况下保持绝对公平，比Stride拥有更多细节	比前面的算法都复杂（但一出现就被Linux系统采用）

3. Unix的策略：MLFQ，多级反馈队列（multi-level feedback queue）在没有关于任务时间的先验知识（prior knowledge）的情况下，同时要降低响应时间和周转时间。现今的Windows系统使用的就是优化后的MLFQ调度方式。
   MLFQ包含许多队列，每个队列代表一个优先级（例如Windows有32个优先级）并且对应一个时间配额（time allotment，一般来说高优先级队列的配额低）；进程在这些队列中，并且拥有一个记录其剩余时间配额的“账户”，首次进入一个队列时“账户”的值被设置为该队列的时间配额值。MLFQ调度遵循如下规则：
   当新进程到达的时候（假定该进程完成时间短），将其加入最高优先级的队列；
   调度的时候会选择优先级最高的非空队列，并将该队列中的进程轮转（RR）运行；
   当一个进程被调度后，对该进程的运行时间计时，并在该进程的“账户”中减去对应时长；
   当一个进程的“账户”归零（即用完了该层的时间配额）的时候，进入下一级队列；
   定期将所有进程提升至最高优先级队列。

Mechanism: Address Translation

1. 既然我们想要为每个进程设立独自的虚拟内存，那么我们必然需要一种机制来将进程中的虚拟地址翻译成实际的物理地址，我们首先介绍一种最简单的地址翻译(Dynamic Relocation)，并且根据它身上存在的问题不断改进成现在主流的地址翻译。
2. Dynamic Relocation需要假设：
   • 进程的虚拟地址空间必须被连续的存放在物理地址空间
   • 进程的虚拟地址空间比物理地址空间小
   • 每个进程的虚拟地址空间同样大
     然后Dynamic Relocation需要硬件提供两个寄存器用于地址翻译，分别是base和bound，base寄存器存储的就是对应物理地址的起点，所以virtual address + base就可以得到实际的物理地址；bound寄存器的作用是声明虚拟地址的大小，以防止该进程访问不属于它的虚拟地址。在进行上下文切换的switch handler处，我们需要保存base和bound寄存器的值，因为每个进程的虚拟地址对应的物理地址都不同，他们的base和bound寄存器也不同，如书中图15.6。
3. Dynamic Relocation存在一个很大的问题：物理内存的利用率很低。假设我们虚拟内存的stack和heap之间存在大量没有使用的虚拟内存，如果按照Dynamic Relocation来进行地址映射，那么这些未使用的虚拟内存也需要映射到物理内存上，于是产生了分段(segmentation)的解决办法。分段其实就是一种一般化的Dynamic Relocation，我们把虚拟内存分成不同的段(code，stack，heap)，然后为每个段设置独立的base和bound寄存器，这样的话每个独立的段都可以映射到物理内存不同的位置，并且很好的解决了物理内存利用率低的问题。
4. 分段存在的主要问题有：
   external fragmentation：由于段都是一些大小不一的内存片段，很可能造成物理内存碎片化，也就是两个段之间存在未被使用的物理内存，但是由于太小而无法被使用，我们可以使用一些算法来重新安排段在物理内存中的排列来减少这种内存碎片，但是无疑使得问题变得复杂
   段的粒度还是太大：假设我们有一块很大的heap，但是其中大部分的内存已经被free了，只有很少部分仍在使用，但由于heap段是一个整体，所以这些free的内存也需要存在于物理内存中，这就造成了很大的物理内存浪费

Paging

1. 由于分段存在的问题，很自然的我们想到可以把如果把虚拟内存和物理内存都分成相同大小的“段”，那么前面的问题就可以迎刃而解了，这就产生了现代计算机普遍使用的分页机制。我们把虚拟内存和物理内存都分割成固定大小的页，虚拟内存的页我们称作虚拟页(virtual page)，物理内存的页我们称作物理页(physical page)或页帧(page frame)。
2. 每个进程都需要一个页表(page table)来存储该进程虚拟页和物理页的映射关系，从而来进行虚拟地址到物理地址的翻译。虚拟地址和物理地址都可以被分成两部分，页号(page number)和偏移量(offset)，页号是当前页的编号，而偏移量表明了当前地址在当前页的偏移，这个偏移量对于虚拟地址和物理地址是相同的(因为我们做的是页的映射而不是每个地址的映射，所以地址在页上的位置肯定是固定的)。所以我们可以想到最简单的页表就是线性页表(linear page table)，储存的就是以虚拟页号(virtual page number)为索引的物理页号(physical page number)。
3. 假设我们的虚拟地址被分成了4页(每页16 byte)，物理地址被分成了8页(书中图18.1，18.2)，并且我们的页表如下所示：

   index	physical page number	valid
   0	3	1
   1	7	1
   2	5	1
   3	2	1
   那么地址翻译的过程如图18.3所示，假设我们指令的虚拟地址是010101，由于虚拟地址共分成了四页，所以虚拟地址的前两位01就是虚拟地址的页号，后四位0101就是虚拟地址也是物理地址的偏移，根据01(1)的二进制数作为索引并查询页表，我们可以得到物理地址的页号是111(7)，所以最终翻译得到的物理地址就是1110101

4. 我们把页表的每一条映射关系叫做一个PTE(page table entry)，PTE除了含有物理页号以外，还有其他的一些功能位，比如valid位表示了映射是否有效，前面我们提到过虚拟地址空间的heap和stack之间可能有很多未被使用的内存，这些未被使用的内存在页表中的valid位会设置为0；protection位表示了页的读写权限；present位表示了
   页是否已经被加载进物理内存，还是被swap out到硬盘中。
5. 那么页表存在什么地方呢？由于每个进程都有自己的页表，并且页表可能会很大，所以页表需要储存在内存中，这里我们假设页表存储在物理内存，并且page table base register会存有当前进程的页表的起始物理地址。当我们需要获取页表中的某个PTE并进行地址翻译的时候，就可以根据page table base register储存的页表的起始物理地址 + VPN * sizeof(PTE)得到我们需要的那个PTE的地址，从而从物理内存中获取PTE。page table base register和base还有bound寄存器一样，都是每个进程独有的，所以在进行上下文切换的时候需要保存到process table
6. 现在我们使用的linear page table还有两个很严重的问题：
   • Too slow：当我们需要从内存中fetch一条指令的时候，现在我们需要先去fetch PTE，然后根据PTE的物理地址再去fetch指令，而访问内存比起访问寄存器要慢得多，这使得我们的计算机运行速度慢了一倍，解决的办法是在CPU中添加address translation cache，也就是后面我们要介绍的TLB
   • Too large：假设我们的虚拟内存是32位的，我们所分的页是4KB，那么代表我们的虚拟内存一共有1M个页，所以我们的页表也需要有1M个PTE，假设一个PTE是4 byte，那么一个进程的页表就需要4MB内存，如果计算机中同时有1000个进程在运行，那么光是这些进程的页表就要占据4GB内存，解决的办法是改变页表的数据结构，采用分级的树形结构(Multi-Level Page Tables)

Paging: Faster translations(TLBs)

1. 为了解决上面出现的Too slow的问题，我们需要在CPU中加入一块叫做translation-lookaside buffer的address translation cache，如果我们查找的虚拟地址已经存储在TLB上，那么我们称其为TLB hit，我们可以很快速的得到翻译后的物理地址；如果我们查找的虚拟地址不在TLV上，那么我们称其为TLB miss，这种情况下根据TLB的类型有不同的处理方式。
2. 如果是硬件管理的TLB(hardware-managed TLB)，那么硬件必须知道页表的数据结构，当产生TLB miss的时候，硬件会通过访问页表来找到PTE并完成翻译，比如Intel x86架构的处理器，就使用固定的Multi-Level Page Tables页表结构；如果是软件管理的TLB(software-managed TLB)，那么当TLB miss的时候会触发一个中断，然后操作系统的trap handler会继续处理，由于是代码处理TLB miss，所以页表的数据结构就非常的灵活，无需固定。RISC指令级架构的处理器一般使用软件管理的TLB。
3. TLB是一种fully associative cache，也就是每条line只有一个block(见CSAPP)，所以TLB entry如下所示：

   virtual page number | physical page number | other bits

   其中需要注意的other bits有valid bit，TLB的valid bit与page table的valid bit含义不同。TLB的valid bit表示这条缓存是否有效，一个很常见的应用就是当我们进行上下文切换的时候，需要把当前TLB entry的valid bit flush为0，因为不同进程的虚拟页号范围是相同的，我们不能将上一个进程储存的TLB缓存用于下一个进程；page table的valid bit只是表示这个虚拟页没有被进程使allocate，所以不应该被访问
4. 前面提到在进行上下文切换的时候处理TLB缓存需要谨慎，因为TLB缓存只应该对某个进程有效，所以前面我们说可以flush valid bit，但是这样的效率太低，所以更常见的做法是在TLB entry增加一个adress space identifier(ASID)，用来表示是哪一个进程的TLB缓存。

Paging: Smaller Tables

1. 为了解决上面出现的Too large的问题，我们可以采用Multi-Level Page Tables，也就是分级的树形页表，它的原理其实就是page table of page table，具体见书中图20.3。
2. Multi-Level Page Tables其实也是一种时间与空间的trade-off，因为相比较与linear page table，虽然Multi-Level Page Table节省了空间，但一旦出现TLB miss，那么需要从内存中查询每一级的page table，这无疑增加了操作时间，但由于局部性的存在，大多数时候我们都会遇到TLB hit，所以这种牺牲时间换空间的做法是值得的。Multi-Level Page Tables的另外一个好处就是不像Linear page table那样需要很大的连续空间.

Beyond Physical Memory: Mechanisms and Polocies

1. 前面我们一直假设进程的虚拟地内存很小并且所有进程的虚拟内存都可以放入物理内存中，但是现实中每个进程都有一个很大的虚拟内存，即使大部分虚拟内存没有被使用(不需要映射到物理内存上),但是肯定会出现虚拟页的总数量大于物理页的数量，这个时候我们就需要使用硬盘的交换空间(swap area)。前面我们提过页表的present位表示了
   页是否已经被加载进物理内存，还是被swap out到硬盘中，当我们遇到了TLB miss并且去PTE中查询物理地址的时候，如果发现present位是0，那么表示这块物理页已经被swap out到硬盘中了，于是一个page fault中断会触发trap handler。当从硬盘中取得这块页后，将其加载到物理页中，这时候可能出现物理内存已满的情况，所以需要replacement policy的存在。内存因此也可以看做是硬盘的缓存。
2. 常见的replacement policy有FIFO，random，LRU，LFU。需要注意的是，TLB作为address translation cache，也是需要replacement policy存在的，凡是缓存都需要有replacement policy。

Concurrency

Concurrency: An introduction

1. 前面所有的例子中我们都把进程当做只有一个线程，也就是单线程进程，但是现实中我们需要多线程的进程，因为我们需要在一个进程中同时做多个事情。以浏览器为例子，本身浏览器是一个进程，如果它只有一个线程，那么同一时间只能做一件事，也就是说同时只能访问一个网页，当访问网页的时候浏览器的UI就会卡住。因此我们引入了线程的概念，同一个进程的线程共享虚拟地址空间，也就是说共享地址空间的代码段和heap，但是每一个线程都会有自己独立的stack，同时寄存器也并不共用。由于线程有自己独立的寄存器，所以多个线程间需要进行上下文切换(线程的上下文切换比进程小)，同时类似进程用来保存寄存器状态的PCB(process control block)，线程也有对应的用来保存寄存器状态的TCB(thread control block)。多线程地址空间图见书中图26.1。
2. 由于线程共享相同的地址空间，所以会带来race condition(data race)问题，最简单的例子就是两个线程都对同一个全局变量counter进行100000次加1操作，我们期望最终运行结束counter的结果是200000，但是最后却不是。原因就是我们其实可以把对counter变量加1的操作分解成三步：从内存中取得counter；在CPU中加1；存回内存中，现在我们假设counter的值为0，此时thread1执行1，2步，随后由于中断thread2执行1，2，3步，然后才回到thread1继续执行第3步，那么我们就会发现运行结束后counter的值为1。根本原因就是我们无法预测scheduler在何时进行上下文切换，如果在不恰当的时机进行了上下文切换，就会造成这种race condition。
3. 我们把上面counter = counter + 1称作critical secion，critical section是一段访问共享变量或者共享资源的代码，critical section如果被多个线程并发执行，就会造成race condition。解决的办法就是使critical secion保持mutual exclusion(互斥)，也就是说同一时间只有一个线程可以执行critical section。

Locks

1. 上面我们提到解决race condition的方法是使得critical section保持mutual exclusion，那么mutual exclusion的具体实现就是lock。锁的本质其实是使加锁和解锁之间的代码变成原子性的(atomical)
2. 那么如何构建一个锁呢？最简单的锁称作自旋锁(spin lock)，也就是说如果已经有一个线程获取了锁，其它尝试获取锁的线程会自旋，也就是一直进行while loop。最简单的想法如下：

   typedef struct __lock_t { int flag; } lock_t;
   void init(lock_t *mutex) {
       // 0 -> lock is available, 1 -> held
       mutex->flag = 0;
       mutex->flag = 1;
   }
   void lock(lock_t *mutex) {
       while (mutex->flag == 1)  // TEST the flag
           ; // spin-wait (do nothing)
       mutex->flag = 1; // now SET it!
   }
   void unlock(lock_t *mutex) {
       mutex->flag = 0;
   }

   但其实这是不对的，由于我们的mutex->flag属于线程间共享的变量，所以仍会造成race condition，比如我们假设此时mutex->flag为0，即没有线程持有锁，当一个线程执行完while (mutex->flag == 1)的比较后，恰好scheduler决定进行上下文切换，切换到的线程也进行while (mutex->flag == 1)的比较，由于此时mutex->flag仍旧为0，会导致这两个线程都认为自己拿到了锁。
3. 由此看来，我们想要单纯的使用代码实现mutual exculsion是不可能的，所以我们需要硬件的支持，这些硬件支持的指令我们称作synchronization primitives。这些primitives把本来多个CPU的指令变成一个atomical的指令，所有锁的根本实现都是这些primitives。
4. 本书中介绍了某些primitives：TEST-AND-SET; COMPARE-AND-SWAP(著名的CAP)；FETCH-AND-ADD。下面我们使用TEST-AND-SET证明通过使用这些primitives可以实现自旋锁：

   int TestAndSet(int *old_ptr, int new) {
       int old = *old_ptr; // fetch old value at old_ptr
       *old_ptr = new;     // store ’new’ into old_ptr
       return old;         // return the old value
   }
   
   typedef struct __lock_t { int flag; } lock_t;
   
   void init(lock_t *mutex) {
       // 0 -> lock is available, 1 -> held
       mutex->flag = 0;
       mutex->flag = 1;
   }
   
   void lock(lock_t *lock) {
       while (TestAndSet(&lock->flag, 1) == 1)
           ; // spin-wait (do nothing)
   }
   void unlock(lock_t *lock) {
       lock->flag = 0;
   }

   这里由于TestAndSet是一个硬件支持的原子操作，所以只能有一个线程可以拿到锁。
5. 自旋锁的问题在于当一个线程持有锁的时候，其它想要获取锁的线程会不停自旋，极大的浪费了CPU资源，简单的解决办法是使用yield()系统调用，但是会出现饥饿问题；更好的解决办法是使用队列加park()和unpark()系统调用，当有一个线程持有锁的时候，其它线程调用park()进入睡眠状态，并且我们把线程ID加入队列中，当持有锁的线程释放锁的时候，我们从队列中取出一个睡眠的线程，使其获取锁。由于队列的存在，我们解决了饥饿问题。代码见书中图28.9。

Condition Variables

1. 前面我们介绍了metual exclusion以及它的实现方式锁，但是在多线程同步中还有一类问题，也就是多个线程之间存在执行先后的问题，比如线程2依赖于线程1执行结束后才可以执行，这在实际应用中是很常见的，比如父线程创建了一个子线程，然后调用wait()等待子线程结束。解决这类问题的方法是使用condition variable，也就是说线程会检查某个condition是否为真，如果是的话才继续执行。
2. 书中没有像介绍锁一样介绍condition vairiable该如何构建，而只是介绍该如何使用condition variable。condition variable一般提供两个接口：wait()和signal(condition)，wait(mutex, condition)使得当前线程进入睡眠状态，signal()表示condition以及改变，睡眠状态中的一个线程会被唤醒，变成RUNNABLE(注意只是RUNNABLE，只有CPU切换到这个线程才会变成RUN的状态)。我们注意到wait的一个参数是mutex，也就是锁，这表示当线程调用wait以后会释放这个锁并进入睡眠状态，当其它线程调用signal唤醒这个线程的时候，它会重新获取这个锁。这个锁是很关键的，它确保了这个线程在睡眠前和睡眠后都获取了锁，从而避免了race condition。
3. 下面是使用condition variable来解决父进程等待子进程问题：

   int done  = 0;
   pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
   pthread_cond_t c  = PTHREAD_COND_INITIALIZER;
   void thr_exit() {
       Pthread_mutex_lock(&m); //由于父子进程都对done这个全局变量进行了修改，所以需要加锁
       done = 1; //这个变量是必须的，没有这个变量也就没有了while (done == 0)的比较，那么可能出现子进程先执行，然后尝试唤醒父进程(没用，因为此时父进程还没进入睡眠状态)，子进程执行完后父进程才执行，然后进入永远的睡眠状态。
       Pthread_cond_signal(&c);
       Pthread_mutex_unlock(&m);
   }
   void *child(void *arg) {
       printf("child\n");
       thr_exit();
       return NULL;
   }
   void thr_join() {
       Pthread_mutex_lock(&m);
       while (done == 0) //这里为什么要用while?后面在producer-consumer部分会说明：我们虽然在wait前后都使用了锁，但并不能保证在睡眠期间done变量不被改变为了。保证wait前后done这个变量的一致性，必须使用while loop
           Pthread_cond_wait(&c, &m);
       Pthread_mutex_unlock(&m);
   } 
   int main(int argc, char *argv[]) {
       printf("parent: begin\n");
       pthread_t p;
       Pthread_create(&p, NULL, child, NULL);
       thr_join();
       printf("parent: end\n");
       return 0; }

4. 另外一个可以使用condition variable解决的问题是producer/consumer(bounded buffer)问题。假设我们有一个固定大小队列(bounded)，producer负责向队列中放入数据，consumer负责从队列中获取数据，由于我们producer和consumer使用同一个共享队列，我们当然需要使用锁，但另一个问题是：当队列已经满了的时候，我们如何保证producer不再继续放入数据；当队列已经空了的时候，我们如何保证不再试图获取数据，这就需要用到condition variable。

解法一：Single CV and If Statement

int loops; // must initialize somewhere...
cond_t  cond;
mutex_t mutex;
void *producer(void *arg) {
    int i;
    for(i=0;i<loops;i++) {
        Pthread_mutex_lock(&mutex);
        if (count == 1)
            Pthread_cond_wait(&cond, &mutex);
        put(i);
        Pthread_cond_signal(&cond);
        Pthread_mutex_unlock(&mutex);
    }
}
void *consumer(void *arg) {
    int i;
    for(i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        if (count == 0)
            Pthread_cond_wait(&cond, &mutex);
        int tmp = get();
        Pthread_cond_signal(&cond);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}

假设我们有一个producer和两个consumer，开始的时候队列为空，两个consumer都是RUNNABLE状态，CPU切换到consumer1，由于此时队列位空，所以consumer1进入SLEEP状态，随后producer执行并放入一个数据，调用signal通知consumer1，因此consumer1变成RUNNABLE状态。然后恰好此时CPU切换上下文到consumer2，由于此时count值为1，consumer2会将队列中的值获取，当CPU再次切换到consumer1的时候，consumer从wait处继续执行并尝试获取数据，但此时队列已经为空，造成错误。根本原因就是我们无法保证线程调用wait前后，count变量的值是否被别的线程所改变，所以通常的做法是使用while loop而不是if。

解法二：Single CV and While Statement

int loops; // must initialize somewhere...
cond_t  cond;
mutex_t mutex;
void *producer(void *arg) {
    int i;
    for(i=0;i<loops;i++) {
        Pthread_mutex_lock(&mutex);
        if (count == 1)
            Pthread_cond_wait(&cond, &mutex);
        put(i);
        Pthread_cond_signal(&cond);
        Pthread_mutex_unlock(&mutex);
    }
}
void *consumer(void *arg) {
    int i;
    for(i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 0)
            Pthread_cond_wait(&cond, &mutex);
        int tmp = get();
        Pthread_cond_signal(&cond);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}

当我们使用while loop后，程序仍旧存在问题，假设我们有两个SLEEP的consumer在等待数据，producer在放入一个数据后调用signal通知consumer1使其变为RUNABLE状态，当CPU切换到consumer1的时候，consumer1会获取队列中的数据，然后consumer1会调用signal想要通知producer放入数据，然而由于我们只使用了一个condition variable，signal错误的唤醒了consumer2，consumer2判断count是0，继续进入SLEEP状态，而producer也仍旧在SLEEP状态。这说明了我们需要两个condition：FULL和EMPTY，这两个状态是不同的。

正确解法三：Two CV and While Statement

int loops; // must initialize somewhere...
cond_t  empty, full;
mutex_t mutex;
void *producer(void *arg) {
    int i;
    for(i=0;i<loops;i++) {
        Pthread_mutex_lock(&mutex);
        if (count == 1)
            Pthread_cond_wait(&empty, &mutex);
        put(i);
        Pthread_cond_signal(&full);
        Pthread_mutex_unlock(&mutex);
    }
}
void *consumer(void *arg) {
    int i;
    for(i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 0)
            Pthread_cond_wait(&full, &mutex);
        int tmp = get();
        Pthread_cond_signal(&empty);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}

5. 我们看到Java对于conditiond的官方例子也是bounded bufffer，实现与我们的方法三完全相同：https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/Condition.html

Semaphores

1. 前面我们以及介绍过了mutual excludion和condition variable，所有的concurrent问题都可以使用这两个方法来解决，信号量(Semaphores)在初始化不同值的时候，可以当做mutex，或者当做condition。所以Semaphores其实就是mutex+condition。Semaphores具体的介绍见书。

Dead Lock

1. 死锁的四个条件：

• Mutualexclusion:Threadsclaimexclusivecontrolofresourcesthat they require (e.g., a thread grabs a lock).
• Hold-and-wait:Threadsholdresourcesallocatedtothem(e.g.,locks that they have already acquired) while waiting for additional re- sources (e.g., locks that they wish to acquire).
• No preemption: Resources (e.g., locks) cannot be forcibly removed from threads that are holding them.
• Circular wait: There exists a circular chain of threads such that each thread holds one or more resources (e.g., locks) that are being requested by the next thread in the chain.

Event-based Concurrency(I/O Multiplexing)

1. I/O多路复用指的是使用select()或者poll()系统调用函数监听文件描述符，如果发现有新的读或者写请求，可以使用当前线程(或者新开一个线程)来处理，如果没有，那么阻塞在select()或者poll()系统调用处。
2. Java BIO(也就是最开始的IO包)是阻塞的，假设我们的InputStream连接的是一个网络流，那么我们的InputStream.read()会一直阻塞的等待新的数据，直到client关闭请求；Java NIO是非阻塞的，也就是说假设我们开启的是一个SocketChannel，如果channel中没有新的数据，那么Channel.read(buffer)会直接返回0。使用非阻塞的NIO有什么好处呢？NIO配合I/O多路复用就可以实现高效的处理并发，我们使用I/O多路复用监听socket，当有新的请求的时候，使用NIO读取数据，读取结束以后由于是非阻塞，可以直接返回0并处理下一个请求。所以Java NIO包也提供selector，也就是I/O多路复用。
3. BIO和NIO本质上就是读取数据的时候是阻塞还是非阻塞的区别，所以在读文件系统的时候，没有必要使用NIO，因为文件系统读取速度很快；NIO的主要使用场景是处理网络请求。
4. https://tech.meituan.com/2016/11/04/nio.html，这里有一个对于BIO/NIO/AIO的总结很好：
   以socket.read()为例子：
   传统的BIO里面socket.read()，如果TCP RecvBuffer里没有数据，函数会一直阻塞，直到收到数据，返回读到的数据。
   对于NIO，如果TCP RecvBuffer有数据，就把数据从网卡读到内存，并且返回给用户；反之则直接返回0，永远不会阻塞。
   最新的AIO(Async I/O)里面会更进一步：不但等待就绪是非阻塞的，就连数据从网卡到内存的过程也是异步的。
5. https://www.zhihu.com/question/26943938/answer/1856426252

Persistence

I/O Devices

1. 操作系统与I/O设备交互使用的最简单的协议如下：

   While (STATUS == BUSY)
       ; // wait until device is not busy
   Write data to DATA register
   Write command to COMMAND register
       (starts the device and executes the command)
   While (STATUS == BUSY)
       ; // wait until device is done with your request

   这个协议存在的问题是CPU的运作速度很快，而I/O设备的运作速度较慢，所以让CPU等待I/O设备操作完成的效率很低，解决的办法是使用中断，当CPU把data和commnad写入I/O设备后，就切换上下文去做别的事情，当较慢的I/O操作完成后，会通过中断通知CPU。
2. 另外一个低效率的操作是假设我们希望把一个大文件从内存拷贝到硬盘(I/O设备)，那么CPU在这段时间内只能不断的拷贝数据，不能做其他事情。解决的办法是我们使用一种特定功能的硬件DMA，我们指定想要拷贝的文件的内存地址和目的地，然后DMA会负责文件的拷贝，在这个期间CPU可以用来做其他操作。

Hard Disk Drives

1. 硬盘的主要延迟 = seek delay + rotation delay + transfer delay。seek delay指的是改变track的时间，rotation delay指的是track旋转的时间，transfer delay指的是传输文件的时间。
2. 硬盘最重要的知识是如果传输的是sequential data，那么传输速率很快，但是如果传输的是random data，那么传输速率很慢，原因就是因为传输random data，主要的延迟都耗在seek delay和rotation delay上了。
3. 磁盘的scheduling以及RAID(同时使用多个硬盘，其中有部分作为backup，保证了存储数据的reliability，一般用于大型机房)的内容见书。

Interlude: Files and Directories

1. 文件系统的一个抽象是文件，文件其实就是字节的数组，每个文件都有一个唯一的low-level name，我们称作inode number；文件系统的另一个抽象是目录(directory)。目录本质上也是一个文件，也有唯一的inode number，只不过你目录存放的内容很特别，it contains a list of (user-readable name, low-level name) pairs。
2. 文件描述符(file descriptor)是一个进程私有的integer，在进程中我们使用文件描述符来访问打开的文件，每个进程默认已经打开了standard input(0)，standard output(1)，standard error(2)三个文件描述符，所以后面开启的文件描述符默认从3开始。由于文件描述符是进程私有的，所以必定存在与进程维护的PCB上：

   struct proc {
       ...
       struct file *ofile[NOFILE]; // Open files
       ...
   };

   可以看到每个进程都维护了一个file指针的数组，所以其实file descriptor就是一个索引值。
3. file对象的定义：

   struct file {
       int ref;
       char readable;
       char writable;
       struct inode *ip;
       uint offset;
   };

   可以看到file对象指明了文件的inode，并且也指明了文件当前的offset，所以通过file对象得到inode从而访问文件。
   操作系统会维护一个open file table，里面存有当前系统所有打开的文件：

   struct {
     struct spinlock lock;
     struct file file[NFILE];
   } ftable;

需要注意的是，如果是两个进程打开同一个文件并试图进行操作，那么操作系统会创建两个file对象在open file table中，两个进程分别通过各自进程中的file descriptor引用这两个file对象，它们的inode相同，但offset及其他信息可能不同。
4. 使用fork()创建的子进程与父进程是完全相同的拷贝，所以进程的proc对象也是拷贝过来的，这就导致了父子进程对同一个打开的文件使用相同的file descriptor(索引)，并且都指向同一个file 对象。见书中图39.3。
5. 硬链接(hard link)指的是在创建链接的文件夹中为链接的文件起一个别名，所以其实就是在目录的list of (user-readable name, low-level name)中加一个entry，链接的文件与原文件有不同的user-readable name，但是有相同的inode number。理解了硬链接，我们就可以理解为什么文件系统删除文件的系统调用叫做unlink，因为文件系统删除一个文件的前提是这个文件的reference count是0。
6. 软连接(symbolic link or soft link)类似windows的快捷方式，本质上是文件系统中区别于文件和目录的第三类文件，所以软连接是一种特殊的文件，这类文件存储的是所链接文件的file path。由于软连接只是储存file path，所以会出现dangling reference，也就是说所链接的文件被删除了，但是链接的文件还在，但由于找不到所链接文件的file path，所以称为dangling reference。

File System Implementation

1. 最简单的文件系统称为Very Simple File System(VSFS)，VSFS由五部分组成：
   • Data blocks：这是文件系统大部分的内容，用来储存数据，文件系统把硬盘分成固定大小的block(与硬盘的sector类似，但是sector一般只有512bytes，block会大一些)
   • Inode table：这是储存所有的Inode
   • Data bitmap：指明哪些Data block已经被使用了，哪些是空闲的
   • Inode bitmap：指明哪些Inode已经被使用了，哪些是空闲的
   • Superblock：文件系统的基本信息，包括inodes和data blocks的数量，inode table起始地址等等
     具体的VSFS数据结构见书中图。
2. Inode的全称叫做index node，每一个Inode都有一个对应的number(index)称作inode number(也就是前面我们提到的文件的low level name)，通过inode number(其实就是inode table的index)我们就能够在Inode table中找到对应的Inode。Inode储存的就是一个文件所有的信息：文件大小，文件类型，文件什么时候被创建和修改等等。Inode中最重要的信息是说明这个文件的数据存在Data blocks的什么位置，一般是通过direct pointers，indirect pointers(double indirect pointers，triper indirect pointers…)来引用的。
3. 前面我们提到过目录也是特殊的文件，所以目录也会使用Inode和Data block，只不过目录存储的内容只是user-readable name和inode number的映射。假设某个目录里有foo，bar，foobar_is_a_pretty_longname三个文件，那么目录文件就会如下所示。

   inum | reclen | strlen | name
     5      12        2     .
     2      12        3     ..
    12      12        4     foo
    13      12        4     bar
    24      36       28     foobar_is_a_pretty_longname

4. 前面介绍了VSFS的数据结构，文件系统另一个重要内容是access methods，由于VSFS的数据结构，我们可以发现在VSFS读写数据需要反复读写inode和data block，假设我们需要访问/foo/bar/file1.txt这个文件，那么我们需要先去查看root inode获取root data block，root data block是一个存有映射关系的目录，我们在其中找到foo目录的inode number，然后去查看foo inode以获取foo data block…..以此类推。如果我们想要修改的文件有着很深的路径，那么访问文件的消耗会很大。

Locality and The Fast File System

1. VSFS的主要问题是性能太差，因为inode table和data blocks分布在硬盘的不同位置，所以我们相当于对硬盘进行random access。FFS的主要思想是将硬盘进行分组，每一个组内的结构与VSFS相同(super block，bitmap，inode table，data blocks)，在每个组内放置相关联的文件，比如在同一个目录下的文件。

Crash Consistency: FSCK and Journaling

1. 到目前为止，我们都没有讨论一个很严重的问题：如果硬盘突然断电，文件系统遇到crash应该如何处理。以VSFS为例，由于我们需要更新bitmap，inode table和data blocks，这些操作不可能是原子性，所以会出现我们已经更新了一部分，但是未更新完的情况。比如我们在更新完inode table后断电，还未更新bitmap和data blocks，就会出现data inconsistency的问题，因为在inode table我们的direct pointer已经更新，但是指向的数据并未更新，所以指向的是没有意义的garbage。具体的crash scenarios见书。
2. 早期的操作系统使用的解决办法是File System checker，也就是在文件系统每次启动之前都是用checker检查是否有inconsistency。checker的问题是不能检查出所有的问题，并且随着文件系统变大，checker运作的时间变得过长。
3. 现代的操作系统使用的解决办法称作Journaling(or Write-Ahead Logging)，其原理是在向硬盘写入数据之前，先在硬盘一块特殊的journaling区写入相同的日志，当出现crash的时候，可以通过日志进行文件系统的恢复。具体的journaling过程见书。

Log-structured File Systems

1. 除了前面提到的文件系统，另一种文件系统称作Log-structured File System(LFS)，其采用的原理现在主流文件系统的瓶颈在写操作，LFS会先把写操作buffering在内存中的segment区域(与虚拟内存的segment无关，只是这里的名字)，当segment存满后，会把这些数据sequential写到硬盘一块空的地方，而不是像前面的文件系统那样对已有的位置进行更新。
2. LFS由于每次都会写到硬盘空的位置上，所以对于同一个文件的data block和inode会有多个版本，关键在于我们如何找到最新的版本。LFS采用的方法是在内存中存有一个inode map，inode map存有inode number和最新版本inode的映射，每次进行新的写操作，我们都需要更新inode map，使得对应的inode number一直指向最新版本的inode；
3. LFS另一个问题是Garbage collection，因为我们不会更新老的data block和inode，而是每次都写一个新的版本，所以老的data block和inode需要定期清理。

Flash-based SSDs

1. 闪存芯片由许多block组成，每一个block又有许多page组成(这里的block和page与前面虚拟内存的page以及文件系统的block无关)，pages与blocks的组成见书中图44.1.
2. 闪存有三个操作：
   • 读操作：读一块page的内容
   • 擦除操作：在向一块page进行写操作之前，我们必须先对page所在的block进行擦除操作，否则无法进行写操作
   • 写操作：写一块page的内容
     由于闪存在写之前需要先进行擦除，所以存在wear out问题，也就是一块闪存经过多少次擦除后就会失去存储功能。
3. SSD是由多块闪存组成的存储设备，有一个falsh translation layer负责将对于文件系统block的读写操作转换成对不同闪存的读写操作，具体的组成见书中图44.3。由于SSD由多块闪存构成，我们不希望其中某块闪存被大量使用从而wear out，而是希望这些闪存都被均匀的使用(wear leveling)，从而增加使用寿命。
4. 最简单的FTL的实现就是direct mapped，但是这会导致某些闪存被反复读写从而出现wear out问题，所以direct mapped FTL是一个不好的选择。
5. 现代的FTL的实现是类似前面我们学习的LFS的log structured结构，也就是写操作不会覆盖旧数据，而是在空白区域写一个新的版本的数据，这种结构的FTL提高了SSD的可用性，实现了wear leveling。