(一)分区法
分区法是为支持多道程序运行而设计的一种最简单的存储管理方式。在这种方式下,将用户使用的内存划分成若干分区,每个分区里容纳一个进程。按照分区的划分方式,可分为固定分区法和动态分区法两种常见的分配 。
(1)固定分区法
固定分区就是内存中分区的个数固定不变,各个分区的大小也固定不变,但不同分区的大小可以不同。每个分区只可装入一个进程。
固定分区法管理方式简单,但内存空间利用率不高,有时浪费情况会相当严重。
(2)动态分区法
动态分区法就是内存中分区的大小和个数可变,在相应进程要进入内存时才建立分区,使其大小恰好适应进程的大小。
为了实现分区分配,系统要设置空闲分区表或者空闲分区链来记录内存的使用情况。
图 空闲分区表
图 空闲分区链示意图
从一组空闲区中选择一个空闲区的常用策略有两种:更先适应算法和更佳适应算法。
① 更先适应算法
在这种算法中,空闲表是按地址排列的,即:空闲分区起始地址小的分区在表中的序号也小。当要为进程分配内存空间时,就查该表,在各空闲分区中查找满足大小要求的可用分区。只要找到之一个足以满足要求的空闲分区就停止查找,并把它分配出去;如果该空闲分区与所需内存的大小一样,则从空闲表中取消该项;如果该空闲分区大于所需内存,那么分出所需内存空间后还有剩余,则余下的部分仍留在空闲表中,但应修改分区大小和分区始址。
这种算法的优点是:便于释放内存时进行合并,且为大进程预留高地址部分的大空闲区。缺点是:内存高地址部分和低地址部分的利用不均衡,且会出现许多很小的空闲分区,影响内存效率。
图 更先适应算法
② 更佳适应算法
这种算法的空闲表是以空闲分区的大小为序、按增量形式排列的,即小分区在前,大分区在后。它在满足需要的前提下,尽量分配最小的空闲分区。
这种算法产生的剩余空闲分区是最小的,但它不便于释放内存时与邻接空闲分区的合并,也同样会出现许多难以利用的小空闲分区。
图 更佳适应算法
(二)可重定位分区法
(1)碎片与紧缩
内存中容量太小、无法被利用的小分区称作“碎片”或“零头”。 依据碎片出现的位置,碎片分为内部碎片和外部碎片两种。
怎样使这些分散的、较小的空闲区得到合理使用呢?最简单的办法是定时或在分配内存时把所有的碎片合并为一个连续区。实现的 是移动某些已分配区的内容,使所有进程的分区紧挨在一起,而把空闲区留在另一端。这种技术称为紧缩。
图 可重定位分区的紧缩
(2)可重定位分区法
定义:采用紧缩技术的分区 称为可重定位分区法。
可重定位分区的硬件支持包括一对寄存器,其中一个存放用户程序在内存的起始地址,称作基址寄存器;另一个表示用户程序的逻辑地址的更大范围,称作限长寄存器。它们是专用的特权寄存器,只能由操作系统设置它们的值。每当选中一个进程运行时,就要为它设置这对寄存器的值。
硬件实现:基址寄存器和限长寄存器。
优点:可以消除碎片,能够分配更多的分区,有助于多道程序设计,提高内存的利用率。
缺点:紧缩花费了大量CPU时间;当进程大于整个空闲区时,仍要浪费一定的内存;进程的存储区内可能放有从未使用的信息;进程之间无法对信息共享。
图4-10 动态重定位的实现过程
(一)分页的基本概念
(1)逻辑空间分页
将一个进程的逻辑地址空间划分成若干大小相等的部分,每个部分称作页面或页。每页都有一个编号,叫做页号,页号从0开始依次编排,如0,1,2……。
(2)内存空间分块
把内存划分成与页面相同大小的若干存储块,称作内存块。块号从0开始依次顺序排列:0#块,1#块,2#块,……。页面(或块)的大小是由硬件确定的,它一般选择为2的若干次幂。不同机器中页面大小是有区别的,例如,IBM AS/400规定的页面大小为512 B,即,29,而Intel 80386的页面大小为4 KB(即212,4096 B)。
(3)逻辑地址表示
在分页存储管理方式中,表示地址的结构如下图所示。
图4-11 分页技术的地址结构
它由两部分组成:前一部分表示该地址所在页面的页号p;后一部分表示页内位移d,即页内地址。本图中所示的两部分构成的地址长度为32位。其中0~11位为页内地址,即每页的大小为4 KB,212;12~31位为页号,表示地址空间中最多可容纳220个页面。
计算:根据逻辑地址计算页号和页内地址?
对于某台具体机器来说,其地址结构是一定的。如果给定的逻辑地址是A,页面的大小为L,则页号p和页内地址d可按下式求得:
p = INT[A/L] , d = [A] MOD L
其中,INT是向下整除的函数,MOD是取余函数。
举例:设某系统的页面大小为1 KB, 逻辑地址A为3456,则页号p=INT (3 456/1 024) =3,页内地址d= 3 456 MOD 1 024 = 384。用一个数对(p, d)来表示就是(3,384)。
(4)内存分配原则
在分页情况下,系统以块为单位把内存分给各个进程,进程的每个页面对应一个内存块,并且一个进程的若干页可以分别装入物理上不连续的内存块中。
(5)设立页表
在分页系统中,允许将进程的各页面离散地装入内存的任何空闲块中,这样就出现进程的页号连续、而块号不连续的情况。怎样找到每个页面在内存中对应的物理块呢?为此,系统为每个进程设立一张页面映像表,简称页表。页表的作用是实现从页号到物理块号的地址映射。
如下图所示,在进程地址空间内的所有页(0~n-1)依次在页表中有一个页表项,其中记载了相应页面在内存中对应的物理块号。进程执行时,按照逻辑地址中的页号查找页表中的对应项,找到该页在内存中的物理块号。
图4-12 分页存储管理系统
(6)建立内存块表
操作系统管理整个内存,它必须知道哪些块已经分出去了,哪些块还是空闲的,总共有多少块等物理存储的情况。这些信息保存在称作内存块表的数据结构中,整个系统有一个内存块表。每个内存块在内存块表中占一项,表明该块当前空闲还是已分出去了;如果已分出去,是分给哪个进程的哪个页面了。
(二)地址映射
计算:根据逻辑地址和页表计算物理地址
通常,页表都放在内存中。当进程需要访问某个逻辑地址中的数据时,分页地址映像硬件自动按页面大小将CPU得到的相对地址分成两部分:页号和页内地址(p, d),具体步骤如下:
① 用页号p为索引去检索页表从页表中得到该页的物理块号f,把它装入物理地址寄存器中。
② 将页内地址d直接送入物理地址寄存器的块内地址字段d中。
③ 物理地址寄存器中的内容就是由二者拼接成的实际访问内存的地址,从而完成从逻辑地址到物理地址的转换。
图4-13 分页系统的地址转换机构
举例:某分页存储管理系统,页面大小L=1K,页表如下:
页号
物理块号
3
1
7
2
11
3
8
则逻辑地址A=2052所对应的物理地址是什么?要求写出主要计算过程。
解:
L=1K=1024,A=2052=1024*2+4
因此页号p=2,页内地址d=4,表示为二进制即……10 0000000100
查页表得页号2对应的物理块号为11,则2052对应的物理地址为:
页长*块号+页内地址=1024*11+4=11268 或者表示为
……1011 0000000100,即2C04(H)
因此物理地址为:2C04(H)=11268
(三)页的共享和保护
(1)页面共享
在多道程序系统中,数据共享很重要。尤其在一个大型分时系统中,往往有若干用户同时运行相同的程序(如编辑程序、编译程序)。很显然,更有效的办法是共享页面,避免同时在内存中有同一页面的两个副本。
页面共享的 是使这些相关进程的逻辑空间中的页指向相同的内存块(该块中放有共享程序或数据)。应当指出,在分页系统中实现页面共享是比较困难的,并非所有页面都可共享。实际上,那些只读的页面(如程序文件)可以被共享,而数据页面往往并不能共享。
下图示出了三个进程共享5#内存块中文本数据的情况。
图4-14 页面的共享
(2)页面保护
页面保护是分页系统中的另一个必须小心处理的问题。即使在单纯分页系统(没有采用虚拟存储技术的分页系统)中,也常在页表的表项中设置存取控制字段,用于指明对应内存块中的内容允许执行何种操作,从而禁止非法访问。一般设定为只读(R)、读写(RW)、读和执行(RX)等权限。如果一个进程试图去写一个只允许读的内存块时,则会引起操作系统的一次中断——非法访问性中断,操作系统会拒绝该进程的这种尝试,从而保护该块的内容不被破坏。
(3)分页技术的总结
分页技术可以用36个字来总结:
逻辑空间分页 物理空间分块
页与块一样大 页连续块离散
用页号查页表 由硬件做转换