第14课(页式存储管理)

操作系统Lecture14存储管理今日内容分页式存储管理3.3分页式存储管理分区存储管理外部碎片解决外部碎片允许程序的物理空间地址非连续3.3.1分页式存储管理的基本思想内存的划分：把整个内存储器划分成大小相等的许多分区，每个分区称为“块”。比如把内存储器划分成n个分区，编号为0,1,2,…,n-1。块是存储分配的单位。用户作业逻辑地址空间的划分：操作系统按照内存块的尺寸对用户地址空间进行划分，每一个分区被称为“页”，编号从0开始。例：逻辑地址空间与物理地址空间:页大小=块大小=4K操作系统内存储器020KB24KB28KB32KB36KB40KB44KB48KB256KB(0~4块)第5块第6块第7块第8块第9块第10块第11块04KB8KB11KB12KB第0页第1页第2页用户作业A例：逻辑地址空间与物理地址空间:页大小=块大小=4K操作系统内存储器作业A(第2页)作业A(第0页)作业A(第1页)020KB24KB28KB32KB36KB40KB44KB48KB256KB(0~4块)第5块第6块第7块第8块第9块第10块第11块04KB8KB11KB12KB第0页第1页第2页用户作业A例：逻辑地址空间与物理地址空间:页大小=块大小=4K操作系统内存储器作业A(第2页)作业A(第0页)作业A(第1页)020KB24KB28KB32KB36KB40KB44KB48KB256KB(0~4块)第5块第6块第7块第8块第9块第10块第11块04KB8KB11KB12KB第0页第1页第2页用户作业A例：逻辑地址空间与物理地址空间:页号物理块号021328进程1页表进程2页表页号物理块号011425页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。例:如何由逻辑地址得物理地址？页长:4页式存储管理中的地址重定位逻辑地址结构:由页号和页内偏移量两部分组成页号页内偏移例:作业7K,页大小:2K逻辑地址13:13=0x2048+13=页号:0页内偏移:13逻辑地址42104210:=2x2048+114=页号:2页内偏移:114物理地址结构：块号和块内偏移量组成如何将逻辑地址转换为物理地址：从逻辑地址算出页号和页内偏移量从页表中找出页号对应块号物理地址：块号×页大小+偏移量将逻辑地址转换为物理地址：例2：下图中，页大小1K，逻辑地址3000，物理地址为？用户作业A的相对地址空间XXXXXX01001KB2KB30003KB952第0页第1页第2页操作系统作业A(第0页)XXXXXX952作业A(第2页)04KB4KB+1005KB6KB7KB7KB+9528KB(0~3块)第4块第5块第6块第7块第8块页表页号块号0124977K+952=8120问题：如何选择页的大小?太小页表过长太大内部碎片一般，一页的大小为2的整数次幂例:逻辑地址应用几位表示？页长：4例：程序11K，页长4k，逻辑地址需要多少位？04KB8KB11KB12KB第0页第1页第2页用户作业A例：下面逻辑地址中，页大小是多少？可以表示多少页？0111231页号P页内位移量W编号0~1048575相对地址0~4095分页硬件实现硬件设置一个专用寄存器：“页表控制寄存器”，存放作业的页表起址和长度。操作系统内存储器块号页内位移绝对地址页表起始地址长度页表控制寄存器页号页内位移相对地址CPU快表取一次数据或指令至少要访问内存两次以上。一次访问页表，一次根据地址取数据或指令，这比通常执行速度慢了一倍。为缩短查找时间（为了提高地址映射速度），可以将页表从内存装入到相联存储器（介于内存与寄存器之间的存储机制）—快表中快表：存放当前执行进程中最常用的页号与所对应的页框号，从而提高查找速度。使用快表的硬件模式操作系统内存储器块号页内位移绝对地址快表页号页内位移相对地址长度起始地址页表控制寄存器页表命中没有命中有效访问时间：EffectiveAccessTime(EAT):EAT=(x+y)α+(x+y+z)(1-α)x:访问快表的时间y:访问内存的时间Z:访问页表的时间α:命中率.访问的页面在快表中找到的百分比例1:命中率=0.8，访问快表需20ns，访问内存需100ns，访问页表需100nsEAT=0.8*（20+100）+0.2*（20+100+100）=140ns例2:命中率=0.98EAT=0.98*120+0.02*220=122ns内存块的分配与回收存储分块表位图单链表存储分块表系统维持一张表格，表格一个表项与内存中的一个存储块相对应，记录该块的使用情况。只要表格中“空闲块总数”记录的数目大于请求的存储量，就可进行分配，并把分配出去的块的状态改为“已分配”。作业完成后归还存储块时，就把表中相应块的状态改为“空闲”。块号状态0已分配1已分配2已分配3已分配4空闲5已分配6空闲7空闲8已分配9空闲10空闲11已分配12已分配13已分配14已分配15空闲空闲块总数：6存储分块表位图用二进制位与内存块的使用建立起关系为“0”，表示对应块空闲；为“1”，表示对应块已分配。1111010010011110空闲块总数：60123456701字节号位号位图单链表把空闲块链接成一个单链表加以管理。系统必须设置一个空闲块链表的起始地址指针，以便进行存储分配时能够找到空闲的内存块。无论是进行空闲块的分配还是作业完成后归还存储块，都要调整空闲块间的链表指针。操作系统作业C第2页作业B第0页作业A第0页空闲块作业A第2页空闲块空闲块作业B第1页空闲块空闲块作业A第1页作业C第3页作业C第0页作业C第1页空闲块内存储器064K空闲块链表起址单链表存储保护与共享在页式环境下，存储保护以页面为单位。在页表的每个表项里设置一个所谓的“保护位”，由该位的不同取值定义对应页是可读、可写或只可读等。还有一位与页表中的每一条目相关联，称为有效－无效位该位“有效”时表示这页在进程的逻辑地址空间内，因此是合法的页。该位“无效”时表示这页不在进程的逻辑地址空间内。例:页表中：有效位(v)无效位(i)系统:14位地址空间(0-16383),页大小2K。一个程序，其地址空间为(0-10468)，需分成6页。共享页面在分时共享环境下,40个用户执行文本编辑器，一个文本编辑器需要150k的代码空间和50k的数据空间。没有共享：(150KB+50KB)*40=200KB*40=8000KB共享每个文本编辑器执行代码是一样的，所以这40个用户可共享代码空间，这些代码要是纯代码（只读代码）50KB*40+150KB=2000KB+150KB=2150KB共享页面例子图：ed1进程A的逻辑地址空间0ed21ed32dataA3进程A的页表03123462ed1进程B的逻辑地址空间0ed21ed32dataB3进程B的页表03123468ed1进程C的逻辑地址空间0ed21ed32dataC3进程C的页表031234611操作系统dataAdataBdataCed1ed2ed30123456789101112共享代码：只读代码，可被进程共享（如文本编辑器,编译器,窗口系统等)。共享代码必须出现在所有进程逻辑地址的同一位置私人代码和数据：每个进程独有私有代码和数据页可以出现在逻辑地址空间的任何地方。分页式存储管理中不能实现真正意义共享被共享的程序文本不一定正好在一个或几个完整的页面中，有可能一个页面中既有允许共享的内容，又有不能共享的私有数据。因此，在分页环境下实现页面的共享比较困难。分页式存储管理的特点内存存储器事先被划分成相等尺寸的块，它是进行存储分配的单位。用户作业的相对地址空间按照块的尺寸划分成页。这种划分是在系统内部进行的，用户感觉不到，即对用户是“透明”的。相对地址空间中的页可以进入内存中的任何一个空闲块，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行。分页式存储管理的优缺点优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。程序占用空间可动态增长。即随着程序运行而动态生成的数据增多，地址空间可相应增长。缺点：作业虽然不占据连续的存储区，但每次仍要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，那么还是存在小内存不能运行大作业的问题。存在内碎片：平均每一个作业要浪费半页大小的存储块。不能实现真正意义上的共享内存访问速度慢（取一次数据或指令至少要访问内存两次以上）练习:逻辑地址0、10、13的物理地址？页长:4逻辑地址0(5x4)+0=20物理地址逻辑地址10(1x4)+2=6物理地址逻辑地址13(2x4)+1=9物理地址pagesize:4练习：一个进程，虚页为3页长，每个页面长度为1k（1024字节），页表如右图所示。进程中指令Load1，2500（从有效地址2500取数据放入1号寄存器中）的虚地址为100，如何找到该指令的内存物理地址及数据存放地址？页表页号块号012238练习：一个进程，虚页为3页长，每个页面长度为1k（1024字节），页表如上图所示。进程中指令Load1，2500（从有效地址2500取数据放入1号寄存器中）的虚地址为100，如何找到该指令的内存物理地址及数据存放地址？页表页号块号012238解：1、由虚地址为100可知，指令Load1，2500在第0页的第100单元中。2、由页表知，第0页与第2页框对应，因此，该指令对应的内存物理地址为：1024×2＋100＝2148。当cpu执行到2148单元的指令Load1，2500时，要从有效地址2500取数据，转换2500：2500＝1024×2＋452，页号为2，页内偏移452单元，由页表知，第2页与第8页框对应，因此，2500对应的内存物理地址为：1024×8＋452＝8644。