计算机操作系统第7章 存储器管理

1、第第7章章 存储器管理存储器管理7。1 有关概念有关概念n这里所说的存储器指的是主存（内存、随机存储器（这里所说的存储器指的是主存（内存、随机存储器（RAM：Random Access Memory）；）；n主存空间分为两大部分：主存空间分为两大部分：n系统区：用以存放操作系统及其工作区；系统区：用以存放操作系统及其工作区；n用户区：由多个进程分配使用；用户区：由多个进程分配使用；n系统区不存在管理问题，存储管理的对象是用户区；系统区不存在管理问题，存储管理的对象是用户区；n存储器管理的目的是要使内存空间得到充分有效和安全有存储器管理的目的是要使内存空间得到充分有效和安全有序的使用。序的使用。

2、系统区用户区存储管理的对象是主存的用户区存储器管理的功能存储器管理的功能n空间分配：空间分配：在多个进程之间分配和回收存储空间；n地址变换：地址变换：将逻辑地址变换为物理地址；n存储保护：存储保护：防止因用户程序错误破坏系统或其他用户，防止程序之间的相互干扰；n存储扩充：存储扩充：在逻辑上为用户提供一个比实际内存更大的存储空间。地址及地址变换地址及地址变换n地址（地址（Address），），是存储空间中某个可访问单元的编号，它又分逻辑地址和物理地址； 逻辑地址：逻辑地址：编程时所使用的地址，又称相对地址、虚地址； 逻辑空间：逻辑空间：逻辑地址的集合，有时就叫地址空间； 物理地址：物理地址：内存

3、中的地址，又称绝对地址、实地址； 物理空间：物理空间：物理地址的集合，也叫存储空间，主存空间；n地址变换：地址变换：将逻辑地址转换为物理地址，又称地址映射、地址重定位。 地址变换分为两类：n静态地址变换；n动态地址变换；静态地址变换静态地址变换 mov ax,500 mov ax,500 54321 54321 mov ax,1000+500 mov ax,1000+500 54321 54321 0100500999 0 1000 1100 1500 19991M-1程序的地址空间主存空间重定位装入程序在程序装入时一次完在程序装入时一次完成，以后不再改变。成，以后不再改变。静态重定位时只须修

4、改指令内部的地址；修改后静态重定位时只须修改指令内部的地址；修改后CPU以物理地址执行程序。以物理地址执行程序。动态地址变换动态地址变换 mov ax,500mov ax,500 54321 54321 mov ax,500mov ax,500 54321 54321 0100500999 0 1000 1100 1500 19991M-1作业的地址空间存储空间5001000逻辑地址重定位寄存器在程序执行的过在程序执行的过程中动态地进行。程中动态地进行。CPU以逻辑地址执行程序，在执行中动态地将逻辑地址转换成物理地址。以逻辑地址执行程序，在执行中动态地将逻辑地址转换成物理地址。7.2 分区存储

5、管理分区存储管理n本章讲述的存储管理方法包括分区管理、分页管理、分段管理和段页式管理等。这里先说分区管理；n分区存储管理是多道程序系统中采用的一种最简单的存储管理方法。它把内存的用户空间划分为若干大小不等的区域，每个进程（每道程序）占用一个区域；n分区存储管理又分为：n固定分区管理；n动态分区管理；7。2。1 固定分区存储管理固定分区存储管理n方法：方法：固定分区存储管理方法将内存空间划分为若干个固定大小的分区，每个分区中可以装入一道程序。分区的个数及每个分区的位置和大小在运行期间不能改变；n管理：管理：系统需要建立一张分区使用表，以记录系统中的分区数目、分区大小、分区起始地址及状态；n分配：

6、分配：当有用户程序要装入时，由内存分配程序检索分区使用表，从中找出一个能满足要求的空闲分区分配给该程序，然后修改分区说明表中相应表项的状态；若找不到大小足够的分区，则拒绝分配内存；n回收：回收：当某程序执行完毕时，释放程序占用的分区，管理程序只需将对应分区的状态置为未分配即可；n特点：特点：管理简单但存储空间利用率较低。固定分区管理举例 操作系统 分区号 大小 起始地址 状态 1 8KB 20KB 已分配 2 32KB 28KB 已分配 3 32KB 60KB 未分配 4 120KB 92KB 未分配 5 300KB 212KB 已分配 0 20KB 28KB 60KB 92KB 212KB5

7、12KB-1进程A（6K）进程B（24K）进程C（128K）1 2 3 4 57。2。2 动态分区存储管理动态分区存储管理n动态分区存储管理又称为可变分区存储管理，这种管理方法是在系统的运行过程中动态地产生和回收分区。系统初启时，整个用户空间就是一个分区，然后根据运行的需要，在分配和回收的过程中逐渐产生和合并新的分区。因此，在这种方法下，系统内分区的个数及每个分区的大小都是动态变化的。系统空间用户空间系统初启时，整个用户空间就是一个分区。动态分区管理中的数据结构动态分区管理中的数据结构n在动态分区管理中常用的数据结构有：n空闲分区表：空闲分区表：用一个空闲分区表来登记系统中的空闲分区，表项内容

8、包括分区的大小和起始地址；n空闲分区链：空闲分区链：在空闲分区内部拿出一点空间用以建立链表，将所有的空闲分区链接起来，构成空闲分区链，供空间分配和回收时查询；n比较而言，空闲分区表查询起来速度较快，但需要额外的空间开销；空闲分区链查询起来较慢，但不需要额外的空间开销，其用以建立链表的空间也可以供分配。空闲分区表示意图空闲分区表示意图分区号 大小 起始地址 1 8KB 24KB 2 12KB 128KB 3 8KB 248KB 4 5 操作系统 空闲 (8K) 已分 (96K) 空闲 (12K) 已分 (108K) 空闲 (8K) 0 24KB 32KB 128KB 140KB 248KB256

9、KB-1空闲分区链示意图空闲分区链示意图 操作系统 空闲 (8K) 已分 (96K) 空闲 (12K) 已分 (108K) 空闲 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1 操作系统 空闲 (8K) 已分 (96K) 空闲 (12K) 已分 (108K) 空闲 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1表头指针分区分配算法分区分配算法n目前常用的分区分配算法有以下几种：目前常用的分区分配算法有以下几种：n首次适应算法（FF：First Fit）；n循环首次适应算法（RFF：Round First Fit）；n最佳适

10、应算法（BF：Best Fit）；n最坏适应算法（WF：Worst Fit）；首次适应算法首次适应算法n首次适应算法又称最先适应算法，该算法要求空闲分区按首地址递增的次序排列；n在进行内存分配时，从空闲分区表（或空闲分区链）头开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止；n然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间，要么作为新的空闲分区仍然留在空闲分区表（或空闲分区链）中，要么作为碎片丢掉；n首次适应法的特点首次适应法的特点：优先利用内存低地址端，以便高地址端逐渐形成大的空闲区；但低地址端有许多小空闲分区时会增加查找开销。循环首次适应算法循环首次适应

11、算法n循环首次适应算法又称下次适应算法，它是首次适应算法的变形；n该算法在为进程分配内存空间时，从上次停下的位置开始查找，直到找到第一个能满足其大小要求的空闲分区为止；n然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间要么作为新的空闲分区仍然留在空闲分区表（或空闲分区链）中，要么作为碎片丢掉；n循环首次适应法的特点：循环首次适应法的特点：使存储空间的利用更加均衡，但会使系统缺乏大的空闲分区。最佳适应算法最佳适应算法n最佳适应算法要求空闲分区按容量大小递增的次序排列；n在进行内存分配时，从空闲分区表（或空闲分区链）头开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为

12、止；n如果该空闲分区大于作业的大小，则从该分区中划出一块内存空间分配给请求者，将剩余空间要么作为新的空闲区仍然留在空闲分区表（或空闲分区链）中，要么作为碎片丢掉；n最佳适应算法的特点：最佳适应算法的特点：按最佳适应算法为作业分配内存，就能把既满足要求又与作业大小最接近的空闲分区分配给作业，这样就可以保留大的空闲区以备大作业使用，但分割后的剩余空闲区很小，往往会被作为碎片丢掉。最坏适应算法最坏适应算法n最坏适应算法要求空闲分区按容量大小递减的次序排列；n在进行内存分配时，只检查空闲分区表（或空闲分区链）中的第一个空闲分区，若第一个空闲分区小于作业要求的大小，则分配失败；n否则从该空闲分区中划出与

13、作业大小相等的一块内存空间分配给请求者，余下的空间要么作为新的空闲分区仍然留在空闲分区表（或空闲分区链）中，要么作为碎片丢掉；n最坏适应法的特点：最坏适应法的特点：剩下的空闲区比较大，但当大作业到来时，其存储空间的申请往往得不到满足。举例举例n下表给出了某系统的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法首次适应算法和最佳适应算法最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求?分区号 大小起始地址132K100K210K150K35K200K4218K220K596K530K采用最佳适应算法分配采用最佳适应算法

14、分配1n申请96K，n选中4号分区，4号分区大小与申请空间大小一致，应从空闲分区表中删去该表项 ，5号记录顺序上移；分区号 大小起始地址15K200K210K150K332K100K496K530K5218K220K分区号 大小起始地址15K200K210K150K332K100K4218K220K采用最佳适应算法分配采用最佳适应算法分配2n申请20K，n选中3号分区，分配后还剩下12K；分区号 大小起始地址15K200K210K150K332K100K4218K220K分区号 大小起始地址15K200K210K150K312K100K4218K220K采用最佳适应算法分配采用最佳适应算法分配

15、3n申请200K,n选中4号分区，分配后剩下18K；n可见，采用最佳适应法是可以满足分配要求的。分区号 大小起始地址15K200K210K150K312K100K4218K220K分区号 大小起始地址15K200K210K150K312K100K418K220K采用首次适应算法分配采用首次适应算法分配1n申请96K，n选中4号分区，进行分配后还剩下122K；分区号 大小起始地址132K100K210K150K35K200K4218K220K596K530K分区号 大小起始地址132K100K210K150K35K200K4122K220K596K530K采用首次适应算法分配采用首次适应算法分配

16、2n申请20K，n选中1号分区，分配后剩下12K；分区号 大小起始地址132K100K210K150K35K200K4122K220K596K530K分区号 大小起始地址112K100K210K150K35K200K4122K220K596K530K采用首次适应算法分配采用首次适应算法分配3n申请200K，n现有的五个分区都无法满足要求，该作业等待；n显然采用首次适应算法显然采用首次适应算法进行内存分配，无法满进行内存分配，无法满足该作业序列的需求。足该作业序列的需求。分区号 大小起始地址112K100K210K150K35K200K4122K220K596K530K空间分配程序空间分配程序n

17、以首次适应以首次适应算法及空闲算法及空闲链表为例，链表为例，申请分区大申请分区大小为小为x， e是是“碎片碎片”大大小的阀值。小的阀值。将剩余量作为“碎片”丢掉开始查表是链表尾？本次无法分配，返回YN空闲区容量x?N继续检查下一项容量xe?YYN将剩余量作为新的分区留在链表中将空间分配给请求者，修改链表分配举例分配举例n假设x=40k，e=2k，t为分得空间的始地址；操作系统用户空间20K42K24Khead40k注意注意:本程序是将高地址部分本程序是将高地址部分的的40K分出去，为什么分出去，为什么要这样做呢？要这样做呢？2KP=head=16KP指向的分区为20K，不够分；Q=P=16K；

18、P=P-link=64K；P指向的分区够分，分出40K；P-size=P-size-40K=2K；2K=阀值，作为新的空闲分区留在链表内；t=P+P-size=64K+2K=66K，返回给申请者；16K64K128KnVoid cmalloc(node * head, int x)n node *p, *q, *t;n p=head;n while ( p-sizelink; n if ( p!=nil )n p -size= p-size-x;n if (p-size link= p- link;n else t=p+ p-size;n n else t=0; printf （“本次无法分配

19、！”n）；n return (t);n 分区回收程序分区回收程序n回收分区时，如果回收区邻接空闲区，则应将它们合并，回收分区时，如果回收区邻接空闲区，则应将它们合并，邻接有四种情况，见邻接有四种情况，见P129。找到回收区在链表中的位置回收区上、下都邻接空闲区吗？三区合并下邻接吗？两区合并上邻接吗？两区合并回收区插入链表ynynny返回内存保护内存保护n存储保护的主要含义是防止程序间的相互干扰和破坏，方法是禁止越界访问；n常用的存储保护方法有：n上下界寄存器法；n基址限长寄存器法；n上下界寄存器法：n用上、下界寄存器分别存放作业存储空间的结束地址和开始地址；n在作业运行过程中，将每一个访问内存

20、的地址都同这两个寄存器的内容进行比较，若超出了上下界寄存器的范围则产生越界中断；n基址、限长寄存器法：n用基址和限长寄存器分别存放作业存储空间的起始地址及作业长度；n当作业执行时，将每一个访问内存的相对地址和这个限长寄存器比较，若逻辑地址超过限长则产生越界中断。7。2。3 碎片问题及拼接技术碎片问题及拼接技术n分区存储管理中，必须把作业装入到一片连续的内存空间中。这种分配方法能满足多道程序设计的需要，但存在碎片问题； n碎片也可称为零头，是指内存中无法被利用的存储空间；n碎片分内部碎片和外部碎片： 内部碎片是指分配给作业的存储空间中未被利用的部分；外部碎片是指系统中无法利用的小存储块；n解决碎

21、片问题的方法之一，是通过移动把多个分散的小碎片拼接成一个大的空闲区，也可称为紧缩或紧凑；n拼接的时空开销较大。拼接示意图拼接示意图n拼接前 拼接后 操作系统 进程5 空闲（10KB） 进程4 空闲（30KB） 进程3 空闲（26KB） 0 40KB 90KB 100KB 170KB 200KB 230KB256KB-1 操作系统 进程5 进程4 进程3 空闲（66KB） 0 40KB 90KB 160KB 190KB 256KB-1拼接需要的技术支持拼接需要的技术支持n动态重定位：动态重定位：拼接后程序在内存的位置发生变化，因此需要动态重定位技术支持；n空闲区放在何处：空闲区放在何处：拼接后的

22、空闲区放在何处不能一概而论，应根据移动信息量的多少来决定；n拼接的时机：拼接的时机：n回收分区时拼接：只有一个空闲区，但拼接频率过高增加系统开销；n找不到足够大的空闲区且系统空闲空间总量能满足要求时：拼接频率小于前者，空闲区管理稍复杂。也可以只拼接部分空闲区。7.3 伙伴系统伙伴系统n固定分区存储管理限制了内存中的进程数，动态分区的拼接需要大量时间，而伙伴系统是一种较为实用的动态存储管理办法；n伙伴系统采用伙伴算法对空闲内存进行管理。系统初启时，整个用户区就是一个空闲块，然后，在运行的过程中通过不断对分大的空闲块来获得小的空闲块，对分出来的空闲块称为“伙伴”（Buddy），每个空闲块的大小为2

23、i；n当内存块释放时，应尽可能合并它的伙伴空闲块；n伙伴系统的主要优点是分配和回收空间的时间开销比最佳适应法和首次适应法要小，其缺点是可能浪费许多存储空间。伙伴系统的分配和回收伙伴系统的分配和回收n伙伴系统的存储分配方法是：伙伴系统的存储分配方法是： 当进程申请大小为n的空间时，设2i-1n2i，则为进程分配大小为2i的空间；如系统不存在大小为2i的空闲块，则查找系统中是否存在大于2i的空闲块，若找到则对其进行对半划分，直到产生大小为2i的空闲块为止。n伙伴系统的存储回收方法是：伙伴系统的存储回收方法是： 当进程释放存储空间时，应检查释放块的伙伴是否空闲，若空闲则合并；这个较大的空闲块也可能存

24、在空闲伙伴，此时也应合并；重复上述过程，直至没有可以合并的伙伴为止。伙伴地址计算公式伙伴地址计算公式n设某空闲块的开始地址为d，长度为2K，其伙伴的开始地址为：nBuddy（k，d）=d+2k，若d % 2k+1=0nBuddy（k，d）=d-2k， 若d % 2k+1= 2kn如果参与分配的2m个单元从a开始，则长度为2K、开始地址为d的块，其伙伴的开始地址为：nBuddy（k，d）=d+2k，若（d-a）% 2k+1=0nBuddy（k，d）=d-2k， 若（d-a）% 2k+1= 2k伙伴系统分配及回收的举例伙伴系统分配及回收的举例n设系统中初始内存空间大小为1MB，进程请求和释放空间的

25、操作序列为：n进程A申请200KB；B申请120KB；C申请240KB； D申请100KB；n进程B释放；E申请60KB；n进程A、C释放；n进程D释放；进程E释放。E A释放分配过程示意图分配过程示意图n 0 128K 256K 384K 512K 640K 768K 896K 1M初始状态A申请200B申请120C申请240D申请100 B释放 E申请60 C释放 D释放 E释放512K256KAA512K128KBAB256KCAB256KCDA256KCD128KA256KCD64E256KCD64E256KD64256K512KE64256K512K128K128K伙伴系统的二叉树表

26、示伙伴系统的二叉树表示n可以用二叉树表示内存分配情况。叶结点表示存储器中的当前分区，如果两个伙伴是叶子，则至少有一个被分配。n右图表示A（200）、B（120）、C（240）、D（100）分配之后的情况。ABDC1M512K256K128K7.4 分页存储管理分页存储管理7。4。1 基本原理基本原理n分区管理中，要求将一道程序装在内存的一片连续的空间，这有可能降低空间的利用率，或者加大紧凑和拼接的时间开销。为了克服这种缺点，提出了分页管理的思想和方法；n在分页存储管理中，将程序的逻辑地址空间和主存的物理空间按同样的大小划分成若干个页面（块），为了区分，逻辑空间的叫“页”（page），物理空间的

27、叫“块”（block）。然后，以块（页）为单位为进程分配空间。这样，同一道程序就可以装在若干个不连续的页面内，从而提高内存空间的利用率。程序逻辑空间内存物理空间012301234567从图示的分配方法可以看出，一道程序在内存是以页面为单位存放的，同一道程序的页面之间可以是不连续的，次序也是随意的。7。4。2 数据结构数据结构n为了支持分页存储管理，虚要建立以下数据结构：为了支持分页存储管理，虚要建立以下数据结构： 1，页表（PT：Page Table）； 2，存储分块表（MBT：Memory Blocking Table）； 3，进程请求表（PRT：Process Request Table）

28、； 下面逐一说明。下面逐一说明。页表（页表（PT）n页表每个进程一张，记录该进程每个页面所分得的物页表每个进程一张，记录该进程每个页面所分得的物理块。理块。内存空间程序的地址空间页表 0页1页2页n页 0 2 1 4 2 7 页号 块号01234567页面大小的选择页面大小的选择n页面的大小应适中。若页面太大，以至和一般进程大小相差无几，则页面分配退化为分区分配，同时页内碎片也较大。若页面太小，虽然可减少页内碎片，但会导致页表增长。因此，页面大小应适中，通常为2的幂，一般在512B到4KB之间。n页表一般存放在内存中。也可以在页表中设置存取控制字段，以实现存储保护。存储分块表（存储分块表（MB

29、T）n存储分块表用来记录内存中各物理块的使用情况及未分配物理块总数。n存储分块表可用下述方式表示：n位示图：利用二进制的一位表示一个物理块的状态，1表示一分配，0表示未分配。所有物理块状态位的集合构成位示图。n空闲存储块链：将所有的空闲存储块用链表链接起来，利用空闲物理块中的单元存放指向下一个物理块的指针。存储分块表（存储分块表（MBT）n存储分块表用来记录内存中各物理块的使用情况及未分配物理块总数；n存储分块表可用下述方式表示：n位示图：位示图：利用二进制的一位表示一个物理块的状态，1表示已分配，0表示未分配。所有物理块状态位的集合构成位示图；n空闲存储块链：空闲存储块链：利用空闲物理块中的

30、单元存放指向下一个物理块的指针，将所有的空闲存储块用链表链接起来。 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4进程请求表进程请求表n请求表用来登记每个进程的页表在内存中的物理位置及每个页表的长度、状态等。如下图所示。进程号 请求页面数页表始址页表长度状态010102410已分120103420已分215105415已分328未分 7。4。3 存储空间的分配

31、及回收存储空间的分配及回收n页面分配：页面分配：计算进程所需页面数，然后在请求表中登记进程号、请求页面数等。如存储分块表中有足够的空闲块可供进程使用，则在系统中取得页表始址，并在页表中登记页号及其对应的物理块号。否则无法分配；（见P138的程序）n页面回收：页面回收：将存储分块表中相应的物理块改为未分配，或将回收块加入到空闲存储块链中，并释放页表，修改请求表中的页表始址及状态；7。4。4 地址变换机构地址变换机构n地址变换机构的任务是实现逻辑地址到物理地址的转地址变换机构的任务是实现逻辑地址到物理地址的转换，即在程序动态执行的过程中，将换，即在程序动态执行的过程中，将CPU的访存逻辑的访存逻辑

32、地址变换成内存的物理地址；地址变换成内存的物理地址；n分页地址变换机构自动地将逻辑地址分为页号和页内分页地址变换机构自动地将逻辑地址分为页号和页内位移，例如，逻辑地址的长度为位移，例如，逻辑地址的长度为20位（逻辑空间的大位（逻辑空间的大小为小为220=1M），页面大小为），页面大小为1K，则页内位移量，则页内位移量W=10位（位（90，210=1K，注意：页的大小一定是注意：页的大小一定是2的整数次方的整数次方），页号），页号P=10位（位（1910），如下图所），如下图所示：示：19 10 9 019 10 9 0 页页 号号 P 页页 内内 位位 移移W地址变换过程地址变换过程n将页号与

33、页表长度进行比较，如果页号超过了页表长度，则表示本次所访问的地址已超越进程的地址空间，系统产生地址越界中断；n若未出现越界，则由页表始址和页号计算出相应页表项的位置，从中得到该页的物理块号；n将逻辑地址中的页内位移与上面得到的物理块号拼接在一起，就形成了访问主存的物理地址；地址变换示意图地址变换示意图n为什么是拼接而不是相加？为什么是拼接而不是相加？页表寄存器页表始址 页表长度越界中断逻辑地址 页号（2） 页内位移（452）页号 块号2385101234 8 452物理地址页表地址变换举例地址变换举例n设逻辑地址为20位，页面大小为1K字节，作业的0、1、2页分别存放在第2、3、8块中。则逻辑

34、地址2500的页号及页内地址分别为：2500/1024=2（页号）；2500 %1024452（页内地址）；n查页表可知第2页对应的物理块号为8；n将块号8与页内地址452拼接得到物理地址为： 810244528644；8644就是本次CPU访存的物理地址。n2500（10）的二进制表示是：的二进制表示是：0000000010 0111000100 P W联想（相联）存储器及快表联想（相联）存储器及快表n因页表放在主存中，故存取指令或数据时CPU至少要访问两次主存。降低了内存访问速度。n为了提高地址变换速度，可在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器（又称联想存储器或快表），用

35、以存放当前访问的那些页表项；n地址变换机构自动将页号与快表中的所有页号进行并行比较，若其中有与此匹配的页号，则取出该页对应的块号，与页内地址拼接形成物理地址；n若页号不在快表中，则再到主存页表中取出物理块号，与页内地址拼接形成物理地址；n同时还应将这次所查到的页表项存入快表中，若快表已满，则必须按某种原则淘汰出一个表项以腾出位置。具有联想存储器（快表）的地址变换具有联想存储器（快表）的地址变换n页表与快表有何不同？快表该多大？页表与快表有何不同？快表该多大？页表寄存器 页表始址 页表长度越界中断逻辑地址 页号 页内位移页号 块号 01234 物理地址页表页号 块号快表7。4。5 多级页表及反向

36、页表多级页表及反向页表n现代计算机系统都支持非常大的逻辑地址空间，致使页表很大，用连续空间存放页表显然不现实；n如逻辑地址32位，页面大小4KB，则页表项为1M，若每个页表项占4字节，则页表共需要4MB内存空间；n解决方案：n用离散方式存储页表n仅将当前需要的部分页表项放在内存，其余放在磁盘上，需要时再调入。两级页表及多级页表两级页表及多级页表n将页表再分页，使每页与内存物理块大小相同，并为它们进行编号0、1、，同时还为离散存放的页表建立一张页表。n例如：32位地址可以划分为31 22 21 12 11 0 一级页号p1 二级页号p2 页内地址w两级页表结构两级页表结构第0页页表内存空间一级页

37、表 200020242700 2 7 0123456785901411012n 0 1 2 1023 85 90 第1页页表 0 1 21023 1411 0 1 21023第n页页表具有两级页表的地址变换机构具有两级页表的地址变换机构 n利用逻辑地址中的一级页号作为索引访问一级页表，找到第二级页表的起利用逻辑地址中的一级页号作为索引访问一级页表，找到第二级页表的起始地址；始地址；n再利用第二级页号找到指定页表项，从中取出块号与页内地址拼接形成物再利用第二级页号找到指定页表项，从中取出块号与页内地址拼接形成物理地址。理地址。 第一级页表寄存器逻辑地址+二级页表一级页表 b w物理地址一级页号

38、二级页号 页内地址 p1 p2 wb反向页表及其地址变换反向页表及其地址变换n为解决页表占用大量存储空间的问题，另一种创新思路是引入反向页表；n反向页表为每个物理块设置一个页表项，并将它们按物理块号大小排序，表项内容为页号及其所属进程的标识号（如果已分配）；n利用进程标识号及页号检索反向页表，若找到相应的页表项，则将其物理块号与页内地址拼接；否则请求调入该进程相应页，在无调页功能的系统中则出错；n由于反向页表中没有存放进程中尚未调入页，因此必须为每个进程建立一张传统页表并存放在外存中，当所访问页不在内存时使用这张页表。页表中包含各页在外存的地址。反向页表的地址变换反向页表的地址变换n反向页表有

39、什么不足？反向页表有什么不足？逻辑地址逻辑地址进程标识号进程标识号 页号页号反向页表反向页表 b w物理地址物理地址 页号页号 页内地址页内地址 p w pid ppid p进程标识号进程标识号pid 0 1 2 bn n7.4.6 存储保护存储保护n分页存储管理采用两种方式保护内存：n地址越界保护：页表长度与逻辑地址中的页号比较；n存取控制保护：在页表中增加保护位；7。5 分段管理分段管理n7。5。1 原理原理n由于分页按物理单位进行，没有考虑程序段的逻辑完由于分页按物理单位进行，没有考虑程序段的逻辑完整性，给程序段的共享和保护带来不便，另外动态链整性，给程序段的共享和保护带来不便，另外动态

40、链接及段的动态增长也要求以逻辑上完整的程序段为单接及段的动态增长也要求以逻辑上完整的程序段为单位管理，于是提出分段管理；位管理，于是提出分段管理；n在分段存储管理系统中，作业的地址空间由若干个逻在分段存储管理系统中，作业的地址空间由若干个逻辑分段组成，每个分段是一组逻辑意义相对完整的信辑分段组成，每个分段是一组逻辑意义相对完整的信息集合，每个分段都有自己的名字，每个分段都从息集合，每个分段都有自己的名字，每个分段都从0开开始编址，每个分段都有一个编号，从而形成一个二维始编址，每个分段都有一个编号，从而形成一个二维的地址空间；的地址空间；n在进行存储分配时，以段为单位分配内存，每段分在在进行存储

41、分配时，以段为单位分配内存，每段分在一个连续的内存区，但各段之间不要求连续。一个连续的内存区，但各段之间不要求连续。分段管理的逻辑地址结构和二维空间分段管理的逻辑地址结构和二维空间n在分段管理下，CPU访存的逻辑地址由段号S和段内位移量W两部分组成，如下图所示的逻辑地址，共有64K个段，每个段的长度为64K字节。010101010段1段2段3段代码段数据段栈段扩展段程序的二维程序的二维地址空间地址空间31 16 15 0 段 号 S 段 内 位 移 W7。5。2 实现实现一一 数据结构数据结构n段表：段表：每个进程建立一个段表，段表的每个表项记录该进程一段的相关信息，包括：n段号；n段长；n段

42、在内存的起始地址；n其他信息；n空闲块表或空闲块链：空闲块表或空闲块链：形式与分区管理相同，用来记录空闲段的现状；段表的作用段表的作用内存空间作业的地址空间段表 30K 40K 20K 80K 15K 120K 10K 150K段号 段长 基址040K80K120K150K(MAIN)=0030K(X)=1020K(D)=2015K(S)=3020K0123 (MAIN)=0 30K (X)=1 20K (D)=2 15K (S)=3 15K二二 地址变换地址变换n为实现从逻辑地址到物理地址的转换，在系统中设置了段表为实现从逻辑地址到物理地址的转换，在系统中设置了段表寄存器，用于存放段表始址和

43、段表长度；寄存器，用于存放段表始址和段表长度；n为了提高内存的访问速度，段表也可以存放在快表内；为了提高内存的访问速度，段表也可以存放在快表内；n进行地扯变换时，系统将逻辑地址中的段号与段表长度进行进行地扯变换时，系统将逻辑地址中的段号与段表长度进行比较，若段号超过了段表长度则产生越界中断；比较，若段号超过了段表长度则产生越界中断；n否则根据段表始址和段号计算出该段对应段表项的位置，从否则根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址；中读出该段在内存的起始地址；n然后再检查段内地址是否超过该段的段长，若超过则同样发然后再检查段内地址是否超过该段的段长，若超过则同样

44、发出越界中断信号；出越界中断信号；n若未越界，则将该段的起始地址与段内位移相加，从而得到若未越界，则将该段的起始地址与段内位移相加，从而得到要访问的内存物理地址。要访问的内存物理地址。地址变换示意图地址变换示意图n设作业分为设作业分为3段，段，0、1、2段长度分别为段长度分别为1K、800、600，分别存放在内存分别存放在内存6K、4K、8K开始的内存区域；开始的内存区域；nCPU访存的逻辑地址（访存的逻辑地址（2，100）的段号为）的段号为2，段内位移，段内位移为为100；n查段表可知第查段表可知第2段在内存的起始地址为段在内存的起始地址为8K；n将起始地址与段内位移相加，将起始地址与段内位

45、移相加，8K1008292，得到得到物理地址为物理地址为8292。段表寄存器 段表始址 段表长度越界中断逻辑地址 段号（2）段内位移（100）段号 段长 始址 1K 6K800 4K600 8K012物理地址8292三三 空间的分配与回收空间的分配与回收n分段管理可以看作是分区管理的扩充，而分区管理可以看作是分段管理的特例。因此，这两种管理方法的空间分配和回收程序是类似的：分区管理为一道程序只分配和回收一段空间，而分段管理要为一道程序分配和回收多段空间，仅次而已。7。5。3 分段与分页的主要区别分段与分页的主要区别n分页管理与分段管理有许多相似之处，但两者在概念上也有分页管理与分段管理有许多相似之处，但两者在概念上也有很多区别，主要表现在：很多区别，主要表现在：n页是信息的物理单位，是为了减少内存碎片及提高内存利页是信息的物理单位，是为了减少内存碎片及提高内存利用率，是系统管理的需要。段是信息的逻辑单位，它含有用率，是系统管理的需要。段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地满足一组意义相对完整的信息，分段的目的是为了更好地满足用户编程的需要；用户编程的需要；n页的