os-overview

Operating System

硬件结构

CPU缓存一致性

由于内存和CPU读写速度的差异，为了加速内存中数据的读写，CPU引入了缓存体系。

缓存的速度比内存快很多很多，将需要读写的数据读取到缓存中，下一次就无须再去内存中寻找。

但缓存也是内存数据的一份副本，也就存在着数据不一致的情况，需要保证数据同步。

写直达（Write Through）：每次需要写缓存中的数据时就修改内存的数据，使其同步。对于读来说，不仅没有加速，反而还多了写缓存的过程。显然效率不高。

写回（write back）：为了防止频繁将缓存的数据写回内存，就引入了写回的的方法。

  • 写数据，且数据已经存储在cache block中时，则无须直接修改内存，而是仅修改cache block中的数据，并标记该cache block为脏。

但由于现代CPU基本上都是多核CPU，就又涉及到多缓存的一致性问题。要保证多缓存的一致性，就要做到两点要求。

  • 写传播（Write Propagation）：一个核心写数据时，需要同步到其他核的缓存中。
  • 事务串行化（Transaction Serialization）：所有核心的数据变化是一致的，即顺序一致性。

要实现写传播，常用总线嗅探（Bus Snooping）实现。

要实现事务串行化，要做到以下两点，常用MESI协议实现。

  • CPU 核心对于 Cache 中数据的操作，需要同步给其他 CPU 核心；
  • 要引入「锁」的概念，如果两个 CPU 核心里有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进行对应的数据更新。

MESI协议

MESI协议定义了一个CPU核心的四种状态，和每个状态对于本核心读写、其他核心读写的四种操作的行为。

  • Modified，已修改
  • Exclusive，独占
  • Shared，共享
  • Invalidated，已失效。

其中，已修改和独占都是仅当前缓存存有该数据。

整个过程可以用有限状态机（finite-state machine）表示

每个状态对于不同的行为产生的变化如下表。

编译过程

  1. 编译预处理
  2. 编译
  3. 汇编
  4. 链接

为什么要有虚拟内存？

绝对物理地址：单片机

从单片机说起，单片机的程序是直接编译，烧进单片机的，一旦需要更改程序，就得重新编译，烧录。

编译后的程序，直接写在单片机的内存ROM中，必要的话，还可以手动更改ROM内容，这些都是直接操作绝对物理地址。

虚拟内存

而现代操作系统会将物理地址和程序操纵的地址解耦开，让MMU（memory manage unit）去管理。程序请求操作内存，则MMU查找对应的物理地址。

那么问题来了，操作系统是如何处理虚拟内存和物理内存的关系呢？

内存分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（*Segmentation*）的形式把这些段分离出来。分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。

可以看出这样分配是一大块分配的，很不利于动态分配内存。这样分配内存存在以下问题

  • 段间内存碎片：段与段之间的内存由于不够分配给一个段而无法使用。
  • 内存交换效率低：为了解决内存碎片问题，就有了将段内容复制到硬盘，再从硬盘读入到新内存中的过程。

内存分页

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

  • 程序请求内存时，以页为单位。这样页间的碎片就不会超过一个页大小。

但由于页也需要页表管理，占用不少额外空间用于管理页表。就衍生出多级页表。

对于一级页表来说，如果没有用到该项，而无需为其分配二级页表，虽然在页表全部使用的情况下多占用了一级页表的空间，但多数情况下可以节省内存。

此外，由于采用了多级页表这种寻址时间来换空间的做法，势必会导致查表耗时更长。于是衍生出缓存机制。

在CPU芯片中加入TLB（Translation Lookaside Buffer），根据程序的空间局部性原理，缓存的命中率通常不低。

段页式管理

顾名思义就是分段和分页结合使用

总结

总的来说，虚拟内存有如下优势

  1. 对于程序来说，只需关心自己的那部分内存，无需关系物理内存，内存管理交给操作系统。进程之间的内存也不会互相影响。算是程序和物理地址解耦的一种方式。
  2. 此外，由于页表的存在，虚拟内存和物理内存之间存在一层代理。对于那些非法的访问、特殊权限等可以做一些控制。
  3. 虚拟内存还可以节省空间。并不是所有程序都在使用其所有空间，对于那些暂时不用的部分，可以暂时换出到硬盘。

栈和堆的区别

栈和堆都是分配内存的方式，其中

  • 栈主要用于一些局部变量，函数传参等程序一般需求，因此栈由编译器管理更方便。
  • 堆主要用于程序特殊需要，因此需要手动管理（当然有垃圾回收的语言不用）。

从实现原理上来说

  • 栈一般是静态分配的（alloca函数动态分配），分配时大小确定，向下、低地址方向增长，需要多少内存直接移动栈指针即可，也就没有内存碎片的问题。
  • 堆是动态管理的，由链表实现，也就可能产生内存碎片问题，向上、低地址增长。

从效率上来说，

  • 栈是一般程序都需要的，因此会有优化，如专门的寄存器和指令
  • 堆是C/C++语言调用相关函数再经操作系统分配，机制复杂，效率不及栈。

从分配大小来看，

  • 栈受限于操作系统指定的参数
  • 堆受限于操作系统的虚拟内存

线程和进程的区别

线程是CPU调度的最小单位，而进程资源分配的最小单位，不同进程的资源是独立的。

进程拥有资源，由PCB控制。所以，线程基于进程。一个进程可以有多个线程，线程共享进程的大部分资源，独有自己的寄存器和栈等资源。

从调度角度来说，切换进程需要替换进程的绝大部分资源，消耗较多。而切换线程，仅仅需要切换独有的那部分寄存器和栈等资源。

在Linux系统下，线程实际上是一种进程，用的相同结构task_struct表示线程和进程，只不过多个线程共享地址空间、文件系统、打开的文件、信号处理函数，但独有寄存器和栈来保证执行的相对独立。实际上，进程的创建是通过一个系统调用clone来实现的，而线程底层也是通过clone来实现。

clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0);

只不过指明了需要与其他线程共享的四个参数。

进程调度

常见算法

  • 先来先服务（First Come First Severd, FCFS）算法
  • 最短作业优先调度算法
  • 高响应比优先调度算法
  • 时间片轮转调度算法
  • 最高优先级调度算法
  • 多级反馈队列调度算法

Linux下的进程调度

调度类

Linux将进程调度抽象成模块，称为调度类（Sched Class）。如何选择调度类，有一定的顺序。

顺序遍历实际上意味着调度类之间存在优先级关系，Linux 总共实现了5种调度类，按照优先级有高到底排序依次为：

  1. stop_sched_class Stop 是特殊的调度类，内核使用该调度类来停止 CPU. 该调度类用来强行停止CPU 上的其他任务，由于该调度类的优先级最高，因此一旦生效就将抢占任何当前正在运行的任务，并且在运行过程中自己不会被抢占。

    该调度类只有在SMP架构的系统中存在，内核使用该调度类来完成负载均衡与CPU热插拔等工作。

  2. dl_sched_class 有些任务必须在指定时间窗口内完成。例如视频的编码与解码，CPU 必须以特定频率完成对应的数据处理；

    这类任务是优先级最高的用户任务，CPU 应该首先满足。

    Deadline 调度类用来调度这类任务，dl 便是单词 Deadline 的缩写，因此该调度类的优先级仅仅低于 Stop 调度类。

  3. rt_sched_class 在本节开头我们提到，实时任务（Real-time Task）对响应时间要求更高，例如编辑器软件，它可能由于等待用户输入长期处于睡眠之中，但一旦用户有输入动作，我们就期望编辑器能够立马响应，而不是等系统完成其它任务之后才开始反应，这一点对用户体验十分重要。

    RT 调度类用来调度这类任务，该调度类的优先级低于 DL.

  4. fair_sched_class Fair 调度类用来调度绝大多数用户任务，CFS 实现的就是这种调度类，其核心逻辑是根据任务的优先级公平地分配 CPU 时间。我们会在后续章节中详细讨论 CFS 的实现细节。

  5. idle_sched_class 与 Stop 类似，Idle 调度类也是仅供内核使用的特殊调度类，其优先级最低，只有在没有任何用户任务时才会用到。内核会为每个 CPU 绑定一个内核线程（kthread）来完成该任务，该线程会在队列无事可做的情况下启动该任务，并将 CPU 的功耗降到最低。

每一个调度类都实现了pick_next_task，用于选择下一个调度的进程。

对于每个调度类，都有对应的调度策略。

调度策略

  1. Stop 调度类 Stop 调度类中只有一个任务可供执行，不需要定义任何调度策略。
  2. DL （Deadline）调度类 DL 只实现了一种调度策略：SCHED_DEADLINE, 用来调度优先级最高的用户任务。
  3. RT （Real-Time） RT 提供了两种调度策略：SCHED_FIFO 与 SCHED_RR,对于使用 SCHED_FIFO 的任务，其会一直运行到主动放弃CPU; 而对于 SCHED_RR 的任务，如果多个任务的优先级相同，则大家会按照一定的时间配额来交替运行，即使一个任务一直处于可运行状态，在使用完自己的时间切片之后也会被抢占，然后被放入队列的尾巴等待下次机会。
  4. Fair CFS 实现了三种调度策略：
    • SCHED_NORMAL: 被用于绝大多数用户进程
    • SCHED_BATCH: 适用于没有用户交互行为的后台进程，用户对该类进程的响应时间要求不高，但对吞吐量要求较高，因此调度器会在完成所有 SCHED_NORMAL 的任务之后让该类任务不受打扰地跑上一段时间，这样能够最大限度地利用缓存。
    • SCHED_IDLE: 这类调度策略被用于系统中优先级最低的任务，只有在没有任何其他任务可运行时，调度器才会将运行该类任务。
  5. Idle 同 Stop 一样，Idle 调度类也没有实现调度策略，注意不要将这类调度类与 CFS 中的 SCHED_IDLE 混淆。

每个进程在创建时都会指定一个调度策略，从而自动归结到某个调度类下。

我们可以通过 /proc/<pid>/sched 中的内容来查看进程的调度策略。

#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6

从上述描述不难看出，只有RT和CFS进程会参与调度的逻辑，Linux也提供了系统调用来修改进程优先级。

nice(); //修改静态优先级，作用于CFS
sched_setscheduler(); //修改动态优先级和调度策略，用于实时进程。

运行队列

运行队列（run queue）rq 是系统可运行任务的容器，调度器的很多工作都是围绕着 rq 来进行的，调度类 struct sched_class 所申明的函数中，绝大多数函数都与 rq 相关。在系统中，每个 CPU 都有一个自己的 rq, 这样可以避免多个 CPU 访问同一个 rq 时产生的并发问题，提升调度器效率。

每个rq都包含上述5个调度类，按照调度类优先级选取进程进行调度。

Linux RT调度

Linux实时进程的调度依赖于实时优先级。Linux提供两种实时进程的调度策略，分别是SCHED_FIFO和SCHED_RR。

SCHED_FIFO

  • 一直执行，直到它阻塞或者显式释放，不依赖时间片，一直执行。
  • 只能被更高优先级的实时进程抢占。
  • 多个同级的进程会轮流运行。

SCHED_RR

  • 类似SCHED_FIFO，但分配时间片。

Linux CFS调度

Linux CFS的设计理念是，每个进程都是完全公平的，他们的虚拟运行时间应该尽可能的相等，虚拟时间根据nice值的比例来分配。CFS分配运行时间不是按照时间片来分配的，而是每个进程运行一段时间，循环轮转，选择运行最少（虚拟运行时间最少）的进程作为下一个运行进程。CFS将nice值作为比列的分配标准，越低的nice值能够获得更高的使用权重。

时间记账：Linux使用一个变量vruntime记录虚拟运行时长。vruntime的更改是由系统定时器周期性调用update_curr()实现。

进程选择：CFS采用红黑树数据结构，按照vruntime大小给进程排序。红黑树用一个变量记录最小vruntime的进程。

进程插入：插入动作发生在进程创建或是进程唤醒时。

进程删除：删除动作发生在进程阻塞或是进程终止时。

休眠和唤醒：

休眠：当进程等待一些事件，例如等待文件I/O、硬件事件、获取锁、磁盘read时，进程会把自己标记成休眠，然后从红黑树移除，加入等待队列。

唤醒：进程设置为可执行状态，然后再从等待队列中加入红黑树。

上下文切换

七种状态变迁

进程的五种主要状态

  • 创建状态
  • 就绪状态
  • 阻塞状态
  • 运行状态
  • 结束状态

进程上下文切换

进程是分配资源的最小单位，因而不同进程拥有不同的

  • 在用户空间中的：虚拟内存（堆栈、全局变量、数据块、代码块）。
  • 在内核空间中的：内核堆栈、寄存器、PC、进程标识信息、进程现场信息、进程控制信息等。

切换时，需要把交换信息保存在进程的PCB中，恢复时取出。

线程上下文切换

线程是CPU调度的最小单位，依托进程存在，同一个进程下的线程共享

  • 虚拟内存、全局变量等资源

线程切换时，无需更改以上资源，而线程独有的

  • 栈、寄存器、私有数据等

需要切换。

在Linux下，线程和进程的都是用task_struct表示，为什么进程需要更大的花销呢？

没错，线程和进程的都是用task_struct表示，而该结构体大部分都是指针和一些小变量，没有数组等很大花销的变量，那么又是什么导致进程花销大呢？

问题出在虚拟内存上。Linux下，

  • 虚拟内存存在多级页表，切换是需要花一定时间的。
  • 除此之外，由于进程切换需要切换整个虚拟内存，因此，CPU的TLB缓存也是需要全部更新的。

而线程之间是共享虚拟内存的，就不存在这些花销。

此外，由于进程和线程切换都存在内核态的切换，也是一笔不小的花销。也因此，衍生出协程这个概念。

协程是轻量级的线程，协程之间的切换全程在用户态进行，也就没有内核态切换的花销。

死锁的条件和预防

四个必要条件

  1. 互斥条件（在多线程环境中，由于共享资源，可能发生race condition情况，通常采用加互斥锁来解决。因而有了互斥条件）
  2. 占有并请求。（占有一个共享资源并请求另一个资源）
  3. 不可剥夺。（在使用资源后才主动释放资源）
  4. 环路等待。

预防

破坏四个必要条件之一即可。比如

  1. 最常见的，破坏环路等待：给资源编号，资源按顺序获取。
  2. 破坏占有并请求：请求不到需要的资源就释放已经占有的资源。

IO：阻塞\非阻塞\同步\异步

在前面我们知道了，I/O 是分为两个过程的：

  1. 数据准备的过程
  2. 数据从内核空间拷贝到用户进程缓冲区的过程

阻塞 I/O 会阻塞在「过程 1 」和「过程 2」，而非阻塞 I/O 和基于非阻塞 I/O 的多路复用只会阻塞在「过程 2」，所以这三个都可以认为是同步 I/O。

异步 I/O 则不同，「过程 1 」和「过程 2 」都不会阻塞。

网络系统

DMA技术

在没有DMA(Direct Memory Access)技术前，I/O需要CPU参与，而由于没有数据处理，实际上就没有必要让CPU参与，因此DMA技术就诞生了。

无DMA流程图

含DMA

零拷贝

在 Linux 系统中，传统的访问方式是通过 write() 和 read() 两个系统调用实现的，通过 read() 函数读取文件到到缓存区中，然后通过 write()方法把缓存中的数据输出到网络端口，伪代码如下：

read(file_fd, tmp_buf, len);
write(socket_fd, tmp_buf, len);

从网络中获取到的数据，需要从磁盘复制到内核，内核复制到内存两个过程，而发送数据需要将用户态数据复制到内核态，再从内核状态复制到网卡发送。

经历了4次拷贝，不仅存在无用拷贝的情况，还有内核态和用户态切换的开销。

就引出了零拷贝技术。零拷贝技术实现的方式通常有 2 种：

  • mmap + write
  • sendfile

mmap + write

在前面我们知道，read() 系统调用的过程中会把内核缓冲区的数据拷贝到用户的缓冲区里，于是为了减少这一步开销，我们可以用 mmap() 替换 read() 系统调用函数。

buf = mmap(file, len);
write(sockfd, buf, len);

mmap() 系统调用函数会直接把内核缓冲区里的数据「映射」到用户空间，这样，操作系统内核与用户空间就不需要再进行任何的数据拷贝操作。

我们可以得知，通过使用 mmap() 来代替 read()， 可以减少一次数据拷贝的过程。

但这还不是最理想的零拷贝，因为仍然需要通过 CPU 把内核缓冲区的数据拷贝到 socket 缓冲区里，而且仍然需要 4 次上下文切换，因为系统调用还是 2 次。

sendfile

在 Linux 内核版本 2.1 中，提供了一个专门发送文件的系统调用函数 sendfile()，函数形式如下：

#include <sys/socket.h>
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

它的前两个参数分别是目的端和源端的文件描述符，后面两个参数是源端的偏移量和复制数据的长度，返回值是实际复制数据的长度。

首先，它可以替代前面的 read() 和 write() 这两个系统调用，这样就可以减少一次系统调用，也就减少了 2 次上下文切换的开销。

其次，该系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态，这样就只有 2 次上下文切换，和 3 次数据拷贝。如下图：

但是这还不是真正的零拷贝技术，如果网卡支持 SG-DMA（The Scatter-Gather Direct Memory Access）技术（和普通的 DMA 有所不同），我们可以进一步减少通过 CPU 把内核缓冲区里的数据拷贝到 socket 缓冲区的过程。

你可以在你的 Linux 系统通过下面这个命令，查看网卡是否支持 scatter-gather 特性：

$ ethtool -k eth0 | grep scatter-gather
scatter-gather: on

于是，从 Linux 内核 2.4 版本开始起，对于支持网卡支持 SG-DMA 技术的情况下， sendfile() 系统调用的过程发生了点变化，具体过程如下：

  • 第一步，通过 DMA 将磁盘上的数据拷贝到内核缓冲区里；
  • 第二步，缓冲区描述符和数据长度传到 socket 缓冲区，这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中，这样就减少了一次数据拷贝；

所以，这个过程之中，只进行了 2 次数据拷贝，如下图：

这就是所谓的零拷贝（Zero-copy）技术，因为我们没有在内存层面去拷贝数据，也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进行传输的。。

零拷贝技术的文件传输方式相比传统文件传输的方式，减少了 2 次上下文切换和数据拷贝次数，只需要 2 次上下文切换和数据拷贝次数，就可以完成文件的传输，而且 2 次的数据拷贝过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。

所以，总体来看，零拷贝技术可以把文件传输的性能提高至少一倍以上。

使用零拷贝技术的项目

  • Kafka
  • Nginx
  • Tomcat

Page Cache

类似CPU cache，Page Cache算是磁盘和内存之间的缓存。ageCache 的优点主要是两个：

  • 缓存最近被访问的数据；
  • 预读功能；

但是，在传输大文件（GB 级别的文件）的时候，PageCache 会不起作用，那就白白浪费 DMA 多做的一次数据拷贝，造成性能的降低，即使使用了 PageCache 的零拷贝也会损失性能

绕开 PageCache 的 I/O 叫直接 I/O，使用 PageCache 的 I/O 则叫缓存 I/O。通常，对于磁盘，异步 I/O 只支持直接 I/O。

于是，在高并发的场景下，针对大文件的传输的方式，应该使用「异步 I/O + 直接 I/O」来替代零拷贝技术。

所以，传输文件的时候，我们要根据文件的大小来使用不同的方式：

  • 传输大文件的时候，使用「异步 I/O + 直接 I/O」；
  • 传输小文件的时候，则使用「零拷贝技术」；

在 nginx 中，我们可以用如下配置，来根据文件的大小来使用不同的方式：

location /video/ { 
    sendfile on; 
    aio on; 
    directio 1024m; 
}

当文件大小大于 directio 值后，使用「异步 I/O + 直接 I/O」，否则使用「零拷贝技术」。

I/O多路复用

高性能网络模式

Reactor

Preactor

一致性哈希

Operating System
os-overview
https://messenger1th.github.io/2024/07/24/Operating System/os-overview/
作者
Epoch
发布于
2024年7月24日
许可协议