地址内存管理

第五章内存管理刘晓建2018年10月23日本章概要进程的内存管理问题是研究:如何把进程的结构加载到物理内存为此需要回答这样几个问题:WhenandWho执行内存管理When=程序运行时一次把程序的全部代码载入内存还是部分代码程序在内存中是连续分布还是离散分布程序在内存中的位置是一成不变的,还是可以移动的进程间如何共享公共代码进程的生命周期=进程在内存中的周期4.
1并发问题内存管理的基本需求:1、重定位的需求:一个程序在不同的运行实例中,操作系统为它分配的物理内存空间可以不同,甚至在一个程序运行期间,它所占据的物理内存空间也可以上下浮动.
2、共享的需求:一是指在多道程序设计中,多个进程共享同一物理内存,为此需要对内存空间进行合理有效的划分,使得每个进程独占一定的内存区域,而且这些区域不相互冲突.
二是指允许多个进程访问同一内存区域(共享库/共享代码).
3、保护的需求:由于多个进程驻留在内存中,因此必须保护一个进程的内存空间不受其它进程有意或无意的干扰.
一个进程不能未经授权的访问另一个进程的内存单元.
4、存储器扩充的需求:用有限的物理内存运行相对更多的程序.
地址定位所谓地址定位(或称为地址绑定,Addressbinding)是指:为了执行一个程序,必须确定程序指令或数据所在物理内存地址的过程.
在程序还没有加载之前,程序以文件的形式存在于磁盘空间中,程序中的指令和数据使用相对地址(或逻辑地址)来编址;当准备运行程序时,程序被加载到内存中,这时需要定位程序指令和数据的物理内存地址,即在物理内存中确定指令和数据的位置.
因此,地址定位过程就是逻辑地址到物理地址的变换过程.
程序加载时地址定位,也称为静态地址定位,是由加载器(Loader)在加载程序过程中将程序指令和数据的物理地址确定下来.
…………0x10jmp0x500……add0x600,%eax……0x0000x1000x6000x5000x1000…………0x10jmp0x(X+500)……add0x(X+600),%eax……0xX0x(X+100)0x(X+600)0x(X+500)0x(X+1000)OS……0x000……加载时地址定位程序中指令和数据的逻辑地址(用LA表示)以及指令所引用的逻辑地址都在加载时被定位到物理地址(用PA表示),地址定位的算法为:PA=LA+X其中X是加载的起始内存地址.
优点是容易实现,无需硬件支持,它只要求程序本身是可重定位的,即对那些要修改的地址部分具有某种标识.
早期的操作系统大多采用这种方法进行地址定位.
主要缺点是:程序经地址定位之后,在程序运行过程中就不能再移动了,因而不能重新分配内存,不利于内存的有效利用;程序在内存空间中只能连续分配,不能离散分布在内存的不同区域;多个用户很难共享内存中的同一程序,如果多个进程要共享同一程序,则必须使用自己的副本.
静态地址定位的优缺点:程序运行时地址定位,也称为动态地址重定位,把地址定位从加载时推迟到运行时.
在加载时,仍然保持程序的相对地址不变,只有在访问一条指令或数据时,才计算它们的物理地址.
…………0x10jmp0x500……add0x600,%eax……0x0000x1000x6000x5000x1000…………0x10jmp0x500……add0x600,%eax……0xX0x(X+100)0x(X+600)0x(X+500)0x(X+1000)OS……0x000……可执行文件(相对地址空间)物理内存地址空间运行时地址定位运行时地址定位使用一个硬件机构MMU(内存管理单元)来实现.
基址寄存器记录程序在内存中的起始地址,界限寄存器记录程序的最大逻辑地址(即程序的字节大小).
当程序被加载入内存或当该进程被换入时,必须设置这两个寄存器.
运行时地址定位的算法为:PA=LA+R[基址寄存器]并且LA内存管理5.
2.
1固定分区管理操作系统8M8M8M8M8M8M8M8M操作系统8M2M4M6M8M8M12M16Ma)大小相等的分区b)大小不等的分区当一个进程请求内存区时,有以下三种分配方法:最小适配:在所有满足进程内存需求的分区中选择一个最小的分区来分配,即min{x|x≥R},其中x是分区的大小,R是进程的内存需求大小.
首次适配:即按照某种顺序,找到的第一个满足进程内存需求的分区分配给该进程.
最大适配:在所有满足进程内存需求的分区中选择一个最大的分区来分配,即max{x|x≥R}.
算法45.
2.
2覆盖技术程序大小超过最大分区时,不能放到一个分区中.
这种情况下,程序员必须使用覆盖技术(Overlaying)设计程序,使得任何时候只有一部分程序驻留内存中,而且不影响程序的运行.
一个程序有主模块main,它分别会调用模块A和模块B,但是A和B之间不会相互调用.
假定这三个模块的大小分别是1024字节、512字节和256字节,在理论上它们需要占用1792个字节的内存.
由于模块A和B相互不调用,因此它们可以相互覆盖,共享同一块内存区域,使得实际内存占用减小到1536字节,覆盖技术对于程序员是不透明的,也就是覆盖是通过程序员编写代码来实现的.
程序员在编写程序时,必须手工将程序分成若干块,然后编写一个小的辅助代码来管理这些模块何时应该驻留在内存、何时应该被替换掉.
这个小的辅助代码就是所谓的覆盖管理器(OverlayManager).
优点:变完全加载为部分加载缺点:(1)内存管理对程序员是透明的,因此增加了编写程序的复杂性;(2)如果一个模块在内存中,那么从该模块开始的整个调用路径上的模块都必须在内存中;(3)分支树上的模块之间不能存在相互调用.
有时,模块之间的调用关系并非树状结构,因此覆盖技术就失去了前提.
5.
2.
3可变分区管理可变分区管理的分区长度和分区数目都是不固定的.
当进程被载入内存时,系统会给它分配一块和它所需内存大小完全相等的内存空间.
操作系统8M56M操作系统8M18M进程120M进程214M进程34M操作系统8M18M进程120M进程48M进程34M6M进程4就绪进程2挂起操作系统8M18M进程214M进程48M进程34M6M进程1退出进程2激活6M容易造成内存碎片克服内存碎片的一个办法是将进程占据的内存上下浮动,使得若干细小、零散的碎片被整合成一整块大的内存,以便用于其它进程的内存分配,但是要这样做需要两个机制的支持:一是动态地址重定位,二是内存拷贝.
在进程的生命周期内,其内存空间要上下浮动,如果采用静态地址定位,当程序和数据部分浮动之后,内存引用就会出现错位.
另外,内存拷贝很浪费处理器时间,效率不高.

分区管理具有下面几个特点:利于共享.
分区管理能够实现多个进程共享同一内存空间,而且便于实现进程的保护.

全部加载.
一个进程的地址空间要么被全部交换到内存空间,要么被全部交换出内存空间.

使用分区管理无法实现真正意义上的存储器扩充.
连续分配.
一个进程需要被映射到连续的内存区域.
无论是静态还是动态地址定位,都以连续内存分配为前提.
如果进程的不同部分被映射到离散的内存区域,那么逻辑地址变换和进程保护就将变得非常复杂.
5.
2.
4伙伴系统伙伴系统是固定分区和可变分区的一种折衷方案.
在伙伴系统中,可用内存块的大小为2K字节,L≤K≤U,其中,2L表示最小内存块的大小,2U表示最大内存块的大小.
通常2U是可供分配的整个内存的大小.
开始时,可用于分配的整个空间被看作一个大小为2U的块.
如果请求的大小s满足2U-1内存管理的一个中间数据结构.
基于虚拟内存的内存管理并不是直接将可执行目标文件映射到物理内存中,而是通过虚拟内存间接建立可执行目标文件与物理内存的映射关系.
5.
3.
1可执行目标文件使用一种程序设计语言编写完程序之后,通常需要进行编译、链接两个阶段,最终产生可执行目标文件.
5.
3.
2虚拟地址空间【定义1】(地址空间)地址空间是一个非负整数地址的有序集合:{0,1,2,…,N-1}如果地址空间中的元素是连续的,那么我们称该地址空间为线性地址空间.

在线性地址空间{0,1,2,…,N-1}中,N称为地址空间的大小.
地址空间是一个抽象的数学概念,使用它可以编码任何字节内容,比如物理内存、处理器寻址范围、文件内容以及进程结构等.
我们把编码M个字节的物理内存的地址空间称为物理地址空间(PAS,PhysicalAddressSpace):{0,1,2,…,M-1}把编码处理器寻址范围的地址空间称为虚拟地址空间(VAS,VirtualAddressSpace):{0,1,2,…,N-1}其中N=2n,n表示处理器所支持的最大地址的位数,通常取32或64.
5.
3.
2虚拟地址空间虚拟地址空间中的每一个地址称为虚拟地址.
虚拟地址空间的大小取决于处理器以及计算机硬件体系结构的设计,表示了处理器能够寻址的字节范围,与物理内存的大小无关.
地址空间概念的引入使得数据对象本身或数据对象的内容,与它们的地址分离开来,地址可以看作是数据对象的一个属性.
意识到这一点,就可以让一个数据对象具有多个独立的地址,每个地址来自不同的地址空间.
一个数据对象在不同地址空间中的地址可能不同,但是这些地址都指向同一个数据对象.
三个空间:磁盘地址空间:保存数据对象的磁盘存储介质的地址空间虚拟地址空间:处理器能够寻址/编址的地址空间物理地址空间:物理内存中所有字节物理地址构成的地址空间【例5-2】设一个可执行目标文件中代码段:.
text的地址范围是0x10~0x100,数据段:.
data的地址范围是0x101~0x200.
把它们分别加载到地址从0x8010到0x8100和0x9101~0x9200的物理内存中.
把.
text和.
data从文件加载到内存的过程,可以看作是把数据对象从文件地址空间映射到物理地址空间的过程.
5.
3.
3虚拟内存【定义2】(虚拟内存)(VM,VirtualMemory)虚拟内存是由N个连续的字节存储单元构成的一个数组,每个字节具有一个唯一的虚拟地址作为其索引,N是虚拟内存的大小.
虚拟内存与虚拟地址空间的关系是:虚拟内存在概念上是一个由连续字节存储单元构成的数组,而虚拟地址空间是虚拟内存中每一个字节的虚拟地址的集合;虚拟内存的大小和虚拟地址空间的大小是相同的.
比如,对于一个32位计算机系统,其虚拟内存和虚拟地址空间的大小都是4G.
由于虚拟内存和虚拟地址空间具有一一对应关系,因此,在以后的讨论中,我们通常不区分虚拟地址空间和虚拟内存,可以相互指代.
回顾5.
3.
3虚拟内存为了便于把虚拟内存映射到磁盘块和物理内存块,虚拟内存通常也被划分为固定大小的块,每一个这样的块被称为虚拟页面(VPs)(简称虚页),页面的大小为P=2p字节.
类似的,物理内存也被划分为P个字节大小的物理页面(PPs),或简称实页或页框/页帧(Pageframe).
通常虚拟页面的大小为4K,即p=12.
管理虚拟页面和物理页面(Page)——以页面(块)为单位进行管理计算:对于大小为4GB的虚拟内存,如果以4KB为一个页面大小.
可以划分出多少个虚页如果为每个虚页从0x0开始连续编址,可以编出多少个虚页地址地址为0x12345的虚页对应的字节地址范围虚拟地址为0x12345678的字节所在的虚拟页面地址有两个事实:1、同一页面内的字节地址的高20位是相同的2、同一页面内的字节地址的低12位总是从000~FFF,这段地址区域的大小恰好是4KB,即页面大小3、页面号恰好是该页面内字节地址的高20位基于此,1、我们用页面号(20位)或页面中首字节地址(32位)来表示页面地址.
二者的关系是:页面中首字节地址=虚拟地址=字节地址与页面号(地址)的关系地址空间的大小为2n页面大小为2p若已知字节地址(二进制)为:若已知页面地址(二进制)为:(0|1)n-p,则该页面内字节地址的范围是(0|1)n-p^0…0,(0|1)n-p^0…1,…,(0|1)n-p^1…15.
3.
3虚拟内存Allocate映射:虚拟内存空间(页面集合)---->磁盘空间(磁盘块集合).
该映射是一个偏函数,将虚拟内存中的一个页面映射到磁盘中的一个数据对象,该数据对象是一段连续字节的区段,这个区段可以是一个普通文件中的一个片段,也可以是磁盘中连续的磁盘块(或称为匿名文件,或Pagingfile).
如果已经建立了Allocate映射,说明虚拟内存中的一些(或全部)虚页已经分配给了磁盘中的数据对象,这时我们也可以把对应的磁盘空间称为虚拟内存的备份区(Backingstore).
Cache映射:把虚拟内存---->物理内存.
它也是一个偏函数,将一个虚拟页面映射到唯一的一个物理页面.
通过虚拟内存以及这两个映射,间接建立了磁盘空间与物理内存空间之间的关系.
当Cache映射发生变化时,说明一个数据对象从原来的物理页面移动到了另一个物理页面,从而实现了一个数据对象在内存中的上下浮动.
Allocate映射和Cache映射【例5-3】图5-14给出了一个虚拟内存与磁盘中的文件以及物理内存的映射关系.

通过Allocate映射和Cache映射,间接建立磁盘空间与物理内存的关系.
页面状态Allocate映射Cache映射说明Unallocated(未分配)未建立未建立该虚页还没有分配给一个磁盘数据对象,因此不占用磁盘上的任何空间.
如果程序访问该虚页中的指令或数据,那么就会出现非法(invalid)访问异常.
Cached(已缓存状态)已建立已建立该虚页已经分配给一个磁盘数据对象,而且已被缓存(或已加载)到一个的物理页面中.
Uncached(未缓存状态)已建立未建立该虚页已经分配给一个磁盘数据对象,但该数据对象还没有被换入(swapin)到一个物理页面中,仍然位于磁盘中.
--未建立已建立该状态不存在虚拟页面的状态5.
3.
4页表为了方便的描述Allocate和Cache映射,需要一个称为"页表"(PT,PageTable)的数据结构.
页表是一个由页表项(PTEs,PageTableEntries)组成的数组.
每个虚拟页面在页表中都对应一个页表项.
就目前而言(以后根据应用需求,还会对页表项进行扩充),每个页表项PTE包含一个1位标识位(validbit)、一个物理页面地址域和一个磁盘数据对象地址域.
标识位和地址域一起指示虚拟页面当前的状态.
页表虚拟内存VP0VP1VPNPTE0PTE1PTEN标识位物理页面地址域磁盘数据对象地址域【例5-4】图5-16用一个页表描述虚拟内存的映射状态.
在N+1个虚拟页面中,6个虚拟页面分别被分配给6个磁盘块(5号块~9号块),其中4个页面已经缓存在物理页面中.
其余虚拟页面均未分配.
A1234BCDEF56789101112PP0PP1PPMVP0VP1VPN磁盘空间虚拟内存物理内存001161350817500091710000000PTE0PTE1PTENPTE2PTE3PTE4PTE5PTE6PTE7VP2VP3VP4VP5VP6VP7PP2PP3PP4PP5PP6PP7BBAADCCEFF页表关于页表还需要注意以下几点:页表存储在物理内存中,占有一定存储空间.
对于一个n位虚拟地址空间,虚拟内存中虚拟页面的个数为2n-p个,那么页表中的页表项就有2n-p个.
如果一个页表项占用m个字节,那么页表总共占用m2n-p个字节.
页表的状态不是一成不变的.
如果操作系统把一个虚拟页面对应的磁盘数据对象换入(swapin)到了某个物理页面中,那么相应页表项的状态变化为如果操作系统把某个虚拟页面从物理页面中换出(swapout)到磁盘空间,那么对应的页表项状态变化为回顾虚拟VPA地址转换:1、求出vaddr对应的虚页号VPN和页内偏移VPOVPN=vaddr/PAGE_SIZEVPO=vaddr%PAGE_SIZEvaddr==2、以VPN为索引,查表中找到对应的页表项PTEifvalid-bit(PTE)=1,说明vaddr所在的虚页已经加载到物理页面中,那么:paddr=PPA+VPO,或=PPN*SIZE+VPOifvalid-bit(PTE)=0,说明vaddr所在的虚页还没有加载到物理页面中,那么中断当前正在执行的程序,把控制流转移到操作系统的缺页故障处理程序,该程序把虚页对应的磁盘数据加载到一个分配的物理页面中.
5.
3.
5虚拟地址转换和缺页故障(Pagefaults)处理在虚拟内存系统中,CPU不是直接用物理地址来访问程序指令和数据,而是先用虚拟地址访问虚拟内存,然后通过硬件地址转换机构MMU,把虚拟地址转换为物理地址,最后通过物理地址访问内存中的指令和数据.
为了判断一个虚拟页面(或物理页面)是否被修改过,通常需要在页表中增加一个变更位(Modifybit,或dirtybit),做了这样的扩充之后,页表项的结构变为:标识位磁盘数据对象地址域PTE变更位物理页面起始地址域在判断内存中是否存在空闲物理页面,以及从物理页面中选择一个将被换出的页面时,需要了解内存中物理页面的状态,我们用内存分配表BT(BlockTable)(或称块表)来描述这个状态.
与页表类似,BT也由若干表项BTE组成,每个表项BTEi描述物理页面PPi的空闲和占用状态,比如用1表示"占用",0表示"空闲".
注意:1、虚拟地址转换是由MMU硬件来完成,而缺页故障处理过程是由MMU硬件和操作系统软件共同来完成的:MMU硬件判断对应页表项的标志位,如果标志位为0,那么产生一个缺页故障,对缺页故障的处理由操作系统内核中的缺页故障处理例程来完成.
2、MMU在进程虚拟地址转换时,只需要用到页表中的部分列,如标志位和物理页面起始地址域(或物理页面号),而缺页故障处理过程中需要用到页表中另外一些列,如变更位和磁盘数据对象地址域等.
因此,在有些文献中,把缺页故障处理过程中用到的部分页表称为"软页表"(SoftwarePageTable).
【例5-4】考虑这样一个虚拟内存,虚拟地址用8位来表示,其中高3位表示虚拟页面号,低5位表示页面偏移.
虚拟内存以字节为单位进行编址和访问.
假设一个进程占用6个虚页,其页表如下:虚拟页面号有效位物理页面号变更位磁盘块号0140711702320--1310194151250--66未分配7未分配求虚拟内存的大小、页面大小和页面的个数写出每个页面的虚拟地址(用十六进制表示)范围如果程序计数器PC=0x25,在访问这条指令时是否会发生缺页故障如果不会,那么MMU把该地址转换成的物理地址是多少执行指令mov%eax,0xD1时,能否执行成功0x000x1F0x200x3F0x400x5FVP0VP1VP2VP3VP4VP5VP6VP70x600x7F0x800x9F0xA00xBF0xC00xDF0xE00xFF7231926虚拟页面号有效位物理页面号变更位磁盘块号0140711702320--1310194151250--66未分配7未分配5.
3.
6对内存管理需求的支持本章一开始,我们就对内存管理提出了可重定位、共享、保护和可扩充等四个基本需求.
虚拟内存的引入,可以使我们以一种非常一致、简洁和优雅的方式实现上面的需求.
(1)对重定位(上下浮动)的支持:VM+PT+动态地址变换(2)对私有和共享的支持:每个进程都有自己的页表+通过页表把自己的虚拟地址空间映射到不同的物理内存空间,以此来实现私有性和隔离性.
同时,不同进程也可以把自己虚拟地址空间中的部分虚页映射到同一物理页面,以此来实现进程间的共享.
(sharememory的实现)(3)对离散内存分配的支持:通过PT(4)对内存保护的支持:内存访问控制作用在虚拟内存的页面上,而不是物理内存上,由于虚拟内存布局是稳定的、一致的,因此内存保护容易实施.

(5)对存储器扩充的支持:运行时加载+部分加载5.
3.
7地址转换的硬件实现和加速地址转换的硬件实现符号描述N=2nn是虚拟地址的位数,N是虚拟地址空间的大小M=2mm是物理地址的位数,M是物理地址空间的大小P=2pP是页面大小(字节)VPO虚拟页面偏移量(字节)VPN虚拟页面号PPO物理页面偏移量(字节)PPN物理页面号VPOVPN虚拟地址0p-1pn-1PTBR标识位物理页面起始地址或PPNPPOPPN0p-1pm-1以VPN为索引,查找PTE页表如果valid-bit(PTE)==0,说明该页不在内存中,触发缺页故障如果valid-bit(PTE)==1物理地址设n位虚拟地址vaddr可以简记为vaddr=.
在页面命中情况下,虚拟地址转换过程可以表示为公式:paddr=其中,PT(VPN)表示以VPN为索引,在页表PT中找到对应的页表项PTE;address-field(PT(VPN))表示页表项PT(VPN)的物理页面地址或页面号.
【例5-5】给定一个32位虚拟地址空间和24位物理地址空间,页面大小为P=4KB.

求VPN,VPO,PPN和PPO的位数求虚拟页面和物理页面的个数把虚拟地址0x08048010转化为物理地址,其中页表为.
.
.
.
10x123.
.
.
.
0x080470x00000.
.
.
.
0x00001.
.
.
.
0x00002……0x08048…….
.
.
.
0xFFFFE标志位物理页面号CPU每产生一个虚拟地址,MMU就必须访问一次PTE以进行地址转换.
由于页表在内存中,地址转换过程会带来额外的内存访问,将花费数十到数百个周期.
为了加速地址转换过程,减小访问页表的开销,许多计算机系统在MMU中增加了一个称为"快表"(TLB,TranslationLookasideBuffer)的存储部件,用来缓存最近访问的部分页表项.
TLB的有效性基于程序局部性原理多级页表通常,我们采用多级页表来管理虚拟页面与物理页面的映射关系.
比如对于2级页表,第1级页表包括若干页表项,每个页表项的地址域指向第2级页表的基地址.
每个第2级页表的页表项的地址域指向物理页面的基地址.
通常我们把第1级页表称为"页目录",对应的页表项称为"页目录表项"(DTE,DirectoryTableEntry),第2级页表仍然称为页表.
与1级页表类似,每一级页表的页表项数目与虚拟地址的分段划分是一一对应的.
比如,对于图5-24所示的2级页表结构,它对应这样的虚拟地址划分:1.
根据DTN,在目录表DT中找到第2级页表的基址:DT(DTN)2.
根据VPN,在相应的第2级页表中找到对应的页表项:DT(DTN)(VPN)3.
获取页表项DT(DTN)(VPN)的地址域,即物理页面的基址:address-field(DT(DTN)(VPN))4.
然后将物理页面基址与VPO拼接,形成物理地址:paddr=给定一个虚拟地址vaddr=,可以通过如下步骤进行地址转换:分页管理回顾一个进程的映像(image)是什么时候被加载进物理内存的一个进程的映像要被完全加载到物理内存吗一个进程的映像要被连续加载物理内存吗一个进程要被换出(swapout)时,是部分换出还是完全换出当一个进程再次被换入时,一定要被换入到上一次被换出时的物理内存吗页表§5.
4分页式虚拟内存管理策略说明读取策略用于决定何时将一个虚拟页面换入内存.
常用的两种方法是:请求分页(Demandpaging):只有当访问到某虚页中的一个数据单元时才将该页换入内存.
预取分页(Prepaging):预测以后将要访问到的虚拟页面,并提前将这些页面取入内存.

驻留策略决定一个进程的虚拟地址空间驻留在(被缓存在)哪些物理页面.
对于分页管理来说,这个问题通常无关紧要,因为无论进程驻留在哪些物理页面,地址转换硬件和内存访问硬件都会以相同的效率访问到进程的数据.
置换策略当没有足够的空闲物理页面,需要把一个物理页面换出时,决定换出哪一个物理页面.

驻留集管理驻留集管理涉及两个问题:驻留集合大小:为每个活动进程分配多少物理页面才合理置换范围:当需要挑选一个物理页面被置换时,是在发生缺页故障的进程物理页面集合中挑选,还是在所有进程的物理页面集合中挑选,即局部置换还是全局置换.
换出策略换出策略与读取策略相反,它用于确定何时将一个修改过的页面写回磁盘.
通常有两种选择:请求式:只有当一个物理页面被挑选用于置换时,才被写回磁盘;预先式:将已修改的多个页面在需要用到它们所占的物理内存之前,成批的写回磁盘.

加载控制决定驻留在内存中进程的数目,或称为"系统并发度".
如果某一时刻,驻留的进程太少,所有进程同时处于阻塞状态的概率较大,则会有许多时间花费在交换上;另一方面,如果驻留的进程太多,平均每个进程占用的内存较少,就会发生频繁缺页故障,从而导致抖动.