非连续分配管理方式
标签: 操作系统
学习人数: 12993

连续分配方式要求为一个进程分配连续的内存空间,会形成许多“碎片”(外部碎片), 尽管采用“紧凑”技术可以解决这个问题,但要为移动大量信息花去不少的处理机时间, 代价较高。

非连续分配管理方式根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

 

1.基本分页存储管理方式

固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免产生碎片,这就引入了分页的思想:被主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请内存中的块空间。

(1)分页存储的几个基本概念

①页面和页面大小:进程中的块称为页,内存中的块称为页框。外存也以同样的单位进行划分,直接称为块。进程在执行时需要申请主存空间,就是要为每一个页面分配主存中的可用页框,这就产生了页和页框一一对应。在为进程分配内存时,以块为单位,将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块,而形成了不可利用的碎片,称之为“页内碎片”。

为了方便地址转换,页面大小应该是2的幂,通常为1KB~8KB。同时页面大小应该适中,如果页面太小,会使进程的页面数过多,这样页表就过长,占用大量内存,而且也会增加硬件地址转换的开销,降低页面换入/换出的效率;页面过大又会使页内碎片增大,降低内存的利用率。所以页面的大小应该适中,考虑到空间效率和时间效率的权衡。

②地址结构:

分页存储管理系统中的逻辑地址

包含两部分,前一部分为页号P,后一部分为页内偏移量W。地址长度为32位,其中0~11位为页内地址,即每页大小为4KB;12-31位为页号,地址空间最多允许有1M=220页。要注意到 地址结构决定了虚拟内存空间有多大。

③页表:为了将逻辑地址上连续的页号映射到物理内存中后成为离散分布的多个物理块,系统为每个进程建立一张页表,记录页面在内存中对应的物理块号,页表通常存放在内存中。页表是由页表项组成的,页表中每个页表项都由页号和块号组成,根据页表项就可以找到每个页号所对应物理内存中物理块的块号。页表的作用是实现从页号到物理块号的地址映射。

(2)基本地址变换机构

地址变换机构的任务是为了将用户地址空间中的逻辑地址转换为内存中的物理地址,地址变换是借助于页表实现的。整个地址变换过程均是由硬件自动完成的。

页表寄存器(PTR):用来存放页表在内存中的起始地址和页表的长度。进程未执行时,页表的始址和长度存放在进程控制块中,当进程执行时,才将页表始址和长度存入页表寄存器。

分页存储管理系统的地址变换结构

①计算页号P=(int)(A/L);页内位移W=A%L。

②比较页号P 和页表长度M ,若P≥M,则产生越界中断,否则转到③接着执行

③页表起始地址F与页号P和页表项长度的乘积相加,用得到的地址值到内存中取出该内存单元存放的数b , 这个b就是物理块号。

④物理块号b和物理块大小的乘积与页内位移W 组合成物理地址E。

⑤用得到的物理地址E去访问内存。

(3)具有快表的地址变换机构

由于页表是存放在内存中的,这使 CPU 在每存取一个数据时,都要两次访问内存。第一次是访问内存中的页表,从中找到指定页的物理块号,再将块号与页内偏移量W拼接,以形成物理地址。第二次访问内存时,才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。

为提高地址变换速度,在地址变换机构中增设一个具有并行查询能力的高速缓冲寄存器,又称为“联想寄存器”或“快表”,又称为 TLB,用来存放当前访问的若干页表项,以加速地址变换的过程。一般快表的命中率可以达到90%以上,这样,分页带来的速度损失就降低到10%以下,快表的有效性是基于著名的局部性原理。快表(TLB)一般是由半导体存储器实现的,其工作周期与CPU的周期大致相同,但造价较高。为了降低成本,通常是在快表中存放正在运行作业当前访问的那些页表项,页表的其余部分仍然存放在内存中。

具有快表的地址变换机构

①CPU给出逻辑地址后,由硬件进行地址转换并将页号送入高速缓存寄存器,并将此页号与快表中的所有页号进行比较。

②如果找到匹配的页号,说明所要访问的页表项在快表中,则直接从中取出该页对应的页框号,与页内偏移量拼接形成物理地址。这样,存取数据仅一次访存便可实现。

③如果没有找到,则需要访问主存中的页表,在读出页表项后,应同时将其存入快表,以便后面可能的再次访问。但若快表已满,则必须按照一定的算法对旧的页表项进行替换。(有些处理机设计为快表和慢表同时查找,如果在快表中查找成功则终止慢表的查找。)

(4)两级页表

在基础分页系统中,页表长度M 是由页号的位数决定的。而页表的大小可以理解成一个矩形的面积,这个矩形的长度就是页表长度M ,宽度是每个页表项的大小,即块号的位数。

从页表大小的计算公式可知,页表大小和页表长度成正比,而页表长度又随着页号位数的增长而呈指数式增长。建立多级页表的目的在于建立索引,这样不用浪费主存空间去存储无用的页表项,也不用盲目地顺序式查找页表项。

两级页表的页表结构

先用外层页号 P1在外部页表上查找,找出的单元内容是二级页表的首地址,页表的首地址加上外层页内地址P2就是页表项的地址,利用 P2 作为指定页表分页的索引,找到指定的页表项,其中即含有该页在内存的物理块号, 该块号P和页内地址 d 即可构成访问的内存物理地址。

多级页表:对于64位的系统,两级页表机构会使页表的大小变得不可接受,所以可以通过继续增加页表的级数来减小页表的大小,不过会使页表的数量大大增加。多级页表最主要的缺点是要多次访问内存,每次地址变换很浪费时间。

二级页表结构示意图

(5)页的共享和保护

在分页存储管理系统中,实现共享的方法是使共享用户地址空间中的页指向相同的物理块。分页存储管理系统中将作业的地址空间划分成页面的做法对用户是透明的,同时作业的地址空间是线性连续的,当系统将作业的地址空间分成大小相同的页面时,被共享的部分不一定被包含在一个完整的页面中,这样不应共享的数据也被共享了,不利于保密。

分页存储管理系统可以为内存提供两种保护方式:一种是地址越界保护,即通过比较地址变换机构中的页表长度和所要访问的逻辑地址中的页号来完成;另一种是通过页表中的访问控制信息对内存信息提供保护。

(6)基本分页存储管理方式的优缺点

优点:①内存利用率高,实现了离散分配,便于存储访问控制,无外部碎片。

缺点:需要硬件支持(尤其是快表),内存访问效率下降,共享困难,有内部碎片。

 

2. 基本分段存储管理方式

分页管理方式是从计算机的角度考虑设计的,以提高内存的利用率,提升计算机的性能,且分页通过硬件机制实现,对用户完全透明;而分段管理方式的提出则是考虑了用户和程序员,以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

(1)分段

在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段定义了一组逻辑信息。段式管理方式按照用户进程中的自然段划分逻辑空间。划分时段内要求连续,段间不要求连续,因此整个作业的地址空间是二维的。其逻辑地址由段号S与段内偏移量归两部分组成。

分段存储管理系统中的逻辑地址结构

在页式系统中,逻辑地址的页号和页内偏移量对用户是透明的,但在段式系统中,段号和段内偏移量必须由用户显示提供,在高级程序设计语言中,这个工作由编译程序完成。

(2)表段

每个进程都有一张逻辑空间与内存空间映射的段表,其中每一个段表对应进程的一个段,段表项记录该段在内存中的起始地址和段的长度。

段表项的结构

在配置了段表后,执行中的进程可通过查找段表,找到每个段所对应的内存区,实现从逻辑段到物理内存区的映射。

利用段表实现物理内存区映射

(3)地址变换机构

为了实现进程从逻辑地址到物理地址的变换功能,在系统中设置了段表寄存器,用于存放段表始址F和段表长度M。

分段系统的地址变换过程

① 从逻辑地址力中取出前几位为段号S,后几位为段内偏移W,注意在段式存储管理的题目中,逻辑地址一般以二进制数给出,而在页式存储管理中,逻辑地址一般以十进制数给出,具体问题具体分析。

② 比较段号S和段表长度M 若,S≥M , 则产生越界中断,否则继续执行③。

③ 段表中段号S对应的段表项地址= 段表始址F+ 段号S×段表项长度,取出该段表项的前几位得到段长C,后几位是段的起始地址(基址)b。若段内位移 W≥C,则产生越界中断,否则转到④接着执行。

④ 段的基址b 和段内位移W相加得到物理地址E,用得到的物理地址E去访问内存。

(4)段的共享和保护

在分段系统中,分段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。注意共享段中信息的保护问题。当一个作业正从共享段中读取数据时,必须防止另一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码(它不属于临界资源),这样不能的代码和不能修改的数据是可共享的,而可修改的代码和数据则不能共享。

与分页管理类似,分段管理的保护方法主要有两种:一种是存取控制保护,另一种是地址越界保护。

(5)基本分段存储管理方式的优缺点

优点:便于程序模块化处理和处理变换的数据结构;便于动态链接和共享;无内部碎片。

缺点:与分页类似,需要硬件支持;为满足分段的动态增长和减少外部碎片,要采用拼接技术;分段的最大尺寸受到主存可用空间的限制;有外部碎片。

(6)分段与分页的区别

段则是信息的逻辑单位,它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信息的性质来划分。

分段的作业地址空间则是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址。

 

3.段页式管理方式

页式存储管理能有效地提高内存利用率,而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方式结合起来,就形成了段页式存储管理方式。

在段页式存储管理系统中,作业的地址空间首先被分成若干个逻辑分段,每段都有自己的段号,然后再将每一段分成若干个大小固定的页。对于主存空间的管理仍然和分页管理一样,将其分成若干个和页面大小相同的物理块,对主存的分配以物理块为单位。

在段式系统中,作业的逻辑地址分为三部分:段号、页号和页内偏移量。在一个进程中,段表只有一个,而页表可能有多个。需要掌握三个问题:逻辑地址结构、表项结构、寻址过程。

段页式系统的逻辑地址结构

为了实现地址变换,段页式存储管理系统中需要同时设立段表和页表。系统为每个进程建立一张段表,而每个分段有一张页表。段表的表项中至少应包括段号、页表始址和页表长度,其中页表始址指出该段的页表在主存中的起始位置;页表的表项中至少应包括页号和块号。此外,为了便于实现地址变换,系统中还需要配置一个段表寄存器,用来存放段表的起始地址和段表长度。

段页式系统中的地址变换机构

①从逻辑地址A 中取出前几位为段号S , 中间几位为页号P,后几位为页内位移W。

②比较段号S 和段表长度M,若 S>M ,则产生越界中断,否则转到③接着执行。

③取出段表起始地址F与段号S相加,用得到的地址值到内存中取出该内存单元存放的数。取出来的数的前几位是页表长度C,后几位是页表起始地址d,若页号P>C,则产生越界中断,否则转到④接着执行。

④页表起始地址d与页号P和页表项长度的乘积相加得到页表项在内存中的物理地址,查找到该地址存放的数值为物理块号b。

⑤用物理块号b 与页内位移W组合成物理地址E。用得到的物理地址E去访问内存。

段页式的确结合了段式和页式的优点,而且克服了段式的外部碎片问题,但是段页式的内部碎片并没有做到和页式一样少。

 



课后作业

课后习题

 

1.【2009统考真题】分区分配内存管理方式的主要保护措施是( )。

A .界地址保护            B .程序代码保护

C .数据保护              D .栈保护

【答案】A

【解析】每个进程都拥有自己独立的进程空间,若一个进程在运行时所产生的地址在其地址空间之外,则发生地址越界,因此需要进行界地址保护,即当程序要访问某个内存单元时,由硬件检查是否允许,若允许则执行,否则产生地址越界中断。

 

2. 【2010统考真题】某基于动态分区存储管理的计算机,其主存容量为55MB(初始为空),采用最佳适配(Best Fit)算法,分配和释放的顺序为:分配 15MB,分配 30MB,释放 15MB,分配8MB,分配6MB,此时主存中最大空闲分区的大小是( )。

A. 7MB                    B. 9MB

C. 10MB                   D. 15MB

【答案】B

【解析】最佳适配算法是指每次为作业分配内存空间时,总是找到能满足空间大小需要的最小空闲分区给作业,可以产生最小的内存空闲分区。下图显示了这个过程的主存空间变化。

图中,灰色部分为分配出去的空间,白色部分为空闲区。这样,容易发现,此时主存中最大空闲分区的大小为9MB。

 

3.动态重定位是在作业的( )中进行的。

A. 编译过程                    B. 装入过程

C. 链接过程                     D. 执行过程

【答案】D

【解析】静态装入是指在编程阶段就把物理地址计算好。

可重定位是指在装入时把逻辑地址转换成物理地址,但装入后不能改变。

动态重定位是指在执行时再决定装入的地址并装入,装入后有可能会换出,所以同一个模块在内存中的物理地址是可能改变的。

动态重定位是指在作业运行过程中执行到一条访存指令时,再把逻辑地址转换为主存中的物理地址,实际中是通过硬件地址转换机制实现的。

 

4.在一页式存储管理系统中,页表内容见右表。若页的大小为4KB,则地址转换机构将逻辑地址0转换成的物理地址为(块号从0开始计算)(  )。

A. 8192                    B. 4096

C. 2048                    D. 1024

【答案】A

【解析】按页表内容可知,逻辑地址0对应块号2 ,页大小为4KB,因此转换成的物理地址为2×4K =8K=8192。

 

5. 页式存储管理中,页表的始地址存放在( )中。

A.内存                           B .存储页表

C .快表                           D .寄存器

【答案】D

【解析】页表的功能由一组专门的存储器实现,其始址放在页表基址寄存器(PTBR) 中。这样才能满足在地址变换时能够较快地完成逻辑地址和物理地址之间的转换。

 

6. 可重入程序是通过( )方法来改善系统性能的。

A .改变时间片长度              B .改变用户数

C .提高对换速度                D .减少对换数量

【答案】D

【解析】可重入程序主要是通过共享来使用同一块存储空间的,或通过动态链接的方式将所需的程序段映射到相关进程中去,其最大的优点是减少了对程序段的调入/调出,因此减少了对换数量。

 

7. 操作系统实现( )存储管理的代价最小。

A .分区                               B .分页

C .分段                               D .段页式

【答案】A

【解析】实现分页、分段和段页式存储管理需要特定的数据结构支持,如页表、段表等。为了提高性能,还需要硬件提供快存和地址加法器等,代价高。分区存储管理是满足多道程序设计的最简单的存储管理方案,特别适合嵌入式等微型设备。

 

8. 对主存储器的访问,( )。

A .以块(即页)或段为单位

B.以字节或字为单位

C.随存储器的管理方案不同而异

D.以用户的逻辑记录为单位

【答案】B

【解析】这里是指主存的访问,不是主存的分配。对主存的访问是以字节或字为单位的。例如,在页式管理中,不仅要知道块号,而且要知道页内偏移。

 

9. 【2009统考真题】一个分段存储管理系统中,地址长度为32位,其中段号占8位,则最大段长是( )。

A. 28B                      B. 216B

C. 224B                     D. 232B

【答案】C

【解析】分段存储管理的逻辑地址分为段号和位移量两部分,段内位移的最大值就是最大段长。地址长度为32位,段号占8 位,因此位移量占32-8 = 24位,因此最大段长为224B。

 

10. 【2010统考真题】某计算机采用二级页表的分页存储管理方式,按字节编址,页大小为210B ,页表项大小为2 B ,逻辑地址结构为

逻辑地址空间大小为216页,则表示整个逻辑地址空间的页目录表中包含表项的个数至少是( )。

A. 64                       B.128

C.256                       D.512

【答案】B

【解析】页大小为210B ,页表项大小为2 B ,因此一页可以存放29个页表项,逻辑地址空间大小为216页,即共需216个页表项,因此需要216/29 = 27= 128个页面保存页表项,即页目录表中包含表项的个数至少是128。

 

11. 【2014统考真题】现有一个容量为10GB的磁盘分区,磁盘空间以簇为单位进行分配,簇的大小为4KB,若采用位图法管理该分区的空闲空间,即用一位标识一个簇是否被分配,则存放该位图所需的簇为( )个。

A. 80

B. 320

C. 80K

D. 320K

【答案】A

【解析】簇的总数为10GB/4KB = 2.5M,用一位标识一簇是否被分配,整个磁盘共需要2.5M b,即需要2.5M/8 = 320KB,因此共需要 320KB/4KB = 80 簇,选 A

 

12. 【2014统考真题】下列选项中,属于多级页表优点的是( )。

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

【答案】B

【解析】多级页表不仅不会加快地址的变换速度,还会因为增加更多的查表过程,使地址变换速度减慢;也不会减少缺页中断的次数,反而如果访问过程中多级的页表都不在内存中,会大大增加缺页的次数,并不会减少页表项所占的字节数,而多级页表能够减少页表所占的连续内存空间,即当页表太大时,将页表再分级,把每张页表控制在一页之内,减少页表所占的连续内存空间,因此选D。

 

13. 【2016统考真题】某进程的段表内容如下所示。

访问段号为2、段内地址为400的逻辑地址时,进行地址转换的结果是( )。

A .段缺失异常             B .得到内存地址4400

G 越权异常               D .越界异常

【答案】D

【解析】分段系统的逻辑地址A 到物理地址E 之间的地址变换过程如下:

① 从逻辑地址A中取出前几位为段号S ,后几位为段内偏移量W , 注意段式存储管理的题目中,逻辑地址一般以二进制数给出,而在页式存储管理中,逻辑地址一般以十进制数给出,读者要具体问题具体分析。

② 比较段号S和段表长度M,若 S>=M , 则产生越界异常,否则继续执行。

③ 段表中段号S对应的段表项地址= 段表始址F + 段号S×段表项长度取出该段表项的前几位得到段长C。若段内偏移量> =C ,则产生越界异常,否则继续执行。从这句话可以看出,段表项实际上只有两部分,前几位是段长,后几位是始址。

④ 取出段表项中该段的基址b,计算E=b+W,用得到的物理地 E去访问内存。

题目中段号为2的段长为300,小于段内地址400,因此发生越界异常,D 正确。

 

14. 【2019统考真题】在分段存储管理系统中,用共享段表描述所有被共享的段。若进程共享段S,则下列叙述中,错误的是( )。

A .在物理内存中仅保存一份段S的内容

B.段S在中应该具有相同的段号

C. 共享段S在共享段表中的段表项

D. 已都不再使用段 S时才回收段 S所占的内存空间

【答案】B

【解析】段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的,因此在内存中仅保存一份段S 的内容,A 正确。段S对于进程来说,使用位置可能不同,所以在不同进程中的逻辑段号可不同,B错误。段表项存放的是段的物理地址(包括段始址和段长度),对于共享段S来说物理地址唯一,C正确。为了保证进程可以顺利使用段S ,段S必须确保在没有任何进程使用它(可在段表项中设置共享进程计数)后才能被删除,D 正确。

 

15. 【2019统考真题】某计算机主存按字节编址,采用二级分页存储管理,地址结构如下

虚拟地址2050 1225H对应的页目录号、页号分别是( )。

A. 081H, 101H     B. 081H, 401H      C. 201H, 101H      D. 201H, 401H

【答案】A

【解析】题中给出的是十六进制地址,首先将它转化为二进制地址,然后用二进制地址去匹配题中对应的地址结构。转换为二进制地址和地址结构的对应关系如下图所示。

前10位、11~20位、21~32位分别对应页目录号、页号和页内偏移。把页目录号、页号单独拿出,转换为十六进制时缺少的位数在高位补零,0000 1000 0001, 0001 0000 0001分别对应

081H, 101H,选项A正确。

 

16. 【2019统考真题】在下列动态分区分配算法中,最容易产生内存碎片的是( )。

A.首次适应算法           B .最坏适应算法

C.最佳适应算法           D.循环首次适应算法

【答案】C

【解析】最佳适应算法总是匹配与当前大小要求最接近的空闲分区,但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等,几乎每次分配内存都会产生很小的难以利用的内存块,所以最佳适应算法最容易产生最多的内存碎片,C 正确。

 

17. 【2013统考真题】某计算机主存按字节编址,逻辑地址和物理地址都是32位,页表项大小为4B。请回答下列问题:

1) 若使用一级页表的分页存储管理方式,逻辑地址结构为

则页的大小是多少字节?页表最大占用多少字节?

2) 若使用二级页表的分页存储管理方式,逻辑地址结构为

设逻辑地址为L A ,请分别给出其对应的页目录号和页表索引的表达式。

3) 采用1)中的分页存储管理方式,一个代码段的起始逻辑地址为0000 8000H,其长度为8 KB;被装载到从物理地址0090 0000H开始的连续主存空间中。页表从主存0020 0000H开始的物理地址处连续存放,如下图所示(地址大小自下向上递增)。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号,以及代码页面2的起始物理地址。

【解析】

1) 因为主存按字节编址,页内偏移量是12位,所以页大小为212B = 4KB。 页表项数为220, 因此该一级页表最大为220×4B = 4MB。

2) 页目录号可表示为(((unsigned int)(LA))>>22) & 0x3FF。

页表索引可表示为(((unsigned int)(LA))>>12) & 0x3FF。

3 ) 代码页面1的逻辑地址为0000 8000H,表明其位于第8个页处,对应页表中的第8个页表项,所以第8 个页表项的物理地址= 页表始址+ 8×页表项的字节数= 0020 0000H + 8x4 = 0020 0020H。由此可得如下图所示的答案。

 


登录后发布评论

暂无评论,来抢沙发