第4章存储管理.ppt

第第4 4章章_ _存储管理存储管理所以，即使是现代的计算机系统，存储容量极大，速度所以，即使是现代的计算机系统，存储容量极大，速度也飞快，内存管理的重要性丝毫没有削弱。也飞快，内存管理的重要性丝毫没有削弱。对于一个单用户、单任务的操作系统的实现相对非常简单，对于一个单用户、单任务的操作系统的实现相对非常简单，支撑这种系统甚至不需要任何存储保护的硬件。在最严重的情支撑这种系统甚至不需要任何存储保护的硬件。在最严重的情况下即使内存崩溃也不会引起严重后果。况下即使内存崩溃也不会引起严重后果。对于一个多用户、多任务的操作系统的实现就复杂的多，对于一个多用户、多任务的操作系统的实现就复杂的多，支撑这种系统必需要有存储保护的硬件，单靠软件是无法胜任支撑这种系统必需要有存储保护的硬件，单靠软件是无法胜任的。在要求具有高可靠性的条件下，内存崩溃会引起严重的后的。在要求具有高可靠性的条件下，内存崩溃会引起严重的后果。果。4.1 4.1 程序的装入和链接的有关概念程序的装入和链接的有关概念用高级、汇编语言上机步骤：编译、链接、装入。用高级、汇编语言上机步骤：编译、链接、装入。编辑：编辑：得到如得到如test.cpp,a.asmtest.cpp,a.asm等源文件等源文件编译：编译：从每个源文件得到对应的目标文件（从每个源文件得到对应的目标文件（PCPC机系统后缀为机系统后缀为OBJOBJ的文件的文件)链接：链接：将若干有关目标文件（在将若干有关目标文件（在VC+VC+环境中为一个环境中为一个workspaceworkspace中中的文件）及有关系统支撑的库目标文件进行链接，得到相应的可的文件）及有关系统支撑的库目标文件进行链接，得到相应的可执行文件（执行文件（PCPC机系统后缀为机系统后缀为EXEEXE的文件或动态连接文件的文件或动态连接文件DLL)DLL)重定位：可执行文件平时驻留在外存上，需要执行时作为作重定位：可执行文件平时驻留在外存上，需要执行时作为作业首先装载到内存。业首先装载到内存。？这种可执行文件在外存？这种可执行文件在外存与内存格式一样吗与内存格式一样吗一样：一样：意味着意味着OS只要读入内存即可只要读入内存即可绝对装入。绝对装入。所以：所以：象象JMPL1指令在变成可执行代码后，该指令的地址场的数据是指令在变成可执行代码后，该指令的地址场的数据是固定的。这就意味该程序只能放在固定的地方。固定的。这就意味该程序只能放在固定的地方。diskJMP200loadJMP200MOVAX,201100200在多任务下在多任务下OS无法保证无法保证执行程序在执行程序在同一个位置，同一个位置，所以比如下所以比如下次装在次装在1000开始开始一、程序的装入一、程序的装入重定位：可执行文件平时驻留在外存上，需要执行时作为作重定位：可执行文件平时驻留在外存上，需要执行时作为作业首先装载到内存。业首先装载到内存。一样：一样：意味着意味着OS只要读入内存即可只要读入内存即可绝对装入。绝对装入。所以：所以：象象JMPL1指令在变成可执行代码后，该指令的地址场的数据是指令在变成可执行代码后，该指令的地址场的数据是定。这就意味该程序只能放在固定的地方。定。这就意味该程序只能放在固定的地方。diskJMP200loadJMP200MOVAX,20110001200一、程序的装入一、程序的装入重定位：可执行文件平时驻留在外存上，需要执行时作为作重定位：可执行文件平时驻留在外存上，需要执行时作为作业首先装载到内存。业首先装载到内存。一样：一样：意味着意味着OS只要读入内存即可只要读入内存即可绝对装入。绝对装入。不一样：不一样：意味着意味着OS只要读入内存时需要对地址场部分做调整只要读入内存时需要对地址场部分做调整可重定位装入。该工作有可重定位装入。该工作有OS中专门的程序负责，一般称为装载中专门的程序负责，一般称为装载（装入，加载）程序。（装入，加载）程序。方法：执行的目标码相对与方法：执行的目标码相对与0编址，涉及到地址的操作指令地址编址，涉及到地址的操作指令地址场称为一个浮动项，在目标码文件的头上有一个浮动项说明表，场称为一个浮动项，在目标码文件的头上有一个浮动项说明表，表中给了浮动项的个数，每个浮动项在文件中的位置（相对于表中给了浮动项的个数，每个浮动项在文件中的位置（相对于0的偏移量），的偏移量），OS的装载程序根据这些信息将本次分配的的装载程序根据这些信息将本次分配的内存地内存地址址+浮动项的内容浮动项的内容-浮动项的位置中。浮动项的位置中。一、程序的装入一、程序的装入例：例：MZMZ10100201头标志头标志MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP（200200）0100300300201头部分头部分代码部分代码部分200MZMZ10100201头部分头部分例：例：MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令码指令码JMP(200)JMP(200)0+1000100+1000300300201+10001000（2）装入）装入（1）头部分由）头部分由OS读入读入（3）OS根据读入根据读入的头对内存浮动项的头对内存浮动项装配装配MZMZ10100201头部分头部分例：例：MOVE,AXMOVE,AXJMPJMP指令码指令码JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令码指令码JMP(JMP(12001200)0+1000100+1000300300201+10001000（2）装入）装入（1）头部分由）头部分由OS读入读入（3）OS根据读入根据读入的头对内存浮动项的头对内存浮动项装配装配MZMZ10100201头部分头部分例：例：MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令码指令码JMP(JMP(12001200)0+1000100+100013001300201+10001000（2）装入）装入（1）头部分由）头部分由OS读入读入（3）OS根据读入根据读入的头对内存浮动项的头对内存浮动项装配装配装入后，进程装入后，进程整体可以移动整体可以移动吗？吗？动态运行装入方式把装入模块装入内存后，并不立即把装入模块中的相对地址（逻辑地址）转换为相对地址（绝对地址），只有在执行的时候才把逻辑地址转换为绝对地址。通常需要重定位寄存器支持。CPU执行过程中的地址都是内执行过程中的地址都是内存的物理地址存的物理地址装入方式汇总绝对装入方式可重定位装入方式动态运行时装入方式简单分析比较简单分析比较 4.1.2 4.1.2 程序的链接程序的链接源程序经过编译后，可能会得到一组目标模块，各个模块都有源程序经过编译后，可能会得到一组目标模块，各个模块都有自己的独立空间，从执行的角度看这些模块又是一个整体，各自己的独立空间，从执行的角度看这些模块又是一个整体，各个模块所涉及的地址最终都要合并为统一的地址。个模块所涉及的地址最终都要合并为统一的地址。静态静态链接：链接：将一个程序运行中所有的目标文件、所需要的将一个程序运行中所有的目标文件、所需要的库文件等链接成一个可执行模块。库文件等链接成一个可执行模块。链接分类链接分类静态静态链接链接动态链接动态链接载入时动态链接载入时动态链接运行时动态链接运行时动态链接对多用户、多任务系统显然有冗余，比如用户用对多用户、多任务系统显然有冗余，比如用户用sin(x)，则目标，则目标代码中都有这部分代码，装入到内存则也都有这部分代码。代码中都有这部分代码，装入到内存则也都有这部分代码。二、二、程序的链接程序的链接静态静态链接链接处理后将多个目标模块合并成为一个整体。处理后将多个目标模块合并成为一个整体。装入时动态装入时动态链接链接合并成为一个整体的过程在装入内存的时合并成为一个整体的过程在装入内存的时候才执行，在加载到内存之前各个模块仍然分离。候才执行，在加载到内存之前各个模块仍然分离。运行时动态运行时动态链接链接程序在执行过程中根据需要把各个模块链程序在执行过程中根据需要把各个模块链接起来，不需要的模块可以仍然留在外存上。接起来，不需要的模块可以仍然留在外存上。链接方式汇总静态链接方式装入时动态链接方式运行时动态链接方式简单的比较4.2 4.2 连续分配存储管理方式连续分配存储管理方式 因为程序的执行是根据指令计数器顺序执行,在执行本指令时,它已是下条指令的位置,跳转指令会自动置为跳转的目标地址,所以决定了程序必须占有连续的一段存储区,连续分配是指为一个用户程序分配一个连续的内存空间。4.2.1 4.2.1 单一连续分配单一连续分配 1)1)内存分为两个区域：系统区，用户区。应用程序装入内存分为两个区域：系统区，用户区。应用程序装入 到用户区，可使用用户区全部空间。到用户区，可使用用户区全部空间。特点：适用于单用户、单任务的特点：适用于单用户、单任务的OSOS。DOSDOS驻留部分驻留部分用户程序区用户程序区COMMANDCOMMAND可覆盖部分可覆盖部分MS_DOSMS_DOS的分布的分布:2)静态与动态重定位静态与动态重定位静态重定位：静态重定位：在程序装入内存时由在程序装入内存时由OSOS进行浮动项的定位进行浮动项的定位此后不在变化。此后不在变化。动态重定位：动态重定位：在程序装入内存时不进行装配，一般直接在程序装入内存时不进行装配，一般直接将程序装入内存。定位问题由系统提供的硬件解决。所以，将程序装入内存。定位问题由系统提供的硬件解决。所以，前提是前提是动态重定位问题需借助于硬件支持动态重定位问题需借助于硬件支持，否则无法解决。否则无法解决。在为单用户、单任务设计的系统中一般不会有此硬件。如在为单用户、单任务设计的系统中一般不会有此硬件。如Intel 8080Intel 8080、80868086、80888088CPU界限界限寄存器寄存器重定位重定位寄存器寄存器基址基址内存内存逻辑地址逻辑地址物理地址物理地址+否否是是地址错地址错带有存储保带有存储保护的地址变换护的地址变换机构机构4.2.2 4.2.2 固定分区分配固定分区分配1 1、把内存划分为若干个固定的连续分区。、把内存划分为若干个固定的连续分区。分区大小相等：只适合于多个相同程序的并发执行（处理多分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。个类型相同的对象）。分区大小不等：多个小分区、适量的中等分区、少量的大分分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。区。根据程序的大小，分配当前空闲的、适当大小的分区。分配策略：分配策略：当作业到达时，选择适合作业要求的最小空闲区分给作业，若当作业到达时，选择适合作业要求的最小空闲区分给作业，若该分区不空，让其在该分区队列中等待。该分区不空，让其在该分区队列中等待。为了充分利用存储器，系统只维持一个等待存贮器的队列。为了充分利用存储器，系统只维持一个等待存贮器的队列。任何时候，只要有一个分区变为空闲，队列中的一个作业就可任何时候，只要有一个分区变为空闲，队列中的一个作业就可装入运行。装入运行。多输入作业队列多输入作业队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统700K400K200K100K0单输入作业队列单输入作业队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统 这种操作员在清晨设置好，以后不能再修改的固定分区这种操作员在清晨设置好，以后不能再修改的固定分区的存储系统，曾经在的存储系统，曾经在IBMOS/360大型机上运行了许多年。大型机上运行了许多年。多输入作业队列多输入作业队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统700K400K200K100K0单输入作业队列单输入作业队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统 管理：管理：采用分区表采用分区表记录分区的大小和使用情况记录分区的大小和使用情况4.2.3 4.2.3 动态分区分配动态分区分配一、分区分配的数据结构：一、分区分配的数据结构：分区表可同时记录空闲和占用情况，也可用两张表分别记分区表可同时记录空闲和占用情况，也可用两张表分别记录空闲（空闲分区表）与占用（使用分区表），表项数目随着录空闲（空闲分区表）与占用（使用分区表），表项数目随着内存的分配和释放而动态改变；对顺序组织，表容量就决定了内存的分配和释放而动态改变；对顺序组织，表容量就决定了分区的最大个数。分区的最大个数。用分区表记录使用情况用分区表记录使用情况链表组织链表组织顺序存储顺序存储二、二、分区分配算法分区分配算法 分区分配算法：分区分配算法：寻找某个空闲分区，其大小需大于或寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于，则将该分区分割成两个分等于程序的要求。若是大于，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为区，其中一个分区为要求的大小并标记为“占用占用”，而，而另一个分区为余下部分并标记为另一个分区为余下部分并标记为“空闲空闲”。分区的先后。分区的先后次序通常是从内存低端到高端排列。次序通常是从内存低端到高端排列。分区释放算法：分区释放算法：注意需要将相邻的空闲分区合并成一注意需要将相邻的空闲分区合并成一个空闲分区。个空闲分区。依依寻找空闲分区的方法分成：寻找空闲分区的方法分成：1 1、首次适应法首次适应法(first-fit)(first-fit)：按分区的先后次序，从头查：按分区的先后次序，从头查找，找到符合要求的第一个分区。找，找到符合要求的第一个分区。特点：特点：该算法的分配和释放的时间性能较好，较大的空该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。而产生较多小分区，每次分配时查找时间开销会增大。3 3、最佳适应法最佳适应法(best-fit)(best-fit)：找其容量与要求最接近的空闲分找其容量与要求最接近的空闲分区。区。特点：特点：从个别来看，外碎片较小，但从整体来看，会形成从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。另外，为了能较较多外碎片。较大的空闲分区可以被保留。另外，为了能较快的定位空闲块，所以空闲分区表若以链表方式组织，则表快的定位空闲块，所以空闲分区表若以链表方式组织，则表应按空闲区大小递增排列。因此，在释放一个占用区时，应应按空闲区大小递增排列。因此，在释放一个占用区时，应按区大小插入链中并可能有区合并（此时合并比较麻烦）。按区大小插入链中并可能有区合并（此时合并比较麻烦）。2 2、下次适应法下次适应法(next-fit)(next-fit)：按分区的先后次序，从上次分配按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区。第一个分区。特点：特点：该算法的分配和释放的时间性能较好，使空闲分区分该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。布得更均匀，但较大的空闲分区不易保留。4.2.4 4.2.4 动态重定位分区分配动态重定位分区分配 在多任务前提下，分配一个区后大部分情况下都是有剩余零在多任务前提下，分配一个区后大部分情况下都是有剩余零头的，因此在一个新任务到达时，就有可能零头分区的和超过头的，因此在一个新任务到达时，就有可能零头分区的和超过新任务要求的分区，但每一个空闲区容量都不够。新任务要求的分区，但每一个空闲区容量都不够。一、一、紧凑紧凑 将各个占用分区向内存一端移动。使各个空闲分区聚集在将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。另一端，然后将各个空闲分区合并成为一个空闲分区。操作系统操作系统用户程序用户程序130KB10KB用户程序用户程序9用户程序用户程序614KB用户程序用户程序326KB操作系统操作系统80KB用户程序用户程序9用户程序用户程序6用户程序用户程序3用户程序用户程序1 问题：紧缩后程序如何重新执行？问题：紧缩后程序如何重新执行？没有重定位硬件支持是无法实现的。没有重定位硬件支持是无法实现的。二、二、动态重定位动态重定位2、什么时候紧缩、什么时候紧缩一旦有任务释放分区一旦有任务释放分区在找不到容量满足的空闲区时在找不到容量满足的空闲区时50001、重定位示意图、重定位示意图2500相对地址相对地址1000MOVE AXMOVE AX，25002500.25003653651010010000MOVE AXMOVE AX，25002500.36536510000重定位寄存器重定位寄存器15000+125004.2.5 PC 4.2.5 PC 微机中的存储管理（实方式）微机中的存储管理（实方式）1 1、重定位机构、重定位机构 四个段寄存器四个段寄存器CSCS、DSDS、ESES、SSSS，每个每个1616位；位；段大小段大小:64K16:64K16位表示段内地址位表示段内地址;逻辑地址：段址：段内偏移逻辑地址：段址：段内偏移 物理地址：段地址左移物理地址：段地址左移4 4位位+偏移偏移2020位物理地址位物理地址 若程序不超过若程序不超过6464K K，可以写成，可以写成COMCOM格式的可执行文件格式的可执行文件 2 2、DOS DOS存储管理接口存储管理接口 通过通过DOSDOS功能调用功能调用INT 21HINT 21H，涉及三个调用号，存储分配，涉及三个调用号，存储分配(48H)(48H)、释放、释放(49H)(49H)和改变分区大小和改变分区大小(4AH)(4AH)3 3、DOS DOS存储管理数据结构与算法存储管理数据结构与算法1）存储分配以存储分配以16字节为一个单位（称为节），所以最小字节为一个单位（称为节），所以最小分配单位是分配单位是1节节2）内存格式）内存格式看成链表看成链表，链首指针（由，链首指针（由DOS保存）给出了第保存）给出了第一个内存结点位置（段地址），内存结点格式如下：一个内存结点位置（段地址），内存结点格式如下：tag:tag:1 1字节，值为字节，值为 M M或或ZZ其中其中Z Z表示为链中最后一块表示为链中最后一块。tagpspsize保留保留内存区内存区psp:psp:（2 2字节）字节）psppsp在在DOSDOS中中称为程序段前缀，占称为程序段前缀，占100H100H的的字节，作用同字节，作用同OSOS中的中的PCBPCB。这里记占用该内存这里记占用该内存的进程的的进程的PSP地址，若为地址，若为0为空闲。为空闲。size:（2字节）内存块大小，以节为单位。字节）内存块大小，以节为单位。保留部分保留部分:（11字节），这样内存块的头正好字节），这样内存块的头正好1节，一个内存块节，一个内存块的字节数为（的字节数为（size+1)*16tagpspsize保留保留内存区内存区3)有关算法讨论有关算法讨论A）如果指针）如果指针p指向内存指向内存块的头块的头,则下块内存块的则下块内存块的头地址是头地址是:p+size+1;pB)若要将若要将p所指的内存块分配出去所指的内存块分配出去x节节(xtag=p-tag;/构造分出的新块数据构造分出的新块数据q-size=p-size-x-1;q-psp=0;c)p-size=x;/修改原块数据修改原块数据p-tag=M;p-psp=当前运行进程的当前运行进程的PSP地址；地址；q qxC)49H调用调用：参数参数ES寄存器，待释放的内存段地址。寄存器，待释放的内存段地址。开始开始p=(ES)-1p-tag为为M或或AL=08H(内存格式错内存格式错)结束结束p-psp=0D)48H调用：参数调用：参数BX申请量申请量返回：返回：成功，成功，AX分配得到的段地址分配得到的段地址不成功，不成功，BX,内存中最大的内存块容量内存中最大的内存块容量AL=08,AH=0开始开始maxsize=0firstblock=NULLp=DOS首块内存指针首块内存指针p-tag=M或或ZAL=07(格式错）格式错）返回返回nyq=pp-psp=0nq-tag=Znp=q+1+q-sizep-tag=M或或ZnyyAyBCDAp=q+1+q-sizeq-tag=Znp-tag=M或或ZnCyp-psp=0yq-size+=p-size+1q-tag=p-tagnyq-sizesizeyq-size申请量申请量firstblock=qfirstblock=NULLyynnDBp=firstblockp=NULLyAL=08(容量不够）容量不够）BX=maxsizen返回返回申请量申请量=p-sizenq=p-size+1+pq-size=p-size-1-申请量申请量p-size=申请量申请量q-psp=0;q-tag=p-tagp-tag=Mp-psp=当前当前DOS的的PSP地址地址yAX=p+1结论：结论：DOS中的存储管理的原理在课程中都有体现中的存储管理的原理在课程中都有体现在实现时又不拘于基本的方法（链，释放空间）在实现时又不拘于基本的方法（链，释放空间）对换对换1 1、引入：引入：多个程序并发执行，在内存容量不够时，将暂时不能执多个程序并发执行，在内存容量不够时，将暂时不能执行的进程（阻塞或就绪）放到外存，从而腾出内存空间。（为了行的进程（阻塞或就绪）放到外存，从而腾出内存空间。（为了装入新进程；处理保存在外存中而目前到达就绪状态的进程；目装入新进程；处理保存在外存中而目前到达就绪状态的进程；目的是加快已有进程的推进速度等）。交换单位为整个进程的地址的是加快已有进程的推进速度等）。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作配合使用。又称作“对换对换”或或“滚进滚进/滚出滚出”。2 2、原理：原理：暂停执行内存中的进程，选择一个处于阻塞（就绪）暂停执行内存中的进程，选择一个处于阻塞（就绪）的进程，将它的整个进程的地址空间保存到外存的交换区中的进程，将它的整个进程的地址空间保存到外存的交换区中，在适当的时候，需将外存中由阻塞变为就绪的进程的地址空间在适当的时候，需将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列。读入到内存中，并将该进程送到就绪队列。3 3、特点：特点：增加并发运行的进程数目，但换入和换出的控制增增加并发运行的进程数目，但换入和换出的控制增加处理机开销加处理机开销4 4、外存考虑的问题：外存考虑的问题：减少交换中传送的信息量，特别是对大程序；减少交换中传送的信息量，特别是对大程序；对外存交换区空间的管理不同于文件系统的管理思路，对外存交换区空间的管理不同于文件系统的管理思路，读写效读写效率是首要的，空间的利用率次要，如采用率是首要的，空间的利用率次要，如采用SISC高速硬盘，设置高速硬盘，设置专用对换区甚至考虑添加专有硬盘。（在对换区中，专用对换区甚至考虑添加专有硬盘。（在对换区中，进程映象进程映象一般使用连续的磁盘块暂存）一般使用连续的磁盘块暂存）总结上述几种内存管理方式单一连续分配方式固定分区分配方式动态分区分配方式可重定位分区分配方式进程必须整体进入内存且必须连续进程必须整体进入内存且必须连续共同的特点是：共同的特点是：吞吐量低吞吐量低不灵活不灵活存储空间浪费存储空间浪费紧凑代价大紧凑代价大4.3分页存储管理方式分页存储管理方式连续分配的问题：连续分配的问题：形成许多碎片形成许多碎片紧凑带来开销。紧凑带来开销。为解决以上问题，多任务的操作系统现在大多不在为解决以上问题，多任务的操作系统现在大多不在用连用连续分配的方式管理内存，而采用页式、段式或段页式的方式续分配的方式管理内存，而采用页式、段式或段页式的方式管理内存。（目前市场上商业的操作系统大都采用了页式管管理内存。（目前市场上商业的操作系统大都采用了页式管理）硬件理）硬件CPU常提供了多种支持，如常提供了多种支持，如Intel从从80286开始，开始，CPU就开始支持页式、段式或段页式。（一个操作系统只能使用就开始支持页式、段式或段页式。（一个操作系统只能使用其中的一种）其中的一种）打破了原来要求进程连续存储于内存的要求打破了原来要求进程连续存储于内存的要求一、原理一、原理0000001000011000001101001001101101111010011001011110111111001101例：例：16个字节内存，逻辑上分成两组，称为两个页，每页个字节内存，逻辑上分成两组，称为两个页，每页8字节字节。一、原理一、原理0000001000011000001101001001101101111010011001011110111111001101例：例：16个字节内存，逻辑上分成两组，称为两个页，每页个字节内存，逻辑上分成两组，称为两个页，每页8字节字节。地址地址0100可理解为可理解为0页，页内地址为页，页内地址为4地址地址1101可理解为可理解为1页，页内地址为页，页内地址为5这样，一个物理上的一维地址在逻这样，一个物理上的一维地址在逻辑上成为了二维地址（页号，页内地辑上成为了二维地址（页号，页内地址）址）因为是人为的划分，同样问题，因为是人为的划分，同样问题，也可以看成也可以看成4页，每页页，每页4字节（页号为字节（页号为高二位，高二位，00，01，10，11；页内地址；页内地址低二位，低二位，00，01，10，11）在页式管理中：在页式管理中：将程序的逻辑地址空间分成页将程序的逻辑地址空间分成页(Page),(Page),物理内存划分为物理内存划分为固定固定的的同样大小的同样大小的页框页框(page frame)(page frame)。程序加载时，分配其所需的全部。程序加载时，分配其所需的全部页，这些页不必连续。页，这些页不必连续。固定固定：一个计算机系统的内存容量是固定的，一个页的容量在一个计算机系统的内存容量是固定的，一个页的容量在硬件设计时也是确定了的。硬件设计时也是确定了的。二、程序装载二、程序装载在装入一个程序时，需找空闲页框，在装入一个程序时，需找空闲页框，OS要将这些页框分配要将这些页框分配给装入的进程，进程地址空间的每个页占用一个页框，页框给装入的进程，进程地址空间的每个页占用一个页框，页框不要求连续。不要求连续。会出现什么新问题出现？会出现什么新问题出现？三、页面管理中所需要的数据结构三、页面管理中所需要的数据结构1）页框使用表：整个系统一张，描述物理内存空间的分配页框使用表：整个系统一张，描述物理内存空间的分配使用状况。组织：顺序、链表等都可以。使用状况。组织：顺序、链表等都可以。2 2）进程页表：每个进程一张，给出了逻辑页号与物理页号的）进程页表：每个进程一张，给出了逻辑页号与物理页号的映射关系。映射关系。3 3）请求表：整个系统有一张请求表，描述系统内各个进程页）请求表：整个系统有一张请求表，描述系统内各个进程页表的位置和大小。表的位置和大小。（给出的是系统中所有进程的页面表地址）（给出的是系统中所有进程的页面表地址）4 4）当前运行进程的进程页表地址（一般用一个称为）当前运行进程的进程页表地址（一般用一个称为页表寄存页表寄存器器的寄存器存储，在进程切换时，修改该寄存器，）的寄存器存储，在进程切换时，修改该寄存器，）注意：以上术语除注意：以上术语除2）比较一致外，其它的并不统一）比较一致外，其它的并不统一内存内存1000100110100001011页框使用表页框使用表1000进程进程idid103210011请求表请求表21页表地址页表地址3101002110042100531020逻辑页号逻辑页号物理页框物理页框进程进程11的的进程表进程表.四、页面大小的选择四、页面大小的选择 通常几通常几KBKB到几十到几十KBKB，比较典型的是，比较典型的是4K4K、8K8K。较小的页面，减小内碎片，但加大页表的长度，从而形成较小的页面，减小内碎片，但加大页表的长度，从而形成新的开销；新的开销；较大的页面，减小页表的长度，加大内碎片；管理开销小。较大的页面，减小页表的长度，加大内碎片；管理开销小。分页方式下是不是可以完全分页方式下是不是可以完全排除存储空间浪费现象？排除存储空间浪费现象？页面的大小是越大越好，还是越小越好？各自有什么缺点页面的大小是越大越好，还是越小越好？各自有什么缺点？五、地址变换机构支持五、地址变换机构支持逻辑上连续的目标程序在物理上已经不能保证连续，因此指令逻辑上连续的目标程序在物理上已经不能保证连续，因此指令计数器从一个页到另一个页按计数器从一个页到另一个页按PC的实方式就不能正确处理了。所的实方式就不能正确处理了。所以，支持页式管理的以，支持页式管理的机器硬件机器硬件上都有一套地址变换机构完成逻辑上都有一套地址变换机构完成逻辑地址到物理地址的变换。地址到物理地址的变换。任何改进往往可以分为两种情况：任何改进往往可以分为两种情况：1.同样条件下的改进2.不同条件下的改进六、基本地址变换机构六、基本地址变换机构(PC或地址场中的）或地址场中的）逻辑地址逻辑地址页号（页号（3）页内地址（页内地址（100）页表地址页表地址页表寄存器页表寄存器长度长度4 41 15 5.9 9进程页表进程页表 越界中断越界中断+9 9100100物理地址物理地址考虑这样一个问题：在硬件支持下，程序执行性能和传统考虑这样一个问题：在硬件支持下，程序执行性能和传统的有变化吗？执行效果等价吗？的有变化吗？执行效果等价吗？执行速度会下降吗？执行速度会下降吗？每次内存操作需要两次访问内存，必然导致执行速度下降！每次内存操作需要两次访问内存，必然导致执行速度下降！对绝大部分系统，页表是利用内存存储的，因此进行一次对绝大部分系统，页表是利用内存存储的，因此进行一次内存操作需要两次访问内存，第一次读页表、第二次访问数内存操作需要两次访问内存，第一次读页表、第二次访问数据。据。如能将页表装在寄存器中访问就快得多，但如果将全部放如能将页表装在寄存器中访问就快得多，但如果将全部放在寄存器，则寄存器成本大的无法忍受。所以采用一种具有在寄存器，则寄存器成本大的无法忍受。所以采用一种具有并行查找功能的并行查找功能的“联想存储器联想存储器”，根据程序局部性原理，将，根据程序局部性原理，将页表的一部分放在里面。联想存储器的个数一般在页表的一部分放在里面。联想存储器的个数一般在8到到32个。个。（超过（超过32个效果并不明显）个效果并不明显）七、具有快表的地址变换机构七、具有快表的地址变换机构联想存储器是什么东西？！联想存储器是什么东西？！页号（页号（3）逻辑地址逻辑地址页内地址（页内地址（100）页表地址页表地址页表寄存器页表寄存器长度长度4 41 15 5.9 9进程页表进程页表 越界中断越界中断+9 91001001 10 02 2.3 34 41 15 5.9 9页号页号块号块号输入寄存器八、两级和多级页表八、两级和多级页表 现代计算机系统，现代计算机系统，CPUCPU都支持非常大的逻辑地址空间都支持非常大的逻辑地址空间（32-6432-64位的地址空间）。这样页表非常大。如果逻辑地址宽位的地址空间）。这样页表非常大。如果逻辑地址宽度为度为3232位，假设页面大小为位，假设页面大小为4K(24K(21212)，页表项达，页表项达1M1M（2 22020）之多，）之多，每个页表项为每个页表项为3 3个个BYTEBYTE，仅页表项就要占用，仅页表项就要占用3MB3MB的连续内存空的连续内存空间。解决方法：间。解决方法：两级页表两级页表当前需要的页表放在内存，其余的暂存于磁盘当前需要的页表放在内存，其余的暂存于磁盘1)1)两级页表结构（两级页表结构（3232位）位）外层页号（页表目录）外层页内地址（页表）页内地址313122222121121211110 0P1P1（目录位移）（目录位移）P2P2（页表位移）（页表位移）d d（页内位移）（页内位移）第第0 0页页表页页表第第1 1页页表页页表页框号页框号011023页框号页框号011023页目录页表起始地址01n1 12 24 4页表页表页框（内存）页框（内存）物理地址物理地址0 05 5页表地址页表地址0 05 5页框地址页框地址页目录地址寄存器页目录地址寄存器页目录页目录（每个进（每个进程程1 1个）个）目录位移目录位移页内位移页内位移页内地址页内地址+数据存取需通过数据存取需通过3次访问内存次访问内存2 2）多级页表）多级页表 对于对于6464位字长的机器，位字长的机器，即使采用两级页表，进程表的项数仍即使采用两级页表，进程表的项数仍然很大。然很大。例如例如SUNSUN的的SPARCSPARC处理器，支持处理器，支持3 3级页表；而级页表；而MotorolaMotorola的的6803068030处理器甚至支持处理器甚至支持4 4级页表。级页表。九、反置页表（本次整理到此为止）九、反置页表（本次整理到此为止）以上方法，每个进程一张页表，页表按照进程的逻辑地以上方法，每个进程一张页表，页表按照进程的逻辑地址顺序排序，内容为物理块号（页框号）。址顺序排序，内容为物理块号（页框号）。反置页表则按物理块号的顺序排序，内容为隶属的进程反置页表则按物理块号的顺序排序，内容为隶属的进程idid及其页号。实例：及其页号。实例：IBM AS/100IBM AS/100、IBM RISC SYSTEM 6000IBM RISC SYSTEM 6000等。等。在利用反置页表进行地址变换时，是利用进程在利用反置页表进行地址变换时，是利用进程idid和页号，和页号，检索反置页表，实际上可利用联想存储器来检索检索反置页表，实际上可利用联想存储器来检索分页管理的方法，提高内存的利用率，对程序员是透明分页管理的方法，提高内存的利用率，对程序员是透明的；分段管理的方法，满足了程序员在编程和使用上的的；分段管理的方法，满足了程序员在编程和使用上的要求，适应软件开发上的要求。要求，适应软件开发上的要求。将程序的地址空间划分为若干个段将程序的地址空间划分为若干个段(segment)(segment)，程序加，程序加载时，分配其所需的所有段（内存分区），这些段不必载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要连续；物理内存的管理采用动态分区。需要CPUCPU的硬件的硬件支持。支持。4.4 4.4 分段存储管理分段存储管理一、特点：一、特点：1.1.方便编程方便编程 按逻辑关系划分段：有独立的段名，逻辑地址均从按逻辑关系划分段：有独立的段名，逻辑地址均从0 0开始。开始。程序通过分段程序通过分段(segmentation)(segmentation)划分为多个模块，如代码段、数划分为多个模块，如代码段、数据段、共享段。据段、共享段。可以分别编写和编译。可以分别编写和编译。2.2.分段共享：分段共享：可以按段为单位来进行共享可以按段为单位来进行共享3.3.分段保护：分段保护：可以针对不同类型的段采取不同的保护可以针对不同类型的段采取不同的保护4.4.动态链接动态链接：通过动态链接进行代码共享：通过动态链接进行代码共享5.5.动态增长动态增长二、二、段式管理的数据结构：段式管理的数据结构：进程段表：每个进程一张，描述组成进程地址空间的各段进程段表：每个进程一张，描述组成进程地址空间的各段系统段表：系统内所有占用段系统段表：系统内所有占用段空闲段表：内存中所有空闲段，可以结合到系统段表中空闲段表：内存中所有空闲段，可以结合到系统段表中段号段内地址0151631三、地址