操作系统内存管理分析

15.3覆盖与交换技术(内存扩充)•问题的提出•物理存储器•物理存储器结构是一维的线性空间，容量有限。•用户程序•用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。•解决办法•内存扩充2•实现内存扩充的方法：•采用覆盖技术•采用交换技术•采用虚拟存储技术3•覆盖技术•将程序结构分层•第0层设置为常驻内存区。•第一层起，为该层中的多个模块设置一个共享覆盖区，其容量与该层中最大模块的容量相当。程序执行到哪个模块就将该模块送到它所共享的覆盖区中。5.3.1覆盖技术4A、B、C、D、E、F总计190K，实际分配110K5•采用交换技术•在系统盘上开辟一个专门的空间作为内存的扩充，这部分磁盘空间称为“交换区”或“对换区”，由内存管理模块进行管理。•交换区的作用是当内存空间不够时，将暂时不用的进程映像调到磁盘交换区，以腾出内存空间，当再度用到被调出的这部分进程映像时再将其调回内存。5.3.2交换技术6交换技术7•1．虚拟存储器的基本思想•问题•作业在运行时暂时不用的程序和数据，全部驻留于内存中降低了内存利用率。•解决方法•当作业开始运行时，将当前使用的部分先装入内存，其余部分先存放在外存中，等到用到这些信息时，再由系统自动把它们装入到内存中，这就是虚拟存储器的基本思想。•概念：虚拟存储器（虚拟内存）•是操作系统采用虚拟技术，在不改变物理内存实际大小的情况下提供的逻辑上被扩充了的内存。这种物理上不具备而逻辑上具备的内存就是虚拟内存。补充:虚拟存储技术8•2.虚拟存储技术的依据•局部性理论（8/2原理）•时间局部性:是指程序即将用到的信息可能就是目前正在使用的信息。•空间局部性:是指程序即将用到的信息可能与目前正在使用的信息在空间上相邻或者临近。•局部性理论的应用意义•虚拟存储管理：程序执行时往往会遵循局部原理(时间、空间)访问内存，将部分进程存入内存，结合外存实现虚拟存储。9•3.虚拟存储技术的硬件技术基础•相当数量的外存•足以存放多个用户程序•一定容量的内存•程序运行过程中，必须有一部分放在内存•地址变换机构•实现逻辑地址到物理地址的变换105.4页式管理5.4.1页式管理的基本原理页式管理的引入•分区存储管理的主要问题是碎片问题。•问题描述在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户程序利用而浪费。•问题产生原因•作业要求分配的空间连续,主存有足够的空间但因不连续而不能分配•解决问题的思路•程序适应主存。将程序分开存放—分页存储管理技术。11•分页的思想•页(虚拟页)：程序地址空间分成大小相等的页面•块(内存块、页块、页祯、内存页面)：把内存分成与页面大小相等的块。•思想：当一个用户程序装入内存时，针对。一每一页分配一个内存块个作业的若干连续的页，可以分配到内存中若干不连续的块中。121.内存页面分配与回收•页式存储管理的数据结构•(1)页表:页表包括用户程序空间的页面与内存块的对应关系。页表每个进程至少一张。5.4.2静态页面管理13•(2)请求表:表明各进程与其分页的页面之间的关联。请求表整个系统一张。图5.16请求表示例14•(3)存储页面表：表示内存的分配情况。存储页面表一个系统一张，可用位示图表示。图5.17位示图155.4.2静态页面管理•2.分配算法•利用页表、请求表、位示图进行分配。图5.18页面分配算法流图163.页式地址变换(1)虚地址（线性地址、逻辑地址）(2)分页地址映射机制•虚地址切分：页号与页内位移•划分页号和页内地址的依椐：页的大小。•2X=页大小，X即为页号的最低位CPU字长为16位，页长为1K的地址分割17movdx,3badh…………页号01234567第0页第1页01023010231…页式管理的地址小结：页大小决定页内位移（地址）的位数，所以在地址划分时以页大小作为划分依据页内地址页大小为1K，以字节（B）为单位划分，可划分为1024个单位，进行编址，表示为0-1023，要表示1023需要10位二进制（1111111111），1KB=210B18二进制表示虚地址页号页内位移十六进制表示页号、页内位移19(3)地址变换•使用二进制方法求物理地址①将逻辑地址线性分割求出页号P和页内位移W：•若逻辑地址以十六进制、八进制的形式给出，将逻辑地址转换成二进制；•按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）；②将位移量直接复制到内存地址寄存器的低位部分；③以页号查页表，得到对应块号，将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。20movdx,3badh页号01234567页号块号0F18233549546A7B0011101110101101块号OS0123456798BACD~~0101115P=7HW=3ADH00000101101110101101虚地址3BAD，页面大小2K，用二进制方法求物理地址物理地址=5BADH21•使用十进制方法求物理地址•根据逻辑地址求出页号P和页内位移W；•页号P=逻辑地址%页大小(%表示整除)•页内位移W=逻辑地址mod页大小•根据页号查页表得块号B；•物理地址=块号B×页大小+页内位移W•公式说明•物理地址＝块起始地址＋块内位移W•块起始地址＝块长×块号块长=页长•块内位移＝页内位移22块号OS0123456798BACD~~第0块起始地址：0第1块起始地址：块号*页长=1*2K块大小：2K02K4K第2块起始地址：块号*页长=2*2K块起始地址计算movdx,3badh…………页号0123456723【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000101011111110P＝1W＝01011111110MR＝0100101011111110＝4AFEH求虚地址1ADDH的物理地址：0001101011011101P＝3W＝01011011101MR＝0010101011011101＝2ADDH24【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：转换虚地址3412：P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796转换虚地址7145：P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241问题：块号若为十六进制的字母表示，MR如何计算？(十六进制转换成十进制)例：考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址至少需要多少二进制位表示？（2）物理地址至少需要多少二进制位表示？分析：逻辑地址结构由两个部分组成：前一部分表示该地址所在页面的页号P；后一部分表示页内地址(页内位移)W。物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。解：因为页面数为8=2^3，故需要3位二进制数表示。每页有1024个字节，1024=2^10，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=2^5）。（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。26相联存储器和快表•问题提出•在页式存储技术中，每访问一次内存，就要做两次访问内存的工作：•查页表时（页表在内存中）；•访问程序时。•为了提高查页表的速度，将当前常用的一部分页表内容存放到高速缓存（相联存储器）中，存放在相联存储器中的页表称之为快表(TLB-translationlookasidebuffer)。•查表时首先在快表中查，只有当快表中没有时才访问内存中的页表，从而减少在内存查表的次数，达到提高查找速度的目的。27作业•习题：P134:5.2,•物理地址计算•有一系统采用页式存储管理，某个作业大小是4GB，页大小为4KB，依次装入内存的第6、5、3、2块，•（1）画出页表；•（2）试将虚地址5000，12000转换成内存地址。285.4.3动态页式管理(请求页式管理)•复习:5.3覆盖与交换技术•实现内存扩充的方法：•采用覆盖技术•采用交换技术•采用虚拟存储技术•常用的虚拟存储技术•请求分页存储管理•请求分段存储管理•请求段页式存储管理29动态页式管理的思想及实现•分页内存管理方式•静态分页管理•动态分页管理•静态分页管理•基本思想：进程开始执行前，将全部页装入内存。•动态分页管理（请求页式管理）•基本思想：进程开始执行前，只需装入即将运行的页面，然后根据需要载入其他页面。30•请求分页管理要解决的问题•不在内存的页什么时候调入内存？（调入策略）•如何知道要访问的页不在内存？不在内存的页在外存的什么地方？(页表)•当页调入内存时，内存没有空闲块时，应覆盖（淘汰）哪些页？（淘汰策略）•被覆盖（淘汰）的页是否需要回写到辅存？（页表）31•请求页式管理的调入策略•预测调页：分析预测，运行前调入•系统根据作业运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。•缺点:系统无法预计系统中作业的运行情况，难以实现。•请求调页（请求分页）：缺页请求，运行时调入•进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求将它所请求的页调入内存。32•请求页式管理的页表结构•页表：反映该页是否在内存，在外存的位置，在内存的时间的长短，是否需要回写等。•页号：•块号：•中断位：0表示该页在内存，1示该页不在内存（需要缺页中断）•辅存地址：该页在辅存的位置•修改位：0表示该页调入内存后没有修改，1表示页调入内存后修改过•引用位：0表示最近没有被访问，1表示最近被访问过页号块号中断位辅存地址修改位引用位请求分页的页表结构……33补充:多级页表•二级页表•问题：页表占用存储空间太大•解决：将页表也分页后，对页表占用的存储空间的分配也采用动态方式分配（部分分配），提高内存利用率。•页表页：将页表分页，称为页表页，大小与页面长度相同。•页目录表：为页表页建立的地址索引表称为页目录表。•二级页表机制：页目录表是一级页表、页表页是二级页表，共同构成二级页表机制。34二级页表结构35具有二级页表的地址结构36二级页表机制的地址变换375.4.4请求页式管理的页面置换算法•当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法。•常用算法：•先进先出算法FIFO：淘汰先调入内存的页•最久未使用淘汰算法LRU：淘汰未被访问的页中时间最长的页•最近未使用淘汰算法NUR：淘汰第1个最近未被访问的页（淘汰页表中第一个访问位为0的页）•最不经常使用页面淘汰算法（LFU）：淘汰那些到当前时间为止访问次数最少的页。页表中增加一个访问记数器。•最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。•页面淘汰算法优劣的衡量标准：缺页中断率f’•f’＝f／a（a是总的页面访问次数，f是缺页中断次数）38【例】一个进程已分到4个页帧（块）（M=4），其页表如下表所示，当进程访问第4页时产生缺页中断，请分别用FIFO、LRU、NRU算法决定将哪一页淘汰？是否需要回写？页表：页号页帧装入时间最近访问时间访问位修改位2060161011113016000022616210332016311FIFO：淘汰最先调入的页面（页帧为3的页）∵修改位为1，∴要回写。LRU：淘汰最久未访问的页（页帧为1的页）