碎片
在数据存储领域中,碎片(fragmentation)是指存储空间使用效率低下,结果导致功能、运行效率变低或二者兼而有之的现象。碎片化所造成的影响取决于具体的存储系统以及碎片化的种类。大部分情况下,碎片化都会导致都会导致存储空间的浪费,此时“碎片”一词亦可指代闲置的空间本身。对于其他的一些系统来说(比如FAT文件系统),数据量一定的前提下,用于存储数据所占的存储空间是一定的,和碎片化的程度无关。
内存碎片是指采用分区式存储管理的系统,在储存分配过程中产生的、不能供用户作业使用的主存里的小分区称成“内存碎片”。内存碎片分为内部碎片和外部碎片。
内部碎片当一个进程装入到固定大小的分区块(比如页)时,假如进程所需空间小于分区块,则分区块的剩余的空间将无法被系统使用,称为内部碎片(internal fragmentation)。
外部碎片当空闲内存被分成小区块,分别为不同的进程所使用时,便会出现外部碎片(external fragmentation)。这种情况下,虽然空闲空间足够大,但是程序没法使用,因为剩余空间被分成了大大小小的区块,没有一块能够大到程序可以使用。
内存分配内存分配是指在程序执行的过程中分配或者回收存储空间的分配内存的方法。内存分配方法有静态内存分配和动态内存分配两种。
静态内存分配静态内存分配,也可以称之为固定分区式分配是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定大小的区域,在每个分区中只装入一道作业,这样,把用户空间划分为几个分区,便允许有几道作业并发运行。当有一空闲分区时,便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区,当该作业结束时,又可再从后备作业队列中找出另一作业调入该分区。
可用下述两种方法将内存的用户空间划分为若干个固定大小的分区:
(1) 分区大小相等,即使所有的内存分区大小相等。其缺点是缺乏灵活性,即当程序太小时,会造成内存空间的浪费;当程序太大时,一个分区又不足以装入该程序,致使该程序无法运行。尽管如此,这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合,因为这些对象所需的内存空间是大小相等的。例如,炉温群控系统,就是利用一台计算机去控制多台相同的冶炼炉。
(2) 分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点,可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样,便可根据程序的大小为之分配适当的分区。1
动态内存分配动态内存分配(Dynamic memory allocation)又称为堆内存分配,是指计算机程序在运行期中分配使用内存。它可以当成是一种分配有限内存资源所有权的方法。
动态分配的内存在被程序员明确释放或被垃圾回收之前一直有效。与静态内存分配的区别在于没有一个固定的生存期。这样被分配的对象称之为有一个“动态生存期”。
分配过程包括寻找一块足够大未被使用的内存。分配过程当中的问题:内部和外部碎片。减少碎片需要特别处理,从而导致更复杂的实现。分配器的元数据需要占用额外的空间。尝试组块来减轻这个效应。
通常,内存是从一个被称为堆的内存池中分配出来的。高级语言封装了内存地址的概念,内存通常是通过指针来间接访问的。分配算法经常将组织分配释放组块等操作封装成抽象的接口供上层函数调用。
可重定位分区分配动态重定位的引入在连续分配方式中,必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区,即使它们容量的总和大于要装入的程序,但由于这些分区不相邻接,也无法把该程序装入内存。例如,图中示出了在内存中现有四个互不邻接的小分区,它们的容量分别为 10 KB、30 KB、14 KB 和 26 KB,其总容量是 80 KB。但如果现在有一作业到达,要求获得 40 KB 的内存空间,由于必须为它分配一连续空间,故此作业无法装入。这种不能被利用的小分区称为“零头”或“碎片” 。
若想把作业装入,可采用的一种方法是:将内存中的所有作业进行移动,使它们全都相邻接,这样,即可把原来分散的多个小分区拼接成一个大分区,这时就可把作业装入该区。这种通过移动内存中作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法,称为“拼接”或“紧凑” ,见图 。由于经过紧凑后的某些用户程序在内存中的位置发生了变化, 此时若不对程序和数据的地址加以修改(变换), 则程序必将无法执行。 为此,在每次“紧凑”后,都必须对移动了的程序或数据进行重定位。
动态重定位的实现在动态运行时装入的方式中,作业装入内存后的所有地址都仍然是相对地址,将相对地址转换为物理地址的工作,被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度,必须有硬件地址变换机构的支持,即须在系统中增设一个重定位寄存器,用它来存放程序(数据)在内存中的起始地址。程序在执行时,真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。 图示出了动态重定位的实现原理。地址变换过程是在程序执行期间,随着对每条指令或数据的访问自动进行的,故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时,不需对程序做任何修改,只要用该程序在内存的新起始地址,去置换原来的起始地址即可。
动态重定位分区分配算法动态重定位分区分配算法与动态分区分配算法基本上相同,差别仅在于:在这种分配算法中,增加了紧凑的功能,通常,在找不到足够大的空闲分区来满足用户需求时进行紧凑。