操作系统课件-第4章

第四章 器管理Memory

Management第4章

主要内容4.1

器的层次结构管理方式程序的装入和连续分配对换分页分段管理方式管理方式2021/11/63主要内容4.1

器的层次结构管理方式程序的装入和连续分配对换分页分段管理方式

管理方式2021/11/644.1

器的层次结构从用户的角度来看，

器的主要指标是？容量，速度，价格(每位价格)多级器结构相互速度容量价格最高

最小

最高最低最大最低2021/11/6体系高速缓存Cache：少量、非常快速、昂贵、易变的内存RAM：若干兆字节、中等速度、中等价格、易变的磁盘：数百兆或数千兆字节、低速、价廉、不易变的由操作系统协调这些

器的使用.2021/11/664.1.2

主

器与寄存器主

器（内存，主存，可执行

器）用于保存进程运行时的程序和数据。CPU的控制部件只能从主存中取得指令和数据到CPU寄存器，同样，CPU寄存器中的数据可存入主存。CPU与外设交换数据必须依托于主存。寄存器寄存器 速度最快，与CPU协调工作。2021/11/674.1.3

高速缓存与磁盘缓存1.高速缓存CPU对高速缓存的

，其速度比问寄存器慢。主存快，比访根据程序执行的局部性原理，将主存中一些经常的数据存放在高速缓存中，减少

主存的次数，提高程序的执行速度。内存一级高速缓存二级高速缓存磁盘2021/11/68高速缓存与磁盘缓存2.磁盘缓存内存中一块

区，对应于某固定磁盘，临时

磁盘数据（如，数据预取）。2021/11/69管理的功能分配和回收地址变换共享和保护器扩充2021/11/610基本概念逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中 信息物理地址（绝对地址，实地址）内存中 单元的地址，可直接寻址地址空间程序用来信息所用地址单元的集合，是逻辑（相对）地址的集合，由编译程序生成。空间：主存中物理单元的集合。2021/11/611符号地址、相对地址和绝对地址地址1200Load

A

2003456。。物理地址空间Loata1data1

3456源程序编译连接Load

A

20034560100200逻辑地址空间BA=1000相对地址绝对地址符号地址2021/11/612§4.2

程序的装入和源程序编译目标模块库…..程序装入模块装入程序内存2021/11/613一.程序的装入绝对装入方式可重定位装入方式动态运行时装入方式2021/11/614绝对装入方式(Absolu oading

Mode)

：编译时，编译程序产生的目标代码是绝对地址。装入程序按装入模块中的地址将程序、数据装入

内存，不需修改地址。绝对地址可直接由程序员给出，或在编译或汇编时给出。程序的装入（续）优点：装入过程简单。缺点：过于依赖于硬件结构，适用于单道程序系统。2021/11/615程序的装入（续）可重定位装入方式(Relocation

Loading

Mode)重定位（地址

/地址变换）：经编译得到的目标模块中为相对地址（通常从0开始），即地址都是相对于0开始的。装入模块中的逻辑地址与实际装入内存的物理地址不同。装入内存时，相对地址（数据、指令地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为重定位。2021/11/616可重定位装入方式重定位：根据地址变换进行的时间及采用技术

不同，分为：静态重定位动态重定位2021/11/617可重定位装入方式2021/11/618静态重定位

地址变换是在装入内存时一次完成的，且以后不能移动。

一般情况下,物理地址=相对地址+内存中的起始地址

适用于多道程序环境，可以将装入模块装入到内存中任何允许的位置。优点：不需硬件支持，可以装入有限多道程序。

缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享。250011000MOV

ax,[2500]365程序空间0100001000内存空间0[12500]1250012500

＝

10000址 相对地址物理地址/11/6193、动态运行时装入方式（动态重定位，Dynamic

Run-time

Loading)装入模块中的为相对地址，在装入内存时，并不立即改变为物理地址（绝对地址），即装入后仍为相对地址。只有在程序真正执行到某一步时才对它进行地址转换。优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。缺点：该方式需要一定特殊硬件的支持，OS实现较复杂，是虚拟 的基础。程序的装入（续）2021/11/620二、程序的

是指将编译或汇编后得到的一组目标模块以及所需库函数装配成一个完整的装入模块(执行文件)。目标模块使用的地址是相对的，都是从0开始,

形成

地址空间的装入模块的过程——

。0000装入模块目标模块阶段产生的可执行目标程序在不运行时，通常作为一个二进制可执行文件驻留在硬盘上。2021/11/621程序的–根据时间的不同，可把分成如下三种：静态装入时动态运行时动态2021/11/622程序的1、静态–

在装入内存之前进行，且 后形成一固定的装入模块（也称为可执行程序），不再拆开的方式。Module

Acall

"function1"0L-1Module

B0M-1...}"function1"F

function1(){Module

Acall

L+F0L-1Module

BL...L+M-1

}"function1"L+F

function1(){

完整的包含所有的目标模块后装入2021/11/61.静态这种方式需要解决：对相对地址进行修改。即将各个模块中的相对地址为相对于一个起始地址0的相对地址；变换外部调用符号。即将各个模块中用到的外部调用符号转换为相对地址。2021/11/624目标模块是在装入内存时边装入边

的。由系统装入操作在装入的同时找到需要的其它模块，并

。优点：便于目标模块的修改和更新；便于多个应用程序对目标模块的共享。缺点：每次都要 装入所有的模块，不论是否用到。2.装入时动态2021/11/6253、运行时动态一开始只

装入部分模块;在运行过程中，若发现被调用模块不在内存，则发出请求，由OS查找、装入并

到调用模块上,再执行。装入后具有高效且节省内存空间的优点。2021/11/626静态例例1库模块目标模块100call

1200H1200Hprintf(

“

OK”

);void

printf(…){{}装入模块0静态2021/11/627装入时动态

例例2主模块库模块00void

printf(…){}0

装入模块装入时动态call

1200H装入printf(

“

OK”

);call

1200Hvoid

printf(…){}1200H21200Hcall

21200H20000H2021/11/628运行时动态

例call

33600H内存主模块库模块00例3装入模块void

printf(…){装入printf(

“

OK”

);

printf(“OK”);

执行33600H运行时动态}2021/11/629§4.3

连续分配方式程序空间本来就是连续的用连续的内存装入连续的程序，减少管理工作的难度连续分配指为用户程序分配续的内存空间。2021/11/6302021/11/631连续分配方式分类：单一连续分配方式固定分区分配(fixed

Partitioning)动态分区分配(DynamicPartitioning)伙伴系统动态重定位分区分配(Relacation

Partitioning)4.3.1单一连续分配内存中仅驻留一道用户程序，整个用户区为一个用户独占。内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单用户、单任务的OS。优点：易于管理。缺点：对要求内存空间少的程序，造成内存浪费；例程序全部装入，很少使用的程序部分也占用内存。例如：DOS2.0以下的DOS操作系统采用单一连续区域主存管理方法。2021/11/632单一连续分配早期大型机使用的内存管理方式少数掌上电脑和系统使用的内存管理方式早期PC使用的内存管理方式（MS-DOS)ROM：DEV用户程序RAM中的OS用户程序RAM中的OS用户程序ROM中的OS2021/11/633例：一个容量为256KB的内存，操作系统占用32KB，剩下224KB全部分配给用户作业，如果一个作业仅需64KB，那么就有160KB的空间被浪费。0KB操作系统作业32KB96KB分配给用户的空间256KB-1返回2021/11/634将内存空间分为若干个固定大小的区域，每个分区中可装入一道作业。划分通常是在系统初使化时执行。1、划分分区的方法分区大小相同(Equal-sizepartitions)：主要用于控制多个相同对象的场合。程序太大？程序太小？分区大小不同(Unequal-sizepartitions)：一般可划分多个小分区，适量中等分区，少量大分区。可适应多种类型的作业。2021/11/6354.3.2固定分区分配Operating

System8

M2

M4

M6

M8

M8

M12

M2021/11/636固定分区(大小相同)固定分区(多种大小)固定分区分配（续）2、内存分配：将分区按大小顺序排列，并建立一张分区使用表（可包括分区起址、大小、状态等）。有内容需要装入时，在分区使用表中查找大小能满足且未分配出去的分区，若能找到，则实施分配且修改分区表中的状态。否则，分配。2021/11/637分区号大小(KB)始址(K)状态11530未分配23045已分配35075已分配4100125未分配内存中已分配给用户但未被利用的区域称为“内零头”（内碎片）固定分区分配有内零头产生。若到来作业A，大小为30K，查找该表，找到分区2为满足大小要求的第一个分区。进行分配且修改分区说明表。到来作业B，大小也为30K，查找该表，将分区3分配到来作业C，大小为110K，不进行分配2021/11/638固定分区分配（续）Advantages

：易于实现，开销小。Disadvantages

：–内碎片造成浪费–分区总数固定，限制了并发执行的程序数目。采用的数据结构：分区表－记录分区的大小和使用情况2021/11/6394.3.3动态分区分配思想：根据进程的实际需要，动态地为之分配连续的内存空间。即进程需要多少内存空间，就划分给它多少。如：在实现动态分区分配

管理方式时，必须解决下述三个问题：分区分配中的数据结构；分区分配算法；分区的分配和回收。2021/11/640动态分区分配（续）1、分区分配中的数据结构1）空闲分区表：用表的方式记录内存中的所有空闲分区。每一分区占一表目。可包括序号、分区大小、始址等。分区号大小KB起始地址KB状态132352空闲2……空表目3520504空闲4……空表目5………2021/11/6动态分区分配（续）2）空闲分区链：用链的方式记录每一空闲分区。链上的每一分区中需

指向前后分区的指针及本分区的大小、状态（0表示可用，1表示已用）。352KB32KB504KB520KBNIL空闲分区链头指针状态大小前一块状态大小后一块状态大小前一块状态大小后一块352KB504KB2021/11/6422、分区分配算法Dynamic

Partitioning

Placement

Algorithm考虑将作业装入内存时，选择什么样的内存分区进行分配。2021/11/643动态分区分配（续）分区分配算法首次适应算法（FF，

－Fit）要求：空闲分区以地址递增的次序

。

分配：从链首顺序查找，直至找到一个能满足大小的空闲分区为止。从选中的分区中分出所需的大小，其余部分仍留在空白分区链表里。倾向：利用低址分区。优点：分区组织简单；高址部分可容纳大作业。缺点：低址处外零头多，查找越来越

。2021/11/644作业1作业2作业3作业4外零头2343540

00

10112在低地址部分会积累大量外零头2021/11/645内零头与外零头内存分配性能评价的一类重要指标内零头(Internal

Fragment):分配给用户但用户没有使用的空间“多分配的空间”外零头(External

Fragment

)：没有分配但无法分配的空间太小而无法分配，“分不出去的空间”单一连续分配有较大的内零头分区分配有小于一个分区的内零头2021/11/6462）循环首次适应(Next-fit)

在首次适应算法的基础上，均衡利用整个内存空间

实现：将空白区链表首尾相接形成环形，设置一个查找指针每次查找从上一次停留的位置开始

特点可以均衡利用高址和低址内存减慢了外零头形成的速度外零头虽然不集中在低址部分，但未得到有效解决。“饼干越掰越碎”2021/11/6473）最佳适应算法(BF,Best－Fit)。要求：空闲分区按大小递增的顺序进行分配：从链表头进行顺序查找，直至第一个大小能满足的分区。则为能满足且最接近需要大小的分区。划分。优点：避免“大材小用”缺点：外零头严重；分区组织、空闲分区的回收复杂。2021/11/6484）

适应算法(WorstFit)

要求：空闲分区按从大到小.

分配：从头顺序查找，找到大小能满足的。则为能满足且划分后剩余空间最大的分区。划分。

优点：外零头较少。

缺点：难以满足大作业的要求；分区组织、空闲分区的回收复杂X2021/11/649OS30K使用20K使用5K使用46K020K100K160K210K255K首次适应算法空闲分区表分区号大小起始地址15K160K220K

2K100K

118K330K20K446K210K最佳适应算法空闲分区表分区号大小起始地址130K

12K20K

38K220K100K35K160K446K210K分区号大小起始地址146K

28K210K

228K230K20K320K100K45K160K适应算法空闲分区表30KOS使用20K使用5K使用46K020K100K160K210K255K020K作业A-18K作业序列作业A-18K20KOS30K使用使用5K使用46K100K160K210K255K020K作业序列160K210K255KOS30K使用20K使用5K使用46K100K作业A-18K作业序列例1:2021/11/650例2：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列2021/11/6512021/11/652思考用可变分区(动态重定位)方式管理主存时,假

定主存中按地址顺序依次有5个空闲区,空闲

区的大小依次为32K,10K,5K,228K和100K。现有5个作业A,B,C,D,E.它们各需主存1K,10K,108K

,28K和115K.若采用首次适应算法能把这5个作业按顺序全部装入主存吗?5)快速适应算法(Quick

Fit)又称分类搜索法;系统中设多个空闲分区链表，每个链表中存放容量相同的所有空闲分区；内存中设一张管理索引表，每一个表项对应一种空闲分区类型，用于记录链表表头指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2

KB、4

KB、8

KB等，对于其它大小的分区，如7

KB这样的空闲区，既可以放在8

KB的链表中，也可以放在一个特殊的空闲区链表中。2021/11/653快速适应算法（续）优点：查找效率高；分配时不对空闲区进行分割，因此不会产生碎片。缺点：在分区归还主存时算法复杂，系统开销较大。2021/11/654总

结从查找速度，速度、空闲区利用面进行比较:首次适应算法：搜索速度，回收速度快，同时尽可能地利用了低地址空间，保证了高地址端有较大的空闲区来放置要求内存较多的进程作业。最佳适应算法：找到的空闲区最佳，产生了大量碎片。适应算法：克服了碎片问题，但大作业往往无法运行。2021/11/6552021/11/6563、分区分配操作1）分配步骤：①按某种算法根据请求的大小，在表或链中进行查找；②找不到则结束；找到进行划分。为减少外零头，可设定一下限。若划分后零头小于该下限，则不划分直接分配③修改相应的数据结构。动态分区分配（续）从空白分区链表中选取适当分区mm.size

–

u.size<minsizeu：用户装入模块

minsize：最小分区从m中划出u.size大小的分区给用户m.size

=

m.size

–u.size将分区从链表中移出NY可能形成将分区分配给用户外零头存在内零头分配过程的流程图2021/11/657动态分区分配（续）2）分区回收：根据回收区的首址在相应的数据结构中查找点.分为四种情况：①回收区与点的前一分区相邻：合并、改大小大小前状态大小前一块状态大小后一块大小后相邻状态大小一块块块状态大小一块2021/11/658分区回收②回收区与点的后一分区相邻：合并、改始址、大小③回收区与

点的前、后分区相邻：合并、共用前分区首址、改大小、取消后分区④回收区与

点的前、后分区不相邻：单独建一表项2021/11/6回收区F1……F1回收区F2…F1回收区F2…4.3.4伙伴系统(

)固定分区和动态分区方案存在的问题？算法复杂，回收分区时系统开销大；21表示分配的最小块的尺寸；2m表示分配的最大块的尺寸，通常是可供分配的整个内存空间的大小。对空闲区按照大小分类，相同大小的分区 为一个双向空闲链表；最多可形成k（0≤k≤m

）个链表。2021/11/660伙伴系统（续）进程请求大小为n的

空间时，–首先计算一个i

值，使2i－1<

n

≤

2i；–在空闲分区大小为2i

的空闲分区链表中查找。if

找到，即把该空闲分区分配给进程。else在分区大小为2i＋1的空闲分区链表中寻找;//表明长度为2i的空闲分区已经耗尽if

找到大小为2i＋1

的空闲分区把该空闲分区分为相等的两个分区（一对伙伴），其中一个用于分配，另一个加入分区大小为2i

的空闲分区链表中。else

查找大小为2i＋2

的空闲分区……2021/11/661伙伴系统示例分割及回收合并分区需要时间开销，多用于多处理机系统中。2021/11/6624.3.5哈希算法2021/11/663利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张哈希表，以空闲分区大小为关键字，每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，

从中得到相应的空闲分区链表，实现最佳分配策

略。4.3.6可重定位分区分配引入在动态分区分配中，拼接仅在相邻空白分区之间进行，而散布在内存中的外零头不便拼接。基本思想：紧凑(Compaction

)

将内存中的作业进行移动，使它们相邻接，可使分散的小分区拼接成一个大分区，从而利于作业的装入。例：以时间换空间Compaction技术要求系统具有动态重定位的能力.2021/11/664可重定位分区分配图4-9

紧凑的示意大量消灭外零头作业1作业4作业2作业3移动作业拼接出大分区2021/11/665可重定位分区分配（续）2、动态重定位的实现为支持作业在内存中的移动，应采用动态运行时装入（动态重定位）方式硬件地址变换机构的支持:在系统中设置一个重定位寄存器,用于存放作业在内存中的起始地址。在运行时，有一个相对地址，则执行：物理地址=重定位寄存器+相对地址以得到它在内存中的实际地址。2021/11/666.LOAD

A

200.34.56.0.LOAD

A

200..3456.0100200逻辑地址空间11001300物理地址空间200VR+000BR300紧凑时，只需修改相应的重定位寄存器的值，使之存放新的起始地址。2021/11/66751200动态重定位示意图5000动态分区分配算法流程图请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和≥u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否2021/11/6682021/11/669可重定位分区分配可重定位分区的优缺点：解决了可变分区分配所引入的“外零头”问题。（优点）消除内存碎片，提高内存利用率。（优点）提高硬件成本，紧凑时花费CPU时间。（缺点）4.4对换(Swap)对换指把内存中暂不能运行的进程或暂时不用和

程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。对换是系统行为，是提高内存的利用率的有效措施。常用于多道程序系统或小型分时系统中，与分区管理配合使用。实现：可在系统中设一对换进程，以执行换进内存、换出至外存操作。2021/11/670Schematic

ViewofSwap2021/11/671分类：“整体对换”（进程对换）：对换以整个进程为单位，用于分时系统，以解决内存紧张的问题；“页面对换”（分段对换）：对换以“页”或“段”为单位进行“部分对换”，该方法是实现请求分页及请求分段

器的基础，支持虚存系统。对换（续）2021/11/672对换（续）面的功能：为实现对换，系统需要对换空间的管理进程的换入换出2021/11/673外存被分为两

分，文件区和对换区文件区用于存放文件，对它的管理应重在如何提高

空间的利用率。所以对它采取离散分配方式。对换区存放从内存换出的进程，它们在外存的对换（续）即一个文件可根据当前外存的使用情况，二、对换空被分成多块，分别到不邻接的多个区域中，用指针相连。管理应重在提高进用连续分配方式。存放时间较短，换即把一个换出的进程存放到续的

空间中。2021/11/6742021/11/675三、进程的换出与换入(由对换进程完成)1、换出（swap

out）1）选择：首先选择阻塞或睡眠状态的进程，若有多个，按优先级由低到高进行选择。若没有此状态进程，则选择就绪状态的，仍然按优先级由低到高进行选择。为避免某进程被频繁的换入换出，还应考虑进程在内存中的驻留时间，优先选择驻留时间长的进程。对换（续）2）换入（swap

in）①从PCB集合中查找“就绪且换出”的进程，有多个，则选择换出时间最长的。②根据进程大小申请内存，成功则读入，否则要先执行换出， 入。③若还有可换入进程，则转向①。直至无“就绪且换出”进程或无法获得足够内存空间为止。对换（续）2021/11/676§4.5分页管理方式2021/11/677分页•离散分配方式的引入连续分配方式会产生内/外零头为解决零头问题又要进行紧凑等高开销活动离散分配程序在内存中不一定连续存放根据离散时的基本单位不同，可分为三种：分页 管理分段

管理段页式 管理管理方式Paged

Memory

Management2021/11/678分页管理1.

分页

管理基本思想1）离散的基础分页(Pages)：将程序地址空间分页分块(Frames)：将内存空间分块2）离散分配的体现内存一块可以装入程序一页连续的多个页不一定装入连续的多个块中注：系统中页块的大小是不变的。012n用户程序012m内存2021/11/679分页

管理3）离散分配的优点没有外零头不受连续空间限制，每块都能分出去仅有小于一个页面的内零头程序大小一般不是页大小的整数倍不支持虚拟

，要求把每个作业全部装入内存才能运行，因此又称为纯分页

管理。2021/11/680分页

管理的基本方法2.

解决两个基本问题：

如何进行地址变换从程序逻辑地址到内存物理地址012m程序空间逻辑空间相对地址内存空间物理空间绝对地址内存用户程序301

m-22

13

m-1

如何建立程序空间与主存空间的页表页号块号01232021/11/681实现分页

管理的数据结构页表：每个进程对应1个页表，描述该进程的各页面在内存中对应的物理块号。页表中包括页号、物理块号（还可有存取控制字段，对 块中的内容进行保护）。注意：全部页表集中存放在主存的系统

区中，只有系统

页表，保证安全。作业表：整个系统1张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。空闲块表：整个系统1张，记录主存当前空闲块。2021/11/682作业号页表大小页表始址状态0已分配1未分配21k40k已分配2k

10000H页号块号 存取控制02kR11kW240kRW作业表（JT）页表（PT）2021/11/683页面大小的选择页面大小由机器的地址结构决定。某一机器只能采用一种大小的页面。小页面大页面页面的大小通常在512B~8KB之间。分页

管理方式（续）2021/11/6844.地址变换机构地址变换机构的功能是将用户的逻辑地址转变为内存中的物理地址。逻辑地址由页号和页内位移量组成。页的大小和内存物理块的大小是相同的，所以页内位移量即为物理块内位移量。关键是页号到物理块号的转换，由页表完成。续分页

管理方式（内存用户程序2021/11/6地址变换机构在分页为：页号+页内位移量。管理的逻辑地址表示管理方式中，任一个逻辑地址都可转变•一个32位的逻辑地址，可转化为如下方式：0～11位表示页内位移量，则每页的大小为212

=4KB。12

～

31位表示页号，220=1M，即最多允许有1M页。1）分页12

11

031页号P位移量W2021/11/686地址变换机构分页 管理的逻辑地址表示设有一逻辑地址A，页面大小为L，则在分页管理方式中，它的地址被转换：页号

P=INT[A/L]页内位移量

W=A

MODL逻辑地址为：2170，页面大小为1KB，则

P=INT[2170/1024]=2；W=2170

MOD1024=122这个地址的变换通常由系统中的某些硬件完成。2021/11/687地址变换机构2）基本的地址变换机构使用寄存器存放页表

速度快，成本高。特别对于大的系统，页表很长，不可能都用寄存器实现。一般系统，将页表 在内存中

设置一个页表寄存器（PTR），记录页表在内存中的始址和页表长度。（平时存于PCB中，要运行时才装入PTR中）2021/11/688分页的地址变换机构逻辑地址址+物理地址页表始址 页表大小页表寄存器（PTR内容）>越界？页号块号页表有效地址寄存器1

1+1

100100

1物理地址寄存器设块大小为4100*4+1=4012021/11/689例：在采用页式管理的系统中，作业J的逻辑空间为4页（每页2048字节），且已知该作业的页表为：02142638页表地址2769页号 页内偏移逻辑地址4865物理地址130576769块号块内偏移主存页表寄存器2021/11/6903）具有快表的地址变换机构局部性原理每存取一个数据，需

两次内存。第一次第二次页表，以得到物理地址；物理地址，以得到数据。存取速度几乎降低了一倍，代价太高。器associative的一些页–

增设一高速缓冲

器（联想memory、快表），用来存放最近表项。地址变换机构2021/11/691快表的页号页内地址页表始址页表大小页表寄存器（PTR内容）+块号 块内地址物理地址寄存器有效地址寄存器>越界？页号块号快表在CPU的高速缓存中进行，在CPU的高速缓存中查不到仅

内存一次页表内存两次2021/11/692关于快表的配置快表效果如何，取决于如检索快表时间为20

ns，快表时

中率。内存为100

ns。若能在快表中检索到CPU给出的页号，则CPU存取一个数据共需120

ns。否则，需要220

ns的时间。当

快表时时，其有效中率分别为0%，50%，80%，90%，98%时间如下表所示：2021/11/693%有效

时间T=h

t1+

(1-

h)

t2(ns)0T=0

120

+

1

220=22050T=0.50

120

+

0.50

220=17080T=0.80

120

+

0.20

220=14090T=0.90

120

+

0.10

220=13098T=0.98

120

+

0.02

220=122选用8～12项组成的联想

器，并采用适当的替换策略，在联想

器中匹配成功的可能性可达80%～90%。可见，由于增设了联想

器，而使

数据的时间，比单周期的

时间要延长40%~22%。但如果不引想

器，其时间将延长一倍。2021/11/694分页

管理方式（续）两级和多级页表引入：在系统中，若支持的逻辑地址空间大，则相应的页表长度会很大。如一个具有32位逻辑地址空间的分页系统，页面大小为4KB，则页表

有232/212=220=1M个。每个页表项占4B，一共占4MB。且页表存放在连续的空间中，占有大量的内存。解决方案：页表本身采用离散分配方式；只将当前需要的部分页表项调入内存。2021/11/695两级页表(Two-Level

Page

Table)实现：采用两级页表把页表分页，每个页面的大小与内存物理块的大小相同，从0开始进行

。离散地将各个页表页面分别放在不同的物理块中。建立一个外层页表：实现页表每一页的页号到所存放的物理块号的

。外层页表的表项记录的是某页表分页在内存中的始址。内层页表的表项记录的是某页在内存中的物理块号。如图2021/11/696¡¡012345671141151468内存空间101110780121742n外部页表14…114115…146801102310241025204720482049页表2021/11/697两级页表逻辑地址结构：地址变换：设置一个外层页表寄存器，存放外层页表的始址。2021/11/698外部页号 外部页内地址

页内地址P1P2d逻辑地址£«外部页表寄存器£«db物理地址外部页表 页表……这种方式只是把连续变为离散，页表所占的总空间没有减少甚至增多了。具有两级页表的地址变换机构2、多级页表结构（64位逻辑地址空间）2021/11/699分页

管理方式小结优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。缺点：程序全部装入内存。2021/11/6100练

习某虚拟

器的用户编程空间共32个页面，每页1KB，主存为16KB。假定某时刻该用户页表如下，（主存中只有部分页）。则与逻辑地址0A5C（H）对应的物理地址为（设

块从0开始编址）：页号块号051102437125C

H2021/11/6101设有一页式

管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个

块，试问逻辑地址至少应为多少位？内存空间有多大？思考2021/11/61024.6

分段管理方式2021/11/61034.6.1引入分段共享方便编程程序

程序由若干具有完整逻辑

信息段大小不一模块化设计 意义的信息段组成分页

以页为内存分配单位 页的大小相等如何使内存管理符合程序的模块化设计思想？2021/11/6104...0S工作区段[B]...0EP子程序段[X]0K..CALL

[X]

[E]...CALL

[Y]

[F]..LOAD

1,

[A][G].......0FL子程序段[Y]N..123450G数组[A].12345主程序段[M]2021/11/61054.6.2分段系统的基本原理分段：作业地址空间按逻辑信息的完整性被划分为若干个段；每段有段名（或段号），每段从0开始编址；段内的地址空间是连续的。许多编译程序支持分段方式，自动根据源程序的情况产生若干个段。2021/11/6106分段系统的基本原理分段系统中的逻辑地址是二维的，表示为：–

逻辑地址

=(段号，段内地址)

（区分分页）如一个32位的逻辑地址：段号段内地址31

16

15

0可知每段最大长度为：216=64KB；最多允许有64K

个段.段长？分段数？2021/11/6107分段

管理（续）2.内存分配内存的物理地址空间开始不作划分.类似于动态分区分配方式。以段为基本单位进行连续区的分配，各段之间的内存空间可以是不邻接的。考虑：与动态分区分配的不同？不再以进程为单位分配内存。分配：查找满足某段大小的内存空间，划分。2021/11/6108分段管理（续）3.段表包括段号、段长、段起始地址（基址）等。作用：是实现从逻辑段到物理内存区的

。通常置于内存中。2021/11/6109作业空间(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K012330K40K20K80K15K120K10K150K段号 段长 基址段表(MAIN)=030K(X)=120K(D)=215K(S)=310K内存空间040K80K120K150K利用段表实现地址2021/11/6110段表寄存器段表始址

段表长度物理地址>+越界中断4.分段系统的地址变换机构1002段号S

位移量W段表1K6K6004K5008K2009200段号

段长

基址0123+82928K82928692主存2021/11/6111分段

管理（续）问：若段表放在内存中，每一个数据需要内存两次。可设置联想

器（快表），以提高

速度。优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。缺点：进程全部装入内存。2021/11/6112练

习某作业的段表：段号址段长021912300142901003580496请给出下列各逻辑地址所对应的物理地址：（0，430）（1，10）（2，88）（3，444）（4，112）2021/11/6113分段

管理（续）Characteristics

of Paging

and

Segmentation（1）可见与不可见“分页”是系统活动，用户无法介入，页的大小固定；“分段”是用户可见的，段大小可变。（2）物理单位与逻辑单位页是信息的物理单位，不是完整的逻辑单位；段是完整的逻辑信息单位。（3）地址空间分页的作业空间是一维的，是单一线性空间；分段的作业空间是二维的。2021/11/61144.6.3信息共享分页系统实现段的共享较为

。分段易于实现段的共享和段的保护。例：一个多用户系统可接纳40个用户，它们都执行一个文本编辑程序(ED)，ED代码共160K，每个用户还有40K的数据区(DA)。–不采用信息共享时需占用的内存空间？(

160K

+

40K

)

*

40

=

8000K2021/11/6115例（续）分页系统：设页面大小为4KB代码：160KB

→

40个页面数据区:

40KB→

10个页面–采用信息共享（若ED可共享）后占用的内存空间？160K

+

40K

*

40

=

1760K2021/11/6116-图419分页系统中共享editor的示意图ed1ed2…ed40data1…data10进程1ed1ed2…ed40data1…data10进程22122…6061…70页表2122…6071…80页表…ed1ed2…ed40data1…data10data1…data1021226061707180主存02021/11/6117图4-20分段系统享editor的示意图data1editor进程1data2editor进程2段长基址1608040240段表