操作系统实验 存储管理-可变分区存储管理的空间分配与去配

实验四 存储管理-可变分区存储管理的空间分配与去配

一、实验目的
要求掌握存储管理中的典型算法，理解各种存储管理的工作原理，特别是可变分区存储管理中最先适应分配算法、最优适应分配算法、最坏适应分配算法以及空间回收算法的工作原理，试采用C语言编程，模拟实现算法功能。

二、实验要求
设计一个可变式分区分配的存储管理方案，并模拟实现分区的分配和回收过程。
假定主存空间为静态分配。为实现分区的分配和回收，需要已分配分区表和系统空闲分区表描述当前系统状态。已分配分区表包括分区编号、已分配分区长度、分区的起始地址等信息。系统空闲分区表包括分区编号、分区长度、分区的起始地址等信息。用户根据需要提出对主存空间大小的申请，系统按照一定的分配策略，找出能满足请求的空闲区进行分配。如果满足要求，输出分配完成后已分配分区表和空闲区表的信息，否则输出“无空闲区分配”。
用户根据需要释放主存空间，实现空间的回收，并输出空间回收后已分配分区表和空闲区表的信息。

反正代码是写吐了
如果要加很多功能的话还可以加
开源图一乐

/* 
    时间：4月27日~4月28日
   	仅供参考，还请不要复制粘贴
 */

#include <iostream>
#include <string>
#include <queue>
using namespace std;
// 分配表最多容纳100个
#define MAX 100

// 创建进程信息
struct process
{
    int seq;
    // 分区表的单行序号
    int length;
    // 分区表的单行长度
    int begin_address;
    // 分区表的起始地址
    int number;
    // 最后哪个进程被分配的进程编号
};

// 创建可变分区表的结构体，表长和进程信息
struct system_list
{

    process informationArray[MAX];
    int size;
};

// 菜单展示
void display()
{
    cout << "__________________________________" << endl;
    cout << "__________1.设计空闲区信息__________" << endl;
    cout << "__________2.显示空闲区信息______________" << endl;
    cout << "__________3.添加作业队列信息______________" << endl;
    cout << "__________4.显示作业队列信息______________" << endl;
    cout << "__________5.最先分配适应算法________________" << endl;
    cout << "__________6.最优分配适应算法______________" << endl;
    cout << "__________7.最坏分配适应算法_______________" << endl;
    cout << "__________8.主存回收_______________" << endl;
    cout << "__________0.退出系统______________" << endl;
    cout << "__________________________________" << endl;
}

void addInfo(system_list *l)
{
    cout << "下面开始建立空闲分区表" << endl;

    int seq;
    cout << "输入空闲分区的分区编号" << endl;
    cin >> seq;
    l->informationArray[l->size].seq = seq;

    int length;
    cout << "输入空闲分区的可分配区域长度" << endl;
    cin >> length;
    l->informationArray[l->size].length = length;

    int begin_address;
    cout << "输入空闲分区的起始地址（十进制）" << endl;
    cin >> begin_address;
    l->informationArray[l->size].begin_address = begin_address;

    l->informationArray[l->size].number = -1;

    l->size++;
}
void displayInformation(system_list *l)
{
    if (l->size == 0)
    {
        cout << "当前空闲区不空闲" << endl;
        return;
    }
    else
    {
        for (int i = 0; i < l->size; i++)
        {
            cout << "----------------------------------------------------------------------------------" << endl;
            cout << "空闲区序号： " << l->informationArray[i].seq << "\t";
            cout << "空闲区长度： " << l->informationArray[i].length << "\t";
            cout << "空闲区起始地址： " << l->informationArray[i].begin_address << "\t";
            cout << "分配的进程编号： " << l->informationArray[i].number << endl;
            cout << "----------------------------------------------------------------------------------" << endl;
        }
    }
}

// 创建作业队列，运用queue标准库
void pushlist(queue<int> *list)
{
    cout << "请输入你要设计的作业队列需要的内存:" << endl;
    int num;
    cin >> num;
    list->push(num);
}
void displaylist(queue<int> *list)
{
    cout << "----------------队列内容：------------------" << endl;
    int n = 0;
    int pop;
    while (n < list->size())
    {
        cout << "序号为：" << n << "  需求内存为: " << list->front() << endl;
        list->push(list->front());
        list->pop();
        // 没有遍历器，就在出队的同时入队
        n++;
    }
}

// 冒泡排序：让地址从低到高排序
void bubble_address(system_list *l)
{
    process temp;
    for (int i = 0; i < l->size - 1; i++)
    {
        for (int j = 0; j < l->size - i - 1; j++)
        {
            if (l->informationArray[j].begin_address > l->informationArray[j + 1].begin_address)
            {
                temp = l->informationArray[j];
                l->informationArray[j] = l->informationArray[j + 1];
                l->informationArray[j + 1] = temp;
            }
        }
    }
}
// 最先适应分配算法
void frist_fit_allocated(system_list *l, queue<int> *list)
{
    // 先将地址进行冒泡排序
    bubble_address(l);
    cout << "++++++++++++++++++++++++++++++分配前的空闲区信息++++++++++++++++++++++++" << endl;
    displayInformation(l);
    int n = 0;

    while (n < list->size())
    {
        for (int i = 0; i < l->size; i++)
        {
            if (list->front() <= l->informationArray[i].length && l->informationArray[i].number == -1)
            {
                l->informationArray[i].length = l->informationArray[i].length - list->front();
                // 将所剩余的空间显示出来。
                l->informationArray[i].number = n;
                // 并且将进程编号放入
                list->pop();
                // 删除队首
                break;
            }
        }
        n++;
    }
    cout << "++++++++++++++++++++++分配后的进程信息++++++++++++++++++===+++" << endl;
    displayInformation(l);
    if ((list->size()) != 0)
    {
        cout << "仍然有作业没有分配到空间，请开始主存回收功能重试" << endl;
        displaylist(list);
    }
}

// 选择排序，将空闲区容量从低到高排序
void select_length(system_list *l)
{
    for (int i = 0; i < l->size; i++)
    {
        for (int j = i + 1; j < l->size; j++)
        {
            if (l->informationArray[i].length > l->informationArray[j].length)
            {
                swap(l->informationArray[i], l->informationArray[j]);
            }
        }
    }
}
// 最优适应分配算法
void frist_best_allocated(system_list *l, queue<int> *list)
{
    // address sort the select
    select_length(l);
    cout << "++++++++++++++++++++++++++++++分配前的空闲区信息++++++++++++++++++++++++" << endl;
    displayInformation(l);
    int n = 0;

    while (n < list->size())
    {
        for (int i = 0; i < l->size; i++)
        {
            if (list->front() <= l->informationArray[i].length && l->informationArray[i].number == -1)
            {
                l->informationArray[i].length = l->informationArray[i].length - list->front();
                // 将所剩余的空间显示出来。
                l->informationArray[i].number = n;
                // 并且将进程编号放入
                list->pop();
                // 删除队首
                break;
            }
        }
        n++;
    }
    cout << "++++++++++++++++++++++分配后的进程信息++++++++++++++++++===+++" << endl;
    displayInformation(l);
    if ((list->size()) != 0)
    {
        cout << "仍然有作业没有分配到空间，请开始主存回收功能重试" << endl;
        displaylist(list);
    }
}

// 冒泡排序，让空闲区容量从高到低
void fast_length(system_list *l)
{
    for (int i = 0; i < l->size - 1; i++)
    {
        for (int j = 0; j < l->size - 1 - i; j++)
        {
            if (l->informationArray[j].length < l->informationArray[j + 1].length)
            {
                swap(l->informationArray[j], l->informationArray[j + 1]);
            }
        }
    }
}
void frist_terrible_allocated(system_list *l, queue<int> *list)
{
    fast_length(l);
    cout << "++++++++++++++++++++++++++++++分配前的空闲区信息++++++++++++++++++++++++" << endl;
    displayInformation(l);
    int n = 0;

    while (n < list->size())
    {
        for (int i = 0; i < l->size; i++)
        {
            if (list->front() <= l->informationArray[i].length && l->informationArray[i].number == -1)
            {
                l->informationArray[i].length = l->informationArray[i].length - list->front();
                // 将所剩余的空间显示出来。
                l->informationArray[i].number = n;
                // 并且将进程编号放入
                list->pop();
                // 删除队首
                break;
            }
        }
        n++;
    }
    cout << "++++++++++++++++++++++分配后的进程信息++++++++++++++++++===+++" << endl;
    displayInformation(l);
    if ((list->size()) != 0)
    {
        cout << "仍然有作业没有分配到空间，请开始主存回收功能重试" << endl;
        displaylist(list);
    }
}

// 重点来了：主存回收-----------------------------------------------------------
void retrieve(system_list *l)
{
    bubble_address(l);
    cout << "地址排序结果" << endl;
    displayInformation(l);
    l->informationArray[l->size].begin_address = -100;
    l->informationArray[l->size + 1].begin_address = -100;
    l->informationArray[l->size + 2].begin_address = -100;
    int i = 1;
    while (l->informationArray[i].begin_address != -100)
    {
        // 上面有空间，下面有空间
        if (l->informationArray[i].begin_address - 1 == l->informationArray[i - 1].begin_address && l->informationArray[i].begin_address + 1 == l->informationArray[i + 1].begin_address && l->informationArray[i].length > 0 && l->informationArray[i + 1].length > 0 && l->informationArray[i - 1].length > 0)
        {
            l->informationArray[i - 1].length += l->informationArray[i].length + l->informationArray[i + 1].length;
            while (2)
            {
                for (int j = i; j < l->size; j++)
                {
                    l->informationArray[j] = l->informationArray[j + 1];
                }
                l->size--;
            }
        }

        // 上面有空间
        else if (l->informationArray[i].begin_address - 1 == l->informationArray[i - 1].begin_address && l->informationArray[i].length > 0 && l->informationArray[i - 1].length > 0)
        {
            l->informationArray[i - 1].length += l->informationArray[i].length;
            for (int j = i; j < l->size; j++)
            {
                l->informationArray[j] = l->informationArray[j+1];
            }
            l->size--;
        }
        // 下面有空间
        else if (l->informationArray[i].begin_address + 1 == l->informationArray[i + 1].begin_address && l->informationArray[i].length > 0 && l->informationArray[i + 1].length > 0)
        {
            l->informationArray[i - 1].length += l->informationArray[i].length;
            for (int j = i + 1; j < l->size; j++)
            {
                l->informationArray[j] = l->informationArray[j + 1];
            }
            l->size--;
        }
        i++;
    }
    cout<<"+++++++++++++++++++++++++回收结果++++++++++++++++++++++++++++++++++"<<endl;
    displayInformation(l);
    cout << "没有可以回收的空间啦" << endl;
}

int main()
{
    int select = 0;
    system_list l;
    queue<int> list;
    l.size = 0;
    cout << "请输入你的选择" << endl;
    while (true)
    {

        display();
        cin >> select;
        switch (select)
        {
            // 1~2输入空闲区信息
        case 1:
        {
            cout << "请按照提示输入信息" << endl;
            int num;
            cout << "请输入你要设定空闲区的个数" << endl;
            cin >> num;
            while (num)
            {
                addInfo(&l);
                num--;
            }
            cout << "添加完毕，请开始你的表演吧！" << endl;
        }
        break;

        case 2:
        {
            displayInformation(&l);
        }
        break;

        // 3~4输入作业队列信息
        case 3:
        {
            cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~开始作业队列的输入~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << endl;
            cout << "请按照提示输入信息" << endl;
            int num1;
            cout << "请输入你要设定进入空闲区进程的的个数" << endl;
            cin >> num1;
            while (num1)
            {
                pushlist(&list);
                num1--;
            }
            cout << "添加完毕" << endl;
        }
        break;
        case 4:
        {
            displaylist(&list);
        }
        break;
        // 最先适应分配算法。
        case 5:
            frist_fit_allocated(&l, &list);
            break;
        // 最优适应分配算法
        case 6:
            frist_best_allocated(&l, &list);
            break;
        // 最坏适应分配算法
        case 7:
            frist_terrible_allocated(&l, &list);
            break;
        case 8:
            retrieve(&l);
            break;

        case 0:
            cout << "不欢迎下次的使用" << endl;
            return 0;
        default:
            break;
        }
    }
}