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

开新坑，记录我学习《程序员的自我修养》这本书的笔记，加上自己的实践和好的例子

更新不会很快，大二太忙了

配合计算机系统基础这门专业课程一起学习

引言

《程序员的自我修养》这本书讲的主要是操作系统内核，装载，链接等一些技术，理解操作系统如何让一段代码工作起来，如何让不同的二进制模块协同工作。

你可以不自己造轮子，但你应该了解轮子的构造，而且越详尽越好，这就是程序员的自我修养吧。————《程序员的自我修养》

推荐书籍
《深入理解计算机系统》（Computer System A Programmer’s Perspective, Randal E. Bryant和David O’Halaron著）
《Advanced Programing in the UNIX Environment, Second Edition》（UNIX程序设计的“圣经”）

温故而知新

hello.c

#include <stdio.h>

int main(){
    printf("Hello World\n");
    return 0;
}

思考下面问题：

• 程序为什么要编译后才能运行？
• 编译器在把C语言变成可执行的机器码中做了什么？怎么做的？
• 最后编译出来的可执行文件里面时是什么？除了机器码还有什么？它们怎么存放？怎么组织？
• #include <stdio.h>是什么意思，C语言库是什么？怎么实现的？
• 不同的编译器（Microsoft VC，GCC）和不同的硬件平台（x86，SPARC，MIPS，ARM）以及不同的操作系统（Windows，Linux，UNIX）最终编译出来的结果一样吗？为什么？
• Hello World程序怎么运行起来的？操作系统如何装载它？从哪里开始执行？到哪儿结束？main函数之前发生了什么，结束之后又发生了什么？
• 没有操作系统，Hello World可以实现吗？如果要在一台没有操作系统的机器上运行Hello World需要什么？怎么实现？
• printf怎么实现？它为什么可以有不定量的参数？为什么可以在终端上输出字符串？
• Hello World程序在运行时，它在内存中是什么样子的？

等到看完整本书后，再次提问自己这些问题，再次给出解答 ，这里记录一下目前我的理解，不一定正确：

1.CPU无法识别高级语言，需要经过“虚拟机”来将高级语言转化为机器语言，编译就是为了实现这个转化的一部分（高级到汇编）
4.由于不同的CPU的指令集架构不同（如x86和arm），所以编译处出来的汇编代码不一样
8.printf把要打印的参数压栈，一个一个取出来，由CPU控制传输给显示屏幕，在对应的位置打印出字符，如果为汉字，将打印字符点阵（如何在对应位置打印不了解）

计算机硬件

南北桥

早期的计算机没有复杂的图形功能，CPU的核心频率不高，和内存的频率一样，它们都是直接连接在同一个总线（Bus）上。为了协调I/O设备与总线之间的速度，也为了能够让CPU能够和I/O设备进行通信，一般每个设备都会有一个相应的I/O控制器。

后来由于CPU核心频率的提升，导致内存跟不上CPU的速度，于是产生了和内存频率一致的系统总线，而CPU采用倍频的方式与系统总线进行通信。为了协调CPU，内存和高速的图形设备，人们专门设计了一个高速的北桥芯片（Northbridge，PCI Bridge），以便它们之间能够高速地交换数据。

由于北桥运行的速度比较高，对于低速数据，人们专门设计了南桥芯片（Southbridge）磁盘，USB，键盘，鼠标等设备都连在南桥上。

SMP与多核

由于工艺的限制，CPU频率在短时间里不会有很高的提高余地。于是人们就想办法从另一个角度来提高频率：增加CPU的数量。很早以前就有了多CPU的计算机，其中最常见的一种形式就是对称多处理器（SMP，Symmetrical Muti-Processing），简单来讲就是每个CPU在系统中所处地位和发挥的功能都是一样的，是相互对称的。多核的处理器应用最多的是在商用服务器和需要处理大量计算的环境，而在个人电脑中，它们共享一个缓存部件，打包成一个处理器，这就是多核处理器（Muti-core Processor）

计算机软件体系结构

计算机系统软件体系结构采取一种层的结构，就是我们所说的应用层，系统层，硬件层。每个层之间需要相互通信，有协议去规范，这就称为接口（Interface）。

• 开发工具和应用程序–调用–>应用程序接口（Application Programming Interface，运行库提供）

如Win32，Linux下Glibc库提供POSIX的API

• 运行库–调用–>系统调用接口（System call Interface，操作系统提供）

系统调用接口在现实中往往以**软件中断（Software Interrupt）**的方式提供，如Linux使用0x80号中断作为系统调用接口

操作系统

操作系统的一个功能就是提供抽象的接口，另一个就是管理硬件资源

CPU

多道程序

早期的时候，为了让CPU等待的时间有事干，人们编写了一个监控程序，当某个程序暂时无需使用CPU时，监控程序就把另外一个等待CPU资源的程序启动，这被称为多道程序（Multiprogramming），虽然使得CPU得到充分利用，但任务调度没有轻重缓急，有些程序紧急需要CPU来完成一些任务，有时会需要等上很长时间。

分时系统

每个程序运行一段时间以后都主动让出CPU给其他程序，使得一段时间内每个程序都有机会运行一小段时间。这种程序协作模式就叫分时系统（Time-Sharing System）。但如果一个程序在进行一个很耗时的计算，或者进入死循环，那么操作系统也没办法，其他程序都只有等着。

多任务系统

多任务（Multi-tasking） 系统中，操作系统接管了所有的硬件资源，并且本身运行在一个受硬件保护的级别。所有的应用程序都以 **进程（Process）**的方式运行在比操作系统权限更低的级别，每个进程都有自己的独立的地址空间，使得进程之间的地址空间相互隔离。

CPU由操作系统统一分配，每个进程根据优先级都有机会获得CPU，但是如果运行时间超出了一定的时间，操作系统会暂停该进程，将CPU资源分配给其他等待运行的进程。这种CPU分配方式叫做抢占式（Preemptive）

当操作系统分给每个进程的时间都很短，即CPU在多个进程之间快速切换，从而造成很多进程都在同时运行的假象。

设备驱动

操作系统作为硬件层的上层，它是对硬件的管理和抽象。对于操作系统上面的运行库和应用程序来说，它们希望看到的是一个统一的硬件访问模式。作为应用程序的开发者，它们不希望在开发应用程序时直接做读写硬件接口，处理硬件中断等繁琐的事。由于硬件之间千差万别，这时候就需要一种统一的接口。

当成熟的操作系统出现以后，硬件逐渐被抽象成了一种概念。在UNIX中，硬件设备的访问跟访问普通的文件形式一样，而在Windows中，图形硬件被抽象成了GDI，声音和多媒体设备被抽象成了DirectX，磁盘被抽象成了普通的文件系统。硬件的细节全部由操作系统中的**硬件驱动（Device Driver）**程序来完成。

驱动可以看做是操作系统的一部分，它往往和操作系统内核一起运行在特权级。

以文件读写为例：

文件系统这个操作系统中最重要的组成部分之一，文件系统管理着磁盘中文件的存储方式，比如我们在Linux系统下有一个文件/home/user/test.dat，长度为8000字节，那么创建这个文件的时候，Linux的ext3文件系统可能将这个文件安照这样的方式存储：

文件的前4096字节存储在磁盘的1000号扇区到1007扇区，每个扇区512字节，8个扇区刚好4096字节，文件的第4097个字节到第8000个字节存储在磁盘的2000号扇区到2007号扇区，没存满的扇区剩余字节无效。

关于硬盘的结构

硬盘的基本存储单位为扇区（Sector），每个扇区512字节。一个硬盘往往有多个扇片，每个盘片分2面，每面按照同心圆划分为若干个磁道（通常说的硬盘坏道就是这个道），每个磁道划分为若干的扇区。
如有一个硬盘有2个盘片，每个盘片分65536（2^16）个磁道，每个磁道分1024个扇区，则容量就是2 * 2 * 65536 * 1024 * 512 = 128GB

当我们在Linux系统下想要读取文件时，就会使用一个read的系统调用，文件系统受到read的时候，判断文件的字节的位置，就向硬盘驱动发出一个读取逻辑扇区的命令，驱动再向硬盘发出硬件命令（方式有很多，最常见的是读写I/O端口寄存器来实现。CPU的in和out指令来实现对端口的读写）

内存

如何将计算机上有限的物理内存分给多个程序？如果简单的按照把a_{b的内存分给一个程序，b}c的内存分给另一个程序，会造成如恶意修改别的程序的内存等问题。

这时候我们就需要加一层中间层————虚拟地址（virtual Address），然后通过一些映射来将虚拟地址转换为实际的物理地址。达到地址空间隔离。

分段（Segmentation）

基本思路就是映射程序需要的内存空间到某个地址空间

当程序A试图访问超出虚拟地址的别的区域，那么硬件就会判断这是一个非法请求，并报告给操作系统或监控程序。

分页（Paging）

仅仅分段仍存在效率问题，若程序只是频繁的使用一小部分数据，没有必要每次读写所有的数据。为了解决效率问题，就创造了分页的方法，简单来说就是更小粒度的分割和映射。

在学习汇编的时候简单了解过，分页就是把地址空间人为的分成固定大小（一般为4K）的页。每次系统装载一定的页（页里有代码和数据），当该页的代码或数据不活跃时，系统便会把他们替换掉，加载立即请求的代码和数据。

以下图为例：

当我们把进程的虚拟地址空间按页分割，把常用的数据和代码装载到内存中，把不常用的代码和数据保存在磁盘里，当需要用到的时候再把它从磁盘里读出来。
我们假设有两个进程 Process1 和 Process2，它们进程中的部分虚拟页面被映射到了物理页面，比如VP0，VP1和VP7映射到PP0，PP2，PP3（PP，physical page）。（VP virtual page）而部分页面仍在磁盘中，比如VP2和VP3位于磁盘中的DP0和DP1中（DP，disk page），另外有些页面如VP4，VP5和VP6可能尚未被用或访问到。

当进程需要VP2和VP3时，硬件会捕获这个消息，就是所谓的页错误（Page Fault），然后操作系统接管进程，负责将VP2和VP3从磁盘中读出来并且装入内存，然后将内存中的这两个页与VP2和VP3之间建立映射。

当然，分页也有一个好处就是保护

简单来说就是为每个页设置权限属性，只有操作系统有权限修改这些属性，这样就保护了进程和数据。

线程（Thread）

有时也称轻量级进程（Lightweight Process，LWP），是程序执行流的最小单元。一个标准的线程由线程ID，当前指令指针（PC），寄存器集合和堆栈组成。

线程访问权限

线程私有	线程共享（进程所有）
局部变量	全局变量
函数参数	堆上的数据
TLS（Thread Local Storage）数据	函数里的静态变量
	程序代码
	打开的文件，A线程打开的文件可以由B线程读写

线程调度

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

通常情况下，频繁地进入等待状态（进入等待状态，会放弃之后仍然可占用的时间份额）的线程（例如处理I/O的线程）比频繁进行大量计算，以至于每次都要把时间片用尽的线程要受欢迎得多。频繁等待的线程会占用很少的时间，CPU也喜欢捏软柿子。

我们把频繁等待的线程称为IO密集型线程（IO Bound Thread），而把很少等待的线程称为CPU密集型线程（CPU Bound Thread）。IO密集型线程总是比CPU密集型线程容易得到优先级的提升。

在优先级调度的环境中，线程的优先级改变一般有三种方式：

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

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

线程用尽时间片之后会被强制剥夺继续执行的权利，而进入就绪的状态，这个过程叫做抢占（Preemption），即之后执行的线程抢占了当前的线程。

Windows对进程和线程的实现十分标准，Windows内核有明确的线程和进程的概念。在Windows API中，你可以使用CreateProcess和CreateThread来创建进程和线程，并且有一系列的API来操纵。而对于Linux来说，并没有真正意义的线程概念。Linux将所有的执行实体都称为任务（Task）

线程安全

竞争与原子操作

对于一些体系，++i的实现方法会如下：
1.读取i到某个寄存器X
2.X++
3.将X的内容存储回i

这样就会存在问题：由于不只有一条命令，因此在多线程环境中很有可能只执行了一半就被调度系统打断，去执行别的代码。
我们把单指令的操作称为原子的（Atomic），单条指令是不会被打断的。很多体系结构都提供了一些常用的原子操作指令，如i386就有一条inc指令可以直接增加一个内存单元值。

原子操作指令对于复杂的数据结构操作十分麻烦，就需要更加通用的手段

同步与锁

为了避免多个线程同时读写一个数据产生不可预料的后果，我们要将各个线程对于同一个数据的访问同步（Synchronization），所谓同步，即指在一个线程访问数据未结束时，其他线程不得对同一个数据进行访问。
同步的最常见方式是使用锁（Lock）。锁是一种非强制机制，每个线程在访问数据或资源之前首先试图**获取（Acquire）锁，并在访问结束后释放（Release）**锁。在锁已经被占用时试图获取锁，线程会等待，直到锁重新可用。

二元信号量

**二元信号量（Binary Semaphore）**是一种最简单的锁，它只有两种状态：占用与非占用。它适合只能唯一一个线程独占访问的资源。当二元信号量处于非占用的状态时，第一个试图获取该二元信号量的线程会获得该锁，并将二元信号重置为占用状态，此后其他所有试图获取该二元信号量的线程将会等待，直到该锁被释放。

对于允许多个线程并发访问的资源，多元信号量简称信号量（Semaphore），它是一个很好的选择。一个初始值为N的信号量允许N个线程并发访问。线程访问资源的时候首先获取信号量，进行如下操作。

• 将信号量的值减1
• 如果信号量的值小于0，则进入等待状态，否则继续执行

访问完后，线程释放信号量，进行如下操作

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

互斥量

**互斥量（Mutex）**和二元信号量很相似，资源仅允许一个线程访问，但和信号量不同的是，信号量在整个系统可以被任意线程获取并释放，也就是说，同一个信号量可以被系统中的一个线程获取之后由另一个线程释放。而互斥量则要求哪个线程获取了互斥量，哪个线程就要负责释放这个锁，其他线程无法释放。

临界区

临界区（Critical Section），在术语中，把临界区的锁的获取称为进入临界区，而把锁的释放称为离开临界区。临界区的作用范围仅限于本进程，其他的进程无法获取该锁。而互斥量和信号量在系统的任何进程里都是可见的

读写锁

**读写锁（Read-Write Lock）**致力于一种更加特定的场合同步。对于一段数据，多个线程可以同时读取，但一段时间内仅有一个线程可以去写。如果使用上述的类型会显得十分低效。读写锁可以避免这个问题。对于同一个锁，读写锁有两种获取方式：共享的（Shared）或者独占的（Exclusive）

读写锁状态	以共享方式获取	以独占方式获取
自由	成功	成功
共享	成功	等待
独占	等待	等待

条件变量

**条件变量（Condition Variable）**作为一种同步手段，作用类似于一个栅栏。对于条件变量，线程可以有两种操作，首先可以被多个线程等待。其次，线程可以唤醒条件变量，此时某个或所有等待此条件变量的线程都会被唤醒并继续支持。也就是说，使用条件变量可以让多线程一起等待某个事件的发生，然后一起恢复执行

可重入与线程安全

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

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

一个函数要成为可重入的，必须有下面的几个特点：

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

过度优化

过度优化往往发生在：

• 编译器为了提高速度把变量缓存在寄存器中而不回写导致即使正确使用了锁也会有线程的修改被抹除
• 编译器为了提高执行效率而交换了两条毫不相干的相邻指令，如下：

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

虽然看上去r1和r2不肯能同时为0，但编译器的优化可能导致指令顺序的交互，成了下面这样:

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

可以使用volatile关键字来试图阻止过度优化
但对CPU的动态调整调度顺序并没有办法
如下面这个典型的例子：

Singleton_doubleCheck

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

说明：

• 构造时上锁，确保只有一个实例被构造出来，否则并非时会导致构造了多个实例。
• 最外面多一层if判断是为了优化，如果没有，每次调用获取实例的时候都会上锁，导致效率的降低。

但实际上这样的代码是有问题的，问题来源于CPU乱序执行。C++的new包含2个步骤：

• (1) 分配内存
• (2) 调用构造函数

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

• (1) 分配内存
• (2) 调用构造函数
• (3) 将内存的地址赋给pInst
  这3步中（2）和（3）的顺序可以颠倒，所以完全可能出现这样的情况：pInst已经指向了内存块但构造仍未完成，这时有个线程调用getInstance()，就会导致错误的发生。
  解决这个问题需要使用CPU的一个barrier指令，在不同的体系结构中他的名字可能不相同，但它会阻止CPU把在此之前的指令交换到这之后。

Singleton_doubleCheck

#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;
}

多线程内部情况

• 一对一模型：一个用户使用的线程对应唯一一个内核使用的线程，一个线程阻塞不会影响其他的
• 多对一模型：多个用户的线程映射到一个内核使用的线程上，线程切换由用户的代码来进行
• 多对多模型：多个用户的线程映射到少数但不止一个内核线程上

写在后面

第一章的理论知识好多啊，整理的时间比我想象的多了好久，才不是鸽子精