操作系统实验：动态分区分配方式的模拟

87 阅读 0 评论 58 点赞

我是靠谱客的博主满意雪碧，最近开发中收集的这篇文章主要介绍操作系统实验：动态分区分配方式的模拟，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

2、实验内容

（1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。

（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：

•作业1申请130KB。

•作业2申请60KB。

•作业3申请100KB。

•作业2释放60KB。

•作业4申请200KB。

•作业3释放100KB。

•作业1释放130KB。

•作业5申请140KB。

•作业6申请60KB。

•作业7申请50KB。

•作业6释放60KB。

请采用最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
设计思路可以参考：blog.csdn.net/Jackson_yee___/article/details/107641690
只用带头单向链表实现，回收算法处也是很强了：https://blog.csdn.net/qq_43605654/article/details/90767364
这篇文章的回收算法有bug，可以看看为什么：
https://blog.csdn.net/aa1927006965/article/details/85176418

采用带头双向链表储存，可以减少回收算法的复杂度；
同时认为可以在本实验的基础上创建一个独立链表—记录空闲分区并且与完整的分区表对应，之后可以对空闲分区链进行排序，每次在排序后的链表中查找可分配分区可以获得更高的效率。最后同学说数组实现十分精简，大家可以尝试一下。

实现代码，释放函数进行了扩充，弥补了释放内存如果为第一分区或者最后一分区会出现的BUG：

#include <iostream>
#include <string>

using namespace std;

struct MEMORY {
    int address;
    int size;
    string id = "NONE";
    string state = "FREE";
    MEMORY *next;
    MEMORY *front;
};
MEMORY *head, *last;

void best_fit(string name, int size) {    //最佳适应
    int surplus;
    MEMORY *flag;    //配分出去的分区
    flag = new MEMORY;
    flag->id = name;
    flag->size = size;
    flag->state = "BUSY";
    MEMORY *p = head->next;
    MEMORY *q = NULL;
    while (p != NULL) {
        if (p->state == "FREE" && p->size >= size) {
            q = p;
            surplus = p->size - size;
            break;
        }
        p = p->next;
    }
    while (p != NULL) {
        if (p->state == "FREE" && p->size >= size) {
            if (p->size - size < surplus) {
                surplus = p->size - size;
                q = p;
                break;
            }
        }
        p = p->next;
    }
    if (q == NULL) {
        cout << "剩余空闲分区无法满足需求,无法分配!" << endl;
        return;
    } else if (q->size > size) {
        flag->next = q;
        flag->front = q->front;
        flag->address = q->address;
        q->front->next = flag;
        q->front = flag;
        q->size = surplus;
        q->address += size;
    } else {
        q->id = name;
        q->size = size;
        q->state = "BUSY";
    }
}

void alloc() {
    string s;
    int size;
    cout << "进程名:";
    cin >> s;
    cout << "操作空间大小:";
    cin >> size;
    best_fit(s, size);
}

void cyc() {
    int f = 0;
    string s;
    cout << "进程名:";
    cin >> s;

    MEMORY *p = head->next;
    while (p != NULL) {
        if (p->id == s)//找到要回收的id区域
        {
            p->state = "FREE";
            p->id = "NONE";
            //判断P与前后区域关系
            if (p != last) {
                if (p->front->state == "FREE" && p->next->state != "FREE") {
                    p->front->size += p->size;
                    p->front->next = p->next;
                    p->next->front = p->front;
                } else if (p->front->state != "FREE" && p->next->state == "FREE") {
                    p->size += p->next->size;
                    if (p->next->next) {
                        p->next->next->front = p;
                        p->next = p->next->next;
                    } else p->next = p->next->next;
                } else if (p->front->state == "FREE" && p->next->state == "FREE") {
                    p->front->size += p->size + p->next->size;
                    if (p->next->next) {
                        p->next->next->front = p->front;
                        p->front->next = p->next->next;
                    } else p->front->next = p->next->next;
                } else if (p->front->state != "FREE" && p->next->state != "FREE") {
                }
            } else {
                if (p->front->state == "FREE") {
                    p->front->size += p->size;
                    p->front->next = NULL;
                } else if (p->front->state != "FREE") {
                    
                }
            }
            f = 1;
            break;
        }
        p = p->next;
    }
    if (f == 0) {
        cout << "无该作业,释放失败!" << endl;
    } else {
        cout << "释放成功!" << endl;
    }
}

void show() {
    MEMORY *p = head->next;
    cout << "***************分区状态***************" << endl;
    while (p != NULL) {
        cout << " 分区始址:" << p->address << " 分区大小:" << p->size << " 分区状态:" << p->state;
        if (p->state == "FREE") {
            cout << endl;
        } else {
            cout << " 储存作业:" << p->id << endl;
        }
        p = p->next;
    }
    cout << "*********************************" << endl;
    delete p;
    p = NULL;
}

int main() {
    head = new MEMORY;
    last = new MEMORY;
    head->front = NULL;
    head->next = last;
    head->state = "ERROR";
    last->front = head;
    last->next = NULL;
    last->address = 0;
    last->state = "FREE";
    last->id = "NONE";
    last->size = 640;
    while (1) {
        A:
        cout << "*******************选择操作*****************" << endl;
        cout << " 1.申请内存   2.释放内存   3.内存情况   4.exit" << endl;
        char ch;
        cin >> ch;
        if (ch == '1') {
            alloc();
            show();
        } else if (ch == '2') {
            cyc();
            show();
        } else if (ch == '3') {
            show();
        } else if (ch == '4') {
            break;
        } else {
            cout << "错误！" << endl;
            goto A;        //goto写点作业还是挺好用的
        }
    }
    cout << "**************模拟结束****************" << endl;
}