1、计算机操作系统第四章第四章 存储器管理存储器管理本章内容n4.1 存储器的层次结构存储器的层次结构n4.2 程序的装入和链接程序的装入和链接n4.3 连续分配方式连续分配方式n4.4 对换对换n4.5 分页存储管理方式分页存储管理方式n4.6 分段存储管理方式分段存储管理方式4.1 存存储储器器4.1.1 多级存储器结构多级存储器结构4.1.2 主主存存1主存储器主存储器n主存储器主存储器(简称内存或主存简称内存或主存)是计算机系统中一个是计算机系统中一个主要部件,用于主要部件,用于保存进程运行时保存进程运行时的程序和数据,的程序和数据,也称可执行存储器也称可执行存储器n CPU的控制部件只能
2、从的控制部件只能从主存储器主存储器中取得指令和中取得指令和数据,数据能够从主存储器读取并将它们装入到数据,数据能够从主存储器读取并将它们装入到寄存器中,或者相反寄存器中,或者相反n 主存储器的访问速度远低于主存储器的访问速度远低于CPU执行指令的速执行指令的速度,引入寄存器和高速缓存。度,引入寄存器和高速缓存。2寄存器寄存器n寄存器访问速度最快,完全能与寄存器访问速度最快,完全能与CPU协调工作,协调工作,但价格却十分昂贵,因此容量不可能做得很大但价格却十分昂贵,因此容量不可能做得很大n寄存器用于加速存储器的访问速度,如用寄存器寄存器用于加速存储器的访问速度,如用寄存器存放操作数,或用作地址寄
3、存器加快地址转换速存放操作数,或用作地址寄存器加快地址转换速度等度等4.1.3 高速缓1高速缓存高速缓存n高速缓存是现代计算机结构中的一个重要部件,其容量大于或远大于寄存器,而比内存约小两到三个数量级左右。1高速缓存(续)高速缓存(续)n根据程序执行的根据程序执行的局部性原理局部性原理,将主存中一些经常,将主存中一些经常访问的信息存放在高速缓存中,减少访问主存储访问的信息存放在高速缓存中,减少访问主存储器的次数,可大幅度提高程序执行速度。器的次数,可大幅度提高程序执行速度。n进程的程序和数据是存放在主存储器中,每当使进程的程序和数据是存放在主存储器中,每当使用时,被临时复制到一个速度较快的高速
4、缓存中。用时,被临时复制到一个速度较快的高速缓存中。n当当CPU访问一组特定信息时,首先检查它是否在访问一组特定信息时,首先检查它是否在高速缓存中,如果已存在,可直接从中取出使用,高速缓存中,如果已存在,可直接从中取出使用,以避免访问主存,否则,再从主存中读出信息。以避免访问主存,否则,再从主存中读出信息。2磁盘缓存磁盘缓存n由于目前由于目前磁盘的磁盘的I/O 速度远低于速度远低于对主存的访问速对主存的访问速度,因此将频繁使用的一部分磁盘数据和信息,度,因此将频繁使用的一部分磁盘数据和信息,暂时存放在磁盘缓存中,可减少访问磁盘的次数。暂时存放在磁盘缓存中,可减少访问磁盘的次数。n磁盘缓存本身并
5、不是一种磁盘缓存本身并不是一种实际存在的存储介质实际存在的存储介质,它依托于固定磁盘,提供对主存储器存储空间的它依托于固定磁盘,提供对主存储器存储空间的扩充,即利用主存中的存储空间,来暂存从磁盘扩充,即利用主存中的存储空间,来暂存从磁盘中读出中读出(或写入或写入)的信息。的信息。n主存也可以看做是辅存的高速缓存。主存也可以看做是辅存的高速缓存。n一个文件的数据可能出现在一个文件的数据可能出现在存储器层次的不同存储器层次的不同级别级别中,例如,一个文件数据通常被存储在辅中,例如,一个文件数据通常被存储在辅存中存中(如硬盘如硬盘),当其需要运行或被访问时,就必,当其需要运行或被访问时,就必须调入主
6、存,也可以暂时存放在主存的磁盘高须调入主存,也可以暂时存放在主存的磁盘高速缓存中。速缓存中。n大容量的辅存常常使用磁盘,磁盘数据经常备大容量的辅存常常使用磁盘,磁盘数据经常备份到磁带或可移动磁盘组上,以防止硬盘故障份到磁带或可移动磁盘组上,以防止硬盘故障时丢失数据。时丢失数据。2磁盘缓存(续)磁盘缓存(续)本章内容n4.1 存储器的层次结构存储器的层次结构n4.2 程序的装入和链接程序的装入和链接n4.3 连续分配方式连续分配方式n4.4 对换对换n4.5 分页存储管理方式分页存储管理方式n4.6 分段存储管理方式分段存储管理方式 n如何将一个用户源程序变成一个可在内如何将一个用户源程序变成一
7、个可在内存中执行的程序,通常要经过存中执行的程序,通常要经过3步骤:步骤:图4-2 对用户程序的处理步骤:由编译程序(由编译程序(Compiler)将用户源代码编译)将用户源代码编译成若个目标模块成若个目标模块 图4-2 对用户程序的处理步骤链接链接:由链接程序(由链接程序(Linker)将编译后形成的一组目)将编译后形成的一组目标模块,以及它们所需要的库函数链接在一起,标模块,以及它们所需要的库函数链接在一起,形成一个完整的装入模块形成一个完整的装入模块 图4-2 对用户程序的处理步骤:由装入程序(由装入程序(Loader)将装入模块装入内存。)将装入模块装入内存。4.2.1 n在将一个装入
8、模块装入内存时,可以有在将一个装入模块装入内存时,可以有绝对装入绝对装入方式、可重定位装入方式、动态运行时装入方式方式、可重定位装入方式、动态运行时装入方式。1绝对装入方式绝对装入方式 如果知道程序将驻留在内存的什么位置,那么,如果知道程序将驻留在内存的什么位置,那么,将产生绝对地址的目标代码。将产生绝对地址的目标代码。按照装入模块中的地址,将程序按照装入模块中的地址,将程序和数据装入内存。装入模块被装入内存后,由和数据装入内存。装入模块被装入内存后,由于程序中的于程序中的n为了便于程序的修改为了便于程序的修改,对编译的程序采用符号对编译的程序采用符号地址,然后在编译或汇编时,再将这些符号地地
9、址,然后在编译或汇编时,再将这些符号地址转换为绝对地址。址转换为绝对地址。n只适合单道程序环境。只适合单道程序环境。1绝对装入方式绝对装入方式 2可重定位装入方式可重定位装入方式 n目标模块的起始地址通常是从目标模块的起始地址通常是从0开始的,程序中开始的,程序中的其它地址也都是相对于起始地址计算的。的其它地址也都是相对于起始地址计算的。n由装入程序将装入模块装入内存后,装入模块中由装入程序将装入模块装入内存后,装入模块中程序所访问的所有逻辑地址与实际装入内存的物程序所访问的所有逻辑地址与实际装入内存的物理地址不同理地址不同,必须进行变换。,必须进行变换。示例:示例:作业装入内存时的情况作业装
10、入内存时的情况2可重定位装入方式可重定位装入方式(续)(续)n把在装入时对目标程序中把在装入时对目标程序中指令指令和和数据数据的变换过程的变换过程称为重定位。因为地址变换是在装入时一次完成称为重定位。因为地址变换是在装入时一次完成的,以后不再改变,故称为的,以后不再改变,故称为静态重定位。静态重定位。n采用静态重定位方法将程序装入内存采用静态重定位方法将程序装入内存,称为称为可重定可重定位装入方式。位装入方式。3动动态态运运n装装入入程程序序将将目目标标模模块块装装入入内内存存后,后,并并不不立立即即把把装装入入模模块块中中的的相相对对地地址址转转换换为为绝绝对对地地址,址,而而是是把把这这种
11、种地地址址转转换换推推迟迟到到程程序序执执行行时时进进行,行,在在硬硬件件地地址址变变换换机机构构的的支支持持下,下,随随着着对对每每条条指指令令或或数数据据的的访访问问自自动动进进行行地地址址变变换,换,故故称称为为动动态态重重定定位位。4.2.2源程序经过编译后,可得到一组目标模块,再利源程序经过编译后,可得到一组目标模块,再利用链接程序将这组目标模块链接形成装入模块。用链接程序将这组目标模块链接形成装入模块。,可把链接分成如下三种:,可把链接分成如下三种:n在程序运行之前,先将各目标模块及它们所需的在程序运行之前,先将各目标模块及它们所需的库函数,链接成一个完整的装配模块(又称执行库函数
12、,链接成一个完整的装配模块(又称执行模块),以后不再拆开。我们把这种事先进行链模块),以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。接的方式称为静态链接方式。B的起始地址变为的起始地址变为L,C的起始地址变为的起始地址变为L+M图图 4-4 程序链接示意图程序链接示意图(1)对相对地址进行修改)对相对地址进行修改 由编译程序产生的所有目标模块中,使用的都是相由编译程序产生的所有目标模块中,使用的都是相对地址,其起始地址都为对地址,其起始地址都为0,在链接成一个装入模块,在链接成一个装入模块时修改模块的相对地址。即把原时修改模块的相对地址。即把原B中的所有相对地址中的所有相对地址都
13、加上都加上L,把原,把原C中所有相对地址都加上中所有相对地址都加上LM。(2)变换外部调用符号)变换外部调用符号 将每个模块中所用的外部调用符号也都变换为相对将每个模块中所用的外部调用符号也都变换为相对地址。例如将地址。例如将call B 变换为变换为JSR“L”2、装入时动态链接、装入时动态链接n是指将用户源程序编译后所得到的一组目标模是指将用户源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的链接块,在装入内存时,采用边装入边链接的链接方式。方式。n装入一个目标模块时,若发生一个外部模块调装入一个目标模块时,若发生一个外部模块调用事件,将引起装入程序去找出相应的外部目用事件
14、,将引起装入程序去找出相应的外部目标模块,并将它装入内存。标模块,并将它装入内存。2、装入时动态链接、装入时动态链接n装入时动态链接方式有以下优点:装入时动态链接方式有以下优点:(1)便于修改和更新)便于修改和更新 u采用动态链接方式,由于各目标模块是分开存放的,采用动态链接方式,由于各目标模块是分开存放的,所以要修改或更新各目标模块,是件非常容易的事。所以要修改或更新各目标模块,是件非常容易的事。(2)便于实现对目标模块的共享)便于实现对目标模块的共享 u在采用静态链接方式时,每个应用模块都必须含有其在采用静态链接方式时,每个应用模块都必须含有其目标模块的拷贝,无法实现对目标模块的共享。目标
15、模块的拷贝,无法实现对目标模块的共享。u但采用装入时动态链接方式时,但采用装入时动态链接方式时,OS则很容易将一个目则很容易将一个目标模块链接到几个应用模块上,实现多个应用程序对标模块链接到几个应用模块上,实现多个应用程序对该模块的共享。该模块的共享。n这是指对某些目标模块的链接,是在程序执行中这是指对某些目标模块的链接,是在程序执行中需要该目标模块时,由需要该目标模块时,由OS去找到该模块并将之装去找到该模块并将之装入内存并把它链接到调用者模块上。入内存并把它链接到调用者模块上。:凡在执行过程中未被用到的目标模块,都凡在执行过程中未被用到的目标模块,都不会被调入内存和被链接到装入模块上,这样
16、不不会被调入内存和被链接到装入模块上,这样不仅可加快程序的装入过程,而且可节省大量的内仅可加快程序的装入过程,而且可节省大量的内存空间。存空间。3、运行时动态链接、运行时动态链接本章内容n4.1 存储器的层次结构存储器的层次结构n4.2 程序的装入和链接程序的装入和链接n4.3 连续分配方式连续分配方式n4.4 对换对换n4.5 分页存储管理方式分页存储管理方式n4.6 分段存储管理方式分段存储管理方式 4.3 连续分配方式连续分配方式 n连续分配方式,是指为一个用户程序分配连续分配方式,是指为一个用户程序分配一个连续的内存空间。一个连续的内存空间。n连续分配方式有四种:连续分配方式有四种:单
17、一连续分配单一连续分配固定分区分配固定分区分配动态分区分配动态分区分配1.重定位分区分配重定位分区分配 4.3.1单一连续分配单一连续分配 n仅适用于单用户,单任务的仅适用于单用户,单任务的OS。n把内存分为把内存分为系统区系统区和和用户区用户区两部分两部分 系统区仅提供给系统区仅提供给OS使用,通常是放在内存的低使用,通常是放在内存的低址部分;址部分;用户区是指除系统区以外的全部内存空间,提用户区是指除系统区以外的全部内存空间,提供给用户使用。供给用户使用。1.配置了存储器保护机构,用于防止用户程序对配置了存储器保护机构,用于防止用户程序对操作系统的破坏操作系统的破坏。后来取消了,因为:。后
18、来取消了,因为:1)节)节约硬件;约硬件;2)破坏微不足道。)破坏微不足道。4.3.2 固定分区分配固定分区分配n固定分区分配:将内存用户空间划分为若固定分区分配:将内存用户空间划分为若干个固定大小的区域,在每个分区中只装干个固定大小的区域,在每个分区中只装入一道作业入一道作业。n用户空间分为几个,就允许有几道作业并用户空间分为几个,就允许有几道作业并发运行。发运行。n分区空闲时或作业结束后,从外存后备作分区空闲时或作业结束后,从外存后备作业中装入。业中装入。4.3.2 固定分区分配(续)固定分区分配(续):(n当程序太小时,会造成内存空间的浪费当程序太小时,会造成内存空间的浪费。当程序。当程
19、序太大时,一个分区又不足以装入该程序,致使该太大时,一个分区又不足以装入该程序,致使该程序无法运行。程序无法运行。n主要用在一台计算机控制多个相同对象的场合。主要用在一台计算机控制多个相同对象的场合。(n可把内存区划含有多个较小的分区、适量的中等可把内存区划含有多个较小的分区、适量的中等分区及少量的大分区。分区及少量的大分区。2内存分配内存分配 n固定分区式分配固定分区式分配 的实现。为了便于内存分配,通的实现。为了便于内存分配,通常将分区按大小进行排队,并为之建立一张常将分区按大小进行排队,并为之建立一张分区分区使用表使用表。如图所示:。如图所示:4.3.2 固定分区分配(续)固定分区分配(
20、续)2内存分配内存分配(续)(续)n固定分区式分配固定分区式分配 的的优缺点优缺点:可运行多道程序的存储管理方式可运行多道程序的存储管理方式。存在存在“内零头内零头”会造成存储空间的浪费会造成存储空间的浪费。n内零头内零头在分区内没有利用的部分称为内零头。在分区内没有利用的部分称为内零头。4.3.2 固定分区分配(续)固定分区分配(续)4.3.3 动态分区分配动态分区分配动态分区分配是根据进程的实际需要,动态地为动态分区分配是根据进程的实际需要,动态地为之分配内存空间。之分配内存空间。为了实现分区分配,系统中配置相应的数据为了实现分区分配,系统中配置相应的数据结构,描述空闲分区以及已分配分区,
21、为分配提结构,描述空闲分区以及已分配分区,为分配提供依据。常用的数据结构有以下两种形式:供依据。常用的数据结构有以下两种形式:n在系统中设置一张空闲分区表,用于记录每个空在系统中设置一张空闲分区表,用于记录每个空闲分区的情况。每个空闲分区占有一个表目,表闲分区的情况。每个空闲分区占有一个表目,表目中包括分区序号,分区始址以及分区大小等。目中包括分区序号,分区始址以及分区大小等。(2)空闲分区链。)空闲分区链。n为了实现对空闲分区的分配和链接,设置前向指为了实现对空闲分区的分配和链接,设置前向指针和后向指针,通过前、后向链接指针将所有的针和后向指针,通过前、后向链接指针将所有的空闲分区链接成一个
22、双向链。空闲分区链接成一个双向链。图图4-6 空闲链结构空闲链结构(1)首次适应算法)首次适应算法FF n要求空闲分区链以地址递增的次序链接。在分配内要求空闲分区链以地址递增的次序链接。在分配内存时,从链首开始顺序查找,直至找到一个大小能存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;然后按照作业大小在该满足要求的空闲分区为止;然后按照作业大小在该区划分所需空间,余下部分仍然放在空闲分区链中。区划分所需空间,余下部分仍然放在空闲分区链中。为大作业分配大的内存空间创造了条件。为大作业分配大的内存空间创造了条件。低址部分不断被划分,会留下许多难以利用的、低址部分不断被划分,会留
23、下许多难以利用的、很小的空闲分区。增加查找可用空闲分区的开销。很小的空闲分区。增加查找可用空闲分区的开销。(2)循环首次适应算法)循环首次适应算法:n不从链首开始,从上次找到的空闲分区的下一不从链首开始,从上次找到的空闲分区的下一个空闲分区开始查找,找到为止;个空闲分区开始查找,找到为止;n将所有的空闲分区构成一个循环链表。采用循将所有的空闲分区构成一个循环链表。采用循环查找方式,设置一个起始查寻指针,用于指环查找方式,设置一个起始查寻指针,用于指示下一次起始查寻的空闲分区。示下一次起始查寻的空闲分区。能使内存中的空闲分区分布得更均匀,从而能使内存中的空闲分区分布得更均匀,从而减少了查找空闲分
24、区时的开销,但这样会缺减少了查找空闲分区时的开销,但这样会缺乏大的空闲分区。乏大的空闲分区。(n最佳最佳:指每次为作业分配内存时,把满足要求又是:指每次为作业分配内存时,把满足要求又是最小的空闲分区分配给作业,避免最小的空闲分区分配给作业,避免“大材小用大材小用”n该算法要求将所有的空闲分区按其容量以从小到大该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链的顺序形成一空闲分区链为大作业分配大的内存空间创造了条件为大作业分配大的内存空间创造了条件每次分配后所切割下来的剩余部分总是最小的,每次分配后所切割下来的剩余部分总是最小的,在存储器中会留下许多难以利用的小空闲区在存储器中会
25、留下许多难以利用的小空闲区 在在动动态态分分区区存存储储管管理理方方式式中,中,主主要要的的操操作作是是分分配配内内存存和和回回收收内内存。存。系系统统应应利利用用某某种种分分配配算算法,法,从从空空闲闲分分区区链链中中找找到到所所需需大大小小的的分分区。区。(1)分分配配内内存存Size 是事先规定的不再是事先规定的不再切割的剩余分区的大小。切割的剩余分区的大小。n当进程运行完毕释放内存时,需当进程运行完毕释放内存时,需相邻的空闲分区相邻的空闲分区,形成大的分区,称为合并技术。形成大的分区,称为合并技术。n需要合并的情况有如下图所示的三种,不论哪种情况,需要合并的情况有如下图所示的三种,不论
26、哪种情况,只需修改相应的分区信息来完成合并即可。只需修改相应的分区信息来完成合并即可。回收分区前有空闲分区回收分区前有空闲分区 回收分区后有空闲分区回收分区后有空闲分区 回收分区前后都有空闲分区回收分区前后都有空闲分区 4.3.4 伙伴系统伙伴系统 n伙伴系统伙伴系统规定,无论已分配分区或空闲分区,其规定,无论已分配分区或空闲分区,其大小均为大小均为2 的的k 次幂,次幂,k 为整数,为整数,lkmn其中:其中:21 表示分配的表示分配的最小最小分区的大小,分区的大小,2m 表示分配的表示分配的最大最大分区的大小,通常分区的大小,通常2m是整是整个可分配内存的大小。个可分配内存的大小。4.3.
27、4 伙伴系统(续)伙伴系统(续)n假设系统的假设系统的可利用空间容量为可利用空间容量为2m个字节个字节,则系统开,则系统开始运行时,整个内存区是一个大小为始运行时,整个内存区是一个大小为2m的空闲分区。的空闲分区。n在系统运行过程中,由于不断的划分,可能会形成在系统运行过程中,由于不断的划分,可能会形成若干个不连续的空闲分区,若干个不连续的空闲分区,n将这些空闲分区将这些空闲分区根据分区的大小根据分区的大小进行分类,对于进行分类,对于每每一类具有相同大小一类具有相同大小的所有空闲分区,单独设立一个的所有空闲分区,单独设立一个空闲分区双向链表。空闲分区双向链表。n不同大小的空闲分区形成了不同大小
28、的空闲分区形成了k(0km)个空闲分区链个空闲分区链表表分配分配n当需要为进程分配一个长度为当需要为进程分配一个长度为n 的存储空间时,首的存储空间时,首先计算一个先计算一个i 值,使值,使2i1 越界越界n页是信息的页是信息的物理物理单位,分页是为实现离散分配方单位,分页是为实现离散分配方式,以消减内存的外零头,提高内存的利用率。式,以消减内存的外零头,提高内存的利用率。n段则是信息的段则是信息的逻辑逻辑单位,它含有一组其意义相对单位,它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用完整的信息。分段的目的是为了能更好地满足用户的需要。户的需要。4分页和分段的主要区别分页和分段的
29、主要区别 之一:之一:n页的大小固定且由系统决定,由系统把逻辑地址页的大小固定且由系统决定,由系统把逻辑地址划分为页号和页内地址两部分,是由机器硬件实划分为页号和页内地址两部分,是由机器硬件实现的,因而在系统中只能有一种大小的页面。现的,因而在系统中只能有一种大小的页面。n段的长度却不固定,决定于用户所编写的程序,段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信通常由编译程序在对源程序进行编译时,根据信息的性质来划分。息的性质来划分。4分页和分段的主要区别之二:分页和分段的主要区别之二:n分页的作业地址空间是一维的,即单一的线分页的作业地址空间是一维的,即单
30、一的线性地址空间,程序员只需利用一个记忆符,性地址空间,程序员只需利用一个记忆符,即可表示一个地址即可表示一个地址n分段的作业地址空间则是二维的,程序员在分段的作业地址空间则是二维的,程序员在标识一个地址时,既需给出段名,又需给出标识一个地址时,既需给出段名,又需给出段内地址。段内地址。4分页和分段的主要区别之三:分页和分段的主要区别之三:4.6.3 信息共享信息共享 n分段系统的一个突出优点,是易于实现段的共享,分段系统的一个突出优点,是易于实现段的共享,即允许若干个进程共享一个或多个分段,且对段即允许若干个进程共享一个或多个分段,且对段的保护也十分简单易行。的保护也十分简单易行。n在分页系
31、统中,实现代码共享应在每个进程的页在分页系统中,实现代码共享应在每个进程的页表中都表中都建立相同个页表项建立相同个页表项和和占用相同的页号占用相同的页号。而而数据页面不受此限制。数据页面不受此限制。文本编辑程序文本编辑程序(Text Editor)示例示例 图:分段系统中共享editor的示意图只需在每个进程的段表中为文本编辑程序设置一个段表项只需在每个进程的段表中为文本编辑程序设置一个段表项(Reentrant Code)又称为)又称为“纯代纯代码码”(Pure Code)是一种允许多个进程同时访)是一种允许多个进程同时访 问的代码。问的代码。n为使各个进程所执行的代码完全相同,绝对不允为使
32、各个进程所执行的代码完全相同,绝对不允许可重入代码在执行中有任何改变。因此,可重许可重入代码在执行中有任何改变。因此,可重入代码是一种不允许任何进程对它进行修改的代入代码是一种不允许任何进程对它进行修改的代码。码。4.6.4 段页式存储管理方式段页式存储管理方式 n分页和分段存储管理方式都各有其优缺点。分页分页和分段存储管理方式都各有其优缺点。分页系统能有效地提高内存利用率,而分段系统则能系统能有效地提高内存利用率,而分段系统则能很好地满足用户需要,将两者结合成一种新的存很好地满足用户需要,将两者结合成一种新的存储管理方式系统,称为储管理方式系统,称为“段页式系统段页式系统”。1基本原理基本原理 段页式系统的基本原理,是分段和分页原理的结段页式系统的基本原理,是分段和分页原理的结合,即先将用户程序分成若干个段,再把每个段合,即先将用户程序分成若干个段,再把每个段分成若干个页,并为每一个段赋予一个段名。分成若干个页,并为每一个段赋予一个段名。图4一21作业地址空间和地址结构 作业有三个段作业有三个段地址结构由段号、地址结构由段号、段内页号段内页号、页内地址三部分构成。、页内地址三部分构成。图图4一一22 利用段表和页表实现地址映射利用段表和页表实现地址映射 2地址变换过程地址变换过程 段号段表长度段号段表长度 -越界越界