1、第四章 存储器管理,存储器管理是指存储器资源（主要指内存)的管理。存储空间的分配与管理；地址重定位（逻辑地址与物理地址的对应关系）存储保护存储空间扩充：虚拟存储器技术以及各种调度算法。,4.1 地址重定位4.2 分区存储管理4.3 覆盖和交换4.4 页面式存储管理4.5 请求式页面存储管理4.6 段式存储管理4.7 段页式存储管理,4.1 地址重定位,主存储器分为两部分：系统区，用户区存储管理主要管理用户区的存储空间,地址空间和存储空间,名空间：程序中由符号名组成的空间。逻辑地址（相对地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。相对于0编址。逻辑地址空间（地
2、址空间）：相对地址的集合。物理地址（绝对地址）：主存储器中一系列物理单元的编号。物理地址可直接寻址。物理地址空间（存储空间）：物理地址的集合。,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。, 逻辑地址、物理地址和地址映射,逻辑地址、物理地址和地址映射,地址映射,1100,Load A,1200,3456,。,。,。
3、,1200,物理地址空间,Load A,data1,data1 3456,源程序,Load A,200,3456,0,100,200,编译连接,逻辑地址空间,BA=1000,地址重定位：实现程序的相对地址空间到绝对地址空间之间的映射。程序在成为进程前的准备工作编辑：形成源文件(符号地址)编译：形成目标模块(模块内符号地址解析)链接：由多个目标模块或程序库生成可执行文件(模块间符号地址解析)装入：构造PCB，形成进程(使用物理地址)重定位方法：静态重定位动态重定位,地址重定位,优点：容易实现，无需硬件支持。缺点： 程序在主存中只能连续分配； 程序装入内存后不能移动； 对共享的同一程序，各用户必须
4、使用自己的副本，浪费存储空间。,在程序执行之前进行地址重定位，即可执行文件中装入主存时，由操作系统中的加载程序来完成地址映射。重定位项：程序中涉及直接寻址的每条指令都要进行修改，需要修改的位置称为重定位项。重定位项表：用相对地址给出需修改的位置。列出各个需要重定位的地址单元和相对地址值。,静态重定位,地址映射,1100,Load A,1200,3456,。,。,。,1200,物理地址空间,Load A,data1,data1 3456,源程序,Load A,200,3456,0,100,200,编译连接,逻辑地址空间,BA=1000,静态重定位,可执行文件在内存中的重定位,说明：重定位表中列出
5、所有修改的位置。如：重定位表的150表示相对地址150处的内容为相对地址(即100为从0起头的相对位置)。在装入时，要依据重定位后的起始位置(2000)修改相对地址。重定位修改：重定位表中的150-绝对地址2150(=2000+150)内容修改：内容100变成2100(=100+2000)。,jmp,150,100,150,.,Relocation,Table,0,jmp,150,2100,2150,.,2000,优点：OS可以将一个程序分散存放于不连续的内存空间；可以移动程序。有利用实现共享。缺点：需要硬件支持（通常是CPU），是虚拟存储的基础。,在程序运行期间进行重定位，装入和执行时通过硬
6、件地址变换机构，完成虚拟地址到实际内存地址的变换,动态重定位,动态重定位,0,100,200,300,.,.,.,.,.,.,.,.,.,LOAD A,200,3456,逻辑地址空间,1100,1200,1300,物理地址空间,200,VR,+,1000,BR（基址寄存器）,LOAD A,200,3456,缺点：不能充分使用存储空间。,4.2分区存储管理,基本思想：将主存储空间划分成若干个连续的存储区，称为分区。每个分区只能存储一道程序，一个程序只能访问其所在分区的存储单元。,内存分为两个连续区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单道程序设计的OS。优
7、点：易于管理。缺点：对要求内存空间少的程序，造成内存浪费（空闲存储区）。,4.2分区存储管理,单一连续区存储管理,适用于单道程序系统,单一连续区存储管理,0H,7FFFH,FFFFFH,操作系统,用户程序区,08000H,界限寄存器,中断矢量表,空闲区,基本思想：把内存分为一些大小相等或不等连续区域分区(partition)，每个分区只能驻留一个程序。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行问题：存在碎片（小得难以使用的分区）问题，可能存在内部碎片和外部碎片。内部碎片：占用分区之内未被利用的空间外部碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）
8、。,分区存储管理,分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,把内存划分为若干个固定大小的连续分区。一旦划分好，在系统运行期间不再重新划分。,固定分区(fixed partitioning),固定分区(大小相同),固定分区(多种大小),优点：简单易于实现，开销小。缺点：内部碎片造成浪费分区总数固定，限制了并发执行的程序数目。采用的数据结构：分区表(分区说明表)记录分区的大小和使用情况,Operating System,空闲分区,分区5,作业C,分区4,分区3,分
9、区2,分区1,空闲分区,作业B,作业A,00000H,08000H,0A000H,12000H,1A000H,3A000H,内存分区说明表,动态分区：在装入作业和处理过程中，按其要求的内存容量以及当时的内存资源使用情况，将一块大小与所要求相近的存储区分配给作业。优点：没有内部碎片。缺点：有外部碎片。,动态分区(dynamic partitioning),分区的数据结构：分区表，或分区链表可以只记录空闲分区，也可以同时记录空闲和占用分区单一分区表中，表项数目随着内存的分配和释放而动态改变，表长难以确定，分配回收分区时降低查找速度。分区表可以划分为两个表：空闲分区表，使用分区表。从而减小每个表长度
10、。空闲分区表（一般常用链表结构）中按不同分配算法相应对表项排序。分区分配和释放算法,动态分区管理：,分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断和合并时机的选择),分区分配算法和释放算法：,最先匹配法(first-fit)：按分区的先后次序，从头查找，找到符合要求的第一个分区该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。最佳匹配法(best-fit)：找到其大小与要求相差最小的空闲分区从个别来看
11、，外部碎片较小，但从整体来看，会形成较多外部碎片。较大的空闲分区可以被保留。最差匹配法(worst-fit)：找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。,分区分配算法,基本思想：分配算法与可变分区分配基本算法基本相同，并对作业进程分区进行搬迁，以形成大的连续的空闲分区。特点：解决外部碎片问题的简单有效的方法对占用分区进行内存数据搬移占用CPU时间如果对占用分区中的程序进行“浮动”，则其重定位需要硬件支持（提供基址界限寄存器对）。实现空闲分区拼接的时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时,动态重定位式分区分配,基本思想：一个作业由一些相对独立的程序段和数
12、据段组成，每个段占用一个连续分区，而相应的各分区之间不要求是连续的。特点：有效地解决外部碎片问题要求：相应的语言编译器能在作业的每个段内生成有效地址（各段相对于0编址）系统内设置多对基址界限寄存器。优点：可以实现分区共享诸进程可以共享数据分区。,多重分区存储管理不拼接而解决碎片问题,引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。基本思想:一个作业的若干程序段，或几个作业的某些部分共享同一存储区。优点：解决小主存容量与大作业之间的矛盾。缺点：实现覆盖管理的系统开销较大。,4.3 覆盖和交换,覆盖(overlay),注：另一种覆盖方法：(100K)A(
13、20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；,覆盖技术,不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区),缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。,引入：解决主存容量不足的矛盾。多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区
14、存储管理配合使用。又称作“对换”或“滚进/滚出(roll-in/roll-out)”。基本思想:暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。,交换(swapping),优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构。缺点： 对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。考虑的问题：程序换入时的重定位；减少交换中传送的信息量，特别是对大程序；对外存交换区空间的管理
15、：如动态分区方法；,覆盖与交换的区别：,覆盖由用户解决空间不足,交换由系统解决空间不足,引入：避开作业的连续性要求，将一个作业存放在 不连续的存储空间中，以很好地解决碎片问题。基本思想:系统把内存物理空间等分为若干大小相等、位置固定的块（或帧）。将程序的逻辑地址空间划分为与块大小相同的页或页面(page or page frame)，程序加载时，分配其所需的所有块，这些块不必连续。需要CPU的硬件支持。,4.4 页面式存储管理,地址空间分成大小相同的部分 页,存贮空间分成大小相同的部分 块(页帧),页大小块大小,页表(PMT) ：又称页面映象表，记录一个作业程序的页号所对应的内存块号。 需要C
16、PU的硬件支持。,页号,块号,0,1,2,2,3,8,分配时页对应块，但不要求连续,页表包括：页号，块号,页帧19,Operating System,作业2（页0）,00000H,0B000H,0A800H,0B800H,0C000H,0E000H,作业1（页0）,作业2（页2）,作业1（页1）,作业2（页1）,作业3（页0）,物理地址空间,页帧0,页帧20,页帧21,页帧22,页帧23,页帧24,页帧25,页帧26,页帧27,页帧28,0C800H,0D000H,0D800H,0,1,逻辑地址空间,作业1(4K),0,1,作业2(5K),2,0,作业3(1.8K),0,1,页表,0,1,2,
17、0,页帧号,22,20,25,21,24,27,页面式存储管理硬件,地址变换：指令所给出地址分为两部分：逻辑页号，页内偏移地址查进程页表，得物理页号物理地址页面大小：通常是几KB到几十KB（取2的幂）。 小内部碎片小；大页表短，管理开销小，交换时对外存I/O效率高。,页式地址变换,分页存储管理算法,作业表：记录每个作业的状态和资源使用情况，包括页表起始地址、页表长度。 空闲块表：页记录内存空闲块的帧号。以链表形式组织内存空闲块。,建立进程时，作业调度程序调用存储管理程序为作业进程分配存储空间。按作业请求的内存容量size计算要分配的块数N=size/size_page(上取整)一个作业终止时，
18、系统调用存储管理程序，回收该作业释放的物理页，修改空闲存储块链表。,引入：向用户提供大容量存储器，把内存和外存统一考虑，外存作为存储信息的主要媒介，内存作为处理机需要访问的数据缓冲区。基本思想:运行一个作业程序时，并不要求把该作业的全部程序和数据都装入内存，可只把目前要执行的几页调入内存的空闲存储块，其余部分仍保存在外存，以后根据作业程序运行情况需要时再调入内存。,4.5 请求式页面存储管理,需解决的问题：提供一种机制，检测访问的页是否在内存，若不在，为之分配一物理页，修改页表项，并将逻辑页调入到物理页。选择淘汰算法。,分页故障处理,活动页：某一时刻驻留在内存的页，称为进程的活动页。 非活动页
19、：某一时刻驻留在外存的页。,作业的页表项包括该页是否在内存的信息。 存在位p=1:该逻辑页在内存 p=0:该逻辑页在外存，对该逻辑页的任何访问都将产生“缺页故障”中断。作业进程欲访问一条不在内存物理页中的指令或操作数时，由地址变换机构硬件产生“缺页故障”中断，并由缺页故障中断处理程序实现物理页的调入、调出操作。,淘汰算法,当外存上某页信息需调入内存而内存中又无空闲存储块时，则需按某种淘汰算法从内存中选择一页将其内容淘汰。淘汰算法不合理将产生抖动现象刚被调出的页马上又被要求调入。,最佳淘汰算法：从内存中淘汰永远不再使用的页；如这样的页不存在，则选择最长时间不再被访问的页为淘汰页。老页：某时刻前，
20、进程访问过的所有页新页：某时刻，进程正在对某页进行第一次访问。自然页流：老页中以后还要访问的页和新页构成进程的使用页集，使用页集的变动为进程的自然页流。,特点：仅有理论意义，实际不可实现明确知道各将来时刻对各页的访问情况，很难。内存容量有限，使得某些页过早淘汰。,先进先出FIFO算法：采用先调入内存的页面先被淘汰的策略；即总选择驻留内存时间最长的一页淘汰。原因：最早调入的页面不再使用的可能性要比最近调入的要大。以调入内存的时间先后顺序组织一个进程现行使用的内存储块为FIFO队列,优点：仅在程序按线性顺序访问地址空间时才是理想的。缺点：未考虑程序运行时的动态特性。可能导致程序中常被访问的页，因其
21、在内存中驻留时间最长而被淘汰。,最近最少使用LRU(Least Recently Used) 算法：选择最近很长时间未被访问的一页淘汰。原因：若一页刚被访问过，很可能最近还要被访问；若一页最近很长时间未被引用，则最近访问的可能性极小。按照各页最近一次的访问时间进行排序,缺点：每访问一次要进行一次排序，系统开销大，难以实现。近似LRU算法（第二次机会淘汰算法）,举例：,设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。用FIFO与LRU页面调度算法
22、，列出各自的页面淘汰顺序和缺页中断次数。(假设开始的4个页面已装入主存),FIFO： 页面淘汰顺序：1 2 3 6 4 7 缺页中断次数：6次 LRU： 页面淘汰顺序： 1 2 6 4 7 3 2 1 4 7 缺页中断次数： 10次 注：假定前面四页1 2 3 6 已在主存,最少使用LFU(Least Frequently Used) 算法：淘汰在现在时刻之前某一段时间内访问频率最低的页。原因：过去一段时间最经常访问的页，将来访问的可能性最大。,特点：需要为每个内存页面设置一个“访问次数计数器” ，每当页面被访问时，该页面的访问计数器加1；应禁止淘汰最近一个时间间隔内调入内存的新页；发生缺页中
23、断时，淘汰计数值最小的页面，并将所有计数清零。,请求调页(demand paging)：只调入发生缺页时所需的页面。优点：容易实现。缺点：对外存I/O次数多，开销较大预调页(prepaging)：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。优点：提高调页的I/O效率。缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。,调入策略确定在外存中的页面调入时机。在虚拟页式管理中有两种常用策略。,分页虚拟存储管理调入策略 (fetch policy),存储保护的目的：保护系统程序区不被用户侵犯（有意或无意的）不允许用户程序读写不属于自己地址空间的数据（系统区地址空
24、间，其他用户程序的地址空间）,1. 存储保护,由于存储保护检查是针对每个存储访问操作进行的，必须由相应的处理器硬件机构支持。,页面的共享与保护,存储保护类型界限保护（上界寄存器/下界寄存器或基址寄存器/限长寄存器）：所有访问地址必须在上下界之间；每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。访问方式保护（保护键）：通过保护键匹配来判断存储访问方式是否合法。对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权(即读写保护)。对每个内存区域指定一个键值和若干禁止的访问方式，进程中也
25、指定键值，如果访问时键值不匹配而且是被禁止的访问方式，则出错；环保护：处理器状态分为多个环(ring)，分别具有不同的存储访问特权级别(privilege)，通常是级别高的在内环，编号小（如0环）级别最高；可访问同环或更低级别环的数据；可调用同环或更高级别环的服务。,共享页面：在物理页面表中有引用计数。只能共享不被修改的页面。这对用户应用是透明的，完全由操作系统控制，目的在于减少系统内的物理页面总数。当共享页从内存中淘汰或重新装入内存时，共享该页的所有作业进程的页表中的相应页表项必须被同时更新。写时复制(copy on write)：如果一个进程要改写共享页面，则先把该页面复制一份，让该进程访
26、问复制后的页面，而让其他进程访问复制前的页面。,通过引用计数(reference count)来描述存储区的共享，引用计数表示共享它的进程的数目：,2.存储共享,页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。,段式存储管理基本思想：,将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。,4.6 段式存储管理,地址结构如下：,通过段表实现逻辑地址到物理地址的映射,段表结构：该段在内存中的首地址；段长；访问权限，段存在位（该段是否在内存）,段表中各表项按
27、段号从小到大顺序排列,B,0,S,A,0,N,Y,0,L,X,0,P,M,0,K,逻辑段号,0,1,2,3,4,作业,1,的地址空间,1000,3200,5000,6000,8000,P,K,S,L,N,主存,K,3200,P 1500,L 6000,N 8000,S 5000,长度,段地址,0,1,2,3,4,操作系统,地址转换,段式地址变换的步骤：,(1) 分段寻址硬件把cpu产生的程序逻辑地址划分为段号s和段内地址d，(s，d),(2) 用S检索段表，得到段基地址B,(3) 如d0或d段表长度L则产生越界异常中断,(4) (B+d)即为所需内存地址,程序通过分段(segmentation
28、)划分为多个模块，如代码段、数据段、共享段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享优点：没有内部碎片，外部碎片可以通过内存拼接来消除。便于改变进程占用空间的大小。便于模块化，便于处理共享问题。缺点：进程全部装入内存。段的最大长度受限于主存空间，开销大。,页式管理和段式管理的比较,分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的，各
29、个模块在链接时可以每个段组织成一个地址空间。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。,段的共享与保护,共享段：被连接或被释放一次则对引用计数加1或减1，计数减至0则可将该共享段删除；目的在于进程间的信息交流。段的保护：段表限制；访问权限控制；特权级。, 一个作业进程的所有分段的副本都保存在外存上；,分段虚拟存储管理, 当作业进程开始运行，系统仅把需要的一段或数段调入内存, 其它段在引用时才装入, 当进程运行时引用不在内存中的分段时，产生缺段故障中断, 按动态重定位分区分配内存，不够时拼接；超过总的空闲分区容量，则淘汰相应段,优点： 程序中各段可以分别独立编写。 便于动态
30、装入和链接。 便于实现分段存储保护。 易实现分段信息共享。缺点： 段的最大长度受限于主存空间； 段作为整体调入、调出内存的开销大，降低了系统工作效率。 采用动态分区，存在外部碎片，内存浪费。,是虚拟页式和虚拟段式存储管理的结合。,4.7 段页式存储管理,为了获得分段在逻辑上的优点和分页在管理存储空间方面的优点采用段页式存贮管理。,1. 将逻辑地址空间以段划分段式特征 2. 将物理地址空间以页划分页式特征 3. 每一段的地址空间划分为页,存储管理的分配单位是：段，页逻辑地址的组成：段号，页号，页内偏移地址。 将段内地址d分为段内页号和页内偏移地址两部分。地址变换：先查段表，再查该段的页表。缺段中
31、断和缺页中断。,地址结构：,虚拟段页式管理中的段表和页表,段页式地址变换,优点：具有分段存储管理和分页存储管理的全部优点；为用户提供了大量的虚拟存储空间，提高内存的利用率。对大、中型计算机来说，是使用最广泛、最灵活的一种存储管理。缺点：增加了硬件成本、系统复杂性和管理上的开销；表格占用了大量的存储空间；仍存在内部碎片，存在系统颠簸的危险。,本章的重要概念及相关要求,了解存储管理的目的和功能；了解虚拟存储器、地址重定位等概念；分区存储管理：了解分区存储的各种方式（固定、可变、浮动、多重分区）；存储“扩充”技术：覆盖与交换；页式存储管理：掌握分页管理的原理，利用PMT实现地址变换；掌握请求式分页机制、页面淘汰算法；了解段式存储管理的特点；了解段页式存储管理的优点。,
