OPERATING_SYSTEM.md

Index

操作系统
 1. 硬件结构
  1.1. 冯-诺伊曼模型-计算机硬件
   1.1.1. 内存
   1.1.2. 中央处理器
   1.1.3. 总线
   1.1.4. 输入、输出设备
  1.2. 线路位宽与 CPU 位宽
  1.3. 指令
 2. 操作系统
  2.1. 内核
  2.2. 核心态与用户态
 3. 内存管理
  3.1. 虚拟内存
  3.2. 内存分段
  3.3. 内存分页
   3.3.1. 多级分表
   3.3.2. TLB
  3.4. 段页式内存管理
  3.5. Linux 内存管理
  3.6. 两种分配内存的调用
 4. 进程管理
  4.1. 进程
  4.2. 线程
  4.3. 线程与进程比较
  4.4. 处理器调度
  4.5. 经典同步问题
   4.5.1. 生产者-消费者问题
   4.5.2. 读者-写者问题
计算机组成原理
 1. 局部性原理
中间件设计资料

操作系统[Top]

参考资料：大量参考=>小林coding-图解系统介绍

硬件结构[Top]

冯-诺伊曼模型-计算机硬件[Top]

计算机的硬件(或称为冯-诺伊曼模型)组成：

• 主机部分：运算器、存储器、控制器
• 外设部分：输入设备、输出设备

没有配置软件的计算机成为裸机，裸机仅仅构成了计算机系统的硬件基础。
计算机硬件、软件以及软件的各个部分是一种层次关系。硬件在最底层，其上层是操作系统。通过操作系统供的资源管理功能和方便用户使用的各种功能，把裸机改造成功能更加强大、使用更方便的机器(通常称为虚拟机)。

各种实用程序和应用程序在操作系统之上，这些程序都在均以操作系统作为支撑，并向用户提供各种服务。

内存[Top]

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

计算机最小的存储单位是字节(byte)，1 字节等于 8 位(8 bit)。每一个字节都对应一个内存地址。

内存的地址是从 0 开始编号的，然后自增排列，最后一个地址为内存总字节数 - 1，这种结构好似我们程序里的数组，所以内存的读写任何一个数据的速度都是一样的。

中央处理器[Top]

央处理器也就是我们常说的 CPU，32 位和 64 位 CPU 最主要区别在于一次能计算多少字节数据：

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

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

之所以 CPU 要这样设计，是为了能计算更大的数值，如果是 8 位的 CPU，那么一次只能计算1个字节(8bit) 0~255 范围内的数值，这样就无法一次完成计算 10000 * 500 ，于是为了能一次计算大数的运算，CPU 需要支持多个 byte 一起计算，所以 CPU 位宽越大，可以计算的数值就越大，比如说 32 位 CPU 能计算的最大整数是 4294967295。

CPU 内部还有一些组件，常见的有寄存器、控制单元和逻辑运算单元等。其中，控制单元负责控制 CPU 工作，逻辑运算单元负责计算，而寄存器可以分为多种类，每种寄存器的功能又不尽相同。

CPU 中的寄存器主要作用是存储计算时的数据，你可能好奇为什么有了内存还需要寄存器？原因很简单，因为内存离 CPU 太远了，而寄存器就在 CPU 里，还紧挨着控制单元和逻辑运算单元，自然计算时速度会很快。

常见的寄存器种类：

• 通用寄存器，用来存放需要进行运算的数据，比如需要进行加和运算的两个数据。
• 程序计数器，用来存储 CPU 要执行下一条指令「所在的内存地址」，注意不是存储了下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令的地址。
• 指令寄存器，用来存放程序计数器指向的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里。

总线[Top]

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

• 地址总线，用于指定 CPU 将要操作的内存地址；
• 数据总线，用于读写内存的数据；
• 控制总线，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；

当 CPU 要读写内存数据的时候，一般需要通过下面这三个总线：

1. 首先要通过「地址总线」来指定内存的地址；
2. 然后通过「控制总线」控制是读或写命令；
3. 最后通过「数据总线」来传输数据；

输入、输出设备[Top]

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

线路位宽与 CPU 位宽[Top]

数据是如何通过线路传输的呢？其实是通过操作电压，低电压表示 0，高压电压则表示 1。

如果构造了高低高这样的信号，其实就是 101 二进制数据，十进制则表示 5，如果只有一条线路，就意味着每次只能传递 1 bit 的数据，即 0 或 1，那么传输 101 这个数据，就需要 3 次才能传输完成，这样的效率非常低。 这样一位一位传输的方式，称为串行，下一个 bit 必须等待上一个 bit 传输完成才能进行传输。

为了避免低效率的串行传输的方式，线路的位宽最好一次就能访问到所有的内存地址。

CPU 要想操作的内存地址就需要地址总线：

• 如果地址总线只有 1 条，那每次只能表示 「0 或 1」这两种地址，所以 CPU 能操作的内存地址最大数量为 2（2^1）个（注意，不要理解成同时能操作 2 个内存地址）；
• 如果地址总线有 2 条，那么能表示 00、01、10、11 这四种地址，所以 CPU 能操作的内存地址最大数量为 4（2^2）个。

那么，想要 CPU 操作 4G 大的内存，那么就需要 32 条地址总线，因为 2 ^ 32 = 4G。

对于 64 位 CPU 就可以一次性算出加和两个 64 位数字的结果，因为 64 位 CPU 可以一次读入 64 位的数字，并且 64 位 CPU 内部的逻辑运算单元也支持 64 位数字的计算。 但是并不代表 64 位 CPU 性能比 32 位 CPU 高很多，很少应用需要算超过 32 位的数字，所以如果计算的数额不超过 32 位数字的情况下，32 位和 64 位 CPU 之间没什么区别的，只有当计算超过 32 位数字的情况下，64 位的优势才能体现出来。

指令[Top]

流水线的方式来执行指令: Fetch -> Decode -> Execution -> Store

指令周期（Instruction Cycle）：CPU 的工作就是一个周期接着一个周期，周而复始。

四个阶段的具体含义：

1. CPU 通过程序计数器读取对应内存地址的指令，这个部分称为 Fetch（取得指令）；
2. CPU 对指令进行解码，这个部分称为 Decode（指令译码）；
3. CPU 执行指令，这个部分称为 Execution（执行指令）；
4. CPU 将计算结果存回寄存器或者将寄存器的值存入内存，这个部分称为 Store（数据回写）；

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

取指令的阶段，我们的指令是存放在存储器里的，实际上，通过程序计数器和指令寄存器取出指令的过程，是由控制器操作的；
指令的译码过程，也是由控制器进行的；
指令执行的过程，无论是进行算术操作、逻辑操作，还是进行数据传输、条件分支操作，都是由算术逻辑单元操作的，也就是由运算器处理的。但是如果是一个简单的无条件地址跳转，则是直接在控制器里面完成的，不需要用到运算器。

指令的执行速度

程序CPU的运行时间 = CPU 时钟周期数（CPU Cycles） * 时钟周期时间（Clock Cycle Time）

时钟周期时间：就是CPU主频，主频越高说明CPU的工作速度就越快。2.4GHz就是电脑的主频，时钟周期时间就是 1/2.4G。

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

• 指令数：表示执行程序所需要多少条指令，以及哪些指令。这个层面是基本靠编译器来优化。
• 每条指令的平均时钟周期数 CPI：表示一条指令需要多少个时钟周期数，现代大多数 CPU 通过流水线技术（Pipeline），让一条指令需要的 CPU 时钟周期数尽可能的少；
• 时钟周期时间：表示计算机主频，取决于计算机硬件。

操作系统[Top]

操作系统是裸机上的第一层软件，是对硬件功能的首次扩充。 引入操作系统的目的：

• 提供一个计算机用户和计算机硬件系统之间的接口，使计算机易于使用。
• 有效的控制和管理计算机系统中的中硬件和软件资源，使之得到更有效的利用。
• 合理地组织计算机系统的工作流程，以改善系统性能。

操作系统的特征：

1. 并发性：
   • 并行性：指两个或多个事件在同一时刻发生。宏观上在一段时间内有多道程序同时运行，但单处理器其实是交替运行，故微观上是交替执行。
   • 并发性：指两个或多个事件在同一事件间隔内发生。如哲学家思考和用餐是可以同时进行的，即两个任务并行执行。
2. 共享性。资源共享是指系统中的硬件和软件不再为某个程序所独占，而是供多个用户共同使用的。
   • 互斥共享：系统中可供共享的某些资源，一段时间内只能供一个作业使用。如打印机、队列等。
   • 同时访问：系统中另一类资源如磁盘、可重入代码，可以供多个作业同时访问。

   并发和共享是操作系统最基本的特征，二者互为存在的条件。一方面，资源共享是以程序并发执行为条件的。另一方面，若系统不能对共享资源进行有效管理，会影响到程序的并发执行。

3. 虚拟性：操作系统中，虚拟指的是一个物理上的实体变为若干个逻辑上的对应物，前者是实际存在的，而后者是虚拟的。
4. 异步性

操作系统基本功能

1. 处理器管理
2. 存储器管理
3. 设备管理
4. 文件管理
5. 用户接口

内核[Top]

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

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

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

对于内核的架构一般有这三种类型：

• 宏内核，包含多个模块，整个内核像一个完整的程序；
• 微内核，有一个最小版本的内核，一些模块和服务则由用户态管理；微内核架构的内核只保留最基本的能力，比如进程调度、虚拟机内存、中断等，把一些应用放到了用户空间，比如驱动程序、文件系统等。
• 混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；

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

Linux 的内核设计是采用了宏内核，Window 的内核设计则是采用了混合内核。 这两个操作系统的可执行文件格式也不一样， Linux 可执行文件格式叫作 ELF，Windows 可执行文件格式叫作 PE。

内核是怎么工作的？

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

• 内核空间，这个内存空间只有内核程序可以访问；
• 用户空间，这个内存空间专门给应用程序使用；

核心态与用户态[Top]

用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间。因此，当程序使用用户空间时，我们常说该程序在用户态执行，而当程序使内核空间时，程序则在内核态执行。 应用程序如果需要进入内核空间，就需要通过系统调用。

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

为了避免操作系统及其关键数据(如PCB等)收到用户程序有意或无意的破坏，通常将处理器的执行状态分为两种：核心态和用户态。

• 核心态(管态、系统态)：是操作系统管理程序执行时机器所处的状态。具有较高的权限，能执行包括特权指令等一切的指令，能访问所有寄存器和存储区。
• 用户态(目态)：是用户程序执行时机器所处的状态，具有较低特权的执行状态，它只能执行规定的指令，只能访问指定的寄存器和存储区。

特权指令：只能由操作系统内核部分使用，不允许用户直接使用的指令，如I/O指令、设置中断屏蔽指令、清内存指令、存储保护指令和设置时钟指令。

用户态程序不能直接调用核心态程序，而是通过执行访问核心态的命令，引起中断，由中断系统传入操作系统相关的程序，例如在系统调用时，由用户态转核心态。

内核的指令操作工作在核心态，主要以下几个方面：

1. 时钟管理。向用户提供标准的系统时间。通过时钟中断的管理，可以实现进程的切换，如时间片轮转调度。
2. 中断机制。中断机制中，只有一小部分属于内核，负责保护和恢复中断现场的信息，转移控制权到相关的处理程序中。(键盘鼠标的输入、进程的管理和调度、设备驱动、文件访问)
3. 原语。原语是一些关闭中断的公用小程序。
   • 处于操作系统最底层，是最接近硬件的部分。
   • 程序执行具有原子性。
   • 这些程序的运行时间较短，调用频繁。
4. 系统控制的数据结构及处理。如进程控制块、缓存区、内存分配表。

系统调用(System call):系统调用把用户程序的请求传到内核，调用相应的内核函数完成所需的处理，并将处理结果返回给对应的应用程序。

操作系统提供的系统调用通常包括：进程管理、文件系统控制(文件读写操作和文件系统操作)、系统控制、内存管理、网络控制、socket控制、用户管理及进程间通信(信号、消息、管道、信号量和共享内存)

内存管理[Top]

虚拟内存[Top]

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

单片机的 CPU 是直接操作内存的物理地址。常见的单片机程序就是跑马灯了，通过控制高低电平，循环及等待进而控制LED灯的亮暗。

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

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

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

于是，这里就引出了两种地址的概念：

• 我们程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
• 实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）。

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存。

操作系统是管理虚拟地址与物理地址，主要有两种方式，分别是内存分段和内存分页

内存分段[Top]

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

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

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

分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址。但它也有一些不足之处：

• 第一个就是内存碎片的问题。
• 第二个就是内存交换的效率低的问题。

存在两部分的内存碎片

• 外部内存碎片，也就是产生了多个不连续的小物理内存，导致新的程序无法被装载；
• 内部内存碎片，程序所有的内存都被装载到了物理内存，但是这个程序有部分的内存可能并不是很常使用，这也会导致内存的浪费；

解决外部内存碎片的问题就是内存交换:
可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。
这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。

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

对于多进程的系统来说，用分段的方式，内存碎片是很容易产生的，产生了内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。

内存分页[Top]

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

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

当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点

虚拟地址与物理地址之间通过页表来映射
页表是存储在内存里的，内存管理单元(MMU)就做将虚拟内存地址转换成物理地址的工作。

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

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

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

• 换出(Swap Out): 如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上。
• 换入(Swap In): 将从内存页面释放而暂存在硬盘上的数据，重新加载进来。

内存分页相比内存分段好处:

1. 对于需要内存交换的情况，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。
2. 分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。

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

多级分表[Top]

对于一个内存地址转换，简单的三个步骤总结：

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

简单分页管理的缺陷？ 在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。
这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。
那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

多级页表(Multi-Level Page Table)
在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。
我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。

进一步节省内存方案：如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。

做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

• 全局页目录项 PGD(Page Global Directory)
• 上层页目录项 PUD(Page Upper Directory)
• 中间页目录项 PMD(Page Middle Directory)
• 页表项 PTE(Page Table Entry)

TLB[Top]

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

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

TLB(Translation LookAside Buffer): 在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，通常称为页表缓存、转址旁路缓存、快表等。

在 CPU 芯片里面，封装了内存管理单元（Memory Management Unit）芯片，它用来完成地址转换和 TLB 的访问与交互。 有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。

段页式内存管理[Top]

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

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

1. 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
2. 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页； 这样，地址结构就由段号、段内页号和页内位移三部分组成。

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

段页式地址变换中要得到物理地址须经过三次内存访问：

• 第一次访问段表，得到页表起始地址；
• 第二次访问页表，得到物理页号；
• 第三次将物理页号与页内位移组合，得到物理地址。

Linux 内存管理[Top]

Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制。 这主要是Intel 处理器发展历史导致的

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间（32 位环境下），也就是所有的段的起始地址都是一样的。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间（虚拟地址），这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。

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

看看用户空间分布的情况，以 32 位系统为例。其中用户态的分布：代码段、全局变量、BSS、函数栈、堆内存、映射区。

两种分配内存的调用[Top]

C 库里的函数malloc()，用于动态分配内存。malloc 申请内存的时候，会有两种方式向操作系统申请堆内存。

1. 通过 brk() 系统调用从堆分配内存。类似与碰撞指针，直接用指针移位表示内存占用。
2. 通过 mmap() 系统调用在文件映射区域分配内存；

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

• malloc 通过 brk() 方式申请的内存，free 释放内存的时候，并不会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用；
• malloc 通过 mmap() 方式申请的内存，free 释放内存的时候，会把内存归还给操作系统，内存得到真正的释放。

mmap与brk分配对比：

mmap 分配的内存每次释放的时候，都会归还给操作系统，于是每次 mmap 分配的虚拟地址都是缺页状态的，然后在第一次访问该虚拟地址的时候，就会触发缺页中断。 也就是说，频繁通过 mmap 分配的内存话，不仅每次都会发生运行态的切换，还会发生缺页中断（在第一次访问虚拟地址后），这样会导致 CPU 消耗较大。

brk的分配方式，调用在堆空间申请内存的时候，由于堆空间是连续的，所以直接预分配更大的内存来作为内存池，当内存释放的时候，就缓存在内存池中。
等下次在申请内存的时候，就直接从内存池取出对应的内存块就行了，而且可能这个内存块的虚拟地址与物理地址的映射关系还存在，这样不仅减少了系统调用的次数，也减少了缺页中断的次数，这将大大降低 CPU 的消耗。
brk的分配方式问题在于，如果申请的空间没办法复用，那么将会导致堆内将产生越来越多不可用的碎片，导致“内存泄露”。

进程管理[Top]

进程[Top]

进程：在计算机操作系统中，进程是资源分配的基本单元，也是独立运行的基本单元。

进程特征：

1. 动态性：进程是程序在处理器上的一次执行过程，过程是动态的。
2. 并发性：多个进程在内存同时存在，并可以并发执行。
3. 独立性：进程是资源分配的基本单元，也是独立运行的基本单元。
4. 异步性
5. 结构特征：为了描述和记录进程的运动变化过程，为每个进程分配一个进程控制快(PCB,process control block)，每个进程都由程序段、数据段和一个进程控制块组成。

进程的组成：

1. 进程控制块(PCB)：每个进程均有一个PCB，是一个既能标识进程存在、又能刻画执行瞬间特征的数据结构。
2. 程序段：进程中能被调度程序调度到CPU上执行的程序代码段。
3. 数据段
4. 进程标识符(PID)：区别系统内其他进程
5. 进程状态
6. 进程优先级
7. CPU现场保护区：当进程因某种原因释放处理器时，CPU现场信息(如指令计数器、状态寄存器、通用寄存器等)被保存在PCB的该区域中，以便重新获得处理器后继续执行
8. 通信信息：和其他进程的通信情况
9. 家族信息：子进程
10. 占有资源清单

进程状态：就绪状态、执行状态、阻塞状态、创建状态、结束状态

线程[Top]

线程是进程内一个相对独立的、可调度的执行单元。线程基本上不拥有资源，只拥有在运行时必不可少的资源(如程序计数器、一组寄存器和栈)，但它可以和其他线程共享进程拥有的全部资源。

线程的实现：

1. 内核级线程：依赖于内核，由操作系统内核完成创建和撤销工作的线程。内核维护进程和线程的上下文信息并完成线程切换工作。

   一个内核级线程由于I/O操作而阻塞时，不会影响其他线程的运行。这时，处理器时间片分配的对象为线程。

2. 用户级线程：不依赖于操作系统核心，由应用程序利用线程库提供创建、同步、调度和管理线程的函数来控制线程。

   用户级线程维护由应用程序完成，内核不需要了解用户级线程存在。用户级线程切换不需要内核特权，通常应用程序的线程调度使用非抢占式或更简单的规则。这时候处理器的时间片是分配给进程的。

多线程模型：

多对一模型：多个用户级线程映射到同一个内核线程。

• 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小、效率高
• 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并发运行

多个用户线程对应一个内核线程,该模型的线程管理是由用户空间的线程库来完成的,因此效率更高,并且高效的上下文切换和几乎无限制的线程数量.不过,如果一个线程执行阻塞系统调用,那么整个进程将会阻塞.再者,因为任一时间只有一个线程可以访问内核,所以多个线程不能并行运行在多处理核系统上.

一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

• 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可以在多核处理机下并行执行
• 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

每个用户线程对应一个内核线程,该模型在一个线程执行阻塞系统调用时,能够允许另一个线程继续执行,所以对于IO密集型的场景,CPU、磁盘IO、网卡等资源利用率还是非常友好的,提供了更好的并发功能.但是对于CPU计算密集型的,会导致上下文切换,结合上面内核线程的劣势.
Java的内存模型就是一对一模型

多对多模型：n个用户级线程映射到m个内核级线程。每个用户进程对应m个内核级线程。

• 优点：克服了多对一模型并发度不高的缺点，又可服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

多个用户线程对应多个内核线程,使得库和操作系统都可以管理线程,用户线程由运行时库调度器管理,内核线程由操作系统调度器管理,可运行的用户线程由运行时库分派并标记为准备好执行的可用线程,操作系统选择用户线程并将它映射到可用内核线程.

线程与进程比较[Top]

• 拥有资源：进程为拥有系统资源的基本单元，而线程不拥有系统资源，但是线程可以访问隶属进程的系统资源
• 并发性：进入线程的操作系统，不仅进程可以并发，而且统一进程的线程也可以并发。系统的并发度更高，大大提高了系统的吞吐量。
• 调度：统一进程中的线程切换不会引起进程切换，而不同进程的线程切换会引起进程切换。
• 系统开销：
  • 创建或撤销开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。操作系统所付出的代价远大于创建或撤销线程是的开销。
  • 切换开销：进程切换时，涉及整个当前进程CPU环境的保存以及新进程的CPU环境的设置。而线程上下文的切换，只需要保存和设置少量寄存器的内容。多线程的同步和通信因为共享同一进程，甚至无需操作系统干预。

处理器调度[Top]

• 高级调度：即作业调度，按照一定策略将选择磁盘上的程序装入内存，并建立进程。
• 中级调度：即交换调度，按照一定策略在内外存之间进行数据交换。
• 低级调度：即CPU调度（进程调度），按照一定策略选择就绪进程，占用cpu执行。

调度基本原则：

1. CPU利用率
2. 系统吞吐量：单位时间内CPU完成的作业数量。
3. 响应时间：多个用户对系统进行操作，都要求在一定的时间内得到响应。
4. 周转时间：作业从提交到完成的时间间隔

调度算法：

1. 先来先服务调度算法(first-come first-serverd,FCFS)
2. 短作业优先调度算法(shortest job first,SJF) : 把处理器分配给最快完成的作业，会导致长作业饿死。
3. 优先级调度算法：确定优先级进行调度，调度方式还可以分为抢占和非抢占的调度方式
4. 时间片轮转调度算法：一个进程在一个时间片未执行完毕，插入到队尾等待，循环直到处理完成
5. 高响应比优先算法(highest response ratio first,HSRF)：通过设置响应比公式：响应比=(作业等待时间+估计运行时间)/估计运行时间，解决长作业饿死问题
6. 多级队列调度算法：多个队列每个队列使用一种调度算法
7. 多级反馈队列调度算法：时间片轮转调度算法和优先级调度算法的综合，动态调整队列优先级和时间片大小。进程所在队列的优先级越高时间片越小。可兼顾多方面的系统目标，如为提高系统吞吐量和缩短平均响应周期而照顾端线程。

适用于作业调度的算法：先来先服务调度算法、短作业优先调度算法、优先级调度算法、高响应比优先算法 适用于进程调度的算法：先来先服务调度算法、短作业优先调度算法、优先级调度算法、时间片轮转调度算法、多级队列调度算法、多级反馈队列调度算法

经典同步问题[Top]

生产者-消费者问题[Top]

生产者-消费者问题(Producer-consumer problem)，也称有限缓冲问题(Bounded-buffer problem)，是一个多线程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

相关问题点：

• 在缓冲区为空时，消费者不能再进行消费
• 在缓冲区为满时，生产者不能再进行生产
• 在一个线程进行生产或消费时，其余线程不能再进行生产或消费等操作，即保持线程间的同步
• 注意条件变量与互斥锁的顺序

读者-写者问题[Top]

计算机组成原理[Top]

局部性原理[Top]

// TODO 计算机组成原理：局部性原理

中间件设计资料[Top]

通常在大部分组件设计时，往往会选择一种主要介质来存储、另一种介质作为辅助使用。就拿 redis 来说，它主要采用内存存储数据，磁盘用来做辅助的持久化。拿 RabbitMQ 举例，它也是主要采用内存存储消息，但也支持将消息持久化到磁盘。而 RocketMQ、Kafka、Pulsar 这种，则是数据主要存储在磁盘，通过内存来主力提升系统的性能。关系型数据库例如 mysql 这种组件也是主要采用磁盘组织数据，合理利用内存提升性能。

针对采用内存存储数据的方案而言，难点一方面在于如何在不降低访问效率的情况下，充分利用有限的内存空间来存储尽可能多的数据，这个过程中少不了对数据结构的选型、优化；另一方面在于如何保证数据尽可能少的丢失，我们可以看到针对此问题的解决方案通常是快照+广泛意义的 wal 文件来解决。此类典型的代表就是 redis 啦。

针对采用磁盘存储数据的方案而言，难点一方面在于如何根据系统所要解决的特点场景进行合理的对磁盘布局。读多写少情况下采用 b+树方式存储数据；写多读少情况下采用 lsm tree 这类方案处理。另一方面在于如何尽可能减少对磁盘的频繁访问，一些做法是采用 mmap 进行内存映射，提升读性能；还有一些则是采用缓存机制缓存频繁访问的数据。还有一些则是采用巧妙的数据结构布局，充分利用磁盘预读特性保证系统性能。

总的来说，针对写磁盘的优化，要不采用顺序写提升性能、要不采用异步写磁盘提升性能(异步写磁盘时需要结合 wal 保证数据的持久化，事实上 wal 也主要采用顺序写的特性)；针对读磁盘的优化，一方面是缓存、另一方面是 mmap 内存映射加速读。

上述这些存储方案上权衡的选择在 kafka、RocketMQ、Pulsar 中都可以看到。其实抛开消息队列而言，这些存储方案的选择上无论是关系型数据库还是 kv 型组件都是通用的。

消息队列背后的设计思想