《操作系统第六章存储管理ppt课件》由会员分享，可在线阅读，更多相关《操作系统第六章存储管理ppt课件（62页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 存储管理存储管理n存储管理功能存储管理功能n内存资源管理内存资源管理n存储管理方式存储管理方式n外存空间管理外存空间管理n虚拟存储系统虚拟存储系统 6.1 存储管理功能存储管理功能n存储分配和去配存储分配和去配n分配去配对象分配去配对象n内存、外存内存、外存(一样方法一样方法)n分配去配时辰分配去配时辰n进程创建、撤销、交换、长度变化进程创建、撤销、交换、长度变化(栈溢出栈溢出, execl)n存储共享存储共享n目的：节省内存、相互通讯目的：节省内存、相互通讯n内容：代码、数据内容：代码、数据n存储维护存储维护n防止地址越界防止地址越界n防止操作越权防止操作越权6.1 存储管理功
2、能存储管理功能(Cont.)n存储扩展存储扩展n内存、外存结合，虚拟存储体系内存、外存结合，虚拟存储体系n速度接近内存，容量相当外存速度接近内存，容量相当外存n地址映射地址映射n逻辑地址逻辑地址=物理地址物理地址n硬件支持硬件支持n基址存放器基址存放器(base)、限长存放器、限长存放器(limit)、快表；快表；n运用上述存放器完成地址映射过程；运用上述存放器完成地址映射过程；n不能正常完成地址映射时产生中断。不能正常完成地址映射时产生中断。6.2 内存资源管理内存资源管理n6.2.1 内存分区内存分区n分区时辰分区时辰n静态分区：系统初始化时分；静态分区：系统初始化时分；n动态分区：恳求时
3、分。动态分区：恳求时分。n分区大小分区大小n等长分区：等长分区：2in异长分区：依程序、程序单位、对象大异长分区：依程序、程序单位、对象大小。小。n通常作法通常作法n静态静态+等长页式、段页式等长页式、段页式n动态动态+异长段式、界地址异长段式、界地址6.2.2 内存分配内存分配n 静态等长分区的分配静态等长分区的分配n 字位映象图字位映象图n 空闲页面表空闲页面表n 空闲页面链空闲页面链n动态异长分区的分配动态异长分区的分配n最先顺应最先顺应 (First Fit)n最正确顺应最正确顺应 (Best Fit)n最坏顺应最坏顺应 (Worst Fit)位示图位示图bit map1 0 0 1
4、. 1 0第第0 页第第2 页第第1 页第第 k 页第第 n 页.分配：自头寻觅第一个为分配：自头寻觅第一个为0的位，改为的位，改为1，前往页号；，前往页号；去配：页号对应的位去配：页号对应的位(bit)置为置为0。用一个用一个bit代表一页形状，代表一页形状，0表空闲，表空闲，1表占用。表占用。 多单元多单元空闲页面表空闲页面表首页号首页号空页数空页数.1204特点：可以分配延续页面。特点：可以分配延续页面。 DMA 要求要求占用占用占用占用120页页121页页122页页123页页 . .空闲页面链空闲页面链占用占用占用占用占用占用Head:优点：节省空间。优点：节省空间。 不适宜管理外存不
5、适宜管理外存动态异长分区的分配动态异长分区的分配空闲区首址空闲区首址空闲区长度空闲区长度.25001500数据构造：数据构造：Criteria: 尽量使空闲区域延续。尽量使空闲区域延续。初始时一个延续空闲区。初始时一个延续空闲区。长度长度=0为表尾。为表尾。最先顺应算法最先顺应算法First Fit空闲区首址空闲区首址空闲区长度空闲区长度128641024256322560.空闲区：首址递增陈列；空闲区：首址递增陈列；恳求：取第一个可满足区域；恳求：取第一个可满足区域；优点：尽量运用低地址空间，优点：尽量运用低地址空间， 高区坚持大空闲区域。高区坚持大空闲区域。缺陷：能够分割大空闲区。缺陷：能
6、够分割大空闲区。 Eg. 恳求恳求32将分割第将分割第 一个区域。一个区域。最正确顺应算法最正确顺应算法Best Fit空闲区：首址递增陈列；空闲区：首址递增陈列；恳求：取最小可满足区域；恳求：取最小可满足区域；优点：尽量运用小空闲区，优点：尽量运用小空闲区， 坚持大空闲区。坚持大空闲区。缺陷：能够构成碎片缺陷：能够构成碎片 (fragment)。 Eg. 恳求恳求30将留下长将留下长 度为度为2的空闲区。的空闲区。 空闲区首址空闲区首址空闲区长度空闲区长度128641024256322560.最坏顺应算法最坏顺应算法Worst Fit空闲区：首址递增陈列；空闲区：首址递增陈列；恳求：取最大可
7、满足区域；恳求：取最大可满足区域；优点：防止构成碎片。优点：防止构成碎片。缺陷：分割大空闲区域。缺陷：分割大空闲区域。空闲区首址空闲区首址空闲区长度空闲区长度128641024256322560.UNIX存储分配存储分配-FFstruct map char *m_size; char *m_addr;struct map coremapCMAPSIZ;struct map swapmapSMAPSIZ;define CMAPSIZ 100define SMAPSIZ 100malloc(mp,size)struct map, *mp; register int a; register stru
8、ct 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) 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(
9、bp=mp; bp-m_addrm_size !=0; bp+); if(bpmp & (bp-1)-m_addr+(bp-1)-m_size = a) /与前合并与前合并 (bp-1)-m_size =+ size; if (a+size = bp-m_addr) /前后合并前后合并 (bp-1)-m_size =+ bp-m_size; while (bp-m_size) bp+; (bp-1)-m_addr = bp-m_addr; (bp-1)-m_size = bp-m_size; else if (a+size = bp-m_addr & bp-m_size) /与后合与后合并并
10、bp-m_addr =- size; 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(248k) P2(250k) 8k 6k 4k256k:512
11、k:768k:264k:518k: P1 OS P2256k:504k:754k:18k6.3 存储管理方式存储管理方式n界地址管理方式一维地址界地址管理方式一维地址n页式管理方式一维地址页式管理方式一维地址n段式管理方式二维地址段式管理方式二维地址n段页式管理方式二维地址段页式管理方式二维地址6.3.1 界地址管理方式界地址管理方式4.3.1.1 根本原理根本原理 1. 内存空间划分：动态异长；内存空间划分：动态异长； 2. 进程空间划分：一个进程一个区域，逻辑地址进程空间划分：一个进程一个区域，逻辑地址0 l-1 3. 进程空间与内存空间对应关系可以浮动：进程空间与内存空间对应关系可以浮动
12、：0:l-1:.b:lb+l-1:进程空间进程空间内存空间内存空间6.3.1 界地址管理方式界地址管理方式 4. 所需表目：所需表目： (1)内存分配表内存分配表-在在PCB中；中； (2)空闲区域表：空闲区域表：array of (addr,size)。 5. 所需存放器：所需存放器： (1)基址存放器基址存放器b: 保管运转进程起始地址；保管运转进程起始地址； (2)限长存放器限长存放器l: 保管运转进程长度。保管运转进程长度。 6. 地址映射：地址映射：6.3.1 界地址管理方式界地址管理方式0:l-1:.b:lb+l-1:lb逻辑地址逻辑地址CP+ab+a步骤：步骤：(1) 由程序确定
13、逻辑地址由程序确定逻辑地址a； (2) a与与l比较判别能否越界，比较判别能否越界， 不满足：不满足：0 a l-1，越界；，越界； (3) a与与b相加得到物理地址。相加得到物理地址。进程空间进程空间内存空间内存空间6.3.1 界地址管理方式界地址管理方式6.3.1.2 双对界双对界 代码代码(I空间空间)：一对界：一对界 数据数据(D空间空间)：一对界：一对界6.3.1.3 交换技术交换技术(swapping) 例：例：UNIX 交换进程交换进程sched (#0) 交换原那么：外存交换原那么：外存 SRUN 形状进程形状进程内存内存 (1)内存有空间，直接移入；内存有空间，直接移入； (
14、2)内存空间不够，移出内存空间不够，移出SWAIT, SSTOP形状进程；形状进程； (3)假设还不够，移出假设还不够，移出SSLEEP, SRUN形状进程，形状进程， 条件：在外时间条件：在外时间 3秒；在内时间秒；在内时间 2秒。秒。 b1l1b2l26.3.1 界地址管理方式界地址管理方式n覆盖技术覆盖技术: 将较大程序装入较小进程空间将较大程序装入较小进程空间的技术的技术.n只将全局代码和数据静态装入内存只将全局代码和数据静态装入内存, 其它其它部分动态装入部分动态装入.n后装入的成分反复运用先装入成分所运后装入的成分反复运用先装入成分所运用的存储区用的存储区, 即覆盖先装入的成分即覆
15、盖先装入的成分.覆盖技术覆盖技术符号表符号表公共例程公共例程覆盖驱动程序覆盖驱动程序覆盖区覆盖区50kbPass130kbPass250kbPass340kbPass425kb6.3.2 分页式存储管理分页式存储管理(paging)6.3.2.1 根本原理根本原理 1. 内存空间划分：静态等长，内存空间划分：静态等长，2i, 称为一个页框称为一个页框frame)。 .第第0页页第第1页页第第k页页第第2n-i-1页页2i0 2i:1 2i:k 2i:(2n-i-1) 2i:物理地址物理地址=页架首址页架首址+页内地址页内地址 =页架号页架号 2i +页内地址页内地址 = 页架号页架号 页内地址
16、页内地址i位位n-i位位6.3.2 分页式存储管理分页式存储管理2. 进程空间划分：静态等长，进程空间划分：静态等长，2i, 称为一个页面。称为一个页面。.第第0页页第第1页页第第k页页 第第l-1页页2i0 2i:1 2i:k 2i: (l-1) 2i:逻辑地址逻辑地址=逻辑页首址逻辑页首址+页内地址页内地址 =逻辑页号逻辑页号 2i +页内地址页内地址 =逻辑页号逻辑页号 页内地址页内地址i位位3. 进程空间与内存空间对应关系进程空间与内存空间对应关系.第第0页页第第1页页第第2页页第第3页页第第16页页第第22页页第第32页页第第15页页.进程空间进程空间内存空间内存空间4. 所需表目：
17、所需表目：(1)页表，每个进程一个页表，每个进程一个物理页号物理页号逻辑页号逻辑页号:1522163201235. 所需存放器所需存放器(2)总页表：系一致总页表：系一致个个(1) 页表首址存放器：页表首址存放器：bl(2) 页表长度存放器：页表长度存放器：系一致个系一致个系一致个系一致个(3) 快表快表(TLB)：系一致组：系一致组：逻辑页号逻辑页号页架号页架号.fp逻辑地址地址(p,d)物理地址物理地址(f,d)(1) 由程序确定由程序确定逻辑地址地址(p,d)；(2) 由由p查快表得快表得页架号架号f； 如如查不到：不到： (3) 由由p与与l比比较，判，判别能否越界：能否越界： 不不满
18、足：足：0pl-1，越界；，越界； (4) 由由p和和b查页表得表得f; (5) parbegin (p,f)快表，如快表，如满淘汰一个淘汰一个; f与与d合并得物理地址合并得物理地址 parend(3) f与与d合并得物理地址合并得物理地址6. 地址映射地址映射 : (p,d)(f,d) .逻辑页号逻辑页号页架号页架号.fplbbl.PCB页架号页架号逻辑页号逻辑页号.f.p.f dp d物理地址物理地址逻辑地址逻辑地址b:.如查不到.逻辑页号逻辑页号页架号页架号.fplbbl.PCB页架号页架号逻辑页号逻辑页号.f.p.f dp d+cp p f 物理地址物理地址逻辑地址逻辑地址b:.有效
19、访问时间有效访问时间n(Effective Access Time)nEAT=快表命中率快表命中率 (快表访问时间快表访问时间+内存内存访问时间访问时间)+快表不中率快表不中率 (快表访问时间快表访问时间+2 内存访问时间内存访问时间) nsn 98% (20+100)+2% (20+200)ns =122ns6.3.2.2 多级页表多级页表n提出背景提出背景n内存空内存空间成倍增成倍增长, 进程虚程虚拟空空间成倍添加成倍添加n单级页表需求很大延表需求很大延续内存空内存空间n例如例如n32位位进程地址空程地址空间，页长占占12位位4k，页号号20位，位，页表最多可达表最多可达220个入口！个入
20、口！n多多线程程设计导致致进程虚程虚拟空空间不延不延续(空洞空洞hole)n栈的的预留空留空间(没有没有页架相架相对应)n页表所占内存空表所占内存空间浪浪费n处理理战略略n二二级或多或多级页表表Two-Level Page-Table Scheme外页表对应外页表对应hole的表项没有对应的表项没有对应的内页表的内页表访问访问hole表项动表项动态建立内页表态建立内页表Two-Level Paging ExampleA logical address (on 32-bit machine with 4K page size) is divided into:a page number cons
21、isting of 20 bits.a page offset consisting of 12 bits.Since the page table is paged, the page number is further divided into:a 10-bit page number. a 10-bit page offset.Thus, a logical address is as follows:where pi is an index into the outer page table, and pj is the displacement within the page tab
22、le.page number page offsetpipjd101012Address-Translation Scheme Address-translation scheme for a two-level 32-bit paging architecture Even though time needed for one memory access is quintupled, caching permits performance to remain reasonable4级页表有效访问时间级页表有效访问时间nEAT=快表命中率快表命中率 (快表访问时间快表访问时间+内存访内存访问时
23、间问时间)+快表不中率快表不中率 (快表访问时间快表访问时间+5 内存访问时间内存访问时间) nsn 98% (20+100)+2% (20+500)nsn=128ns6.3.2.3 反置页表反置页表(inverted page table)n传统页外表向进程空间传统页外表向进程空间n每个进程逻辑页面有一表项每个进程逻辑页面有一表项n当进程空间很大时，页表很大当进程空间很大时，页表很大n反置页外表向内存空间反置页外表向内存空间n每个内存页架一个表项每个内存页架一个表项n大小固定大小固定反置页表反置页表-任务原理任务原理程序程序物理物理内存内存pidpf dpid p df逻辑地址逻辑地址物理地
24、址物理地址反置页表反置页表6.3.2 页式存储管理页式存储管理(Cont.)采用散列技术的反置页表地址映射采用散列技术的反置页表地址映射逻辑地址逻辑地址pidpd进程进程逻辑逻辑页号页号冲突冲突计数计数空闲空闲.pidp21进进程程散列散列函数函数ffd物理地址物理地址采用散列技术的反置页表采用散列技术的反置页表物理内存物理内存速度问题速度问题n反置页表查找反置页表查找n由表头起始，平均为表长度的一半由表头起始，平均为表长度的一半n速度慢速度慢n处理方案处理方案n在反置页表前添加一级杂凑表在反置页表前添加一级杂凑表n查找杂凑表与反置页表至少需求两次访查找杂凑表与反置页表至少需求两次访问内存问内
25、存n为进一步提高速度，快表缓冲为进一步提高速度，快表缓冲1. 内存空内存空间划分：划分：动态异异长，每区一段。，每区一段。段首址段首址+段内地址段内地址物理地址物理地址=b：lb+d6.3.3 分段式存储管理分段式存储管理(segmentation)2. 进程空间划分：假设干段，每段一个程序单位。进程空间划分：假设干段，每段一个程序单位。调用用x段段ef: 访问d段段ae: 调用用y段段fmain(段号段号0)X(段号段号1)Y(段号段号2)D(段号段号3)a:080k-10.40k-1020k-1060k-1逻辑地址地址= 段号段号 段内地址段内地址(二二维地址地址)mainxyd3. 对应
26、关系对应关系40k60k80k20k.进程空间进程空间内存空间内存空间100k:200k:300k:320k:4. 所需表目所需表目(1) 段表：每进程一个段表：每进程一个段首址段首址段长度段长度100k40k80k60k段号段号 0: 1: 2: 3:20k200k320k300k(2) 空闲表：系一致个空闲表：系一致个 array of (addr,size)5. 所需存放器所需存放器(1) 段表首址存放器：段表首址存放器：bl(2) 段表段表长度存放器：度存放器：系一致个系一致个系一致个系一致个(3) 快表快表(TLB)：系一致：系一致组： 段号段号 段首址段首址 段长度段长度.ls.b
27、.6. 地址映射地址映射 : (s,d)(b+d) 逻辑地址地址(s,d)物理地址物理地址(b+d) (1)由程序确定由程序确定逻辑地址地址(s,d); (2) 由由s查快表得快表得b和和l 如如查不到：不到： (3) 由由s与与l比比较判判别能否越界能否越界 不不满足：足：0sl-1，越界；，越界； (4) 由由s和和b查段表，得段表，得b和和l (5) 由由d与与l比比较，判，判别能否越界能否越界 不不满足：足：0dl-1，越界，越界; (6) parbegin (s,b,l)快表快表, 如快表如快表满淘汰一个；淘汰一个； 由由bd得物理地址得物理地址 parend (3) 由由d与与l比
28、比较，判，判别能否越界能否越界 不不满足：足：0dl-1，越界；，越界； (4) 由由bd得物理地址。得物理地址。段号段号段长段长 段首址段首址. . . l b slbbl.PCB段首址段首址 段长段长 段号段号 b l.s.b+d物理地址物理地址s d逻辑地址逻辑地址 cp+b:假假设查不到不到段号段号段长段长 段首址段首址. . . l b slbbl.PCB段首址段首址 段长段长 段号段号 . b l.s.b+d物理地址物理地址s d逻辑地址逻辑地址 . s l b b:+cpcp+6.3.3.2 段的共享段的共享段长段长 段首址段首址 . l b . .段号段号 si .P1段表：段
29、表：段长段长 段首址段首址 . l b . .段号段号 sj .P2段表：段表：共享段共享段.b:l内存空间内存空间 如何如何实现？ 共享段表共享段表段名段名 共享记数共享记数 段长段长 段首址段首址 其它其它 . vi 3 35k 125k ? 共享段表：共享段表：进程段表进程段表(n)共享段表共享段表(1)共享段共享段(1)例子：例子：UNIX正文段正文段(text段段)struct text int x_daddr; /*disk address int x_caddr; /*core address, if loaded int x_size; /*size( 64) int *x_i
30、ptr; /*inode pointer char x_count; /*reference count char x_ccount; /*number of loaded reference; textNTEXT;define NTEXT 40 struct proc int *p_textp; /*pointer to text structure;struct user int u_tsize; 6.3.3.2 段的维护段的维护 (1) 段表的改良：段表的改良：段长段长 段首址段首址 . . . l b e 1 0 1段号段号 s .访问权限访问权限R W E . . . 段号段号 段长
31、段长 段首址段首址 . . . s l b 1 0 1访问权限访问权限R W E(2) 快表的改良：快表的改良： . . .共享段共享段 表入口表入口6.3.4 段页式存储管理段页式存储管理(segmentation with paging)n段式段式优于于页式式n便于共享和便于共享和维护n页式式优于段式于段式n消除消除“碎片碎片问题n段段页式：式：结合二者合二者优点点n每个每个进程包含假程包含假设干段干段n每个段包含假每个段包含假设干干页6.3.4.1 根本原理根本原理 1. 内存空内存空间划分：划分：(同同页式式) 静静态等等长，2i, 称称为一一页架。架。 物理地址物理地址=(页架号架号
32、,页内地址内地址)=(f,d) 2. 进程空程空间划分：划分： 一个一个进程程假假设干个段干个段 一个段一个段假假设干个干个页 逻辑地址地址=(段号段号, 逻辑页号号, 页内地址内地址)=(s,p,d)6.3.4 段页式存储管理段页式存储管理3. 对应关系：对应关系：0页页1页页2页页0页页1页页第第1段：段：0页页1页页2页页第第0段：段：第第2段：段：25页页26页页27页页28页页29页页30页页31页页32页页33页页 . .内存空间内存空间进程空间进程空间4. 所需表目所需表目 (1) 段表：每个段表：每个进程一个程一个页表首址页表首址 页表长度页表长度 . b l .段号段号 0
33、. s . l-1(2)页表：每个段一个表：每个段一个逻辑页号号 0 p l-1页架号页架号.f.(3) 总页表：系一致个表：系一致个5. 所需存放器所需存放器 (1)段表基址存放器：保管正运段表基址存放器：保管正运转程序段表首址；程序段表首址； (2)段表限段表限长存放器：保管正运存放器：保管正运转程序段表程序段表长度。度。 (3)快表：一快表：一组联想存放器想存放器 (快段表快段表+快快页表表) (TLB)段号段号 逻辑页号号 页架号架号 . s p f .bl6. 地址映射地址映射 : (s,p,d)(f,d) 逻辑地址地址(s,p,d)物理地址物理地址(f,d) (1) 由程序确定由程
34、序确定逻辑地址；地址； (2) 由由(s,p)查快表得快表得f； 如找不到：如找不到： (3) 由由s与与l比比较判判别能否越界：能否越界： 不不满足：足：0sl-1, 越界越界 (4) 由由s和和b查段表得段表得页表表(b,l) (5) 由由p与与l比比较判判别能否越界：能否越界： 不不满足：足：0pl-1, 越界越界 (6) 由由b与与p查页表得表得f (7) parbegin f与与d合并得物理地址合并得物理地址 (s,p,f)快表，假快表，假设快表已快表已满，淘汰一个，淘汰一个 parend (3) 由由f与与d合并得物理地址合并得物理地址(f,d)lbbl.PCBf d物理地址物理地址s p d逻辑地址逻辑地址段号段号0Sl-1页表长页表长首址首址lb页架号页架号f页号号0pl-1段号段号 页号页号 架号架号spf如如查不到不到lbbl.PCBf d物理地址物理地址s p d逻辑地址逻辑地址 s p f +cpcp+段号段号0Sl-1页表长页表长首址首址lb页架号页架号f页号号0pl-1段号 页号 架号spf
