操作系统内存管理

1,5.3覆盖与交换技术(内存扩充),问题的提出物理存储器物理存储器结构是一维的线性空间，容量有限。用户程序用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。解决办法内存扩充,2,实现内存扩充的方法：采用覆盖技术采用交换技术采用虚拟存储技术,3,覆盖技术将程序结构分层第0层设置为常驻内存区。第一层起，为该层中的多个模块设置一个共享覆盖区，其容量与该层中最大模块的容量相当。程序执行到哪个模块就将该模块送到它所共享的覆盖区中。,5.3.1覆盖技术,4,A、B、C、D、E、F总计190K，实际分配110K,5,采用交换技术在系统盘上开辟一个专门的空间作为内存的扩充，这部分磁盘空间称为“交换区”或“对换区”，由内存管理模块进行管理。交换区的作用是当内存空间不够时，将暂时不用的进程映像调到磁盘交换区，以腾出内存空间，当再度用到被调出的这部分进程映像时再将其调回内存。,5.3.2交换技术,6,交换技术,7,1虚拟存储器的基本思想问题作业在运行时暂时不用的程序和数据，全部驻留于内存中降低了内存利用率。解决方法当作业开始运行时，将当前使用的部分先装入内存，其余部分先存放在外存中，等到用到这些信息时，再由系统自动把它们装入到内存中，这就是虚拟存储器的基本思想。概念：虚拟存储器（虚拟内存）是操作系统采用虚拟技术，在不改变物理内存实际大小的情况下提供的逻辑上被扩充了的内存。这种物理上不具备而逻辑上具备的内存就是虚拟内存。,补充:虚拟存储技术,8,2.虚拟存储技术的依据局部性理论（8/2原理）时间局部性:是指程序即将用到的信息可能就是目前正在使用的信息。空间局部性:是指程序即将用到的信息可能与目前正在使用的信息在空间上相邻或者临近。局部性理论的应用意义虚拟存储管理：程序执行时往往会遵循局部原理(时间、空间)访问内存，将部分进程存入内存，结合外存实现虚拟存储。,9,3.虚拟存储技术的硬件技术基础相当数量的外存足以存放多个用户程序一定容量的内存程序运行过程中，必须有一部分放在内存地址变换机构实现逻辑地址到物理地址的变换,10,5.4页式管理5.4.1页式管理的基本原理,页式管理的引入分区存储管理的主要问题是碎片问题。问题描述在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户程序利用而浪费。问题产生原因作业要求分配的空间连续,主存有足够的空间但因不连续而不能分配解决问题的思路程序适应主存。将程序分开存放分页存储管理技术。,11,分页的思想页(虚拟页)：程序地址空间分成大小相等的页面块(内存块、页块、页祯、内存页面)：把内存分成与页面大小相等的块。思想：当一个用户程序装入内存时，针对。一每一页分配一个内存块个作业的若干连续的页，可以分配到内存中若干不连续的块中。,12,内存页面分配与回收页式存储管理的数据结构(1)页表:页表包括用户程序空间的页面与内存块的对应关系。页表每个进程至少一张。,5.4.2静态页面管理,13,(2)请求表:表明各进程与其分页的页面之间的关联。请求表整个系统一张。,图5.16请求表示例,14,(3)存储页面表：表示内存的分配情况。存储页面表一个系统一张，可用位示图表示。,图5.17位示图,15,5.4.2静态页面管理,2.分配算法利用页表、请求表、位示图进行分配。,图5.18页面分配算法流图,16,3.页式地址变换(1)虚地址（线性地址、逻辑地址）(2)分页地址映射机制虚地址切分：页号与页内位移划分页号和页内地址的依椐：页的大小。2X=页大小，X即为页号的最低位,CPU字长为16位，页长为1K的地址分割,17,第0页,第1页,0,1023,0,1023,1,页式管理的地址小结：页大小决定页内位移（地址）的位数，所以在地址划分时以页大小作为划分依据,页内地址,页大小为1K，以字节（B）为单位划分，可划分为1024个单位，进行编址，表示为0-1023，要表示1023需要10位二进制（1111111111），1KB=210B,18,19,(3)地址变换使用二进制方法求物理地址将逻辑地址线性分割求出页号P和页内位移W：若逻辑地址以十六进制、八进制的形式给出，将逻辑地址转换成二进制；按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）；将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应块号，将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,20,0,10,11,15,P=7H,W=3ADH,虚地址3BAD，页面大小2K，用二进制方法求物理地址,物理地址=5BADH,21,使用十进制方法求物理地址根据逻辑地址求出页号P和页内位移W；页号P=逻辑地址%页大小(%表示整除)页内位移W=逻辑地址mod页大小根据页号查页表得块号B；物理地址=块号B页大小+页内位移W公式说明物理地址块起始地址块内位移W块起始地址块长块号块长=页长块内位移页内位移,22,块起始地址计算,23,【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000101011111110P1W01011111110MR01001010111111104AFEH求虚地址1ADDH的物理地址：0001101011011101P3W01011011101MR00101010110111012ADDH,24,【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：转换虚地址3412：P341220481W3412mod20481364MR=9*2048+1364=19796转换虚地址7145：P714520483W7145mod20481001MR=5*2048+1001=11241问题：块号若为十六进制的字母表示，MR如何计算？(十六进制转换成十进制),例：考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址至少需要多少二进制位表示？（2）物理地址至少需要多少二进制位表示？,分析：逻辑地址结构由两个部分组成：前一部分表示该地址所在页面的页号P；后一部分表示页内地址(页内位移)W。物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。,解：因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（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转换成内存地址。,28,5.4.3动态页式管理(请求页式管理),复习:5.3覆盖与交换技术实现内存扩充的方法：采用覆盖技术采用交换技术采用虚拟存储技术常用的虚拟存储技术请求分页存储管理请求分段存储管理请求段页式存储管理,29,动态页式管理的思想及实现,分页内存管理方式静态分页管理动态分页管理静态分页管理基本思想：进程开始执行前，将全部页装入内存。动态分页管理（请求页式管理）基本思想：进程开始执行前，只需装入即将运行的页面，然后根据需要载入其他页面。,30,请求分页管理要解决的问题不在内存的页什么时候调入内存？（调入策略）如何知道要访问的页不在内存？不在内存的页在外存的什么地方？(页表)当页调入内存时，内存没有空闲块时，应覆盖（淘汰）哪些页？（淘汰策略）被覆盖（淘汰）的页是否需要回写到辅存？（页表）,31,请求页式管理的调入策略预测调页：分析预测，运行前调入系统根据作业运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。缺点:系统无法预计系统中作业的运行情况，难以实现。请求调页（请求分页）：缺页请求，运行时调入进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求将它所请求的页调入内存。,32,请求页式管理的页表结构页表：反映该页是否在内存，在外存的位置，在内存的时间的长短，是否需要回写等。页号：块号：中断位：0表示该页在内存，1示该页不在内存（需要缺页中断）辅存地址：该页在辅存的位置修改位：0表示该页调入内存后没有修改，1表示页调入内存后修改过引用位：0表示最近没有被访问，1表示最近被访问过,33,补充:多级页表,二级页表问题：页表占用存储空间太大解决：将页表也分页后，对页表占用的存储空间的分配也采用动态方式分配（部分分配），提高内存利用率。页表页：将页表分页，称为页表页，大小与页面长度相同。页目录表：为页表页建立的地址索引表称为页目录表。二级页表机制：页目录表是一级页表、页表页是二级页表，共同构成二级页表机制。,34,二级页表结构,35,具有二级页表的地址结构,36,二级页表机制的地址变换,37,5.4.4请求页式管理的页面置换算法,当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法。常用算法：先进先出算法FIFO：淘汰先调入内存的页最久未使用淘汰算法LRU：淘汰未被访问的页中时间最长的页最近未使用淘汰算法NUR：淘汰第1个最近未被访问的页（淘汰页表中第一个访问位为0的页）最不经常使用页面淘汰算法（LFU）：淘汰那些到当前时间为止访问次数最少的页。页表中增加一个访问记数器。最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。页面淘汰算法优劣的衡量标准：缺页中断率fffa（a是总的页面访问次数，f是缺页中断次数）,38,【例】一个进程已分到4个页帧（块）（M=4），其页表如下表所示，当进程访问第4页时产生缺页中断，请分别用FIFO、LRU、NRU算法决定将哪一页淘汰？是否需要回写？页表：页号页帧装入时间最近访问时间访问位修改位2060161011113016000022616210332016311FIFO：淘汰最先调入的页面（页帧为3的页）修改位为1，要回写。LRU：淘汰最久未访问的页（页帧为1的页）修改位为0，不要回写。NRU：淘汰最近未使用的页，淘汰第一个访问位为0的页（页帧为0的页）修改位为1，要回写。,39,【例】对访问串：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用FIFO（先进先出）和LRU（最久未使用）置换算法的缺页率，结果说明了什么？（设驻留集M表示分给该作业的内存块数）分析：,40,M=3，FIFO淘汰先调入内存的页,M=4，FIFO,41,刚被访问,最久未被访问,M=3，LRU淘汰最久未使用的页,M=4，LRU,调整顺序,42,解FIFO：M3ffa91275%M4f101283%LRU：M3ffa101283%M4ffa81267%Belady异常现象：对于FIFO算法，有时会出现当M增加时缺页次数不是减少，反而增加的现象。,43,课堂练习：设页面走向为：2、3、2、1、5、2、4、5、3、2、5、2，页帧M=3，试用FIFO和LRU两种算法分别计算访问过程中的缺页率。,44,补充:抖动,抖动主存和辅存之间的频繁的页面置换现象称为抖动，也称为颠簸，其导致系统效率急剧下降。产生抖动的原因：系统的淘汰算法不合理从而导致刚淘汰的页面马上又要访问的频繁的页面置换状态。系统在考虑置换算法时既要考虑有尽可能少的缺页率、置换算法的简单性、还要尽量避免系统抖动。,45,5.4.5页的共享与保护,页面共享（各进程中统一页号）,46,分页管理的存储保护有两种方式：一是由CPU提供的越界保护，当地址映射机构分离出页号和页内位移后，若0页号用户程序的总页数则访问合法，否则访问越界。二是由操作系统在页表中为页的存取权限设置的保护位，表示该页的存取控制权限，如r表示可读，w表示可读，e表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。,47,5.4.6页式管理的优缺点,优点：有效地解决了碎片问题；提供了内存和外存统一管理的虚拟存储器实现方式，使用户可以利用的存储空间大大增加。缺点：要求有相应的硬件支持；增加了系统开销（如缺页中断处理）；如置换算法选择不当，可能会产生抖动现象；每个进程的最后总有一部分空间得不到利用。,48,作业,习题：缺页次数及中断率的计算。在一个请求分页虚拟存储管理系统中，一个程序页面的访问序列是1、2、3、4、2、1、5、2、1、2、3、5、2、1、4、2、3。分别用FIFO和LRU算法，对分配给程序3个页框和4个页框的情况下，求出缺页次数和缺页中断率。,49,5.5分段内存管理段式管理的引入,问题的提出由于分页方式只考虑程序空间按页的尺寸切分，没有考虑各连续的页之间是否在逻辑上也是连续的。逻辑上的不连续导致请调一页，可能只用到该页中的一部分；不方便实现段的共享和保护。解决办法段式管理,保留程序在逻辑上的完整性,50,5.5.1段式管理的基本原理,段式管理原理作业：按逻辑意义分段内存分配段内在内存中连续各段在内存中可连续，也可不连续,51,段程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、数据等都可各成一段。每个段的大小可以不相等。逻辑地址程序中的逻辑地址由段号和段内位移两部分（二维）组成。段号将一个程序的所有逻辑段从0开始编号，称为段号。段内地址每一个逻辑段都是从0开始编址，称为段内地址。,5.5.2段式管理的实现原理,52,段式管理地址,53,段式管理的分配与回收参考动态分区管理段式管理中使用的数据结构段表：记录内存分配情况段表属性段号段首址段长中断位引用位改变位保护位段式管理地址映射机制由逻辑地址得到段号S和段内位移W；查段表得到物理起址B，加上W即得物理地址。,54,55,段的共享与保护,段的共享实现：段表中设置指向共享段的地址指针,56,段保护：地址越界保护：段起址物理地址段起址+段长段式管理中，地址越界引发的中断称为越段中断。但如果系统允许段动态增长，则应修改段表中的段长表项值。此时的段表数据结构如表所示。设置段的存取保护位:可读、可写、可执行等。相比较页的存取保护，段的存取保护更易于实现，解决了分页管理中由于页在逻辑上不具备逻辑完整性，当一页的内容涉及多个逻辑模块时，该页的存取控制难以实现的难题。,57,5.5.3分段的优缺点,分段的优缺点：见下分段和分页的比较不同（1）段根据用户的需要划分，便于存储保护和信息的共享；页是为了管理内存的方便而划分的，页的保护和共享受到限制。（2）页的大小固定不变，由系统决定；段的大小是不固定的，由其完成的功能决定。（3）段式提供的是二维地址空间；页式提供的是一维地址空间。（4）段式管理可能产生内存外碎片，页式管理消除了外碎片，但有页内碎片。,58,相同（5）段式与页式一样，都需要在进程运行前，全部信息装内存，内存利用不够充分。（6）段式与页式一样，为实现地址变换，CPU要花费较大的开销，为实现管理要提供更多的表格。（7）段式与页式一样，寻址都需要访问二次内存，如果要提高访问速度，都需要在相联存储器中设置快表。,59,请求段式管理的基本思想,段式存储也可实现虚拟存储管理，称为请求段式