跳转至

操作系统

CPU 缓存/内存数据一致性

数据以"cache lines"的形式在cpus的cache和内存之间传输，cache line是定长的block，大小通常在16～256 bytes。

  • cache miss 时会加载数据，一般采用组相联模式；

cpu cache

CPU 的缓存一致性问题应该从 2 个维度理解：

  • 纵向：Cache 与内存的一致性问题： 在修改 Cache 数据后，如何同步回内存？
  • 横向：多核心 Cache 的一致性问题： 在一个核心修改 Cache 数据后，如何同步给其他核心 Cache？

Cache 与内存的一致性

写直达策略（Write-Through）：每次更新 Cache 时，同步更新内存；

写回策略（Write-Back）：每个 Cache 块上增加一个 “脏（Dirty）” 标记位，在 Cache 块被替换出去的时候将数据写回缓存：

  • 写入时，数据不在Cache，需要先加载到 Cache，如果替换策略换出的旧 Cache 块是脏的，就会触发一次写回内存操作；
  • Cache Miss 时：替换策略换出的旧 Cache 块是脏的，就会触发一次写回内存操作；

MESI（缓存一致性）

MESI在线体验网站

示例：假设 A 和 B 两个CPU，线程 T 先在 CPU A 上写数据，写到 CPU A 的缓存，再切换到 CPU B 上执行，此时 CPU B 的缓存没有数据。

  • CPU B 读取时，会触发CPU A的缓存将数据写回主存，然后CPU B从主存加载到缓存，此时CPU A 和 CPU B的Cache line的状态是 Shared。

缓存一致性机制需要解决的问题就是 2 点：

  • 特性 1 - 写传播（Write Propagation）： 每个 CPU 核心的写入操作，需要传播到其他 CPU 核心；
  • 特性 2 - 事务串行化（Transaction Serialization）： 各个 CPU 核心所有写入操作的顺序，在所有 CPU 核心看起来是一致。

MESI 缓存一致性协议，每个cache line上用2位来维护状态值"tag"，四种状态分别为：

  • Modified：表明 Cache 块被修改过，但未同步回内存；
  • Exclusive：表明 Cache 块被当前核心独占，而其它核心的同一个 Cache 块会失效，内存跟缓存一致。
  • Shared：表明 Cache 块被多个核心持有且都是有效的，不用负责将数据写回或者移交给其它cache，内存跟缓存一致。
  • Invalid：处于invalid状态的line是空的，没有数据，当新的数据进入cache时，将会优先被放入invalid状态的cache line中。

状态转换图如下所示：

img

现代的 CPU 会在增加写缓冲区和失效队列将 MESI 协议的请求异步化，以提高并行度：

  • 写缓冲区（Store Buffer）：
  • 在写入操作之前，CPU 核心 1 需要先广播 RFO 请求获得独占权，在其它核心回应 ACK 之前，当前核心只能空等待，这对 CPU 资源是一种浪费
  • 写入指令放到写缓冲区后并发送 RFO 请求后，CPU 就可以去执行其它任务，等收到 ACK 后再将写入操作写到 Cache 上。
  • 失效队列（Invalidation Queue）
  • 其他核心在收到 RFO 请求时，需要及时回应 ACK。但如果核心很忙不能及时回复，就会造成发送 RFO 请求的核心在等待 ACK。
  • 先把其它核心发过来的 RFO 请求放到失效队列，然后直接返回 ACK，等当前核心处理完任务后再去处理失效队列中的失效请求。

mesi_store_buffer.png

事实上，写缓冲区和失效队列破坏了 Cache 的一致性。 举个例子：初始状态变量 a 和变量 b 都是 0，现在 Core1 和 Core2 分别执行这两段指令，最终 x 和 y 的结果是什么？

Core1 指令

a = 1; // A1
x = b; // A2

Core2 指令

b = 2; // B1
y = a; // B2

写缓冲区造成指令重排，出现意料之外的结果

mesi_store_buffer_error.png

顺序一致性

内存读写指令的重排

内存重排（由Store Buffer、CPU乱序、编译器重排等造成）带来的内存一致性memory consistency问题，MESI协议也是处理不了的。

  • X86 上的LOCK前缀指令：原子性 + 禁止前后指令的重排序

内存读写指令的重排分为软件层面的编译器重排 和硬件层面的CPU重排 。

CPU重排：

  • CPU指令重排：并行执行、延迟执行、分支预测技术等；
  • 缓存读写重排：先进行缓存读写操作，而不是直接对内存进行读写，包括 MESI 的写缓冲区和失效队列机制；

内存屏障类型

barrier 有四种:

  • LoadLoad 阻止不相关的 Load 操作发生重排
  • LoadStore 阻止 Store 被重排到 Load 之前
  • StoreLoad 阻止 Load 被重排到 Store 之前
  • StoreStore 阻止 Store 被重排到 Store 之前

CPU 内存一致性模型

目前有多种内存一致性模型：

  • 顺序存储模型（sequential consistency model）：理想模型，没有乱序的存在。
  • 完全存储定序（total store order）：强一致性模型
  • 部分存储定序（part store order）
  • 宽松存储模型（relax memory order）

进程

三态模型：运行态、就绪态、阻塞态

进程的组成部分：程序、数据集合、PCB（进程控制块）

  • PCB是种数据结构，是进程存在的唯一标识；

PCB的组织方式：

  • 线性方式：所有PCB无论状态，连续存放在内存区域（线性表组织），每次查找扫描全表；
  • 链接方式：按照进程的状态，将进程的PCB组织成队列，形成就绪、阻塞、运行队列（队列头指针）等；
  • 索引方式：按照进程状态，建立就绪、阻塞、运行索引表等；

pcb_ds

进程空间

虚拟内存机制：每个进程都逻辑上独占拥有全部的内存。

  • 内存分配是分配虚拟内存给进程，当进程真正访问某一虚拟内存地址时，操作系统通过触发缺页中断，在物理内存上分配一段相应的空间再与之建立映射关系，虚拟内存地址会被自动转换变成有效物理内存地址，便可以进行数据的存储与访问；

process_virtual_memory

  • 64位地址的虚拟内存空间为256TB ( 2^48 )：目前的x86-64架构CPU都遵循AMD的Canonical form， 即只有虚拟地址的最低48位才会在地址转换时被使用，且任何虚拟地址的48位至63位必须与47位一致(sign extension)。

  • 内核空间占一半（同样是高地址区域），普通进程使用另外一半。

  • 使用40位来表示物理地址空间，可以通过cat /proc/cpuinfo来查看；

Kernel space：操作系统内核地址空间；

  • 每个进程的内核虚拟地址空间都是映射到相同的真实物理地址；
  • 内核虚拟地址空间总是存放在虚拟内存的地址最高处。

Stack：栈空间。

  • Random stack offset（栈随机偏移）：因为内存布局按照严格的规则摆放，因此很容易被恶意访问，通过加入随机偏移，使的每个进程的栈空间起始位置都稍有不同，使的被确定栈空间起始位置具有一定难度，防止被恶意访问。

Heap与Memory Mapping Segment：堆与内存映射段都属于堆空间

  • 堆负责小额内存的管理，内存映射段负责大额内存的管理，方便的存储数据并且减少动态分配内存时系统的开销；

Text segment：代码段。这一块区域是用来存放进程代码；

Data segment：数据段。存放全局数据与静态数据；

BBS segment：保存的是全局/静态未初始化数据

死锁

两个或多个任务（线程）形成循环等待各自的共享资源释放，形成了死锁。

Coffman条件：死锁的充要条件

  • 互斥：资源不可共享；
  • 占有并等待条件：一个任务占有某个互斥资源同时且请求另一个互斥资源，且等待时不会释放任何资源；
  • 不可剥夺：资源只能被那些持有它们的任务释放；
  • 循环等待：拥有资源和申请资源形成了环状的循环。

解决死锁的策略：

  • 死锁预防：破坏死锁条件中的任一个；
  • 死锁避免：申请资源时判断是否会发生死锁，如银行家算法；
  • 死锁检测：判断当前是否处于死锁，如果是则进死锁解除；
  • 死锁解除：与死锁检测配合使用，剥夺进程的资源；

一般来说，通过预防就可以避免死锁，比如多资源申请的顺序要一致，且最先申请的资源最后释放。

活锁

系统有两个任务，因对方的行为而改变自己的状态，则出现了活锁。最终是它们陷入状态变更的循环而无法继续向下执行。

通过对多个资源的同顺序申请，可以预防活锁。

寻址

虚拟地址(逻辑地址)

所有现代操作系统都使用虚拟内存，使用虚拟的地址取代物理地址，这样做的好处是：

  1. 一个以上的虚拟地址可以指向同一个物理内存地址；

  2. 虚拟内存空间可大于实际可用的物理地址；

利用第一条特性可以把内核空间地址和用户空间的虚拟地址映射到同一个物理地址，这样DMA就可以填充对内核和用户空间进程同时可见的缓冲区。

地址重定位

将程序的虚拟地址（逻辑地址）转为内存的真实地址（物理地址）的过程，由单独的硬件处理。

  • 静态重定位：
  • 绝对地址（物理地址） = 相对地址（逻辑地址） + 程序存放的内存起始地址
  • 程序运行前确定映射关系，程序装入后不能移动，占用连续的内存空间；
  • 动态重定位：
  • 绝对地址（物理地址）= 逻辑地址寄存器的值（VR）+ 重定位寄存器的值（BR）
  • 程序占用的内存空间可动态变化，不要求连续的内存空间，便于多个进程共享代码；

存储管理

分区管理

把主存的用户区划分为若干个区域（连续），每个区域分配给用户作业使用，并限定他们只能在自己的区域中运行。

  • 固定分区：每个分区用来装入一个作业；
  • 可变分区：进程装入内存时，根据进程的大小动态地建立分区，系统分区的大小和数目是可变的（空闲分区会合并）；
  • 首次适应算法：第一个区域能够满足程序的空间需求；
  • 最佳适应算法：最小剩余的区域能够满足程序的空间需求；
  • 最差适应算法：最大剩余的区域能够满足程序的空间需求；
  • 可重定位分区：
  • 程序使用的空间（连续）可以整体移动，让使用的分区集中，进一步减少内存碎片；

案例：伙伴系统（buddy system）：内存是以2的幂次个字节大小的空闲块为分配单位

分页管理

页：将进程的地址空间划分为若干个大小相等的区域。

页框：将主存空间也划分跟页大小相等的若干个物理块，也称为块。

逻辑地址：页号+页内地址；

物理地址：页框号（物理块号）+块内地址；

通过页表记录 页号 -> 页框号，页内地址等于块内地址。

os_page

分段管理

为每个段分配一个连续的区域（各个段的长度可以不一样），进程中的各个段可以离散地分配到主存的不同分段中。

逻辑地址：段号+段内地址；

物理地址：段基址+段内地址；

通过段表记录 段号 -> 段基址，段内地址一样。

image-20220331103554438

段页式管理

将主存划分成大小相等的存储块（页框），将用户程序按程序逻辑关系分为若干段，将每个段划分为若干页，以页框为单位离散分配。

逻辑地址：段号 + 段内页号 + 页内地址

物理地址：段基址 + 页框号 + 页内地址

os_segment.png

虚拟存储

当主存空间不能满足作业要求时，作业无法装入主存执行。

如果一个作业只部分装入主存便可开始启动运行，其余部分暂时留在磁盘上，在需要时再装入主存，这样可以有效地利用主存空间。

从用户角度看，该系统所具有的主存容量将比实际主存容量大得多，人们把这样的存储器称为虚拟存储器。

  • 根据不同的管理方式分为：请求分页、请求分段、请求段页式

页面淘汰

请求分页管理中，淘汰页面的算法：

  • 状态位在内存的页面才可以被淘汰；
  • 根据访问位（0未访问，1访问），修改位（0未修改，1修改）进行淘汰：
  • 按照 00 -> 01 -> 10 -> 11 的顺序进行淘汰；

设备管理

程序控制：CPU与设备串行工作

  • 无条件传送：IO端总是准备好，CPU需要时，随时使用IO端口；
  • 程序查询：CPU轮询IO端是否准备好，再进行发送数据；

中断：

  • 某个进程要启动某个设备时，CPU就向相应的设备控制器发出一条设备I/O启动指令，然后CPU又返回做原来的工作；
  • 设备准备好时，可以发送中断请求，CPU响应中断请求发送数据；
  • CPU与I/O设备可以并行工作（即设备准备时，CPU可以继续执行其它程序）。

os_interrupt.png

DMA：

  • 通过DMA控制器直接进行批量数据交换，除了在数据传输开始和结束时，整个过程无须CPU的干预；

os_dma.png

文件存储管理

索引视图

os_file_index.png

位视图

该方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0 和1 分别表示空闲和占用。

os_file_bitindex.png

内核态和用户态

内核态：控制计算机的硬件资源，并提供上层应用程序运行的环境。比如socket I/O操作或者文件的读写操作等

用户态：上层应用程序的活动空间，应用程序的执行必须依托于内核提供的资源。

系统调用：为了使上层应用能够访问到这些资源，内核为上层应用提供访问的接口。

Intel X86 CPU 有四种不同执行级别0到3，Linux用0和3分别表示内核态和用户态。

缓冲区

  • 用户缓冲区的目的是为了减少系统调用次数，从而降低操作系统在用户态与核心态切换所耗费的时间；
  • 比如 Java 中的 BufferedReader，用户空间的缓存；
  • 内核缓冲区，是为了在OS级别，提高磁盘IO效率，优化磁盘写操作；
  • 读写文件时的内存缓冲区，等到一定时间或数据规模后，再写入磁盘。

I/O

同步、异步、阻塞、非阻塞

  • 同步：不管是BIO/NIO/IO多路复用，从内核缓存写入用户缓存一定是由用户线程自行读取数据，处理数据

  • 异步：数据是内核写入的，并放在了用户线程指定的缓存区，写入完毕后通知用户线程

  • 阻塞：数据从网口写到内核,如果没写好,线程就一直在等待
  • 非阻塞：数据从网口写到内核,用一个线程轮询的去查看所有的数据是否准备好(I/O多路复用,监听多个socket)

IO分类

  • BIO:同步阻塞IO,一个客户端连接，对应一个服务端线程
  • BIO还有一种变种,伪异步IO,当有新的客户端接入时，将客户端的socket封装成一个task，丢到线程池中处理。优化了后续处理线程的方式
  • NIO： 同步非阻塞IO
  • AIO:：异步非阻塞IO(异步一定是非阻塞)

I/O多路复用

select：知道了有I/O事件发生了，却并不知道是哪那几个流（可能有一个，多个，甚至全部），只能无差别轮询所有流(O(n))，找出能读出数据或者写入数据的流，再进行操作；

poll：本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态， 但是它没有最大连接数的限制，原因是它是基于链表来存储的

epoll(Linux内核所特有)：可以理解为event poll，不同于忙轮询和无差别轮询，epoll会把哪个流发生了怎样的I/O事件通知我们（O(1)）。epoll实际上是事件驱动（每个事件关联上fd）；

注意：表面上看epoll的性能最好，但是在连接数少并且连接都十分活跃的情况下，select和poll的性能可能比epoll好，毕竟epoll的通知机制需要很多函数回调；

锁页内存

设备可以通过直接内存访问（direct memory access，DMA）方式来访问主机的锁页内存。

锁页就是将内存页面标记为不可被操作系统换出的内存。所以设备驱动程序给这些外设编程时，可以使用页面的物理地址直接访问内存（DMA），从而避免从外存到内存的复制操作。

  • 锁页内存和GPU内存之间的拷贝可以和内核程序同时执行，也就是异步并发执行；