[系统运维]操作系统--动态分区存储管理

操作系统–动态分区存储管理

实验内容：

分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。
分区的初始化——可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小）
分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。
分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出来。（注意：不存在的作业号要给出错误提示！）
分区的显示：任何时刻，可以查看当前内存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来）。

代码：

#include <iostream>
#include <string>
#include <cstdio>
#include <map>
#include <cstdlib>

using namespace std;
const int MAX = 109;
const int INF = 1 << 30;

struct WORK
{
    int work_id; // 作业号
    int work_size; // 作业大小
    bool is_load; //作业是否被装入分区
    bool is_delete; // 作业是否回收
    WORK & operator=(const WORK &w)
    {
        work_id = w.work_id;
        work_size = w.work_size;
        is_load = w.is_load;
        is_delete = w.is_delete;
        return *this;
    }
};

struct SUBAREA
{
    int area_size; // 分区大小
    int area_id; // 分区编号
    bool exist_work; // 该分区是否有作业
    WORK current_work; // 当前存放的作业
    SUBAREA & operator=(const SUBAREA &s)  // 重载赋值运算符
    {
        area_size = s.area_size;
        area_id = s.area_id;
        exist_work = s.exist_work;
        current_work = s.current_work;
        return *this;
    }
};

SUBAREA subarea[MAX];
WORK work[MAX];
int subarea_size; // 初始分区的大小
int work_num; // 作业数量
int subarea_num; // 分区数量
map<int, bool> exist_work;
map<int, int> work_pos;

void init() // 初始化
{
    for(int i = 0; i < MAX; i++)
    {
        work[i].is_load = work[i].is_delete = false;
        subarea[i].exist_work = false;
        subarea[i].current_work.work_id = -1;
    }
}

int order_insert_subarea(WORK w, int s_num) // 最初将作业顺序装入分区,传入作业和分区数量
{
    int insert_num = -1; // 该作业装入的分区编号
    int sum = 0;
    int next_s = 0;
    for(int i = 0; i < s_num; i++)
    {
        //printf("sum = %d workSize = %d subsize = %d\n", sum, w.work_size, subarea[i].area_size);
        if(subarea[i].exist_work)
        {
            sum += subarea[i].current_work.work_size;
        }
        else if(w.work_size <= subarea[i].area_size && !subarea[i].exist_work) // 作业大小小于等于当前分区大小并且该分区空闲则可以装入
        {
            sum += w.work_size;
            subarea[i].current_work = w;
            subarea[i].area_size = w.work_size;
            subarea[i].exist_work = true;
            subarea[i].area_id = i;
            insert_num = i;
            next_s = i + 1;
            break;
        }
    }

    if(insert_num != -1) // 装入作业成功，进行分区
    {
        subarea_num ++; // 分区数量加一
        // 更新分区信息
        subarea[next_s].area_id = next_s;
        subarea[next_s].area_size = subarea_size - sum;
        subarea[next_s].exist_work = false;
        subarea[next_s].current_work.work_id = -1;
    }
//    printf("insert_num = %d\n", insert_num);
//    printf("suba_num = %d\n", subarea_num);
    return insert_num;
}

int judge_worknum(int nu) // 判断作业号是否存在
{
    int exist_pos = -1;
    for(int i = 0; i < subarea_num; i++)
    {
        if(subarea[i].current_work.work_id == nu)
        {
            exist_pos = i;
            return exist_pos;
        }
    }
    return exist_pos;
}

void recycle_work(int p) // 回收作业
{
    int s_num = 0;
    bool before = false;
    bool next = false;
    for(int i = 0; i < subarea_num - 1; i++)
    {
        if(i == p)
        {
            if( i != 0 && !subarea[i - 1].exist_work) // 前一个分区空闲
            {
                // 与待回收的作业合并
                before = true;
                s_num++;
            }
            if(!subarea[i + 1].exist_work) // 后一个分区空闲
            {
                // 与待回收的作业合并
                next = true;
                s_num++;
            }
            break;
        }
    }

    if(before || next) // 待回收的作业前后有空弦分区
    {
        if(before && !next) // 前有空闲后没有
        {
            //cout << p << "前空闲后不空闲" << endl;
            subarea[p - 1].exist_work = false; // 合并后该分区不存在作业
            subarea[p - 1].current_work.work_id = -1;
            subarea[p - 1].area_size += subarea[p].area_size;
            for(int i = p; i < subarea_num - 1; i++)
            {
                subarea[i] = subarea[i + 1];
                subarea[i].area_id = i;
            }

            subarea_num --;
        }
        else if(!before && next) // 后有空闲前没有
        {
            //cout  << p << "前不空闲后空闲" << endl;
            subarea[p].exist_work = false;
            subarea[p].current_work.work_id = -1;
            subarea[p].area_size += subarea[p + 1].area_size;
            for(int i = p + 1; i < subarea_num - 1; i++)
            {
                subarea[i] = subarea[i + 1];
                subarea[i].area_id = i;
            }
            subarea_num --;
        }
        else // 前后都有空闲
        {
            //cout  << p << "前后都空闲" << endl;
            subarea[p - 1].exist_work = false;
            subarea[p - 1].current_work.work_id = -1;
            subarea[p - 1].area_size += (subarea[p].area_size + subarea[p + 1].area_size);
            for(int i = p; i < subarea_num - 2; i++)
            {
                subarea[i] = subarea[i + 2];
                subarea[i].area_id = i;
            }
            subarea_num -= 2;
        }
    }
    else // 前后都没有空闲
    {
        subarea[p].exist_work = false;
        subarea[p].current_work.work_id = -1;
    }
}



int first_fit(WORK cur) // 首次适应算法
{
    for(int i = 0; i < subarea_num; i++)
    {
        // 当前分区不存在作业且分区大小够装入作业
        if(!subarea[i].exist_work && subarea[i].area_size >= cur.work_size)
        {
            return i;
        }
    }
    return -1;
}

int best_fit(WORK cur) // 最佳适应算法
{
    int minn = INF;
    int minn_id = -1;
    for(int i = 0; i < subarea_num; i++)
    {
        // 当前分区不存在作业且分区大小够装入作业
        // 更新最小能装下的分区编号
        if(!subarea[i].exist_work &&  subarea[i].area_size >= cur.work_size && subarea[i].area_size < minn)
        {
            minn = subarea[i].area_size;
            minn_id = i;
        }
    }
    return minn_id;
}

int worst_fit(WORK cur) // 最坏适应算法
{
    int maxx = -1;
    int max_id = -1;
    for(int i = 0; i < subarea_num; i++)
    {
        // 当前分区不存在作业且分区大小够装入作业
        // 更新最小能装下的分区编号
        if(!subarea[i].exist_work &&  subarea[i].area_size >= cur.work_size && subarea[i].area_size > maxx)
        {
            maxx = subarea[i].area_size;
            max_id = i;
        }
    }
    return max_id;
}

void update_subarea(int posi, WORK cur) // 更新分区
{
    int t = subarea[posi].area_size - cur.work_size;
    if(t == 0) // 刚好装满分区
    {
        subarea[posi].current_work = cur;
        subarea[posi].exist_work = true;
        return;
    }

    subarea[posi].area_size = cur.work_size;
    subarea[posi].area_id = posi;
    subarea[posi].current_work = cur;
    subarea[posi].exist_work = true;
    // 更新分区
    for(int j = subarea_num; j > posi + 1; j--)
    {
        subarea[j] = subarea[j - 1];
    }
    subarea[posi + 1].area_size = t;
    subarea[posi + 1].area_id = posi + 1;
    subarea[posi + 1].exist_work = false;
    subarea[posi + 1].current_work.work_id = -1;
    subarea_num++;
}



int main()
{
    while(true)
    {
        init();
        cout << "***********请选择你想实现的算法：***************" << endl;
        cout << "************* 1、首次适应算法 ******************" << endl;
        cout << "************* 2、最佳适应算法 ******************" << endl;
        cout << "************* 3、最坏适应算法 ******************" << endl;
        cout << "*****************  0、退出 *********************" << endl;

        int sel;
        cin >> sel;
        if(sel == 0)
            break;

        cout << "请输入初始分区的大小：" << endl;
        cin >> subarea_size;

        // 初始化
        subarea_num = 1;
        subarea[0].area_id = 0;
        subarea[0].area_size = subarea_size;

        cout << "请输入待处理的作业个数： ";
        cin >>  work_num;

        cout << "请输入各个作业信息（作业号 + 作业大小）：" << endl;
        for(int i = 0; i < work_num; i++)
        {
            cin >> work[i].work_id >> work[i].work_size;
            exist_work[work[i].work_id] = true;
            work_pos[work[i].work_id] = i;
        }


        // 初始状态下顺序装入
        int load_work_num = 0;
        bool exist_unwork = false;
        for(int i = 0; i < work_num; i++)
        {
            int t_num = order_insert_subarea(work[i], subarea_num);
            if(t_num != -1)
            {
                load_work_num++;
                work[i].is_load = true;
                cout << "作业 " << work[i].work_id << " 成功装入分区 " << t_num << endl;
            }
            else
            {
                cout << "作业 " << work[i].work_id << "暂无可用分区，等待回收...."  << endl;
                exist_unwork = true;
                //break;
            }
        }

        cout << endl;
        if(load_work_num != work_num)
        {
            cout << "存在 " << work_num - load_work_num << "个作业未装入，等待回收...." << endl;
        }

        //printf("load_num = %d worknum = %d\n", load_work_num, work_num);

        while(load_work_num != work_num)
        {
            cout << "存在未装入的作业，请选择: 1、回收  其他、装入" << endl;
            int se;
            cin >> se;
            if(se == 1)
            {
                int rework_num;
                cout << "请输入待回收的作业号：";
                cin >> rework_num;

                int pos = judge_worknum(rework_num); // 获取待回收作业在分区中的位置

                if(pos == -1) // 要回收的作业号不存在
                    cout << "您要回收的作业号不存在！" << endl;

                else // 进行回收
                {
                    recycle_work(pos);

                    cout << "回收后的分区状况：" << endl;
                    printf("%10s%10s%10s\n", "是否空闲", "分区编号", "分区大小");
                    for(int i = 0; i < subarea_num; i++)
                        printf("%10d%10d%10d\n", subarea[i].exist_work, subarea[i].area_id, subarea[i].area_size);
                }
            }

            else // 继续装入未装入的作业 (三种算法)
            {
                int load_id;
                cout << "请输入要装入的作业编号：";
                cin >> load_id;

                int temp = judge_worknum(load_id);

                if(temp != -1) // 要装入的作业号已经装入
                    cout << "您要装入的作业已装入,请勿重复装入！" << endl;
                else if(!exist_work[load_id])
                    cout << "您要装入的作业不存在！" << endl;
                else
                {
                    int suit_pos = work_pos[load_id];
                    int area_pos;
                    if(sel == 1) // 首次适应算法
                    {
                        area_pos = first_fit(work[suit_pos]);
                        if(area_pos == -1)
                        {
                            cout << "暂无可用分区！" << endl;
                        }
                        else
                        {
                            update_subarea(area_pos, work[suit_pos]);
                            load_work_num ++;
                            cout << "已成功装入分区，装入后的分区分配如下：" << endl;
                            printf("%20s%20s%20s%20s%20s\n", "是否空闲", "分区编号", "分区大小", "装入的作业号", "装入的作业大小");
                            for(int i = 0; i < subarea_num; i++)
                                printf("%20d%20d%20d%20d%20d\n", subarea[i].exist_work, subarea[i].area_id, subarea[i].area_size, subarea[i].current_work.work_id, subarea[i].current_work.work_size);
                        }
                    }
                    else if(sel == 2) // 最佳适应算法
                    {
                        area_pos = best_fit(work[suit_pos]);
                        if(area_pos == -1)
                        {
                            cout << "暂无可用分区！" << endl;
                        }
                        else
                        {
                            update_subarea(area_pos, work[suit_pos]);
                            load_work_num ++;
                            cout << "已成功装入分区，装入后的分区分配如下：" << endl;
                            printf("%20s%20s%20s%20s%20s\n", "是否空闲", "分区编号", "分区大小", "装入的作业号", "装入的作业大小");
                            for(int i = 0; i < subarea_num; i++)
                                printf("%20d%20d%20d%20d%20d\n", subarea[i].exist_work, subarea[i].area_id, subarea[i].area_size, subarea[i].current_work.work_id, subarea[i].current_work.work_size);
                        }
                    }
                    else // 最坏适应算法
                    {
                        area_pos = worst_fit(work[suit_pos]);
                        load_work_num ++;
                        if(area_pos == -1)
                        {
                            cout << "暂无可用分区！" << endl;
                        }
                        else
                        {
                            update_subarea(area_pos, work[suit_pos]);
                           cout << "已成功装入分区，装入后的分区分配如下：" << endl;
                            printf("%20s%20s%20s%20s%20s\n", "是否空闲", "分区编号", "分区大小", "装入的作业号", "装入的作业大小");
                            for(int i = 0; i < subarea_num; i++)
                                printf("%20d%20d%20d%20d%20d\n", subarea[i].exist_work, subarea[i].area_id, subarea[i].area_size, subarea[i].current_work.work_id, subarea[i].current_work.work_size);
                        }
                    }
                }
                if(load_work_num == work_num)
                    cout << "所有作业均已全部装入！" << endl;
            }
        }
        system("pause");
        system("clear");
    }
    return 0;
}

如有错误，欢迎指正~~