第三章 内存管理[1].ppt

第三章第三章内存管理内存管理(1)(1)内存管理内存管理l目的与要求：掌握程序处理基本过程中内存管理相目的与要求：掌握程序处理基本过程中内存管理相关环节的概念及内存管理的各种方法与技术。关环节的概念及内存管理的各种方法与技术。l重点与难点：重定位的基本概念，动态分区分配方重点与难点：重定位的基本概念，动态分区分配方式、分段和分页存储管理方式、虚拟存储器等主要式、分段和分页存储管理方式、虚拟存储器等主要内存管理方式的相关概念及关键技术。内存管理方式的相关概念及关键技术。l作业：作业：2，3，4，5，6，7，8，10，11，15，17，18第三章存储器管理3.1 3.1 存储器的层次结构存储器的层次结构3.2 3.2 程序的装入和链接程序的装入和链接 3.3 3.3 连续分配方式连续分配方式 3.1.1 3.1.1 存储器的层次结构存储器的层次结构1.1.存储器的层次结构存储器的层次结构 在现代计算机系统在现代计算机系统中，存储器是信息外理中，存储器是信息外理的来源与归宿，占据重的来源与归宿，占据重要位置。但是，在现有要位置。但是，在现有技术条件下，任何一种技术条件下，任何一种存储装置，都无法同时存储装置，都无法同时从速度与容量两方面，从速度与容量两方面，满足用户的需求。实际满足用户的需求。实际上它们组成了一个速度上它们组成了一个速度由快到慢，容量由小到由快到慢，容量由小到大的存储装置层次。大的存储装置层次。存储器的层次结构存储器的层次结构 2.2.各种存储器各种存储器l高速缓存高速缓存CacheCache：少量的、非常快速、昂贵、易变的少量的、非常快速、昂贵、易变的l内存内存RAMRAM：若干兆字节、中等速度、中等价格、易变的若干兆字节、中等速度、中等价格、易变的 l 磁盘：磁盘：数百兆或数千兆字节、低速、价廉、不易变数百兆或数千兆字节、低速、价廉、不易变的的 l由操作系统协调这些存储器的使用由操作系统协调这些存储器的使用 3.1.2 3.1.2 存储管理的目的存储管理的目的l内存分配l使各得其所、提高利用率及适应动态增长要求l连续分配/离散分配方式l地址映射l逻辑地址转换为物理地址，与分配方式相关l内存保护l基于地址的保护、存取访问控制保护l内存扩充l对换技术、虚拟存储技术 3.1.3.3.1.3.基本概念基本概念1.1.定定位位（存存储储分分配配）：为为具具体体的的程程序序和和数数据据等等分配存储单元或存储区工作。分配存储单元或存储区工作。2.2.映映射射：把把逻逻辑辑地地址址转转换换为为相相应应的的物物理理地地址址的的过程。过程。3.3.隔隔离离：按按存存取取权权限限把把合合法法区区与与非非法法区区分分隔隔，实现存储保护。实现存储保护。4.名空间l程序员在程序中定义的标识符程序员在程序中定义的标识符l程序符号集合程序符号集合l由程序员自定义由程序员自定义l没有地址的概念没有地址的概念符号指令数据说明I/O说明 5.5.地址空间地址空间l程序用来访问信息所用地址单元的集合程序用来访问信息所用地址单元的集合l逻辑（相对）地址的集合逻辑（相对）地址的集合l由编译程序生成由编译程序生成6.6.存储空间存储空间l主存中物理单元的集合主存中物理单元的集合l物理（绝对）地址的集合物理（绝对）地址的集合l由装配程序等生成由装配程序等生成地址映射地址映射LoadA2003456。1200物理地址空间物理地址空间LoadAdata1data13456源程序源程序LoadA20034560100200编译编译连接连接逻辑地址空间逻辑地址空间BA=1000名空间 地址空间 存储空间7.7.逻辑地址与物理地址逻辑地址与物理地址l逻辑地址逻辑地址（相对地址，虚地址）（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地目标代码通常采用相对地址的形式，其首地址为址为0 0，其余指令中的地址都相对于首地址而，其余指令中的地址都相对于首地址而编址。编址。不能用逻辑地址在内存中读取信息不能用逻辑地址在内存中读取信息l物理地址物理地址（绝对地址，实地址）（绝对地址，实地址）内存中存储单元的地址，可直接寻址内存中存储单元的地址，可直接寻址8.8.存储共享存储共享l内存共享：两个或多个进程共用内存中相内存共享：两个或多个进程共用内存中相同区域同区域l目的：节省内存空间，提高内存利用率目的：节省内存空间，提高内存利用率l实现进程通信（数据共享）实现进程通信（数据共享）l共享内容：共享内容：代码共享，要求代码为纯代码代码共享，要求代码为纯代码 数据共享数据共享 9.9.存储保护与安全存储保护与安全保护目的：保护目的：为多个程序共享内存提供保障为多个程序共享内存提供保障,使在内使在内存中的各道程序存中的各道程序,只能访问它自己的区域，只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程避免各道程序间相互干拢，特别是当一道程序发生错误时序发生错误时,不致于影响其他程序的运不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）实现。（特权指令不能完成存储保护。）1)1)存储保护存储保护l保护系统程序区不被用户侵犯（有意或无意保护系统程序区不被用户侵犯（有意或无意的）的）l不允许用户程序读写不属于自己地址空间的数不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址据（系统区地址空间，其他用户程序的地址空间）空间）2)2)保护过程保护过程-防止地址越界防止地址越界 每个进程都有自己独立的进程空间，每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。越界中断，由操作系统进行相应处理。10.10.内存内存“扩充扩充”通过虚拟存储技术实现通过虚拟存储技术实现 l用户在编制程序时，不应该受内存容量限用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来制，所以要采用一定技术来“扩充扩充”内存内存的容量，使用户得到比实际内存容量大的的容量，使用户得到比实际内存容量大的多的内存空间多的内存空间l具体实现是在硬件支持下，软硬件相互协具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程过这种方法把内存扩充，使用户在编制程序时不受内存限制序时不受内存限制3.2程序的装入和链接程序程序处理基本过程处理基本过程内存装入模块装入装入程序程序链接链接程序程序编译编译程序程序源程序库目标模块符号名符号名空间空间目标地址目标地址空间空间统一的统一的目标地址目标地址空间空间物理地址物理地址空间空间布局？3.2.1 程序的装入1.绝对装入方式绝对装入方式 程程序序中中所所使使用用的的绝绝对对地地址址，可可在在编编译译或或汇汇编编时时给给出出，也也可可由由程程序序员员直直接接赋赋予予。但但在在由由程程序序员员直直接接给给出出绝绝对对地地址址时时，不不仅仅要要求求程程序序员员熟熟悉悉内内存存的的使使用用情情况况，而而且且一一旦旦程程序序或或数数据据被被修修改改后后，可可能能要要改改变变程程序序中中的的所所有有地地址址。因因此此，通通常常是是宁宁可可在在程程序序中中采采用用符符号号地地址址，然然后后在在编编译译或或汇汇编编时时，再再将将这这些些符符号号地地址址转转换换为绝对地址。为绝对地址。l绝对装入模块及绝对装入方式绝对装入模块及绝对装入方式2.可重定位装入方式可重定位装入方式 l静态可重定位装入方式和动态可重定位装入方式静态可重定位装入方式和动态可重定位装入方式l如果在程序装入时一次性地完成程序中所有地如果在程序装入时一次性地完成程序中所有地址敏感指令及数据的地址修正且以后不再改变，址敏感指令及数据的地址修正且以后不再改变，则称对应的地址变换为则称对应的地址变换为静态重定位。静态重定位。l如果在程序装入时并不进行由相对地址到绝对如果在程序装入时并不进行由相对地址到绝对地址的转换过程，而是伴随程序执行进展来逐地址的转换过程，而是伴随程序执行进展来逐步进行程序中相关地址敏感指令及数据的地址步进行程序中相关地址敏感指令及数据的地址修正，则称对应的地址变换为修正，则称对应的地址变换为动态重定位动态重定位。l静态可重定位装入方式并不允许程序在装静态可重定位装入方式并不允许程序在装入之后的运行过程中发生内存位置的移动入之后的运行过程中发生内存位置的移动l动态可重定位装入方式及动态重定位过程动态可重定位装入方式及动态重定位过程通常需要一定的硬件机构支持以使地址转通常需要一定的硬件机构支持以使地址转换不影响指令执行速度换不影响指令执行速度3.动态运行时装入方式 动动态态运运行行时时的的装装入入程程序序，在在把把装装入入模模块块装装入入内内存存后后，并并不不立立即即把把装装入入模模块块中中的的相相对对地地址址转转换换为为绝绝对对地地址址，而而是是把把这这种种地地址址转转换换推推迟迟到到程程序序真真正正要要执执行行时时才才进进行行。因因此此，装装入入内内存存后后的的所所有有地地址址都都仍是相对地址。仍是相对地址。l运行时链接装入模块及运行时链接装入方式运行时链接装入模块及运行时链接装入方式 3.2.2 3.2.2 程序的链接程序的链接程序链接示意图1.静态链接方式2.装入时动态链接装入时动态链接方式有以下优点：装入时动态链接方式有以下优点：(1)便于修改和更新。便于修改和更新。(2)(2)便于实现对目标模块的共享。便于实现对目标模块的共享。3.运行时动态链接这这种种链链接接方方式式是是将将对对某某些些模模块块的的链链接接推推迟迟到到执执行行时时才才执执行行，即即，在在执执行行过过程程中中，当当发发现现一一个个被被调调用用模模块块尚尚未未装装入入内内存存时时，立立即即由由OS去去找找到到该该模模块块并并将将之之装装入入内内存存，把把它它链链接接到到调调用用者者模模块块上上。凡凡在在执执行行过过程程中中未未被被用用到到的的目目标标模模块块，都都不不会会被被调调入入内内存存和和被被链链接接到到装装入入模模块块上上，这这样样不不仅仅可可加加快程序的装入过程，而且可节省大量的内存空间。快程序的装入过程，而且可节省大量的内存空间。3.2.3 3.2.3 重定位重定位 把把作作业业地地址址空空间间中中使使用用的的逻逻辑辑地地址址变变换换成成内内存存空空间间中中的的物物理理地地址址的的过过程程。又又称称地地址址映映射射。如如下下图图，作作业业i i经经过过重重定定位位，把把地地址址集集合合映映射射到到以以10001000为始址的内存中，作为作业为始址的内存中，作为作业i i的存储空间。的存储空间。1 1.重定位的类型重定位的类型 1)1)静静态态重重定定位位:当当用用户户程程序序被被装装入入内内存存时时，一一次次性性实实现现逻逻辑辑地地址址到到物物理理地地址址的的转转换换，以以后后不不再再转转换换（一一般般在在装装入入内内存存时时由由软软件件完完成成）作作业业i i在在执执行行前前一一次次变变址址，直直到到该该作作业业完完成成退退出出内内存存为止。为止。2)动态重定位动态重定位 在程序运行过程中要访问数据时再进行在程序运行过程中要访问数据时再进行地址变换。地址变换。由地址变换机构进行的地址变换，由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。硬件上需要重定位寄存器的支持。2.2.动态重定位的实现方式动态重定位的实现方式l重重定定位位寄寄存存器器：在在执执行行一一条条指指令令取取操操作作数数时时，要要将将指指令令给给出出的的有有效效地地址址(500)(500)与与重重定定位位寄寄存存器器中中的的内内容容（10001000）相相加加，得得访访问问地地址址（15001500），从从而而实实现现了了地地址址动动态修改。态修改。l映映象象方方式式：采采用用页页表表来来描描述述虚虚、实实页页面面的的对应关系对应关系 。3.3 连续分配存储管理 3.3.1 3.3.1 单一连续内存管理单一连续内存管理l在在单单道道环环境境下下，不不管管是是单单用用户户系系统统还还是是单单道道批批处处理理系系统统，进进程程（作作业业）执执行行时时除除了了系系统统占占用用一一部部分分主主存存外外，剩剩下下的的主主存存区区域域全全部部归归它它占占用用。主主存存可可以以划划分分为为三三部部分分：系系统统区区、用用户户区区、空空闲闲区区。用用户户占占用用区区是是一一个个连连续续的的存存储储区区所所以以又又称称单单一一连连续区存储管理续区存储管理。l单单用用户户系系统统在在一一段段时时间间内内，只只有有一一个个进进程程在在内内存存，故故内内存存分分配配管管理理十十分分简简单单，内内存存利利用用率率低低。内内存存分分为为两两个个区区域域，一一个个供供操操作作系系统统使使用用，一一个个供供用用户使用户使用用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0单一连续区存储分配示意图单一连续区存储分配示意图工作流程工作流程 单单一一连连续续区区分分配配采采用用静静态态分分配配和和静静态态重重定定位位方方式式，亦亦即即作作业业或或进进程程一一旦旦进进入入主主存存，就就一一直直等等到到它它运运行行结结束束后后才才能能释释放放主主存存。如如下下图图所所示示的的主主存存分分配配与与回回收收法法。并并且且由由装装入入程程序序检检查查其其绝绝对对地地址址是是否否超超越越，即即可可达达到到保保护护系系统的目的。统的目的。工作流程工作流程(续续)缺点缺点l不支持多道。不支持多道。l主存利用率不高。主存利用率不高。l程序的运行受主存容量限制。程序的运行受主存容量限制。存储保护存储保护 l自自动动地地址址修修改改例例如如，存存储储器器的的地地址址空空间间为为，而而操操作作系系统统位位于于低低址址端端的的内内。对对于于这这样样的的系系统统，我我们们给给用用户户一一个个位位的的地地址址空空间间，并并对对其其每每个个存存储储器器访访问问自自动动加加上上。如如果果操操作作系系统统占占用用高高址址端端的的，则则我我们们取取每每一一个个存存储储访访问问，而而实实际际上上，其其地地址址为为（）。从从而而实实现现了了对对操作系统的保护。操作系统的保护。存储保护（续）存储保护（续）l页页、页页寻寻址址通通过过对对每每个个用用户户生生成成的的地地址址左左端端拼拼接接上上一一位位来来实实现现区区与与用用户户区区。把把操操作作系系统统确确定定在在页页，而而把把用用户户作作业业放放在在页。页。l界界限限寄寄存存器器通通过过增增加加界界限限寄寄存存器器，划划分分区与用户区。区与用户区。3.3.2 3.3.2 固定分区分配固定分区分配 分分区区式式管管理理是是满满足足多多道道程程序序的的最最简简单单的的存存储储管管理理方方案案。它它的的基基本本思思想想是是将将内内存存划划分分成成若若干干个个连连续续区区域域，称称为为分分区区。每每个个分分区区只只能能存存储储一一个个程程序序，而而且且程程序序也也只只能能在在它它所所驻驻留留的的分分区区中中运运行。行。l预先把可分配的主存储器空间分割预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个变，每个分区装一个且只能装一个作业作业l存储分配：如果有一个空闲区存储分配：如果有一个空闲区,则则分配给进程分配给进程 1.固定分区分区分区4分区分区3分区分区2分区分区1操作系统操作系统多个等待队列多个等待队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统单个等待队列单个等待队列固定分区示意图固定分区示意图 2.内存分配管理固定分区使用表固定分区使用表通过设置内存分配表，内存分配简单通过设置内存分配表，内存分配简单缺点：内存利用率不高缺点：内存利用率不高 3.3.2 3.3.2 可变分区分配可变分区分配l基本思想：内存不是预先划分好的，而是当作基本思想：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待需要分割一部分分区给该进程；否则令其等待主存空间主存空间l内存管理：设置内存空闲块表内存管理：设置内存空闲块表记录了空闲记录了空闲区起始地址和长度区起始地址和长度l内存分配：动态分配内存分配：动态分配l内存回收：当某一块归还后，前后空间合并，内存回收：当某一块归还后，前后空间合并，修改内存空闲块表修改内存空闲块表1.1.分区分配中的数据结构分区分配中的数据结构(1)分区分配表（见图 4-3-5）(2)空闲分区链空闲链结构空闲链结构0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表分区分配表：分区分配表分区分配表0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K 2.2.分区分配操作分区分配操作1)分配内存分配内存内存分配流程内存分配流程 2)2)回收内存回收内存 内存回收时的情况 3.3.空闲分区链表空闲分区链表l为为了了实实现现动动态态分分配配，系系统统设设立立空空闲闲分分区区链链表表：每每个个空空闲闲块块的的前前后后两两个个单单元元，放放置置必必要要的的说说明明信信息息和和指指针针。系系统统只只要要设设立立一一个个链链首首指指针针，指指向向第第一一个个空空闲闲块块即即可可。分分配配程程序序可可以以依依照照自自由由块块链链表表，来来查查找找适适合合的的空空闲闲块块进进行行分分配配。（如如下图）下图）4.4.分配算法分配算法 按空闲块链接的方式不同，可以有以下四种算法：按空闲块链接的方式不同，可以有以下四种算法：l最佳适应法最佳适应法l最坏适应法最坏适应法l首次适应法首次适应法l循环首次适应法循环首次适应法1)1)最佳适应算法最佳适应算法l接到内存申请时，在空闲块表中找到接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配一个不小于请求的最小空块进行分配l为作业选择分区时总是寻找其大小最为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。接近于作业所要求的存储区域。l特点：用最小空间满足要求特点：用最小空间满足要求2)2)最坏适应算法最坏适应算法l接到内存申请时，在空闲块表中找接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行到一个不小于请求的最大空块进行分配，分配，与最佳适应法相反，它在作与最佳适应法相反，它在作业选择存储块时，总是寻找最大的业选择存储块时，总是寻找最大的空白区。空白区。l特点：当分割后空闲块仍为较大空特点：当分割后空闲块仍为较大空块块分配算法（续）分配算法（续）3)首次适应法：为为作作业业选选择择分分区区时时总总是是按按地地址址从从高高到到低低搜搜索索，只只要要找找到到可可以以容容纳纳该该作作业业的的空空白白块块，就就把把该该空白块分配给该作业。空白块分配给该作业。4)循环首次适应法循环首次适应法 类类似似首首次次适适应应法法每每次次分分区区时时，总总是是从从上上次次查查找找结结束束的的地地方方开开始始，找找到到一一个个足足够够大大的的空空白白区分配。区分配。5.5.碎片问题碎片问题l经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片l造成存储资源的浪费碎片问题的解决碎片问题的解决l紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域 （紧缩技术，紧致技术，浮动技术，搬家技术）l问题：开销大；移动时机优点：便于动态申请内存便于动态申请内存 便于共享内存便于共享内存 便于动态链接便于动态链接缺点：缺点：碎片问题碎片问题(外碎片外碎片)，内存利用率，内存利用率不高，受实际内存容量限制不高，受实际内存容量限制6.分区式存储管理的优缺点 3.3.3 3.3.3 可重定位分区分配可重定位分区分配1.动态重定位的引入动态重定位的引入紧凑的示意紧凑的示意2.动态重定位的实现动态重定位示意图动态重定位示意图3.3.动态重定位分区分配算法动态重定位分区分配算法动态分区分配算法流程图动态分区分配算法流程图 4.4.可重定位分区的优缺点可重定位分区的优缺点l优优点点:解解决决了了可可变变分分区区分分配配所所引引入入的的“外外零零头头”问问题题。消消除除内内存存碎碎片片，提高内存利用率。提高内存利用率。l缺缺点点:提提高高硬硬件件成成本本，紧紧凑凑时时花花费费时间。时间。