操作系统之内存管理(分页存储分段存储虚拟存储器置换算法)

谁践踏了优雅 2023-09-29 15:31 26阅读 0赞

![在这里插入图片描述][e503dce657e64084af774776cb1507eb.png_pic_center]

### 一、层次结构 ###

速度越快的存储器，存储容量单价就越贵，所以为了平衡处理速度和价格，存储器的设计分成了多个结构。

#### 1.1 多级存储器结构 ####

![在这里插入图片描述][ac4880417bf34b90beec416e281eea9e.png_pic_center]

这部分的内容不做过多的介绍

### 二、程序的装入和链接 ###

在使用进程管理的操作系统下，想要运行一个程序，首先要把程序变成一个进程，这个过程就是程序装入和链接的过程。先把程序链接编译，然后装入内存。

#### 2.1 程序的装入 ####

把一个程序装入内存中，有多种方式。

*  绝对装入
 *  可重定位装入
 *  动态装入

##### 2.1.1 绝对装入 #####

所谓绝对，意思就是程序的物理地址和逻辑地址是一致的，一眼就能看出来这个程序在内存中的什么位置。

##### 2.1.2 可重定位装入 #####

可重定位是绝对装入的补充。绝对装入只适用于单道程序中，能知道内存的地址。但是多道程序做不到，只能知道相对的地址。

![在这里插入图片描述][6a7f82e9e9094c929f5244f9faf4b6ad.png_pic_center]

##### 2.1.3 动态运行时装入 #####

上诉说的装入方式，都不支持程序在内存中的移动。该方法先给程序分配逻辑地址，当程序运行时，再分配内存，即得到物理地址。

#### 2.2 程序的链接 ####

程序的链接也是有三种方式

*  静态链接
 *  装入时链接
 *  运行时链接

##### 2.2.1 静态链接 #####

使用一个例子解释静态链接需要解决的问题

![在这里插入图片描述][309e01d365014d3c9c73b6c1b9632f38.png_pic_center]

程序编译后，分成三个模块，A模块调用B，B模块调用C。链接时要做两个修改：

##### 1）修改相对地址 #####

由于程序分模块装入，原模块使用的都是相对地址，每个模块都是从零开始，因此要修改每个模块的起始地址

##### 2）变换外部调用符号 #####

把调用符号改成模块所在地址

##### 2.2.2 装入时动态链接 #####

在程序编译得到目标模块后，边装入内存边链接。当装入一个模块时，发生外部调用事件时，再找到该模块装入内存。

这种方式第一便于修改和更新模块。第二，能够实现对目标模块的共享。

##### 2.2.3 运行时动态链接 #####

一个程序运行时，每次运行的模块可能是不一样的，所以可以在程序运行时再把模块载入。

### 三、 虚拟存储器 ###

作业运行的前提就是放在内存中。但是内存又贵又少，导致作业的运行会收到很大的限制。采用虚拟存储器，链接外存和内存，从逻辑上扩充内存容量。

#### 3.1 解决的问题 ####

引入新的设计，目的是为了解决问题，下面先来看看，原先的解决办法所存在的问题，再来分析虚拟存储器存在的意义。

##### 3.1.1常规存储器管理方式的特征 #####

**①一次性**。作业在运行前要全部装入内存。

**②驻留性**。作业装入内存后，就一直留在内存，直到整个作业完成才离开。会占用大量的内存时间。

##### 3.1.2局部性原理 #####

在短时间内，程序的执行仅局限于某个部分，相应其存储空间也局限于某个区域。

还包括时间局限性，空间局限性。某条指令被执行后，不久后有可能再次执行，某个存储单位被访问后，后面一段时间访问的位置在其附近。

##### 3.1.3虚拟存储器的定义 #####

基于局部性原理，在作业运行之前没必要全部装入内存。先把当前需要的少数页面或者段装入，在运行过程中，发生缺页或者缺段时再调入。当内存满时，使用置换功能，把展示不用的页面或段调到外存。

所以实际上虚拟存储器做的工作就是充分利用外存。

#### 3.2 实现方法 ####

##### 3.2.1 分页请求 #####

在分页系统的基础上，增加的请求调页和页面置换的功能。

实现这样的功能，在硬件上需要一定支持：

*  页表机制
 *  缺页中断机制
 *  地址变换机制

##### 3.2.2 分段请求 #####

同上

#### 3.3 特征 ####

**多次性**：一个作业被分为多次调入内存。

**对换性**：允许作业在运行时换进换出。

**虚拟性**：从逻辑上扩充内存容量。

### 四、连续分配 ###

连续分配是最简单的内存分配算法，甚至说毫无算法可言，就是把一整块内存空间丢给用户程序。

#### 4.1 单一连续分配 ####

只把内存分成两块，OS用的和用户用的，不做其他管理。

#### 4.2 固定分区分配 ####

把用户空间的内存分成几块，每块装入一个作业，这样就允许几个作业并发执行了。

但是问题也很多，你的分区分多大？怎么分区？分几个？这是非常不灵活的。

#### 4.3 动态分区分配 ####

所谓动态，就是给进程分配的内存资源是动态的，根据进程需要分配的。但是这又带来一个大问题，如何确定进程需要多少内存？

##### 1）实现 #####

要实现动态分区，要提供一个分区管理的功能。设置一个数据结构，能够记录空闲空间和已分配空间。

![在这里插入图片描述][6c56194181004ac4a13075c59c3df5c5.png_pic_center]

设置一个块，里面存放的当前空闲区域的起始地址，结束地址以及可以大小。再设置一个链，用来链接这一个一个分散的空闲区域。

##### 2）分配算法 #####

把作业装入内存中，有几个常见的分配算法

**首次适应算法**

找到第一个满足作业需要的，就给他分配

**循环首次适应算法**

对首次适应算法的改进，不要每次都从链头找，从上次分配区域的下一个地方开始找。

这个算法比起第一个来说，为什么是改进呢？

如果每次都从链头开始，那后面为程序分配的内存位置是不一定的，因为内存中存在许多碎片。这样可能导致内存碎片越来越多。

**最佳适应算法**

找到满足需求的最小的空间

**最坏适应算法**

找到最大的区域

**快速适应算法**  
以上所说都算是顺序搜索法的一种，该算法是分类搜索法。

该算法对所有分区大小相同的分区设置一个链表进行管理，进行分类。

#### 4.4 可重定位分区分配 ####

为了解决内存中碎片过多，导致某些占用内存大的作业无法运行的情况。该算法可以把内存作业进行重定位。

把碎片作业进行移动，凑出一个较大的空闲分区出来。

实现过程要注意修改相对地址。

#### 4.5 对换 ####

对换其实就是对虚拟存储器的利用，把内存中暂时不运行的作业丢到外存中去。

### 五、页面置换算法 ###

页面置换是基于虚拟存储器技术的，当有新作业想要调入内存，但是内存不足，或者进程需要访问某个页面但是不在内存中，则需要使用页面调度算法，清理部分内存空间，调入所需页面。

#### 5.1 最佳置换算法 ####

该算法是一直理论算法，就是每次淘汰一个以后永不使用的页面。实际上该算法无法实现，因为没有办法预知哪个页面以后永远不使用。

#### 5.2 先进先出算法FIFO ####

这个算法是最简单的也是最常见的。每次淘汰最先进入的页面，即在内存中驻留最久的页面被淘汰。但实际上该算法与实际使用情况中并不合理。因为可能一些页面会经常使用到，如果把它淘汰了，会经常导致缺页。

##### 1）算法支持 #####

要实现该算法，需要一个指针，指向当前驻留最久的页面，如下图，把页面先后连接成一个队列。

##### 2）例子 #####

![在这里插入图片描述][81622b0da0d2423c895b670a6017b256.png_pic_center]

从图中可以看到，FIFO进行了12次页面置换。

#### 5.3 最久未使用算法LRU ####

##### 1）算法描述 #####

最久未使用算法则更接近最佳置换算法，因为最久没使用的页面以后也不适用的可能性较大。

![在这里插入图片描述][0df68a573f774866a704d4c7cbe290b7.png_pic_center]

可以看到，使用该算法一共进行了9次页面置换

##### 2）算法支持 #####

要实现该算法，首先要确定，哪个页面是最久未使用的？这就需要设置一个信号量。

实现支持可以用寄存器或者栈。

**寄存器**

![在这里插入图片描述][6ae7396ab08b4a1e90bd2f960448f145.png_pic_center]

使用寄存器来记录页面使用情况。倘若有n哥页面，设置n个具有n位的寄存器，每个100ms寄存器右移一位。

**栈**

使用一个栈保存各个页面。当进程访问页面时，栈中把该页面从栈中移除，然后压入栈顶。栈底则是最久未使用的页面的。

![在这里插入图片描述][a75ec2614648443496770f89991c6d01.png_pic_center]

### 六、分页存储 ###

连续的分配方式会导致大量的碎片，碎片难以被利用，造成内存浪费。如果把允许把一个进程分散转入到其他不相邻的分区中，可以解决该问题。因为连续分配需要知道进程内存，从而一步到位，但是离散分配可以更灵活。

如果离散分配的基本单位是页，则曾为分页存储；如果是段，则称为分段。

#### 6.1 基本分页存储方式 ####

基本分页方式是不支持对换，不知道页面调度的，因此也是不支持虚拟存储技术。基于调度的分页管理在第二节介绍。

##### 1）页面和页表 #####

页面是一个逻辑地址概念，是一段地址空间，页是针对作业而言的，把一个作业所需要的内存分成多个页，更便于管理，这个页引用地址中不同的块。

页表是逻辑地址和物理地址的转换机构，转换页号和块号。

块则是物理地址的概念，块的大小通常和页面大小相同，以匹配分页存储方式。

**地址结构**

![在这里插入图片描述][4ddc3d777ba14854bc917b89554f4872.png_pic_center]

使用分页技术后，地址应该首先表明页号，然后就是内容在该页的偏移量。

**页表**

![在这里插入图片描述][5a62535cc8264f9eaaf2db65e47072b7.png_pic_center]

##### 2）地址变换机构 #####

进程访问的是逻辑地址。因此计算机中需要有一个机构，来把逻辑页面地址映射到物理地址块号中。上面的页表其实就是这个变换机构。

**基本的地址变换机构**

页表的功能可以由寄存器来实现。但是寄存器实在太贵了，一个页表项用一个寄存器，倘若页表项大大增加，成本也蹭蹭往上涨。因此，页表大部分都驻留在内存中。系统中只放一个页表寄存器来表明页表在内存的位置和长度。当进程未启动时，这些信息放在PCB中，启动后把信息装入页表寄存器中。

**具有快表的地址变换机构**

使用基本的变换机构，每次计算机要访问两次内存。第一次是找到页表，获得其物理地址。第二次的访问内存中该物理地址的位置。这会让计算机处理速度大大降低，因此设置一个快表，可以直接读到页面物理地址，可以加大处理速度。

新设置一个快表寄存器，CPU给出地址有，把页号信息丢入快表中进行查找，找到就能直接读取块地址，如果找不到，就使用原方式，同时修改快表。

当然，修改快表的过程也类似于页面对换，要有一个机制决定把哪些表信息移除。

##### 2） 多级页表 #####

计算机系统发展非常快，内存发展很快。当页表非常大之后，每个PCB可能需要很大的内存来记录页表位置(2^31…等)，那肯定造成资源浪费。

于是就设置二级页表或者多级页表。

把页表当成也来进行分页存储。(递归实现了属于是)

![在这里插入图片描述][40e78b7ae4494ec09979432ab04e2b57.png_pic_center]

#### 6.2 请求分页存储 ####

请求分页是基于基本分页技术，在此基础上，支持虚拟存储技术，实现调页，置换页面的功能。

##### 1）硬件支持 #####

**页表**

实现请求分页，在基本分页的基础上，首先页表要进行一定的修改。

![在这里插入图片描述][b3dcc1c573b1449a95da50a5aec00301.png_pic_center]

从中可以看到，比普通页表多了一个**访问字段，状态位，修改位，外存地址**。状态位用来记录内存是否调入内存。访问字段用来辅助页面调入算法的。修改位则是用来标记页面是否被修改，由于页面在外存中也有一个副本，如果修改了就要把内容重写进外存中。

**缺页中断机构**  
当进程执行过程中，发现页面不在内存中，要中断CPU，然后去寻找内存。要有一个中断保护机制，保护好当前的运行环境，相关数据。

### 七、分段存储 ###

分页管理可以提高内存利用率，而分段管理的目的是满足用户的更多需求。

#### 7.1 基本分段 ####

##### 1）基本原理 #####

**分段**  
一个作业的地址空间被分成几个段，每个段有各自的逻辑信息。比如说主程序段，子程序段，数据段等。

**段表**

不同的段也是离散的存放在内存中，因此也需要一个地址映射表来找到程序需要的段的位置。

![在这里插入图片描述][f1c3f280945c4889934991d480c2b5b5.png_pic_center]

**地址变换机构**

实现这个段表，需要一个段表寄存器，来存放段地址和长度。

同时，和分页一样，每次寻找段要访问两次内存，解决方案也和页一样。

**分页&分段的区别**

*  页是信息的物理单位，段是逻辑单位
 *  页的大小由系统决定，段则由程序决定

##### 2）信息共享 #####

分段系统可以实现段的共享。不同的进程可以共享一个段，对段的保护也很简单。因为段是逻辑单位，实际上需要共享的内容不多，只需要分一个较小的段即可。而页则是信息单位，比较不便于实现用户的期望。

##### 3）段页式 #####

分页分段各有利弊，分段对于用户更友好，因为是逻辑单位，分段更便于提高内存利用率，因为它不负载逻辑信息，所以它负载的信息比分段少。而两者相结合，则能得到一个更优化的系统，段页式系统。

**基本原理**  
段页式管理，首先把用户程序分段，然后用页来管理段。

![在这里插入图片描述][711ecd20854d4cd7a59986c51846a085.png_pic_center]

#### 7.2 请求分段 ####

请求分段和请求分页其实相似。

[e503dce657e64084af774776cb1507eb.png_pic_center]: https://img-blog.csdnimg.cn/e503dce657e64084af774776cb1507eb.png#pic_center
[ac4880417bf34b90beec416e281eea9e.png_pic_center]: https://img-blog.csdnimg.cn/ac4880417bf34b90beec416e281eea9e.png#pic_center
[6a7f82e9e9094c929f5244f9faf4b6ad.png_pic_center]: https://img-blog.csdnimg.cn/6a7f82e9e9094c929f5244f9faf4b6ad.png#pic_center
[309e01d365014d3c9c73b6c1b9632f38.png_pic_center]: https://img-blog.csdnimg.cn/309e01d365014d3c9c73b6c1b9632f38.png#pic_center
[6c56194181004ac4a13075c59c3df5c5.png_pic_center]: https://img-blog.csdnimg.cn/6c56194181004ac4a13075c59c3df5c5.png#pic_center
[81622b0da0d2423c895b670a6017b256.png_pic_center]: https://img-blog.csdnimg.cn/81622b0da0d2423c895b670a6017b256.png#pic_center
[0df68a573f774866a704d4c7cbe290b7.png_pic_center]: https://img-blog.csdnimg.cn/0df68a573f774866a704d4c7cbe290b7.png#pic_center
[6ae7396ab08b4a1e90bd2f960448f145.png_pic_center]: https://img-blog.csdnimg.cn/6ae7396ab08b4a1e90bd2f960448f145.png#pic_center
[a75ec2614648443496770f89991c6d01.png_pic_center]: https://img-blog.csdnimg.cn/a75ec2614648443496770f89991c6d01.png#pic_center
[4ddc3d777ba14854bc917b89554f4872.png_pic_center]: https://img-blog.csdnimg.cn/4ddc3d777ba14854bc917b89554f4872.png#pic_center
[5a62535cc8264f9eaaf2db65e47072b7.png_pic_center]: https://img-blog.csdnimg.cn/5a62535cc8264f9eaaf2db65e47072b7.png#pic_center
[40e78b7ae4494ec09979432ab04e2b57.png_pic_center]: https://img-blog.csdnimg.cn/40e78b7ae4494ec09979432ab04e2b57.png#pic_center
[b3dcc1c573b1449a95da50a5aec00301.png_pic_center]: https://img-blog.csdnimg.cn/b3dcc1c573b1449a95da50a5aec00301.png#pic_center
[f1c3f280945c4889934991d480c2b5b5.png_pic_center]: https://img-blog.csdnimg.cn/f1c3f280945c4889934991d480c2b5b5.png#pic_center
[711ecd20854d4cd7a59986c51846a085.png_pic_center]: https://img-blog.csdnimg.cn/711ecd20854d4cd7a59986c51846a085.png#pic_center