计算机操作系统05存储管理课件

,*,第五章 存储管理,第五章 存储器管理,教学目的与要求：,1了解操程序的编译、,装入和链接,2掌握存储器管理的主要功能和基本概念,3掌握储器管理的连续分配和离散分配方式,4了解,IBM-PC,微机中的存储管理方式,重点与难点：,1动态重定位、对换等基本概念,2动态分区分配算法与时机，分页与分段存储管理,3地址转换,主要内容：,51 程序的装入和链接,52 连续分配存储管理方式,53 对换,54 分页存储管理方式,55 分段存储管理,56 作业,2,5.1 程序的装入和链接,在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步：,（1）编译（,Compile）,（2）链接（,Link）,（3）装入（,Load）,3,5.1.1 程序的装入,一.绝对装入方式（,Absolute Loading Mode）,装入程序按照模块中的地址将程序和数据装入内存。在这种方式下，内存地址对于程序员来说是可见的。,二.可重定位装入方式（,Relocatable Loading Mode）,也叫相对装入方式，系统根据当时内存的使用情况将模块装入到内存的适当位置。这种方式下，装入程序需先将目标代码中与地址有关的指令和数据全部重定位，因此这种重定位也叫静态重定位。,三.动态运行时装入方式（,Dynamic Run-Time Loading)，,与上述方式不同的是，动态装入方式是在运行时才临时进行重定位工作，因此也叫动态重定位。,4,5.1.2,程序的链接,程序的链接的功能是将分散的若干模块及所需库函数链接在一起形成一个完整的可装入模块。,一.静态链接,静态链接所形成的完整的可装入模块也叫可执行文件，形成后不再分开，可多次执行。需解决以下两个问题：,1.按照模块间的调用关系对相对地址进行修改；,2.按照模块间的调用关系变换外部调用符号。,二.装入时动态链接（,Load-TimeDynamicinking）,在模块被调用装入内存时才临时链接，其优点是：,1.便于软件版本的修改和更新,2.便于实现目标模块共享,三.运行时动态链接（,Run-TimeDynamicLinking）,将部分不常用的模块推迟到运行时才临时链接。,5,5.2 连续分配存储管理方式,连续分配是指为一个用户程序分配一个连续的内存空间。包括单一连续分配和分区式分配方式两种。,5.2.1 单一连续分配,这是最简单的一种存储管理方式，但只能用于单用户.单任务的操作系统中。且通常不设置保护措施。采用这种存储管理方式时，内存分为以下两个分区：,（1）系统区。,（2）用户区。,6,5.2.2 固定分区分配,一.划分分区的方法:,将内存空间划分为若干个固定大小的分区，可用下述两种方法：,1.分区大小相等,2.分区大小不等,二.内存分配,建立分区使用表,表项包含有每个分区的起始地址.大小及状态(是否已分配)。,7,5.2.3 动态分区分配,动态分区分配是根据进程的实际需要，动态地为之分配连续的内存空间。在实现可变分区分配存储管理方式时，必须解决下述三个问题：,（1）分区分配中所用的数据结构；,（2）分区的分配算法；,（3）分区的分配和回收操作。,一.分区分配中的数据结构,1.空闲分区表,2.空闲分区链,8,二.分区分配算法,1.首次适应算法,，,也叫最先适应法。选择找到的第一个不小于程序空间大小的空闲分区分配给程序。,2.,循环首次适应算法，是对首次适应法的发展。,3.最佳适应算法。（区别：最坏适应法）,三.分区分配操作,在动态分区存储管理方式中，主要的操作是分配和回收内存。,1.分配内存,2.回收内存:可能出现下列四种情况,（1）回收区与插入点的前一个分区,F1,相邻接,（2）回收分区与插入点的后一分区,F2,相邻接,（3）回收区同时与插入点的前.后两个分区邻接,（4）回收区既不与,F1,邻接，也不与,F2,邻接。,9,5.2.4 动态重定位分区分配,一.紧凑,把不能被利用的小分区称为“零头”或“碎片”。,通过移动，把多个分散的小分区拼接成大分区的方法被称为“拼接”或“紧凑”。但是，由于紧凑后的程序的绝对地址再一次发生改变，导致程序无法继续运行。,二.动态重定位,就是将重定位工作推迟到程序运行时再进行的一种重定位方法。重定位工作由专门的动态地址重定位机构来实现。,三.动态重定位分区分配算法,紧凑动作通常是在找不到足够大的空闲分区来满足用户需求时才进行，具体流程图见教材,P145。,10,5.3 对换,5.3.1 多道程序环境下的对换,所谓“对换”，是指把内存中暂不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。对换是提高内存利用率的有效措施。也称“交换”.,如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”；如果对换是以“页”或“段”为单位进行，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。实现进程对换，系统必须具备三个功能，即对对换空间的管理以及进程的换出和换入。,11,5.3.2 对换空间的管理,在具有对换功能的,OS,中，通常把外存分为文件区和对换区。,为了提高进程换出换入的速度，对对换区的分配采用了连续分配方式，因而对对换区空间的分配与回收，采用了与动态分区方式相同的策略。如采用空闲分区表（链）进行管理；分配算法采用首次适应算法.循环首次适应算法和最佳适应算法等等。操作流程图见教材,P142,图5-9。,与动态分区管理方式相同，对换区的回收操作也可分为四种情况。,12,5.3.3 进程的换出与换入,当内核因执行某些操作而发现内存不足时,便调用对换程序或唤醒对换进程，实现进程的换入与换出。,一.进程的换出,就是将内存中的某些进程调至对换区,以腾出内存空间。两个步骤：,1.选出被换出的进程,原则：从处于阻塞或睡眠状态的进程中选择优先级最低的进程换出；若阻塞队列为空,而空闲内存仍不时,便选择优先级最低的就绪进程换出。当然，通常还要考虑的一个因素是进程驻留内存的时间，驻留时间长的换出。,13,2.换出过程,（1）将非共享的程序和数据段换出；,（2）对于共享的程序段和数据段,判断是否正被其他进程调用,若无，则换出；,（3）申请对换空间，将被换出的程序和数据写入对换区,并释放该进程所占用的内存；,（4）修改进程控制块和内存分配表等数据结构。,二.进程的换入,（1）选择可换入的进程处于“就绪且换出”状态的换出时间最久的进程。,（2）申请合适大小的内存空间。若申请成功,则直接将进程换入；若申请失败,须先将内存中的某些进程换出,腾出足够的内存后,再将该进程换入。如此反复，直至无可换入进程,14,由于连续分配方式会形成许多“碎片”,虽然可通过“紧凑”方法来避免浪费,但须为此付出很大开销。而采用离散分配方式则可取得较好的效率。根据分配时所用基本单位的不同,离散分配方式可分为以下三种:,1.分页存储管理,基本分配单位为页（或页面）,2.分段存储管理,基本分配单位为段,3.段页式存储管理,是上述两种方式的结合，基本分配单位还是页。是目前效率较高使用较多的一种存储管理方案。,5.4 分页存储管理方式,15,5.4.1 分页存储管理的基本方法,一.页面和物理块,1.在分页存储管理方式中，将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。相应地，内存空间也分成与页相同大小的若干个存储块，或称为物理块或页框（,frame）。,由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为“页内碎片”。,2.在分页存储管理方式中的地址结构：,页号,P,位移量,d,P=INTA/L d=A MOD L,其中为逻辑地址,L,为页面大小,d,为页内偏移量（即页内地址）,16,二.页表,页号,物理块号,0,12,1,34,2,65,n,09,系统为每个程建立一张页面映射表,简称页表。其功能是实现从页号到物理块号的映射，从而实现从逻辑地址到物理地址的转换。,页面示意图如下：,（当然，页表中还会含有,其它信息，详细情况将在,虚存管理中介绍）,17,三.页面大小的选择,在确定地址结构时，若选择的页面较小，一方面可使内存碎片小，并减少了内存碎片的总空间.有利于提高内存利用串；但另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存；此外，还会降低页面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但却又会使页内碎片增大。因此。页面的大小应选得适中，通常页面的大小是2的幂，且常在29一212之间，即在512字节一4,KB,之间。,页面大小的选择也与系统的能力有关。现在的系统多选择较大的页面以提高运行效率。,18,5.4.2 地址变换机构,地址变换机构的基本任务是实现逻辑地址到物理地址的转换。,一.基本的地址变换机构,1.页表通常全部或者部分驻留在内存中，且随着进程滚进滚出内存；,2.系统为每个活动进程设置一个页表寄存器（单机系统中只有一个）,，,用来存放页表在内存的始址和页表的长度。（进程未执行时,页表的始址和长度是存放在该进程的,PCB,中）,3.地址转换过程(见教材,P152,图5-17),静态页式管理的另一个关键问题是地址变换。即怎样由页号和页内相对地址变换到内存物理地址的问题。,19,另外，由于静态重定位可以使,CPU,直接访问物理地址，而分区式管理中的动态重定位也只需把基址寄存器中的分区起始地址与待访问指令的虚地址相加即可得到所要访问的物理地址。这两种重定位法都不需要访问内存就可得到待执行指令所要访问的物理地址。页式管理时，地址变换的速度也是设计地址变换机构时必须考虑的问题之一。,例如，设一个3页长的进程具有页号0，1，2，但其对应的页面号则为2，3，8。设每个页面长度为1,K，,指令,LOAD 1，2500,的虚地址为100。地址转换过程如下：,首先，需要有一个装置页表始址和页表长度用的控制寄存器。系统把所调度执行的进程页表始址和长度从请求表中取出置入控制寄存器中。然后，由控制寄存器的页表始址，可以找到页表所在位置。,20,并由虚地址100可知，指令,LOAD 1，2500,在第0页的第100单元之中。由于第0页与第2个页面相对应，因此，该指令在内存中的地址为2048+100=2148。,当,CPU,执行到第2148单元的指令时，,CPU,要从有效地址2500中取数据放入1号寄存器中。为了找出2500对应的实际物理地址，地址变换机构首先将2500转换为页号与页内相对地址组成的地址形式。即,p=2，w=452。,由页表，可知第2页所对应的页面号等于8。最后，将页面号8与页内相对地址,w=452,相连，得到待访问的物理内存地址8644。,二.具有快表的地址变换机构,在具有一级页表的系统中，,CPU,每访问一个数据就必须两次访问内存，效率很低。在具有多级页表的系,21,统中更为严重。因此，为了提高地址变换速度,在地址变换机构中,增设一个具有并行查寻能力的特殊高,速缓冲存储器,又称快表。其工作机理见教材,P153,图。,5.4.3 两级和多级页表,现代的大多数计算机系统,都支持非常大的逻辑地址空。这时，页表就会变得很大,需要占用相当大的连续的内存空间。这很不经济，通常采用多级页表的办法来解决，即只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上,需要时再将它们调入内存。,一两级页表地址结构,外层页号 外层页内地址 页内地址,P1,P2,d,22,二多级页表结构,一般情况下，采用两级页表已能满足需要，但是对于逻辑空间巨大的作业或进程，则必须考虑采用多级页表。现在有很多系统都支持多级页表结构。（见教材,P156,图）,544 反置页表,与一般页表相反，反置页表为每个物理块设置一个表项并将它们安物理块的号数排序，通过,hash,表实现物理地址到逻辑地址的映射。对于逻辑地址空间很大的进程很有效，现代很多系统中采用。,23,5.5 分段存储管理,5.5.1 分段存储管理方式的引入,主要有下述几个方面的原因：,1.方便编程：作业按逻辑关系分段，段具有较好的独立性。,2.分段共享的需要；,3.分段保护的需要；,4.有利于实现动态链接；,5.有利于实现数据段的动态增长,24,5.5.2 分段系统的基本原理,（与份页方式十分类似）,一分段,1与分页式管理不同，分段式管理把一个进程的虚地址空间设计成二维结构，即段号,s,与段内相对地址,w。,另外，段的长度是不固定的。每个段定义一组逻辑上完整的程序或数据。,2每个段是一个首地址为零的、连续的一维线性空间。根据需要，段长可动态增长。对段式虚地址空间的访问包括两个部分:段名和段内地址。,3段式管理中以段为单位分配内存，每段分配一个连续的内存区。由于各段长度不等，所以这些存储区的大小不一。而且，同一进程所包含的各段之间不要求连续。,25,二段表,和页式管理方案类似，段式管理程序在进行初始内存分配之前，首先根据用户要求的内存大小为一个作业或进程建立一个段表，以实现动态地址变换和缺段中断处理及存储保护等。与页式管理时一样，段式管理也是通过段表来进行内存管理。,三地址变换机构（与分页方式相似，见教材,P160,图）,四分页和分段的主要区别,1页是信息的物理单位，段是信息的逻辑单位,2页的大小固定且由系统确定，段的长度不固定,决定于用户所编写的程序,3分页的作业地址空间是一维的，分段的作业地址空间是二维的。,26,5.5.3 共享与保护,在多道环境下，常常有许多子程序和应用程序是被多个用户所使用的。这种情况下，如果每个用户进程或作业都在内存保留它们共享程序和数据的副本，那就会极大地浪费内存空间。最好的办法是内存中只保留一个副本，供多个用户使用，称为共享。,2段的保护,与页式管理时相同，段式管理的保护主要有两种。一种是地址越界保护法，另一种是存取方式控制保护法。地址越界保护则是利用段表中的段长项与虚拟地址中的段内相对地址比较进行的。若段内相对地址大于段长，系统就会产生保护中断。不过，在允许段动态增长的系统中，段内相对地址大于段长是允许的。,27,为此，段表中设置相应的增补位以指示该段是否允许该段动态增长。,5.5.4 段页式存储管理方式,一.基本原理,是分页方式与分段方式的有机结合，即先将作业按逻辑关系分段，段内再分页。每个进程只有一个段表，而每个段都有一个页表。,段页式管理的开销会更大。因此，段页式管理方式一般只用在大型机系统中。近年来由于硬件发展很快，段页式管理的开销在工作站等机型上已变得可以容忍了。,28,二.地址变换过程,先查段表以获取相应段所对应的页表地址，再查页表以获取相应的绝对地址，最后访问该物理地址，所以,CPU,每访问一次物理地址至少要三次访问主存。变换过程见教材,P163-164,图。,总之，因为段页式管理是段式管理的页式管理方案结合而成的，所以具有它们二者的优点。但反过来说，由于管理软件的增加，复杂性和开销也就随之增加了。另外，需要的硬件以及占用的内存也有所增加。更重要的是，如果不采用有效的方式提高,CPU,访问内存的速度，将会使得执行速度大大下降。,29,教材,P164,习题：1，2，4，6，9，10，14，15，16，17,56 作业,30,31,