操作系统内存基础篇

1. 操作系统对内存的管理

1.1. 进程内存申请

物理内存也叫主存，用的大都是 DRAM(随机访问内存)，只有 OS 内核能直接访问物理内存，进程只能通过虚拟内存(虚拟地址空间)访问；

Linux 内核为每个进程提供了独立的虚拟地址空间，且是连续的，这样进程可以很方便的访问虚拟内存；

虚拟地址空间又分为内核空间和用户空间，不同字长(CPU 指令可以处理的数据最大长度)分为32和64位，对应的内核与用户空间大小分别为[1G<内核>，3G<用户>]，[128T<内核>，未定义，128T<用户>]；

进程的用户态和内核态(ring0和ring3)，进程在用户态只能访问用户空间内存，只有陷入(中断、异常、系统调用)到内核态才可以访问内核空间内存。

每个进程都包含内核空间，实际上是相同的物理内存，这样进程陷入切换到内核态后，可以很方便的访问内核空间内存；

1.2. 进程的内存段

用户空间内存包括多个不同的内存段，比如只读段(代码和常量)、数据段(全局变量)、堆(malloc()动态分配的内存，由低到高地址)、文件映射段(mmmap()动态库、共享内存，由高到低)、栈(局部变量、函数调用上下文，栈大小一般是固定的，通常是 8M)等。

第一个内核线程initproc，初始化堆栈指针，初始化 initproc，初始化内核堆栈，内存共享，将initproc放入就绪队列，唤醒initproc;

1.3. fork-and-exec

程序启动过程，父进程通过fork()系统调用 fork 出一个子进程，OS 拷贝父进程的段内存(数据、代码、堆栈)，然后利用exec()加载和执行程序取代拷贝的进程信息(系统调用)；

子进程fork()返回 0,父进程fork()返回子进程 pid，同时利用wait()等待子进程的exit()退出事件通知；

由于 fock 开销太大（子进程分配内存、拷贝父进程的内存和 CPU 寄存器信息、关闭父进程的打开的文件资源)，当 fork 后，99%情况会立马执行 exec 覆盖掉拷贝的内存，因此两者可以结合起来，即vfork；

vfork：也称为轻量级 fork，不在和 fork 一样需要拷贝内存映像，同时进程立即执行 exec。目前 Linux 下的 fork 也多采用COW(Copy On Write)写时复制技术进行优化。

1.4. COW - 写时复制

COW：可以理解 COW 是一种写资源优化策略，优化性能提升；通常，写时复制用于解决并发问题。即程序执行 vfork 系统调用，系统不是立即对内存的进行 Copy 操作，而只是进行指针标记资源，直至调用者试图 Write（修改资源）内容时候，才去真正的 Copy，因此可以理解为延时复制。一般把这种被共享访问的页被标记为只读，当一个 task 试图向内存中写入数据时，内存管理单元（MMU）抛出一个异常，内核处理该异常时为该 task 分配一份物理内存并复制数据到此内存，重新向 MMU 发出执行该 task 的写操作，然后创建一个副本。

虽然 fork 拷贝了整个父进程的内存虚拟地址空间信息，但也做了一些初始化和清理操作，比如自己 PID、PPID、清理事件通知、进程资源使用率重置、父进程的锁记录等，另外子进程继承了父进程的文件打开资源、消息队列等信息；

1.5. 堆栈 Stack 与堆 Heap

• 堆栈是为执行线程预留的暂存空间
  • 调用函数时，将在堆栈顶部保留一个块，用于存放局部变量和一些簿记数据。当该函数返回时，该块将变为未使用状态，并且可以在下次调用该函数时使用。
  • 堆栈始终按 LIFO（后进先出）顺序保留；最近保留的块始终是下一个要释放的块，这使得跟踪堆栈非常简单。
  • 从堆栈中释放一个块无非就是调整一个指针。
• 堆是为动态分配预留的内存
  • 与堆栈不同，堆中的块分配和释放没有强制的模式，您可以随时分配一个块，并随时释放它，这使得跟踪在任何给定时间分配或释放堆的哪些部分变得更加复杂。
  • 有许多自定义堆分配器可用于调整不同使用模式的堆性能。
• 每个线程都有一个堆栈，而应用程序通常只有一个堆（尽管对于不同类型的分配有多个堆并不少见）
  • 创建线程时，操作系统会为每个系统级线程分配堆栈。通常，语言运行库会调用 OS 来为应用程序分配堆。
• 作用范围
  • 堆栈连接到线程，因此当线程退出时，堆栈将被回收。
  • 堆是在运行时在应用程序启动时分配的，并在应用程序（技术上已退出）退出时被回收。
• 大小设置与变化
  • 创建线程时设置堆栈的大小。
  • 堆的大小是在应用程序启动时设置的，但是可以随需要的空间而增长（分配器从操作系统请求更多的内存 - 动态内存分配）。
• 速度差异
  • 堆栈速度更快，因为访问模式使分配和释放内存变得很简单（指针/整数只是增加或减少），而堆的分配或释放则要复杂得多。
  • 同样，堆栈中的每个字节都倾向于被非常频繁地重用，这意味着它倾向于被映射到处理器的高速缓存中，从而使其非常快。
  • 堆的另一个性能损失是，堆（通常是全局资源）通常必须是多线程安全的，即每个分配和释放都必须（通常）与程序中的“所有”其他堆访问同步。

1.6. 堆栈内存分配与回收

当我们在程序中定义了一个局部变量，比如一个整数数组int data[64]，就定义了一个可以存储 64 个整数的内存段。

由于这是一个局部变量，它会从内存空间的栈中分配内存。栈内存由系统自动分配和管理，一旦程序运行超出了这个局部变量的作用域，栈内存就会被系统自动回收，所以不会产生内存泄漏的问题。

1.7. 动态内存分配与回收

很多时候，我们事先并不知道数据大小，所以你就要用到标准库函数malloc()， 在程序中动态分配内存。这时候，系统就会从内存空间的堆中分配内存。堆内存由应用程序自己来分配和管理。

除非程序退出，这些堆内存并不会被系统自动释放，而是需要应用程序明确调用库函数free()来释放它们，如果应用程序没有正确释放堆内存，就会造成内存泄漏。

malloc 是 C 函数库提供的，对应系统调用上有：brk()对小块内存分配，即<128K，以及mmap()对大块内存分配，即>128K，前者由于内存没有归还系统，可以减少缺页率；后者由于通过free()、unmap()等归还系统，导致大块内存缺页异常，导致缺页率升高;

对 OS 来说，如果仅申请不回收内存，会导致内存泄露，因此需要有借有还；

到此我们知道了，当 OS 发现内存紧张时候，会通过页面置换算法、OOM、SWAP等机制进行内存回收处理

2. 虚拟内存

• 背景：
  1. 不同层次的存储差异很大，最慢的磁盘到最快的寄存器，差别百万倍，一次磁盘访问需要 10ms，一次内存访问 10ns，而寄存器仅 1ns
  2. 不同进程的存储抽象，地址空间
  3. 内存不足：覆盖(手动，进程内)、SWAP 交换(OS 自动进行进程间内外存倒腾)、虚拟存储(以页为单位，自动装入更大的程序)
• 目标:
  1. 只装载部分程序到内存中，从而可以运行比物理内存更大的程序；(OS 完成)
  2. 实现内外存交换，从而获得更多的内存空间；
• 局部性：空间局部性(指令和数据在相邻区域)、时间局部性(数据上下文)、分支局部性(循环)
• 原理:
  1. 装载程序时候，只将指令执行需要的页或段装入内存；
  2. 指令执行中需要的指令或数据不在页表或段表中，称之为缺页或缺段，相应的缺页异常会通知 OS 调入对应的数据载入内存，并更新页表或段表
  3. OS 将暂时不用的内存，置换到外存
• 实现: 虚拟页式存储、虚拟段式存储
• 特征:
  1. 不连续：物理内存分配不连续、虚拟地址空间使用非连续
  2. 局部置换
  3. 大用户空间

2.1. 虚拟内存映射

操作系统，对虚拟内存的管理方式通过段式存储和页式存储方式管理，即段表和页表管理虚拟内存与物理内存的映射(即虚拟内存地址映射到物理内存地址)，页表存储在 CPU 中的MMU单元中，CPU 通过 MMU 对内存管理，同时利用 CPU 的L2或L3级缓存按块读取内存，加速内存指令和数据的读取访问；

缺页异常：当进程访问虚拟地址在页表中查不到记录时，系统会产生一个缺页异常，操作系统调用对应的异常服务例程，进入内核空间分配物理内存、更新页表，再返回用户空间，恢复进程的运行；

TLB(Translation Lookaside Buffer)快表: TLB 其实就是 MMU 中页表的高速缓存，由于进程的虚拟地址空间是独立的，TLB 又比 MMU 快得多，所以可以减少进程的上下文切换，减少 TLB 的刷新次数，从而提高 CPU 性能；

MMU按页管理，意思是 MMU 并不是以字节来管理内存，而是规定一个固定的内存映射最小单位，即页表大小来做基本单元管理，通常是 4K: cat /proc/meminfo|grep PageTables

多级页表，由于一页的容量很小，如果单张页表管理则整个页表会过大，比如 32 位系统(4G 虚拟内存空间，4G/4K=100 万页表记录)，Linux 通过HugePage和多级页表进行页表管理(其他的还有反置页表)；

CR3寄存器：存储页表基址(PTBR, Page Tabel Base Register)；

2.2. 逻辑物理页号转换为物理页帧号

3. 页表概念

每个进程都有一个页表，页表的基地址存储在 CPU 中的CR3寄存器内；一个页表项代表一个页，页表项包含驻留位、修改位、引用位等信息。

3.1. 页表结构

3.2. 页表项结构

3.3. TLB 快表 - 页表的性能提升

针对页表过大，操作系统还提供了多级页表、反置页表等概念；

访问一个内存单元需要 2 次内存访问：获取页表项、再访问数据，单页表过大，引出多级页表、大页等概念，同时 CPU 为了更快的性能访问，加入了 TLB 快表；

4. 缺页异常处理流程

1. CPU 在执行指令时(比如MOV REG, 8129)，CPU 会通过 MMU 从页表中检测页号是否有效，有效则直接读入对应的物理内存信息到 CPU 中；
   • 若 MMU 从页表检测不到无物理页帧映射记录，则会产生一个缺页异常；
2. OS 收到缺页异常会执行缺页异常例程，例程会查询在外存中对应的数据信息，若有空闲物理页帧，则置换入内存并更新页表项；
   • 若调入新页面而内存已满时候（没有找到空闲物理页帧），操作系统会调用相关置换算法，回收系统内存，再进行相关内存换入操作；
3. 物理页帧换入后，修改页表项驻留位为 1 和对应的物理页帧编码；
4. 返回用户空间；
5. 重新执行导致异词的指令，恢复进程运行；

虚拟页式存储中，被置换到外存中的物理内存采用特殊的格式存储，代码段采用可执行二进制文件、动态载入的外部库程序段采用动态调用的库文件、其他段放入交换区间中；

除此外，操作系统还会通过 OOM、SWAP 等机制进行内存回收或兑换，以提供内存给优先级高的进程；

5. 局部置换算法

相关页面置换算法有局部置换算法(当前进程占用的物理页，包含最优、FIFO、LRU、时钟置换、LFU)和全局置换算法(所有可换出的物理页，包含工作集、缺页率算法)；

5.1. LRU 算法实现

使用链表维护一个按时间访问页表的链表，表头是最近访问的页表，表尾是最久未被访问的页表：

1. 当有页面访问，搜索链表，当搜索到页表项或不在页表内，则将页表插入表头；
2. 当链表满需要进行页面置换的情况，从队尾移除相应的页表；

缺点是开销较大，需要与其他数据结构匹配使用

5.2. Belady 现象

Belady 现象指增大物理分配页帧数，反倒缺页率会增加；

FIFO 有 Belady 现象(没有考虑历史的物理页帧访问频率)，而 LRU 没有 Belady 现象(考虑了之前的物理页帧访问频率)；

6. 全局置换算法

核心思想：由于进程在不同时刻，对物理内存的需要时不一样的，同时操作系统对内存的需要也是变化的，全局置换算法就是提供给进程可变的物理页数量。

6.1. 单一进程的工作集

工作集：指的是一个进程当前正在使用的逻辑页面的集合，其映射到不同的物理页帧上；

常驻集：即停留在物理内存区域内的工作集，没有被换出到外存中的页面集合。当常驻集区域稳定，缺页率也逐渐区域稳定；

工作集的变化：基于程序的局部性原理，当进程开始执行时，由于访问新页，缺页率较高，随着访问新页逐步趋于稳定，直至到以下一个局部性趋于，重复该过程；

6.2. CPU 利用率与并发进程数的关系

6.3. 缺页率

缺页率=缺页数量/页表访问次数，影响缺页率的因素：页面置换算法、分配给进程的物理页帧数、物理页帧大小、程序编写方式相关；

6.4. 抖动问题

• 抖动现象：进程物理页太少，不能包含工作集，造成大量缺页异常，频繁置换内外存页表单元，从而导致进程运行速度变慢；
• 原因：是因为随着进程增加，分配给每个进程的物理内存数减少，导致缺页率增加；

需要达到缺页率与进程并发数量的平衡；

6.5. 负载控制

讨论了这么多，实际上就是需要达到一个并发进程和物理内存的平衡(下图的虚线区间内)，即负载控制，从而保证系统的整体资源利率最大化！

7. 回答几个问题

• 虚拟地址空间是什么？
  • 进程访问虚拟地址空间，Linux 内核为每个进程提供了独立的虚拟地址空间，且是连续的，这样进程可以很方便的访问虚拟内存；
  • 虚拟地址空间又分为内核空间和用户空间；
  • 用户空间又分代码段、数据段、堆Heap、内存映射段、栈Stack几大块；
  • 虚拟地址空间，即单一进程的虚拟内存区域，每个进程都有自己的虚拟地址空间；
• pcb 存储在哪？
  • pcb 存在在内核空间，由 os 管理 pcb；
  • pcb 指进程控制块，pcb 包括进程标识、cr3 页表基址、进程 cpu 执行信息(SP、寄存器)、虚拟内存地址信息，每个 pcb 代表着一个进程对象；
  • 操作系统通过 pcb 管理进程，在各个进程状态队列(就绪、运行、等待、挂起)，负责相关进程的上下文切换；
• fork 过程？
  • 创建一个进程，可以通过系统初始进程(initproc)、用户执行(fork)、请求服务创建等方式创建；
  • 拷贝父进程虚拟地址空间，同时会做一些初始化和清理操作；
• 缺页异常流程？
  • 从 cpu 执行一条内存操作MOV REG 8096指令来说起，CPU 中 MMU 内存管理单元会先查 TLB 快表，若没有相关页表 Hash 记录，则查询页表；
  • MMU 在查询页表过程中，若没有找到对应的页表项纪录则会触发缺页异常；
  • OS 接收到异常后，调用对应的异常例程，发现是缺页例程；OS 会执行缺页异常例程，查询物理内存中的空闲物理页面，将进程需要的数据从外存中换入到物理内存中；
  • 若物理内存已满，则采用内存置换算法回收内存(将有修改的数据写会外存，并将驻留位置零)
  • 再尝试换入空闲物理页，更新页表，返回用户空间，重复执行之前的导致异常的指令；