第四章存储管理新

1、第四章第四章存储器管理存储器管理Operating System4.14.1存储器的层次结构存储器的层次结构4.24.2程序的装入和链接程序的装入和链接4.34.3连续分配方式连续分配方式4.44.4基本分页存储管理方式基本分页存储管理方式4.54.5基本分段存储管理方式基本分段存储管理方式4.64.6虚拟存储器的基本概念虚拟存储器的基本概念4.74.7请求分页存储管理方式请求分页存储管理方式4.84.8页面置换算法页面置换算法4.94.9请求分段存储管理方式请求分段存储管理方式Operating System 4.14.1 存储器的层次结构存储器的层次结构Operating System4.

2、1.1 4.1.1 多级存储结构多级存储结构 在现代计算机系统在现代计算机系统中，存储器是信息外理中，存储器是信息外理的来源与归宿，占据重的来源与归宿，占据重要位置。但是，在现有要位置。但是，在现有技术条件下，任何一种技术条件下，任何一种存储装置，都无法同时存储装置，都无法同时从速度与容量两方面，从速度与容量两方面，满足用户的需求。实际满足用户的需求。实际上它们组成了一个速度上它们组成了一个速度由快到慢，容量由小到由快到慢，容量由小到大的存储装置层次。大的存储装置层次。 存储器的层次结构存储器的层次结构Operating Systemv 高速缓存高速缓存CacheCache： 少量的、非常快速

3、、昂贵、易变的少量的、非常快速、昂贵、易变的v 寄存器寄存器 访问速度最快，价格十分昂贵访问速度最快，价格十分昂贵v 内存内存RAMRAM： 若干兆字节、中等速度、中等价格、易变的若干兆字节、中等速度、中等价格、易变的 v 磁盘：磁盘： 数百兆或数千兆字节、低速、价廉、不易变的数百兆或数千兆字节、低速、价廉、不易变的 由操作系统协调这些存储器的使用由操作系统协调这些存储器的使用v 磁盘缓存：内存中磁盘缓存：内存中Operating System1)1)主存的分配和管理：当用户需要内存时主存的分配和管理：当用户需要内存时, ,系统为系统为之分配相应的存储空间；不需要时，及时回收，之分配相应的存储

4、空间；不需要时，及时回收，以供其它用户使用。以供其它用户使用。2)2)提高主存储器的利用率：不仅能使多道程序动态提高主存储器的利用率：不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。主存中某个区域的信息。Operating System3)3)“扩充扩充”主存容量：为用户提供比主存物理空间主存容量：为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他的作业大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行。是在这样一个大的存储器中运行。4)4)存储保护：确保多道程序都在各自分配到存储区存储保护：确

5、保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破坏其它域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。作业或系统文件的信息。Operating System1.1.定位（存储分配）定位（存储分配）：为具体的程序和数据等分配：为具体的程序和数据等分配存储单元或存储区工作。存储单元或存储区工作。2.2.映射：映射：把逻辑地址转换为相应的物理地址的过程。把逻辑地址转换为相应的物理地址的过程。3.3.隔离：隔离：按存取权限把合法区与非法区分隔，实现按存取权限把合法区与非法区分隔，实现存储保护。存储保护。Operating Systemv程序员在程序中定义的标识符程序员在程

6、序中定义的标识符v程序符号集合程序符号集合v由程序员自定义由程序员自定义v没有地址的概念没有地址的概念符号指令数据说明I/O说明Operating Systemv 逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址） ： 用户的程序经过汇编或编译后形成目标代码，目标代用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为码通常采用相对地址的形式，其首地址为0 0，其余指，其余指令中的地址都相对于首地址而编址。令中的地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息不能用逻辑地址在内存中读取信息v 物理地址（绝对地址，实地址）物理地址（绝对地址，实地址）

7、内存中存储单元的地址，可直接寻址内存中存储单元的地址，可直接寻址Operating System6.6.地址空间地址空间v 程序用来访问信息所用地址单元的集合程序用来访问信息所用地址单元的集合v 逻辑（相对）地址的集合逻辑（相对）地址的集合v 由编译程序生成由编译程序生成7.7.存储空间存储空间v 主存中物理单元的集合主存中物理单元的集合v 物理（绝对）地址的集合物理（绝对）地址的集合v 由装配程序等生成由装配程序等生成Operating System 4.2 4.2 程序的装入和链接程序的装入和链接Operating System4.2 4.2 程序的装入和链接程序的装入和链接图 4-2-1

8、 对用户程序的处理步骤Operating System4.2.1 4.2.1 程序的装入程序的装入1. 1. 绝对装入方式绝对装入方式 程序中所使用的绝对地址，可在编译或汇编时给程序中所使用的绝对地址，可在编译或汇编时给出，出， 也可由程序员直接赋予。但在由程序员直接给也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，所有地址。因此，通常是宁可在程序中采用符号地址，然后在

9、编译或汇编时，再将这些符号地址转换为绝对然后在编译或汇编时，再将这些符号地址转换为绝对地址。地址。 Operating System图 4-2-2 作业装入内存时的情况Operating System3. 3. 动态运行时装入方式动态运行时装入方式 动态运行时的装入程序，在把装入模块装动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，程序真正要执行时才进行。因此， 装入内存后装入内存后的所有地址都仍是相对地址。的所有地址

10、都仍是相对地址。 Operating System图 4-2-3 程序链接示意图1.1.静态链接方式静态链接方式Operating System2. 2. 装入时动态链接装入时动态链接装入时动态链接方式有以下优点：装入时动态链接方式有以下优点： (1)(1)便于修改和更新。便于修改和更新。 (2) (2) 便于实现对目标模块的共享。便于实现对目标模块的共享。 Operating System3. 3. 运行时动态链接运行时动态链接 这种链接方式是将对某些模块的链接推迟这种链接方式是将对某些模块的链接推迟到执行时才执行。凡在执行过程中未被用到的目到执行时才执行。凡在执行过程中未被用到的目标模块，

11、都不会被调入内存和被链接到装入模块标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。省大量的内存空间。 Operating System 把作业地址空间中使用的逻辑地址变换成把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。内存空间中的物理地址的过程。又称地址映射。如下图，作业如下图，作业i i经过重定位，把地址集合映射到经过重定位，把地址集合映射到以以10001000为始址的内存中，作为作业为始址的内存中，作为作业i i的存储空间。的存储空间。Operating Syst

12、em1)1)静态重定位静态重定位: :当用户程序被装入内存时，一次当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）作再转换（一般在装入内存时由软件完成）作业业i i在执行前一次变址，直到该作业完成退出在执行前一次变址，直到该作业完成退出内存为止。内存为止。2)2)动态重定位动态重定位Operating System 在程序运行过程中要访问数据时再进行地址在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。上需要重

13、定位寄存器的支持。Operating Systemv 重定位寄存器重定位寄存器：在执行一条指令取操作数时，：在执行一条指令取操作数时，要将指令给出的有效地址要将指令给出的有效地址(500)(500)与重定位寄与重定位寄存器中的内容（存器中的内容（10001000）相加，得访问地址）相加，得访问地址（15001500），从而实现了地址动态修改。），从而实现了地址动态修改。v 映象方式映象方式：采用页表来描述虚、实页面的对：采用页表来描述虚、实页面的对应关系应关系 。Operating System4.3 4.3 连续分配方式连续分配方式 Operating Systemv 在单道环境下，不管是单

14、用户系统还是单道批处在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：可以划分为三部分：系统区、用户区、空闲区系统区、用户区、空闲区。用户占用区是一个连续的存储区所以又称单一连用户占用区是一个连续的存储区所以又称单一连续区存储管理续区存储管理。v 单用户系统在一段时间内，只有一个进程在内存，单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存故内存分配管理十分简单，内存利用率低。内存分

15、为两个区域，一个供操作系统使用，一个供用分为两个区域，一个供操作系统使用，一个供用户使用户使用Operating System用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0图图 4-3-1 4-3-1 单一连续区存储分配示意图单一连续区存储分配示意图Operating System 单一连续区分配采用静态分配和静态重定位单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直方式，亦即作业或进程一旦进

16、入主存，就一直等到它运行结束后才能释放主存。如下图所示等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。绝对地址是否超越，即可达到保护系统的目的。Operating SystemOperating Systemv 不支持多道。不支持多道。v 主存利用率不高。主存利用率不高。v 程序的运行受主存容量限制。程序的运行受主存容量限制。Operating System 分分区式管理是满足多道程序的最简单的存储管区式管理是满足多道程序的最简单的存储管理方案。它的基本思想是将内存划分成若干个理方

17、案。它的基本思想是将内存划分成若干个连续区域，称为分区。每个分区只能存储一个连续区域，称为分区。每个分区只能存储一个程序，而且程序也只能在它所驻留的分区中运程序，而且程序也只能在它所驻留的分区中运行。行。Operating Systemv 预先把可分配的主存储器空间分割成若干个连续区预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业。区装一个且只能装一个作业。v 存储分配：如果有一个空闲区存储分配：如果

18、有一个空闲区, , 则分配给进程。则分配给进程。 1. 1. 固定分区固定分区Operating System分区分区4分区分区3分区分区2分区分区1操作系统操作系统多个等待队列多个等待队列单个等待队列单个等待队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统图图 4-3-2 4-3-2 固定分区示意图固定分区示意图Operating System 2. 2.内存分配管理内存分配管理图图 4-3-3 4-3-3 固定分区使用表固定分区使用表通过设置分区说明表，内存分配简单通过设置分区说明表，内存分配简单缺点：内存利用率不高缺点：内存利用率不高Operating Systemv 基本思

19、想：内存不是预先划分好的，而是根据进程基本思想：内存不是预先划分好的，而是根据进程的需求和内存空间的使用情况来决定是否分配。若的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。否则令其等待主存空间。v 内存管理：设置内存空闲块表内存管理：设置内存空闲块表记录了空闲区起记录了空闲区起始地址和长度始地址和长度v 内存分配：动态分配内存分配：动态分配v 内存回收：当某一块归还后，前后空间合并，修改内存回收：当某一块归还后，前后空间合并，修改内存空闲块表内存空闲块表Operating Syste

20、m(1)(1)分区分配表（见图分区分配表（见图 4-3-54-3-5）(2) (2) 空闲分区链空闲分区链图图 4-3-4 4-3-4 空闲链结构空闲链结构Operating System0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表：分区分配表：图图 4-3-54-3-5分区分配表分区分配表Operating System0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区

21、表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98KOperating System1) 1) 分配内存分配内存 图图 4-3-6 4-3-6 内存分配流程内存分配流程Operating System 2) 2)回收内存回收内存图图 4-3-7 4-3-7 内存回收时的情况内存回收时的情况Operating Systemv 为了实现动态分配，系统设立空闲分区链表：为了实现动态分配，系统设立空闲分区链表：每个空闲块的前后两个单元，放置必要的说明每个空

22、闲块的前后两个单元，放置必要的说明信息和指针。系统只要设立一个链首指针，指信息和指针。系统只要设立一个链首指针，指向第一个空闲块即可。分配程序可以依照自由向第一个空闲块即可。分配程序可以依照自由块链表，来查找适合的空闲块进行分配。（如块链表，来查找适合的空闲块进行分配。（如下图）下图）Operating System按空闲块链接的方式不同，可以有以下四按空闲块链接的方式不同，可以有以下四种算法：种算法：v 最佳适应法最佳适应法v 最坏适应法最坏适应法v 首次适应法首次适应法v 循环首次适应法（下次适应法）循环首次适应法（下次适应法）v 快速适应算法快速适应算法Operating Systemv

23、 所有的空闲分区按其容量以从小到大的顺序形所有的空闲分区按其容量以从小到大的顺序形成一个空闲分区链，接到内存申请时，在空闲成一个空闲分区链，接到内存申请时，在空闲分区链中找到一个不小于请求的最小空块进行分区链中找到一个不小于请求的最小空块进行分配。分配。v 为作业选择分区时总是寻找其大小最接近于作为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。业所要求的存储区域。v 特点：用最小空间满足要求。特点：用最小空间满足要求。v 缺点：存储器中会留下难以利用的小空闲分区缺点：存储器中会留下难以利用的小空闲分区（碎片）。（碎片）。Operating Systemv 所有的空闲分区按其容量以从

24、大到小的顺所有的空闲分区按其容量以从大到小的顺序形成一个空闲分区链，接到内存申请时，序形成一个空闲分区链，接到内存申请时，在空闲分区链中找到一个不小于请求的最在空闲分区链中找到一个不小于请求的最大空块进行分配，与最佳适应法相反，它大空块进行分配，与最佳适应法相反，它在作业选择存储块时，总是寻找最大的空在作业选择存储块时，总是寻找最大的空白区。白区。v 特点：当分割后空闲块仍为较大空块。特点：当分割后空闲块仍为较大空块。Operating System3)3)首次适应法：首次适应法： 空闲分区链以地址递增的次序链接，为作业选择空闲分区链以地址递增的次序链接，为作业选择分区时总是从链首开始查找，只

25、要找到可以容分区时总是从链首开始查找，只要找到可以容纳该作业的空白块，就把该空白块分配给该作纳该作业的空白块，就把该空白块分配给该作业。业。4)4)循环首次适应法循环首次适应法 类似首次适应法，每次查找分区时，总是从上次类似首次适应法，每次查找分区时，总是从上次查找结束的地方开始，找到一个足够大的空白查找结束的地方开始，找到一个足够大的空白区分配。区分配。5 5）快速适应算法：按容量大小分类）快速适应算法：按容量大小分类Operating Systemv 经过一段时间的分配回收后，内存中存在很多很经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分小的空闲块。它

26、们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被配要求；但其总和满足分配要求。这些空闲块被称为碎片称为碎片v 造成存储资源的浪费造成存储资源的浪费碎片问题的解决碎片问题的解决v 紧凑技术：通过在内存移动程序，将所有小的空紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域闲区域合并为大的空闲区域 （紧缩技术，紧致技术，浮动技术，搬家技术）（紧缩技术，紧致技术，浮动技术，搬家技术）v 问题：开销大；移动时机问题：开销大；移动时机Operating System 优点：优点： 便于动态申请内存便于动态申请内存 便于共享内存便于共享内存 便于动态链接便于动态链接缺

27、点：缺点：碎片问题碎片问题( (外碎片外碎片) )，内存利用率不高，受，内存利用率不高，受实际内存容量限制实际内存容量限制6.6.分区式存储管理的优缺点分区式存储管理的优缺点Operating System4.3.4伙伴系统4.3.5哈希算法Operating System1. 1. 动态重定位的引入动态重定位的引入图图 4-3-1 4-3-1 紧凑的示意紧凑的示意Operating System2. 2. 动态重定位的实现动态重定位的实现图图 4-3-2 4-3-2 动态重定位示意图动态重定位示意图Operating System图图 4-3-3 4-3-3 动态分区分配算法流程图动态分区分

28、配算法流程图Operating Systemv 优点优点: :解决了可变分区分配所引入的解决了可变分区分配所引入的“外零头外零头”问题。消除内存碎片，提高内存利用率。问题。消除内存碎片，提高内存利用率。v 缺点缺点: :提高硬件成本，紧凑时花费时间。提高硬件成本，紧凑时花费时间。Operating System 用可变分区用可变分区( (动态重定位动态重定位) )方式管理主存方式管理主存时时, ,假定主存中按地址顺序依次有假定主存中按地址顺序依次有5 5个空闲个空闲区区, ,空闲区的大小依次为空闲区的大小依次为32K,10K,5K,228K32K,10K,5K,228K和和100K,100K,

29、现有现有5 5个作业个作业A,B,C,D,E.A,B,C,D,E.它们各需它们各需主存主存1K,10K,108K,28K1K,10K,108K,28K和和115K.115K.若采用首次若采用首次适应算法能把这适应算法能把这5 5个作业按顺序全部装入主个作业按顺序全部装入主存吗存吗? ?你认为怎样的次序装入这你认为怎样的次序装入这5 5个作业可个作业可使主存的利用率最高使主存的利用率最高? ?Operating System1. 1. 对换的引入对换的引入 所谓所谓“对换对换”， 是指把内存中暂时不能运行的是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾进程或者暂时不

30、用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。有效措施。 Operating System2. 2. 对换空间的管理对换空间的管理 为了能对对换区中的空闲盘块进行管理，在系统为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同式与内存在动态分区分配方式中所用数

31、据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，个表目中应包含两项， 即对换区的首址及其大小，它们的即对换区的首址及其大小，它们的单位是盘块号和盘块数。单位是盘块号和盘块数。 Operating System3. 3. 进程的换出与换入进程的换出与换入 (1) (1) 进程的换出。进程的换出。 每当一进程由于创建子进程而需要更多的内存空每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进间，但又无足够的内存空间等情况发生时，系统应将某进程换出。程换出。 其过程是：系统

32、首先选择处于阻塞状态且优先级其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。制块做相应的修改。 Operating System (2) (2) 进程的换入。进程的换入。 系统应定时地查看所有进程的状态，从中找出系统应定时地查看所有进程的状态，从中找出“就绪就绪”状态但已换出的进程，

33、将其中换出时间状态但已换出的进程，将其中换出时间( (换出到换出到磁盘上磁盘上) )最久的进程作为换入进程，将之换入，直至已无最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。可换入的进程或无可换出的进程为止。 Operating System Operating Systemv在动态分区的存储空间中，在动态分区的存储空间中， 存在存在“零头零头”问题。尽管采用问题。尽管采用“紧凑紧凑”技术可以解决这技术可以解决这个问题，但要为移动大量信息花去不少的个问题，但要为移动大量信息花去不少的处理机时间，代价较高。（处理机时间，代价较高。（离散方式离散方式）v分页：把用户程序

34、按逻辑页划分成大小相分页：把用户程序按逻辑页划分成大小相等的部分，称为页或虚页。从等的部分，称为页或虚页。从0 0开始编制开始编制页号，页内地址是相对于页号，页内地址是相对于0 0编址。编址。Operating Systemv 块：内存按页的大小划分为大小相等的区域，称为块：内存按页的大小划分为大小相等的区域，称为内存块（物理页面，页框内存块（物理页面，页框) )。v 内存分配：以页为单位进行分配，并按作业的页数内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻，多少来分配。逻辑上相邻的页，物理上不一定相邻，通过页表把作业的各个页面与页框对应起来。通过页表

35、把作业的各个页面与页框对应起来。 Operating System 1.1.页面和物理块页面和物理块n 分页存储管理，是将一个进程的逻辑地址空间分成分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加若干个大小相等的片，称为页面或页，并为各页加以编号。以编号。页面的大小应选择得适中，且页面大小应页面的大小应选择得适中，且页面大小应是是2 2的幂，通常为的幂，通常为512B512B到到8KB8KB。n 把内存空间分成与页面相同大小的若干个存储块，把内存空间分成与页面相同大小的若干个存储块，称为称为( (物理物理) )块或页框块或页框(frame)(frame)

36、，在为进程分配内存时，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。以不相邻接的物理块中。n “页内碎片页内碎片”-最后一页不满。最后一页不满。 Operating System2. 2. 地址结构地址结构 分页地址中的地址结构如下：分页地址中的地址结构如下： 页号P位移量W3112110 对某特定机器，其地址结构是一定的。若给定一个逻对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为辑地址空间中的地址为A A，页面的大小为，页面的大小为L L，则页号，则页号P P和页内和页内地址地址d d可按

37、下式求得：可按下式求得： MODLAdLAINTPOperating Systemv 页表，即为页面映射表，作用是实现从页号到物页表，即为页面映射表，作用是实现从页号到物理块号的地址映射。理块号的地址映射。v 一个页表中包含若干个表项，表项的自然序号对一个页表中包含若干个表项，表项的自然序号对应于用户程序中的页号，表目中的块号是该页对应于用户程序中的页号，表目中的块号是该页对应的物理块号。应的物理块号。v 页表的每一个表项除了包含指向页框的指针外，页表的每一个表项除了包含指向页框的指针外，还包括一个存取控制字段。还包括一个存取控制字段。Operating System分页管理中页与页框的对应分

38、页管理中页与页框的对应关系示意图关系示意图Operating System 1. 1. 基本的地址变换机构基本的地址变换机构图 4-4-2分页系统的地址变换机构 Operating System2. 2. 地址变换过程地址变换过程v 例如指令例如指令 LOAD 1,2500 LOAD 1,2500 的地址变换过程如下：的地址变换过程如下： 把虚拟地址把虚拟地址25002500转换成页号转换成页号P=2P=2，位移量，位移量W=452W=452； 如果页号如果页号2 2大于页表大小，则中断；否则继续；大于页表大小，则中断；否则继续； 页号页号2 2与页表起址与页表起址10001000运算（运算（

39、1000+21000+2* *2020，设页表，设页表项大小为项大小为2020）得到页表项地址为）得到页表项地址为10401040；Operating Systemv 从页表中读取块号从页表中读取块号8 8；v 根据页表的根据页表的“存取控制存取控制”判断该指令是否被允判断该指令是否被允许访问内存，如果不允许，则中断；否则继续；许访问内存，如果不允许，则中断；否则继续；v 块号块号8 8与位移量与位移量452452运算（运算（8 8* *1024+452=96441024+452=9644，10241024为页面大小）得到物理地址为页面大小）得到物理地址96449644；v 把数字把数字1 1

40、写进内存地址写进内存地址96449644单元中。单元中。Operating System1)1)页表：系统为每个进程建立一个页表，页表给出页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系逻辑页号和具体内存块号相应的关系 页表放在内存，属于进程的现场信息页表放在内存，属于进程的现场信息2)2)内存的分配与回收内存的分配与回收Operating System 4. 4.快表快表 如果把页表放在主存中，无疑会影响系统的如果把页表放在主存中，无疑会影响系统的性能。这是因为每次访问主存，首先必须访问性能。这是因为每次访问主存，首先必须访问页表，读出页表项，之后根据形成的实际地址

41、页表，读出页表项，之后根据形成的实际地址再访问主存，这样使访问主存的次数加倍，因再访问主存，这样使访问主存的次数加倍，因而使总的处理速度明显下降。而使总的处理速度明显下降。 为了解决这个问题人们采用一组联想寄存器，为了解决这个问题人们采用一组联想寄存器，就是就是“快表快表”，存放当前访问过的页的页表项，存放当前访问过的页的页表项，每次访问主存时，首先查找快表，若找到所需每次访问主存时，首先查找快表，若找到所需的页表项，则快速形成物理地址。否则从页表的页表项，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页表项写入快中查找后形成物理地址，同时把页表项写入快表。如果设计得当，快表的命中

42、率可以很高。表。如果设计得当，快表的命中率可以很高。 Operating System图图 4-4-3 4-4-3 具有快表的地址变换机构具有快表的地址变换机构Operating System 现代的大多数计算机系统，都支持非现代的大多数计算机系统，都支持非常大的逻辑地址空间常大的逻辑地址空间(2(23232到到2 26464) )。页表就变得。页表就变得非常大，要占用相当大的内存空间。可采用两非常大，要占用相当大的内存空间。可采用两个方法来解决这一问题：个方法来解决这一问题： 采用离散分配方采用离散分配方式来解决难以找到一块连续的大内存空间的问式来解决难以找到一块连续的大内存空间的问题：题：

43、 只将当前需要的部分页表项调入内存，只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。其余的页表项仍驻留在磁盘上，需要时再调入。 Operating System1. 两级页表逻辑地址结构可描述如下： Operating System 图 4-4-4 两级页表结构 Operating System页目录地址页目录地址目录位移目录位移页表位移页表位移页位移页位移虚拟地址虚拟地址页表地址页表地址.页目录（每进程一个）页目录（每进程一个）块号块号.页表页表代码或数据代码或数据.内存块内存块二级页表结构及地址映射二级页表结构及地址映射+Operating Systemv 32

44、位 进程页表多大？设：页面大小为4K 用户空间 2GB则：一个进程 219页设：每个内存块号 4字节则：进程页表 512页v 结论：一个进程的页表的各页之间可以不连续存放v 解决：页表本身使用地址索引页目录Operating System 4.5 4.5 分段存储管理分段存储管理Operating System 在分页存储系统中，作业的地址空间是一维线在分页存储系统中，作业的地址空间是一维线性的，这破坏了程序内部天然的逻辑结构性的，这破坏了程序内部天然的逻辑结构, ,造成共享、造成共享、保护的困难。引入分段存储管理方式，保护的困难。引入分段存储管理方式， 主要是为了主要是为了满足用户和程序员的

45、下述需要：满足用户和程序员的下述需要： 1) 1) 方便编程方便编程 2) 2) 信息共享信息共享 3) 3) 信息保护信息保护 4) 4) 动态增长动态增长 5) 5) 动态链接动态链接 Operating System.0S工作区段工作区段B主程序段主程序段M.0EP子程序段子程序段X0K.CALLXE.CALLYFCALLA116.0FL子程序段子程序段Y0116N数组数组A12345.Operating System1.分段分段分段地址中的地址具有如下结构：分段地址中的地址具有如下结构： 段号段内地址31 16 15 0Operating System 它记录了段号，段的首（地）址和长

46、度它记录了段号，段的首（地）址和长度之间的关系之间的关系 每一个程序设置一个段表，放在内存每一个程序设置一个段表，放在内存, ,属属于进程的现场信息于进程的现场信息段号段号012段首址段首址段长度段长度58K20K100K110K260K140KOperating System操作系统操作系统.B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存K3200P1500L6000N8000S5000长度长度段地址段地址01234操作系统操作系统分段管理中作业分段管理中作业i i与段表、存储空间的关系与段表、

47、存储空间的关系Operating Systemv系统设置段表寄存器系统设置段表寄存器v段表始址：段表始址： 用于保存正在运行进程的段表的始址用于保存正在运行进程的段表的始址v段表长度：段表长度： 用于保存正在运行进程的段表的长度（例如用于保存正在运行进程的段表的长度（例如上图的段表长度为上图的段表长度为3 3）Operating System图 4-5-2 分段系统的地址变换过程Operating System5. 5. 分页和分段的主要区别分页和分段的主要区别 (1) (1) 页是信息的物理单位，段则是信息的逻辑单页是信息的物理单位，段则是信息的逻辑单位。位。(2) (2) 页的大小固定且由

48、系统决定，而段的长度却页的大小固定且由系统决定，而段的长度却不固定，决定于用户所编写的程序。不固定，决定于用户所编写的程序。 (3) (3) 分页的作业地址空间是一维的，即单一的线分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的。性地址空间，分段的作业地址空间则是二维的。Operating System图 4-5-3 分页系统中共享editor的示意图Operating System图 4-5-4 分段系统中共享editor的示意图 Operating System 分段管理的优缺点分段管理的优缺点 优点： 便于动态申请内存 管理和使用统一化 便于共享 便于动态链

49、接缺点：产生碎片Operating System 1.1.产生背景：产生背景： 结合了段式与页式二者优点结合了段式与页式二者优点 克服了二者的缺点克服了二者的缺点Operating System 用户程序划分：按段式划分（对用户来讲，用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页按段的逻辑关系进行划分；对系统讲，按页划分每一段）。用户程序分段，段内分页。划分每一段）。用户程序分段，段内分页。 逻辑地址：逻辑地址：段号段号段内地址段内地址页号页号页内地址页内地址Operating System1.1.段表：记录了每一段的页表始址和页表长段表：记录了每一段的页表始址和

50、页表长度度2.2.页表：记录了逻辑页号与内存块号的对应页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多关系（每一段有一个，一个程序可能有多个页表）个页表）3.3.空块管理：同页式管理空块管理：同页式管理4.4.分配：同页式管理分配：同页式管理Operating System 一个程序首先被划分成若干程序段，一个程序首先被划分成若干程序段，每一段给予不同的分段标识符然后，对每一段给予不同的分段标识符然后，对每一分段又分成若干个固定大小的页面。每一分段又分成若干个固定大小的页面。如下图如下图(a)(a)所示，系统中的一个作业的地所示，系统中的一个作业的地址空间结构页面尺寸为

51、字节，该作址空间结构页面尺寸为字节，该作业有三个分段，第一段为业有三个分段，第一段为15K15K字节，占字节，占4 4页，最后一页只有页，最后一页只有1K1K未用；其它段同理。未用；其它段同理。未足一页大小的补为一页。未足一页大小的补为一页。Operating System作业的作业的地址空间和地址结构地址空间和地址结构 1.作业地址空间:如图（a）所示2. 地址结构如图（b）所示页Operating SystemOperating SystemOperating Systemv 从控制寄存器读取段表始址，找到段表；从控制寄存器读取段表始址，找到段表；v 段号段表始址段号段表始址 得到段描述子

52、地址；得到段描述子地址；v 从段描述子读取页表始址，找到页表；从段描述子读取页表始址，找到页表；v 页号页表始址页号页表始址 得到页描述子地址；得到页描述子地址；v 从页描述子读取物理块号；从页描述子读取物理块号；v 物理块号页内位移量物理块号页内位移量 得到物理地址。得到物理地址。 上述的地址变换至少要访问主存三次，这将上述的地址变换至少要访问主存三次，这将使执行程序的速度大大降低。为了解决上述问使执行程序的速度大大降低。为了解决上述问题，可以采取前边讲过的题，可以采取前边讲过的“快表快表”技术。技术。Operating SystemOperating System课堂练习题课堂练习题Ope

53、rating Systemv某虚拟存储器的用户空间共有某虚拟存储器的用户空间共有3232个页面，每页个页面，每页1KB1KB，主存主存16KB16KB。假定某时刻，系统为用户的第。假定某时刻，系统为用户的第0 0，1 1，2 2，3 3页分配的块号分别为页分配的块号分别为5 5，1010，4 4，7 7，而该用户的作，而该用户的作业长度为业长度为6 6页，试将十六进制的虚拟地址页，试将十六进制的虚拟地址0A5C0A5C和和103C103C转化成物理地址。转化成物理地址。Operating System3.3.对于如下表所示的段表，请将逻辑地址对于如下表所示的段表，请将逻辑地址0,137,1,4

54、000,2,3600,5,2300,137,1,4000,2,3600,5,230转转换成物理地址。换成物理地址。Operating System4.64.6 虚拟存储器虚拟存储器Operating System问题的提出问题的提出 : :程序大于内存程序大于内存 程序暂时不执行或运行完是否还要占用内存程序暂时不执行或运行完是否还要占用内存 虚拟存储器的基本思想是：程序、数据、堆栈虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘使用的部分保留在内存，而把其它部分保存在磁盘

55、上，并在需要时在内存和磁盘之间动态交换。上，并在需要时在内存和磁盘之间动态交换。 虚拟存储器支持多道程序设计技术。虚拟存储器支持多道程序设计技术。Operating System驻留性驻留性一次性一次性 Operating Systemv 程序局部性原理程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面局部性，表现在时间与空间两方面v 时间局部性：时间局部性： 一条指令被执行了，则在不久的将来它可能再被一条指令被执行了，则在不久的将来它可能再被执行执行v 空间局部性：空间局部性： 若某一存储单元被使用，则在一定时间

56、内，与该若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用存储单元相邻的单元可能被使用 3. 3.局部性原理局部性原理Operating Systemv具有请求调入功能和置换功能具有请求调入功能和置换功能, ,能从逻辑上对能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储内存容量进行扩充的存储器系统。虚拟存储器就是一个地址空间，且具有比实存大得多器就是一个地址空间，且具有比实存大得多的容量。的容量。Operating Systemv对用户：指令地址部分所限定的比实存对用户：指令地址部分所限定的比实存大得多的地址实间。大得多的地址实间。v对系统：借助于各种表格机构，体现虚对系

57、统：借助于各种表格机构，体现虚拟实间。拟实间。 Operating Systemv 一个虚拟存储器的最大容量是由计算机的地址一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若结构确定的。如：若CPUCPU的有效地址长度为的有效地址长度为3232位，位，则程序可以寻址范围是则程序可以寻址范围是0 0(232)-1 (232)-1 ，即虚存，即虚存容量为容量为 4GB4GB。v 虚拟存储器的容量与主存的实际大小没有直接虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。的关系，而是由主存与辅存的容量之和所确定。Operating System虚存：把内存与外存

58、有机的结合起来使用，虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的从而得到一个容量很大的“内存内存”，这就是，这就是虚存虚存实现思想：当进程运行时，先将一部分程序实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它行的指令不在内存时，由系统自动完成将它们从外存调入内存工作们从外存调入内存工作目的：提高内存利用率目的：提高内存利用率Operating Systemv多次性多次性v对换性对换性v虚拟性虚拟性Operating System4.7.1 4.7.1 请求分页中的数据结构及硬

59、件支持请求分页中的数据结构及硬件支持一、页表机制一、页表机制页表项：页表项：二、缺页中断机构：可在指令执行期间产生（如图二、缺页中断机构：可在指令执行期间产生（如图4-4-2323），转入缺页中断处理程序。），转入缺页中断处理程序。三、地址变换机构三、地址变换机构比较简单分页机制，增加了中断处理，比较简单分页机制，增加了中断处理，图图4.244.24页号页号物理块物理块号号状态位状态位P P访问字访问字段段A A修改位修改位M M外存地外存地址址Operating SystemOperating Systemv一、最小物理块数一、最小物理块数不同的作业要求不同。不同的作业要求不同。如：允许间接

60、寻址：则如：允许间接寻址：则至少要求至少要求3 3个物理块。个物理块。Mov A, B Mov A, B Operating Systemv 二、页面分配和置换策略。二、页面分配和置换策略。1 1固定分配局部置换。固定分配局部置换。 缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数.(.(少：置换少：置换率高率高 多：浪费多：浪费) )2.2.可变分配全局置换可变分配全局置换3.3.可变分配局部置换可变分配局部置换 根据进程的缺页率进行页面数调整，进程之根据进程的缺页率进行页面数调整，进程之间相互不会影响。间相互不会影响。Operating System1 1平均分配算法平均分配算法2