操作系统(小林coding)

一、硬件结构

1.1 CPU是如何执行程序的？

冯诺依曼模型

定义了计算机基本结构

中央处理器（CPU）
内存
输入设备
输出设备
总线

内存

程序和数据都是存储在内存的，存储的区域是线性的。

数据存储的单位是一个二进制位（bit），即0或1。最小的存储单位是字节（byte），1byte=8bit

内存的地址从0开始编号，然后递增排列，结构类似数组，因此内存读写任何一个数据的速度都是一样的

中央处理器（CPU）

32位和64位CPU最主要的区别在于一次能计算多少字节数据：

32位CPU一次可以计算4个字节
64位PU一次可以计算8个字节

32位和64位通常称为CPU的位宽

CPU这样的设计的原因是为了能计算更大的值，如果是8位CPU，一次只能计算1个字节，即0~255的范围，这样就无法一完成计算10000*500，于是为了能够一次计算大数的运算，CPU需要支持多个byte一起计算，因此CPU位宽越大，可以计算的数值也就越大。

CPU内部还有一些组件，常见的有寄存器、控制单元和逻辑运算单元等。

控制单元：负责控制CPU工作
逻辑运算单元：负责计算
寄存器：有多种类型，每种寄存器的功能不一样。主要储存计算时的数据，寄存器就在CPU里，且紧挨着控制单元和逻辑运算单元，计算速度更快。
1. 通用寄存器：用来存放需要进行运算的数据
2. 程序计数器：用来存储CPU要执行的下一条指令所在的内存地址，此时指令还在内存中
3. 指令寄存器：用来存放程序计数器指向的指令，即指令本身，指令被执行完之前都存储在这里

为什么有程序计数器存放下一条指令的内存地址，还需要指令寄存器呢？

程序计数器和指令寄存器都是计算机中重要的寄存器之一，但是它们的作用是不同的。程序计数器用于存放下一条指令在内存中的地址，而指令寄存器则是用于存放当前正在执行的指令。

当计算机需要执行指令时，程序计数器会把下一条指令的地址取出来，然后将其存放到指令寄存器中，执行该指令后指令寄存器会自动移动到下一条指令的内存地址。这样计算机就能顺序执行程序中的指令了。

另外，指令寄存器还可以用于存放预取出的指令，这样可以提高指令的执行效率。当执行完当前指令后，指令寄存器可以直接取出预取出的指令执行，而不需要重新从内存中取出下一条指令的地址，从而节省了时间。

总线

总线用于CPU和内存以及其他设备之间的通信，可分为3种

地址总线：用于指定CPU将要操作的内存地址
数据总线：用于读写内存的数据
控制总线：用于发送和接收信号，比如中断、设备复位等信号，

当CPU要读写内存数据时，一般通过两个总线：

首先通过地址总线指定内存地址
再通过数据总线来传输数据

输入、输出设备

输入设备向计算机输入数据，计算机经过计算后，把数据输出给输出设备。期间，如果输入设备是键盘，按下按键是需要和CPU进行交互的，此时就需要用到控制总线了。

线路位宽与CPU位宽

数据通过线路电压的变化来传输的，低电压表示0，高电压表示1

一位一位的传输方式称为串行，下一个bit必须等待上一个bit传输完成后才能进行传输。如果想一次传输多位数据，只需要增加线路即可，此时数据可以并行传输。

为了避免低效率的串行传输的方式，线路的位宽最好一次就能访问到所有的内存地址。CPU要想操作内存地址就需要总线，如果总线只有一条，那每次只能表示0或1这两种情况，所以CPU一次只能操作两个内存地址了，如果CPU要想操作4G的内存，就需要32条地址总线，因为log2(4G)=32

CPU的位宽最好不要小于线路位宽，32位CPU一次最多只能操作32位宽的地址总线和数据总线

如果计算的数额不超过2^32的情况下，32位和64位CPU之间的处理速度没什么区别

32位CPU最大只能操作4GB内存，就算有8GB内存条也没用，因为寻址不到。而64位CPU的理论最大寻址空间2^64

程序执行的基本过程

程序实际上是一条一条指令，程序的运行过程实际上就是一条一条执行指令，负责执行指令的就是CPU了

CPU获取程序计数器的值，该值是指令的内存地址，然后CPU的控制单元通过操作地址总线指定需要访问的内存地址，接着通知内存设备准备数据，数据准备好后通过数据总线将指令数据传给CPU，CPU接收到内存传来的地址后，将这个指令数据存入到指令寄存器
CPU分析指令寄存器中的指令，确定之类的类型和参数，如果是计算类型的指令，就把指令交给逻辑运算单元运算；如果是存储类型的指令，则交给控制单元执行
CPU执行完指令后，程序计数器的值自增，表示指向下一条指令。自增的大小由CPU的位宽决定，比如32位的CPU，指令是4个字节，需要4个内存地址存放，因此程序计数器的值会增加4

总结：一个从程序执行的时候，CPU会根据程序计数器的内存地址，从内存里把需要执行的指令读取到指令寄存器里面指向。然后根据指令长度自增，即自增到下一个指令内存地址，然后又开始循环反复

a=1+2的执行具体过程

CPU不认识a=1+2这个字符串，这个字符串只是方便我们程序员认识。要想将这段程序跑起来，还需要把整个程序编译成汇编代码。

针对汇编代码，还需要把汇编代码翻译成机器码，即由0和1组成的机器语言。

程序编译过程中，编译器通过分析代码，发现1和2是数据，于是程序运行时，内存会有个专门的区域来存放这些数据，这个区域就是数据段，注意，数据和指令是分开区域存放的，存放指令区域的地方叫做正文段，如下图

注意，以上是编译器干的事

由于是在32位CPU执行的，因此一条指令是占32位大小，所以每条指令间隔4个字节

而数据的大小是根据程序中指定的变量类型，比如int类型的数据占4个字节，char类型的数据占1个字节

指令

上图中的指令内容实际上是一串二进制数字的机器码，简易的汇编代码实际上只是方便我们理解

不同的CPU有不同的指令集，也就对应着不同的汇编语言和不同的机器码

R指令：用在算数和逻辑操作，里面有读取和写入数据的寄存器地址。如果是逻辑位移操作，后面还有位移操作的位移量，而最后的功能码则是再前面的操作码不够时，扩展操作码；来表示对应的具体指令
I指令：用在数据传输、条件分支等。这个类型的指令，就没有了位移量和操作码，也没有了第三个寄存器，而是把这三部分直接合并成了一个地址值或一个常数
J指令：用在跳转，高6位之外的26位都是一个跳转的目标地址

编译器在编译程序时会构造指令，这个过程叫做指令的编码。CPU执行程序时，就会解析指令，这个过程叫做指令的解码。

现代大多数CPU都使用流水线的方式来执行指令，所谓的流水线实际上就是把一个任务拆分成多个小任务，于是一条指令通常分为4个阶段，称为4级流水线，如下图：

Fetch：CPU通过程序计数器读取对应内存地址的指令
Decode：CPU对指令进行解码
Execute：CPU执行指令
Store：CPU将计算结果存回寄存器或者将寄存器的值存入内存

这4个阶段，称为指令周期（Instruction Cycle），CPU的工作就是一个周期接着一个周期，周而复始

实际上，不同阶段其实是由计算机中不同组件完成的

指令的类型

指令的执行速度

假设CPU的主频是2.4GHz，意味着1秒钟会产生2.4G次的脉冲信号，则时钟周期时间是(1/2.4G)s

提升CPU执行效率可以从两方面入手：

降低时钟周期时间，即提高CPU主频，但今非昔比，摩尔定律早已失效，CPU主频很难再做到翻倍成长
降低CPU时钟周期数

CPU时钟周期数可以拆解成指令数*每条指令的平均时钟周期数（Cycles Per Instruction，简称CPI）

总结

1.2 存储器金字塔

内存和硬盘都属于计算机的存储设备，断电后内存的数据是会丢失的，而硬盘不会，因为硬盘是持久化存储设备，同时也是一个I/O设备

CPU内部也有存储数据的组件，比如寄存器、CPU的L1/L2/L3 Cache，只不过存储的数据非常小，但又因为接近CPU核心，所以访问速度很快，比硬盘快好几个数量级

存储器的层次结构

CPU内部
- CPU：大脑
- CPU中的寄存器：大脑正在思考的东西，处理速度最快，但是能存储的数据也是最少的
- CPU Cache：大脑中的记忆
  
  ——L1 Cache：数据存储和指令存储，L1距离CPU最近，所以它比L2、L3的读写速度都更快、存储空间更小
  
  ——L2/L3 Cache：大脑中的长期记忆
  
  寄存器和CPU Cache都在CPU内部，跟CPU距离近，因此读写速度都快，但是内存小
CPU外部
- 内存：书桌上的书，虽然一伸手就可以拿到，但是读写速度远慢于寄存器
- 硬盘：图书馆书架上的书，能存储的数据十分大，但是读写速度比内存差好几个数量级

从图书馆书架取书，把书放到桌子上，再阅读书，大脑记忆知识点，然后经过大脑思考。这一过程相当于从硬盘加载到内存，再从内存加载到CPU的寄存器和Cache中，然后再通过CPU进行处理和计算

对于存储器，速度越快 -> 能耗越高 -> 材料成本越贵，所以速度快的存储器容量都比较小

存储器可以分为以下几个级别：

寄存器
CPU Cache：
1. L1-Cache
2. L2-Cache
3. L3-Cache
内存
SSD/HDD硬盘

寄存器

最靠近CPU控制单元和逻辑计算单元的存储器

32位CPU中大多数寄存器可以存储4个字节
64位CPU中大多数寄存器可以存储8个字节

寄存器的访问速度非常快，一般要求在半个CPU时钟周期内完成读写，CPU时钟周期跟CPU主频息息相关，比如2GHz主频的CPU的时钟周期就是1/2G，也就是0.5ns

CPU处理一条指令的时候，除了读写寄存器，还需要解码指令、控制指令执行和计算。如果寄存器的速度太慢，则会拉长指令的处理周期，从而给用户感觉电脑"很慢"

CPU Cache

CPU Cache用的是一种叫SRAM(Static Random-Access Memory，静态随机存储器)的芯片

SRAM之所以叫静态存储器，是因为只要有电，数据就可以保持存在，而一旦断电，数据就会丢失了

在SRAM中，一个bit的数据，通常需要6晶体管，所以SRAM存储密度不高，同样的物理空间下，能存储的数据有限，不过因为SRAM电路简单，所以访问速度非常快

L1高速缓存

L1高速缓存的访问速度几乎和寄存器一样快，通常只需要2~4个时钟周期，大小在几十KB到几百KB不等

每个CPU核心都有一块属于自己的L1高速缓存，指令和数据在L1是分开存放的，所以L1高速缓存通常分成指令缓存和数据缓存

L2高速缓存

L2高速缓存同样存在于每个CPU核心，但离CPU核心的位置比L1更远，但大小比L1大，CPU型号不同大小也不同，通常在几百KB到几MB不等，访问速度更慢，在10~20个时钟周期

L3高速缓存

L3高速缓存通常是多个CPU核心共用，位置比L2高速缓存距离CPU核心更远，但大小更大，通常在几MB到几十MB不等，访问速度在20~60个时钟周期

内存

内存使用DRAM(Dynamic Random Access Memory，动态随机存取存储器)的芯片

相比SRAM，DRAM的密度更高，功耗更低，有更大的容量，而且造价比SRAM芯片便宜很多

DRAM存储一个bit数据，只需要一个晶体管和一个电容，但是因为数据会被存储在电容里，电容会不断漏电，所以需要定时刷新电容，才能保证数据不会丢失，这就是DRAM被称为动态存储器的原因，只有不断刷新，数据才不会丢失，才能够存储起来

DRAM的数据访问电路和刷新电路都比SRAM更复杂，所以访问速度会更慢，内存速度大概在200~300个时钟周期

SSD/HDD硬盘

SSD（Solid-state disk），固体硬盘，结构和内存类似，但是它相比内存的优点是断电后数据还在，而内存、寄存器、高速缓存断电后数据都会丢失。内存读写的速度比SSD快10~1000倍

还有一种传统硬盘，即机械硬盘（Hard Disk Drive，HDD），通过物理读写的方式来访问数据，因此访问速度非常慢，比内存慢10w倍左右

由于SSD价格接近机械硬盘，因此机械硬盘已经逐渐被SSD替代了

存储器的层次关系

CPU并不会直接和每一种存储器设备直接打交道，而是每一种存储器设备只和它相邻的存储器设备打交道

当CPU需要访问内存中的某个数据时，如果寄存器有这个数据，CPU直接从寄存器取数据即可，如果寄存器没有这个数据，CPU就会查询L1高速缓存，如果L1没有，则查询L2高速缓存，L2还是没有就查询L3高速缓存，L3依然没有的话，才去内存中取数据。（顿时理解了为什么传的是地址而不是其它了，因为地址是唯一的，不会出现歧义，而值可能有相等的两个值出现的情况）所以，存储层次结构也形成了缓存的体系

存储器之间的实际价格和性能差距

总结

不同的存储器之间性能差距很大，构造存储器分级很有意义，分级的目的是要构造缓存体系

1.3 如何写出让CPU跑得更快的代码？

CPU Cache有多快？

CPU和内存的访问速度的增长速率不匹配，导致CPU与内存的访问速度相差200~300多倍，意味着内存已经不满足CPU的需求了。为了弥补CPU与内存二者之间的性能差异，就在CPU内部引入了CPU Cache，也称高速缓存

CPU Cache通常分为大小不等的三级缓存，分别是L1 Cache、L2 Cache和L3 Cache

L3 Cache比L1 Cache和L2 Cache大很多，这是因为L1 Cache和L2 Cache都是每个CPU核心独有的，而L3 Cache是多个CPU核心共享的

CPU Cache的数据结构和读取过程是什么样的？

CPU Cache的数据是从内存中读取过来的，以一小块一小块读取数据的，而不是按照单个数据元素读取数据。在CPU Cache中，这样一小块一小块的数据，称为Cache Line（缓存块）

比如，有一个int array[100]的数组，载入array[0]时，由于数组元素大小在内存只占4字节，不足64字节，CPU就会顺序加载数组元素到array[15]，意味着array[0]~array[15]数组元素都会被缓存在CPU Cache中，因此当下次访问这些数组元素时，会直接从CPU Cache读取，而不需要再从内存中读取，大大提高了CPU读取数据的性能。

事实上，CPU读取数据时，无论数据是否存放到Cache中，CPU都是先访问Cache，只有当Cache中找不到数据时，才回去访问内存，并把内存中的数据读入到Cache中，CPU再从CPU Cache读取数据

这样的访问机制，和使用内存作为硬盘的缓存的逻辑是一样的，如果内存有缓存的数据，则直接返回，否则要访问龟速般的硬盘

CPU访问内存数据时，是一小块一小块数据读取的，具体大小取决于coherency_line_size的值，一般是64字节。在内存中，这块数据称为内存块（Block），读取时我们需要拿到数据所在内存块的地址。

直接映射Cache（Direct Mapped Cache）

把内存块的地址始终映射在一个CPU Line（缓存块）的地址，至于映射关系实现方式，则是使用取模运算，取模运算的结果就是内存块地址对应的CPU Line（缓存块）的地址

为了区别不同的内存块，在对应的CPU Line中会存储一个组标记（Tag），记录当前CPU Line中存储的数据对应的内存块，可以使用组标记来区分不同组但映射到同一块CPU Line的内存块。

除了组标记信息外，CPU Line还有两个信息：

从内存加载过来的实际存放数据（Data）
有效位（Valid bit），它是用标记对应的CPU Line中的数据是否是有效的，如果有效位是0，无论CPU Line中是否有数据，CPU都会直接访问内存，重新加载数据。

CPU在从CPU Cache读取数据时，并不是读取CPU Line中的整个数据块，而是读取CPU所需要的一个数据片段（Block），这样的数据统称为一个字（Word），即一个特。在对应的CPU Line中数据块中找到所需的字需要一个偏移量（Offset）

因此，一个内存的访问地址，包括组标记、CPU Line索引、偏移量，对于CPU Cache里的数据结构，则是由索引+有效位+组标记+数据块组成

如果内存中的数据已经在CPU Cache中，CPU访问一个内存地址的时候，会经历以下4个步骤：

根据内存地址中索引信息，计算在CPU Cache中的索引，也就是找出对应的CPU Line的地址
找到对应CPU Line后，判断CPU Line中的有效位，确认CPU LIne中数据是否有效，如果无效，CPU直接访问内存，并重新加载数据，如果数据有效，则往下执行
对比内存地址中组标记和CPU Line中的组标记，确认CPU Line中的数据是我们要访问的内存数据，如果不是的话，CPU就会直接访问内存，并重新加载数据，如果是的话，则往下执行
根据内存地址中偏移量信息，从CPU Line的数据块中，读取对应的字

其他通过内存地址找到CPU Cache中数据的策略：

全相连Cache（Fully Associative Cache）
组相连Cache（Set Associative Cache）

如何写出让CPU跑得更快的代码？

CPU访问内存的速度比访问CPU Cache的速度慢很多。所以如果 CPU 所要操作的数据在 CPU Cache 中的话，这样将会带来很⼤的性能提升。访问的数据在 CPU Cache 中的话，意味着缓存命中，缓存命中率越⾼的话，代码的性能就会越好，CPU 也就跑的越快。于是，「如何写出让 CPU 跑得更快的代码？」这个问题，可以改成「如何写出 CPU 缓存命中率⾼的代码？」。

L1 Cache通常分为数据缓存和指令缓存，因为CPu会分别处理数据和指令，比如 1+1=2 这个运算，+ 就是指令，会被放在「指令缓存」中，而输⼊数字 1 则会被放在「数据缓存」里。

因此，要分开看数据缓存和指令缓存的缓存命中率

eg.

一行一行遍历二维数组的速度快于一列一列遍历二维数组，是因为二维数组所占用的内存是连续的，且是按行顺序来保存的，局部性原理。

CPU具体会一次从内存中加载多少元素到CPU Cache和CPU Cache Line有关，表示CPU Cache一次性能加载数据的大小（Word）。

因此，遇到遍历数组的问题，按照内存布局顺序访问访问，可以有效利用CPU Cache带来的好处，提高代码性能

如何提高指令缓存的命中率？

eg.

//有一个元素为0到99之间随机数字组成的一维数组
int array[N];
for(int i=0;i<N;i++){
    array[i]=rand()%100;
}

//接下来，对这个数组做两个操作
//操作一：数组遍历
for(i=0;i<N;i++){
    if(array[i]<50){
        array[i]=0;
    }
}

//操作二：排序
sort(array,array+N);

问题：先遍历再排序快，还是先排序再遍历快

先了解CPU的分支预测期，对于if条件语句，意味着此时至少可以选择跳转到两段不同的指令执行，也就是if还是else中的指令。那么，如果分支预测可以预测到接下来要执行if里的指令还是else指令的话，就可以提前把这些指令放在缓存中，这样CPU可以直接从Cache读取到指令，于是执行速度就会很快

当数组中的元素是随机的，分支预测就无法有效工作，而当数组元素都是有序时，分支预测会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。

因此先排序再遍历速度会快很多，因为排序后，数字是从小到大的，前几次循环命中if<50的次数会比较多，于是分支预测就会缓存if里的array[i]=0指令到Cache中，后序CPU执行该指令就只需要从Cache读取即可

如果你肯定代码中if中表达式判断为true的概率比较高，可以使用显示分支预测工具，比如在C/C++语言中编译器提供了likely和unlikely这两种宏，可以用likely宏把if里的表达式包裹起来，反之用unlikely宏

#define likely(x)__builtin_expect(!!(x),1)
#define unlikely(x)__builtin_expect(!!(x),0)

if(likely(a==1)){
    //do something...
}else{
    //do something...
}

实际上，CPU自身的动态分支预测已经比较准了，只用当非常确信CPU预测的不准，且能够知道实际的概率情况时，才建议使用这两种宏。

如何提升多核CPU的缓存命中率？

在单核CPU，虽然只能执行一个进程，但是操作系统给每个进程分配了一个时间片，时间片用完了，就调度下一个进程，于是各个进程就按时间片交替地占用CPU，从宏观上看起来各个进程同时在执行

而现代CPU都是多核心的，进程可能在不同CPU核心来回切换执行，这对CPU Cache不是有利的，虽然L3 Cache事多核心之间共享的，但是L1和L2 Cache是每个核心独有的，如果一个进程在不同核心来回切换，各个核心呃缓存命中率会受到影响，相反如果进程都在同一个核心上执行，其数据的L1和L2 Cache的缓存命中率可以得到有效提高，缓存命中率高意味着CPU可以减少访问内存的频率

当有多个同时执行计算密集型的线程，为了防止因切换到不同的核心，而导致缓存命中率下降的问题，可以把线程绑定在某一个CPU核心上，性能得到非常可观的提升。

1.4 CPU缓存一致性

CPU Cache的数据写入

CPU Cache的结构：CPU Cache是由很多个Cache Line组成的，CPU Line是CPU从内存读取数据的基本单位，而CPU Line是由各种标志（Tag）+数据块（Data Block）组成

数据不光只有读操作，还有写操作，如果数据写入Cache之后，内存与Cache相对应的数据将会不同，这种情况下Cache和内存数据都不一致了，于是我们肯定需要把Cache中的数据同步到内存中。

两种写入数据的方法：

写直达（Write Through）
写回（Write Back）

写直达

保存内存与Cache一致性最简单的方式是，把数据同时写入内存和Cache中，这种方法成为写直达（Write Through）

写入钱会先判断数据是否已经在CPU Cache里面：

如果数据已经在Cache里面，先将数据更新到Cache里面，再写入到内存里面
如果数据没有在Cache里面，就直接把数据更新到内存里面

缺点：无论数据在不在Cache里面，每次写操作都会写回到内存，这样写操作将会花费大量的时间，性能会受到很大影响

写回

在写回机制中，当发生写操作时，新的数据仅仅被写入Cache Block，只有当修改过的Cache Block被替换时才需要写到内存中，减少了数据写回内存的频率，提高系统的性能

具体步骤：

如果当发生写操作时，数据已经在CPU Cache里的话，则把数据更新到CPU Cache里，同时标记CPU Cache里的这个Cache Block为脏（Dirty）的，表示CPU Cache里面的这个Cache Block的数据和内存不一致，这种情况还不需要把数据写回到内存中
如果当发生写操作时，数据所对应的Cache Block存放的是别的内存地址的数据的话，就要检查这个Cache Block里的数据是否标记为Dirty，如果已被标记，需要先把这个Cache Block里的数据写回到内存，然后再把当前要写入的数据写入到这个Cache Block，同时标记为Dirty；如果Cache Block没有被标记为Dirty，直接将数据写入到Cache Block就行，再把这个Cache Block标记为Dirty即可，原Cache Block无需写回到内存中

缓存一致性问题

现在CPU都是多核的，由于L1/L2 Cache是多个核心各自独有的，那么会带来多核心的缓存一致性问题。

假设A号核心和B号核心同时运行两个线程，都操作共同变量i（初始值为0）

A核心执行i++语句，出于性能的考虑，使用写回策略，先把值为1的执行结果写入到L1/L2 Cache中，然后把L1/L2 Cache中对应的Block标记为脏的，但这个时候数据还没有同步到内存中。这时如果B核心尝试从内存中读取变量i的值，将会得到错误的值，因为正确的i值还未被写回到内存中。所谓缓存一致性问题就是A号核心和B号核心的缓存在这个时候是不一致的。

解决这一问题需要一种机制，来同步两个不同核心里面的缓存数据，要做到以下2点：

第一点，某个CPU核心里的Cache数据更新时，必须要传播到其他核心的Cache，这称为写传播(Write Propagation)
第二点，某个CPU核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这称为事物的串行化(Transaction Serialization)

举例：

假设有一个含有4个核心的CPU，这4个核心都操作共同变量i（初始值为0）。A号核心先把i值变为100，而此时同一时间B号核心先把i值变为200，这里两个修改都会传播到C和D号核心。

问题来了，C号核心先收到了A号核心更新数据的事件，再收到B号核心更新数据的事件，因此C号核心看到的变量i是先变成100，后变成200。而如果D号核心接受到的事件是反过来的，则D号核心看到的是变量i先变成200，再变成100，虽然做到了写传播，但是各个Cache里面的数据仍然不一致。

所以，我们需要保证C号核心和D号核心都能看到相同顺序的数据变化，比如i变量都是先变成100，再变成200

要实现事物串形化需要做到以下2点：
- CPU核心对于Cache中数据的操作，需要同步给其他CPU核心
- 引入锁的概念，如果两个CPU核心里有相同数据的Cache，对于这个Cache数据的更新，只有拿到了锁，才能进行对应的数据更新

总线嗅探

写传播的原则就是当某个CPU核心更新了Cache中的数据，要把该事件广播通知到其他核心。最常见的实现方式是总线嗅探（Bus Snooping）

当A号CPU核心修改了L1 Cache中变量i的值，通过总线把这个事件广播通知给其他所有核心，然后每个CPU核心都会监听总线上的广播事件，并检查是否有相同的数据在自己的L1 Cache里面，如果B号CPU核心的L1 Cache中有该数据，那么也需要把该数据更新到自己的L1 Cache。

总线嗅探的方式很简单，CPU需要每时每刻监听总线上的⼀切活动，但是不管别的核心的 Cache 是否缓存相同的数据，都需要发出⼀个⼴播事件，这⽆疑会加重总线的负载。另外，总线嗅探只是保证了某个 CPU 核心的 Cache 更新数据这个事件能被其他 CPU 核心知道，但是并不能保证事务串形化。

MESI协议

Modified：已修改
Exclusive：独占
Shared：共享
Invalidated：已失效

这四个状态来标记Cache Line四个不同的状态

已修改对应着脏标记，代表该Cache Block上的数据已经被更新过，但是还没有写到内存里

已失效表示这个Cache Block里的数据已经失效了，不可以读取该状态的数据

独占和共享状态都代表Cache Block里的数据是干净的，即这个时候Cache Block里的数据和内存里面的数据是一致性的

独占和共享的差别在于，独占状态是，数据只存储在一个CPU核心的Cache里，而其他CPU核心的Cache没有该数据。这个时候如果要向独占Cache写数据，就可以直接自由地写入，而不需要通知其他CPU核心，因为只有这个Cache有这个数据，就不存在缓存一致性问题，于是就可以随便操作该数据。

另外，在独占状态下的数据，如果有其他核心从内存也读取了相同的数据到各自的Cache，那么这个时候，独占状态下的数据就会变成共享状态

共享状态代表着相同的数据在多个CPU核心里的Cache里都有，所以当我们要更新Cache里面的数据的时候，不能直接修改，而是要先向所有的其他CPU核心广播一个请求，要求先把其他核心的Cache中对应的Cache Line标记为无效状态，然后再更新当前Cache里面的数据

eg：

当A号核CPU核心从内存中读取变量i的值，数据被缓存在A号CPU核心自己的Cache里面，此时其他CPU核心的Cache没有缓存该数据，于是标记Cache Line状态为独占，此时其Cache中的数据与内存是一致的
然后B号CPU核心也从内存中读取了变量i的值，此时会发送消息给其他CPU核心，由于A号CPU核心已经缓存了该数据，所以会把数据返回给B号CPU核心，在这个时候，A和B核心缓存了相同的数据，Cache Line的状态就会变成共享，并且其Cache中的数据与内存也是一致的
当A号CPU核心要修改Cache中i变量的值，发现数据对应的Cache Line的状态是共享状态，则要向所有其他CPU核心广播一个请求，要求先把其他核心的Cache中对应的Cache Line标记为无效状态，然后A号CPU核心才更新里面的数据，同时标记Cache Line为已修改状态，此时Cache中的数据就与内存不一致了
如果A号CPU核心继续修改Cache中i变量的值，由于此时的Cache LIne是已修改状态，因此不需要给其他CPU核心发送消息，直接更新数据即可
如果A号CPU核心的Cache对应的i变量对应的Cache要被替换，发送Cache Line状态是已修改状态，就会在替换前先把数据同步到内存中

所以，发现当Cache Line状态是已修改或者独占状态时，修改更新其数据不需要广播给其他CPU核心

总结

CPU在读写数据：

CPU读数据：都是在CPU Cache读写数据的，原因是Cache里CPU很近，读写性能相比内存高出很多。对于Cache里没有缓存CPU所需要的数据的情况，CPU则会从内存中读取数据，并将数据缓存到Cache里面，最后CPU再从Cache读取数据
CPU写数据：写直达或写回两种策略

缓存一致性：

写传播
事物的串行化

基于总线嗅探的MESI协议满足以上两点，保障了缓存一致性

1.5 CPU是如何执行任务的

问题引入

CPU如何读写数据的？

Cache伪共享是什么？

现在假设有一个双核心的CPU，这两个CPU核心并行运行着两个不同的线程，它们同时从内存中读取两个不同的数据，分类是类型为long的变量A和B，这两个数据的地址在物理内存上是连续的，如果Cache LIne的大小是64字节，并且变量A在Cache Line的开头位置，那么这两个数据是位于同一个Cache Line中，又因为CPU Line是CPU从内存读取数据到Cache的单位，所以这两个数据会被同时读入到了两个CPU核心中各自的Cache中。

如果两个不同核心的线程分别修改不同的数据，比如1号核心的线程只修改了变量A，或2号CPU核心的线程只修改了变量B，会发生什么？

分析伪共享问题

结合保证多核缓存一致的MESI协议，来说明整个过程。

最开始变量A和B都还不在Cache里面，假设1号核心绑定了线程A，2号核心绑定了线程B，线程A只会读写变量A，线程B只会读写变量B
1号核心读取变量A，由于CPU从内存读取数据到Cache的单位是Cache Line，也正好是变了A和B的数据归属于同一个Cache Line，所以A和B的数据都会被加载到Cache，并将此Cache Line标记为独占状态
接着，2号核心开始从内存里读取变量B，同样也是读取Cache Line大小的数据到Cache中，此Cache Line中的数据也包含了变量A和B，此时1号和2号核心的Cache Line状态变为共享状态
1号核心需要修改变量A，发现此Cache Line的状态是共享状态，所以先需要通过总线发送消息给2号核心，通知2号核心把Cache中对应的Cache Line标记为已失效状态，然后1号核心对应的Cache Line状态变成已修改状态，并且修改变量A
之后，2号核心需要修改变量B，此时2号核心的Cache中对应的Cache Line是已失效状态，另外由于1号核心的Cache也有此相同的数据，且状态为已修改状态，所以要先把1号核心的Cache对应的Cache Line写回内存，然后2号核心再从内存读取Cache Line大小的数据到Cache中，最后把变量B修改到2号核心的Cache中，并将状态标记为已修改状态

Cache并没有起到缓存的效果，虽然变量A和B之间其实没有任何的关系，但是因为同时归属于一个 Cache Line，这个Cache Line中的任意数据被修改后，都会相互影响，从而出现4和5这两个步骤

因此，这种因为多个线程同时读写同一个Cache Line的不同变量时，而导致CPU Cache失效的现象称为伪共享（False Sharing)

避免伪共享的方法

因此，对于多个线程共享的热点数据，即经常会修改的数据，应该避免这些数据刚好在用一个Cache Line中，否则就会出现伪共享问题

从上面的宏定义可以看到：

如果在多核（MP）系统里，该宏定义是__cacheline_aligned，也就是Cache Line的大小
如果在单核系统里，该宏定义是空的

因此针对在同一个Cache Line中的共享的数据，如果在多核之间竞争比较严重，为了防止伪共享现象的发生，可以采用上面的宏定义使得变量在Cache Line里是对齐的

假设有以下结构体
struct test{
    int a;
    int b;
};

结构体里的两个成员变量a和b在物理内存地址上是连续的，于是它们可能会位于同一个Cache Line中，所以，为了防止前面提到的Cache伪共享问题，我们可以使用上面的宏定义，将b的地址设置为Cache Line对齐地址，如下：
struct test{
    int a;
    int b __cacheline_aligned_in_smp;
};

这样a和b变量就不会在同一个Cache Line中了

所以，避免Cache伪共享实际上是用空间换时间的思想

另一个应用层面的规避方案，有一个Java并发框架Discruptor使用字节填充+继承的方式，来避免伪共享问题

RingBufferPad类里7个long类型的名字看起来很奇怪，但事实上，它们虽然看起来毫无作用，但是对性能的提升起到了至关重要的作用

CPU Cache从内存读取数据的单位是CPU Line，一般64位CPU的CPU Line的大小是64字节，一个long类型的数据是8个字节，所以CPU一下会加载8个long类型的数据

根据JVM对象继承关系中父类成员和子类成员，内存地址是连续排列布局的，因此RingBufferPad中的7个long类型数据作为Cache Line前置填充，而RingBuffer中的7个long类型数据则作为Cache Line后置填充，这14个long变量没有任何实际用途，更不会对它们进行读写操作

另外，RingBufferFelds里面定义的这些变量都是final修饰的，意味着第一次加载之后不会再修改，又由于前后各填充了7个不会被读写的long类型变量，所以无论怎么加载Cache Line，这整个Cache Line里都没有会发生更新操作的数据，于是只要数据被频繁地读取访问，就自然没有数据被换出Cache的可能，也因此不会产生伪共享问题

CPU如何选择线程的？

在Linux内核中，进程和线程都是用tark_struct结构体表示的，区别在于线程的tark_struct结构体里部分资源是共享了进程已创建的资源，比如内存地址空间，代码段、文件描述符等，所以Linux中的线程也被称为轻量级线程，因为线程的tart_struct相比进程的tatk_struct承载的资源比较少

一般来说，没有创建线程的进程，是只有单个执行流，它被称为是主线程。如果想让进程处理更多事情，可以创建多个线程分别去处理，但不管怎么样，它们对应到内核里都是tark_struct

所以，Linux内核里的调度器，调度的对象就是tark_struct，接下来就把这个数据结构统称为任务

在Linux系统中，根据任务的优先级以及响应要求，主要分为两种，其中优先级的数值越小，优先级越高：

实时任务：对系统的响应时间要求很高，也就是要尽可能快的执行实时任务，优先级在0~99范围内的就算实时任务
普通任务：响应时间没有很高的要求，优先级在100~139范围内的都是普通任务级别

调度类

由于任务有优先级之分，Linux系统为了保障高优先级的任务能够尽可能早的被执行，于是分为了这几种调度类，如下图：

完全公平调度（Completely Fair Scheduling）

这个算法的理念是想让分配给每个任务的CPU时间是一样的，于是它为每个任务安排一个虚拟运行时间vruntime，如果一个任务在运行，其运行的越久，该任务的vruntime自然就会越大，而没有被运行的任务，vruntime是不会变化的

在CFS算法调度的时候，会优先选择vruntime少的任务，以保证每个任务的公平性，同时计算vruntime的同时还要考虑普通任务的权重值，并不是优先级的值，内核中会有一个nice级别与权重值的转换表，nice级别越低的权重值就越大

把NICE_0_LOAD当作一个常量，通过计算，高权重任务的vruntime比低权重的vruntime少，由于是CFS调度，所以会优先选择vruntime少的任务进行调度，所以高权重的任务就会被优先调度了，于是高权重的实际运行时间自然就多了

CPU运行队列

一个系统通常都会运行很多任务，多任务的数量基本都是远超CPU核心数量的，因此这时候就需要排队

事实上，每个CPU都有自己的运行队列，，用于描述在此CPU上所运行的所有进程，其队列包含三个运行队列，Deadline运行队列dl_rq、实时任务运行队列rt_rq和CFS运行队列csf_rq，其中cfs_rq是用红黑树来描述的，按vruntime大小来排序的，最左侧的叶子节点，就是下次会被调度的任务

这几种调度类是有优先级的，优先级如下：Deadline>Realtime>Fair，这意味着Linux选择下一个任务执行的时候，会按照此优先级顺序进行选择，也就是说先从dl_rq里选择任务，然后从rt_rq里选择任务，最后从csf_里选择任务。因此，实时任务总是会比普通任务优先被执行

调整优先级

如果启动任务时，没有特意指定优先级的话，默认呢情况下都是普通任务，普通任务的调度类是Fair，由CFS调度器来进行管理。CFS调度器的目的是实现任务运行的公平性，也就是保障每个人物的运行时间是差不多的

如果你想让某个普通任务有更多的执行时间，可以调整任务的nice值，从而让优先级高一些的任务执行更多时间。nice值能设置的范围是-20~19，值越低，表明优先级越高，因此，-20是最高优先级，19则是最低优先级，默认优先级是0

事实上，nice值并不是优先级，而是表示优先级的修正数据，它与优先级（priority）的关系是这样的：priority(new)=priority(old)+nice。内核中，priority的范围是0~~139，值越低，优先级越高，其中前面的0~~99范围是提供给实时任务使用的，而nice值是映射到100~139，这个范围是提供给普通任务用的，因此nice值调整的是普通任务的优先级

nice值调整的是普通任务的优先级，所以不管怎么缩小nice值，任务永远都是普通任务，如果某些任务要求实时性比较高，那么可以考虑改变任务的优先级以及调度策略，使得它变成实时任务

1.6 软中断

中断是什么？

在计算机中，中断是系统用来响应硬件设备的请求的一种机制，操作系统收到硬件的中断请求，会打断正在执行的进程，然后调用内核中的中断处理程序来响应请求。中断是一种异步的事件处理机制，可以提高系统的并发处理能力

操作系统收到了中断请求，会打断其他进程的运行，所以中断请求的响应程序，也就是中断处理程序，要尽可能快的执行完，这样可以减少对正常进程运行调度的影响。

而且，中断处理程序在响应中断时，可能还会临时关闭中断，这意味着，如果当前中断处理程序没有执行完之前，系统中其他的中断请求都无法被响应，也就是说中断有可能会丢失，所以中断处理程序要短且快

什么是软中断？

Linux系统为了解决中断处理程序执行过长和中断丢失的问题，将中断过程分成了两个阶段，分别是上半部和下半部：

上半部用来快速处理中断，一般会暂时关闭中断请求，主要负责处理跟硬件紧密相关或者时间敏感的事情
下半部用来延迟处理上半部未完成的工作，一般以内核线程的方式运行

也可以理解为：

上半部直接处理硬件请求，也就是硬中断，主要是负责耗时短的工作，特点是快速执行
下半部是由内核触发，也就是说软中断，主要是负责上半部未完成的工作，通常都是耗时比较长的事情，特点是延迟执行

还有一个区别，硬中断（上半部）是会打断CPU正在执行的任务，然后立即执行中断处理程序，而软中断（下半部）是以内核线程的方式执行，并且每一个CPU都对应一个软中断内核线程，名字通常为 ksoftirqd/CPU编号

不过，软中断不只是包括硬件设备中断处理程序的下半部，一些内核自定义事件也属于软中断，比如内核调度等， RCU锁（内核里最常用的一种锁）等。

系统里有哪些软中断？

如何定位软中断CPU使用率过高的问题？

1.7 为什么0.1+0.2不等于0.3？

引入：

为什么负数要用补码表示？

如果负数不是使用补码的方式表示，则在做基本对加减法运算时，还需要多一步操作来判断是否为负数，如果为负数，还得把加法反转成减法，或者把减法反转为加法，因为加减法运算在计算机里十分常见，为了性能考虑，应当尽量简化该过程

利用补码的表示方式，对于负数的加减法操作，实际上是和正数的加减法操作一样的

十进制小数与二进制的转换

整数部分的转换是用除2取整法，而小数部分使用乘2取整法，将十进制中的小数部分乘以2作为二进制的一位，然后继续取小数部分乘以2作为下一位，直到不存在小数为止

并非所有小数都可以转二进制表示

由于计算机的资源是有限的，所以没办法用二进制精确地表示0.1，只能用近似值来表示，就是在有限的精度情况下，最大化接近0.1的二进制数，于是就会造成精度缺失的情况

计算机是怎么存小数的？

计算机存储小数的采用的是浮点数，名字里的浮点表示小数点是可以浮动的

比如1000.101这个二进制数，可以表示成1.000101×2^3，类似于数学上的科学计数法

0.1+0.2==0.3?

这主要是因为有的小数无法可以用完整的二进制来表示，所以计算机里只能采用近似数的方式来保存，两个近似数相加，得到的必然也是一个近似数

总结

负数采用补码的形式表达是为了统一和正数的加减法操作

二、操作系统结构

2.1 Linux内核 vs Windows内核

内核

内核作为应用连接硬件设备的桥梁，应用程序只需关心与内核交互，不用关心硬件的细节

现代操作系统，内核一般提供4个基本能力：

进程调度：管理进程、线程，决定哪个进程、线程使用CPU
内存管理：管理内存，决定内存的分配与回收
硬件通信：管理硬件设备，为进程与硬件设备之间提供通信能力
系统调用：提供系统调用，如果应用程序要运行更高权限的服务，就需要有系统调用，它是用户程序与操作系统之间的接口

内核具有很高的权限，可以控制CPU、内存、硬盘等硬件，而应用程序具有的权限很低，因此大多数操作系统吧内存分成了两个区域：

内核空间：该内存空间只有内核程序可以访问
用户空间：该内存空间专门给应用程序使用

用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间。因此，当程序使用用户空间时，常说该程序在用户态执行，而当程序在内核空间时，程序则在内核态执行

应用程序如果需要进入内核空间，需要通过系统调用，以下是系统调用的过程：

Linux的设计

Linux内核设计理念：

MultiTask：多任务
SMP：对称多处理
ELF：可执行文件链接格式
Monolithic Kernel：宏内核

MultiTask

多任务意味着可以有多个任务同时执行，这里的同时可以是并发或并行

并发：对于单核CPU时，可以让每个任务执行一小段时间，时间到就切换到另一个任务，从宏观角度看，一段时间执行了多个任务
并行：对于多核CPU，多个任务可以同时被不同核心的CPU同时执行

SMP

对称多处理意味着每个CPU的地位是相等的，对资源的使用权限也是相同的，多个CPU共享同一个内存，每个CPU都可以访问完整的内存和硬件资源。这个特点决定了Linux操作系统不会有某个CPU单独服务应用程序或内核程序，而是每个程序都可以被分配到任意一个CPU上被执行

ELF

可执行文件链接格式是Linux中可执行文件的存储格式，格式如下：

ELF文件有两种索引，Program header table记录了运行时所需的短，Section header table记录了二进制文件中各个段的首地址

ELF文件生成过程：

我们编写的代码，首先通过编译器编译成汇编代码，接着通过汇编器编程目标代码，也就是目标文件，最后通过链接器把多个目标文件以及调用的各种函数库链接起来，形成一个可执行文件，也就是ELF文件

ELF文件执行过程：

执行ELF文件时，会通过装载器把ELF文件装载到内存里，CPU读取内存中的指令和数据，于是程序就被执行起来了

Monolithic Kernel

Linux内核架构就是宏内核，意味着Linux的内核是一个完整的可执行程序，且拥有最高的权限

宏内核的特征是系统内核的所有模块，比如进程调度、内存管理、文件系统、设备驱动等都运行在内核态

Linux同时也实现了动态加载内核模块的功能，例如大部分设备驱动是以可加载模块的形式存在的，与内核其他模块解耦，让驱动开发和驱动加载更为方便、灵活。

与宏内核相反的是微内核，微内核架构的内核只保留最基本的能力，比如进程调度、虚拟机内存、中断等，把一些应用放到了用户空间，比如驱动程序、文件系统等。这样服务与服务之间是隔离的，单个服务出现故障或者完全攻击，也不会导致整个操作系统挂掉，提高了操作系统的稳定性和可靠性。

微内核内核功能少，可移植性高，相比宏内核有一点不好的地方在于，由于驱动程序不在内核中，而且驱动程序一般会频繁调用底层，于是驱动和硬件设备交互就需要频繁切换到内核态，带来性能损耗。

还有一种内核叫混合类型内核，他的架构类似微内核，内核里面会有一个最小版本的内核，然后其他模块在这个基础上搭建，实现时和宏内核类似，即把整个内核做成一个完整的程序，大部分服务都在内核中，相当于宏内核的方式包裹着一个微内核

Windows设计

当今Windows使用的内核叫Windows NT(New Technology)，结构如下：

Windows和Linux一样，同样支持MultiTask和SMP，但不同的是，Window的内核设计是混合型内核。

Windows的可执行文件的格式与Linux也不同，所以这两个系统的可执行文件是不可以在对方系统上运行的

Windows的可执行文件格式叫PE，称为可移植执行文件，扩展名通常是.exe、.dll、.sys。结构如下：

三、内存管理

3.1 为什么要有虚拟内存？

虚拟内存

单片机没有操作系统，每次写完代码，都需要借助工具把程序烧录进去，这样程序才能跑起来。

另外，单片机的CPU是直接操作内存的物理地址。

在这中情况下，要想在内存中同时运行两个程序是不可能的。如果第一个程序在2000的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的，这两个程序会立刻崩溃

操作系统如何解决这个问题呢？

这个问题的关键在于两个程序都引用了绝对物理地址，而这正式所需要避免的

我们可以把进程所使用的地址隔离开来，即让操作系统为每个进程分配独立的一套虚拟地址。前提是每个进程都不能访问物理地址，至于虚拟地址怎么翻译成物理地址，对进程来说是透明的，由操作系统安排。

操作系统负责将不同进程的虚拟地址和不同内存的物理地址映射起来

这样程序要访问虚拟地址时，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，就不会有冲突了

虚拟内存地址：程序所使用的内存地址
物理内存地址：硬件里面的空间地址

进程持有的虚拟地址会通过CPU芯片中的内存管理单元MMU的映射关系来转换成物理地址，然后再通过物理地址访问内存

操作系统是如何管理虚拟地址与物理地址之间的关系？

主要有两种方式，分别是内存分段和内存分页

内存分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段的形式把这些段分离出来

分段机制下，虚拟地址和物理地址是如何映射的？

分段机制下的虚拟地址由两部分组成，段选择子和段内偏移量

段选择子就保存在段寄存器里面。段选择子里面最重要的就是段号，用作段表的索引。段表里面保存的是这个段的基地址和特权等级等
虚拟地址中的段内偏移量应该位于0和段界限之间，如果段内偏移量是合法的，就将段内基地址加上段内偏移量得到物理内存地址

虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序的虚拟地址分成4个段，每个段在段表中有一个项，在这一项中找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址，如下图：

分段方式解决了程序本身不需要关系具体的物理内存地址的问题，但是也有不足之处：

内存碎片
内存交换的效率低

分段为什么会产生内存碎片问题？

分段为什么会导致内存交换效率低的问题？

对于多进程的系统来说，用分段的方式，很容易产生内存碎片，产生了内存碎片，就不得不重新Swap内存区域，这个过程会产生性能瓶颈

因为硬盘的访问速度比内存慢太多了，每一次内存交换，都需要把一大段连续的内存数据写到硬盘上

所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，整个机器会显得卡顿

为了解决内存分段的内存碎片和内存交换效率低的问题，出现了内存分页

内存分页

分段的好处就是能产生连续的内存空间，但是会出现内存碎片和内存交换空间太大的问题

要解决这些问题，就要减少出现内存碎片的情况。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点。

分页是把整个虚拟和物理地址切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，叫页。在Linux下，每一页的大小为4KB

虚拟地址与物理地址之间通过页表来映射，如下图：

页表存储在内存里，内存管理单元（MMU）就做将虚拟内存地址转换成物理地址的工作

而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表、最后再返回用户空间，恢复进程的运行

分页是怎么解决分段的内存碎片、内存交换效率低的问题？

由于内存空间都是预先划分好的，不会像分段产生间隙非常小的内存，这正是分段会产生内存碎片的原因，而采用了分页，那么释放的内存都是以页为单位释放的，也就不会产生无法给进程使用的小内存

如果内存空间不够，操作系统就会把其他正在运行中的最近没被使用的（NRU）的内存页面给释放掉，也就是暂时写在硬盘上，称为换出。一旦需要的时候，再加载进来，称为换入。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高

更进一步地，分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存里面的指令和数据时，再加载到物理内存里面去。

分页机制下，虚拟地址和物理地址是如何映射的？

在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理地址，如下图：

对于一个内存地址转换，三个步骤：

把虚拟内存地址，切分成页号和偏移量
根据页号，从页表里面，查询对应的物理页号
直接拿物理页号，加上前面的偏移量，就得到了物理内存地址

简单的分页有什么缺陷？

有空间上的缺陷

因为操作系统是可以同时运行非常多的进程的，意味着页表会非常的庞大

每个进程都有自己的页表（互不干扰，我认为是一种保护机制）

多级页表

要解决上面的问题，就需要采用一种叫作多级页表的解决方案

如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，可以在需要时再创建二级页表

为什么不分级的页表就做不到这样节约内存？

从页表的性质看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。加入虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有100多万个页表项来映射，而二级分页则只需要1024个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）

把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用

TLB

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，降低了地址转换速率，带来了时间上的开销

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域

利用这一特性，把最常问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在CPU芯片中，加入了一个专门存放程序最常访问的页表项的Cache，这个Cache就是TLB，通常成为页表缓存、转址旁路缓存、快表等

有了TLB后，CPU在寻址时，会先查TLB，如果没找到才会继续查常规的页表

TLB的命中率很高，因为程序最常访问的页表就那么几个

段页式内存管理

内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理

段页式内存管理实现的方式：

先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制
接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页

这样，地址结构就由段号、段内页号和页内位移三部分组成

用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号，如图所示：

Linux内存管理

页式内存管理的作用是在由段式内存管理所映射而成的地址上再加上一层地址映射

由于此时由段式内存管理映射而成的地址不再是“物理地址”了，Intel就称之为“线性地址”（也称虚拟地址）。于是，段式内存管理先将逻辑地址映射成线性地址，然后再由页式内存管理将线性地址映射成物理地址

逻辑地址：程序所使用的地址，通常是没被段式内存管理映射的地址
虚拟地址：通过段式内存管理映射的地址，称为线性地址

Linux内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制

3.2 malloc是如何分配内存的？

Linux进程的内存分布长什么样？

32位系统的用户空间分布情况如下：

用户空间从低到高分别是6种不同的内存段：

malloc是如何分配内存的？

实际上，malloc()并不是系统调用，而是C库里的函数，用于动态分配内存

malloc申请内存的时候，有两种方式向操作系统申请堆内存

方式一：通过brk()系统调用从堆分配内存
方式二：通过mmap()系统调用在文件映射区域分配内存

malloc()分配的是物理内存吗？

malloc(1)会分配多大的虚拟内存？

free释放内存，会归还给操作系统吗？

为什么不全部使用mmap来分配内存？

既然brk那么牛逼，为什么不全部使用brk来分配？

free()函数只传入一个内存地址，为什么能知道要是否多大的内存？

总结

malloc()有两种分配方式：

brk系统调用：通过往高地址移动堆顶指针来获取地址空间，一般在低于某个阈值下使用
mmap系统调用：通过向文件映射区域索要地址空间，一般在高于某个阈值下使用

free()对于不同malloc()方式也不同：

brk的free：free之后操作系统并没有真正的回收，而是将空闲空间保留在了malloc内存池，等下次有需求时就直接分配，更快速
mmap的free：free之后直接被操作系统回收

brk()和mmap()必须一起使用：

只用brk()：时间久了，malloc内存池会越来越大，空闲区域也就越来越多，导致内存泄漏
只用mmap()：总是要系统调用，浪费时间

只需传给free内存起始地址，free就知道该释放多大的内存，因为malloc返回给用户态的内存起始地址比进程的堆空间起始地址多了16字节，这16个字节就是用来保存该内存块的信息的，free的时候只需要对传进来的内存地址向左偏移16字节，然后从这16字节读取内存块信息，就知道要释放多大的内存了。

3.3 内存满了，会发生什么？

虚拟内存有什么用？

虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域
由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性

内存分配的过程是怎样的？

申请物理内存的过程如下：

哪些内存可以被回收？

主要有两类内存可以被回收，而且它们的回收方式也不同

回收内存带来的性能影响

调整文件页和匿名页的回收倾向
尽早触发kswapd内核线程异步回收内存
NUMA架构下的内存回收策略

如何保护一个进程不被OOM杀掉呢？

总结

内存回收主要有两种方式：

后台回收内存：kswapd内核线程回收内存，该方式是异步的，不会阻塞进程的执行
直接回收内存：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，该方式是同步的，会阻塞进程的执行

可被回收的内存类型有两种：

文件页的回收：对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先写回到磁盘再释放内存，这个操作会发生磁盘I/O，因而影响系统性能
匿名页的回收：如果开启了Swap机制，那么Swap机制会将不常访问的匿名页换出到磁盘中，下次访问时再从磁盘换入到内存中，这个操作是会影响系统性能的

文件页和匿名页的回收都是基于LRU算法的，也就是优先回收不常访问的内存，回收内存的操作基本都会发生磁盘I/O的，如果回收内存的操作很频繁，意味着词频I/O次数会很多，这个过程势必会影响系统的性能

3.4 在4GB物理内存的机器上，申请8G内存会怎么样？

操作系统虚拟内存大小

32位系统的场景

64位系统的场景

Swap机制的作用

实验一：没有开启Swap机制

实验二：有开启Swap机制

总结

在32位操作系统下，进程理论上最大能申请3GB大小的虚拟内存，所以直接申请8GB内存，会申请失败
在64位操作系统下，因为进程理论上最大能申请128TB大小的虚拟内存，即使物理内存只有4GB，申请8GB内存也没问题，因为申请的内存是虚拟内存。如果这块虚拟内存被访问了（要有对应物理内存了），要看系统有没有Swap分区：
- 没有Swap分区：物理空间不够，进程会被操作系统杀掉，原因是OOM（Out Of Memory）
- 有Swap分区：即使物理内存只有4GB，程序也能正常使用8GB的内存，进程可以正常运行

3.5 如何避免预读失效和缓存污染的问题？

Linux和MySQL缓存

Linux操作系统的缓存

在应用程序读取文件的数据的时候，Linux操作系统是会对读取的文件数据进行缓存的，会缓存在文件系统中的Page Cache（如下图中的页缓存）

Page Cache属于内存空间里的数据，由于内存访问比磁盘访问快很多，在下一次访问相同的数据就不需要通过磁盘I/O了，命中缓存就直接返回数据即可

因此，Page Cache起到了加速访问数据的作用

MySQL的缓存

MySQL的数据是存储在磁盘里的，为了提升数据库的读写性能，InnoDB存储引擎设计了一个缓存池(Buffer pool)，Buffer pool属于内存空间里的数据

传统LRU是如何管理内存数据的？

3.5.3 预读失效，怎么办？

什么是预读机制？

预读失效会带来什么问题？

如何避免预读失效造成的影响？

Linux是如何避免预读失效带来的影响？

MySQL是如何避免预读失效带来的影响？

缓存污染，怎么办？

什么是缓存污染？

缓存污染会带来什么问题？

怎么避免缓存污染造成的影响？

MySQL的方式可以理解为经过那么长的时间，这个页还停留在old区域而没被淘汰，说明是常用页，可以升级到young区域。而如果在1秒内又第二次访问了，说明该页当前是在批量读入，还无法确定是否为常用页。

总结

传统LRU算法遇到的问题及解决方式：

预读失效：改善链表结构
缓存污染：提高进入活跃LRU链表或young区域的门槛

3.6 深入理解Linux虚拟内存管理

到底什么是虚拟内存地址

为什么要使用虚拟地址访问内存

如果在程序中直接使用物理内存地址会发生什么情况？

进程虚拟内存空间

Linux进程虚拟内存空间

32位机器上进程虚拟内存空间分布

64位机器上进程虚拟内存空间分布

进程虚拟内存空间的管理

无论是32位还是64位，都有如下几个核心内存区域：

内核如何划分用户态和内核态虚拟内存空间

内核如何布局进程虚拟内存空间

内核如何管理虚拟内存区域

定义虚拟内存区域的访问权限和行为规范

关联内存映射中的映射关系

针对虚拟内存区域的相关操作

虚拟内存区域在内核中是如何被组织的

程序编译后的二进制文件如何映射到虚拟内存空间中

static int load_elf_binary(struct linux_binprm *bprm)
{
      ...... 省略 ........
  // 设置虚拟内存空间中的内存映射区域起始地址 mmap_base
  setup_new_exec(bprm);

     ...... 省略 ........
  // 创建并初始化栈对应的 vm_area_struct 结构。
  // 设置 mm->start_stack 就是栈的起始地址也就是栈底，并将 mm->arg_start 是指向栈底的。
  retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP),
         executable_stack);

     ...... 省略 ........
  // 将二进制文件中的代码部分映射到虚拟内存空间中
  error = elf_map(bprm->file, load_bias + vaddr, elf_ppnt,
        elf_prot, elf_flags, total_size);

     ...... 省略 ........
 // 创建并初始化堆对应的的 vm_area_struct 结构
 // 设置 current->mm->start_brk = current->mm->brk，设置堆的起始地址 start_brk，结束地址 brk。 起初两者相等表示堆是空的
  retval = set_brk(elf_bss, elf_brk, bss_prot);

     ...... 省略 ........
  // 将进程依赖的动态链接库 .so 文件映射到虚拟内存空间中的内存映射区域
  elf_entry = load_elf_interp(&loc->interp_elf_ex,
              interpreter,
              &interp_map_addr,
              load_bias, interp_elf_phdata);

     ...... 省略 ........
  // 初始化内存描述符 mm_struct
  current->mm->end_code = end_code;
  current->mm->start_code = start_code;
  current->mm->start_data = start_data;
  current->mm->end_data = end_data;
  current->mm->start_stack = bprm->p;

     ...... 省略 ........
}

内核虚拟内存空间

32位体系内核虚拟内存空间布局

直接映射区

ZONE_HIGHMEM高端内存

vmalloc动态映射区

永久映射区

固定映射区

临时映射区

32位体系结构下Linux虚拟内存空间整体布局

64位体系内核虚拟内存空间布局

64位体系结构下Linux虚拟内存空间整体布局

到底什么是物理内存地址

3.7 深入理解Linux物理内存管理

从CPU角度看物理内存模型

FLATMEM平坦内存模型

DISCONTIGMEM非连续内存模型

SPARSEMEM稀疏内存模型

物理内存热插拔

从CPU角度看物理内存架构

一致性内存访问UMA架构

非一致性内存访问NUMA架构

NUMA的内存分配策略

内核如何管理NUMA节点

内核如何统一组织NUMA节点

四、进程与线程

4.1 进程、线程基础知识

进程

我们编写的代码只是一个存储在硬盘的静态文件，通过编译后就会生成二进制可执行文件，当运行这个可执行文件后，它就会被装载到内存中，接着CPU会执行程序中的每一条指令，这个运行中的程序，就被称为进程（Process）

当进程要从硬盘读取数据时，CPU不需要阻塞等待数据的返回，而是去执行另外的进程。当磁盘数据返回时，CPU会收到中断，于是CPU再继续执行这个进程

虽然单核的CPU在某一个瞬间，只能运行一个进程。但在1秒钟期间，可能会运行多个进程，这样就产生了并行的错觉，实际上这是并发。

并发和并行有什么区别？

进程与程序的关系的类比

进程是程序运行的实例

进程的状态

运行状态：该时刻进程占用CPU
就绪状态：可运行，由于其他进程处于运行状态而暂时停止运行
阻塞状态：该进程正在等待某一事件发生而暂时停止运行，此时即使给它CPU控制权，它也无法运行

进程还有另外两个基本状态：

创建状态：进程正在被创建时的状态
结束状态：进程正在从系统中消失时的状态

如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间，显然不是我们所希望的，比较物理内存空间是有限的，被阻塞状态的进程占用着物理内存就是一种浪费物理内存的行为

所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存

因此，就需要一个新的状态来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。这根阻塞状态不同，阻塞状态是等待某个事件的返回

挂起状态可以分为两种：

阻塞挂起状态：进程在外存（硬盘）中等待某个事件的出现
就绪挂起状态：进程在外存（硬盘），但只要进入内存，就能立刻运行

导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还有如下情况：

通过sleep让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程
用户希望挂起一个程序的执行，比如在Linux中用Ctrl+Z挂起进程

进程的控制结构

在操作系统中，用进程控制块（process control block，PCB）数据结构来描述进程的

PCB是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个PCB，如果进程消失了，那么PCB也会随之消失

PCB具体包含什么信息？

进程描述信息：
- 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符
- 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
进程控制和管理信息：
- 进程当前状态，如new、ready、running、waiting或blocked等
- 进程优先级：进程抢占CPU时的优先级
资源分配清单：
- 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的I/O设备信息
CPU相关信息：
- CPU中各个寄存器的值，当进程被切换时，CPU的状态信息都会被保存在相应的PCB中，以便进程重新执行时，能从断点处继续执行

每个PCB是如何组织的？

通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

进程的控制

创建进程

操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程的所拥有的资源，当子进程被终止时，其在父进程所继承的资源应当还给父进程。同时，终止父进程时同时也会终止其所有的子进程

注意：Linux操作系统对于终止有子进程的父进程，会把子进程交给1号进程接管。

创建进程的过程如下：
- 为新进程分配一个唯一的进程标识号，并申请一个空白的PCB，PCB是有限的，若申请失败则创建失败
- 为进程分配资源，此处如果资源不足，进程就会进入等待状态，以等待资源
- 初始化PCB
- 如果进程的调度队列能够接纳新进程，那就将进程插入到就绪队列中，等待被调度运行
终止进程

进程有3种终止方式：正常结束、异常结束以及外界干预（信号kill掉）

终止进程过程如下：
- 查找需要终止的进程的PCB
- 如果处于执行状态，则立即终止该进程的执行，然后将CPU资源分配给其他进程
- 如果其还有子进程，则应将其所有子进程终止
- 将该进程所拥有的全部资源都归还给父进程或操作系统
- 将其从PCB所在队列中删除
阻塞进程

当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒

阻塞进程的过程如下：
- 找到将要被阻塞进程标识号对应的PCB
- 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
- 将该PCB插入到阻塞队列中去
唤醒进程

进程由运行转变为阻塞状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的

如果某进程正在等待I/O时间，需要别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它

唤醒进程的过程如下：
- 在该事件的阻塞队列中找到相应进程的PCB
- 将其从阻塞队列中移出，并置为就绪状态
- 把该PCB插入到就绪队列中，等待调度程序调度
进程的阻塞和唤醒是一对功能相反的语句，如果某个进程调用了阻塞语句，则必有一个与之对应的唤醒语句

进程的上下文切换

各个进程之间是共享CPU资源的，在不同的时候进程之间需要切换，让不同进程可以在CPU执行，那么这样一个进程切换到另一个进程运行，称为进程的上下文切换

任务是交给CPU运行的，那么在每个任务运行期，CPU需要知道任务从哪里加载，又从哪里开始运行

所以，操作系统需要事先帮CPU设置好CPU寄存器和程序计数器

程序计数器是用来存储CPU正在执行的指令位置、或者即将执行的下一条指令位置

所以，CPU寄存器和程序计数器是CPU在运行任何任务前，所必须依赖的环境，这些环境叫做CPU上下文

CPU上下文切换就是先把前一个任务的CPU上下文保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务

根据任务的不同可以把CPU上下文切换分层：进程上下文切换、线程上下文切换、中断上下文切换

进程的上下文切换到底是切换什么？

进程是由内核管理和调度的，所以进程的切换只能发生在内核态

所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间资源，还包括了内核堆栈、寄存器等内核空间的资源

通常，会把交换的信息保存在进程的PCB，当要运行另外一个进程的时候，我们需要从这个进程的PCB取出上下文，然后恢复到CPU中，使得这个进程可以继续运行，如下图所示：

发生进程上下文切换有哪些场景？

线程

比进程更小的独立运行的基本单位

线程之间可以并发运行且共享相同的地址空间

线程是进程当中的一条执行流程

同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源。但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

线程的优点：

一个进程中可以同时存在多个线程
各个线程之间可以并发执行
各个线程之间可以共享地址空间和文件等资源

线程的缺点：

当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃

eg.对于游戏的用户设计，则不应该使用多线程的方式，否则一个用户挂了，会影响其他同个进程的线程

线程与进程的比较

线程与进程的比较如下：

进程是资源（包括内存、打开的文件等）分配的单位，线程是CPU调度的单位
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈
线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系
线程能减少并发执行的时间和空间开销

对于线程相比进程能减少开销，体现在：

线程的创建时间比进程快，因为进程在创建过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们
线程的终止时间比进程快，因为线程释放的资源相比进程少很多
同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的。
由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这使得线程之间的数据交互效率更高了

线程的上下文切换

线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位

所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源

对于线程和进程，可以这么理解：

当进程只有一个线程时，可以认为进程就等于线程
当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的

另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的

线程上下文切换的是什么？

这还得看线程是不是属于同一个进程

当两个线程不是属于同一个进程，则切换的过程就和进程上下文切换一样
当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据

所以，线程的上下文切换相比进程，开销要小很多

线程的实现

主要有三种线程的实现方式：

用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理
内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程
轻量级进程（LightWeight Proces）：在内核中来支持用户线程

用户线程和内核线程的对应关系：

多对一（多个用户线程对应同一个内核线程）：
一对一（一个用户线程对应一个内核线程）“
多对多（多个用户线程对应多个内核线程）：

用户线程如何理解？存在什么优势和缺陷？

用户线程是基于用户态的线程管理库来实现的，那么线程控制块（Thread Control Block，TCB）也是在库里面来实现的，对于操作系统而言是看不到这个TCB的，它只能看到整个进程的PCB

所以，用户线程的整个线程管理和调度，操作系统是不直接参与的，而是由用户级线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等

用户级线程的模型，也就类似于前面提到的多对一的关系，即多个用户线程对应同一个内核线程，如下图所示：

用户线程的优点：

每个进程都需要它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB由用户级线程库函数来维护，可用于不支持线程技术的操作系统
用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快

用户线程的缺点：

由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了
当一个线程开始运行后，除非它主动交出CPU使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的
由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢

内核线程如何理解？存在什么优势和缺陷？

内核线程是由操作系统管理的，线程对应的TCB自然是操作系统里，这样线程的创建、终止和管理都是由操作系统负责

内核线程的模型，类似一对一的关系，即一个用户线程对应一个内核线程

内核线程的优点：

在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行
分配给线程，多线程的进程获得更多的CPU运行时间

内核线程的缺点：

在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如PCB和TCB
线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大

如何理解轻量级进程？

轻量级进程（Light-weight process，LWP）是内核支持的用户线程，一个进程可有一个或多个LWP，每个LWP是跟内核线程一对一映射的，也就是LWP都是由一个内核线程支持

另外，LWP只能由内核管理并像普通进程一样被调度，Linux内核是支持LWP的典型例子

在大多数系统中，LWP与普通进程的区别也在于它只有一个最小执行上下文和调度程序所需的统计信息。一般来说，一个进程代表程序的一个实例，而LWP代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息，所以LWP也不带有这样的信息

在LWP之上也是可以使用用户线程的，那么LWP与用户的对应关系就有三种：

1:1，即一个LWP对应一个用户线程
N:1，即一个LWP对应多个用户线程
M:N，即多个LWP对应多个用户线程

LWP和用户线程可以是（1:1,N:1,M:N），但和内核线程只能是1:1

调度

进程都希望自己能够占用CPU进行工作，那么这涉及到前面说过的进程上下文切换

一旦操作系统把进程切换到运行状态，也就意味着该进程占用着CPU在执行，但是当操作系统把进程切换到其他状态时，那就不能在CPU中执行了，于是操作系统会选择下一个要运行的进程

选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序

调度时机

在进程的生命周期中，当进程从一个运行状态到另外一个状态变化的时候，其实会触发一次调度

调度原则

调度算法

单核CPU常见的调度算法

先来先服务调度算法

最短作业优先调度算法

高响应比优先调度算法

时间片轮转调度算法

最高优先级调度算法

多级反馈队列调度算法

多级反馈队列调度算法实例：

如果更高优先级的队列里来了新的进程，那么就中断当前进程去处理更高优先级的进程，但是优先级越高的队列处理时间也越短，所以也相对公平一些

4.2 进程间通信

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程，之间要通信必须通过内核。

管道

$ ps auxf | grep mysql

上面Linux命令行里的 | 竖线就是一个管道，它的功能是将前一个命令（ps auxf）的输出，作为后一个命令（grep mysql）的输入，从这功能描述，可以看出管道传输数据时单向的。如果向相互通信，需要创建两个管道才行。

同时，上面这种管道是没有名字的，所以 | 表示的管道成为匿名管道，用完了就销毁

管道还有另外一个类型是命名管道，也被叫做FIFO，因为数据是先进先出的传输方式

在使用命名管道前，先需要通过mkfifo命令来创建，并指定管道名字：

$ mkfifo myPipe

myPipe就是这个管道的名称，基于Linux一切皆文件的理念，所以管道也是以文件的方式存在，用ls查看，这个文件类型是p，也就是pipe（管道）的意思

$ ls -l
prw-r--r--  1 root Jomo    0 Jul 14 10:37 myPipe

接下来，往myPipe管道写入数据：

$ echo "hello" > myPipe #将hello写入myPipe
						#停住了

命令执行后就停在这了，因为管道里的内容没有被读取，只有管道里的数据被读取完了，命令才可以正常退出

于是，执行另外一个命令来读取管道里的内容：

$ cat < myPipe
hello

注意：

使用echo "hello" > myPipe将字符串"hello"写入管道后，如果立即使用cat < myPipe命令尝试读取管道内的内容，可能无法成功读出内容。

这是因为echo命令是立即执行的，它会将字符串写入管道后就立即完成任务并退出。而cat命令是在<重定向操作符的作用下，试图从管道中读取数据，如果此时cat命令还未开始执行，那么管道中可能还没有数据可以读取，所以cat命令无法读到任何内容。

为了确保cat命令能够读取到管道中的内容，你可以在执行echo "hello" > myPipe后，稍等一段时间，让cat命令开始执行后再去尝试读取管道，或者在一次终端会话中执行echo命令，另一次终端会话中再使用cat命令读取管道。这样就能够保证cat命令在echo命令完成写入操作后进行读取。

可以看出，管道这种通信方式效率低，不适合进程间频繁地交换数据，好处是简单，并且能够轻易地知道管道内的数据已经被另一个进程读取了

管道如何创建呢？背后原理是什么？

匿名管道的创建，需要使用下面这个系统调用：

int pipe(int fd[2])

这里表示创建一个匿名管道，并返回两个描述符，一个是管道的读取端描述符fd[0]，另一个是管道的写入端fd[1]。注意，这个匿名管道是特殊的文件，只存在于内存，不存在于文件系统中

其实，所谓的管道，实际上就是内核里面的一串缓存。从管道的一端写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限

这两个描述符都是在一个进程里面的，并没有起到进程间通信的作用，怎么样才能使得管道是跨过两个进程的呢？

可以使用fork创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各有两个fd[0]和fd[1]，两个进程就可以通过各自的fd写入和读取同一个管道文件实现跨进程通信了。

（拷贝的是读写端口，共享的是管道）

管道只能一端写入，另一端读出，所以上面这种模式容易造成混乱，因为父进程和子进程都可以同时写入，也都可以读出。为了避免这种情况，通常的做法是：

父进程关闭读取的fd[0]，只保留写入的fd[1]
子进程关闭写入的fd[1]，只保留读取的fd[0]

所以，如果需要双向通信，则应该创建两个管道

在shell里面执行 A | B命令的时候，A进程和B进程都是shell创建出来的子进程，A和B之间不存在父子关系，它两的父进程都是shell

所以说，在shell里通过 | 匿名管道将多个命令连接在一起，实际上也是创建了多个子进程，在编写shell脚本时，能使用一个管道搞定的事情，就不要多用一个管道，这样可以减少创建子进程的系统开销

对于匿名管道，它的通信范围是存在父子关系的进程。因为管道没有实体，也就是没有管道文件，只能通过fork来复制父进程fd文件描述符，来达到通信的目的

对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信

不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持lseek之类的文件定位操作

消息队列

管道的通信方式是低效的，因此管道不适合进程间频繁地交换数据

对于这个问题，消息队列的通信模式可以解决。比如，A进程要给B进程发送消息，A进程把数据放在对应的消息队列后就可以正常反悔了，B进程需要的时候再去读取数据就可以了。同理，B进程要给A进程发送消息也是如此

消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除

消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁

消息队列这种模型，两个进程之间的通信就像是平常发邮件一样，你来一封，我回一封，可以频繁沟通了

但是邮件的通信方式存在不足的地方两点，一是通信不及时，而是附近也有大小限制，这同样也是消息队列通信不足的点

消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。在Linux内核中，会有两个宏定义MSGMAX和MSGMNB，它们以字节为单位，分别定义了一条消息的最大长度和一个队列的最大长度

消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程

共享内存

消息队列的读取和写入的过程，都会发生用户态与内核态之间的消息拷贝过程。

现代操作系统，对于内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中。所以，即使进程A和进程B的虚拟地址是一样的，其实访问的是不同的物理地址空间，对于数据的增删改查互不影响

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，不需要拷贝来拷贝去，大大提高了进程间通信的速度

信号量

用了

共享内存通信方式，带来新的问题，就是如果多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了

为了防止多进程竞争共享资源，而造成的数据混乱，所以需要保护机制，使得共享的资源，在任意时刻只能被一个进程访问。正好，信号量就实现了这一保护机制

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据

信号量表示资源的数量，控制信号量的方式有两种原子操作：

P操作：这个操作会把信号量减去1，相减后如果信号量<0，表明资源已被占用，进程需阻塞等待；相减后如果信号量>=0，表明还有资源可用，进程可正常继续执行
V操作：这个操作会把信号量加1，相加后如果信号量<=0，表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后，如果信号量>0，则表明当前没有阻塞中的进程

P操作是用在进入共享资源之前，V操作是用在离开共享资源之后，这两个操作必须成对出现的

eg.如果要使得两个进程互斥访问共享内存，可以初始化信号量为1

信号量初始化为1，就代表着是互斥信号量，它可以保证共享内存存在任何时刻只有一个进程在访问，很好地保护了共享内存

另外，在多进程里，每个进程并不一定是顺序执行的它们基本是以各自独立的、不可预知的速度向前推进，但有时候又希望多个进程能密切合作，以实现一个共同的任务

例如，进程A是负责生产数据，而进程B是负责读取数据，这两个进程是相互合作、相互依赖的，进程A必须先生产了数据，进程B才能读取到数据，所以执行是有先后顺序的

信号

上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用信号的方式来通知进程

信号和信号量的用途完全不一样

运行在shell终端的进程，通过键盘输入某些组合键的时候，给进程发送信号。例如：

Ctrl+C产生SIGINT信号，表示终止该进程
Ctrl+Z产生SIGTSTP信号，表示停止该进程，但还未结束

如果进程在后台运行，可以通过kill命令的方式给进程发送信号，但前提是需要知道运行中的进程PID号

所以，信号事件的来源主要有硬件来源（如键盘Ctrl+C）和软件来源（如kill命令）

信号时进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式

执行默认操作。Linux对每种信号都规定了默认操作，例如，SIGTERM信号就是终止进程的意思
捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，就执行相应的信号处理函数
忽略信号。当我们不希望处理某些信号时，就可以忽略该信号，不作任何处理。有两个信号是应用进程无法捕捉和忽略的，即SIGKILL和SEGSTOP，它们用于在任何时候中断或结束某一进程

Socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，要想跨网络与不同主机上的进程之间通信，就需要Socket通信了

实际上，Socket通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信

创建socket的系统调用：

int socket(int domain,int type,int protocal)

三个参数分别代表：

domain参数用来指定协议族，比如AF_INET用于IPV4、AF_INET6用于IPV6、AF_LOCAL/AF_UNIX用于本机
type参数用来知道通信特性，比如SOCK_STREAM表示的是字节流，对应TCP、SOCK_DGRAM表示的是数据报，对应UDP、SOCK_RAW表示的是原始套接字
protocal参数原本是用来指定通信协议的，但现在基本报废。因为协议已经通过前面两个参数指定完成，protocal目前一般写成0即可

根据创建socket类型的不同，通信的方式也就不同：

实现TCP字节流通信：socket类型是AF_INET和SOCK_STREAM
实现UDP数据报通信：socket类型是AF_INET和SOCK_DGRAM
实现本地进程间通信：本地字节流socket类型是AF_LOCAL和SOCK_STREAM，本地数据报socket类型是AF_LOCAL和SOCK_DFRAM。另外，AF_UNIX和AF_LOCAL是等价的，所以AF_UNIX也属于本地socket

针对TCP协议通信的socke编程模型

服务端调用accept时，连接成功了会返回一个已完成连接的socket，后续用来传输数据

所以，监听的socket和真正用来传送数据的socket，是两个socket，一个叫作监听socket，一个叫作已完成连接socket

成功连接建立之后，双方开始通过read和write函数来读写数据，就像往一个文件流里面写东西一样

针对UDP协议通信的socket编程模型

UDP是没有连接的，所以不需要三次握手，也就不需要像TCP调用listen和connect，但是UDP的交互仍然需要IP地址和端口号，因此也需要bind

对于UDP来说，不需要维护连接，那么也就没有所谓的发送方和接收方，甚至都不存在客户端和服务端的概念，只要有一个socket多台机器就可以任意通信，因此每一个UDP的socket都需要bind

另外，每次通信时，调用sendto和recvfrom，都要传入目标主机的IP地址和端口

针对本地进程间通信的socket编程模型

本地socket被用于在同一台主机上进程间通信的场景：

本地socket的编程接口和IPV4、IPV6套接字编程接口是一致的，可以支持字节流和数据报两种协议
本地socket的实现效率大大高于IPV4和IPV6的字节流、数据报socket实现

对于本地字节流socket，其socket类型是AF_LOCAL和SOCK_STREAM

对于本地数据报socket，其socket类型是AF_LOCAL和SOCK_DGRAM

本地字节流socket和本地数据报socket在bind的时候，不像TCP和UDP要绑定IP地址和端口，而是绑定一个本地文件，这也是它们之间最大的区别

总结

匿名管道是特殊文件只存在于内存，没有存在于文件系统中，通信的数据是无格式的流并且大小受限，方向是单向的，如果需要双向通信，需要创建两个管道，且匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失
命名管道突破了匿名管道只能在亲缘关系进程间的同信限制
消息队列克服了管道通信的数据是无格式的字节流的问题
共享内存可以解决消息队列中用户态和内核态之间数据拷贝过程带来的开销
信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源
信号是进程间通信机制中唯一的异步通信机制
Socket用于不同主机进程间通信，也可以用于本地主机进程间通信

同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步：

互斥：保证任意时刻只有一个线程访问共享资源
同步：保证线程A应在线程B之前执行（A先写，B后读）

4.3 多线程同步

竞争与协作

线程是调度的基本单位，进程是资源分配的基本单位

线程之间是可以共享进程的资源，比如代码段、堆空间、数据段、打开的文件等资源，但每个线程都有自己独立的栈空间

多个线程共享资源，如果不采取有效措施，就会造成共享数据的混乱

eg.创建两个线程，分别对共享变量 i 自增 1 执行 10000 次

#include<iostream>//std::cout
#include<thread>  //std::thread

int i = 0;		  //共享数据

//线程函数：对共享变量 i 自增 1 执行 10000 次
void test() {
	for (int n = 0; n < 10000; n++) {
		i++;
	}
}

int main(void) {
	std::cout << "Start all threads." << std::endl;

	//创建线程
	std::thread thread_test1(test);
	std::thread thread_test2(test);

	//等待线程执行完成
	thread_test1.join();
	thread_test2.join();

	std::cout << "All threads joined." << std::endl;
	std::cout << "now i is" << i << std::endl;

	return 0;
}

按理来说，i变量最后的值应该是20000，但实际情况是可能会出现20000，也可能会出现其他值的情况

每次运行不但会产生错误，而且得到不同的结果，在计算机里是不能容忍的

为什么会发生这种情况？

互斥的概念

上面的情况称为竞争条件，当多线程相互竞争操作共享变量时，由于运气不好，在执行过程中发生了上下文切换，得到了错误的结果，事实上，每次运行都可能得到不同的结果，因此输出的结果存在不确定性

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此将此段代码称为临界区，它是访问共享资源的代码片段，一定不能给多线程同时执行

我们希望这段代码是互斥的，也就是保证一个线程在临界区执行时，其他线程应该被阻止进入临界区，换句话说，这段代码执行过程中，最多只能出现一个线程

互斥并不是只针对多线程。在多进程竞争共享资源时，也同样是可以使用互斥的方式来避免资源竞争造成的资源混乱

同步的概念

互斥解决了并发进程/线程对临界区的使用问题。这种基于临界区控制的交互作用是比较简单的，只要一个进程/线程进入了临界区，其他试图进入临界区的进程/线程都会被阻塞，直到第一个进程/线程离开了临界区

在多线程里，每个线程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个线程能够密切合作，以实现一个共同的任务

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步

注意，同步与互斥是两张不同的概念：

同步：操作A应在操作B之前执行，操作C必须在操作A和操作B都完成之后才能执行
互斥：操作A和操作B不能在同一时刻执行

互斥与同步的实现和使用

在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系

为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种：

锁：加锁、解锁操作
信号量：P、V操作

这两个都可以方便地实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以方便地实现进程/线程同步

锁

使用加锁和解锁操作可以解决并发线程/进程的互斥问题

任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可以进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源

根据锁的实现不同，可以分为忙等待锁和无等待锁

忙等待锁的实现

现代CPU体系结构提供的特殊原子操作指令——测试和置位（Test-and-Set）指令

如果用C代码表示Test-and-Set指令，形式如下：

关键是这些代码是原子执行。因为既可以测试旧值，又可以设置新值，所以把这条指令叫作测试并设置

原子操作：原子操作就是要么全部执行，要么都不执行，不能出现执行到一半的中间状态

可以运用Test-and-Set指令来实现忙等待锁，代码如下：

无等待锁的实现

无等待锁获取不到锁时，不用自旋

当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把CPU让给其他线程执行

信号量

信号量是操作系统提供的一种协调共享资源访问的方法

通常信号量表示资源的数量，对应的变量是一个整型(sem)变量

操作系统是如何实现PV操作的？

PV操作的函数是由操作系统管理和实现的，所以操作系统已经使得执行PV函数时是具有原子性的

PV操作如何使用的呢？

使用信号量实现临界区的互斥访问：

为每类共享资源设置一个信号量s，初始值为1，表示该资源未被占用

只要把进入临界区的操作置于P(s)和V(s)之间，即可实现进程/线程互斥

使用信号量实现事件同步：

同步的方式是设置一个信号量，其初值为0

生产者—消费者问题

经典同步问题

哲学家就餐问题

如何保证哲学家们的动作有序进行，而不会出现有人永远拿不到叉子呢？

方案一

方案二

方案三

方案四

读者—写者问题

哲学家进餐问题对于互斥访问有限的竞争问题（如I/O设备）类的建模过程十分有用

读者—写者问题为数据库访问建立了一个模型

方案一

rCount也是共享变量，所以需要一个锁rCountMutex去互斥rCount的修改

方案二

因为写者之间的写操作需要互斥，所以相比于读者优先策略，写者在write前需要先申请锁，然后write后释放锁，这样做还有一个原因是需要等所有读者读完之后，rCount==0时，V(wDataMutes)唤醒写者的写操作

方案三

为什么加了一个信号量flag，就实现了公平竞争？

在方案一读者优先策略中，只要有读者来了就进入读者队列，直到读者队列为空时，写者才可以进入临界区执行写操作

而这里的flag就是阻止读者的这种特殊权限（只要读者到达，就可以进入读者队列）

阻止的方式：读者队列还没空时，此时来了一个写者，执行了P(flag)操作，后续如果又来了一些读者，它们会阻塞在P(flag)这步上，因此不会进入读者队列。而写者也不能立马写（阻塞在P(wDataMutex)），因为读者队列还没有空，等到读者队列为空时，读者执行V(wDataMutex)唤醒写者写操作

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

操作系统(小林coding).md

操作系统(小林coding).md

操作系统(小林coding)

一、硬件结构

1.1 CPU是如何执行程序的？

1.2 存储器金字塔

1.3 如何写出让CPU跑得更快的代码？

1.4 CPU缓存一致性

1.5 CPU是如何执行任务的

1.6 软中断

1.7 为什么0.1+0.2不等于0.3？

二、操作系统结构

2.1 Linux内核 vs Windows内核

三、内存管理

3.1 为什么要有虚拟内存？

3.2 malloc是如何分配内存的？

3.3 内存满了，会发生什么？

3.4 在4GB物理内存的机器上，申请8G内存会怎么样？

3.5 如何避免预读失效和缓存污染的问题？

3.6 深入理解Linux虚拟内存管理

3.7 深入理解Linux物理内存管理

四、进程与线程

4.1 进程、线程基础知识

4.2 进程间通信

4.3 多线程同步

Files

操作系统(小林coding).md

Latest commit

History

操作系统(小林coding).md

File metadata and controls

操作系统(小林coding)

一、硬件结构

1.1 CPU是如何执行程序的？

1.2 存储器金字塔

1.3 如何写出让CPU跑得更快的代码？

1.4 CPU缓存一致性

1.5 CPU是如何执行任务的

1.6 软中断

1.7 为什么0.1+0.2不等于0.3？

二、操作系统结构

2.1 Linux内核 vs Windows内核

三、内存管理

3.1 为什么要有虚拟内存？

3.2 malloc是如何分配内存的？

3.3 内存满了，会发生什么？

3.4 在4GB物理内存的机器上，申请8G内存会怎么样？

3.5 如何避免预读失效和缓存污染的问题？

3.6 深入理解Linux虚拟内存管理

3.7 深入理解Linux物理内存管理

四、进程与线程

4.1 进程、线程基础知识

4.2 进程间通信

4.3 多线程同步