【www.bbyears.com--安卓教程】
/*可变分区回收算法
将回收的内存插入到自由主存队列中,供下次分配内存时使用.在本模拟程序中,自由主存队列的排序原则是按地址排列的(即低地址的可用空闲区间在队列前面,从而配套使用的放置策略就是首次适应法了).
分区回收有四种情况：
1.待回收区(以下称为自由块)与自由主存队列中有上邻空闲区,回收时直接将其大小加到其上邻空闲区的大小上即可.
2.自由块有下邻空闲区,此时需要将前驱的next指针改为指向自由块首址,而将自由块的next指针指向其下邻空闲区中的下一节点,同时合并大小.
3.自由块既有上邻区也有下邻区,此时需要将其上邻区的next指针指向自由块下邻区的next指向的地址,同时合并三个可用分区的大小.
4.自由块不存在空闲邻区,是独立的一块.此时将其插入到自由主存队列中即可.由于在合并分区的时候已经是以按地址来放置队列的,故无须再对队列中元素进行排序了.
模拟实现：
先分配256个字节作为模拟的主存(以下称虚主存),然后插入4个任务(即task1,task2,task3,task4).每个分区描述器占了6个字节,free_head是自由主存队列的头指针.回收分区时,每回收一次后,系统又重新复位了任务在虚主存中(便于模拟四次的回收情况).其中task1有上邻空闲区(属第1种情况),task2属第4种情况,task3属于第2种情况,task4属于第3种情况.输出信息时是从虚主存的低地址开始的,依次输出队列中的各可用空间(含分区描述器大小).
*/
/*本程序在TC2.0下编译通过――铁木箱子*/
#include
#include
typedef struct PD /* 分区描述器数据结构 */
{
int flag;
int size;
struct PD *next;
}node,*LINK;
LINK free_head;
LINK task1,task2,task3,task4; /* tasks */
char *p;
void Init() /*初始化模拟内存内的任务和空闲区*/
{
char *tmp;
LINK cursor; /* temp pointer */
tmp=p;
task1=(LINK)(tmp+30); /* 事先各作业的分配情况 */
task2=(LINK)(tmp+70);
task3=(LINK)(tmp+130);
task4=(LINK)(tmp+196);
task1->flag=1;task1->size=40;task1->next=NULL;
task2->flag=1;task2->size=60;task2->next=NULL;
task3->flag=1;task3->size=30;task3->next=NULL;
task4->flag=1;task4->size=35;task4->next=NULL;
free_head=(LINK)tmp; /* free memory queue */
cursor=free_head;
cursor->flag=0;cursor->size=30;cursor->next=(LINK)(tmp+160);
cursor=cursor->next;
cursor->flag=0;cursor->size=36;cursor->next=(LINK)(tmp+231);
cursor=cursor->next;
cursor->flag=0;cursor->size=25;cursor->next=NULL;
}
void PrintInfo(int n) /* 打印自由主存队列信息 */
{
LINK temp;
temp=free_head;
printf("nAfter free task%d,free memory are:",n);
while(temp)
{
printf("%-3d ",temp->size);
temp=temp->next;
}
printf("n");
}