实验名称：
采用首次适应算法实现动态分区分配过程的模拟
实验要求：
用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
采用首次适应算法进行内存块的分配，要求每次分配后显示出空闲内存分区链的情况。
任务分析
根据首次适应算法的特点和实验要求，本程序采用双向链表作为主要数据结构，每块分区作为链表上的一个结点。创建一个结构体来表示结点，分区起始地址、分区长度、作业号、分区是否分配等作为结构体的属性。在此我们约定作业号为正数。如果分区已分配，则作业号即表示真正的作业号；否则作业号为-1，来表示空闲分区。只有空闲分区可以拿来分配，已分配的分区不能再分配。
程序流程图
程序流程图
程序源代码
#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;
}
运行结果
Snipaste_2020-05-08_21-14-52.png
Snipaste_2020-05-08_21-25-26.png
Snipaste_2020-05-08_21-26-03.png
Snipaste_2020-05-08_21-26-57.png
