操作系统讲稿内存管理.pptx

主存储器是仅次于CPU的宝贵资源。众多进程共用一个存储器，必然涉及到存储器的分配、安全、利用率、共享以及扩展等诸多问题。存储管理需要做的事情是：将用户程序所用的地址空间转换为主存储器中的实际地址空间，将用户程序的操作地址变换为存储器上的具体位置。为存储空间提供安全和共享的手段。为用户程序实现虚拟存储空间等。第1页/共100页概述DOS分区及分段 Windows XP的存储器 Linux存储管理 实用系统中的存储管理方法实用系统中的存储管理方法第2页/共100页DOS分区及分段 主存储器被限制为主存储器被限制为1MB的内存空间。的内存空间。低端的低端的640KB的基的基本内存。本内存。高端的扩展内存。高端的扩展内存。系统启动后将操作系系统启动后将操作系统调入基本内存的低端统调入基本内存的低端位置，大概占几十位置，大概占几十KB的空间。的空间。基基本本内内存存的的剩剩余余部部分分便便是是用用来来存存放放用用户户程程序序的的用户区。用户区。在在DOS发发展展的的后后期期，已已经经可可以以利利用用扩扩展展内内存存来来存存放放系系统统的的数数据据结结构构、驱驱动动程程序序以以及及某某些些库库文文件件等等内内容容，但但用用户户不不能能对对扩扩展展存存储储器器中中的的内内容容进行修改。进行修改。程序和数据不能突程序和数据不能突破基本内存的限制，因破基本内存的限制，因此，用户程序的大小必此，用户程序的大小必须低于须低于640KB。用户区内只能存放用户区内只能存放一个用户程序，因此，一个用户程序，因此，DOS系统只支持单道程系统只支持单道程序。序。第3页/共100页Windows xp的存储器 Windows xp要求存储器最低为要求存储器最低为64MB。内存被划分为大小为内存被划分为大小为4KB的页面。内存中可以存放多个用的页面。内存中可以存放多个用户任务的页面，因此，户任务的页面，因此，Windows支持多任务同时运行。支持多任务同时运行。用户在编制程序时，其大小最高可达用户在编制程序时，其大小最高可达4GB，但在程序运行，但在程序运行时，并不是全部程序都装入内存，而是只装入程序的部分时，并不是全部程序都装入内存，而是只装入程序的部分页面来运行。页面来运行。当需要装入新的程序页面而内存中又没有足够的空闲区域当需要装入新的程序页面而内存中又没有足够的空闲区域时，操作系统将内存中长期未使用的页面换出到辅助存储时，操作系统将内存中长期未使用的页面换出到辅助存储器上早已安排的页面（器上早已安排的页面（paging file）文件中，腾出空间后）文件中，腾出空间后再将需要换进的页面调入。再将需要换进的页面调入。Windows 支持虚拟存储器。支持虚拟存储器。第4页/共100页Windows xp的存储器 页页面面在在内内存存中中换换出出换换进进Page Faults/sec 是是每每秒秒钟钟发发生生页页面面缺缺失失的的平平均均数数量量。页页面面缺缺失失将将直直接接导致页面换进。导致页面换进。Pages Input/sec 是是从从磁磁盘换进页面的速度。盘换进页面的速度。当当一一个个进进程程引引用用一一个个虚虚拟拟内内存存的的页页面面，而而此此页页面面不不存存在在于于内内存存，就就会会发生页面缺失。发生页面缺失。Pages Output/sec 是是指指为为了了释释放放物物理理内内存存空空间间而而将将页页面面写写入入磁磁盘盘的的速速度。度。当当物物理理内内存存不不足足时时，Windows 会会将将页页面面写写回回到磁盘以便释放空间。到磁盘以便释放空间。出出页页的的峰峰值值往往往往与与进进页页峰值接近。峰值接近。说说明明出出页页多多是是因因为为有有进进页页需需求求，即即只只有有当当内内存存中中没没有有可可分分配配空空间间，同同时时又又必必须须调调入入内内存存新新的的页页面面时时，才才需需要要换换出出页页面。面。第5页/共100页Windows xp的存储器 可可用用物物理理内内存存Available MBytes 是是计计算算机机上上运运行行的的进进程程的的可可用用物物理理内内存存大大小小。它它是是将将零零的的、空空闲闲的的和和备备用用内内存存列列表表的的空空间间添添加加在在一起来计算的。一起来计算的。第6页/共100页Linux存储管理 Linux系统也是将存储器空间划分成页面，系统也是将存储器空间划分成页面，根据进程运行时的需要来对页面进行换进、根据进程运行时的需要来对页面进行换进、换出的。换出的。同样在磁盘上也安排了交换区来与内存同样在磁盘上也安排了交换区来与内存协调工作，以达到扩大内存的目的。协调工作，以达到扩大内存的目的。但是但是Linux系统的交换区多采用在硬盘上系统的交换区多采用在硬盘上划分出一个指定区域来作为交换区，因此，划分出一个指定区域来作为交换区，因此，交换区的大小不可变化。交换区的大小不可变化。第7页/共100页4.1 内存管理功能 用户实体与存储空间分配、释放及分配原则地址映射虚拟存储器存储保护与共享存储区整理 第8页/共100页用户实体与存储器的关系n任务任务在被激活之前在被激活之前存放在辅助存储器存放在辅助存储器上。上。n当任务被激活时，它成为当任务被激活时，它成为进程进入主存储器进程进入主存储器。n进程的描述进程的描述部分部分及主程序及主程序部分始终存放于部分始终存放于主存储器主存储器，其他其他程序和数据部分视需要由操作系统程序和数据部分视需要由操作系统在内存与外存之在内存与外存之间交换间交换。n当用户向计算机当用户向计算机提交提交自己的自己的任务任务时，存储管理是以一时，存储管理是以一种种逻辑形式逻辑形式来进行描述。来进行描述。n而当操作系统而当操作系统处理处理用户的用户的任务任务时，是对具体的时，是对具体的存储器存储器地址进行操作。地址进行操作。n存储管理存储管理的工作就是圆满地处理发生在的工作就是圆满地处理发生在衔接逻辑和物衔接逻辑和物理存储理存储时所产生的各种问题。时所产生的各种问题。第9页/共100页存储空间与存储地址概念：逻辑地址逻辑地址空间物理地址物理地址空间用用户户的的每每一一条条程程序序指指令令要要访访问问的的数数据据都都有有一一个个对对应应的的地地址址，这这个个地地址址被被称称为为逻逻辑地址辑地址。由由于于它它是是相相对对于于0的的地地址址，因因此此又又被被称称为为相对地址相对地址。当当用用户户程程序序被被编编译译为为目目标标代代码码时时也也使使用用的是相对地址。的是相对地址。原原则则上上讲讲，因因此此用用户户可可以以无无限限制制地地加加长长自己的程序。自己的程序。在在具具体体应应用用中中相相对对地地址址的的大大小小受受相相对对地地址址寄寄存存器器位位数数的的限限制制，如如在在Windows 中中相相对对地地址址寄寄存存器器为为32位位，表表示示相相对对地地址址最大可达最大可达4GB。逻逻辑辑地地址址空空间间可可以以定定义义为为：实实体体（用用户户、作作业业、任任务务、进进程程或或程程序序）所所用用的的所所有有逻辑地址的集合逻辑地址的集合。不不同同的的操操作作系系统统赋赋予予逻逻辑辑地地址址空空间间不不同同的表现形式，它的大小也是可以确定的。的表现形式，它的大小也是可以确定的。用用户户可可以以直直接接对对逻逻辑辑地地址址和和逻逻辑辑地地址址空空间进行访问和操作间进行访问和操作。逻逻辑辑地地址址空空间间又又称称为为相相对对地地址址空空间间，有有时时候候也也被被简简称称为为用用户户空空间间或或者者作作业业空空间间。逻逻辑辑地地址址空空间间的的大大小小被被限限制制在在0到到相相对对地地址最大值之间。址最大值之间。内存中的实际地址被称为物理地址。内存中的实际地址被称为物理地址。由由于于它它并并不不和和任任何何相相对对地地址址相相关关，因因此，物理地址又称为绝对地址。此，物理地址又称为绝对地址。物物理理地地址址的的最最小小值值为为0，最最大大值值取取决决于于内内存存的的大大小小和和内内存存地地址址寄寄存存器器的的所所能能表表现现的的最最大大值值，二二者者中中较较小小的的那那一一个值为物理地址的最大值。个值为物理地址的最大值。物物理理地地址址空空间间可可以以定定义义为为：当当逻逻辑辑地地址址空空间间被被映映射射到到内内存存时时所所对对应应的的物物理理地址的集合。地址的集合。物理地址空间又称为物理地址空间又称为绝对地址空间绝对地址空间。物物理理地地址址空空间间并并不不是是指指物物理理内内存存，只只有有当当逻逻辑辑地地址址空空间间存存在在时时，才才会会有有物物理地址空间。理地址空间。物物理理地地址址空空间间受受存存储储器器大大小小的的限限制制，也也就就是是说说物物理理地地址址空空间间最最大大只只能能达达到到内存的大小。内存的大小。第10页/共100页一、地址重定位装装入入后后的的作作业业并并不不能能立立即即运运行行，因因为为作作业业中中每每一一个个指指令令要要访访问问的的地地址址依依然然是是相相对对地地址址，相相对对地地址址是是逻逻辑辑地地址址空空间间中中的的地地址址，并并不不是是内内存存中中的的实实际际地地址址，因因此此不不能能够访问。够访问。装装入入是是指指将将逻逻辑辑地地址址空空间间安安排到内存中具体的物理位置上。排到内存中具体的物理位置上。装装入入针针对对的的是是整整个个逻逻辑辑地地址址空空间。间。1.装入装入2.地址映射地址映射对对于于指指令令要要访访问问的的地地址址进进行行相相对对地地址址到到绝绝对对地地址址的的变变换换，就就是是地地址映射。址映射。地地址址映映射射就就是是将将逻逻辑辑地地址址空空间间中中的的地地址址映映射射到到物物理理地地址址空空间间中中去去。采用的办法为重定位。采用的办法为重定位。1.装入程装入程序序 在在装装入入过过程程完完成成后后，根根据据装装入入的的起起始始位位置置来来修修改改程程序序中中指指令令要要访访问问的的地地址址，将将相对地址改为绝对地址就是重定位。相对地址改为绝对地址就是重定位。绝对地址绝对地址（BR）相对地址）相对地址 根据不同的根据不同的地址修改时间地址修改时间可可将重定位划分为将重定位划分为静态静态重定位重定位和和动态动态重定位。重定位。第11页/共100页2.重定位：重定位：静态重定位静态重定位动态重定位动态重定位 静态重定位是在装入过程完成后在静态重定位是在装入过程完成后在程序运行程序运行前前，一次一次将所有的指令要访问的地址全部修改将所有的指令要访问的地址全部修改为绝对地址，在程序运行过程中不再修改。为绝对地址，在程序运行过程中不再修改。静态重定位要求程序一旦装入其静态重定位要求程序一旦装入其绝对地址空间绝对地址空间就就不能发生变化不能发生变化了。了。动态重定位是在程序的动态重定位是在程序的运行过程运行过程中，当指令需中，当指令需要执行时对将要访问的要执行时对将要访问的地址地址进行进行修改修改。动态重定位动态重定位允许允许在在程序运行过程程序运行过程中，其中，其绝对地绝对地址址空间发生变化或被分割为不同的区域，空间发生变化或被分割为不同的区域，变化变化后后只需要将基地址寄存器中的内容作对应修改。只需要将基地址寄存器中的内容作对应修改。采用静态重定位方式的采用静态重定位方式的主要优点主要优点是：是：（1）可以在一般机器上全部用）可以在一般机器上全部用软件实现软件实现软件实现软件实现。（2）装入程序可以实现）装入程序可以实现静态连接静态连接静态连接静态连接。静态重定位方式静态重定位方式主要缺点主要缺点是：是：（1）执执行行期期间间程程序序不不不不能能能能在在主主存存储储器器中中移移移移动动动动，所以对提高主存储器的利用率不利。所以对提高主存储器的利用率不利。（2）若若程程序序空空间间大大于于被被分分配配的的物物理理空空间间，由由程程序序员员自自行行采采取取某某种种手手段段来来空空空空间间间间不不不不足足足足问问题题，如采用覆盖结构。如采用覆盖结构。（3）用用户户不不不不能能能能共共共共享享享享已已经经存存放放在在主主存存中中的的同同一一个个程程序序，如如果果几几个个用用户户要要使使用用同同一一个个程程序序，则则每每个个用用户户必必须须在在各各自自的的主主存存空空间间中中存存放放一一个程序副本。个程序副本。采用动态重定位方式的采用动态重定位方式的主要优点主要优点有：有：（1）在在程程序序开开始始执执行行之之前前，不不一一定定要要把把整整个个程程序序都都调调入入到到主主存存中中。一一个个程程序序可可以以被被分分配配在在多多个个不不连连续续的的主主存存物物理理空空间间内内，以以提提高高主存储器的利用率。主存储器的利用率。（2）几几个个程程序序可可以以共共享享存存放放在在主主存存中中的的同同一个程序段。一个程序段。（3）支持）支持虚拟虚拟存储器。存储器。动态重定位方式的动态重定位方式的主要缺点主要缺点有：有：（1）需要有）需要有硬件支持硬件支持。（2）实现存储管理的软件算法）实现存储管理的软件算法比较复杂比较复杂。第12页/共100页二、内存分配与回收 1.存储分配存储分配 2.存储释放存储释放 3.分配原则分配原则 在设计分配程序时需要考虑诸多因素:(1)内存空间的划分(2)数据结构的确定(3)作业空间的划分(4)淘汰算法(5)分配算法 存存储储分分配配实实际际上上是是将将作作业业的的逻逻辑辑地地址址空空间间映映射射成成为内存中的物理地址空间。为内存中的物理地址空间。内内存存中中有有许许多多尚尚未未使使用用的的区区域域即即自自由由区区都都可可以以被被分分配配，但但到到底底选选择择哪哪一一自自由由区区必必须须依依据据分分配配算算法法来来确定。确定。存存储储释释放放实实际际上上是是解解除除逻逻辑辑地地址址空空间间与与物物理理地地址址空空间间的的联联系系，并并释释放放物物理理空间。空间。存存储储释释放放程程序序将将回回收收的的内内存存区区域域重重新新设设定定为为自自由由区区，并并将将其其安安排排进进入入自自由由区区队队列列。进进入入自自由由区区队队列列的的具具体体位位置置也也必必须须依依据据分分配算法。配算法。第13页/共100页三、存储保护与共享 存储保护就是要保护进程的数据不被非法访问者破坏。（1）界地址寄存器保护法（2）访问授权保护第14页/共100页（1）界地址寄存器保护法 采用硬件：基地址寄存器BR长度寄存器LR 采用软件：当进程之间需要共享当进程之间需要共享某些数据时，使用界地址某些数据时，使用界地址寄存器就表现得无能为力。寄存器就表现得无能为力。第15页/共100页（2）访问授权保护当进程访问某个区域时，若进程的当进程访问某个区域时，若进程的访问权限大于等访问权限大于等于被访问区域的权限值于被访问区域的权限值，访问可以进行，否则视为，访问可以进行，否则视为非法。非法。系统为每一个系统为每一个存储区域存储区域都给都给定一个定一个访问权限值。访问权限值。同时也为每一个同时也为每一个进程进程赋予一赋予一个个访问权限值访问权限值。一个进程可以对不同存储区域有一个进程可以对不同存储区域有不同的访问权限；不同的访问权限；一个存储区域也可以被多个具有一个存储区域也可以被多个具有不同访问权限的进程按权限级别进不同访问权限的进程按权限级别进行访问。行访问。访问授权保护还有一个好处是它访问授权保护还有一个好处是它允许存储区域的共享。允许存储区域的共享。第16页/共100页四、虚拟存储器(1)实际内存空间实际内存空间(2)辅助存储器上的内存交换区辅助存储器上的内存交换区(3)虚拟地址虚拟地址(4)换进、换出机制换进、换出机制 虚拟存储器是将内存进行虚拟，使用户能使用比实际内存大得多的虚拟空间。要实现虚拟内存必须具备如下条件：目前的操作系统几乎目前的操作系统几乎全部全部具具备虚拟存储器功能，虽然不同的备虚拟存储器功能，虽然不同的系统其实现虚拟存储器的系统其实现虚拟存储器的基本条基本条件都相似件都相似，但在数据的换进、换，但在数据的换进、换出出策略上是可以不同策略上是可以不同的。的。第17页/共100页存储区整理 当系统运行一段时间后，可能出现如下问题：产生许多碎片；进程过分分散存储；换进、换出的次数过多，导致系统运行缓慢；不断“内存空间不够”。存储区需要整理。第18页/共100页存储器的整理方法：（1）定期将内存中的碎片合并；（2）将某些进程的分散存储区域移动到一起。经过整理后 系统中有更大的自由分区，提高存储管理的效率；在整理时中断所有进程，并且需要消耗较多的CPU时间。第19页/共100页4.2 分区管理 单一分区分配方式多重固定分区分配方式多重动态分区分配方式伙伴系统 第20页/共100页一、单一连续分配方式 1.原理 连续的用户逻辑地址空间，经过装入程序直接装入分区的低地址部分的单一的连续的区域。第21页/共100页2.分配与释放 第22页/共100页3.地址映射 采采用用静静态态重重定定位位的的方方式式在在作作业业装装入入时时一一次次性性对对所所有有指指令令将将要要访访问问的的地地址址进进行行修改。修改。由由于于作作业业的的物物理理地地址址空空间间不不会会发发生生变变化化，因因此此，单单一一连连续续分分区区不不适适合合使使用用动动态重定位态重定位。第23页/共100页4.存储保护 使用界界地地址址寄寄存存器器保保护护法法。其中，基址寄存器的内容是操作系统常驻内存部分以后的首地址，长度寄存器的内容便是用户可用区域的长度。由于操作系统不会发生变化，甚甚至至可可以以不不使使用用界界地地址址寄寄存存器器，而将基址和长度用两个常量来代替。第24页/共100页5.单一连续分区的优缺点（1）管理简单。管理简单。（2）使用安全。）使用安全。（3）不需要任何附加的硬件设备。）不需要任何附加的硬件设备。（1）作业的大小受用户区大小的限制。作业的大小受用户区大小的限制。（2）不支持多用户。）不支持多用户。（3）容易造成系统资源的浪费。）容易造成系统资源的浪费。第25页/共100页二、多重固定分区分配方式 将内存空间由小到大将内存空间由小到大划分为若干个划分为若干个位置固定大位置固定大小不等小不等的区域，每个区域的区域，每个区域可以存放一个作业，存放可以存放一个作业，存放于不同区域的于不同区域的作业可以并作业可以并行行。用户逻辑地址空间依用户逻辑地址空间依然是一个连续的整体，在然是一个连续的整体，在作业申请进入内存时作业申请进入内存时一次一次性装入性装入。描述内存中每一个区描述内存中每一个区域的情况域的情况描述存放于区域中的描述存放于区域中的作业作业 第26页/共100页地址映射地址映射 由由于于作作业业被被分分配配进进入入内内存存后后位位置置不不再再发发生生变变化化，因因此此，地地址址映映射射可可以以采采用用静静态态重重定定位位方方法法。不不过过我我们们要要注注意意到到每每一一个个作作业业的的物物理理地地址址空空间间的的起起始始位位置置是是不不相相同同的的，因因此，对每一个作业进行重定位时要修正基址寄存器的值。此，对每一个作业进行重定位时要修正基址寄存器的值。存储保护存储保护 存储保护可以采取存储保护可以采取界地址寄存器界地址寄存器的方法和的方法和访问授权访问授权保护保护，由于作业在内存中的位置保持不变，可以用两个，由于作业在内存中的位置保持不变，可以用两个常量替代界地址寄存常量替代界地址寄存。第27页/共100页优缺点：优缺点：（1）提高了）提高了CPU的的利用率利用率。（2）作业大小受到最大分）作业大小受到最大分区大小的区大小的限制限制。（3）空间）空间浪费浪费。（4）碎片碎片问题。问题。第28页/共100页三、可变分区分配方式 根据作业对内存空间根据作业对内存空间的申请来划分主存区的申请来划分主存区域，区域的域，区域的大小可变大小可变、位置可变位置可变、数量也可数量也可变变 描述已被分配的区域描述已被分配的区域 描述内存中的自由区域描述内存中的自由区域 为每一个为每一个自由分区自由分区设置一设置一个个链接链接指针来指向下一个指针来指向下一个自由分区，使所有的自由自由分区，使所有的自由分区形成一个链表分区形成一个链表 第29页/共100页多重分区分配与释放多重分区分配与释放 将作业分配到内存中将作业分配到内存中第一第一个碰到个碰到的大于或等于作业的大于或等于作业申请空间的未分配区。申请空间的未分配区。将作业申请大小与内存中将作业申请大小与内存中所有未分配区的大小进行所有未分配区的大小进行比较，直到找到比较，直到找到最小的最小的大大于或等于作业空间的区分于或等于作业空间的区分配给作业。配给作业。将作业申请大小与内存中将作业申请大小与内存中所有未分配区的大小进行所有未分配区的大小进行比较，直到找到比较，直到找到最大的最大的大大于或等于作业空间的区分于或等于作业空间的区分配给作业。配给作业。算法简单但分配比较盲目，算法简单但分配比较盲目，可能造成较小的作业分割可能造成较小的作业分割了较大的空间，使大作业了较大的空间，使大作业无法被分配。无法被分配。优先使用小的自由空间，优先使用小的自由空间，但每次分配以后的剩余空但每次分配以后的剩余空间可能变得过小而成为碎间可能变得过小而成为碎片。片。使用大的自由空间，在进使用大的自由空间，在进行分割后剩余空间还可以行分割后剩余空间还可以被使用，但也使大的自由被使用，但也使大的自由空间无法保留给需要大空空间无法保留给需要大空间的作业。间的作业。另外可以有：另外可以有：最佳适应算法也是最先适应最佳适应算法也是最先适应算法算法最坏适应算法也是最先适应最坏适应算法也是最先适应算法算法如何实现？如何实现？几种方法比较几种方法比较第30页/共100页4.4.地址映射地址映射 动态分区采用动态分区采用动态重定位动态重定位方式来实现地址映射，这方式来实现地址映射，这样作业的基地址发生变化也不会影响执行。样作业的基地址发生变化也不会影响执行。当作业被选择当作业被选择运行时运行时，其物理空间，其物理空间起始地址起始地址被装入被装入基地址寄存器中，基地址寄存器中，CPUCPU每执行一条指令之前每执行一条指令之前重定位硬件重定位硬件对指令要访问的地址进行修改。对指令要访问的地址进行修改。5.5.存储保护存储保护 存存储储保保护护可可以以采采用用界界地地址址寄寄存存器器的的方方法法和和访访问问授授权权保保护护，不不过过由由于于作作业业被被分分配配于于内内存存一一个个连连续续的的区区域域中中，访访问问授授权权保保护护的的作作用用似似乎乎并并不不大大，因因为为作作业业并并没没有有对对其其他他作业空间的访问权力。作业空间的访问权力。第31页/共100页6.6.存储区整理存储区整理经经过过不不断断地地分分配配和和释释放放后后，内内存存中中自自由由分分区区会会变变得得越越来来越越多多和和越越来来越越小小，这这就就使使很很多多小小自自由由分分区区成成为为碎片碎片。可可以以用用紧紧缩缩的的方方法法来来解解决决碎碎片片。紧紧缩缩是是将将内内存存中中已已使使用用区区域域经经过过移移动动沉沉淀淀到到低低地地址址部部分分，从从而而使使碎碎片片浮动浮动到内存的高地址部分合并成较大的可使用空间。到内存的高地址部分合并成较大的可使用空间。用用紧紧缩缩方方法法来来消消除除碎碎片片需需要要占占用用大大量量的的CPUCPU时时间间，并并且在移动过程中稍有且在移动过程中稍有不慎不慎就有可能就有可能破坏破坏全部数据。全部数据。第32页/共100页7.7.多重动态分区的优缺点多重动态分区的优缺点（1 1）多道程度得以提高。）多道程度得以提高。（2 2）提高了内存的利用率。）提高了内存的利用率。（3 3）作业大小依然受内存容量的限制。）作业大小依然受内存容量的限制。（4 4）对碎片问题的解决需要以增加系统开销为代价。）对碎片问题的解决需要以增加系统开销为代价。（5 5）不便共享。）不便共享。第33页/共100页举例：举例：作业作业A要求要求18KB；作业；作业B要求要求25KB；作业；作业C要求要求30KB。用首次适应算法、最佳适应算法来处理该作业序列，看哪种用首次适应算法、最佳适应算法来处理该作业序列，看哪种算法合适。算法合适。os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1第34页/共100页 (1)首次适应算法中的自由主存队列首次适应算法中的自由主存队列 (a)首次适应算法中的自由主存队列首次适应算法中的自由主存队列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1第35页/共100页 (2)最佳适应算法中的自由主存队列最佳适应算法中的自由主存队列 (b)最佳适应算法中的自由主存队列最佳适应算法中的自由主存队列 160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1第36页/共100页(a)首次适应算法中的自由主存队列首次适应算法中的自由主存队列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB (b)最最佳佳适适应应算算法法中中的的自自由由主主存存队队列列 160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 作业作业A要求要求18KB作业作业B要求要求25KB作业作业C要求要求30KB第37页/共100页 分页存储管理方式分页存储管理方式 页式系统应解决的问题页式系统应解决的问题 分区存储管理的主要问题是碎片问题。分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪不能被系统中的任何用户（程序）利用而浪费。费。造成这样问题的主要原因是用户程序装造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。提出了分页存储管理技术。第38页/共100页页式存储管理要解决如下问题页式存储管理系统的地址映射；调入策略；淘汰策略；放置策略第39页/共100页 一、一、页式系统的基页式系统的基本概念本概念 （1 1）页面页面 程序的地址空间被等程序的地址空间被等分成大小相等的片，称为分成大小相等的片，称为页面，又称为虚页。页面，又称为虚页。（2 2）主存块主存块 主存被等分成大小相主存被等分成大小相等的片，称为主存块，又等的片，称为主存块，又称为实页。称为实页。第40页/共100页（3 3）页表页表 为了实现从地址空间到物理主存的映象，为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。地址变换的机构称为页面映像表，简称页表。第41页/共100页01KB01KB2KB3KB 1主存主存作业作业2地址空间地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB 101KB2KB 1作业作业1地址空间地址空间01KB 1作业作业3地址空间地址空间0516页号页号块号块号02140827作业作业1页表页表作业作业2页表页表作业作业3页表页表osos 分页映像存储的例分页映像存储的例 第42页/共100页 （4 4）虚地址结构）虚地址结构(程序字程序字)虚虚地地址址是是用用户户程程序序中中的的逻逻辑辑地地址址，它它包包括括页页号号和和页内地址（页内位移）。页内地址（页内位移）。区区分分页页号号和和页页内内地地址址的的依依椐椐是是页页的的大大小小，页页内内地地址占虚地址的低位部分，页号占虚地址的高位部分。址占虚地址的低位部分，页号占虚地址的高位部分。假假定定页页面面大大小小1024字字节节，虚虚地地址址共共占占用用2个个字字节节(16位位)页号页号 页内地址（位移量）页内地址（位移量）P W 15 10 9 0第43页/共100页（5）页式地址变换页式地址变换l页式地址变换举例页式地址变换举例 作业作业2 2地址空间中，设地址空间中，设100100号单元处有如下指令：号单元处有如下指令：mov mov r1,2500r1,2500。当这条指令执行时，如何进行正确的地址变换。当这条指令执行时，如何进行正确的地址变换。mov r1,250012301KB1KB3KB 1作业作业2地址空间地址空间 2500 2*1024 +452 2*1024 +452 p=2 w=452 p=2 w=452第44页/共100页l 页式地址变换过程页式地址变换过程 000111 011100010015 10 9 0页号页号P页内位移页内位移W页表始址寄存器页表始址寄存器mov r1,250012301KB2KB3KB 1作业作业2地址空间地址空间+021427页表页表 000010 011100010015 10 9 0页号页号P页内位移页内位移W250001KB主存主存2KB3KB4KB5KB6KB7KB8KB9KB10KB 1ososmov r1,2500123第第1页页7*1024+452=7620第45页/共100页l 页式地址变换的步骤页式地址变换的步骤 CPU给出操作数地址给出操作数地址(为为2500)；由分页机构自动地把逻辑地址分为两部分，由分页机构自动地把逻辑地址分为两部分，得到页号得到页号p和页内相对位移和页内相对位移w(p=2，w=452)；根据页表始址寄存器指示的页表始地址，以根据页表始址寄存器指示的页表始地址，以页号为索引，找到第页号为索引，找到第2页所对应的块号页所对应的块号(为为7)；最后，将块号最后，将块号b和页内位移量和页内位移量w拼接在一起，拼接在一起，就形成了访问主存的物理地址就形成了访问主存的物理地址 (7*1024+452=7620)。第46页/共100页二、静态分页管理 1、分配与回收l在静态分页管理时，作业的一页可分配到存储空间的任何一个可用的物理块中 作业完成后，系统回收分配给该作业的内存块 l作业完成后，系统回收分配给该作业的内存块 第47页/共100页2、优缺点、优缺点（1）管理简单（2）每访问一次内存数据需要经过二次寻址。（3）解决了碎片问题。无须内存碎片整理。（4）无法实现共享。（5）作业大小受内存可用页面数的限制。如果想在内存中运行较大的作业，则必须利用内存以外的存储空间。第48页/共100页 例例：有有一一系系统统采采用用页页式式存存储储管管理理，有有一一作作业业大大小小是是8KB8KB，页页大大小小为为2KB2KB，依依次次装装入入内内存存的的第第7 7、9 9、1010、5 5块，试将虚地址块，试将虚地址71457145，34123412转换成内存地址。转换成内存地址。虚地址虚地址 34123412P P3412 3412 2048 2048 1 1W W 3412 mod 20483412 mod 2048 13641364MR=9*2048+1364=19796MR=9*2048+1364=19796虚地址虚地址34123412的内存地址的内存地址是：是：1979619796第49页/共100页三、请求分页管理 1.原理 与静态分页管理与静态分页管理不同不同：按需分配。将按需分配。将需要需要运行运行的页面的页面存放于内存存放于内存，暂时，暂时不不需要需要运行的页面存放于辅存，运行的页面存放于辅存，当需要运行当需要运行存放于辅存存放于辅存上的上的页面时，再将对应的页面调页面时，再将对应的页面调入内存。入内存。注意页表变化注意页表变化第50页/共100页2.分配与淘汰算法动态分配 第51页/共100页分配与淘汰算法淘汰算法衡量淘汰算法依据：衡量淘汰算法依据：好的淘汰算法应该有好的淘汰算法应该有较低的缺页率和淘汰率。较低的缺页率和淘汰率。第52页/共100页选择在最远的将来才被访问的页面淘汰。选择在最远的将来才被访问的页面淘汰。谁是最远的、将来才被访问的页面？选择最早进入内存的页面淘汰 这种方法包含一个假定：这种方法包含一个假定：最早进入内存的页面就是目前最不会被使最早进入内存的页面就是目前最不会被使用的页面。用的页面。假定不成立？假定不成立？系统抖动！系统抖动！第53页/共100页选择最近一段时间内最长时间未被使用选择最近一段时间内最长时间未被使用的页面淘汰的页面淘汰 该算法的该算法的假定假定：长时间未使用的页面不会马上被使用。：长时间未使用的页面不会马上被使用。这正好符合内存这正好符合内存局部性原理局部性原理（内存中某个位置现在被（内存中某个位置现在被访问，很快将再次被访问；某个位置现在被访问，其访问，很快将再次被访问；某个位置现在被访问，其邻近位置也将被访问。）邻近位置也将被访问。）问题：问题：需需要要确确定定一一个个比比较较时时间间段段来来反反映映哪哪一一个个页页面面长长期期未未被被使使用用，时时间间段段过过长长时时该该算算法法将将变变为为先先进进先先出出算算法法，时时间间段段过过短短又又会会使使系系统统频频繁繁地地记记录录访访问问次次数数并并进进行行比比较较，从而增加系统从而增加系统开销开销。第54页/共100页（4）最近未使用算法（NRU）选择页面选择指针遇到的选择页面选择指针遇到的最近未被访问的页面淘汰。最近未被访问的页面淘汰。简化的方法是：简化的方法是：页面选择指针下移，只要遇到刚才页面选择指针下移，只要遇到刚才未使用的页面就可以淘汰。未使用的页面就可以淘汰。第55页/共100页例例:某作业有某作业有a,b,c,da,b,c,d四个页面四个页面,作业在运行过程中的访作业在运行过程中的访问次序为问次序为:a,b,c,a,d,a,:a,b,c,a,d,a,试计算采用试计算采用FIFOFIFO和和LRULRU淘汰算法淘汰算法,各会产生几次缺页中断各会产生几次缺页中断?(?(注：系统为该作业分配个内注：系统为该作业分配个内存块存块)缺页中断次数淘汰的页面进入主存的页面1-a2-B3-C4ad5ba缺页中断次数淘汰的页面进入主存的页面1-a2-b3-c4bd LRU LRUFIFOFIFO第56页/共100页举例FIFO算法的异常现象(Belady)设进程共有8页,且已在内存中分配有3个页面,程序访问内存的顺序为7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1.求缺页次数和缺页率,当分配4个页面时,缺页次数和缺页率为多少?第57页/共100页又进程P有5页,访问串为分得3个页面,情况如何?当分配4个页面时,会出现什么情况?第58页/共100页虚拟存储器 动态分页技术实现了虚拟存储器。虚拟要素？第59页/共100页3.加速寻址 二次寻址？一次寻址？第60页/共100页举例有一页式系统，页表放在主存中如对主存的一次存取需，试问实现一次页面访问的存取时间是多少？如系统有快表，平均命中率为85%，当页表在快表中时，查找时间忽略为0。此时的存取时间为多少？解：（1）1.5*2=3us（2）0.85*1.5+（）*。第61页/共100页4.分页管理的优缺点（1）管理简单。（2）支持虚拟存储器。（3）无法实现共享。作业空间按逻辑意义分割！第62页/共100页4.4 段式管理 简单分段管理 请求分段管理第63页/共100页一、基本概念 作业地址空间按逻辑意义划分成段，作业地址空间按逻辑意义划分成段，每段都有其对应的段号和段长，对分每段都有其对应的段号和段长，对分段数量和分段的长度没有限制。段数量和分段的长度没有限制。内存空间采用多重动态分内存空间采用多重动态分区的形式，分区的长度和区的形式，分区的长度和位置没有限制。位置没有限制。段表将作业中的段对应于内段表将作业中的段对应于内存中的分区。有缺段机制。存中的分区。有缺段机制。1.