程序员的自我修养一温故而知新

1.1从Hello World说起

目的：从最基本的编译，静态链接到操作系统如何转载程序，动态链接及运行库和标准库的实现，和一些操作系统的机制。了解计算机上程序运行的一个基本脉络。

1.2变不离其宗

计算机最关键的三个部分：CPU,内存,I/O控制芯片。

• 早期的计算机：没有复杂的图形功能，CPU和内存频率一样，都连接在同一个总线上。
• CPU频率提升：内存跟不上CPU，产生了和内存频率一致的系统总线，CPU使用倍频的方式和总线通信。
• 图形界面的出现：图形芯片需要和内存和CPU大量交换数据，慢速的I/O总线无法满足图形设备的巨大需求。为了高效处理数据，设计了一个高速的北桥芯片。后来有设计处理低速处理设备南桥芯片，磁盘，USB，键盘都是连接在南桥上。在由南桥将它们汇总到北桥上。

北桥

• 北桥左边CPU和cache：CPU负责所有控制和运算。
• 北桥下面PCI总线
• 北桥右边memory

SMP和多核

现在CPU已经达到物理极限，被4GHz所限制，于是，开始通过增加CPU数量来提高计算机速度。
对称多处理器（SMP）：最常见的一种形式。每个CPU在系统中所处的地位和所发挥的功能是一样，是相互对称的。但在处理程序时，我们并不能把他们分成若干个不相干的子问题，所以，使得多处理器速度实际提高得并没有理论上那么高。当对于相互独立的问题，多处理器就能最大效能的发挥威力了（比如：大型数据库,网络服务等）。
对处理器由于造价比较高昂，主要用在商用电脑上，对于个人电脑，主要是多核处理器。
多核处理器：其实际上是(SMP)的简化版，思想是将多个处理器合并在一起打包出售，它们之间共享比较昂贵的缓存部件，只保留了多个核心。在逻辑上看，它们和SMP完全相同。

1.3站得高,看得远

系统软件：一般用于管理计算机本地的软件。

主要分为两块：

• 平台性的：操作系统内核，驱动程序，运行库。
• 程序开发：编译器，汇编器，链接器。

计算机系统软件体系结构采用一种层的结构。
每个层次之间都需要相互通信，那么它们之间就有通信协议，我们将它称为接口，接口下层是提供者，定义接口。上层是使用者，使用接口实现所需功能。
除了硬件和应用程序，其他的都是中间层，每个中间层都是对它下面的那层的包装和扩展。它们使得应用程序和硬件之间保持相对独立。
从整个层次结构来看，开发工具与应用程序属于同一个层次，因为它们都使用同一个接口—操作系统应用程序编程接口。应用程序接口提供者是运行库，什么样的运行库提供什么样的接口。winsows的运行库提供Windows API，Linux下的Gliba库提供POSIX的API。
运行库使用操作系统提供的系统调用接口。
系统调用接口在实现中往往以软件中断的方式提供。
操作系统内核层对于硬件层来说是硬件接口的使用者，而硬件是接口的定义者。这种接口叫做硬件规格。

1.4操作系统做了什么

操作系统的一个功能是提供抽象的接口，另外一个主要功能是管理硬件资源。
一个计算机中的资源主要分CPU,存储器（包括内存和磁盘）和I/O设备。下面从这3个方面来看如何挖机它们。

1.4.1不要让CPU打盹

多道程序：编译一个监控程序，当程序不需要使用CPU时，将其他在等待CPU的程序启动。但它的弊端是不分轻重缓急，有时候一个交互操作可能要等待数十分钟。
改进后
分时系统：每个CPU运行一段时间后，就主动让出给其他CPU使用。完整的操作系统雏形在此时开始出现。但当一个程序死机的时候，无法主动让出CPU，那么，整个系统都无法响应。
目前操作系统采用的方式
多任务系统：操作系统接管了所有的硬件资源，并且本身运行在一个受硬件保护的级别。所有的应用都以进程的方式运行在比操作系统更低的级别，每个进程都有自己独立的地址空间，使得进程之间的地址空间相互隔离。CPU由操作系统进行同一分配，每个进程根据进程优先级的高低都有机会获得CPU，但如果运行超过一定的时间，CPU会将资源分配给其他进程，这种CPU分配方式是抢占式。如果操作系统分配每个进程的时间很短，就会造成很多进程都在同时运行的假象，即所谓的宏观并行，微观串行。

设备驱动

操作系统作为硬件层的上层，它是对硬件的管理和抽象。
对于操作系统上面的运行库和应用程序来说，它们只希望看到一个统一的硬件访问模式。
当成熟的操作系统出现后，硬件逐渐成了抽象的概念。在UNIX中，硬件设备的访问形式和访问普通的文件形式一样。在Windows系统中，图形硬件被抽象成GDI，声音和多媒体设备被抽象成DirectX对象，磁盘被抽象成普通文件系统。
这些繁琐的硬件细节全都交给了操作系统中的硬件驱动。
文件系统管理这磁盘的存储方式。
磁盘的结构：一个硬盘往往有多个盘片，每个盘片分两面，每面按照同心圆划分为若干磁道，每个磁道划分为若干扇区，每个扇区一般512字节。
LBA：整个硬盘中所有扇区从0开始编号，一直到最后一个扇区，这个扇区编号叫做逻辑扇区号。
文件系统保存了这些文件的存储结构，负责维护这些数据结构并且保证磁盘中的扇区能有效的组织和利用。

1.5内存不够怎么办

在早期计算机中，程序是直接运行在物理内存上的，程序所访问的都是物理地址。
那么如何将计算机有限的地址分配给多个程序使用。
直接按物理内存分配将产生很多问题：

• 地址空间不隔离：所有的程序都直接访问物理地址，导致程序使用的物理地址不是相互隔离的，恶意的程序很容易串改其他程序的内存数据。
• 内存使用效率低：由于没有有效的内存管理机制，通常一个程序执行的时候，监控程序要将整个程序读入。内存不够的时候，需要先将内存中的程序读出，保存在硬盘上，才能将需要运行的程序读入。这样会使得整个过程有大量数据换入换出。
• 程序运行地址不确定：每次程序运行都需要内存分配一块足够大的内存空间，使得这个地址是不确定的。但在程序编写的时候，他访问的数据和指令跳转的目标地址都是固定的，这就涉及到了程序的重定向问题。

一种解决办法：
中间层：使用一种间接的地址访问方法，我们把程序给出的地址看作一种虚拟地址。虚拟地址是物理地址的映射，只要处理好这个过程，就可以起到隔离的作用。

1.5.1关于隔离

普通的程序它只需要一个简单的执行环境，一个单一的地址空间，有自己的CPU。
地址空间比较抽象，如果把它想象成一个数组，每一个数组是一字节，数组大小就是地址空间的长度，那么32位的地址空间大小就是2^32=4294967296字节，即4G，地址空间有效位是0x00000000~0xFFFFFFFF。
地址空间分为两种：
物理空间：就是物理内存。32位的机器，地址线就有32条，物理空间4G，但如果值装有512M的内存，那么实际有效的空间地址就是0x00000000~0x1FFFFFFF，其他部分都是无效的。
虚拟空间：每个进程都有自己独立的虚拟空间，而且每个进程只能访问自己的空间地址，这样就有效的做到了进程隔离。

1.5.2分段

基本思路：把一段与程序所需要的内存空间大小的虚拟空间映射到某个地址空间。虚拟空间的每个字节对应物理空间的每个字节。这个映射过程由软件来完成。
分段的方式可以解决之前的第一个（地址空间不隔离）和第三个问题（程序运行地址不确定）
第二问题内存使用效率问题依旧没有解决。

1.5.3分页

基本方法：把地址空间人为的分成固定大小的页，每一页大小有硬件决定或硬件支持多种大小的页，由操作系统决定页的大小。
目前几乎所有的PC上的操作系统都是4KB大小的页。
我们把进程的虚拟地址空间按页分割，把常用的数据和代码页转载到内存中，把不常用的代码和数据保存到磁盘里，当需要的时候从磁盘取出来。
虚拟空间的页叫做虚拟页（VP）,物理内存中页叫做物理页，把磁盘中的页叫做磁盘页。虚拟空间的有的页被映射到同一个物理页，这样就可以实现内存共享。
当进程需要一个页时，这个页是磁盘页时，硬件会捕获到这个消息，就是所谓的页错误，然后操作系统接管进程，负责从磁盘中读取内容装入内存中，然后再将内存和这个页建立映射关系。
保护也是页映射的目的之一，每个页都可以设置权限属性，只有操作系统可以修改这些属性，这样操作系统就可以保护自己保护进程。
虚拟存储的实现需要依靠硬件支持，所有硬件都采用一个叫做MMU的部件来进行页映射。
CPU发出虚拟地址经过MMU转换成物理地址，MMU一般都集成在CPU内部。

1.6众人拾柴火焰高

1.6.1线程基础

多线程现在作为实现软件并发执行的一个重要方法，具有越来越重的地位。

什么是线程

线程有时被称为轻量级的进程，是程序执行流的最小单位。

构成：

• 线程ID
• 当前指令指针
• 寄存器集合
• 堆栈空间（代码段，数据段，堆）
• 进程级的资源（打开文件和信号）

线程与进程的关系：

多线程可以互不干扰的并发执行，并共享进程的全局变量和堆的数据。
使用多线程的原因有如下几点：

• 某个操作可能会陷入长时间等待，等待的线程会进入睡眠状态，无法继续执行。
• 某个操作会消耗大量的时间，如果只有一个线程，程序和用户之间的交互会中断。
• 程序逻辑本身就要求并发操作。
• 多CPU或多核计算机，本身具备同时执行多个线程的能力。
• 相对于多进程应用，多线程在数据共享方面效率要高很多。

线程的访问权限

线程的访问非常自由，它可以访问进程内存里所有数据，包括其他线程的堆栈（如果知道地址的话，情况很少见）。
线程自己的私用存储空间：

• 栈（并发完全无法被其他线程访问）
• 线程局部存储。某些操作系统为线程提供私用空间，但容量有限。
• 寄存器。执行流的基本数据，为线程私用。

线程调度与优先级

不论在多处理器还是单处理器上，线程都是“并发”的。
线程数量小于处理器数量时，是真正并发的。
单处理器下，并发是模拟的，操作系统会让这些多线程程序轮流执行，每次都只执行一小段时间，这就称为线程调度。
线程调度中，线程拥有三种状态：

• 运行：线程正在执行
• 就绪：线程可以立刻运行，但CPU被占用
• 等待：线程正在等待某一事件发生，无法立即执行。

处于运行中的线程拥有一段可以执行的时间，这称为时间片，当时间片用尽的时候，进程进入就绪状态，如果在用尽之前开始等待某事件，那么它就进入等待状态。每当一个线程离开运行状态的时候，调度系统就会选择一个其他的就绪线程继续执行。

现在的主流调度方法尽管都不一样，但基本都带有优先级调度和轮转法。
轮转法：各个线程轮流执行一段时间。
优先级调度：按线程的优先级来轮流执行，每个线程都拥有各自的线程优先级。
在win和lin里面，线程优先级不仅可以由用户手动设置，系统还会根据不同线程表现自动调整优先级。
一般频繁等待的线程称之为IO密集型线程，而把很少等待的线程称为CPU密集型线程。
优先级调度下，存在一种饿死现象。
饿死：线程优先级较低，在它执行之前，总是有较高级的线程要执行，所以，低优先级线程总是无法执行的。
当一个CPU密集型线程获得较高优先级时，许多低优先级线程就可能被饿死。
为了避免饿死，操作系统常常会逐步提升那些等待时间过长的线程。
线程优先级改变一般有三种方式：

• 用户指定优先级
• 根据进入等待状态的频繁程度提升或降低优先级
• 长时间得不到执行而被提升优先级

可抢占线程和不可抢占线程

抢占：在线程用尽时间片之后被强制剥夺继续执行的权利，而进入就绪状态。
在早期的系统中，线程是不可抢占的，线程必须主动进入就绪状态。
在不可抢占线程中，线程主动放弃主要是2种：

• 当线程试图等待某个事件（I/O）时
• 线程主动放弃时间片

不可抢占线程有一个好处，就是线程调度只会发生在线程主动放弃执行或线程等待某个事件的时候，这样就可以避免一些抢占式线程时间不确定而产生的问题。

Linux的多线程

Linux内核中并不存在真正意义上的线程概念。Linux所有执行实体（线程和进程）都称为任务，每一个任务概念上都类似一个单线程的进程，具有内存空间，执行实体，文件资源等。Linux不同任务之间可以选择共享内存空间，相当于同一个内存空间的多个任务构成一个进程，这些任务就是进程中的线程。

fork产生新任务速度非常快，因为fork不复制原任务的内存空间，而是和原任务一起共享一个写时复制的内存空间。

写时复制：两个任务可以同时自由读取内存，当任意一个任务试图对内存进行修改时，内存就会复制一份单独提供给修改方使用。
fork只能够产生本任务的镜像，因此需要和exec配合才能启动别的新任务。
而如果要产生新线程，则使用clone。
clone可以产生一个新的任务，从指定位置开始执行，并且共享当前进程的内存空间和文件等，实际效果就是产生一个线程。

1.6.2线程安全

多线程程序处于一个多变的环境中，可访问的全局变量和堆数据随时都可能被其他的线程改变。因此多线程程序在并发时数据的一致性变得非常重要。

竞争与原子操作

++i的实现方法：

• 读取i到某个寄存器X
• X++
• 将X的内容存储回i
  单条指令的操作称为原子的，单挑指令的执行不会被打断。在windows里，有一套API专门进行一些原子操作，这些API称为Interlocked API。

同步与锁

为了防止多个线程读取同一个数据产生不可预料结果，我们将各个线程对一个数据的访问同步。
同步：在一个线程对一个数据访问结束的时候，其他线程不能对同一个数据进行访问。对数据的访问被原子化。
锁：锁是一种非强制机制，每一个线程在访问数据或者资源之前会先获取锁，在访问结束后会释放锁。在锁被占用时候试图获取锁时，线程会等待，知道锁可以重新使用。
二元信号量：最简单的锁，它适合只能被唯一一个线程独占访问的资源，它的两种状态：

• 非占用状态：第一个获取该二元信号量的线程会获得该锁，并将二元信号量置为占用状态，其他所有访问该二元信号量线程将会等待。
• 占用状态

信号量：允许多个线程并发访问的资源。一个初始值为N的信号量允许N个线程并发访问。
操作如下：

• 将信号量值键1
• 如果信号量值小于0，就进入等待状态。

访问完资源后，线程释放信号量：

• 将信号量加1
• 如果信号量的值小于1，唤醒一个等待中的线程。

互斥量：和二元信号量很类似，但和信号量不同的是：信号量在一个系统中，可以被任意线程获取或释放。互斥量要求那个线程获取互斥量，那么哪个线程就释放互斥量，其他线程释放无效。
临界区：比互斥量更加严格的手段。把临界区的锁获取称为进入临界区，而把锁的释放称为离开临界区。临界区和互斥量，信号量区别在与互斥量，信号量在系统中任意进程都是可见的。临界区的作用范围仅限于本线程，其他线程无法获取。其他性质与互斥量相同。
读写锁：致力于一种更加特定的场合的同步。如果使用之前使用的信号量、互斥量或临界区中的任何一种进行同步，对于读取频繁，而仅仅是偶尔写入的情况会显得非常低效。读写锁可以避免这个问题。对于同一个锁，读写锁有两种获取方式：

• 共享的
• 独占的

读写锁的总结

条件变量：作为同步的手段，作用类似于一个栅栏。对于条件变量，线程有两个操作：

• 线程可以等待条件变量，一个条件变量可以被多个线程等待
• 线程可以唤醒条件变量，此时某个或所有等待此条件变量的线程都会被唤醒并继续支持

使用条件变量可以让许多线程一起等待某个事件的发生，当事件发生时，所有线程可以一起恢复执行。

可重入与线程安全

一个函数被重入，表示这个函数没有执行完成，由于外部因素或内部调用，又一次进入该函数执行。
一个函数要被重入，只有两种情况：

• 多个线程同时执行这个函数
• 函数自身（可能经过多层调用之后）调用自身

一个函数被称为可重入，表示重入之后不会产生任何不良影响

可重入函数：

1 int sqr(int x)
2 {
3 return x*x;
4 }

一个函数要成为可重入，必须具有如下特点：

• 不使用任何（局部）静态或全局的非const变量
• 不返回任何（局部）静态或全部的非const变量的指针
• 仅依赖调用方提供的参数
• 不依赖任何单个资源的锁
• 不调用任何不可重入的函数

可重入是并发安全的强力保障，一个可重入的函数可以在多程序环境下方向使用

过度优化

有时候合理的合理的使用了锁也不一定能保证线程的安全。

//Thread1
x=0;
lock();
x++;
unlock();
//Thread2
x=0;
lock();
x++;
unlock();

上面X的值应该为2，但如果编译器为了提高X的访问速度，把X放到了某个寄存器里面，不同线程的寄存器是各自独立的，因此，如果Thread1先获得锁，则程序的执行可能会呈现如下：
[Thread1]读取x的值到某个寄存器R [1] (R[1]=0);
[Thread1]R[1]++(由于之后可能要访问到x,所以Thread1暂时不将R[1]写回x);
[Thread2]读取x的值到某个寄存器R[2] (R[2]=0);
[Thread2]R[2]++(R[2]=1);
[Thread2]将R[2]写回至x(x=1);
[Thread1] (很久以后)将R[1]写回至x(x=1);
如果这样，即使加锁也不能保证线程安全

x=y=0;
//Thread1
x=1;
r1=y;
//Thread2
y=1;
r2=x;

上面代码有可能发生r1=r2=0的情况。
CPU动态调度：在执行程序的时候，为了提高效率有可能交换指令的顺序。
编译器在进行优化的时候，也可能为了效率交换两个毫不相干的相邻指令的执行顺序。
上面代码执行顺序可能是这样：

x=y=0;
[Thread1]
r1=y;
x=1;
[Thread2]
y=1;
r2=x;

使用volatile关键字可以阻止过度优化，colatile可以做两件事情：

• 阻止编译器为了提高速度将一个变量缓存到寄存器内而不写回
• 阻止编译器调整操作volatile变量的指令顺序

但volatile无法阻止CPU动态调度换序
C++中，单例模式。

volatile T* pInst=0;
T* GetInstance()
{
if(pInst==NULL)
{
LOCK();
if(pInst==NULL)
pInst=new T;
unlock();
}
return pInst;
}

CPU的乱序执行可能会对上面代码照成影响
C++里的new包含两个步骤：

• 分配内存
• 调用构造函数

所以pInst=new T包含三个步骤：

• 分配内存
• 在内存的位置上调用构造函数
• 将内存的地址赋值给pInst

这三步中2和3的步骤可以颠倒，可能出现这种情况：pInst中的值不是NULL，但对象还是没有构造完成。
要阻止CPU换序，可以调用一条指令，这条指令常常被称为barrier：它会阻止CPU将该指令之前的指令交换到barrier之后。
许多体系的CPU都提供了barrier指令，不过，它们的名称各不相同。例如POWERPC提供的指令就叫做lwsync。所以我们可以这样保证线程安全：

#define barrier() __asm__ volatile ("lwsync")
volatile T* pInst=0;
T* GetInstance()
{
if(pInst==NULL)
{
LOCK();
if(pInst==NULL)
{
T* temp=new T;
barrier();
pInst=temp;
}
unlock();
}
return pInst;
}

1.6.3多线程的内部情况

线程的并发执行是由多处理器或操作系统调度来实现的。windows和linux都在内核中提供线程支持，有多处理器或调度来实现并发。用户实际使用线程并不是内核线程，而是存在于用户态的用户线程。用户线程并不一定在操作系统内核里对应同等数量的内核线程。对用户来说，如果有三个线程同时执行，可能在内核中只有一个线程。

一对一模型

对于直接支持线程的系统，一对一模型始终是最为简单的模型。一个用户使用的线程就唯一对应一个内核使用的线程，但返回来，一个内核里面的线程在用户态不一定有对应的线程存在。

对于一对一模型，线程之间的并发是真正的并发，一个线程因为某个原因阻塞，并不会影响到其他线程。一对一模型也可以让多线程程序在多处理器的系统上有更好的表现。
一般直接使用API或者系统调用创建的线程均为一对一线程。
一对一线程的两个缺点：

• 由于许多操作系统限制了内核线程数量，因此一对一线程会让用户的线程数量受到限制。
• 许多操作系统内核线程调度是，上下文切换的开销较大，导致用户线程的执行效率下降。

多对一模型

多对一模型将多个用户线程映射到一个内核线程上，线程之间的切换由用户态的代码来进行，相对于一对一模型，多对一模型的线程切换要快速许多。

多对一模型的问题就是如果一个用户线程阻塞了，那么所有的线程都将无法执行。在多处理系统上，处理器的增多对多对一模型的线程性能不会有明显帮助。多对一模型得到的好处是高效的上下文切换和几乎无限制的线程数量。

多对多模型

多对多模型结合了多对一和一对一的特点，将多个用户线程映射到少数但不止一个内核线程上。

一个用户线程阻塞并不会使得所有的用户线程阻塞。并且对用户线程数量也没有什么限制，在多处理器系统上，多对多模型的线程也能得到一定的性能提升，不过提升的幅度没有一对一模型高。