北语13春《操作系统概论》辅导资料十六
北语13春《操作系统概论》辅导资料十六主 题：第八章实存储器管理技术(5—7节）
学习时间：
内 容：
第八章实存储器管理技术
这周我们将学习第八章中的第5—7节，下面整理出的理念框架供同学们学习。
第五节 简单分页
一、为何要引入简单分页存储管理技术
前面我们已经介绍了两大类的存储管理技术,分别是固定分区存储管理技术和可变分区存储管理技术.它们都存在共同的缺点:主存的低利用率和主存分配与释放的低速度.可变分区存储管理技术虽然在主存利用率方面有所提高,但还是不能满足系统要求.
请考虑,造成固定分区存储管理技术和可变分区存储管理技术主存低利用率的原因分别是什么,区别在哪里?
就固定分区存储管理技术而言,主存的低利用率主要是由分区内部的碎片造成的.因为在作业进入主存前,主存已被划分成若干大小固定的分区,在作业进入主存后,操作系统会将一个大于作业所需空间的分区分给作业,这样那些剩余的空间就形成碎片,从而造成主存的低利用率.
就可变分区存储管理技术而言,主存的低利用率主要是由分区外部的碎片造成的.因为作业在进入主存时,系统根据作业的大小分配从空闲主存中划分出一个分区给作业使用,因此分区内是没有碎片问题的.但是对于整个主存而言,经过多次的划分,可能在主存中形成许多小到无法使用的碎片,因此分区外部的许多碎片造成主存的低利用率.碎片的增多也直接影响到主存分配与释放的速度,因为系统查找与作业大小匹配的主存分区的数量增多了.如果系统使用”存储紧缩”技术,则也会响应地增加CPU机时.
鉴于以上两类存储管理技术的缺点,人们提出了一种新的存储管理技术------简单分页技术.
1、分页存储管理技术中的基本做法：
（1）等分主存
把主存划分成相同大小的存储块，称为页架。对于一个特定的计算机系统而言，页架大小通常是固定不变的，并给各页架从零开始依次编以连续的页架号0，1，2
（2）用户逻辑地址空间的分页
把用户的逻辑地址空间（虚拟地址空间）划分成若干个与页架大小相同的部分，每部分称为页。并给各页从零开始依次编以连续的页号0，1，2，
（3）逻辑地址的表示
在分页系统中，用户的逻辑地址用一个数对（p,d）来表示。其中p是页号，d是该逻辑地址在页号为p的页中的相对地址，称为页内地址或偏移量。若给定一个用户逻辑地址A，页面大小为L。则：
其中INT是向下整除的函数（取模），MOD是取余。
例如：分页系统中页面大小为1000byte,则第0页对应的虚拟地址为0-999，第一页为1000-1999。设一用户作业的逻辑地址A=3456，则p=3 ,d=456，故逻辑地址A=3456在分页系统中表示为（3，456）。
2.主存分配原则
在分页系统中，系统以页架为单位把主存分给进程，并且分给一个进程的各页架不一定是相邻和连续的。进程的一个页面装入系统分给的某个页架中，所以页面与页架对应。一个作业的相邻的连续的几个页面，可被装入主存中任一不相邻的页架中，具体如何分配，取决于分配主存时空闲页架的情况。
由于进程各个页面不一定装在主存的各相邻的连续的页架中，因此需要用一个表格来指出每个进程的各页放在主存的哪些页架中，这种表格称为页表。在分页系统中，每个进程有一个页表。图8.11给出了几个进程的页表与主存使用情况的例子。
进程的逻辑地址在计算机系统中如何表示？
前面我们提到了，进程的逻辑地址在分页系统中用一个数对（p,d）来表示，其中的p,d都是十进制数，在计算机系统是不被识别的，因此，必须将其转换为计算机能识别的表示方法。
例：设系统有一16位主存空间专门用来存放进程的页号和页内地址，低位（0--？）用来存放页内地址，高位（？--15）用来存放页号。现假设用于存放页的页架大小为1KB，则逻辑地址4101的页号、页内地址可这样定：
因为，页架大小为1KB(1024byte)，所以页内地址的取值范围为0-1023Byte,故用10个二进制位就可表示页内地址，因此，把低位的10个二进制位用来存放页内地址（0-9位），把剩下的6个二进制位（10-15位）用来存放页号。
将逻辑地址4101用P158的公式进行转换，可知页号为4，页内地址为5。将4和5换算为二进制可得P159图的结果.
3.地址转换过程(逻辑地址转换为物理地址)
(1)首先将逻辑地址左边表示页号部分的页号抽取出来.
(2)以页号作为索引查找该进程页表,找出该页存放的主存页架号.
(3)将页架号和页内地址合并,就构成了物理地址,CPU就可以根据物理地址来访问主存.
简单分页方法的优点:
① 基本没有页内碎片(每个进程的最后一页中,会有页内碎片),主存利用率高.
② 分配和释放存储都很快,不需使用存储紧缩算法.
第六节简单分段
前面介绍的各种存储管理技术中（除了多重分区存储管理技术）,用户的逻辑地址空间被要求是一个连续的线性空间。而事实上一个作业常常由大量的相对独立的子程序模块、数据段组成。因此，如果使用前面介绍的存储管理技术，则作业在运行前，必须将其所需的各程序段和数据段连接成一个连续的线性地址空间，这样的话，既费时，又不便于共享（如编译程序的例子）。
因此，人们希望按照程序模块来划分段，并按这些段来分配主存。这就是简单分段的基本思路。
分段存储管理的基本概念可用下列几方面来描述：
1.进程的逻辑地址空间
分段情况下要求每个进程的地址空间按照程序自身的自然逻辑关系分成若干段,每个段有自己的段名(段名通常由程序员给出),系统为了管理的方便,常常为每一段规定一个内部段名.内部段名实际上是一个编号,称为段号.每个段的地址空间都从“0”开始编址成连续的线性地址。因此，进程中每个虚拟地址均要求用两个成分来描述：段名S和段内地址W。
2.程序的地址结构
因为进程中一个地址要用两个成分(S,W)来描述,所以地址在计算机中的表示形式,也必须分成两个部分:一部分表示段号,一部分表示段内地址.
例如某机器指令的地址部分长为24位,如果规定左边8位表示段号,而右边16位表示段内地址.这样的地址结构就限定了一个进程最多的段数为256段,最大的段长为64KB.
3.主存分配
段式管理的主存分配以段为单位,每一段分配一块连续的主存分区，一个进程的各段所分到的主存分区不要求是相邻连续的分区。
4.段表
一个进程往往由很多段组成,而且各段可能被分配在主存中多个不相邻的分区中,为了将进程的逻辑地址转换为物理地址,需要有一个段表来指出进程的某段放在主存中的何处,以及该段的长度等信息.每个进程对应一个段表,段表的结构见P174。
5.段的地址转换(逻辑地址转换为物理地址)
把逻辑地址左边段号部分提取出来,作为索引,查找进程的段表.将段内地址与段的长度比较.如果大于段的长度,则将引起非法访问中断(越界访问).如果是合法访问,那么将段的起始地址与段内地址相加,即是所要访问的物理地址.
6.简单分段存储管理技术的优点:
没有内部碎片,只有外部碎片问题,但由于模块化设计技术的成熟以及线程机制的推广,外部碎片问题也得到了很好的改善.
第七节内核主存管理
一、内核主存管理概述
操作系统的存储管理系统包含两大部分:一是对用户存储区的管理,它主要是为用户进程分配主存;另一部分是对内核主存的管理,它通过内核主存分配器为不同的内核子系统提供各种尺寸的主存块(操作系统的内核代码存放的主存区域成为内核主存,在系统启动后,这部分主存将不再释放,不得挪为他用,无须对它进行管理.但随着操作系统的发展,目前存在许多内核子系统,他们可能会要求系统提供各种不同尺寸的主存块.)
下面主要介绍几种常用的内核主存分配器:
1）、2次幂空闲表分配器
2）、伙伴系统
3）、SVR4的延迟伙伴系统
1、2次幂空闲表分配器
本方法使用一组空闲表，每一个表存放某一特定尺寸的空闲块，空闲块的大小均为2的整数幂，图8.14表示了这种分配器的结构。
本方法中每一个空闲块有一个字的头结构，可用空间不包括这个字。当该块空闲时，这个头结构字用来存放下一空闲块指针。当该块被分配后，头结构用以存放其所在的空闲表的指针。
该方法的缺点：
（1）内存利用率低。因为每个空闲块都有一个字的头结构；
（2）空闲块不能合并，不能满足大主存块的请求。
2、伙伴系统
伙伴系统是通过不断地对分大主存块来获得小主存块,并且尽可能合并空闲块,但合并空闲块要在伙伴的关系上才能合并.
所谓伙伴是指当一个主存块被对分后,每一部分称为另一部分的伙伴.
伙伴系统的基本概念:
①伙伴系统是通过对分大空闲块来获得小空闲块,对分生成的两个空闲块互称为伙伴,合并时需以伙伴关系为基础.
②系统中规定最小分配单位,通常为32byte或64byte.
③系统使用位图来维护主存中每一个最小分配单位的使用状况,如果某位置1,表示对应块正在使用,0表示该块空闲.
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
④系统为每一种可能的空闲块大小(最小分配单位的2的整数幂,如64*2 =64,64*2 =256)维护一个空闲链表。
⑤系统初启时,只有一个大的空闲块.其分配算法是首先将请求取整为2的整数次幂(如请求220byte的空间,则取整为64*2 =256byte),然后查找对应的空闲链表,如非空,分配器直接分配此链表上的空闲块；如该链表为空,则将一个大空闲块进行对分,直至与请求大小相符(例如请求220byte的空间,这时空闲链表上没有256byte的空闲块,只有512byte的空闲块,则将512byte的空闲块对分成两个256byte的空闲块).在两个符合要求的伙伴中,通常先分配低地址的那一块以使系统中的空闲块相对集中于一侧.分配时需同时更新位图的使用状况.接上例,为了满足220byte的请求,可将E’等分为两个空闲块(G,G’).若低地址为G’,则将G’分配出来,并将对应位设为1.
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
⑥主存空闲块的基址和大小是定位其伙伴的根本数据.例如上例中基址是512,大小是128byte的主存块的伙伴,其基址是640,大小是128byte的块.而不是基址是384,大小是128byte的块.为什么?而基址是256,大小是256byte的主存块的伙伴的基址为0.而不是基址是512,大小是256byte的块.为什么?
每当有主存块释放时,修改空闲链表和位图,并检查其伙伴是否也为空闲,如为空闲,应立即合并.合并后继续检查新块的伙伴能否继续合并,也就是说递归地进行合并,直至不能继续合并为止.
伙伴系统的缺点是每释放一块主存,分配器都尽可能地进行合并.那么可能刚刚递归地合并好,马上又要把它对分,这可能导致很差的性能.
3、SVR4的延迟伙伴系统
本算法是对伙伴系统的改进,伙伴系统的缺点是由于过分频繁的不断的合并和对分造成的性能不佳.因此直接的改进方法就是延迟合并操作直到必要时才合并.这虽然可以减少系统平均的分配和释放的时间,但等到需要时再合并空闲块,可能使得那一时刻的工作变得很大.因此,我们提出延迟伙伴系统,它既能延缓合并,又不要等到非做合并不可才去做,以便把合并的代价分散到若干请求中去.
延迟伙伴算法的一些基本概念:
(1) 延迟伙伴算法使用以下参数:
①N :大小为2 的主存块的当前总数.
②A :大小为2 已分配的主存块当前总数.
③L :大小为2 的局部空闲块当前总数.所谓局部空闲块是指它可以在2 类中分配,但不能与其伙伴合并(即使其伙伴也空闲).且它在位图中未标志为空闲.
④G :大小为2 的全局空闲块当前总数.所谓全局空闲块是指它在位图中标志为空闲,可以合并的空闲块.
这些参数有以下关系: N = A + L + G
(2) 延迟伙伴系统试图维护一个2 类局域空闲块池在合理的范围.如果2 级局域空闲块过多,说明下一级,即2 +1级局域空闲块过少,将不能满足分配请求,因此应进行合并.通常规定合并的标准是某类的局域空闲块不应超过该类的已分配的空闲块数,即L <=A .把他们二者的差设为slack,即
slack=A -L =N -2L -G
(3) 根据slack参数值不同,每个主存块类有如下三种状态:
①平稳状态,slack值大于等于2,没有必要进行合并.
②回收状态,slack值等于1,需要进行合并.
③加速状态,slack值等于0,分配器必须更快地进行合并.
注:算法必须保证slack不会成为负值.
(4) 当释放一个主存块时,分配器将其放入空闲块链表,并检验该主存块的状态:如果是”平稳”状态,分配器什么也不做,位图中也不把该块标为空闲,这样的主存块称为”延迟主存块”,在其头结构(只有空闲块才有头结构)中标志为空闲;如果状态是”回收”,分配器在位图中标志该块为空闲,并进行可能的合并(如果全局空闲块有其伙伴的话,就进行合并);如果是”加速”状态,分配器合并两个主存块,一个是刚释放的主存块,另一个从延迟主存块中找一个,合并后释放给下一级的空闲链表,然后根据新主存块类的状态,决定是否继续合并.所有这些操作都要重算slack值.
填空题
1、把逻辑地址转变为内存的物理地址的过程称为（）。
A、编译
B、连接
C、运行
D、地址映射
2、动态重定位（地址映射）是在作业的（）中进行的。
A、编译过程 B、装入过程 C、修改过程 D、执行过程
3、下列选项中，不会产生内部碎片的存储管理是（）。
A、分页式存储管理
B、分段式存储管理
C、固定分区式存储管理
D、段页式存储管理
4、在分页式存储管理中用做存储保护的是（）。
A、页表长度 B、页表始址 C、页长（大小）D、重定位寄存器
5、在分段式存储管理中用作存储保护的首先是（）。
A、段表长度
B、段表始址
C、段长
D、重定位寄存器
参考答案
1-5DDBAA
页:
[1]