当前位置：首页 > news >正文

计算机操作系统知识集合

news 2025/5/2 6:35:00

主要来自小林coding

硬件结构

cpu位宽

如果用 32 位 CPU 去加和两个 64 位大小的数字，就需要把这 2 个 64 位的数字分成 2 个低位 32 位数字和 2 个高位 32 位数字来计算，先加个两个低位的 32 位数字，算出进位，然后加和两个高位的 32 位数字，最后再加上进位，就能算出结果了，可以发现 32 位 CPU 并不能一次性计算出加和两个 64 位数字的结果。

对于 64 位 CPU 就可以一次性算出加和两个 64 位数字的结果，因为 64 位 CPU 可以一次读入 64 位的数字，并且 64 位 CPU 内部的逻辑运算单元也支持 64 位数字的计算。

但是并不代表 64 位 CPU 性能比 32 位 CPU 高很多，很少应用需要算超过 32 位的数字，所以如果计算的数额不超过 32 位数字的情况下，32 位和 64 位 CPU 之间没什么区别的，只有当计算超过 32 位数字的情况下，64 位的优势才能体现出来。

另外，32 位 CPU 最大只能操作 4GB 内存，就算你装了 8 GB 内存条，也没用。而 64 位 CPU 寻址范围则很大，理论最大的寻址空间为 2^64。

存储器分层

寄存器和cache

我们可以把 CPU 比喻成我们的大脑，大脑正在思考的东西，就好比 CPU 中的寄存器，处理速度是最快的，但是能存储的数据也是最少的，毕竟我们也不能一下同时思考太多的事情，除非你练过。

我们大脑中的记忆，就好比 CPU Cache，中文称为 CPU 高速缓存，处理速度相比寄存器慢了一点，但是能存储的数据也稍微多了一些。

CPU Cache 通常会分为 L1、L2、L3 三层，其中 L1 Cache 通常分成「数据缓存」和「指令缓存」，L1 是距离 CPU 最近的，因此它比 L2、L3 的读写速度都快、存储空间都小。我们大脑中短期记忆，就好比 L1 Cache，而长期记忆就好比 L2/L3 Cache。

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

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

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

CPU 的高速缓存，通常可以分为 L1、L2、L3 这样的三层高速缓存，也称为一级缓存、二级缓存、三级缓存。

寄存器和 CPU Cache 都是在 CPU 内部，跟 CPU 挨着很近，因此它们的读写速度都相当的快，但是能存储的数据很少，毕竟 CPU 就这么丁点大。
在这里插入图片描述
寄存器的访问速度非常快，一般要求在半个 CPU 时钟周期内完成读写，CPU 时钟周期跟 CPU 主频息息相关，比如 2 GHz 主频的 CPU，那么它的时钟周期就是 1/2G，也就是 0.5ns（纳秒）。

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

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

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

L3 高速缓存通常是多个 CPU 核心共用的，位置比 L2 高速缓存距离 CPU 核心更远，大小也会更大些，通常大小在几 MB 到几十 MB 不等，具体值根据 CPU 型号而定。

访问速度相对也比较慢一些，访问速度在 20~60个时钟周期。

我们执行一条命令，实际上在寄存器中是这样的：
在这里插入图片描述

内存

内存用的芯片和 CPU Cache 有所不同，它使用的是一种叫作 DRAM （Dynamic Random Access Memory，动态随机存取存储器）的芯片。

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

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

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

如何写出让cpu跑的更快的代码

CPU Cache 的数据是从内存中读取过来的，它是以一小块一小块读取数据的，而不是按照单个数组元素来读取数据的，在 CPU Cache 中的，这样一小块一小块的数据，称为 Cache Line（缓存块）。
你可以在你的 Linux 系统，用下面这种方式来查看 CPU 的 Cache Line，你可以看我服务器的 L1 Cache Line 大小是 64 字节，也就意味着 L1 Cache 一次载入数据的大小是 64 字节。
比如，有一个 int array[100] 的数组，当载入 array[0] 时，由于这个数组元素的大小在内存只占 4 字节，不足 64 字节，CPU 就会顺序加载数组元素到 array[15]，意味着 array[0]~array[15] 数组元素都会被缓存在 CPU Cache 中了，因此当下次访问这些数组元素时，会直接从 CPU Cache 读取，而不用再从内存中读取，大大提高了 CPU 读取数据的性能。

如何提升数据缓存的命中率？

假设要遍历二维数组，有以下两种形式，虽然代码执行结果是一样，但你觉得哪种形式效率最高呢？为什么高呢？
在这里插入图片描述
经过测试，形式一 array[i][j] 执行时间比形式二 array[j][i] 快好几倍。

之所以有这么大的差距，是因为二维数组 array 所占用的内存是连续的，比如长度 N 的值是 2 的话，那么内存中的数组元素的布局顺序是这样的：
在这里插入图片描述
形式一用 array[i][j] 访问数组元素的顺序，正是和内存中数组元素存放的顺序一致。当 CPU 访问 array[0][0] 时，由于该数据不在 Cache 中，于是会「顺序」把跟随其后的 3 个元素从内存中加载到 CPU Cache，这样当 CPU 访问后面的 3 个数组元素时，就能在 CPU Cache 中成功地找到数据，这意味着缓存命中率很高，缓存命中的数据不需要访问内存，这便大大提高了代码的性能。

而如果用形式二的 array[j][i] 来访问，则访问的顺序就是：
在这里插入图片描述
你可以看到，访问的方式跳跃式的，而不是顺序的，那么如果 N 的数值很大，那么操作 array[j][i] 时，是没办法把 array[j+1][i] 也读入到 CPU Cache 中的，既然 array[j+1][i] 没有读取到 CPU Cache，那么就需要从内存读取该数据元素了。很明显，这种不连续性、跳跃式访问数据元素的方式，可能不能充分利用到了 CPU Cache 的特性，从而代码的性能不高。

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

提升数据的缓存命中率的方式，是按照内存布局顺序访问，那针对指令的缓存该如何提升呢？

我们以一个例子来看看，有一个元素为 0 到 100 之间随机数字组成的一维数组：
在这里插入图片描述
接下来，对这个数组做两个操作：

第一个操作，循环遍历数组，把小于 50 的数组元素置为 0；
第二个操作，将数组排序；
那么问题来了，你觉得先遍历再排序速度快，还是先排序再遍历速度快呢？

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

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

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

如果你肯定代码中的 if 中的表达式判断为 true 的概率比较高，我们可以使用显示分支预测工具，比如在 C/C++ 语言中编译器提供了 likely 和 unlikely 这两种宏，如果 if 条件为 ture 的概率大，则可以用 likely 宏把 if 里的表达式包裹起来，反之用 unlikely 宏。
在这里插入图片描述
实际上，CPU 自身的动态分支预测已经是比较准的了，所以只有当非常确信 CPU 预测的不准，且能够知道实际的概率情况时，才建议使用这两种宏。

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

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

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

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

在 Linux 上提供了 sched_setaffinity 方法，来实现将线程绑定到某个 CPU 核心这一功能。

CPU 缓存一致性

小林里面内容比较多以后用到再看吧

需要注意的是
写直达保持内存与 Cache 一致性最简单的方式是，把数据同时写入内存和 Cache 中，这种方法称为写直达（Write Through）。
既然写直达由于每次写操作都会把数据写回到内存，而导致影响性能，于是为了要减少数据写回内存的频率，就出现了写回（Write Back）的方法。

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

中断是什么？

先来看看什么是中断？在计算机中，中断是系统用来响应硬件设备请求的一种机制，操作系统收到硬件的中断请求，会打断正在执行的进程，然后调用内核中的中断处理程序来响应请求。

这样的解释可能过于学术了，容易云里雾里，我就举个生活中取外卖的例子。

小林中午搬完砖，肚子饿了，点了份白切鸡外卖，这次我带闪了，没有被某团大数据杀熟。虽然平台上会显示配送进度，但是我也不能一直傻傻地盯着呀，时间很宝贵，当然得去干别的事情，等外卖到了配送员会通过「电话」通知我，电话响了，我就会停下手中地事情，去拿外卖。

这里的打电话，其实就是对应计算机里的中断，没接到电话的时候，我可以做其他的事情，只有接到了电话，也就是发生中断，我才会停下当前的事情，去进行另一个事情，也就是拿外卖。

从这个例子，我们可以知道，中断是一种异步的事件处理机制，可以提高系统的并发处理能力。

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

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

还是回到外卖的例子，小林到了晚上又点起了外卖，这次为了犒劳自己，共点了两份外卖，一份小龙虾和一份奶茶，并且是由不同地配送员来配送，那么问题来了，当第一份外卖送到时，配送员给我打了长长的电话，说了一些杂七杂八的事情，比如给个好评等等，但如果这时另一位配送员也想给我打电话。

很明显，这时第二位配送员因为我在通话中（相当于关闭了中断响应），自然就无法打通我的电话，他可能尝试了几次后就走掉了（相当于丢失了一次中断）。

#什么是软中断？
前面我们也提到了，中断请求的处理程序应该要短且快，这样才能减少对正常进程运行调度地影响，而且中断处理程序可能会暂时关闭中断，这时如果中断处理程序执行时间过长，可能在还未执行完中断处理程序前，会丢失当前其他设备的中断请求。

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

上半部用来快速处理中断，一般会暂时关闭中断请求，主要负责处理跟硬件紧密相关或者时间敏感的事情。
下半部用来延迟处理上半部未完成的工作，一般以「内核线程」的方式运行。
前面的外卖例子，由于第一个配送员长时间跟我通话，则导致第二位配送员无法拨通我的电话，其实当我接到第一位配送员的电话，可以告诉配送员说我现在下楼，剩下的事情，等我们见面再说（上半部），然后就可以挂断电话，到楼下后，在拿外卖，以及跟配送员说其他的事情（下半部）。

这样，第一位配送员就不会占用我手机太多时间，当第二位配送员正好过来时，会有很大几率拨通我的电话。

再举一个计算机中的例子，常见的网卡接收网络包的例子。

网卡收到网络包后，通过 DMA 方式将接收到的数据写入内存，接着会通过硬件中断通知内核有新的数据到了，于是内核就会调用对应的中断处理程序来处理该事件，这个事件的处理也是会分成上半部和下半部。

上部分要做的事情很少，会先禁止网卡中断，避免频繁硬中断，而降低内核的工作效率。接着，内核会触发一个软中断，把一些处理比较耗时且复杂的事情，交给「软中断处理程序」去做，也就是中断的下半部，其主要是需要从内存中找到网络数据，再按照网络协议栈，对网络数据进行逐层解析和处理，最后把数据送给应用程序。

所以，中断处理程序的上部分和下半部可以理解为：

上半部直接处理硬件请求，也就是硬中断，主要是负责耗时短的工作，特点是快速执行；
下半部是由内核触发，也就说软中断，主要是负责上半部未完成的工作，通常都是耗时比较长的事情，特点是延迟执行；
还有一个区别，硬中断（上半部）是会打断 CPU 正在执行的任务，然后立即执行中断处理程序，而软中断（下半部）是以内核线程的方式执行，并且每一个 CPU 都对应一个软中断内核线程，名字通常为「ksoftirqd/CPU 编号」，比如 0 号 CPU 对应的软中断内核线程的名字是 ksoftirqd/0

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

为什么 0.1 + 0.2 不等于 0.3 ？

补码

如果负数不是使用补码的方式表示，则在做基本对加减法运算的时候，还需要多一步操作来判断是否为负数，如果为负数，还得把加法反转成减法，或者把减法反转成加法，这就非常不好了，毕竟加减法运算在计算机里是很常使用的，所以为了性能考虑，应该要尽量简化这个运算过程。

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

精度

在计算机中 0.1 + 0.2 并不等于完整的 0.3。

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

我们二进制只能精准表达 2 除尽的数字 1/2, 1/4, 1/8，但是对于 0.1(1/10) 和 0.2(1/5)，在二进制中都无法精准表示时，需要根据精度舍入。

我们人类熟悉的十进制运算系统，可以精准表达 2 和 5 除尽的数字，例如 1/2, 1/4, 1/5(0.2), 1/8, 1/10(0.1)。

当然，十进制也有无法除u尽的地方，例如 1/3, 1/7，也需要根据精度舍入。

内核结构

对于内核的架构一般有这三种类型:
宏内核，包含多个模块，整个内核像一个完整的程序;
微内核，有一个最小版本的内核，一些模块和服务则由用户态管理;。
混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的
内核，其他模块就在这个基础上搭建，整个内核是个完整的程序:
Linux 的内核设计是采用了宏内核，Window 的内核设计则是采用了混合内核。
这两个操作系统的可执行文件格式也不一样， Linux 可执行文件格式叫作 ELF，Windows 可执行文件格式叫作 PE。

内存管理

为什么要有虚拟内存

是什么

如果你是电子相关专业的，肯定在大学里捣鼓过单片机。

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

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

在这里插入图片描述

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

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

这里关键的问题是这两个程序都引用了绝对物理地址，而这正是我们最需要避免的。

我们可以把进程所使用的地址「隔离」开来，即让操作系统为每个进程分配独立的一套「虚拟地址」，人人都有，大家自己玩自己的地址就行，互不干涉。但是有个前提每个进程都不能访问物理地址，至于虚拟地址最终怎么落到物理内存里，对进程来说是透明的，操作系统已经把这些都安排的明明白白了。

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

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

虚拟内存的作用:

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

内存分配管理

程序员阿沛写的比小林好，主要来自阿沛
https://mp.weixin.qq.com/s?__biz=MzUxMjczODMyMA==&mid=2247484085&idx=1&sn=ead5eb84f73b2260437eb21650509241&chksm=f8bda2f4d9572c3b05cc05f3bd864f57bba41d11826f92bb6ad36a80ab28210259f7cc5dbe99&mpshare=1&scene=24&srcid=0501FQLJ9FombY8gSMZTXYm5&sharer_shareinfo=c31674ae5ee2fe805e76ca9a9b932af5&sharer_shareinfo_first=c31674ae5ee2fe805e76ca9a9b932af5#rd

存在的问题

内存碎片分外部碎片和内部碎片后面会讲

内存的连续分配管理

连续分配是指，整个进程在物理内存中是连续存储的，分配给进程的内存空间是连续的内存空间。连续分配策略分为单一连续分配、固定分区分配和动态分区分配3种。

单一连续分配是指将内存中整个用户区空间分配给1个用户程序，无需对用户区再分区，内存中只能有一道用户程序，用户程序独占整个用户区空间。
固定分区分配是指在进程装入内存之前，就将整个用户区分为多个分区，进程装入内存时选择一个大小大于等于该进程所需内存的分区给该进程。
动态分区分配：进程装入内存时才对内存分区，分区的大小就是进程所需的所有内存大小。

固定分区分配和动态分区分配都是一个进程只能占用一个分区，不能占用多个分区。

单一连续分配

单一连续分配是指将内存中整个用户区空间分配给1个用户程序，无需对用户区再分区，内存中只能有一道用户程序，用户程序独占整个用户区空间。

在这里插入图片描述

优点：

实现简单；

无外部碎片；

如果用户区内存不足以装下整个进程，可以采用覆盖技术扩充内存；

不一定需要采取内存保护。

缺点：

内存只装入一个进程的信息，内部碎片可能极大，内存利用率极低。

无法实现进程并发，并发率低。

固定分区分配

固定分区分配是指整个用户空间划分为若干个大小固定的分区，每个分区中只装入一道作业，进程装入内存时选择一个大小大于等于该进程所需内存的分区给该进程。

按照分区大小是否相等，又有两种分法：
在这里插入图片描述
固定分区分配如何实现内存分配和回收？

操作系统需要建立一个分区分配表的数据结构，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。可以使用数组或者链表在逻辑上实现这个分区分配表。

在这里插入图片描述
优点：实现简单，无外部碎片。

缺点：

a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；

b. 会产生大量内部碎片，内存利用率低。

c.难以合理预先划分分区, 分区个数划分少了意味着物理内存中能装入的进程个数少了，降低并发度。分区个数划分多了，每个分区大小就小了，就会造成大进程无法装下任何一个分区。

动态分区分配

这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此动态分区的大小是不固定的。

在这里插入图片描述
动态分区分配可以使用空闲分区表或者空闲分区链管理，表项中包含分区号、分区大小、分区起始地址等信息。

如果回收分区的时候，待回收的分区和其他空闲分区相连，需要合并这些分区的表项为一个表项。

动态分区分配的过程如下图所示，在一开始给多个进程分配分区时，这些进程在内存中是紧挨着的，随着多次回收和分配，进程在内存中会变成离散分布，并可能出现大量外部碎片。动态分区不会产生内部碎片，因为每个分区大小都等于该进程所需内存大小。
在这里插入图片描述

此时可以用紧凑技术解决，将离散的进程变成在内存中紧密相连。

紧凑技术是指将所有进程占用的分区移动到一端使其紧凑的挨在一起，空闲区留在另一端。如下图所示，原本所有碎片分区都容纳不下进程5，但移动后所有碎片分区相邻融合为一个连续的空闲区就能放下进程5：
在这里插入图片描述

紧凑技术要将进程在内存中的物理位置“搬家”，因此需要在分区表对所有进程与地址有关的项修改，例如基址寄存器、程序计数器等，还会造成内存数据大量拷贝。因此紧凑会花费大量CPU时间。

紧缩的时机：当所有空闲分区的大小不满足要装入内存的进程大小时发生。

动态分区的优点：

分区大小可变，进程在内存的起始位置可变，空闲分区可合并，更灵活，内存利用率更高；

无内部碎片；

缺点：

有外部碎片，外部碎片过多就可能触发“紧凑”，导致系统开销变大；

一个进程需要占用连续的内存空间，相比于离散分配而言，内存利用率低，这点是静态分区和单一连续分配都有的问题，而离散分区管理可以解决该问题；

动态分区分配算法

动态分区分配算法研究的是，内存中有空闲分区时，动态分区分配法优先选择哪个分区给进程。动态分区算法分为首次适应算法、最佳适应算法、最坏适应算法和邻近适应算法。

首次适应算法

从低地址开始查找分区，找到第一个能满足待装入进程大小的空闲分区。

如何实现：空闲分区在空闲分区链中以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

缺点：低地址空闲区会产生很多外部碎片，查找空闲区链表时会重复遍历低地址的外部碎片分区，增加了查找的开销。

最佳适应算法

从所有空闲分区中选择满足待装入进程大小的最小空闲分区，目的是预留大分区给大进程。

如何实现：空闲分区在空闲分区链中按容量递增次序排序。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
在这里插入图片描述
缺点：每次都选最小的分区进行分配，会留下越来越多的、小到难以利用的外部碎片。

最坏适应法

从所有空闲分区中选择满足待装入进程大小的最大空闲分区。目的是尽可能避免生成外部碎片。

如何实现：空闲分区在空闲分区链中按容量降序排序实现。
在这里插入图片描述

缺点：每次都选最大的分区进行分配，可以让分配后留下的空闲区更大，避免外部碎片。但是会导致较大的连续空闲区被迅速用完，“大进程”到达就没有内存分区可用了。

邻近适应算法

该算法按照首次适应算法的逻辑查找，但下次查找按上次查找结束的位置开始检索，目的是解决首次适应算法查找时间递增的缺点。

如何实现：空闲分区在空闲分区链中以地址递增的顺序排列，排成一个循环链表。使用一个头指针指向上次分配内存时查找结束的位置，下次从该位置开始查找空闲分区链，找到大小能满足要求的第一个空闲分区。

在这里插入图片描述

缺点：进程装入时，头指针之前的空闲分区（低地址的分区）即使有足够空间分配给该进程，系统还是会选择头指针之后的空闲分区来分配。因此该算法会导致高地址和低地址分区可无大分区可用。

四种算法中，首次适应算法的效果反而最好。首次适应算法和邻近适应算法的优点是分配分区后，无需移动链表节点，而最佳适应和最坏适应算法则需要移动链表节点。邻近适应算法的查找效率最高。

在这里插入图片描述

连续分配的方式分配内存的最大缺点在于会产生很多内存碎片，内存利用率低，而产生很多内存碎片的根本原因在于必须为进程分配连续的内存空间，虽然可以通过紧凑技术解决，但是需要花费很多CPU时间。

为什么连续存储会造成很多内存碎片？

因为对于较大的进程，系统要挑选大块的空闲空间给进程，而很小块的空闲空间可能连较小的进程都无法容纳而永远无法被利用，就变成了内存碎片。进程换入和换出的次数多了之后就会产生很多碎片。

离散分配则允许为进程分配分散的内存块，即一个进程可以分布在不相邻的多个小分区中。离散分配管理分为分页存储、分段存储和段页式存储3种。

内存的离散分配管理

页式存储

页式存储又称分页存储，是指在物理上将内存空间分为多个大小相等的物理块（又叫内存块），在逻辑上将进程的逻辑地址空间分为多个页面（又叫逻辑页），每个页面和物理块一样大。

操作系统分配与进程占用页面数量相同的物理块给该进程，该进程的页面可以离散的存放在内存的块中，与内存块一一对应，每个进程会维护一个逻辑页和物理块映射关系的页表。

在这里插入图片描述

页面是逻辑空间单位，块是物理空间单位。页面的编号叫页号，内存块的编号叫块号，编号和页号都是从0开始。页面大小由硬件决定，一般为2的若干次幂，有些是512B，有些是4K等，不同机器的页面大小不同。

逻辑地址的构成

一个逻辑地址可能是32位或者64位。一般来说，32位的逻辑地址的前 20 位就是页号，后12位就是页内偏移，也就是说逻辑地址是由页号和页内偏移组成的。这里有个通用的结论：页面大小是 2 ^ k 情况下，页号是逻辑地址的前 32 - k 位，页内偏移是逻辑地址的末尾 k 位。

在这里插入图片描述
页号P表示这个逻辑地址位于逻辑空间的第几个页，页内偏移W表示这个逻辑地址位于页面的第几个字节。

分页存储如何实现地址转换

分页存储采用动态重定位，即装入时不进行地址转换，运行指令时才进行地址转换。指令中的地址是逻辑地址。逻辑地址转为物理地址的过程如下：

在这里插入图片描述

例如，程序中某个数据的逻辑地址L为80，页面大小p为50，页号块号映射关系为块号数 = 页号数+10，求物理地址（这里为了方便计算所以用公式表示映射关系，实际上页号与块号的映射关系需要查询页表得出）。

页号P = floor(80 / 50) = 1

页内偏移i = 80 % 50 = 30

块号B = 1 + 10 = 11

物理地址S = 11 * 50 + 30 = 580

页表

页表是操作系统为每个进程创建的进程页号与内存块号的映射关系表。

进程的页表保存在内存中，而页表在内存的指针存在PCB内。

在这里插入图片描述

需要注意：

一个进程都有属于自己的页表，进程的每个页面对应一个页表项，每个页表项的大小是相同的。
每个页表项由“页号”和“块号”组成，但页号是“隐含”的，不占存储空间，页表实际只保存了块号。
如果不采用多级页表，则一个页表是连续存放在内存中的。

一个页表项的大小取决于内存最多有多少个物理块。

假设某系统物理内存大小为 4GB，页面大小为 4KB，则 4GB 的内存总共会被切分为 40G / 4K = 2^32 / 2^12 = 2^20个内存块，因此内存块号的范围应该是 0 ~ 2^20 -1，内存块号至少要用 20 bit 来表示，即页表项至少需要3B的大小才能保存下最大的块号（3*8=24bit）

基本地址变换机构

基本地址变换机构是帮助系统将逻辑地址转换为物理地址的硬件设施。这些硬件中最重要的是页表寄存器（PTR）。页表寄存器存放页表在内存中的起始地址F 和页表长度（页表项个数）M。

进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们load到页表寄存器中。下图是CPU将程序计数器中指令的逻辑地址转为物理地址的过程。

在这里插入图片描述

从上面的过程中我们注意两点：

1、页式管理的地址是一维的，因为只需向系统提供一个逻辑地址系统就能算出物理地址。

2、CPU根据逻辑地址访问某个指令或数据时会发生2次内存IO，一次是根据页号+页表地址查页表，一次是实际访问目标指令或数据。

为了让CPU根据逻辑地址寻址可以更快，计算机会使用一种叫快表的硬件把访问过的页表项缓存到CPU中，如果下次根据页号命中快表中的页表项，则可以避免查页表的过程，减少1次内存IO。

在介绍快表之前需要先介绍局部性原理，局部性原理分为时间局部性和空间局部性。

局部性原理

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能会再次被执行；如果某个数据被访问过，不久之后该数据很可能会再次被访问。（典型的例子就是循环）

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。

时间局部性强调对同一个指令或数据的重复访问。空间局部性强调对邻近指令或数据的访问。

例如下面这段代码：

int i = 0;
int a[100];
while(i < 100){
a[i] = i;
i++;
}

while代码块内的重复执行就是时间局部性的体现，会重复访问相同的指令和 i 这个数据；数组a的访问就是空间局部性的体现，a[0_{99]是连续存储的，对a[0]}a[99]的访问很可能是访问同一个页面。

快表 TLB

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。
程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。
我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer），通常称为页表缓存、转址旁路缓存、快表等。

快表（TLB）本质上是一种被称为联想寄存器的硬件，用来缓存CPU最近访问过的若干个页表项，可以加快地址转换的速度。访问快表的速度远高于访问内存的速度。

根据时间和空间局部性，CPU根据逻辑地址查找物理块时，可能多次查询不同逻辑地址都会查到同一个页表项和同一个物理块，因此快表正是利用了局部性原理优化了地址转换的过程。而局部行原理也可以使快表的命中率高达90%。下图为添加了快表之后的地址变换机构。
在这里插入图片描述
① CPU给出逻辑地址，由硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较（遍历所有页号是O(n)复杂度，但该过程快到耗时可以忽略不计，因为这是高速缓存）。

② 如果页号命中快表则从快表读出对应的块号，块号+页内偏移量拼接得到物理地址，访问该物理地址对应的内存单元。若快表命中则访问某个物理地址仅需一次访存即可。

③ 如果没有命中快表，则需要访问内存中的页表，将查到的页表项存入快表，以便后面可能发生的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。若快表未命中，则访问某个逻辑地址需要两次访存。

多级页表

简单的分页有什么缺陷吗？
有空间上的缺陷。
因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。
在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万（2^20）个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。
这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。
那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。
你可能会问，分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？
当然如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。
其实我们应该换个角度来看问题，还记得计算机组成原理里面无处不在的局部性原理么？
每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。
如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？
那么为什么不分级的页表就做不到这样节约内存呢？
我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。
我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。
对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：
全局页目录项 PGD（Page Global Directory）；
上层页目录项 PUD（Page Upper Directory）；
中间页目录项 PMD（Page Middle Directory）；
页表项 PTE（Page Table Entry）；

采用单级页表会有两个问题。

1、页表必须连续存放在内存，当页表很大时，页表需要占用多个连续的内存块。而从上面的内容我们知道连续存储会造成内存碎片。对于该问题，系统采用多级页表来解决。

2、根据局部性原理，进程一段时间内可能只访问特定的几个页面，因此没有必要让整个页表常驻内存。对于该问题，系统采用虚拟内存技术解决。

举个例子，某32位计算机系统按字节编址，采用分页存储管理，页面大小P=4KB，页表项长度L= 4B。那么内存存储一个页表需要耗费 1024 个页面。已知页面大小是12位。（下面给出计算过程，不感兴趣的朋友可以跳过）

计算过程：

最大页号N = 2 ^ (32-12) = 2^20

页表总大小S = 4 * N = 2 ^ 22

内存存储一个页表所需页面个数 = S / P = 2^22 / 2^12 = 2^10 = 1024 个页面

这就意味着每个进程的页表就可能占用连续1024个物理块。为了解决页表的存储需要连续占用多个物理块这个问题，操作系统使用两级页表。

操作系统将原本的单级页表划分为多个页，每页包含若干个表项，一个单级页表被分散存储在内存中。再用一个作为目录的页表记录这些离散的单级页表的页与其对应的块号，目录页表就是一个一级页表，或称为页目录表，原本的单级页表变成多个二级页表。一级页表的一个表项代表一个二级页表的位置。如下如所示：

在这里插入图片描述

地址转换过程：

1、使用二级页表时，系统会将一个逻辑地址按照位数解释为3个部分：一级页号、二级页号和数据所在的页内偏移。

2、从PCB 中读出页目录表的起始地址，再根据一级页号和页目录表的起始地址在内存查询页目录表，找到下一级页表在内存中的存放位置。

3、根据二级页号和二级页表的始址在内存中查二级页表，找到最终想访问的内存块号。

4、根据目标内存块号 + 页内偏移得到物理地址。

注意两个细节：

1、对于一个更长的逻辑地址，意味着系统的页面数量上限更多，系统可能使用三级或四级页表才能实现页表离散存储。非顶级页表的个数可以有多个，但每个页表的大小不能超过一个页面；顶级页表的个数只能有一个，只占用1个页面。根据这个原则可以判断出一个系统需要采用几级页表。

2、无论是多少级页表，进程的PCB只记录顶级页表的起始指针。因此n级页表下，CPU根据逻辑地址访问目标值需要进行 n+1 次内存访问。

页式存储下的内部碎片

考虑一种情况，系统的页面大小是4K，一个进程大小为49K，会占用13个页面，但是最后一个页面只用了1K，剩余3K没有被该进程使用，也不会被其他进程使用，于是会造成3K的内存碎片。

因此页式存储不会产生外部碎片，但会产生内部碎片，而且每个进程产生的碎片大小范围为 0~页面大小p，可以认为每个进程平均产生 p/2 字节的内部碎片大小。

页面尺寸

页面尺寸（也就是页面大小）是影响分页管理中内存使用效率的重要因素。

如果页面尺寸太大，就会出现越大的内存碎片；

如果页面太小，同一个进程所需的页面数会越多，该进程的页表占用的空间越多，而且会造成多级页表，每多一级页表，CPU根据逻辑地址找到目标值就需要多一次内存IO。

段式存储

通常用户程序由若干个逻辑模块组成，例如一个C程序中有一个主函数main，它调用子函数f1~f3，又调用标准函数库的printf和scanf，每一个函数都是一个独立的逻辑结构，都应该有自己独立的内存空间，每个内存空间的地址从0开始。

段式存储（又叫做分段存储）是指将进程按独立的逻辑结构划分为若干个段，每个段都被分配连续的内存空间，段与段之间离散存储。

在这里插入图片描述
用户程序进行编译时，编译程序会为该程序的各个逻辑结构构建段，例如在编译程序中会为下面内容建立单独的段：

1.全局变量

2.函数调用栈，用来放参数和返回地址

3.每个函数的代码部分

4.每个函数的局部变量

一个进程的程序段和数据段不止一个，而是程序中有多少个独立的逻辑模块就会产生多少个段。

例如进程A包含 main()、f()和g()这3个函数，其中 main()调用了f()和g()，此时进程A会产生3个程序段存放 main()/f()/g() 对应的机器指令，产生3个数据段存放 main()/f()/g() 生成的临时数据。而且这些段相互独立，相互离散。

如果main()先调用 f() 后调用 g() ，那么f() 和 g()的数据段不会同时出现在内存中，而是f()的数据段先被回收再创建g()的数据段，但 main()的数据段和f()的数据段肯定是同时在内存中的。

分段存储中，每个段都有一个段名和段号。和分页存储不同的是，每个页的长度是相同的，由操作系统决定；而每个段的长度是不同的，是由模块内的代码量和产生的数据量决定。

分段系统的逻辑地址结构由段号（也就是段名）和段内地址（段内偏移量）所组成。段号的位数决定了每个进程最多可以分几个段，段内地址位数决定了每个段的最大长度是多少。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

在这里插入图片描述

和页表类似，为了方便系统找到进程的某个段在物理内存中的起始地址，系统为分段存储管理下的每个进程建立了一个段表。如下所示：

在这里插入图片描述

1、每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称 “基址”）和段的长度（要记录长度是因为每个段的长度不同，而页的长度都相同）。

2、各个段表项的长度是相同的。段表项长度取决于段长的位数和段基址的位数（即操作系统位数）。由于段表项长度相同，因此段号是隐含的，不占存储空间。

分段存储的地址变换

在这里插入图片描述
①根据逻辑地址得到段号、段内地址。

②判断段号是否越界。若S≥M，说明CPU正访问一个不存在于该进程的段，产生越界中断，否则继续执行。

③根据段表基址和段号查询段表，找到对应的段表项，段表项的存放地址为 F+S*段表项长度。得到段基址b

④检查段内地址是否超过段长。若W≥C，说明CPU正访问一个该段不存在的地址，产生越界中断，否则继续执行。

⑤根据段基址b和段内偏移W计算得到物理地址。

⑥访问目标内存单元。

分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

分段和分页管理对比

1、从页和段的含义

分页的主要目的是为了实现进程在内存的离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

分段的主要目的是更好地满足用户需求。一个段通常包含着一个逻辑模块的信息，分段对用户是可见的。

2、从页和段的长度

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

3、分段比分页更容易实现程序的共享和保护。

因为我们共享程序具体是共享一个独立的逻辑模块，而分段存储管理是对独立的逻辑模块分配连续内存空间，系统只需将共享的这段代码在内存中的地址添加到要引用这段代码的进程中的段表中即可。

在这里插入图片描述
而如果在分页存储管理中共享，一个逻辑模块的内容可能分在在不同的页面中。假如该逻辑模块横跨11个页，就需要将这些页面的页号块号映射都添加到共享进程们的页表中。而且一个页可能既有共享模块的内容也有非共享模块的内容，如果让共享进程们的页表指向这个页，就可能访问到不可共享的代码和数据。

在这里插入图片描述
简单来说：在分页系统中实现页的共享较为困难，因为分页是对连续的进程逻辑空间等分，被共享的程序不一定刚好分在一个或多个完整的页面。此时就会出现一个页面既有共享程序又有不能共享的该进程自己的私有数据，因此页式存储不利于共享。

PS：关于共享程序

不能被修改的代码称为纯代码或可重入代码，这样的代码是可以安全的被并行执行的，只有这样的代码可以被多进程或多线程共享，而可修改的代码是不能共享的。

以函数为例，如果一个函数是可重入的，则该函数不能含有全局变量，只能包含调用者提供的参数，和函数自己产生的局部变量，可重入函数也不能调用其他不可重入的函数；

如下所示：

int g_var = 1;

int f()
{
g_var = g_var + 2;
return g_var;
}

int g()
{
return f() + 2;
}

f() 和 g() 都是不可重入函数，因为他们包含了一个全局变量 g_var，如果多进程共享f()和g()会导致g_var变量因为多进程并发的异步性而被改乱。

int f(int i)
{
return i + 2;
}

int g(int i)
{
return f(i) + 2;
}

这两个函数才是可重入函数。多进程只能共享f() 和 g() 的代码段，但是不会共享f()和g()的数据段。f() 和 g()运行过程中产生的数据分别保存在各自进程自己在运行f()/g()时创建的数据段中。例如进程A和进程B共享 f() ，进程A运行f()时系统会为其创建一个数据段A1用来保存f()产生的临时变量i，而且数据段A1和进程A运行自身其他逻辑模块产生的数据段是相互独立的，离散的。

在这里插入图片描述

段页式管理

段页式管理将进程按逻辑模块分段，再将各段分页，再将物理空间分为大小相同的内存块，把进程各页面分别装入各内存块中。

段页式存储同时继承了分页管理和分段管理的优点，分段方便用户进程按以逻辑模块为单位规划和运行，段内分页使一个段可以离散存储，提高了内存利用率，避免外部碎片。
在这里插入图片描述
段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成。

“分段”对用户是可见的，程序员知道程序中有多少个段，因为它亲手实现了这些逻辑模块。而将各段“分页”对用户是不可见的，系统会根据段内地址自动划分页号和页内偏移量。段页式管理中，一个进程对应一个段表和多个页表，一个段对应一个页表。

在这里插入图片描述

每个段对应一个段表项，每个段表项由段号、段对应的页表长度、页表存放的块号（页表起始地址）组成。每个页面对应一个页表项，每个页表项由页号、块号组成。

段页式存储地址变换的过程
在这里插入图片描述
无论是段式存储、页式存储还是段页式存储，其地址变换都发生在进程运行时，即CPU执行指令时发生的。

linux内存布局与管理

用户空间和系统空间

在这里插入图片描述

内存满了，会发生什么？

更多看小林
在这里插入图片描述

文件页（File-backed Page）：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Cache）都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据（也就是脏页），就得先写入磁盘，然后才能进行内存释放。所以，回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存。
匿名页（Anonymous Page）：这部分内存没有实际载体，不像文件缓存有硬盘文件这样一个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们回收的方式是通过 Linux 的 Swap 机制，Swap 会把不常访问的内存先写到磁盘中，然后释放这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。

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

在系统空闲内存不足的情况，进程申请了一个很大的内存，如果直接内存回收都无法回收出足够大的空闲内存，那么就会触发 OOM 机制，内核就会根据算法选择一个进程杀掉。

Linux 到底是根据什么标准来选择被杀的进程呢？这就要提到一个在 Linux 内核里有一个 oom_badness() 函数，它会把系统中可以被杀掉的进程扫描一遍，并对每个进程打分，得分最高的进程就会被首先杀掉。

进程得分的结果受下面这两个方面影响：

第一，进程已经使用的物理内存页面数。
第二，每个进程的 OOM 校准值 oom_score_adj。它是可以通过 /proc/[pid]/oom_score_adj 来配置的。我们可以在设置 -1000 到 1000 之间的任意一个数值，调整进程被 OOM Kill 的几率。
函数 oom_badness() 里的最终计算方法是这样的：

// points 代表打分的结果
// process_pages 代表进程已经使用的物理内存页面数
// oom_score_adj 代表 OOM 校准值
// totalpages 代表系统总的可用页面数
points = process_pages + oom_score_adj*totalpages/1000

用「系统总的可用页面数」乘以「OOM 校准值 oom_score_adj」再除以 1000，最后再加上进程已经使用的物理页面数，计算出来的值越大，那么这个进程被 OOM Kill 的几率也就越大。

每个进程的 oom_score_adj 默认值都为 0，所以最终得分跟进程自身消耗的内存有关，消耗的内存越大越容易被杀掉。我们可以通过调整 oom_score_adj 的数值，来改成进程的得分结果：

如果你不想某个进程被首先杀掉，那你可以调整该进程的 oom_score_adj，从而改变这个进程的得分结果，降低该进程被 OOM 杀死的概率。
如果你想某个进程无论如何都不能被杀掉，那你可以将 oom_score_adj 配置为 -1000。
我们最好将一些很重要的系统服务的 oom_score_adj 配置为 -1000，比如 sshd，因为这些系统服务一旦被杀掉，我们就很难再登陆进系统了。

但是，不建议将我们自己的业务程序的 oom_score_adj 设置为 -1000，因为业务程序一旦发生了内存泄漏，而它又不能被杀掉，这就会导致随着它的内存开销变大，OOM killer 不停地被唤醒，从而把其他进程一个个给杀掉。

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

存在比较大的争议，有人说会申请失败，有的人说可以申请成功。

这个问题在没有前置条件下，就说出答案就是耍流氓。这个问题要考虑三个前置条件：

操作系统是 32 位的，还是 64 位的？
申请完 8G 内存后会不会被使用？
操作系统有没有使用 Swap 机制？
更多看小林

预读失效和缓存污染——如何改进 LRU 算法

Linux 的 Page Cache 和 MySQL 的 Buffer Pool 的大小是有限的，并不能无限的缓存数据，对于一些频繁访问的数据我们希望可以一直留在内存中，而一些很少访问的数据希望可以在某些时机可以淘汰掉，从而保证内存不会因为满了而导致无法再缓存新的数据，同时还能保证常用数据留在内存中。

要实现这个，最容易想到的就是 LRU（Least recently used）算法。

LRU 算法一般是用「链表」作为数据结构来实现的，链表头部的数据是最近使用的，而链表末尾的数据是最久没被使用的。那么，当空间不够了，就淘汰最久没被使用的节点，也就是链表末尾的数据，从而腾出内存空间。

因为 Linux 的 Page Cache 和 MySQL 的 Buffer Pool 缓存的基本数据单位都是页（Page）单位，所以后续以「页」名称代替「数据」。

传统的 LRU 算法的实现思路是这样的：

当访问的页在内存里，就直接把该页对应的 LRU 链表节点移动到链表的头部。
当访问的页不在内存里，除了要把该页放入到 LRU 链表的头部，还要淘汰 LRU 链表末尾的页。
比如下图，假设 LRU 链表长度为 5，LRU 链表从左到右有编号为 1，2，3，4，5 的页。
在这里插入图片描述
如果访问了 3 号页，因为 3 号页已经在内存了，所以把 3 号页移动到链表头部即可，表示最近被访问了。

而如果接下来，访问了 8 号页，因为 8 号页不在内存里，且 LRU 链表长度为 5，所以必须要淘汰数据，以腾出内存空间来缓存 8 号页，于是就会淘汰末尾的 5 号页，然后再将 8 号页加入到头部。
在这里插入图片描述

传统的 LRU 算法并没有被 Linux 和 MySQL 使用，因为传统的 LRU 算法无法避免下面这两个问题：

预读失效导致缓存命中率下降；
缓存污染导致缓存命中率下降；

预读失效，怎么办？

Linux 操作系统为基于 Page Cache 的读缓存机制提供预读机制，一个例子是：

应用程序只想读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block（4KB），于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。
但是操作系统出于空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page；

上图中，应用程序利用 read 系统调动读取 4KB 数据，实际上内核使用预读机制（ReadaHead）机制完成了 16KB 数据的读取，也就是通过一次磁盘顺序读将多个 Page 数据装入 Page Cache。

这样下次读取 4KB 数据后面的数据的时候，就不用从磁盘读取了，直接在 Page Cache 即可命中数据。因此，预读机制带来的好处就是减少了磁盘 I/O 次数，提高系统磁盘 I/O 吞吐量。

MySQL Innodb 存储引擎的 Buffer Pool 也有类似的预读机制，MySQL 从磁盘加载页时，会提前把它相邻的页一并加载进来，目的是为了减少磁盘 IO。

预读失效会带来什么问题？
如果这些被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是预读失效。

如果使用传统的 LRU 算法，就会把「预读页」放到 LRU 链表头部，而当内存空间不够的时候，还需要把末尾的页淘汰掉。

如果这些「预读页」如果一直不会被访问到，就会出现一个很奇怪的问题，不会被访问的预读页却占用了 LRU 链表前排的位置，而末尾淘汰的页，可能是热点数据，这样就大大降低了缓存命中率。

#如何避免预读失效造成的影响？
我们不能因为害怕预读失效，而将预读机制去掉，大部分情况下，空间局部性原理还是成立的。

要避免预读失效带来影响，最好就是让预读页停留在内存里的时间要尽可能的短，让真正被访问的页才移动到 LRU 链表的头部，从而保证真正被读取的热数据留在内存里的时间尽可能长。

那到底怎么才能避免呢？

Linux 操作系统和 MySQL Innodb 通过改进传统 LRU 链表来避免预读失效带来的影响，具体的改进分别如下：

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）；
MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：young 区域和 old 区域。
这两个改进方式，设计思想都是类似的，都是将数据分为了冷数据和热数据，然后分别进行 LRU 算法。不再像传统的 LRU 算法那样，所有数据都只用一个 LRU 算法管理。

接下来，具体聊聊 Linux 和 MySQL 是如何避免预读失效带来的影响？

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

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）。

active list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；
inactive list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

有了这两个 LRU 链表后，预读页就只需要加入到 inactive list 区域的头部，当页被真正访问的时候，才将页插入 active list 的头部。如果预读的页一直没有被访问，就会从 inactive list 移除，这样就不会影响 active list 中的热点数据。

接下来，给大家举个例子。

假设 active list 和 inactive list 的长度为 5，目前内存中已经有如下 10 个页：
在这里插入图片描述
现在有个编号为 20 的页被预读了，这个页只会被插入到 inactive list 的头部，而 inactive list 末尾的页（10号）会被淘汰掉。

即使编号为 20 的预读页一直不会被访问，它也没有占用到 active list 的位置，而且还会比 active list 中的页更早被淘汰出去。

如果 20 号页被预读后，立刻被访问了，那么就会将它插入到 active list 的头部， active list 末尾的页（5号），会被降级到 inactive list ，作为 inactive list 的头部，这个过程并不会有数据被淘汰。
在这里插入图片描述
MySQL 是如何避免预读失效带来的影响？

MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域，young 区域和 old 区域。

young 区域在 LRU 链表的前半部分，old 区域则是在后半部分，这两个区域都有各自的头和尾节点，如下图：
在这里插入图片描述

young 区域与 old 区域在 LRU 链表中的占比关系并不是一比一的关系，而是 63:37（默认比例）的关系。

划分这两个区域后，预读的页就只需要加入到 old 区域的头部，当页被真正访问的时候，才将页插入 young 区域的头部。如果预读的页一直没有被访问，就会从 old 区域移除，这样就不会影响 young 区域中的热点数据。

接下来，给大家举个例子。

假设有一个长度为 10 的 LRU 链表，其中 young 区域占比 70 %，old 区域占比 30 %。
在这里插入图片描述
现在有个编号为 20 的页被预读了，这个页只会被插入到 old 区域头部，而 old 区域末尾的页（10号）会被淘汰掉。

在这里插入图片描述
如果 20 号页一直不会被访问，它也没有占用到 young 区域的位置，而且还会比 young 区域的数据更早被淘汰出去。

如果 20 号页被预读后，立刻被访问了，那么就会将它插入到 young 区域的头部，young 区域末尾的页（7号），会被挤到 old 区域，作为 old 区域的头部，这个过程并不会有页被淘汰。

在这里插入图片描述

缓存污染，怎么办？

#什么是缓存污染？
虽然 Linux （实现两个 LRU 链表）和 MySQL （划分两个区域）通过改进传统的 LRU 数据结构，避免了预读失效带来的影响。

但是如果还是使用「只要数据被访问一次，就将数据加入到活跃 LRU 链表头部（或者 young 区域）」这种方式的话，那么还存在缓存污染的问题。

当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young 区域）里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了。

#缓存污染会带来什么问题？
缓存污染带来的影响就是很致命的，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，系统性能就会急剧下降。

我以 MySQL 举例子，Linux 发生缓存污染的现象也是类似。

当某一个 SQL 语句扫描了大量的数据时，在 Buffer Pool 空间比较有限的情况下，可能会将 Buffer Pool 里的所有页都替换出去，导致大量热数据被淘汰了，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，MySQL 性能就会急剧下降。

注意，缓存污染并不只是查询语句查询出了大量的数据才出现的问题，即使查询出来的结果集很小，也会造成缓存污染。

比如，在一个数据量非常大的表，执行了这条语句：

select * from t_user where name like “%xiaolin%”;
可能这个查询出来的结果就几条记录，但是由于这条语句会发生索引失效，所以这个查询过程是全表扫描的，接着会发生如下的过程：

从磁盘读到的页加入到 LRU 链表的 old 区域头部；
当从页里读取行记录时，也就是页被访问的时候，就要将该页放到 young 区域头部；
接下来拿行记录的 name 字段和字符串 xiaolin 进行模糊匹配，如果符合条件，就加入到结果集里；
如此往复，直到扫描完表中的所有记录。
经过这一番折腾，由于这条 SQL 语句访问的页非常多，每访问一个页，都会将其加入 young 区域头部，那么原本 young 区域的热点数据都会被替换掉，导致缓存命中率下降。那些在批量扫描时，而被加入到 young 区域的页，如果在很长一段时间都不会再被访问的话，那么就污染了 young 区域。

举个例子，假设需要批量扫描：21，22，23，24，25 这五个页，这些页都会被逐一访问（读取页里的记录）。
在这里插入图片描述
在批量访问这些页的时候，会被逐一插入到 young 区域头部。

在这里插入图片描述
可以看到，原本在 young 区域的 6 和 7 号页都被淘汰了，而批量扫描的页基本占满了 young 区域，如果这些页在很长一段时间都不会被访问，那么就对 young 区域造成了污染。

如果 6 和 7 号页是热点数据，那么在被淘汰后，后续有 SQL 再次读取 6 和 7 号页时，由于缓存未命中，就要从磁盘中读取了，降低了 MySQL 的性能，这就是缓存污染带来的影响。

#怎么避免缓存污染造成的影响？
前面的 LRU 算法只要数据被访问一次，就将数据加入活跃 LRU 链表（或者 young 区域），这种 LRU 算法进入活跃 LRU 链表的门槛太低了！正式因为门槛太低，才导致在发生缓存污染的时候，很容就将原本在活跃 LRU 链表里的热点数据淘汰了。

所以，只要我们提高进入到活跃 LRU 链表（或者 young 区域）的门槛，就能有效地保证活跃 LRU 链表（或者 young 区域）里的热点数据不会被轻易替换掉。

Linux 操作系统和 MySQL Innodb 存储引擎分别是这样提高门槛的：

Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。
MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行停留在 old 区域的时间判断：
如果第二次的访问时间与第一次访问的时间在 1 秒内（默认值），那么该页就不会被从 old 区域升级到 young 区域；
如果第二次的访问时间与第一次访问的时间超过 1 秒，那么该页就会从 old 区域升级到 young 区域；
提高了进入活跃 LRU 链表（或者 young 区域）的门槛后，就很好了避免缓存污染带来的影响。

在批量读取数据时候，如果这些大量数据只会被访问一次，那么它们就不会进入到活跃 LRU 链表（或者 young 区域），也就不会把热点数据淘汰，只会待在非活跃 LRU 链表（或者 old 区域）中，后续很快也会被淘汰。

总结

传统的 LRU 算法法无法避免下面这两个问题：

预读失效导致缓存命中率下降；
缓存污染导致缓存命中率下降；

为了避免「预读失效」造成的影响，Linux 和 MySQL 对传统的 LRU 链表做了改进：

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active list）和非活跃 LRU 链表（inactive list）。
MySQL Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：young 区域和 old 区域。

但是如果还是使用「只要数据被访问一次，就将数据加入到活跃 LRU 链表头部（或者 young 区域）」这种方式的话，那么还存在缓存污染的问题。

为了避免「缓存污染」造成的影响，Linux 操作系统和 MySQL Innodb 存储引擎分别提高了升级为热点数据的门槛：

Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。
MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行停留在 old 区域的时间判断：
如果第二次的访问时间与第一次访问的时间在 1 秒内（默认值），那么该页就不会被从 old 区域升级到 young 区域；
如果第二次的访问时间与第一次访问的时间超过 1 秒，那么该页就会从 old 区域升级到 young 区域；
通过提高了进入 active list （或者 young 区域）的门槛后，就很好了避免缓存污染带来的影响。

进程管理

并发和并行有什么区别？

在这里插入图片描述

程序进程的区别

在这里插入图片描述

进程

状态

在这里插入图片描述

进程的控制结构PCB

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

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

PCB 具体包含什么信息呢？

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

可见，PCB 包含信息还是比较多的。

每个 PCB 是如何组织的呢？

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

将所有处于就绪状态的进程链在一起，称为就绪队列；
把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

进程的上下文切换

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

在详细说进程上下文切换前，我们先来看看 CPU 上下文切换

大多数操作系统都是多任务，通常支持大于 CPU 数量的任务同时运行。实际上，这些任务并不是同时运行的，只是因为系统在很短的时间内，让各个任务分别在 CPU 运行，于是就造成同时运行的错觉。

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

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

CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存（缓存）。我举个例子，寄存器像是你的口袋，内存像你的书包，硬盘则是你家里的柜子，如果你的东西存放到口袋，那肯定是比你从书包或家里柜子取出来要快的多。

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

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

既然知道了什么是 CPU 上下文，那理解 CPU 上下文切换就不难了。

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

系统内核会存储保持下来的上下文信息，当此任务再次被分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

上面说到所谓的「任务」，主要包含进程、线程和中断。所以，可以根据任务的不同，把 CPU 上下文切换分成：进程上下文切换、线程上下文切换和中断上下文切换。

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

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

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

通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行，如下图所示：
在这里插入图片描述
大家需要注意，进程的上下文开销是很关键的，我们希望它的开销越小越好，这样可以使得进程可以把更多时间花费在执行程序上，而不是耗费在上下文切换。

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

为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；
进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；
以上，就是发生进程上下文切换的常见场景了。

线程

为什么使用线程？

我们举个例子，假设你要编写一个视频播放器软件，那么该软件功能的核心模块有三个：

从视频文件当中读取数据；
对读取的数据进行解压缩；
把解压缩后的视频数据播放出来；
对于单进程的实现方式，我想大家都会是以下这个方式：

在这里插入图片描述

对于单进程的这种方式，存在以下问题：

播放出来的画面和声音会不连贯，因为当 CPU 能力不够强的时候，Read 的时候可能进程就等在这了，这样就会导致等半天才进行数据解压和播放；
各个函数之间不是并发执行，影响资源的使用效率；
那改进成多进程的方式：

在这里插入图片描述

对于多进程的这种方式，依然会存在问题：

进程之间如何通信，共享数据？
维护进程的系统开销较大，如创建进程时，分配资源、建立 PCB；终止进程时，回收资源、撤销 PCB；进程切换时，保存当前进程的状态信息；
那到底如何解决呢？需要有一种新的实体，满足以下特性：

实体之间可以并发运行；
实体之间共享相同的地址空间；
这个新的实体，就是线程( Thread )，线程之间可以并发运行且共享相同的地址空间。

什么是线程？

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

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

在这里插入图片描述
线程的优缺点？

线程的优点：

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

线程的缺点：

当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java语言中的线程奔溃不会造成进程崩溃，具体分析原因可以看这篇：线程崩溃了，进程也会崩溃吗？ (opens new window)）。

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

线程与进程的比较

更多看那篇单独的博客

线程与进程的比较如下：

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

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

所以，不管是时间效率，还是空间效率线程比进程都要高。