计算机操作系统李翠霞os44

1、第四章 存储器管理主讲：李翠霞主讲：李翠霞办公室：水环楼办公室：水环楼306306电话：电话：0371-638872910371-63887291e-mail:e-mail:2reviewreview基本的地址变换机构基本的地址变换机构1具有快表的地址变换机构具有快表的地址变换机构2分页存储管理方式的地址变换：实质是将逻辑地址中的页号，分页存储管理方式的地址变换：实质是将逻辑地址中的页号，转换为内存中的物理块号。转换为内存中的物理块号。可借助于页表实现。可借助于页表实现。若页表驻留在内存中，则在系统中设置一个页表寄存器来存放若页表驻留在内存中，则在系统中设置一个页表寄存器来存放页表在内存中的首

2、地址和页表的长度。这时的地址变换称为基页表在内存中的首地址和页表的长度。这时的地址变换称为基本的地址变换。本的地址变换。若为了提高地址变换速度，引入了快表，则此时的地址变换称若为了提高地址变换速度，引入了快表，则此时的地址变换称为具有快表的地址变换。为具有快表的地址变换。分页系统的地址变换机构分页系统的地址变换机构+物理块号块内地址越界中断 页表始址页表寄存器ptr逻辑地址l物理地址ma寄存器va寄存器页表长度页内地址页号(3)块号页号0115263breview4具有快表的地址变换机构具有快表的地址变换机构2问题：由于页表是存放在内存中的，问题：由于页表是存放在内存中的，cpucpu每存取一

3、个数据，都要两次访每存取一个数据，都要两次访问内存。第一次访问内存中的页表，从中找到指定页的物理块号，再将问内存。第一次访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量块号与页内偏移量ww拼接，以形成物理地址。第二次访问内存时，从第拼接，以形成物理地址。第二次访问内存时，从第一次所得地址中获得所需数据（或向此地址中写入数据）。一次所得地址中获得所需数据（或向此地址中写入数据）。将将cpucpu速度降低速度降低1/21/2。为了提高地址变换速度，可在地址变换结构中增设一个具有并行查询能为了提高地址变换速度，可在地址变换结构中增设一个具有并行查询能力的特殊高级缓冲寄存器，又称为力的

4、特殊高级缓冲寄存器，又称为“联想寄存器（联想寄存器（associative associative memorymemory）”，或称为，或称为“快表快表”。5具有快表的地址变换机构具有快表的地址变换机构2地址变换过程：在地址变换过程：在cpucpu给出有效地址后，由地址变换机构自动地将页号给出有效地址后，由地址变换机构自动地将页号p p送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从

5、快表中读出该页所对应的物理块号，并送到物理地址寄存器中。可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在快表中未找到对应的页表项，则还须再访问内存中的页表，找到后，如在快表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。表。但如果联想寄存器已满，则但如果联想寄存器已满，则osos必须找到一个老的且已被认为不再需要的必须找到一个老的且已被认为不再需要的页表项，将它

6、换出。页表项，将它换出。b页表页表地址越界地址越界l比较比较plpb. . .快表快表页表始址+页号页号p p 页内地址页内地址wbw物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址具有快表的地址映射机构具有快表的地址映射机构7练习练习1 1某系统应用页式存储管理策略，拥有逻辑空间某系统应用页式存储管理策略，拥有逻辑空间3232页，页，每页每页2k2k，拥有物理空间，拥有物理空间1m1m。（1 1）写出逻辑地址的格式。）写出逻辑地址的格式。（2 2）若不考虑访问权限等，进程的页表有多少项？）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？每项至少有多少

7、位？（3 3）如果物理空间减少一半，页表结构应相应作）如果物理空间减少一半，页表结构应相应作怎样的改变？怎样的改变？8练习1参考答案（1 1）由于该系统拥有）由于该系统拥有3232个逻辑页面，所以页号必个逻辑页面，所以页号必须用须用5 5位表示；而每页位表示；而每页2k2k，页内地址需要，页内地址需要1111位来位来描述。描述。（2 2）进程的页表项最多为）进程的页表项最多为3232项；若不考虑访问权项；若不考虑访问权限，每个页表项至少限，每个页表项至少9 9位（因为共有位（因为共有2 22020/2/21111个不同个不同的物理块号，需要的物理块号，需要9 9位即可表示）。位即可表示）。（3

8、 3）如果物理空间减半，则页表中页表项数不变，）如果物理空间减半，则页表中页表项数不变，但每项的长度可减少但每项的长度可减少1 1位。位。9练习练习2 2已知某分页系统，主存容量为已知某分页系统，主存容量为64k64k，页面大小为，页面大小为1k1k，对一个，对一个4 4页大的作业，其页大的作业，其0 0、1 1、2 2、3 3页分别页分别被分配到主存的被分配到主存的2 2、4 4、6 6、7 7块中。块中。（1 1）将十进制的逻辑地址）将十进制的逻辑地址10231023、25002500、35003500、45004500转换成物理地址。转换成物理地址。（2 2）以十进制的逻辑地址）以十进制

9、的逻辑地址10231023为例画出地址变为例画出地址变换过程图。换过程图。n21023y越界(页式地址变换举例)页 号 表长度 页表始址页表寄存器ptr有效地址1023送虚地址寄存器va3071物理地址ma寄存器va寄存器( mmu )地址变换机构地址变换机构页号 块号0 21 42 63 7页表长度1023011练习2参考答案（1 1）逻辑地址）逻辑地址10231023对应的物理地址为对应的物理地址为30713071。（2 2）逻辑地址为）逻辑地址为25002500对应的物理地址为对应的物理地址为65966596。（3 3）逻辑地址为）逻辑地址为35003500对应的物理地址为对应的物理地址

10、为75967596。（4 4）逻辑地址为）逻辑地址为45004500会产生越界中断。会产生越界中断。124.4.3 4.4.3 两级和多级页表两级和多级页表v 逻辑地址空间的扩大导致单页表不可用逻辑地址空间的扩大导致单页表不可用 3232位逻辑地址空间采用分页系统时，若页面大小为标位逻辑地址空间采用分页系统时，若页面大小为标准值（准值（4kb4kb），则每个进程页表中的页表项将有），则每个进程页表中的页表项将有1m1m个，个，每项占用每项占用 一字节时，存储页表需要一字节时，存储页表需要1mb1mb空间。而且还空间。而且还要求是连续的。要求是连续的。v 解决办法解决办法 离散存放离散存放 解决

11、难以找到一块连续的大内存空间的问题解决难以找到一块连续的大内存空间的问题 按需调入页表项按需调入页表项 只将当前需要的部分页表项调入内存，只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。其余的页表项仍驻留在磁盘上，需要时再调入。13两级页表两级页表v外层页表：为解决大型页表对空间的需求，可以外层页表：为解决大型页表对空间的需求，可以将其进一步分页，即对页表再分页后分别离散存将其进一步分页，即对页表再分页后分别离散存放，并对离散的分页表再建立一张页表。放，并对离散的分页表再建立一张页表。v外层页表各表项记录页表分页的物理帧号；内层外层页表各表项记录页表分页的物理帧号；

12、内层页表各表项记录各页面的物理帧号。页表各表项记录各页面的物理帧号。14两级页表两级页表例：设例：设3232位逻辑地址空间中各页面大小为位逻辑地址空间中各页面大小为4kb4kb，采，采用两级页表结构分配内存时，需要对页表再分页，用两级页表结构分配内存时，需要对页表再分页，使每个分页中含有使每个分页中含有10241024个页表项，最多允许有个页表项，最多允许有10241024个页表分页，则此时的逻辑地址结构为个页表分页，则此时的逻辑地址结构为页号页号p1位移量位移量w页号页号p231 22 21 12 11 0 外层页号外层页号外层页内地址外层页内地址页内地址页内地址15两级页表两级页表012n

13、1460121023114115012102314680121023012435671141151468第第0 0页页表页页表第第1 1页页表页页表第第n n页页表页页表16两级页表两级页表.外部页表寄存器外部页表寄存器外部页表外部页表页表页表外部页号外部页号外部页内地址外部页内地址页内地址页内地址p1p1p2p2d dd db b逻辑地址逻辑地址17两级页表两级页表v 页表的离散分配不能解决使用页表的离散分配不能解决使用较少内存空间较少内存空间存放大页表的存放大页表的需求需求v 解决办法解决办法 按需调入页表项：进程或作业装入内存时仅选择当前按需调入页表项：进程或作业装入内存时仅选择当前所需

14、的一批页表项调入内存，以后再根据需要陆续调所需的一批页表项调入内存，以后再根据需要陆续调入入 以两级页表为例，外层页表必须调入内存，内层页表只调入需以两级页表为例，外层页表必须调入内存，内层页表只调入需要的若干页，内层页是否调入内存需要在外部页表的对应表项要的若干页，内层页是否调入内存需要在外部页表的对应表项的状态位中有所体现，程序运行时若发现该位为的状态位中有所体现，程序运行时若发现该位为“尚未调入尚未调入”，则产生中断，请求则产生中断，请求osos调入该页调入该页18多级页表多级页表v 对更加大型的逻辑地址空间（如对更加大型的逻辑地址空间（如6464位），位），两级页表无能为两级页表无能为

15、力力 设页面大小为设页面大小为4kb4kb，页表可用的位数为，页表可用的位数为64-12=5264-12=52位，其位，其中低中低1010位用来标识每个页表分页（内页表）中的各表位用来标识每个页表分页（内页表）中的各表项（每个页表分页是项（每个页表分页是1024kb1024kb），这些表项分别对应一），这些表项分别对应一个物理帧；高个物理帧；高4242位用来标识外层页号位用来标识外层页号 此时外层页表有此时外层页表有4096g4096g个页表项，若每一页表项占用个页表项，若每一页表项占用4 4个字节，则需要的连续内存空间为个字节，则需要的连续内存空间为16384gb16384gbv 一种可能的

16、解决方法是使用多级页表，即对页表进一步分一种可能的解决方法是使用多级页表，即对页表进一步分割，形成三级甚至更多层次的页表割，形成三级甚至更多层次的页表19本章主要内容本章主要内容4.1 4.1 存储器的层次结构存储器的层次结构4.2 4.2 程序的装入和链接程序的装入和链接4.3 4.3 连续分配方式连续分配方式4.4 4.4 基本分页存储管理方式基本分页存储管理方式4.5 4.5 基本分段存储管理方式基本分段存储管理方式4.6 4.6 虚拟存储器的基本概念虚拟存储器的基本概念4.7 4.7 请求分页存储管理方式请求分页存储管理方式4.8 4.8 页面置换算法页面置换算法4.9 4.9 请求分

17、段存储管理方式请求分段存储管理方式204.5 4.5 基本分段存储管理方式基本分段存储管理方式 段式是从段式是从方便用户角度方便用户角度提出的管理方案，提出的管理方案，为方便用户引入段式管理为方便用户引入段式管理 段式管理优越性段式管理优越性: :页式管理的目的是提高内存利用率。页式管理的目的是提高内存利用率。用户使用的是一维线性地址空间用户使用的是一维线性地址空间：0 0、1 1、2 2、3 3、作业的结构特征消失作业的结构特征消失: : 主程序、子程序、数组、栈主程序、子程序、数组、栈.(1)(1)方便用户编程方便用户编程 (2)(2)便于信息共享便于信息共享(3)(3)便于信息保护便于信

18、息保护 (4)(4)便于段动态增长便于段动态增长(5)(5)便于动态链接便于动态链接 (6)(6)可以分别编写和编译可以分别编写和编译21段式管理优越性段式管理优越性v 方便编程方便编程 通常，用户把自己的作业按照逻辑关系划分为通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都从若干个段，每个段都从0 0开始编址，并有自己的名字和长开始编址，并有自己的名字和长度；度；v 信息共享信息共享 在实现对程序和数据的共享时，是以信息的逻在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分页系统中的辑单位为基础的。分页系统中的“页页”只是存放信息的物只是存放信息的物理单位，并无完整的意义，

19、不便于实现共享；理单位，并无完整的意义，不便于实现共享；v 信息保护信息保护 信息保护同样是对信息的逻辑单位进行保护；信息保护同样是对信息的逻辑单位进行保护；v 动态增长动态增长 在实际应用中，往往有些段，尤其是数据段，在实际应用中，往往有些段，尤其是数据段，在使用过程中会不断地增长，而事先又无法知道数据段会在使用过程中会不断地增长，而事先又无法知道数据段会增长到多大；增长到多大；v 动态链接动态链接 动态链接要求在运行过程中需要调用某段时，动态链接要求在运行过程中需要调用某段时，才将该段（目标程序）调入内存并进行链接。才将该段（目标程序）调入内存并进行链接。22 段式管理系统的段式管理系统的

20、编译器功能编译器功能，例如，例如pascalpascal语言语言pascalpascal语言编译器在编译过程中可创建如下的段：语言编译器在编译过程中可创建如下的段：全局变量；全局变量；过程调用堆栈；过程调用堆栈；过程（函数）代码；过程（函数）代码；过程（函数）的局部变量。过程（函数）的局部变量。 加载创建进程时会装入所有的段，并为每个段加载创建进程时会装入所有的段，并为每个段分配段号。分配段号。段式管理优越性段式管理优越性23作业的地址空间被划分成若干个段，每个段定义了一作业的地址空间被划分成若干个段，每个段定义了一组逻辑信息；组逻辑信息；每段都有自己的名字，通常用段号代替段名；每段都有自己的

21、名字，通常用段号代替段名；每段都从每段都从0 0开始编址，并采用一段连续的地址空间；开始编址，并采用一段连续的地址空间；段的长度由逻辑信息组的长度决定；段的长度由逻辑信息组的长度决定；逻辑地址是二维的，由段号和段内地址组成。逻辑地址是二维的，由段号和段内地址组成。4.5.2 4.5.2 分段系统的基本原理分段系统的基本原理段号段号段内地址段内地址0 0151516163131该地址结构中，允许一个作业最长有该地址结构中，允许一个作业最长有64k64k个段，每个段的最大个段，每个段的最大长度为长度为64kb64kb。1.分段分段24为每一分段分配一个连续的分区，各段可以离散地移为每一分段分配一个

22、连续的分区，各段可以离散地移入内存中不同的分区中；入内存中不同的分区中；为实现地址变换，应提供一张段映射表，简称为实现地址变换，应提供一张段映射表，简称“段段表表”；每个段在表中占有一个表项，其中记录了该段在内存每个段在表中占有一个表项，其中记录了该段在内存中的起始地址和段的长度；中的起始地址和段的长度；4.5.2 4.5.2 分段系统的基本原理分段系统的基本原理2. 段表段表假设：有主程序段假设：有主程序段mainmain、子程序段、子程序段x x，数据段，数据段d d及栈段及栈段s s等。等。则利用段表可实现地址映射（则利用段表可实现地址映射（p137 p137 图图4-174-17）：）

23、：作业空间作业空间（mainmain）=0=0（x x）=1=1（d d）=2=2（s s）=3=3030k20k015k010k030k40k20k80k15k 120k10k 150k段号段号段长段长基址基址0123(main)=030k(x)=120k(d)=215k(s)=310k内存空间内存空间040k80k120k150k26段表寄存器：存放段表基址和段表长度段表寄存器：存放段表基址和段表长度tltl地址变换过程地址变换过程a a、逻辑地址中的段号、逻辑地址中的段号s s与与tltl比较，若比较，若s stltl，越界，越界中断；反之，根据段表基址和段号所指示的段表项中断；反之，根

24、据段表基址和段号所指示的段表项找到所需段在内存中的基址找到所需段在内存中的基址b b、逻辑地址中的段内偏移、逻辑地址中的段内偏移d d和上一步找到的段长和上一步找到的段长slsl相比较，若相比较，若d d slsl，越界中断；反之，将，越界中断；反之，将d d与段基址与段基址相加得到数据物理地址相加得到数据物理地址4.5.2 4.5.2 分段系统的基本原理分段系统的基本原理3. 地址变换机构地址变换机构273. 地址变换机构地址变换机构1k 6k600 4k500 8k 200 92008k82928692段号段号 段长段长 基址基址0123段表寄存器段表寄存器段表基址段表基址段表长度段表长度

25、 段号段号s s 段内偏移段内偏移d d2100物理地址物理地址内内存存段表段表越界越界8292段表smt段长始址500h 1500h200h 3400h35c4内存段表始址 段表长度段表寄存器11c4段内wva段号sma越界段号01 smt smt对于小系统也可用寄存器来实现对于小系统也可用寄存器来实现对对smtsmt物理概念进一步讨论物理概念进一步讨论: :pdp-11/45pdp-11/45上的上的unixunix用寄存器实现了段式管理用寄存器实现了段式管理: :作业地址空间作业地址空间: : 允许允许8 8个段个段, , 每段每段8k, 8k, 共计共计64k.64k.有有8 8对寄存

26、器对寄存器: : uisa0 uisa7 uisa0 uisa7 段地址寄存器段地址寄存器uisd0 uisd7 uisd0 uisd7 段说明寄存器段说明寄存器存段在内存的始址存段在内存的始址存段的大小存段的大小, ,权限等权限等 内存空间装配内存空间装配: :设主程序占设主程序占3 3个段个段, , 存入内存存入内存a0a0、a1a1、a2a2开始的地址中；数据占开始的地址中；数据占1 1个段个段, , 存入存入a3a3；栈占；栈占1 1个段存入个段存入a4a4。则：。则：a0a0uisa0uisa0，0 0号寄存器存号寄存器存a0a0，0 0段段a1a1uisa1uisa1，1 1号寄存

27、器存号寄存器存a1a1，1 1段段a2a2uisa2uisa2，2 2号寄存器存号寄存器存a2a2，2 2段段a3a3uisa3uisa3，3 3号寄存器存号寄存器存a3a3，3 3段段a4a4uisa4uisa4，4 4号寄存器存号寄存器存a4a4，4 4段段 cpu cpu给出逻辑地址送给出逻辑地址送va:va:0 0131314141515ww012012位位 , ,2 21313= =8k8k 偏移偏移段号段号 s: 07s: 07段内位移量段内位移量wwvava若若cpucpu给出虚地址给出虚地址: 24676 (6064h) : 24676 (6064h) 送送vava分离出分离出

28、: :3 100 3 100 或或 1616进制表示进制表示 3 643 64由由3 3查查 uisa3 , uisa3 , 再由再由uisa3 uisa3 的内容的内容a3a3做基地址做基地址进行地址重定位进行地址重定位, , 求得物理地址求得物理地址: :物理地址物理地址: a3+100 : a3+100 或或1616进制表示进制表示 a3+64ha3+64h0110 0000 0110 0100十进制十进制31练习对于如下所示的段表，请将逻辑地址（对于如下所示的段表，请将逻辑地址（0 0，137137），（），（1 1，40004000），（），（2 2，36003600），（），（5

29、5，230230）转换成物理地址。）转换成物理地址。段号段号内存始址内存始址段长段长050k10k160k3k270k5k3120k8k4150k4k32（0,137）51337（1,4000）越界越界（2,3600）75280（5,230）越界越界333 3）通常段比页大，因而段表比页表短，可以缩短查找时间，）通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。提高访问速度。页式管理和段式管理的比较页式管理和段式管理的比较1. 1. 分页是出于系统管理的需要，分段是出于用户应用的需要。分页是出于系统管理的需要，分段是出于用户应用的需要。2. 2. 一条指令或一个操作数可能会跨越两

30、个页的分界处，而不一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。会跨越两个段的分界处。3. 3. 页大小是系统固定的，而段大小则通常不固定。页大小是系统固定的，而段大小则通常不固定。4. 4. 逻辑地址表示：逻辑地址表示：1 1）分页是一维的，各个模块在链接时必须组织成同一个地）分页是一维的，各个模块在链接时必须组织成同一个地址空间；址空间；2 2）分段是二维的，各个模块在链接时可以每个段组织成一）分段是二维的，各个模块在链接时可以每个段组织成一个一维地址空间。个一维地址空间。3401234567pagedynamic data incrementnote:页式管理与

31、段式管理的比较页式管理与段式管理的比较datacodestackfree space10lm0n002segmentapplication354.5.3 4.5.3 信息共享信息共享分段系统的一个突出优点是易于实现段的共享，允许若干个进分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。程共享一个或多个分段，且对段的保护也十分简单易行。例如：有一个多用户系统，可同时接纳例如：有一个多用户系统，可同时接纳4040个用户，他们都执行一个文本编辑个用户，他们都执行一个文本编辑程序。如果文本编辑程序有程序。如果文本编辑程序有160kb160kb的代码

32、和另外的代码和另外40kb40kb的数据区，则总共需要的数据区，则总共需要有有8mb8mb（40 40 200k 200k）的内存空间来支持）的内存空间来支持4040个用户。个用户。如果如果160kb160kb的代码是可重入的，则无论是分页系统还是在分段系统中，该代的代码是可重入的，则无论是分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间是存空间是1760kb1760kb（4040* *40+16040+160），而不是），而不是8000kb8000kb。假定每个页面大小是。

33、假定每个页面大小是4kb4kb，160kb160kb的代码将占用的代码将占用4040个页面，数据区占个页面，数据区占1010个页面。为实现代码共享，应在个页面。为实现代码共享，应在每个进程的页表中都建立每个进程的页表中都建立4040个页表项，它们的物理块号都是个页表项，它们的物理块号都是2121# #6060# #。在每。在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是6161# #7070# #，7171# #8080# #，8080# #9090# #，。ed 1ed 2ed 40data 1data

34、102122606170ed 1ed 2ed 40data 1data 10进程进程1 1进程进程2 22122607180页表页表页表页表ed 1ed 2ed 40data 1data 10data 1data 10021226061707180主存主存把把smtsmt中的段号指向共享段在内存中的地址即可中的段号指向共享段在内存中的地址即可, ,如如: :数据区1editor进程1数据区2editor进程2地址空间段号01段号01内存data 2data 1editor240k40k180k160k0始址段长段号smt1380k50k180k160k0始址段长段号smt280k240k380

35、k注: 1.页式pmt过大,开销大. 2. editor为纯代码(可再入代码).384.5.4 4.5.4 段页式存储管理方式段页式存储管理方式分页系统：有效地提高内存利用分页系统：有效地提高内存利用分段系统：很好地满足用户需要分段系统：很好地满足用户需要段页式存储管理方式段页式存储管理方式段页式存储管理方式段页式存储管理方式:既具有分段系统的便于实现、分段可共享、既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等优点，又能像分页系统那样很好地解易于保护、可动态链接等优点，又能像分页系统那样很好地解决内存的外部碎片，以及可为各个分段离散地分配内存等问题。决内存的外部碎片，以及可为各个分段离散地分配内存等问题。v 基本原理基本原理 结合分段和分页思想，先将用户程序分成若干段并分别结合分段和分页思想，先