第4章存储器管理

1、第四章第四章 存储器管理存储器管理n重点重点n理解理解重定位的基本概念重定位的基本概念 n掌握掌握动态分区分配方式动态分区分配方式 n掌握理解掌握理解分页存储管理方式分页存储管理方式 n掌握理解掌握理解分段存储管理方式分段存储管理方式 n难点难点n动态分区分配动态分区分配算法算法 n分页和分段地址转换分页和分段地址转换第四章第四章 存储器管理存储器管理n知识点知识点n重定位的基本概念重定位的基本概念 n动态分区分配方式及分配算法、分区保护动态分区分配方式及分配算法、分区保护n对换区的实现对换区的实现n分页存储管理及地址变换，信息共享和保护分页存储管理及地址变换，信息共享和保护n分段存储管理及地

2、址变换，信息共享和保护分段存储管理及地址变换，信息共享和保护第四章第四章 存储器管理存储器管理n存储器包括内存（主存）和外存（磁盘）存储器包括内存（主存）和外存（磁盘）n功能：保存数据；功能：保存数据；n发展方向：高速、大容量和小体积。发展方向：高速、大容量和小体积。n内存在访问速度方面的发展：内存在访问速度方面的发展：DRAM、SDRAM、SRAM，DDRSDRAM等；等；n硬盘技术在大容量方面的发展：接口标准、硬盘技术在大容量方面的发展：接口标准、存储密度等；存储密度等；n主存储器管理技术分为两大类主存储器管理技术分为两大类n实存储器管理实存储器管理n虚拟存储器管理（第虚拟存储器管理（第5

3、章讲述）章讲述）第四章存储器管理 4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配存储器管理方式连续分配存储器管理方式4.4对换（对换（Swapping） 4.5分页存储管理方式分页存储管理方式4.6分段存储管理方式分段存储管理方式4.1 存储器的层次结构存储器的层次结构n4.1.1 多层结构的存储系统多层结构的存储系统n4.1.2 主存储器和寄存器主存储器和寄存器n4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存4.1.1 多层结构的存储系统多层结构的存储系统n存储器的多层结构存储器的多层结构n存储组织是指在存储技术和存储组织是指在存储技术和C

4、PU寻址技术许可的寻址技术许可的范围内组织合理的存储结构。范围内组织合理的存储结构。n依据是访问速度匹配关系、容量要求和价格。依据是访问速度匹配关系、容量要求和价格。n“寄存器寄存器-内存内存-外存外存”结构结构n“寄存器寄存器-缓存缓存-内存内存-外存外存”结构；结构；n微机中的存储层次组织：微机中的存储层次组织：n访问速度越慢，容量越大，价格越便宜；访问速度越慢，容量越大，价格越便宜；n最佳状态应是各层次的存储器都处于均衡的繁最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持忙状态（如：缓存命中率正好使主存读写保持繁忙）；繁忙）；4.1.1 多层结构的存储系统

5、多层结构的存储系统n高速缓存：高速缓存：nData CachenTLB(Translation Lookaside Buffer)n内存：内存：DRAM, SDRAM等；等；n外存：软盘、硬盘、光盘、磁带等；外存：软盘、硬盘、光盘、磁带等；4.1.2 主存储器和寄存器主存储器和寄存器n主存储器，也称可执行存储器主存储器，也称可执行存储器n用于保存进程运行时的程序和数据；用于保存进程运行时的程序和数据；n容量：数百容量：数百MB到数十到数十GB（微机和大中型机），（微机和大中型机），几十几十KB到几到几MB（嵌入式计算机）。（嵌入式计算机）。n访问速度远低于访问速度远低于CPU执行指令的速度执行

6、指令的速度n解决方法：引入寄存器和高速缓存。解决方法：引入寄存器和高速缓存。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器管理功能主存储器管理功能n存储分配和回收存储分配和回收n分配和回收算法及相应的数据结构分配和回收算法及相应的数据结构n地址变换和重定位地址变换和重定位n可执行文件生成中的链接技术可执行文件生成中的链接技术n程序加载程序加载(装入装入)时的重定位技术时的重定位技术n进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构n存储共享和保护存储共享和保护n代码和数据共享代码和数据共享n地址空间访问权限（读、写、执行）地址空间访问权限（读、写、执行）

7、n存储器扩充：存储器的逻辑组织和物理组织；存储器扩充：存储器的逻辑组织和物理组织；n由应用程序控制：覆盖；由应用程序控制：覆盖；n由由OS控制：交换（整个进程空间），虚拟存储的请求调入和控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）预调入（部分进程空间）4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nRAM（random access memory）随机存储器。）随机存储器。按照存储信息的不同，随机存储器又分为静态按照存储信息的不同，随机存储器又分为静态随机存储器（随机存储器（Static RAM,SRAM)和动态随机和动态随机存储器（存

8、储器（Dynamic RAM,DRAM)。n静态存储器（静态存储器（SRAM）n存储原理：由触发器存储数据存储原理：由触发器存储数据 n单元结构：六管单元结构：六管NMOS或或OS构成构成 n优点：速度快、使用简单、不需刷新、静态功耗极优点：速度快、使用简单、不需刷新、静态功耗极低；常用作低；常用作Cache n缺点：元件数多、集成度低、运行功耗大缺点：元件数多、集成度低、运行功耗大 4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史n动态存储器（动态存储器（DRAM）n存贮原理：利用存贮原理：利用MOS管栅极电容可以存储电荷的原管栅极电容可以存储电荷的原理，需刷新

9、；理，需刷新；n刷新刷新(再生再生)：为及时补充漏掉的电荷以避免存储的：为及时补充漏掉的电荷以避免存储的信息丢失，必须定时给栅极电容补充电荷的操作信息丢失，必须定时给栅极电容补充电荷的操作 n刷新时间：定期进行刷新操作的时间。该时间必须刷新时间：定期进行刷新操作的时间。该时间必须小于栅极电容自然保持信息的时间（小于小于栅极电容自然保持信息的时间（小于2ms）。）。 n优点：优点： 集成度远高于集成度远高于SRAM、功耗低，价格也低、功耗低，价格也低 n缺点：因需刷新而使外围电路复杂；刷新也使存取缺点：因需刷新而使外围电路复杂；刷新也使存取速度较速度较SRAM慢，所以在计算机中，慢，所以在计算机

10、中，DRAM常用于常用于作主存储器。作主存储器。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nSIMM（Single In-lineMemory Modules）n单边接触内存模组，单边接触内存模组，80286上使用，容量为上使用，容量为30pin，256kb，由，由8片数据位和片数据位和1片检验位组成组成一个片检验位组成组成一个bank。因此，常由。因此，常由4条一起使用。条一起使用。n386,486使用使用72pin SIMM支持支持32bit快速页模式内存，快速页模式内存，容量为容量为512kb2mb，仅要求，仅要求2条一起使用。条一起使用。n与与30p

11、in不兼容，因此淘汰了不兼容，因此淘汰了30pin SIMM。nFPMDRAM：（：（FastPageMode），在），在386时代很流时代很流行。行。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nEDODRAM：(Extended Data Out)，19911995年年n取消了扩展数据输出与传输内存两个存储周期之间取消了扩展数据输出与传输内存两个存储周期之间的时间间隔，数据发给的时间间隔，数据发给CPU同时访问下一个页面。同时访问下一个页面。n速度比普通速度比普通DRAM快快1530%。n主要应用于主要应用于486及早期及早期pentium，分为，分为72

12、pin和和168pin两种。两种。n单条容量已达单条容量已达416MB。n由于由于Pentium及更高及更高CPU支持支持64bit，故，故EDO RAM与与FPM RAM都必须成对使用。都必须成对使用。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDIMM：Dual-Inline-Memory-Modules,即双列直插式即双列直插式存储模块存储模块nDIMM提供了提供了64位的数据通道，因此它在奔腾主板位的数据通道，因此它在奔腾主板上可以单条使用。它有上可以单条使用。它有168条引脚，故称为条引脚，故称为168线内线内存条。存条。nSO-DIMM（Smal

13、l Outline DIMM Module）：它的）：它的尺寸比标准的尺寸比标准的DIMM要小很多，而且引脚数也不相要小很多，而且引脚数也不相同。同。nFB-DIMM （Full Buffered DIMM） ：每个：每个DIMM上的缓冲区是互相串联的，之间是点对点的上的缓冲区是互相串联的，之间是点对点的连接方式，数据会在经过第一个缓冲区后传向下一连接方式，数据会在经过第一个缓冲区后传向下一个缓冲区。个缓冲区。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nRIMM：Rambus Inline Memory ModulenRambus生产的生产的RDRAM内存所

14、采用的接口类型。内存所采用的接口类型。nRIMM非非ECC版有版有16位和位和32位数据宽度，位数据宽度，ECC版则版则都是都是18位宽。位宽。nRIMM非非ECC版版16位内存每面位内存每面92线，双面线，双面184线。线。32位内存每面位内存每面116线，双面为线，双面为232线。线。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nSDRAM：（：（Synchronous Dynamic）n第一代使用第一代使用PC66规范，由于规范，由于Intel与与AMD之争，之争，CPU外频提升到外频提升到100MHz，PC66很快被很快被PC100取代，取代，接着接着

15、133MHz的的PIII与与K7出现，出现，PC133规范进一步规范进一步提高提高SDRAM的整体性能，带宽提高到的整体性能，带宽提高到1GB/sec以上。以上。nSDRAM带宽为带宽为64bit，与，与CPU完全对应，故仅需一完全对应，故仅需一条就可与工作。条就可与工作。nRAM与与CPU以相同的时钟频率控制，使它们与外频以相同的时钟频率控制，使它们与外频同步，速度明显超越同步，速度明显超越EDO。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nRDRAM：（：（Rambus DRAM）nIntel与与Rambus联合推广。采用类联合推广。采用类RISC（Re

16、ducde Instruction Set Computing）理论，减少数据的复杂）理论，减少数据的复杂性，提高整个系统的性能。性，提高整个系统的性能。nPC600，PC700的的RDRAM出现出现Intel820芯片组芯片组“失失误事件误事件”，PC800 RDRAM成本过高，成本过高，PC1066 也无也无法力挽狂澜。法力挽狂澜。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDDRSDRAM：Double Data Rate SDRAMn双倍速率双倍速率SDRAM，可以认为是，可以认为是SDRAM的升级的升级nDDR在时钟脉冲的上升沿和下降沿各传输一次数

17、据，在时钟脉冲的上升沿和下降沿各传输一次数据，故比传统故比传统SDRAM速度快一倍。速度快一倍。n由于仅多使用下降信号传输数据，故不会增加能耗。由于仅多使用下降信号传输数据，故不会增加能耗。至于定址与控制信号则与传统至于定址与控制信号则与传统SDRAM相同采用时相同采用时钟上升沿传输。钟上升沿传输。nDDRn第一代第一代DDR200没有得到推广；没有得到推广；n第二代第二代PC266 DDR SDRAM由由PC133 SDRAM衍生得到。衍生得到。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDDRSDRAM：Double Data Rate SDRAMnDD

18、Rn随后出现随后出现DDR 333，DDR 400，双通道，双通道DDR 400，DDR 533。nDDR2nJEDEC组织提出组织提出DDR2标准，加上标准，加上LGA775的的915/925以及以及945。n融入融入Post CAS、OCD（Off-Chip Driver）、）、ODT（On Die Termination）等新性能指标和中）等新性能指标和中断指令，提升内存带宽的利用率。断指令，提升内存带宽的利用率。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDDRSDRAM：Double Data Rate SDRAMnDDR2n采用采用400，667

19、 ，800 ，1000MHz等不同等不同的时钟频率。的时钟频率。n采用采用200、220、 240pin的的FBGA封装形式。封装形式。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDDRSDRAM：Double Data Rate SDRAMnDDR3n使用了使用了SSTL 15的的I/O接口，运作接口，运作I/O电压是电压是1.5V，采用采用CSP、FBGA封装方式包装。封装方式包装。n新增了更为精进的新增了更为精进的CWD（作为写入延迟之用）、（作为写入延迟之用）、Reset（提供了超省电功能的命令）、（提供了超省电功能的命令）、ZQ（新增（新增校准功能

20、）、校准功能）、SRT（Self-Reflash Temperature，可编程化温度控制内存时脉功能）、可编程化温度控制内存时脉功能）、PASR（Partial Array Self-Refresh）局部）局部Bank刷新功刷新功能。能。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDDRSDRAM：Double Data Rate SDRAMnDDR4n内存规格原计划在内存规格原计划在2011年制定完成，标准规范的年制定完成，标准规范的正式公布是在正式公布是在2012年年9月底，月底， 2012年开始投入生年开始投入生产并上市的。产并上市的。n于于2014

21、年首先用于服务器领域，支持桌面很可年首先用于服务器领域，支持桌面很可能要等到再往后的能要等到再往后的14nm工艺新架构工艺新架构“Skylake”。4.1.2 主存储器和寄存器主存储器和寄存器n主存储器发展历史主存储器发展历史nDDRSDRAM：Double Data Rate SDRAMnDDR4，主要变化，主要变化n外观变化明显，金手指变成弯曲状外观变化明显，金手指变成弯曲状n频率提升明显，可达频率提升明显，可达4266MHzn容量提升明显，可达容量提升明显，可达128GBn功耗明显降低，电压达到功耗明显降低，电压达到1.2V、甚至更低、甚至更低4.1.2 主存储器和寄存器主存储器和寄存器

22、n寄存器寄存器n访问速度最快，完全能与访问速度最快，完全能与CPU协调工作，但价协调工作，但价格却十分昂贵，因此容量不可能做得很大。格却十分昂贵，因此容量不可能做得很大。n长度一般以字长度一般以字(word)为单位。为单位。n寄存器的数目，对于当前的微机系统和大中型寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。机系统一般仅有几个到几十个。n作用：加速存储器的访问速度，或加快地址转作用：加速存储器的访问速度，或加快地址转换速度等。换速度等。 4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存n高速

23、缓存高速缓存n介于寄存器和主存储器之间的存储器，主要用介于寄存器和主存储器之间的存储器，主要用于备份主存储器中的数据。于备份主存储器中的数据。n容量：大于或远大于寄存器，而比内存约小两容量：大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十到三个数量级左右，从几十KB到几到几MB。n根据程序执行的局部性原理，将主存中一些经根据程序执行的局部性原理，将主存中一些经常访问的信息存放在高速缓存中，减少访问主常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。存储器的次数，可大幅度提高程序执行速度。4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存n磁盘缓存磁盘缓存n

24、磁盘的磁盘的I/O速度远低于对主存的访问速度，因速度远低于对主存的访问速度，因此将频繁使用的磁盘数据，暂时存放在磁盘缓此将频繁使用的磁盘数据，暂时存放在磁盘缓存中，可减少访问磁盘的次数。存中，可减少访问磁盘的次数。n磁盘缓存本身并不是一种实际存在的存储介质，磁盘缓存本身并不是一种实际存在的存储介质，利用主存中的存储空间，来暂存从磁盘中读出利用主存中的存储空间，来暂存从磁盘中读出(或写入或写入)的信息。的信息。n另外，主存也可以看做是辅存的高速缓存。另外，主存也可以看做是辅存的高速缓存。4.2 程序的装入和链接程序的装入和链接n物理地址物理地址n内存单元所看到的地址。用于内存芯片级的单内存单元所

25、看到的地址。用于内存芯片级的单元寻址，与处理器和元寻址，与处理器和CPU连接的地址总线相对连接的地址总线相对应。又称为应。又称为绝对地址绝对地址。n逻辑地址逻辑地址n由由CPU生成。机器语言指令中，用来指定一个生成。机器语言指令中，用来指定一个操作数或者是一条指令的地址。也称为操作数或者是一条指令的地址。也称为虚拟地虚拟地址址，相对地址相对地址。0X000000000XFFFFFFFF4GB4.2 程序的装入和链接程序的装入和链接n多道程序环境下，程序以进程方式运行；多道程序环境下，程序以进程方式运行；n创建进程创建进程 分配内存分配内存n源程序源程序编译（编译（compile）链接链接(li

26、nk)装入装入(load) 进程进程4.2 程序的装入和链接程序的装入和链接int i=0,n=200;while (in) couti; myprint（i）; i+;0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;编译编译逻辑逻辑地址地址myprint(int i) int j=i*2; coutj;0: j=i*2;1: coutj;2: holt;4.2 程序的装入和链接程序的装入和链接0: i=0;1: n=200;2: if not (in) jmp 7;

27、3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;链接链接0: j=i*2;1: coutj;2: holt;0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;0: j=i*2;1: coutj;2: holt;0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: jmp 8;5: i+;6: jmp 2;7: holt;8: j=i*2;9: coutj;10: jmp 5

28、;4.2 程序的装入和链接程序的装入和链接0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;装入装入i=0;n=200;if not (in) jmp 7;couti;call myprint(i);i+;jmp 2;holt;500050015002500350045005500650074.2.1 程序的装入程序的装入n绝对装入方式绝对装入方式(Absolute Loading Mode) n事先事先确定（知道）确定（知道）了程序将了程序将驻留在内存驻留在内存的的位

29、置位置，即在内存中的即在内存中的绝对地址。绝对地址。n绝对地址的产生绝对地址的产生n程序员直接赋予。不仅要求程序员熟悉内存程序员直接赋予。不仅要求程序员熟悉内存使用情况，而且一旦程序或数据被修改后，使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。可能要改变程序中的所有地址。n编译或汇编时产生。通常在程序中采用符号编译或汇编时产生。通常在程序中采用符号地址，在编译或汇编时，再将符号地址转换地址，在编译或汇编时，再将符号地址转换为绝对地址。为绝对地址。优点优点：程序中的逻辑地址与实际内存地址完全相同，故不：程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。

30、须对程序和数据的地址进行修改。缺点缺点： 程序和数据，不能在内存中移动。适用于单道程序程序和数据，不能在内存中移动。适用于单道程序环境。环境。4.2.1 程序的装入程序的装入n可重定位装入方式可重定位装入方式(Relocation Loading Mode) n在多道程序环境下，绝对装入方式不适合。在多道程序环境下，绝对装入方式不适合。n目标模块的地址通常从目标模块的地址通常从0开始的相对地址开始的相对地址n重定位重定位n在装入时对目标程序中指令和数据的地址修改的过在装入时对目标程序中指令和数据的地址修改的过程。程。n静态重定位静态重定位n地址变换通常是在装入时一次完成的，以后不再改地址变换通

31、常是在装入时一次完成的，以后不再改变。变。4.2.1 程序的装入程序的装入缺点：不断的分配和回收，造成内存中小空闲块很多，总缺点：不断的分配和回收，造成内存中小空闲块很多，总空闲空间量够，但分配不了空闲空间量够，但分配不了办法：紧凑（移动），但该装入方法不支持办法：紧凑（移动），但该装入方法不支持0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;装入装入i=0;n=200;if not (in) jmp 5007;couti;call myprint(i);i+;jmp

32、 5002;holt;500050015002500350045005500650074.2.1 程序的装入程序的装入n动态运行时装入方式动态运行时装入方式(Denamic Run-time Loading) n在把装入模块装入内存后，并不立即把装入模在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，装入内存后块中的相对地址转换为绝对地址，装入内存后的所有地址都的所有地址都仍是相对地址仍是相对地址。n地址转换时机地址转换时机n程序真正要程序真正要执行执行时进行。时进行。4.2.2 程序的链接程序的链接n静态链接方式静态链接方式(Static Linking) n在程序在程序

33、运行前运行前，先将各目标模块及所需的库函，先将各目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开数链接成一个完整的装配模块，以后不再拆开n在将这几个目标模块装配成一个装入模块时，在将这几个目标模块装配成一个装入模块时，需要解决以下两个问题需要解决以下两个问题n对相对地址进行修改对相对地址进行修改n变换外部调用符号变换外部调用符号4.2.2 程序的链接程序的链接n静态链接方式静态链接方式0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;链接链接0: j=i*2

34、;1: coutj;2: holt;0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;0: j=i*2;1: coutj;2: holt;0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: jmp 8;5: i+;6: jmp 2;7: holt;8: j=i*2;9: coutj;10: jmp 5;4.2.2 程序的链接程序的链接n装入时动态链接装入时动态链接(Loadtime Dynamic Linking) n将用户

35、的源程序编译后所得的一组目标将用户的源程序编译后所得的一组目标模块在装入内存时采用模块在装入内存时采用边装入边链接边装入边链接的的方式方式n便于修改和更新便于修改和更新n便于实现对目标模块的共享便于实现对目标模块的共享 4.2.2 程序的链接程序的链接n装入时动态链接装入时动态链接0: i=0;1: n=200;2: if not (in) jmp 7;3: couti;4: call myprint(i);5: i+;6: jmp 2;7: holt;装入装入0: j=i*2;1: coutj;2: holt;i=0;n=200;if not (in) jmp 5007;couti;call

36、 myprint(i);i+;jmp 5002;holt;j=i*2;cout 限长寄存器的值，则产生访问地址限长寄存器的值，则产生访问地址越界中断。越界中断。4.3.6 动态可重定位分区分配动态可重定位分区分配n读写保护读写保护防止操作越权防止操作越权n对于允许多个进程共享的存储区域，每个进程对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权域的访问违反了权限规定，则发生操作越权4.4 对换（对换（Swapping）n内存扩充方法内存扩充方法n目的：在多道环境下，目的：在多道环境下，解

37、决解决在在较小的存储空间较小的存储空间中运行较大程序中运行较大程序的问题的问题n覆盖技术：覆盖技术：主要用在早期的操作系统中；主要用在早期的操作系统中；n交换技术：交换技术：被广泛用于小型分时系统中，它被广泛用于小型分时系统中，它的发展导致了虚存技术的出现。的发展导致了虚存技术的出现。4.4 对换对换n覆盖技术覆盖技术n把程序划分为若干个功能上相对独立的程序段，把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些按照其自身的逻辑结构将那些不会同时执行不会同时执行的的程序段程序段共享同一块内存共享同一块内存区域区域n程序段先保存在磁盘上，当有关程序段的前一程序段先保存在磁盘上，当

38、有关程序段的前一部分执行结束，把后续程序段调入内存，部分执行结束，把后续程序段调入内存，覆盖覆盖前面的程序段前面的程序段（内存（内存“扩大扩大”了）了）n一般要求作业各模块之间有明确的调用结构，一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构程序员要向系统指明覆盖结构，然后由操作系，然后由操作系统完成自动覆盖。统完成自动覆盖。4.4 对换对换n覆盖技术覆盖技术4.4.1 多道程序环境下的对换技术多道程序环境下的对换技术n交换交换(对换对换)技术技术n问题问题n在内存中的某些进程等待某事件发生而被阻塞，但在内存中的某些进程等待某事件发生而被阻塞，但它却占用了大量的内存空间，甚至

39、可能出现在内存它却占用了大量的内存空间，甚至可能出现在内存中所有进程都被阻塞而迫使中所有进程都被阻塞而迫使CPU停止下来等待；停止下来等待；n许多作业在外存上等待，因无内存而不能进入内存许多作业在外存上等待，因无内存而不能进入内存运行。运行。n解决方法解决方法n把把内存内存中暂时不能运行的进程或者暂时不用的程序中暂时不能运行的进程或者暂时不用的程序和数据，调出到和数据，调出到外存外存；n再把已具备运行条件的进程或所需要的程序和数据，再把已具备运行条件的进程或所需要的程序和数据，调入调入内存内存。4.4.1 多道程序环境下的对换技术多道程序环境下的对换技术n对换的类型对换的类型n整体对换整体对换

40、n以整个进程为单位的对换，又称为进程对换。以整个进程为单位的对换，又称为进程对换。n页面对换（分段对换）页面对换（分段对换）n以页（段）为单位进行的对换，又统称为部分对换。以页（段）为单位进行的对换，又统称为部分对换。4.4.2 对换空间的管理对换空间的管理n外存空间划分外存空间划分n文件区：存放文件；文件区：存放文件；n对换区：主要存放从内存中换出的进程。对换区：主要存放从内存中换出的进程。n主要目标主要目标n提高进程换入和换出的速度提高进程换入和换出的速度n对换区空闲盘块的管理中的数据结构对换区空闲盘块的管理中的数据结构n记录对换区的使用情况。形式与内存在动态分区分配记录对换区的使用情况。

41、形式与内存在动态分区分配方式中所用数据结构相似，即用方式中所用数据结构相似，即用空闲分区表或空闲分空闲分区表或空闲分区链区链。n在空闲分区表中的每个表目中应包含两项，在空闲分区表中的每个表目中应包含两项， 即对换区即对换区的首址及其大小，它们的单位是盘块号和盘块数。的首址及其大小，它们的单位是盘块号和盘块数。4.4.2 对换空间的管理对换空间的管理n对换空间分配与回收对换空间分配与回收n对换空间的分配对换空间的分配n采用连续分配方式，可以是首次适应算法、循环首采用连续分配方式，可以是首次适应算法、循环首次适应算法或最佳适应算法。次适应算法或最佳适应算法。n对换空间的对换空间的回收操作回收操作n

42、回收区与插入点的前一分区回收区与插入点的前一分区F1相邻接；相邻接；n回收区与插入点的后一分区回收区与插入点的后一分区F2相邻接；相邻接；n回收区还同时与回收区还同时与F1和和F2二个分区相邻接；二个分区相邻接；n回收区的前、后没有与之相邻接的空闲分区。回收区的前、后没有与之相邻接的空闲分区。4.4.2 对换空间的管理对换空间的管理回收区回收区F1F2回收区回收区F2回收区回收区F1F1F2F2回收区回收区F1F14.4.3 进程的换出与换入进程的换出与换入n进程的换出进程的换出n换出进程：换出进程：阻塞阻塞 且且优先级最低优先级最低；n启动盘块，将该进程的程序和数据传送到磁盘启动盘块，将该进

43、程的程序和数据传送到磁盘的的对换区对换区上。上。n若传送未出现错误，便回收其占用的内存空间，若传送未出现错误，便回收其占用的内存空间，并对该进程的并对该进程的进程控制块进程控制块做相应的修改做相应的修改n进程的换入进程的换入n换入进程：换入进程：就绪就绪” 且且换出时间换出时间(换出到磁盘上换出到磁盘上)最久最久；n直至已无可换入的进程或无可换出的进程直至已无可换入的进程或无可换出的进程为止为止4.4.3 进程的换出与换入进程的换出与换入4.4.3 进程的换出与换入进程的换出与换入n交换技术实现中的问题交换技术实现中的问题n选择原则选择原则: :将哪个进程换出内存？将哪个进程换出内存？n交换时

44、机的确定？交换时机的确定？n交换时需要做哪些工作？交换时需要做哪些工作？n换入内存时位置的确定？换入内存时位置的确定？4.4.3 进程的换出与换入进程的换出与换入n选择原则：选择原则：将哪个进程换出内存？将哪个进程换出内存？n例，分时系统，时间片轮转法或基于优先数的例，分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定调度算法，在选择换出进程时，要确定换出的换出的进程是要长时间等待进程是要长时间等待的。的。n需要特殊考虑的情形需要特殊考虑的情形n任何等待任何等待I/OI/O的进程中存在的问题的进程中存在的问题n解决方法解决方法n从来不换出处于等待从来不换出处于等待I/OI/

45、O状态的进程状态的进程 有些有些I/O进程因进程因DMA（直接存储器访问）而不（直接存储器访问）而不能换出内存或换出前需要操作系统的特殊帮助能换出内存或换出前需要操作系统的特殊帮助4.4.3 进程的换出与换入进程的换出与换入n交换时机的确定：交换时机的确定：何时需发生交换？何时需发生交换？n只要不用就换出（很少再用）只要不用就换出（很少再用）n只在内存空间不够或有不够的危险时换出只在内存空间不够或有不够的危险时换出n交换时需要做哪些工作交换时需要做哪些工作n盘交换区盘交换区：足够大，存放所有用户程序的所有：足够大，存放所有用户程序的所有内存映像的内存映像的拷贝拷贝n直接存取直接存取：必须能够对

46、这些用户程序的内存映：必须能够对这些用户程序的内存映像进行存取操作。像进行存取操作。4.4.3 进程的换出与换入进程的换出与换入n换入内存时位置的确定换入内存时位置的确定n换出后再换入的内存位置一定要在换出前的原换出后再换入的内存位置一定要在换出前的原来位置上吗？来位置上吗？n受地址受地址“绑定绑定”技术的影响，即绝对地址产生技术的影响，即绝对地址产生时机的限制。时机的限制。4.4.3 进程的换出与换入进程的换出与换入n交换与覆盖异同点交换与覆盖异同点n共同点：共同点：n进程的程序和数据主要放进程的程序和数据主要放在外存在外存，当前需要，当前需要执行的部分放在内存执行的部分放在内存，内外存之间

47、进行信息，内外存之间进行信息交换交换n不同点：不同点：n交换交换发生在进程或作业之间，发生在进程或作业之间，而覆盖而覆盖发生在发生在同一进程或作业内同一进程或作业内。n覆盖只能覆盖那些与覆盖段无关的程序段。覆盖只能覆盖那些与覆盖段无关的程序段。4.5 分页存储管理方式分页存储管理方式n连续分配方式主要问题连续分配方式主要问题n形成许多形成许多“碎片碎片”；n通过通过“紧凑紧凑”方法将碎片拼接成可用的大块空方法将碎片拼接成可用的大块空间，但须为此付出很大开销。间，但须为此付出很大开销。n离散分配：将一个进程直接分散地装入到离散分配：将一个进程直接分散地装入到许多不相邻接的分区。许多不相邻接的分区

48、。n分页存储管理：基本单位是页；分页存储管理：基本单位是页；n分段存储管理：基本单位是段；分段存储管理：基本单位是段；n段页式存储管理段页式存储管理 ：基本单位是段，段内分页。：基本单位是段，段内分页。4.5 分页存储管理方式分页存储管理方式存储器管理存储器管理连续分配方式连续分配方式离散分配方式离散分配方式分页存储管理分页存储管理分段存储管理分段存储管理段页式存储管理段页式存储管理4.5.1 分页存储管理的基本方法分页存储管理的基本方法n页面和物理块页面和物理块n页面：页面：将一个进程的逻辑地址空间分成若干个将一个进程的逻辑地址空间分成若干个大小相等的片，称为大小相等的片，称为页面或页页面或

49、页，并加以编号，并加以编号，从从0开始编制页号，页内地址是相对于开始编制页号，页内地址是相对于0编址。编址。n物理块：物理块：内存按页的大小划分为大小相等的区内存按页的大小划分为大小相等的区域，域，称为物理块（物理页面，页框称为物理块（物理页面，页框(frame)，帧），帧），同样加以编号，如同样加以编号，如0块、块、1块等等块等等n在为进程分配内存时，以块为单位将进程中的在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称

50、之为形成了不可利用的碎片，称之为“页内碎片页内碎片”4.5.1 分页存储管理的基本方法分页存储管理的基本方法n页面页面和物理块和物理块n页面大小。页面大小。适中，且页面大小应是适中，且页面大小应是2的幂，的幂，通常为通常为1K B4MBn页面较小页面较小n内存内存碎片减小碎片减小，有利于，有利于提高内存利用率提高内存利用率，但也会，但也会导致进程的导致进程的页表过长页表过长，占用大量内存；，占用大量内存； 此外，还此外，还会会降低页面换进换出的效率降低页面换进换出的效率n页面较大页面较大n可以可以减少页表的长度减少页表的长度，提高页面换进换出的速度，提高页面换进换出的速度，但却又会使但却又会使

51、页内碎片增大页内碎片增大。4.5.1 分页存储管理的基本方法分页存储管理的基本方法n地址结构地址结构n分页地址中的地址结构分页地址中的地址结构 对某特定机器，其地址结构是一定的。若给定一个逻对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为辑地址空间中的地址为A，页面的大小为，页面的大小为L，则页号，则页号P和页和页内地址内地址d可按下式求得：可按下式求得： 例如：其系统的页面大小为例如：其系统的页面大小为1KB，设，设A=2170B，则由，则由下式可以求得下式可以求得P= ，d= 。 页号页号P位移量位移量W3112110页内地址页内地址212=4*2104KB220=210

52、*2101MMODLAdLAINTP212220481224.5.1 分页存储管理的基本方法分页存储管理的基本方法n页表页表n主存分配过程：把用户程序的任一页分配到内主存分配过程：把用户程序的任一页分配到内存中的任一物理块，从而实现非连续的内存分存中的任一物理块，从而实现非连续的内存分配。配。n问题问题n如何管理、如何进行地址变换？如何管理、如何进行地址变换？4.5.1 分页存储管理的基本方法分页存储管理的基本方法n将进程的每一页离散地存储在内存的任一物理块中，为将进程的每一页离散地存储在内存的任一物理块中，为每个进程建立一张页面映像表，简称页表每个进程建立一张页面映像表，简称页表4.5.1

53、分页存储管理的基本方法分页存储管理的基本方法n页表页表n用户程序的逻辑地址与其在主存中的物理地址用户程序的逻辑地址与其在主存中的物理地址间的对应关系。间的对应关系。n一个页表中包含若干个表目，表目的一个页表中包含若干个表目，表目的自然序号自然序号对应于用户程序中的对应于用户程序中的页号页号，表目中的，表目中的块号块号是该是该页对应的页对应的物理块号物理块号。n每一个表目包含每一个表目包含指向页框的指针指向页框的指针，存取控制字存取控制字段段。n表目也称为表目也称为页描述子。页描述子。4.5.1 分页存储管理的基本方法分页存储管理的基本方法进程进程A页表页表00页号页号 块号块号11243548

54、59程序程序A 00程序程序A 11程序程序B 02程序程序B 13程序程序A 24程序程序A 35程序程序B 26程序程序B 37程序程序A 48内存内存程序程序A 59程序程序A0页页1页页2页页3页页4页页5页页n页页程序程序B0页页1页页2页页3页页4页页5页页m页页进程进程B页表页表02页号页号 块号块号132637n页表页表4.5.2 地址变换机构地址变换机构n基本地址变换机构基本地址变换机构n实现从实现从逻辑地址逻辑地址到到物理地址物理地址的转换，将逻辑地址中的的转换，将逻辑地址中的页号页号转换为内存中的转换为内存中的物理块号物理块号，通过，通过页表页表来完成来完成n页表的实现页

55、表的实现n寄存器：变换速度快、成本高，适应小型系统。寄存器：变换速度快、成本高，适应小型系统。n驻留在内存：速度较低、成本低，适应大系统。驻留在内存：速度较低、成本低，适应大系统。n页表大多驻留在内存中，在系统中设置页表大多驻留在内存中，在系统中设置页表寄存器页表寄存器PTR(Page Table Register)，存放页表在内存中的，存放页表在内存中的始始址（址（PTBR）和和页表的长度（页表的长度（PTLR）n进程未执行时，页表的始址和页表长度存放在本进程进程未执行时，页表的始址和页表长度存放在本进程的的PCB中，当调度程序调度到某进程时，才将这两个中，当调度程序调度到某进程时，才将这两

56、个数据装入页表寄存器。数据装入页表寄存器。4.5.2 地址变换机构地址变换机构n地址转换过程地址转换过程4.5.2 地址变换机构地址变换机构n地址转换过程地址转换过程n指令指令 LOAD 1,2500 的地址变换过程（块大小为的地址变换过程（块大小为1024B）n把虚拟地址把虚拟地址2500转换成页号转换成页号P=2，位移量，位移量W=452；n如果页号如果页号2大于页表大小，则中断；否则继续；大于页表大小，则中断；否则继续；n页号页号2与页表起址与页表起址1000运算（运算（1000+2*4，设页描述子，设页描述子大小为大小为4）得到页描述子地址为）得到页描述子地址为1008；n从页描述子中

57、读取块号从页描述子中读取块号8；n根据页描述子的根据页描述子的“存取控制存取控制”判断该指令是否被允许判断该指令是否被允许访问内存，如果不允许，则中断；否则继续；访问内存，如果不允许，则中断；否则继续；n块号块号8与位移量与位移量452运算（运算（8*1024+452=9644，1024为为页面大小）得到物理地址页面大小）得到物理地址9644；n执行执行LOAD操作。操作。4.5.2 地址变换机构地址变换机构n具有快表的地址变换机构具有快表的地址变换机构n由于页表是存放在内存中，因此每次由于页表是存放在内存中，因此每次CPU存取存取一个数据要一个数据要两次访问内存；两次访问内存；n为提高地址变

58、换速度，在地址变换机构中增设为提高地址变换速度，在地址变换机构中增设一个具有一个具有并行查询能力并行查询能力的高速缓冲寄存器，又的高速缓冲寄存器，又称为称为“联想寄存器联想寄存器”（Associative Memory）或或“快表快表”，“转换表缓冲区转换表缓冲区”，“关联内关联内存存”，用以存放当前访问的那些页表项。用以存放当前访问的那些页表项。n快表通常可存放快表通常可存放16-512个表项，如果设计得当，个表项，如果设计得当，命中率可达命中率可达90以上。以上。4.5.2 地址变换机构地址变换机构n具有快表的地址变换机构具有快表的地址变换机构页表寄存器页表寄存器页表始址页表始址页表长度页

59、表长度页号页号页页内地址内地址逻辑地址逻辑地址L越界中断越界中断块号块号b页表页表页号页号页号页号输输入入寄寄存存器器块号块号bb快表快表d物理地址物理地址4.5.3 访问内存的有效时间访问内存的有效时间n可能访问时间：可能访问时间：n 访问快表；访问快表；n访问页表（访问内存）；访问页表（访问内存）；n修改快表；修改快表；n访问内存，存取数据。访问内存，存取数据。n有效访问时间：有效访问时间：n设设TLB查找时间为查找时间为，内存访问时间为，内存访问时间为。n命中率：特定页在命中率：特定页在TLB中被查找到的百分比。用中被查找到的百分比。用表示表示n有效访问时间（有效访问时间（Effecti

60、ve Access Time, EAT）n EAT = ( + ) + (2 + ) (1 - )n = 2 + - 4.5.3 访问内存的有效时间访问内存的有效时间例：有一页式系统，其页表存放在主存中：例：有一页式系统，其页表存放在主存中： 如果对主存的一次存取需要如果对主存的一次存取需要1.51.5s,s,试问试问实现一次页面访问的存取时间是多少实现一次页面访问的存取时间是多少? ? =1.5=1.5* *2=3(s)2=3(s) 如果系统加有快表如果系统加有快表, ,平均命中率为平均命中率为85%,85%,当当页表项在快表中时页表项在快表中时, ,其查找时间忽略为其查找时间忽略为0, 0