段式存储

基本思想

页面是主存物理空间中划分出来的等长的固定区域。分页方式的优点是页长固定，因而便于构造页表、易于管理，且不存在外碎片。但分页方式的缺点是页长与程序的逻辑大小不相关。例如，某个时刻一个子程序可能有一部分在主存中，另一部分则在辅存中。这不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦。

另一种划分可寻址的存储空间的方法称为分段。段是按照程序的自然分界划分的长度可以动态改变的区域。通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中，并且每个程序可以有多个相同类型的段。

段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。

将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

分段地址结构

作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例程序段、数据段等。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间是二维的。

下图中，段号是16位，段内偏移量是为16位，则一个作业最多可有216=65536个段，最大段长为64KB。

在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在段式系统中，段号和段内偏移量必须由用户显示提供，在髙级程序设计语言中，这个工作由编译程序完成。

在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：有效位（指明该段是否已经调入主存）、段起址(该段在实存中的首地址)和段长（记录该段的实际长度）。

段表用于实现从逻辑段到物理内存区的映射。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。

%!(EXTRA markdown.ResourceType=, string=, string=)

地址变换

针对每一个虚拟地址，存储管理部件首先以段号S为索引访问段表的第S个表项。若该表项的有效位为1，则将虚拟地址的段内地址D与该表项的段长字段比较；若段内地址较大则说明地址越界，将产生地址越界中断；否则，将该表项的段起址与段内地址相加，求得主存实地址并访存。如果该表项的有效位为0，则产生缺页中断，从辅存中调入该页，并修改段表。段式虚拟存储器虚实地址变换过程如图所示。

绝对地址=根据段号找到段表中的起始地址+段内地址 (如果段内地址超过限长则产生“地址越界”程序性中断事件达到存储保护)

段的共享和保护

在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据。

不能修改的代码称为纯代码或可重入代码（它不属于临界资源）。这样的代码和不能修改的数据是可以共享的，而可修改的代码和数据则不能共享。（需要修改数据时，每个访问进程必须配置局部数据区，并在执行中可能改变的部分拷贝到该区域）

与分页管理类似，分段管理的保护方法主要有两种：一种是存取控制保护，另一种是地址越界保护。地址越界保护是利用段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度则产生越界中断；再利用段表项中的段长和逻辑地址中的段内位移进行比较，若段内位移大于段长，也会产生越界中断。

分段存储方式的优缺点

分页对程序员而言是不可见的，而分段通常对程序员而言是可见的，因而分段为组织程序和数据提供了方便。与页式虚拟存储器相比，段式虚拟存储器有许多优点：

1. 段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。
2. 段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。
3. 方便编程，分段共享，分段保护，动态链接，动态增长

因为段的长度不固定，段式虚拟存储器也有一些缺点：

1. 主存空间分配比较麻烦。
2. 容易在段间留下许多碎片，造成存储空间利用率降低。
3. 由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持。

页式存储

页式存储管理页式存储管理中，物理内存被划分为大小相同的基本分配单位，我们称为页帧，页帧的大小必须是2的幂次方，这样进行地址转换的时候比较快，可以通过二进制移位实现。比如32位系统中，4Kbyte是常见的页帧大小。而逻辑内存也被划分为大小相同的基本分配单位，我们称为页面，页面与页帧大小必须相等。

页帧与页面一个是对物理内存地址一个是对逻辑内存地址而言的。因此页式存储管理中要处理逻辑地址与物理地址的转换，也就变为对页面到页帧的转换。而储存映射关系的表我们称为页表，由操作系统维护。具体硬件实现则是由MMU和TLB共同实现。

帧

物理内存被分为大小相等的帧，物理内存的地址用一个二元组表示%!(EXTRA markdown.ResourceType=, string=, string=)

，其中 f 是帧号，比如一个帧号由F bit表示，那也就是说一共有%!(EXTRA markdown.ResourceType=, string=, string=)

个帧，o 是帧内偏移，比如偏移由S bit表示，那么一个帧内有

字节。那么物理地址 = 

页

逻辑内存被划分为大小相等的页，表示方式与帧类似。由于帧与页的大小是相等的。因此在映射关系中 ，页内偏移与帧内偏移是相等的，但是页号与帧号通常是不相等的。因为逻辑内存是连续的，物理地址不是连续的。

页表

那么如何实现页与帧之间的地址转换呢？也就是如何实现逻辑地址与物理地址之间的转换。如下图：操作系统维护页表，页表内存储页号与帧号之间的映射关系。页表基址表明了页表存储在什么地方。比如当程序P执行过程中，CPU要访问(p, o)，操作系统通过页表得到帧号f，通过(f, o)找到物理内存地址。而由于帧和页的大小是2的幂次方，因此实际上地址就是将 f 左移 S 位之后加上 o 即得到物理地址。

每个进程都有一个页表，且有以下特点：

• 每个页面对应一个页表项
• 页表随进程运行状态而动态变化
• 页表的起始地址即基址存储在页表基址寄存器（PTBR: Page Table Base Register）中

页表内除了存储前面提过的帧号，还存储了一些页表项标志位：

• 存在位，记录该页号是否有对应的帧
• 修改位，记录页面的内容是否修改了
• 引用位，记录是否有对该页面的访问

那么实际操作中，如下图，标志位为0意味着没有给页分配帧，就可以动态的进行变化。

页表项

页目录和页表的表项格式如图4-18所示。其中位31～12含有物理地址的高20位，用于定位物理地址空间中一个页面（也称为页帧）的物理基地址。表项的低12位含有页属性信息。

• P:位0是存在（Present）标志，用于指明表项对地址转换是否有效。P=1表示有效；P=0表示无效。在页转换过程中，如果说涉及的页目录或页表的表项无效，则会导致一个异常。如果P=0，那么除表示表项无效外，其余位可供程序自由使用，如图4-18b所示。例如，操作系统可以使用这些位来保存已存储在磁盘上的页面的序号。
• R/W:位1是读/写（Read/Write）标志。如果等于1，表示页面可以被读、写或执行。如果为0，表示页面只读或可执行。当处理器运行在超级用户特权级（级别0、1或2）时，则R/W位不起作用。页目录项中的R/W位对其所映射的所有页面起作用。
• U/S:位2是用户/超级用户（User/Supervisor）标志。如果为1，那么运行在任何特权级上的程序都可以访问该页面。如果为0，那么页面只能被运行在超级用户特权级（0、1或2）上的程序访问。页目录项中的U/S位对其所映射的所有页面起作用。
• A:位5是已访问（Accessed）标志。当处理器访问页表项映射的页面时，页表表项的这个标志就会被置为1。当处理器访问页目录表项映射的任何页面时，页目录表项的这个标志就会被置为1。处理器只负责设置该标志，操作系统可通过定期地复位该标志来统计页面的使用情况。
• D:位6是页面已被修改（Dirty）标志。当处理器对一个页面执行写操作时，就会设置对应页表表项的D标志。处理器并不会修改页目录项中的D标志。
• AVL:该字段保留专供程序使用。处理器不会修改这几位，以后的升级处理器也不会。

页式访问的性能问题

内存访问的性能问题：访问一个物理内存单元需要两次访问内存。第一次先访问页表进行查询，第二次才是访问物理内存获取数据。页表的大小问题：页表可能非常大。比如一个64位机器（

字节内存），假如一页大小为1024字节（%!(EXTRA markdown.ResourceType=, string=, string=)

），那么一共可以产生

页（帧），64位的系统想要表示一个帧的地址就需要64位，也就是8字节，也就是说想表示一个帧，即使不考虑标志位也需要8字节，那使用很多页面，比如全部使用

页，就需要%!(EXTRA markdown.ResourceType=, string=, string=)

字节，仅仅存储页表就要这么多字节占用了很多空间。

针对这些问题，也有一些对应的解决方案：

• 缓存：程序执行时具有连续性即相邻性，访问了一个数组第一个元素，下一个极有可能访问第二个元素，因此当我缓存下来页表项，利用缓存可以极大可能地访问到想要的数据。
• 间接访问：将长页表切断，实际就是多级页表，一层层去查询。

为了缓解上述性能问题，出现了一些解决方案，比如快表、多级页表和反置页表。

快表（TLB: Translation Look-aside Buffer）

快表是指缓存近期访问过的页表项。

它有以下特点：

TLB使用关联存储（associative memory）实现，具备快速访问性能，因为关联存储在CPU内；如果TLB命中，可以直接访问物理内存；如果TLB未命中，仍需查询页表，并将对应表项更新到TLB中。

如果能够很大比例地命中，就可以大幅度提高访问效率。

多级页表

多级页表顾名思义，类似于树的概念，一级一级往下查询，图示如下：比如图中是三级页表，逻辑地址的表示由四元组%!(EXTRA markdown.ResourceType=, string=, string=)

表示。p1、p2、p3 分别表示在各级页表中的偏移，o 则表示物理内存中的偏移。通过多级页表可以有效减少每级页表的长度。

具体操作中，比二级页表的操作如下：一级页表的起始地址存储在CPU寄存器CR3中，然后一级一级根据偏移获取实际内存地址。

优势：

1. 使用多级页表可以使得页表在内存中离散存储。多级页表实际上是增加了索引，有了索引就可以定位到具体的项。举个例子：比如虚拟地址空间大小为4G，每个页大小依然为4K，如果使用一级页表的话，共有2^20个页表项，如果每一个页表项占4B，那么存放所有页表项需要4M，为了能够随机访问，那么就需要连续4M的内存空间来存放所有的页表项。随着虚拟地址空间的增大，存放页表所需要的连续空间也会增大，在操作系统内存紧张或者内存碎片较多时，这无疑会带来额外的开销。但是如果使用多级页表，我们可以使用一页来存放页目录项，页表项存放在内存中的其他位置，不用保证页目录项和页表项连续。
   2。 使用多级页表可以节省页表内存。使用一级页表，需要连续的内存空间来存放所有的页表项。多级页表通过只为进程实际使用的那些虚拟地址内存区请求页表来减少内存使用量（出自《深入理解Linux内核》第三版51页）。举个例子：一个进程的虚拟地址空间是4GB，假如进程只使用4MB内存空间。对于一级页表，我们需要4M空间来存放这4GB虚拟地址空间对应的页表，然后可以找到进程真正使用的4M内存空间。也就是说，虽然进程实际上只使用了4MB的内存空间，但是为了访问它们我们需要为所有的虚拟地址空间建立页表。但是如果使用二级页表的话，一个页目录项可以定位4M内存空间，存放一个页目录项占4K，还需要一页用于存放进程使用的4M（4M=1024*4K，也就是用1024个页表项可以映射4M内存空间）内存空间对应的页表，总共需要4K（页表）+4K（页目录）=8K来存放进程使用的这4M内存空间对应页表和页目录项，这比使用一级页表节省了很多内存空间。当然，在这种情况下，使用多级页表确实是可以节省内存的。但是，我们需要注意另一种情况，如果进程的虚拟地址空间是4GB，而进程真正使用的内存也是4GB，如果是使用一级页表，则只需要4MB连续的内存空间存放页表，我们就可以寻址这4GB内存空间。而如果使用的是二级页表的话，我们需要4MB内存存放页表，还需要4KB内存来存放页目录项，此时多级页表反倒是多占用了内存空间。注意在大多数情况都是进程的4GB虚拟地址空间都是没有使用的，实际使用的都是小于4GB的，所以我们说多级页表可以节省页表内存。

劣势：

使用以及页表时，读取内存中一页内容需要2次访问内存，第一次是访问页表项，第二次是访问要读取的一页数据。但如果是使用二级页表的话，就需要3次访问内存了，第一次访问页目录项，第二次访问页表项，第三次访问要读取的一页数据。访存次数的增加也就意味着访问数据所花费的总时间增加。

反置页表

反置页表也是为了减少页表占用存储空间的一种做法。对于大地址空间系统，比如64位系统，多级页表变的非常繁琐，比如5级页表，正常情况下总共需要6次查询。并且逻辑地址空间的增长速度快于物理地址空间。每个进程有一个页表，随进程数量增加页表占用的存储空间也会增加。

针对上述情况，出现了页寄存器，页寄存器与反置页表思路相同：

• 不让页表与逻辑地址空间的大小相对应
• 让页表与物理地址空间的大小相对应

通过这个思路就可以使页表占用空间与进程数目没有关系，而至于物理内存的大小有关。

页寄存器

理解了页寄存器就可以轻松理解反置页表。

页寄存器将每个物理帧与与一个页寄存器关联，寄存器内存储以下内容：

• 使用位：此帧是否被进程占用
• 占用页号：对应的逻辑页号p
• 保护位：比如可读、可写等性质

由上面的内容我们可以看到页寄存器的优点是与逻辑地址空间大小无关，并且大小相对物理内存而言很小。

缺点是需要在页寄存器中存储页号，也就是帧号是键，页号是值，而进程运行时CPU产生的是逻辑地址页号，因此需要在页寄存器中搜索逻辑地址的页号。那么这种搜索是比较困难的。

实际操作中，采用hash将页号映射到帧号，提高检索效率。这样又产生一个问题就是hash冲突，出现冲突时遍历冲突链表，找到需要的帧号。同时还可以将快表的思想融入进来，缓存使用过的页号帧号映射。引入快表又引入了新的问题，快表存储在CPU缓存中容量被限制到很小，同时快表的功耗是很大的。

反置页表

反置页表也是基于hash映射查找页对应的帧，但是反置页表将进程号也考虑进来，对进程号和页号同时进行hash。这里我自己的理解是最初给进程分配帧的时候就是根据哈希值进行分配的，因此查找时自然可以根据哈希值进行查询。冲突解决方式依然是链表的方式解决，查询发现第一个地址内的进程号与页号与需要的进程号与页号不一致时则继续查询链表中的下一个节点。

过程如下图：哈希值加反置页表基址得到反置页表中的位置，验证进程号和页号，命中则根据hash结果查询物理内存。

具体实现看下图。pid和vpn（virtual page number）共同参与哈希，得到一个物理地址，根据这个地址去查询反置页表，验证pid和vpn是否匹配，不匹配则查询next中存储的地址，此时匹配，则访问此时对应的物理地址。

段页式存储

原理

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

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

在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量：

%!(EXTRA markdown.ResourceType=, string=, string=)

注意：在一个进程中，段表只有一个，而页表可能有多个。

在进行地址变换时，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。如图所示，进行一次访问实际需要三次访问主存，这里同样可以使用快表以加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。

优缺点

优点

1. 它提供了大量的虚拟存储空间。
2. 能有效地利用主存，为组织多道程序运行提供了方便。

缺点：

1. 增加了硬件成本、系统的复杂性和管理上的开消。
2. 存在着系统发生抖动的危险。
3. 存在着内碎片（页内的碎片）。
4. 还有各种表格要占用主存空间。

目的

解决计算机系统时常出现内存空间不够用问题

解决办法

覆盖（overlay）

依据程序逻辑结构，将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域

目标：在较小的可用内存中运行较大的程序

1. 必要部分（常用功能）的代码和数据常驻内存
2. 可选部分（不常用功能）放在其他程序模块中,只在需要用到时装入内存
3. 不存在调用关系的模块可相互覆盖，共用同一块内存区域
   注：不存在相互调用关系可以分成一个覆盖区
   

交换（swapping）

操作系统自动把暂时不能执行的程序保存到外存中

目标：增加正在运行或需要运行的程序的内存

换入换出的基本单位（整个进程的地址空间）；

换出（swap out）：把一个进程的整个地址空间保存到外存；

换入（swap in）：将外存中某进程的地址空间读入到内存；

虚拟存储

在有限容量的内存中，以页为单位自动装入更多更大的程序

目标：

• 只把部分程序放到内存中，从而运行比物理内存大的程序由操作系统自动完成，无需程序员的干涉
• 实现进程在内存与外存之间的交换，从而获得更多的空闲内存空间在内存和外存之间只交换进程的部分内容
  

思路：将不常用的部分内存块暂存到外存

原理：装载程序时，只将当前指令执行需要的部分页面或段装入内存。指令执行中需要的指令或数据不在内存（称为缺页或缺段）时，处理器通知操作系统将相应的页面或段调入内存，操作系统将内存中暂时不用的页面或段保存到外存

实现方式：虚拟页式存储；虚拟段式存储

基本特征：

• 不连续性：
  物理内存分配非连续
  虚拟地址空间使用非连续
• 大用户空间：
  提供给用户的虚拟内存可大于实际的物理内存
• 部分交换
  虚拟存储只对部分虚拟地址空间进行调入和调出

支持技术：

硬件： 页式或短时存储中的地址转换机制

操作系统： 管理内存和外存间页面或段的换入和换出

内存局部性原理

程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，具体来说，局部性通常有两种形式：时间局部性和空间局部性。

• 时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
• 空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

缺页异常

linux内存管理–缺页异常处理

Linux Page Fault(缺页异常)

Linux的内存管理采用分页管理，使用多级页表，动态地址转换机构与主存、辅存共同实现虚拟内存。即使每个进程有相同的逻辑地址空间，通过分页机制，相应的物理地址也是不同的，因此他们在物理上不会彼此重叠。

从内核角度来看，逻辑地址和物理地址都被划分成为固定大小的页面。每个合法的逻辑页面敲好处于一个物理页面中，方便MMU的地址转换。当地址转换无法完成时(例如由于给定的逻辑地址不合法或由于逻辑页面没有对应的物理页面)，MMU将产生中断，向核心发出信号。Linux核心可以处理这种页面错误(Page Fault)问题。

MMU也负责增强内存保护，当一个应用程序试图在它的内存中队一个已标明是只读的页面进行写操作时，MMU也会产生中断错误，通知内核。在没有MMU的情况下，内核不能防止一个进程非法存取其他进程的内存空间。

每个进程都有一套自己的页目录与页表，其中页目录的基地址是关键，通过它才能查到逻辑所对应的物理地址。页目录的基地址是每个进程的私有资源，保存在该进程的task_struct对象的mm_struct结构变量mm中。

在进程切换时，CPU会把新进程的页目录基地址填入CPU的页目录寄存器，供MMU使用。当新进程有地址访问时，MMU会根据被访问地址的最高10位从页目录中找到对应的页表基地址，然后根据次高10位再从页表中找到对应的物理地址的页首，最后根据剩下的12位偏移量与页首地址找到逻辑地址对应的真正物理地址。

与直接访问物理内存不同，Page Fault过程大部分是由软件完成的，消耗时间比较久，所以是影响性能的一个关键指标。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

1. 保护CPU现场
2. 分析中断原因
3. 转入缺页中断处理程序进行处理
4. 恢复CPU现场，继续执行

但是缺页中断时由于所要访问的页面不存在与内存时，有硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

1. 在指令执行期间产生和处理缺页中断信号
2. 一条指令在执行期间，可能产生多次缺页中断
3. 缺页中断返回时，执行产生中断的那一条指令，而一般的中断返回时，执行下一条指令

分类

• 软性
  软性页缺失指页缺失发生时，相关的页已经被加载进内存，但是没有向MMU注册的情况。操作系统只需要在MMU中注册相关页对应的物理地址即可。
  发生这种情况的可能性之一，是一块物理内存被两个或多个程序共享，操作系统已经为其中的一个装载并注册了相应的页，但是没有为另一个程序注册。
  可能性之二，是该页已被从CPU的工作集中移除，但是尚未被交换到磁盘上。比如OpenVMS这样的使用次级页缓存的系统，就有可能会在工作集过大的情况下，将某页从工作集中去除，但是不写入硬盘也不擦除（比如说这一页被读出硬盘后没被修改过），只是放入空闲页表。除非有其他程序需要，导致这一页被分配出去了，不然这一页的内容不会被修改。当原程序再次需要该页内的数据时，如果这一页确实没有被分配出去，那么系统只需要重新为该页在MMU内注册映射即可。
• 硬性
  与软性页缺失相反，硬性页缺失是指相关的页在页缺失发生时未被加载进内存的情况。
  硬性页缺失导致的性能损失是很大的。以一块7200rpm的主流机械硬盘为例，其平均寻道时间为8.5毫秒，读入内存需要0.05毫秒。相对的，DDR3内存的访问延迟通常在数十到100纳秒之间，性能差距可能会达到8万到22万倍。
  另外，有些操作系统会将程序的一部分延迟到需要使用的时候再加载入内存执行，以此来提升性能。这一特性也是通过捕获硬性页缺失达到的。
  当硬性页缺失过于频繁的发生时，称发生系统颠簸。
  这时操作系统需要：
  1. 寻找到一个空闲的页。或者把另外一个使用中的页写到磁盘上（如果其在最后一次写入后发生了变化的话），并注销在MMU内的记录
  2. 将数据读入被选定的页
  3. 向MMU注册该页
• 无效
  当程序访问的虚拟地址是不存在于虚拟地址空间内的时候，则发生无效页缺失。一般来说这是个软件问题，但是也不排除硬件可能，比如因为内存故障而损坏了一个正确的指针。
  具体动作与所使用的操作系统有关，比如Windows会使用异常机制向程序报告，而类Unix系统则会使用信号机制。如果程序未处理相关问题，那么操作系统会执行默认处理方式，通常是转储内存、终止相关的程序，然后向用户报告。

触发时间

在linux中，用户空间的内存由VMA(virtual memory areas)结构管理：

当用户进程进程在一下情形时，会由MMU触发Page Fault中断：

1. 新申请的堆内存（malloc等），由于lazy机制，只建立页表而没有真实物理内存的映射，因此页表里的权限是R，发生Page Fault，在Page Fault回调中，linux会去申请一页内存，此时把页表权限设置为R+W。
2. 用户访问了非法的内存（例如引用野指针等），MMU就会触发Page Fault中断，回调中检查进程并没有对应这段内存的VMA，给用户进程发送SIGSEGV信号报段错误并终止。
3. 代码段在VMA中权限为R+X，如果程序中有野指针飞到此区域去写，则也会由MMU触发Page Fault中断，导致用户进程收到SIGSEGV信号。（另，malloc堆区在VMA中权限为R+W，如果程序的PC指针飞到此区域去执行，同样发生段错误。）
4. 在代码段区域运行执行操作时发生缺页，说明该段代码数据未从磁盘加载，则Linux申请一页内存，并从硬盘读取出代码段，此时产生了IO操作，为major主缺页。

如果按场景划分：

1. 请求调页: 当进程调用malloc（）之类的函数调用时，并未实际上分配物理内存，而是仅仅分配了一段线性地址空间，在实际访问该页框时才实际去分配物理页帧，这样可以节省物理内存的开销，还有一种情况是在内存回收时，该物理页面的内容被写到了磁盘上，被系统回收了，这时候需要再分配页帧，并且读取其保存的内容。
2. 写时复制:当fork()一个进程时，子进程并未完整的复制父进程的地址空间，而是共享相关的资源，父进程的页表被设为只读的，当子进程进行写操作时，会触发缺页异常，从而为子进程分配页帧。
3. 地址范围外的错误:内核访问无效地址，用户态进程访问无效地址等。
4. 内核访问非连续性地址：用于内核的高端内存映射，高端内存映射仅仅修改了主内核页表的内容，当进程访问内核态时需要将该部分的页表内容复制到自己的进程页表里面。

触发流程

从上面的讲解很容易看出，Page Fault是一个由硬件中断触发的可以由软件逻辑纠正的错误。根据《linux下的中断机制》中的叙述，一个Page Fault的触发流程为：

缺页中断发生时的事件顺序如下：

1. 硬件陷入内核，在内核堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
2. 启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
3. 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
4. 一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
5. 如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
6. 一旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
7. 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
8. 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
9. 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
10. 该例程恢复寄存器和其他状态信息

页面置换算法

最佳置换算法（OPT）（理想置换算法）

这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。

先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。

这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

最近最久未使用（LRU）算法

FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。

LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。

LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：

1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。

2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。

因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。

一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。

Clock置换算法（LRU算法的近似实现）

思路：仅对页面的访问情况进行大致统计

实现：在页表项中增加访问位，描述页面在过去一段时间的内访问情况，将各页面组织成环形链表，指针指向最先调入的页面，访问页面时，在页表项记录页面访问情况，缺页时，从指针处开始顺序查找未被访问的页面进行置换

特点：时钟算法是LRU和FIFO的折中

最少使用（LFU）置换算法

在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。

LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。

思路：缺页时，置换访问次数最少的页面

实现：每个页面设置一个访问计数，访问页面时，访问计数加1，缺页时，置换计数最小的页面

特点：算法开销大，开始时频繁使用，但以后不使用的页面很难置换

详细的置换过程见下图：执行在4个页帧中，假定最初的访问次数a-＞8 b-＞5 c-＞6 d-＞2

工作集算法

工作集时钟算法

缺页率置换算法

老化算法（非常类似LRU的有效算法）

NRU(最近未使用）算法

第二次机会算法

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

GPM

goroutine调度器

并发包

unsafe.Pointer

unsafe.Pointer

golang作为强类型静态语言，不允许指针类型转换。所以有了unsafe.Pointer，相当C语言中的void *

四个规则：

1. 任何指针都可以转换为unsafe.Pointer
2. unsafe.Pointer可以转换为任何指针
3. uintptr可以转换为unsafe.Pointer
4. unsafe.Pointer可以转换为uintptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

func main() {
	u:=new(user)
	fmt.Println(*u)

	pName:=(*string)(unsafe.Pointer(u))
	*pName="张三"

	pAge:=(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(u))+unsafe.Offsetof(u.age)))
	*pAge = 20

	fmt.Println(*u)
}

type user struct {
	name string
	age int
}

要注意的是，uintptr不能作为临时变量，GC可能会产生潜在问题

atomic.Value

sync.Map

sync.Pool

sync.Pool

保存和复用临时对象，减少内存分配，降低GC压力。

设计模式

Reactor模式

Handles ：表示操作系统管理的资源，我们可以理解为fd。

Synchronous Event Demultiplexer ：同步事件分离器，阻塞等待Handles中的事件发生。

Initiation Dispatcher ：初始分派器，作用为添加Event handler（事件处理器）、删除Event handler以及分派事件给Event handler。也就是说，Synchronous Event Demultiplexer负责等待新事件发生，事件发生时通知Initiation Dispatcher，然后Initiation Dispatcher调用event handler处理事件。

Event Handler ：事件处理器的接口

Concrete Event Handler ：事件处理器的实际实现，而且绑定了一个Handle。因为在实际情况中，我们往往不止一种事件处理器，因此这里将事件处理器接口和实现分开，与C++、Java这些高级语言中的多态类似。

以上各子模块间协作的步骤描述如下：

我们注册Concrete Event Handler到Initiation Dispatcher中。

Initiation Dispatcher调用每个Event Handler的get_handle接口获取其绑定的Handle。

Initiation Dispatcher调用handle_events开始事件处理循环。在这里，Initiation Dispatcher会将步骤2获取的所有Handle都收集起来，使用Synchronous Event Demultiplexer来等待这些Handle的事件发生。

当某个（或某几个）Handle的事件发生时，Synchronous Event Demultiplexer通知Initiation Dispatcher。

Initiation Dispatcher根据发生事件的Handle找出所对应的Handler。

Initiation Dispatcher调用Handler的handle_event方法处理事件。

类

访问修饰符

访问修饰符

构造&析构&拷贝构造

构造函数

构造函数的名称与类的名称是完全相同的，并且不会返回任何类型，也不会返回 void。默认的构造函数没有任何参数，但如果需要，构造函数也可以带有参数。

1
2
3

C::C( double a, double b, double c): X(a), Y(b), Z(c){
  ....
}

X(a)等同于C.X=a;

析构函数

析构函数的名称与类的名称是完全相同的，只是在前面加了个波浪号（~）作为前缀，它不会返回任何值，也不能带有任何参数。析构函数有助于在跳出程序（比如关闭文件、释放内存等）前释放资源。

1
2
3

C::~C(void){
  ....
}

拷贝构造函数

拷贝构造函数是一种特殊的构造函数，它在创建对象时，是使用同一类中之前创建的对象来初始化新创建的对象。拷贝构造函数通常用于：

• 通过使用另一个同类型的对象来初始化新创建的对象。
• 复制对象把它作为参数传递给函数。
• 复制对象，并从函数返回这个对象。
  如果在类中没有定义拷贝构造函数，编译器会自行定义一个。如果类带有指针变量，并有动态内存分配，则它必须有一个拷贝构造函数。拷贝构造函数的最常见形式：

1
2
3

classname (const classname &obj) {
   // 构造函数的主体
}

友元函数

类的友元函数是定义在类外部，但有权访问类的所有私有（private）成员和保护（protected）成员。尽管友元函数的原型有在类的定义中出现过，但是友元函数并不是成员函数。

1
2
3
4
5

class Box
{
public:
   friend void printWidth( Box box );
};

声明类 ClassTwo 的所有成员函数作为类 ClassOne 的友元，需要在类 ClassOne 的定义中放置如下声明：

1

friend class ClassTwo;

内联函数

引入内联函数的目的是为了解决程序中函数调用的效率问题，程序在编译器编译的时候，编译器将程序中出现的内联函数的调用表达式用内联函数的函数体进行替换，而对于其他的函数，都是在运行时候才被替代。这其实就是个空间代价换时间的i节省。所以内联函数一般都是1-5行的小函数。在使用内联函数时要留神：

1. 在内联函数内不允许使用循环语句和开关语句；
2. 内联函数的定义必须出现在内联函数第一次调用之前；
3. 类结构中所在的类说明内部定义的函数是内联函数。

this指针&指向类的指针

在 C++ 中，每一个对象都能通过 this 指针来访问自己的地址。this 指针是所有成员函数的隐含参数。因此，在成员函数内部，它可以用来指向调用对象。

友元函数没有 this 指针，因为友元不是类的成员。只有成员函数才有 this 指针。

1
2
3
4
5
6
7

class Box
{
   public:
      int compare(Box box){
         return this->Volume() > box.Volume();
      }
};

一个指向 C++ 类的指针与指向结构的指针类似，访问指向类的指针的成员，需要使用成员访问运算符 ->，就像访问指向结构的指针一样。与所有的指针一样，您必须在使用指针之前，对指针进行初始化。

1
2

ptrBox = &Box1;
cout << "Volume of Box1: " << ptrBox->Volume() << endl;

静态成员

static 关键字把类成员定义为静态的。无论创建多少个类的对象，静态成员都只有一个副本。

静态成员属性

静态成员在类的所有对象中是共享的。如果不存在其他的初始化语句，在创建第一个对象时，所有的静态数据都会被初始化为零。不能把静态成员的初始化放置在类的定义中，但是可以在类的外部通过使用范围解析运算符 :: 来重新声明静态变量从而对它进行初始化。

1
2
3
4
5
6
7

class Box
{
   public:
      static int objectCount;
};
// 初始化类 Box 的静态成员
int Box::objectCount = 0;

静态成员函数

如果把函数成员声明为静态的，就可以把函数与类的任何特定对象独立开来。静态成员函数即使在类对象不存在的情况下也能被调用，静态函数只要使用类名加范围解析运算符 :: 就可以访问。

静态成员函数只能访问静态成员数据、其他静态成员函数和类外部的其他函数。

静态成员函数有一个类范围，他们不能访问类的 this 指针。您可以使用静态成员函数来判断类的某些对象是否已被创建。

继承

1

class derived-class: access-specifier base-class

继承类型

一个派生类继承了所有的基类方法，但下列情况除外：

• 基类的构造函数、析构函数和拷贝构造函数。
• 基类的重载运算符。
• 基类的友元函数。

多继承

多继承即一个子类可以有多个父类，它继承了多个父类的特性。

C++ 类可以从多个类继承成员，语法如下：

class <派生类名>:<继承方式1><基类名1>,<继承方式2><基类名2>,…

{

<派生类类体>

};