Linux内存管理

· ☕ 16 分钟 · 👻 Victor
🏷️
  • #Linux
  • 关于程序的装入

    • 绝对装入:绝对映射,程序中逻辑地址与内存物理地址完全相同 (单片机)

    • 可重定位装入:静态映射,在装入时对逻辑地址进行修改

    • 动态运行时装入:逻辑地址到物理地址的映射在程序运行时才执行 (现代PC机)

    绝对装入与可重定向装入

    而动态重定位如下:

    动态重定位

    静态重定位的特点是在一个作业装入内存时,必须分配其要求的全部内存空间,如果没有足够的内存,就不能装入该作业。此外,作业一旦进入内存后,在整个运行期间不能在内存中移动,也不能再申请内存空间。

    关于程序的链接

    • 静态链接方式(Static Linking)

      在程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的可执行程序,以后不再拆开。

    • 装入时动态链接(Load time Dynamic Linking)

      将用户源程序编译后所得到的一组目标模块,在装入内存时,釆用边装入边链接的链接方式。

    • 运行时动态链接(Run-time Dynamic Linking)

      对某些目标模块的链接,是在程序执行中需要该目标模块时,才对它进行的链接。其优点是便于修改和更新,便于实现对目标模块的共享。

    连续分配方式

    单一连续分配

    只能用于单用户、单任务的操作系统中。采用这种存储管理方式时,可把内存分为系统区和用户区两部分,系统区仅提供给 OS 使用,通常是放在内存的低址部分;用户区是指除系统区以外的全部内存空间,提供给用户使用。

    单一连续分配

    固定分区连续分配

    将内存用户空间划分为若干个固定大小的区域,在每个分区中只装入一道作业,这样,把用户空间划分为几个分区,便允许有几道作业并发运行。当有一空闲分区时,便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区,当该作业结束时,又可再从后备作业队列中找出另一作业调入该分区。

    划分分区的方法:

    1. 分区大小相等
    2. 分区大小不相等

    固定分区

    另外可以设置分区大小不等的一些分区,如下:

    大小不等的分区

    固定分区分配的缺点:

    1. 造成存储空间的浪费
    2. 拓展性差

    动态分区分配

    动态分区分配数据结构:

    • 空闲分区表

      在系统中设置一张空闲分区表,用于记录每个空闲分区的情况。每个空闲分区占一个表目,表目中包括分区序号、分区始址及分区的大小等数据项。

      空闲分区表

    • 空闲分区链

      为了实现对空闲分区的分配和链接,在每个分区的起始部分,设置一些用于控制分区分配的信息,以及用于链接各分区所用的前向指针;在分区尾部则设置一后向指针,通过前、后向链接指针,可将所有的空闲分区链接成一个双向链,如下图所示:

      空闲分区链

    内存分配分配算法

    基于顺序搜索:(适合不太大的系统)

    • 首次适应算法(FF)

      在分配内存时,从链首开始顺序查找,直到找到一个大小能满足的空闲分区即可。然后再再按照作业的大小,从空间分区中划分出与作业大小相同的空间给作业使用,余下的空间留在空闲分区链中。

      首次适应算法要求空闲分区链以地址递增的次序链接。

      缺点:空闲分区链的低地址部分不断被划分,会有许多细小的碎片空间难以利用。每次都是从低地址开始找空闲分区,查找的效率低。

    • 循环首次适应算法(NF)

      循环首次适应算法在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直到找到一个能够满足进程的空闲分区为止,最后从空闲分区划分出与请求大小相等的空间给作业。

      循环到链表末尾又从新从链首开始查找。

      缺点:缺少可用的大空间空闲分区。

    • 最佳适应算法(BF)

      最佳适应算法在分配内存的时候,把满足要求并且又是最小的空闲分区给作业。为了加速寻找,该算法需要对空闲分区链按照空闲分区大小进行从小到大排序。

      缺点:会产生许多细小的碎片

    • 最差适应算法(WF)

      最差适应算法每次分配内存的时候,把满足要求的最大的空闲分区给作业,将与作业申请大小的空间划分出来,剩余的空间留在空闲分区中,并且更新空闲分区链。该算法需要对空闲分区链按照空闲分区大小进行从大到小排序。

      优点:查找效率块,产生碎片少。

      缺点:缺少大的空闲分区

    例子:

    假设有新程序F装入,大小为32K,当前已有程序B和D,最近一次空间分配是D:

    三种分配算法

    基于索引搜索:(适合比较大的系统)

    • 快速适应算法(QF)

      该算法又叫做分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设置一个空闲分区链,这样系统存在多个空闲分区链。同时,还需要在内存中设立一张管理索引表,其中的每一个索引表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头指针。

      空闲分区的分类是根据进程常用的空闲大小进行划分的,如2KB、4KB、8KB等,对于其他大小的空闲分区像7KB的空闲分区,既可以放在8KB的链表中,也可以放在一个特殊的空闲链表中。

    • 伙伴系统

      该算法规定,无论是分配分区还是空闲分区,其大小均为2的k次幂(k为整数且1<=k<=m)。通常$2^m$是整个可分配内存的大小。

      伙伴系统

    • 哈希算法

      哈希算法是利用哈希快速查找的优点,以及空闲分区在可利用空闲分区表中的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。

    动态重定位分区分配

    紧凑

    对内存中正在使用的分区进行搬迁,使多个小的空闲分区(碎片)合并为一个大的空闲分区

    紧凑

    动态重定位

    动态重定位

    算法

    算法

    什么是内存碎片?

    内部碎片是指已经分配给作业但不能被利用的内存空间,外部碎片是指系统中还没有分配给作业,但由于碎片太小而无法分配给申请内存空间的新进程的存储块。通俗点的理解就是,某个作业所占用的内存区域如果没有装满,就是内部碎片,而作业与作业之间,如果有内存区域没有分配给某个作业,但又不能分配给任何作业,就是外部碎片。

    内存碎片

    连续分配: 为用户进程分配的必须是一个连续的内存空间。
    非连续分配: 为用户进程分配的可以是一些分散的内存空间。

    非连续分配方式(离散分配方式)

    思想

    假设进程A大小为23MB,但是每个分区大小只有10MB,如果进程只能占用一个分区,那显然放不下。
    解决思路:

    如果允许进程占用多个分区,那么可以把进程拆分成10MB+10MB+3MB三个部外,再把这三个部分分别放到三个分区中(这些分区不要求连续)…
    进程A的最后一个部分是3MB,放入分区后会产生7MB的内部碎片,如果每个分区大小为2MB,那么进程A可以拆分成11*2MB +1MB共12个部分,只有最后一部分1MB占不满分区,共产生1MB的内部碎片.
    显然,如果把外区大小设置的更小一些,内部碎片会更小,内学利用率会更高.

    非连续分配

    具有快表的地址变换机构:(时间局部性与空间局部性原理)

    快表,又称联想寄存器(TLB) ,是一种访问速度比内存快很多的高速缓冲存储器,用来存放当"前访间的若干页表项,以加速地址变换的过程。与此对应,内存中的页表常称为慢表。

    TLB

    多级页表

    问题

    加载一个大的页表需要占用很大的内存

    解决

    将大表分为几个小表。类似CIDR。

    可将长长的页表进行分组,使每个内存块刚好可以放入一个分组(比如上个侧子中,页面大小4KB,每个页表项48,每个页面可存放1K个页表项,因此每1K个连续的页表项为一组,每组刚好占一个内存块,再讲各组离散地放到各个内存块中)另外,要为离散分配的页表再建立一张页表,称为页目录表,或称外层页表,或称顶层页表

    存储管理方式

    本质上是一种内存的划分方法

    分页存储管理

    这种方式中,将用户程序的地址空间,注意,是用户程序的地址空间分为若干个固定大小的区域,成为“页”或“页面”。我们可以知道,这也页其实是不存在的,只是一种划分内存空间的方法。也就是说,这种方式将用户的程序**“肢解”**了,分成很多个小的部分,每个部分称为一个“页”。

    逻辑地址

    将逻辑地址的前n位作为页号,后面32-n位作为页内偏移量。

    逻辑地址

    页内碎片

    由于进程的最后一页经常装不满一个块,从而形成了不可利用的碎片,称之为**“页内碎片”**。

    程序逻辑地址划分为页和页内地址

    页表

    作用:实现页号到物理号的地址映射。

    页表是记录逻辑空间(虚拟内存)中每一页在内存中对应的物理块号。但并非每一页逻辑空间都会实际对应着一个物理块,只有实际驻留在物理内存空间中的页才会对应着物理块。

    系统会为每一个进程建立一张页表,页表是需要一直驻留在物理内存中的(多级页表除外),另外页表的起址和长度存放在 PCB(Process Control Block)进程控制结构体中。

    页表

    可以在页表的表项中设置相关的权限控制字段,例如设置存取控制字段,用于保护该存储块的读写;若存取控制字段为2位,则可以设置读/写、只读和只执行等存取方式。

    物理块

    物理块是实实在在存在于内存中的:

    物理块

    地址变换机构

    由于执行频率高,要求效率比较高,需要使用硬件实现。

    在系统中设置一个页表寄存器(PTR),其中存放页表在内存的起始地址和页表的长度。平时进程未执行的时候,页表的起始地址和页表长度放在本进程的PCB中。当调度程序调度到某个进程的时候,才将这两个数据装入页表寄存器

    注意,当创建一个进程的时候,它的页表也同时创建了,只不过只在PCB存储了页表的起始地址和长度。

    变换过程:

    1. 进程访问某个逻辑地址时,分页地址机构自动将逻辑地址分为页号和页内地址
    2. 页号大于页表长度,越界错误;否则继续下面的步骤
    3. 页表项的地址 p = 页表起始地址 F + 页号 P * 表项大小 S,从而得到对应的物理块号 B
    4. 页和物理块的大小是一致的,所以 页内地址=块内地址
    5. 然后 物理地址 = 物理块号 B * 页大小 L + 页内地址
    6. 根据物理地址读取数据

    地址变换

    快表的变换机构

    基础的地址变换机构的缺点:

    由于页表是存放在内存中的,这使得CPU在每存取一个数据时,都需要两次访问内存。第一次时访问内存中的页表,获取物理块号,于偏移值拼接得到物理地址,第二次是从第一次所得物理地址获取所需数据(或者向该地址写入数据)。这样计算机的处理速度几乎降低了1/2;

    为了提高地址变换速度,可在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器,又称为"联想寄存器"或者“快表”。俗称TLB。

    快表与页表的功能类似,其实就是将一部分页表存到 CPU 内部的高速缓冲存储器 Cache。CPU 寻址时先到快表查询相应的页表项形成物理地址,如果查询不到,则到内存中查询,并将对应页表项调入到快表中。但,如果快表的存储空间已满,则需要通过算法找到一个暂时不再需要的页表项,将它换出内存。

    具有快表的地址变换机构

    由于成本的关系,快表不可能做得很大,通常只存放 16~512 个页表项,这对中、小型作业来说,已有可能把全部页表项放在快表中;但对于大型作业而言,则只能将其一部分页表项放入其中。由于对程序和数据的访问往往带有局限性,因此,据统计,从快表中能找到所需页表项的概率可达 90% 以上。这样,由于增加了地址变换机构而造成的速度损失可减少到 10% 以下,达到了可接受的程度。

    两级页表

    一级页表的缺陷:由于页表必须连续存放,并且需要常驻物理内存,当逻辑地址空间很大时,导致页表占用内存空间很大。

    我们可以采用这样两个方法来解决这一问题:

    ① 对于页表所需的内存空间,可采用离散分配方式,以解决难以找到一块连续的大内存空间的问题;

    只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上,需要时再调入。

    二级页表的页表项:

    二级页表页表项

    过程:

    1. 外层页表寄存器中保存了外层页表的始址,根据外层页号查找到内层页号。
    2. 找到指定页表分页的始址,根据内层页号找到物理块号。
    3. 物理块号P和页内地址d组装成一个实际的物理地址。

    二级页表工作流程

    在采用两级页表结构的情况下,对于正在运行的进程,必须将其外层页表调入内存,而对于内页表则只需调入一页或几页。为了表征某页的页表是否已经调入内存,还应在外层页表项中增设一个状态位 S,其值若为 0,表示该页表分页不在内存中,否则说明其分页已调入内存。进程运行时,地址变换机构根据逻辑地址中的 P1去查找外层页表;若所找到的页表项中的状态位为 0,则产生一个中断信号,请求 OS 将该页表分页调入内存。

    多级页表

    多级页表和二级页表类似。多级页表和二级页表是为了节省物理内存空间。使得页表可以在内存中离散存储。(单级页表为了随机访问必须连续存储,如果虚拟内存空间很大,就需要很多页表项,就需要很大的连续内存空间,但是多级页表不需要。)

    分页式管理很好的避免了外部碎片,但是还是存在内部碎片,因为程序大小不可能总是2的n次幂。多级页表使得页表数据可以不需要连续存储,即实现了页表的离散式存储。并且在当对应程序运行才将内页表数据调入内存也减少了页表所占用的内存空间。本质上是提高内存利用率。

    分段存储管理

    为了满足用户要求的一种存储管理的方式

    为什么引入分段存储管理?

    1. 通常的程序都可以分为若干个段,如主程序段、子程序段A、子程序段B、…、数据段和栈段等等。
    2. 实现和满足信息共享、信息保护、动态链接以及信息的动态增长

    引入效果:

    • 方便编程

      使用符号作为段地址进行使用。(每个段都是从 0 开始的独立逻辑地址空间;)

    • 信息共享

      在实现对程序和数据的共享时,是以信息的逻辑单位为基础的。比如,为了共享某个过程、函数或文件。分页系统中的“页”只是存放信息的物理单位(块),并无完整的逻辑意义,这样,一个可被共享的过程往往可能需要占用数十个页面,这为实现共享增加了困难。段可以是信息的逻辑单位,因此,我们可以为该被共享过程建立一个独立的段,这就极大地简化了共享的实现。

    • 信息保护

      信息保护同样是以信息的逻辑单位为基础的,而且经常是以一个过程、函数或文件为基本单位进行保护的。例如,我们希望函数 A 仅允许进程执行,而不允许读,更不允许写,那么,我们只须在包含了函数 A 的这个段上标上只执行标志即可。但是在分页系统中,函数 A 可能要占用若干个页面,而且其中的第一个和最后一个页面还会装有其它程序段的数据,它们可能有着不同的保护属性,如可以允许进程读写,这样就很难对这些页面实施统一的保护,因此,分段管理方式能更有效和方便地实现对信息的保护功能。

    • 动态增长

      在实际应用中,往往存在着一些段,尤其是数据段,在它们的使用过程中,由于数据量的不断增加,而使数据段动态增长,相应地它所需要的存储空间也会动态增加。然而,对于数据段究竟会增长到多大,事先又很难确切地知道。对此,很难采取预先多分配的方法进行解决。前述的其它几种存储管理方式都难以应付这种动态增长的情况,而分段存储管理方式却能较好地解决这一问题。

    • 动态链接

      动态链接在作业运行之前,并不是把所有的目标程序段都链接起来。当程序要运行时,首先将主程序和它立即需要用到的目标程序装入内存,即启动运行。而在程序运行过程中,当需要调用某个目标程序时,才将该段(目标程序)调入内存并进行链接。可见,动态链接要求的是以目标程序(即段)作为链接的基本单位,因此,分段存储管理方式非常适合于动态链接。

    它将用户程序的地址空间分为若干个大小不同的的段,每个段可以定义一组完整的信息。

    分段地址

    段号表示段名,每个段都从0开始编址,并且采用一段连续的地址空间。

    分段地址

    在该地址结构中,允许一个作业最长有64K个段,每个段的最大长度为64KB。

    在分段式存储管理系统中,为每一个分段分配一个连续的分区。进程的各个段,可以离散地装入内存中不同的分区中。

    段表

    作用:实现从逻辑地址到物理内存区的映射。

    为了保证程序能够正常运行,就必须能够从物理内存中找出每个逻辑段所对应的位置。为此在系统中会为每一个进程建立一张段表。每个段在表中有一个表项,其中记录了该段在内存中的起始地址和段的长度。一般将段表保存在内存中。

    image-20200819224122503

    在配置了段表之后,执行的过程可以通过查找段表,找到每一个段所对应的内存区。

    地址变换机构

    为了实现进程从逻辑地址到物理地址的变换功能,在系统设置了段表寄存器,用于存放段表的起始地址和段表长度TL。

    在进行地址变换时,系统将逻辑地址中的段号与段表长度TL 进行比较。若 S > TL,表示段号太大,是访问越界,于是产生越界中断信号。若未越界,则根据段表的始址和该段的段号,计算出该段对应段表项的位置,从中读出该段在内存的起始地址。然后,再检查段内地址 d 是否超过该段的段长 SL。若超过,即 d>SL,同样发出越界中断信号。若未越界,则将该段的基址 d 与段内地址相加,即可得到要访问的内存。

    分段地址变换过程

    像分页系统一样,当段表放在内存中时,每要访问一个数据,都须访问两次内存,从而成倍地降低了计算机的速率。解决的方法和分页系统类似,也增设一个联相存储器,用于保存最近常用的段表项。一般情况下,由于是段比页大,因而段表项的数目比页表项的数目少,其所需的联想存储器也相对较小,所以可以显著地减少存取数据的时间,与没有地址变换的常规存储器相比而言,其存取速度约慢 10%~15%。

    段页式存储管理

    分页和分段的区别

    分页和分段系统相似之处:两者都采用离散分配方式,且都是通过地址映射机构实现地址变换。

    但在概念上两者完全不同,主要表现在下述三个方面:

    1. 页是信息的物理单位,段是信息的逻辑单位。
    2. 页的大小确定且又系统决定;段的长度不固定,决定于用户所编写的程序。
    3. 分页的用户程序地址空间是一维的,只需要一个记忆符就能够表示一个地址;分段的用户程序地址空间是二维的,既需要段名,又需要段内地址。

    段页式

    分页系统以页面作为内存分配的基本单位,能有效地提高内存利用率,而分段系统以段作为内存分配的基本单位,它能够更好地满足用户多方面的需要。

    段页式地址结构

    段页式地址结构由段号、段内页号及页内地址三部分所组成

    地址结构

    段页式系统的基本原理是分段和分页原理的结合,即先将用户程序分成若干个段,再把每个段分成若干个页,并为每一个段赋予一个段名。如下图展示了一个作业地址空间的结构。该作业有三个段:主程序段、子程序段和数据段;页面大小为 4 KB:

    段页式作业地址空间的结构

    在段页式系统中,为了实现从逻辑地址到物理地址的变换,系统中需要同时配置段表和页表。段表的内容与分段系统略有不同,它不再是内存始址和段长,而是页表始址和页表长度。下图展示出了利用段表和页表进行从用户地址空间到物理(内存)空间的映射。

    段表页表实现地址映射

    地址变换过程

    在段页式系统中,为了便于实现地址变换,须配置一个段表寄存器,其中存放段表始址和段长 TL。进行地址变换时,首先利用段号 S,将它与段长 TL 进行比较。若 S < TL,表示未越界,于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置,从中得到该段的页表始址,并利用逻辑地址中的段内页号 P 来获得对应页的页表项位置,从中读出该贝所在的物理块号 b,再利用块号 b 和页内地址来构成物理地址。

    段页式系统的地址变换机构

    在段页式系统中,为了获得一条指令或数据,须三次访问内存。第一次访问是访问内存中的段表,从中取得页表始址;第二次访问是访问内存中的页表,从中取出该页所在的物理块号,并将该块号与页内地址一起形成指令或数据的物理地址;第三次访问才是真正从第二次访问所得的地址中取出指令或数据。

    显然,这使访问内存的次数增加了近两倍。为了提高执行速度,在地址变换机构中增设一个高速缓冲寄存器。每次访问它时,都须同时利用段号和页号去检索高速缓存,若找到匹配的表项,便可从中得到相应页的物理块号,用来与页内地址一起形成物理地址:若未找到匹配表项,则仍需第三次访问内存。


    参考链接:

    1. 【操作系统 - 4】动态分区分配算法
    2. 程序的链接的三种方式
    3. 连续分配管理方式
    4. 深入理解操作系统之——分页式存储管理
    5. 《计算机操作系统》(第四版)
    分享

    redisread
    作者
    Victor
    Full Stack