存储器管理.pptx

<p>第四章第四章存储器管理存储器管理2024/3/26周二存储器管理24.14.1存储器的层次结构存储器的层次结构4.1.14.1.1多级存储器结构多级存储器结构4.1.24.1.2主存储器与寄存器主存储器与寄存器4.13.4.13.高速缓存和磁盘缓存高速缓存和磁盘缓存2024/3/26周二存储器管理3程序在成为进程前的准备工作程序在成为进程前的准备工作编辑：形成源文件编辑：形成源文件(符号地址符号地址)编译：形成目标模块编译：形成目标模块(模块内符号地址解析模块内符号地址解析)链接：由多个目标模块或程序库生成可执行文件链接：由多个目标模块或程序库生成可执行文件(模块间符号模块间符号地址解析地址解析)，形成一个装入模块，形成一个装入模块装入：由装入程序将装入模块装入内存，构造装入：由装入程序将装入模块装入内存，构造PCB，形成进，形成进程程(使用物理地址使用物理地址)将一个模块装入内存时，可采用三种方式：将一个模块装入内存时，可采用三种方式：绝对装入绝对装入可重定位装入可重定位装入动态装入动态装入2024/3/26周二存储器管理44.2 程序的装入和链接 编辑编辑编译编译链接链接装入装入运行运行图图4.12024/3/26周二存储器管理54.2.1 程序的装入 1、绝对装入：、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。时不再作地址重定位。绝对地址的产生：（绝对地址的产生：（1）由编译器完成，（）由编译器完成，（2）由程序）由程序员编程完成。员编程完成。对（对（1）而言，编程用符号地址。）而言，编程用符号地址。优点：装入过程简单，实现容易。优点：装入过程简单，实现容易。缺点：过于依赖于硬件结构，不适于多道程序系统。缺点：过于依赖于硬件结构，不适于多道程序系统。2024/3/26周二存储器管理62、可重定位装入、可重定位装入编译程序所生成的目标模块中采用逻辑地址，而地址映编译程序所生成的目标模块中采用逻辑地址，而地址映射是在装入模块装入内存时一次性进行的，即采用静射是在装入模块装入内存时一次性进行的，即采用静态重定位。态重定位。装入时完成，主要工作是对相对地址中的指令和数装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图据地址的调整过程，例：图42优点：不需硬件支持，可以装入有限多道程序。优点：不需硬件支持，可以装入有限多道程序。缺点：一个程序通常需要占用连续的内存空间，程序缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。装入内存后不能移动。不易实现共享。0100025005000LOAD 1,2500LOAD 1,250036536510000110001250015000作业地址空间作业地址空间内存空间内存空间图图4-24-2作业装入内存示意图作业装入内存示意图2024/3/26周二存储器管理83.动态运行时装入动态运行时装入将装入模块原样装入内存，而地址映射工作推迟到程序真将装入模块原样装入内存，而地址映射工作推迟到程序真正执行时才进行，即采用动态重定位。正执行时才进行，即采用动态重定位。优点：优点：OS可以将一个程序分散存放于不连续的内存空间，可可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变量（能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。而不仅是生成可执行文件时的地址引用）。缺点：缺点：需要硬件支持，需要硬件支持，OS实现较复杂实现较复杂。2024/3/26周二存储器管理94.2.2 程序的链接1、静态链接、静态链接a对相对地址的修改对相对地址的修改b变换外部调用符号变换外部调用符号2、装入时动态链接、装入时动态链接a.便于修改和更新便于修改和更新b.便于实现对目标模块的共享便于实现对目标模块的共享3、运行时动态链接、运行时动态链接a.执行时需要用到的模块才会被调入内存执行时需要用到的模块才会被调入内存b.加快程序的装入过程，节省大量的内存空间。加快程序的装入过程，节省大量的内存空间。模块模块ACALLB;RETURN模块模块BCALLC;RETURN模块模块CRETURN0L-10M-10N-1(a)目标模块目标模块模块模块AJSRL;RETURN模块模块BJSRL+M;RETURN模块模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块装入模块程序链接示意图程序链接示意图2024/3/26周二存储器管理114.3连续分配方式连续分配方式 单一连续分配单一连续分配用于单用户，单任务用于单用户，单任务OS中中分区式分配分区式分配固定式固定式可变式（动态）可变式（动态）可重定位分区分配可重定位分区分配2024/3/26周二存储器管理124.3.1单一连续分区单一连续分区系统区系统区系统区系统区用户区用户区用户区用户区 存贮保护存贮保护存贮保护存贮保护 一般不设置保护也可以，因单任务。一般不设置保护也可以，因单任务。一般不设置保护也可以，因单任务。一般不设置保护也可以，因单任务。2024/3/26周二存储器管理134.3.2固定分区固定分区特点：有特点：有n个分区，则可同时装入个分区，则可同时装入n个作业个作业/任务。任务。一、分区大小：一、分区大小：相等相等:不相等：不相等利用率更高。不相等：不相等利用率更高。二、内存分配：二、内存分配：数据结构数据结构将分区按大小排序，并将其地址、分配标识作将分区按大小排序，并将其地址、分配标识作记录记录例：例：dos的的MCB(memorycontrolblock)三、特点：三、特点：简单，分区大小固定，造成存储空间的浪费简单，分区大小固定，造成存储空间的浪费2024/3/26周二存储器管理14图图44a分区说明表分区说明表分区分区号号大小大小（KB)起址起址（KB）状态状态11220已分配已分配23232已分配已分配36464已分配已分配4128128已分配已分配操作系统操作系统作业作业A作业作业B作业作业C20KB32KB64KB128KB256KB0KB分配情况分配情况图图44b存储空间分配情况存储空间分配情况2024/3/26周二存储器管理152024/3/26周二存储器管理164.3.3可变式分区（比固定式分区有改善）可变式分区（比固定式分区有改善）一、数据结构一、数据结构1空闲分区表空闲分区表2空闲分区链空闲分区链前向指针前向指针N个字节可用个字节可用后向指针后向指针N+2N+2002024/3/26周二存储器管理17二、二、可变式分区分配算法分配算法1首次适应算法首次适应算法FF。要求：分区按低址要求：分区按低址高址链接高址链接特点：找到第一个大小满足的分区，划分。这特点：找到第一个大小满足的分区，划分。这种方案的出发点是尽量减少查找时间，它实现种方案的出发点是尽量减少查找时间，它实现简单。但低址内存使用频繁，有可能把大的空简单。但低址内存使用频繁，有可能把大的空闲分区分割成许多小的分区，因此对大作业有闲分区分割成许多小的分区，因此对大作业有利有弊。每次都从低址开始查找，增加了查找利有弊。每次都从低址开始查找，增加了查找的开销。的开销。2024/3/26周二存储器管理182循环首次适应算法。循环首次适应算法。从从1中上次找到的空闲分区的下一个开始中上次找到的空闲分区的下一个开始查找。查找。特点：空闲分区分布均匀，提高了查找速特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。度；缺乏大的空闲分区。2024/3/26周二存储器管理193最佳适应算法最佳适应算法要求：分区按大小递增形成空闲分区链。要求：分区按大小递增形成空闲分区链。特点：实行这种分配算法时，总是从当前特点：实行这种分配算法时，总是从当前所有空闲区中找出一个能够满足存储需求所有空闲区中找出一个能够满足存储需求的、最小的空闲分区作为分配的对象。能的、最小的空闲分区作为分配的对象。能保证大作业的需要。实现比较费时，麻烦保证大作业的需要。实现比较费时，麻烦。留下许多难以利用的小分区。留下许多难以利用的小分区。2024/3/26周二存储器管理204.4.最坏适应算法最坏适应算法挑选最大的空闲分区，挑选最大的空闲分区，优点：使剩下的空闲分区不至于太小，对中小优点：使剩下的空闲分区不至于太小，对中小作业有利，查找效率高。所有空闲分区按容量作业有利，查找效率高。所有空闲分区按容量大小形成空闲分区链。大小形成空闲分区链。缺点：是存储器中缺乏大的分区缺点：是存储器中缺乏大的分区2024/3/26周二存储器管理215.5.快速适应算法（分类搜索算法）快速适应算法（分类搜索算法）将空闲分区按容量大小进行分类，同类具有相将空闲分区按容量大小进行分类，同类具有相同容量，并为其单独设立一个空闲分区链，因同容量，并为其单独设立一个空闲分区链，因此系统中存在多个空闲分区链表，设立一张管此系统中存在多个空闲分区链表，设立一张管理索引表，每个表项对应一类空闲分区。理索引表，每个表项对应一类空闲分区。2024/3/26周二存储器管理22三、可变式分区分配操作三、可变式分区分配操作1分配：图分配：图4-62回收：图回收：图4-7（1）上邻空闲区：合并，无需分配新表项，）上邻空闲区：合并，无需分配新表项，只需修改大小只需修改大小（2）下邻空闲区：合并，改大小，首址。）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。根据首址插）不邻接，则建立一新表项。根据首址插入到空闲链表的适当位置。入到空闲链表的适当位置。图图4 4-6 6 内内存存分分配配流流程程2024/3/26周二存储器管理24F1回收区回收区回收区回收区F2F1回收区回收区F24-7内存回收时的情况内存回收时的情况F1回收区回收区F22024/3/26周二存储器管理254.3.4可重定位分区分配可重定位分区分配1.动态重定位的引入动态重定位的引入连续式分配中，总量大于作业大小的多个连续式分配中，总量大于作业大小的多个小分区不能容纳作业。小分区不能容纳作业。紧凑紧凑通过作业移动将原来分散的小分区拼接通过作业移动将原来分散的小分区拼接成一个大分区。成一个大分区。作业的移动需重定位。是动态（因作业作业的移动需重定位。是动态（因作业已经装入）已经装入）紧凑操作系统操作系统用户程序用户程序110KB用户程序用户程序330KB用户程序用户程序614KB用户程序用户程序926KB操作系统操作系统用户程序用户程序1用户程序用户程序3用户程序用户程序6用户程序用户程序980KB2024/3/26周二存储器管理272、动态重定位的实现load1,2500365load1,25003650100250050002500100001000010100+1250015000作业作业J处理机一侧处理机一侧存储器一侧存储器一侧重定位寄存器重定位寄存器相对地址相对地址主存主存2024/3/26周二存储器管理28图4.10动态重定位分区分配算法2024/3/26周二存储器管理294.3.5 对换1.对换的引入对换的引入将阻塞进程，暂时不用的程序，数据换出。将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。将具备运行条件的进程换入。类型：类型：整体对换：进程对换，解决内存紧张整体对换：进程对换，解决内存紧张部分对换：页面对换或分段对换：提供虚存支持部分对换：页面对换或分段对换：提供虚存支持2.对换空间的管理对换空间的管理外存外存对换区对换区比比文件区文件区侧重于对换速度。侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。可变化分区分配。2024/3/26周二存储器管理303.换出与换入换出与换入、换出、换出1选出被换出进程：选出被换出进程：因素：优先级，驻留时间，进程状态因素：优先级，驻留时间，进程状态2换出过程：换出过程：选出对换进程，启动磁盘，将对换进程的程序和数据传送到选出对换进程，启动磁盘，将对换进程的程序和数据传送到对换区。修改对换区。修改PCB和和MCB（或内存分配表）（或内存分配表）、换入：、换入：1选择换入进程：优先级，换出时间等。选择换入进程：优先级，换出时间等。2申请内存。申请内存。3换入换入2024/3/26周二存储器管理314.4 基本分页存储管理 连续分配引起连续分配引起:碎片碎片碎片问题的解决：紧凑方式消耗系统开碎片问题的解决：紧凑方式消耗系统开销。销。离散分配离散分配分页式、分段式、段页式分页式、分段式、段页式2024/3/26周二存储器管理321.页面页面页页面面和和物物理理块块：逻逻辑辑空空间间和和内内存存空空间间（物物理理空空间）间）由机器的地址结构决定由机器的地址结构决定页太大：减少了页表的长度，提高换入页太大：减少了页表的长度，提高换入/消除消除速度，页内碎片大。速度，页内碎片大。页太小：使内存碎片减小，减少了内存碎片页太小：使内存碎片减小，减少了内存碎片的总空间；但页表可能很长，换入的总空间；但页表可能很长，换入/出效率低出效率低4.4.1页面与页表2024/3/26周二存储器管理332.地址结构地址结构3112110逻辑地址逻辑地址A，页面的大小为，页面的大小为L，则页号，则页号P和页内偏移和页内偏移d可可按如下公式求得：按如下公式求得：P=INT(A/L)d=AmodL例：系统的页面大小为例：系统的页面大小为1KB，A2170B.则可求得则可求得P=2,d=1224.4.1页面与页表页面与页表页号页号P位移位移W2024/3/26周二存储器管理343.页表n n页页5 5页页4 4页页3 3页页2 2页页1 1页页0 0页页用户程序用户程序5 59 94 48 83 36 62 23 31 12 20 09 98 87 76 65 54 43 32 21 10 0页表页表页号页号 块号块号内存内存2024/3/26周二存储器管理354.4.2 地址变换机构 完成：逻辑地址完成：逻辑地址物理地址的转化物理地址的转化逻辑页号逻辑页号物理块号的映射，由页表完成。物理块号的映射，由页表完成。一、基本地址变换机构：一、基本地址变换机构：越界保护越界保护每个进程对应一页表，其信息（如长度、始每个进程对应一页表，其信息（如长度、始址）放在址）放在PCBPCB中，执行时将其首地址装入中，执行时将其首地址装入页表页表寄存器寄存器。2024/3/26周二存储器管理36返回2024/3/26周二存储器管理37例：例：一个一个3页长的进程具有页面号为页长的进程具有页面号为0，1，2，对应的页框（，对应的页框（块）号为块）号为4，5，9，页面长度（大小）为，页面长度（大小）为1KB，指令：，指令：LOAD2，2480；的虚拟（逻辑）地址为；的虚拟（逻辑）地址为200，如何确定最后的，如何确定最后的物理地址？物理地址？页号：页号：INT2480/1024=2;页内地址：页内地址：2480MOD1024=432(D);块的大小和页面大小相等，都是块的大小和页面大小相等，都是1024(D)；起；起-止块是止块是4-9物理地址物理地址=块内地址块内地址+页内地址页内地址,所以该进程（指令）起始物理地址所以该进程（指令）起始物理地址:4*1024+200=4296（D），即），即10C8(H)该进程（指令）的结束物理地址：该进程（指令）的结束物理地址：9*1024+432=9648(D)，即数据地址，即数据地址即：即：25B0(H)2024/3/26周二存储器管理38例例：某某虚虚拟拟存存储储器器的的用用户户编编程程空空间间共共32个个页页面面，每每页页为为1KB，内内存存为为16KB。假假定定某某时时刻刻一一用用户户页页表表中中已已调调入入内存的页面对应的物理块号如下表：内存的页面对应的物理块号如下表：问：逻辑地址问：逻辑地址0A5C（H）所对应的物理地址是多少？）所对应的物理地址是多少？页号页号物理块号物理块号0 05 51 110102 24 43 37 70A5C(H)=2652(D)页号页号:INT2652/1024=2，页内地址：页内地址：2652MOD1024=604(D)该页号对应的块号为该页号对应的块号为4，则块内地址为：，则块内地址为：4*1024=4096(D)因此物理地址因此物理地址=块内地址块内地址+页内地址页内地址即：即：4096+604=4700(D)即：即：0001,0010,0101,1100(B)即：即：125C（H）2024/3/26周二存储器管理392.具有快表的地址变换机构具有快表的地址变换机构 不具备快表，则需两次访问内存。不具备快表，则需两次访问内存。（1 1）访页表）访页表（2 2）得到绝对地址内容）得到绝对地址内容有快表，速度提高。有快表，速度提高。快表贵，不能太多。快表贵，不能太多。2024/3/26周二存储器管理402.具有快表的地址变换机构具有快表的地址变换机构2024/3/26周二存储器管理41 例：有一页式系统，其页表存放在主存中：例：有一页式系统，其页表存放在主存中：如果对主存的一次存取需要如果对主存的一次存取需要1.5 1.5 s,s,试问实现一次页面访问的存取时间是多少试问实现一次页面访问的存取时间是多少?(?(基本地址变换机构基本地址变换机构)对主存的一次存取时间还是对主存的一次存取时间还是1.5s1.5s，如果系统加有快表，如果系统加有快表,平均命中平均命中率为率为85%,85%,当页表项在快表中时当页表项在快表中时,其查找时间忽略为其查找时间忽略为0,0,试问此时的存取时间是多少试问此时的存取时间是多少?答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。才根据该地址存取页面数据。页表在主存的存取访问时间页表在主存的存取访问时间 =1.5*2=3(1.5*2=3(ss)增加快表后的存取访问时间增加快表后的存取访问时间 =0.85*1.5+(1-0.85)*2*1.5=1.725(s)0.85*1.5+(1-0.85)*2*1.5=1.725(s)2024/3/26周二存储器管理424.4.3 两级和多级页表 页表可能很大，将其离散存放在不同页块中。页表可能很大，将其离散存放在不同页块中。建一建一“外外部部页表页表”来管理这些离散页表块。来管理这些离散页表块。(P133)(P133)相当于单级相当于单级页表中页表中的页表寄存器，一般的页表寄存器，一般应常驻内存。每项记录页表始址，且增应常驻内存。每项记录页表始址，且增加存在位。加存在位。6464位机器页表一般位机器页表一般33级，最外层页表常驻内级，最外层页表常驻内存。存。2024/3/26周二存储器管理442024/3/26周二存储器管理464.5.2分段系统的基本原理分段系统的基本原理 分段分段分段是分段是2 2维的。维的。段号段号+段内地址。段内地址。段表：段表：逻辑段逻辑段mapmap物理段物理段地址变换机构：地址变换机构：图图4 41717分页与分段：分页与分段：（1 1）页是信息的物理单位，段是逻辑单位）页是信息的物理单位，段是逻辑单位（2 2）页长度固定，段长度不固定（由用户指定）页长度固定，段长度不固定（由用户指定）（3 3）一维与二维）一维与二维 2024/3/26周二存储器管理47图图4 41616利用分段实现地址映射利用分段实现地址映射40K80K120K150K2024/3/26周二存储器管理48页表2024/3/26周二存储器管理494.5.3共享共享 段式系统易于共享段式系统易于共享例：图例：图4-184-18及及4-194-19 分页与分段共享比较分页与分段共享比较可重入码（纯代码）可重入码（纯代码）P139P139各个进程应保留局部数据区各个进程应保留局部数据区例例：设设某某一一分分时时系系统统中中，现现有有40个个用用户户要要求求运运行行，每每个个用用户户都都要要求求执执行行正正文文编编辑辑程程序序，如如果果这这个个正正文文编编辑辑程程序序有有30KB代代码码并并且且每每个个用户在编辑时需要用户在编辑时需要10KB的数据区，这个系统必须提供的数据区，这个系统必须提供多少多少内存才能同时支持内存才能同时支持40个用户上机个用户上机？若采用页面共享（即编辑程序代码是可重入的），若采用页面共享（即编辑程序代码是可重入的），则则又需多少内存？又需多少内存？(10+30)40=1600kB104030=430KBed1ed2ed40data1data102122606170ed1ed2ed40data1data10data1data10进程进程1进程进程2页表页表页表页表ed1ed2ed40data1data102122607180主存4-18分页系统中共享分页系统中共享editor图4-19分段系统中共享分段系统中共享editoreditordata1editordata2段长段长基址基址1608040240段长段长基址基址1608040380editordata1data280280240380420进程进程2进程进程12024/3/26周二存储器管理52分段和分页的差异分段和分页的差异页和分段系统有许多相似之处，但在概念上两者完全不同，主要页和分段系统有许多相似之处，但在概念上两者完全不同，主要表现在：表现在：1、页是信息的物理单位，分页是为实现离散分配方式，以消减、页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，内存的外零头，提高内存的利用率；或者说，分页仅仅是由分页仅仅是由于系统管理的需要于系统管理的需要，而不是用户的需要。，而不是用户的需要。段是信息的逻辑单段是信息的逻辑单位，它含有一组其意义相对完整的信息。位，它含有一组其意义相对完整的信息。分段的目的是为了分段的目的是为了能更好的满足用户的需要。能更好的满足用户的需要。2、页的大小固定且由系统确定页的大小固定且由系统确定，把逻辑地址划分为页号和页内，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。种大小的页面。段的长度却不固定，决定于用户所编写的程段的长度却不固定，决定于用户所编写的程序，序，通常由编辑程序在对源程序进行编辑时，根据信息的性通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。质来划分。3、分页的作业地址空间是一维的分页的作业地址空间是一维的，即单一的线性空间，程序员，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。只须利用一个记忆符，即可表示一地址。分段的作业地址空分段的作业地址空间是二维的间是二维的，程序员在标识一个地址时，既需给出段名，又，程序员在标识一个地址时，既需给出段名，又需给出段内地址。需给出段内地址。2024/3/26周二存储器管理534.5.4段页式存储管理段页式存储管理分页优点：提高内存利用率分页优点：提高内存利用率分段优点：方便用户，易于共享，保护，动态链接。分段优点：方便用户，易于共享，保护，动态链接。一、段页式系统基本原理一、段页式系统基本原理段号段号+段内页号段内页号+页内地址页内地址注意：对用户而言，仍然是二维编址。对系统注意：对用户而言，仍然是二维编址。对系统而言，则是三维编址而言，则是三维编址 2024/3/26周二存储器管理54子程序段子程序段016K15K12K8K4K04K8K主程序段主程序段数据段数据段04K8K12K10K页内地址页内地址(d)段内页号段内页号(p)段号段号(s)图图4-20作业地址和地址结构作业地址和地址结构w2024/3/26周二存储器管理554.5.4段页式存储管理段页式存储管理二、地址变换二、地址变换三次访内存操作，为提高速度，在地址变换三次访内存操作，为提高速度，在地址变换机构中增设一高速缓冲寄存器（机构中增设一高速缓冲寄存器（Cache）2024/3/26周二存储器管理56图图4-21利用段表和页表实现地址映射利用段表和页表实现地址映射2024/3/26周二存储器管理57图图4-224-22段页式系统的地址变换机构段页式系统的地址变换机构2024/3/26周二存储器管理584.6虚拟存储器虚拟存储器4.6.1引入引入1.常规存储管理的特征：常规存储管理的特征：一次性（指全部装入）、一次性（指全部装入）、驻留性（指驻留在内存不换出）驻留性（指驻留在内存不换出）2、局部性原理、局部性原理时间局部性：一条时间局部性：一条指令指令的一次执行和下次执行，一个的一次执行和下次执行，一个数据数据的一次访问和下次访问都集中在一个较短时期内；如循环的一次访问和下次访问都集中在一个较短时期内；如循环执行执行空间局部性：当前指令和空间局部性：当前指令和邻近的几条指令邻近的几条指令，当前访问的数，当前访问的数据和据和邻近的数据邻近的数据都集中在一个较小区域内都集中在一个较小区域内。如顺序执行。如顺序执行。3、虚拟存储器、虚拟存储器定义定义具有请求调入功能和置换功能，能从逻辑上对内存容量进具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。行扩充的一种存储器系统。实质：以时间换空间，但时间牺牲不大。实质：以时间换空间，但时间牺牲不大。虚拟大小由内存容量和外存容量之和决定。虚拟大小由内存容量和外存容量之和决定。2024/3/26周二存储器管理594.6.2虚拟存储器的实现方式虚拟存储器的实现方式需要动态重定位需要动态重定位一、请求分页系统一、请求分页系统以页为单位转换以页为单位转换需硬件：需硬件：（1 1）请求分页的页表）请求分页的页表机制机制（2 2）缺页中断机构）缺页中断机构（3 3）地址变换机构）地址变换机构需实现请求分页机制的需实现请求分页机制的软件（置换软件等）软件（置换软件等）目前目前Intel80386以上处理芯片都支持段页式虚拟存储器以上处理芯片都支持段页式虚拟存储器。二、请求分段系统二、请求分段系统 以段为单位转换以段为单位转换:也需硬件支持：也需硬件支持：（1 1）请求分段的）请求分段的段表机制段表机制（2 2）缺段中断）缺段中断（3 3）地址变换机）地址变换机构构 需实现请求分段机需实现请求分段机制的软件（置换软件制的软件（置换软件等）等）2024/3/26周二存储器管理604.6.3虚拟存储器特征虚拟存储器特征1.离散性：内存空间离散分配；离散性：内存空间离散分配；2.多次性：局部装入，多次装入。多次性：局部装入，多次装入。3.对换性对换性：允许资源的换进换出：允许资源的换进换出4.虚拟性：逻辑上的扩充；虚拟性：逻辑上的扩充；2024/3/26周二存储器管理614.7.1请求分页中的数据结构及硬件支持请求分页中的数据结构及硬件支持一、页表机制一、页表机制页表项：页表项：二、缺页中断机构：可在指令执行期间产生（如图二、缺页中断机构：可在指令执行期间产生（如图4-23）转入缺页中断处理程序。转入缺页中断处理程序。三、地址变换机构三、地址变换机构比较简单分页机制，增加了中断处理，比较简单分页机制，增加了中断处理，图图4.244.7请求分页存储管理请求分页存储管理页号页号物理块号物理块号状态位状态位P P访问字段访问字段A A修改位修改位M M外存地址外存地址2024/3/26周二存储器管理62 图图423涉及涉及6次缺页中断的指令次缺页中断的指令2024/3/26周二存储器管理63图图4-24请请求求分分页页中中的的地地址址变变换换过过程程2024/3/26周二存储器管理644.7.2内存分配策略和分配算法内存分配策略和分配算法一、最小物理块数一、最小物理块数不同的作业要求不同。不同的作业要求不同。如：允许间接寻址：则至如：允许间接寻址：则至少要求少要求3个物理块。个物理块。MovA,B 2024/3/26周二存储器管理654.7.2内存分配策略和分配算法内存分配策略和分配算法二、页面分配和置换策略。二、页面分配和置换策略。1固定分配局部置换。固定分配局部置换。缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数.(少：置换率高少：置换率高多：浪费多：浪费)2.可变分配全局置换可变分配全局置换OS从内存任选一页调出，可能会增加缺页率从内存任选一页调出，可能会增加缺页率3.可变分配局部置换可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不根据进程的缺页率进行页面数调整，进程之间相互不会影响。会影响。换出的是本进程在内存中的页面。换出的是本进程在内存中的页面。2024/3/26周二存储器管理66三、分配算法三、分配算法 1 1平均分配算法（可能会增大缺页率或者产生浪费平均分配算法（可能会增大缺页率或者产生浪费）2 2按进程大小比例分配算法按进程大小比例分配算法（n n个进程，个进程，m m个内存块个内存块，每个进程的页面数，每个进程的页面数S Si i，每个进程分到的内存块数，每个进程分到的内存块数b bi i）3 3考虑优先权分配算法考虑优先权分配算法 （重要的实时控制系统）（重要的实时控制系统）2024/3/26周二存储器管理674.7.3页面调入策略页面调入策略 1.调入时机：调入时机：预调：（主要用于进程的首次调入）预调：（主要用于进程的首次调入）目前：成功率目前：成功率50，由程序员指出应该先调入哪些，由程序员指出应该先调入哪些页页请求调页：易于实现，较费系统开销请求调页：易于实现，较费系统开销各有优劣，虚拟存储器中大多采用请求调页各有优劣，虚拟存储器中大多采用请求调页2从何处调页：从何处调页：拥有足够的对换区：修改过的页被换出时入对换拥有足够的对换区：修改过的页被换出时入对换区，区，快快缺少足够的兑换区，利用文件区缺少足够的兑换区，利用文件区稍慢稍慢对共享页（对共享页（UNIX方式），应判断其是否在内存区。方式），应判断其是否在内存区。3.页面调入过程页面调入过程2024/3/26周二存储器管理684.8.1 4.8.1 最佳置换算法和先进先出算法最佳置换算法和先进先出算法一、最佳置换算法（理论上的）一、最佳置换算法（理论上的）4.8页置换算法页置换算法 2024/3/26周二存储器管理69假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，并考虑有以下的页并考虑有以下的页并考虑有以下的页并考虑有以下的页面号引用串：面号引用串：面号引用串：面号引用串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1 7 7 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1引引引引用用用用序序序序列列列列缺缺缺缺页页页页标标标标志志志志7 70 07 70 01 12 20 01 1F F2 20 01 12 20 03 3F F2 20 03 32 24 43 3F F2 24 43 32 24 43 32 20 03 3F F2 20 03 32 20 03 32 20 01 1F F2 20 01 12 20 01 12 20 01 17 70 01 1F F7 70 01 17 70 01 1缺页缺页缺页缺页6 6次，总访问次数次，总访问次数次，总访问次数次，总访问次数2020次，缺页率次，缺页率次，缺页率次，缺页率6/206/2030302024/3/26周二存储器管理704.8页置换算法页置换算法 二、二、FIFO2024/3/26周二存储器管理717 77 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1引用引用引用引用序列序列序列序列缺页缺页缺页缺页标志标志标志标志7 70 07 70 01 12 20 01 1F F2 20 01 12 23 31 1F F2 23 30 0F F4 43 30 0F F4 42 20 0F F4 42 23 3F F0 02 23 3F F0 02 23 30 02 23 30 01 13 3F F0 01 12 2F F0 01 12 20 01 12 27 71 12 2F F7 70 02 2F F7 70 01 1F F缺页缺页缺页缺页1212次，总访问次数次，总访问次数次，总访问次数次，总访问次数2020次，缺页率次，缺页率次，缺页率次，缺页率12/2012/2060602024/3/26周二存储器管理72Belady现象（异常）：现象（异常）：使用使用FIFO算法时，在给进程或作业未分配它足所要求算法时，在给进程或作业未分配它足所要求的页面数时，有时会出现分配的页面数增多，缺页次的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为数反而增加的奇怪现象。这种现象称为Belady现象现象页面页面“抖动抖动”：置换算法选择不当导致刚被换出的页面又被访问置换算法选择不当导致刚被换出的页面又被访问2024/3/26周二存储器管理734.8.2最近最久未用最近最久未用LRU置换置换一、算法描述一、算法描述将将“最近的过去最近的过去”，作为，作为“最近的将来最近的将来”。2024/3/26周二存储器管理741.LRU(LeastRecentlyUsed)1.LRU(LeastRecentlyUsed)置换算法的描述置换算法的描述置换算法的描述置换算法的描述 7 77 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1引用引用引用引用序列序列序列序列缺页缺页缺页缺页标志标志标志标志7 70 07 70 01 12 20 01 1F F2 20 01 12 20 03 3F F2 20 03 34 40 03 3F F4 40 02 2F F4 43 32 2F F0 03 32 2F F0 03 32 20 03 32 21 13 32 2F F1 13 32 21 10 02 2F F1 10 02 21 10 07 7F F1 10 07 71 10 07 7缺页缺页缺页缺页9 9次，总访问次数次，总访问次数次，总访问次数次，总访问次数2020次，缺页率次，缺页率次，缺页率次，缺页率9/209/2045452024/3/26周二存储器管理75一个进程的访问内存序列如下：一个进程的访问内存序列如下：101，511，604，170，273，309，185，445，246，434，658，364（1）若页尺寸为若页尺寸为100，给出访页踪迹。，给出访页踪迹。（2）若该进程的内存空间大小为若该进程的内存空间大小为300，采用，采用FIFO淘汰算法淘汰算法，那么缺页率是多少？，那么缺页率是多少？（3）若采用若采用LRU淘汰算法，给出缺页率。淘汰算法，给出缺页率。2024/3/26周二存储器管理76二、二、LRU算法的硬件支持：（用来记录谁最近最久未访问）算法的硬件支持：（用来记录谁最近最久未访问）1移位寄存器：（定时右移）移位寄存器：（定时右移）R=Rn-1R02栈：栈：当进程访问某页时，将其移出压入当进程访问某页时，将其移出压入</p>