【Linux实践2】实验四：存储管理

---

一、存储管理的目的

1.1 内存空间的分配与回收

操作系统需要确保每个程序都能获得所需的内存空间，并在不需要时释放内存，以避免资源浪费。

1.2 地址转换

操作系统为每个程序提供相对地址或虚拟地址，并负责将这些地址转换为物理地址。

1.3 内存保护

防止一个程序访问另一个程序的内存空间，确保系统的稳定性和安全性。

1.4 内存共享

允许多个程序共享同一块内存区域，提高内存使用效率。

1.5 内存扩充

通过虚拟内存技术，使得程序可以使用比物理内存更大的地址空间。

二、可变分区存储管理

2.1 分区结构体定义

我们定义了一个分区结构体Partition，用于描述内存分区的状态，包括分区的ID、大小、起始地址、状态（空闲或已分配）以及指向下一个分区的指针。

typedef struct Partition {int id;int size;int start;int status;  // 0表示空闲，1表示已分配struct Partition *next;
} Partition;

2.2 初始化分区链表

通过initPartitionList函数，我们初始化了一个分区链表，模拟了内存的初始状态。

Partition* initPartitionList() {Partition *head = (Partition *)malloc(sizeof(Partition));head->id = 0;head->size = 1024;  // 假设初始内存大小为1024head->start = 0;head->status = 0;head->next = NULL;return head;
}

三、内存分配算法实现

3.1 首次适应算法（First Fit）

首次适应算法从内存分区链表的开始进行搜索，找到第一个足够大的空闲分区进行分配。

3.1.1 算法实现

在firstFit函数中，我们遍历分区链表，寻找第一个状态为空闲且大小足够大的分区进行分配，并可能进行分区分割。

Partition* firstFit(Partition *head, int jobSize) {Partition *curr = head;while (curr != NULL) {if (curr->status == 0 && curr->size >= jobSize) {// 如果找到合适的空闲分区，进行分配curr->status = 1;// 如果分区大小大于作业需求，进行分割if (curr->size > jobSize) {Partition *newPartition = (Partition *)malloc(sizeof(Partition));newPartition->id = curr->id + 1;newPartition->size = curr->size - jobSize;newPartition->start = curr->start + jobSize;newPartition->status = 0;newPartition->next = curr->next;curr->size = jobSize;curr->next = newPartition;}return curr;}curr = curr->next;}return NULL;  // 未找到合适分区
}

3.2 循环首次适应算法（Next Fit）

循环首次适应算法从上一次分配结束的位置开始搜索，而不是从头开始。

3.2.1 算法实现

在circularFirstFit函数中，我们使用一个last指针来记录上次分配的结束位置，并从该位置开始搜索合适的分区。

Partition* circularFirstFit(Partition *head, int jobSize) {Partition *curr = head;Partition *last = NULL;do {if (curr->status == 0 && curr->size >= jobSize) {// 如果找到合适的空闲分区，进行分配curr->status = 1;// 如果分区大小大于作业需求，进行分割if (curr->size > jobSize) {Partition *newPartition = (Partition *)malloc(sizeof(Partition));newPartition->id = curr->id + 1;newPartition->size = curr->size - jobSize;newPartition->start = curr->start + jobSize;newPartition->status = 0;newPartition->next = curr->next;curr->size = jobSize;curr->next = newPartition;}return curr;}last = curr;curr = curr->next;} while (curr != head);return NULL;  // 未找到合适分区
}

3.3 最佳适应算法（Best Fit）

最佳适应算法搜索整个分区链表，找到能够满足请求且剩余空间最小的空闲分区进行分配。

3.3.1 算法实现

在bestFit函数中，我们遍历整个分区链表，记录并返回最小的足够大的空闲分区。

Partition* bestFit(Partition *head, int jobSize) {Partition *best = NULL;Partition *curr = head;while (curr != NULL) {if (curr->status == 0 && curr->size >= jobSize) {if (best == NULL || curr->size < best->size) {best = curr;}}curr = curr->next;}if (best != NULL) {best->status = 1;// 如果分区大小大于作业需求，进行分割if (best->size > jobSize) {Partition *newPartition = (Partition *)malloc(sizeof(Partition));newPartition->id = best->id + 1;newPartition->size = best->size - jobSize;newPartition->start = best->start + jobSize;newPartition->status = 0;newPartition->next = best->next;best->size = jobSize;best->next = newPartition;}}return best;  // 返回找到的最佳分区或NULL（未找到合适分区）
}

四、内存回收与分区链表维护

4.1 回收内存

在releaseMemory函数中，我们释放了指定分区的内存，并尝试与相邻的空闲分区合并，以减少内存碎片。

void releaseMemory(Partition *head, int partitionId) {Partition *curr = head;Partition *prev = NULL;while (curr != NULL && curr->id != partitionId) {prev = curr;curr = curr->next;}if (curr != NULL) {curr->status = 0;// 合并相邻的空闲分区if (prev != NULL && prev->status == 0) {prev->size += curr->size;prev->next = curr->next;free(curr);curr = prev;}if (curr->next != NULL && curr->next->status == 0) {curr->size += curr->next->size;Partition *temp = curr->next;curr->next = curr->next->next;free(temp);}}
}

4.2 打印分区链表状态

printPartitionList函数用于打印当前分区链表的状态，包括每个分区的ID、大小、起始地址和状态。

void printPartitionList(Partition *head) {Partition *curr = head;printf("分区ID\t分区大小\t起始地址\t状态\n");while (curr != NULL) {printf("%d\t\t%d\t\t%d\t\t%s\n", curr->id, curr->size, curr->start,curr->status == 0 ? "空闲" : "已分配");curr = curr->next;}
}

五、实验结果与分析

5.1 分配作业

通过调用不同的内存分配函数，我们为作业分配了内存，并记录了分配结果。

int main() {Partition *head = initPartitionList();// 使用首次适应算法分配作业Partition *assignedPartition1 = firstFit(head, 200);if (assignedPartition1 != NULL) {printf("首次适应算法：作业分配到分区ID：%d\n", assignedPartition1->id);} else {printf("首次适应算法：未找到合适分区分配作业\n");}// 使用循环首次适应算法分配作业Partition *assignedPartition2 = circularFirstFit(head, 300);if (assignedPartition2 != NULL) {printf("循环首次适应算法：作业分配到分区ID：%d\n", assignedPartition2->id);} else {printf("循环首次适应算法：未找到合适分区分配作业\n");}// 使用最佳适应算法分配作业Partition *assignedPartition3 = bestFit(head, 150);if (assignedPartition3 != NULL) {printf("最佳适应算法：作业分配到分区ID：%d\n", assignedPartition3->id);} else {printf("最佳适应算法：未找到合适分区分配作业\n");}// 回收内存releaseMemory(head, assignedPartition1->id);releaseMemory(head, assignedPartition2->id);releaseMemory(head, assignedPartition3->id);// 打印分区链表最终状态printPartitionList(head);return 0;

5.2 回收内存

作业完成后，我们调用内存回收函数释放内存，并观察了分区链表的变化。

5.3 最终状态

实验结束时，我们打印了分区链表的最终状态，以验证内存分配和回收的正确性。

5.4 完整代码

#include <stdio.h>
#include <stdlib.h>// 定义分区结构体
typedef struct Partition {int id;int size;int start;int status;  // 0表示空闲，1表示已分配struct Partition *next;
} Partition;// 初始化分区链表
Partition* initPartitionList() {Partition *head = (Partition *)malloc(sizeof(Partition));head->id = 0;head->size = 1024;  // 假设初始内存大小为1024head->start = 0;head->status = 0;head->next = NULL;return head;
}// 首次适应算法分配内存
Partition* firstFit(Partition *head, int jobSize) {Partition *curr = head;while (curr!= NULL) {if (curr->status == 0 && curr->size >= jobSize) {// 如果找到合适的空闲分区，进行分配curr->status = 1;// 如果分区大小大于作业需求，进行分割if (curr->size > jobSize) {Partition *newPartition = (Partition *)malloc(sizeof(Partition));newPartition->id = curr->id + 1;newPartition->size = curr->size - jobSize;newPartition->start = curr->start + jobSize;newPartition->status = 0;newPartition->next = curr->next;curr->size = jobSize;curr->next = newPartition;}return curr;}curr = curr->next;}return NULL;  // 未找到合适分区
}// 循环首次适应算法分配内存
Partition* circularFirstFit(Partition *head, int jobSize) {Partition *curr = head;Partition *last = NULL;do {if (curr->status == 0 && curr->size >= jobSize) {// 如果找到合适的空闲分区，进行分配curr->status = 1;// 如果分区大小大于作业需求，进行分割if (curr->size > jobSize) {Partition *newPartition = (Partition *)malloc(sizeof(Partition));newPartition->id = curr->id + 1;newPartition->size = curr->size - jobSize;newPartition->start = curr->start + jobSize;newPartition->status = 0;newPartition->next = curr->next;curr->size = jobSize;curr->next = newPartition;}return curr;}last = curr;curr = curr->next;} while (curr!= head);return NULL;  // 未找到合适分区
}// 最佳适应算法分配内存
Partition* bestFit(Partition *head, int jobSize) {Partition *best = NULL;Partition *curr = head;while (curr!= NULL) {if (curr->status == 0 && curr->size >= jobSize) {if (best == NULL || curr->size < best->size) {best = curr;}}curr = curr->next;}if (best!= NULL) {best->status = 1;// 如果分区大小大于作业需求，进行分割if (best->size > jobSize) {Partition *newPartition = (Partition *)malloc(sizeof(Partition));newPartition->id = best->id + 1;newPartition->size = best->size - jobSize;newPartition->start = best->start + jobSize;newPartition->status = 0;newPartition->next = best->next;best->size = jobSize;best->next = newPartition;}}return best;  // 返回找到的最佳分区或NULL（未找到合适分区）
}// 回收内存
void releaseMemory(Partition *head, int partitionId) {Partition *curr = head;Partition *prev = NULL;while (curr!= NULL && curr->id!= partitionId) {prev = curr;curr = curr->next;}if (curr!= NULL) {curr->status = 0;// 合并相邻的空闲分区if (prev!= NULL && prev->status == 0) {prev->size += curr->size;prev->next = curr->next;free(curr);curr = prev;}if (curr->next!= NULL && curr->next->status == 0) {curr->size += curr->next->size;Partition *temp = curr->next;curr->next = curr->next->next;free(temp);}}
}// 打印分区链表状态
void printPartitionList(Partition *head) {Partition *curr = head;printf("分区ID\t分区大小\t起始地址\t状态\n");while (curr!= NULL) {printf("%d\t\t%d\t\t%d\t\t%s\n", curr->id, curr->size, curr->start,curr->status == 0? "空闲" : "已分配");curr = curr->next;}
}int main() {Partition *head = initPartitionList();// 使用首次适应算法分配作业Partition *assignedPartition1 = firstFit(head, 200);if (assignedPartition1!= NULL) {printf("首次适应算法：作业分配到分区ID：%d\n", assignedPartition1->id);} else {printf("首次适应算法：未找到合适分区分配作业\n");}// 使用循环首次适应算法分配作业Partition *assignedPartition2 = circularFirstFit(head, 300);if (assignedPartition2!= NULL) {printf("循环首次适应算法：作业分配到分区ID：%d\n", assignedPartition2->id);} else {printf("循环首次适应算法：未找到合适分区分配作业\n");}// 使用最佳适应算法分配作业Partition *assignedPartition3 = bestFit(head, 150);if (assignedPartition3!= NULL) {printf("最佳适应算法：作业分配到分区ID：%d\n", assignedPartition3->id);} else {printf("最佳适应算法：未找到合适分区分配作业\n");}// 回收内存releaseMemory(head, assignedPartition1->id);releaseMemory(head, assignedPartition2->id);releaseMemory(head, assignedPartition3->id);// 打印分区链表最终状态printPartitionList(head);return 0;
}

5.3 输出结果