操作系统 第四章存储器管理

4.1 存储器的层次结构

4.1.1 多层结构的存储器系统

  1. 存储器的多层结构

    对于通用计算机而言,存储层次至少应具有三级:最高层为 CPU 寄存器,中间为主存,最底层是辅存。

  2. 可执行存储器

    寄存器和主存储器又被称为可执行存储器。进程可以在很少的时钟周期内使用一条 load 或store 指令对可执行存储器进行访问。但对辅存的访问则需要通过 I/O 设备实现,因此访问辅存所需耗费的时间远远高于访问可执行存储器的时间,一般相差 3 个数量级甚至更多。

4.1.2 主存储器与寄存器

  1. 主存储器

    简称内存或主存,是计算机系统中的主要部件,用于保存进程运行时的程序和数据,也称可执行存储器。

  2. 寄存器

    寄存器具有与处理机相同的速度,故对寄存器的访问速度最快,完全能与 CPU 协调工作,但价格昂贵,因此容量不是很大。

4.1.3 高速缓存和磁盘缓存

  1. 高速缓存

    介于寄存器和存储器之间的存储器,主要用于备份主存中较常用的数据,以减少处理机对主存储器的访问次数,大幅提高程序执行速度。容量大于寄存器,访问速度快于主存储器。

  2. 磁盘缓存

    本身并不是实际存在,而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息。主要用于暂时存放频繁使用的一部分磁盘数据和信息,以减少访问磁盘的次数。

4.2 程序的装入和链接

系统中运行,必须先将它装入内存,然后再将其转变为一个可以执行的程序,步骤:

  1. 编译,由编译程序(Compiler)对用户源程序进行编译,形成若干个目标模块(Object Module);
  2. 链接,由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起,形成一个完整的装入模块(Load Module);
  3. 装入,由装入程序(Loader)将装入模块装入内存。

4.2.1 程序的装入

无需进行链接的单个目标模块——装入模块。有三种装入方式:

  1. 绝对装入方式(Absolute Loading Mode)

    计算机系统很小,且仅能运行单道程序时,完全有可能知道程序将驻留在内存的什么位置。此时可以采用绝对装入方式。用户程序经编译后,将产生绝对地址(即物理地址)的目标代码。

  2. 可重定位装入方式(Relocation Loading Mode)

    对于用户程序编译所形成的若干个目标模块,起始地址通常都是从 0 开始,程序中的其他地址也都是相对于起始地址计算的。装入模块中的所有逻辑地址与实际装入内存后的物理地址不同。

    在装入时对目标程序中指令和数据地址的修改过程称为重定位。地址变换在进程装入时一次完成,以后不再改变,称为静态重定位

  3. 动态运行时装入方式(Dynamic Run-time Loading)

    动态运行时的装入程序在把装入模块装入到内存后,并不立即把装入模块中的逻辑地址转换为物理地址,而是把这种地址转换推迟到程序真正要执行时才进行。转入内存后的所有地址都仍是逻辑地址。

4.2.2 程序的链接

链接程序的功能是将编译产生的目标模块以及它们所需要的库函数装配成一个完整的装入模块。根据链接的时间不同,把链接分为三种方式:

  1. 静态链接(Static Linking)方式

    程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的装配模块,以后不再拆开。须解决以下两个问题:①对相对地址进行修改。②变换外部调用符号。

  2. 装入时动态链接

    用户源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的链接方式。在装入一个目标模块时,若发生一个外部模块调用事件,将引起装入程序去找出相应的外部目标模块,并将它装入内存,还要修改目标模块中的相对地址。优点:①便于修改和更新。②便于实现对目标模块的共享。

  3. 运行时动态链接

    将对某些模块(错误处理模块)的链接推迟到程序执行时才进行。加快装入过程、节省大量的内存空间。

4.3 连续分配内存管理方式

一个用户程序分配一个连续的内存空间,即程序中代码或数据的逻辑地址相邻,体现在内存空间分配时物理地址的相邻。连续分配方式可分为四类:单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法。

4.3.1 单一连续分配

单道程序环境下,存储器管理方式把内存分为系统区和用户区两部分,系统区仅提供给 OS 使用,通常是放在内存的低址部分。而在用户区内存中,仅装有一道用户程序,即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。

4.3.2 固定分区分配

多道程序系统中,将整个用户空间划分为若干个固定大小的区域,每个分区中只装入一道作业。

  1. 划分分区的方法

    分区大小相等(缺乏灵活性)、分区大小不等。

  2. 内存分配

    将分区按其大小进行排队,并为之建立一张分区使用表,当有用户程序要装入时,有内存分配程序依据用户程序的大小检索该表,从中找出一个能满足要求的、尚未分配的分区,将之分配给该程序。若未找到大小足够的分区,则拒绝为该用户程序分配内存。

4.3.3 动态分区分配

又称可变分区分配,它是根据进程的实际需要,动态地为之分配内存空间。

  1. 动态分区分配中的数据结构

    空闲分区表和空闲分区链。

  2. 动态分区分配算法

    见下一节。

  3. 分区分配操作

    分配内存

    回收内存

    进程运行完毕释放内存时,根据回收区的首址,从空闲区链(表)中找到相应的插入点:

    • 回收区与插入点的前一个空闲分区 F1 相邻接,此时应将回收区与插入点的前一分区合并,不必为回收分区分配新表项,而只需修改其前一分区 F1 的大小。
    • 回收分区与插入点的后一空闲分区 F2 相邻接,此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和。

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

4.3.4 基于顺序搜索的动态分区分配算法

顺序搜索——依次搜索空闲分区链上的空闲算法。

  1. 首次适应(first fit,FF)算法

    FF 算法要求空闲分区链以地址递增的次序链接。在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存空间,分配给请求者,余下的空闲分区仍留在空闲链中。找不到则内存分配失败。优点:高地址部分存在大的内存分区;缺点:低地址部分碎片较多,查找开销大。

  2. 循环首次适应(next fit,NF)算法

    为避免低址部分留下许多很小的空闲分区,减少查找可用空闲分区的开销,NF 在为进程分配内存空间时,从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业。优点:内存空闲区分布均匀,查找开销小;缺点:缺乏大的空闲分区。

  3. 最佳适应(best fit,BF)算法

    每次为作业分配内存时,总是把能满足要求、又是最小的空闲分区分配给作业。该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。 缺点:每次分配后所切割下来的剩余部分总是最小的,这样存储器中会留下很多难以利用的碎片。

  4. 最坏适应(worst fit,WF)算法

    与最佳适应算法相反:扫描整个空闲分区表或链表时,总是挑选一个最大的空闲区,从中分割一部分存储空间给作业使用,以至于存储器中缺乏大的空闲分区,故把它称为是最坏适应算法。优点:分配是剩下的空闲区不至于太小,产生碎片的可能性最小。

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

大、中型系统往往采用基于索引搜索的动态分区分配算法。

  1. 快速适应(quick fit)算法

    又称为分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表。同时,在内存中设立一张管理索引表,其中的每一个索引表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。 分配时分两步:第一步根据进程的长度,从索引表中去寻找能容纳它的最小空闲区链表;第二步从链表中去下第一块进行分配。

  2. 伙伴(buddy system)系统

    该算法规定,无论已分配分区或空闲分区,其大小均为 2k(k为整数,l≤k≤m)。通常 2m 是整个可分配内存的大小。假设系统的可利用空间容量为 2m 个字,则系统开始运行时,整个内存区大小为 2m。在系统运行过程中,不断划分,将会形成若干个不连续的空闲分区,将这些空闲分区按大小分类。具有相同大小的所有空闲分区,单独设立一个空闲分区双向链表,形成 k 个空闲分区链表。

    分配时:首先根据需要的存储空间 n 计算一个i值,使得 2i-1<n≤2i,然后在空闲分区大小为 2i 的空闲分区链表中查找。若找到,则分配给进程;否则,则在分区大小为 2i+1 的空闲分区链表中寻找,若存在,则把该空闲分区分为两个相等的分区,称为一对伙伴,其中一个用于分配,另一个加入分区大小为 2i 的空闲分区链表中。若大小为 2i+1 的空闲分区也不存在,则需要查找大小为 2i+2 的空闲分区,进行两次分区分割,第一次,将其分割为两个 2i+1 大小的分区,一个用于分配,一个假如到空闲分区链表中,第二次,将用于分配的分区进行分割,一个用于分配,一个加入到大小为 2i 的空闲分区链表中。以此类推。

    对一个大小为 2k,地址为 x 的内存块,其伙伴块的地址用 buddyk(x) 表示,其通式为:

  3. 哈希算法

    利用哈希快速查找的优点,以及空闲分区在可利用空闲分区表中的分区规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。分配时,根据所需大小,通过哈希函数计算,得到在哈希表中的位置,从中得到相应的空闲分区链,以实现最佳分配策略。

4.3.6 动态可重定位分区分配

  1. 紧凑

    将内存中的作进行移动,使他们相邻接,把分散的多个空闲小分区拼接成一个大分区,可将一个作业装入该区。称为“拼接”或“紧凑”。

  2. 动态重定位

    在 4.2.1 节中所介绍的动态运行时装入的方式中,作业装入内存后的所有地址都是相对(逻辑)地址。到程序指令要真正执行时才将相对地址转换为绝对(物理)地址。

    为使地址的转换不会影响到指令的执行速度,必须有硬件地址变换机构的支持,即须在系统中增设一个重定位寄存器,存放程序(数据)在内存中的起始地址。

    程序在执行时,真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

  3. 动态重定位分区分配算法

    动态重定位分区分配算法与动态分区分配算法基本上相同,差别仅在于:在这种分配算法中,增加了紧凑的功能。

    当该算法不能找到一个足够大的空闲分区以满足用户需求时,如果所有的小的空闲分区的容量总和大于用户的要求,这时便须对内存进行“紧凑”,将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求,则返回分配失败信息。

4.4 对换(Swapping)

4.4.1 多道程序环境下的对换技术

  1. 对换的引入

    在多道程序环境下,一方面,在内存中的某些进程被阻塞运行,但占用了大量的内存空间,甚至所有进程都被阻塞,迫使CPU停止下来等待的情况;另一方面,却又有着许多作业,因内存空间不足,一直驻留在外存上,而不能进入内存运行。

  2. 对换的类型

    整体对换、页面(分段)对换。

4.4.2 对换空间的管理

  1. 对换空间管理的主要目标

    具有对换功能的 OS 中,通常把磁盘空间分为文件区和对换区两部分。

  2. 对换区空闲盘块管理中的数据结构

    记录外存对换区中的空闲盘块的使用情况。用空闲分区表或空闲分区链。在空闲分区表的每个表目中,应包含两项:对换区的首址及其大小,分别用盘块号和盘块数表示。

  3. 对换空间的分配与回收

    由于对换分区的分配采用的是连续分配方式,因而对换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同。

4.4.3 对换空间的换出与换入

  1. 进程的换出

    分为以下两步:选择被换出的进程、进程换出过程。

  2. 进程的换入

    首先查看 PCB 集合中所有进程的状态,从中找出“就绪”状态但已换出的进程。当有许多这样的进程时,它将选择其中已换出到磁盘上时间最久(必须大于规定时间,如 2 s)的进程作为换入进程,为它申请内存。如果申请成功,可直接将进程从外存调入内存;如果失败,则需先将内存中的某些进程换出,腾出足够的内存空间后,再将进程调入。

4.5 分页存储管理方式

分页存储管理方式、分段存储管理方式、 段页式存储管理方式。

4.5.1 分页存储管理的基本方法

  1. 页面和物理块

    分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域,称为页/页面。相应地,将内存空间划分成与页相同大小的若干个物理块,称为块或页框/物理块。在为进程分配内存时,以页面为单位进行分配。将进程中的若干页分别装入多个不相邻接的块中。

  2. 地址结构

    分页系统由两部分组成:前部分为页号 P;后一部分为位移量 W,即页内地址 d。图 中的地址长度为 32 位,其中 0~11 位为页内地址(每页的大小为 4KB),12~31 位为页号,所以允许地址空间的大小,最多为 1MB 个页。

    若给定逻辑地址 A,页面大小 L,则可求:\(P=INT[\frac AL],\ d=[A]\ MOD \ L\)

    INT 整除,MOD 取余。页面大小 L 为 1KB,设 A=2170B,则 P=2,d=122。

  3. 页表

    在将进程的每一页离散地分配到内存的多个物理块中后,系统应能保证能在内存中找到每个页面所对应的物理块。

    为此,系统为每个进程建立了一张页面映射表,简称页表。每个页在页表中占一个表项,记录该页在内存中对应的物理块号。页表的作用是实现从页号到物理块号的地址映射。

    页面大小通常是:几 KB 到几十 KB,由机器的地址结构所决定的,即由硬件所决定。

    • 小->内碎片小,内存利用率高,但页面数目多,使页表过长,占大量内存,管理开销大;
    • 大->页表短,管理开销小,内碎片大,内存利用率低。

4.5.2 地址变换机构

基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址,实际上就要将用户程序中的页号变换成内存中的物理块号。

  1. 基本的地址变换机构

    • 进程访问某个逻辑地址时,地址变换机构把有效地址 / 相对地址分为 2 部分——页号与页内地址;
    • 页内地址与块内地址/页框内地址一一对应,无须转换。
    • 在系统中设置页表寄存器,用来存放页表在内存的始址和页表的长度。在进程未执行时,每个进程对应的页表的始址和长度存放在进程的 PCB 中,当该进程被调度时,就将它们装入页表寄存器。
    • 将物理地址存储在物理地址寄存器中——块号、块内地址。
    • 实现过程:
    • 地址转换图示:1556150929471
  2. 具有快表的地址变换机构

    如果页表存放在内存中,则每次访问内存时,CPU 存取一个数据必须访问两次内存。第 1 次,访问内存中的页表——物理地址;第 2 次再访问内存,去存取物理地址中的数据。

    快表内容:用以存放当前访问的那些页表项。

    此时地址变换过程为:在 CPU 给出有效地址后,地址变换机构自动地将页号送入高速缓存,确定所需要的页是否在快表中。若是,则直接读出该页所对应的物理块号,送入物理地址寄存器;若在快表中未找到对应的页表项,则需再访问内存中的页表,找到后,把从页表中读出的页表项存入快表中的一个寄存器单元中,以取代一个旧的页表项。

    快表通常只能存放 16~512 个页表项。

4.5.3 访问内存的有效时间

从进程发出指定逻辑地址的访问请求,到找到对应的实际物理地址单元并取出数据,花费的总时间,称为内存的有效访问时间(Effective Access Time,EAT)。

有效访问时间分为第一次访问内存时间(即查找页表对应的页表项所耗费的时间 t)与第二次访问内存时间(即将页表项中的物理块号与页内地址拼接成实际物理地址所耗费的时间 t)之和。

在引入快表的分页存储管理方式中,\(EAT=a\times \lambda+(t+\lambda)(1-a)+t=2t+\lambda-t\times a ​\)。λ 表示查找快表所需要的时间,а 表示命中率,t 表示访问一次内存所需要的时间。

4.5.4 两级和多级页表

每个进程的页表占用很多内存空间(太大了),还要求连续,显然不现实。解决办法:

  • 对页表所需的空间,采用离散分配方式,形成两级(甚至多级页表);
  • 将当前所需要的部分页表项调入内存,其余部分仍然驻留在磁盘上,需要时再将它们调入内存。
  1. 两级页表
    • 基本方法:是将页表进行分页,每个页面的大小与内存物理块的大小相同,并为它们进行编号,离散地将各个页面分别存放在不同的物理块中,为此再建立一张页表,称为外层页表(页表目录),即第一级页表,其中的每个表目是页表页面的物理块号。第二级才是页表,其中的每个表目所存放的才是页的物理块号。
    • 逻辑地址结构:两级页表系统将 32 位逻辑地址空间的地址分成三段:其中,页表目录号(外层页号 p1)和页号(外层页内地址 p2)两项各占 10 位,偏移量(页内地址 d)占 12 位。物理块号和页表的物理地址都占 4 个字节,每页中包含 1024个 页表项,则每页的大小为 4KB。
    • 两级页表结构:
    • 访问内存时间:$EAT=t+t+t=3t $,以时间换空间。
  2. 多级页表

    针对 64 位的机器,采用两级页表就不太合适。

4.5.5 反置页表

  1. 反置页表的引入

    为了减少页表占用的内存空间,引入了反置页表。反置页表依据该进程在内存中的物理块号来组织(即:按物理块号排列)。反置页表为每一个物理块设置一个页表项,并将它们按照物理块的编号排序,内容是页号和其所隶属进程的标识符。

  2. 地址变换

    根据进程标识符和页号,去检索反置页表。如果检索到匹配的页表项,则该页表项(中)的序号i 便是物理块号,该块号与页内地址构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项,则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统,此时则表示地址出错。对于具有请求调页功能的存储器管理系统,此时应产生请求调页中断,系统将把此页调入内存。

4.6 分段存储管理方式

4.6.1 分段存储管理方式的引入

  1. 方便编程

    程序员们需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的,这不仅可以方便程序员编程,也可使程序非常直观,更具可读性。

  2. 信息共享

    在实现对程序和数据的共享时,是以信息的逻辑单位为基础的。

  3. 信息保护

    信息保护同样是以信息的逻辑单位为基础的,而且经常是以一个过程、函数或文件为基本单位进行保护的。

  4. 动态增长

    存在着一些段,尤其是数据段,在它们的使用过程中,由于数据量的不断增加,而使数据段动态增长,相应地它所需要的存储空间也会动态增加。

  5. 动态链接

    当程序要运行时,首先将主程序和它立即需要用到的目标程序装入内存,即启动运行。而在程序运行过程中,当需要调用某个目标程序时,才将该段(目标程序)调入内存并进行链接。

4.6.2 分段系统的基本原理

  1. 分段

    在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段定义了一组逻辑信息。例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等,如图所示。分段地址中的地址具有如下结构:

  2. 段表

    在分段式存储管理系统中,则是为每个分段分配一个连续的分区。进程中的各个段,可以离散地装入内存中不同的分区中。为保证程序能正常运行,就必须能从物理内存中找出每个逻辑段所对应的位置。

  3. 地址变换机构

  4. 分页和分段的主要区别

  • 页是信息的物理单位。
  • 页的大小固定且由系统决定。
  • 分页的用户程序地址空间是一维的。

4.6.3 信息共享

  1. 分页系统中对程序和数据的共享

    分页系统中,虽然也能实现对程序和数据的共享,但远不如分段系统来得方便。

  2. 分段系统中程序和数据的共享

4.6.4 段页式存储管理方式

  1. 基本原理

    先将用户程序分成若干个段,再把每个段分成若干个页,并为每一个段赋予一个段名。

  2. 地址变换过程

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×