Linux操作系统-(1) 内存管理

操作系统的四个特征： 并发、共享、异步、虚拟

并发：指两个或多个事件在同一时间间隔内发生。在多道程序环境下，一段时间内，宏观上有多个程序在同时运行，而每一时刻，单处理器环境下仅能有一道程序执行，故微观上这些程序还是在分时地交替执行。操作系统的并发性是通过分时实现的。

共享：指系统中的资源可以被多个并发执行的程序共同使用，而不是被其中一个独占。资源共享有两种方式，互斥访问和同时访问。

异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一管到底，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。异步性使得操作系统运行在一种随机的环境下，可能导致进程产生与时间有关的错误。但只要运行环境相同，操作系统必须保证多次运行程序，都获得相同的结果。

虚拟：虚拟性是一种管理技术，把物理上的一个实体变成逻辑上的一个或多个对应物。采用虚拟技术的目的是为用户提供易于使用、方便高效的操作环境。

1. 内存管理

1.1 虚拟地址、逻辑地址、线性地址、物理地址

1.2 内存分配管理方式

内存分配管理包括连续分配管理方式和非连续分配管理方式。

连续分配方式，是指为一个用户分配一个连续的内存空间。主要包括单一连续分配、固定分区分配和动态分区分配。
非连续分配管理方式允许一个程序分散地装入到不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。分页存储管理方式中，又根据运行作业时是否需要把所有页面都装入内存才能运行分为基本分页储存管理方式和请求分页储存管理方式。

1.2.1 基本分页储存管理方式

页面和页面大小。进程中的块称为页(Page)，内存中的块称为页框（Page Frame，或页帧）。外存也以同样的单位进行划分，直接称为块(Block)。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。
地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量W。地址长度为32 位，其中0~~11位为页内地址，即每页大小为4KB；12~~31位为页号，地址空间最多允许有220页。
页表。为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般存放在内存中。

1.2.2 基本分段储存管理方式

段式管理方式按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序、两个子程序、栈和一段数据组成，于是可以把这个用户进程划分为5个段，每段从0 开始编址，并分配一段连续的地址空间（段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的）。其逻辑地址由段号S与段内偏移量W两部分组成。

每个进程都有一张逻辑空间与内存空间映射的段表，其中每一个段表项对应进程的一个段，段表项记录该段在内存中的起始地址和段的长度。

分段管理方式的引入原因：

一般程序分为若干段，如：主程序段、数据段、栈段等，每个段大多是一个相对独立的单位
实现满足信息共享、信息保护、动态链接、以及信息动态增长等需要

1.2.3 段页式存储

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。

在段页式系统中，作业的地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的存储块，对内存的分配以存储块为单位。

基本原理是分段和分页相结合，其地址结构由：段号、段内页号、页内地址三部分组成。在段页式系统中获得一条指令需要三次访问内存，第一次访问内存中的段表，第二次访问内存中的页表，第三次访问内存中的数据。

1.2.4 分页和分段的比较

页式和段式系统有许多相似之处。比如，两者都采用离散分配方式，且都通过地址映射机构来实现地址变换。但概念上两者也有很多区别，主要表现在：

需求：是信息的物理单位，分页是为了实现离散分配方式，以减少内存的碎片，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。
大小：页大小固定且由系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的。段的长度不固定，且决定于用户所编写的程序，通常由编译系统在对源程序进行编译时根据信息的性质来划分。
逻辑地址表示：页式系统地址空间是一维的，即单一的线性地址空间，程序员只需利用一个标识符，即可表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。

1.3 虚拟内存

1.3.1 虚拟存储器的定义和特征

程序的局部性原理是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。

基于局部性的原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行的过程中，当所访问的信息不在内存中时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放要调入内存的信息。这样系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

虚存技术的基本特征：

大的用户空间：通过物理内存和外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离。如32位的虚拟地址理论上可以访问4GB，可能计算机只有256M内存，但硬盘容量大于4GB
部分交换：虚拟存储的调入和调出是对部分虚拟地址空间进行的
不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续

虚存的优缺点：

虚存比实存有以下好处：

扩大地址空间。
内存保护。每个进程运行在各自的虚拟内存空间，互相不能干扰对方。
公平分配内存。采用了虚存之后，每个进程都相当于有通用大小的虚存空间。
当进程需要通信时，可采用虚存共享的方式实现。

使用虚存也是有代价的，主要表现在以下几个方面：

虚存的管理需要建立很多数据结构，这些数据结构也占用额外的内存
虚拟地址到物理地址的转换，增加了指令的执行时间
页面的换入换出需要磁盘I/O，这是很耗时的
如果一页中只有一部分数据，会浪费内存

1.3.2 虚拟内存的实现

虚拟内存的实现有以下三种方式：

请求分页存储管理
请求分段存储管理
请求段页式存储管理

不管哪种方式，均需要一定的硬件支持，主要体现在以下几个方面：

一定容量的内存和外存
页表机制（或者段表机制），作为主要的数据结构
中断机制，当用户程序要访问的部分尚未调入内存，则产生中断
地址变换机制，逻辑地址到物理地址的变换

1.3.3 页式虚拟存储器

以页为基本单位的虚拟存储器叫做页式虚拟存储器。主存空间和虚存空间都划分成若干个大小相等的页，主存（即实存）的页称为实页，虚存的页称为虚页。

虚存地址分为高低两个字段：高位字段为逻辑页号，低位字段为页内地址。实存地址也分为高低两个字段：高位字段为物理页号，低位字段为页内地址。虚存地址到实存地址的变换是通过存放在主存中的页表来实现的。在页表中，对应每一个虚存逻辑页号有一个表项，表项内容包含该逻辑页所在的主存页面地址（物理页号），用它作为实存地址的高字段，与虚存地址的页内地址字段相拼接，产生完整的实存地址，据此来访问主存。

页式虚拟存储器的每页长度是固定的，页表的建立很方便，新页的调入也容易实现。但是由于程序不可能正好是页面的整数倍，最后一页的零碎空间将无法利用而造成浪费。同时，页不是逻辑上独立的实体，这使得程序的处理、保护和共享都比较麻烦。

1.3.4 段式虚拟存储器

段式虚拟存储器中的段是按照程序的逻辑结构划分的，各个段的长度因程序而异。在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，为了把程序虚地址变换成主存实地址，需要一个段表。段表一般驻留在主存中，其中每一行记录了某个段对应的若干信息，包括段号、装入位、段起点和段长等。这里的段号指的是虚拟段号。装入位为“1”，表示该段已调入主存；装入位为“0”，表示该段不在主存中。由于段的大小可变，所以在段表中要给出各段的起始地址与段的长度。段表实际上是程序的逻辑结构段与其在主存中的存放位置之间的关系对照表。

CPU根据虚地址访存时，首先将段号与段表的起始地址相拼接，形成访问段表对应行的地址，然后根据段表的装入位判断该段是否已调入主存。若已调入主存，则从段表读出该段在主存中的起始地址，与段内地址（偏移量）相加，得到对应的主存实地址。

由于段的分界与程序的自然分界相对应，具有逻辑独立性，所以易于实现程序的编译、管理、修改和保护，也便于多道程序共享。但是，因为段的长度参差不齐，起点和终点不定，给主存空间分配带来了麻烦，容易在段间留下不能利用的零碎空间，造成浪费。

1.3.5 段页式虚拟存储器

段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合。它把程序按逻辑单位分段以后，再把每段分成固定大小的页。主存空间也划分为若干个同样大小的页。虚存和实存之间以页为基本传送单位，每个程序对应一个段表，每段对应一个页表。虚地址包含段号、段内页号、页内地址三部分。CPU访问时，首先将段表起始地址与段号合成，得到段表地址，然后从段表中取出该段的页表起始地址，与段内页号合成，得到页表地址，最后从页表中取出实页号，与页内地址拼接形成主存实地址。

段页式存储器综合了前两种结构的优点，但要经过两级查表才能完成地址转换，要多花费一些时间。

1.3.6 页面替换算法

当CPU要访问的数据或指令不在主存中时，产生页面失效（缺页），此时就要从外存调进包含此数据或指令的页，若主存页面已全部占满，就需要采用某种替换算法将主存中的某一页替换出去。

最佳置换算法（Optimal）：一种理论的算法，选着淘汰的页面是以后一定不再使用的页面（理想化的），该算法无法实现，只能作为其他算法好坏的一个评价对比。
先进先出（FIFO）算法：总是最先淘汰最先进去的页面，该算法容易实现。缺点：通常程序调入内存的先后顺序和程序执行的先后顺序不一致，导致缺页率高。会出现Belady异常。
最近最久未使用（LRU）：FIFO算法性能差，LRU算法根据页面调入内存的先后顺序决定，因为无法预测未来的使用情况，就是用过去的使用情况作为将来的使用情况的近似。
最少使用算法（LFU）：在每个页面设置一个移位寄存器记录该页面的访问频率，最近时期最少使用的页面被淘汰

1.3.7 内存碎片

内存碎片是由于多次内存分配造成的，当进行内存分配时，内存格式一般为：（用户使用段）（空白段）（用户使用段），当空白段很小的时候可能不能提供给用户足够需要的空间，可能夹在中间的空白段的不能分配而产生空隙。

内碎片： 在页式虚拟存储系统中，用户作业的地址空间被划分成若干大小相等的页面，存储空间也分成也页大小相等的物理块，但一般情况下，作业的大小不可能都是物理块大小的整数倍，因此作业的最后一页中仍有部分空间被浪费掉了。由此可知，页式虚拟存储系统中存在内零头（碎片）。

外碎片： 在段式虚拟存储系统中，作业的地址空间由若干个逻辑分段组成，每段分配一个连续的内存区，但各段之间不要求连续，其内存的分配方式类似于动态分区分配。由此可知，段式虚拟存储系统中存在外零头（碎片）。

1.4 动态内存分配

C程序运行时在需要额外的存储空间时，一般会使用动态存储器分配器，它维护着一个进程的虚拟存储器区域，称为堆。堆是一个请求二进制零的区域，内核为每个进程维护一个变量brk，指向堆的顶部。

分配器将堆视为一组不同大小的块，每个块为虚拟存储器的一个连续组块，是已分配的或空闲的。

有两种分配器。显式分配器要求应用显式地释放任何已分配的块，如C的 malloc/free 和C++的 new/delete 。隐式分配器则由分配器检测不再被使用的已分配块，并释放块，也称为垃圾收集器，Lisp、ML和Java等高级语言使用垃圾收集。

1.4.1 显式分配器

C标准库提供了 malloc 程序包作为显式分配器，包括 malloc 、 calloc 、 realloc 、 free 函数。

动态存储分配器可以使用 mmap 和 munmap 函数显式地分配和释放堆，还有 sbrk、brk 函数：

#include <unistd.h>

/** 将内核的brk指针增加increment来扩展和收缩堆，increment为0时返回brk当前值
 * @return      返回brk的旧值，出错返回-1，并设errno为ENOMEM */
void *sbrk(intptr_t increment);

int brk(void *end_data_segment);  // 参数为分配或者释放后的堆的绝对地址

显式分配器的要求和目标：

能够处理任意（分配和释放）请求的序列，释放请求必须对应以前分配请求分配的块。
立即响应分配请求，不允许分配器为了提高性能重新排列或者缓冲请求
只使用堆
对齐块，使可以保存任何类型的数据对象，因此大多数系统中分配器返回的块为8字节对齐的。
不修改已分配的块。

1.4.2 隐式空闲链表和显式空闲链表

1. 隐式空闲链表

空闲块是通过头部中的大小字段隐含地连接着的，分配器可以通过遍历堆中的所有块，从而间接地遍历整个空闲块的集合。但是需要某种特殊标记的结束块，在下图的示例中，就是一个设置了已分配位而大小为0的终止头部。

隐式空闲链表由N个块组成，一个块由头部、有效载荷（只包括已分配的块），以及可能的一些额外的填充（为了保证内存字节对齐而需要的填充）和尾部组成。头部大小为4个字节，在强加双字对齐的约束之后，块大小总是8的倍数，所以用高29位来表示存储块大小，剩余3位中利用最低位来表示块是否已分配(1表示已分配，0表示空闲)；尾部和头部的内容一样，加入尾部是为了分配器可以判断出一个块的起始位置和状态。整个堆空间就是一个隐式空闲链表，从低地址向高地址生长，第一个和最后一个8字节标记为已分配，以确定堆的大小。

优点：简单，缺点：任何操作的开销，对链表的搜索与堆中已分配块和空闲块的总数呈线性关系。

2. 显式空闲链表

对于通用的分配器，隐式空闲链表并不适合，因为它的块分配和堆块的总数呈线性关系。可以在空闲块中增加一种显式的数据结构。下面是双向空闲链表的堆块的格式。双向链表使首次适配时间从块总数的线性时间减少到了空闲块数的线性时间。

用一个链表将可用的内存块连接为一个长长的列表，称为空闲链表。将堆组织成双向空闲链表，每一个空闲块结点都包含一个祖先指针和一个后继指针。链表中的每个结点记录一个连续的、未分配的内存小块。结点的结构很简单，只需要记录可用内存小块的首地址和大小即可。

显式链表的缺点是空闲块必须足够大来包含结构，这增大了最小块的大小，也潜在提高了内部碎片的程度。

1.4.3 内存块的选择算法

首次适应法（First Fit）：链表按块地址排序。选择第一个满足要求的空闲块。特点：低地址碎片多，高地址碎片少。
最佳适应法（Best Fit）：链表按空闲块大小排序。选择满足要求的，且大小最小的空闲块。特点：费时间，并且会出现很小的碎片。
最坏适应法（Worst Fit）：链表按空闲块大小排序。选择最大的空闲块。特点：碎片少，容易缺乏大块。
循环首次适应法（Next Fit）：链表按块地址排序。从上次分配位置开始找到第一个满足要求的空闲块。特点：碎片分布的又多又均匀。

1.4.4 内存碎片

造成堆利用率很低的原因是一种称为碎片的现象，当虽然有未使用的存储器但不能用来满足分配请求时，就会发生这种现象。分为内碎片和外碎片。

内部碎片是在一个已分配块比有效载荷大时发生的。

外部碎片是当空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。此时就会向内核请求额外的虚拟存储器来满足需求。

1.4.5 malloc实现

malloc是一个库函数，不同的操作系统上具体实现细节是不同的，以下就以linux条件下进行分析：linux采用的是glibc中堆内存管理ptmalloc实现，虚拟内存的布局规定了malloc申请位置以及大小，malloc一次性能申请小内存（小于128KB），分配的是在堆区（heap），用sbrk()进行对齐生长，而malloc一次性申请大内存（大于128KB时）分配到的是在映射区，而不是在堆区，采用的mmap()系统调用进行映射。当然虚拟地址只是规定了一种最理想的状态，实际分配还是要考虑到物理内存加交换内存总量的限制，因为每次分配，特别是大内存分配采用mmap（）映射内存需要记录物理内存加交换内存地址，所有物理内存加交换内存限制了malloc实际分配。比如32位情况下，最新版本的linux的映射区在用户空间区的3G位置，而映射区向下生长，所以理想情况下大概能有2.9GB（除去开始地址128M）,如果你的物理内存加交换区只有2G，malloc一次申请最多1.8G左右，如果你的物理内存加交换区大于4G，那么最多能有2.9G或者2.8G左右。

在Linux下，glibc 的malloc提供了下面两种动态内存管理的方法：堆内存分配和mmap的内存分配，此两种分配方法都是通过相应的Linux 系统调用来进行动态内存管理的。具体使用哪种方式分配，根据glibc的实现，主要取决于所需分配内存的大小。

一般情况中，应用层面的内存从进程堆中分配，当进程堆大小不够时，可以通过系统调用brk来改变堆的大小，但是在以下情况，一般由mmap系统调用来实现应用层面的内存分配：
A、应用需要分配大于1M的内存，B、在没有连续的内存空间能满足应用所需大小的内存时。

调用brk实现进程里堆内存分配
在glibc中，当进程所需要的内存较小时，该内存会从进程的堆中分配，但是堆分配出来的内存空间，系统一般不会回收，只有当进程的堆大小到达最大限额时或者没有足够连续大小的空间来为进程继续分配所需内存时，才会回收不用的堆内存。在这种方式下，glibc会为进程堆维护一些固定大小的内存池以减少内存碎片。
使用mmap的内存分配
在glibc中，一般在比较大的内存分配时使用mmap系统调用，它以页为单位来分配内存的（在Linux中，一般一页大小定义为4K），这不可避免会带来内存浪费，但是当进程调用free释放所分配的内存时，glibc会立即调用unmmap，把所分配的内存空间释放回系统。

注意：这里我们讨论的都是虚拟内存的分配（即应用层面上的内存分配），主要由glibc来实现，它与内核中实际物理内存的分配是不同的层面，进程所分配到的虚拟内存可能没有对应的物理内存。如果所分配的虚拟内存没有对应的物理内存时，操作系统会利用缺页机制来为进程分配实际的物理内存。

相关知识：

1. Linux进程的虚拟空间及其划分

在32位硬件平台上，Linux的逻辑地址为32位，因此，每个进程的虚拟地址空间为4GB，在4GB的空间中，操作系统占用了高端的1GB，而低端的3GB则留给用户程序使用。如下图所示：

2. Linux内核虚拟存储器

Linux中1GB的内核虚拟存储器空间又被划分为物理内存映射区、虚拟内存分配区、高端页面映射区、专用页面映射区和系统保留映射区这几个区域。
一般情况下，物理内存映射区最大长度为896MB，系统的物理内存被顺序映射到物理内存映射区中。当系统物理内存大于896MB时，超过系统物理内存的那部分内存称为高端内存（小于896MB的系统物理内存称为常规内存），内核在存取高端内存时必须将它们映射到高端内存映射区中。下图可以反映出Linux内核虚拟存储器与物理内存之间的映射关系。

注意：物理内存中0~896MB区域通常由内核使用，当然内核不用时用户程序可以使用；896MB以上的区域通常由用户程序来使用。

3. Linux用户虚拟存储器

Linux用户虚拟存储器总是通过页表访问内存，决不会直接访问。如下图所示：

参考：
1. 知乎-malloc 的实现涉及物理内存，虚拟内存
 2. 嵌入式动态内存分配过程
 3. Linux的内存映射
 4. linux内核内存管理

1.5 Linux共享内存实现

共享内存允许两个或多个进程共享一个给定的存储区，因为数据不需要来回复制，所以是最快的一种进程间通信机制。共享内存可以通过mmap()映射普通文件（特殊情况下还可以采用匿名映射）机制实现，也可以通过系统V共享内存机制实现。应用接口和原理很简单，内部机制复杂。为了实现更安全通信，往往还与信号灯等同步机制共同使用。

实现共享内存主要有如下两种机制：

mmap的机制如：就是在磁盘上建立一个文件，每个进程存储器里面，单独开辟一个空间来进行映射。如果多进程的话，那么不会对实际的物理存储器（主存）消耗太大。
shm机制：每个进程的共享内存都直接映射到实际物理存储器里面。

两种机制的对比：

1、mmap有两种方式，一种是映射内存，它把普通文件映射为实际物理内存页，访问它就和访问物理内存一样（这也就和shm的功能一样了）（同时不用刷新到文件）
2、mmap可以映射文件，不确定会不会像windows“内存映射文件”一样的功能，如果是，那么他就能映射好几G甚至好几百G的内存数据，对大数据处理将提供强大功能了？？？
3、shm只做内存映射，和mmap第一个功能一样！只不过不是普通文件而已，但都是物理内存。

1.6 Windows下内存管理

1：虚拟内存，最适合用来管理大型对象或者结构数组；
2：内存映射文件，最适合用来管理大型数据流（通常来自文件）以及在单个计算机上运行多个进程之间共享数据；
3：内存堆栈，最适合用来管理大量的小对象。
　
Windows操纵内存可以分两个层面：物理内存和虚拟内存。
其中物理内存由系统管理，不允许应用程序直接访问

本文由『后端精进之路』原创，首发于博客 http://teckee.github.io/ , 转载请注明出处

搜索『后端精进之路』关注公众号，立刻获取最新文章和价值2000元的BATJ精品面试课程。