第三章内存管理

第三章内存管理,内存管理相关概念及方法与技术,目的与要求：掌握程序处理基本过程中内存管理相关环节的概念及内存管理的各种方法与技术。重点与难点：目标程序结构及各种链接程序与装入程序的设计原理；各主要内存管理方式的相关概念及基本方法与技术。作业：2，3，4，5，6，7，8，10，11，15，16，17，18,第三章内存管理,3.1内存管理概述3.2连续分配内存管理3.3基本分页内存管理3.4基本分段内存管理3.5段页式内存管理3.6虚拟存储管理,3.1内存管理概述,3.1.1计算机存储系统3.1.2程序处理与内存管理3.1.3内存管理方法与技术的衍化3.1.4现代操作系统内存管理功能要求,3.1.1计算机存储系统,3.1.2程序处理与内存管理,程序处理基本过程,装入模块,库,符号名空间,目标地址空间,统一的目标地址空间,物理地址空间,数据和指令构成：存取访问问题,布局？,程序地址空间及形成目标模块（由编译/汇编得到）：相对地址链接过程实现各目标模块相对地址的统一内存管理物理部件MMU负责将逻辑地址转换为物理地址X86体系结构MMU支持分页和分段机制内存管理方式实模式和保护模式,3.1.2程序处理与内存管理,可按照记录的形式来组织目标程序文件目标程序可由一条表头记录、若干条正文记录及一条结尾记录构成表头记录：包含表头记录标志字符H、程序名称、起始地址以及程序长度正文记录：包含有正文记录标志字符T、记录长度、机器指令、程序数据以及指令与数据的装入地址信息等结尾记录：用来表明程序的结束并指定程序执行的起始地址，可包含有结尾记录标志字符E和起始执行地址,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,表头记录格式示例,3.1.2程序处理与内存管理,正文记录格式示例,3.1.2程序处理与内存管理,结尾记录格式示例,程序装入与链接程序的链接与装入过程是一个相互交织的过程，链接与装入功能的分配在一定程度上受到链接程序和装入程序的设计策略的影响链接程序承担同属一个程序的各目标模块（包括库例程目标模块）的链接功能，具体包括各目标模块地址空间的统一以及有关地址敏感代码的修正；而装入程序则主要承担装入模块（即可执行程序或动态链接库例程）的装入功能，其间也会发生装入模块地址空间的调整及相关地址敏感代码的修正过程,3.1.2程序处理与内存管理,程序装入内存空间装入内存空间是程序运行的前提条件。也正因如此，在执行程序各条指令及访问有关数据时须基于内存地址（又称为物理地址或绝对地址）来进行指令与数据的存取。而程序装入模块中原有的指令和数据地址则不一定是内存地址，且往往是相对地址（又称为逻辑地址、虚拟地址），即相对于装入模块起始位置为0推算得到的地址。所以，程序的执行同时还要求以相对地址到内存地址的转换为先决条件。,3.1.2程序处理与内存管理,程序装入模块组织结构就装入模块的组织结构而言，一般由程序前缀部分和程序正文部分构成。前者包括程序名称、程序大小、程序执行起始地址、程序装入起始地址、重定位表、动态链接表等关于程序的装入、链接和执行及地址转换等方面的管理控制信息；后者则为程序的可执行代码即机器指令序列，其中并包括常量数据等,3.1.2程序处理与内存管理,程序装入过程可以是在执行之前一下子完全装入到内存空间，也可以是伴随执行过程及调用需要分步骤装入到内存空间。前者要求装入模块是由整个程序的所有目标模块及库例程目标模块经链接和整合构成的可执行文件；而后者则不要求在启动执行程序时装入整个程序的所有目标模块，也即程序执行所需的部分目标模块（对应于所谓的动态链接库例程）是在程序执行的过程中伴随其被调用才进行链接的，且相关目标模块的装入可能先于程序的启动执行，也可能滞后于程序的启动执行，因为动态链接库例程可被多个程序同时共享和调用。,3.1.2程序处理与内存管理,程序装入过程与地址变换类似地，程序关于相对地址到内存地址的转换可以是一下子全部完成，也可以是伴随程序的分步骤装入和执行过程分阶段完成的，而前者又可细分为装入之前一下子全部完成和装入时一下子全部完成两种情况。为此，程序装入内存的过程可划分为绝对装入、可重定位装入及运行时链接装入等三种方式。,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,绝对装入模块及绝对装入方式,3.1.2程序处理与内存管理,可重定位装入模块及可重定位装入方式,静态可重定位装入方式和动态可重定位装入方式如果在程序装入时一次性地完成程序中所有地址敏感指令及数据的地址修正且以后不再改变，则称对应的地址变换为静态重定位；但如果在程序装入时并不进行由相对地址到绝对地址的转换过程，而是伴随程序执行进展来逐步进行程序中相关地址敏感指令及数据的地址修正，则称对应的地址变换为动态重定位。静态可重定位装入方式并不允许程序在装入之后的运行过程中发生内存位置的移动动态可重定位装入方式及动态重定位过程通常需要一定的硬件机构支持以使地址转换不影响指令执行速度,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,运行时链接装入模块及运行时链接装入方式,程序链接程序的链接，实际就是根据程序目标模块之间的调用及依赖关系，将主调模块及其各级被调模块（包括库例程）逐步装配和链接到一起的过程。根据程序链接发生的时机及链接操作特点，可将程序链接划分为静态链接、装入时动态链接及运行时动态链接等三种方式。,3.1.2程序处理与内存管理,静态链接方式指在程序装入到内存和运行之前，就已将程序的所有目标模块及它们所需要的库例程进行链接和装配成一个完整的装入模块即可执行文件，且以后不再拆开。其具有使链接过程与装入过程相对独立，因而链接程序和装入程序设计简便灵活且使程序装入及启动执行快捷的优点；但其不支持内存空间中目标模块的唯一装入及不利于模块共享和不利于软件版本修改、更新，因为各道程序都必须包含彼此间公共目标模块的拷贝，且若要修改或更新程序装入模块中的某个目标模块，必然会要求进行链接或打开装入模块进行修正。,3.1.2程序处理与内存管理,装入时动态链接方式指在程序装入内存之前不进行程序各目标模块的链接，而是在程序装入时，一边装入内存一边进行链接的。进一步说，在装入一个目标模块时，若发生一个外部模块调用，将引发相应外部目标模块的搜索、装入和链接过程。其间，各目标模块相对独立存在，故易进行个别目标模块的修改更新，且不影响程序的装入和执行，所以便于软件版本的更新换代；同时，若在程序装入及链接过程中发现所需某外部目标模块已在内存，可直接进行链接和无需再次装入，因而具有方便目标模块共享的优点。不过，由于装入和链接过程交织在一起，所以装入程序和链接程序将合二为一，增加设计和开发难度；另外，还将延缓程序的装入和启动执行进度,3.1.2程序处理与内存管理,运行时动态链接方式指将某些目标模块的链接推迟到执行时才进行。具体而言，在程序执行过程中，若发现一个被调用模块尚未链接，则首先在内存中进行搜索以查看其是否装入内存；若已装入内存，则直接将其链接到调用者模块上，否则才进行该模块在外存空间的搜索以及装入内存和链接过程。它是为了避免程序执行过程中可能不被调用和使用的某些目标模块也在执行之前进行了链接和装入而引入的，其目的在于提高系统资源利用率和系统效率，即节省内存空间和加快程序启动执行装入过程。运行时动态链接方式运行时链接装入方式,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,程序链接方式与装入方式间关系及设计策略影响分析,链接程序设计程序链接的关键问题在于，一是统一程序各组成目标模块的地址空间（即形成一片连续且无地址重复情况的地址空间），二是确保各模块中的外部引用符号所在的定义模块已被链接和装配并根据对应寻址方式将相应外部符号引用指令进行适当的地址变换。,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,程序链接时目标模块地址空间统一化示意图,3.1.2程序处理与内存管理,目标模块组成结构示例,链接程序设计-数据结构假设程序各目标模块可重定位表项结构元组形式第一项为地址敏感代码所在的翻译时相对地址，即；而链接表表项结构为由标识符名称、翻译时相对地址及标识符类型构成的三元组形式，即，其中TYPE为PUB说明Identifier为公用标识符且TanslatedAddr为其定义位置，TYPE为EXT说明Identifier为外部引用标识符且TanslatedAddr为其引用位置；同时，程序所有目标模块将顺次装入到起始地址为WorkStartAddr的内存工作区域，而程序的链接起始地址被设定为LinkStartAddr（通常其值为0）,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,链接程序基本设计思想及算法流程（待续）,3.1.2程序处理与内存管理,链接程序基本设计思想及算法流程（续完）,3.1.2程序处理与内存管理,程序外部名表示例,3.1.2程序处理与内存管理,程序外部引用名表示例,3.1.2程序处理与内存管理,由示例链接得到的装入模块,装入程序设计装入程序的主要作用是将可执行程序装入到计算机内存空间，并从指定的位置开始执行。运行时链接装入程序同时还应支持动态链接库的动态链接及装入过程。为此，将主要就绝对装入程序、链接装入程序及自启动装入程序的设计思想及算法流程分别展开介绍。,3.1.2程序处理与内存管理,绝对装入程序设计因为绝对装入程序是将具有绝对地址的完整的装入模块即可执行文件装入物理内存空间，相关装入过程不会牵涉到外部符号引用的处理以及地址的重定位操作，所以设计方案非常简单，只需将程序正文即可执行机器代码装入到由程序前缀指定的起始装入位置开始的内存空间，并转至由程序前缀指定的起始执行位置启动程序执行即可。对于独立的装入程序而言，一般只是在绝对装入程序功能的基础上增加了重定位操作，即利用重定位表有关信息定位到地址敏感代码处，然后根据装入地址、指令相对地址、操作数相对地址及指令寻址方式等修正对应的操作数地址。所以，也不算非常复杂。,3.1.2程序处理与内存管理,链接装入程序设计无论是静态可重定位装入方式或动态可重定位方式，还是运行时链接装入方式，均支持链接过程与装入过程的合二为一。链接装入程序具有很强的代表性，但其真正适用的场合应主要是动态链接库的调用执行及集成开发环境关于系统程序库的调用执行。就链接装入程序的设计而言，鉴于其融入了外部符号引用的处理、链接以及地址的重定位操作，所以相对要复杂许多。但其基本思想与前面的链接程序差别不大，并基本一致。进一步说，装入链接程序也用到了程序的外部名表及外部引用名表，且二者均采用二元组形式的表项结构，即。其中，若采用静态可重定位，则Addr为链接时相对地址，否则为装入时实际物理地址。程序目标模块组织结构（包括重定位表和链接表表项结构）同前所述，并设程序起始装入地址为LoadStartAddr（通常由系统存储管理器分配和提供）。,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,支持重定位选择的链接装入程序的基本算法流程3-1,3.1.2程序处理与内存管理,支持重定位选择的链接装入程序的基本算法流程3-2,3.1.2程序处理与内存管理,支持重定位选择的链接装入程序的基本算法流程3-3,链接装入程序设计补充说明显然，上面的链接装入程序将直接适用于连续内存管理方式，即支持将程序装入到一片连续的内存空间；若系统内存管理采用离散分配方式，则凡涉及内存存取操作及地址计算的地方需做进一步的调整和改进。另外，对于程序库中目标模块的链接和装入过程，链接装入程序还需要提供程序库的自动搜索功能；而为支持动态链接库的动态链接和使用，链接装入程序并应提供内存区域动态链接库库例程标识、共享及搜索机制。,3.1.2程序处理与内存管理,自启动装入程序及其雏形称能够实现自我装入到系统内存的装入程序为自启动装入程序。在计算机系统诞生初期，自启动装入程序是数十个字节的机器语言程序，但严格意义上而言，其根本谈不上自启动装入，而是由人们直接从控制台手工输入的，故而一般称为初始装入程序。后来，人们使用电路实现了数十个字节的所谓“初始引导程序”，并且仅需设置一个按钮即可将该初始引导程序装入到存储器和让它直接开始执行。然后，由该初始引导程序装入指定辅助存储设备上的下一个可执行程序，如监控程序、装入程序和汇编程序等，就可以使一台计算机开始运行。这时的初始引导程序即为自启动装入程序的雏形。,3.1.2程序处理与内存管理,装入程序与系统引导程序鉴于现代计算机系统中，装入程序已演化为操作系统的重要系统过程。也就是说，所有其它程序是在操作系统及其“程序装入”族系统调用的控制下装入到内存的。所以，典型的自启动装入程序的基本任务应包括计算机通电时操作系统自身的装入，其也因此被俗称为系统引导程序。进一步说，此类自启动装入程序至少应由两部分构成，一部分是固化在ROM中的BIOS（包括INT19H自举中断例程），另一部分是保存在操作系统启动盘上的引导记录。,3.1.2程序处理与内存管理,基本输入输出系统BIOS其为计算机提供最基本、最直接的一组硬件控制程序，包括自诊断测试程序、系统自举装入程序、系统设置程序以及主要输入输出设备的设备驱动程序和中断服务程序等，所以已成为现代计算机系统中操作系统与硬件之间的桥梁。当计算机（80 x86结构）刚接通电源后，系统将自动进入实模式和执行始于0 xFFFF0（这一地址空间对应于BIOS）的加电自检例程（PowerOnSelfTest，简称POST），负责对系统内部的各个设备（包括CPU、系统主板、基本的640KB内存、1MB以上的扩展内存、系统ROMBIOS、视频控制器、视频内存、视频信号、同步信号、CRT接口、并行口、串行口、键盘、软驱、硬盘及CD-ROM子系统等）进行检查和测试。然后，执行BIOS设置及初始化例程，以创建中断向量（始于绝对地址0 x00000处的内存空间）、设置寄存器和对一些外部设备进行检测和初始化等。接下来，启动自举例程，按照系统CMOS设置中的启动顺序搜寻软盘、硬盘、光盘及网络服务器等有效的驱动器，读入操作系统的引导记录到系统内存空间，将系统控制权交给该引导记录以完成操作系统的装入、启动和执行。,3.1.2程序处理与内存管理,引导记录由于BIOS已被固化和为计算机硬件厂商直接提供，所以一般情况下真正需要设计的是引导记录。需要强调的是，引导记录必须位于启动盘的引导扇区，即第一个扇区（对应三维物理地址0#柱面、0#磁头、1#扇区，注意此处扇区计数从1开始）；同时引导记录的标志是引导扇区末两个字节必须为0XAA55。引导记录通常基于BIOS中断调用或直接对设备端口进行读写和执行机器指令来实现对操作系统的装入过程。同时，鉴于操作系统的装入、初始化和启动执行过程往往比较复杂，相关代码并非一个引导扇区（512个字节）可以容纳下的，所以操作系统在装入之后，还需经由非引导扇区上存放的其它初始化程序完成必要的系统初始化工作后方可启动执行。,3.1.2程序处理与内存管理,3.1.2程序处理与内存管理,DOS操作系统引导过程,3.1.2程序处理与内存管理,Linux操作系统引导过程,自启动装入程序设计要领基本运行支撑环境不同于普通的系统程序，连操作系统的基本系统功能都无法调用和利用，而只能基于机器指令及ROM-BIOS中断处理服务程序来实现程序的装入。也正因如此，自启动装入程序初始部分特别是引导记录不能采用高级程序设计语言，而只能运用汇编语言或机器语言来编制；而且其中不能利用操作系统的系统功能调用中断指令，但可利用ROM-BIOS中断调用功能指令。对于系统启动时由ROM-BIOS构建和初始化的系统中断向量表往往需要重新设置，其中还可能涉及可编程中断控制器8259A的编程与设置；同时，还需检测和确认各类系统硬部件的配置参数，构建操作系统及其上各类程序的基本运行环境，包括进程管理、文件管理、设备管理和内存管理用数据结构的初始化以及从实模式到保护模式的转换等。系统地址空间及内存空间布局的部署及动态调整。其间，伴随系统装入过程的推进，某些单纯具备装入与初始化功能的模块所占内存可能被覆盖。,3.1.2程序处理与内存管理,内存管理的基本任务是为程序分配必要的内存空间以满足其运行需求方法与技术衍化内存空间为单个程序所独占和连续存放多道程序设计技术与连续分配内存管理方式“零头”（或“碎片”）与“紧凑”技术离散分配内存管理方式（分页、分段与段页式）虚拟存储器技术归纳而言，根据内存分配时为各用户程序分配的内存空间的连续性与否，可将内存管理方式划分为连续分配内存管理方式和离散分配内存管理方式,3.1.3内存管理方法与技术的衍化,连续分配内存管理方式和离散分配内存管理方式的区别,3.1.3内存管理方法与技术的衍化,内存分配使各得其所、提高利用率及适应动态增长要求连续分配/离散分配方式地址映射逻辑地址转换为物理地址，与分配方式相关内存保护基于地址的保护、存取访问控制保护内存扩充对换技术、虚拟存储技术,3.1.4现代操作系统内存管理功能要求,3.2连续分配内存管理,3.2.1单一连续内存管理3.2.2分区内存管理3.2.3覆盖与对换技术,存储管理部件地址映射及地址保护示意图,3.2.1单一连续内存管理,3.2.2分区内存管理,分区内存管理把内存空间用户区（即可分配内存空间）以静态方式或动态方式划分成若干连续内存区域，不妨称之为内存分区或简称分区；在每个分区可装入一道作业，故允许多道程序同时装入内存不同分区和支持多道程序并发执行。分区内存管理方式的内存保护和地址转换机制类似于单一连续内存管理方式，只是对于动态重定位地址转换过程而言，每次进程调度或进程切换时，均需根据当前执行进程的逻辑地址限长及其内存装入起始地址（即其所占用的内存分区起始地址）重新加载界限寄存器和基址寄存器以更新其内容。,3.2.2分区内存管理,如果每道作业只能占用一个分区，则各作业之间无法设立公共区域，于是当多个作业共享同一个例行程序时就只好在各自的内存空间中存放一套，从而限制了内存空间利用率的提升。换句话说，分区内存管理方式本质上并不支持内存共享。但如果由计算机硬件提供多对基址/界限寄存器，并允许一道作业占用两个或多个分区，则可规定某对基址/界限寄存器指定用于存放共享程序代码或数据的共享内存区域（该内存区域只允许读出而禁止写入），于是若干作业共享的例行程序或公用数据便可放在指定的共享内存区域中，同时让各道作业的共享部分具有相同的基址/限长值即可支持内存共享。但事实上，这已经破坏了分区内存管理方式作为连续内存管理方式关于作业不可划分和不可存入不相连续内存区域的限制条件，即已经演化成后面的分段内存管理方式。,3.2.2分区内存管理,固定分区内存管理方式其可分配内存空间划分方式有如下两种使所有的内存分区大小相等。本方式具有程序较小则浪费分区及内存空间、程序过大则无法装入及运行的弊端。但其在利用一台计算机同时控制多个相同对象（如冶炼炉）的场合（如炉温控制系统中）仍被选用，因为有关受控对象对应的控制程序（含控制数据）所需的内存空间大小相同且可预先获悉。把用户区划分为若干大小不一的分区，具体可为多个较小的分区、适量的中等大小的分区及少量的大分区，以避免分区大小相等内存分配方式的缺点。对于小程序，可为之分配小分区；这样，当大、中程序到来时，就可以找到合适的分区予以分配和将其装入内存并运行。当然，若作业任务在每天系统开机初启时便可确立的情况下，也可由系统操作员在系统启动时根据当天任务情况并利用操作系统初始化模块完成内存用户区的具体划分。,固定分区内存管理方式,3.2.2分区内存管理,动态分区内存管理,基本思想根据进程的实际需求，动态地对内存空间进行分配、回收及划分关键问题分区分配用数据结构分区分配算法分区分配与回收操作碎片（零头）处理,？,3.2.2分区内存管理,动态分区内存管理方式分区分配用数据结构,3.2.2分区内存管理,3.2.2分区内存管理,动态分区内存管理方式分区分配算法最佳适应算法最坏适应算法首次适应算法循环首次适应算法快速适应算法伙伴式内存分配与回收算法,基本思想、要领及问题？,伙伴式内存分配与回收过程示例,3.2.2分区内存管理,动态分区内存管理方式内存分配流程,3.2.2分区内存管理,动态分区内存管理方式内存回收时可能情况分析,3.2.2分区内存管理,动态分区内存管理方式内存回收流程,3.2.2分区内存管理,紧凑（拼接）技术,紧凑前,紧凑后,3.2.2分区内存管理,引入紧凑技术的动态分区内存分配流程,3.2.2分区内存管理,3.2.3覆盖与对换技术,覆盖技术的提出主要基于这样的考虑，即一个程序通常无需把所有指令和数据都装入内存，故可把程序划分为若干功能上相对独立的程序段，并让那些不会同时执行的程序段共享一块内存；当对应内存区域被一个新的程序段使用时，原有信息将自动清除和不会产生任何其它影响。从而对于用户来讲，内存似乎扩大了，进而达到了内存扩充的目的。在此，可以互相覆盖的程序段称为覆盖段。,覆盖技术及引入,覆盖技术应用示例,3.2.3覆盖与对换技术,3.2.3覆盖与对换技术,对于一个大型用户程序，可根据其组成程序段之间的相互调用关系并加以分析和建立常驻内存部分、覆盖区以及其与程序段之间的逻辑对应关系，并称之为该程序的覆盖结构。用户程序运行后，可由覆盖管理例程基于系统支持实施覆盖管理，当然覆盖管理例程将常驻内存。程序执行过程中，若其需要调用新的覆盖段，便启动覆盖管理例程读取所需覆盖段并装入到对应的覆盖区中。覆盖技术要求程序员提供一个清晰的覆盖结构，即程序员必须完成程序划分为若干程序段以及规定它们执行和覆盖次序的工作。在此基础上，操作系统和覆盖管理例程根据程序员所提供的覆盖结构实现程序段之间的有序覆盖。自然地，这对于程序员来讲要求较高，所以覆盖技术大多用在系统设计人员清楚了解逻辑地址空间和内部结构的程序如操作系统程序中。,覆盖技术要领,3.2.3覆盖与对换技术,覆盖主要在同一道作业或进程中进行，且覆盖技术只能用于处理相互间较为独立的程序段。进一步说，覆盖技术存在以下主要问题：（1）技术实现困难。覆盖实施的关键在于程序覆盖结构的分析和建立，这对于较大的程序或较复杂的程序而言不仅工作量庞大，而且是相当困难的。同时，其对用户或程序人员的素质要求较高。（2）利用覆盖技术的内存扩充空间非常有限，特别对于大多数规模不断增大的系统软件和应用软件而言，其内存容量的要求远非利用覆盖技术扩充内存就可满足的。（3）覆盖技术无法从根本上解决多道程序、多用户及多个设备共享内存的问题。鉴于此，尽管覆盖技术在早期的计算机系统中曾得到广泛应用，但目前已很少使用。换句话说，覆盖技术现在已退化到在那些仍不能提供虚拟存储技术的系统上要运行大的用户程序时才不得不的一种无奈选择。,覆盖技术局限性,3.2.3覆盖与对换技术,在多道程序环境下，常常会发生这样的现象：一方面在内存中和占用大量内存空间的某些进程由于某些原因被阻塞，极端情况甚至会出现内存所有进程都被阻塞而导致处理机也停下来等待；另一方面，却有不少作业在外存上等待，因无法分配到内存而不能进入内存运行。这将造成系统资源的极大浪费和系统吞吐量的下降。为了解决这一问题，需引入对换技术和在系统中增加对换机制。,对换技术引入,3.2.3覆盖与对换技术,所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序或数据调出到外存上，以便腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是提高内存利用率及系统吞吐量的有效措施，现已广泛应用于各类实用操作系统。按对换单位及实现方式的不同，对换具体可分为两种类型：（1）进程对换，指对换是以整个进程为单位；（2）页面对换或分段对换（又统称为部分对换），指对换以“分页”或“分段”为单位。,对换技术及分类,进程对换-对换空间的管理,文件区和对换区功能、管理目标及管理方式对换区使用情况数据结构空闲盘区表/链（盘块组为基本单位）对换区分配与回收操作分配算法分配操作回收操作,3.2.3覆盖与对换技术,进程对换-进程的换出和换入,进程的换出被换出进程的选择（进程状态+优先级+内存驻留时间）换出过程（换出非共享或不再共享的程序及数据段对换空间申请换出内存释放内存分配数据结构及PCB修改）进程的换入被换入进程的选择（进程状态+换出时间）换入过程（内存申请换入PCB修改）,3.2.3覆盖与对换技术,3.3基本分页内存管理,3.3.1分页内存管理基本思想3.3.2分页机制3.3.3地址变换机构3.3.4多级页表与反置页表3.3.5分页共享与保护,3.3.1分页内存管理基本思想,为实现分页内存管理方式，首先需要引入内存及程序空间的划分机制，其次要求形成基于内存页表的分配与回收机制及基于进程页表的地址转换机构。,3.3.2分页机制,页面与物理块在分页内存管理方式中，内存空间被划分成一系列大小相同的内存区域，称之为物理块（又称为内存分页或页框）。相对应地，各进程逻辑地址空间也被划分成与所装入系统物理块大小相同的若干区域，称之为页面或分页。注意，页面的大小与物理块大小保持一致。换句话说，页面的大小取决于物理块大小。物理块编号与页面编号（一般从0#开始）物理块大小是由机器的地址结构所决定的，也即由硬件决定且取为2的整数次幂,分页存储地址结构及地址变换,分页存储管理地址结构逻辑地址与页号及页内偏移地址之间的换算PageNo=INTAddr/PageLengthPageOffset=AddrMODPageLength举例：若给定逻辑地址8170B，则PageNo=INT8170/4096=1，PageOffset=4074地址变换任务关键在于页号到物理块号的转变,3.3.2分页机制,内存页表（物理块表）,3.3.2分页机制,用户程序,进程页表,页号,块号,内存,3.3.2分页机制,进程页表（或简称页表）,页表项结构？,位图,利用位图（即二维数组Mapm,n）的一位（0/1）来表示一个内存物理块的使用情况，使内存所有物理块都与一个二进制位相对应,3.3.2分页机制,物理块的分配,3.3.2分页机制,基于位图示例为某用户进程分配两个内存物理块的具体过程,3.3.2分页机制,物理块的回收,3.3.2分页机制,分页系统基本的地址变换机构,页表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,页号,物理块号,0,1,2,3,3.3.3地址变换机构,具有快表的地址变换机构,页表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,页号,物理块号,0,1,2,3,输入寄存器,页号,物理块号,快表,3.3.3地址变换机构,快表引入前后数据存取速度比较,假定快表检索时间为20ns，内存访问时间为100ns，则若能在快表中找到CPU给出的页号，CPU为存取一个数据将需要(100+20)=120ns；而若不能在快表中找到CPU给出的页号，CPU为存取一个数据将需要(100+100+20)=220ns。进一步说，若假定快表查找命中率为80%，则其有效访问时间为12080%220(180%)=140ns。,3.3.3地址变换机构,页表空间问题及对策,页表空间问题现代计算机系统支持非常大的逻辑地址空间(232264)，页表变得庞大。例如，对于具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个；若同时设定页表项大小为4B，则每个进程仅页表便需占用4MB内存空间，且要求是连续的解决方案多级页表(页表分页及对换)或反置页表,3.3.4多级页表与反置页表,两级页表结构基本方法,基本思想对页表按内存物理块大小进行分页，对它们进行编号并离散地存放于不同的物理块中；同时为离散分配的页表分页再建立一张页表，称之为外层页表，以记录各页表分页对应的物理块号以前述32位逻辑地址空间、页面大小为4KB的系统为例，若采用一级页表结构，则每个进程页表的页表项可达1M个；而若采用两级页表结构，由于各页表分页包含4KB/4B=1K个页表项，故需1K个页表分页即可，因此外层页表的外层页号及内层页号均为10位。此时逻辑地址结构为：,3.3.4多级页表与反置页表,两级页表结构示例,外层页表,第0页页表,内存,0,1,2,n,0,1,2,1023,第1页页表,0,1,1023,第n页页表,0,1,1023,102,103,107,108,217,101,105,106,104,218,695,3.3.4多级页表与反置页表,具有两级页表的地址变换结构,外层页表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,内层页号,物理块号,外层页表,外层页号,分页页表起始地址,+,3.3.4多级页表与反置页表,多级页表结构,对于64位计算机，如规定页面大小仍为4KB，则每个进程的页表项可达264/4K=252个，且外层页表可能有252/210=242个页表项；即使按每个页表分页1M个页表项来划分，页表分页将达到4MB，而外层页表仍有252/220=4G个页表项，要占用16GB的连续内存空间。可见，无论怎样划分，其结果都是不能接受的。因此，必须采用多级页表，将16GB的外层页表再进行分页，并将各个分页离散的分配到不相邻接的物理块中，在利用第二级的外层页表来映射它们之间的关系。事实上，对于64位的机器，用三级页表结构都很难适应,3.3.4多级页表与反置页表,反置页表,一般页表的表项是按页号进行排序，而页表项内容包括物理块号的；反置页表则是为每一个物理块设置一个页表项并将它们按物理块的号数排序，页表项内容包括对应页号及其隶属进程的标识符在利用反置页表进行地址变换时，是用进程标识符和页号去检索反置页表。若找到与之匹配的表项，则以该表项序号即该页所在物理块号与页内地址构成物理地址；否则地址出错或产生调页中断请求进程外部页表的设立及反置页表Hash检索,3.3.4多级页表与反置页表,基于反置页表的地址变换机构,逻辑地址寄存器,反置页表,物理地址寄存器,PID/页号,物理块号,0,1,3.3.4多级页表与反置页表,3.3.5分页共享与保护,程序往往具有逻辑自然段构成的特点，而分页内存管理系统是基于计算机系统硬件机构决定的物理块及其大小对应的分页概念来进行内存管理的。为此，同一逻辑意义相对完整的程序段或数据段不仅可能占用多个内存分页而需在页表中设置多个页表项，而且它们也可能被不合理地错落分散开来，对应于地址转换过程势必复杂化和增大系统开销，信息共享过程中必要的代码或数据访问所耗费的时空开销必然急剧加大，信息保护实施同样非常困难。,可重入代码（纯代码）一种允许多个进程同时访问的代码为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变，所以它是一种不允许任何进程对其进行修改的代码但事实上，大多数代码在执行时都有可能发生改变，例如其中用于控制程序执行次数的变量及指针、信号量及数组等。为此，在每个进程中都必须配备局部数据区，并把在执行中可能改变的部分都拷贝到该数据区。这样，在程序执行时，只去对属于特定进程私有的数据区中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码,3.3.5分页共享与保护,信息共享比较举例说明,多个用户对文本编辑程序的共享某多用户系统，可同时接纳40个用户，假设均在执行Editor进行文本编辑。若该文本编辑程序含有160KB的代码区和40KB的数据区，则总共需有8000KB的内存空间来支持40个用户。如果该文本编辑程序代码是可重入的，则无论分页系统还是分段系统该程序代码都能被共享，即内存中只需保留一份文本编辑程序的副本，因而所需内存空间仅为4040+160=1760KB,3.3.5分页共享与保护,基于分页的文本编辑器共享,进程1,内存,22,进程2,进程1页表,进程2页表,21,24,23,61,60,80,71,70,160KB,40KB,160KB,40KB,3.3.5分页共享与保护,3.4基本分段内存管理,3.4.1分段内存管理基本思想3.4.2分段机制3.4.3地址变换机构3.4.4分段共享与保护3.4.5分段/分页内存管理系统的比较,分段内存管理引入及基本思想,满足用户在编程和使用上的多方面要求方便编程（作业基于逻辑关系自然分段）LOAD1,A|;STORE1,B|;信息共享信息保护（分段作为信息的逻辑单位）动态链接动态增长（特别是数据段地动态增长）,3.4.1分段内存管理基本思想,分段,作业地址空间被划分为若干段，每个段定义了一组逻辑信息，如主程序MAIN、子程序段X、数据段D及栈段S，各段均有自己的名字（段号）每个段都从0开始编址，并采用一段连续的地址空间，且段的长度取决于相应的逻辑信息组的长度，因而各段长度可不等整个作业的地址空间是二维的，其逻辑地址有段号(名)和段内地址所组成,3.4.2分段机制,内存分配？,利用段表实现地址映射示例,作业空间,段表,内存,段长,段号,0,1,(MAIN)=0,0,50K,(X)=1,0,35K,(D)=2,0,30K,(S)=3,0,40K,基址,2,3,(MAIN)=050K,(X)=135K,(D)=230K,(S)=340K,200K,280K,360K,410K,3.4.2分段机制,段表寄存器,逻辑地址寄存器,段表,物理地址寄存器,+,越界中断,段长,段号,0,1,基址,2,3,+,越界中断,低四位为0,3.4.3地址变换机构,8292,5,4,2,510,100,基于分段的文本编辑器共享,进程1,内存,80K,进程2,进程1段表,240K,段长,段号,0,1,基址,进程2段表,段长,段号,0,1,基址,280K,380K,420K,3.4.4分段共享与保护,共享段表,共享进程计数存取控制字段共享段不同段号,共享进程计数count,分段共享进程描述,共享段表,3.4.4分段共享与保护,共享段的分配与回收,共享段的分配对于第一个请求使用某共享段的进程，由系统为该共享段进行内存区的分配和装入，同时把共享段信息填入对应进程段表中，并在共享段表中为之增加一个表项和填写相关内容；对于以后其它进程提出共享该段要求，则仅需对对应的进程段表表项及共享段表表项修正即可共享段的回收与共享段分配过程恰好相逆,3.4.4分段共享与保护,越界检查与存取控制检查,越界检查段号及段内地址合法性检查存取控制检查段表中对应表项存取控制字段为依据通常访问方式包括只读、只执行（既不可读也不可写）、读/写三种共享段的存取控制应对不同进程赋予不同权限，既要保证信息安全，又要满足运行需要,3.4.4分段共享与保护,环保护机构,程序间控制传输一个程序可调用驻留在相同环或较高特权环中的服务,数据访问一个程序可访问驻留在相同环或较低特权环中的数据,3.4.4分段共享与保护,相似之处实现机制（离散分配、地址映射机构）目的及内涵系统管理需要/用户需要、物理/逻辑单位分页/段长度固定与否、决定因素(系统硬件/信息性质)作业地址空间维数一维/二维、程序员编程内存分配与回收性能优劣零头问题、共享/保护/动态链接,3.4.5分段/分页内存管理系统的比较,3.5段页式内存管理,3.5.1段页式内存管理方式的引入3.5.2基本原理3.5.3地址映射,3.5.1段页式内存管理方式的引入,分页与分段存储管理各有优缺点分页系统能有效地提高内存利用率分段系统则能很好地满足用户需要分页/段存储管理各取所长、有机结合既具有分段系统便于实现、分段可共享、易于保护、可动态链接等一系列优点；又能像分页系统那样很好地解决内存的外部碎片问题以及为各个分段离散地分配内存等问题,3.5.2基本原理,分段与分页方法的结合先将用户程序按信息性质分为若干段（赋予一个段名），再把每个段划分为若干页,主程序段,0,4K,8K,12K,15K,16K,子程序段,0,4K,8K,数据段,0,4K,8K,10K,12K,段页式内存管理地址结构,利用段表和页表实现地址映射,段表,第0段页表,内存,第1段页表,段表寄存器,3.5.3地址映射,段页式系统的地址变换结构,段表寄存器,逻辑地址寄存器,分段页表,物理地址寄存器,+,越界中断,页号,物理块号,段表,段号,页表长度,+,页表始址,状态,越界中断,3.5.3地址映射,3.6虚拟存储管理,3.6.1虚拟存储器概述3.6.2请求分页存储管理3.6.3请求分段存储管理3.6.4请求段页式存储管理,常规存储管理问题与对策,要求将一个作业全部装入内存方能运行一些对内存空间要求超过内存容量的大作业因不能全部装入内存而无法运行同时有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，则只能将少数作业装入内存首先运行，而将其它大量作业留在外存上等待解决方法增加物理内存容量（系统成本和机器条件）从逻辑上扩充内存容量=虚拟存储技术,3.6.1虚拟存储器概述,一次性全部装入及驻留性问题,作业“一次性”全部装入内存并不必要许多作业在每次运行时并非用到其全部程序和数据作业常驻内存存在不合理性因输入输出操作尚未完成而处于长期等待状态的运行进程或某些一次性运行程序对宝贵内存资源的占据问题后果使一些需要运行的作业无法装入运行，从而严重降低内存利用率和减少系统吞吐量,3.6.1虚拟存储器概述,局部性原理,程序在执行时将呈现局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的内存空间也仅局限于某个区域程序在大多数情况下的顺序执行特点过程调用深度及执行轨迹程序循环结构执行及数据结构操作特点局部性表现形式时间局部性（指令执行与数据结构访问）空间局部性（存储单元临近访问）,3.6.1虚拟存储器概述,虚拟存储器技术要点,作业部分装入内存即可启动运行其余部分暂留磁盘程序执行过程页段访问机制已调入内存则直接访问尚未调入内存则缺页/段中断及请求调入页段置换功能技术效果大用户程序在小内存空间的运行多道程序度的提高,3.6.1虚拟存储器概述,虚拟存储器的定义,所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体地说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。实际上，用户看到的大容量只是一种感觉，是虚的，故而得名虚拟存储器。其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。,3.6.1虚拟存储器概述,虚拟存储器的特征,离散性离散分配方式多次性作业被分成多次调入内存和运行对换性程序和数据在作业运行过程中的换进/出虚拟性内存容量的逻辑扩充,3.6.1虚拟存储器概述,调页/段策略-分页/分段调入时机,预调入策略将那些预计在不久之后便会被访问的程序或数据所在的分段或分页，预先调入内存以预测为基础，主要用于进程首次调入请求调入策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的分段或分页不在内存，应立即提出请求，由系统将其所需分段/分页调入内存；易于实现但系统开销大,3.6.1虚拟存储器概述,调页/段策略-分页/分段调入位置,对换区空间充分进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区对换区空间不足文件是否修改分别处理UNIX方式凡未运行过的分页或分段都应从文件区调入，而对于曾运行过又被换出到对换区的分页或分段则从对换区调入,3.6.1虚拟存储器概述,调页/段策略-分页/分段调入过程,缺页/缺段中断发生程序所访问的分页/段不在内存时产生缺页/段中断并转入缺页/段中断处理程序根据页表项外存地址字段调入所缺分页/段页表项及时更新内存不足置换分页/段淘汰算法是否重写磁盘,3.6.1虚拟存储器概述,虚拟存储器的实现方式,请求分页虚拟存储系统技术组成：分页+请求调页+页面置换硬件支持：请求分页的页表机制+缺页中断机构+地址变换机构软件支持：请求调页功能模块+页面置换功能模块请求分段虚拟存储系统请求段页式虚拟存储系统,3.6.1虚拟存储器概述,请求分页的页表机制,页表项的扩充,3.6.2请求分页存储管理,缺页中断机构,缺页中断之中断特征保护CPU现场分析中断原因转入缺页中断处理程序恢复CPU现场缺页中断之特殊性在指令执行期间产生和处理中断信号一条指令执行期间，可能产生多次缺页中断,6,5,4,1,2,3,页面,copyATOB,B:,A:,3.6.2请求分页存储管理,缺页中断处理算法流程,3.6.2请求分页存储管理,地址变换机构,在分页系统的地址变换机构的基础上，增加缺页中断产生和处理并页面置换功能而构成地址变换过程要领从页表找到对应分页的页表项获悉该页尚未调入内存时，应产生缺页中断，请求操作系统从外存把该页调入内存关于快表和页表的检索及表项修改,3.6.2请求分页存储管理,请求分页系统地址变换过程,硬件支持！,3.6.2请求分页存储管理,内存分配最小物理块数的确定,保证进程正常运行所需的最少物理块数若系统为某进程分配的物理块数少于此值，进程将无法正常运行不同于使进程有效工作所需的物理块数与计算机的硬件结构有关，并取决于指令的格式（指令长度及操作数个数）、功能和寻址方式（直接/间接）,3.6.2请求分页存储管理,物理块分配与置换策略,固定分配局部置换为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变可变分配全局置换系统设立一个空闲物理块队列可变分配局部置换依据缺页率酌情增加或减少物理块,3.6.2请求分页存储管理,物理块分配算法,平均分配算法将系统可供分配的物理块平均分配按比例分配算法BlockOfPk=maxminBlocks,BlocksPagesOfPk/PagesOfPi考虑优先权的分配算法照顾重要或紧迫的作业能尽快完成,3.6.2请求分页存储管理,页面置换算法及抖动与缺页率,页面置换算法与抖动如果所用置换算法不当，便可能导致这样一种情形：刚被换出的页面很快又被访问，需重新调入，为此，又需再选一页换出；而此刚被换出的页面，不久也被访问，故又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分的时间耗费在页面置换的工作上，称该进程发生了抖动（或称之为颠簸）缺页率缺页率=缺页中断次数/页面访问次数,3.6.2请求分页存储管理,最佳置换算法,基本思想选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存评价理想化算法，具有最好性能（对于固定分配页面方式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要用于算法评价参照,3.6.2请求分页存储管理,最佳置换算法举例说明,某进