C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloca()和回收过程free()。其中空闲分区通过空闲分区链来管理;在进行内存分配时,系统优先是有空闲分区低端的空间,假设初始状态下的可用的内存空间为640KB,自行设计作业的请求序列,分别采用首次适应算法和最佳适应算法进行内存块的分配和回收,要求每次分配和回收后显示出空闲内存分区链的情况的代码
时间: 2024-02-03 20:12:24 浏览: 16
首次适应算法的代码实现:
```c
#include <stdio.h>
#define MEM_SIZE 640 // 内存总大小
#define ALLOC_ERROR -1 // 内存分配错误返回标志
// 定义内存块结构体
typedef struct mem_block {
int size; // 内存块大小
int start; // 内存块起始地址
struct mem_block* next; // 指向下一个内存块
} MemBlock;
// 定义空闲分区链表的头结点
MemBlock* free_list_head;
// 初始化空闲分区链表
void init_free_list() {
free_list_head = (MemBlock*)malloc(sizeof(MemBlock));
free_list_head->size = MEM_SIZE;
free_list_head->start = 0;
free_list_head->next = NULL;
}
// 显示空闲分区链表
void show_free_list() {
MemBlock* p = free_list_head;
printf("Free List:\n");
while (p != NULL) {
printf(" [start:%d, size:%d]\n", p->start, p->size);
p = p->next;
}
}
// 内存分配函数
int my_alloc(int size) {
MemBlock* p = free_list_head;
MemBlock* pre = NULL;
while (p != NULL) {
if (p->size >= size) { // 如果当前空闲分区可以满足请求
if (p->size == size) { // 如果当前空闲分区大小等于请求大小
if (pre == NULL) { // 如果当前空闲分区为链表头
free_list_head = p->next;
} else {
pre->next = p->next;
}
} else { // 如果当前空闲分区大小大于请求大小
p->size -= size;
p->start += size;
}
return p->start;
}
pre = p;
p = p->next;
}
return ALLOC_ERROR; // 没有符合请求的空闲分区
}
// 内存回收函数
void my_free(int start, int size) {
MemBlock* p = free_list_head;
MemBlock* pre = NULL;
while (p != NULL && p->start < start) { // 找到插入位置
pre = p;
p = p->next;
}
if (pre == NULL) { // 如果回收分区插入到链表头
free_list_head = (MemBlock*)malloc(sizeof(MemBlock));
free_list_head->size = size;
free_list_head->start = start;
free_list_head->next = p;
} else if (pre->start + pre->size == start) { // 如果回收分区与前一个空闲分区合并
pre->size += size;
if (p != NULL && start + size == p->start) { // 如果回收分区与后一个空闲分区也合并
pre->size += p->size;
pre->next = p->next;
free(p);
}
} else if (p != NULL && start + size == p->start) { // 如果回收分区与后一个空闲分区合并
p->size += size;
p->start = start;
} else { // 如果回收分区不与任何空闲分区合并
MemBlock* new_block = (MemBlock*)malloc(sizeof(MemBlock));
new_block->size = size;
new_block->start = start;
new_block->next = p;
pre->next = new_block;
}
}
int main() {
init_free_list(); // 初始化空闲分区链表
// 采用首次适应算法进行内存块的分配和回收
int alloc1_size[] = {120, 250, 60, 150, 100, 70};
int alloc1_len = sizeof(alloc1_size) / sizeof(alloc1_size[0]);
for (int i = 0; i < alloc1_len; i++) {
int start_addr = my_alloc(alloc1_size[i]);
if (start_addr == ALLOC_ERROR) {
printf("Memory allocation failed!\n");
break;
} else {
printf("Allocate %d bytes of memory at address %d\n", alloc1_size[i], start_addr);
show_free_list();
}
}
my_free(0, 120);
printf("Free 120 bytes of memory at address %d\n", 0);
show_free_list();
my_free(190, 60);
printf("Free 60 bytes of memory at address %d\n", 190);
show_free_list();
my_free(310, 100);
printf("Free 100 bytes of memory at address %d\n", 310);
show_free_list();
my_free(400, 200);
printf("Free 200 bytes of memory at address %d\n", 400);
show_free_list();
return 0;
}
```
最佳适应算法的代码实现:
```c
#include <stdio.h>
#define MEM_SIZE 640 // 内存总大小
#define ALLOC_ERROR -1 // 内存分配错误返回标志
// 定义内存块结构体
typedef struct mem_block {
int size; // 内存块大小
int start; // 内存块起始地址
struct mem_block* next; // 指向下一个内存块
} MemBlock;
// 定义空闲分区链表的头结点
MemBlock* free_list_head;
// 初始化空闲分区链表
void init_free_list() {
free_list_head = (MemBlock*)malloc(sizeof(MemBlock));
free_list_head->size = MEM_SIZE;
free_list_head->start = 0;
free_list_head->next = NULL;
}
// 显示空闲分区链表
void show_free_list() {
MemBlock* p = free_list_head;
printf("Free List:\n");
while (p != NULL) {
printf(" [start:%d, size:%d]\n", p->start, p->size);
p = p->next;
}
}
// 内存分配函数
int my_alloc(int size) {
MemBlock* p = free_list_head;
MemBlock* pre = NULL;
MemBlock* min_p = NULL;
MemBlock* min_pre = NULL;
int min_size = MEM_SIZE + 1;
while (p != NULL) {
if (p->size >= size && p->size < min_size) { // 如果当前空闲分区可以满足请求且比当前最小空闲分区更小
min_p = p;
min_pre = pre;
min_size = p->size;
}
pre = p;
p = p->next;
}
if (min_p == NULL) {
return ALLOC_ERROR; // 没有符合请求的空闲分区
}
if (min_p->size == size) { // 如果当前空闲分区大小等于请求大小
if (min_pre == NULL) { // 如果当前空闲分区为链表头
free_list_head = min_p->next;
} else {
min_pre->next = min_p->next;
}
} else { // 如果当前空闲分区大小大于请求大小
min_p->size -= size;
min_p->start += size;
}
return min_p->start;
}
// 内存回收函数
void my_free(int start, int size) {
MemBlock* p = free_list_head;
MemBlock* pre = NULL;
while (p != NULL && p->start < start) { // 找到插入位置
pre = p;
p = p->next;
}
if (pre == NULL) { // 如果回收分区插入到链表头
free_list_head = (MemBlock*)malloc(sizeof(MemBlock));
free_list_head->size = size;
free_list_head->start = start;
free_list_head->next = p;
} else if (pre->start + pre->size == start) { // 如果回收分区与前一个空闲分区合并
pre->size += size;
if (p != NULL && start + size == p->start) { // 如果回收分区与后一个空闲分区也合并
pre->size += p->size;
pre->next = p->next;
free(p);
}
} else if (p != NULL && start + size == p->start) { // 如果回收分区与后一个空闲分区合并
p->size += size;
p->start = start;
} else { // 如果回收分区不与任何空闲分区合并
MemBlock* new_block = (MemBlock*)malloc(sizeof(MemBlock));
new_block->size = size;
new_block->start = start;
new_block->next = p;
pre->next = new_block;
}
}
int main() {
init_free_list(); // 初始化空闲分区链表
// 采用最佳适应算法进行内存块的分配和回收
int alloc1_size[] = {120, 250, 60, 150, 100, 70};
int alloc1_len = sizeof(alloc1_size) / sizeof(alloc1_size[0]);
for (int i = 0; i < alloc1_len; i++) {
int start_addr = my_alloc(alloc1_size[i]);
if (start_addr == ALLOC_ERROR) {
printf("Memory allocation failed!\n");
break;
} else {
printf("Allocate %d bytes of memory at address %d\n", alloc1_size[i], start_addr);
show_free_list();
}
}
my_free(0, 120);
printf("Free 120 bytes of memory at address %d\n", 0);
show_free_list();
my_free(190, 60);
printf("Free 60 bytes of memory at address %d\n", 190);
show_free_list();
my_free(310, 100);
printf("Free 100 bytes of memory at address %d\n", 310);
show_free_list();
my_free(400, 200);
printf("Free 200 bytes of memory at address %d\n", 400);
show_free_list();
return 0;
}
```