操作系统 - 虚拟内存管理基础篇(一)

操作系统内存基础篇

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

1.1. 进程内存申请

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

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

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

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

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

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发现内存紧张时候,会通过页面置换算法OOMSWAP等机制进行内存回收处理

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的L2L3级缓存按块读取内存,加速内存指令和数据的读取访问;

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

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会执行缺页异常例程,查询物理内存中的空闲物理页面,将进程需要的数据从外存中换入到物理内存中;
    • 若物理内存已满,则采用内存置换算法回收内存(将有修改的数据写会外存,并将驻留位置零)
    • 再尝试换入空闲物理页,更新页表,返回用户空间,重复执行之前的导致异常的指令;