每个进程特点
- 逻辑地址空间是一个抽象模型。
- 保护独立地址空间。P1进程只能访问自己的地址空间，不能意外跨越去访问P2的地址空间；
- 共享。进程P1, P2, … , 又是共享操作系统内核的
- 虚拟化。每个进程的逻辑地址空间都是一致的，都是从地址0X0000开始。
内存管理方式
- 重定位 relocation
- 分段 segmentation
- 分页 paging
- 虚拟存储 virtual memory
目前大多数系统，如 Linux 采用按页式虚拟存储。
地址空间
物理地址空间—-硬件支持的地址空间
逻辑地址空间—– 一个运行的程序所拥有的内存范围
逻辑地址生成：编译，汇编，链接，载入（程序重定位）
操作系统 建立逻辑地址和地址之间的映射
地址生成及处理过程：
ALU需要逻辑地址中的内容（读或写）， MMU对逻辑地址进行转换，转换为物理地址， CPU控制逻辑给总线发送物理地址请求。 内存发送物理地址的内容给CPU或者将CPU给的数据存储到物理地址。操作系统做的是简历逻辑地址LA和物理地址PA之间的映射。
地址检查：
CPU执行到某条指令，得到它的逻辑地址，首先根据逻辑地址判断所在它的偏移量是否在所在段（比如数据段）的长度之内，如果超出了段长度，认为是非法请求，否则认为是合法的。此时加上段基址得到物理地址，进行访问。在这个过程中操作系统要做的就是设置段起始地址和最大逻辑地址空间（段长度）。
连续地址分配
内存碎片
内存碎片：有的还可以用，有的无论如何都用不起来了。
外部碎片：分配单元之间的未被使用内存
内部碎片：分配单元内部的未被使用内存（你只占500字节，但是不得不分配512字节）
分配策略
- 最先匹配(First Fit Allocation)策略。
空闲分区列表按地址顺序排序 分配过程时，搜索一个合适的分区 释放分区时，检查是否可与临近的空闲分区合并
- 最佳匹配(Best Fit Allocation)策略
空闲分区列表按照大小排序 分配时，查找一个合适的分区 释放时，查找并且合并临近的空闲分区（如果找到）
- 最差匹配(Worst Fit Allocation)策略
空闲分区列表按由大到小排序 分配时，选最大的分区 释放时，检查是否可与临近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序
碎片整理
碎片紧凑
实现方式：通过移动分配给进程的内存分区，以合并外部碎片。
条件：所有的应用程序可以动态重定位。这是因为程序中可能有很多地址引用，如果引用了绝对地址，移动分配的内存位置可能就会出错。因此需要动态重定位，执行到命令的时候才生成内存地址。
时机：进程处于等待状态时搬动。
开销：移动已分配的内存分区是有开销的，因此不会为了一小块碎片就进行紧凑。具体开销暂且按下不讲。
分区对换
分区对换是通过抢占并回收处于等待状态进程的分区，以增大可用内存空间。即将等待状态进程的数据存储到外存中，也就是对换到对换区
伙伴系统
伙伴系统是一个结合了2的方幂个分配器和空闲缓冲区合并计技术的内存分配方案, 其基本思想很简单. 内存被分成含有很多页面的大块, 每一块都是2个页面大小的方幂. 如果找不到想要的块, 一个大块会被分成两部分, 这两部分彼此就成为伙伴. 其中一半被用来分配, 而另一半则空闲. 这些块在以后分配的过程中会继续被二分直至产生一个所需大小的块. 当一个块被最终释放时, 其伙伴将被检测出来, 如果伙伴也空闲则合并两者
非连续内存分配
连续内存分配缺点
-
分配给程序的物理内存必须连续
-
存在外碎片和内碎片
-
内存分配的动态修改困难
-
内存利用效率低
非连续分配设计目标
提高内存利用效率和管理灵活性
允许一个程序的使用非连续的物理地址空间
允许共享代码与数据
支持动态加载和动态链接
如何实现虚拟地址和物理地址的转换
软件实现(灵活,开销大)
硬件实现(够用，开销小)
段式存储管理
页式存储方式，是以计算机的角度设计的，以便提高内存的利用率和计算机的性能，且分页机制是通过硬件实现的。对用户而言是完全透明的段式存储器的引入，主要是为了满足用户在编程和使用上的要求。具体来说：
-
方便编程。因为人们写的程序是分成了许多个段的，比如一个程序里面有很多和函数等等
-
段的共享。实现程序和数据的共享，都是以信息的逻辑单位为基础的。比如一些公共函数，一些全局变量等等。
-
动态链接。动态链接是程序在运行的过程中实现目标模块的链接，动态链接同样要求以段为存储管理的单位。（写过dll的同学应该深有体会，里面就是一些类库）
-
动态增长。程序运行过程中，往往有些段，特别是数据段，会不断的往上增长。而分页确实固定的。
-
段的保护
页式存储管理
将内存空间分成大小相同的存储块，并按顺序编号（一般从0开始）。相应的将进程的逻辑地址空间分成若干个与内存块大小相等的块，但是为了方便区分，我们称为页。（也就是说，在实际的内存中我们称为块，在逻辑地址中我们称为页）。在为进程分配内存空间的时候，以页为单位进行。进程中若干个页分别装入多个不相邻的存储块中，通常，进程的最后一页通常装不满一个存储块，形成不可利用的碎片，称为页内碎片。
页式存储的地址变换
-
首先，页号与页表寄存器中的页表长度进行比较，若页号大于页表长度，则产生越界中断。（判越界）
-
否则，通过页表起始地址，找出页表。
-
根据页号，找出相应的页表项，得到该页的存储块号
-
根据块号与页内偏移，算出实际的物理地址
页式存储管理的性能问题
- 内存访问性能问题：访问一个内存单元需要两次内存访问，第一次访问获取页表项，第二次访问获取数据，这样与连续内存分配相比，读写的性能大幅下降
- 页表大小问题：当内存空间很大时，页表可能会非常大，页表的容量是不可忽视的，比如32位的机器，内存大小为4G，假设页面的大小是1K，则一共有222个页面，每个页表项的地址为4个字节，整个页表的大小为224个字节，也就是16M。而且每个进程都有一个页表，100个进程仅页面大小就有1600M，这是无法忽视的
解决：
- 采用Cache：利用局部性原理，减少缓存次数，TLB（快表）
- 间接访问：多级页表，将一个长的页表切分成多个字表，先确定在哪个字表中，再去子表中寻找。（多级页表）
快表和多级页表
快表 ：快表中缓存近期访问的页表项。TLB条目由两部分组成：键（标签）和值。当关联内存通过给定值查找时，它会同时与所有的键进行比较。
多级页表： 多级页表是通过间接引用，将页号分成多级
反置页表
反置页表与物理地址挂钩，对于每个真正的内存页或者帧才有一个条目。每个条目包含保存在真正内存位置的页的虚拟地址以及拥有该页的进程信息。因此，整个系统只有一个页表，对每个物理内存的页只有一条相应的条目。此时进程的增加和逻辑地址空间的增大都对页表占用的空间没有影响。
段页式存储
在段式存储管理的基础上，给每个段增加一个一级页表（多级也可以），从而将逻辑地址变为段号+页号+页内偏移，由逻辑地址转化为物理地址时，先根据段号找到相应的段表项，得到段的页表的起始位置，在根据页号在页表中找到帧号，帧号与页内偏移加起来就找到了响应的物理地址。
虚拟存储
虚拟存储是想把一部分内存中的内容暂时存放到外存中，以提供更大的内存空间。
覆盖和交换
覆盖：由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区。其余部分按调用关系 分段。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调入覆盖区，替换覆盖区中原有的段。
交换：把处于等待状态（或在CPU调度原则下被剥夺运行权利）的程序从内存移到辅存，把内存空间腾出来，这个过程叫做换出。把准备好竞争CPU运行的程序从辅存移到内存，这个过程又称为换入
局部性
在一较短的时间内，程序的执行仅局限于某个部分；相应地，所访问的存储空间也局限于某个区域。
虚拟存储
所谓“虚拟存储器”，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。 虚拟存储管理下 内存逻辑容量由内存容量和外存容量之和所决定 运行速度接近于内存速度 每位的成本却接近于外存。
虚拟页式存储
以页为单位的虚拟存储器，称为页式虚拟存储器。它的虚拟空间跟主存空间都将被划分为相同大小的页。主存中的页，称为实页，虚存中的页，称为虚页。虚拟地址被分为两个字段，虚页号和页内偏移。为了对每个虚拟页的存放位置，存取位置，使用情况，修改情况等等进行等进行说明，操作系统在主存中给每个进程都生成一个页表。因此，每个虚拟页表都对应有一个页表项。页表是一张存放在主存中的，虚拟页与实页对照的映射表。其中存放位置字段用来建立虚拟页与实页之间的映射，进而进行地址转换。有效位用来表示对应页面是否存在。
状态位P：用于记录该页是否已经调入内存
访问字段：记录该页多久没有被访问了
修改位：标识该页调入内存后是否被修改过
外存地址：指出该页在内存外的地址，供调入该页的时候使用。
缺页异常
当地址转换无法完成时(例如由于给定的逻辑地址不合法或由于逻辑页面没有对应的物理页面)，MMU将产生中断，向核心发出信号。Linux核心可以处理这种页面错误(Page Fault)问题。
页面置换算法
局部页面置换算法
### 最优页面置换算法（OPT，optimal） 当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之间，还需等待多长的时间，从中选择等待时间最长的那个，作为被置换的页面。
无法实现，可用作其他算法的评价的依据 ### 先进先出算法（FIFO） 选择在内存中驻留时间最长的页面置换
性能较差，调出的页面可能是经常要访问的页面（驻留时间长，本身就说明可能常用
### 最近最久未使用算法（LRU，Least Recently Used） 选择最长时间未被使用的页面置换
LRU算法需要记录各个页面使用时间的先后顺序，开销比较大，两种可能的实现方法。
系统维护一个页面链表，最近刚使用的页面作为首结点，最久未使用的页面作为尾结点，每次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首，每次缺页中断发生时，淘汰链表末尾的页面。
设置一个活动页面堆栈：当访问某页时，将此页号入栈顶，并去除栈内的重复页。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。
### 时钟页面置换算法（Clock） Clock 页面置换算法——LRU的近似，对FIFO的改进 基本思路：需要用到页表项的访问位（access bit），当一个页面被装入内存时，把该位初始化为0，然后如果这个页被访问（读/写）时，硬件把它置为1. 把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）；当发生一个缺页中断，考察指针所指向的最老的页面，若它的访问为为0，则立即淘汰。若访问为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。
#### 增强时钟页面置换算法 修改Clock算法，使它允许脏页总是在一次时钟头扫描中保留下来，同时使用脏位（dity bit,也叫写位）和使用位来指导置换
### 最不常用算法（LFU，Least Frequently Used） 基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之
对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1，淘汰计数值最小的那个页面
LRU/LFU区别：LRU考察的是多久未访问，时间越短越值得留在内存，LFU是访问次数/频度，次数越多越好。
### Belady现象 Belady现象：在采用FIFO,Clock算法时，有时会出现的物理页面数增加，缺页率反而提高的异常现象。
### LRU、FIFO和Clock的比较 LRU和FIFO本质都是先进先出的思路，但LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态的调整各个页面之间的先后顺序（每一个页面的最近访问时间变了）；而FIFO针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以页面之间的先后顺序是固定不变的。如果程序局部性，则LRU会很好。如果内存中所有页面都没有被访问过会退化为FIFO（如页面进入内存后没有被访问，最近访问时间与进入内存的时间相同）。
LRU算法性能较好，但系统开销较大；FIFO算法的系统的开销较小，但可能发生Belady现象。因此，择衷的办法就是Clock算法，在每一次页面访问时，它不必去动态调整页面在链表中的顺序，而仅仅是做一个标记，等待发生缺页中断的时候，再把它移动到链表的末尾。对于内存当中未被访问的页面，Clock算法的表现与LRU一样好，而对于那些曾经访问过的页面，它不能像LRU那样记住它们的准确访问顺序。
全局页面置换算法
### 工作集页置换算法 常驻集大小可变。例如每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态的调整常驻集的大小
工作集窗口里的页代表当前这段时间内被访问的页，如果其中的页需要替换时，需要替换不在工作集中的页；随着程序执行，窗口在挪动，评议过程中某个页不再在国工作集窗口内，则这个页也需要丢掉，并不是一定要等到缺页时再置换出去。
### 缺页率置换算法 若运行程序缺页率高我们会增加工作集，希望他访问的页尽量在内存中，可以降低缺页率。如果缺页率过低，意味着可能分配的内存比较多，则可以减少工作集来减少程序需要的物理页面（意味着常驻集也被减少），使得每个程序的缺页率保持在一个合理的范围内。整体系统的性能从而平衡地提高。
-
访存时，设置引用位标志
-
缺页时，计算从上次缺页时间tlast到现在tcurrent的时间间隔
-
如果t_current–t_last>T,则置换所有在[tlast , tcurrent ]时间内没有被引用的页(缺页率比较低，把不用的置换出去)
-
如果t_current–t_last≤T,则增加缺失页到工作集中
### 抖动和负载控制 进程物理页面太少，不能包含工作集
造成大量缺页，频繁置换
进程运行速度变慢
随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升
选择一个适当的进程数目和进程需要的物理页面数
通过调节并发进程数（MPL）来进行系统负载控制
平均缺页间隔时间(MTBF) =缺页异常处理时间(PFST)：
