操作系统

冯诺依曼模型

计算机基本结构：运算器，存储器，控制器，IO设备

存储单元和输入输出设备和CPU的交互离不开总线，计算机基本结构的关系如下：

中央处理器

中央处理器就是所谓的CPU，常说的32位，64位指的是CPU的位宽。位宽代表了CPU一次可以运算的数据量。

CPU内部还有一系列的寄存器，他们与CPU的物理距离非常近，因此可以非常快速的进行运算。

寄存器的分类大致如下：

1. 通用寄存器：存放需要进行运算的数据
2. 程序计数器：存储CPU要执行吓一跳指令所在的内存地址
3. 指令存储器：存放当前正在执行的指令

CPU执行的具体流程

CPU从程序计数器中获取将要执行的指令的内存地址，接着CPU的控制单元操作地址总线指定要访问的内存地址。然后通知内存设备准备数据，数据准备好后通过数据总线将指令送入CPU，CPU收到数据后，将这个指令传入指令寄存器。

完成上述步骤后，CPU就算完成了指令读取，接下来程序计数器会自增，自增大小取决于CPU的位宽。

最后CPU分析指令寄存器中的指令，确认指令的类型和参数，如果是计算类型的指令，就将指令交给逻辑运算单元运算，如果是存储类型的指令，就交由控制单元执行。

现在大多数CPU都采用流水线的方式执行指令，流水线就是把一个任务拆成多个小任务，一条指令通常包含4个阶段：

1. CPU通过程序计数器读取对应内存地址的指令
2. CPU对指令进行解码
3. CPU执行指令
4. CPU将计算结果写回寄存器或内存

总线

总线用于CPU和内存以及其他设备之间的通信，它的分类如下：

1. 地址总线：指定CPU将要操作的内存地址
2. 数据总线：用于读写内存的数据
3. 控制总线：用于发送和接收信号

当CPU要读写内存数据时，一般会经过如下步骤：

1. 通过地址总线获取要读写的内存地址
2. 通过控制总线获取要执行的命令
3. 通过数据总线传输数据

线路位宽

在总线中有个概念叫线路位宽，它与CPU位宽并不相同，CPU位宽表示这个CPU一次最多能运算的数据位数，而线路位宽表示这个机器的寻址范围。

eg：如果只有1根地址总线，那么CPU能操作的内存范围就是2^1，如果有32根地址总线，那么CPU可以寻址的范围就是2^32。

通常情况下，CPU位宽大于等于线路位宽，否则的话CPU的操作会变得非常复杂。

CPU Cache

在Linux中，CPU Cache被分为大小不等的三级缓存，分别是L1 Cache，L2 Cache，L3 Cache。其中的L1 Cache通常会分为数据缓存和指令缓存。

L1和L2缓存是每个核心独有的，而L3缓存是多个CPU核心共享的

CPU Cache由多个Cache Line组成，Cache Line是CPU从内存读取数据的基本单位。

Cache Line由各种标志+数据块组成

直接映射

直接映射是CPU查询缓存的策略之一。他的基本思想是：将内存块的地址始终映射在一个缓存块当中，映射关系式用的是取模运算。

eg：一台机器的内存有32个内存块，CPU中包含8个Cache Line，那么对于每个内存块，将它的编号%8就是它对应的缓存块。

从上面的例子我们可以很明显的看出一个缓存块会对应多个内存块，CPU判断当前位于缓存块的数据是否是自己想要数据的依据就是Cache Line中的组标记，这个组标记会记录当前缓存块中的数据对应的内存块，CPU可以利用他区分不同的内存块。

除了组标记之外，CPU Cache Line还包含三个信息：

• 实际的数据
• 有效位，标记缓存块中的数据是否是有效的，如果有效位是0，即使缓存块中有数据也不会读取缓存。

当CPU要访问内存时，他会先通过地址总线获取一个内存的访问地址，这个地址包含：组标记，Cache Line索引，偏移量。偏移量帮助CPU确定目标数据在缓存数据块中的位置。

综上所述，CPU访问一个内存地址时会经历4个步骤：

1. 根据地址中的索引信息，计算它在Cache Line中对应的索引
2. 找到Cache Line后，判断有效位，如果无效，直接访问内存
3. 对比内存地址中的组标记和缓存块中的组标记，确认缓存块中的数据就是否为要访问的数据，如果不是，CPU会直接访问内存，并重新加载数据
4. 根据内存地址中的偏移量信息，从缓存块的数据块中读取对应的字。

缓存一致性

CPU Cache有两种写入数据的方式：

1. 写直达

将数据同时写入内存和缓存

每次写入数据之前都会判断数据是否在CPU Cache里，如果在，将数据写入CPU Cache和内存。如果不在，直接写入内存。

2. 写回

当发生写操作时，数据只会被写入CPU Cache中，只有当该数据所在的Cache Block被替换掉时，才会将数据写入内存。

具体流程：

当CPU要写入数据时，如果数据就在Cache中，直接将数据写入到缓存，并将这个数据块标记为dirty

如果数据不在Cache中，定位所在的Cache Block

• 如果目标Block不是dirty，从内存中读取数据到这个Block中，然后写入数据。

• 如果是dirty，首先要将该数据块写回内存，然后读取对应数据块到Cache中，接着修改数据，最后标记这个数据块为dirty。

  这里可能会有些疑问：既然写操作必然会导致数据块被标记为dirty，那有什么必要将数据块先读入内存。

  将数据块读入内存，其实并不一定是要利用它的数据，而是让其他CPU核心知道，自己获得了这块数据的占有权。如果该数据块之前被其他CPU修改过，但还没有写入内存，此时这个读操作就会将脏页刷入内存，保证缓存一致性。

缓存一致性问题

由于CPU每个核心都有自己的缓存，当某个核心修改和其他核心共享的数据时，就会导致缓存不一致。

针对这一问题，解决方案需要满足以下两点：

1. 写广播：一个核心要进行写操作，必须通知其他核心
2. 串行化：写操作的执行顺序在其他核心看来必须是一致的

要想保证第二点，就需要引入锁机制

总线嗅探

每当有核心要进行写操作，它就会向总线发送一条广播，其他核心在收到这条消息后，如果发现修改的数据块在自己的缓存中也有，就将对应的缓存块标记为已失效。

总线嗅探的思想非常简单，但它的问题在于会给总线带来很大的压力，并且无法保证串行化。

MESI协议

MESI协议就是基于总线嗅探实现事务串行化，并且利用状态机机制减轻总线压力。

MESI代表4个状态的首字母缩写：

• Modified 已修改 （dirty标记）
• Exclusive 独占 （只有一个核心持有该数据块）
• Shared 共享 （多个核心持有该数据块）
• Invalidated 已失效 （当前缓存块已失效）

当A号CPU核心要读取数据时，会向总线发送一条广播，如果没有其他核心拥有该数据，它会从内存中读取，并将这个数据块标记为独占。

如果核心B有对应的数据且不是脏的，他就会将这个数据发送给核心A，并将这个数据块标记为共享。此时A和B持有的缓存数据是一样的。

接着A修改了这个数据，此时他会向广播中发送一条消息，B收到消息后会将对应缓存块标记为已失效。A完成修改后将数据块标记为已修改。此后A再修改这个数据块就不需要再向总线发送消息了，因为其他核心已经知道自己对应的缓存已经失效。

如果其他核心要读取更新之后的数据，他们会向总线发送一条通知，A发现这个数据自己有，且是修改状态。此时它就会将缓存数据刷回内存。这样其他核心读取到的就是最新的数据了。

伪共享

伪共享的场景：多个CPU核心共享某个数据块，但使用的都是该数据块中不同部分的数据。如果每个核心轮番进行写操作，就会导致缓存被频繁刷入内存，缓存命中率大幅降低。

伪共享的解决方案显然是避免让频繁修改的热点数据出现在同一个Cache Line里。

Linux内核提供了__cacheline_aligned_in_smp宏定义来解决伪共享问题。

struct test {
    int a;
    int b __cacheline_aligned_in_smp;
}

由于a和b被定义在同一个结构体里，因此他们很可能出现在同一个Cache Line中。

但在加上了宏定义之后，他们实际的存储方式是这样的

显然这是空间换时间的思想，消耗一部分CPU缓存空间，换来性能提升。

线程

在Linux中，进程和线程都使用task_struct结构体来表示，区别在于线程的task_struct结构体里部分资源是共享了进程已创建的资源

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

1. 实时任务：对系统的响应事件要求很高，优先级在0-99范围内
2. 普通任务：优先级在100-139

调度类

Linux为了保证高优先级的任务能够尽早被执行，设置了如下调度类：

Deadline和RealTime都是用于实时任务，他们的调度策略解释如下：

1. DEADLINE：优先执行临近截止时间的任务
2. FIFO：对于同优先级的任务，先到先服务。高优先级任务可以抢占低优先级任务
3. RR：对于相同优先级的任务，轮流分配时间片。用完时间片的任务会被放到队列尾部。保证优先级相同的任务的公平性。但高优先级任务仍然可以抢占低优先级。

Fair调度类应用于普通任务：

1. NORMAL：普通任务使用的调度策略
2. BATCH：后台任务使用的调度策略，不与终端进行交互

完全公平调度

在系统中，实时任务的数量远小于普通任务。因此这里我们着重关注一下普通任务。而对普通任务来说，公平性是最重要的。Linux基于完全公平调度（CFS）设计了一个调度算法。

算法的理念是让分配给每个任务的CPU时间是一样的。因此它会为每一个任务安排一个虚拟运行时间vruntime。一个任务运行的时间越久，vruntime会越大。某个任务如果用完时间片后还没有完成，会被重新估计vruntime，因此一个多次耗尽时间片的任务最终会被分配一个较低的优先级。而CPU在挑选任务时，优先选择vruntime较小的。

$$
vruntime += delta_exec * NICE_0_LOAD / 权重
$$

这里nice级别越低，代表优先级越高

中断

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

由于OS在收到中断后会打断其他进程的运行，因此中断处理程序必须要尽可能快的执行完，否则不仅会影响其他进程运行，还会导致后续到来的中断丢失（处理中断期间，CPU会关闭中断）。

软中断

为了解决中断处理程序运行过长以及中断丢失的问题，Linux将中断分为两个阶段：

• 上半部分：暂时关闭中断请求，主要负责处理跟硬件紧密相关或时间敏感的部分
• 下半部分：延迟处理上半部分未完成的工作

不难看出，软中断的核心思想就是：让CPU尽快从中断状态中抽身出来，只负责完成没它不行的任务，其余部分交给内核线程去处理。

虚拟内存

我们使用计算机时经常会需要同时运行多个进程，那么就需要一种方式确保各个进程之间使用的地址不冲突。OS的解决方案就是使用虚拟地址，每个进程都只能使用自己的虚拟地址，不允许直接操作物理地址。至于物理地址和虚拟地址之间的映射，交给操作系统来解决。

内存分段

内存分段是OS管理虚拟地址与物理地址映射关系的一种方法。分段机制中的虚拟地址由两部分组成：段选择因子和段内偏移量

1. 段选择因子：存储在段寄存器里，其中存储着段号作为段表的索引。段表里存储段的基地址和段的界限以及特权等级等。

2. 段内偏移量：位于0和段界限之间

分段的方式简明直接，想要计算某个数据的物理地址只需要获取对应段的基地址再加上偏移量即可。

但是分段也有很明显的缺点：

1. 内存碎片：计算机往往都是按程序启动的时间点来按顺序分配内存，如果某个分配到中间部分内存的程序关闭（假设它占用128MB），那么即使最后总的空闲内存有256MB，也无法启动一个200MB的程序。

2. 内存交换效率低：解决外部内存碎片的一种方式就是使用内存交换，当计算机发现出现内存碎片时，会将内存地址在此之后的程序先写入硬盘，也就是Swap空间。然后再读回内存，这样就可以清理掉内存碎片。但是由于内存分段会导致大量的内存碎片出现，因此会导致频繁的内存交换，而磁盘读写性能又有限，因此会大幅降低效率。

内存分页

内存分页可以有效解决分段的缺陷。他将整个虚拟和物理内存切成一段段固定尺寸的大小，每一段称为一页，在Linux中的大小是4KB。

而虚拟地址和物理地址之间使用页表进行映射，内存管理单元就负责将虚拟内存地址转换为物理地址。

由于内存空间都是预先划分好的，也就不会像内存分段那样在段与段之间产生间隙非常小的内存。不过也正因为内存分页机制最小单位是一页，面对一些比较小的程序段会导致内存浪费，也就是内部内存碎片。

如果内存空间不够，OS会将正在运行的进程中最近没被使用的内存页给替换掉。也就是将他们暂时写在磁盘上。

如果进程访问的虚拟地址在页表中查询不到，就会产生一个缺页异常，此时就需要进入系统内核空间分配物理内存、更新进程页表，再返回用户空间。

映射方式

分页机制下，虚拟内存分为两部分：页号和页内偏移。页号是页表的索引。页表包含物理页每页所在物理内存的基地址。

因此最简单的内存地址转换步骤为：

1. 将虚拟内存地址切分为页号和偏移量

2. 根据页号从页表里面查询对应的物理页号

3. 用物理页号基地址加上偏移量

但这种内存地址转换方式有一个非常明显的问题：在32位环境下，虚拟地址空间有4GB，利用上面的转换方式，我们启动一个进程必须准备100W个页表，再加上系统中可以运行大量的进程，这就导致页表的空间开销会非常大。

多级页表

为了解决上述缺陷，系统将单级页表再次进行分页，一级页表拥有1024个页表项，二级页表中包含1024个页表项形成二级分页。

这样做表面上看还增大了空间开销，但实际上所有的程序都有局部性原理，对于那些不常用的页，随时都可以被操作系统置换出去腾出空间给其他进程。

并且一级页表就可以实现对4GB虚拟地址的覆盖，如果某个一级页表项没有被用到，那么它的二级页表就可以暂时不创建，这更进一步节省了空间。

单级页表无法节省空间的原因就在于，它必须创建100w个页表项才能实现对虚拟地址的覆盖，如果无法覆盖虚拟地址，程序的运行根本无法运行，因此单级页表的实现无法节省空间。

如果我们进一步将二级页表推广到多级页表，那就可以节省更多的空间。不过这种方式也是有代价的，系统在进行地址映射的时候多了几道转换工序，因此这是种时间换空间的思想。

TLB

为了解决多级页表在转换上带来的时间问题，计算机会将最长访问的页表项放入专门的缓存，也就是TLB。

段页式内存管理

段页式内存管理方式：

• 将程序划分为多个段（分段）

• 然后再将这些段划分为多个页，也就是对分段出来的连续空间再划分固定大小的页

可用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率

进程与线程

进程

程序是可以被系统执行的二进制文件，而进程就是正在运行的程序

进程的状态有：

1. 新建

2. 就绪：可运行

3. 运行：正占据CPU时间片

4. 阻塞：进程正在等待某一事件发送而暂时停止运行

5. 结束

6. 挂起：被从内存中调换到磁盘上，避免大量阻塞线程占用物理内存空间

PCB

PCB是进程唯一标识，里面记录了：

进程标识符，用户标识符

进程当前状态，进程优先级

资源分配清单

CPU信息，也就是进程运行时的上下文

PCB通常使用链表组织起来，一般同一种状态的进程被串在同一个链表里。选择链表的原因是，操作系统随时面临着进程的增加与删除，链表相比数组在增删方面更有优势。

进程间通信

1. 管道

2. 消息队列

管道的通信方式效率比较低下，通信双方必须是同步的。消息队列很好的解决了这个问题，它是保存在内核中的消息链表，如果进程A需要与进程B通信，它只需要向消息队列中投放要发送的信息，不需要等待B的响应，然后B从消息队列中读取，并自行处理即可。

但消息队列也有缺点，首先因为使用了内核内存，因此消息大小不宜过大。其次，由于接收者必须主动到消息队列中收取消息，存在通信不及时的情况。

还有一点是，当进程要发送消息时，涉及将数据从用户空间到内核空间的拷贝，这里有一次状态转换。接收消息同理

3. 共享内存

取出一块虚拟地址空间，映射到相同的内存地址中去。这就免去了拷贝，且更新几乎是实时的。不过缺点在于，共享内存会引入资源竞争。

为了解决资源竞争的问题，操作系统引入了信号量，它是用于进程间同步或互斥的手段。（具体情况去看操作系统）

4. 信号

进程间的异步通信机制，发送者可以在任意时刻发送信号给指定进程。在收到信号后可以采取以下措施：

1.执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。

2.捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。

3.忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

5. Socket

线程

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

和进程相比，线程之间共享相同的地址空间，可以方便的相互通信。并且由于他们大部分资源都是共享的，在上下文切换时需要保存的资源就非常少，减少了系统的开销。

线程与进程之间最大的区别在于，线程是CPU的调度单位，进程是资源分配的单位

线程与进程的比较如下：

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

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

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

线程又分为用户线程以及内核线程，还有轻量级线程

用户线程

用户线程的线程管理与调度，不是由操作系统来执行，而是由特定的线程库来完成这些操作。

这样做的好处在于，它和操作系统完全解耦，甚至可以在不支持线程计数的操作系统上运行。同时也减少了内核态与用户态的切换，效率很高。

不过缺点在于，操作系统对用户线程是无感知的，如果一个线程因为系统调用而阻塞，进程中的其他用户线程都不能执行，并且由于用户线程没有权限打断其他运行中的线程，一旦一个线程开始运行，除非它主动让出CPU，否则进程中的其他用户线程都无法运行。

此外，因为时间片是分配给进程的，因此如果某个线程得到的时间片较少，执行效率就会很低。

内核线程

内核线程都由操作系统直接管理，线程对应的TCB都存储在操作系统里。

对于一个内核线程来说，如果进程内其他线程被阻塞，并不会影响自身运行，因为CPU分配时间片的单位是线程。并且多线程的进程可以获取更多的时间片。

不过内核线程的缺陷在于，它的所有管理与调度完全由内核完成，效率不如用户线程高，并且只能在支持线程的操作系统中运行。

调度

调度原则

1. 在发生IO这类导致CPU空闲的事件时，调度程序需要从内存中取出一个就绪的线程来执行，避免资源浪费。

2. 权衡长任务与短任务运行的运行完成数量

3. 避免进程饥饿，尽可能减少进程的周转时间（等待时间+运行时间）

4. 已经处于就绪队列中的进程，等待时间应该越短越好

5. 对于交互式较强的应用，要考虑响应时间

调度算法

1. 先来先服务

2. 最短作业优先

3. 高响应比优先

$$
权重 = (等待时间+运行时间) \div 运行时间
$$

       高响应比优先算法在确保短作业优先执行的前提下，保证了长作业的运行，确保长作业不会饥饿。

4. 时间片轮换算法

将CPU运行时间划分为一个一个时间片分配给进程，每个进程只有在分配到时间片时才能运行。如果时间片用完还没有执行完，也强制阻塞这个进程，将CPU资源释放出来。

5. 最高优先级调度算法

这种算法挑选就绪队列中优先级最高的进程执行，优先级分为以下两种：

• 静态优先级：在运行之前就决定好的优先级

• 动态优先级：运行期间动态改变的优先级，一个进程运行时间越长，优先级越低，等待时间越长，优先级越高

6. 多级反馈队列算法

这种算法建立了多个优先级队列，队列优先级从高到低，分配的时间片随着优先级降低而增多。如果在低优先级队列的任务执行过程中，有新的任务到来，就立即将当前进程停止，并移动到原队列末尾，转去执行新来的任务。

这种算法可以确保短任务可以很快被执行完，长任务虽然会随着执行次数增多，优先级降低，但每次分配到的时间片变多了。

IO多路复用

由于为每个连接都分配一个进程或线程是一种很低效的做法，因此人们开始寻找是否有一种方法可以让一个进程维护多条连接。

IO多路复用就是这样的一个技术，虽然一个进程在同一时刻只能处理一个请求，但如果每个请求的处理时间可以压缩到1ms，那么在外界看来，就好像一个进程在1s内处理了1000条连接。这就是所谓的时分多路复用。

select/poll

select实现多路复用的方式是，将所有已连接的Socket放到一个文件描述符集合，然后调用select函数将文件描述符集合拷贝到内核里，由内核来检查是否有读/写事件的发生。如果有发生，就将它添加到可读可写集合中，最后拷贝到用户态里面。

这里总共发生了两次遍历文件描述符集合，并且进行了两次拷贝。

poll的基本实现思路和select一样，区别在于它使用链表和动态数组而非bitMaps作为文件描述符集合，突破了select文件描述符个数的限制，不过依旧会受系统描述符个数的限制。

epoll

epoll的流程：

首先调用epoll_create建立一个epoll对象，接着将待检测的socket加入到epoll对象中，然后使用epoll_wait等待事件发生

epoll相比于select和poll进行了如下改进：

1. 在内核中维护一个红黑树，存储待检测的socket，因此用户只需要传入一个待检测socket到内核即可，而不需要传入整个待检测socket集合。

2. epoll使用事件驱动，在内核里维护一个链表来存储就绪事件，当某个socket有事件发生时，就通过回调函数将事件加入到链表当中。当用户调用epoll_wait时只会返回就绪事件的个数，而不需要直接遍历整个socket集合。