文章前言连续分配单连续分配分区表达式分配固定分区分配动态分区分配可重定位分区分配离散分配分页多级页表(TLB )分段页表表达式Linux
前言
Linux内存管理|虚拟内存管理:虚拟内存空间、虚拟内存分配
Linux内存管理|物理内存、内存碎片整理程序、合作伙伴系统、SLAB分配器
前面的两个博客分别介绍了如何管理虚拟内存和物理内存,那么对于操作系统来说,它们是如何管理这两种关系的呢? 如何进行地址映射?
内存的分配方式有两种:
为每个连续分配:进程分配地址空间的连续内存空间。
连续的内存分配方法如下。
单连续分配分区表达式分配固定分区分配动态分区分配可重定位分区分配离散分配:可以将进程分散分配到多个不相邻的分区,程序可以
由于目前离散分配方式的使用较多,我们将对连续分配进行简要介绍,并对离散分配进行详细说明。
连续分配单连续分配使用该存储器分配方式,存储器区域分为系统区和用户区,系统区域仅提供给OS,系统区域外的用户区域为用户
特点:
仅适用于单道程序。 如果用户作业大于用户区域,或者无法运行的用户作业小于用户区域,则会浪费内存,导致单道程序的特点:
资源独占性:任何时候,内存中的程序都可以使用系统中的所有资源,不能与其他程序竞争。执行的顺序性:内存中只有一个程序。 每个程序都按顺序执行。 在完成一个程序的过程中,不能混入另一个程序中运行。结果的可再现性:如果运行环境和初始条件相同,则即使重复运行一个程序,得到的结果也始终相同。运行结果的无关性:程序的执行结果与程序的执行速度无关。 系统内工作串行处理,CPU、内存利用率低。 分区分配固定分区分配固定分区分配是可在多道程序上执行的最简单的存储管理方法。
多道程序:是指在计算机内存中同时存储多个相互独立的程序,在虚拟机管理程序的控制下使它们相互交织运行,两个或多个程序在计算机系统中从相同的开始到结束之间的状态当然,对于单个CPU系统来说,程序同时运行是一个宏观概念,他们已经开始运行,但微观上,任意给定时间在CPU上运行的程序只有一个。
基本原理:
将内存空间划分为几个固定大小的分区。 尺寸不同也没关系。 每个分区只能加载一个作业; 如果有可用分区,请选择大小合适的作业并将其加载到分区中。 工作结束后,释放分区。缺点:
程序的大小受分区大小限制。程序数受分区数限制。每个分区可能会发生内部碎片,从而导致内存浪费。 动态分区分配基本思想:
如果工作需要加载到内存中,请根据工作的大小对其进行分区。 每个分区容纳一个进程。可变分区的管理与组织方式:
表法:内存按是否中空分别存在于空闲分区表和已分配分区表。 管理很简单,但需要占用部分内存空间。
链表法:保持链的开头指针,每个空闲空间在开头地址记录两个数据。 此可用空间的大小,下一个可用空间的起始地址。动态分区分配的内存回收方式:上邻居空闲空间(F1 )合并、大小调整下邻居空闲空间(F2 )合并、大小调整、起始地址。 上、下邻的空闲区域(F1、F2 ) :合并,变更大小。 如果不相邻,则创建新的表条目。动态分配分区内存分配算法:
将3358www.Sina.com/可用分区排列为首次适应算法:,进行内存分配时,从低到高依次查找,分配第一个足够大的分区。 优点:优先分配低地址部分的空闲分区,确保高地址部分的缺点:低地址部分集中了很多小分区,很难使用。 首次适应地址顺序算法的改进版。 在按地址顺序配置循环链表和分配内存时,循环查找空闲分区,不从链的开头查找,而是从循环首次适应算法:查找。 优点:内存中空闲分区分布均匀,比首次自适应算法减少了查找空闲分区的开销; 缺点:缺少大的空闲分区。上次找到的空闲分区的下一个空闲分区空闲分区以大小最佳适应算法:配置队列,并从队列开头进行查找
找到第一个满足要求的空闲区时,则停止查找。 优点:找到的空闲分区最接近要求的大小;缺点:会产生非常小的碎片,难以利用。 最差适应算法: 空闲分区按大小递增排序构成队列,查找最大的空闲区。与上面三个同属 顺序搜索法 。 优点:剩余的分区空间最大;缺点:在空间利用率方面较差。 可重定位分区分配假设现在有这样一个情况,用户内存空间中有几个较小的空闲分区,但是现在有一个作业请求连续的内存空间,这几个较小的空闲分区任何一个都不能单独满足请求空间的大小。 现在一种可行的办法就是:移动内存,使所有空闲区域合并为一整块空闲区域。
这种通过移动内存中的作业位置,将原来分散的小分区拼接成一个大分区的思想就是 紧凑 。 说的直白一点,可重定位分区分配就是 动态分区分配+紧凑 。
动态重定位的实现:
作业装入内存后的所有地址都是相对地址,在程序将要执行的时候,才会将相对地址转换为物理地址。为了不影响指令执行的速度,系统中增设了一个 重定位寄存器(即段寄存器、基址寄存器) ,用它来存放程序(数据)在内存中的起始地址。
程序真正执行时访问的地址是 重定位寄存器中的地址+相对地址 。
离散分配 分段为了简化地址管理,所以将虚拟内存空间中的 虚拟内存 按照其逻辑划分为代码段、数据段、堆段、栈段几部分。编译、连接、加载过程都以段为单位。
段的特点:
地址结构:
虚拟地址是二维的:[jjdxte,段内位移] 。32位地址结构中, jjdxtes:16位表示,216 个段段内位移d:16位表示,每段最大长度是64KB。通过 段寄存器 中的 段表 ,将虚拟地址与物理地址进行映射。段表由三部分组成:
jjdxte:用于区别每个段。段基址(segment base):该段在物理内存中的首地址。axdm(segment limit ):记录该段的实际长度。因此虚拟地址与物理地址的转换方式如下:
根据虚拟地址中的jjdxte查询段表,得到对应的段的物理内存起始地址;物理内存起始地址加上段内偏移,即为其对应的物理地址。
分段存储方式解决了两个问题 —— 地址空间不隔离 和 程序运行的地址无法确定。但还存在 内存使用效率低 的问题。内存使用效率低主要是因为两个原因造成的:内存碎片 和 内存交换的效率低 。
内存碎片问题
例如我们有 1G 的物理内存,倘若我们运行了 512M 的程序A,接着运行了 128M 的程序B,128M 的程序C。剩余内存为 256M 。
倘若我们此时结束程序B,释放内存,此时总剩余空间为 384M 。
倘若我们此时需要运行 300M 的进程D,但是这时候就会因为剩余空间不连续,导致我们的程序无法运行,这也就是我们常说的 内存外碎片 问题。
那么如何解决这个问题呢?这就会使用到类似于 紧凑 的思想。先将程序C写入硬盘的 SWAP分区 (交换分区,用于内存和硬盘的空间交换)。紧接着再将其从硬盘中读取回来,让其紧挨着程序A的那块内存,这样就能保证后面的空闲内存都是连续的了。
内存交换效率低
由于分段对物理内存的映射是以 程序 为单位,按照其逻辑进行分段映射,如果我们的内存不足,那么被换入换出到硬盘中的都是整个程序,这样就必然会造成大量的磁盘访问操作,总所欢呼的网络,磁盘IO的速度特别慢,因此就会严重影响我们的访问速度。
而且,当一个程序在运行时,在某个时间段内,它只是 频繁地用到了一小部分数据 ,也就是说程序中的很多数据其实在一个时间段内都是不会被用到的。因此我们将整个程序装入内存其实是对内存的一种浪费。
分页总结一下,分段技术仍未解决的问题有:
虽然分段式存储方式不畏惧 内存外碎片,但将内存中的数据暂时写入到硬盘中,之后再重新写回来这样的换入换出操作在程序很大时是很废时间的。值得一提的是,两者都无法摆脱 内碎片 的桎梏。而且分段需要将程序全部装入内存,这就对程序的大小有了限制——不能超过剩余空闲内存的大小。而分页技术解决上述两个问题的方法是:
使用页为单位后,即使我们还是需要进行磁盘IO,但是由于我们交换的容量仅仅只有几个页,所以也不会花费过多的时间。分页技术下并不需要将程序整个装入内存。在建立了虚拟内存空间后并不会直接分配物理内存,而是在程序运行中需要访问物理内存的时候,再将其加载进内存中。所以如果在页表中查找不到时,此时就会由内核的 请求分页机制 产生 缺页中断 ,然后进入 内核态 中分配物理内存、更新进程页表,最后再返回用户态,恢复进程的运行。基本概念:
帧/物理块/页框(frame): 物理内存分为固定大小的块。页(page): 逻辑内存分为同样大小的块,在 Linux 中,一页是 4KB 。页表(page table): MMU(内存管理单元) 中的页面映射表,记录了 页 和 页框 的映射关系。
页表中不仅保存了页号,物理内存地址,还保留了该物理页的 访问权限 ,用以实现对页的访问控制。
在分页机制下,虚拟地址由 页号 以及 页内偏移 组成
因此在分页机制下,虚拟地址与物理地址的转换方式如下:
根据虚拟地址中的页号查询页表,获得对应的页的物理内存起始地址;物理内存起始地址加上页内偏移,即为其对应的物理地址。 多级页表在上面所介绍的 页表 有一个非常致命的缺点,就是空间占用大。
在 Linux 中,可以并发的执行多个进程,而每个进程都有其自己的虚拟内存空间,那么也自然都有自己独有的页表。在32位Linux系统下,我们的虚拟内存空间的大小为 4G ,而每页的大小为 4K ,这也就意味着我们至少有 220 个内存页,倘若每个页表项为 4Byte ,那么每个页表大小也至少为 4M 。
倘若我们此时并发了两百个进程,那么占用则高达 800M ,即使对于如今的操作系统而言,这个数字也是非常庞大的,因为并发数百个进程是非常常见的情况,更别提64位的操作系统,随着寻址范围的增加,页表将更为庞大。
为了解决这个问题,就引入了多级页表。
我们将 一级页表 再进行分页,分成 1024 个 二级页表 ,并且每个 二级页表 中存有 1024 个页表项,形成如下的 二级分页 的结构。
对于已分配的页表项,如果存在最近一定时间未访问的页表,在物理内存紧张的情况下,操作系统会将页面换出到硬盘,也就是说不会占用物理内存。
如果某个一级页表的页表项没有被用到,也就不需要创建这个页表项对应的二级页表了,即可以在需要时才创建二级页表。
如果一级页表所有表项都被用到,那么此时二级页表大小为 4M(1024 * 4K) ,假设我们只是用了一级页表的 20% 。
在这种情况下,页表所占用的物理内存就只有 4K(一级页表大小) + 20% * 4M(存在的二级页表) ,即 0.804M ,比起只用了二级页表的 4M (一级页表没有用到的表项不用创建对应的二级页表,因此此时存在的二级页表共 20% * 4M ,但单极页表时,二级页表必须建满 4M),大大的节约了内存。
而在64位系统中,两级页表是肯定不够用的,因此又演变成了四级目录:
全局页目录项 PGD上层页目录项 PUD中间页目录项 PMD页表项 PTE 快表(TLB)多级页表虽然解决了空间占用大的问题,但是由于其复杂化了地址的转换,因此也带来了 大量的时间开销 ,使得地址转换速度减慢。
解决这个问题最简单的方式就是降低查询页表的频率,那么如何实现呢?这时候就需要用到 缓存 的技术
对于热点资源,我们可以将其提前缓存下来,到以后使用时就可以直接到缓存中查找。对于操作系统来说,也是这么一个道理。
在操作系统中,这个缓存就是 CPU 中的 TLB ,也就是我们通常所说的 快表 。我们将 最常访问的几个页表项存储到 TLB 中 ,在之后进行寻址时, CPU 就会先到 TLB 中进行查找,如果没有找到,这时才会去查询页表。
段页式虽然分段和分页各有优缺点,但他们直接并不是对立的,所以如今大部分的内存管理方式,都是将分段与分页相结合,也就是我们常说的段页式。
它的原理非常简单,就是先对 虚拟内存空间进行分段管理,然后再对每一个段进行分页管理。 如下图:
所以此时的虚拟地址结构,就由 jjdxte、段内页号、页内偏移 所组成。此时对于每个进程来说,都会建立一个段表,而对于段表中的每一个段,又会再分别建立一个页表:
以此时的虚拟地址转换为物理地址,就需要以下三个步骤:
这种方法虽然增加了系统开销以及硬件成本,但是内存的利用率得到了巨大的提升。
Linux由于硬件问题的限制,Linux 内存主要采用的是页式内存管理,但同时也不可避免地涉及了段机制。
在往常的机制中,地址的转换流程如下:
但是在 Linux 中,并没有逻辑地址这一说(所有段起始地址相同),因为其将段机制进行了弱化,此时段只用于进行访问控制以及内存保护。
Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间(32 位环境下),也就是所有的段的起始地址都是一样的。
这意味着,Linux 系统中的代码,包括操作系统本身的代码和应用程序代码,所面对的地址空间都是线性地址空间(虚拟地址),这种做法相当于屏蔽了处理器中的逻辑地址概念,段只被用于访问控制和内存保护。