实验二 分区式存储管理
实验性质：设计
建议学时：2学时
实验目的：
通过这次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。
实验内容：
设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，釆用最坏适应算法从自 由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。
假定系统的内存共640K,初始状态为操作系统本身占用64K。在tl时间之后，有作业A、B、C、
D分别请求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业
E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出tl、t2、t3、t4时刻内存
的空闲区的状态。
实现提示（C语言）:
1.程序中自由链队列的结点类型可描述如下：
struct freelink（ int len, address; //len 为分区长度 //address为分区起始地址 struct freelink *next; }
内存占用区用链表描述，其结点类型描述如下：
struct busylink{ char name; //作业或进程名 name='S'表示OS占用 int len , address; struct busylink *next; }
并设全程量：
struct freelink *free_head=NULL; //自由链队列（带头结点）队首指针 struct busylink *busy_head=NULL, //占用区队列队（带头结点）首指针 * busy_tail=NULL ； //占用区队列队尾指针
2.设计子函数：
void start（void）; /*设置系统初始状态*/ struct freelink * p; struct busylink *q; free_head=(struct freelink*)malloc(sizeo instruct freelink)); free_head->next=NULL; //创建自由链头结点 busy_head=busy_tail=(struct busylinktf!)malloc(sizeof(struct busy link)); busy_head->next=NULL; //创建占用链头结点 p=( struct freelink *)malloc(sizeof(struct freelink)); p->add ress=64; p->Ien=640-64; //OS 占用了 64K p->next=NULL; freehea d->n ext=p; q=( struct busy link *)malloc(sizeofi(struct busylink)); q->name=,S,; //S表示操作系统占用 q->len=64; q->address=O; q->n ext=NULL; b usyh ea d->next=q; busy_tail=q; void } requireMemo(char name, int require); //模拟内存分配 void freeMemo(cha r name); //模拟内存回收 void past(int time); //模拟系统过了 time时间 void printlinkQ; //输出内存空闲情况（自由链的结点）
3.设计主函数：
int main() { start(); past(1); requireMemo('A', 8); requireMemo('B', 16); requireMemo('C', 400); requireMemo('D', 124); printlink(); past(2); freeMemo('C'); printlink(); past(3); requireMemo('E', 200); printlink(); freeMemo('B'); printlink(); freeMemo('D'); printlink(); system("pause"); return 0; }
实验要求：
1 上机前仔细编好程序；
2 上机时独立调试程序；
3 提交实验报告，包括纸质稿和电子稿两部分。实验报告要求详见实验报告模板。
实验用例：
代码展示
#include <iostream> #include <fstream> using namespace std; struct freelink { int len, address; freelink *next; }; struct busylink { char name; int len, address; busylink *next; }; freelink *free_head = NULL; busylink *busy_head = NULL; busylink *busy_tail = NULL; // 函数声明 void start(); // 模拟内存分配 void requireMemo(char name, int require); // 更新空闲区前先删除同首地址节点 void delete_freearea(int address); // 内存回收时删除占用区节点 void delete_busyarea(int address); // 将节点按序插入空闲区 void insert_freearea(freelink *my); // 模拟内存回收 void freeMemo(char name); // 模拟系统时间 void past(int time); // 输出内存空闲情况 void printlink(); int main() { start(); past(1); requireMemo('A', 8); requireMemo('B', 16); requireMemo('C', 400); requireMemo('D', 124); printlink(); past(2); freeMemo('C'); printlink(); past(3); requireMemo('E', 200); printlink(); freeMemo('B'); printlink(); freeMemo('D'); printlink(); system("pause"); return 0; } void start() { freelink *p; busylink *q; free_head = new freelink; free_head->next = NULL; busy_head = busy_tail = new busylink; busy_head->next = NULL; p = new freelink; p->address = 64; p->len = 640 - 64; p->next = NULL; free_head->next = p; q = new busylink; q->name = 'S'; q->len = 64; q->address = 0; q->next = NULL; busy_head->next = q; busy_tail = q; } void requireMemo(char name, int require) { freelink *p = free_head->next; if (p->len >= require) { busylink *tmp = new busylink; tmp->name = name; tmp->len = require; tmp->address = p->address; tmp->next = NULL; // 放入占用区末尾 busy_tail->next = tmp; busy_tail = tmp; // 更新空闲区 freelink *q = new freelink; q->next = NULL; q->len = p->len - require; q->address = p->address; delete_freearea(q->address); q->address = p->address + require; insert_freearea(q); } else { printf("Insufficient free space\n"); } } void delete_freearea(int address) { freelink *p = free_head; while (p->next) { if (address == p->next->address) { p->next = p->next->next; return; } p = p->next; } } void delete_busyarea(int address) { busylink *p = busy_head; while (p->next) { if (address == p->next->address) { p->next = p->next->next; if (p->next == NULL) { busy_tail = p; } return; } p = p->next; } } void insert_freearea(freelink *my) { freelink *q = free_head->next; int mystart = my->address; int myend = my->address + my->len; freelink *beforenode = NULL; freelink *afternode = NULL; while (q) { if (q->address + q->len == mystart) { beforenode = q; } if (myend == q->address) { afternode = q; } q = q->next; } if (beforenode) { delete_freearea(beforenode->address); my->address = beforenode->address; my->len += beforenode->len; } if (afternode) { delete_freearea(afternode->address); my->len += afternode->len; } freelink *p = free_head; while (p->next) { if (my->len >= p->next->len) { my->next = p->next; p->next = my; return; } p = p->next; } my->next = p->next; p->next = my; } void freeMemo(char name) { busylink *busyp = busy_head->next; freelink *freep = free_head->next; while (busyp) { if (busyp->name == name) { freelink *tmp = new freelink; tmp->address = busyp->address; tmp->len = busyp->len; tmp->next = NULL; delete_busyarea(tmp->address); insert_freearea(tmp); } busyp = busyp->next; } } void past(int time) { printf("After t%d:\n", time); } void printlink() { printf("The memory usage is:\n"); printf("Job\tStart address\tSize\n"); busylink *p = busy_head->next; while (p) { printf("%c\t%d\t\t%d\n", p->name, p->address, p->len); p = p->next; } printf("Memory free area is\n"); printf("Start address\tSize\n"); freelink *q = free_head->next; while (q) { printf("%d\t\t%d\n", q->address, q->len); q = q->next; } printf("------------------------------------\n"); }
