操作系统-------------------内存空间的分配方式(连续分配和非连续分配和虚拟存储技术)_计算机操作系统存储空间分配

 

目录

一、连续分配方式

1. 单一连续分配（过时）

2.固定分区分配

3.动态分区分配

3.1 动态分区分配算法

3.11 首次适应算法

3.12 最佳适应算法

3.13 最坏适应算法(又称最大适应算法)

3.14 邻近适应算法

连续分配方式的缺点：

二、非连续分配方式

2.1 基本分页存储管理

页表

快表与慢表：

两级页表：

2.2 基本分段存储管理

3. 段页式

三、虚拟内存技术

3.1 请求分页存储管理

3.1.1 请求分页的页表机制

3.1.2 页面置换算法

3.1.2.1 先进先出置换算法(FIFO)

3.1.2.2 最近最久未使用置换算法(LRU)

3.1.2.3 时钟置换算法（CLOCK）

3.1.2.4 改进型的时钟置换算法

3.1.3 页面分配算法

1.固定分配局部替换

2.可变分配局部替换：

3.可变分配全局替换：

内存抖动

---

一、连续分配方式

1. 单一连续分配（过时）

整个内存只能有一个程序。

内存被分为 系统区和用户区，系统区用于装操作系统的相关数据，用户区用于装程序。由于整个用户区只能有一个程序，因此内存利用率极差。

2.固定分区分配

固定分区能够支持多道程序。

原理是：把用户区进一步分成多个分区，每一个分区存放一个进程。固定分区分配又分成两种：一种是各个分区大小相同，另一种是各个分区大小不相等。

分区大小不等有利于存放大小不同的进程。

当操作系统用到分区技术时，都会维护一个数据结构----分区说明表，来实现各个分区的分配与回收，每个表项对应一个分区，通常按分区大小排列，用数组或链表都可以表示这张表，表具体如下：

优点：实现简单，无外部碎片。(外部碎片即用户区里有未被用到的地方，由于分区是刚好占满用户去的，故没有外部碎片)

缺点：存在内部碎片(即分区内因进程没占满分区而多出来未被使用的地方)；而且遇到一个大进程，以致所有分区都放不下，那就只能使用覆盖技术，覆盖技术由于会把进程的某些段从外存和内存之间调出调入，因此会增加I/O开销。

 

3.动态分区分配

亮点：这种分区方式不会预先划分内存分区，而是在进程装入内存时，再动态地根据进程的大小建立分区。使得分区的大小刚好适合进程使用。

存在的问题：（如下图）

由于进程在运行完后，会退出内存，留下空余的碎片，如下面的6MB和10MB和4MB。此时若 有一个 20MB的进程进来，则虽然空闲空间刚刚好有20MB，但依然是放不下的。这就是存在的问题，为了解决这个问题，只能引入拼凑技术。

拼凑技术：

拼接技术/紧凑技术：移动内存中所有已经分配区到内存的一端，将其余空闲分区合并为一个大的空闲分区

拼凑后就能放入20MB的进程了

优点：动态分区没有内部碎片

缺点：动态分区有外部碎片。必要时要引入拼凑技术解决存在的问题。但是紧凑技术的时间成本很大。

 

记录空闲分区的两种数据结构

空闲分区表 or 空闲分区链：

空闲分区表：

表中各个表项分别记录着分区号，分区大小，起始地址，状态。

空闲分区链：

每个分区的起始部分和末尾部分分别指向前一个分区和后一个分区。起始部分还记录着当前分区大小等信息。

3.1 动态分区分配算法

动态分区算法：在动态分区分配方式中，当很多个空闲分区都能满足要求时，应选择哪个分区进行分配？动态分区算法就是干这个的。

3.11 首次适应算法

思想：每次都从内存低地址开始遍历，寻找第一个满足要求的分区。

实现：让空闲分区表和空闲分区链按地址递增顺序存放，遍历空闲分区表或者空闲分区链就好了。

3.12 最佳适应算法

思想：优先选择小分区，尽量留下大分区，保证当大进程来的时候有分区存放。

实现：让空闲分区表和空闲分区链按容量递增顺序存放，遍历空闲分区表或者空闲分区链就好了。

缺点：每次都选择最小的分区进行分配，当小进程运行结束退出内存时，会留下越来越多的，很小的，难以利用的内存块(即产生很多外部碎片)。如下图的1MB：

3.13 最坏适应算法(又称最大适应算法)

思想：跟最佳适应算法相反，最坏适应算法优先适应空间大的分区。由于最佳适应算法能产生很多难以利用的外部碎片，所以最坏适应算法通过优先使用最大的分区，就可以使得剩下的分区不至于太小而难以利用。

实现：让空闲分区表和空闲分区链按容量递减顺序存放，遍历空闲分区表或者空闲分区链就好了。

缺点：每次都选最大的分区进行分配的话，那么很快就会造成没大分区，这时候如果有大进程进来，那么就会放不下。

 

3.14 邻近适应算法

思想：首次适应算法每次都从链头开始查找分区。经过一段时间后，起始位置附近的分区肯定被用得差不多了，而且也会出现很多太小难以利用的小分区，这样子的话，每次查找还是要从头开始，经过这些分区，会增加查找的开销，所以如果每次查找能从上次查找结束的地方开始，就会解决问题。

实现：形成一个循环链表。

缺点：这种算法会导致无论是低地址还是高地址的分区都会被相同概率地使用，那就会有可能造成所有大分区都会被弄成小分区，从而有大进程进来时，无法存放(最坏适应算法的缺点）。

综合来看：首次适应算法反而效果最好。

归纳：

连续分配方式的缺点：

1.固定分区分配：由于没有按照进程来考虑分区大小，所以会产生很多内部碎片。

2.动态分区分配：会产生很多外部碎片，虽说可以用紧凑技术处理，但是紧凑技术的时间成本太大。

 

二、非连续分配方式

连续分配方式：一个分区一个进程

非连续分配方式：把一个进程分解成几块，分别放入几个不同的分区。

什么是分页？

分页就是容量更小的分区。

 

2.1 基本分页存储管理

思想：

页框：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。这些小从部分就是所谓的“页框”或“页帧”或“内存块”。每个页框都有一个编号，叫页框号，编号从0开始。

页面：把进程分成多个部分，每个部分大小与页框相等，这些部分就叫页面。

具体如下：

可以看见，内存分成了n个页框，进程A也被分成4份，分别放在不同的页框中。

有人问，那么这种分页存储方式会不会产生碎片呢？

这种方式其实跟固定分区方法一样嘛，外部碎片是不会有的，但是会不会有内部碎片呢，会有一丢丢，为什么，因为有空能进程的最后一部分的容量小于页框大小，就会造成一点内部碎片，所以页框不能太大，否则会产生过于大的内部碎片。

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

页表存储位置：进程的页表是存储在内存中的，而且是以连续的方式存放。

CPU想找到对应的进程页面，需要2次访问内存，一次访问页面，找到对应页面的页框号，一次用得到的页框号，在内存中找到对应页框。

快表与慢表：

快表：其实是一个访问速度比访问内存快很多的高速缓存器。

慢表：内存中的页表相对于快表而言，它就是慢表了。

快表的作用：

作用：快表用于存放当前访问的若干个页表项(页表项即页表中的一行数据)。操作系统会把最近经常访问的页表对应的页表项放入快表中。

背景：快表的设计是基于时间局部性原理的，意思就是当前使用的页面很可能在接下来的时间内被再次使用。 

引入快表后的不同：

当没有引入快表时，CPU访问某个进程的页面需要两次访问内存：1次是访问内存中的慢表(页表)，从里面找到所需页面在内存的哪个页框内。第2次是根据页表得到的内存页框号访问内存，找到所需进程页面。

当引入快表时，CPU访问某个进程的页面会现在快表中查找，若查不到，则会回到页表上找。若找到，就会根据快表中给出的页框号，直接访问内存对应的页框。差别就在，快表是高速缓存器，访问快表比访问内存快多了，所以可以节省时间，而且快表肯定比页表小，所以查询起来，查询成本也低。

详细流程如下图：

两级页表：

一级页面的缺点：

问题1. 由于页表必须要连续存放，因此当页表很大的时候，需要占用很多个连续的页框。

问题2.由于时间局部性原理，一个进程在一段时间内可能只需要访问某几个特定的页面，因此没必要让整个页表都常驻内存。

 

我们先谈问题1：解决页表必须要连续存放的问题。

使用两级页表，意思就是把连续的页表像进程一样进行分解，分解成几组。每组扔进内存中空闲的页框中，这样连续存放变成离散存放了。但是对应的，为了检索离散分配的页表，我们也必须再构造一个连续的页表(叫页目录表)用于检索离散存储的页表。

两级页表具体如下：

这样就可以把连续的页表分成离散的多个部分存放了。但是要额外占用一个页目录表的空间。

问题2：一个进程在一段时间内可能只需要访问某几个特定的页面，因此没必要让整个页表都常驻内存。

可以在需要访问页面时，才把页面从外存调入内存，所以可以在页表项中增加一个标志位，用于表示该页面是否调入内存。

若想访问的页面不在内存中，则会产生缺页中断，然后将目标页面调入内存。

如果设计到从外存调入页面和从内存调出页面，那就不是基本分页存储管理了，那就变成了请求分页存储管理。

（PS：由于请求分页是虚拟内存的范畴，将会在迟下的时候讲）

总结两级页面(甚至多级页面)的优缺点：

优点：可以以更小的空间存储页表，例如有两级页表，一级页表肯定比二级页表小嘛，因为一级页表是二级页表的索引，当然还要加上一个条件，就是二级页表也是会被调出外存的，这个时候，才能说多级页表能减少存储空间。

缺点：额外增加访存次数。

 

2.2 基本分段存储管理

与分页的不同就在，分页存储方式的页面是大小一样的。而分段是可以大小不一样的。类似于固定分区分配和动态分区分配的区别。

分段：按照程序自身逻辑关系划分为若干个段。每个段在内存中占连续空间，但是各个段之间可以不相邻。

段表：分页有页表，那么分段也有段表，段表用于记录每个段在内存中的起始位置与大小。

分段比分页好的地方在于，分段可以按照程序的需求来划分段，如：

分段和分页的对比：

分段比分页更容易实现信息的共享和保护。

怎么理解呢？其实一个程序中，分为可修改代码和不可修改代码，可修改代码是不可共享的，比如一个代码段有很多变量，各进程并发访问会造成数据的不一致。

分段的优点：很方便地对逻辑模块实现信息的共享和保护。

分段的缺点：跟动态分区分配一样，会产生外部碎片。虽然说外部碎片可以使用紧凑技术处理，但是这样会付出很大的时间成本。而且如果段长过大，为其分配的连续存储空间会很不方便。

3. 段页式

由于分页和分段都有各自的缺点，因此结合了两种方式提出了段页式管理方式。

段页式是将进程先分段，然后再对段进行分页。

段页式的段表和页表：

段页式存储，都会维护一个段表和一个页表。

好处：就是把每段都分组了，这些组其实可以通过一些技术调出内存的，只有用到了再调回来。无外部碎片，但是有内部碎片。因为可以看到内存都是以页框存储的。因为分页式的优点就是内存利用率高，先分段再分页，那样既在逻辑上满足了用户需求，又提升了内存利用率。

坏处：至少需要三次访存，第一次访段表，第二次访页表，第三次访数据。

 

三、虚拟内存技术

之前的方法有个问题就是，进程必须要全部放进去才能开始运行，但是由于局部性原理我们可以知道，一个进程有时候只会频繁使用某些页面，因此其他不被使用到的页面就会占用着内存空间。为了解决这个问题，提出了虚拟内存技术的，总体而言就是把用不到的进程页面从内存调到外存中，当使用到的时候再调入内存。

从上图可以看到，虚拟内存技术其实就是分页、分段、段页式的改进。那我们就逐个来看一看：

 

3.1 请求分页存储管理

主要流程：

在请求分页中，如果所需要的页面不在内存中，就会产生一个缺页中断，然后由操作系统的缺页中断程序来处理。此时缺页的进程阻塞，并进入阻塞队列，当调页码完成后，再将它唤醒，放入就绪队列。

此时，如果内存中有空闲的页框，则会把所缺页面装入这个页框。如果内存中已经没有空闲的页框，则由页面置换算法选择一个页面淘汰掉。（页面置换算法等下会讲）

 

请求分页和传统分页的分别：

1。当需要的页面不在内存中，由操作系统负责将所需要的页面从外存调入内存。

2.。当内存空间不够时，由操作系统将内存中暂时用不到的页面换出到外存。

从上面的表述可以看到，内存和外存的调入调出都要经过操作系统的。所以就意味着肯定会产生中断。这也意味着其实会有额外的开销。

3.1.1 请求分页的页表机制

我们回顾一下，传统的分页机制的页表：

可以看到非常简单，只需要记录对应页表的内存块号(页框)就行了。

请求分页的页表：

由于请求分页方式可能会把某些页面放到外存，因此此页表不仅要记录，内存位置，还要记录外存的位置。 

修改位：因为有的页面从外存调入内存后，可能会被修改，所以就要记录这个页面是否被修改过，若被修改过，就要花点时间把它写回到外存中，保持数据的一致性，若是没修改过，则不需要花费额外的时间把数据写回去。

访问字段：记录最近此页面被调用过几次。用于判断此页面是否要被调到外存去。

3.1.2 页面置换算法

由于页面的换出、换入是需要用到磁盘I/O的(毕竟与外存交互)，所以好的页面置换算法需要追求更小的缺页率。

页面置换算法：目的就是用来确定竟然要从内存中调哪一个页面到外存去。

由上图可知，页面置换算法一共5种，其实只有4种。因为第一种OPT算法是不可能实现的，因为它是淘汰以后不再使用或者很长时间不再使用的页面，但是我们永远不知道哪些页面是之后再也不会用到的，我们不能预言，所以OPT算法只能存在于理论上。

3.1.2.1 先进先出置换算法(FIFO)

顾名思义，就是淘汰最早进来的页面，跟队列一样。

但是FIFO会出现belady异常，belady异常就是为进程分配的内存块(页框)越多，缺页率反而越大。这是一种只会在FIFO置换算法出出现的异常。

为什么会发生belady异常？

进程页数增加 —> 能贮存的页数增加 —> 哪些页？—> 后面来的页
先进先出的替换算法，完全不考虑使用频率，即使增加了进程页数，多贮存的部分接下来常访问可能性也不一定大（看运气），也就并不一定能增加命中率。

具体例子如下：

进程的页数为3的情况：(即内存块最多3个)

进程的页数为4的情况：

缺页了10次，比内存块为3的情况还多。

 

3.1.2.2 最近最久未使用置换算法(LRU)

LRU：替换的页面都是最近最久未被使用的页面。

实现方法：在页表中，新增一个访问字段，用于记录该页面自上次被访问以来所经历的时间t。然后淘汰时就淘汰t最大的页面。

LRU算法是性能最接近理想的OPT算法的，但缺点就是需要专门硬件支持，实现困难，开销大。

硬件实现方式：

内存中的每个页面都会有一个寄存器R，可以表示为：

当访问某个页面时，会把该页面的R寄存器的 Rn-1 位置成1。注意，每隔一段时间，R的位是会往右移的，补位的是0。因此若把R看作是一个整数的话，其实右移一位相当于除了2，所以要淘汰页面时，淘汰R最小的那个页面就行了。

如下图，是某时刻8个页面的R：

可以看到，页3是最小的，所以首先要移出3。还能看出，最近访问的页面是2和5，因为他们的R7位都是1。

 

3.1.2.3 时钟置换算法（CLOCK）

OPT算法：性能最好，但无法实现。

FIFO算法：实现简单，但性能差，其换页的逻辑跟局部性原理无关，就是不考虑页面被使用的频次，有可能出现belady异常。

LRU算法：性能最接近OPT，但需要额外硬件，需要额外开销，实现难度大。

所以有了 时间置换算法(CLOCK)，这是一种均衡性能和开销的算法。

实现方法：

为每个页面设置一个访问位置，再将内存中的页面都通过链接指针连接成一个循环队列，当某页被访问时，该访问位置为1。当需要淘汰页面时，只需检查页的访问位，如果是0，则换出，如果是1则把它置为0，暂不换出，继续检查下个页面。若第一轮扫描中，页面的访问位都是1，则把1都置0，然后启动第二轮扫描，第二轮扫描肯定会有0的页面。所以这种方法最多会经过两轮扫描。

对应页表设计：

内存中的页面链接方式：

 

3.1.2.4 改进型的时钟置换算法

普通的时钟置换算法，只考虑一个页面最近有没有被修改过，但是改进型时钟算法除了考虑最近是否被访问过之外，也考虑了页面有没有被修改过，因为没有修改过的页面是不需要花额外开销去执行I/O操作把他重新写回外存的，所以在其他条件相同时，优先换出没有修改过的页面。

同样在页面中，维护一个(访问位，修改位)，例如（1，1）为最近被访问过且被修改过。

最多进行4轮扫描。

页面置换算法的总结：

 

3.1.3 页面分配算法

之前的页面置换算法目的是为了从内存调出页面到外存时，选择哪个页面需要被淘汰。

这里的页面分配算法目的是为了从外存调入页面到内存时，要选择哪个页框来存放。

首先要明白一个概念：

驻留集：指请求分页存储管理中给进程分配的内存物理块(页框)个数。

若驻留集太小，则会造成进程频繁缺页，系统处理花费大量时间通过I/O从外存里调页。

若驻留集太大，则会导致进程并发度下降，资源利用率低，因为进程频繁使用的页面小于驻留集，则该进程的驻留集中很多都是使用频率较小的页面，所以会导致并发度低，资源利用率低。

所以如何决定进程的驻留集大小，是个问题：

1.固定分配局部替换

系统为每个进程分配固定数量的内存块(页框)，整个运行过程都不变，若发生缺页，只能从进程已有的物理块中选择一页换出，并调入所需页面。

缺点：很难在一开始就决定一个进程到底分配多少物理块才合理。

2.可变分配局部替换：

刚开始会被进程分配一定数量的物理块，当某进程发生缺页时，只允许从进程自己的物理块中挑出一个进行淘汰，但如果发生频繁缺页，系统会被这个进程多分配几个物理块，直到该进程的缺页率减少到一定程度，反之，如果进程在运行过程中，缺页率特别低，则适当减少该进程的物理块。（要根据发生缺页的频率来动态增加或减少进程的物理块）

3.可变分配全局替换：

刚开始会被进程分配一定数量的物理块，且会维持一个空闲物理块队列，当某进程发生缺页时，从空闲物理块队列中挑出一页分配给该进程，若已经没有空闲的物理块，则选择调出的的页面有空能是系统中任何一个进程的页面。（只要发生缺页就分配新物理块）

内存抖动

内存抖动：刚刚换出的页面马上又要换入内存，刚刚换入内存的页面马上又要换出。这种频繁页面调度的行为就叫内存抖动。

产生的原因：进程频繁访问的页面数大于进程可用的物理块数。

解决方法：（引入工作集概念）

工作集：在某段时间内，进程实际访问的页面集合。

如下图，工作集的大小其实不是固定的，但我们只要保证进程的驻留集(进程拥有的物理块数量)不小于工作集大小即可。