操作系统复习 第四章
第四章 存储器管理
存储器是计算机系统的重要组成部分之一。 对存储器加以有效管理,不仅直接影响存储器的利用率,而且对系统性能有重大影响。存储器管理的主要对象是内存,对外存的管理在文件管理中。
存储器的层次结构
存储器的多层结构
理想的存储器:
速度快
容量大
价格低
现代计算机系统的存储部件实际上采用了层次结构,组成了一-个速度由快到慢,容量由小到大,价格由高到低的存储装置层次。
可执行存储器
寄存器和主存储器为可执行存储器。
进程访问可执行存储器:使用load或者store指令便可访问
进程访问辅存：通过I/O设备实现,在访问中将涉及到中断、设备驱动程序以及物理设备的运行。
层次结构
寄存器
- 寄存器访问速度最快,完全能与CPU协调工作,但价格昂贵,因此容量不可能做得很大。寄存器的长度一般以字为单位。
高速缓存
是现代计算机结构中的一个重要部件,其容量大于或远大于寄存器,速度快于主存储器。
根据局部性原理,将主存储器中一些经常访问的信息存放在高速缓存中,减少访问主存储器的次数,提高程序执行速度。
主存储器
简称内存或主存,用于保存进程运行时的程序和数据,也成为可执行存储器。
CPU的控制部件只能从主存储器中取得指令和数据,数据能够从主存储器读取并将他们装入到寄存器中,或者从寄存器存入到主存储器中。
外存
由于I/O速度远低于对主存的访问速度,因此加了磁盘缓存,利用它将使用频繁的部分磁盘数据和信息,暂时存放在磁盘缓存中,用以减少磁盘访问次数。
它利用主存空间来暂存从磁盘中读出的信息。
程序的连接与装入
在多道程序环境下,要使程序运行,必须为之。先建立进程。创建进程的第一件事是将程序和数据装入内存。
将用户源程序变为可在内存中执行的程序的步骤:
编译:由编译程序将用户源代码编译成若干个目标模块
链接:由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块
装入:由装入程序将装入模块装入内存
程序的装入
绝对装入方式
在编译时,如果知道程序驻留在内存的什么位置,那么编译程序将产生绝对地址的目标代码。
装入模块装入内存后,程序中的逻辑地址与实际内存地址完全相同,不须对程序和数据的地址进行修改。
程序中所使用的绝对地址,可在编译或汇编时给出,也可由程序员赋予。
只适合于单道程序环境
可重定位装入方式（Relocation Loading Mode）
在多道程序环境下,可重定位装入方式,根据内存的当前情况,将装入模块装入到内存的适当位置。
- 注意:在采用可重定位装入方式将装入模块装入内存后,会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。
在装入时对目标程序中指令和数据的修改过程称为重定位。地址变换在装入时一次完成,以后不再改变,称为静态重定位。
动态运行时的装入程序
在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时(访问内存之前)才进行。
装入内存后的所有地址都仍是相对地址。
为使地址转换不影响指令的执行速度,应设置一个重定位寄存器。
重定位寄存器:存放装入模块的起始位置
程序的链接
静态链接方式
在程序运行前,将目标模块及所需的库函数链接成一个完整的装配模块 ,以后不再拆开。
将目标模块装配成装入模块时需解决的两个问题:
对相对地址进行修改
变换外部调用符号
库有两种:静态库和动态库。windows. 上对应的是.lib .dll、 linux. 上对应的是.a .so
静态库
:在链接阶段,会将汇编生成的目标文件.o与引用到的库一起链接打包到可执行文件中。因此对应的链接方式称为静态链接。
静态库对函数库的链接是放在编译时期完成的程序在运行时与函数库再无瓜葛,移植方便。
浪费空间和资源,因为所有相关的目标文件与牵涉到的函数库被链接合成一个可执行文件
动态库
动态库在程序编译时并不会被连接到目标;代码中,而是在程序运行时才被载入。
不同的应用程序如果调用相同的库,那么在内存里只需要有一份该共享库的实例,规避了空间浪费问题。
装入时动态链接
用户源程序经编译后所得的目标模块,是在装入内存时,边装入边链接的,即在装入一个目标模块时,若发生一个外部模块调用事件,将引起装入程序去找出相应的外部目标模块,并将它装入内存,还要修改目标模块中的相对地址
优点:
便于修改和更新
便于实现对目标模块的共享。
运行时动态链接
运行时动态链接是将对某些模块的链接推迟到执行时才执行,即在执行过程中,当发现一个被调用模块尚未装入内存时,立即由OS去找到该模块并将之装入内存,把它链接到调用者模块上。
凡执行过程中未被用到的目标模块,不会调入内存和链接,这样不仅加快程序的装入过程。而月节省大量的内存空间.
连续分配存储方式
连续分配方式:为一个用户程序分配一个连续的存储空间。
单一连续分配
最简单,只适用于单用户、单任务系统,内存只有一道用户程序
内存分为两部分:
系统区
内存的低址部分,仅供OS使用
不一定需要内存保护
用户区
- 系统区以外的全部内存空间,供用户程序使用,存储器利用率低
固定分区分配
将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业,便可以有多道作业并发执行。
当有一空闲分区时,便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。
划分分区
分区大小相等
适用于控制多个相同对象的场合
缺乏灵活性,小程序浪费空间,大程序无法装入
分区大小不等
- 解决了灵活性问题,将内存分为多个大小不等的分区:小分区(较多) ,中等分区(适量) ,大分区(少量)
内存分配
分区说明表
用于管理和分配内存的数据结构。
每个表项对应一个分区,记载着这个分区的序号、空间大小、起始地址和使用状况。
分配过程
当有一用户程序要装入时，由内存分配程序检索该表,从中找出一-个能满足要求的、尚未分配的分区,将之分配给该程序,然后将该表项中的状态置为“已分配”;
若未找到大小足够的分区,则拒绝为该用户程序分配内存。
动态分区分配
动态分区法在作业执行前并不建立分区,分区的建立是在作业的处理过程中进行的,且其大小可随作业或进程对内存的要求而改变。
这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象,从而提高了内存的利用率。
采用动态分区法,在系统初启时,除了操作系统中常驻内存部分之外,只有一-个空闲分区。随后,分配程序将该区依次划分给调度选中的作业或进程。
在实现过程中涉及如下问题:
分区分配中的数据结构
空闲分区表
- 在系统中设置-一张空闲区表,每个表目记录-个空闲区,主要参数包括分区号、长度和起始地址。
空闲分区链
- 在每个分区的起始部分,设置一些用于控制分区分配的信息,以及用于链接各分区所用的前向指针;在分区尾部则设置一后向指针,将所有的空闲分区链接成一个双向链。
分区分配算法
把一个新作业装入内存时,须按照一 定的动态分区分配算法,从空闲分区表(或空闲分区链)中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响,因此人们对它进行了广泛的研究。
基于顺序搜索的动态分区分配算法
首次适应算法（First Fit）
要求按地址递增的次序组织空闲区表(链)。
申请和分配:从低地址找起,直至找到-个能可满足要求的空闲分区,根据作业大小划出一-块给申请者,剩余空间仍留在空闲链中,成为一个小的空闲分区。
优点:
- 优先使用内存中低址部分的小空闲区，从而保留了高址部分的大空闲区,有利于大作业。
缺点:
低址部分不断被划分,形成许多难以利用的小空闲分区(碎片) ,造成间浪费
碎片聚集在低址区域,每次又从低址开始查找,增加时间开销
循环首次适应算法（Next Fit）
是FF算法的演变和改进，每次分配不再从空闲分区链(表)的开始找起,而是从上次找到的空闲分区的下一个找起,找到一个能满足要求的空闲区。
需增设一个起始查寻指针,指示下一次查找从那个空闲分区开始。
优点:使空闲分区分布均匀,减少查找开销
缺点:缺乏大空闲分区,不利于大作业
最佳适应算法（Best Fit）
‘最佳”的含义:把能满足要求的最小空闲分区分配给作业,避免“大材小
用”空闲分区链组织方式:按容量从小到大
优点:尽量使用小空闲区,保留大空闲区
孤立地看,对每个程序,分区大小是最合适的,浪费最小
宏观上看，每次分配切割下来的剩余部分最小,因此会形成许多难以利用的碎片
最坏适应算法(Worst Fit)
总是挑选最大的空闲分区分割给作业使用
空闲分区链组织方式:按容量从大到小
优点:
防止产生碎片,空间浪费最少有利于中、小作业
查找效率很高(只需查找第一块)
缺点
- 缺乏大的空闲分区
基于索引搜索的动态分区分配算法
快速适应算法
也称分类搜索法
将空闲分区按大小分类,每类具有相同容量，放入一个空闲分区链表
增设一张管理索引表,每个表项对应一个分类,并记录相应链表的表头指针
即:按分区容量大小，分类索引、搜索
优点:
- 查找效率高,仅需要根据进程的长度,寻找到能容纳它的最小空闲区链表,并取下第一块进行分配即可。
缺点:
在分区归还主存时算法复杂,系统开销较大
浪费空间,空闲分区划分越细,浪费则越严重。
伙伴系统
无论已分配分区或空闲分区,分区大小必须是2的k次幂，k为整数, I≤k≤m
2m表示最大分区大小,通常是整个可分配内存的大小
每次切分必须对半分(分开的两半称之为一对伙伴)
每次合并必须与其伙伴合并
分配过程：
首先计算一个i值 ,使2i-1<n<=2i
在分区大小为2i的空闲分区链表中查找，找到则分配，否则转3
查找分区大小为2i+1的空闲分区链表,若存在空闲分区,则将其划分为两个大小相同(2i)的分区(一对伙伴) , 一个用于分配，一个加入到分区大小为2的空闲分区链表。若仍然找不到, 转4
继续查找大小为2i+2的空闲分区链表,此时需要进行两次划分
以此类推
回收
- 回收时,与其伙伴分区合并一次回收可能进行多次合并
性能
- 时间开销:查找、分割、合并空闲分区
哈希算法
哈希算法就是利用哈希快速查找优点,以及空闲分区在可利用空间表中的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时,根据所需要的分区大小,通过哈希函数计算,即得到在哈希表中的位置,从中得到相应的空闲分区链表,实现最佳分配策略。
分区分配及回收操作
分配：利用某种分配算法,从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size ,表中每个空闲分区的大小表示为m.size ,若m.size- u.sizessize(规定的不再切割的分区大小, 将整个分区分配给请求者,否则从分区中按请求的大小划出一块内存空间分配出去,余下部分留在空闲链中,将分配区首址返回给调用者。
回收：当某一个用户作业完成释放所占分区时,系统应进行回收。在可变式分区
中,应该检查回收区与内存中前后空闲区是否相邻若相邻,则应进行合并,形成一个较大的空闲区,并对相应的链表指针进行修改
若不相邻,应将空闲区插入到空闲区链表的适当位置。
动态重定位分区分配
动态分区分配方式,要求把一个系统程序或用户程序装入一个连续的内存空间中。
随着各进程不断申请和释放内存,导致在内存中出现大量分散的小空闲区。
内存中这种容量太小、无法利用的小分区称做(外部)“碎片”或“零头”
碎片：
内部碎片:指已分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。
外部碎片:指系统中无法利用的小空闲分区。如动态分区中存在的碎片。
动态重定位分区分配
将内存中所有作业移到内存一端(作业在内存中的位置发生了变化,这就必须对其地址加以修改或变换,即重定位) , 使本来分散的多个小空闲分区连成一个大的空闲区
这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑。
拼接时机:
分区回收时;当找不到足够大的空闲分区,且总空闲分区容量可以满足作业要求时。
定时。
实现
作业被装入内存后所有地址仍然是相对地址,将相对地址转换为物理地址的工作,被推迟到程序指令真正执行时。
需要硬件地址变换机构的支持
重定位寄存器,保存作业在内存中的起始地址
“紧凑”之后,程序移动了位置,只需更改重定位寄存器的内容为新的起始地址
对换
问题
- 内存中被阻塞的进程占用大量空间,外存，上却有许多作业因为内存不足而等待。
对换
- 把内存中暂时不能运行的进程或暂时不用的程序和数据调出到外存上,以便腾出足够的内存空间
类型
进程
- “整体对换”, “进程对换”,常用于中级调度、分时系统
“页”或”段”
- “页面对换”或”分段对换”,统称“部分对换”,用于支持虚拟存储系统
空间管理
一般从磁盘上划出一块空间作为对换区使用
在系统中设置相应的数据结构以记录外存的使用情况
对换空间的分配与回收,与动态分区方式时的内存分配与回收雷同。
进程的换入与换出
进程的换出
选择换出进程的优先次序
- 阻塞>睡眠>优先级&驻留时间>就绪进程
换出过程
申请对换空间(外存)
启动磁盘并传送数据
回收内存空间
修改数据结构
进程的换入
选择
- “就绪”已换出>换出最久
换入过程
申请内存
申请成功,直接调入
申请失败,先换出,再换入
对换伴随着较大的系统开销
CPU时间
I/O开销
不必要的对换可能导致系统性能下降
常用方案：正常时并不启用对换,内存紧张时,启用对换,把部分进程调出,缓解紧张状况后,暂停对换程序
分页存储
连续分配方式的缺点:
会形成许多“碎片”
“紧凑”产生较大开销
离散分配方式
允许将一个进程分散地装入多个不相邻的分区,从而无需“紧凑”。
可按离散分配的基本单位，分为两种方式:
分页存储管理方式
分段存储管理方式
段页式存储管理方式
页面
把进程的逻辑地址空间划分成若干大小相等的区域,每个区域称作页面或页。每个页都有一个编号,叫做页号。页号一般从0开始编号,如0 , 1, 2, …等。
把内存空间划分成若3 F和页大小相同的物理块，这些物理块叫页框(frame)或(物理)块。同样,每个物理块也有一个编号，块号从0开始依次顺序排列。
以页为单位进行内存分配,并按进程的页数多少来分配。逻辑上相邻的页,物理上不- 定相邻。
“页内碎片”：最后一页装不满而形成的碎片,不可利用。
页面大小
页太大，页表短，管理开销小,内碎片大,内存利用率低
页太小:内碎片小,内存利用率高，但页面数目多,使页表过长,占大量内存，管理开销大
页面大小由硬件地址结构决定,机器确定,页面大小就确定了
一般来说，页面大小为2的若干次幂,根据计算机结构的不同,其大小从1 KB到8KB不等。
地址结构：
分页地址中的地址结构如下:
地址长度32位:
0~11位为位移量(页内地址)，即每页的大小为4KB
12-31位为页号,地址空间最多允许有1 M页
对于某特定的机器,其地址结构是一定的。
如果给定的逻辑地址是A ,页面的大小为L ,则:
页号P = INT[A/L]
页内地址d = [A] MOD L
页表
进程的每一页离散地存储在内存的任一存储块中,为方便查找,系统为每一进程建立一张页面映像表,简称页表。
页表实现了从页号到物理块号的地址映射。
地址变化机构
由于页内地址和(块内)物理地址是一-对应的 ,地址变换机构的任务实际上是将逻辑地址中的页号转换为内存中的物理块号。
基本的地址变换机构
页表寄存器PTR
- 每个进程对应一个页表，页表驻留在内存中,页表始址和长度存放在PCB中，进程被调度时,这两个数据被装入页表寄存器
地址变换处理
得到页号:自动将逻辑地址分为页号和页内地址
用页号查页表,得到块号
将块号与页内地址拼接,即得物理地址
越界保护
- 查页表前,将页号与PTR中的页表长度比较,超出(> =)则越界
具有快表的地址变换机构
对于基本的地址变换机构(无快表) ,每存取一个数据,需要访问两次内存
访问页表=>数据所在的块号,形成物理地址
访问数据所在的物理地址=>数据
增设一个联想寄存器(快表TLB )
具有并行查询能力的高速缓冲寄存器
存放当前访问的那些页表项
每次地址变换时,先在快表中查找页号
快表中找不到,再访问内存中的页表,并将页表项存入快表,若快表已满,应换出最老的页表项
命中率:第3步时,在快表中查找成功的概率。
局部性原理
时间局部性:如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行;如果某个数据被访问过,不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
空间局部性:一旦程序访问了某个存储单元,在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)
访问内存的有效时间：
进程发出指定逻辑地址的访问请求,到在内存中找到对应的实际物理地址单元并取出数据,所需要花费的总时间,为内存的有效访问时间(EAT)。
假设访问一次内存的时间为t ,在基本分页存储管理方式中,有效访问时间为
- EAT=t+t=2t
在引入快表的分页存储管理方式中,有效访问时间的计算公式即为:
EAT =axλ+ (t+λ)(1-a)+t=2t+λ-txa
λ表示查找快表所需要的时间, a表示命中率, t表示访问一次内存所需要的时间。
两级和多级页表
现代计算机系统都支持非常大的逻辑地址空间(232~264) ,页表就非常大，需占用较大的地址空间。
解决方法:
采用离散方式存储
只将当前所需页表项调入内存
二级页表
- 将页表分页,并离散地将各个页面分别存放在不同的物理块中,同时为离散分配的页表再建立一张页表,称为外层页表,其每个页表项记录了页表页面的物理块号。
上述方法用离散分配空间解决了大页表无需大片存储空间的问题,但并未减少页表所占的内存空间。
解决方法:
把当前需要的一批页表项调入内存,以后再根据需要陆续调入。在采用两级页表结构的情况下,对正在运行的进程,必须将其外层页表调入内存,而对页表则只需调入一页或几页。
这就需要在外层页表项中增设一个状态位S ,用于表示该页表是否内存调入内存。
多级页表
- 二级页表的扩展,对外层页表再分页
反置页表
反置页表是为每一个物理块设置一个页表项并将按物理块号排序,其中的内容则是页号及其隶属进程的标志符。
所有进程共同使用一张页表
分段存储
引入
分页从根本.上克服了外部碎片(地址空间、物理空间都分割)。内存利用率提高。
缺点
- 无论信息内容如何,按页长分割,分割后装入内存,有可能使逻辑完整的信息分到不同的页面, 执行速度降低
所以考虑以逻辑单位分配内存。
分页主要是为了提高系统资源利用率
分段主要是为了满足用户(程序员)的需求
方便编程.
信息共享
信息保护
动态增长或者动态链接
分段
进程的地址空间:按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言中,程序员使用段名来编程),通常用段号代替段名,每段从0开始编址,段内地址是连续的。
段长由逻辑信息组的长度决定,逻辑地址由段号(段名)和段内地址所组成。
段表
分段式存储管理:以段为单位分配内存,每一个段在内存中占据连续空间,各段之间可以不连续存放。
为使程序正常运行,须在系统中为每个进程建立一张段映射表,简称”段表”。每个段在表中占有一个表项。
段表结构:段号;段在内存中的起始地址(基址) ;段长。
段表可以存放在寄存器中,但更多的是存放在内存中。
段表用于实现从逻辑段到物理内存区的映射。
分页与分段
相似点
- 采用离散分配方式,通过地址映射机构实现地址变换
不同点
页是信息的物理单位,分页是为了满足系统的需要;段是信息的逻辑单位，含有意义相对完整的信息,是为了满足用户的需要。
页的大小固定且由系统确定,由系统把逻辑地址分为页号和页内地址,由机器硬件实现;段的长度不固定,取决于用户程序,编译程序对源程序编译时根据信息的性质划分。
分页的作业地址空间是一维的;分段的作业地址空间是二维的。
信息共享
分段系统的一个突出优点是易于实现段的共享和保护,允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。
分页系统中虽然也能实现程序和数据的共享,但远不如分段系统方便。
分页系统的信息共享
共享页面时只需要在物理内存中保存一个编辑器的拷贝。
每个用户的页表映射到编辑器的同一物理拷贝,而数据页映射到不同的块。
分段系统的信息共享
- 在分段系统中,实现共享十分容易,只需在每个进程的段表中为共享程序设置一个段表项。
段页式存储
作业地址空间进行段式管理。( 面向用户 )
每段内再分成若干大小固定的页,每段都从零开始为自己的各页依次编写连续的页号。
对内存空间的管理仍然和分页存储管理一样,将其分成若干个和页面大小相同的物理块。(面向机器 )
作业的逻辑地址包括3个部分:段号、页号和页内位移。
为实现地址变换,段页式系统设立了段表和页表。
