《操作系统课件第4章》由会员分享，可在线阅读，更多相关《操作系统课件第4章（48页珍藏版）》请在金锄头文库上搜索。
1、第四章 存储器管理,4.1 存 储 器 的 层 次 结 构,多级存储器结构,存储层次：CPU寄存器，主存，辅存。 高档计算机中：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质。,计算机系统存储层次示意,在存储层次中越往上，存储 介质的访问速度越快，价格也 越高，相对存储容量也越小。,CPU寄存器,主存,辅存,3主存储器,主存储器(内存)保存进程运行时的程序和数据。,寄存器访问速度最快,协调CPU工作，价格昂贵，容量很小。,1. 寄存器,2高速缓存,容量大于寄存器,小于主存。 访问速度比主存快。将经常访问的信息存放在高速缓存中。,4磁盘缓存,利用主存中的存储空间，暂时存放从磁盘中
2、读出(或写入)的信息。,台式PC机内存插槽和内存条,4.2 程 序 的 装 入 和 链 接,编译，源代码目标模块。 链接，目标模块，库函数装入模块。 装入，装入模块内存。,编译程序 产生的目 标模块,库,内存,装入模块,程序的装入,1. 绝对装入方式,按照绝对地址装入。,只适用于单道程序环境。,2可重定位装入方式,首址可以平移。 装入时地址修改。 整体搬移连续存放。,3动态运行时装入方式,装入内存后的所有地址都是相对地址。地址修改推迟到程序执行时进行 ，动态重定位。,装入时地址不变，运行时地址修改。,程序的链接,1. 静态链接方式（在外存形成装入模块）,2. 装入时动态链接（进内存后形成装入模
3、块）,装入时动态链接方式有以下优点： 便于修改和更新。 (2) 便于实现对目标模块的共享。,高档操作系统流行方式 Windows Linux等通用技术 OS下存有大量的DLL动态连接库文件。,3. 运行时动态链接,执行过程中，当一个被调用模块尚未装入内存时，由OS找到该模块并将之装入内存， 把它链接到调用者模块上。当前不用的目标模块，都不会进内存。加快程序的装入过程，节省大量的内存空间。,高档操作系统流行方式 Windows 、Linux、Solars、Mach等OS通用的技术（使用DLL文件）,4.3 连 续 分 配 方 式,单一连续分配,只能用于单用户、单任务操作系统中。内存分为系统区和用
4、户区两部分。,每次一个作业，上一个完成退出，下一个才能进入,利用率极低,固定分区分配,用户空间划分为若干个固定大小的区域，在每个分区中装入一 道作业，允许几道作业并发运行。,简单、可靠，但产生分区“内零头”，内存利用效低。,动态分区分配,根据进程的实际需要，动态地为之分配内存空间。,空闲分区表 记录每个空闲分区的情况。,(2) 空闲分区链,将所有的空闲分区链接成一个双向链。,当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。,Job1,Job2,Job3,Job4,Job5,Job6,Job6,分区分配算法,1) 首次适应算法(first fit),空闲分区链以地址
5、递增的次序链接。从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给作业，余下的空闲分区仍留在空闲链中。 该算法的优缺点：为大作业分配大的内存空间创造了条件。 低址部分不断被划分，会留下许多难以利用的、很小的空闲 分区。,新作业装入内存时，按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。常用的分配算法：,2) 循环首次适应算法(next fit),将所有的空闲分区构成一个循环链表。采用循环查找 方式，设置一个起始查寻指针，用于指示下一次起始查 寻的空闲分区。 该算法的优缺点：能使内存中的空闲分区分布得更均 匀
6、，从而减少了查找空闲分区时的开销，但这样会缺乏 大的空闲分区。,为进程分配内存时，不再是每次都从链首开始查找，而是从上次找到空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。,3) 最佳适应算法(best fit),将所有的空闲分区按容量以从小到大的顺序形成空闲分区链。 该算法的优缺点：为大作业分配大的内存空间创造了条 件。每次分配后所切割下来的剩余部分总是最小的，这样， 在存储器中会留下许多难以利用的小空闲区。,把能满足要求、又是最小的空闲分区分配给作业。,4) 最坏适应算法(worst fit) 该算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其
7、优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，但查找效率很高。 所有的空闲分区按容量从大到小的顺序形成空闲分区链，查找时只要看第一个分区能否满足作业要求。该算法的缺点是它会使存储器中缺乏大的空闲分区。 最坏适应算法与首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。,5) 快速适应算法(quick fit),该算法又称为分类搜索法，是将空闲分区根据其容量大 小进行分类，对于每一类具有相同容量的所有空闲分区， 单独设立一个空闲分区链表，这样，系统中存在多个空闲 分区链表，同时在内存中设立一张管理索引表。,该算法的优点是查找效率高，仅需要根据进程的长度， 找到能容纳它的最
8、小空闲区链表即可；另外不会对任何分 区产生分割，满足对大空间的需求，不会产生内存碎片。 缺点是在分区归还主存时算法复杂，系统开销较大。,可重定位分区分配,经过紧凑后，用户程序在 内存中的位置发生了变化， 所以必须对移动了的程序 或数据进行重定位。,紧凑技术,也称为“拼凑”技术，解决可变分区中产生的“外零头”。移动某些已分配分区，使“外零头”合并为一个大的连续空闲区。,以时间和技术换内存空间。,可以装入作业7,暂不能装入J7,重定位寄存器，存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。,动态重定位的实现原理,365,LOAD 1
9、,2500,5000,2500,1000,365,LOAD 1,2500,15000,12500,10000 11000,10000,重定位 寄存器,处理机一侧 存储器一侧,作业J,内存,重定位是一种运算寻址，需硬件支持,4.4 基 本 分 页 存 储 管 理 方 式,将一个进程的逻辑地址空间分成若干个大小相等的 片，称为页，并为各页编号。 把内存空间分成与页相同大小的若干个存储块，称为块，同样予以编号。,页的大小通常为512 B8 KB。,若干个页分别装入可以不相邻接的物理块中。最后一页经常装不满一块形成“页内碎片”。,页式最先实现了作业空间的离散分配！,地址结构,页号 P 位移量 W,31
10、,12 11,0,前一部分为页号P，后一部分为位移量W(或称为页内地址)。例：地址长度为32位，011位为页内地址，1231位为页号。,若逻辑地址为A，页的大小为L，则页号P和页内地址d可按下式求得：,页号：,页面地址：,作业分页，内存分块 页块等大，对应存放 建立页表，查表访问,页表,页表放在内存中，它的作用是实现从页号到物理块号的地址映射。,页表的作用,分页系统的地址变换机构,地址变换机构,页表,物理地址,页表始址,页表长度,页表寄存器,5,2018,3,2018,逻辑地址,越界中断,+,5,4.5 基 本 分 段 存 储 管 理 方 式,作业的地址空间划分为若干个段，每个段都有自己的名字
11、。通常用一个段号来代替段名，每个段都是从0开始编址的。 地址结构,段表,分段地址变换由段表实现，在作业被调入时，为其建立一张段表。,利用段表实现 地址映射,每个段在表中占有一 个表项，其中记录了 该段在内存中的起始 地址(又称为“基址”) 和段的长度,程序按段存放 运行查段表进行,地址变换机构,分段系统的地址变换过程,段号S 段表长度TL 访问越界。否则，从段表 项中读出该段在内存的起始地址。,段内地址d 段长SL越界中断。否则，基址 + 段内地址d = 内存物理地址。,页号,位移量,页表,不变,(a)分页,页号 块号,段号,段内地址,段表,(a)分段,段号 段长 基址,分页和分段的主要区别,
12、分 页,分 段,信息的物理单位,信息的逻辑单位,出于系统管理的需要,出于用户的需要,大小固定由系统确定,长度不固定由编译确定,作业地址空间一维,作业地址空间二维,页内碎片,外部碎片,不易共享,易共享,页表较长，查找费时,段表较短，查找速度快,段页式存储管理方式,将分页管理和分段管理的优点集中起来。 即对作业的地址空间分段，段内再分页。,该作业有三个段，页面大小为4KB。,段页式地址结构,由段号S、段内页号P和页内地址W三部分组成。,通常，分段由程序员完成，分页由系统自动完成。,利用段表和页表实现地址映射,地址变换过程,段表寄存器,段 表 始 址,段表长度TL,段号S,段页式系统中获得一条数据或
13、指令，需访问内存几次？ 三次,4.6 虚 拟 存 储 器 的 基 本 概 念,常规存储器管理方式的特征,1. 一次性,2.驻留性,资源实体性和有限性,局部性原理,在一较短的时间内，程序的执行仅局限于某个部分；相应地，它访问的存储空间也局限于某个区域。,(1)时间局部性: 一个数据结构被访问，不久可能再次被访问。 典型原因： 程序中存在大量的循环操作。,(2)空间局部性:一段时间访问的地址可能集中在一定范围 。 典型原因：程序顺序执行,局部性原理是虚拟内存得以实现的本质,虚拟存储器,实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动将它们从
14、外存调入内存。,虚拟存储器定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。它把内存与外存有机结合起来使用，构成容量很大的“内存”。,虚拟存储器的特征,1. 多次性,2. 对换性,3. 虚拟性,4.7 请求分页存储管理方式,请求分页中的硬件支持,页表机制,主要是缺页中断机构,地址变换机构,最小物理块数的确定,能保证进程正常运行所需的最小物理块数。,页面调入过程 当程序要访问的页面未在内存时，向CPU发出一缺页中断，中断处理程序保留CPU环境，查找页表，得到该页在外存的物理块。 如果此时内存能容纳新页，则启动磁盘I/O将所缺页调入内存，然后修改页表。 如果内存已满，
15、选一页换出；再把所缺的页调入内存， 并修改页表。,4.8 页面置换算法,最佳置换算法 选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。,比较理想，但不易实现,1.换页的原则 2.淘汰哪些页面 3.调入调出的速度,先进先出FIFO算法,淘汰留在内存时间最长的页面，即先进入内存的页面先被淘汰。实现简单。设分配给一个作业的实页数为m，则只需建立一个由m个元素组成的队列表和一个替换指针即可。,例：系统为某进程分配了三个物理块，页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，置换算法采用FIFO，计算缺页中断次数及缺页率。,F=12 f=12/20=60%,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,最近最久未使用LRU置换算法 选择最近最久未使用的页面予以淘汰。记录每个页面自上次被访问以来所经历的时间t，选最大的页面淘汰。,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,F=9 f=9/20=45%,4.9 请求分段存储管理方式（小型机用）,段表机制,缺段中断机构,地址变换机构,
