《计算机操作系统—存储管理.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统—存储管理.ppt（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机操作系统计算机操作系统计算机操作系统计算机操作系统第五章第五章第五章第五章 存储管理存储管理存储管理存储管理主讲教师主讲教师 王帅强王帅强http:/ 存储管理存储管理5.1 5.1 引言引言5.2 5.2 连续分配方式连续分配方式5.3 5.3 基本分页、分段和段页式基本分页、分段和段页式存储管理存储管理v存储管理是指存储器资源存储管理是指存储器资源（主要指内存并涉及外存）（主要指内存并涉及外存）的管理。的管理。存储器资源的组织（如内存的组织方式）地址变换（逻辑地址与物理地址的对应关系维护）虚拟存储的调度算法5.1 5.1 引言引言5.1.1 5.1.1 存储组织存储组织5.1.2 5
2、.1.2 存储管理的功能存储管理的功能5.1.3 5.1.3 重定位方法重定位方法5.1.4 5.1.4 链接链接返回5.1.1 5.1.1 存储组织存储组织v存储器的功能是保存数据，存储器的发展方向是高速、大容存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；v存储组织是指在存储技术和存储组织是指在存储技术和CPUCPU寻址技术许可的范围内组织合寻址技术许可的范围内组织合理的存储结构。理的存储结构。其依据是访问速度匹配关系、容量要求和价格。“寄存器-内存-外
3、存”结构“寄存器-缓存-内存-外存”结构；v微机中的存储层次组织：微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；存储层次结构存储层次结构v快速缓存（快速缓存（目前一般采用目前一般采用SRAMSRAM实现）：实现）：Data CacheTLB(Translation Lookaside Buffer)v内存：内存：DRAM,SDRAMDRAM,SDRAM等；等；v外存：软盘、硬盘、光盘、磁带等；外存：软盘、硬盘、光盘、磁带等；5.1.2 5.1.2 存储管理的功能存储管理的功能v存储分配和回收：存
4、储分配和回收：分配和回收算法及相应的数据结构。分配和回收算法及相应的数据结构。v地址变换：地址变换：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构v存储共享和保护：存储共享和保护：代码和数据共享地址空间访问权限（读、写、执行）v存储器扩充：存储器的逻辑组织和物理组织；存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）返回5.1.3 5.1.3 重定位重定位v重定位：在可执行文件装入时需要解决可执行文件中地址重定位：在可执行文件装入时需要解决可执行文件中地址（
5、指令和数据）和内存地址的对应。由操作系统中的装入程（指令和数据）和内存地址的对应。由操作系统中的装入程序序loaderloader来完成。来完成。v程序在成为进程前的准备工作程序在成为进程前的准备工作编辑：形成源文件(符号地址)编译：形成目标模块(模块内符号地址解析)链接：由多个目标模块或程序库生成可执行文件(模块间符号地址解析)装入：构造PCB，形成进程(使用物理地址)v重定位方法：重定位方法：绝对装入可重定位装入动态装入返回1.1.逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射v逻辑地址（相对地址，虚地址）：逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成用户的程序经
6、过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。v物理地址（绝对地址，实地址）：物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址内存中存储单元的地址。物理地址可直接寻址。可直接寻址。v地址映射：地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。地址。当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，
7、是按物理地址进行的，所以要进行地址转换。逻辑地址、物理地址和地址映射地址映射2.2.绝对装入绝对装入(absolute loading)(absolute loading)v优点：装入过程简单。优点：装入过程简单。v缺点：过于依赖于硬件结构，不适于多道程序系缺点：过于依赖于硬件结构，不适于多道程序系统。统。在可执行文件中记录内存地址，装入时直接定在可执行文件中记录内存地址，装入时直接定位在上述位在上述(即文件中记录的地址即文件中记录的地址)内存地址。内存地址。3.3.可重定位装入可重定位装入(relocatable loading)(relocatable loading)v优点：不需硬件支持
8、，可以装入有限多道程序优点：不需硬件支持，可以装入有限多道程序v缺点：一个程序通常需要占用连续的内存空间，程序缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。装入内存后不能移动。不易实现共享。在可执行文件中，列出各个需要重定位的地址单在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即：装入时根据所定般在装入内存时由软件完成）。即：装入时根据所定位的内存地址去修
9、改每个重定位地址项，添加相应偏位的内存地址去修改每个重定位地址项，添加相应偏移量。移量。4.4.动态装入动态装入(dynamic run-time loading)(dynamic run-time loading)v优点：优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。v缺点：需要硬件支持（通常是缺点：需要硬件支持（通常是CPU），），OS实现较复杂。实现较复杂。它是虚拟存储的基础。它是虚拟存储的基础。在可执行文件中记录虚拟内存地址，装入和执行时通在可执行文件中记录虚拟内存地
10、址，装入和执行时通过硬件地址变换机构，完成虚拟地址到实际内存地址过硬件地址变换机构，完成虚拟地址到实际内存地址的变换。的变换。5.1.4 5.1.4 链接链接5.1.4.1 5.1.4.1 链接方法链接方法5.1.4.2 5.1.4.2 链接举例链接举例返回链接是指多个目标模块在执行时的地址空间分链接是指多个目标模块在执行时的地址空间分配和相互引用。配和相互引用。5.1.4.1 5.1.4.1 链接方法链接方法1.1.静态链接静态链接(static-linking)(static-linking)返回 静态链接是在生成可执行文件时进行的。在目标模块中记静态链接是在生成可执行文件时进行的。在目标
11、模块中记录符号地址录符号地址(symbolic address)(symbolic address)，而在可执行文件中改写为指，而在可执行文件中改写为指令直接使用的数字地址。令直接使用的数字地址。2.2.动态链接动态链接(dynamic-linking)(dynamic-linking)v优点优点共享：多个进程可以共用一个DLL，节省内存，减少文件交换。部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。便于运行环境适
12、应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。v缺点：缺点：链接开销：增加了程序执行时的链接开销；管理开销：程序由多个文件组成，增加管理复杂度。在装入或运行时进行链接。通常被链接的共享代码称为动态链接在装入或运行时进行链接。通常被链接的共享代码称为动态链接库库(DLL,Dynamic-Link Library)(DLL,Dynamic-Link Library)或共享库或共享库(shared library)(shared library)。5.1.4.2 Windows NT5.1.4.2 Windows
13、NT动态链接库动态链接库返回v库程序文件库程序文件.C：相当于给出一组函数定义的源代码；：相当于给出一组函数定义的源代码；v模块定义文件模块定义文件.DEF：相当于定义链接选项，也可在源代码中定：相当于定义链接选项，也可在源代码中定义；如：义；如：DLL中函数的引入和引出中函数的引入和引出(dllimport和和dllexport)。v编译程序利用编译程序利用.C文件生成目标模块文件生成目标模块.OBJv库管理程序利用库管理程序利用.DEF文件生成文件生成DLL输入库输入库.LIB和输出文件和输出文件.EXPv链接程序利用链接程序利用.OBJ和和.EXP文件生成动态链接库文件生成动态链接库.D
14、LL。1.1.构造动态链接库构造动态链接库DLLDLL是包含函数和数据的模块，它的调用模块可为是包含函数和数据的模块，它的调用模块可为EXEEXE或或DLLDLL，它，它由调用模块在运行时加载；加载时，它被映射到调用进程的地由调用模块在运行时加载；加载时，它被映射到调用进程的地址空间。在址空间。在VCVC中有一类工程用于创建中有一类工程用于创建DLLDLL。2.DLL2.DLL的装入方法的装入方法v装入时动态链接装入时动态链接(load-time)(load-time)：在编程时显式调用某个DLL函数，该DLL函数在可执行文件中称为引入(import)函数。链接时需利用.LIB文件。在可执行文
15、件中为引入的每个DLL建立一个IMAGE_IMPORT_DESCRIPTOR结构。在装入时由系统根据该DLL映射在进程中的地址改写Import Address Table中的各项函数指针。Hint是DLL函数在DLL文件中的序号，当DLL文件修改后，就未必指向原先的DLL函数。在装入时，系统会查找相应DLL，并把它映射到进程地址空间，获得DLL中各函数的入口地址，定位本进程中对这些函数的引用；v运行时动态链接运行时动态链接(run-time)(run-time)：在编程时通过：在编程时通过LoadLibraryLoadLibrary（给（给出出DLLDLL名称，返回装入和链接之后该名称，返回装
16、入和链接之后该DLLDLL的句柄）的句柄）,FreeLibrary,GetProcAddressFreeLibrary,GetProcAddress（其参数包括函数的符号名称，（其参数包括函数的符号名称，返回该函数的入口指针）等返回该函数的入口指针）等APIAPI来使用来使用DLLDLL函数。这时不再需函数。这时不再需要引入库（要引入库（import libraryimport library）。）。LoadLibrary或LoadLibraryEx把可执行模块映射到调用进程的地址空间，返回模块句柄；GetProcAddress获得DLL中特定函数的指针，返回函数指针；FreeLibrary把
17、DLL模块的引用计数减1；当引用计数为0时，拆除DLL模块到进程地址空间的映射；2.DLL2.DLL的装入方法的装入方法5.2 5.2 连续分配方式连续分配方式5.2.1 5.2.1 单一连续分配单一连续分配5.2.2 5.2.2 分区分配分区分配5.2.3 5.2.3 覆盖和交换技术覆盖和交换技术5.2.15.2.1单一连续区存储管理单一连续区存储管理返回v内存分为两个区域：系统区，用户区。应用程内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。序装入到用户区，可使用用户区全部空间。v最简单，适用于单用户、单任务的最简单，适用于单用户、单任务的OSOS。v优点：易
18、于管理。优点：易于管理。v缺点：对要求内存空间少的程序，造成内存浪缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占费；程序全部装入，很少使用的程序部分也占用内存。用内存。单一连续区存储管理单一连续区存储管理5.2.2 5.2.2 分区存储管理分区存储管理1 1 原理原理2 2 固定分区固定分区(fixed partitioning)(fixed partitioning)3 3 动态分区动态分区(dynamic partitioning)(dynamic partitioning)4 4 分区分配算法分区分配算法5 MS DOS5 MS DOS中的分区存储管理中
19、的分区存储管理返回1.1.原理原理v把内存分为一些大小相等或不等的分区把内存分为一些大小相等或不等的分区(partition)(partition)，每，每个应用进程占用一个或几个分区。操作系统占用其中一个应用进程占用一个或几个分区。操作系统占用其中一个分区。个分区。v特点：适用于多道程序系统和分时系统特点：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享。v问题：可能存在内碎片和外碎片。问题：可能存在内碎片和外碎片。内碎片：占用分区之内未被利用的空间外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。返回v分区的数据结构：分区表，或分区链表分区的数据结构：分区表
20、，或分区链表可以只记录空闲分区，也可以同时记录空闲和占用分区分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。分区表可以划分为两个表格：空闲分区表，占用分区表，从而减小每个表格长度。空闲分区表中按不同分配算法相应对表项排序。数据结构数据结构2.2.固定分区固定分区(fixed partitioning)(fixed partitioning)v分区大小相等：只适合于多个相同程序的并发分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。执行（处理多个类型相同的对象）。v分区大小不等：多个小分区、适量的中等分区、分区大小不等：多个小分区、适量的中等分区、少
21、量的大分区。根据程序的大小，分配当前空少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。闲的、适当大小的分区。返回把内存划分为若干个固定大小的连续分区。把内存划分为若干个固定大小的连续分区。固定分区固定分区(大小相同大小相同)固定分区固定分区(多种大小多种大小)v优点：易于实现，开销小。优点：易于实现，开销小。v缺点：缺点：内碎片造成浪费分区总数固定，限制了并发执行的程序数目。v可以和覆盖、交换技术配合使用。可以和覆盖、交换技术配合使用。v采用的数据结构：分区表记录分区的大小和采用的数据结构：分区表记录分区的大小和使用情况使用情况2.固定分区固定分区(fixed partition
22、ing)固定分区的进程队列固定分区的进程队列：多队列适用于大小不等的固定分区；单：多队列适用于大小不等的固定分区；单队列适用于大小相同的固定分区，也可用于大小不等的情况。队列适用于大小相同的固定分区，也可用于大小不等的情况。固定分区使用表固定分区使用表图4-4固定分区使用表3.3.动态分区动态分区(dynamic partitioning)(dynamic partitioning)v动态创建分区：在装入程序时按其初始要求分动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配配，或在其执行过程中通过系统调用进行分配或改变分区大小。或改变分区大小。v优点：没有内碎片。
23、优点：没有内碎片。v缺点：有外碎片；如果大小不是任意的，也可缺点：有外碎片；如果大小不是任意的，也可能出现内碎片。能出现内碎片。返回3.3.动态分区动态分区(dynamic partitioning)(dynamic partitioning)3.3.动态分区动态分区(dynamic partitioning)(dynamic partitioning)3.3.动态分区动态分区(dynamic partitioning)(dynamic partitioning)动态分区分配动态分区分配 1.分区分配中的数据结构分区分配中的数据结构(1)空闲分区表。(2)空闲分区链。图4-5空闲链结构4.4.
24、分区分配算法分区分配算法v分区分配算法：寻找某个空闲分区，其大小需大于或等分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为分区，其中一个分区为要求的大小并标记为“占用占用”，而另一个分区为余下部分并标记为而另一个分区为余下部分并标记为“空闲空闲”。分区的先。分区的先后次序通常是从内存低端到高端。后次序通常是从内存低端到高端。v分区释放算法：需要将相邻的空闲分区合并成一个空闲分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。分区。(这时要解决的问题是：合并条件
25、的判断和合并这时要解决的问题是：合并条件的判断和合并时机的选择时机的选择)返回v最先匹配法最先匹配法(first-fit)(first-fit)：按分区的先后次序，从头查找，找：按分区的先后次序，从头查找，找到符合要求的第一个分区到符合要求的第一个分区该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。v下次匹配法下次匹配法(next-fit)(next-fit)：按分区的先后次序，从上次分配的：按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的分区起查找（到最后分区时再回到
26、开头），找到符合要求的第一个分区第一个分区该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。v最佳匹配法最佳匹配法(best-fit)(best-fit)：找到其大小与要求相差最小的空闲：找到其大小与要求相差最小的空闲分区分区从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。v最坏匹配法最坏匹配法(worst-fit)(worst-fit)：找到最大的空闲分区：找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。v内存紧缩内存紧缩(compaction)(compaction)：将各个占用分区向内存：将各个占用分区
27、向内存一端移动。使各个空闲分区聚集在另一端，然后一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。将各个空闲分区合并成为一个空闲分区。对占用分区进行内存数据搬移占用CPU时间如果对占用分区中的程序进行浮动，则其重定位需要硬件支持。紧缩时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时可重定位分区分配可重定位分区分配1.动态重定位的引入动态重定位的引入图4-8紧凑的示意动态重定位的实现动态重定位的实现 图4-9动态重定位示意图动态重定位分区分配算法动态重定位分区分配算法 图4-10动态分区分配算法流程图5.2.3 5.2.3 覆盖和交换技术覆盖和交换技术5.2
28、.3.1 5.2.3.1 覆盖覆盖(overlay)(overlay)5.2.3.2 5.2.3.2 交换交换(swapping)(swapping)返回5.2.3.1 5.2.3.1 覆盖覆盖(overlay)(overlay)v引入：其目标是在较小的可用内存中运行较大的程序。常引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。用于多道程序系统，与分区存储管理配合使用。v原理：一个程序的几个代码段或数据段，按照时间先后来原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常
29、驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)返回注：另一种覆盖方法：注：另一种覆盖方法：(100K)(100K)A(20K)A(20K)占一个分区：占一个分区：20K20K；B(50K)B(50K)、D(20K)D(20K)和和E(40K)E(40K)共用一个分区：共用一个分区：50K50K；F(30K)F(30K)和和C(30K)C(30K)共用一个分区：共用一个分区：30K30K；覆盖技术覆盖技术v缺点：缺点：编程时必须划分程序模块和确
30、定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。v实现：函数库（操作系统对覆盖不得知），或实现：函数库（操作系统对覆盖不得知），或操作系统支持操作系统支持覆盖技术覆盖技术5.2.3.2 5.2.3.2 交换交换(swapping)(swapping)v引入：多个程序并发执行，可以将暂时不能执行的程序送到外引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址存中而目前到达就绪状态的进程。交换单位
31、为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作理配合使用。又称作 对换对换 或或 滚进滚进/滚出滚出(roll-in/roll-(roll-in/roll-out)out)；程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）；v原理：暂停执行内存中的进程，将整个进程的地址空间保存到原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出外存的交换区中（换出swap outswap out），而将外存中由阻塞变为就），而将外存中由阻塞变为就绪的进程的地址空间读
32、入到内存中，并将该进程送到就绪队列绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入（换入swap inswap in）。）。返回v优点：增加并发运行的程序数目，并且给用户提供适当的响优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构应时间；编写程序时不影响程序结构v缺点：对换入和换出的控制增加处理机开销；程序整个地址缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。空间都进行传送，没有考虑执行过程中地址访问的统计特性。v考虑的问题：考虑的问题：程序换入时的重定位；减少交换中传送的信息量，特别是
33、对大程序；对外存交换区空间的管理：如动态分区方法；5.2.3.2 5.2.3.2 交换交换(swapping)(swapping)5.3 5.3 页式、段式和段页式存储管理页式、段式和段页式存储管理5.3.1 5.3.1 简单页式简单页式(simple paging)(simple paging)5.3.2 5.3.2 简单段式简单段式(simple segmentation)(simple segmentation)5.3.3 5.3.3 页式管理和段式管理的比较页式管理和段式管理的比较5.3.4 5.3.4 段页式管理段页式管理返回页式和段式存储管理是通过引入进程的逻辑地址，把页式和段式存
34、储管理是通过引入进程的逻辑地址，把进程地址空间与实际存储位置分离，从而增加存储管进程地址空间与实际存储位置分离，从而增加存储管理的灵活性。理的灵活性。5.3.1 5.3.1 简单页式简单页式(simple paging)(simple paging)返回1.1.简单页式管理的基本原理简单页式管理的基本原理 将程序的逻辑地址空间和物理内存划分为固定大将程序的逻辑地址空间和物理内存划分为固定大小的页或页面小的页或页面(page or page frame)(page or page frame)，程序加载时，程序加载时，分配其所需的所有页，这些页不必连续。需要分配其所需的所有页，这些页不必连续。需
35、要CPUCPU的的硬件支持。硬件支持。v优点：优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。v缺点：程序全部装入内存。缺点：程序全部装入内存。5.3.1 5.3.1 简单页式简单页式(simple paging)(simple paging)2.2.简单页式管理的数据结构简单页式管理的数据结构v进程页表：每个进程有一个页表，描述该进程占用的进程页表：每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；物理页面及逻辑排列顺序；逻辑页号（本进程的地址空间）物理页面号（实际内存空间）；v物理
36、页面表：整个系统有一个物理页面表，描述物理物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况。内存空间的分配使用状况。数据结构：位示图，空闲页面链表；v请求表：整个系统有一个请求表，描述系统内各个进请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到程页表的位置和大小，用于地址转换，也可以结合到各进程的各进程的PCBPCB里；里；进程页表进程页表3.3.简单页式管理的地址变换简单页式管理的地址变换v指令所给出地址分为两部分：逻辑页号，页内偏移地址指令所给出地址分为两部分：逻辑页号，页内偏移地址 查进程页表，得物理页号查进程页表，得物理页
37、号 物理地址物理地址为缩短查找时间，可以将页表从内存装入到关联存储器(TLB,Translation Lookaside Buffer)，按内容查找(associative mapping)，即逻辑页号物理页号页式地址变换页式地址变换页式地址变换举例页式地址变换举例5.5.页的大小页的大小v通常是：几通常是：几KBKB到几十到几十KBKB。小内碎片小；大页表短，管理开销小，交换时对外存I/O效率高。和目前计算机的物理内存大小有关：4MB到255MB，不太大。5.3.2 5.3.2 简单段式简单段式(simple segmentation)(simple segmentation)返回页式管理是
38、把内存视为一维线性空间；而段式页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一管理是把内存视为二维空间，与进程逻辑相一致。致。1.1.简单段式管理的基本原理简单段式管理的基本原理将程序的地址空间划分为若干个段将程序的地址空间划分为若干个段(segment)(segment)，程序，程序加载时，分配其所需的所有段（内存分区），这些加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要段不必连续；物理内存的管理采用动态分区。需要CPUCPU的硬件支持。的硬件支持。v程序通过分段程序通过分段(segmentation)(segment
39、ation)划分为多个模块，如划分为多个模块，如代码段、数据段、共享段。代码段、数据段、共享段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享v优点：优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。v缺点：缺点：进程全部装入内存。5.3.2 5.3.2 简单段式简单段式(simple segmentation)(simple segmentation)2.2.简单段式管理的数据结构简单段式管理的数据结构v进程段表：描述组成进程地址空间的各段，可进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的
40、索引。每段有段基以是指向系统段表中表项的索引。每段有段基址址(base address)(base address)和段长度和段长度v系统段表：系统内所有占用段系统段表：系统内所有占用段v空闲段表：内存中所有空闲段，可以结合到系空闲段表：内存中所有空闲段，可以结合到系统段表中统段表中3.3.简单段式管理的地址变换简单段式管理的地址变换段式地址变换举例段式地址变换举例5.3.3 5.3.3 页式管理和段式管理的比较页式管理和段式管理的比较v分页是出于系统管理的需要，分段是出于用户应用的需要。分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨
41、越两个段的分界处。v页大小是系统固定的，而段大小则通常不固定。页大小是系统固定的，而段大小则通常不固定。v逻辑地址表示：逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。v通常段比页大，因而段表比页表短，可以缩短查找时间，提通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。高访问速度。返回共享与保护共享与保护 段是信息的逻辑单位。分段系统易于实现段段是信息的逻辑单位。分段系统易于实现段的共享，即允许若干个进程共享一个或多个段，的共享，即允许若干个进程共享一个或多个段，而且对段的保护也十分简单易行。而且
42、对段的保护也十分简单易行。P122 5.3.4 5.3.4 段页式存储管理段页式存储管理v基本原理：基本原理：分段和分页原理的相结合。先将用分段和分页原理的相结合。先将用户程序分段，再把每个分段划分成若干页，并户程序分段，再把每个分段划分成若干页，并为每个段赋予一个段名。为每个段赋予一个段名。v数据结构：段表和页表数据结构：段表和页表 段表：段号段表：段号 状态状态 页表大小页表大小 页表始址页表始址 页表：页号页表：页号 状态状态 存储块号存储块号 CPU给出的有效地址：给出的有效地址：段号段号 段内页号段内页号 页内地址页内地址5.3.4 段页式存储管理方式段页式存储管理方式 1.基本原理
43、基本原理 图4-20作业地址空间和地址结构2.地址变换过程地址变换过程 图4-22段页式系统中的地址变换机构5.5 虚拟存储器的基本概念虚拟存储器的基本概念 5.5.1 虚拟存储器的引入虚拟存储器的引入 1.常规存储器管理方式的特征常规存储器管理方式的特征 (1)一次性。(2)驻留性。2.局部性原理局部性原理 早在1968年，Denning.P就曾指出：(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。(3)程序中存在许多循环结构，这些虽然只由少
44、数指令构成，但是它们将多次执行。(4)程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。局限性又表现在下述两个方面：(1)时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。(2)空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。3.虚拟存储器定义虚拟存储器定义 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从
45、逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。5.5.3 虚拟存储器的特征虚拟存储器的特征 1.多次性多次性 2.对换性对换性3.虚拟性虚拟性 5.6 请求分页存储管理方式请求分页存储管理方式 5.6.1 请求分页中的硬件支持请求分页中的硬件支持 1.页表机制页表机制 页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 状态位：是否调入内存状态位：是否调入内存访问
46、字段：本页在一段时间内访问次数访问字段：本页在一段时间内访问次数修改位：是否修改过修改位：是否修改过2.缺页中断机构缺页中断机构 图4-23涉及6次缺页中断的指令3.地址变换机构地址变换机构 图请求分页中的地址变换过程5.6.2 内存分配策略和分配算法内存分配策略和分配算法 1.最小物理块数的确定最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令
47、的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。2.物理块的分配策略物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(FixedAllocation,LocalReplacement)2)可变分配全局置换(VariableAllocation,GlobalReplacement
48、)3)可变分配局部置换(VariableAllocation,LocalR3.物理块分配算法物理块分配算法 1)平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。2)按比例分配算法这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假
49、定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。3)考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。5.7 页面置换算法页面置换算法 5.7.1 最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1.最佳(Optimal)置换算法最佳置换算
50、法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1最久要访问的页被置换，从而把因需要调回这一页发生的缺页推到将来，越远越好。图4-25利用最佳页面置换算法时的置换图2.先进先出先进先出(FIFO)页面置换算法页面置换算法 图4-26利用FIFO置换算法时的置换图5.7.2 最近最久未使用最近最久未使用(LRU)置换算法置换