操作系统之内存管理

发表于:2018-4-09 09:57

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:芥末无疆sss    来源:51testing软件测试网采编

分享:
  内存管理
  包括内存管理和虚拟内存管理
  内存管理包括内存管理概念、交换与覆盖、连续分配管理方式和非连续分配管理方式(分页管理方式、分段管理方式、段页式管理方式)。
  虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。
  3.1 内存管理的概念
  内存管理(Memory Management)是操作系统设计中最重要和最复杂的内容之一。虽然计算机硬件一直在飞速发展,内存容量也在不断增长,但是仍然不可能将所有用户进程和系统所需要的全部程序和数据放入主存中,所以操作系统必须将内存空间进行合理地划分和有效地动态分配。操作系统对内存的划分和动态分配,就是内存管理的概念。
  有效的内存管理在多道程序设计中非常重要,不仅方便用户使用存储器、提高内存利用率,还可以通过虚拟技术从逻辑上扩充存储器。
  内存管理的功能有:
  内存空间的分配与回收:由操作系统完成主存储器空间的分配和管理,使程序员摆脱存储分配的麻烦,提高编程效率。
  地址转换:在多道程序环境下,程序中的逻辑地址与内存中的物理地址不可能一致,因此存储管理必须提供地址变换功能,把逻辑地址转换成相应的物理地址。
  内存空间的扩充:利用虚拟存储技术或自动覆盖技术,从逻辑上扩充内存。
  存储保护:保证各道作业在各自的存储空间内运行,.互不干扰。
  在进行具体的内存管理之前,需要了解进程运行的基本原理和要求。
  程序装入和链接
  创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序,通常需要以下几个步骤:
  编译:由编译程序将用户源代码编译成若干个目标模块。
  链接:由链接程序将编译后形成的一组目标模块,以及所需库函数链接在一起,形成一个完整的装入模块。
  装入:由装入程序将装入模块装入内存运行。
  这三步过程如图3-1所示。
  image
  图3-1 对用户程序的处理步骤
  程序的链接有以下三种方式:
  静态链接:在程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的可执行程序,以后不再拆开。
  装入时动态链接:将用户源程序编译后所得到的一组目标模块,在装入内存时,釆用边装入边链接的链接方式。
  运行时动态链接:对某些目标模块的链接,是在程序执行中需要该目标模块时,才对它进行的链接。其优点是便于修改和更新,便于实现对目标模块的共享。
  内存的装入模块在装入内存时,同样有以下三种方式:
  绝对装入。在编译时,如果知道程序将驻留在内存的某个位置,编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址,将程序和数据装入内存。由于程序中的逻辑地址与实际内存地址完全相同,故不需对程序和数据的地址进行修改。
  绝对装入方式只适用于单道程序环境。另外,程序中所使用的绝对地址,可在编译或汇编时给出,也可由程序员直接赋予。而通常情况下在程序中釆用的是符号地址,编译或汇编时再转换为绝对地址。
  可重定位装入。在多道程序环境下,多个目标模块的起始地址通常都是从0开始,程序中的其他地址都是相对于起始地址的,此时应釆用可重定位装入方式。根据内存的当前情况,将装入模块装入到内存的适当位置。装入时对目标程序中指令和数据的修改过程称为重定位,地址变换通常是在装入时一次完成的,所以又称为静态重定位,如图3-2(a) 所示。
  image
  图3-2 重定向类型
  静态重定位的特点是在一个作业装入内存时,必须分配其要求的全部内存空间,如果没有足够的内存,就不能装入该作业。此外,作业一旦进入内存后,在整个运行期间不能在内存中移动,也不能再申请内存空间。
  动态运行时装入,也称为动态重定位,程序在内存中如果发生移动,就需要釆用动态的装入方式。装入程序在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行。因此,装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持,如图3-2(b)所示。
  动态重定位的特点是可以将程序分配到不连续的存储区中;在程序运行之前可以只装入它的部分代码即可投入运行,然后在程序运行期间,根据需要动态申请分配内存;便于程序段的共享,可以向用户提供一个比存储空间大得多的地址空间。
  逻辑地址空间与物理地址空间
  编译后,每个目标模块都是从0号单元开始编址,称为该目标模块的相对地址(或逻辑地址)。
  当链接程序将各个模块链接成一个完整的可执行目标程序时,链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。用户程序和程序员只需知道逻辑地址,而内存管理的具体机制则是完全透明的,它们只有系统编程人员才会涉及。不同进程可以有相同的逻辑地址,因为这些相同的逻辑地址可以映射到主存的不同位置。
  物理地址空间是指内存中物理单元的集合,它是地址转换的最终地址,进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时,必须通过地址转换将逻辑地址转换成物理地址,这个过程称为地址重定位。
  内存保护
  内存分配前,需要保护操作系统不受用户进程的影响,同时保护用户进程不受其他用户进程的影响。通过釆用重定位寄存器和界地址寄存器来实现这种保护。重定位寄存器含最小的物理地址值,界地址寄存器含逻辑地址值。每个逻辑地址值必须小于界地址寄存器;内存管理机构动态地将逻辑地址与界地址寄存器进行比较,如果未发生地址越界,则加上重定位寄存器的值后映射成物理地址,再送交内存单元,如图3-3所示。
  当CPU调度程序选择进程执行时,派遣程序会初始化重定位寄存器和界地址寄存器。每一个逻辑地址都需要与这两个寄存器进行核对,以保证操作系统和其他用户程序及数据不被该进程的运行所影响。
  image
  图3-3 重定位和界地址寄存器的硬件支持
  3.2 内存覆盖与内存交换
  覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法。
  内存覆盖
  早期的计算机系统中,主存容量很小,虽然主存中仅存放一道用户程序,但是存储空间放不下用户进程的现象也经常发生,这一矛盾可以用覆盖技术来解决。
  覆盖的基本思想是:由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序),因此可以把用户空间分成一个固定区和若干个覆盖区。将经常活跃的部分放在固定区,其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区,其他段放在外存中,在需要调用前,系统再将其调入覆盖区,替换覆盖区中原有的段。
  覆盖技术的特点是打破了必须将一个进程的全部信息装入主存后才能运行的限制,但当同时运行程序的代码量大于主存时仍不能运行。
  内存交换
  交换(对换)的基本思想是,把处于等待状态(或在CPU调度原则下被剥夺运行权利)的程序从内存移到辅存,把内存空间腾出来,这一过程又叫换出;把准备好竞争CPU运行的程序从辅存移到内存,这一过程又称为换入。中级调度就是釆用交换技术。
  例如,有一个CPU釆用时间片轮转调度算法的多道程序环境。时间片到,内存管理器将刚刚执行过的进程换出,将另一进程换入到刚刚释放的内存空间中。同时,CPU调度器可以将时间片分配给其他已在内存中的进程。每个进程用完时间片都与另一进程交换。理想情况下,内存管理器的交换过程速度足够快,总有进程在内存中可以执行。
  有关交换需要注意以下几个问题:
  交换需要备份存储,通常是快速磁盘。它必须足够大,并且提供对这些内存映像的直接访问。
  为了有效使用CPU,需要每个进程的执行时间比交换时间长,而影响交换时间的主要是转移时间。转移时间与所交换的内存空间成正比。
  如果换出进程,必须确保该进程是完全处于空闲状态。
  交换空间通常作为磁盘的一整块,且独立于文件系统,因此使用就可能很快。
  交换通常在有许多进程运行且内存空间吃紧时开始启动,而系统负荷降低就暂停。
  普通的交换使用不多,但交换策略的某些变种在许多系统中(如UNIX系统)仍发挥作用。
  交换技术主要是在不同进程(或作业)之间进行,而覆盖则用于同一个程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构,使得其对用户和程序员不透明,所以对于主存无法存放用户程序的矛盾,现代操作系统是通过虚拟内存技术来解决的,覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力。
  3.3 内存连续分配管理方式
  连续分配方式,是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。
  单一连续分配
  内存在此方式下分为系统区和用户区,系统区仅提供给操作系统使用,通常在低地址部分;用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。
  这种方式的优点是简单、无外部碎片,可以釆用覆盖技术,不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中,有内部碎片,存储器的利用率极低。
  固定分区分配
  固定分区分配是最简单的一种多道程序存储管理方式,它将用户内存空间划分为若干个固定大小的区域,每个分区只装入一道作业。当有空闲分区时,便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区,如此循环。
  image
  图3-4 固定分区分配的两种方法
  固定分区分配在划分分区时,有两种不同的方法,如图3-4所示。
  分区大小相等:用于利用一台计算机去控制多个相同对象的场合,缺乏灵活性。
  分区大小不等:划分为含有多个较小的分区、适量的中等分区及少量的大分区。
  为便于内存分配,通常将分区按大小排队,并为之建立一张分区说明表,其中各表项包括每个分区的起始地址、大小及状态(是否已分配),如图3-5(a)所示。当有用户程序要装入时,便检索该表,以找到合适的分区给予分配并将其状态置为”已分配”;未找到合适分区则拒绝为该用户程序分配内存。存储空间的分配情况如图3-5(b)所示。
  这种分区方式存在两个问题:一是程序可能太大而放不进任何一个分区中,这时用户不得不使用覆盖技术来使用内存空间;二是主存利用率低,当程序小于固定分区大小时,也占用了一个完整的内存分区空间,这样分区内部有空间浪费,这种现象称为内部碎片。
  固定分区是可用于多道程序设计最简单的存储分配,无外部碎片,但不能实现多进程共享一个主存区,所以存储空间利用率低。固定分区分配很少用于现在通用的操作系统中,但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用。
  image
  图3-5 固定分区说明表和内存分配情况
  动态分区分配
  动态分区分配又称为可变分区分配,是一种动态划分内存的分区方法。这种分区方法不预先将内存划分,而是在进程装入内存时,根据进程的大小动态地建立分区,并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。
  image
  图3-6动态分区
  如图3-6所示,系统有64MB内存空间,其中低8MB固定分配给操作系统,其余为用户可用内存。开始时装入前三个进程,在它们分别分配到所需空间后,内存只剩下4MB,进程4无法装入。在某个时刻,内存中没有一个就绪进程,CPU出现空闲,操作系统就换出进程2,换入进程4。由于进程4比进程2小,这样在主存中就产生了一个6MB的内存块。之后CPU又出现空闲,而主存无法容纳进程2,操作系统就换出进程1,换入进程2。
  动态分区在开始分配时是很好的,但是之后会导致内存中出现许多小的内存块。随着时间的推移,内存中会产生越来越多的碎片(图3-6中最后的4MB和中间的6MB,且随着进程的换入/换出,很可能会出现更多更小的内存块),内存的利用率随之下降。
  这些小的内存块称为外部碎片,指在所有分区外的存储空间会变成越来越多的碎片,这与固定分区中的内部碎片正好相对。克服外部碎片可以通过紧凑(Compaction)技术来解决,就是操作系统不时地对进程进行移动和整理。但是这需要动态重定位寄存器的支持,且相对费时。紧凑的过程实际上类似于Windows系统中的磁盘整理程序,只不过后者是对外存空间的紧凑。
  在进程装入或换入主存时,如果内存中有多个足够大的空闲块,操作系统必须确定分配哪个内存块给进程使用,这就是动态分区的分配策略,考虑以下几种算法:
  首次适应(First Fit)算法:空闲分区以地址递增的次序链接。分配内存时顺序查找,找到大小能满足要求的第一个空闲分区。
  最佳适应(Best Fit)算法:空闲分区按容量递增形成分区链,找到第一个能满足要求的空闲分区。
  最坏适应(Worst Fit)算法:又称最大适应(Largest Fit)算法,空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区,也就是挑选出最大的分区。
  邻近适应(Next Fit)算法:又称循环首次适应算法,由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。
  在这几种方法中,首次适应算法不仅是最简单的,而且通常也是最好和最快的。在UNIX 系统的最初版本中,就是使用首次适应算法为进程分配内存空间,其中使用数组的数据结构 (而非链表)来实现。不过,首次适应算法会使得内存的低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。
  邻近适应算法试图解决这个问题,但实际上,它常常会导致在内存的末尾分配空间(因为在一遍扫描中,内存前面部分使用后再释放时,不会参与分配),分裂成小碎片。它通常比首次适应算法的结果要差。
  最佳适应算法虽然称为“最佳”,但是性能通常很差,因为每次最佳的分配会留下很小的难以利用的内存块,它会产生最多的外部碎片。
  最坏适应算法与最佳适应算法相反,选择最大的可用块,这看起来最不容易产生碎片,但是却把最大的连续内存划分开,会很快导致没有可用的大的内存块,因此性能也非常差。
  Kunth和Shore分别就前三种方法对内存空间的利用情况做了模拟实验,结果表明:
  首次适应算法可能比最佳适应法效果好,而它们两者一定比最大适应法效果好。另外注意,在算法实现时,分配操作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找,而首次适应法和邻近适应法只需要简单查找;回收操作中,当回收的块与原来的空闲块相邻时(有三种相邻的情况,比较复杂),需要将这些块合并。在算法实现时,使用数组或链表进行管理。除了内存的利用率,这里的算法开销也是操作系统设计需要考虑的一个因素。
  表3-1三种内存分区管理方式的比较
  以上三种内存分区管理方法有一共同特点,即用户进程(或作业)在主存中都是连续存放的。这里对它们进行比较和总结,见表3-1。
  3.4 内存非连续分配管理方式
  非连续分配允许一个程序分散地装入到不相邻的内存分区中,根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。
  分页存储管理方式中,又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。下面介绍基本分页存储管理方式。
  基本分页存储管理方式
  固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生,这就引入了分页的思想:把主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请主存中的块空间。
  分页的方法从形式上看,像分区相等的固定分区技术,分页管理不会产生外部碎片。但它又有本质的不同点:块的大小相对分区要小很多,而且进程也按照块进行划分,进程运行时按块申请主存可用空间并执行。这样,进程只会在为最后一个不完整的块申请一个主存块空间时,才产生主存碎片,所以尽管会产生内部碎片,但是这种碎片相对于进程来说也是很小的,每个进程平均只产生半个块大小的内部碎片(也称页内碎片)。
  1) 分页存储的几个基本概念
  ①页面和页面大小。进程中的块称为页(Page),内存中的块称为页框(Page Frame,或页帧)。外存也以同样的单位进行划分,直接称为块(Block)。进程在执行时需要申请主存空间,就是要为每个页面分配主存中的可用页框,这就产生了页和页框的一一对应。
  为方便地址转换,页面大小应是2的整数幂。同时页面大小应该适中,如果页面太小,会使进程的页面数过多,这样页表就过长,占用大量内存,而且也会增加硬件地址转换的开销,降低页面换入/换出的效率;页面过大又会使页内碎片增大,降低内存的利用率。所以页面的大小应该适中,考虑到耷间效率和时间效率的权衡。
  ②地址结构。分页存储管理的逻辑地址结构如图3-7所示。
  image
  图3-7 分页存储管理的地址结构
  地址结构包含两部分:前一部分为页号P,后一部分为页内偏移量W。地址长度为32 位,其中011位为页内地址,即每页大小为4KB;1231位为页号,地址空间最多允许有2^20页。
  ③页表。为了便于在内存中找到进程的每个页面所对应的物理块,系统为每个进程建立一张页表,记录页面在内存中对应的物理块号,页表一般存放在内存中。
  在配置了页表后,进程执行时,通过查找该表,即可找到每页在内存中的物理块号。可见,页表的作用是实现从页号到物理块号的地址映射,如图3-8所示。
  image
  图3-8 页表的作用




上文内容不用于商业目的,如涉及知识产权问题,请权利人联系博为峰小编(021-64471599-8017),我们将立即处理。
21/212>
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号