操作系统学习2025.04.02-2025.04.08-EW帮帮网

程序局部性原理

程序局部性原理表现为：时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某块数据被访问，则不久之后该数据可能再次被访问。空间局部性是指一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。

硬件结构

冯诺依曼模型

内存：程序和内存存储在内存，存储的区域是线性的。存储的基本单位是字节（byte），1字节等于8位（8bit）。每一个字节都对应一个内存地址。内存的地址是从0开始编写，自增排列，最后一个地址len-1。内存的读写任何一个数据速度是一样的。。
中央处理器CPU：32位一次可计算4个字节，64----8个字节。32和64称为CPU的位宽，表示CPU一次可计算的数据量。
1. 8位CPU一次能计算1个字节，即0~255范围内的数。即 $2^8$ 。
2. 内部组件：寄存器、控制单元、逻辑运算单元。控制单元负责控制CPU工作、逻辑运算单元负责计算、寄存器各不相同（主要存储计算时的数据，如果都把数据存放到内存中，CPU计算的时候还要传送，太慢了，不如自己搞一个存储数据的组件。）：**通用寄存器：**存放需要进行运算的数据；**程序计数器：**用来存储CPU要执行的下一条指令【所在内存地址】，此时指令还在内存里面；**指令寄存器：**存放正在执行的指令，执行完成之前都存在这里面
总线：总线用于CPU和内存以及其他设备之间的通信：**地址总线：**用于指定CPU将要操作的内存地址；**数据总线：**用于读写内存的数据；**控制总线：**发送和接收信号；
1. CPU读写内存数据过程：先通过地址总线来指定内存地址、再通过控制总线控制是读或写命令、最后通过数据总线来传输数据。
输入、输出设备：如果输入设备是键盘、按下键时需要和CPU进行交互，会用到控制总线。
32位CPU地址总线32位，能表示 $2^{32}$ 个不同的地址。一个地址对应一个一字节内存空间，刚好4GB
只要当计算超过32位数字的情况下，64位的优势才能体现出来。32位CPU最多只能操作4GB内存，就算装了8GB内存条也没用
程序执行流程：当一个程序执行时，CPU会根据程序计数器的内存地址，从内存里面把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，开始顺序读取下一条指令。CPU从程序计数器读取指令、到执行、再到下一条指令。这个过程会不断循环，知道程序执行结束。这个过程为CPU的指令周期。

总结：如果32位指令在64位机器上执行，需要兼容机制，做到兼容运行。64位不能在32位上执行，因为32位寄存器存不了64位的指令。硬件的64位和32位是指CPU的位宽，软件的64位和32位指的是指令的位宽。

磁盘和内存

对于存储器，它的速度越快，能耗就会越高，而且材料的成本也是越贵，速度快的存储器的容量都比较小。
- 通常有这么几种：寄存器、CPU Cache(L1、L2、L3)、内存、SSD/HDD硬盘
- CPU Cache CPU高速缓存：用的是SRAM（static Random-Access Memory，静态随机存储器）的芯片。之所以叫做静态，是因为只要有电数据就可以存在，断电就消失。
- 内存：DRAM（Dynamic Random Access Memory，动态随机存取存储器），功耗低，容量更多，比SRAM偏移。
- SSD、HDD 固体硬盘、机械硬盘。
直接映射Cache：可以找到Cache中对应的数据。就是把内存块的地址适中映射在一个CPU Cache Line（缓存块）的地址，以实现映射关系，使用取模运算，运算的结果就是内存块地址对应的CPU Cache Line（缓存块）的地址。
一个内存的访问地址，包括组标记、CPU Cache Line 索引、偏移量三种信息。CPU通过这些信息，就可以在CPU Cache中找到缓存的数。CPU Cache里的数据结构是由索引+有效位+组标记+数据块组成

如何让CPU跑的更快？

如果访问的数据在CPU Cache中的话，意味着缓存命中，那么缓存命中率越高的话，CPU 就跑的越快。L1 Cache分为【数据缓存】和【指令缓存】

提高数据缓存的命中率：遇到遍历数组的时候，按照内存布局顺序访问，可以有效的利用CPU Cache带来的好处。
提高指令缓存的命中率：
1. 两个操作，循环遍历数组，把小于50的数组元素置为0、将数组排序。
2. CPU中分支预测器；如果分支预测可以预测接下来要执行if里的指令，还是else指令的话，可以提前把这些指令放在指令缓存中，这样CPU可以之间从Cache读取到指令，于是执行速度会很快。比如，排序后，前几次循环命中符合条件的次数比较多，分支预测就会缓存array[i] = 0指令到Cache中，后面直接从缓存里取就好了
多核CPU的缓存命中率：对于多核CPU，线程可能在不同CPU核心来回切换，这样核心的缓存命中率就会收到影响，于是要想提高线程的缓存命中率，可以考虑把线程绑定CPU到某一个CPU核心上
1. 在Linux上提供了sched_setaffinity方法，来实现将线程绑定到某个CPU核心这一功能。

什么时候把Cache的数据写回到内存呢？

如果数据写入Cache后，内存与Cache相对应的数据将会不同，这种情况下Cache和内存数据都不一致了，于是肯定是要把Cache中数据同步到内存里。

写直达（Write Through）：保持内存和Cache一致性最简单的方式就是：把数据同时写入内存和Cache中，这种方法称为写直达（Write Through）。
- ？先判断数据是否已经在CPU Cache里了，如果在，先将数据更新到Cache里面，再写入到内存里面，如果不在，就直接把数据更新到内存里面。
- 这样无论在不在，每次写操作都要回到内存，这会浪费很多时间的
- 所以要减少数据写回内存的频率。
写回（Write Back）：当发生写操作时，新的数据仅仅被写入了Cache Block里，只有当修改过的Cache Block【被替换】才会写到内存。

多核心下的缓存一致性问题

当A号核心更新了i的值之后，还未写入到内存，此时核心B从内存读取到的i的值肯定是错误的。这将导致执行结果的错误。所以，我们需要一个机制来同步不同核心里面的缓存数据。

写传播：某个CPU核心里的Cache数据更新时，必须要传播到其他Cache；
事务串行化：某个CPU核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的。
1. CPU核心对于Cache中数据的操作，需要同步给其他CPU核心。
2. 要引入【锁】的概念，如果两个CPU核心里有相同数据的Cache，那么对于这个Cache数据的更新，只有拿到了【锁】，才能进行更新
MESI协议

CPU如何执行任务？

CPU从内存读取数据到Cache的时候，并不是一个字节一个字节读取，而是一块一块的方式来读取数据的。即CPU Cache Line（缓存块）所以CPU Cache Line是CPU从内存读取数据到Cache的单位。

伪共享：多个线程同时读写同一个Cache Line 的不同变量时，而导致CPU Cache 失效的现象称为伪共享

怎么避免？用空间换时间，浪费一部分Cache空间，从而换来性能的提升。针对同一个Cache Line 中共享的数据，如果多核之间竞争较为严重，为防止伪共享现象发生，可采用宏定义__cacheline_aligned使得变量在Cache Line里是对齐的。

CPU如何选择线程？

在Linux内核中，进程和线程都是用task_struct结构体表示的，区别在于线程的task_struct结构体里部分资源是共享了进程已创建的资源，如内存地址空间、代码段、文件描述符，所以Linux中线程也叫做**【轻量化进程】**
没有创建线程的进程，只有单个执行流，被称为主线程。为了处理更多事情，就创建多个线程。
Linux内核里的调度器，调度对象就是task_struct，接下来就把这个数据结构称为任务。根据任务的优先级以及响应要求，分两种，优先级数值越小，优先级越高。
- 实时任务，都系统的响应时间要求很高，也就是要尽可能快执行实时任务；优先级0~99
- 普通任务，响应时间没有很高，优先级100~139
调度类：由于任务有优先级之分，为了保障高优先级的任务尽快完成，就设计了调度类
安全公平调度

什么是软中断？

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

中断请求的响应程序，也就是中断处理程序，要尽可能快的执行完，减少对正常进程运行调度地影响。
软中断：Linux系统为了解决中断处理程序过长和中断丢失的问题，将中断过程分成两个阶段，分别是【上半部和下半部分】
1. 上半部用来快速处理中断：一般会暂时关闭中断请求，主要负责处理跟硬件紧密相关或者时间敏感的事情。上半部直接处理硬件请求，也就是硬中断，主要负责耗时短的工作，特点是快速执行；
2. 上半部用来延迟上半部未完成的工作，一般以【内核线程】的方式运行。下半部是由内核触发，也就是软中断，主要是负责上半部未完成的工作，通常都是耗时比较长的事情，特点是延迟执行。

补码

为什么负数要用补码表示？
1. 为了统一和正数的加减法操作一样，毕竟数字的加减法是很常用的一个操作，所以尽量以统一的方式进行运算。
十进制小数转换成二进制？
1. 十进制整数转二进制【除2取余法】，十进制小数使用【乘二取整法】
计算机怎么存小数？
1. 符号位：0表示正，1表示负
2. 指数位：指数位长度越长则数值表示范围越大
3. 尾数位：小数点右侧的数字
0.1+0.2==0.3？
1. 因为0.1的二进制表示位0.00110011…对于计算机而言无法精确表达，所以浮点数只能根据精度舍入。近似值表示二进制

操作系统结构

内核？Kernel

计算机由各种硬件设备组成，如果每个应用都要和这些硬件设备对接通信协议，太麻烦，所以由内核来做这个中间人，让内核作为应用连接硬件设备的桥梁，应用程序只需要关心与内核交互，不用关心硬件细节。

内核有啥用？
1. 管理进程、线程，决定哪个进程、线程使用CPU，进程调度的能力；
2. 管理内存，决定内存的分配和回收，内存管理的能力
3. 管理硬件设备，为进程与硬件设备之间提供通信能力，硬件通信能力；
4. 提供系统调用，如果应用程序要运行更高权限运行的服务，需要系统调用，它是用户与操作系统之间的接口。
内核怎么工作？

内核举要很高的权限，可以操作硬件；大多数操作系统将内存分成两个区域
1. 内核空间：这个内存空间只有内核程序可以访问；
2. 用户空间：这个内存空间专门给应用程序使用；
用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间；程序使用用户空间的时候，就说该程序在用户态执行，当程序使用内核空间时，程序则在内核态执行。
应用程序怎么进入内核空间呢？

内核程序执行在内核态，用户程序执行在用户态。当应用程序使用系统调用时，会产生一个中断，发生中断后，CPU会中断当前执行的用户程序，转而跳转到中断处理程序，也就是开始执行内核程序。内核处理完后，主动触发中断，把CPU执行权限交回给用户程序，回到用户态继续工作。

Linux的设计：Linus Torvalds 芬兰

Linux内核设计的理念

MultiTask：多任务，意味着多个任务可同时执行，这里的同时可以是并发或并行。
SMP：对称多处理，每个CPU的地位是相等的，对资源的使用权限也是相同的，多个CPU共享一个内存，每个CPU都可以访问完整的内存硬件资源
ELF：可执行文件链接格式，它是Linux操作系统中可执行文件的存储格式。结构：ELF header、program header table、.text、.rodata、…、.data、section header table
Monolithic Kernel：宏内核，Linux内核架构就是宏内核，意味着Linux的内核是一个完整的可执行程序，且拥有最高的权限。宏内核的特征是：系统内核的所有模块，比如进程调度、内存管理、文件系统、设备驱动都运行在内核态。

微内核：只保留最基本的能力，比如进程调度、虚拟机内存，中断等等，把一些应用放到用户空间，比如驱动程序、文件系统等；因此内核功能少，可以移植性高；但是由于驱动程序不在内核中，而且驱动程序一般会频繁调用底层能力的，于是驱动和硬件设备交互就需要频繁切换到内核态，这样会带来性能损耗

Windows设计

混合类型内核：内核里面会有一个最小版本的内核，然后其他模块会在这个基础上搭建，然后实现的时候会跟宏内核类似，把整个内核做出一个完整的程序，大部分服务都在内核中，像是宏内核的方式包裹一个微内核
Windows 和 Linux一样，同样支持 MultiTask、SMP，
- 但是Windows内核设计是混合型内核，内核中由一个MicroKernel模块，这个就是最小版本的内核，而整个内核实现是一个完整的程序。
- Window的可执行文件格式叫**PE：可移植执行文件**，扩展名通常是.exe、.dll、.sys

总的来说，内核的架构一般就是这三种：

宏内核：包含多个模块，整个内核就像一个完整的程序 Linux
微内核：有一个最小版本的内核，一些模块和服务则由用户态管理
混合内核：是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的内核，其他模块就在这个基础上搭建，整个内核就是完整的程序。Windows

内存管理

虚拟内存

单片机的CPU都是直接操作内存的【物理地址】
想要在内存中同时运行两个程序是不可能的。假如第一个程序在2000的位置上写入新的值，将会擦掉第二个程序存放在相同位置上的内容，此时两个程序会立刻崩溃。
操作系统如何解决这个问题呢？
- 我们可以把进程所使用的地址隔离开，让操作系统为每个进程分配独立的一套虚拟地址，人人都有，互不干涉。前提是：每个进程都不能访问物理地址。
虚拟地址怎么落到物理内存呢？
- 操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。
- 如果程序要访问虚拟地址的时候，由于操作系统换成不同的物理地址，不同的进程运行的时候，写入的是不同的物理地址，这样就会冲突了。
  - 程序所使用的内存地址叫做：虚拟内存地址
  - 实际存在硬盘里面的空间地址叫做：物理内存地址
- 操作系统引入虚拟内存，进程持有的虚拟地址会通过CPU芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存。

如何管理虚拟地址与物理地址之间的关系呢？

内存分段、内存分页

内存分段：程序是由若干个逻辑分段组成的，可由代码分段、数据分段、栈段、堆段组成。不同的段有不同的属性，所以就用分段的形式把这些分离出来。
- 分段机制下，虚拟地址和物理地址如何映射？
  - 虚拟地址由 段选择因子和段内偏移量 组成
  - 段选择因子：保存在段寄存器里面，段选择因子里面最重要的就是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级。
  - 虚拟地址中的 段内偏移量 应该位于 0 和段界限之间，如果段内偏移量是合法的，就将基地址加上段内偏移量得到物理内存地址。、
- 虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序虚拟地址分成4个段：代码段、数据段、堆段、栈段。
- 产生内存碎片的问题、以及内存交换的效率低的问题
为什么产生内存碎片问题？
- 因为内存分段管理是按需求分配相应大小的段，所以不会出现内存碎片
- 假设一共1G的物理内存，游戏占用了512、浏览器占了128、音乐占了256，浏览器退出还剩256，但是剩余的256不是连续的，所以导致我们没有空间打开一个200MB的程序。
- 内存碎片：内部内存碎片、外部内存碎片
- 怎么解决？内存交换：先把音乐占用的256MB写到硬盘上，然后再从硬盘上读回到内存里，在读回的时候，不能装载到原来的位置，而是紧紧跟着已被占用的512内存后面，这样后面就能空缺处256MB空间，这样200MB的程序就可以装载进来；
  - 这个内存交换空间，在Linux系统里，也就是我们常看到的Swap空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。
分段为什么会导致内存交换效率低的问题？
- 对于多进程的系统，分段的方式，外部内存碎片化很容易产生，产生了外部内存碎片，就不得不重新Swap内存区域。因为硬盘的访问速度要比内存慢太多了，每一次内存交换，都需要把一大段连续的内存数据连续写到硬盘上。
- 如果内存交换的时候，交换的是一个占用内存空间很大的程序，这样整个机器都会显得卡顿

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

怎么能少出现一些内存碎片呢？在要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点，就可解决问题了。
内存分页：就是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，叫页。在Linux下，每一页的大小为4KB。
- **虚拟地址与物理地址之间通过页表来映射。**页表是存储在内存里的，内存管理单元MMU就做将虚拟地址转换成物理地址的工作。
分页怎么解决问题的？
- 内存分页由于内存空间都是预先划分好的，页与页之间是紧密排列的，所以不会有外部碎片
- 内存分页机制分配内存的最小单位是一页，如果程序不足一页大小，就会出现页内内存浪费，即内部内存碎片
- 如果内存空间不够，操作系统会把其他正在运行的进程中的【最近没被使用】的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap out）。一旦需要的时候，再加载进来，称为 换入（Swap In）。所以一次性写入磁盘的也只有少数的一个或几个页，不会花太多时间，内存交换的效率就相对比较高
分页的方式：在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去
- 分页机制下，虚拟地址和物理地址如何映射？
  - 页号和 页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址
  - 先把虚拟内存地址，切分为页号和偏移量；根据页号，从页表里面，查询对应的物理页号；直接拿物理页号加上偏移量就得到了物理内存地址。
简单的分页会有空间上的限制。因为操作系统可以同时运行非常多的进程，意味着页表会非常的庞大。
- 假如在32位环境下，虚拟地址空间共有4GB，假设一个页大小时4KB，那么需要4MB的内存存储页表。并且每个进程有自己的页表，100个进程，就需要400MB内存来存储页表。
多级页表（Muti-Level Page Table）
- 那么为什么不分级的页表就做不到这样节约内存呢？
  - 从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。如果虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要100多万个页表项来映射，而二级分页只需要1024个页表项（此时以及页表覆盖到了全部虚拟地址空间，二级页表在需要的时候创建）
- 局部原理性
- 对于64位系统，两级分页肯定不够，就变成四级目录：
  - 全局页目录项PGD（Page Global Directory）
  - 上层页目录项PUD（Page Upper Directory）
  - 中间页目录项PMD（Page Middle Directory）
  - 页表项 PTE（Page Table Entry）
多级页表解决了空间上的问题，但又增加了时间上的问题。由于程序是由局部性的，在某一段时间，整个程序的执行权限仅限于程序中的某一部分。相应地，执行所访问地存储空间也局限于某个内存区域。
利用这一特性，就把最常访问的几个页表存储到访问速度更快的硬件，所以在CPU中，加入一个专门存放程序最常访问的页表项Cache，这个Cache就是TLB（Translation Lookaside Buffer），通常称为页表缓存、转址旁路缓存、块表等
- 这样，CPU 在寻址时，先查TLB，如果没有再查常规的页表

段页式内存管理

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

这样：地址结构由 段号、段内页号和页内位移 组成

段页式地址变换的数据结构是每一个程序一张段表、每个段又建立一个页表，段表中的地址是页表的起始地址，而页表的地址则为某页的物理地址。

怎么访问？

先访问段表，得到页表起始地址；再访问页表，得到物理页号；最后将物理页号与页内位移组合，得到物理地址。

Linux内存布局

段式内存管理先将逻辑地址映射成线性地址，然后再由页式内存管理将线性地址映射成物理地址。

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

Linux系统主要采用了分页管理，但是由于Intel处理器的发展史，Linux系统无法避免分段管理。于是Linux就把所有段的基地址设为0，也就意味着所有程序的地址空间都是线性地址空间（虚拟地址），相当于屏蔽了CPU逻辑地址的概念，所以段只能被用于访问控制和内存保护

Linux系统中虚拟空间分布可分为用户态和内核态两部分，其中用户态的分布：代码段、全局变量、BSS、函数栈、堆内存、映射区。

虚拟内存的作用

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

malloc如何分配内存？

《虚拟地址空间大小分布》

进程在用户态时，只能访问用户空间内存；
只有进入内核态后，才可以访问内核空间的内存；

每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。进程切换到内核态后，可以方便地访问内核空间内存。

用户空间内存从低到高分布是6种不同地内存段：
- 代码段：包括二进制可执行代码
- 数据段：包括已初始化地静态变量和全局变量
- BSS段：包括未初始化地静态变量和全局变量
- 堆段：包括动态分配地内存，从低地址开始向上增长
- 文件映射段：包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关）；
- 栈段：包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是8MB。当然系统也提供了参数，以便我们自定义大小。
这六个内存段，堆和文件映射段的内存是动态分配的。使用C标准库的malloc或者mmap()就可以分别在堆和文件映射段动态分配内存。

malloc申请内存，有两种方式向操作系统申请内存：
- 一：通过brk()系统调用从堆分配内存：就是通过brk()函数将【堆顶】指针向高地址移动，获得新的内存空间；
- 二：通过mmap()系统调用在文件映射区域分配内存：通过mmap()系统调用中**【私有匿名映射】方式，在文件映射区分配一块内存**，也就是从文件映射区“偷”一块内存。
这两种方式怎么选择呢？

malloc源码默认定义阈值：
- 用户分配内存 $< 128 K B$ ，则通过brk()申请内存；
- 用户分配内存 $> 128 K B$ ，则通过mmap()申请内存；
- 二者分配的时候，返回给用户态的内存起始地址比进程的堆空间起始地址多16字节
malloc()分配的是虚拟内存。
- 如果分配后的虚拟内存没有被访问的话，虚拟内存不会映射到物理内存，就不会占用物理内存。只有在访问已分配的虚拟地址空间的时候，操作系统通过查页表，发现对应的页没有在物理内存中，会触发缺页中断，然后操作系统会建立虚拟内存和物理内存之间的映射关系
对于【malloc申请的内存，free是否内存后会归还操作系统吗？】
- malloc通过brk()方式申请的内存，不会把内存归还给操作系统，而是缓存在malloc的内存池中，待下次使用。
- malloc通过mmap()方式申请的内存，会把内存归还给操作系统，内存得到真正的释放。
为什么不全部使用mmap来分配内存？
- 因为mmap分配的内存每次释放都要归还给操作系统，然后每次再去申请，这样会进行大量的系统调用，浪费时间。再者，频繁使用mmap分配的内存的话，不仅每次都会发生运行态的切换**（用户带-》内核态-》用户态），还会发生缺页中断（在第一次访问虚拟地址后），这样CPU消耗较大**
- 而**brk()在下次申请内存的时候，直接从内存池取出对应内存块就行，而且这个内存块的虚拟地址与物理地址的映射关系还在，这样不仅减少系统调用的次数，也减少了缺页中断的次数。**
全部使用brk()：频繁使用malloc和free，对于小块内存，堆内出现越来越多不可用的碎片，会导致**“内存泄漏”**

因此，为了减少二者的缺点，就规定一个（ $128 K B$ ）的阈值

free()只传入一个内存地址，为啥能知道释放多大的内存？
- malloc返回给用户态的内存起始地址比进程的堆空间起始地址多16字节【用来保存内存块的描述信息，比如块的大小】
- free()执行时，free会对传入的内存地址向左偏移16字节，然后从这个16字节的分析出当前块的大小！

内存满了会发生什么？

如果没有空闲的物理内存，内核开始进行 回收内存的工作。

后台内存回收：在物理内存紧张的时候，会唤醒**kswapd内核线程来回收内存，这个回收内存的过程是异步的，不会阻塞进程的执行**。
直接内存回收：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是同步的，会阻塞进程的执行。

如果空闲的物理内存仍无法满足此次物理内存的申请，就会触发OOM（out of Memory）机制

哪些内存可以被回收？

文件页：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Cache）都叫做文件页。回收干净页的方式是直接释放内存，回收 脏页（被应用程序修改过，但还未写入磁盘的数据）的方式是先写回磁盘后再释放内存。
匿名页：这部分内存没有实际载体，比如堆栈数据。这部分内存很有可能会再次被访问，所以不能直接释放内存，回收的方式是通过Linux的Swap机制，Swap会把不常访问的内存先写到磁盘中，然后释放这些内存，给其他更需要的进程使用。

文件页和匿名页的回收都是基于LRU算法。LRU算法回收算法，实际上维护了active和inactive两个双向链表：

active_list 活跃内存页表链表，这里存放的是最近被访问过（活跃）的内存页；
inactive_list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；
越接近链表尾部，就表示内存页不常访问，在回收的时候就优先回收不活跃的内存。

内存回收的操作基本上都会发生磁盘I/O，如果回收内存的操作很频繁，磁盘I/O次数就很多，这个过程会影响系统的性能。但是对干净页的回收是直接释放内存，不会影响系统性能，所以尽量回收文件页的内存。

什么时候会触发`kswapd`内核线程回收内存？

内核定义了三个内存阈值（watermark，也称为水位），用来衡量当前剩余内存（pages_free）是否充裕或紧张：

页高阈值（pages_high）—— 页低阈值（pages_low）—内存压力大，此时kswapd会执行内存回收，直到剩余内存大于页高阈值，这是还是异步进行的— 页最小阈值（pages_min）此时直接触发内存回收，这时应用程序会被阻塞，因为二者关系是同步的

NUMA架构下的内存回收策略？

SMP和NUMA两个架构都是针对CPU的

SMP指：多个CPU处理器共享资源的电脑硬件架构，也就是每个CPU地位平等，他们共享相同的物理资源，包括总线、内存、IO、操作系统等。每个CPU访问内存所用的时间都是相同的，因此这种系统也被称为一致存储访问结构（UMA，Uniform Memory Access）

CPU处理器核数越来越高，多个CPU通过一个总线访问内存，这样总线的带宽压力会越来越大，同时每个CPU可用带宽也会减少，为解决这个问题，就引入了NUMA架构

NUMA，非一致性存储访问结构：它将每个CPU进行分组，每一组CPU用Node表示，一个Node包含多个CPU。每个Node有自己独立的资源，包括内存、IO等。每个Node之间通过互联模块总线（QPI）进行通信。所以每个Node的CPU都可以访问到整个系统的所有内存，但访问远端Node耗时更多。

在 NUMA 架构下，当某个 Node 内存不足时，系统可以从其他 Node 寻找空闲内存，也可以从本地内存中回收内存。

OOM(Out of memory)如何杀掉一个进程来释放空间的呢？

在Linux内核中又一个oom_badness()函数，他会把系统中可被杀掉的进程扫描一遍，并对每个进程打分，得分最高的进程会被首先杀掉；得分？

第一，进程已经使用的物理内存页面数
第二，每个进程的OOM校准值oom_score_adj。可以在设置 -1000 到 1000 之间的任意一个数值，调整进程被 OOM Kill 的几率。

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

什么是OOM？

内存溢出（Out of Memory）是指应用系统中存在无法回收的内存或使用的内存过多，最终使得程序运行要用到的内存大于能提供的最大内存。此时程序就运行不下去，系统会提示内存溢出

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

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

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

这就是传统LRU算法存在的问题，与其说避免这两个问题，不如说说怎么改进LRU算法

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

Redis的缓存淘汰算法则是通过实现LFU算法来避免【缓存污染】而导致缓存命中率下降的问题**（Redis没有预读机制）**

MySQL和Linux操作系统是通过改进LRU算法来避免【预读失效和缓存污染】而导致缓存命中率下降的问题。

Linux操作系统的缓存

在应用程序读取文件的数据的时候，Linux操作系统是会对读取的文件数据进行缓存的，会缓存在文件系统中的 Page Cache（页缓存），Page Cache属于内存空间中的数据，由于内存访问比磁盘访问快，Page Cache 起到了加速访问数据的作用
MySQL的缓存

MySQL的数组是存储在磁盘里的，为了提升数据库的读写性能，Innoddb存储引擎设计了一个缓存池（Buffer Pool），Buffer Pool 属于内存空间的数据
- 当读取数据时，如果数据位于Buffer Pool中，客户端就会直接读取Buffer Pool 中的数据，否则就再去磁盘中读取。
- 在修改数据时，首先是修改Buffer Pool中数据所在的页，然后将其设置为脏页，最后由后台线程将脏页写入到磁盘。

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

传统LRU算法思路：

当访问的页在内存里，就直接把该页对应得LRU链表节点移动到链表的头部。
当访问的页不在内存里，除了要把该页放入到LRU链表的头部，还要淘汰LRU链表末尾的页。

预读失败怎么办？

什么是预读机制？当前要读取的文件大小为3KB也会读取4KB，因为磁盘的基本读写单位为block（4KB）。操作系统出于空间局部性原理会把和当前要访问的数据相邻的数据也加载到内存，因为这些内存极有可能被访问到，这样可以减少磁盘I/O次数，提高系统磁盘I/O吞吐量。

这会有什么问题？
- 如果这些提前加载进来的页，没有被访问，就相当于预读工作白做，就是预读失败
- 如果使用传统的LRU算法，就会把【预读页】放到链表头部，当内存空间不够的时候，还需要把末尾淘汰掉。如果预读页一直不会被访问，就会出现不会被访问的预读页却占用了LRU链表前排的位置，而末尾淘汰的页，可能是热点数据，这回大大降低缓存命中率。
怎么解决？

让预读页停留在内存里的时间尽可能的短，让真正被访问的页才移动到LRU链表的头部，从而保证被读取的热点数据留在内存里的时间尽可能长。
- Linux操作系统实现了两个LRU链表：活跃LRU链表（active_list）和非活跃LRU链表（inactive_list）；
- MySQL的Innodb存储引擎是在一个LRU链表上划分2个区域：young区域和 old区域。
设计思想类似，都是将数据划分为了冷数据和热数据，然后分别进行LRU算法。

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

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

有这两个链表，预读页就只需要加入到inactive_list区域的头部，当页真正访问的时候，再插入到active _list的头部。如果预读页一直没有被访问，就会从 inactive_list移除。这两个链表之间，存在这降级和升级机制，从active_list淘汰的不能直接删掉，而是放到inactive_list；而预读页被访问会升级到active_list

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

young区域和 old区域都维护了一对 头尾指针，他们的占比不是一比一的关系，而是63：37的默认比例

划分这两个区域后，预读的页就需要加入到old区域的头部，当页真正访问的时候，才将页插入到young区域。

缓存污染怎么办？

什么是缓存污染？当批量读取数据时，由于数据被访问一次就被加入到活跃LRU链表中，之前缓存在链表中的热点数据会被淘汰，如果这些大量的只访问过一次的数据在很长一段时间都不会被访问的话，那么整个活跃LRU链表（或者young区域）就被污染了。

缓存污染的影响是很致命的，经常需要被访问的数据，由于缓存未命中，会产生大量的I/O，系统性能就会急剧下降。
怎么避免呢？
- Linux操作系统：在内存页被访问第二次的时候，才将页从inactive_list升级到active_list里。
- MySQL Innodb：在内存页被访问第二次的时候，并不会直接将该页从old区域升级到young区域，要进行停留在old区域的时间判断
  - 只有第二次的访问时间与第一次访问的时间超过1秒，该页就会从old区域升级到young区域
也就是提高进入active_list（或者young区域）的门槛，可以很好避免缓存污染带来的影响。

深入理解Linux虚拟内存管理

进程虚拟内存空间中的每一个字节都有与其对应的虚拟内存地址，一个虚拟内存地址表示进程虚拟内存空间中的一个特定的字节。

堆空间中地址的增长方向是从低地址到高地址。
在文件映射与匿名映射区的地址增长方向是从高地址向低地址增长。
栈空间中的地址增长方向是从高地址向低地址增长。

struct task_struct{//进程在内核中的描述符
    //进程id
    pid_t	pid;
    //用于标识线程所属的进程pid
    pid_t	tgid;
    //进程打开的文件信息
    struct files_struct		*files;
    //内存描述符表示进程虚拟地址空间
    struct mm_struct		*mm;
    .......
}

每个进程都有唯一的mm_struct结构体，也就是每个进程的虚拟地址空间都是独立，调用fork()创建进程时，会同时创建一个mm_struct。在copy_process函数中创建task_struct，并拷贝父进程相关资源到新进程的task_struct结构里。，包括拷贝父进程的虚拟内存空间mm_struct结构。所以子进程在新创建出来之后它的虚拟内存空间和父进程的虚拟内存空间一模一样，是直接拷贝来的

通过 $f or k ()$ 函数创建出来的子进程，它的虚拟内存空间以及相关页表相当于父进程虚拟内存空间的一份拷贝，直接从父进程中拷贝到子进程中。

子线程共享了父进程的虚拟内存空间，进程就变成了线程，是否共享地址空间几乎是进程与线程之间本质区别。线程对于Linux内核来说仅仅是一个共享特定资源的进程而已

父进程与子进程的区别，进程与线程的区别，以及内核线程与用户态线程的区别其实都是围绕着这个 `mm_struct` 展开的。

struct mm_struct{
    unsigned long task_size;
    unsigned long start_code,end_code,start_data,end_data;//代码段、数据段
    unsigned long start_brk,brk,start_stack;//堆、栈
    unsigned long arg_start,arg_end,env_start,env_end;//参数列表、环境变量
    unsigned long mmap_base;//内存映射去
    unsigned long total_vm;//进程虚拟内存空间中总共与物理内存映射的页的总数。
    unsigned long locked_vm;//被锁定不能换出的内存页总数
    unsigned long pinned_vm;//既不能换出也不能移动的内存页总数
    unsigned long data_vm;//数据段映射的内存页数目
    unsigned long exec_vm;//代码段中存放可执行文件的内存页数目
    unsigned long stack_vm;//栈中所映射的内存也数目
    ...省略...
}

内核是通过一个mm_struct结构的内存描述符来表示进程的虚拟内存空间，并通过task_size域划分用户态虚拟内存空间和内核态虚拟内存空间
虚拟内存区域可以映射到物理内存上，也可以映射到文件中，映射到物理内存上我们称之为匿名映射，映射到文件中我们称之为文件映射。

Linux虚拟内存空间整体布局

CPU从内存读取数据过程

CPU只会访问虚拟内存，在操作总线前，需要把虚拟内存地址转换为物理内存地址

首先CPU芯片中的总线接口会在总线上发起读事务（read transaction）。

CPU将物理内存地址A放到系统总线上。随后IO bridge将信号传递到存储总线上。
主存感受到存储总线上的地址信号并通过存储控制器将存储总线上的物理内存地址A读取出来。
存储控制器通过物理内存地址A定位到具体的存储器模块，从DRAM芯片中取出物理内存地址A对应的数据X。
存储控制器将读取到的数据X放到存储总线上，随后 IO brige 将存储总线上的数据信号转换为系统总线上的数据信号，然后继续沿着系统总线传递。
CPU芯片感受到系统总线上的数据信息，将数据从系统总线上读取出来并拷贝到寄存器中。

CPU向内存写入数据过程

首先，CPU芯片中的总线接口会向总线发起写事务。

CPU将要写入的物理内存地址A放入系统总线上。
通过IO bridge 的信号转换，将物理内存地址A传递到存储总线上。
存储控制器感受到存储总线上的地址信号，将物理内存地址A从存储总线上读取出来，并等待数据的到达。
CPU将寄存器中的数据拷贝到系统总线上，通过IO bridge的信号转换，将数据传递到存储总线上。
存储控制器感受到存储总线上的数据信号，将数据从存储总线上读取出来。
存储控制器通过内存地址A定位到具体的存储器模块，最后将数据写入存储器模块中的8个DRAM芯片中。

深入理解Linux物理内存管理

FLATMEM平坦内存模型

这块物理内存是连续的，物理地址也是连续的，划分出来的这一页一页的物理页必然也是连续的，并且每页的大小都是固定，所以用一个数组来组织这些连续的物理内存页 struct page 结构，其在数组中对应的下标即PFN。

内核中使用了一个mem_map的全局数组用来组织所有划分出来的物理内存页。mem_map全局数组的下标就是相应物理页对应的PFN

DISCONTIGMEM非连续内存模型

为了组织和管理不连续的物理内存，所以引入了DISCONTIGMEM非连续内存模型。

在该模型中，内核将物理内存从宏观上划分成一个一个的节点 node，每个node节点管理一块连续的物理内存。这样一来这些连续的物理内存页均被划归到了对应的 node 节点中管理，避免了内存空洞的造成的空间浪费。

SPARSEMEM稀疏内存模型

在上面的模型中，每个node都有一套完整的内存管理系统，如果node数目多的话，那这个开销就大了，为了对连续物理内存更细粒度的管理要求，为了能够更灵活地管理粒度更小的连续物理内存，SPARSEMEM稀疏内存模型就出现了。

该模型核心思想就是对粒度更小的连续内存块进行精细的管理，用于管理连续内存的单元被称作section。物理页大小为4K的情况下，section的大小为128M。

进程管理

进程的状态变迁

NULL->创建状态：一个新进程被创建时的第一个状态；
创建状态->就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；
就绪状态->运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给CPU正式运行该进程
运行状态->结束状态：当进程已经运行完成或出错时，会被操作系统做结束状态处理；
运行状态->就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行；
运行状态->阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；
阻塞状态->就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态；

如果有大量处于阻塞状态的进程，就会占用大量物理内存空间，所以在虚拟内存管理的操作系统中会把这些进程的物理内存空间换出到硬盘，随用随取，不用就存。那么这个操作过程就出现了另外两个状态，用来描述进程没有占用实际的物理内存空间的情况

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

导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还有：通过sleep让进程间歇性挂起，其工作原理是设置一个定时器，到期唤醒进程以及 用户希望挂起一个程序的执行，在Linux使用Ctrl+Z挂起进程

进程控制结构——进程控制块(process control block, PCB)

PCB是进程存在的唯一标识。包含以下信息

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

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

将所有处于就绪状态的进程链在一起，称为就绪队列；
把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；

线程

线程的优点：一个进程中可有多个线程；各个线程之间可以并发执行；各个线程之间可以共享地址空间和文件等资源；

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

***线程和进程

线程是调度的基本单位、进程则是资源拥有的基本单位。

进程就是系统中正在运行的一个应用程序，程序一旦运行就是进程、线程是资源分配处理器时间资源的基本单位。

二者区别：

因为进程拥有独立的堆栈空间和数据段，所以每当启动一个新的进程必须分配给它独立的地址空间，建立很多数据表来维护它的代码段、堆栈段和数据段，所以系统开销比较大。而线程拥有独立的堆栈空间，但是共享数据段，共享大部分数据，比进程更节俭，开销比较小，切换速度也比进程快。
进程的安全性比较高，因为进程之间相互独立，在保护模式下，一个进程的崩溃不会影响其他进程的运行，而一个线程死掉相当于整个进程死掉。
在通信上，进程间的通信机制很复杂，像管道、信号、消息队列、共享内存、套接字等通信机制，而线程拥有共享数据段，所以通信起来比较方便

上下文切换

CPU上下文：CPU寄存器和程序计数是CPU在运行任何任务前，所必须依赖的环境，这些环境叫做CPU上下文。
CPU上下文切换：就是先把前一个任务的CPU上下文（CPU寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。
进程上下文切换不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。
线程上下文切换：
1. 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文一样；
2. 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

上下文切换的肯定是开销越小越好

发生在改变进程状态的时候

线程的实现

用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
- 优点：TCB列表，可以跟踪记录各个线程状态信息（PC、栈指针、寄存器），TCB由用户级线程库函数来维护，可用于不支持线程技术的操作系统； 用户线程的切换也是由线程库函数来完成的，不需要用户态与内核态的切换，速度快；
- 缺点：当一个线程发起系统调用而阻塞，操作系统无法参与，也就会导致进程中所有线程都不能执行；其他用户态线程无法打断正在运行的线程；在多线程中，由于时间片分给进程的，所以每个线程得到的时间并不多，执行会慢一些。
内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；
- 线程对应的 TCB 是放在操作系统里的，所以线程的创建、终止和管理交给操作系统负责
- 优点：某个内核线程发起系统调用被阻塞不影响其他内核线程的运行； 时间片分配给线程，多线程的进程获得更多CPU运行时间
- 缺点：需要内核维护进程和线程的上下文切换；通过系统调用的方式管理线程，系统开销比较大。
轻量级进程（LightWeight Process）：在内核中来支持用户线程；

用户线程和内核线程是多对一、一对一、多对多的关系

用户线程是基于用户态的线程管理库实现的，**线程控制块（Thread Control Block，TCB）**同样也是。

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

轻量级进程

轻量级进程（Light-weight process，LWP）是内核支持的用户线程，一个进程可有一个或多个LWP，每个LWP是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持，而且LWP是由内核管理并像普通进程一样被调度。

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

调度！！！

选则一个进程运行这一功能实在操作系统中完成的，通常称为 调度程序（scheduler）

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

在状态发生变化的时候，操作系统需要考虑是否要让新的进程给CPU运行？

因此，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断，把调度算法分为两类：
- 非抢占式调度算法：挑选一个进程，然后让该进程运行直到被阻塞或进程退出，才调用另外的进程，就是不用理会时钟中断。
- 抢占式调度算法：挑选一个进程，只运行某段时间，时间结束，调度程序就从就绪队列挑选另外一个进程。抢占式调度处理，需要在时间间隔末尾发生时钟中断，便于CPU控制返回给调度程序进行调度，也就是时间片机制

共有五种调用原则：

CPU利用率：调度程序应确保CPU是始终匆忙的状态，可提高CPU的利用率
系统吞吐量：吞吐量表示的是单位时间内CPU完成进程的数量，长作业的进程会占用较长的CPU资源，因此会降低吞吐量，相反短作业的进程会提升系统的吞吐量；
周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准

调度算法

**先来先服务：**非抢占式，每次从就绪队列最先进入队列的进程开始，直到它退出或阻塞才会继续执行下一个。对长作业有利，适合CPU繁忙型作业的系统，不适合I/O繁忙型作业的系统
最短作业优先：优先选择运行时间最短的进程来运行。对长作业极其不利
高响应比优先： $\frac{等待时间+要求服务时间}{要求服务时间}$ ，但要求服务时间是不可预估的，所以是个理想型调度算法。
时间片轮转：最古老、最简单、最公平的算法，每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中允许
最高优先级：肯定是越重要的进程越提前进行，所以可以从就绪队列中选择优先级最高的进程进行运行。优先级被分为静态优先级（在创建进程时就确定了优先级）和动态优先级（跟随进程的动态变化而调整，就是随着时间的推移要增加等待进程的优先级）
1. 也有非抢占式和抢占式之分！就是当就绪队列出现更高优先级的时候，当前进程是否挂起。
多级反馈队列：时间片轮转和最高优先级算法的综合发展
- 多级：表示多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
- 反馈：表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列
工作流程：其实就是等待时间越长、优先级越高、受到服务时间也就越长
1. 设置多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
2. 新的进程会被放入到第一级队列（最高优先级）的末尾，按先来先服务的原则排队等待调度，如果在第一级队列规定的时间片没有运行完成，则将其转入到第二级队列的末尾。
3. 当较高优先级的队列为空，才会去调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行。

进程间通信方式

每个进程的用户地址空间都是独立的，所以进程间通信必须要通过内核。Linux内核提供了如下机制：

管道：实际上就是内核里面的一串缓存。管道传输数据是单向的，管道的效率低，不适合进程频繁交换信息。
```
ps auxf | grep mysql   将前一个命令的输出，作为后面的输入
mkfifo myPipe	创建并命名管道
echo "hello" > myPipe	将数据写进管道
cat < myPipe	读取管道的数据
```
shell通过 | 匿名管道将多个命令连接起来，其实就是创建了多个子进程。
- 对于匿名管道，它的通信范围是存在父子关系的进程
- 对于命名管道，它可以在不相关的进程间相互通信
管道的生命周期是伴随进程的。
消息队列：A进程把数据放到对应的消息队列后就可以正常返回，B进程需要的时候再进去取数据就可以了。
- 消息队列是保存在内核中的消息链表，生命周期随内核，释放或者关闭操作系统才会消失
- 缺点：通信不及时、附件有大小限制，再者，消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销。
共享内存：就是拿出一块虚拟地址空间出来，映射到相同的物理内存中。
1. 优点：一个进程写入的东西，另外一个进程马上就能看到，不需要进行拷贝传递
信号量：信号量是一个整形计数器，主要用于实现进程间的互斥与同步，而不是用于缓存间通信的数据，就是为了防止多进程竞争共享资源，就类似于锁似的，在任意时刻只能被一个进程访问到，包括两个原子操作：
- P操作：把信号量减去1。如果信号量 < 0，表明资源已被占用，进程需要阻塞等待；>= 0表明资源可使用，进程可正常执行。
- V操作：把信号量加上1。如果信号量<=0，表明当前有阻塞中的进程，于是会将该进程唤醒（其实就是上一个进程完成了，轮到下一个了）；> 0，表明当前没有阻塞中的进程；
P操作是在进入共享资源之前，V操作是在离开共享资源之后，这两个操作必须成对出现。
1. 如果是两个进程互斥访问共享内存，初始化信号量为1，可以保证共享内存任何时刻只有一个进程在访问。
2. 如果进程A是负责生产数据，B负责读取数据，二者是相互合作的，初始化信号量为0，给进程A后面加上V操作，进程B前面加上P操作，这样只有A完成了信号量才会 >=0。
信号初始化为1，代表互斥信号量；信号初始化为0，代表同步信号量
信号：对于异常情况下的工作模式，需要用【信号】来通知进程。

信号是进程间通信机制中唯一的异步通信机制。因为可以在任何时候发送信号给某一进程，一旦有信号产生，用户进程对信号的处理方式有以下几种：
1. 执行默认操作：Linux对每种信号都规定了默认操作，比如SIGTERM终止进程。
2. 捕捉信号：为信号定义一个处理函数，信号发生，执行函数
3. 忽略信号：不想处理就忽略。
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：原本用来指定通信协议，进本废弃，一般默认为0

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

实现TCP字节流通信：AF_INET和SOCK_STREAM；
实现UDP数据报通信：AF_INET和SOCK_DGRAM；
实现本地进程通信：**【本地字节流】AF_LOACL和SOCK_STREAM；【本地数据报】**AF_LOCAL和SOCK_DGRAM。

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

服务端和客户端初始化socket，得到文件描述符；
服务端调用bind，将绑定在IP地址和端口
服务端调用listen，进行监听；
服务端调用accept，等待客户端连接；
客户端调用connect，向服务器的地址和端口发起请求连接；
服务端accept返回用于传输的socket的文件描述符；
客户端调用write写入数据，服务端调用read读取数据；
客户端断开连接时，会调用close，那么服务端read读取数据的时候，就会读取到EOF，待处理完数据后，服务端调用close，表示连接关闭。

服务端调用accept时，连接成功了会返回一个已完成连接的socket，后续用来传输数据。所以共两个socket，一个叫做 监听socket 一个叫做已完成连接socket

对于UDP，每次通信只需要调用sendto 和 recvfrom，都要传入主机的IP地址和端口

并发、同步、异步、阻塞、非阻塞

并发（concurrency）：在操作系统中，是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行。其中两种并发关系分别是同步和互斥。

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
**同步：**是指在互斥的基础上，通过其他机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

异步：异步和同步是相对的，同步就是顺序执行，执行完一个再执行下一个，需要等待、协调运行。异步就是彼此独立，在等待某事件的过程中继续做自己的事，不需要等待这一事件完成后再工作。线程就是实现异步的一个方式。异步是让调用方法的主线程不需要同步等待另一线程的完成，从而可以让主线程干其他的事情。
阻塞和非阻塞是针对于进程在访问数据的时候，根据IO操作的就绪状态来才需不同的方式。是一种读取或者写入操作函数的实现方式。阻塞方式下读取或者写入函数将一直等待，而非阻塞方式下，读取或者写入函数会立即返回一个状态值

IO模型分为：同步阻塞、同步非阻塞、异步阻塞、异步非阻塞

同步阻塞IO：用户进程发起一个IO操作以后，必须等待IO操作的完成，只有当真正完成了IO操作以后，用户进程才能进行。
同步非阻塞IO：用户进程发起一个IO操作以后可返回做其他事情，但是用户进程需要时不时的询问IO操作是否就绪，这就要求用户进程不停的去询问，从而引起不必要的CPU资源浪费。应用发起一个IO操作以后，使用阻塞select系统调用来等待I/O可用的通知。
异步阻塞IO：应用发起一个IO操作以后，不等待内核IO操作的完成，等待内核完成IO操作以后会通知应用程序，这其实就是同步和异步最关键的区别。同步必须等待或者主动去询问IO是否完成。
异步非阻塞IO：用户进程只需要发起一个IO操作后立即返回，等IO操作真正的完成以后，应用程序会得到IO操作完成的通知，此时用户进程只需要对数据进行处理就好，不需要进行实际的IO读写操作因为真正的IO读取或者写入操作已经由内核完成了。

同步和异步是对应的，它们是线程之间的关系，两个线程之间要么是同步的，要么是异步的。

阻塞与非阻塞是对同一个线程来说的，在某个时刻，线程要么处于阻塞，要么处于非阻塞。

阻塞是使用同步机制的结果，非阻塞则是使用异步机制的结果。

线程同步与阻塞的关系？同步一定阻塞吗？阻塞一定同步吗？

异步必定是非阻塞的。同步才有阻塞和非阻塞之分。

同步：执行一个操作之后，等待结果，然后才继续执行后续的操作。
异步：执行一个操作后，可以去执行其他的操作，然后等待通知再回来执行刚才没有执行完的操作。
阻塞：进程给CPU传达一个任务之后，一直等待CPU处理完成，然后才执行后面的操作。
非阻塞：进程给CPU传达任务后，继续处理后续的操作，隔断时间再来询问之前的操作是否完成。这样的过程也叫轮询。

乐观锁与悲观锁

互斥锁、自旋锁、读写锁都属于悲观锁。

悲观锁：做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。

乐观锁：做事比较乐观，它认为冲突的概率很低。工作方式：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程再修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。所以乐观锁全程并没有加锁，所以叫做无锁编程

最常见的是互斥锁，互斥锁加锁失败，会用线程切换来应对，当加锁失败的线程再次加锁成功后的这一过程，会有两次线程上下文切换的成本，性能损耗比较大。

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img

一个进程最多可以创建多少个线程？

32位系统，用户态的虚拟空间只有3G，如果创建线程时分配的栈空间是10M，那么一个进程最多只能创建300个左右的线程。
64位系统，用户态的虚拟空间大到有128T，理论上不会受虚拟内存大小的限制，而会受到系统的参数或性能限制

操作系统学习2025.04.02-2025.04.08