操作系统第4章课件

1、24 七月 2022第4章 存储器管理24 七月 2022目 录4.1 存储器管理的基本知识4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 段页式存储管理方式4.6 虚拟存储器的基本知识4.7 请求分页存储管理方式4.8 页面置换算法4.9 请求分段存储管理方式24 七月 2022教学目标熟练掌握： 最佳置换和先进先出页面置换算法，理解并掌握最近最久未使用置换算法，了解Clock、最少使用和页面缓冲置换算法掌握： 存储器管理的基本概念，分页存储管理方式和分段存储管理方式的基本原理，虚拟存储器的基本概念，请求分页存储管理方式。了解： 程序装入的方式和实现链接的

2、方法,几种连续分配方式，对换和覆盖技术，段页式存储管理技术，领会虚拟存储器的实现方式，请求分页、请求分段中的硬件支持。 24 七月 20224.1.1 存储器管理的功能 1内存空间的分配和回收 内存分配的主要任务是采用一定的数据结构，按照一定的算法为每一道程序分配内存空间，并记录内存空间的使用情况和作业的分配情况。当程序运行结束后，其所占用的内存空间必须归还给操作系统，即回收内存空间。 2地址转换 所谓地址转换是指将用户程序的逻辑地址转换为运行时能由机器直接寻址的物理地址的过程，也称为地址映射（即程序装入）。4.1 存储器管理的基本概念 24 七月 2022 3内存空间的共享与保护 在多道程序

3、设计的系统中，内存中允许同时装入多个作业，这些作业在执行时可能要调用共同的程序或数据，这就是内存的共享。存储保护的工作一般由硬件和软件配合实现。 4内存空间的扩充 由于内存空间有限，有的作业太大无法调入内存运行，因此需要借助于覆盖、交换和虚拟存储技术，为用户提供比内存大的地址空间，使用户编写程序时不必考虑内存的实际容量，使计算机系统似乎有一个比实际内存容量大得多的内存空间，从而保证大作业和多通道作业的正常运行。24 七月 20224.1.2 程序的装入将一个用户源程序变为一个可在内存中执行的程序，处理过程如下：（1）编译（2）链接（3）装入源程序的执行过程24 七月 2022 将一个程序装入内

4、存，可采用3种方式： 1绝对装入方式 由装入程序根据装入模块中的地址将程序和数据装入内存。程序中所使用的绝对地址 2可重定位装入方式 又称静态重定位装入，装入程序根据内存当前的实际使用情况，将装入模块装入到内存适当的地方，地址变换在装入时一次完成。这种方式采用相对地址来存放程序和数据。 3动态运行时装入方式 又称动态重定位装入，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。24 七月 20224.1.3 程序的链接实现链接的方法有3种：1.静态链接静态链接是指事先进行链接，以后不再拆开。静态链接示意图24 七月 20222

5、.装入时动态链接边装入边链接 其优点：（1）便于修改和更新。（2）便于实现对目标模块的共享。 3.运行时动态链接 将对某些模块的链接推迟到执行时才执行。 24 七月 20224.2.1 单一连续分配 采用单一连续分配方式时，内存被分成系统区和用户区两个区域：系统区仅供操作系统使用，存放操作系统常驻内存的代码和数据，通常设置在内存的低段；用户区供用户使用，它是除系统区以外的全部内存区域，任何时刻内存储器中最多只有一个作业存在。 4.2 连续分配方式24 七月 2022是否给作业分配内存空间，装入并执行该作业释放该作业内存空间接受下一作业作业大小用户区空间？本次作业无法运行作业运行结束是否单一连续

6、分配算法示意图24 七月 2022 单一连续分配方式的优点：（1）分配算法简单，易于实现 （2）每次装入新作业时，只需要覆盖掉原来的作业 单一连续分配方式的缺点：（1）存储器没有得到充分利用（2）处理器的利用率较低（3）作业周转时间较长（4）缺乏灵活性24 七月 20224.2.2 固定分区分配 固定分区分配是满足多道程序设计的最简单的管理方式。 1基本思想 把内存空间划分成若干个固定大小的连续存储区，称为分区。 2内存的分配与回收 为了管理内存空间的分配和回收，系统必须设置一张“内存分配表”记录各个分区的使用情况。其内容包括分区号、分区大小、起始地址和状态（是否分配）。 24 七月 2022

7、4.2.2 固定分区分配 在下表所示的内存空间中，已装入作业A（10KB）和B（40KB），需要装入作业C（50KB），系统的内存空间情况如图所示。 固定分区内存分配表区 号分区大小（KB）起始地址（KB）状 态11616已分配23232未分配3864未分配46472已分配5120136未分配24 七月 202224 七月 20223固定分区分配的优缺点优点：（1）解决了多个作业共享内存空间的问题（2）支持多道程序设计（3）容易实现缺点： （1）不能充分利用内存空间，（2）由于分区大小事先已经决定，限制了可装入程序的大小。（3）分区数目固定，限制了可同时执行的作业数目。24 七月 20224.

8、2.3 动态分区分配 1基本思想 动态分区指系统不预先划分固定分区，而是在作业装入内存时才建立分区，使为作业分配的分区大小刚好等于该作业的需求量，且分区个数是可变的。24 七月 2022 例如，有一个256KB的内存，其中操作系统占16KB，用户区占240KB，内存的分配变化过程如下图所示。24 七月 2022已分配分区表区 号分区大小起始地址状 态11616已分配22032已分配3-未分配4864已分配54072已分配6-未分配空闲分区表区 号分区大小起始地址状 态11252可用2144112可用24 七月 2022 2动态分区的分配算法 （1）首次适应算法 每次分配分区时，操作系统顺序查找

9、空闲分区表，把最先能够满足要求的空闲分区进行分割。 （2）最佳适应算法 为一个作业选择分区时总是寻找其大小最接近于作业要求的内存分区。 （3）最坏适应算法 与最佳适应算法相反，空闲分区按长度从大到小顺序链接，空闲分区表中的第一个空闲分区总是最大的。 24 七月 2022【例4-1】 某系统采用动态分区管理计算。某时刻在内存有3个空闲区，它们的首地址和大小分别是：空闲区1（100KB，10KB），空闲区2（200KB，30KB），空闲区3（300KB，15KB）。现有如下作业序列：作业1需要15KB，作业2需要16KB，作业3需要10KB。要求：（1）画出该时刻内存分配图。（2）画出采用首次适应

10、算法和最佳适应算法后的内存分配图。24 七月 2022解：（1）作业序列装入主存之前，内存的分配图如图所示。10KB30KB15KB315KB300KB230KB200KB110KB100KB0KB24 七月 2022 （2）采用首次适应算法和最佳适应算法分配作业内存示意图如图所示。作业3（10KB）15KB100KB110KB200KB230KB15KB300KB315KB(a)首次适应算法（15KB） 0KB100KB110KB200KB230KB300KB315KB(b)最佳适应算法作业3（10KB）作业2（16KB）14KB作业1（15KB）0KB24 七月 20223动态分区内存回收

11、一般情况应考虑四种可能性：（1）回收分区与前空闲分区相邻（2）回收分区与后空闲分区相邻（3）回收分区与前后空闲分区相邻（4）回收分区不与任何空闲分区相邻24 七月 20224动态分区分配的优缺点优点：分区大小不固定，管理方式比较灵活缺点：产生大量的容量较小的空闲分区，因而降低了系统的效率。24 七月 20224.2.4 动态重定位分区分配 1基本思想 移动所有已分配的分区，使之成为一个连续的区域，从而把碎片集中成一个较大的空闲区，这个移动的过程称为“紧凑”或“聚拢”。24 七月 20222紧凑的时机（1）是立即靠拢（2）是需要时靠拢3动态重定位分区分配的优缺点优点：消除了碎片，提高了内存利用率

12、。缺点：增加了计算成本，降低了计算机的速度。24 七月 20224.2.5 对换和覆盖1覆盖就是一个进程的若干个程序段，或几个进程的某些部分共享同一内存空间2对换 指将内存中暂时不运行的进程调出内存，存放在外存的交换区 中，以便腾出足够的内存空间，装入新程序或把已具备运行条件的进程调入内存并让其执行的一种内存扩充技术。 24 七月 20224.3 基本分页存储管理方式 4.3.1基本分页存储管理的基本原理1.内存块或块 2.辑页面或页 3.页内碎片 4.页表（1）页号 （2）页面对应的块号24 七月 20220页1页作业A作业B0页1页2页3页0 21 5作业A页表作业B页表0 01 32 7

13、3 401234567内存空间分页存储管理示意图24 七月 20224.3.2 基本分页存储管理的地址变换机构 由逻辑地址计算出页号和页内地址的方法：页号=逻辑地址/页长 （商）页内地址=逻辑地址mod页长 （余）由块号计算物理地址的计算方法为：物理地址=块号块长+块内地址+用户区基址1.硬件支持（1）页表寄存器 （2）逻辑地址寄存器 （3）物理地址寄存器 （4）越界中断机构 24 七月 20222.地址转换过程24 七月 2022【例4-2】某系统采用基本分页存储管理方式，其逻辑地址结构为16位，其中，页内地址占10位，页号占6位。某作业有5页，页号为04，依次存放在内存的2、3、4、7、8

14、块中。试问：（1）作业的虚存地址空间有多大？（2）系统的页面大小是多少？（3）逻辑地址5000对应的物理地址是多少？解：（1）由于逻辑地址结构为16位，所以作业的虚存地址空间有216B=64KB。（2）由于页内地址占10位，所以系统页面大小为210B=1KB。（3）在分页存储管理方案中，系统通过页表实现地址转换，操作系统将逻辑地址分为页号P（P=5000/1024）为4，页内地址W（W=5000 mod 1024=904）为904，然后查页表得页号4对应的物理块为8，从而变换出相应的物理地址为：物理地址=块号页面大小+页内地址=81KB+904B=9096B24 七月 2022 3.快表的引入

15、 引入快表的地址变换过程 （1）在CPU给出了有效地址后，地址变换机构自动将页号送入高速缓存，再确定所需的页是否在快表中。（2）若在快表中，直接读出该页所对应的物理块号，并送入物理寄存器。（3）若在快表中未找到对应页表项，需访问内存中的页表，把从页表中读出的页表项存入快表的一个寄存器空闲单元中。（4）若快表中没有空闲单元，则根据淘汰算法淘汰某一行，然后填入得到的页号和块号。（5）根据得到的块号和逻辑地址中的页内地址得到物理地址。24 七月 202224 七月 2022 假定访问内存的时间为200纳秒，访问高速缓存的时间是40纳秒，高速缓冲存储器有16个单元时，查找快表的命中率可达90%，若不使

16、用快表，需要两次访问内存，需要时间为200+200=400纳秒，概率为10%，若使用快表，需要时间为40+200=240纳秒，概率为90%。于是，根据逻辑地址转换成物理地址进行存取的平均时间是： （40+200）90%+（200+200）10%=256（纳秒）24 七月 20224.3.3 基本分页存储管理的共享和保护 1页面共享共享的方法是使各自页表中的有关表目指向共享信息的内存块。页号块号02142538页号块号01152637页表1页表2 2存储保护（1）在进行地址变换时，产生的页号应小于页表长度 （2）扩充页表的功能 24 七月 2022 基本分页存储管理的主要优点有：不要求作业或进程

17、的程序和数据在内存中连续存放，从而有效地解决了碎片问题；提高了内存的利用率，又有利于组织多道程序运行。 主要缺点有：采用动态地址变换机构降低了CPU的速度；由于作业的地址空间不一定是存储块的整数倍，因而最后一个存储块往往是装不满的，即出现了块内碎片问题；要求运行的作业必须全部装入内存才能运行，如果现有的空闲块不足以满足该作业的要求，作业只能等待，浪费了内存空闲空间。 24 七月 20224.4 基本分段存储管理方式 4.4.1 基本分段存储管理的基本原理 将用户的作业按逻辑结构划分为若干相互独立的段，每个段都有自己的名字，且每个段都占据一段连续的内存空间，各个段之间可以不连续。 例如一个程序可

18、以划分成主程序段，子程序段A、B、C，数据段D和堆栈段S，每个段有一个段名，都从0开始编址。每个段内的地址是连续的，而段和段的地址不一定连续，且各段的长度也不一定相等，如图所示。01N1X:子程序段A012.N0Call A|(调用A段入口X)Call D|(调用D段入口Y)Load 1，S|（将A段的C单元的内容读人1号寄存器）主程序段Main012N2Y:数据段D01N3C:堆栈段S24 七月 2022段号S段内地址W分段地址结构分段管理系统24 七月 20224.4.2 基本分段存储管理的地址变换机构 1硬件支持（1）CPU给出的有效地址应是分段的编址形式。（2）整个系统需要设置一个段表

19、寄存器。（3）为加快地址映射，也可以采用快表技术。24 七月 2022 2地址转换过程（1）提取逻辑地址中的段号，比较段号和段表长，若段号超过段表长度，表示访问越界，则发出“越界中断”。（2）若未出现越界错误，则根据段表始址在内存中找到段表，以逻辑地址中的段号为索引，查找段表，找到其对应的表项。（3）比较段表项中的段长和逻辑地址中的段内地址，若段内地址超过段长则产生越界中断。（4）否则，检查是否符合存取权限，如不符合存取权限，则发出“保护中断”。（5）取出段表项中欲访问段的基址，加上逻辑地址中的偏移量得到物理地址。 24 七月 202224 七月 20224.4.3 基本分段存储管理的共享和保

20、护 1段的共享24 七月 2022 2段的保护 （1）地址越界保护：在地址转换过程中，限制段内地址超过段长，使保护作业不能访问属于它的地址空间，因而就消除了一个用户作业破坏另一个用户作业的危险。 （2）存取权限保护：每个作业对访问的段都有规定的存取权限，只有符合存取权限才允许访问，因而防止了用户误操作对段的破坏。24 七月 2022【例4-3】 设作业的虚拟地址为24位，其中高8位为段号，低16位为段内相对地址。试问： （1）一个作业最多可以有多少段？ （2）每段的最大长度为多少字节? （3）某段式存储管理采用如表所示的段表，试计算0，430、1，50、 3，20的物理地址。解：（1）一个作业

21、最多可以有28=256个段。 （2）每段的最大长度为21664KB。 （3）逻辑地址0，430的物理地址为：2100+430=2530；逻辑地址1，50无法进行地址变换，因为产生了段内地址越界；逻辑地址3，20无法进行地址变换，因为段号越界。某段式存储管理采用的段表段号 段长访问权限基址0600E2100140R28002100R/W290024 七月 20224.5 段页式存储管理方式4.5.1 分段和分页的区别 （1）页是信息的物理单位，分页是为了提高内存的利用率；段是信息的逻辑单位，分段是为了满足用户的需要。 （2）页的大小固定不变，由系统决定 ，页只能以页大小的整数倍地址开始 ；段的大

22、小不固定，由用户编写的程序决定，段可以从内存的任何地址开始。 （3）分页的逻辑地址空间是一维的；分段的地址空间是二维的。 （4）段是信息的逻辑单位，段可以充分实现共享和保护；页是信息的物理单位，页的共享和保护受到限制。 （5）段式管理可能产生内存碎片；而页式管理则能很好地消除碎片。24 七月 20224.5.2 段页式存储管理方式介绍 1.基本思想 将分段在地址空间管理上的优点和分页在内存空间管理上的优点结合起来，作业中具有独立功能的程序段和数据段仍然按照逻辑功能来划分，并且每一段具有一个段名，反映了段式管理的特征；对应段中的程序和数据，按固定的大小将其划分成不同的页，这和页式管理相同，体现了

23、页式管理的特征。段号S页号P 页内地址W段页式结构示意图24 七月 202224 七月 2022 2地址转换（1）提取逻辑地址中的段号，比较段号和段表长，若超出段表长度，表示访问越界，则发出“越界中断”。（2）若未出现越界错误，则根据段表始址在内存中找到段表，以逻辑地址中的段号为索引，查找段表，找到该段对应的页表的大小和起始地址。（3）利用逻辑地址中的页号和页表大小进行比较，若页号超过页表大小，则产生地址越界中断。（4）否则，利用页表始址和逻辑地址中的页号得到该页所对应的页表项，从而获得该页在页表中的物理块号。（5）利用物理块号和页内地址形成物理地址。 24 七月 202224 七月 2022

24、 3段页式存储管理的优缺点 段页式管理保留了段式管理和页式管理的全部优点，提供了大量的虚存空间，能有效利用内存，便于处理变化的数据结构，便于共享和控制存取访问权限，为组织多道程序运行提供了方便。 缺点是增加了软件的复杂性和管理开销，需要更多的硬件支持，系统的复杂性提高；各种表格占据了存储空间，同时也存在着发生抖动的危险；页面使用不充分，和基本分页存储管理一样，存在页内碎片。 24 七月 20224.6 虚拟存储器的基本知识4.6.1虚拟存储器的引入 1局部性原理 （1）时间局限性 （2）空间局限性 2虚拟存储器 是指具有请求调入功能和置换功能，把内存和外存结合起来使用，能从逻辑上对内存容量加以

25、扩充的一种存储器系统。 24 七月 20224.6.2 虚拟存储器的实现方法 1.分页式虚拟存储管理 它是在分页式存储管理系统上增加了请求调页功能、页面置换功能所形成的页式虚拟存储管理系统。 2.分段式虚拟存储管理 它是在分段式存储管理系统上增加了请求调段功能、分段置换功能所形成的段式虚拟存储管理系统。 24 七月 20224.6.3 虚拟存储器的特征（1）离散性：装入虚拟存储器的进程都是离散存放的，这是虚拟存储器的基础。（2）多次性：一个作业被分成多次调入内存运行，即在作业运行时没必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存，以后每当运行到尚未调入的那部分程序时，再将它调入。

26、 （3）对换性：允许在作业的运行过程中进行换进、换出。在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换进）。（4）虚拟性：指能够从逻辑上扩充内存容量，虚拟出一个较大的逻辑空间，使用户所看到的内存容量远大于实际内存容量。 24 七月 20224.7 请求分页存储管理方式4.7.1 请求分页中的硬件支持 1.页表 请求分页存储管理方式需要对页表进行扩充，增加状态位、外存地址、访问位和修改位等信息，扩充后的页表如图所示。页号块号状态位外存地址访问位修改位请求页式存储管理页表24 七月 20222地址变换24 七月 2022 3缺页

27、中断 缺页中断是在指令执行过程中产生的中断，与在一条指令执行完成后产生的一般中断不同。 缺页中断是一种特殊的中断与一般的中断的区别： （1）中断产生的时间不一样 （2）产生中断的次数不一样24 七月 2022 【例4-4】 在请求分页存储管理系统中，存取一次内存的时间是8s，查询一次快表的时间是1s，缺页中断的时间是20s，假设页表的查询与快表的查询同时进行。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页的页表项送入快表。 （1）求对某一数据进行一次存取可能需要的时间。 （2）现对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间。解： （1）当系统对数据进行存取

28、时，有3种可能性。 所存取的数据的页面在内存，其页表项已经存储到快表，此时存取数据的时间是： 查询快表的时间+存取内存数据的时间=1s +8s =9s 所存取的数据的页面在内存，但是其页表项没有存储到快表，没有命中快表，此时存取数据的时间是： 查询页表的时间+存取内存数据的时间=8s +8s =16s24 七月 2022 所存取的数据的页面不在内存，发生缺页中断，此时存取数据的时间是： 查询页表的时间（页面不在内存）+缺页中断的时间+查询页表的时间（页面在内存）+存取内存数据的时间=8s +20s +8s +8s =44s （2）当对某一数据进行4次连续读取时： 第1次可能的时间为：1s +8

29、s =9s；8s +8s =16s；8s +20s +8s +8s =44s。 第2次时，对应页面的页表项已经交换到快表中。因为存取是连续的，不存在页面被淘汰的可能性，所以第2次、第3次、第4次的存取时间是一样的，消耗的时间为1s +8s =9s。24 七月 20224.7.2 内存分配策略和分配算法1最小物理块数的确定 2物理块的分配策略1）固定分配策略 采用以下3种算法 ： （1）平均分配算法 （2）按比例分配算法 （3）考虑优先权的分配算法2）可变分配策略24 七月 20223页面置换策略1）全局置换策略2）局部置换策略页面置换策略和内存分配策略3种组合方式1）固定分配局部置换2）可变分

30、配全局置换3）可变分配局部置换24 七月 20224.7.3 调页策略 1请求调页策略 请求跳页策略是指需要访问程序和数据时，才把所需页面装入内存，即按需跳页，每次调入一页。 2预调页策略 预调页策略是指系统预测进程要使用的页面，使用前预先调入内存，每次调入若干页面，而不仅仅是一页。24 七月 20224.7.4 请求分页式存储管理方式的特点（1）要运行的作业可以不必全部装入内存就能运行。（2）节省内存空间，增加并发执行的作业个数，提高系统的利用率。（3）增加了程序运行的时间，加大了系统的硬件开销。24 七月 20224.8 页面置换算法4.8.1 最佳置换算法 基本思想是：选择将来永不再使用

31、的或在将来最迟才会被访问的页面进行置换。 例如，采用固定分配局部置换策略，系统为某个进程在内存中分配了3个物理块，该进程的页面访问序列为：4、3、2、1、4、3、5、4、3、2、1、5。 采用最佳置换算法共发生7次缺页中断，缺页中断率=不成功的访问次数/总访问次数100%=7/12100%=58.3%。 24 七月 20224.8.2 先进先出置换算法基本思想:置换最早进入内存的页面，即置换在内存中驻留时间最长的页面。采用FIFO算法共发生9次缺页中断，缺页中断率=9/12100%=75%。 24 七月 2022 一般来说，分配给进程的物理块数越多，产生的缺页中断次数就会减少，但对于某些页面走

32、向，采用FIFO算法时，随着分配给它的物理块数增加，会出现缺页中断次数增加的现象，称为Belady现象。24 七月 202224 七月 20224.8.3 最近最久未使用置换算法 基本思想: 因无法预测将来，所以用“最近的过去”作为“最近的将来”的近似。共发生缺页中断10次，缺页率为10/12100%=83.3%。 24 七月 20224.8.4 Clock置换算法 基本思想: 将进程的页表中增加一个指针项，用于将内存中的页面链接成一个循环队列，并用一个指针指向循环队列中下一个将被置换的页面。共发生缺页中断10次，缺页率为10/12100%=83.3%。24 七月 20224.8.5 最近最少使用置换算法 基本思想: 选择最不经常使用的一页淘汰，它是LRU算法的一种近似算法，实现起来较为简单，只需为每页增设一个计数器。页面被访问一次，计算器加1，当产生缺页中断时，淘汰计数最小的一页，并将所有计数器清零。 24 七月 20224.8.6 置换算法总结最佳置换算法性能最好，是一种理想情况下的页面置换算法，无法实现。先进先出置换算法简单，易实现，性能最差，不实用。最近最久未使用置换算法性能较好，常被采用，但对硬件要求较高。24 七月 2022 【例4-5】 在一请求分页式管理系统中，假如系统分配给一个作业的物理块数为