① 首次满足去:只要在空闲块链表中找到满足需要的一块,就进行分配。如果该块很大,则按申请的大小进行分割,剩余的块仍留在空闲块链表中;如果该块不很大,比如说,比申请的块大不了几个字节,则整块分配出去,以免使空闲链表中留下诈多无用的小碎块。 ② 最优满足法:将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户,则系统在分配前首先要对空闲块链表从头至尾描一遍,然后从中找出一块不小于申请块且最接近于申请块的空闲块分配,在用最优满足法进行分配时,为避免每次分配都要扫描整个链表,通常将空闲块链表空间的大小从小到大排序。这样,只要找到第一块大小申请块的空闲块即可进行分配。当然,在回收时变需将释放在空闲块插入到链表的适当位置上去。 ③ 最差满足法:将空闲块表中不小于申请块且是最大的空闲的一部全分配给用户。此时的空闲块链表按空闲的块的大小从大到小排序。这样每次分配无需查找,只需从链表中删除第一个结点,并将其中一部分分配给用户,而其它部分作为一个新的结点插入到空闲块表的适当置上去。上述三种分配策略各有所长。一般来说,最优满足法适用于请求分配的内存大小范围较广的系统。因为按最优满足法分配时,总是找大小最接近于请求的空闲块,系统中可能产生一些存储量很小而无法利用的小片内存,事时也保留那些很大的内存块以备响应后面可能发生的内存量较大的请求。反之,由于最差满足法每次都是从内存最大的结点开始分配,从而使链表中的结点趋于均匀。因此,它适用于请求分配的内存大小范围较窄的系统,而首次满足法的分配是随机的,因此它介于两者之间,通常适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息情况。从时间上来比较,首次满足法在分配时需查询空闲块链表,而回收时仅需插入到表头即可,最差满足法恰好相反,分配时无需查表,回收时则为将新的空闲块插入表中适当的位置,需先进行查找,最优满足法则不论分配与回收,均需查找链表,因此最费时间。 不同的情况应采用不同的方法。通常在选择时需考虑下列因素:用户的要求;请求分配量的大小分布;分配和释放的频率以及效率对系统的重要性等等。 至于存储回收的实现我们这里不进行讨论。 |