操作系统-存储管理动态分区分配及回收算法附源码.doc

. .存储管理动态分区分配及回收算法课程名称：计算机操作系统班级：信1501-2实验者XX：琛实验日期：2021年5月20日评分：教师签名：一、实验目的分区管理是应用较广泛的一种存储管理技术。本实验要求用一种构造化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同分配算法的特点。二、实验要求1、编写：First Fit Algorithm 2、编写：Best Fit Algorithm 3、编写：空闲区回收算法三、实验过程一主程序 1、定义分区描述器 node，包括 3 个元素：1adr分区首地址2size分区大小3next指向下一个分区的指针 2、定义 3 个指向 node 构造的指针变量：1head1空闲区队列首指针2back1指向释放区 node 构造的指针3assign指向申请的存分区 node 构造的指针 3、定义 1 个整形变量： free用户申请存储区的大小由用户键入二过程 1、定义 check 过程，用于检查指定的释放块由用户键入的合法性 2、定义 assignment1 过程，实现 First Fit Algorithm 3、定义 assignment2 过程，实现 Best Fit Algorithm 4、定义 acceptment1 过程，实现 First Fit Algorithm 的回收算法 5、定义 acceptment2 过程，实现 Best Fit Algorithm 的回收算法 6、定义 print 过程，打印空闲区队列三执行程序首先申请一整块空闲区，其首址为 0，大小为 32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。实验代码Main.cpp#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>usingnamespace std;#defineMAX_SIZE 32767typedefstructnodeint id;int adr;int size;structnode *next;Node;Node *head1, *head2, *back1, *back2, *assign;int request;int check(intadd, intsiz, charc)Node *p, *head;int check = 1;if (add<0 | siz<0)check = 0;/*地址和大小不能为负*/if (c = 'f' | c = 'F')head = head1;elsehead = head2;p = head->next;while (p != NULL) && check)if (add<p->adr) && (add + siz>p->adr) | (add >= p->adr) && (add<p->adr + p->size)check = 0;elsep = p->next;if(check = 0)printf("t输入释放区地址或大小有错误！n");return check;void init()Node *p;head1 = (Node*)malloc(sizeof(Node);head2 = (Node*)malloc(sizeof(Node);p = (Node*)malloc(sizeof(Node);head1->next = p;head2->next = p;p->size = MAX_SIZE;p->adr = 0;p->next = NULL;p->id = 0;Node* assignment1(intnum, intreq)Node *before, *after, *ass;ass = (Node*)malloc(sizeof(Node);before = head1;after = head1->next;ass->id = num;ass->size = req;while (after->size<req)before = before->next;after = after->next;if (after = NULL)ass->adr = -1;elseif (after->size = req)before->next = after->next;ass->adr = after->adr;elseafter->size -= req;ass->adr = after->adr;after->adr += req;return ass;void acceptment1(intaddress, intsiz, intrd)Node *before, *after;int insert = 0;back1 = (Node*)malloc(sizeof(Node);before = head1;after = head1->next;back1->adr = address;back1->size = siz;back1->id = rd;back1->next = NULL;while (!insert&&after)/将要被回收的分区插入空闲区按首址大小从小到大插入if (after = NULL) | (back1->adr <= after->adr) && (back1->adr >= before->adr)before->next = back1;back1->next = after;insert = 1;elsebefore = before->next;after = after->next;if (insert)if (back1->adr = before->adr + before->size)/和前边分区合并before->size += back1->size;before->next = back1->next;free(back1);elseif (after&&back1->adr + back1->size = after->adr)/和后边分区合并back1->size += after->size;back1->next = after->next;back1->id = after->id;free(after);after = back1;printf("t首先分配算法回收存成功！n");elseprintf("t首先分配算法回收存失败！n");Node* assignment2(intnum, intreq)Node *before, *after, *ass, *q;ass = (Node*)malloc(sizeof(Node);q = (Node*)malloc(sizeof(Node);before = head2;after = head2->next;ass->id = num;ass->size = req;while (after->size<req)before = before->next;after = after->next;if (after = NULL)ass->adr = -1;elseif (after->size = req)before->next = after->next;ass->adr = after->adr;elseq = after;before->next = after->next;ass->adr = q->adr;q->size -= req;q->adr += req;before = head2;after = head2->next;if (after = NULL)before->next = q;q->next = NULL;elsewhile (after->size)<(q->size)before = before->next;after = after->next;before->next = q;q->next = after;return (ass);void acceptment2(intaddress, intsiz, intrd)Node *before, *after;int insert = 0;back2 = (Node*)malloc(sizeof(Node);before = head2;after = head2->next;back2->adr = address;back2->size = siz;back2->id = rd;back2->next = NULL;if (head2->next = NULL)/空闲队列为空head2->next = back2;head2->size = back2->size;else/空闲队列不为空while (after)if (back2->adr = after->adr + after->size)/和前边空闲分区合并before->next = after->next;after->size += back2->size;back2 = after;elsebefore = before->next;after = after->next;before = head2;after = head2->next;while (after)if (after->adr = back2->adr + back2->size)/和后边空闲区合并before->next = after->next;back2->size += after->size;elsebefore = before->next;after = after->next;before = head2;after = head2->next;while (!insert)/将被回收的块插入到恰当的位置按分区大小从小到大if (after = NULL | (after->size>back2->size) && (before->size<back2->size)before->next = back2;back2->next = after;insert = 1;break;elsebefore = before->next;after = after->next;if (insert)printf("t最正确适应算法回收存成功！n");elseprintf("t最正确适应算法回收存失败！n");void print(charchoice)/输出空闲区队列信息Node *p;if (choice = 'f' | choice = 'F')p = head1->next;elsep = head2->next;if (p)printf("n空闲区队列的情况为：n");printf("t编号t首址t终址t大小n");while (p)printf("t%dt%dt%dt%dn", p->id, p->adr, p->adr + p->size - 1, p->size);p = p->next;void menu()/菜单及主要过程char chose;int ch, num=0, r, add, rd;while (1)system("cls");printf("-存储管理动态分区分配及回收算法-n");printf(" F 最先适应算法n");printf(" B 最正确适应算法n");printf(" E 退出程序n");printf("-n");printf("请选择算法:");cin >> chose;/scanf("%c", &chose);if (chose = 'e' | chose = 'E')exit(0);elsesystem("cls");while (1)if (chose = 'f' | chose = 'F')printf("最先适应算法:n");if (chose = 'b' | chose = 'B')printf("最正确适应算法:n");printf("-n");printf(" 1 分配存n");printf(" 2 回收存n");printf(" 3 查看存n");printf(" 4 返回n");printf("-nn");printf("请选择:");scanf("%d", &ch);fflush(stdin);switch (ch)case 1:printf("输入申请的分区大小："); scanf("%d", &r);if (chose = 'f' | chose = 'F')assign = assignment1(num, r);elseassign = assignment2(num, r);if (assign->adr = -1)printf("分配存失败！n");elseprintf("分配成功！分配的存的首址为:%dn", assign->adr);break;case 2:printf("输入释放的存的首址："); scanf("%d", &add);printf("输入释放的存的大小："); scanf("%d", &r);printf("输入释放的存的编号："); scanf("%d", &rd);if (check(add, r, chose)if (chose = 'f' | chose = 'F')acceptment1(add, r, rd);elseacceptment2(add, r, rd);break;case 3:print(chose); break;case 4:menu();break;void main()/主函数init();menu();四、实验结果五、实验总结通过这次实验我练习了存储管理动态分区分配及回收算法，对操作系统中动态可变分区存储管理有了更深刻的了解。刚开场编程时并没有什么思路，查阅相关书籍，浏览网上的论坛后，才对这次实验有了编程思路，在编程中总会遇到各种意想不到问题，这些问题一定要解决。在解决问题的同时，自己的编程能力也在提高。. .word.zl.