采用首次适应算法实现动态分区分配过程的模拟

向右看齐 2023-03-12 12:19 14阅读 0赞

# 采用首次适应算法实现动态分区分配过程的模拟 #

## 实验要求 ##

用C语言编程，实现采用首次适应算法的动态分区分配过程

## 实验内容 ##

（1）空闲分区通过空闲分区链来管理；进行内存分配时，系统优先使用空闲区低端的空间。  
（2）假设初始状态下可用的内存空间为640KB，并有下列的请求序列：  
作业1申请130KB  
作业2申请60KB  
作业3申请100KB  
作业2释放60KB  
作业4申请200KB  
作业3释放100KB  
作业1释放130KB  
作业5申请140KB  
作业6申请60KB  
作业7申请50KB  
作业6释放60KB

采用首次适应算法进行内存块的分配，要求每次分配后显示出空闲内存分区链的情况。

## 程序流程图 ##

![程序流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]

> 注：本程序使用了双向链表

## 程序源代码 ##

#include <stdio.h>
    #include <stdlib.h>
    
    enum isAllocated{ yes, no};		// 是否分配
    
    typedef struct Node { 
    	int id;						// 作业号（如果是未分配的空闲分区，则为-1）
    	int start;					// 起始地址
    	int length;					// 大小
    	enum isAllocated isallocated;	// 是否分配
    	struct Node* next;			// 指向后面的Node
    	struct Node* prev;			// 指向前面的Node
    }Node;
    
    Node* head;						// 链表的头指针
    
    // 打印菜单
    void printMenu() { 
    	
    	printf("\n1. 申请内存\n");
    	printf("2. 释放内存\n");
    	printf("0. 退出\n");
    	printf("请选择：");
    }
    
    // 初始化（新建一个和内存相同大小的空闲结点）
    void init(int capacity) { 
    	Node* p = (Node*)malloc(sizeof(Node));		// 给新结点开辟空间
    	p->id = -1;
    	p->start = 0;
    	p->length = capacity;
    	p->isallocated = no;
    	p->prev = NULL;
    	p->next = NULL;
    
    	head = p;
    }
    
    // 打印空闲分区
    void printSpare() { 
    	Node* p = head;
    	printf("空闲分区如下：\n起始地址\t长度\n---------------------\n");
    	while (p != NULL) { 
    		if (p->isallocated == no) { 
    			printf("%d\t\t%d\n", p->start, p->length);
    		}
    		p = p->next;
    	}
    }
    
    // 申请内存
    void getMemory() { 
    	int id, size;
    	Node* p;
    	printf("请输入作业号和要申请的内存大小:");
    	scanf("%d%d", &id, &size);
    
    	p = head;
    	while (p != NULL) { 
    		// 当找到一块长度大于所需空间的空闲分区时
    		if (p->isallocated == no && p->length > size) { 
    			// 首先新建一个结点
    			Node* newNode = (Node*)malloc(sizeof(Node));
    			newNode->id = id;
    			newNode->length = size;			// 新结点的长度即所需空间的大小
    			newNode->isallocated = yes;
    			newNode->start = p->start;		// 新结点的起始地址即空闲分区的起始地址
    			p->start += size;				// 空闲分区的起始地址修改为新结点的末尾
    			p->length -= size;				// 空闲分区的长度做相应的修改
    			// 判断这块空闲分区是不是第一块分区
    			if (p != head) { 
    				newNode->prev = p->prev;
    				p->prev->next = newNode;
    				newNode->next = p;
    				p->prev = newNode;
    			}
    			else { 
    				newNode->prev = NULL;
    				newNode->next = p;
    				p->prev = newNode;
    				head = newNode;
    			}
    			break;
    		}	// 当找到一块长度恰好等于所需空间的空闲分区时
    		else if (p->isallocated == no && p->length == size) { 
    			p->id = id;				// 直接修改作业号
    			p->isallocated = yes;
    			break;
    		}
    		p = p->next;
    	}
    
    	if (p == NULL) { 
    		printf("没有足够的内存可以分配了!\n");
    	}
    }
    
    // 释放内存
    void returnMemory() { 
    	int id;
    	Node* p;
    	printf("请输入要释放内存的作业号:");
    	scanf("%d", &id);
    
    	p = head;
    	while (p != NULL) { 
    		// 根据作业号查找要释放的作业
    		if (p->id == id) { 
    			p->id = -1;
    			p->isallocated = no;
    			// 如果此作业前面还有空闲分区，则与之合并
    			if (p->prev != NULL && p->prev->isallocated == no) { 
    				p->start = p->prev->start;
    				p->length += p->prev->length;
    				p->prev = p->prev->prev;
    				p->prev->next = p;
    			}
    			// 如果此作业后面还有空闲分区，则与之合并
    			if (p->next != NULL && p->next->isallocated == no) { 
    				p->length += p->next->length;
    				p->next = p->next->next;
    				p->next->prev = p;
    			}
    			break;
    		}
    		p = p->next;
    	}
    
    	if (p == NULL) { 
    		printf("您输入的作业号不存在!\n");
    	}
    }
    
    int main() { 
    	int option;			// 用户选择的选项
    	int capacity;		// 内存容量
    
    	printf("请先输入内存的容量：");
    	scanf("%d", &capacity);
    	init(capacity);		// 根据内存容量进行初始化
    	printSpare();
    
    	while (1) { 
    		printMenu();			// 打印菜单
    		scanf("%d", &option);	// 输入选项
    		switch (option)			// 判断选项
    		{ 
    		case 1:
    			getMemory();		// 申请内存
    			break;
    		case 2:
    			returnMemory();		// 释放内存
    			break;
    		case 0:					// 退出
    			return 0;
    		default:
    			break;
    		}
    		printSpare();		// 打印空闲分区
    	}
    	return 0;
    }

## 程序运行截图 ##

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 2]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 3]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]: /images/20230312/35168cfa8f6043f8b96f50c7567d2052.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200508212805377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200508212954258.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200508213022678.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 4]: /images/20230312/6142bead5dde435f86420d0a69cd948c.png