操作系统_第4章_存储器管理

1、 OPERSTERING SYSTEM第第4 4章章 存储器管理存储器管理 存储管理是指存储器资源（主要指内存和外存）的管理。本章我们讨论的内容包括： 存储器资源的组织（如内存的组织方式） 地址变换（逻辑地址与物理地址的对应关系） OPERSTERING SYSTEM存储器的功能:保存数据.存储器的发展方向是高速、大容量和小体积。如：内存在访问速度方面的发展：DRAM(动态随机存储器 )、SDRAM(同步动态随机存储器 )、DDRAM(DoubleDataRate )、RDRAM(存储器总线式动态随机存储器 )等；硬盘技术在大容量方面的发展：接口标准、存储密度等；存储组织的功能:存储技术和CP

2、U寻址技术许可的范围内组织合理的存储结构，其依据是访问速度匹配关系、容量要求和价格。如：“寄存器-内存-外存”结构和“寄存器-缓存-内存-外存”结构；现在微机中的存储层次组织：访问速度越来越慢，容量越来越大，价格越来越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态(如：缓存命中率正好使主存读写保持繁忙) OPERSTERING SYSTEM外存(secondary storage)DOS核心命令处理程序主存(primary storage)快速缓存(cache)寄存器(register) OPERSTERING SYSTEM存储管理的功能(1) 存储分配和回收：是存储管理的主要内容。讨论

3、其算法和相应的数据结构。(2) 地址变换：可执行文件生成中的链接技术、程序加载时的重定位技术，进程运行时硬件和软件的地址变换技术和机构。(3) 存储共享和保护：代码和数据共享，对地址空间的访问权限（读、写、执行）。(4) 存储器扩充：它涉及存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），请求调入和预调入（部分进程空间） OPERSTERING SYSTEM背景程序必须装入到内存并放置在该进程拥有的内存区域中才能执行。输入队列 存放在磁盘上等待装入内存以便运行的程序队列集合。用户程序在获得执行以前需要经历几个步骤：生成源程序文件、生成目标模块、生成可加载模块以

4、及在内存中创建进程。 OPERSTERING SYSTEM4.1 程序的装入和链接 步骤：编译、链接、装入。可执行文件的建立：源程序，编译，成为目标模块多个目标模块或程序库，链接，成为可执行文件装入，成为进程编译：高级语言的源程序机器指令 符号地址内存地址（相对地址）链接：将各个目标模块中的相对地址统一转成相对于各个模块地址的位移。装入：执行程序时，将该程序和其所要处理的数据装入内存。 OPERSTERING SYSTEM库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存 OPERSTERING SYSTEM装入：重定位：在可执行文件装入时需要解决可执行文件中地址（指令和数

5、据）和内存地址的对应。由操作系统中的装入程序loader来完成 OPERSTERING SYSTEM程序的装入程序的装入 三种方式：1. 绝对装入(absolute loading)在可执行文件中记录内存地址，装入时直接定位在上述内存地址。 程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 但在由程序员直接给出绝对地址时， 不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。 OPERSTERING SYSTEM一样：一样：意味着意味着OSOS只要读入内存即可只要读入内存即可绝对装入。绝对装入。所以：所以： 象象 JMP L1JMP

6、 L1 指令在变成可执行代码后，该指令的地址场的数据是指令在变成可执行代码后，该指令的地址场的数据是一定的。这就意味该程序只能放在固定的地方。一定的。这就意味该程序只能放在固定的地方。diskdiskJMP 200JMP 200loadloadJMP 200JMP 200MOV AX, 201MOV AX, 2011000100012001200 OPERSTERING SYSTEM优点：装入过程简单。缺点：过于依赖于硬件结构，不适于多道程序系统。 OPERSTERING SYSTEM0000 .1000 . .11001102110411061108 . . . .物理内存OS重定位的概念L

7、oad R1,106Add R1,108Store R1,110234128程序A的代码000100102104106108Load R1,106Add R1,108Store R1,110234128Load R1,1106Add R1,1108Store R1,1110234128 OPERSTERING SYSTEM在装入前链接所假设的程序地址与此时装入的实际地址不一致。在可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。 可重定位装入（静态） (relocatable loading) OPERSTERING S

8、YSTEM重定位分类:静态重定位Load R1,106Add R1,108Store R1,110234128程序A的代码0001001021041061080000 .1000 . .11001102110411061108 . . . .物理内存OSLoad R1,1106Add R1,1108Store R1,1110234128加载时定位Load R1,1106Add R1,1108Store R1,1110234128例：例：MZMZ10100201头标志头标志MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP（200200）0100300300201头部分头部分代

9、码部分代码部分200MZMZ10100201头部分头部分例：例：MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP(200)(200)0+1000100+1000300300201+10001000（2）装入）装入（1）头部分由）头部分由OS读入读入（3）OS根据读入根据读入的头对内存浮动项的头对内存浮动项装配装配MZMZ10100201头部分头部分例：例：MOVE,AXMOVE,AXJMPJMP指令码指令码JMPJMP（200200）0100300300201

10、200MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP( (12001200) )0+1000100+1000300300201+10001000（2）装入）装入（1）头部分由）头部分由OS读入读入（3）OS根据读入根据读入的头对内存浮动项的头对内存浮动项装配装配MZMZ10100201头部分头部分例：例：MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令码指令码JMPJMP( (12001200) )0+1000100+100013001300201+1000

11、1000（2）装入）装入（1）头部分由）头部分由OS读入读入（3）OS根据读入根据读入的头对内存浮动项的头对内存浮动项装配装配 OPERSTERING SYSTEMjmp150100150.RelocationTable0jm2000 OPERSTERING SYSTEM优点：不需硬件支持，可以装入有限多道程序.缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。 OPERSTERING SYSTEM 动态运行期装入（动态重地位）动态运行期装入（动态重地位）( (dynamic run-time loading)dynamic run-ti

12、me loading)在可执行文件中记录虚拟内存地址，装入和执行时通过硬件地址变换机构，完成虚拟地址到实际内存地址的变换。 OPERSTERING SYSTEM重定位分类:动态重定位Load R1,106Add R1,108Store R1,110234128程序A的代码0001001021041061080000 .1000 . .11001102110411061108 . . . .物理内存OSLoad R1,106Add R1,108Store R1,110234128重定位寄存器(位于CPU中)+1000 OPERSTERING SYSTEM OPERSTERING SYSTEM优点

13、：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）缺点：需要硬件支持（通常是CPU），OS实现较复杂是虚拟存储的基础 OPERSTERING SYSTEM逻辑地址空间与物理地址空间将逻辑地址空间与物理地址空间相分离，是内存管理的核心。逻辑地址逻辑地址 由CPU（指令译码器）生成的地址（程序员使用的地址或指令的地址码部分最终确定的地址），也称虚地址虚地址 （ virtual address）。物理地址物理地址 内存单元的地址。如果地址绑定工作在编译阶段或加载阶段完成，那么逻辑地址与物理地

14、址是相同的。如果地址绑定工作在执行阶段完成，那么逻辑地址（虚地址）与物理地址是不相同的。 OPERSTERING SYSTEM存储管理单元 (MMU)MMU是一个硬件装置，它将虚地址映射（转换）成物理地址。（MMU目前是作为CPU硬件的一个功能单元存在于CPU中）在使用 MMU 的方案中，用户进程每次产生的地址在送到存储器（译码器）之前，都要加上存放在重定位寄存器（基地址寄存器）中的值（基地址），从而形成存储器物理单元的地址，即物理地址。用户程序中出现的地址都是逻辑地址；用户程序不可能知道真实的物理地址是什么。 OPERSTERING SYSTEM OPERSTERING SYSTEM程序的链

15、接程序的链接 链接是指多个目标模块在执行时的地址空间分配和相互引用。 链接分类链接分类静态静态链接链接动态链接动态链接载入时动态链接载入时动态链接运行时动态链接运行时动态链接 OPERSTERING SYSTEM静态链接(static-linking)静态链接是在生成可执行文件时进行的。在目标模块中记录符号地址(symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。 OPERSTERING SYSTEMModule AModule Acall function10L-1Module BModule B0M-1function1().function1FModule

16、AModule Acall L+F0L-1Module BModule BLL+M-1function1().function1L+F对多用户、多任务系统显然有冗余，比如用户用对多用户、多任务系统显然有冗余，比如用户用sin(x)sin(x)，则则目标代码中都有这部分代码，装入到内存则也都有这部分代目标代码中都有这部分代码，装入到内存则也都有这部分代码。码。 OPERSTERING SYSTEM动态链接(dynamic-linking)在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL)或共享库(shared library)。 OPERSTERING SYSTEM优点共享：多

17、个进程可以共用一个DLL，节省内存，减少文件交换。部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。 OPERSTERING SYSTEM缺点：链接开销：增加了程序执行时的链接开销；管理开销：程序由多个文件组成，增加管理复杂度。 OPERSTERING SYSTEM覆盖任何

18、时候在内存中仅保留需要的指令和数据,将程序的必要部分的代码和数据常驻内存，可选部分平时存放在外存中，需要时装入。当进程的大小比分配给他的内存地址空间大时，可以考虑使用覆盖技术谁覆盖谁，由用户实现，无需操作系统的支持，程序设计时程序员需要精心地考虑编写支持覆盖的程序结构。 OPERSTERING SYSTEM在一个两趟汇编的汇编程序中使用覆盖技术 OPERSTERING SYSTEMA20KB50KC30KF30KD20KE40KResident20KOverlay 050KOverlay 140KTotal: 190KTotal: 110K OPERSTERING SYSTEM交换一个进程可以

19、从内存临时交换到后备存储器（外存）上存放，其后需要执行时再将其调入内存中。后备存储器 快速的磁盘，需要有足够的存储空间用来存放所有用户在内存的存储映像，同时必须提供对这些内存映像的直接访问。滚出（Roll out），滚进（ roll in） 交换技术的一个变种，被用在基于优先权调度算法的系统中；低优先权进程被换出，而高优先权进程便可以装入执行。交换所花费时间的主要部分是传输时间，传输时间与需要交换的内存单元的数量成正比.在许多操作系统中，例如UNIX, Linux和 Windows 都有各种形式交换存在。 OPERSTERING SYSTEM交换示意图 OPERSTERING SYSTEM4.

20、2 4.2 连续分配存储管理方式连续分配存储管理方式 连续分配是指为一个用户程序分配一个连续的内存空间。 因为程序的执行是根据指令计数器顺序执行,在执行本指令时,它已是下条指令的位置,跳转指令会自动置为跳转的目标地址,所以决定了程序必须占有连续的一段存储区,连续分配是指为一个用户程序分配一个连续的内存空间。 OPERSTERING SYSTEM连续内存分配法(1) 内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。(2) 最简单，适用于单用户、单任务的OS。CP/M和DOS 2.0以下。 OPERSTERING SYSTEM单道连续区管理000020KB100KB2

21、56KBOS用户程序需80KB存储空间空闲区一次只能装入一个作业 OPERSTERING SYSTEM内存内存+重定位寄存器物理页面号（实际内存空间）；每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况。数据结构：位示图，空闲页面链表；请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里； OPERSTERING SYSTEM用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910 OPERSTERING

22、SYSTEM三、页面大小的选择通常是：几KB到几十KB。和目前计算机的物理内存大小有关：4MB到256MB，不太大。较小的页面，减小内碎片，但加大页表的长度，从而形成新的开销并增加换入、换出的开销；较大的页面，减小页表的长度，加大内碎片；管理开销小，交换时对外存I/O效率高。两者的折中。计算机页大小(byte)Intel 804864096IBM AS/400512VAX-11/780128Motorola680404096 OPERSTERING SYSTEM四、优缺点 优点： 没有外碎片，每个内碎片不超过页大小。 一个程序不必连续存放。便于改变程序占用空间的大小（主要指随着程序运行而动态生

23、成的数据增多，要求地址空间相应增长，通常由系统调用完成而不是操作系统自动完成）。 缺点： 程序全部装入内存。 OPERSTERING SYSTEM地址变换机构地址变换机构 逻辑地址物理地址地址变换机构逻辑页号物理块号 OPERSTERING SYSTEM一、一、基本地址变换机构指令所给出地址分为两部分：逻辑页号，页内偏移地址,通过查进程页表，得物理页号，从而形成物理地址。 OPERSTERING SYSTEM页表始址页表始址 页表长度页表长度作业名作业名A A页表始址页表始址xxxxxxxxxxxx页表长度页表长度3 3作业表作业表块号块号比较比较页号页号 页内地址页内地址块号块号 页内地址页

24、内地址页表页表页表控制寄存器页表控制寄存器绝对地址绝对地址逻辑地址逻辑地址地址越界地址越界 OPERSTERING SYSTEM分页存储管理原理页号2页内地址452逻辑地址2500页表基址寄存器页表起址页长021425.页号 块号页表块号5块内地址452越界中断+物理地址55725*1024+452纯分页系统的基本地址转换机构设每页1KB(1024) OPERSTERING SYSTEM OPERSTERING SYSTEM某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5C(H)所对应的物

25、理地址是什么？ 页号物理块号031721138 OPERSTERING SYSTEM逻辑地址0A5C(H)所对应的二进制表示形式是： 0000 1010 0101 1100 所对应的页号是： 2 （十进制） 查页表，得到物理块号是： 11 （十进制） 拼接后，得到物理地址： 0010 1110 0101 1100 即：2E5C(H) OPERSTERING SYSTEM页表的实现页表通常被存放在主存中.页表基地址寄存器页表基地址寄存器（ PTBR， Page-table base register） 用来指示页表在内存的起始位置.页表长度寄存器页表长度寄存器（ PRLR， Page-table

26、 length register ）用来指示页表的大小.每次CPU对内存中的指令或数据的访问都需要访问两次内存，第一次访问页表，第二次才是访问指令或数据.为了解决上述问题，通常在CPU中设置一个容量不大的专门用于快速查找（页框起始地址）的Cache，即一种联想存储器（ associative memory ），称作翻译对照缓冲存储器（translation look-aside buffers ，TLBs） OPERSTERING SYSTEM二、具有快表的地址变换机构为缩短查找时间，可以将页表从内存装入到关联存储器(TLB, Translation Lookaside Buffer)：按内容

27、查找,即逻辑页号物理页号。 联想存储器(快表):具有并行查寻能力的特殊高速缓冲存储器,一种硬件机构,由若干个寄存器组成。 联想存储器速度快但成本高,通常由16512个单元组成,例如Intel 80486只有32个联想寄存器，对于大型作业，其页表有一部分必须放在内存。 OPERSTERING SYSTEM页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址 OPERSTERING SYSTEM页号2页内地址425逻辑地址2500页表基址寄存器页表起址页长021425.页号 块号页表块号5块内地址425越界中断+物理地址55725*1024+4

28、52具有快表的分页地址转换机构设每页1KB(1024) 543725快表 OPERSTERING SYSTEM 妈妈新开了个淘宝店，欢迎前来捧场妈妈新开了个淘宝店，欢迎前来捧场 妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来出自己的一份力，帮忙宣传一下。有人气，所以我也来出自己的一份力，帮忙宣传一下。 并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。并且

29、妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。 另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。 欢迎大家来逛逛欢迎大家来逛逛【扬州五亭龙玩具总动员】 个人小广告：个人小广告： OPERSTERING SYSTEM两级和多级页表两级和多级页表 现代计算机系统，CPU都支持非常大的逻辑地址空间（ -2）。这样可想而知页表会非常大。例如:如果逻辑地址宽度为32bit，假设页面大小为4K（即 ），页表项达1M之多，每个页表项为4个BYTE，仅页表项就要占用4MB的连续内存空间。解决方法：分散存储；当前需要的放在

30、内存，其余的暂存于磁盘。643222 122 OPERSTERING SYSTEM一、两级页表（Two Level Page Table）分散存储：将页表分页，每个页面的大小与物理块的大小相同。解决难于找到大的连续的物理内存的问题。相应的机制：增加页表的页表外层页表（页表目录）。逻辑地址结构： OPERSTERING SYSTEM两级页表结构： P1（目录位移）P2（页表位移）d（页内位移）外层页号（页表目录）外层页内地址（页表）页内地址3122 2112 110 OPERSTERING SYSTEM页目录012n3011023第0页页表01第1页页表1023页表起始地址页框号页框号 OPER

31、STERING SYSTEM地址变换机构： 外部页号P1P2外部页内地址 页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址 OPERSTERING SYSTEM二、多级页表对于64位字长的机器，虚拟地址空间很大而每页比较小，则进程页表太长。宜采用两级或多级页表。例如SUN的SPARC处理器，支持3级页表；而Motorola的68030处理器甚至支持4级页表。 OPERSTERING SYSTEM.166.111.2.85166810.81.61118560929Virtual AddressReal Address OPERSTERING SYSTEM为缩短查找时间，多级页表中的每

32、级都可以装入到关联存储器（即页表的高速缓存）中，并按照cache的原理进行更新。多级页表结构中，指令所给出的地址除偏移地址之外的各部分全是各级页表的页表号或页号，而各级页表中记录的全是物理页号，指向下级页表或真正的被访问页。 OPERSTERING SYSTEM某计算机有32位虚地址空间，且页大小为1024字节。每个页表项长4个字节。因为每个页表都必须包含在一页中，所以使用多级页表，问共需要几级？ OPERSTERING SYSTEM反置页表（反置页表（Inverted Page TableInverted Page Table） 以上方法，每个进程一张页表，页表按照进程的逻辑地址顺序排序，内

33、容为物理块号（页框号）。反置页表则按物理块号的顺序排序，内容为隶属的进程ID及其页号。实例：IBM AS/100、IBM RISC SYSTEM 6000等。在利用反置页表进行地址变换时，是利用进程ID和页号，检索反置页表，实际上可利用联想存储器来检索。 OPERSTERING SYSTEMPIDP（页号）d（页内偏移）反置页表PIDP页框号物理地址逻辑地址d（联想存储器） OPERSTERING SYSTEM pid page offset进程标识进程标识 特征位特征位 页面号页面号 B offsetB反置页表反置页表物理地址物理地址逻辑地址逻辑地址 OPERSTERING SYSTEM哈希

34、页表目前指令的地址位数普遍 32 位.页号被散列到页表。对具有相同散列值的页表项，可一通过链表实现在一个位置上存放多个页框号。页号与链表中的链接元素包含的页号依次比较，如果匹配即可取得相应的物理页框号。 OPERSTERING SYSTEM哈希页表 OPERSTERING SYSTEM4.4 4.4 分段存储管理分段存储管理 分页管理的方法，提高内存的利用率，对程序员是透明的；分段管理的方法，满足了程序员在编程和使用上的要求，适应软件工程开发上的要求。将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要C

35、PU的硬件支持。 OPERSTERING SYSTEM分段系统的基本原理分段系统的基本原理 一、分段 逻辑地址：32 最大段长： ； 最多有 个段 162162段号段内地址0151631 OPERSTERING SYSTEM二、段表：由段基址和段长组成。 作业空间(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间0123 OPERSTERING SYSTEM三、地址变换机构 ：控制寄存器段表始址段表长度210

36、0段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量 W82928K82928692主存物理地址有效地址 OPERSTERING SYSTEM段表始址段表始址 段表长度段表长度作业名作业名A段表始址段表始址xxxxxx段表长度段表长度3作业表作业表限长限长比较比较段号段号 段内地址段内地址段表段表段表控制寄存器段表控制寄存器绝对地址绝对地址逻辑地址逻辑地址地址越界地址越界始址始址+ OPERSTERING SYSTEM四、分页和分段的主要区别 (1) 页是物理单位，而段是逻辑单位。分页是出于系统管理的需要，分段是出于用户应用的需要。因此，一条指令或一个操作数

37、可能会跨越两个页的分界处，而不会跨越两个段的分界处。 (2) 页大小是系统固定的，而段大小则通常不固定。 (3) 逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间；而分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。 在分页中，只需要一个标识符，即可表示一个地址，是一维的。分段时，既要给出段名，又需要给出段内地址，是二维的。 (4) 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。 OPERSTERING SYSTEM分段存储管理方式的引入分段存储管理方式的引入 1.方便编程按逻辑关系划分段：有独立的段名，逻辑地址均从0开始。程序通过分段(segm

38、entation)划分为多个模块，如代码段、数据段、共享段。可以分别编写和编译。2. 分段共享：可以按段为单位来进行共享3. 分段保护：可以针对不同类型的段采取不同的保护4.动态链接：通过动态链接进行代码共享5.动态增长 OPERSTERING SYSTEM6. 优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。7.缺点：进程全部装入内存。8. 段式管理的数据结构：进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(base address)系统段表：系统内所有占用段空闲段表：内存中所有空闲段，可以结合到系统段表中 OPERSTERIN

39、G SYSTEM共享与保护共享与保护 比分页系统更容易共享代码。例如页尺寸为4K，160K的程序需要维护40个页表项，而分段系统只需要维护1个段表项。 OPERSTERING SYSTEM OPERSTERING SYSTEM段页式存储管理方式段页式存储管理方式 结合分段和分页的优点。一、基本原理段内分页管理。逻辑地址：段号S段内页号P页内偏移地址W OPERSTERING SYSTEM段表及其页表： 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器 OPERSTERING SYSTEM二、地址变换过程 段表始 地址

40、段表长度段表寄存器页内地址段号有效地址越界中断+页表长度页表始址段表页号页框物理地址页表页号段号+ OPERSTERING SYSTEM4.5 4.5 虚拟存储器虚拟存储器 前一章所介绍的各种存储器管理方式，其共同的特点是要求将一个作业全部装入内存方能运行，因而难以适应：（1）作业的尺寸大于实际内存的容量；（2）有大量的作业等待运行，但实际内存容量不足以及其全部装入。因此必须找到一种合适的方法解决此类问题，从而引入了虚拟存储器。 OPERSTERING SYSTEM虚拟存储器的基本概念 实存：作业一次性全部装入内存，作业不能大于内存的实际尺寸，大于往往采用覆盖技术。程序的驻留性：阻塞时也在内存

41、，交换技术，但装入内存的程序和数据不一定马上使用。 OPERSTERING SYSTEM具体体现程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。 OPERSTERING SYSTEM虚拟存储器的引入虚拟存储器的引入 局部性原理(1) 局部性原理(principle of locality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域

42、。可以表现为：时间局部性，即一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；空间局部性，即当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。 OPERSTERING SYSTEM虚存的定义在一个操作系统下，如果不要求任意用户程序实际占用的物理地址空间，大于或等于用户程序的逻辑地址空间，而且这种功能的实现对用户来说是透明的，这称该操作系统实现了虚拟存储管理技术，相应的用户进程空间称为虚存空间或虚地址空间。其大小由指令的有效地址的宽度决定。虚拟存储器是一种借助于外存空间，从而允许一个进程在其运行过程中部分地装入内存的技术。 OPERSTE

43、RING SYSTEM虚拟存储的基本原理在程序装入时，不需要将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段具有请求调入和置换功能，只需程序的一部分在内存就可执行，对于动态链接库也可以请求调入 OPERSTERING SYSTEM引入虚拟存储技术的好处可在较小的可用内存中执行较大的用户程序；可在内存中容纳更多

44、程序并发执行；不必影响编程时的程序结构（与覆盖技术比较）提供给用户可用的虚拟内存空间通常大于物理内存(real memory) OPERSTERING SYSTEM虚拟存储器的实现方式虚拟存储器的实现方式 建立在离散分配存储管理方式的基础上请求分页系统纯分页系统+请求调页+页面置换页式虚拟存储器实现机制：（1）请求分页的页表（2） 缺页中断（3） 地址变换需CPU MMU 支持 OPERSTERING SYSTEM请求分段系统纯分段系统+请求调段+分段置换段式虚拟存储器（1）请求分段的段表（2）缺段中断（3） 地址变换需CPU MMU 支持段页式虚拟存储器 OPERSTERING SYSTEM

45、虚拟存储器的特征虚拟存储器的特征 离散性、多次性、对换性、虚拟性。 物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间） 与交换的比较：调入和调出是对部分虚拟地址空间进行 通过物理内存和快速外存相结合，提供大范围的虚拟地址空间 范围大，但占用容量不超过物理内存和外存交换区容量之和 占用容量包括：进程地址空间中的各个段，操作系统代码 OPERSTERING SYSTEM4.6 4.6 请求分页存储器管理方式请求分页存储器管理方式 在简单页式存储管理的基础上，增加请求调页和页面置换功能,最常用方式。重要的数据结构：页表增加若干项，供os实现虚拟

46、存储功能时参考。 OPERSTERING SYSTEM OPERSTERING SYSTEM请求分页中的硬件支持请求分页中的硬件支持 一、页表机制增加换入换出所要求的必要信息。 页号物理块号状态位P访问字段A修改位M外存地址状态位P：存在位（present bit，内存页和外存页）修改位M(modified bit):是否被修改过访问字段A：在近期内被访问的次数，或最近一次访问到 现在的时间间隔外存地址：磁盘上的地址 ，供调入该页时使用 OPERSTERING SYSTEM二、缺页中断机构由处理器的地址变换机构产生缺页中断，然后调用操作系统提供的中断处理例程。缺页中断的特殊性： 缺页中断在指令

47、执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。一条指令的执行可能产生多次缺页中断， 如：swap A, B 而指令本身和两个操作数A, B都跨越相邻外存页的分界处，则产生5次缺页中断（不可能出现指令本身的两次缺页）。必须由CPU硬件确保对多个现场的保存。 OPERSTERING SYSTEM页面0123456SAWP A,BAB OPERSTERING SYSTEM OPERSTERING SYSTEM三、地址变换机构 OPERSTERING SYSTEM缺页处理过程小结：缺页处理过程小结：(1)(1)硬件陷阱进入核心，保存硬件陷阱进入核心，保

48、存PCPC到栈中，大多数机器将当前各种状态保存到栈中，大多数机器将当前各种状态保存在特殊的寄存器中。在特殊的寄存器中。(2)(2)启动一个汇编程序代码保存通用寄存器和其它重要的动态信息，以免启动一个汇编程序代码保存通用寄存器和其它重要的动态信息，以免被操作系统破坏。被操作系统破坏。(3)(3)操作系统发现一个缺页时，查找需要哪个虚页。（通常一个硬件寄存操作系统发现一个缺页时，查找需要哪个虚页。（通常一个硬件寄存器含有该信息）器含有该信息）(4)(4)一旦知道了发生缺页的虚拟地址，操作系统检查这个地址是否有效，一旦知道了发生缺页的虚拟地址，操作系统检查这个地址是否有效，如无效，向进程发一个信号或

49、杀死进程（如无效，向进程发一个信号或杀死进程（UNIXUNIX）；）；若有效也没有保护错误若有效也没有保护错误发生，系统则从空闲页框中选一个页框分配，如果没有空闲页框，执行页发生，系统则从空闲页框中选一个页框分配，如果没有空闲页框，执行页面置换算法找一个页淘汰。面置换算法找一个页淘汰。(5)(5)若选择淘汰的页框不若选择淘汰的页框不“脏脏”，直接到，直接到(6),(6),否则该页写回磁盘，并发生否则该页写回磁盘，并发生一次进程切换（暂停本进程，让其它进程运行到页面写完成，在这期间，一次进程切换（暂停本进程，让其它进程运行到页面写完成，在这期间，该页框标志忙，以免被占用）该页框标志忙，以免被占用

50、）(6)(6)页框页框 “ “干净干净”后，操作系统查找磁盘上所需调入的页，通过磁盘操作后，操作系统查找磁盘上所需调入的页，通过磁盘操作策略将其装入。（在这期间，产生缺页的进程仍然挂起，而其它正在运行策略将其装入。（在这期间，产生缺页的进程仍然挂起，而其它正在运行的进程也依然在运行）的进程也依然在运行） OPERSTERING SYSTEM(7)(7)当传送完成，磁盘发生中断，表明该页已经装入，更新页表有关项以当传送完成，磁盘发生中断，表明该页已经装入，更新页表有关项以表明正确的状态。表明正确的状态。(8)(8)恢复发生缺页指令以前的状态，程序计数器重新指向这条指令。恢复发生缺页指令以前的状态

51、，程序计数器重新指向这条指令。(9)(9)缺页进程恢复，操作系统返回调用它的汇编语言例程。缺页进程恢复，操作系统返回调用它的汇编语言例程。(10)(10)该例程恢复寄存器和其它重要的动态信息，回到用户空间继续执行，该例程恢复寄存器和其它重要的动态信息，回到用户空间继续执行，就好象缺页没有发生过一样就好象缺页没有发生过一样 OPERSTERING SYSTEM查快表查快表有登记有登记无登记无登记查页表查页表登记入快表登记入快表发缺页中断发缺页中断在主存在主存在辅存在辅存形成绝对地址形成绝对地址继续执行指令继续执行指令重新执行重新执行被中断指令被中断指令恢复现场恢复现场调整页表和调整页表和主存分配

52、表主存分配表装入所需页面装入所需页面主存有空闲块主存有空闲块保护现场保护现场有有选择调出页面选择调出页面该页是否修改该页是否修改未修改未修改已修改已修改把该页写回把该页写回辅存相应位置辅存相应位置操作系统操作系统硬件硬件逻辑地址逻辑地址无无 OPERSTERING SYSTEM OPERSTERING SYSTEM页面分配策略内存分配策略包括： 分配时机 分配数量 分配位置 调度策略 OPERSTERING SYSTEM何时分配与装入立即调页：在进程开始执行之前分配与装入。请求调页：只有在实际访问某页时才通过发生缺页中断处理程序分配。优点：容易实现。缺点：对外存I/O次数多，开销较大，要求I/

53、O速度快。预先调页：由操作系统根据一定的算法，动态预测将来最近时间最可能要访问那些页，并在这些页实际访问之前预先调入。 发生的时机：缺页中断时 页簇化优点：提高调页的I/O效率。缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页 OPERSTERING SYSTEM从何处调入页面文件区或交换区。 外存通常分为外存通常分为文件区和和交换区。通常外存交换区的。通常外存交换区的I/OI/O效效率比文件区的高（通过采取文件连续存放，加大物理块容率比文件区的高（通过采取文件连续存放，加大物理块容量等措施）。量等措施）。关于调入页面的来源，这里有几种做法：进程装入时，将其全部页面

54、复制到交换区，以后总是从交换区调入。执行时调入速度快，要求交换区空间较大。凡不会修改的页面或是未被修改的页面，直接从文件区调入，换出时不必写回磁盘，下次仍从文件区调入。已被修改的页面，被置换时需调出到交换区，以后从交换区调入。节省交换区空间。UNIX方式，未运行过的页面，直接从文件区调入，而曾经运行过的页面，换出时放在对换区，下次调入时，应从对换区调入。在进程结束时，更新文件区内容。 OPERSTERING SYSTEM页面分配分配数量页面分配分配数量 为每个进程分配多少个页框？如何分？目的：减少缺页中断。一、最小物理块数保证进程运行的至少要分配的物理块数，少了则无法运行。如何预测？与指令系统

55、有关：单地址且直接寻址：2个页面；若支持间接寻址：则至少需要3个页面；如上，最多至少需要6个。 OPERSTERING SYSTEM二、页面分配和置换策略1 固定分配局部置换（Fixed Allocation, Local Replacement） 给每个进程分配固定数目的页框，当发生缺页中断缺页中断时，只考虑从该进程所属的页框中调出旧的页面，从而换入新的页面。 困难在于分配多少个页框合适？少了中断频繁，多了内存装入的进程减少。 2 可变分配全局置换（Variable Allocation, Global Replacement） 预分配给进程一定数目的页框，OS控制一定数量的空闲页框，在进程

56、的执行过程中，发生缺页时，OS就分配给该进程一个空闲的页框，当空闲的页框用完时，OS可根据需要从任意的进程中调出一个页框。会有不公平。 OPERSTERING SYSTEM3 可变分配局部置换（Variable Allocation, Local Replacement） 预分配给进程一定数目的页框，OS控制一定数量的空闲页框，在进程的执行过程中，发生缺页时，首先考虑从该进程所属的页框中调出旧的页面，若发现该进程频繁发生缺页中断，这时可分配新的页框给该进程。统计进程的缺页中断率系统会有开销。 OPERSTERING SYSTEM三、分配算法1. 平均分配2. 按比例分配3. 按优先权分配mSs

57、pamsSpsiiiiii分配的页框数为进程总共可用的页框数的大小进程 5964137127564137101271064212aassmi OPERSTERING SYSTEM页长和页簇化页大小通常为2的指数幂简化计算 例如：页长为2NB，则逻辑地址的低N位即为页内位移，剩余的高位是逻辑页号。页长的确定 OPERSTERING SYSTEM4.3 4.3 页面置换算法页面置换算法 (1) 功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacement policy。(2) 目标（出发点）：降低页面更换率，应把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下

58、依据过去的统计数据进行预测；相反会有“抖动”。(3) 页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lock bit)。 OPERSTERING SYSTEM1.先来先服务（先来先服务（FIFO）在内存时间最长的页最先被淘汰. Time t | 0| 1 2 3 4 5 6 7 8 9 10 11 12RS | | a b c d a b e a b c d e Frame 0| | a a a d d d e e e e e eFrame 1| | b b b a a a

59、a a c c cFrame 2| | c c c b b b b b d d IN | | a b c d a b e c dOUT | | a b c d a b OPERSTERING SYSTEMTime t | 0| 1 2 3 4 5 6 7 8 9 10 11 12RS | | a b c d a b e a b c d e Frame 0| |a a a a a a e e e e d dFrame 1| | b b b b b b a a a a eFrame 2| | c c c c c c b b b bFrame 3| | d d d d d d c c c IN |

60、| a b c d e a b c d eOUT | | a b c d e aMore Frames Fewer Page Faults?Beladys Anomaly: more frames more page faults OPERSTERING SYSTEMBelady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。 OPERSTERING SYSTEM引用