第3章存储管理

第3章存储管理分区式存储管理分页式存储管理分段存储管理段页式存储管理引言内存管理的需求内存管理使用的技术分区式管理：固定式、可变式分区、多重分区页式管理、段式管理段页式管理OS的存储管理机构必须解决以下问题内存分配存储保护地址变换存储共享存储扩充同时进行多个任务编辑文档运行程序网上浏览CD音乐欣赏为多个程序安排内存PCB1PCB2PCB3程序1程序2程序3数据程序进程控制块PCB采用内存分配与管理技术：实存管理技术：分区式、分页式、分段式、段页式虚存管理技术：请求分页式、请求分段式、请求段页式OS

分配内存程序1程序2程序33.1分区式存储管理地址重定位静态重定位动态重定位固定式分区可变式分区多重分区覆盖与交换可变分区分配和释放算法

3.1地址重定位内存储器一般分为：系统区和用户区程序的名字空间、地址空间及存储空间符号源程序目标代码可执行代码汇编编译连接地址重定位名字空间地址空间存储空间:x=x+1::R=XR=R+1X=R:0:K

100:100+K:R=XR=R+1X=R:1.静态重定位示意图::LOAD1,300:5678:

01003004001000110013001400::LOAD1,1300:5678:

某程序的地址空间内存2.动态重定位示意图1000110013001400

LOAD1,300

5678

内存物理地址空间0100300400

LOAD1,300

5678某程序的逻辑地址空间1000+3.1.2固定分区和可变分区区号大小起始地址标志123416K32K64K124K20K36K68K132K已分配已分配已分配未分配操作系统作业A作业C作业B020K36K68K132K第1分区第2分区第3分区第4分区(未分配)(b)内存分配图(a)分区说明表1.固定分区分配2.可变分区说明表序号P大小起址状态18K20K已分配232K28K已分配3——空表目4120K92K已分配5——空表目…………已分配分区说明

序号F大小起址状态132K60K空闲2300K212K空闲3——空表目4——空表目5——空表目…………空闲分区说明表

可变分区示例3.可变分区分配和释放算法分配算法一般有：①最佳适应（BestFit）算法，它从全部空闲区中找出能满足作业需求的容量最小的空闲区分配之，此法的着眼点是使碎片尽量小。②最先适应（FirstFit）算法，它按序查找，把最先找到的满足需求的空闲区分配之，此法的目的在于尽量减少查找时间。③*最坏适应（WorstFit）算法,此法的目的在于使剩下的空区最大，减少空区碎片机会。④*下次适应算法（NextFit），此法将空闲区链成环形链，每次分配从上次分配的位置开始查找合适的空闲区。

可变分区的分配算法F=F+1置空闲区号F=1=Loc

F的起始地址置置F的状态=空表目置置P的大小=Xk置P的始址=Loc置P的=已分配本次无法分配=申请分配一个xk大小的分区F已超出最大项号？F的状态=空表目？F的大小

Xk?在已分配表中找一个状态=空表目的序号P返回序号P否是是否否否大于等于F的大小

Xk=新空闲块大小Loc+Xk=新起始地址回收示意图空闲区F1程序区回收区R空闲区F1

空闲区F2程序区回收区R

空闲区F2程序程序回收区R

程序区程序区回收区R

空闲区F2程序区程序区回收区R可变分区的回收算法=置新空闲分区的大小=Size始址=Loc状态=空闲在空闲分区表中置F2为空闲表目分区R与F1邻接？分区R与F1邻接？在空闲分区表中找一个空闲表目分区R与F2邻接？Size

Size+F2的大小已分配区说明表中置R的状态=空表目Size

分区R的大小Loc

分区的起始地址否是是是否否请求回收分区R置空闲分区F2的大小=Size+F1的大小置空闲分区F2的大小=Size始址=Loc返回F13.1.3覆盖与交换技术1.覆盖技术所谓覆盖，就是一个作业的若干程序段或几个作业的某些部分共享某一段存储空间覆盖技术举例A20KB50KF30KC30KD20KE40KRAMA20K覆盖区050K覆盖区140KBCFDE(a)作业模块的调用结构(b)存储分配及覆盖结构2.交换技术所谓交换，就是允许把一个作业装入内存之后仍能把它交换出内存或再交换入内存。3.2分页式存储管理实存管理分页原理页表地址变换机构虚存管理页表的扩充缺页中断处理页面淘汰算法快表页面共享分页原理1、等分内存2、建立页表3、动态地址转换4、缺页处理1、等分内存（页面和物理块）将一个进程的逻辑地址空间分成若干个大小相等的区域，称为页面或页。从0开始编号。内存空间也分成与页相同大小的若干个存储块，或称为物理块或页框（frame）,同样为它们进行编号(如图4－11左、右两边所示)。以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为“页内碎片”。在分页存储管理方式中的地址结构如下：位移量W又称为页内地址问题：（1）每页大小为？（2）地址空间中最多有？页二、页表

在分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，但系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立一张页面映射表，简称页表。

页表的作用：实现从页号到物理块号的映射。表项中常设有存储控制字段一位：允许读/写只读两位：允许读/写只读只执行页表的作用

页表、存储分块表及其关系0000100000000000

页内地址

页号相对页号P页内地值D分页原理0000010000000000

页内地址

页号相对页号P页内地值D页表项页表项区域PCB区域OS用户区页号物理块号1025171220某作业页表有效（虚地址）操作系统物理块号特征页号作业2页表4528物理地址物理块号页表起始地址页表长度页表始址寄存器页号页内相对位移内存8644外存LOAD1,25004522150地址变换过程请求分页页表页号特征内存块号外存块号修改位访问位0 00 11 01 1淘汰优先级01此页不在内存此页在内存缺页中断处理页面淘汰算法先进先出(FIFO)最近最久未使用淘汰算法(LRU)最近不频繁使用淘汰算法(LFU)最优算法(OPT)以上几种淘汰算法中，FIFO算法最简单，但效率不高，有异常现象。LRU的近似算法和LFU是较为实用的算法，效果较好，实现也不难。OPT算法是一种最佳算法，但并不实用，因为要跟踪各页面方可预测未来。而这种预测往往是很困难的。FIFO异常现象FIFO异常现象FIFO异常现象快表 序号 相对页号 物理块号 访问过 特征位 0

1

2

3

m-1

快表地址映象快表的地址映象操作页面共享共享的例程页面共享的数据页面...共享的历程页面作业1页表作业2页表作业1页表作业2页表公共页表3.3段式管理段式地址结构段号s段内位移w3.3.1段式系统的特点3.3.2段式地址变换段号段内地址sw长度基址段表第s段b+wlb程序地址段式地址变换的步骤：1）取出程序地址(S,W)。2）用S检索段表。3）如W<0或W>1则内存越界。4)(b+w)即为所需内存地址3.3.3扩充段表功能段页式管理作业地址空间和地址结构主程序段子程序段数据段04K8K12K