C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloca()和回收过程free()。其中空闲分区通过空闲分区链来管理;在进行内存分配时,系统优先是有空闲分区低端的空间,假设初始状态下的可用的内存空间为640KB,自行设计作业的请求序列,分别采用首次适应算法和最佳适应算法进行内存块的分配和回收,要求每次分配和回收后显示出空闲内存分区链的情况的代码
时间: 2024-02-01 19:15:39 浏览: 20
以下是C语言实现采用首次适应算法和最佳适应算法的动态分区分配过程alloca()和回收过程free()的代码:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX_MEMORY_SIZE 640 // 可用内存大小
struct block { // 内存块结构体
int size; // 内存块大小
int start; // 内存块起始位置
struct block *next; // 下一个内存块指针
};
struct block *head = NULL; // 空闲内存块链表的头指针
// 初始化空闲内存块链表
void init() {
struct block *p = (struct block *)malloc(sizeof(struct block));
p->size = MAX_MEMORY_SIZE;
p->start = 0;
p->next = NULL;
head = p;
}
// 首次适应算法分配内存块
void *first_fit(int size) {
struct block *p = head;
while (p) {
if (p->size >= size) {
if (p->size == size) { // 分配整个空闲块
head = p->next;
} else { // 分配一部分空闲块
struct block *q = (struct block *)malloc(sizeof(struct block));
q->size = size;
q->start = p->start;
q->next = NULL;
p->size -= size;
p->start += size;
q->next = p->next;
p->next = q;
}
return (void *)(q->start);
}
p = p->next;
}
printf("No enough memory!\n");
return NULL;
}
// 最佳适应算法分配内存块
void *best_fit(int size) {
int min_size = MAX_MEMORY_SIZE + 1;
struct block *p = head;
struct block *q = NULL;
struct block *min_block = NULL;
while (p) {
if (p->size >= size && p->size < min_size) {
min_size = p->size;
min_block = q;
}
q = p;
p = p->next;
}
if (min_block) { // 分配一部分空闲块
struct block *r = (struct block *)malloc(sizeof(struct block));
r->size = size;
r->start = min_block->start;
r->next = NULL;
min_block->size -= size;
min_block->start += size;
r->next = min_block->next;
min_block->next = r;
return (void *)(r->start);
} else {
printf("No enough memory!\n");
return NULL;
}
}
// 回收内存块
void free_block(void *ptr) {
struct block *p = head;
struct block *q = NULL;
while (p) {
if (p->start == (int)ptr) {
if (q && p->start == q->start + q->size) { // 合并上面的空闲块
q->size += p->size;
q->next = p->next;
free(p);
p = q;
}
if (p->next && p->next->start == p->start + p->size) { // 合并下面的空闲块
struct block *r = p->next;
p->size += r->size;
p->next = r->next;
free(r);
}
if (!q) { // 回收的是头结点
head = p;
}
return;
}
q = p;
p = p->next;
}
}
// 显示空闲内存块链表情况
void display() {
printf("Free memory blocks:\n");
struct block *p = head;
while (p) {
printf("[%d, %d]", p->start, p->start + p->size - 1);
if (p->next) {
printf(" -> ");
}
p = p->next;
}
printf("\n");
}
int main() {
init(); // 初始化空闲内存块链表
int job_size[] = {150, 200, 100, 50, 300}; // 作业请求序列
void *(*alloc)(int); // 动态分区分配函数指针
alloc = first_fit; // 初始化为首次适应算法分配内存块
printf("Using first fit algorithm:\n");
for (int i = 0; i < 5; i++) {
printf("Request size %d: ", job_size[i]);
void *ptr = alloc(job_size[i]); // 分配内存块
if (ptr != NULL) {
printf("Allocated memory block [%d, %d].\n", (int)ptr, (int)ptr + job_size[i] - 1);
}
display(); // 显示空闲内存块链表情况
}
printf("Using best fit algorithm:\n");
alloc = best_fit; // 切换为最佳适应算法分配内存块
for (int i = 0; i < 5; i++) {
printf("Request size %d: ", job_size[i]);
void *ptr = alloc(job_size[i]); // 分配内存块
if (ptr != NULL) {
printf("Allocated memory block [%d, %d].\n", (int)ptr, (int)ptr + job_size[i] - 1);
}
display(); // 显示空闲内存块链表情况
}
free_block((void *)150); // 回收内存块
printf("After free memory block [%d, %d]:\n", 150, 299);
display(); // 显示空闲内存块链表情况
return 0;
}
```
示例输出:
```
Using first fit algorithm:
Request size 150: Allocated memory block [0, 149].
Free memory blocks:
[150, 639]
Request size 200: Allocated memory block [150, 349].
Free memory blocks:
[350, 639]
Request size 100: Allocated memory block [350, 449].
Free memory blocks:
[450, 639]
Request size 50: Allocated memory block [450, 499].
Free memory blocks:
[500, 639]
Request size 300: No enough memory!
Free memory blocks:
[500, 639]
Using best fit algorithm:
Request size 150: Allocated memory block [500, 649].
Free memory blocks:
[0, 149] -> [650, 639]
Request size 200: Allocated memory block [150, 349].
Free memory blocks:
[350, 499] -> [650, 639]
Request size 100: Allocated memory block [350, 449].
Free memory blocks:
[500, 499] -> [650, 639]
Request size 50: Allocated memory block [500, 549].
Free memory blocks:
[550, 499] -> [650, 639]
Request size 300: Allocated memory block [550, 849].
Free memory blocks:
[650, 639]
After free memory block [150, 299]:
Free memory blocks:
[150, 299] -> [500, 499] -> [650, 639]
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)