Linux教程

操作系统实现可变分区内存管理

本文主要是介绍操作系统实现可变分区内存管理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述

问题


模拟可变分区内存管理,模拟内存的分配和回收;分配算法实现3种(首次适应、最佳适应、最坏适应);回收时要考虑分区的合并;有碎片产生时,要考虑碎片整理。

思路


首次适应算法介绍点击这篇

开始有两个节点,一个是头结点,不存储任何信息,还有一个主节点,大小为你设置的最大值,后续所有节点都是在这个节点的基础上划分。

1.最先适应算法:

从这个结点开始,剩余空间大小<你需要的,不满足条件,分配失败。剩余空间大小>你需要的,我们只占用了空闲块的一部分,我们只占用块的前半部分,后面的部分还是空闲,空闲块要新生成,空闲块(temp)位于当前节点(p)和当前节点的下一节点(p->next)之间,如果可用空间大小等于你需要的,直接全占用。

2.最佳适应算法:

最佳适应算法理应是建立一张空闲分区表,将所有空闲分区从小到大排序,但这样实现太麻烦,我们直接找能存所需内存的最小空闲块。遍历所有空闲节点,如果剩余某块空间大小刚好等于你所需要的空间,直接分配,否则就找能装入你所需内存的且块最小的,我们用dValue存空闲块与我们所需内存的差值,差值最小的那个就是我们要求的块。差值越小说明空闲越小,越符合条件。

3.最坏适应算法:

最坏适应算法理应是建立一张空闲分区表,将所有空闲分区从大到小排序,但这样实现太麻烦,我们直接找能存所需内存的最大空闲块。遍历所有空闲节点,找能装入你所需内存的且块最大的,我们用dValue存空闲块与我们所需内存的差值,差值最大的那个就是我们要求的块。差值越大说明空闲越大,越符合条件。

回收注意事项:

回收内存时要注意被回收块的前后块是否空闲,空闲的话要合并,当后块空闲时合并后块,当前后块都空闲时,先合并的后面块,再合并前面块。

代码:

/*
 * @Author: robot-cmy
 * @Date: 2022-1-1 08:03:50
 * @Last Modified by: robot-cmy
 * @Last Modified time: 2022-1-1 08:03:50
 */
//参考了下方链接的代码
// https://blog.csdn.net/weixin_39924920/article/details/81054205?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E6%9C%80%E5%85%88%E9%80%82%E5%BA%94%E7%AE%97%E6%B3%95&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-81054205.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187

#include <iostream>
using namespace std;

#define MAX_MEMORY 666	//假设最大内存

void init();	//初始化函数,对初始节点初始化
void showInfo();	//显示分配信息
bool firstFit( int id, int memorySize );	//最先适应算法
bool bestFit( int id, int memorySize );		//最佳适应算法
bool badFit( int id, int memorySize );		//最坏适应算法
void allocate();	//内存分配
void recycle();	//内存回收

//链表数据块
struct Area {
    int id;	//作业id
    int size;	//作业大小
    int address;	//作业起始地址
    bool flag;	//=1表示被占用  =0表示未被占用
};

//采用双链表表示法
typedef struct Node {
    Area data;	//节点数段块
    Node *pre;	//前指针
    Node *next;	//后指针

} * LinkList;

//firstPointer时链头  lastPointer实际节点,所有数据分配都是基于这个节点
LinkList firstPointer, lastPointer;

//为两个头结点分配空间并初始化
void init() {
    firstPointer = new Node;
    lastPointer = new Node;
    firstPointer->pre = NULL;	//头结点前指针为空
    firstPointer->next = lastPointer;
    firstPointer->data.size = 0;

    lastPointer->pre = firstPointer;
    lastPointer->next = NULL;
    lastPointer->data.address = 0;	//我们实际操作都基于lastPointer节点,所以设这个起始地址为0
    lastPointer->data.size = MAX_MEMORY;	//同理,size也设为最大
    lastPointer->data.id = 0;
    lastPointer->data.flag = 0;
}

//打印内存分配情况
void showInfo() {
    Node *p = firstPointer->next;	//指针p指向实际的第一个节点
    cout << "\n---------------------内存分配表-----------------\n";

    cout << "------------------------------------------------\n";
    cout << "分区号\t" << "分区地址\t" << "分区大小\t" << "分区状态\t\n";
    cout << "------------------------------------------------\n";

    while( p ) {
        //cout << "分区号:";

        if( p->data.id ) {
            cout << p->data.id << "\t";	//输出id
        } else {
            cout << "空闲" << "\t";
        }

        cout << p->data.address << "\t\t";
        cout << p->data.size << "\t\t";

        //flag=1表示被占用,=0表示未占用
        if( p->data.flag ) {
            cout << "占用" << "\t\t";
        } else {
            cout << "空闲" << "\t\t";
        }

        p = p->next;
        cout << endl;
        //cout << "------------------------\n";
    }

    cout << "------------------------------------------------\n";
}

//最先适应算法  id为输入的作业编号  memorySize为输入的作业大小
bool firstFit( int id, int memorySize ) {
    Node *p = firstPointer->next;	//指针p指向实际的第一个节点

    while( p ) {
        //当前块未被占用且空间>=需要的空间大小
        if( !p->data.flag && p->data.size >= memorySize ) {
            //当前块刚好等于所需要的大小,直接分配
            if( p->data.size == memorySize ) {
                p->data.id = id;
                p->data.flag = 1;
                return true;
            } else {	//当前块大于需要的,只分当前块的前半部分,后半部分还是空闲
                LinkList temp = new Node;	//后面的空闲块

                temp->data.size = p->data.size - memorySize;	//空闲块大小=原来块大小-需要的
                temp->data.address = p->data.address + memorySize;	//地址=原来块的地址+需要的大小
                temp->data.flag = 0;	//空闲块表示未被占用
                temp->data.id = 0;
                temp->pre = p;	//相当于在p和p->next之间插入了一个新空闲块temp
                temp->next = p->next;

                //原节点此时被完全占用
                p->data.size = memorySize;
                p->data.id = id;
                p->data.flag = 1;
                p->next = temp;		//占用块指向空闲块
                return true;		//分配成功
            }
        }

        p = p->next;

    }

    return false;	//没有找到可用空闲块
}

//最佳适应算法 并没有按可用分区大小从小到大排序  而是遍历全部可用分区找最小可用的那块
bool bestFit( int id, int memorySize ) {
    Node *p = firstPointer->next;	//指针p指向实际的第一个节点
    Node * bestAddr = nullptr;	//最小且能容纳memorysize块地址  即最好块地址
    int dValue = MAX_MEMORY;	//可用块大小与实际所需空间之间的差值  最小的就是最好的,浪费最少的

    while( p ) {
        //当前块未被占用且空间>=需要的空间大小
        if( !p->data.flag && p->data.size >= memorySize ) {

            //当前块刚好等于所需要的大小,直接分配并返回true
            if( p->data.size == memorySize ) {
                p->data.id = id;
                p->data.flag = 1;
                return true;
            } else {	//没有刚好能存所需的块,找最先适应块地址
                if( p->data.size - memorySize < dValue ) {	//找dvalue最小的
                    bestAddr = p;
                    dValue = p->data.size - memorySize;	//更新最小差值
                }
            }
        }

        p = p->next;

    }

    //bestAddr不为空,说明找到了最小可用块
    if( bestAddr != nullptr ) {
        LinkList temp = new Node;	//可用块分配完后的后面的空闲块

        temp->data.size = bestAddr->data.size - memorySize;	//空闲块大小=原来块大小-需要的
        temp->data.address = bestAddr->data.address + memorySize;	//地址=原来块的地址+需要的大小
        temp->data.flag = 0;	//表示未被占用
        temp->data.id = 0;
        temp->pre = bestAddr;	//相当于在p和p->next之间插入了一个新空闲块
        temp->next = bestAddr->next;

        //原节点此时被完全占用
        bestAddr->data.size = memorySize;
        bestAddr->data.id = id;
        bestAddr->data.flag = 1;
        bestAddr->next = temp;	//连接最先适应块与temp(即后面的空闲块)
        return true;
    }

    return false;	//没有找到可用空闲块
}

//最坏适应算法  同理,并没有按空闲块大小排序,而是便利所有空闲块找空间最大的那块
bool badFit( int id, int memorySize ) {
    Node *p = firstPointer->next;	//指针p指向实际的第一个节点
    Node * badAddr = nullptr;	//存最大块地址
    int dValue = 0;	//可用块大小与实际所需空间之间的差值  差值最大的就是最大块

    while( p ) {
        //当前块未被占用且空间>=需要的空间大小
        if( !p->data.flag && p->data.size >= memorySize ) {
            //找最大空闲块
            if( p->data.size - memorySize >= dValue ) {
                badAddr = p;
                dValue = p->data.size - memorySize;
            }
        }

        p = p->next;

    }

    if( badAddr != nullptr ) {
        LinkList temp = new Node;	//后面的空闲块

        temp->data.size = badAddr->data.size - memorySize;	//空闲块大小=原来块大小-需要的
        temp->data.address = badAddr->data.address + memorySize;	//地址=原来块的地址+需要的大小
        temp->data.flag = 0;	//表示未被占用
        temp->data.id = 0;
        temp->pre = badAddr;	//相当于在p和p->next之间插入了一个新空闲块
        temp->next = badAddr->next;

        //原节点此时被完全占用
        badAddr->data.size = memorySize;
        badAddr->data.id = id;
        badAddr->data.flag = 1;
        badAddr->next = temp;	//连接最大块与temp(即后面的空闲块)
        return true;
    }

    return false;	//没有找到可用空闲块
}
//作业内存分配
void allocate( int allocateChoice ) {
    int id, memorySize;//id为要分配内存块编号  memorysize为要分配的大小
    bool sign ;	//判断分配是否成功
    cout << "输入作业编号和申请内存大小:";
    cin >> id >> memorySize;

    //最先适应
    if( allocateChoice == 1 ) {
        sign = firstFit( id, memorySize );
    } else if( allocateChoice == 2 ) {	//最佳适应
        sign = bestFit( id, memorySize );
    } else if( allocateChoice == 3 ) {	//最坏适应
        sign = badFit( id, memorySize );
    }

    if( sign ) {
        cout << "分配成功!!!\n";
    } else {
        cout << "内存不足,分配失败!!!\n";
    }
}

//作业内存回收,前面的块空闲要与前面块合并,后面的块空闲要与后面的块合并
void recycle() {
    int id;
    Node *p = firstPointer->next;	//指针p指向实际的第一个节点
    cout << "输入要释放的进程序号:";
    cin >> id;

    while( p ) {
        //找到了内存块
        if( p->data.id == id ) {
            p->data.id = 0;	//id=0表示内存卡未被使用
            p->data.flag = 0; // 1占用  0空闲

            //与前一个块合并时要考虑先合并后面的块,这样才能不出错
            if( !p->pre->data.flag ) {
                //合并后面的块
                if( !p->next->data.flag ) {
                    p->data.size += p->next->data.size;	//将后面块的内存加到前一块中

                    if( p->next->next == nullptr ) {	//p块后面的后面是空指针  就是p后面一共只有一块
                        p->next = p->next->next;	//将后面的块加到前面后就将p的next指针置空  因为后面没有块了
                    } else {	//p后面的后面还有块的情况  example 有1 2 3三个块 2是空块 已经将2的内存加到了1中
                        //1块和2块合成了一块  p->next->next是3块
                        p->next->next->pre = p;	//3块前指针应变成1
                        p->next = p->next->next;	//1的后指针应变成3
                    }
                }

                //合并前面块
                p->pre->data.size += p->data.size;
                p->pre->next = p->next;
                p->next->pre = p->pre;
            }




            //合并后面块
            if( !p->next->data.flag ) {
                p->data.size += p->next->data.size;	//将后面块的内存加到前一块中

                if( p->next->next == nullptr ) {	//p块后面的后面是空指针  就是p后面一共只有一块
                    p->next = p->next->next;	//将后面的块加到前面后就将p的next指针置空  因为后面没有块了
                } else {
                    //p后面的后面还有块的情况  example 有1 2 3三个块 2是空块 已经将2的内存加到了1中
                    //1块和2块合成了一块  p->next->next是3块
                    p->next->next->pre = p;	//3块前指针应变成1
                    p->next = p->next->next;	//1的后指针应变成3
                }
            }

            cout << "内存回收成功!!" << endl;
        }

        p = p->next;
    }
}

int main() {
    init();//初始化
    int choice;
    int allocateChoice;	//内存分配方式选择
    cout << "\t选择内存分配方式  1.首次适应  2.最佳适应  3.最坏适应" << endl;
    cout << "请选择:";
    cin >> allocateChoice;

    while( 1 ) {
        cout << "\n\n1.分配空间";
        cout << "\n2.回收空间";
        cout << "\n3.显示内存分配情况";
        cout << "\n0.退出\n";
        cout << "输入选项:";
        cin >> choice;

        switch( choice ) {
        case 1:

            allocate( allocateChoice );	//分配空间
            break;

        case 2:
            recycle();	//回收空间
            break;

        case 3:
            showInfo();	//输出分配信息
            break;

        case 0:
            return 0;
            break;

        }
    }

    return 0;
}

在这里插入图片描述

这篇关于操作系统实现可变分区内存管理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!