《存储器管理》PPT课件.ppt

《《存储器管理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《存储器管理》PPT课件.ppt（183页珍藏版）》请在三一办公上搜索。

1、1,第四章 存储器管理,2,第四章 存储器管理,如何对存储器进行有效的管理，不仅影响到存储器的利用率，而且还对系统性能有重大影响。存储器：内存（本章）外存（第六章）,3,主要内容,new 存储器的层次结构4.1 程序的装入和链接 4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,4,本章学习目标,了解存储管理的研究对象和目的了解存储管理的基本功能和有关的基本概念掌握分页存储管理和分段存储管理的基本概念掌握请求分页和请求分段存储管理的基本原理,New 4.1存储器的

2、层次结构,1.多级存储器结构2.主存储器与寄存器3.高速缓存与磁盘缓存,5,1.多级存储器结构,6,三层由快到慢寄存器与主存（前四者）由操作系统直接管理，可快速访问，称为可执行存储器。后两者需要通过I/O访问,2.主存储器与寄存器,1.主存储器容量大小2.寄存器速度与CPU完全协调长度以字为单位，几十至几百个,7,3.高速缓存和磁盘缓存,高速缓存局部性原理CPU与内存之间磁盘缓存频繁使用的磁盘数据暂存在内存中的 磁盘高速缓存中,8,9,预备知识,地址空间的概念1内存空间(物理空间)内存是由若干个存储单元组成的，每个存储单元的编号称为内存地址(或物理地址)2逻辑空间 经过汇编或编译后形成目标程序

3、是以0为基址顺序进行编址的，目标程序占据的地址空间称为作业的逻辑地址空间。逻辑空间中的地址称为逻辑地址，这是一个相对地址。,10,4.1 程序的装入和链接,为作业创建进程需将其装入内存。要把程序装入内存，就要对程序进行编译和链接。1.编译 由编译程序把源程序翻译成若干个目标模块；2.链接 由链接程序把目标模块以及相关的库函数链接在一起，形成完整的装入模块；3.装入 由装入程序把装入模块装入内存。,11,4.1.1 程序的装入,将一个装入模块装入内存时，有三种方式：绝对装入方式可重定位装入方式动态运行时装入方式,关键在于将逻辑地址转换为物理地址的时机不同,12,1.绝对装入方式Absolute

4、Loading Mode,若编译时知道程序将在内存的(起始)驻留地址，编译程序将产生绝对(物理)地址的目标代码。只适用单道程序环境。装入模块不需再地址转换，直接装入内存。绝对地址，即可在编译或汇编时给出，也可由程序员直接给出。通常在程序中采用符号地址，在编译或汇编时，再将其转换为绝对地址。,13,2.可重定位装入方式Relocation Loading Mode,多道程序环境下，各目标模块的起始地址均从0开始，程序中的其它地址都是相对于起始地址计算的，不是绝对的物理地址，编译程序无法预知目标模块应放于何处。装入时，需根据内存当前的情况，将模块装入到内存的适当位置，存在一个逻辑地址空间到内存物理

5、地址空间的转换过程（即重定位）。,14,2.可重定位装入方式Relocation Loading Mode,逻辑地址与实际装入内存的物理地址会不同。,Load 1,2500 的作用是把2500单元中的数据送至寄存器1。在装入时，指令的地址会由原来的1000，变为11000，取数地址2500也会变为12500。该例中，在装入时对目标程序中指令和数据的地址修改过程称为重定位。该地址变换是在装入时一次完成的，不再改变，故称为静态重定位。,15,3.动态运行时装入方式Dynamic Run-time Loading,把程序装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，仍是相对地址。逻辑地址

6、到物理地址的转换直到程序真正运行时才进行。不仅允许装入模块装入到内存中的任何位置，而且允许程序在运行时在内存中移动。（动态重定位分区分配）,16,4.1.2 程序的链接,根据链接时间的不同，可分为：静态链接装入时动态链接运行时动态链接,关键在于进行链接的时机,17,1.静态链接方式Static Linking,在程序运行之前把各目标模块及库函数链接成一个完整的装入模块，以后不再拆开。装配时需解决两个问题：(1)对相对地址进行修改。(2)变换外部符号。,18,模块ABC在链接前其内部地址均是相对于起始地址0而言的。链接成一个装入模块后，BC的首地址分别变成了L和L+M，这就需要修改BC中的相对地

7、址，将其全部加上L或L+M；对于ABC各模块中所使用的外部调用符号，也都需进行变换，CALL B需变换为JSL L。,19,2.装入时动态链接Load-time Dynamic Linking,编译的目标模块在装入内存时，边装入边链接。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还需修改目标模块中的相对地址。,20,2.装入时动态链接Load-time Dynamic Linking,优点:VS 静态链接 1.便于修改和更新 各目标模块分开存放，便于修改或更新。静态链接要修改或更新时，需重新打开装入模块，低效。2.便于实现对目标模块的

8、共享 可将一个目标模块链接到几个应用模块，实现多个应用程序对该模块的共享。静态链接，每个应用模块都必须含有该目标模块的完整拷贝，无法共享。,21,3.运行时动态链接Run-time Dynamic Linking,把对某些模块的链接推迟到执行时进行。在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并链接到调用者模块上。优点：本次执行不需要的模块不链接。可加快装入过程，而且节省内存空间。,22,4.1 程序的装入和链接 小结,程序的装入绝对装入方式可重定位装入方式动态运行时装入方式程序的链接静态链接方式装入时动态链接运行时动态链接,23,4.2 连续分配方式,连续分配方式

9、，指为一个用户程序分配一个连续的内存空间。4.2.1 单一连续分区分配 4.2.2 固定分区分配4.2.3 动态分区分配4.2.4 动态重定位分区分配4.2.5 对换(Swapping),24,4.2.1 单一连续分区分配,1.内存划分(1)系统区 仅提供给OS使用，通常为内存中的低址部分(2)用户区 单一分区，除系统区外的全部内存空间，只提供给用户使用2.适用环境 只适用于单用户、单任务环境？,25,4.2.2 固定分区分配,最早使用的一种可运行多道程序的存储管理方式。将内存空间划分为若干个固定大小的区域，在每个分区中可以装入一道作业，当内存中划分成几个分区时，便允许几道作业并发运行；当有一

10、个空闲分区时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业结束时，又可从后备队列中找出另一个作业调入该分区。,划分分区,内存分配,26,1.划分分区的方法,1.分区大小相等使所有的内存分区大小相等。适用于利用一台计算机去控制多个相同对象的场合。缺乏灵活性。2.分区大小不等将内存区分为大小不等的多块，灵活性稍好，可根据程序的大小为之分配适当的分区。,27,2.内存分配,把分区按大小排队，并建立一个分区使用表。分区表中记录各分区的起始地址、大小和状态。分配内存时，检索分区表，如果存在大小合适且未分配的分区，就把其分配给相应的程序，然后置“已分配”标志；若未找到大小足够的分区，

11、则拒绝为之分配内存。,28,2.内存分配,分区大小固定，灵活性仍不足，会产生内存碎片；在某些用于控制相同对象的场合仍有一定应用。,作业2：30K,作业1：112K,29,4.2.3 动态分区分配,动态分区分配是根据进程的实际需要，动态地为之分配内存空间。又称为可变分区分配。示意图,30,可变分区内存使用示意图,31,4.2.3 动态分区分配,三个问题分区分配中的数据结构分区分配算法分区分配操作,32,1.分区分配中的数据结构,记录内存的使用情况，为分配提供依据。(1)空闲分区表在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大

12、小等数据项。,33,1.分区分配中的数据结构,(2)空闲分区链每个分区的起始部分，设置用于链接各分区的前向指针；在分区尾部设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。,前后向指针，大小，状态,34,2.分区分配算法,按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。常用的三种分配算法：首次适应算法循环适应算法最佳适应算法,35,(1)首次适应算法,空闲分区以地址递增的次序链接。分配时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区；然后根据作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。优点：倾向于利

13、用内存中低址的空闲区，保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件。缺点：低址不断被划分，会产生大量的碎片；每次从低址开始查找，会增加查找可用空间的开销。,36,(1)首次适应算法,图中采用的空闲分区链按地址由小到大的顺序对空闲分区进行组织，开始指向以40k为首址的空闲分区（其大小为46k，下一个空闲分区为始址为118k）。,作业5大小为36k,37,(2)循环首次适应算法,分配时，不每次均从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，并从中划出一块与请求的大小相等的内存空间分配给作业。需设置一起始查寻指针，以指

14、示下一次起始查寻的空闲分区，并采用循环查找方式。即如果最后一个(链尾)空闲分区，其大小仍不能满足要求，应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应立即调整起始查寻指针。优点：空闲分区分布均更均匀，减少了查找空闲分区的开销，但会导致缺乏大的空闲分区。,38,(3)最佳适应算法,每次为作业分配内存时，总是把既能满足要求，又是最小的空闲分区分配给作业，避免了“大材小用”。为了加速寻找，要求将所有的空闲区，按其容量大小以递增的顺序形成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。特点：每次似乎是最佳的，然而在宏观上却不一定。每次分配后所切割下来的剩余部分总是最小的，在存储

15、器中会留下许多这样难以利用的小空闲区。,39,(3)最佳适应算法,图中采用的空闲分区链按容量由小到大的顺序组织,40,3.分区分配操作(分配回收),1)分配内存若m.size-u.size=size，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则，从该分区中划分出与请求的大小相等的内存空间分配出去，余下的部分仍留在空闲分区链或空闲分区表中。最后，将分配区的首址返回给调用者。,m.size 空闲分区大小u.size 用户作业大小,41,3.分区分配操作,2)回收内存当一个进程（或程序）释放其所占内存区时，系统将首先检查回收区是否与其它空闲区相邻，若相邻则合并成一个空闲区，否则，将回收

16、区插入空闲分区表（或空闲分区链）中的适当位置。回收情况：A.只有前邻空闲区B.只有后邻空闲区C.既有前邻空闲区又有后邻空闲区D.没有邻接空闲区根据不同情况，A、B、C有不同的合并策略。,42,回收内存示意图,A.将R合并到f1，f1.addr；f1.size+R.size-f1.sizeB.将f2 合并到R，R.addr；f2.size+R.size-f2.sizeC.f1、R、f2合并到f1，f1.addr；f1.size+R.size+f2.size-f1.size；撤消f2空闲区表项D.R作为一个新空闲区，插入到空闲区表（链）的适当位置。,43,4.2.4 动态重定位分区分配,1.动态重

17、定位的引入2.动态重定位的实现3.动态重定位分区分配算法,44,1.动态重定位的引入,为了充分利用内存碎片，可利用“紧凑”操作把多个碎片处理为一个比较大的分区，以便利用。经过紧凑后的某些用户程序在内存中的位置发生了变化，此时需对程序和数据的地址加以修改（变换），即需要进行重定位。,45,2.动态重定位的实现,采用动态运行时装入方式，地址转换推迟到程序指令真正要执行时进行。为避免影响速度，必须有硬件地址变换机构的支持（重定位寄存器），用它来存放程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间，随着对每条指令和数据的

18、访问而自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序的新起始地址，去置换原来的起始地址即可。,46,2.动态重定位的实现,47,3.动态重定位分区分配算法,与动态分区分配算法基本相同，差别仅在于：增加了紧凑功能，在找不到足够大的空闲分区来满足用户需求时进行紧凑。,48,3.动态重定位分区分配算法,优点：解决了动态分区分配所引入的“内存零头”问题。消除内存碎片，提高内存利用率。缺点：提高硬件成本，紧凑时花费CPU时间。,49,动态重定位 VS 静态重定位,静态重定位:当用户程序被装入内存时，一次性实现逻辑地址到物

19、理地址的转换，以后不再转换。动态重定位:在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。动态重定位分区分配VS动态分区分配相对而言，前者具有紧凑功能，需要重定位寄存器支持,50,4.2.5 对换(Swapping),1.对换的引入把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到外存，而把已具备运行条件的进程或进程所需要的程序和数据，换入内存，使其投入运行(从而提高内存利用率)。如果对换以整个进程为单位，称之为“整体对换”或“进程对换”。目的是为了解决内存紧张问题如果对换以“页”或“段”为单位，则称之为“页面对换”或“分段对换”。目

20、的是为了支持虚拟存储系统此小节仅介绍进程对换。为了进程对换，需三方面功能：对换空间的管理、进程的换出及换入。,51,2.对换空间的管理,把外存分为文件区和对换区文件区：用于存放文件；为了提高空间的利用率，对其采用离散分配方式。对换区：用于存放从内存换出的进程；因对换操作频繁，为提高进程换入换出速度，对其采用连续分配方式。(对换是在 内存与 外存的对换区之间进行）,52,2.对换空间的管理,为了对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。与内存在动态分区分配方式中所用的数据结构相似，同样可以用空闲分区表或空闲分区链。对换空间的分配与回收，与动态分区分配方式中

21、的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法。,53,3.进程的换出和换入,进程换出：选择处于阻塞状态且优先级最低的进程作为换出进程，将其程序和数据传送到外存的对换区上，然后便可回收其所占用的内存空间，并对其PCB作相应修改。进程换入：查找处于“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将其换入。,54,4.2 连续分配方式 小结,单一连续分配方式固定分区分配 分区使用表动态分区分配 首次适应算法 循环首次适应算法 最佳适应算法动态重定位分区分配“紧凑”动态重定位的实现（重定位寄存器）对换,55,4.3 基本分页存储管理方式,引入

22、：连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出较大开销。?如果允许将一个进程直接分散地分配到许多不相邻接的分区中，就不必再进行“紧凑”。基于这一思想而产生了离散分配方式，相异于4.2所述连续分配方式。,56,4.3 基本分页存储管理方式,分段存储管理方式 基本单位是段分页存储管理方式 基本单位是页基本的分页存储管理方式，要求把每个作业全部装入内存后方能运行。（不具备页面对换功能）4.3.1 页面和页表4.3.2 地址变换机构4.3.3 两级和多级页表,57,4.3.1 页面与页表,1.页面1)页面和物理块页面：将一个进程的逻辑地址空间分成若干个

23、大小相等的片物理块：内存物理空间分成与页相同大小的若干个存储块分配内存时，可将进程中的若干页(逻辑地址空间)分别装入多个可以不相邻接的块(物理地址空间)中。“页内碎片”,58,1.页面,2)页面大小页面大小应适中，且页面大小应为2的幂，一般为512B8KB。页面太小，减少了内存碎片，有利于提高内存利用率；但也会导致页面过多，页表过长页面太大，则会导致内存碎片较多,59,2.分页存储的地址结构,两部分，前一部分为页号P(220);后一部分为位移量W，即页内地址(212)。从逻辑地址获得页号p和页内偏移dp=INT(A/L)d=A MOD LA逻辑地址；L页大小,60,2.地址结构,61,3.页表

24、,各页离散存储在任一物理块，系统需记录各页面对应的物理块。系统为每个进程建立一张页面映射表，简称页表。进程的所有页，依次在页表中有一页表项，其中记录了其对应的物理块号。页表的作用是实现从页号到物理块号的地址映射。查找页表，即可找到每页在内存中的物理块号。,62,页表的作用实现从页号到物理块号的地址映射,作业每页1K,内存每块1K,63,4.3.2 地址变换机构,功能：完成从逻辑地址（页号+页内地址）到物理地址的转换。(页与物理块的大小完全一致，故)页内地址和内存物理块中的物理地址是一一对应的，无需再转换页号需转换成内存中的物理块号，这也是地址变换机构的实质需做的工作。借助于页表完成。两种实现方

25、法基本的地址变换机构具有快表的地址变换机构,64,1.基本的地址变换机构,由于页表项的总数很多，不可能均用寄存器来实现，页表大多驻留在内存中。需设置一个页表寄存器PTR（Page-Table Register），存放页表在内存的始址和页表的长度。进程未执行时，这两个数据存于进程的PCB中；执行时，才将它们装入PTR。,65,1.基本的地址变换机构,地址变换过程：1)分页地址变换机构自动将有效地址分为页号和页内地址两部分，再以页号为索引去检索页表。2)在检索页表前，将页号与页表长度比较，如果越界则产生一越界中断，本次访问失败3)如果未越界，则 页表始址+页号*页表项长度 得到该页号在页表中的位置

26、，从中可得到该页的物理块号，将之装入物理地址的物理块号部分。4)最后再将有效地址中的页内地址送入物理地址寄存器的块内地址中。,66,分页系统的地址变换机构,67,分页系统的地址变换 实例,逻辑地址为3BADH 页面大小为2KB,页表寄存器,68,1.基本的地址变换机构,一个问题？页表是存放在内存中的，这使CPU每次要存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到该页的物理块号，将此块号与页内偏移量W拼接以形成物理地址；第二次访问内存时，才是从第一步所得地址中获得所需数据(或向此地址中写入数据)。将使计算机的处理速度降低近1/2。？,69,2.具有快表的地址变换机构,增设一

27、个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)或“快表”，用于存放当前访问的那些页表项。（意味着这些页表项不在存放在内存中）,70,2.具有快表的地址变换机构,地址变换过程：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲存储器（快表），将此页号与其中的页号进行比较若有相匹配的页号（在快表中），直接读出其所对应的物理块号，并送物理地址寄存器中。若没有匹配的，还需访问内存中的页表。找到后，把对应的物理块号送地址寄存器；也将此页表项存入快表中。但如果快表已满，则将一个老的且已被认为不再需要的页表项换出。,71,2.具有快表的地址

28、变换机构,72,2.具有快表的地址变换机构,由于成本，快表不可能做的很大，一般只存放16512个页表项。但对于中小型作业来说，已有可能把全部页表项放在快表中，但对于大型作业，则只能将其一部分页表项放入其中。从快表中能找到所需页表项的机率，可达90%以上。,73,练习,例：有一页式系统，其页表存放在主存中：如果对主存的一次存取需要1.5 s,试问实现一次页面访问的存取时间是多少?如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?,74,练习,答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（

29、称为定位）。第二次才根据该地址存取页面数据。页表在主存的存取访问时间=1.5*2=3(s)增加快表后的存取访问时间=0.85*1.5+(1-0.85)*2*1.5=1.725(s),75,练习,某存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：,则逻辑地址0A5C（H）所对应的物理地址为：125C,76,练习,0A5C0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C,77,4.3.3 两级和多级页表,引入：计算机支持的逻辑地址空间非常大(23

30、2264)，每个进程的页表项也非常庞大，需占据大量的连续内存空间，这显然不现实。如何解决？1.采用离散分配方式解决需大量连续内存空间问题(将页表再次进行分块)2.只将当前需要的部分页表项调入内存使页表需占用的内存减少,78,1.两级页表,将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散的页表再建立一张页表，称为外层页表，其每个表项记录了页表分页的物理块号。逻辑地址结构如下：,79,1.两级页表,页内地址:12位，页面大小为212，4KB外层页内地址:10位，每个页表分页中最多可包含210个页表项（对应210个物理块）外层页号:10位，最多允许210个页表分页,80,两级页

31、表示意图,外层页表的每个表项存放的是某页表分页的在内存中的物理块号页表(分页)的每个表项存放的是某页在内存中的物理块号可利用两级页表，实现逻辑地址到物理地址的转换,这里只是物理块号，并不是内存单元的编号,比如外层页号为1,外层页内地址也为1,寻址,81,具有两级页表的地址变换,外层页表寄存器，用于存放外层页表的始址d01.以逻辑地址中的外层页号p1，作为外层页表的索引，找到d0和p1对应的表项，从中可知指定页表分页的始址d1(物理块号)；2.以外部页内地址p2，作为指定页内分页的索引，找到d1和p2对应的表项，从中可知该页在内存的物理块号b3.物理块号b与页内地址d，即构成了要访问的内存的物理

32、地址。,d0,d1,82,如何减少页表所占的内存空间,上述离散分配空间的办法只解决了大页表无需大片连续存储空间的问题，并未减少页表所占的内存空间。如何减少？只把当前需要的一些页表项调入内存，以后再根据需要陆续调入其它的。在采用两级页表的情况下，需把外层页表全部调入内存，对于页表分页只需调入需要使用的。在外层页表的表项中，需增设一个状态位，表示相应的页表分页是否已调入内存。（请求分页存储，虚拟存储器中再作详细介绍）,83,2.多级页表,对于64位机器，若采用两级页表，页内地址12位，外部页内地址10位，这时外部页号会达42位，每个表项占4个字节，就需要244B的连续内存空间。显然无法接受。采用多

33、级页表，将外层页表再进行分页，将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。,84,4.3 基本分页存储管理方式 小结,页面、物理块与页表 分页地址结构：页号页内地址地址变换机构 基本的地址变换机构具有快表的地址变换机构两级和多级页表,85,4.4 基本分段存储管理方式,存储管理方式从固定分区到动态分区分配，进而到分页存储管理方式主要是为了提高内存的利用率。提出基本分段存储管理方式主要是为了满足用户（程序员）在编程和使用上的多方面的要求。,86,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共

34、享4.4.4 段页式存储管理方式,87,4.4.1 分段存储管理方式的引入,为了满足用户和程序的如下需要：1)方便编程用户通常将作业按逻辑关系划分为若干段。希望要访问的逻辑地址是由段名和段内偏移量决定。2)信息共享实现共享是以信息的逻辑单位段为基础的。为实现段的共享，希望存储管理能与用户程序分段的组织方式相适应。,88,4.4.1 分段存储管理方式的引入,3)信息保护对信息的逻辑单位段进行保护4)动态增长段在使用过程中可能会不断增长，唯有分段存储可较好解决该问题5)动态链接动态链接在运行时，只将主程序对应的目标程序段装入内存。在需调用某些段时才将其装入，需要以段作为存储管理的单位。,89,4.

35、4.2 分段系统的基本原理,1.分段2.段表3.地址变换机构,90,1.分段,作业的地址空间被划分为若干个段，每个段用来定义一组逻辑信息，均从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。逻辑地址由段号和段内地址组成。,91,2.段表,进程的多个段被离散的放入内存不同位置。为了能将物理内存与逻辑段地址对应起来，需为每个进程建立一张段映射表。每个段在表中占有一个表项，记录了该段在内存中的始址和段的长度。进程可通过查找段表，找到每个段对应的内存区，实现从逻辑段到物理内存区的映射。,92,利用段表实现地址映射,93,3.地址变换机构,段表寄存器存放段表

36、始址和段表长度SL。,94,与分页系统一样，当段表放在内存中时，每访问一个数据，都须访问两次内存。解决方法也类似，增设一个高速缓冲寄存器用于保存最近常用的段表项。,95,4.分页和分段的主要区别,分页是出于系统管理的需要，分段是出于用户应用的需要一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页是一维地址空间，各个模块在链接时组织成同一个地址空间；只利用一个标记符即可表示一个地址。分段是二维地址空间，各个模块在链接时可以每个段组织成一个地址空间；标识地址需给出段名和段内地址。通常段比页大，因而段表比页表短，可以缩

37、短查找时间，提高访问速度。,96,4.4.3 信息共享,分段系统的突出优点，易于实现段的共享，即允许若干个进程共享一个或多个分段。分页系统也可实现程序和数据的共享，但不如分段系统来得方便。（举例对比）可重入代码：一种允许多个进程同时访问（可被共享）的代码；不允许任何进程对它进行修改。,97,4.4.3 信息共享,例：多用户系统，可同时接纳40个用户，每个用户均可执行文本编辑程序。文本编辑程序有160KB代码和40KB数据区，若代码为非可重入的，需要8000KB内存空间支持40个用户。如果160KB程序代码为可重入的，则不论在分页还是在分段系统中该代码均可被共享，此时所需内存空间为160+40*

38、40=1760KB。,98,4.4.3 信息共享,分页系统中：假定每个页面大小为4KB，代码需占用40个页面，数据需占10页面。每个用户进程的页表中均需建立相应的页表项。如图:,99,进程1,进程2,页表,页表,主存,分页系统中共享editor，需建立比较复杂的页表,0,21,22,60,61,70,71,80,100,分段系统中共享editor示意,进程2,进程1,在分段系统中，实现共享只需在每个进程的段表中为文本编辑程序代码段设置一个段表项，比分页系统简单的多。,101,略过：关于共享的进一步说明,页式地址是一维的，即每个逻辑地址是一个整数，由硬件将其分成：页号|页内位移,故页号是唯一的，

39、程序段的共享必须用相同页号。如：call 2148call 2|100段式地址是二维的，两个数字。各进程的段号未必一致，因此不同的进程可用不同的段号共享同一段。如：call ac1|100 进程1：ac1=2；进程2：ac1=4,102,4.4.4 段页式存储管理方式,分页系统能有效地提高内存利用率，而分段系统则能很好地满足用户需要。？段页式系统,103,1.基本原理,将分段和分页原理结合，先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。段页式系统中，地址结构由段号、段内页号及页内地址三部分组成。,页,104,利用段表和页表实现地址映射,每个作业一张段表，每段一张页

40、表。先查段表，再查该段的页表，才能找到物理块号。再将其与页内地址组合,105,2.地址变换过程,1.利用段表始址d0和段号s来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址d1；2.利用页表始址d1和段内页号P获得对应页的页表项位置，从中读出该页所在的物理块号P；3.利用块号P和页内地址d来构成物理地址。,106,2.地址变换过程,1.利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址；2.利用页表始址和段内页号P获得对应页的页表项位置，从中读出该页所在的物理块号b；3.利用块号b和页内地址来构成物理地址。,107,2.地址变换过程,段页式系统中，访

41、问数据需三次访问内存。第一次访问内存中的段表，取得页表始址；第二次访问内存的页表，取得该页的物理块号，并与页内地址一起组成实际的物理地址；第三次从物理地址中取出指令或数据。为了避免每次均需三次访问，可在地址变换机构中增设一个高速缓冲寄存器，将常用的段表和页表存储在高速缓冲中。,108,4.4 基本分段存储管理方式 小结,分段存储管理方式的引入 方便用户分段系统的基本原理分段系统的地址变换过程段表始址+段号-段的基址 与 段内地址 结合-物理地址信息共享分页系统 与 分段系统的比较段页式存储管理方式段表始址+段号-页表始址 与 页号 结合-页面对应的物理块号 与 页内地址 结合-物理地址,109

42、,4.5 虚拟存储器的基本概念,连续分配方式、基本分页、基本分段存储管理方式均需将一个作业全部装入内存后方能运行，这将导致大作业无法运行。解决方法：物理上增加内存容量 有一定限制从逻辑上扩充内存容量 此即虚拟存储器所要解决的主要问题,110,4.5 虚拟存储器的基本概念,4.5.1 虚拟存储器的引入4.5.2 虚拟存储器的实现方法4.5.3 虚拟存储器的特征,111,4.5.1 虚拟存储器的引入,1.常规存储器管理方式的特征一次性：作业运行前需一次性全部装入内存这可能导致大作业无法装入并非全部程序和数据都需用到，一次装入，浪费内存驻留性：一旦装入便一直驻留内存直至作业结束不再运行的程序模块仍将

43、占用宝贵的内存资源一次性及驻留性是否是必需的？,112,4.5.1 虚拟存储器的引入,2.局部性原理程序执行时的特点：程序执行时，除少部分转移和过程调用指令外，大多仍是顺序执行的。过程调用虽可导致程序由一区域转至另一区域，但调用深度大多不超过5。程序在一段时间内都局部于这些过程的范围内执行。程序中存在循环结构，它们将多次执行程序中对数据结构的处理，往往局限于较小的范围内,113,4.5.1 虚拟存储器的引入,2.局部性原理局部性的表现：空间局限性。一段时间内所访问的地址可能集中于一定的范围之内。（程序的顺序执行）时间局限性。某条指令或数据可能被再次执行或访问。（循环操作）根据局部性原理，程序在

44、运行之前没有必要一次性全部装入，也没必要长期驻留内存。,114,4.5.1 虚拟存储器的引入,引入虚拟存储器基于局部性原理，程序可仅将需运行的部分页或段装入内存便可开始执行。执行中，如果访问的页段已调入内存便可继续；否则，应利用OS提供的请求调页(段)功能将它们调入内存。若此时内存已满，应利用页(段)置换功能，将暂时不用的调出，腾出地方调入需要的页(段)。这样，便可使一个大的程序在较小的空间中运行;也可使内存中同时装入更多的进程并发执行。,115,4.5.1 虚拟存储器的引入,3.虚拟存储器定义具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺

45、牲不大。虚拟大小由内存容量和外存容量之和决定。,116,4.5.2 虚拟存储器的实现方法,虚拟存储器是建立在离散分配的存储管理方式基础上的。为什么？虚拟存储器 请求调入 页面转换若采用连续分配方式，一次性将全部数据调入，无需虚拟存储。实现的两种方式:请求分页 请求分段,117,1.分页请求系统,在分页系统的基础上，增加了请求调页功能和页面置换功能。只装入部分页面即可运行，可通过调页和页面置换功能，调入需要的页面，同时将暂不需要的换出。以页为单位置换需硬件：请求分页的页表机制 缺页中断机构地址变换机构需软件：实现请求调页的软件实现页面置换的软件,118,2.请求分段系统,在分段系统的基础上，增加

46、了请求调段及分段置换功能。只装入部分段即可运行，可通过调段和段置换功能，调入需要的段，同时将暂不需要的调出。以段为单位置换需硬件：请求分段的段表结构缺段中断机构地址变换机构需软件：请求调段和置换软件,119,4.5.3 虚拟存储器的特征,1.离散性：离散分配内存2.多次性：多次装入3.对换性：允许作业运行中进行换进换出4.虚拟性：从逻辑上扩充内存虚拟性以多次性和对换性为基础，而多次性和对换性又必须建立在离散分配的基础上。最本质的特征是离散性，在此基础上又形成了多次性和对换性，所表现出来的最重要的特征是-虚拟性.,120,4.5 虚拟存储器 小结,虚拟存储器的引入大作业小内存运行 局部性原理具有

47、请求调入功能和置换功能，能从逻辑上扩充内存虚拟存储器的实现方法分页请求系统请求分段系统虚拟存储器的特征离散性多次性对换性虚拟性,121,4.6 请求分页存储管理方式,建立在基本分页基础上，为了支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。每次调入和换出的基本单位是固定长度的页。,122,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持4.6.2 内存分配策略和分配算法4.6.3 调页策略,123,4.6.1 请求分页中的硬件支持,1.页表机制由于应用程序只是一部分调入内存即只有部分页位于内存中，须在页表中增加若干项，供程序（数据）换进换出时参考。,P:是否已调入内存A:

48、一段时间内使用的次数或多久未使用M:调入内存后是否修改过,124,4.6.1 请求分页中的硬件支持,2.缺页中断机构当访问的页不在内存中时便产生缺页中断，请求OS将其调入。缺页中断具有一般中断的入栈、转中断处理、出栈等过程，但又其特殊性：在指令执行期间产生和处理中断。发现访问的页不在内存即产生；通常是在等到指令执行完毕后。一条指令在执行期间，可能要产生多次中断。（如图）,125,涉及6次缺页中断的指令,页面,6,5,4,3,2,1,126,4.6.1 请求分页中的硬件支持,3.地址变换机构大致步骤：1)在地址变换时，首先检索快表，试图从中找到要访问的页。如找到，修改其访问位；对于“写”指令，还

49、要设置修改位的值。如未找到，则转3。2)利用页表项中的物理块号和页内地址，形成物理地址，结束。3)查找页表，找到页表项后，判断其状态位P，查看该页是否在内存中。如果在，则将该页写入快表（若快表已满，则应该先调出某个或某些页表项）。如果不在，则产生缺页中断，由OS从外存将该页调入内存。返回1。参图4-24,127,128,4.6.2 内存分配策略和分配算法,三个问题最小物理块数的确定物理块的分配策略物理块的分配算法,129,1.最小物理块数的确定,最小物理块数是指保证进程正常运行所需的最少物理块数。与计算机的硬件机构有关，取决于指令的格式、功能和寻址方式。单地址指令且采用直接寻址方式，最少物理块

50、数为2(指令页面 数据页面)单地址指令且采用间接寻址方式，3多字节指令，6（幻灯片125页）,130,2.物理块的分配策略,1)固定分配局部置换2)可变分配全局置换3)可变分配局部置换,131,2.物理块的分配策略,1)固定分配局部置换每个进程分配固定数目的物理块数，在整个运行期间都不改变如果缺页，则只能从该进程在内存的页面中选中一页，进行换出操作，然后再调入一页。特点：为每个进程分配多少页是合适的值难以确定。此外，在对换时会浪费比较多的时间。,132,2.物理块的分配策略,2)可变分配全局置换每个进程预先分配一定数目的物理块，同时OS也保持一个空闲物理块队列。（进程的块数运行时可能会有变化）