计算机操作系统 存储器管理

1、v 编辑编辑编译编译链接链接装入装入运行运行v 图图4.14.1v 1 1、绝对装入：、绝对装入： 编译后，装入前已产生了绝对地址（内存地址），装编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。入时不再作地址重定位。 绝对地址的产生：（绝对地址的产生：（1 1）由编译器完成，（）由编译器完成，（2 2）由程序）由程序员编程完成。员编程完成。 对（对（1 1）而言，编程用符号地址。）而言，编程用符号地址。v 2 2、可重定位装入；、可重定位装入； 静态重定位：装入时完成，主要工作是对相对地址中静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图的指

2、令和数据地址的调整过程，例：图4 42 2 问题：问题： 如何知道哪些位置需调整？如何知道哪些位置需调整？ 链接时产生可装入模块的具体功能链接时产生可装入模块的具体功能? ?0100025005000LOAD 1, 2500LOAD 1, 250036536510000110001250015000作业地址空间作业地址空间内存空间内存空间图图4-2v 3.3.动态运行时装入动态运行时装入 在装入后不能移动，在装入后不能移动， 该情况一般在执行时才完成相对该情况一般在执行时才完成相对绝对地址的转换绝对地址的转换且有硬件的支持且有硬件的支持, ,能保证进程的可移动性。能保证进程的可移动性。v 1

3、1、静态链接、静态链接 a a对相对地址的修改对相对地址的修改 b b变换外部调用符号变换外部调用符号v 2 2、装入时动态链接、装入时动态链接 a.a.便于修改和更新便于修改和更新 b.b.便于实现对目标模块的共享便于实现对目标模块的共享v 3 3、运行时动态链接、运行时动态链接模块模块A ACALL B;CALL B;RETURNRETURN模块模块B BCALL C;CALL C;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-10 0M-1M-10 0N-1N-1(a)(a)目标模块目标模块模块模块A AJSR L;JSR L;RETURNRETURN模块

4、模块B BJSR L+M;JSR L+M;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-1L LL+M-1L+M-1L+ML+ML+M+N-1L+M+N-1(b)(b)装入模块装入模块v 单一连续分配单一连续分配 用于单用户，单任务中用于单用户，单任务中v 分区式分配分区式分配 固定式固定式 可变式可变式 可重定位分区分配可重定位分区分配 v 特点：有特点：有n n个分区，则可同时装入个分区，则可同时装入n n个作业个作业/ /任务。任务。v 一、分区大小：一、分区大小： 相等相等: : 不相等：不相等利用率更高。不相等：不相等利用率更高。v 二、内存分配：二、

5、内存分配： 数据结构数据结构 将分区按大小排序，并将其地址、分配标识作记录将分区按大小排序，并将其地址、分配标识作记录 例：例：dosdos的的MCBMCBv 三、特点：三、特点： 简单，有碎片（内零头）简单，有碎片（内零头）分区号分区号 大小（大小（K)起址（起址（K）状态状态11220已分配已分配23232已分配已分配36464已分配已分配4128128已分配已分配操作系统操作系统作业作业A A作业作业B B作业作业C C24K32K64K128K256K分配情况分配情况v 一、数据结构一、数据结构1 1 空闲分区表空闲分区表2 2 空闲分区链空闲分区链前向指前向指针针N N个字节可用个字

6、节可用后向指后向指针针N+2N+2N+2N+20 0（分配（分配标识）标识）0 0v 二、分配算法二、分配算法1 1 首次适应算法首次适应算法FFFF。 要求：分区按低址要求：分区按低址高址链接高址链接 特点：找到第一个大小满足的分区，划分。有外零头，特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。低址内存使用频繁。2 2 循环首次适应算法。循环首次适应算法。 从从1 1中上次找到的空闲分区的下一个开始查找。中上次找到的空闲分区的下一个开始查找。 特点：空闲分区分布均匀，提高了查找速度；缺乏大特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。的空闲分区。3 3 最佳适

7、应算法最佳适应算法 分区按大小递增排序；分区释放时需插入到适当位置。分区按大小递增排序；分区释放时需插入到适当位置。v 三、分区分配三、分区分配1 1 分配：图分配：图4-64-62 2 回收：回收： （1 1）上邻空闲区：合并，改大小）上邻空闲区：合并，改大小 （2 2）下邻空闲区：合并，改大小，首址。）下邻空闲区：合并，改大小，首址。 （3 3）上、下邻空闲区：合并，改大小。）上、下邻空闲区：合并，改大小。 （4 4）不邻接，则建立一新表项。）不邻接，则建立一新表项。F1F1回收区回收区回收区回收区F2F2F1F1回收区回收区F2F24-7 4-7 内存回收时的情况内存回收时的情况v 1.

8、1.动态重定位的引入动态重定位的引入 连续式分配中，总量大于作业大小的多个小分连续式分配中，总量大于作业大小的多个小分区不能容纳作业。区不能容纳作业。 紧凑紧凑 通过作业移动将原来分散的小分区拼接成一通过作业移动将原来分散的小分区拼接成一个大分区。个大分区。 作业的移动需重定位。是动态（因作业已经作业的移动需重定位。是动态（因作业已经装入）装入）操作系统操作系统用户程序用户程序1 110kb10kb用户程序用户程序3 330kb30kb用户程序用户程序6 614kb14kb用户程序用户程序9 926kb26kb操作系统操作系统用户程序用户程序1 1用户程序用户程序3 3用户程序用户程序6 6用

9、户程序用户程序9 9load 1,2500load 1,2500365365load 1,load 1,250025003653650 0100100250025005000500025002500100001000010000100001010010100+ +12500125001500015000作业作业J J处理机一侧处理机一侧存储器一侧存储器一侧重定位寄存器重定位寄存器相对地址相对地址v 1 1 对换的引入对换的引入 将阻塞进程，暂时不用的程序，数据换出。将阻塞进程，暂时不用的程序，数据换出。 将具备运行条件的进程换入。将具备运行条件的进程换入。 类型：类型： 整体对换：进程对换，解

10、决内存紧张整体对换：进程对换，解决内存紧张 部分对换：页面对换部分对换：页面对换/ /分段对换：提供虚存支持分段对换：提供虚存支持v 2 2 对换空间的管理对换空间的管理 外存外存 对换区对换区比比文件区文件区侧重于对换速度。侧重于对换速度。 因此，对换区一般采用连续分配。采用数据结构和因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。分配回收类似于可变化分区分配。v 3 3 换出与换入换出与换入 一、换出一、换出 1 1选出被换出进程：选出被换出进程：因素：优先级，驻留时间，进程状态因素：优先级，驻留时间，进程状态 2 2换出过程：换出过程：对于共享段：计数减对于共享

11、段：计数减1 1， 是是0 0则换出，否则不换则换出，否则不换修改修改PCBPCB和和MCBMCB（或内存分配表）（或内存分配表） 二、换入：二、换入： 1 1选择换入进程：优先级，换出时间等。选择换入进程：优先级，换出时间等。 2 2申请内存。申请内存。 3 3换入换入v 连续分配引起连续分配引起: :碎片碎片v 碎片问题的解决：紧凑方式消耗系统开销。碎片问题的解决：紧凑方式消耗系统开销。v 离散分配离散分配 分页、分段、段页分页、分段、段页v 1.1.页面页面 页面和物理块：逻辑空间和内存空间页面和物理块：逻辑空间和内存空间 由机器的地址结构决定由机器的地址结构决定 页太大，页内碎片大。页

12、太大，页内碎片大。 页太小：页表可能很长，换入页太小：页表可能很长，换入/ /出效率低出效率低v 2.2.地址结构地址结构13 3112 1112 110 0 逻辑地址逻辑地址A A；页大小；页大小L(L(设为设为1024)1024)；页内偏移；页内偏移d dd=A mod Ld=A mod L如：如： A A2170B. 2170B. 则则P=2, d=122 P=2, d=122 页号页号P P 位移位移W W 0 0页页1 1页页2 2页页3 3页页4 4页页5 5页页n n页页0 02 21 13 32 26 63 38 84 49 95 50 01 12 23 34 45 56 67

13、 78 89 9用户程序用户程序页表页表页号页号块号块号内存内存v 完成：逻辑页号完成：逻辑页号物理块号的映射，由页表完成。物理块号的映射，由页表完成。v 一、基本地址变换机构：一、基本地址变换机构： 越界保护越界保护 每个进程对应一页表，其信息（如长度、始址）放在每个进程对应一页表，其信息（如长度、始址）放在PCBPCB中，执行时将其首地址装入中，执行时将其首地址装入页表寄存器页表寄存器。v 不具快表，则需两次访问内存。不具快表，则需两次访问内存。（ （1 1）访页表）访页表（ （2 2）得到绝对地址内容）得到绝对地址内容v 有快表，速度提高。有快表，速度提高。v 快表贵，不能太多。快表贵，

14、不能太多。 例：有一页式系统，其页表存放在主存中：例：有一页式系统，其页表存放在主存中： 如果对主存的一次存取需要如果对主存的一次存取需要1.5 1.5 s,s,试问实试问实现一次页面访问的存取时间是多少现一次页面访问的存取时间是多少? ? 如果系统加有快表如果系统加有快表, ,平均命中率为平均命中率为85%,85%,当页表当页表项在快表中时项在快表中时, ,其查找时间忽略为其查找时间忽略为0, 0, 试试问此时问此时的存取时间是多少的存取时间是多少? ?答：若页表存放在主存中，则要实现一次页面访问需两次访问答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取

15、页面的物理地址（称为主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。定位）。第二次才根据该地址存取页面数据。 页表在主存的存取访问时间页表在主存的存取访问时间 =1.5=1.5* *2=3(s)2=3(s) 增加快表后的存取访问时间增加快表后的存取访问时间 =0.85=0.85* *1.5+(1-0.85)1.5+(1-0.85)* *2 2* *1.5=1.725(s)1.5=1.725(s)v 页表可能很大，将其离散存放在不同页块中。页表可能很大，将其离散存放在不同页块中。v 建一建一“外外部部页表页表”来管理这些离散页表块。来管理这些离散页表块

16、。 相当于单级相当于单级页表中页表中的页表寄存器，一般应常驻内存。的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。每项记录页表始址，且增加存在位。v 6464位机器页表一般位机器页表一般33级，最外层页表常驻。级，最外层页表常驻。 v某虚拟存储器的用户编程空间共某虚拟存储器的用户编程空间共3232个页面，每页为个页面，每页为1KB1KB，内存为，内存为16KB16KB。假定某时刻一用户页表中已调入。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：内存的页面对应的物理块号如下表：页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地

17、址0A5C0A5C（H H）所对应的物理地址为）所对应的物理地址为 ：125C125Cv 0A5C0A5C0000,100000,1010,0101,110010,0101,1100v 页号为页号为2 2，对应块号为，对应块号为4 4，有：，有：v 物理地址：物理地址：00010001，000010,0101,110010,0101,1100v 即：即：125C125Cv 即多重定位分区管理即多重定位分区管理 v 4.4.14.4.1引入引入 每个段可有其逻辑意义及功能，使得便于每个段可有其逻辑意义及功能，使得便于 （1 1）方便编程；）方便编程； （2 2）分段共享；）分段共享； （3 3）

18、分段保护；）分段保护； （4 4）动态链接；）动态链接； （5 5）动态增长；（如数据段的增长）动态增长；（如数据段的增长）v 分段分段 对用户而言，分段是对用户而言，分段是2 2维的。维的。 段号段号+ +段内地址。段内地址。v 段表：段表： 逻辑段逻辑段mapmap物理段物理段v 地址变换机构：地址变换机构：图图4 41616，4 41717v 分页与分段：分页与分段：（ （1 1）页是信息的物理单位，段是逻辑单位）页是信息的物理单位，段是逻辑单位（ （2 2）页长度固定，段长度不固定（由用户指定）页长度固定，段长度不固定（由用户指定）（ （3 3）一维与二维）一维与二维 v 段式系统易于

19、共享段式系统易于共享 例：图例：图4-184-18及及4-194-19 分页与分段共享比较分页与分段共享比较 可重入码（纯代码）可重入码（纯代码） 各个进程应保留局部数据区各个进程应保留局部数据区ed1ed2ed40data1data102122606170ed1ed2ed40data1data10data1data10进程进程1进程进程2页表页表页表页表ed1ed2ed40data1data102122607180主存分页系统中共享分页系统中共享editoreditordata1editordata2段长段长基址基址1608040240段长段长基址基址1608040380editordata

20、1data2v 分页优点：提高内存利用率分页优点：提高内存利用率v 分段优点：方便用户，易于共享，保护，动态链接。分段优点：方便用户，易于共享，保护，动态链接。v 一、段页式系统基本原理一、段页式系统基本原理 图图4-20 4-20 图图4-214-21 段号段号+ +段内页号段内页号+ +页内地址页内地址 注意：注意： 对用户而言，仍然是二维编址。对用户而言，仍然是二维编址。 对系统而言，则是三维编址对系统而言，则是三维编址 v 二、地址变换二、地址变换 图图4-224-22 三次访内存操作，为提高速度，在地址变换机构三次访内存操作，为提高速度，在地址变换机构中增设一高速缓冲寄存器（中增设一

21、高速缓冲寄存器（CacheCache）v 4.5.1 4.5.1 引入引入.1 1.常规存储管理的特征：常规存储管理的特征： 一次性（指全部装入）、一次性（指全部装入）、 驻留性（指驻留在内存不换出）驻留性（指驻留在内存不换出）、2 2 局部性原理、局部性原理 时间局部性：如循环执行时间局部性：如循环执行 空间局部性：如顺序执行。空间局部性：如顺序执行。、3 3 虚拟存贮器、虚拟存贮器 具有请求调入功能和置换功能，能从逻辑上对内具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。存容量进行扩充的一种存储系统。 实质：以时间换空间，但时间牺牲不大。实质：以时间换空间，但时间牺

22、牲不大。 虚拟大小由虚拟大小由_决定。决定。v 需要动态重定位需要动态重定位v 一、请求分页系统一、请求分页系统 以页为单位转换以页为单位转换 需硬件：需硬件：（1 1）请求分页的页表机制）请求分页的页表机制（2 2）缺页中断）缺页中断（3 3）地址变换机构）地址变换机构 需实现请求分页机制的软件（置换软件等）需实现请求分页机制的软件（置换软件等）v 二、请求分段系统二、请求分段系统 以段为单位转换以段为单位转换: :（1 1）请求分段的段表结构）请求分段的段表结构（2 2）缺段中断）缺段中断（3 3）地址变换机构）地址变换机构 需实现请求分段机制的软件（置换软件等）需实现请求分段机制的软件（

23、置换软件等）v 1 1离散性：部分装入离散性：部分装入（若连续则不可能提供虚存），无法支持大（若连续则不可能提供虚存），无法支持大作业小内存运行作业小内存运行v 2 2多次性：局部装入，多次装入。多次性：局部装入，多次装入。v 3 3对换性：对换性：v 4 4虚拟性虚拟性. .v4.6.1 4.6.1 请求分页中的数据结构及硬件支持请求分页中的数据结构及硬件支持一、页表机制一、页表机制页表项：页表项：二、缺页中断机构：可在指令执行期间产生（如图二、缺页中断机构：可在指令执行期间产生（如图4-234-23）转入缺页中断处理程序。转入缺页中断处理程序。三、地址变换机构三、地址变换机构比较简单分页机

24、制，增加了中断处理，比较简单分页机制，增加了中断处理，图图4.244.24页号页号物理块物理块号号状态位状态位P P访问字访问字段段A A修改位修改位M M外存地外存地址址v一、最小物理块数一、最小物理块数不同的作业要求不同。不同的作业要求不同。如：允许间接寻址：则如：允许间接寻址：则至少要求至少要求3 3个物理块。个物理块。MovMov A, B A, B v 二、页面分配和置换策略。二、页面分配和置换策略。1 1 固定分配局部置换。固定分配局部置换。 缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数.(.(少：置换少：置换率高率高 多：浪费多：浪费) ).2 2.可变分配全局置换可

25、变分配全局置换.3 3.可变分配局部置换可变分配局部置换 根据进程的缺页率进行页面数调整，进程之根据进程的缺页率进行页面数调整，进程之间相互不会影响。间相互不会影响。v 1 1平均分配算法平均分配算法v 2 2按进程大小比例分配算法：按进程大小比例分配算法：v 3 3考虑优先权分配算法考虑优先权分配算法 mssbiiniiss1v 1.1.调入时机：调入时机： 预调：（根据空间局部性）预调：（根据空间局部性） 目前：成功率目前：成功率5050 请求调：较费系统开销请求调：较费系统开销 各有优劣各有优劣v 2 2从何处调页：从何处调页： 对换区：修改过的页被换出时入对换区，对换区：修改过的页被换

26、出时入对换区， 快快 文件区：文件区：稍慢稍慢 对共享页，应判断其是否在内存区。对共享页，应判断其是否在内存区。v 3.3.页面调入过程页面调入过程v 目的：减少对换量，提高系统性能目的：减少对换量，提高系统性能 v 4.7.1 4.7.1 最佳置换算法和先进先出算法最佳置换算法和先进先出算法 一、最佳置换算法（理论上的）一、最佳置换算法（理论上的）v 目的：减少对换量，提高系统性能目的：减少对换量，提高系统性能 v 4.7.1 4.7.1 最佳置换算法和先进先出算法最佳置换算法和先进先出算法 二、二、FIFOFIFOv 一、算法描述一、算法描述 将将“最近的过去最近的过去”，作为，作为“最近

27、的将来最近的将来”。图图4-274-27v 二、二、LRULRU算法的硬件支持：（用来记录谁最近最久未访问）算法的硬件支持：（用来记录谁最近最久未访问）1 1 位移寄存器：（定时右移）位移寄存器：（定时右移）R=RR=Rn-1n-1R R0 0图图4-284-28v 2 2栈：栈： 当进程访问某页时，将其移出压入当进程访问某页时，将其移出压入“栈顶栈顶”，“栈底栈底”换出。换出。图图4-294-29v 一、简单算法：一、简单算法： 设一访问位：设一访问位：图图4-304-30 循环扫描，每次扫描时将访问位复位。循环扫描，每次扫描时将访问位复位。v 二、改进：二、改进：A=0; M=0A=0;

28、M=0v 一、最少使用（是频率）一、最少使用（是频率） 与与LRULRU类似（记录访问次数），设置一个访问计数器。类似（记录访问次数），设置一个访问计数器。v 二、页面缓冲算法：二、页面缓冲算法： 特点：淘汰的页只是修改标志；若页被修改过，则在特点：淘汰的页只是修改标志；若页被修改过，则在欲复盖它时回写，否则成批回写。欲复盖它时回写，否则成批回写。 在欲重访问该页时，若页换出则只需修改标志。在欲重访问该页时，若页换出则只需修改标志。v 补充：补充：8038680386的页描述的页描述。v 段表：段表：v 段名段名 段长段长 段基址段基址 存取方式存取方式 访问字段访问字段A A 修改字段修改字

29、段M M 存在位存在位P P 增补位增补位 外存起址外存起址v 二、缺段中断机构：二、缺段中断机构： 段不定长，处理起来比缺页中断复杂。段不定长，处理起来比缺页中断复杂。图图4.314.31v 三、地址变换机构三、地址变换机构 图图4.324.32v 一、共享段表：（整个系统一张）一、共享段表：（整个系统一张） 图图4.334.33.1 1.共享进程计数。共享进程计数。.2 2.存取控制字段。存取控制字段。.3 3.段号：不同的进程可以使用不同的段号去共享段号：不同的进程可以使用不同的段号去共享段。段。段名段名段长段长内存地内存地址址状态状态外存地外存地址址共享进程计数共享进程计数状态状态进程

30、名进程名进程号进程号段号段号存取控存取控制制v 二、共享段的分配与回收二、共享段的分配与回收.1 1.分配：分配： 第一次访问：分配内存，（第一次访问：分配内存，（1 1）增加共享段表；）增加共享段表；（2 2）修改进程段表。）修改进程段表。 第二次访问：（第二次访问：（1 1）修改共享段表；（）修改共享段表；（2 2）修改进）修改进程段表。程段表。.2 2.回收：回收： （1 1）count=0 count=0 （2 2）count0count0三、分段保护三、分段保护.1 1.越界检查越界检查 段号越界检查。段号越界检查。 段内偏移越界检查。段内偏移越界检查。.2 2.存取控制检查。存取控

31、制检查。 R R；R/WR/W；E E.3 3.环保护机构环保护机构 （1 1）内环可访问外环数据；）内环可访问外环数据； （2 2）外环可请求内环服务。）外环可请求内环服务。v实现实现LRULRU算法和算法和FIFOFIFO算法算法v要求要求 给出任意的输入流、计算失效率。给出任意的输入流、计算失效率。 输入流长度、输入流长度、cachecache尺寸可定制。尺寸可定制。 测试：测试： CacheCache5 5， 从从0 09 9可数字的任意排序，长度为可数字的任意排序，长度为3030。 例如：例如：12568,36536,56892,70495,36745,8734512568,3653

32、6,56892,70495,36745,87345v 虚地址：程序中的地址，如虚地址：程序中的地址，如 MOVE REG, 2000MOVE REG, 2000v 内存管理单元（内存管理单元（MMUMMU）：完成地址转换（图）：完成地址转换（图4.14.1）v 虚拟地址空间：二维：虚拟地址空间：二维：16k16k* *4G=64T4G=64T（LDT 8K LDT 8K GDT 8KGDT 8K）v 线性地址空间线性地址空间: : 一维：一维：4G4Gv 物理地址空间物理地址空间: : 一维：一维：4G4G选择子偏移量：段机制313101500页机制310线性地址物理地址v 段基地址段基地址v

33、 段界限段界限v 段属性段属性v 以上三者存储在段描述符表中以上三者存储在段描述符表中G G：粒度位，：粒度位，0 0时，段长表示段格式的字节长度，即一个段最长可达时，段长表示段格式的字节长度，即一个段最长可达1M1M字节；字节；1 1时，段长表示段格式以时，段长表示段格式以4K4K字节为一页的页目录数，即一个字节为一页的页目录数，即一个段最长可达段最长可达1M1M* *4K=4G4K=4GD D：表示缺省操作数的大小，：表示缺省操作数的大小，=0=0操作数为操作数为1616位。位。1 1为为3232位位v P:P:存在位。描述段是否在内存存在位。描述段是否在内存v S:S:表示该段是系统段（表示该段是系统段（0 0）还是用户段（）还是用户段（1 1）v DPL:DPL:该段的特权级该段的特权级v 类型：数据段还是代码段类型：数据段还是代码段v A:A:该段是否被访问该段是否被访问v 3 3位位: :为为0 0表示数据段，表示数据段，1 1表示代码段表示代码段v W:W:为为0 0表示不可写，为表示不可写，为1 1表示可写表示可写v R:R:该段可读否该段可