_第04章+存储器管理.ppt

第四章存储器管理,第一节程序的装入和链接（了解）第二节连续分配方式（基础）第三节基本分页存储管理方式（重点）第四节基本分段存储管理方式（重点）第五节虚拟存储器的基本概念（基础）第六节请求分页存储管理方式（重点）第七节页面置换算法（重点）第八节请求分段存储管理方式（重点）,存储器的层次结构,1.存储器的层次结构在现代计算机系统中，存储器是信息处理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。,存储器的层次结构,各种存储器,内存RAM：若干兆字节、中等速度、中等价格、易变的高速缓存Cache：少量的、非常快速、昂贵、易变的磁盘：数百兆或数千兆字节、低速、价廉、不易变的由操作系统协调这些存储器的使用,存储管理的目的,存储器管理的主要对象是内存（主存），而外存主要存放文件，对外存的管理主要是文件管理。（1）主存的分配和管理（2）提高主存储器的利用率（3）“扩充”主存容量（4）存储保护,4.1程序的装入和链接,从源程序到程序执行地址空间的概念重定位的概念程序的装入程序的链接,编译、链接、装入,编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。,从源程序到程序执行,库,装入模块,库,主,子1,子2,库,主,子1,子2,4.1.1程序的装入,就是把链接好的装入模块装入“内存”。装入方式绝对装入：单道（任务）；装入位置是固定的。程序员直接编址或由汇编、编译程序完成地址重定位。可重定位装入（静态重定位）动态运行时装入（动态重定位）提示：通常链接、装入程序是一体的。,地址空间的概念,物理（绝对）地址程序执行每个内存单元的固定顺序地址（编号）。逻辑（相对）地址装入（汇编编译）被链接装配（或汇编、编译）后的目标模块所限定的地址的集合；相对于某个基准量（通常为：0）的编址。,程序中所使用绝对地址（在编译或汇编时给出，也可由程序员直接赋予），要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。此时程序中的逻辑地址与实际内存地址完全相同。,1.绝对装入方式,2.可重定位装入方式,绝对定位方式只能将目标模块装入到内存中事先指定的位置（必须预知），只适合单道程序。在多道程序中，所得到的目标模块的起始地址通常以“0”开始的，程序中的其它地址也都是相对于起始地址计算的（不必预知），这时采用可重定位装入方式。注意：在采用可重定位装入内存后，装入的模块的所有逻辑地址与实际装入内存的物理地址不同。,重定位的概念：把在装入时对目标程序中指令和数据的修改过程称为重定位。它是将逻辑地址变换为物理地址的过程。重定位的类型：静态重定位：程序执行前，一次性链接装入程序，以后不在改变。动态重定位：处理机每次访问主存时，有动态地址变换机构（硬件）自动执行。,重定位概念,作业地址空间内存空间,可重定位装入,图4-2作业装入内存时的情况,静态重定位装入内存的情况,问题,问题的提出：可重定位装入方式，虽然可以将装入模块装入到内存中的任何允许的位置上，但不允许程序运行时在内存中移动位置（即不允许程序在内存中的物理位置发生变化）。问题的解决：把装入模块装入内存后，并不立即把装入模块中的相对地址装换为绝对地址，而是在程序真正要执行时才做地址转换，即采用动态运行时装入方式（装入内存后的所有地址都是相对地址）。,问题的提出：可重定位装入方式，虽然可以将装入模块装入到内存中的任何允许的位置上，但不允许程序运行时在内存中移动位置（即不允许程序在内存中的物理位置发生变化）。问题的解决：把装入模块装入内存后，并不立即把装入模块中的相对地址装换为绝对地址，而是在程序真正要执行时才做地址转换，即采用动态运行时装入方式（装入内存后的所有地址都仍然是相对地址）。,3.动态运行时装入方式,4.1.2程序的链接,链接概念：把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体，装入模块的过程。具体工作：对相对地址的修改；变换外部调用符号。,链接方式（1）静态链接：程序在运行之前，事先将各个目标模块及程序所需的各个库函数，链接成一个完整的装配模块（可执行文件），以后不在拆开。（2）装入时动态链接：将用户原程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式；（3）运行时动态链接：对于某些目标模块程序的链接是在程序执行中需要该模块时，才对它进行链接；,1.静态链接方式,（1）将用户原程序编译后所得到的一组目标模块，都是分开存放的；（2）若发生一个外部调用事件，将引起装入程序去找出相应的外部目标模块，在将它装入内存时，采用边装入边链接的方式，同时修改目标模块中的相对地址。优点：（1）便于修改和更新。（2）便于实现对目标模块的共享。,2.装入时动态链接,将对某些模块的链接推迟到执行时才执行。即：在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。优点：最小化快速装入，节省内存。,3.运行时动态链接,4.2连续分配方式,为用户程序分配一个连续的内存空间。曾被广泛应用，且现在仍被采用。1.单一连续分配2.固定分区分配3.动态分区分配4.可重定位分区分配5.实存扩充技术,4.2.1单一连续分配,单一连续分配的基本思想把内存分为系统区和用户区。系统区仅供OS使用，通常放在低址部分，系统区以外的全部内存空间是用户区。单一连续分配的特点只能用于单用户、单任务的OS中。软件简单，硬件要求低（无需存储保护）实例MS-DOS，CP/M，RT-11,4.2.2固定分区分配,划分分区的方法分区大小相等分区大小不相等内存分配管理分区按大小排队；分区使用表（MBT）：起始地址、大小、状态；由内存分配程序检索分区使用表，找到符合要求的分区。实例：60年代的控制相同对象的控制系统:IBM360的MFT，(每个对象的控制程序大小相同,所需要的数据也一致)缺点：造成存储空间的浪费,4.2.3动态分区分配,思想应作业、进程的实际需要，动态地分配内存空间，位置和大小都不固定。,1.分区分配中的数据结构,数据结构的两种形式:空闲分区表：一个空闲分区占一个表目，包括：分区序号、分区始址、分区大小空闲分区链：（1）分区起始部分组成：控制分区分配信息+链接各分区前向指针+后向指针（2）分区尾部部分组成：状态位（“0”分区未分配，“1”已分配）+分区大小,（1）首次（最先）适应算法：思想:从链首开始循序查找，直至找到一个大小合适的空闲分区为止；优点：优先利用内存低地址部分空闲空间，保留大量高地址空间，以便为后到达的大作业分配大的内存空间。缺点：a.低地址空间因被划成很小的空间，很难再利用。b.每次查找都从低地址部分开始，增加系统查找可用空闲分区的开销；,2.存储分配算法,（2）循环首次适应算法：思想:每次查找空闲分区不是从链首开始，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个满足条件的空闲分区；利用查寻指针，指示下一次起始查寻的空闲分区，并循环查找，如果最后一个（链尾）空闲分区的大小仍不合适，则返回到第一个空闲分区去比较大小是否合适。优点：内存中的空闲分区分布均匀；减少查找空闲内存开销；缺点：系统缺乏大的空闲分区；,（3）最佳适应算法：思想:每次分配内存时，将所有的空闲分区按其容量大小从小到大的顺序排成一个空闲分区链，依次查找大小最接近的空闲分区予以分配，保证较小的碎片。优点：大多数作业能够以较快的速度分配到合适的空闲分区。缺点：宏观上，系统会残留许多难以利用的小的空闲区。,（4）最差适应算法：思想:每次分配内存时，将所有的空闲分区按其容量大小从大到小的顺序排成一个空闲分区链，依次查找大小最接近的空闲分区予以分配，保证较小的碎片。优点：大多数作业能够以较快的速度分配到合适的空闲分区。缺点：系统会残留许多难以利用的小的空闲区。,例题1：存储分配算法,在一个使用交换技术的系统中，按地址从低到高排列的内存空间长度是：10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对于下列顺序的作业请求：12KB10KB15KB18KB12KB问题:(1)分别使用首次(最先)适应算法、循环首次适应算法、最佳适应算法、最差适应说明空间的使用情况;(2)说明暂不能分配情况的处理方法。,为了减小大量难以利用的小空闲分区造成的查找开销，在进行内存分配时，可以事先设定一个限定值，当找到的分区中剩余空间小于该值时，将不再进行分区的分割，而是把整个分区分配给请求者。,3.分区分配操作,空闲分区大小（M.Size）与所需空间大小(U.Size)“匹配”条件：M.SizeU.SizeSize（Size为系统规定不再分割的剩余分区的尺寸）满足：将整个空闲分区分配给所需者；不满足：剩余部分挂接到空闲分区链（表）上。,（1）分配内存,进程运行完毕后释放内存时，系统先检查是否有空闲分区与回收区相临：若有则必须修改空闲分区表或空闲分区链将它们进行合并，回收区或合并后得到的新空闲分区将根据分配算法按它的起始地址或分区大小插入空闲分区表或空闲分区链。,（2）回收内存,系统根据回收区的首地址，从空闲区链（表）中找到相应的插入点，但可能会出现以下四种情况：回收区与插入点的前一个空闲分区F1相邻接；回收区与插入点的后一个空闲分区F2相邻接；回收区与插入点的前、后两个空闲分区相邻接；回收区不与任何一个空闲分区相邻接；缺点管理复杂，总会有闲置的小分区“碎片”。,(a)(b)(c)图4-7内存回收时的情况,(a)：合并（F1和回收区），F1的首址为新的首地址；(b)：合并（回收区和F2），回收区的首址为新的首地址；(c)：合并（F1、回收区和F2），F1的首址为新的首地址；,4.2.4可重定位分区分配1.动态重定位的引入,随着系统接收的作业的增加，内存中连续的大块分区将不存在，产生了大量的“碎片”。前提:新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。解决方案:通过移动内存中作业的位置，把原来多个分散的小分区“拼接”成一个大分区的方法，称为“拼接”或“紧凑”/“紧缩”/“”澄清“。,2.动态重定位的实现,动态重定位概念:作业被装入到内存中的相对地址要转换为物理地址，被推迟到程序指令真正要执行的时候进行。,实现：（1）必须由硬件地址变换机构重定位寄存器支持：存放程序的起始地址;（2）当系统对内存进行了“紧凑”，使得真正访问的内存物理地址=相对地址+重定位寄存器中地址,动态重定位装入方式,动态运行时装入,优点：消除“碎片”，提高了内存利用率，同时提高了系统效率。缺点：（1）需要动态重定位“硬件”机构支持，增加了系统成本；（2）轻度降低了程序执行速度；（3）“紧凑”处理增加了系统开销。,3.可重定位分区分配算法,4.2.5对换技术（Swapping）1.对换的引入,是实存扩充技术中的一种。用于解决内存不足的问题；通过外存缓冲，以进程为单位“滚进滚出”。一个作业的所有进程不必同时位于内存中；对换的时机：创建新进程而内存不足时。,对换概念,指把内存中暂时不能运行的进程或暂时不能用的程序和数据，调出到外存上，以便腾出足够的内存空间。同时当内存中又稍有空闲时，把已具备运行条件的进程或进程所需要的程序和数据，调入内存。,对换类型,整体对换（进程对换）广泛应用于分时系统中；部分对换（分页、分段对换）为了支持虚拟存储系统：分页对换：以“页”为对换单位进行对换；分段对换：以“段”为对换单位进行对换。,2.进程对换系统要实现的功能,（1）对换空间的管理把外存分为：a.文件区（存放文件）提高文件存储空间的利用率;b.对换区（存放内存换出的进程）提高进程换入/出的速度；对换空间管理的主要目标是提高进程换入、换出的速度，因此常将对换空间设置在高速的磁盘中，采用连续分配方式。,（2）进程的换入和换出a.进程的换出：条件:创建进程需更多的内存空间时,或内存空间不够用时;过程:选择阻塞、优先级最低的进程作为换出进程启动盘块将进程的程序和数据传送到磁盘的对换区上。b.进程的换入：条件:当内存空间稍有空闲时;过程:找出就绪、但已经换出（到磁盘上）的进程将其中换出时间最久的进程将其换出,直至已经无可以换入的进程或无可以换出的进程为止。,4.3基本分页存储管理方式,连续分配方式“碎片”过多，“紧凑”方法开销很大，将一个进程直接分散地装入到许多不相邻接的分区中，无须“紧凑”，促使人们产生了离散分配的管理思想,从而引入了“分页”分配管理的管理方式。分为：（1）基本分页（纯分页）管理：不具备页面置换功能；不具备支持实现虚拟存储器的功能；要求把每个作业全部装入内存后才能运行。（2）支持虚存管理的请求分页管理。,4.3.1页面与页表,0,1,2,3,4,5,6,7,8,9,11,10,内存,用户作业,02K-1,第2页（页长2K）,02K-1,4号页架（页长2K）,1.页面,页面（页）：将一个进程的逻辑地址空间分成若干个大小相等的片；顺序编号（从0开始）。物理块（页框/架）：把内存空间分成与页面相同大小的若干个存储块；顺序编号（也从0开始）。,页内碎片：是指在为进程分配内存时，以块为单位将进程中的若干个页也分别装入到多个可以不相邻接的物理块中，进程的最后一页经常装不满一块，而又不可以利用的碎片，称为“页内碎片”。页面大小：（1）页面过小：内存碎片小页面多页表过长占用内存大（2）页面过大：页面少页表长度短占用内存大页内碎片大（3）页面大小适中：2nBytes，一般在：512B8/32K,2.分页地址结构,逻辑地址n-1kk-10,线性的逻辑地址长度为n位,包括两部分：页号P：n-k位,即:地址空间最多允许有2n-kB页；位移量W（页内位移量，即页内地址）：k位,页内地址大小=2kB若给定一个逻辑地址空间中的地址为A，页面大小为L，则可以由公式求出：页号P=INTA/L，页内地址d=AmodL例如：系统的页面大小L为1KB，A=2170B，求出P=2,d=122,逻辑地址3112110,页号P：1231共20位地址空间最多允许有220B=1M页，即每个进程占用1M个页。位移量W：011共12位页内地址大小（即每页的大小）为212B=4KB。,例：现代的大多数计算机系统的逻辑地址空间都支持很大的逻辑地址空间（232264）B，如下逻辑地址长度为32位，包括两部分：,3.页表,页表：系统为每一个进程建立的，在内存中找到每个页面所对应的物理块号的一张页面映像表。一个进程占用多少页，就在页表中有多少页表项。页表的作用：实现从页号到物理块号的地址映射。数据结构：页号、块号、存取控制字段（控制存储块中的内容是允许读/写、只读、只执行）。,内存,图4-11页表的作用,4.3.2地址变换机构,地址映射从逻辑地址到物理地址的变换过程。将用户地址空间中的逻辑地址变换为内存空间中的物理地址，系统设置了地址变换机构。由于页面地址和物理地址一一对应，所以地址变换机构只是将逻辑地址中的页号，转换为内存中的物理地址的物理块号。借助页表完成。,逻辑地址物理地址,1.基本的地址变换机构,页表存放在内存系统区的一个连续空间中；分页地址变换机构变换过程：（1）进程执行之前：PCB（内存中的页表始址+页表长度）（2）进程调度后：页表寄存器PTR（内存中的页表始址+页表长度）（3）检索页表条件：页表长度逻辑地址中的页号不成立：所访问的地址越界，产生一地址越界中断；成立：未地址越界，则：由“页表始址+页号x页表长度”找到该页号在页表中的位置。,提出改进的原因：计算机CPU存取数据需要访问内存两次，处理速度降低为1/2。改进方法：利用联想寄存器（快表）并行查询；空间大小：几K到几百K，存放16512个页表项；,2.具有快表的地址变换机构,实现原理：快表与页表同时访问：（1）在快表中找到相匹配的页号直接从快表中读出对应物理块号；（2）在快表中没有找到相匹配的页号还须找页表，再从页表中对出物理块号；再将此页表项存入快表中，重新更新快表。优点：加快了地址变换的速