第四章存储管理

1、第四章存储管理操作系统原理操作系统原理第四章第四章 存储管理存储管理简介简介 操作系统中的存储管理主要是指对主存的管理。操作系统中的存储管理主要是指对主存的管理。 主存即内存，是指处理机可以直接存取指令和数主存即内存，是指处理机可以直接存取指令和数据的存储器。主存是现代操作系统进行操作的中心，据的存储器。主存是现代操作系统进行操作的中心，是计算机系统中的一种重要资源。作为系统资源管理是计算机系统中的一种重要资源。作为系统资源管理程序的操作系统，必须对主存施以有效、精心的管理。程序的操作系统，必须对主存施以有效、精心的管理。 多道程序设计技术出现后，对存储管理提出了更多道程序设计技术出现后，对存

2、储管理提出了更高要求。一方面，要使主存得到充分、有效的利用；高要求。一方面，要使主存得到充分、有效的利用；另一方面要为用户提供方便的使用环境。另一方面要为用户提供方便的使用环境。 4.1 存储器管理的基本概念存储器管理的基本概念4.1.1 4.1.1 存储管理研究的课题存储管理研究的课题计算机的存储设备可以分为三个层次：计算机的存储设备可以分为三个层次：p高速昂贵而易变（断电后信息丢失）的高速缓存和高速昂贵而易变（断电后信息丢失）的高速缓存和寄存器，数量很少；寄存器，数量很少；p速度快，价格高且易变的主存储器速度快，价格高且易变的主存储器(RAM)；p速度较低，价格低廉，但不易变的辅存如软、硬

3、磁速度较低，价格低廉，但不易变的辅存如软、硬磁盘、光盘等。盘、光盘等。 4.1 存储器管理的基本概念存储器管理的基本概念目前关于存储管理的主要研究课题归纳为四个方面目前关于存储管理的主要研究课题归纳为四个方面p存储分配问题：重点是研究存储共享和各种分配算存储分配问题：重点是研究存储共享和各种分配算法；法；记住主存各个位置的状态，哪些空间已分配，哪些空间记住主存各个位置的状态，哪些空间已分配，哪些空间设置相应的数据结构记录分配。设置相应的数据结构记录分配。按一定的策略为用户作业分配内存。按一定的策略为用户作业分配内存。实施分配，当用户作业申请时，按需分配，修改相应的实施分配，当用户作业申请时，按

4、需分配，修改相应的表格。表格。回收内存，作业完成，退出主存，修改相应的分配表格。回收内存，作业完成，退出主存，修改相应的分配表格。p地址再定位问题：研究各种地址变换机构，以及静地址再定位问题：研究各种地址变换机构，以及静态和动态再定位方法。地址重定位、地址映射。态和动态再定位方法。地址重定位、地址映射。4.1 存储器管理的基本概念存储器管理的基本概念p存储保护问题：研究保护各类程序、数据区的方法。存储保护问题：研究保护各类程序、数据区的方法。 为多个程序共享内存提供保障，使在内存中的各为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相道程序，只能访问它自己

5、的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行。通常由硬件完成保护功能，由软件其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。辅助实现。p存储扩充问题：主要研究虚拟存储器问题及其各种存储扩充问题：主要研究虚拟存储器问题及其各种调度算法。调度算法。一方面需要提高主存利用率，共享主存；一方面需要提高主存利用率，共享主存；另一方面为用户提供一个远远大于主存的地址空间。另一方面为用户提供一个远远大于主存的地址空间。4.1 存储器管理的基本概念存储器管理的基本概念4.1.2 4.1.2 地址再定位地址再定位1.地

6、址空间和存储空间地址空间和存储空间p地址空间（逻辑空间）：一个目标程序所限定的地地址空间（逻辑空间）：一个目标程序所限定的地址范围，成为该作业的地址空间。是虚的概念。址范围，成为该作业的地址空间。是虚的概念。相对地址（逻辑地址）：地址空间的地址都是相对于起相对地址（逻辑地址）：地址空间的地址都是相对于起始地址始地址0为基准量的，称为相对地址。为基准量的，称为相对地址。绝对地址（物理地址）：指存储控制部件能识别存储单绝对地址（物理地址）：指存储控制部件能识别存储单元的号。元的号。 p存储空间（物理空间）：所有内存中实际的物理存存储空间（物理空间）：所有内存中实际的物理存储单元的集合。存储空间是一

7、个储单元的集合。存储空间是一个“实实”的物体。的物体。4.1 存储器管理的基本概念存储器管理的基本概念名空间名空间符号指令符号指令数据说明数据说明I/O说明说明地址空间地址空间目目 标标程程 序序（装配模块）（装配模块）存储空间存储空间0 x01MB4.1 存储器管理的基本概念存储器管理的基本概念2.地址的再定位地址的再定位 一个逻辑地址空间的程序装入到物理地址空间的一个逻辑地址空间的程序装入到物理地址空间的时候，由于两个空间不一致，需要进行地址变换，或时候，由于两个空间不一致，需要进行地址变换，或称地址映射，即地址的再定位。地址再定位有静态再称地址映射，即地址的再定位。地址再定位有静态再定位

8、和动态再定位两种。定位和动态再定位两种。p静态再定位是在程序执行之前进行地址再定位。通静态再定位是在程序执行之前进行地址再定位。通常由装配程序完成。常由装配程序完成。4.1 存储器管理的基本概念存储器管理的基本概念例例 现有一个作业现有一个作业A，它需要，它需要20K空间，两次运行分别空间，两次运行分别被装入主存中的不同地址。被装入主存中的不同地址。A作业的地址空间作业的地址空间0K20K操作系统操作系统操作系统操作系统主存100K120KA作业的地址空间作业的地址空间0K20K主存120K140K4.1 存储器管理的基本概念存储器管理的基本概念p优点：容易实现，无需硬件支持，只要求程序本身优

9、点：容易实现，无需硬件支持，只要求程序本身时可再定位的。时可再定位的。p缺点：缺点：程序经地址再定位后就不能再移动了，因而不能重新分程序经地址再定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用；配内存，不利于内存的有效利用；程序在存储空间中只能连续分配，不能分布在内存的不程序在存储空间中只能连续分配，不能分布在内存的不同区域；同区域；若干用户很难共享内存中的同一程序，如若共享同一程若干用户很难共享内存中的同一程序，如若共享同一程序，则各用户必须使用自己的副本。序，则各用户必须使用自己的副本。4.1 存储器管理的基本概念存储器管理的基本概念p动态再定位是在程序执行期间，在每次存储

10、访问之动态再定位是在程序执行期间，在每次存储访问之前进行的。作业在存储空间中的位置是装入时确定前进行的。作业在存储空间中的位置是装入时确定的，但在运行时允许的，但在运行时允许“搬家搬家”和附加存储空间。和附加存储空间。4.1 存储器管理的基本概念存储器管理的基本概念p优点：优点：在执行过程中，用户程序在内存中可以移动，这有利于在执行过程中，用户程序在内存中可以移动，这有利于内存的充分利用；内存的充分利用；程序不必连续存放在内存中，可以分散在内存的若干个程序不必连续存放在内存中，可以分散在内存的若干个不同区域，这只需增加几对基址限长寄存器，每对寄不同区域，这只需增加几对基址限长寄存器，每对寄存器

11、对应一个区域；存器对应一个区域；若干用户可以共享同一程序。若干用户可以共享同一程序。p缺点：需要附加的硬件支持，实现存储管理的软件缺点：需要附加的硬件支持，实现存储管理的软件算法比较复杂。算法比较复杂。4.1 存储器管理的基本概念存储器管理的基本概念4.1.3 4.1.3 虚拟存储器概念的引入虚拟存储器概念的引入虚拟存储器的提出虚拟存储器的提出Virtual Store（VS）1.解决小内存运行大作业问题解决小内存运行大作业问题 连续区，分区的管理，分页式管理中，如作业长连续区，分区的管理，分页式管理中，如作业长大于内存的用户区长，将无法运行该作业，因为作业大于内存的用户区长，将无法运行该作业

12、，因为作业一次全装入主存。在多道环境下，要求内存放入多个一次全装入主存。在多道环境下，要求内存放入多个作业，问题更为突出。作业，问题更为突出。2.用户扩大内存的要求，以便有效地支持多道系统和用户扩大内存的要求，以便有效地支持多道系统和大型程序的需要由于内存硬件价格贵，因此利用大型程序的需要由于内存硬件价格贵，因此利用VS，可以从逻辑上扩充主存。可以从逻辑上扩充主存。4.1 存储器管理的基本概念存储器管理的基本概念3.程序的访问局部性程序的访问局部性p时间的局部性：刚刚访问的部分，可能马上还要访时间的局部性：刚刚访问的部分，可能马上还要访问。例如程序中有大量的循环语句。问。例如程序中有大量的循环

13、语句。p空间的局部性：被访问部分的邻近区域，可能马上空间的局部性：被访问部分的邻近区域，可能马上就要被访问（程序的顺序性）。就要被访问（程序的顺序性）。p程序段的互斥性：不是每个程序段在执行时同时都程序段的互斥性：不是每个程序段在执行时同时都运行到。运行到。4.1 存储器管理的基本概念存储器管理的基本概念虚拟存储器的定义虚拟存储器的定义p让用户编程使用的地址范围决定的虚存空间，远远让用户编程使用的地址范围决定的虚存空间，远远大于实际的内存空间。大于实际的内存空间。p对用户而言，它是一个比主存大得多的地址空间，对用户而言，它是一个比主存大得多的地址空间，可以按它来编程，而不必考虑主存的不足。可以

14、按它来编程，而不必考虑主存的不足。p对对OS而言，是用各种表格机构构造的一个虚拟存储而言，是用各种表格机构构造的一个虚拟存储器。器。4.1 存储器管理的基本概念存储器管理的基本概念VS的基本实现原理的基本实现原理p利用表格为用户构造一个虚拟空间，作为实现利用表格为用户构造一个虚拟空间，作为实现VS的的机构。机构。 p利用大容量的外存，存放进入利用大容量的外存，存放进入VS中的信息中的信息, 是是VS的的硬件基础。硬件基础。p主存作为主存作为VS中的程序和数据得以运行的缓冲区。中的程序和数据得以运行的缓冲区。p在内、外存之间信息调度。在内、外存之间信息调度。p硬件提供动态地址转换机构。硬件提供动

15、态地址转换机构。注注 VS的容量由虚拟地址结构决定，也受外存容量的的容量由虚拟地址结构决定，也受外存容量的限制。限制。 4.2 早期的存储管理早期的存储管理4.2.1 4.2.1 单一连续分配单一连续分配 每个进程所需的空间分配到主存一块连续区。早每个进程所需的空间分配到主存一块连续区。早期的单道成批处理或个人微机期的单道成批处理或个人微机OS或专用或专用OS多用。多用。p目的：解决成批作业自动接续问题，不提供共享主目的：解决成批作业自动接续问题，不提供共享主存功能。存功能。p分配方法分配方法将主存分为二块连续区：系统区将主存分为二块连续区：系统区存放存放OS和用户区和用户区存放用户程序；存放

16、用户程序；系统设置一个界限寄存器（系统设置一个界限寄存器（Fence register）指出）指出OS区区和用户区的界限，当用户程序地址小于边界地址时，产和用户区的界限，当用户程序地址小于边界地址时，产生越界中断；生越界中断；由装入程序每次装入一个作业到用户区，剩余的用户区由装入程序每次装入一个作业到用户区，剩余的用户区空间浪费掉；空间浪费掉；采用静态重定位。采用静态重定位。 4.2 早期的存储管理早期的存储管理p特点特点单道运行，独占资源，浪费了内存碎片，资源利用率低。单道运行，独占资源，浪费了内存碎片，资源利用率低。简单，简单，OS可以小到可以小到1KB（一般几十（一般几十KB），不需复杂

17、的硬、），不需复杂的硬、软件支持。软件支持。缺少灵活性，大作业不能在小内存运行。缺少灵活性，大作业不能在小内存运行。操作系统操作系统32KB作业作业64KB未用未用160KB分配给用户分配给用户作业的空间作业的空间4.2 早期的存储管理早期的存储管理4.2.2 4.2.2 分区分配分区分配 分区分配是能满足多道程序设计需要的一种最简分区分配是能满足多道程序设计需要的一种最简单的存储管理技术，分区管理法也称界地址存储管理单的存储管理技术，分区管理法也称界地址存储管理法。通常，按照分区的划分方式，又可分为固定式分法。通常，按照分区的划分方式，又可分为固定式分区、可变式分区、可再定位式分区和多重分区

18、。区、可变式分区、可再定位式分区和多重分区。1.固定式分区法固定式分区法p思想：预先将主存用户区划成大小不等若干分区；思想：预先将主存用户区划成大小不等若干分区；分区的个数和长度保持固定，每个分区只装入一个分区的个数和长度保持固定，每个分区只装入一个作业。分区的个数等于作业的道数。固定分区是实作业。分区的个数等于作业的道数。固定分区是实现多道程序设计最简单的一种技术。现多道程序设计最简单的一种技术。 4.2 早期的存储管理早期的存储管理p分区的分配和释放分区的分配和释放作业都必须规定最大的存储量；作业都必须规定最大的存储量；OS设立一张分区说明表，指明块号、位置、长度和状态；设立一张分区说明表

19、，指明块号、位置、长度和状态；装入一个作业时，由再定位装入程序按作业的内存需求装入一个作业时，由再定位装入程序按作业的内存需求量在表中找一个够大的未分配分区，用静态再定位方式量在表中找一个够大的未分配分区，用静态再定位方式装入作业，修改状态标志；装入作业，修改状态标志；回收时，将分区状态置回收时，将分区状态置0，即释放。，即释放。4.2 早期的存储管理早期的存储管理分区号分区号容量容量位置位置状态状态1 18KB8KB312KB312KB在使用在使用2 232KB32KB320KB320KB在使用在使用3 332KB32KB352KB352KB未用未用4 4120KB120KB384KB384

20、KB未用未用5 5520KB520KB504KB504KB在使用在使用操作系统操作系统 312KB 8KB 32KB 32KB 120KB 520KB0312KB320KB352KB384KB504KB4.2 早期的存储管理早期的存储管理p存储保护存储保护设立上界寄存器和下界寄存器分别存放当前运行作业的设立上界寄存器和下界寄存器分别存放当前运行作业的分区最小绝对地址和最大绝对地址；分区最小绝对地址和最大绝对地址；当访问的地址小于上界或下界时产生越界中断。当访问的地址小于上界或下界时产生越界中断。p优点优点可以共享主存，提高主存利用率。可以共享主存，提高主存利用率。程序一次性装入主存。程序一次性

21、装入主存。由于静态再定位，程序不能移动。由于静态再定位，程序不能移动。4.2 早期的存储管理早期的存储管理p缺点缺点分区内部碎片大，浪费内存。分区内部碎片大，浪费内存。例例 现有四个作业，其作业长度分别为现有四个作业，其作业长度分别为1K1K，9K9K，23K23K，33K33K，总计长度为总计长度为66K66K，为它们分配分区长分别为，为它们分配分区长分别为4K4K，12K12K，28K28K，44K44K，共占，共占88K88K，浪费了，浪费了22K22K。作业长度大于分区最大长度，无法分配。作业长度大于分区最大长度，无法分配。 这种方式适于能掌握作业大小、数量的系统及中这种方式适于能掌握

22、作业大小、数量的系统及中型机以上的型机以上的OS，如，如IBM OS/MFT（任务数固定的多道（任务数固定的多道程序设计系统）。程序设计系统）。4.2 早期的存储管理早期的存储管理2.可变式分区法可变式分区法 为了解决固定分区的内部碎片问题，在固定分区为了解决固定分区的内部碎片问题，在固定分区管理技术上设计了可变分区管理，适用于多道系统。管理技术上设计了可变分区管理，适用于多道系统。可变式分区法也就是动态划分存储器的分区方法，它可变式分区法也就是动态划分存储器的分区方法，它是在作业装入和处理过程中建立的分区，并且要使分是在作业装入和处理过程中建立的分区，并且要使分区的容量能正好适应作业大小。在

23、作业进入系统前，区的容量能正好适应作业大小。在作业进入系统前，根据作业的大小来申请所需存储容量，然后由系统实根据作业的大小来申请所需存储容量，然后由系统实施分配。系统为了管理主存分区分配情况，需建立两施分配。系统为了管理主存分区分配情况，需建立两张表，分别登记已分配区和未分配区的分区容量、位张表，分别登记已分配区和未分配区的分区容量、位置和状态信息。置和状态信息。4.2 早期的存储管理早期的存储管理p可变分区的分配思想可变分区的分配思想新作业装入主存时，找一个足够大的空闲区，按作业长新作业装入主存时，找一个足够大的空闲区，按作业长度划分，剩余仍为一个小空闲区；度划分，剩余仍为一个小空闲区；释放

24、时，与相邻的空闲区合并。释放时，与相邻的空闲区合并。OS作业作业1（8KB）作业作业2（32KB）作业作业4（24KB）作业作业3（120KB）作业作业5（128KB）作业作业6（256KB）0312KB320KB352KB376KB384KB504KB632KB888KB1024KBOS作业作业1（8KB）作业作业2（32KB）作业作业3（120KB）0312KB320KB352KB384KB504KB1024KBOS作业作业1（8KB）作业作业4（24KB）作业作业5（128KB）作业作业6（256KB）0312KB320KB352KB376KB504KB632KB888KB1024KB4

25、.2 早期的存储管理早期的存储管理p可变分区管理的数据结构可变分区管理的数据结构线性表结构线性表结构 OS设立二张表，已分配区表和空闲区表（未分配区表）。设立二张表，已分配区表和空闲区表（未分配区表）。 已分配区说明表已分配区说明表未分配区说明表未分配区说明表序号序号首址首址大小大小状态状态序号序号首址首址大小大小状态状态120K8K已分（已分（1）156K30K可用（可用（1）228K28K已分（已分（1）228K28K空白（空白（0）3142K100K空白（空白（0）386K22K可用（可用（1）4108K34K已分（已分（1）4142K100K 可用（可用（1）可变式分区状态表可变式分区

26、状态表4.2 早期的存储管理早期的存储管理p链表结构：一种利用存储分块自身存放信息即分区链表结构：一种利用存储分块自身存放信息即分区附加数据集，并由链指针按照一定算法链接起来。附加数据集，并由链指针按照一定算法链接起来。FPBPFPBPFPBPFPBPFB空闲区链结构空闲区链结构状态状态大小大小前向指针前向指针1N+2含有含有N个字的作业个字的作业1N+2状态状态大小大小后向指针后向指针已分配区已分配区状态状态大小大小前向指针前向指针1M+2FP含有含有M个字的空闲区个字的空闲区1M+2BP状态状态大小大小后向指针后向指针空闲区空闲区4.2 早期的存储管理早期的存储管理可变分区的管理可变分区的

27、管理分配与回收分配与回收p分配的步骤分配的步骤按作业长度找一个够大的空闲区，划出作业长度，多余按作业长度找一个够大的空闲区，划出作业长度，多余仍为空闲区；仍为空闲区；修改空闲区表，填写已分配区表。修改空闲区表，填写已分配区表。p释放的步骤释放的步骤查看已分配区表，根据释放的地址、长度，得对应表项；查看已分配区表，根据释放的地址、长度，得对应表项；该项状态置该项状态置0，空白项；，空白项；将释放区记入未分配表中空项，状态置为可用空间；将释放区记入未分配表中空项，状态置为可用空间；与相邻区合并。与相邻区合并。4.2 早期的存储管理早期的存储管理p合并邻接空闲区有四种情况合并邻接空闲区有四种情况合并

28、上邻接区；合并上邻接区；合并下邻接区；合并下邻接区；上下两邻接区均可合并；上下两邻接区均可合并；上下两邻接区均不可合并。上下两邻接区均不可合并。作业作业B回收区回收区P上邻接区上邻接区f1作业作业B上邻接区上邻接区f1下邻接区下邻接区f2回收区回收区P回收区回收区P回收区回收区P作业作业A下邻接区下邻接区f2作业作业A4.2 早期的存储管理早期的存储管理可变分区的分配算法可变分区的分配算法p最先适应法（最先适应法（first fit）FF：找能满足需求的第一个：找能满足需求的第一个空闲区，即可分配，剩余部分仍留在空闲区表中。空闲区，即可分配，剩余部分仍留在空闲区表中。可把空闲区表按地址大小由小

29、到大排列。可把空闲区表按地址大小由小到大排列。优点优点p释放时，若有相邻区，易于合并；释放时，若有相邻区，易于合并；p先分配低地址空间，保留高地址较大的的空间，以备先分配低地址空间，保留高地址较大的的空间，以备大作业分配。大作业分配。 4.2 早期的存储管理早期的存储管理p最佳适应法（最佳适应法（BF Best fit） 找能满足作业需要的最小分区分配。将空闲区按找能满足作业需要的最小分区分配。将空闲区按长度由小到大排列，即长度由小到大排列，即X1X2X3Xn，其，其中中Xi为第为第i分空闲区长度。分空闲区长度。S为作业的需要量，则从为作业的需要量，则从X1顺序比，直到顺序比，直到SXi，从，

30、从Xi中分配，若中分配，若Xn不能分，则不能分，则失败。如失败。如XiS，剩余的插入合适位置。，剩余的插入合适位置。4.2 早期的存储管理早期的存储管理p优点优点平均查到一半时，即可以找到最佳空闲区，若有平均查到一半时，即可以找到最佳空闲区，若有Xi=S，必被选中。必被选中。保留与保留与S相差大的空闲区，每次分相差小的空闲区。相差大的空闲区，每次分相差小的空闲区。p缺点缺点碎片太小，无法利用；碎片太小，无法利用；分配、回收查找费时；分配、回收查找费时；合并不易，要对各空闲区计算最高地址，然后比较，找合并不易，要对各空闲区计算最高地址，然后比较，找邻接区，费时。合并后，要插入合适位置也费时。邻接

31、区，费时。合并后，要插入合适位置也费时。4.2 早期的存储管理早期的存储管理p最坏适应法（最坏适应法（worst fit）：每次总是选最大的空闲）：每次总是选最大的空闲区分配。将空闲区按长度由大到小排列：区分配。将空闲区按长度由大到小排列：X1X2X3Xn，若，若X1S，从，从X1中分中分X1-S0，剩余的插入合适位置，剩余的插入合适位置，X1不够大，失败！不够大，失败！优点优点p分配速度快，只比较分配速度快，只比较X1长度，即可确定分配；长度，即可确定分配；pX1分配后，剩余仍较大，可满足以后的需求。分配后，剩余仍较大，可满足以后的需求。缺点缺点p各区都均等地减小，不能满足大作业需要。各区都

32、均等地减小，不能满足大作业需要。4.2 早期的存储管理早期的存储管理操作系统操作系统作业作业A2n130K作业作业D1n214K作业作业C3N310K作业作业A1n470K（a）存储器示意图）存储器示意图序号序号首址首址大小大小状态状态1n2+13K1K12n310K13n130K14n470K15m160K06m220K0（c）分配后的最佳适应算法空闲区）分配后的最佳适应算法空闲区表表序号序号首址首址大小大小状态状态1n4+13K57K12n130K13n214K14n310K15m160K06m220K0（d）分配后的最差适应算法空闲区）分配后的最差适应算法空闲区表表序号序号首址首址大小大

33、小状态状态1n1+13K17K12n214K13n310K14n470K15m160K06m220K0（b）分配后的首次适应算法空闲区表）分配后的首次适应算法空闲区表4.2 早期的存储管理早期的存储管理3.可再定位式分区分配可再定位式分区分配p碎片：内存中无法被利用的小的空闲分区。碎片：内存中无法被利用的小的空闲分区。p可再定位式分区分配即浮动分区分配，是解决碎片可再定位式分区分配即浮动分区分配，是解决碎片问题的简单而有效的方法。其基本思想是移动所有问题的简单而有效的方法。其基本思想是移动所有被分配了的分区，使之称为一个连续区域，而留下被分配了的分区，使之称为一个连续区域，而留下一个较大的空白

34、区。由于程序涉及到基址寄存器、一个较大的空白区。由于程序涉及到基址寄存器、访问内存指令、访问参数表或数据结构，所以一个访问内存指令、访问参数表或数据结构，所以一个作业移动位置后，通常无法保证程序在新位置上能作业移动位置后，通常无法保证程序在新位置上能够正确运行，为此，应解决程序的可再定位（浮动）够正确运行，为此，应解决程序的可再定位（浮动）问题。问题。 4.2 早期的存储管理早期的存储管理操作系统操作系统操作系统操作系统用户程序用户程序A用户程序用户程序A10K用户程序用户程序B用户程序用户程序B用户程序用户程序C50K用户程序用户程序D用户程序用户程序C105K45K用户程序用户程序（a）紧

35、凑前）紧凑前（b）紧凑后）紧凑后紧凑内存示意图紧凑内存示意图4.2 早期的存储管理早期的存储管理解决程序的可再定位（浮动）问题的方法：解决程序的可再定位（浮动）问题的方法：p使用模块装入程序，将程序的装配模块重新装入到使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始执行。缺点花费较多的处理指定位置，并从头开始执行。缺点花费较多的处理机时间；如果程序已经执行了一段时间，必须从头机时间；如果程序已经执行了一段时间，必须从头开始，否则将引起混乱。开始，否则将引起混乱。p动态再定位技术。当一个作业装入与其地址空间不动态再定位技术。当一个作业装入与其地址空间不一致的存储空间时，可在访问指

36、令或数据时，通过一致的存储空间时，可在访问指令或数据时，通过再定位寄存器（或称浮动寄存器）来自动修改访问再定位寄存器（或称浮动寄存器）来自动修改访问存储器的地址。因此，一个作业再主存中移动后，存储器的地址。因此，一个作业再主存中移动后，只需要改变再定位寄存器的内容即可。只需要改变再定位寄存器的内容即可。 4.2 早期的存储管理早期的存储管理 可再定位分区分配算法和固定式（或可变式）分可再定位分区分配算法和固定式（或可变式）分区分配算法基本相同。问题是何时进行靠拢，一般有区分配算法基本相同。问题是何时进行靠拢，一般有两种时机的选择两种时机的选择p当某个分区内的作业一完成，就立即靠拢。这样的当某个

37、分区内的作业一完成，就立即靠拢。这样的靠拢操作是比较频繁的，由于实施程序的移动要花靠拢操作是比较频繁的，由于实施程序的移动要花费较多的处理机时间，因此应尽可能减少靠拢操作费较多的处理机时间，因此应尽可能减少靠拢操作的次数；的次数；p在为某一作业请求一个分区时，当时内存没有足够在为某一作业请求一个分区时，当时内存没有足够大的空白区，但各空白区之和可以满足该作业存储大的空白区，但各空白区之和可以满足该作业存储要求，此时须进行靠拢操作。这样的靠拢次数要少要求，此时须进行靠拢操作。这样的靠拢次数要少得多，从而可以节省处理机时间。得多，从而可以节省处理机时间。4.2 早期的存储管理早期的存储管理分配算法

38、流程图分配算法流程图请求分配一个大小请求分配一个大小为为xKB的分区的分区有大于有大于xKB的空白区吗？的空白区吗？空白区的空白区的总和总和 xKB执行靠拢操作执行靠拢操作并修改状态表并修改状态表此时无法分配此时无法分配返回一个返回一个分区号分区号分配一个分区并分配一个分区并修改状态表修改状态表NNYY4.2 早期的存储管理早期的存储管理4.多重分区分配多重分区分配 通常一个作业由一些相对独立的程序段和数据段通常一个作业由一些相对独立的程序段和数据段组成，如主程序、子程序、数据组等。这些程序段中组成，如主程序、子程序、数据组等。这些程序段中的每一个在逻辑上必须是连续的，但是相应的各分区的每一个

39、在逻辑上必须是连续的，但是相应的各分区不要求是连续的。采用多重分区分配方案，作业可以不要求是连续的。采用多重分区分配方案，作业可以在其执行期间申请附加的分区。在其执行期间申请附加的分区。p优点：可使存储空间的利用率提高。优点：可使存储空间的利用率提高。p缺点：作业分段越多，分区越小，存储器过碎，造缺点：作业分段越多，分区越小，存储器过碎，造成没有较大的空白区；实现多重分区要求更多的硬成没有较大的空白区；实现多重分区要求更多的硬件支持，管理也比较复杂。件支持，管理也比较复杂。 4.2 早期的存储管理早期的存储管理5.分区的保护措施分区的保护措施 存储保护是为了防止一个作业有意或无意的破坏存储保护

40、是为了防止一个作业有意或无意的破坏操作系统或其他作业。通常采用界限寄存器或者存储操作系统或其他作业。通常采用界限寄存器或者存储保护键两种方法。保护键两种方法。p界限寄存器界限寄存器定位寄存器和界限寄存器：利用定位寄存器的值（定位寄存器和界限寄存器：利用定位寄存器的值（=存储存储空间首址减去地址空间首址的值空间首址减去地址空间首址的值)，和界限寄存器的值进，和界限寄存器的值进行存储访问检查行存储访问检查(界限寄存器的值存放作业地址空界限寄存器的值存放作业地址空间的大间的大小）。小）。上下限寄存器。每次访主存时上下限寄存器。每次访主存时,其地址值与上限寄存器值其地址值与上限寄存器值(物理地址的最高

41、地址物理地址的最高地址)和下限寄存器值和下限寄存器值(最低物理地址最低物理地址)比比较：若大于上限或小于下限时则中断访问主存。较：若大于上限或小于下限时则中断访问主存。4.2 早期的存储管理早期的存储管理下界寄存器下界寄存器60KB基址寄存器基址寄存器60KB限长寄存器限长寄存器64KB上界寄存器上界寄存器124KB060KB作业作业2的分区的分区124KB256KB060KB作业作业2的分区的分区124KB256KB上下界寄存器进行存储保护上下界寄存器进行存储保护基址寄存器进行存储保护基址寄存器进行存储保护4.2 早期的存储管理早期的存储管理p存储保护键存储保护键将主存静态分成若干块，一般是

42、等分为将主存静态分成若干块，一般是等分为1k2k大小分块；大小分块；每块都指定一个单独的保护键，保护键由保护字和保护每块都指定一个单独的保护键，保护键由保护字和保护方式组成：保护方式分为写保护、读写保护两种，而保方式组成：保护方式分为写保护、读写保护两种，而保护字由一组代码组成；护字由一组代码组成；每个作业赋于一个不同代码并存入该作业的程序状态字每个作业赋于一个不同代码并存入该作业的程序状态字中，访问主存时用此代码中，访问主存时用此代码(钥匙钥匙)与保护键进行匹配检查；与保护键进行匹配检查；先进行保护方式检查，若是写保护，则对一切读指令都先进行保护方式检查，若是写保护，则对一切读指令都不进行匹

43、配检查允许访问主存，但对写指令必须进行匹不进行匹配检查允许访问主存，但对写指令必须进行匹配检查；若是读写保护，则对任何指令都进行匹配检查。配检查；若是读写保护，则对任何指令都进行匹配检查。匹配检查是用作业代码钥匙与主存的代码锁相比较，若匹配检查是用作业代码钥匙与主存的代码锁相比较，若相同则允许访问主存，否则作为访问主存出错被中断；相同则允许访问主存，否则作为访问主存出错被中断；一般系统都将操作系统的程序状态字一般系统都将操作系统的程序状态字(PSW)钥匙置为钥匙置为0，它具有万能钥匙之功效它具有万能钥匙之功效可访问任一主存块。可访问任一主存块。4.2 早期的存储管理早期的存储管理4.2 早期的

44、存储管理早期的存储管理6.分区分配方案的评价分区分配方案的评价p优点优点对多道程序设计，实现了存储的共享，更有效地使用了对多道程序设计，实现了存储的共享，更有效地使用了处理机和处理机和I/O设备，从而使系统的吞吐量和作业周转时间设备，从而使系统的吞吐量和作业周转时间得到了相应的改善；得到了相应的改善；高了主存利用率，可变式分区高于固定式分区，可定位高了主存利用率，可变式分区高于固定式分区，可定位式分区更高；式分区更高；实现存储保护的措施比较简单；实现存储保护的措施比较简单；多重分区分配方案能实现对子数据、程序段的共享。多重分区分配方案能实现对子数据、程序段的共享。4.2 早期的存储管理早期的存

45、储管理p缺点：缺点：主存仍不能充分利用，存在严重碎片问题主存仍不能充分利用，存在严重碎片问题(可重定位分区可重定位分区分配除外分配除外)；不能实现对主存的扩充，作业大小受到主存可用空间的不能实现对主存的扩充，作业大小受到主存可用空间的限制；限制；和单一连续分配一样，要求一个作业在执行之间必须全和单一连续分配一样，要求一个作业在执行之间必须全部装入内存，因此在主存中可能包含从未使用过的信息。部装入内存，因此在主存中可能包含从未使用过的信息。采用靠拢方法，虽然能解决碎片问题，但有时需移动大采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。量信息，从而损失了处理机时间。除

46、多重分区外，几个共行作业之间不能共享存入主存的除多重分区外，几个共行作业之间不能共享存入主存的单一信息副本。单一信息副本。4.3 分页存储管理分页存储管理 可再定位（即浮动）式分区分配技术，使用这种可再定位（即浮动）式分区分配技术，使用这种分配技术可以消除碎片，使一些零散的空白区汇合成分配技术可以消除碎片，使一些零散的空白区汇合成较大的连续的空白区，提高主存的利用率。但是，各较大的连续的空白区，提高主存的利用率。但是，各作业分区的靠拢花费了较多的处理机时间，并不可取。作业分区的靠拢花费了较多的处理机时间，并不可取。这是由于我们提出了每个作业占有的存储空间必须是这是由于我们提出了每个作业占有的存

47、储空间必须是连续的。避开这一要求，就引进了分页存储管理技术。连续的。避开这一要求，就引进了分页存储管理技术。4.3 分页存储管理分页存储管理4.3.1 4.3.1 分页原理分页原理 用户作业地址空间起点与分区的物理位置无关，用户作业地址空间起点与分区的物理位置无关，所以作业的地址空间通常从所以作业的地址空间通常从0开始。分页存储管理就开始。分页存储管理就是从逻辑地址空间到物理地址空间的一种变换，即是从逻辑地址空间到物理地址空间的一种变换，即f：LS，其中，其中，L、S分别表示逻辑地址空间和物理地分别表示逻辑地址空间和物理地址空间。址空间。p页框（物理块）：将主存按页框（物理块）：将主存按2n划

48、成位置固定，长度划成位置固定，长度相等的块，称为页框（相等的块，称为页框（pageframe）或物理页。如）或物理页。如1KB，PC机为机为4KB一页。一页。对页框进行统一编号对页框进行统一编号0，1，2，n-1，称为块号，称为块号（页框号页架号物理页号绝对页号）；（页框号页架号物理页号绝对页号）；页框是分配内存的基本单位。页框是分配内存的基本单位。4.3 分页存储管理分页存储管理p页面页面(页页)：作业的虚拟地址空间也按同样长度分成：作业的虚拟地址空间也按同样长度分成页面页面(虚页，虚拟页面虚页，虚拟页面)，对其统一编号，对其统一编号0，1，2，m-1，称为页面号，称为页面号(虚页号逻辑页号

49、相对页号虚页号逻辑页号相对页号)。p一个作业的逻辑地址空间的所有页面是邻接的，而一个作业的逻辑地址空间的所有页面是邻接的，而变换到物理存储空间的各块可以不邻接。变换到物理存储空间的各块可以不邻接。p逻辑地址空间和物理地址逻辑地址空间和物理地址空间的对应关系由称为页空间的对应关系由称为页面变换表的面变换表的PMT指出，指出，PMT也简称为页表。也简称为页表。 虚页号虚页号页框号页框号0317218页表（页表（PAGE TABLE）4.3 分页存储管理分页存储管理在分页存储管理方式中，系统以页框为单位把主存分给在分页存储管理方式中，系统以页框为单位把主存分给进程，并且每个进程分给的各页框不一定相邻

50、和连续。进程，并且每个进程分给的各页框不一定相邻和连续。页表的作用是实现从页号到物理块号的地址映射。页表的作用是实现从页号到物理块号的地址映射。每一个进程对应一张页表，一个页表表项的数目等于其每一个进程对应一张页表，一个页表表项的数目等于其所记录的进程逻辑地址空间的页面数。所记录的进程逻辑地址空间的页面数。CPU中设立一个页表地址寄存器。中设立一个页表地址寄存器。例例 作业作业A的地址空间为的地址空间为11KB，按，按4KB分页，分为分页，分为0，1，2页。页。 4.3 分页存储管理分页存储管理作业作业101KB2KB作业作业201KB2KB3KB作业作业301KB操作系统操作系统作业作业2（

51、0页）页）作业作业2（1页）页）作业作业1（0页）页）作业作业1（1页）页）作业作业2（2页）页）作业作业3（0页）页）物理地址空间物理地址空间页号页号块号块号051601KB2KB3KB4KB5KB6KB7KB8KB9KB10KB02142708页面变换表页面变换表逻辑地址空间逻辑地址空间4.3 分页存储管理分页存储管理L1，2KB6001557100作业作业2的地址空间的地址空间05181KB2KB2KB60L1，2KB6001557100存储空间存储空间2KB3KB4KB5KB6KB7KB7KB608KB021427页面变换表页面变换表页面变换表保证了作业的正确执行页面变换表保证了作业的

52、正确执行4.3 分页存储管理分页存储管理4.3.2 4.3.2 地址变换机构地址变换机构1.动态地址变换机构动态地址变换机构DAT 考察计算机系统指令考察计算机系统指令L R1，D2（X2，B2），），其中，其中，X2、B2、D2为第二操作数域使用的变址寄存为第二操作数域使用的变址寄存器、基址寄存器和位移量，器、基址寄存器和位移量，R1是第一操作数域的通用是第一操作数域的通用寄存器。寄存器。指令格式为图指令格式为图LR1X2B2D207 811 1215 1619 20314.3 分页存储管理分页存储管理 指令的第二操作数的有效地址为指令的第二操作数的有效地址为E2（X2）（B2）D2，该指令

53、的有效地址占，该指令的有效地址占24位。因此，逻位。因此，逻辑地址空间最大可达辑地址空间最大可达22416MB。假定页面大小为。假定页面大小为4KB，于是逻辑地址空间可达，于是逻辑地址空间可达4096个页面，每个页面个页面，每个页面4096个字节。个字节。24位有效地址自然地被划分为两部分，位有效地址自然地被划分为两部分，前前12位为页号，后位为页号，后12位为页内地址。位为页内地址。页号页号页内地址页内地址07 819 20314.3 分页存储管理分页存储管理 动态地址变换机构自动地将所有地址划分为页号动态地址变换机构自动地将所有地址划分为页号和页内地址两部分。利用和页内地址两部分。利用PM

54、T表将页号代之以块号，表将页号代之以块号，得到要使用的物理存储地址。得到要使用的物理存储地址。LR1，D2（X2，B2）LR1X2B2D2（7）0000 0000 0111（144）0000 1001 0000有效地址有效地址（2）0000 0000 0000（144）0000 1001 0000页号页号页内地址页内地址页号页号 块号块号011427255页面变换表页面变换表4.3 分页存储管理分页存储管理 每个作业都有一个页面变换表，通常各作业的页每个作业都有一个页面变换表，通常各作业的页面变换表放在操作系统的一个工作区中，由页面变换面变换表放在操作系统的一个工作区中，由页面变换地址寄存器（

55、地址寄存器（PMTAR）指出作业的页面变换表的起）指出作业的页面变换表的起始地址。当处理机执行一个新作业或恢复一个旧作业始地址。当处理机执行一个新作业或恢复一个旧作业时，只要修改时，只要修改PMTAR的内容，使之指向要执行作业的内容，使之指向要执行作业的的PMT起始地址即可。起始地址即可。4.3 分页存储管理分页存储管理PMTAR34160长度长度PMT起始地址起始地址0KB4KB8KB12KB0 页页1页页2页页作业作业2的地址空间的地址空间4字节字节247作业作业2（0页）页）作业作业2（1页）页）作业作业2（2页）页）操作系统用04KB块块2块块4块块74160PMTAR、PMT、页面和

56、块之间的关系、页面和块之间的关系4.3 分页存储管理分页存储管理2.高速页面变换寄存器高速页面变换寄存器 为了实现从作业地址空间到物理地址空间变换，为了实现从作业地址空间到物理地址空间变换，可采用硬件的高速寄存器来实现。可采用硬件的高速寄存器来实现。3.联想存储器联想存储器 页面变换表存放在主存，由操作系统实施管理，页面变换表存放在主存，由操作系统实施管理，在作业执行时，每条指令的执行都必须进行地址变换。在作业执行时，每条指令的执行都必须进行地址变换。每条指令必须两次访问存储器：一次把页号变成物理每条指令必须两次访问存储器：一次把页号变成物理块号，一次进行实际存取所要的数据或指令，增加了块号，

57、一次进行实际存取所要的数据或指令，增加了指令执行的机器时间，影响了计算机的速度。指令执行的机器时间，影响了计算机的速度。 采用高速寄存器方法，如果作业地址空间较大，采用高速寄存器方法，如果作业地址空间较大，所需存储器较多，花费较高。所需存储器较多，花费较高。 4.3 分页存储管理分页存储管理 因此采用一种折衷办法来解决这一矛盾，即把高因此采用一种折衷办法来解决这一矛盾，即把高速寄存器作为速寄存器作为DAT的辅助机构来实行地址变换。这些的辅助机构来实行地址变换。这些寄存器连同管理它们的硬件构成了一个容量较小的存寄存器连同管理它们的硬件构成了一个容量较小的存储器，称之为联想存储器，也称快表。在联想

58、存储器储器，称之为联想存储器，也称快表。在联想存储器中，存放正运行作业当前最常用的页号和相应块号，中，存放正运行作业当前最常用的页号和相应块号，具有并行查询能力。具有并行查询能力。4.3 分页存储管理分页存储管理有效地址有效地址PW页号页号P块号块号BBW物理地址物理地址输入寄存器输入寄存器输出寄存器输出寄存器4.3 分页存储管理分页存储管理 在采用联想存储器的系统中，通常采用在采用联想存储器的系统中，通常采用“双管齐双管齐下下”的方针，既按给出的页号检索联想存储器中的相的方针，既按给出的页号检索联想存储器中的相应块号，同时按应块号，同时按PMT表进行查找块号，同时进行。如表进行查找块号，同时

59、进行。如果在联想存储器中，检索到所要块号，立即停止果在联想存储器中，检索到所要块号，立即停止PMT表的查找，利用联想存储器给出的块号访问主存。如表的查找，利用联想存储器给出的块号访问主存。如果联想存储器检索不到需要的块号，将果联想存储器检索不到需要的块号，将PMT表查找到表查找到的页号以及所对应的块号填入联想寄存器内的空白单的页号以及所对应的块号填入联想寄存器内的空白单元中，如没有空白单元，根据某种规则淘汰一个单元元中，如没有空白单元，根据某种规则淘汰一个单元内容后填入。内容后填入。4.3 分页存储管理分页存储管理例例 设设CPU访问内存要访问内存要200ns，访问快表一次要，访问快表一次要4

60、0ns，命中率为命中率为90%，求一次访问内存的平均时间是多少？，求一次访问内存的平均时间是多少？比慢表访问下降了多少？比慢表访问下降了多少？解解 访问内存的平均时间为：访问内存的平均时间为： （40+200)*0.9+(200+200)*0.1=216+40=256（ns） 不用快表，每取一指令或数据要用不用快表，每取一指令或数据要用 400ns，则（，则（400-256）/400=36%4.3 分页存储管理分页存储管理例例 CPU访问慢表为访问慢表为100ns，访问快表为，访问快表为20ns，希望，希望把进行一次访问内存存取指令的或数据的时间控制把进行一次访问内存存取指令的或数据的时间控制