操作系统【七】

四、存储器管理


【操作系统】存储器管理(四)

存储器管理功能有:

  • 内存分配:为每道程序分配内存空间,提高存储器的利用率,允许正在运行的程序申请附加的内存空间;
  • 存储保护:确保每道用户程序都只在自己的内存空间中运行,彼此互不干扰;
  • 地址映射(变换):进程的逻辑地址到内存物理地址的映射。
  • 内存扩充:用虚拟存储技术解决内存容量不足的问题;

1、存储器的层次结构

  • 存储器的层次结构(缓存、内存、外存)

    • 主存储器与寄存器

      • 主存储器:用于保存进程运行时的程序和数据。
      • 寄存器:寄存器访问速度最快,与CPU协调工作。
    • 高速缓存与磁盘缓存

      • 高速缓存:CPU对高速缓存的访问,其速度比访问主存快比访问寄存器慢
      • 磁盘缓存:内存中一块存储区,对应于某固定磁盘,临时存储磁盘数据(如,数据预取)。

磁盘的IO速度远低于对主存的访问速度,因此将频繁使用的一部分磁盘数据和信息暂时存放在磁盘缓存中,可减少访问磁盘的次数,磁盘缓存本身并不是一种实际存在的存储介质,它依托于固定磁盘,提供对主存储器空间的扩充,即利用主存中的存储空间,来暂存从磁盘中读出或写入的信息,主存可以看做是辅存的高速缓存,因为,辅存中的数据必须复制到主存方能使用,反之,数据也必须先存在主存中,才能输出到辅存。

2、程序的装入和链接

为了使程序能够运行,必须先为之创建进程,而创建进程的第一件事,就是将程序和数据装入内存,如何将一个用户源程序变为一个可在内存中执行的程序,通常要经过如下几步:

  • 首先是编译(由编译程序将用户源代码编译成若干个目标模块)

  • 其次是链接(由链接程序将编译后形成的一组目标模块,以及它们所需要的库函数链接在一起,形成一个完整的装入模块)

  • 最后是装入(由装入程序将装入模块装入内存)

一些基本概念

  • 逻辑地址: 用户的程序经过汇编或编译后形成目标代码,目标代码通常采用相对地址的形式,其首地址为0,其余指令中的地址都相对于首地址而编址。
  • 物理地址:内存中存储单元的地址,可直接寻址
  • 名空间:一个用高级语言编制源程序,我们说它存在于由程序员建立的符号名字空间
  • 地址空间:程序用来访问信息所用地址单元的集合,是逻辑(相对)地址的集合,由编译程序生成。
  • 存储空间:主存中物理单元的集合
  • 外部碎片指的是尚未分配出去、由于太小而无法分配出去的内存空间
  • 内部碎片指的是已经分配出去、但没有完全得到利用的内存空间

(1)程序装入的方式

在装入一个模块到内存时,有绝对装入方式,可重定位装入方式,动态运行时装入方式。

绝对装入方式

如果在编译时知道程序驻留在内存的什么位置,那么,==编译程序将产生绝对地址的目标代码==,绝对装入方式按照装入模块中的地址,将程序和数据装入内存,装入模块被装入内存后,由于程序中的逻辑地址与实际内存地址完全相同,故不需要对程序和数据的地址进行修改。

可重定位装入方式

由于绝对装入方式只能将目标模块装入到内存中事先指定的位置,在多道程序环境下,编译程序不可能事先知道所编译的目标模块应放在内存的何处,因此,绝对装入方式只适用于单道程序环境,在多道程序环境下,所得到的目标模块的起始地址通常都是以0开始的,程序中的其他地址也都是相对于起始地址计算的,此时应采用可重定位装入方式,根据内存的当前情况,将装入模块装入到内存的适当位置。该方式会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同,需要对数据地址和指令地址进行修改,通常把再装入时对目标程序中指令和数据的修改过程称为重定位,又因为地址变换通常是在装入时(第三步)一次完成的,以后不再变化,故称为静态重定位

第一步第二步,只是绝地地址,第三步进行转换映射。

动态运行时装入方式

可重定位装入方式允许将装入模块装入到内存中任何允许的位置,故可用多道程序环境,但这种方式并不允许程序运行时在内存中移动位置,因为,程序在内存中的移动,意味着它的物理位置发生了变化,这就必须对程序和数据的地址进行修改后方能运行。然而,在运行过程中它在内存中的位置可能经常要改变,此时就应该采用动态运行时装入方式。动态运行时的装入程序在把装入程序装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行因此,装入内存后的所有地址都仍是相对地址,为了使地址转换不影响指令的执行速度,需要重定位寄存器的支持。

重定位寄存器用于记录和更新装入模块当前的物理起始地址,逻辑地址只需要和这个物理起始地址相加即可得到物理地址。

(2)程序链接的方式

源程序经过编译后,可得到一组目标模块,再利用链接程序把这组目标模块链接,形成装入模块,根据链接时间的不同,可把链接分为

  • 静态链接(在程序运行之前,先将各目标模块及他们所需的库函数,链接成一个完整的装配模块,以后不再拆开)

  • 装入时动态链接(将用户源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的链接方式)

  • 运行时动态链接(对某些目标模块的链接,是在程序执行中需要盖模块时,才对它进行链接)。

静态链接

在将目标模块装配成一个装入模块时,需要对相对地址进行修改(由于编译程序产生的所有目标模块中,使用的都是相对地址,其起始地址都为0,每个模块中的地址都是相对于起始地址计算的)。也需要变换外部调用符号(将每个模块中所用的外部调用符号都变换为相对地址),这种先进行链接所形成的一个完整的装入模块又称为可执行文件,通常都不再拆开它,要运行时可直接将它装入内存,这种事先进行链接,以后不再拆开的链接方式,称为静态链接方式。

装入时动态链接

用户源程序经编译后所得是目标模块,是在装入内存时边装入边链接的,即在装入一个目标模块时,若发生一个外部模块调用事件,将引起装入程序去找出相应的外部目标模块,并将它装入内存,装入时动态链接有如下优点

  • 便于修改和更新(各目标模块是分开的存放的,所以要修改或更新各目标模块非常容易),

  • 便于实现对目标模块的共享(很容易将一个目标模块链接到几个应用模块上,实现多个应用程序对该模块的共享)

运行时动态链接

将某些模块的链接推迟到程序执行时才进行链接,即在执行过程中,当发现一个被调用模块尚未装入内存时,立即由OS去找到该模块并将之装入内存,把它链接到调用者模块上,凡在执行过程中未被调用到的模块,都不会被调入内存和被链接到装入模块上,这样不仅加快程序的装入过程,同时也节省了大量的内存空间。

3、连续分配方式

连续分配方式,是指为一个用户程序分配一个连续的内存空间.

可以将连续分配方式分为

  1. 单一连续分配
  2. 固定分区分配
  3. 动态分区分配
  4. 动态重定位分区分配

(1)单一连续分配

单一连续分配。这是一种最简单的存储管理方式,但只能在单用户、单任务的操作系统中,将内存分为系统区和用户区,系统区供OS使用,通常放在内存的低地址,用户区是指除系统区以外的全部内存空间,提供给用户使用。

(2)固定分区分配

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

对于内存的用户空间的划分,有如下两种方法。

  • 分区大小相等,即所有的内存分区大小相等。缺点是缺乏灵活性,即当程序太小时,会造成内存资源的浪费,程序太大时,一个分区由不足以装入该程序,只是该程序无法运行。

  • 分区大小不等,把内存区划分成含有多个较小的分区、适量中等分配和少量大分区,这样,便可根据程序的大小为之分配适当的分区。

为了便于内存分配,将分区按大小进行排队,并为之简历一张分区使用表,其中各表项包括每个分区的起始地址、大小、状态(是否已分配),当有一个程序需要装入时,由内存分配程序检索该表,从中找出一个能满足要求的,尚未分配的分区,将之分配给该程序,然后将该表项中的状态设置为已分配,若未找到大小足够的分区,则拒绝为该用户分配内存。

(图中起止改为起址,因为有大小了只需要起始地址就可以。)

(3)动态分区分配

动态分区存储管理不是预先把主存储器中的用户区域划成分区,而是在作业要求装入主存储器时,根据作业需要的主存空间大小和当时主存空间使用情况来决定是否为作业分配一个分区。在实现可变分区分配时,将涉及到分区分配中所用的数据结构、分区分配算法、分区的分配和回收等。

操作系统只管理空闲的,分配出去了就不再管理,就相当于没有这块内存

注意会合并连续的空闲分区。

①分区分配中的数据结构

为了实现分区分配,胸中必须配置相应的数据结构,用来描述空闲分区和已分配分区的情况,为分配提供依据,常用的数据结构有如下两种形式:

  • 空闲分区表(在系统中设置一张空闲分区表,用于记录每个空闲分区的情况,每个空闲分区占一个表目,表目中包括分区序号、分区始址、分区大小等,在前面已有介绍)

  • 空闲分区链(为了实现对空闲分区的分配和链接,在每个分区的起始部分,设置一些用于控制分区分配的信息,以及用于链接各分区所用的向前指针;在分区尾部设置一向后指针,这样,可以将空闲分区链接成一个双向链),为了检索方便,在分区尾部重复设置状态为和分区大小表目,当分区被分配出去以后,把状态为从0改成1,此时前后指针都失去意义(已经不再空闲链表中)。

分区分配算法
I.基于顺序搜索的动态分区分配算法
  1. 首次适应算法(First Fit)

以空闲分区链为例进行说明,FF算法要求空闲分区链以地址递增的次序链接,在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止,然后再按照作业的大小,从该分区划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中,若从链首直至链尾都不能找到一个能满足要求的分区,则此次内存分配失败,返回。

优点:优先利用内存低址部分的内存空间

缺点:低址部分不断划分,产生小碎片;每次查找从低址部分开始,增加了查找的开销

  1. 循环首次适应算法(Next Fit)

由首次适应算法演变而来,在未进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划分出一块与请求大小相等的内存空间分配给作业。进行空闲分区分配时,会采用循环查找方式,即如果最后一个(链尾)空闲分区的大小仍不能满足要求,则返回第一个空闲分区。

优点:使内存空闲分区分布均匀,减少查找的开销

缺点:缺乏大的空闲分区

  1. 最佳适应算法(Best Fit)

该算法总是能把满足要求、又是最小的空闲分区分配给作业,避免大材小用,为了加速寻找,该算法要求把所有的空闲分区按其容量以从小到大的顺序形成一个空闲分区链,这样,第一次就能找到满足要求的空闲区,必然是最佳的,孤立地看,最佳适应算法似乎是最佳的,然而宏观上却不一定,因为每次分配后所切割下来的剩余部分总是最小的,会留下很多难以使用的小空闲区。

缺点:产生许多难以利用的小空闲区(内存零头,内存碎片)

  1. 最坏适应算法(Worst Fit)

所谓“最坏”是指每次为作业分配内存时, 要扫描整个空闲分区表或链表总是挑选一个 最大的空闲分区分配给作业。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链,查找时只要看第一个分区是否满足要求。

优点:产生碎片的几率最小

缺点:使存储器缺乏大的存储空间 。

总结

==由于动态分区分配不是事先划分好区域,而是“按需分配”,所以不会出现区域划分出去后无法完全得到利用的情况,也即不会产生内部碎片;但是可能出现内存空间太小而无法被分配出去的情况,也即可能产生外部碎片。==

II.基于索引搜索的动态分区分配算法

1.快速适应算法(分类搜索法) (Quick Fit)

该算法又称为分类搜索法,是空闲分区容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,这些,系统中存在多个空闲分区链表,同时在内存中设立一张管理索引表,该表的每一项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。该算法的优点是查找效率高,仅需根据进程的长度,寻找到能容纳它的最小空闲区链表,并取下第一块进行分配即可。该算法在进行空闲分区分配时,不会对任何分区产生分割,所以能保留大的分区,满足对大空间的需求,也不会产生内存碎片。但是在分区归还主存时算法复杂,系统开销大。

优点:查找效率高,根据进程的长度查找,不分割分区,因而不会产生新的碎片

缺点:1、分区归还存储器时算法复杂,2、会造成空间的浪费。

是典型的以空间换时间的做法。

2.伙伴系统(buddy system)

伙伴系统(buddy system) 是Linux Kernel 进行物理内存页管理的一个子系统

伙伴系统的特点:无论是占用块或空闲块,其大小均为2的k次幂(k为某个正整数)。

伙伴:是指由同一个大的空闲块分裂成的两个大小相等的存储区,这两个由同一大块分裂出来的小块就称之“互为伙伴”。

伙伴系统规定,无论已分配分区还是空闲分区,其大小均为2的k次幂,k为整数,1<= k <= m,其中,2^1^表示分配的最小分区的大小,2^m^表示分配的最大分区的大小,通常2^m^是整个可分配内存的大小。假设系统开始时的初始容量为2^m^个字,由于不断切分,可能会形成若干个不连续的空闲分区,将这些空闲分区根据分区的大小进行分类,对于每一类具有相同大小的所有空闲分区,单独设立一个空闲分区双向链表。这样,不同大小的空闲分区形成了k个空闲分区链表。

当需要为进程分配一个长度为n的存储空间时,首先计算一个i值,使2^i^-1 < n <= 2^i^,然后,在空闲分区大小为2^i^的空闲分区链表中查找,若找到,即把该空闲分区分配给进程,否则,表明2^i^的空闲分区已经耗尽,在大小为2^i+1^的空闲分区链表中查找,若存在,则将该空闲分区分为两个大小为2^i^的分区,一个用于分配,一个加入到大小为2^i^的空闲分区链表中,若还是不存在,则继续在大小为2^i^+2的空闲分区链表中查找,若存在,则将空闲分区进行两次分割,一次分割为两个大小为2^i^+1的空闲分区,一个加入到大小为2^i^+1的空闲分区链表中,另外一个继续进行分割,分成两个大小2^i^的空闲块,一个用于分配,另外一个加入到大小为2^i^的空闲分区链表中,以此类推。在最坏的情况下,可能需要对2^k^的空闲分区进行k此分割才能得到所需分区。

当回收空闲分区时,也需要经过多次合并,如回收大小为2^i^的空闲分区时,若事先已经存在2^i^的空闲分区,则应将其与伙伴分区合并为一个大小为2^i^+1的空闲分区,若事先已存在2^i^+1的空闲分区,则再次进行合并,合并为2^i^+2的分区,以此类推。

为了更直观地理解,这里用一个例子来说明。

假设系统总的内存为 512 kb,现有进程活动如下:

  • 进程 A 请求 100kb,进程 B 请求 50kb,进程 C 请求 100kb
  • 进程 A 释放 100kb
  • 进程 D 请求 20kb
  • 进程 D 释放 20kb
  • 进程 B 释放 50kb

按照伙伴系统的算法,内存的分配和回收是怎么进行的呢?

首先,一开始肯定是整片空的内存空间:

进程 A 请求 100kb,因为 64<100<128,即 2^6^<100<2^7^,所以寻找是否有 2^7^=128 的空闲分区,当然是没有的(目前只有 512kb),所以寻找是否有 2^8^=256 的空闲分区,也没有,所以寻找是否有 2^9^=512 的空闲分区,找到了,此时就把 512kb 一分为二:

一半的 256kb 加入到对应的空闲分区链表,一半的 256kb 用于分配,对这一半继续一分为二:

一半的 128kb 加入到对应的空闲分区链表,一半的 128kb 用于分配,这一半对进程 A 来说足够了,于是占用它:

进程 B 请求 50kb,因为 32<50<64,即 2^5^<100<2^6^,所以寻找是否有 2^6^=64 的空闲分区,当然是没有的,所以寻找是否有 2^7^=128,找到了,此时就把 128kb 一分为二:

一半的 64kb 加入到对应的空闲分区链表,一半的 64kb 用于分配,这一半对进程 B 来说足够了,于是占用它:

进程 C 请求 100kb,因为 64<100<128,即 2^6^<100<2^7^,所以寻找是否有 2^7^=128 的空闲分区,当然是没有的,所以寻找是否有 2^8^=256 的空闲分区,找到了,此时就把 256kb 一分为二:

一半的 128kb 加入到对应的空闲分区链表,一半的 128kb 用于分配,这一半对进程 C 来说足够了,于是占用它:

进程 A 释放 100kb:

进程 D 请求 20kb,因为 16<20<32,即 2^4^<100<2^5^,所以寻找是否有 2^5^=32 的空闲分区,当然是没有的,所以寻找是否有 2^6^=64 的空闲分区,找到了,此时就把 64kb 一分为二:

一半的 32kb 加入到对应的空闲分区链表,一半的 32kb 用于分配,这一半对进程 D 来说足够了,于是占用它:

进程 D 释放 20kb,回收 32kb,由于事先已经有一个 32kb,所以此时两个互为伙伴的 32kb 进行合并:

进程 B 释放 50kb,回收 64kb,由于事先已经有一个 64kb,所以此时两个互为伙伴的 64kb 进行合并,形成 128kb,由于事先已经有一个 128kb,所以此时两个互为伙伴的 128kb 进行合并,形成 256kb:

回收空闲块时,首先判别其伙伴是否为空闲块,

若否,则只要将释放的空闲块简单插入在相应子表中即可;

若是,则需在相应子表中找到其伙伴并删除之,然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复,直到归并所得空闲块的伙伴不是空闲块时,再插入到相应的子表中去。

最后补充一个计算伙伴地址的方法:

对于给定的内存块,若它的大小为 2^k^,起始地址为 x,那么它的伙伴地址:

  • 如果 x/2^k 为奇数,则伙伴地址为 x - 2^k
  • 如果 x/2^k 为偶数,则伙伴地址为 x + 2^k

与前面所述的多种方法相比较,由于该算法在回收空闲分区时,需要对空闲分区进行合并,所以其时间性能比前面所述的分类搜索算法差,但比顺序搜索算法好,而其空间性能则远优于前面所述的分类搜索法,比顺序搜索法略差。

3.哈希算法

前面的两种方法(快速适应和伙伴系统)都是将空闲分区按照大小进行分类,并为每一类建立一个独立的空闲分区链表,再用一个总的索引表进行记录。不过,如果分类过多,则索引表的表项也会过多,这时候搜索索引表的时间开销就会比较大。

因此,哈希算法选择建立一张哈希表(而不是普通的索引表),这张哈希表以空闲分区大小作为关键字,每次需要进行分配的时候,会根据所需空闲分区的大小,通过哈希函数快速计算得到该空闲分区在表中的位置,从而得到对应的空闲分区链表。

③分区分配操作
I.内存分配

利用某种分配算法,从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size,表中每个空闲分区的大小表示为m.size,若m.size- u.size≤size(规定的不再切割的分区大小),将整个分区分配给请求者,否则从分区中按请求的大小划出一块内存空间分配出去,余下部分留在空闲链(表)中,将分配区首址返回给调用者。

II.内存回收

当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时会出现如下四种情况之一:

  • 回收分区与插入点的前一个空闲区F1相邻接,此时不必为回收区分配新表项,只需将回收区与F1合并,修改F1的表项的分区大小
  • 回收分区与插入点的后以空闲分区F2相邻接,将回收区与F2合并,修改F2的表项的首址、分区大小
  • 回收区同时与插入点的前、后两个分区邻接,此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和。
  • 回收区既不与F1邻接,也不与F2邻接,这时为回收区单独建立一个新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置。

(4)动态可重定位分区分配

到目前为止,我们所讲的都是连续分配的方式,也就是说,为某个进程分配的必须是一块连续的空间 —— 若多个空闲分区不是相邻的,那么即便它们的大小相加后,已经足以满足进程的需求,也无济于事。为此,可以采用紧凑技术解决这个问题。紧凑技术可以把内存中各个进程进行移动,使得它们都相邻,从而把原先分开的各个空闲分区合并在一起,带来了更大的、可以充分利用的空闲分区:

在每次紧凑之后,都必须对移动了的数据和程序进行重定向

  • 假定我们先前采用的是静态重定位装入方式,那么在模块装入内存的时候,就已经把逻辑地址转换为物理地址了,就会导致在这里需要再进行一次地址的修改,更麻烦的是,之后每次发生紧凑,都要在程序上重新修改一次物理地址。
  • 相反,如果我们采用动态重定位装入方式,那么各个程序和数据的地址其实全程都是逻辑地址,在每次程序执行到需要访问地址的时候,无需修改程序上的地址,只需要将该逻辑地址与当前重定位寄存器里存放的物理起始地址进行相加即可。并且,每次发生紧凑的时候,也只需要用紧凑后的新起始地址去替换重定位寄存器里的旧起始地址。(因为初始大家个个块都是0开始的逻辑地址)

动态可重定位分区分配算法动态分区分配算法基本一致,区别仅在于,它在原有的基础上增加了紧凑功能。

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~