计算机操作系统课件(第四版)第四五章

第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配存储管理方式4.4对换4.5分页存储管理方式4.5分段存储管理方式14.1存储器的层次结构4.1.1多级存储器结构4.1.2主存储器与寄存器4.1.3高速缓存和磁盘缓存24.1.1多级存储器结构存储层次至少应有三级：CPU寄存器、主存、辅存寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存图4-1存储层次示意图价格高低速度快慢容量小大34.1.2主存储器与寄存器1、主存储器主存也称可执行存储器。CPU可从其中取指令和数据，数据能从主存读取并装入到寄存器中，或从寄存器存入到主存。•2、寄存器寄存器访问速度最快。其长度以字为单位。44.1.3高速缓存和磁盘缓存1、高速缓存（cache）容量大于寄存器，访问速度快于内存。Cache分类：一级cache紧靠内存，速度最高，容量最小。二级cache容量稍大，速度也稍低。•2、磁盘缓存磁盘缓存本身并不是一种实际存储介质。实质：利用主存中的存储空间，来暂存从磁盘中读出或写入的信息54.2程序的装入和链接从源程序到程序执行地址空间的概念重定位的概念程序的装入程序的链接61、从源程序到程序执行编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子272、地址空间的概念物理（绝对）地址——程序执行每个内存单元的固定顺序地址（编号）。内存：由字或字节组成的一维线性地址空间逻辑（相对）地址——装入（汇编编译）被链接装配（或汇编、编译）后的目标模块所限定的地址的集合；相对于某个基准量（通常为：0）的编址。物理地址内存000000000100002...0100002200主子1子2主子1子2逻辑地址装入模块0000...1200主子1子2相对地址源程序/单个目标模块0005000003000004008重定位概念：在装入时对目标程序中指令和数据的修改过程称为重定位。即，逻辑地址变换为物理地址的过程。重定位的类型静态重定位：地址变换是在装入时一次完成的，以后不再改变。动态重定位：地址变换是在程序指令执行时进行的。作业地址空间内存空间装入365LOAD1,25005000250000001000365LOAD1,2500150001250010000110003、重定位的概念365LOAD1,12500150001250010000110009BR：重定位寄存器VR:变址寄存器00104、程序的链接链接：把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体——装入模块的过程。具体工作：对相对地址的修改；变换外部调用符号。链接方式分类：静态链接装入时动态链接运行时动态链接模块ACallB;Return;0L-1模块BCallC;Return;0M-1模块C……;Return;0N-1链接模块AJSR”L”;Return;0L-1模块BJSR”L+M”;Return;LL+M-1模块C……;Return;L+ML+M+N-1装入模块115、程序的装入含义：就是把链接好的装入模块装入“内存”。装入方式分类：绝对装入可重定位装入（静态重定位）动态运行时装入（动态重定位）提示：通常链接、装入程序是一体的。124.3连续分配存储管理方式为用户程序分配一个连续的内存空间。曾被广泛应用，且现在仍被采用。单一连续分配固定分区分配动态分区分配基于顺序搜索的动态分区分配算法基于索引搜索的动态分区分配算法动态可重定位分区分配134.3.1单一连续分配基本思想把内存分为系统区和用户区，系统区供OS使用，通常放在低址部分；系统区以外的全部内存空间是用户区。特点只能用于单用户、单任务的OS中。软件简单，硬件要求低（无需存储保护）实例CP/M，MS-DOS，RT-11DOS内存分区CP/M内存分配系统参数区BIOSCCPBDOS系统区系统区144.3.2固定分区分配最简单的一种可运行多道程序的存储管理方式。1、划分分区的方法分区大小相等：缺乏灵活性，用于控制多个相同对象的系统分区大小不等：多个较小分区、适量中等分区、少量大分区2、内存分配管理将分区按大小排队建立分区使用表——起址、大小、状态程序装入时，由内存分配程序检索分区使用表，找到符合要求的分区，并进行标记。15分区号大小起址状态18K512K未使用232K520K未使用332K552K未使用4128K584K未使用5512K712K未使用…………系统区分区1分区4分区5分区2分区3系统区分区1分区4分区5分区2分区3作业1作业2作业3已使用已使用已使用作业1进入，大小30K作业2进入，大小500K作业3进入，大小8K164.3.3、动态分区分配根据进程的实际需要，动态的分配内存空间1、内存管理方式（数据结构）：空闲分区表——序号、起址、大小等项空闲分区链——双向链表前向指针+2N0后向指针+2N0N个字节可用空闲链表结构172、动态分区分配算法（4.3.4—4.3.5）4.3.4基于顺序搜索的动态分区分配算法首次适应算法：空闲分区按起址递增次序排列，从头开始直至找到第一个满足要求的空闲分区。特点：内存低端会留下小的空闲区，高端有大的空闲区；循环首次应算法：从上次分配的位置之后开始查找。特点：使内存的空闲分区均匀，但缺乏大的空闲分区；18最佳适应算法：空闲分区按大小递增的次序排列，从头开始找到第一个满足要求的空闲分区。缺点：会留下大量小碎片。最坏适应算法：空闲分区按大小递减的次序排列，最前面的最大的空闲分区就是找到的分区。优点：分配后剩下的可用空间比较大缺点：一段时间后就不能满足对于较大空闲区的分配要求。19•4.3.5基于索引搜索的动态分区分配算法1、快速适应算法：空闲分区按容量大小进行分类。对于每一类具有相同容量的所有空闲空间分区，单独设立一个空闲分区链表。在内存中设立一张管理索引表，每个表项对应一种空闲分区类型。优点：查找效率高。保留大分区也不会产生碎片缺点：分区归还主存时算法复杂。202、伙伴系统：分区（已分配和空闲）大小均为2的k次幂（1=k=m）,2m为可分配内存大小。对不连续的空闲分区，按分区大小进行分类。对具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，即会存在k个空闲分区链表。分配时，设需分配长度为n，找2i分区链的分区，使2i-1n2i若无，找2i+1且把它均分两块，称为伙伴。一个加入2i分区链，一个分配；.......回收时，若已存在2i空闲分区，则将其于伙伴合并为2i+1分区，.....特点：性能取决于查找空闲分区的位置和分割、合并的时间。时间上不及快速适应算法，但空闲分区的使用率高213、哈希算法：利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张一空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表。分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，再分配223、分区分配操作（分配算法流程）分配内存从空闲分区链（表）中找到所需大小的分区。判断条件：M.Size-U.Size≦Size剩余部分挂接到空闲分区链（表）上。回收内存回收区与插入点的前一个空闲分区相邻接；回收区与插入点的后一个空闲分区相邻接；回收区与插入点的前后两个空闲分区相邻接；回收区不与任何一个空闲分区相邻接；优缺点管理复杂，总会有闲置的小分区——“碎片”。请求的分区大小表中空闲分区大小下限值23查找空闲分区链表第一项检索完否？m.sizeu.size?m.size-u.size≦size?划出u.size大小的分区修改有关的数据结构返回将该分区从链表中移出继续检索下一个表项YYYNNN内存分配流程24……F1(空闲区)回收区…………回收区F2(空闲区)…………F1(空闲区)回收区F2(空闲区)……内存回收时的情况情况1：情况2：情况3：……（占用区）回收区（占用区）……情况4：254.3.6、可重定位分区分配1、动态重定位的引入随着系统接收的作业的增加，内存中连续的大块分区不复存在，产生了大量的“碎片”。新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。通过“拼接”或“紧凑”来实现程序的浮动（动态重定位）。26OS区Job2Job4Job3Job1Job5Job6Job7“零头”碎片OS区Job2Job4Job3Job1Job5Job6Job7OS区Job2Job4Job3Job1Job5Job6Job7“零头”碎片272、动态重定位的实现必须由硬件地址变换机构支持实现——重定位R重定位寄存器：存放程序在内存中的起始地址。处理机一侧存储器一侧作业J内存365LOAD1,2500500025001000365LOAD1,2500150001250010000110002500相对地址10000重定位寄存器000028优缺点分析优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。缺点：需要动态重定位“硬件”机构支持，增加了系统成本，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销。3、可重定位分区分配算法与动态分区分配算法基本相同，但增加了紧凑功能动态重定位分区分配算法流程查找空闲分区链表第一项找到可用分区？按动态分区方式进行分配修改有关的数据结构返回分区号及首批进行紧凑形成连续空闲区YYNN请求分配u.size分区空闲分区和=u.size？修改有关的数据结构无法分配返回291、对换的引入对换的定义P135目的：用于解决内存不足的问题；对换的类型：整体对换：以进程为单位的对换部分对换：以“页”或“段”为单位的对换2、对换空间的管理外存的划分：文件区、对换区管理方式：空闲分区表、空闲分区链分配算法：首次适应法、循环首次适应法、最佳适应法4.4、对换（Swapping）303、进程的换出与换入进程的换出选择处于阻塞状态且优先级最低的进程将该进程的程序和数据传送道磁盘的对换区上回收内存空间，修改该进程的PCB进程的换入定时查看进程状态将处于就绪态的换出时间最久的进程换入内存31例如：在分时系统中，一台主机，多台终端，每个用户得到的内存有限，因此可利用外存作为补充。RUNReadyAReadyB内存头尾就绪队列时间片到（换出）调度换入324.5基本分页存储管理方式连续分配方式的不足，促使人们产生了离散分配的管理思想。从而引入了“分页”分配管理的管理方式。分为：基本分页（纯分页）和支持虚存管理的请求分页管理。页面与页表地址变换机构两级和多级页表基本分页的特点334.5.1、页面与页表1、页面页面和物理块（页框/架）：顺序编号，页内碎片页面大小：2nBytes一般在：512B~8/32K2、地址结构逻辑地址物理地址页内地址d物理块号P位移量W页号P例如：位移量（页内地址）W页号P3112110每页大小为4KB，地址空间最多允许有1M页01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业02K-1第2页（页长2K）02K-14号页架（页长2K）34页号P和页内地址d的计算公式P＝INT[A/L]INT：整除函数d＝[A]MODLMOD：取余函数（A：逻辑地址空间中的地址，L：页面大小）例如：某系统的页面大小为1KB，地址A=2170B，则求得P=2，d=1223、页表——页面映像表数据结构：页号、块号、存取控制项页表作用：实现从页号到物理块号的地址映射。01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业块号页号1051169453327120页表