存储管理动态分区分配及回收算法

2022/6/12 5:20:24

编程Tag： 算法 after before next size printf 分区 adr 存储管理

本文主要是介绍存储管理动态分区分配及回收算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、目的和要求

分区管理是应用较广泛的一种存储管理技术。本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同分配算法的特点。

 

二、实验内容

    1、编写：First Fit Algorithm

    2、编写：Best Fit Algorithm

3、编写：空闲区回收算法

 

三、提示和说明

   （一）主程序

    1、定义分区描述器node，包括 3个元素：

    （1）adr——分区首地址

    （2）size——分区大小

    （3）next——指向下一个分区的指针

    2、定义 3个指向node结构的指针变量：

    （1）head1——空闲区队列首指针

    （2）back1——指向释放区node结构的指针

    （3）assign——指向申请的内存分区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；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。

   （四）输出   

    要求每执行一次，输出一次空闲区队列情况，内容包括：

                     编号  首址  终址  大小

    注：输出空闲区队列的排序，应符合所用分配算法的要求。

 

 

实验报告

一、实验目的

分区管理是应用较广泛的一种存储管理技术。本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同分配算法的特点。。

二、实验内容和要求

  1. 编写：First Fit Algorithm

编写：Best Fit Algorithm

编写：空闲区回收算法编写两种调度算法程序：

2.  程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。

3. 将程序源代码和运行截图写入实验报告并提交。

三、实验步骤

  1. 实验准备

(1) 查阅相关资料；

编写两种地址分配算法的程序参考了比较多的内容，首先参考了教材，将两种地址分配算法又重新复习了一下，增加了一下理论的掌握情况，然后又根据实验报告上的要求进行了主体的搭建，具体细节的实现主要参考了一些网上的文章。主要包括下面三篇文章。

https://www.doc88.com/p-1146521830717.html?s=rel&id=1

https://www.doc88.com/p-9197402934769.html?s=rel&id=4

 

https://blog.csdn.net/c1194758555/article/details/53047570?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165142364816782248521163%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=165142364816782248521163&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-13-53047570.142^v9^pc_search_result_cache,157^v4^control&utm_term=%E6%97%B6%E9%97%B4%E7%89%87%E8%BD%AE%E8%BD%AC%E7%AE%97%E6%B3%95%E5%92%8C%E4%BC%98%E5%85%88%E7%BA%A7%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

 

(2) 初步编写程序；

进程调度算法程序主体框架：

void menu() {

//菜单及主要过程

char chose;

int ch,num=0, r, add, rd;

while (1) {

system("cls");//清屏 

printf("选择最先适应算法输入F，选择最佳适应算法请输入B，退出程序请输入E\n\n");

printf("请选择你的输入:");

scanf("%c", &chose);

if (chose == 'e' || chose == 'E')

exit(0);

else {

system("cls");

while (1) {

if (chose == 'f' || chose == 'F')

printf("最先适应算法(First-Fit)模拟：\n");

if (chose == 'b' || chose == 'B')

printf("最佳适应算法(Best-Fit)模拟：\n");

printf("1.分配内存，2.回收内存，3.查看内存，4.返回\n\n");

printf("请输入你的选择：");

scanf("%d", &ch);

fflush(stdin);//清除输入缓冲区中的数据 

switch (ch) {

case 1:

printf("输入申请的分区大小:");

scanf("%d", &r);

if (chose == 'f' || chose == 'F')

assign = assignment1(num, r);

else {

assign = assignment2(num, r);

}

 

if (assign->adr == -1) {

printf("分配内存失败！\n");

}

else {

printf("分配内存成功！分配的首地址为:%d\n", 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);

if (chose == 'b' || chose == 'B')

acceptment2(add, r, rd);

}

break;

case 3:

print(chose);

break;

case 4:

menu();

break;

}

}

}

}

}

 

(3) 准备测试数据；

进程调度模拟算法，数据输入格式

首先选择算法类型，然后进行分配内存、回收内存、查看内存、返回，等一系列的选择，如下图所示：

 

  1. 上机调试

 

 

 

 

 

 

 

源代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#pragma warning(disable:4996)
#define MAX_SIZE 32767 
typedef struct node {
    int id;
    int adr;
    int size;
    struct node* next;
}Node;
Node* head1, * head2, * back1, * back2, * assign;
int request;
//add释放内存的首地址 siz释放内存大小 c算法类型 
int check(int add, int siz, char c) {
    Node* p, * head;
    int check = 1;
    if (add < 0 || siz < 0)
        check = 0;//地址和大小不能为负
    if (c == 'f' || c == 'F')
        head = head1;
    else
        head = 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;
        else
            p = 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(int num, int req) {
    printf("%d %d", num, req);
    Node* before, * after, * ass;
    ass = (Node*)malloc(sizeof(Node));
    before = head1;
    after = head1->next;
    ass->id = num;
    ass->size = req;
    //将after指针指向大小刚好适应需求的空闲地址
    while (after->size < req) {
        before = before->next;
        after = after->next;
    }
    if (after == NULL) {
        ass->adr = -1;
    }
    else {
        //地址与需求地址相等 
        if (after->size == req) {
            before->next = after->next;
            ass->adr = after->adr;
        }
        else {
            //地址比需求地址大 
            after->size -= req;
            ass->adr = after->adr;
            after->adr += req;
        }
    }
    return ass;
}
//首先分配算法回收内存 
void acceptment1(int address, int siz, int rd) {
    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;
    printf("%d,%d", head1->adr, head1->size);
    while (!insert && after) {
        //将要被收回的分区插入到 空闲区(按首地址从小到大插入)
        //back1地址的大小位于after和before之间 
        if ((after == NULL) || ((back1->adr <= after->adr) && (back1->adr >= before->adr))) {
            before->next = back1;
            back1->next = after;
            insert = 1;
        }
        else {
            before = before->next;
            after = after->next;
        }
    }
    if (insert) {
        //back1的首地址刚好等于before的末地址 
        if (after && back1->adr + back1->size == after->adr) {
                    //back1的 
                    //和后边分区合并
                    back1->size += after->size;
                    back1->next = after->next;
                    back1->id = after->id;
                    free(after);
        }
        if (back1->adr == before->adr + before->size) {
            //和前面分区合并
            before->size += back1->size;
            before->next = back1->next;
            free(back1);
        }
        
        printf("\t 首先分配算法回收内存成功\n");
    }
    else {
        printf("\t首先分配算法回收内存失败\n");
    }
}
// 最佳适应算法分配内存 
Node* assignment2(int num, int req) {
    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;
        //printf("while");
    }
    if (after == NULL) {
        ass->adr = -1;
        printf("null");
    }
    else {
        if (after->size == req) {
            printf("==");
            before->next = after->next;
            ass->adr = after->adr;
        }
        else {
            //after->size > req
            //q是前去req之后的空白分区
            q = after;
            before->next = after->next;
            ass->adr = q->adr;
            q->size -= req;
            q->adr += req;
            //将q插入到空白链表的对应位置
            before = head2;
            after = head2->next;
            if (after == NULL) {
                before->next = q;
                q->next = NULL;
            }
            else {
                while (after!=NULL&&(after->size) < (q->size)) {
                    before = before->next;
                    after = after->next;
                    //ass->adr=after->adr;
                }
                before->next = q;
                q->next = after;
            }
        }
    }
    return (ass);
}
//最佳适应算法回收内存
void acceptment2(int address, int siz, int rd) {
    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;
        //printf("null");
    }
    else {
        //空闲队列不为空
        while (after) {
            if (back2->adr == after->adr + after->size) {
                //和前面空闲分区合并
                before->next = after->next;
                after->size += back2->size;
                back2 = after;
            }
            else {
                before = before->next;
                after = after->next;
            }
        }
        before = head2;
        after = head2->next;
        //printf("%d %d\n",before->adr,after->adr);
        while (after) {
            if (after->adr == back2->adr + back2->size) {
                //和后边空闲区合并
                before->next = after->next;
                back2->size += after->size;
            }
            else {
                before = before->next;
                after = after->next;
            }
        }
        before = head2;
        after = head2->next;
        //printf("%d %d\n",before->adr,after->adr);
        //printf("%d,%d,%d\n",after->size,before->size,back2->size);
        while (!insert) {
            //printf("%d,%d,%d\n",after->size,before->size,back2->size);
            //将被回收的快插入到恰当的位置(按分区大小从小到大)
            if (after == NULL || ((after->size > back2->size))) {
                before->next = back2;
                back2->next = after;
                insert = 1;
                break;
            }
            else {
                before = before->next;
                after = after->next;
                //    printf("%d\n",before->adr);
            }
        }
    }
    if (insert)
        printf("\t最佳适应算法回收内存成功\n");
    else
        printf("\t最佳适应算法回收内存失败\n");
}

void print(char choice) {
    //输出空闲区队列信息
    Node* p;
    if (choice == 'f' || choice == 'F')
        p = head1->next;
    else
        p = head2->next;
    if (p) {
        printf("\n空闲队列的情况为:\n");
        printf("\t编号\t首址\t终址\t大小\n");
        while (p) {
            printf("\t%d\t%d\t%d\t%d\n", 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("选择最先适应算法输入F，选择最佳适应算法请输入B，退出程序请输入E\n\n");
        printf("请选择你的输入:");
        scanf("%c", &chose);
        if (chose == 'e' || chose == 'E')
            exit(0);
        else {
            system("cls");
            while (1) {
                if (chose == 'f' || chose == 'F')
                    printf("最先适应算法(First-Fit)模拟：\n");
                if (chose == 'b' || chose == 'B')
                    printf("最佳适应算法(Best-Fit)模拟：\n");
                printf("1.分配内存，2.回收内存，3.查看内存，4.返回\n\n");
                printf("请输入你的选择：");
                scanf("%d", &ch);
                fflush(stdin);//清除输入缓冲区中的数据 
                switch (ch) {
                case 1:
                    printf("输入申请的分区大小:");
                    scanf("%d", &r);
                    if (chose == 'f' || chose == 'F')
                        assign = assignment1(num, r);
                    else {
                        assign = assignment2(num, r);
                    }

                    if (assign->adr == -1) {
                        printf("分配内存失败！\n");
                    }
                    else {
                        printf("分配内存成功！分配的首地址为:%d\n", 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);
                        if (chose == 'b' || chose == 'B')
                            acceptment2(add, r, rd);
                    }
                    break;
                case 3:
                    print(chose);
                    break;
                case 4:
                    menu();
                    break;
                }
            }
        }
    }
}

int main() {
    //主函数
    init();
    menu();
    return 0;
//}

 



这篇关于存储管理动态分区分配及回收算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程