4.4 页式存储管理

第四章存储器管理4.1概述4.2存储管理的功能4.3分区存储管理4.4页式存储管理4.5段式存储管理4.6段页式存储管理4.7UNIX系统的存储管理4.4页式存储管理分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的空闲分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是连续装入的，为解决这个问题，提出了分页存储管理技术。4.4.1页式系统应解决的问题一、问题的提出二、分页的概念程序地址空间分成大小相等的页面，同时把内存也分成与页面大小相等的块，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是为2n,通常为1KB，2KB，nKB等。页式存储管理要解决如下问题：1、地址映射；2、调入策略；3、淘汰策略；4、放置策略。4.4.2页式地址变换一、页表页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。页号内存块号存取控制状态其它7页6页5页4页3页2页1页0页用户程序……11109876543210内存1191076425块号76543210页号页表页号页内地址（位移量）PW151090二、虚地址结构虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。假定页面大小1024字节，虚地址共占用2个字节(16位)页表寄存器页表长度页表起址程序地址L页内地址W页号（P=2）越界6425块号3210页号页表WP’=4物理地址WP程序地址P’P页表拼接P’+W内存三、页式地址映射1.虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出将虚地址转换成二进制的数；按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；根据题意产生页表；将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。2.虚地址以十进制数给出页号＝虚地址％页大小位移量＝虚地址mod页大小根据题意产生页表；以页号查页表，得到对应页装入内存的块号内存地址＝块号×页大小＋位移量例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。虚地址0AFEH0000101011111110P＝1W＝01011111110MR＝0100101011111110＝4AFEH例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796练习在分页存储管理系统中，有一作业大小为4页，页长为2K，页表如下。试借助地址变换图（即要求画出地址变换图）求出逻辑地址0x095C所对应的物理地址。页号块号05132736解答31637250块号页号00101011100000010010101110000011页表首址+010物理地址为：0x195C在页式存储技术中，每访问一次内存，就要做两次访问内存的工作，即查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。在早期的计算机系统中有的采用联想存储器的技术来加快查表的速度，有的采用寄存器做页表。四、采用相应技术加快页表的查询速度具有快表的地址变换机构：快表：将页表中作业运行最常用的部分放入快表。页表寄存器页表长度页表起址程序地址L页内地址w页号p越界页表65p’块号43210页号p’块号41253页号快表输入寄存器wp’物理地址例:设访问内存的时间为200ns，访问快表（高速缓冲）的时间为40ns，如果快表命中率为90%，则将逻辑地址转换成物理地址进行内存访问的平均时间为：40*90%+200*10%+200=256ns。不用快表时，需访问两次内存，需要200*2=400ns。4.4.3请调策略一、问题的提出在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。二、请求分页概念请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。一、程序的局部性原理在一段小的时间间隔内，被访问过的某指令或数据，很快会被再次访问（时间局部性）；作业访问的地址空间往往集中在某个区域（空间局部性）。二、虚拟存储器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充。实际容量由内存和外存之和决定。速度接近于内存，每位的成本接近于外存。虚拟存储器三、请求分页要解决的问题1、如何发现执行的程序或访问的数据不在内存；2、程序或数据什么时候调入内存，调入策略；3、当一些页调入内存时，内存没有空闲内存时，将淘汰哪些页，淘汰策略。四、数据结构为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。中断位：0表示该页在内存，1表示该页不在内存引用位：0表示最近没有进程访问1表示最近有进程访问修改位：0该页调入内存后没有修改1表示页调入内存后修改过五.调入策略1、预调系统根据作业（进程）运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。这样方法从表面上看起来很好，但系统无法预计系统中作业的运行情况，难以实现。2、请调进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。4.4.4淘汰策略一、置换算法当要索取一页面并送入到内存，但此时该作业所分得的内存块已全部用完时，必须把它已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。二、颠簸内存和外存之间的频繁的页面置换现象，将会导致系统效率急剧下降。假定程序p共有n页，而系统分配给它的内存只有m块（1≤m≤n），并且以作业在执行的过程中页面置换的频率的高低来衡量算法的优劣。访问的页在内存，称访问成功，否则为失败。a=s+fa:访问的总次数s：访问成功的次数f：访问失败的次数缺页中断率f’=f/a则有：f’＝f(r,m,p）4.4.5几种置换算法最佳算法是指对于任何m和p，r，调度算法有f’＝f(r,m,p）最小。最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。原因？一、最佳算法例：某进程可占用3个内存块，页面引用顺序如下：缺页率=缺页次数/访问次数=7/12=58.3%512345341234引用串X512X532534534X534134134X134X234X34X4缺页：块理物5127次1259次X125X325345345X345X341X241X231X234X34X4缺页：块理物512345341234引用串二、先进先出算法先进入内存的页，先退出内存。实质上是淘汰在内存驻留时间最长的页。其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。这种算法简单，实现容易。X201231X231230230X230X234X204X304302X302102X102X107X07X7缺页：块：理物10212303240302107引用串2018次三、最久未使用淘汰算法（LRU算法）算法的实质：当需要淘汰一页时，选择最长时间未使用的页。依据的理论是如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。置换时顺序查找页面链，R=0，淘汰该页；R=1，将R置0，替换指针前移。下次淘汰时，从替换指针处开始查找。页号块号访问位1112130405160718替换指针四、Clock置换算法（LRU近似）每页页表项设一访问位某页被访问时，其访问位置1；某进程的所有页面排成一循环链；内存中的所有页面排成一循环链；某页被访问时，其访问位R置1；被修改时，其修改位M置1。页号块号访问位R修改位M页号内存块号访问位修改位0……011……102……113……004……015……10在最近的一个时钟周期（如20ms）内，访问过页1、2、5。自装入内存后，修改过页0、2、4。每页页表项设一访问位和修改位改进的Clock算法有四类页面：①R=0，M=0（最佳淘汰页）②R=0，M=1③R=1，M=0④R=1，M=1（最不该淘汰）将找到的第一页淘汰将找到的第一页淘汰扫描循环链，查找R=0，M=0的页面未找到扫描，查找R=0，M=1的页面，同时令所有经过的页面的R=0未找到五、最不经常使用淘汰算法（LFU算法）算法的实质：当需要淘汰一页时，选择最近应用次数最少的页。Belady异常现象：一般地，分配的内存页面越多，则缺页次数越少。但在FIFO算法中：有时分配的页面数越多，缺页次数越多。例：访问串012301401234物000333444444理11100000222块：2221111133缺页：XXXXXXXXX访问串012301401234物000000444433理11111100004块：2222221111333333222缺页：XXXXXXXXXX9次10次4.4.6页式系统的存储保护页式系统的存储保护的方法类似于基址限长存储保护，当地址映射机构分离出页号和页内位移后。若0≤页号＜用户程序的总页数，则访问合法，否则访问越界。页式系统的存储保护还包括存取控制。在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。4.5段式存储管理一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。程序地址的组成：S：W例:S1：XXXXS2：XXXXS3；XXXX3、数据结构的设置段表：每个进程一个段表。段表结构如下：内存分配表：同分区式管理。段号段的内存起址段长2、段式管理的内存分配与释放：每段要求一个连续的内存区，所以其分配和回收算法类似于分区管理，如FF，BF，WF，相邻区合并。1、分段与分页的区别：•段是信息逻辑单位，页是物理单位（长度）。•段长不固定，页等长；页号连续，段号间无顺序关系。•段式作业地址空间是二维的，页式地址空间是一维的。4、地址变换过程程序地址L段内地址d段号S越界段表寄存器段表长度段表起址段表SL段长SB段首址3210段号SL段长SB段首址1023段号快表输入寄存器SB+d物理地址d=SL越界WS程序地址S段内存起址S’S段表S’+W内存地址例：load1，[X]|Y=load1，[1]|200段表2048+2002248内存地址段号装入位段长起址0Y1K7K1Y4K2K即：0000100000000000+0000000011001000=000000000000000000001000110010005、请求分段存储管理方式基本思想：当发生缺段中断时，内外存的交换是以段为单位的。淘汰段时，可能需要淘汰多个段才能满足需要。段表项：段名段长段的内存起址存取权限访问字段修改位存在位扩充位外存地址存取权限：本段的存取权限是可写、只读或执行。访问字段：指示最近被访问次数或距上次访问的时间间隔。扩充位：指示此段是否已动态增长。缺段中断：在一条指令