满嘴都是糖果

操作系统内存管理：总的来说，操作系统内存管理包括物理内存管理和虚拟内存管理。

物理内存管理：包括程序装入等概念、交换技术、连续分配管理方式和非连续分配管理方式（分页、分段、段页式）。
虚拟内存管理：虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。

物理内存：连续分配存储管理方式

单一连续存储管理

在这种管理方式中，内存分为系统区和用户区，应用程序装入到用户区，并且可使用用户区全部空间。虽然易于管理，但是十分浪费内存，例如对内存要求很少的程序也占有很多内存空间。

分区式存储管理

为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。

分区式管理有两个问题：内碎片和外碎片

内碎片：占用的分区未被利用的空间
外碎片：占用分区之间难以利用的小空闲分区。

固定分区

固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等，也可以不等，例如有多个小分区、适量的中等分区以及少量的大分区。

固定分区的优点是：易于实现；缺点是：内碎片浪费；分区总数是固定的，程序并发执行数目有限。

动态分区

动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。没有内碎片。但它却引入了另一种碎片——外碎片。如果分区大于程序所需，就会对分区进行分割，如果分割之后的空闲分区较小，就容易成为外碎片。

分区适配算法：

最先适配法(nrst-fit)：按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。
下次适配法(循环首次适应算法 next fit)：按分区在内存的先后次序，从上次分配的分区起查找(到最后{区时再从头开始}，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大空闲分区不易保留。
最佳适配法(best-fit)：按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保留。
最坏适配法(worst- fit)：按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，当对内存需求较大的进程需要运行时，其要求不易被满足。

内存紧缩（内存碎片化处理）

内存紧缩：将各个占用分区向内存一端移动，然后将各个空闲分区合并成为一个空闲分区。

在动态存储过程中，不管哪个时刻，可利用空间都是-一个地址连续的存储区，在编译程序中称之为”堆”，每次分配都是从这个可利用空间中划出一块。由于系统的可利用空间始终是一个地址连续的存储块，因此回收时必须将所释放的空间块合并到整个堆上去才能重新使用。

进行内存紧缩需要执行以下四个步骤：

计算占用块新地址，从最低地址开始巡査整个存储空间，对每一个占用块找到它在紧缩后的新地址。
修改用户初始变量表，以便在存储紧缩后用户程序能继续正常运行
检查每个占用块中存储的数据，若有指向其他存储换的指针，则需作相应修改.
将所有占用块迁移到新地址走，这实质上是作传送数据的工作。

因此，存储紧缩也是个系统操作，且非不得已就不用。

覆盖技术

将程序必要部分(常用功能)的代码和数据常驻内存；可选部分(不常用功能)平时存放在外存(覆盖文件)中，在需要时才装入内存。不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。在任何时候只在内存中保留所需的指令和数据；当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的内存空间；

覆盖技术的缺点是编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度

交换技术

交换 (swapping)技术在多个程序并发执行时，可以将暂时不能执行的程序（进程）送到外存中，从而获得空闲内存空间来装入新程序（进程），或读入保存在外存中而处于就绪状态的程序。交换单位为整个进程的地址空间。

原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。

优点：增加并发运行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比不影响程序结构。

覆盖与交换比较

1）与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。

2）交换主要是在进程与作业之间进行，而覆盖则主要在同一作业或进程内进行。另外覆盖只能覆盖那些与覆盖程序段无关的程序段。

物理内存非连续：页式和段式存储管理

在前面的几种存储管理方法中，为进程分配的空间是连续的，使用的地址都是物理地址。如果允许将一个进程分散到许多不连续的空间，就可以避免内存紧缩，减少碎片。基于这一思想，通过引入进程的逻辑地址，把进程地址空间与实际存储空间分离，增加存储管理的灵活性。

地址空间：将源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。地址空间是逻辑地址的集合。

存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址存储空间是物理地址的集合。

根据分配时所采用的基本单位不同，可将离散分配的管理方式分为以下三种： 页式存储管理、段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。

页式和段式管理的区别

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

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

页式存储管理

基本原理：将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame)。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成，前一部分是页号p，后一部分为页内地址w（位移量）

页式管理方式的优点是：

没有外碎片，每个内碎片不超过页大比前面所讨论的几种管理方式的最大进步是，一个程序不必连续存放。
便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。

缺点是：要求程序全部装入内存，没有足够的内存，程序就不能执行。

页式管理的数据结构

进程页表：完成逻辑页号(本进程的地址空间)到物理页面号(实际内存空间，也叫块号)的映射。每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序。

物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况，其数据结构可采用位示图和空闲页链表。

请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换也可以结合到各进程的PCB(进程控制块)里。

页式管理地址变换

在页式系统中，指令所给出的地址分为两部分：逻辑页号和页内地址。

原理：CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内地址相加形成物理地址

逻辑页号，页内偏移地址－>查进程页表，得物理页号－>物理地址

一般来说，页表存储在主存之中。这样处理器每访问一个在内存中的操作数，就要访问两次内存：

第一次用来查找页表将操作数的逻辑地址变换为物理地址；
第二次完成真正的读写操作。

这样做时间上耗费严重。为缩短查找时间，可以将页表从内存装入快表（TLB， translation lookaside buffer）

1、CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将次页号与快表中的页号做比较
2、如果找到，直接从快表去除该页对应的页框号，与地址结构的地址偏移量计算出物理地址访存
3、如果没有找到，再去慢表中找，然后如上访存，之后将这个页表项加入到快表中。注意有的系统为了节省时间，会在快表中找与在慢表中找同时进行，这样可以节约系统时间。

多级页表

进程在一段时间内可能只需要访问某几个特定的页面，没有必要让整个页表常驻内存。避免把全部页表一直保存在内存中是多级页表的关键所在。特别是那些不需要的页表就不应该保留。

使用简单的一级页表，如果进程使用全部4G线性地址空间，那么将需要高达2^20表项（总共地址线是32位，每页大小为4kb，则页偏移量需要低12位，高20位当作页表地址）来保存表示每个进程的页表，若每项4B，则需要4MB的ram来存储页表。尽管一个进程并不使用内的所有地址。而使用二级页表时，还需要为一级页表建立索引，4MB/4KB4B=1KB个存储空间，那么加起来就是4.004MB，比一级页表还多了，那为什么说多级页表省内存呢？因为程序通常并不需要整个内存空间，因此在二级页表中，我们只需要一个页目录就可以映射到程序所需要的页表了，那么内存中只需要存放一个一级页目录和几个需要的二级页表。举个极端的例子，假如第一级页表只有前两个页表项（PTE0和PTE1）不为空，那么操作系统将只会存储两个二级页表项，此时的内存占用便只有 4KB*2（页表） + 4KB（页目录） =12KB. 是不是极大的节省了内存空间。

通过一个顶级页表为真正有用的页表提供索引，这是多级页表的本质。

段式存储管理

在段式存储管理中，将程序的地址空间划分为若干个段(segment)，这样每个进程有一个二维的地址空间。段式存储管理系统为每个段分配一个连续的分区，而进程中的各个段可以不连续地存放在内存的不同分区中。

优点：没有内碎片，外碎片可以通过内存紧缩来消除；每个进程具有独立的进程地址空间，保证了地址空间的隔离性。同时它也解决了程序重定位的问题，因为程序始终是在逻辑地址空间下运行的

缺点：进程必须全部装入内存，映射的粒度太大，是以程序为单位的，如果内存不足，那么只能换出整个程序。

段式管理的数据结构

进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段内地址。

系统段表：系统所有占用段（已经分配的段）

空闲段表：内存中所有空闲段，可以结合到系统段表中

段式管理地址变换

在段式管理系统中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。

进程逻辑地址到物理地址的映射过程：处理器会查找内存中的段表，由段号得到段的首地址，加上段内地址，得到实际的物理地址

段页式存储管理

段页式管理就是将程序分为多个逻辑段，在每个段里面又进行分页，即将分段和分页组合起来使用。

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

为了实现地址变化，系统为每个进程维护了一个段表，每个分段又有一个页表。段表中包含段号、页表长度和页表的起始地址。页表中包含页号和块号。系统还有一个段表寄存器，存储段表的起始地址和段表长度

虚拟内存

虚拟内存由主内存+I/O设备组成，或者简单点说，虚拟内存包内存和磁盘。虚拟内存是一种存储模式，通过这种模式能让我们有种感觉，即：我们的内存本身能够处理远比内存大的多的数据或者文件。

虚拟内存能够处理比本身更大的数据的原理其实非常简单，简单理解为按需加载，内存都会按照固定大小的页进行划分，我们在使用cpu处理磁盘上的文件的时候，并不是一下会把整个文件都载入内存，而是当用到这部分数据的时候才会去加载，触发机制是：

这块数据需要被加载
当发生操作系统发起缺页信号时

如果在内存里面申请的固定空间满了，会淘汰一部分页然后替换为新的页，这就需要页面置换算法出场了。

虚拟内存的优缺点

优点：

（1）可以使用有限的内存资源，处理比实际内存更大的文件或者数据

（2）更加高效的内存利用

（3）在有限的内存资源内，让系统运行更多的程序实例，因为每个程序都是按需取。

缺点：

（1）如果内存严重不足，而处理超级大的文件时，会频繁引起内存和磁盘进行页面置换，从而降低系统性能。

（2）在多个应用程序之间切换会花费更多的时间

（3）虚拟内存本质上是利用磁盘空间，但同时变相的提供用户使用的实际磁盘空间也会变小。

页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。选择调出页面的算法就称为页面置换算法。

常见的置换算法有四种：最佳置换算法（OPT），先进先出（FIFO）置换算法，最近最久未使用（LRU）置换算法，时钟（CLOCK）置换算法

最佳置换算法（OPT）：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，但是最佳置换算法可以用来评价其他算法。

先进先出（FIFO）置换算法：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

最近最久未使用（LRU）置换算法：选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。LRU算法是一种经典的淘汰算法，在Redis中也有应用，不过Redis在实现的时候采用的是近似值。

时钟（CLOCK）置换算法：时钟置换算法可以认为是一种最近未使用算法，即逐出缓冲池中最近没有使用的那个页面。我们给每一个页面设置一个标记位u，u=1表示最近有使用u=0则表示该页面最近没有被使用，应该被逐出。每一次进行替换指针的位置就从替换数移到下一个位置,每一次进行访问时，则指针保持不动。

访问5的时候，因为缓冲池已经满了，所以要进行一次逐出操作

页面分配策略

驻留集

工作集（或驻留集）是指在某段时间间隔内，进程要访问的页面集合。对于分页式的虚拟内存，在准备执行时，不需要也不可能把一个进程的所有页都读取到主存，因此，操作系统必须决定读取多少页。也就是说，给特定的进程分配多大的主存空间，这需要考虑以下几点：

分配给一个进程的存储量越小，在任何时候驻留在主存中的进程数就越多，从而可以提高处理机的时间利用效率。
如果一个进程在主存中的页数过少，尽管有局部性原理，页错误率仍然会相对较高。
如桌页数过多，由于局部性原理，给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响。

考虑到这些，有三种常用策略

固定分配局部策略：给每个进程分配一定数目的物理页，在整个运行期间不改变。若发生缺页中断，只能从该进行的内存中的选出一页进行置换。
可变分配全局置换：为每个进行分配一定数据的物理块，操作系统自身也保持一个空闲物理块队列。当某进程发生缺页时，系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中。
可变分配局部置换：为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页进行置换。如果进程在运行中频繁地缺页，系统再为该进程分配若干物理块，直至该进程缺页率趋于适当程度；反之，若进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

调入页面的时机

为确定系统将进程运行时所缺的页面调入内存的时机，可釆取以下两种调页策略：

1）预调页策略。

根据局部性原理，一次调入若干个相邻的页可能会比一次调入一页更高效。但如果调入的一批页面中大多数都未被访问，则又是低效的。所以就需要釆用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。但目前预调页的成功率仅约50%。故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

（2）请求调页策略。

进程在运行中需要访问的页面不在内存而提出请求，由系统将所需页面调入内存。由这种策略调入的页一定会被访问，且这种策略比较易于实现，故在目前的虚拟存储器中大多釆用此策略。它的缺点在于每次只调入一页，调入调出页面数多时会花费过多的I/O开销。

页面抖动

在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。

正确选择工作集的大小，对存储器的利用率和系统吞吐量的提嵩，都将产生重要影响。

This site is open source. Improve this page.