操作系统三个关键：虚拟化( virtualization) 并发(concurrency) 持久性（persistence）

1 CPU虚拟化

1.1 进程

虚拟化CPU：许多任务共享物理CPU，让它们看起来像是同时运行。

时分共享：运行一个进程一段时间，然后运行另一个进程，如此轮换，以此实现虚拟化。

进程创建：将代码和所有静态数据加载到内存中，分配栈内存并初始化，初始化I/O等模块，执行main()函数

进程三种状态：运行、就绪、阻塞

数据结构：操作系统会保存进程相关的信息，比如进程列表，寄存器上下文等。

进程API：

• fork()：进程分裂出一个子进程，会获得父进程的内存、句柄等资源的副本。
• wait()：等待任意一个子进程执行完毕
• exec()：将当前进程替换为一个新程序

这种fork()及exec()的方式有利于编写shell脚本。

1.2 机制：受限直接执行

虚拟化CPU两个关键问题：高效、可控

受限直接执行：程序直接在CPU上运行，但指令执行和执行时间受到限制。
用户程序运行于用户模式，执行I/O等操作是受限的；操作系统运行于内核模式，允许执行受限操作。
程序执行受限操作时，需要执行系统调用，此时会陷入内核模式，操作系统执行完操作后，再从陷阱返回到用户模式。陷入内核会保存进程的寄存器以及程序计数器，从陷阱返回时恢复。
系统启动时会初始化陷阱表，告诉CPU陷阱指令对应的处理程序地址。

进程切换：程序是直接运行在CPU上的，此时操作系统并没有运行，操作系统需要重新获取CPU控制权，才能进行进程切换。获取控制权有两种方式：

• 协作方式
  进程执行系统调用、或执行一些非法操作时，会将CPU的控制权转移给操作系统，若程序进入死循环，则无法切换
• 非协作方式
  通过时钟中断，中断同样是陷阱指令，时钟设备可以每几毫秒产生一次中断，中断时会执行操作系统的中断处理程序

进程切换时系统会执行上下文切换：把当前程序寄存器保存到它的内核栈，然后从即将执行的程序的内核栈恢复寄存器。

1.3 进程调度

指标：

• 任务周转时间：任务完成时间减去任务到达系统的时间。
• 响应时间：从任务到达系统到首次运行的时间
• 公平

非抢占式调度：一个任务完成，再执行下一个任务
抢占式调度：可以中断一个任务，执行另一个任务

先进先出（FIFO）
先到的任务先执行，非抢占式。若短时间任务排在长时间任务之后，会导致平均周转时间很长。

最短任务优先（SJF）
先运行时间最短的任务，非抢占式。平均周转时间优于FIFO。

最短完成时间优先（STCF）
每当新任务进入时，执行剩余时间最少的任务，抢占式。平均周转时间优于SJF。

以上调度算法适用于批处理系统，响应时间和交互性很差。

轮转（RR）
一个工作运行一个时间片，然后切换到下一个任务，依次循环。抢占式。
时间片越短响应性越好，但上下文切换的成本影响整体性能。
任务在I/O期间不会使用CPU，此时可以切换到下一个任务。

调度：多级反馈队列(MLFQ)

目的：在运行过程中学习进程的特征，做出更好的调度决策，以此优化周转时间和响应时间。

一种具体算法：为每个工作设置一个优先级，优先级会动态改变，满足以下规则

1. 如果A的优先级 > B的优先级，运行A。
2. 如果A的优先级 = B的优先级，轮转运行A和B。
3. 工作进入系统时，放在最高优先级。
4. 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级。
5. 经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

调度：比例份额

目的：确保每个工作获得一定比例的CPU时间

一种具体实现是彩票调度，每个进程获得一定数量的彩票，每次调度时随机抽取彩票，以此决定调度哪个进程。难点在于如何分配彩票，常用于虚拟机等容易确定额度的系统中。

1.4 多处理器调度

多处理器与单处理器的区别在于对硬件缓存的使用，以及多处理器之间共享数据的方式。

缓存是基于局部性的概念：

• 时间局部性：指当一个数据被访问后，它很有可能会在不久的将来被再次访问，比如循环代码中的数据或指令本身。
• 空间局部性：指当程序访问地址为x的数据时，很有可能会紧接着访问x周围的数据，比如遍历数组或指令的顺序执行。

缓存一致性：
多个CPU同时访问内存会出现缓存一致性问题，即一个CPU在本地缓存中修改了数据，新的值不会立即同步到内存，此时另一个CPU读取内存的值，就会出现两个CPU看到的值不一致。硬件提供了基本解决方案：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性，比如总线窥探技术。
但是跨CPU访问仍需要使用互斥原语或无锁数据结构来保证正确性。比如多CPU修改同一个队列。

总线窥探：每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如果CPU发现对它放在缓存中的数据的更新，会作废本地副本，或更新它。

缓存亲和度
多处理器调度还有缓存亲和度的问题：一个进程在某个CPU上运行时，会在该CPU的缓存中维护许多状态。下次该进程在相同CPU上运行时，由于缓存中的数据而执行得更快。

单队列多处理器调度(SQMS)
与单处理器调度类似，将所有工作放入一个单独的队列中，问题在于多CPU访问队列需要加锁，性能损失极大，而且不能很好的保证缓存亲和度。

多队列多处理器调度(MQMS)
每个CPU有一个队列，可以减小加锁损失，且具有良好的缓存亲和度，问题是不同队列负载不均衡。
实现负载均衡的方法是让工作跨CPU迁移，一种具体实现是工作窃取技术：工作量较少的队列不定期地“偷看”其他队列，如果目标队列比源队列更满，就“窃取”一个或多个工作。

现代操作系统的调度算法有O(1)调度程序、完全公平调度程序（CFS）以及BF调度程序（BFS）等。

2 内存虚拟化

2.1 抽象：地址空间

早期系统只运行一个程序，内存简单分为操作系统部分和程序部分。

后来出现运行多道程序的时分系统，最简单的方式是CPU程序切换时，将程序内存全部保存到硬盘上，再将下一个程序从硬盘加载到内存中。缺点是读写硬盘效率低下。

可以在进程切换时，仍将进程信息保留在内存中，每个进程拥有一部分内存，如下图所示：

此时就出现了内存保护的问题：我们不希望一个程序读、写另一个程序的内存。所以操作系统抽象出了地址空间，即一个进程可见的内存，进程的地址空间包含程序的所有内存状态，包括代码、堆、栈等，如下图：

地址空间是操作系统提供的内存抽象，是从0开始的连续空间，而程序可能加载在物理内存的任意位置，操作系统需要将地址空间中的虚拟地址与物理内存地址对应起来。这便是内存虚拟化的关键。

虚拟内存的实现有3个目标：

• 透明：程序感知不到内存虚拟化的存在，就和独占一整个物理内存一样
• 效率：包括时间效率和空间效率
• 保护：一个进程不会影响其他的进程，也不影响操作系统本身

内存操作API：

• 进入函数时，会在栈上分配函数内的局部变量，函数退出时释放内存
• malloc() 分配堆内存
• free() 释放堆内存
• 其他还有 brk、sbrk、mmap、calloc、realloc 等

2.2 机制：地址转换

地址转换：硬件对每次地址访问进行处理，将指令中的虚拟地址转换为实际物理地址。

动态重定位：每个CPU需要两个寄存器，基址寄存器和界限寄存器，基址寄存器存储进程在物理内存中的实际加载地址，此时，物理地址 = 虚拟地址 + 基址。而界限寄存器提供了访问保护，若进程访问超过界限的地址，CPU会发生异常。

CPU的这个负责地址转换的部分统称为内存管理单元(MMU)。

动态重定位存在资源浪费：必须将进程的地址空间完整的加载到连续的物理内存上。

分段：将地址空间分为代码、栈、堆等不同逻辑段， MMU为每个逻辑段分配一对基址和界限寄存器。这样，只有已使用的内存才在物理内存中分配空间。

段错误：在支持分段的机器上内存访问超过界限。也用于不支持分段的机器。

分段的地址转换方式：

• 显式方式：用虚拟地址的开头几位来标识不同的段。
• 隐式方式：硬件通过地址产生的方式来确定段。例如，如果地址由程序计数器产生，那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他地址则在堆段。

栈是反向增长的，所以硬件除了记录基址和界限，还需要记录段的增长方向。

支持共享：硬件为每个段设置保护位，标记是否可读写、执行，并检查程序内存访问是否允许。这样不可写的段就可以被多个进程共享。

分段粒度：上述的分为代码、栈、堆三个段是粗粒度分段。早期有的系统会划分大量较小的段，称为细粒度分段，这种分段需要进一步的硬件支持，并在内存中保存某种段表。

分段的操作系统支持：

1. 上下文切换时，各个段寄存器中的内容必须保存和恢复
2. 管理物理内存的空闲空间。由于每个程序的每个段大小不同，物理内存中会有很多不连续的空闲空间，这种问题被称为外部碎片。一种解决方案是紧凑物理内存，重新安排原有的段。另一种是利用空闲列表管理算法，试图保留大的内存块用于分配。

空闲空间管理
管理空闲空间的数据结构称为空闲列表，记录哪些空间还没有分配，如下所示：


分配内存时，从空闲列表找到合适的空间，并更新列表。释放内存时，会对列表进行合并。

查找可用空间的具体策略有最优匹配、最差匹配、首次匹配、下次匹配、分离空闲列表、伙伴算法等。

2.3 分页

分页：将进程的地址空间分割成固定大小的单元，每个单元称为一页。相应地，把物理内存看成是定长槽块的阵列，叫作页帧。每个页帧包含一个虚拟内存页。
示例：

页表：操作系统为每个进程创建的数据结构，记录地址空间的每个虚拟页放在物理内存中的位置。

典型页的大小一般为4KB。

两个进程可以共享同一物理页，比如代码页。

快速地址转换TLB:
TLB是虚拟到物理地址转换的硬件缓存，会缓存页表中的部分映射关系。
由于TLB只对当前进程生效，所以上下文切换时，要么清空TLB，要么TLB支持多进程，方式是在TLB中添加表示进程的地址空间标识符。
替换策略：RLU(最近最少使用)或随机策略。

页表实现方式：

• 线性页表：基于数组的页表，占用内存大。
• 大型页：可减少TLB内存占用，但是会导致内部碎片。
• 分段+分页：为进程的每个逻辑分段(代码、堆和栈)提供一个页表。MMU中的基址寄存器保存分段的页表的物理地址，界限寄存器用于指示页表的结尾。
• 多级页表：树形结构，将页表分成页大小的单元，如果整页无效，就不分配该页的页表，然后使用页目录记录页表单元。
• 反向页表：物理页映射到虚拟页，整个系统只有一个，并建立散列表。

2.4 交换空间

程序的地址空间超过物理内存大小时，需要将一部分地址空间存到磁盘等大而慢的设备上。

交换空间： 在硬盘上开辟一部分空间用于物理页的移入和移出。

如果一个物理页已被交换到硬盘，访问该页会产生页错误，操作系统会将该页交换到内存中。

页交换策略： 决定哪些页被交换出内存，具体策略有FIFO、随机、LRU、近似LRU等。

3 并发

3.1 并发介绍

线程：进程可以有多个线程，和进程类似，每个线程有自己的程序计数器、寄存器，线程切换会发生上下文切换。一个进程的每个线程有自己的栈空间，共享堆空间。

共享数据：
以下代码，假设两个线程各执行一次mythread()，执行1000万次+1操作，那么预期结果应该是2000万。

static volatile int counter = 0;

void mythread()
{
    for (int i = 0; i < 1e7; i++) {
        counter = counter + 1;
    }
}

然而实际的结果可能不是2000万，原因是，counter = counter + 1 实际的汇编代码可能是：

mov 0x8049a1c, %eax 
add $0x1, %eax
mov %eax, 0x8049a1c

这个例子假定，变量counter位于地址0x8049a1c。在这3条指令中，先用x86的mov指令，从内存地址处取出值，放入eax。然后，给eax寄存器的值加1（0x1）。最后，eax的值被存回内存中相同的地址。

假设counter=50，线程1先执行前2条汇编指令，此时eax=51，然后发生时钟中断，切换到线程2运行。
线程2执行了全部的3条指令，将共享变量counter设为51(每个线程都有自己的专用寄存器)。
然后又发生了一次上下文切换，线程1恢复运行，线程1的eax=51，执行mov，counter再次被设置为51。
所以，counter = counter + 1 代码执行了两次，counter的值却只增加了1。

此段代码称为临界区，即访问共享资源的代码片段，资源通常是一个变量或数据结构。

这种情况称为竞态条件，出现在多个线程同时进入临界区时，它们都试图更新共享资源，导致了意外的结果。

不确定性程序由一个或多个竞态条件组成，程序的输出因运行而异，具体取决于哪些线程在何时运行。

我们真正想要的代码就是所谓的互斥。这个属性保证了如果一个线程在临界区内执行，其他线程将被阻止进入临界区。

原子性：原子性是指作为一个单元，要么全部执行，要么没有执行。以上例子，如果counter = counter + 1是一个原子操作，则不会有不确定性问题。

同步原语：指硬件提供的一些指令，用于受控的访问临界区，产生确定的结果。

3.2 锁

锁：为临界区加锁，保证临界区能够像单条原子指令一样执行。

1    lock_t mutex; // 锁，为全局变量
2    ...
3    lock(&mutex); // 获取锁
4    balance = balance + 1; // 临界区代码
5    unlock(&mutex); // 释放锁

锁变量保存了锁在某一时刻的状态，要么是unlocked，表示没有线程持有锁，要么是locked，表示有一个线程持有锁。锁也会保存其他的信息，比如持有锁的线程，或请求获取锁的线程队列。

调用lock()尝试获取锁，如果没有其他线程持有锁，该线程会获得锁，进入临界区。如果有其他线程持有锁，该线程会等待。 持有锁的线程调用unlock()释放锁，此时如果有等待线程，其中一个会获取该锁，进入临界区。

锁评价标准：

1. 提供互斥，能够阻止多个线程进入临界区
2. 公平性，竞争线程有公平的机会抢到锁，或者说是否有竞争锁的线程会饿死，一直无法获得锁
3. 性能，有几种场景：只有一个线程、一个CPU上多个线程竞争、多个CPU上多个线程竞争

锁的实现方式

锁由硬件提供的同步原语以及操作系统共同实现。硬件原语有：

• 控制中断
  在单处理器系统上，进入临界区之前关闭中断，可以保证临界区的代码不会被中断，从而原子地执行，结束之后重新打开中断，程序正常运行。
  问题是程序可以通过关闭中断独占处理器、不支持多处理器、关闭中断导致中断丢失。
• test-and-set 指令
  硬件提供test-and-set(原子交换)指令，检查锁的状态是否是unlocked，如果是，则设置为locked。如果不满足，则循环检查。由于该指令是原子的，所以可以满足互斥。
  这种循环检查的锁称为自旋锁。
• compare-and-swap 指令
  该指令检测指针指向的值是否和expected相等；如果是，更新指针所指的值为新值，否则，什么也不做。该指令同样可以实现自旋锁。
• 链接的加载（load-linked）和条件式存储（store-conditional）指令
• 获取并增加（fetch-and-add）指令
  这种方式可以保证所有线程都抢到锁。

自旋锁由于一直自旋占用CPU，可能会产生性能问题，解决方式有：

• 获取锁失败、要自旋的时候，通过yield()系统调用取消调度，让出CPU。
• 使用等待队列：获取锁失败时，线程睡眠，并加入到等待队列中，锁被释放时，唤醒等待队列中的下一个线程。
• 两阶段锁：第一阶段先自旋一段时间，希望可以获取锁，如果没有获得锁，第二阶段调用者会睡眠，直到锁可用。Linux就是这种锁，不过只自旋一次。

基于锁的并发数据结构

• 懒惰计数器
  通过多个局部计数器和一个全局计数器来实现一个逻辑计数器，其中每个CPU核心有一个局部计数器，每个局部计数器有一个锁，全局计数器有一个锁。
  线程只增加局部计数器。局部计数器定期转移给全局计数器，并将自己清0。
• 并发链表
  链表只有一把锁，插入、查找、删除等操作加锁。
• 并发队列 (链表实现)
  有两个锁，一个锁队列头，一个锁队列尾，支持入队和出队操作。
• 并发散列表 (不需要扩展大小)
  每个散列桶（每个桶都是一个链表）有一个锁。

3.3 条件变量

在很多情况下，线程需要检查某一条件满足之后，才会继续运行，比如父线程需要检查子线程是否执行完毕 (称为join)。

当某些条件不满足时，线程把自己加入等待队列。其他线程改变了上述条件时，唤醒一个或者多个等待线程，让它们继续执行。这种思想称为条件变量。

条件变量有两种相关操作：wait() 和 signal()。线程要睡眠的时候，调用wait()。当线程想唤醒等待在某个条件变量上的睡眠线程时，调用signal()。调用signal和wait时要持有锁。

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 = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void thr_join() {
   Pthread_mutex_lock(&m);
   while (done == 0)
       Pthread_cond_wait(&c, &m);
   Pthread_mutex_unlock(&m);
}

生产者/消费者（有界缓冲区）问题：
有一个或多个生产者线程和一个或多个消费者线程。生产者把生成的数据项放入缓冲区；消费者从缓冲区取走数据项。当缓冲区满时，生产者等待，当缓冲区空时，消费者等待。

覆盖条件：用 pthread_cond_broadcast() 代替上述 pthread_cond_signal()，唤醒所有的等待线程

3.4 信号量

信号量(sem_t)是有一个整数值的对象，需要设置初始值

int sem_wait(sem_t * s){
    信号量的值减1
    若值为非负数，直接返回，否则等待
}
int sem_post(sem_t * s){
    信号量的值加1
    如果有等待线程，唤醒其中一个
}

由此可知，信号量值为负数时，表示等待线程的个数。

二值信号量（锁）
把临界区用一对sem_wait()/sem_post()环绕，并将信号量初始化为1，这样就能实现锁。

信号量用作条件变量
一个线程等待条件成立，另外一个线程修改条件并发信号给等待线程，从而唤醒等待线程。

生产者/消费者（有界缓冲区）问题
用两个信号量empty和full分别表示缓冲区空或者满，并用二值信号量加锁。

3.5 常见并发问题

违反原子性缺陷：
代码段本意是原子的，但在执行中并没有强制实现原子性，案例：

Thread 1::
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}
Thread 2::
thd->proc_info = NULL;

非空检查和fputs()是假设原子的，当假设不成立时，代码就出问题了。

错误顺序缺陷：
不同线程的内存访问的预期顺序被打破了。

死锁缺陷：
死锁的四个条件：

• 互斥：线程对于需要的资源进行互斥的访问。
• 持有并等待：线程持有了资源，同时又在等待其他资源。
• 非抢占：线程获得的资源，不能被抢占。
• 循环等待：线程之间存在一个环路，每个线程持有一个资源，而这个资源又是下一个线程要申请的。

预防死锁：

• 循环等待：按固定顺序加锁。全序：设定全部锁的加速顺序。偏序：设定部分锁的加锁顺序。
• 持有并等待：为抢锁的过程加锁。
• 非抢占：获取锁失败时，释放已获取的所有的锁。
• 互斥：使用硬件的原子指令，避免需要加锁。

避免死锁：可以通过处理器调度来避免死锁，如银行家算法。

检查和恢复：允许死锁偶尔发生，检查到死锁时再采取行动。

3.6 基于事件的并发

等待事件发生；当它发生时，检查事件类型，然后做出处理；这是最基础的事件循环：

while (1) {
    events = getEvents(); 
    for (e in events)
        processEvent(e);
}

存在的问题：

• 事件处理程序不允许阻塞调用，I/O需要使用异步I/O。
• 需要手动管理状态，比如发出异步I/O时，必须打包一些程序状态，以便下一个事件处理程序在I/O最终完成时使用。
• 和使用多线程相比，增加了系统的复杂性。

4 持久性

4.1 I/O设备

典型系统架构：

总线分层设计，高性能设备离CPU更近，而外围总线可连接的设备更多。

一个标准设备可分为接口和内部结构两部分，接口通常由3个寄存器组成：

• 状态寄存器，可以读取并查看设备的当前状态
• 命令寄存器，用于通知设备执行某个具体任务
• 数据寄存器，将数据传给设备或从设备接收数据

通过读写这些寄存器，操作系统可以控制设备的行为：

• 轮询，操作系统轮询设备的状态，等待设备就绪
• 中断，设备就绪时抛出硬件中断，引发CPU跳转执行预定义的中断处理程序

利用DMA进行高效数据传送：DMA引擎是一个特殊设备。操作系统告诉DMA数据在内存的位置，要拷贝的大小以及要拷贝到哪个设备。数据传输完成后，DMA会抛出中断通知操作系统。

两种设备交互方式：

• I/O指令，操作系统调用I/O指令，指定一个存入数据的特定寄存器及一个代表设备的特定端口。
• 内存映射I/O，硬件将设备寄存器作为内存地址提供，操作系统通过该内存地址读写设备数据。

设备驱动程序：
封装设备交互的细节，为操作系统提供抽象接口。
驱动程序占据了操作系统大部分的代码，且是系统崩溃的主要原因。