一本让我意外的书，从一个简单的helloworld开始，讲出了整本书。相对来说较薄的一本书，但仅仅看了第一章就让我理顺了线程和进程的由来。本以为这本书和CSAPP应该差不多，但很意外，研究生写的书也能这么棒，让我也有了写书的冲动
本书所讲的技术，大多成型在十年前，乃至二十年前，他们是整个计算机行业技术的根本，也几乎是现在所有计算机应用的基础。在当今计算机技术发生根本性变革之前，这些技术还将继续存在并保持活力
操作系统
操作系统的一个功能就是提供抽象的接口，另一个功能就是管理硬件资源
开发工具和应用程序使用一个接口，即操作系统应用程序编程接口（Application Programming Interface），该接口的提供者是运行库（如Linux下的CLibc库提供POSIX的API）
运行库使用操作系统提供的系统调用接口（System Call Interface），该接口的实现往往以软件中断的方式提供
操作系统的内核层对于硬件层来说是硬件接口的使用者，而硬件是接口的定义者
CPU分配
对于CPU的使用机制经历了以下几个历史阶段
- 多道程序：编写一个监控程序，当程序暂时无需使用CPU时，就把另外正在等待CPU资源的程序启动。这种机制的问题就在于调度机制过于粗糙，各种程序之间没有轻重缓急
- 分时系统：每个程序运行一段时间后都会主动让出CPU给其他程序，但这种系统遇到某个死循环程序，也只能等待，就导致系统整个看上去都死机了
- 多任务系统：操作系统接管了所有的硬件资源，本身运行在一个手硬件保护的级别。所有应用程序以进程的方式运行在比操作系统权限更低的级别上，每个进程都有自己的独立地址空间，使得进程之间地址空间相互隔离。CPU由操作系统统一分配，每个进程根据进程优先级获得CPU。当某个程序运行时间超过了一定时间，操作系统就会暂停该进程，把资源分配给其他程序，这种分配方式叫做抢占式
设备驱动
对于操作系统上面的运行库和应用程序来说，它们希望看到的是一个统一的硬件访问模式。在操作系统成熟之前，应用程序的程序员就要直接和硬件打交道，之后硬件就被抽象成了一系列的概念。如在Unix中，所有硬件设备都被抽象为文件；在Windows中图形硬件被抽象为GDI，磁盘被抽象成为了普通文件系统。这些繁琐的硬件细节都交给了操作系统中的硬件驱动程序完成。驱动程序和内核一起运行在特权级上
虚拟内存
早期计算机的程序是直接运行在物理内存上的，可以理解为编译好的程序直接写入了内存条，但是思考一个问题，运行在计算机中的程序肯定不止一个吧，每个程序占用一部分内存，自然就会产生内存不足的现象
这样直接使用物理内存的第一个问题就是内存使用效率不高，例如假设总共有50MB的内存，程序A使用10MB,这里需要明确一点的是程序内存的使用都是连续的，程序B使用30MB，程序C需要20M，显然要把程序A和B的数据都存入磁盘才可以去运行程序C，但是其实将程序A移除后，内存中就已经有20M空闲的内存，但却得不到利用，而且大量的数据在内存和磁盘中移动显然是低效率的
第二个问题就是安全问题，程序内存地址是不隔离的，程序之间可以很容易的访问相互之间的数据，这对于恶意程序显然是个好机会，通过轻易访问其他程序的内存，修改内存内容，执行破坏计算机的程序，想想都有点激动
第三个问题是地址空间的不确定性，每次运行程序对应的物理地址都是不确定的，这次可能是0x0000-0x1111,下次就可能是0x2222-0x3333，这种不确定性会给程序编写造成麻烦，例如如果了解汇编的话，程序跳转都是跳转到特定的地址，也就是说编译之后就会给出特定的内存地址
解决上述问题的方法就是增加中间层，也就是虚拟地址，并通过某些映射的方法（分段和分页），将这个虚拟地址转换成物理地址，这就是虚拟地址带来的好处，但是如果是物理地址就不能带来这种便利
分段
即把一个程序所需要内存空间大小的虚拟空间映射到某个地址空间
这种方法只解决上述问题中的地址隔离和地址不确定问题，但没有解决效率问题。
当程序访问虚拟地址超过了一定范围，硬件就会判断这是一个非法访问，拒绝这个请求，并将这个请求报告给操作系统，由它来决定如何处理
但是分段对于内存映射依旧是按照程序为单位，被换入换出的是整个程序，这就导致了大量的磁盘访问操作，影响效率。事实上根据程序的局部性原理，程序运行时，只会频繁使用一小部分数据，大部分数据并不会被用到，因此就采取了更小粒度的内存分隔和映射方法，也就是分页
分页
把地址空间人为地等分成固定大小的页，每一页的大小由硬件决定或者硬件支持多种大小的页，由操作系统决定页的大小
可以看到进程1某部分虚拟地址被映射到物理地址，一部分被映射到磁盘中。不同的进程可以映射到同一个物理页中，实现内存共享
当进程需要的页不在内存中时，硬件就会捕捉到这个信息，也就是页错误，然后操作系统就会接管进程，将对应的页从磁盘中读出来并装载到内存中，并建立物理页和虚拟页的映射关系
虚拟地址的实现需要硬件的支持，即MMU（Memory Management Unit）来进行页映射，页映射模式下，CPU发出的是Virtual Address，经过MMU转化后变成Physical Address，MMU一般都集成在CPU内部
线程
一直在思考一个问题，既然有了进程的概念，为什么还要有线程的概念？现给出自己的答案
进程的缺点
进程是为了CPU和硬件资源等方面提供的抽象，能够有效提高CPU的利用率。
- 进程只能在一个时间干一件事，如果想同时干两件事或多件事，进程就无能为力了。
- 进程在执行的过程中如果阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖于输入的数据，也将无法执行。
线程是什么
线程是在进程这个层次上提供的一层并发的抽象，也被成为轻量级进程，是程序执行流的最小单位
一个标准的线程具有线程ID、当前指令指针、寄存器集合和堆栈等组成。C语言中的全局变量被映射到读写区域，任何线程都可以引用；本地自动变量（定义咋函数内部但是没有static属性的变量）被映射到每个线程的栈中；本地静态变量（定义在函数内部并有static属性的变量）映射到读写区域，每个对等线程都能读写该变量
- 可以有效地利用多处理器和多核计算机，在没有线程之前，多核并不能让一个进程的执行速度提高
- 能够使系统在同一时间能够做多件事情，当进程遇到阻塞时，例如等待输入，线程能够使不依赖输入数据的工作继续执行，例如多线程可以让一个线程负责交互，另一个线程负责计算
- 多线程在数据共享方面效率更高
进程和线程区别
进程和线程的并发层次不同：进程属于在处理器这一层上提供的抽象；线程则属于在进程这个层次上再提供了一层并发的抽象。
如果我们进入计算机体系结构里，就会发现，流水线提供的也是一种并发，不过是指令级的并发。这样，流水线、线程、进程就从低到高在三个层次上提供我们所迫切需要的并发！
- 从内核的观点看，进程的目的就是担当分配系统资源（CPU时间、内存等）的基本单位。线程是进程的一个执行流，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位
- 进程有独立的地址空间，线程没有单独的地址空间
- 启动一个线程所花费的空间远远小于启动一个进程所花费的空间，而且，线程间彼此切换所需的时间也远远小于进程间切换所需要的时间。据统计，总的说来，一个进程的开销大约是一个线程开销的30倍左右
- 线程间方便的通信机制
- 从函数调用上来说，进程创建使用fork()操作；线程创建使用clone()操作
访问权限
从上图可以产看出，线程具有一些私有存储空间，如栈、线程局部存储（某些操作系统为线程单独提供的私有空间）和寄存器，线程之间共享的则有全局变量、堆上的数据、静态变量、程序代码和打开文件
线程调用与优先级
当线程数量小于处理器数量时，线程的并发是真正的并发，不同的线程运行在不同的处理器上，彼此互不相干。但是当线程数量大于处理器数量的情况下，就会出现一个处理器运行多个线程的情况。
对于在单处理器上运行多线程情况下，并发是模拟出来的概念，操作系统会让程序轮流执行，每次执行几十到几百毫秒，这样就看起来在同时执行（联想数电仿真的波形图就能理解），这样不断切换不同线程的行为就称为线程调度
线程通常有三种状态
- 运行（Running）
- 就绪（Ready）：如CPU被占用
- 等待（Waiting）：线程正在等待某一事件（如IO）而无法执行
主流的线程调度都带有优先级调度和轮转法，Linux可以通过pthread库来进行相关设置，如设置线程优先级，这是第一种用户指定优先级改变
操作系统也会根据线程的表现自动调整优先级，IO密集型线程（即因为IO输出输出而频繁等待）比CPU密集型（经常要使用完时间片）更容易得到优先级提升
为了避免低优先级的线程始终无法得到执行，调度系统对逐步提升这种“饿死”线程的优先级，使其肯定会被执行
Linux多线程
linux内核并不存在真正意义上的线程概念，所有执行实体（无论是线程还是进程）都称为Task。每个Task都类似于一个单线程的进程，具有内存空间、执行实体、文件资源等。linux中允许Task之间选择共享内存空间，因此共享了内存空间的Task构成了一个进程，而这些Tasks也就是线程
fork系统调用：复制当前进程，本任务的fork返回新任务的pid，而新任务的fork返回0，fork并不复制原任务的内存空间，而是和原任务一起共享一个写时复制（Copy on Write，COW）的内存空间，可以理解为延迟复制，只当任意一个任务试图修改内存时，才会复制内存空间给任务单独使用。fork是最简单的调用，不需要任何参数，仅仅是在创建一个子进程并为其创建一个独立于父进程的空间，即产生本任务的镜像，要exec配合才能够启动别的新任务，这两个配合通常用于产生新任务
线程安全
自增在多线程环境下会出现错误是因为这个操作被编译为汇编代码之后不止一条指令，因此可能在执行到一半就被调度系统打断，去执行别的代码。
锁
单指令的操作成为原子操作，但原子操作只适用于简单场合，复杂场合就会显得力不从心，因此使用更加通用的锁
每个线程在访问数据之前先试图获取锁，并在访问结束之后释放锁，在锁被占用的时候试图获得锁时，线程就会等到，直到锁重新可用
- 二元信号量：最简单的一种锁，只有占用和非占用两种状态
- 信号量：即多元信号量，用在允许多个线程并发访问的资源上，初始值为N的信号量允许N个线程并发访问
- 互斥量：类似于二元信号量，但是信号量可以被系统任意线程获取并释放，互斥量要求哪个线程获取，哪个线程释放，更加严格
- 临界区：临界区比互斥量更加严格，临界区的作用范围仅限于本进程，其他进程无法获取该锁，而对于互斥量和信号量，系统任何进程都是可见的、可获取的
- 读写锁：虽然对于读写同步来说，信号量、互斥量和临界区都能实现目的，但是对于读取频繁，仅仅偶尔写入的情况，会显得很低效，读写锁则可以避免这个问题，读写锁分为读锁和写锁，且有两种获取方式：共享的和独占的
- 条件变量：类似于栅栏，使用条件变量可以是许多线程一起等待某个事件的发生，当事件发生时（条件变量被唤醒），所有线程一起恢复执行
可重入函数
重入：重复进入，即该函数被调度系统中断后，再一次进入该函数，不会产生不良后果，就称这个函数是可重入函数
可重入函数的一些特点：
- 不使用任何（局部）静态或全局的非const变量
- 不返回任何（局部）静态或全局的非const变量指针
- 仅依赖于调用方提供的参数
- 不依赖任何单个资源的锁
- 不调用任何不可重入函数
一个可重入函数可以在多线程环境下放心使用
过度优化
落后的编译器技术无法满足日益增长的并发需求，编译器可能会为了提高变量的访问速度，而把变量放到某个寄存器中，而不是放在内存中，但不同的线程的寄存器是各自独立的，因此就会出现以下问题1
2
3
4
5
6
7
8
9
10
11x = 0;
//Thread 1
lock();
x++;
unlock();
//Thread 2
lock();
x++;
unlock();
编译器
这个程序看起来并没有问题，但是问题出在了自作聪明的编译器中，它可能会把x放在寄存器中，这样就可能出现x=1的情况，为此可以使用volatile关键字阻止这种不同步类型的过度优化，这个关键字可以做到以下两件事
- 阻止编译器为了提高速度将一个变量缓存到寄存器而不写回内存
- 阻止编译器调整操作volatile变量的指令顺序
CPU
另一种问题则是因为CPU的动态调度或者说是乱序执行，在执行程序的时候为了提高效率有可能交换指令的顺序1
2
3
4
5
6
7
8
9x = y = 0;
//Thread 1
x = 1;
r1 = y;
//Thread 2
y = 1;
r2 = x;
CPU对于这种不相干的指令，就可能出现下面顺序，这样完全可能出现r1=r2=0的情况，而这种情况volatile是不能解决的1
2
3
4
5
6
7
8
9x = y = 0;
//Thread 1
r1 = y;
x = 1;
//Thread 2
y = 1;
r2 = x;
为了阻止CPU换序，可以调用CPU提供的一条指令barrier，该指令会阻止CPU将barrier指令之前的指令交换到barrier之后，类似于一个拦水坝
线程模型
用户实际使用的线程并不是内核线程，而是存在于用户态的用户线程，用户态线程并不一定在操作系统内核上对应同等数量的内核线程
一对一模型
一个用户态线程就唯一对应于内核线程，但内核线程不一定对于一个用户态线程，一般使用API或系统调用产生的线程都是一对一线程，如linux的clone
一对一模型的缺点：
- 许多操作系统限制了内核线程的数量，因此一对一线程也会让用户线程的数量受影响
- 内核线程调度时，上下文切换的开销大，导致用户线程的执行效率下降
多对一模型
多个用户线程映射到一个内核线程上，线程之间的切换由用户态的代码来进行，上下文切换成本低，无限制的线程数量
缺点：
- 一个用户线程阻塞，就会导致所有线程阻塞，因为内核线程也随之阻塞
- 多处理器对该模型没有明显帮助
多对多模型
该模型则是结合了上述两种模型的特点