最先适应分配算法

快来打我* 2022-02-04 02:53 70阅读 0赞

1．运行结果

假设内存中已装入三个作业，且形成三个空闲区，内存使用情况如图4.3所示。现有40K大小的作业a申请装入内存；作业a执行完毕后撤离系统。运行可变分区存储管理模拟程序进行内存分配和回收，将空闲区表和已分配区表的初值以及每次分配或回收后的变化显示输出。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzYzOTI5_size_16_color_FFFFFF_t_70][]

图4.3  内存使用情况

可变分区存储管理模拟程序运行结果如下所示。

<<---!!!@@@最先适应算法@@@!!!--->>

输入空闲区个数:3

输入空闲区0的起始地址和长度: 50  80

输入空闲区1的起始地址和长度: 200  50

输入空闲区2的起始地址和长度: 350  674

空闲区表:

起始地址  长度    状态

50       80          0

200              50     0

350      674    0

已分配区表:

起始地址  长度    状态         占用作业

0         50         1                  Unknow

130         70         1                  Unknow

250       100    1    Unknow

1.装入作业

2.撤销作业

请选择:1

输入作业名字: a

输入作业大小:40

空闲区表:

起始地址  长度    状态

90            40    0

200           50     0

350     674    0

已分配区表:

起始地址  长度    状态         占用作业

0         50         1                  Unknow

50        40    1     a

130         70          1                  Unknow

250       100    1    Unknow

1.装入作业

2.撤销作业

请选择:2

输入作业名：a

空闲区表:

起始地址  长度    状态

50       80         0

200              50     0

350      674    0

已分配区表:

起始地址  长度    状态         占用作业

0             50      1        Unknow

130        70           1             Unknow

250      100    1     Unknow

2．简要分析

程序运行时，用户输入目前空闲区的信息，内存其他区域为已分配区，内存管理程序初始化空闲区表和已分配区表，空闲区按地址递增的顺序排列。

当装入大小为40K的作业a时，程序顺序扫描空闲区表找到第一个能满足作业大小的空闲区，即起始地址为50K，大小为80K的空闲区，从此空闲区中分割40K分配给作业a，剩下的仍然作为一个空闲区登记在空闲区表中，程序输出了分配后空闲区表和已分配区表的信息。

作业a运行完毕后撤离系统，内存管理程序回收其内存空间，此时回收区后存在相邻的空闲区，将其合并成一个空闲区，程序输出了回收内存后空闲区表和已分配区表的信息。

#include "stdio.h"
    #include "string.h"
    
    #define n 100					// 最大空闲区个数
    int p_num = 0;					// 作业个数
    int num = 0;					// 空闲区个数
    
    struct
    {
    	char name[20];
    	int address;
    	int length;
    	int flag;
    } free_table[n], work_table[n], temp;
    
    void sort()		// 空闲区按起始地址从小到大排序
    {
    	int i;
    	for (i = 0; i < num - 1; i++)
    		for (int j = 0; j < num - i - 1; j++)
    			if (free_table[j].address > free_table[j + 1].address)
    			{
    				temp = free_table[j];
    				free_table[j] = free_table[j + 1];
    				free_table[j + 1] = temp;
    			}
    
    	for (i = 0; i < p_num - 1; i++)
    		for (int j = 0; j < p_num - i - 1; j++)
    			if (work_table[j].address > work_table[j + 1].address)
    			{
    				temp = work_table[j];
    				work_table[j] = work_table[j + 1];
    				work_table[j + 1] = temp;
    			}
    }
    
    
    void merge()		// 扫描空闲区若前后有相邻空闲区则合并
    {
    	for (int i = 0; i < num-1; i++)
    	{
    		if (free_table[i].address + free_table[i].length == free_table[i+1].address)
    		{
    			if(!free_table[i].flag && !free_table[i+1].flag)
    			{
    				free_table[i].length += free_table[i+1].length;
    				for (int j = i+1; j < num-1; j++)
    						free_table[j] = free_table[j + 1];
    				i--;
    				num--;
    			}
    		}
    	}
    }
    
    
    void output1()		// 输出空闲区表信息
    {
    	printf("\n空闲区表:\n起始地址  长度\t状态\n");
    	for (int i = 0; i < num; i++)
    		printf("%4d\t %3d\t%3d\n", free_table[i].address, free_table[i].length,
    			   free_table[i].flag);
    }
    
    void output2()		// 输出已分配区表信息
    {
    	printf("\n已分配区表:\n起始地址  长度\t状态\t占用作业\n");
    	for (int i = 0; i < p_num; i++)
    		printf("%4d\t %3d\t%3d\t%s\n", work_table[i].address, work_table[i].length,
    			   work_table[i].flag, work_table[i].name);
    }
    
    void init()			// 初始化空闲区信息
    {
    	int i;
    	printf("\n\t\t<<---!!!@@@最先适应算法@@@!!!--->>\n\n");
    	printf("输入空闲区个数:");
    	scanf("%d", &num);
    	for (i = 0; i < num; i++)
    	{
    		printf("输入空闲区%d的起始地址和长度: ", i);
    		scanf("%d%d", &free_table[i].address, &free_table[i].length);
    		free_table[i].flag = 0;
    	}
    	sort();
    	merge();
    
    	if(free_table[0].address!=0)
    {
    	work_table[p_num].address =0;
    	work_table[p_num].length =free_table[0].address;
    	work_table[p_num].flag = 1 ;
    	strcpy(work_table[p_num].name, "Unknow");
    	p_num++;
    }
    
    	for(i=0; i<num-1; i++)			
    	{ 
    			work_table[p_num].address = free_table[i].address + free_table[i].length;
    			work_table[p_num].length= free_table[i+1].address - work_table[p_num].address;
    			work_table[p_num].flag = 1;
    			strcpy(work_table[p_num].name, "Unknow");
    			p_num++;
    	}
    
    if(free_table[num-1].address+free_table[num-1].length!=1024)
    	{
    		work_table[p_num].address = free_table[num-1].address + free_table[num-1].length;
    		work_table[p_num].length = 1024 - work_table[p_num].address;
    		work_table[p_num].flag = 1 ;
    		strcpy(work_table[p_num].name, "Unknow");
    		p_num++;
    	}
      sort();
    	output1();
    	output2();
    }
    
    
    void input()		// 装入作业，分配内存
    {
    	int i, length;
    	char name[20];
    	printf("输入作业名字: ");
    	gets(name);
    	printf("输入作业大小: ");
    	scanf("%d", &length);
    	fflush(stdin);
    
    	for (i = 0; i < num; i++)
    	{
    		if(!free_table[i].flag)		
    		{
    			if (length < free_table[i].length)  
    			{
    				work_table[p_num].address = free_table[i].address;
    				free_table[i].length = free_table[i].length - length;
    				free_table[i].address = free_table[i].address + length;
    				strcpy(work_table[p_num].name, name);
    				work_table[p_num].flag = 1;
    				work_table[p_num].length = length;
    				p_num++;
    				break;
    			}
    			else if (length == free_table[i].length)
    			{
    				strcpy(work_table[p_num].name, name);
    				work_table[p_num].flag = 1;
    				work_table[p_num].address = free_table[i].address;
    				work_table[p_num].length = free_table[i].length;
    				p_num++;
    				for(int j=i; j<num; j++)
    				{
    					free_table[j]=free_table[j+1];
    				}
    				num--;			
    				break;
    			}
    		}
    	}
    	if (i == num)
    	{
    		puts("\n无合适空闲区，不能为作业分配内存！\n");
    		return;
    	}
    	sort();
    	output1();
    	output2();
    }
    
    void finish()				// 撤消作业，回收内存
    {
    	char name[20];
    	int i;
    	printf("输入作业名:");
    	gets(name);
    	fflush(stdin);
    	for (i = 0; i < p_num; i++)
    	{
    		if (!strcmp(name, work_table[i].name))
    		{
    			free_table[num] = work_table[i];
    			free_table[num].flag = 0;
    			num++;
    
    			sort();
    			merge();
    			
    
    			for(int j = i; j < p_num; j++)
    				work_table[j] = work_table[j+1];
    			p_num--;		
    			break;
    		}
    	}
    	if (i == p_num)
    		puts("\n没有此作业，重新输入！");
    	output1();
    	output2();
    }
    
    void FIRST_FIT()		
    {
    	init();
    	while (1)
    	{
    		int c;
    		printf("\n1.装入作业\n2.撤销作业\n请选择:");
    		scanf("%d",&c);
    		fflush(stdin);
    		if (c == 1)
    			input();
    		else if (c == 2)
    			finish();
    	}
    }
    
    int main(void)
    {
    	FIRST_FIT();
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzYzOTI5_size_16_color_FFFFFF_t_70]: /images/20220204/f19dfcc93cc54064851603d694a59beb.png