页式内存管理（Paging）.ppt

1页式内存管理页式内存管理(Paging)2页式内存管理页式内存管理n注意一个事实：进程并不要求逻辑地址必须连续的n把物理空间等分成长度一致的数据块，称作“页帧”(frames) ，操作系统对空闲页帧进行统一管理n把逻辑空间等分成长度一致的数据块，称作“页”(pages)，并且与页帧长度相等n通常，页长(也就是页帧长度)是 2 的幂次，取512字节与8192字节之间的数值3逻辑空间至物理空间的函数模型逻辑空间至物理空间的函数模型y=f(x) ?4假设逻辑地址空间 2m ，页长P为 2nnCPU提供的逻辑二进制地址addr区分为两个部分p页号页号 (p) : p=addr/P作为下标查询页表(page table)中目标单元，该单元包含对应于物理空间的页帧的基地址p页内偏移量页内偏移量 (d): d=addr%P该地址在对应页帧内部的偏移位置逻辑地址至物理地址的地址翻译逻辑地址至物理地址的地址翻译page number page offsetpdm - nn5地址翻译地址翻译6示例：地址翻译示例：地址翻译物理空间32字节，页长4字节7页式内存管理页式内存管理(续续)nOS负责监控所有空闲页帧n若进程需要 n 页逻辑空间，OS分配 n个空闲页帧给它，装入代码和数据nOS分配页表需要的物理空间，布置好页表(决定了 f 函数)n页式内存管理存在Internal fragmentation问题8空闲页帧空闲页帧分配前分配后9如何实现页表如何实现页表n页表必须驻留内存。

为什么？页表必须驻留内存为什么？n页表基地址寄存器页表基地址寄存器Page-table base register (PTBR) 指向页表的首地址n页表长度寄存器页表长度寄存器Page-table length register (PTLR) 表示页表占用的空间长度10如何实现页表如何实现页表(续续)n访问一个数据/地址，需 2 次内存访问 ！l1次访问页表l1次访问数据/地址本身n解决2次访问问题，借助硬件translation look-aside buffers (TLBs)11n也称关联存储器Associative memoryn其特征 并行搜索 nTLB用于对(p, d)的地址翻译p如果 p 恰好在TLB(称为命中或hit), 直接从TLB得到页帧号p否则(fail), 从内存页表中取得页帧号TLBPage #Frame #12有有TLB参与的地址翻译参与的地址翻译13有效访问时间有效访问时间(Effective Access Time)n设TLB的查询时间 = 单位时间n假设内存访问周期为 1 微秒n命中率(Hit ratio)l成功地在TLB取得页号的百分率；l命中率与TLB的单元总数有关n设命中率 = n有效访问时间(EAT)EAT = (1 + ) + (2 + )(1 ) = 2 + 14内存保护内存保护n在进程页表的每个页表项中，为每个页设置一个保护位 Valid-invalid bitn页表项的“有效-无效”位n“有效”表示该页面在进程的逻辑地址空间范围内，因此是合法页面n“无效”表示该页面不在进程的逻辑地址空间范围内15示例：页表项的有效位示例：页表项的有效位(v)、无效位、无效位(i)16共享页面共享页面n共享代码共享代码p只读(可重入)代码只需要一份，供若干进程共享 (i.e., 文本编辑器、编译器、窗口系统)p对所有进程来说，共享代码必须位于逻辑地址空间的相同位置n进程自有代码和数据进程自有代码和数据 p进程各自拥有一份p为自有代码、数据分配的页面，可以分布在进程逻辑地址空间的任意位置17示例：共享页面示例：共享页面18例题例题n假定某页式管理系统中，主存为128KB，分成32块，块号为0、1、2、3、31；某作业有5块，其页号为0、1、2、3、4，被分别装入主存的3、8、4、6、9块中。

有一逻辑地址为3，70试求出相应的物理地址（其中方括号中的第一个元素为页号，第二个元素为页内地址，按十进制计算），并画图说明地址变换过程19n【答案】相应的物理地址为24646n【分析】块大小为128KB/32=4KB，因为块与页面大小相等，所以每页为4KB第3页被装入到主存第6块中，故逻辑地址3，70对应的物理地址为4KB6+70=24576+70=24646其地址变换过程如下图例题例题20页表的数据结构页表的数据结构n层次页表（Hierarchical Paging）n哈希页表（Hashed Page Table）n反向页表（Inverted Page Table）21层次页表层次页表(Hierarchical Page Table)n将页表的逻辑地址拆分成多张页表n一种简单的技巧：二级页表22二级页表策略二级页表策略23示例：二级页表示例：二级页表n逻辑地址 (32位CPU，页长4KB) 分割成两部分p页号，20 位p页内偏移量， 12 位n页表被进一步分页，其页号分割成两部分p页号的页号， 10 位p页号的页内偏移量，10 位n因此，一个逻辑地址分割成三部分n其中，p1 是外层页表的下标， p2 是外层页表内部之位移page number page offsetp1p2d10101224二级页表策略的地址翻译二级页表策略的地址翻译25三级页表的策略三级页表的策略26哈希页表（哈希页表（Hashed Page Table）n多见于地址空间大于 32 位的CPUn虚拟页号经过哈希函数转换后，指向页表中某个页表项n哈希函数值相同的虚拟页号，指向同一个页表项，它们在那个页表项下组成一个链表n地址翻译时，由虚拟页号哈希后锁定对应链表，搜索与虚拟页号的匹配项n如果找到匹配项，则找到了虚拟页号对应的物理页帧27Hashed Page Table28反向页表（反向页表（Inverted Page Table）n每个物理页帧，对应Inverted Page Table的一个表项n对于每个表项，它表示的物理页帧存储了某个进程的一个逻辑页。

表项内容包含该进程id、页号n对比传统页表，该方法的页表空间大幅度减少n但是，查找页表项的时间明显增加n利用哈希表，使得查页表操作能一次命中，或者耗费较少的查找次数29Inverted Page Table30例题例题n哈希页表是否适合处理大量的地址空间？31n答案：当一个程序占用大的虚拟地址空间的一小部分时，哈希页表非常适合哈希页表的缺点是在同样的哈希页表上映射多个页面而引起的冲突如果多个页表项映射在同个入口处，则可能导致其相应的哈希入口负担过重例题例题32END。