C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloca()和回收过程free()。其中空闲分区通过空闲分区链来管理;在进行内存分配时,系统优先是有空闲分区低端的空间,假设初始状态下的可用的内存空间为640KB,自行设计作业的请求序列,分别采用首次适应算法和最佳适应算法进行内存块的分配和回收,要求每次分配和回收后显示出空闲内存分区链的情况的代码
时间: 2024-02-03 17:12:25 浏览: 29
以下是使用首次适应算法的动态分区分配过程alloca()和回收过程free()的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义内存块结构体
typedef struct block {
int start; // 内存块起始位置
int size; // 内存块大小
struct block *next; // 下一个空闲内存块
} Block;
// 初始化内存块链表
Block *initBlockList(int start, int size) {
Block *head = (Block *)malloc(sizeof(Block));
head->start = start;
head->size = size;
head->next = NULL;
return head;
}
// 显示空闲内存块链表
void showBlockList(Block *head) {
printf("空闲内存分区链:\n");
while (head != NULL) {
printf("起始地址:%d\t大小:%d\n", head->start, head->size);
head = head->next;
}
printf("\n");
}
// 首次适应算法内存分配函数
int firstFit(Block *head, int size) {
Block *p = head;
while (p != NULL) {
if (p->size >= size) { // 找到第一个合适的空闲内存块
if (p->size == size) { // 内存块大小刚好等于请求大小
p->start = -1; // 标记为已分配
} else { // 内存块大小大于请求大小
Block *newBlock = (Block *)malloc(sizeof(Block)); // 创建新的空闲内存块
newBlock->start = p->start;
newBlock->size = size;
newBlock->next = p->next;
p->start += size;
p->size -= size;
p->next = newBlock;
}
return p->start + 1; // 返回分配的内存块起始地址,加1是因为要跳过标记位
}
p = p->next;
}
return -1; // 没有找到合适的空闲内存块
}
// 内存回收函数
void freeBlock(Block *head, int start) {
Block *p = head;
while (p != NULL) {
if (p->start == -1 && p->next != NULL && p->next->start == start) { // 合并相邻的空闲内存块
p->size += p->next->size;
Block *temp = p->next;
p->next = temp->next;
free(temp);
break;
} else if (p->start == start) { // 标记为空闲内存块
p->start = 0;
break;
}
p = p->next;
}
}
int main() {
int start = 0; // 内存起始地址
int size = 640; // 内存大小
Block *head = initBlockList(start, size); // 初始化空闲内存块链表
// 请求序列
int request[5] = {100, 200, 50, 300, 180};
// 首次适应算法内存分配过程
printf("首次适应算法:\n");
for (int i = 0; i < 5; i++) {
int addr = firstFit(head, request[i]);
if (addr == -1) {
printf("第%d个作业无法分配内存\n", i+1);
} else {
printf("第%d个作业分配了%dKB内存,起始地址为:%d\n", i+1, request[i], addr);
showBlockList(head);
}
}
// 内存回收过程
printf("内存回收:\n");
freeBlock(head, 0);
freeBlock(head, 500);
showBlockList(head);
return 0;
}
```
以下是使用最佳适应算法的动态分区分配过程alloca()和回收过程free()的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义内存块结构体
typedef struct block {
int start; // 内存块起始位置
int size; // 内存块大小
struct block *next; // 下一个空闲内存块
} Block;
// 初始化内存块链表
Block *initBlockList(int start, int size) {
Block *head = (Block *)malloc(sizeof(Block));
head->start = start;
head->size = size;
head->next = NULL;
return head;
}
// 显示空闲内存块链表
void showBlockList(Block *head) {
printf("空闲内存分区链:\n");
while (head != NULL) {
printf("起始地址:%d\t大小:%d\n", head->start, head->size);
head = head->next;
}
printf("\n");
}
// 最佳适应算法内存分配函数
int bestFit(Block *head, int size) {
Block *p = head;
Block *bestBlock = NULL; // 最佳的空闲内存块
while (p != NULL) {
if (p->size >= size) { // 找到一个合适的空闲内存块
if (bestBlock == NULL || p->size < bestBlock->size) { // 更新最佳的空闲内存块
bestBlock = p;
}
}
p = p->next;
}
if (bestBlock != NULL) {
if (bestBlock->size == size) { // 内存块大小刚好等于请求大小
bestBlock->start = -1; // 标记为已分配
} else { // 内存块大小大于请求大小
Block *newBlock = (Block *)malloc(sizeof(Block)); // 创建新的空闲内存块
newBlock->start = bestBlock->start;
newBlock->size = size;
newBlock->next = bestBlock->next;
bestBlock->start += size;
bestBlock->size -= size;
bestBlock->next = newBlock;
}
return bestBlock->start + 1; // 返回分配的内存块起始地址,加1是因为要跳过标记位
} else {
return -1; // 没有找到合适的空闲内存块
}
}
// 内存回收函数
void freeBlock(Block *head, int start) {
Block *p = head;
while (p != NULL) {
if (p->start == -1 && p->next != NULL && p->next->start == start) { // 合并相邻的空闲内存块
p->size += p->next->size;
Block *temp = p->next;
p->next = temp->next;
free(temp);
break;
} else if (p->start == start) { // 标记为空闲内存块
p->start = 0;
break;
}
p = p->next;
}
}
int main() {
int start = 0; // 内存起始地址
int size = 640; // 内存大小
Block *head = initBlockList(start, size); // 初始化空闲内存块链表
// 请求序列
int request[5] = {100, 200, 50, 300, 180};
// 最佳适应算法内存分配过程
printf("最佳适应算法:\n");
for (int i = 0; i < 5; i++) {
int addr = bestFit(head, request[i]);
if (addr == -1) {
printf("第%d个作业无法分配内存\n", i+1);
} else {
printf("第%d个作业分配了%dKB内存,起始地址为:%d\n", i+1, request[i], addr);
showBlockList(head);
}
}
// 内存回收过程
printf("内存回收:\n");
freeBlock(head, 0);
freeBlock(head, 500);
showBlockList(head);
return 0;
}
```