《吉林大学操作系统课件第六章存储管理1讲述》由会员分享，可在线阅读，更多相关《吉林大学操作系统课件第六章存储管理1讲述（64页珍藏版）》请在金锄头文库上搜索。
1、第六章 存储管理 n存储管理功能 n内存资源管理 n存储管理方式 n外存空间管理 n虚拟存储系统 6.1 存储管理功能 n存储分配和去配 n分配去配对象 n内存、外存(相同方法) n分配去配时刻 n进程创建、撤销、交换、长度变化(栈溢出, execl) n存储共享 n目的：节省内存、相互通讯 n内容：代码、数据 n存储保护 n防止地址越界 n防止操作越权 6.1 存储管理功能(Cont.) n存储扩充 n内存、外存结合，虚拟存储体系 n速度接近内存，容量相当外存 n地址映射 n逻辑地址=物理地址 n硬件支持 n基址寄存器(base)、限长寄存器(limit)、快表； n使用上述寄存器完成地址映
2、射过程； n不能正常完成地址映射时产生中断。 6.2 内存资源管理 n6.2.1 内存分区 n分区时刻 n静态分区：系统初始化时分； n动态分区：申请时分。 n分区大小 n等长分区：2i n异长分区：依程序、程序单位、对象大小。 n通常作法 n静态+等长（页式、段页式） n动态+异长（段式、界地址） 6.2.2 内存分配 n 静态等长分区的分配 n 字位映象图 n 空闲页面表 n 空闲页面链 n动态异长分区的分配 n最先适应 (First Fit) n最佳适应 (Best Fit) n最坏适应 (Worst Fit) 位示图（bit map） 1 0 0 1 . 1 0 第0 页 第2 页 第
3、1 页 第 k 页 第 n 页 分配：自头寻找第一个为0的位，改为1，返回页号 ； 去配：页号对应的位(bit)置为0。 用一个bit代表一页状态，0表空闲，1表占用。（ 多单元 ） 空闲页面表 首页号空页数 . . . . 1204 特点：可以分配连续页面。 DMA 要求 占用 占用 120页 121页 122页 123页 . . 空闲页面链 占用 占用 占用 Head: 优点：节省空间。 （不适合管理外存） 动态异长分区的分配 空闲区首址空闲区长度 . . . . 25001500 数据结构： Criteria: 尽量使空闲区域连续 。 初始时一个连续空闲区。 长度=0为表尾。 最先适应算
4、法（First Fit） 空闲区首址空闲区长度 12864 1024256 32 256 0 空闲区：首址递增排列； 申请：取第一个可满足区域； 优点：尽量使用低地址空间， 高区保持大空闲区域。 缺点：可能分割大空闲区。 Eg. 申请32将分割第 一个区域。 下次适应算法（Next Fit, NF) n思想：自上次分配空闲区域的下一个位置开始 选取第一个可满足的空闲区域 n实现：设置一个循环查找指针，开始时指向表 头，每次分配从该指针处开始查找（若查到表 尾则将指针置到表头）第一个遇到的可满足的 区域，分配后将指针调整为所分配区域的下一 个区域处。 n优点：可以减少查找空闲区域所花费的时间开
5、销，并使空闲区域分布更均匀。 n缺点：可能分割大空闲区 最佳适应算法（Best Fit） 空闲区：首址递增排列； 申请：取最小可满足区域； 优点：尽量使用小空闲区， 保持大空闲区。 缺点：可能形成碎片 (fragment)。 Eg. 申请30将留下长 度为2的空闲区 。 空闲区首址空闲区长度 12864 1024256 32 256 0 最坏适应算法（Worst Fit） 空闲区：首址递增排列； 申请：取最大可满足区域； 优点：防止形成碎片。 缺点：分割大空闲区域。 空闲区首址空闲区长度 12864 1024256 32 256 0 UNIX存储分配-FF struct map char *m
6、_size; char *m_addr; ; struct map coremapCMAPSIZ; struct map swapmapSMAPSIZ; define CMAPSIZ 100 define SMAPSIZ 100 malloc(mp,size) struct map, *mp; register int a; register struct map *bp; for(bp = mp; bp-m_size; bp+) if (bp-m_size = size) a=bp-m_addr; bp-m_addr =+ size; if (bp-m_size =- size) = 0)
7、do bp+; (bp-1)-m_addr = bp-m_addr; while(bp-1)-m_size = bp-m_size); return(a); return(0); mfree(mp,size,aa) struct map *map; register struct map bp; register int t,a; a = aa; for(bp=mp; bp-m_addrm_size !=0; bp+); if(bpmp if (a+size = bp-m_addr) /前后合并 (bp-1)-m_size =+ bp-m_size; while (bp-m_size) bp+
8、; (bp-1)-m_addr = bp-m_addr; (bp-1)-m_size = bp-m_size; else if (a+size = bp-m_addr bp-m_size =+ size; else if (size) do /无合并 t = bp-m_addr; bp-m_addr = a; a = t; /a与bp-m_addr交换 t = bp-m_size; bp-m_size = size; bp+; /size与bp-m_size交换 while (size = t); 6.2.3 碎片处理 紧凑：移动占用区域，使所有空闲区域连成一片（开销很大） 。 OS P1(2
9、48k) P2(250k) 8k 6k 4k 256k: 512k: 768k: 264k: 518k: P1 OS P2 256k: 504k: 754k: 18k 6.3 存储管理方式 n界地址管理方式（一维地址） n页式管理方式（一维地址） n段式管理方式（二维地址） n段页式管理方式（二维地址） 6.3.1 界地址管理方式 4.3.1.1 基本原理 1. 内存空间划分：动态异长； 2. 进程空间划分：一个进程一个区域，逻辑地址0l-1 3. 进程空间与内存空间对应关系（可以浮动）： 0: l- 1: . . b: l b+l-1: 进程空间 内存空间 6.3.1 界地址管理方式 4.
10、所需表目： (1)内存分配表-在PCB中； (2)空闲区域表：array of (addr,size)。 5. 所需寄存器： (1)基址寄存器b: 保存运行进程起始地址； (2)限长寄存器l: 保存运行进程长度。 6. 地址映射： 6.3.1 界地址管理方式 0: l- 1: . . b : l b+l- 1: lb 逻辑地址CP+ ab+a 步骤：(1) 由程序确定逻辑地址a； (2) a与l比较判断是否越界， 不满足：0al-1，越界； (3) a与b相加得到物理地址。 进程空间 内存空间 6.3.1 界地址管理方式 6.3.1.2 双对界 代码(I空间)：一对界 数据(D空间)：一对界
11、经典UNIX将进程空间分为I空间和D空间，前者对应指令 地址，后者对应数据地址。硬件能够识别逻辑地址所属空 间，并使用对应的地址映射寄存器。 b1l1 b2l2 6.3.1 界地址管理方式 6.3.1.3 交换技术(swapping) n交换又称换进换出，是指进程在内外存之间的动态调 度，主要为了缓解内存空间不足的有效方法。 n当外存储器中有可运行进程时，系统试图将其调入内存； n当内存空间紧张时，系统将内存中的某些进程，尤其是暂时 不可运行的进程移出到外存； 例：UNIX 交换进程sched (#0) 交换原则：外存 SRUN 状态进程内存 (1)内存有空间，直接移入； (2)内存空间不够，
12、移出SWAIT, SSTOP状态进程； (3)如果还不够，移出SSLEEP, SRUN状态进程， 条件：在外时间3秒；在内时间2秒 6.3.1 界地址管理方式 n重定位：被换出进程再次运行之前必须重新装入内 存，而再次进入内存的位置与换出前的位置一般不 同，这就要求程序编址与内存存放位置无关，这种 程序称为可重定位程序。 n由0起始编址的程序都满足重定位要求，这样的程 序也称为浮动程序。 6.1.3.4覆盖技术: 将较大程序装入较小进程空间的技术. n只将全局代码和数据静态装入内存, 其它部分动态 装入. n后装入的成分重复使用先装入成分所使用的存储区, 即覆盖先装入的成分. 覆盖技术 符号表
13、 公共例程 覆盖驱动程序 覆盖区50kb Pass1 30kb Pass2 50kb Pass3 40kb Pass4 25kb 6.3.2 分页式存储管理 (paging) 6.3.2.1 基本原理 1. 内存空间划分：静态等长，2i, 称为一个页框（frame) 。 . . 第0页 第1页 第k页 第2n-i-1页 2i 02i: 12i: k2i: (2n-i-1)2i: 物理地址=页架首址+页内地址 =页架号 2i +页内地址 = 页架号 页内地址 i位n-i位 6.3.2 分页式存储管理 2. 进程空间划分：静态等长，2i, 称为一个页面。 . . 第0页 第1页 第k页 第l-1页
14、 2i 02i: 12i: k2i: (l-1)2i: 逻辑地址=逻辑页首址+页内地址 =逻辑页号 2i +页内地址 = 逻辑页号 页内地址 i位 3. 进程空间与内存空间对应关系 . 第0页 第1页 第2页 第3页 第16页 第22页 第32页 第15页 . . . 进程空间 内存空间 4. 所需表目： (1)页表，每个进程一个 物理页号逻辑页号 : 15 22 16 32 0 1 2 3 5. 所需寄存器 (2)总页表：系统一个 (1) 页表首址寄存器： b l (2) 页表长度寄存器： 系统一个 系统一个 (3) 快表(TLB)：系统一组 ： 逻辑页号页架号 . . . . f p 逻辑
15、地址(p,d)物理地址(f,d) (1) 由程序确定逻辑地址(p,d)； (2) 由p查快表得页架号f； 如查不到： (3) 由p与l比较，判别是否越界： 不满足：0pl-1，越界； (4) 由p和b查页表得f; (5) parbegin (p,f)快表，如满淘汰一个; f与d合并得物理地址 parend (3) f与d合并得物理地址 6. 地址映射 : (p,d)(f,d) . 逻辑页号页架号 . . . . f p lb b l . . PCB 页架号逻辑页号 . f . p . f d p d 物理地址 逻辑地址 b: . 如查不到 . 逻辑页号页架号 . . . . f p lb b
16、l . . PCB 页架号逻辑页号 . f . p . f d p d +cp p f 物理地址 逻辑地址 b: . 有效访问时间 n(Effective Access Time) nEAT=快表命中率(快表访问时间+内存访 问时间)+快表不中率(快表访问时间+2 内存访问时间) ns n 98%(20+100)+2% (20+200)ns =122ns 6.3.2.2 多级页表 n提出背景 n内存空间成倍增长, 进程虚拟空间成倍增加 n单级页表需要很大连续内存空间 n例如 n32位进程地址空间，页长占12位（4k），页号20位，页 表最多可达220个入口！ n多线程设计导致进程虚拟空间不连续(空洞hole) n栈的预留空间(没有页架相对应) n页表所占内存空间浪费
