[操作系统]动态分区式存贮区管理

C++ 操作系统
操作系统
发布日期:   2021-04-25
文章字数:   4.3k
阅读时长:   18 分
阅读次数:  

题目描述

设计一个动态分区式存贮区管理程序，要求支持不同的放置策略。包括首次、最佳、最坏。

说明：

(1) 分区描述器rd如下:

flag size next

要求空闲区队列按链表组织。

主存大小假设为maxsize（单位为节=rd的大小）。

（2）主程序结构如下：

输入放置策略

申请一块内存作为主存

循环处理用户的请求（包括申请、释放）

需设计两个函数处理用户请求：

申请函数 Addr=Request(size)

释放函数 Release(addr）

（3）数据实例：maxsize=512

J1申请162，J2申请64，J3申请120，J4申请86，J1完成，J3完成，J5申请72，J6申请100，J2完成，J7申请36，J8申请60，J4完成，J9申请110，J10申请42。

备注：

（a）所有大小其单位为节（1节=rd的大小）

（b）作业申请n节,实际分配的分区大小应为n+1节。 其中一节作为分区描述器，其他n节提供给作业。

（c）已分配区放在高地址处。

（d）合并时应考虑四种情况： 假设回收区为r,上邻为f1（f1需搜索自由主存队列）,下邻为f2（f2可直接计算）

A)f1空闲，f2已分配；

B)f1已分配，f2空闲；

C)f1空闲，f2空闲；

D)f1已分配，f2已分配；

程序功能及设计思路

程序功能：

用户可以选择请求资源的方式，包括首次适应算法、最佳算法和最坏算法三种方式。程序将根据请求的方式在主存中找到合适的位置分配空间并放置分区描述器rd。用户要释放内存时，根据分区所处的位置选择释放的方式，将这个分区占用的内存释放出来。

设计思路：

先获取用户的放置策略，再循环处理用户的请求(包括申请、释放)。放置策略一共有三种。

首次适应算法:由于已分配区放在高地址区，每次从高地址区向低地址区搜索，找到第一个空地址区，从高地址向低地址数n+1节地址，其中后面n节地址分配给作业，最前面的一节(低地址区)放置这块空间的分区描述器即可。

最佳适应算法:搜素整个内存中的所有空闲区域，找出能满足作业要求且大小最小的空闲分区，从高地址向低地址数n+1节地址，其中后面n节地址分配给作业，最前面的一节(低地址区)放置这块空间的分区描述器即可。

最差适应算法:搜素整个内存中的所有空闲区域，找出能满足作业要求的、且大小最大的空闲分区，从高地址向低地址数n+1节地址，其中后面n节地址分配给作业，最前面的一节(低地址区)放置这块空间的分区描述器即可。

​

程序功能及设计思路

数据结构：

//分区描述器
struct RDNode
{
    bool flag;
    string name;
    int size;
    int nextAdd;
    RDNode() :name(""), flag(0), size(0), nextAdd(-1) {};
    RDNode(bool f, string na, int s, int ne) :name(na), flag(f), size(s), nextAdd(ne) {};
};

分区描述器一共由四个数据成员构成，第一个成员flag用于标志整个分区为空闲还是被占用；第二个成员name为分区的名称；第三个成员size为整个分区的大小；第四个成员指向下一个分区描述器的地址。

class Partion
{
public:
    Partion();                        //构造函数
    ~Partion();                        //析构函数
    void show();                    //显示内存状况
    int findLocation(string name);        //通过分区名找到对应分区描述器位置
    int findPreNode(string name);        //通过分区名找到这个分区的前一个分区描述器
    //choose为1时为首次适应算法，为2时为最佳算法，为3时为最坏算法
    bool request(int size, string name,int choose);    
    void release(string name);            //释放函数

private:
    int maxSize;                //最大容量
    RDNode* memory;                //地址空间
};

Partion类为动态分区式存贮区管理类，私有成员有最大容量maxSize以及整个内存空间memory。

算法设计：

void Partion::show()
{
    cout << "内存的总容量为：" << maxSize << endl;
    //memory[0]存有第一个分区描述器
    RDNode temp = memory[0];
    int begin = 0;
    int used = 0, unsed = 0;

    while (true)
    {
        if (temp.flag == 0)
        {
            unsed += temp.size;
            cout << "分区" << temp.name << "的" << "地址空间为" << begin << "-" << temp.nextAdd - 1
                << "为空闲状态，" << "分区大小为：" << temp.size << "rd!" << endl;
        }
        else
        {
            used += temp.size;
            cout << "分区" << temp.name << "的" << "地址空间为" << begin << "-" << temp.nextAdd - 1
                << "为被占用状态，" << "分区大小为：" << temp.size << "rd!" << endl;
        }
        begin = temp.nextAdd;
        if (begin == maxSize)
        {
            break;
        }
        temp = memory[begin];
    }
    cout << "处于空闲的空间有：" << unsed << "rd!" << endl;
    cout << "处于被占用的空间有：" << used << "rd!" << endl;
}

算法分析：先输出整个内存的总容量，定位到第一个分区节点即memory[0]，遍历内存中的每一个分区描述器，输出每一个分区的地址空间范围、这个分区所处的状态和这个分区的大小，最后输出总的空闲空间大小和总的占用空间大小。

//通过分区名找到对应分区描述器位置
int Partion::findLocation(string name)
{
    int result = -1;    //如果没有这个分区返回-1
    for (int i = 0;i < maxSize;i++)
    {
        if (memory[i].name == name)
        {
            result = i;
            break;
        }
    }
    return result;
}

算法思想：通过参数分区名在内存中找到对应分区描述器的位置，如果没找到就返回-1。否则遍历所有的分区描述器，找到了就返回地址位置。

//通过分区名找到这个分区的前一个分区描述器
int Partion::findPreNode(string name)
{
    int result = -1;    //如果没有这个分区返回-1
    for (int i = 0;i < maxSize;i++)
    {
        if (memory[memory[i].nextAdd].name == name)
        {
            result = i;
        }
    }
    return result;
}

算法思想：通过分区名在内存中找到对应分区的前一个分区位置，如果没找到就返回-1。否则遍历整个分区描述器，如果某个分区描述器的指针指向的分区描述器为结果，就返回这个分区描述器的位置。

//内存分配,choose为1时为首次适应算法，为2时为最佳算法，为3时为最坏算法
bool Partion::request(int size, string name, int choose)
{
    //先默认最后一个空闲的分区为第一个
    int ptr = 0, cur = 0, des = 0;
    RDNode* result = &memory[cur];

    //找到适合的空闲分区
    while (ptr != maxSize)
    {
        //首次适应算法
        if (choose == 1)
        {
            if (memory[ptr].flag == 0 && memory[ptr].size >= size)
            {
                cur = ptr;
                des = ptr;
                result = &memory[cur];
            }
        }
        //最佳算法
        else if(choose == 2)
        {
            if (memory[ptr].size > result->size && memory[ptr].size >= size)
            {
                cur = ptr;
                des = ptr;
                result = &memory[cur];
            }
        }
        //最坏算法
        else if (choose == 3)
        {
            if (memory[ptr].size < result->size && memory[ptr].size >= size)
            {
                cur = ptr;
                des = ptr;
                result = &memory[cur];
            }
        }
        //否则输入不合法
        else
        {
            cout << "输入不合法，第三个参数必须为1、2或3！" << endl;
            return false;
        }

        des = ptr;
        ptr = memory[des].nextAdd;

    }

    //如果搜索一圈了都是第一个分区并且第一个分区空间不够，那么返回false
    if (cur == 0 && memory[0].size < size) return false;

    //在这个分区分配空间
    if (result->size == size)
    {//申请的空间恰好等于这块空间
        result->flag = 1;    //表示被占用
        result->name = name;
    }

    else
    {//否则该分区空间大于需要的空间
        //申请的空间分区
        des = cur + result->size - size;
        RDNode newNode(1, name, size, result->nextAdd);
        memory[des] = newNode;
        result->size = result->size - size - 1;
        result->nextAdd = des;
    }
    //cout << "分区地址为" << cur << endl;
    return true;
}

算法思想：先默认最后一个空闲的分区为第一个，根据不同的算法找到适合的空闲分区：如果是首次适应算法就找到最靠近高地址位的空闲分区(必须比请求的空间大)；如果是最佳算法就找出能满足作业要求且大小最小的空闲分区；如果是最佳算法就找出能满足作业要求且大小最大的空闲分区。如果没有合适的分区就请求失败，否则就找到了合适的位置，如果这个分区的大小恰好等于申请的资源就只需要把分区描述器的状态设置为被占用，并将这个这个分区描述器的名称设置为申请空间的名字。否则这个分区的大小大于申请的空间，就在这个分区中开辟一个新的分区，从高地址位向低地址位开辟，最前面的一个空间设置为分区描述器，向这个分区描述器中填充相关信息并更改原来的分区描述器信息，原来的分区描述器指针指向新开辟的分区描述器位置。

//释放函数
void Partion::release(string name)
{
    bool a = 0, b = 0;    //标记上邻和下邻是否存在
    int des;
    RDNode *pre=nullptr, *current=nullptr, *next=nullptr;
    des = findLocation(name);
    if (des == -1)
    {
        cout << "该区不存在！" << endl;
        return;
    }
    current = &memory[des];                        //需要回收的区
    des = findPreNode(name);
    //上邻存在
    if (des != -1)
    {
        pre = &memory[des];
        a = 1;
    }
    //下邻存在
    des = current->nextAdd;
    if(des != maxSize)
    {
        next = &memory[des];
        b = 1;
    }

    //只有上邻没有下邻时
    if (a == 1 && b == 0)
    {
        //上邻空闲时,把两个区合并
        if (pre->flag==0)
        {
            pre->nextAdd = current->nextAdd;
            pre->size = pre->size + current->size + 1;
        }
        //否则就是已分配,设置为空闲即可
        else
        {
            current->flag = false;
        }
    }

    //上下邻都没有，即这一整块空间都属于一个
    else if (a == 0 && b == 0)
    {
        current->flag = 0;
    }

    //只有下邻没有上邻时
    else if (a == 0 && b == 1)
    {
        //下邻空闲时，把两个区合并
        if (next->flag == 0)
        {
            current->flag = 0;
            current->nextAdd = next->nextAdd;
            current->size = current->size + next->size + 1;
        }
        //否则就是已分配
        else
        {
            current->flag = 0;
        }
    }
    //否则下邻和上邻都存在，有4种情况
    else
    {    //上邻空闲下邻已分配
        if (pre->flag == false && next->flag == true)
        {
            pre->nextAdd = current->nextAdd;
            pre->size = pre->size + current->size + 1;
        }
        //上邻分配下邻空闲
        if (pre->flag == true && next->flag == false)
        {
            current->flag = false;
            current->nextAdd = next->nextAdd;
            current->size = current->size + next->size + 1;
        }
        //上邻空闲下邻空闲
        if (pre->flag == false && next->flag == false)
        {
            pre->nextAdd = next->nextAdd;
            pre->size = pre->size + current->size + next->size + 2;
        }
        //上邻已分配下邻已分配
        if (pre->flag == true && next->flag == true)
        {
            current->flag = false;
        }
    }
}

算法思想：释放空间时一共有7种情况。①：只有上邻没有下邻时，如果上邻空闲，就把两个区合并，如果上邻占用，就把这个空间标志设为空闲。②：上下邻都没有，即这一整块空间都属于一个，把整个空间设置为空闲③：只有下邻没有上邻时，如果下邻空闲就把两个区合并，否则设置为空闲④：上邻空闲下邻已分配，和上邻合并⑤：上邻分配下邻空闲，和下邻合并⑥：上邻空闲下邻空闲，三个区域合并成一个区域并设置为空闲⑦上邻已分配下邻已分配，将整个分区设置为空闲。

源代码

stdfax.h

#ifndef STDAFX_H_INCLUDE
#define STDAFX_H_INCLUDE

#include <iostream>

using namespace std;

#define max 512

#endif // !STDAFX_H_INCLUDE

partion.h

#ifndef PARTION_H_INCLUDE
#define PARTION_H_INCLUDE

#include "stdafx.h"

//分区描述器
struct RDNode
{
    bool flag;
    string name;
    int size;
    int nextAdd;
    RDNode() :name(""), flag(0), size(0), nextAdd(-1) {};
    RDNode(bool f, string na, int s, int ne) :name(na), flag(f), size(s), nextAdd(ne) {};
};

class Partion
{
public:
    Partion();                        //构造函数
    ~Partion();                        //析构函数
    void show();                    //显示内存状况
    int findLocation(string name);    //通过分区名找到对应分区描述器位置
    int findPreNode(string name);    //通过分区名找到这个分区的前一个分区描述器
    bool request(int size, string name,int choose);    //choose为1时为首次适应算法，为2时为最佳算法，为3时为最坏算法
    void release(string name);            //释放函数

private:
    int maxSize;            //最大容量
    RDNode* memory;            //地址空间
};

//构造函数
Partion::Partion()
{
    maxSize = max;
    memory = new RDNode[maxSize];
    RDNode* node = new RDNode(0, "J0", maxSize - 1, maxSize);
    memory[0] = *node;
}

//析构函数
Partion::~Partion()
{
    delete[] memory;
}

//显示现在的内存状况
void Partion::show()
{
    cout << "内存的总容量为：" << maxSize << endl;
    RDNode temp = memory[0];
    int begin = 0;
    int used = 0, unsed = 0;

    while (true)
    {
        if (temp.flag == 0)
        {
            unsed += temp.size;
            cout << "分区" << temp.name << "的" << "地址空间为" << begin << "-" << temp.nextAdd - 1
                << "为空闲状态，" << "分区大小为：" << temp.size << "rd!" << endl;
        }
        else
        {
            used += temp.size;
            cout << "分区" << temp.name << "的" << "地址空间为" << begin << "-" << temp.nextAdd - 1
                << "为被占用状态，" << "分区大小为：" << temp.size << "rd!" << endl;
        }
        begin = temp.nextAdd;
        if (begin == maxSize)
        {
            break;
        }
        temp = memory[begin];
    }
    cout << "处于空闲的空间有：" << unsed << "rd!" << endl;
    cout << "处于被占用的空间有：" << used << "rd!" << endl;
}

//通过分区名找到对应分区描述器位置
int Partion::findLocation(string name)
{
    int result = -1;    //如果没有这个分区返回-1
    for (int i = 0;i < maxSize;i++)
    {
        if (memory[i].name == name)
        {
            result = i;
            break;
        }
    }
    return result;
}

//通过分区名找到这个分区的前一个分区描述器
int Partion::findPreNode(string name)
{
    int result = -1;    //如果没有这个分区返回-1
    for (int i = 0;i < maxSize;i++)
    {
        if (memory[memory[i].nextAdd].name == name)
        {
            result = i;
        }
    }
    return result;
}

//内存分配,choose为1时为首次适应算法，为2时为最佳算法，为3时为最坏算法
bool Partion::request(int size, string name, int choose)
{
    //先默认最后一个空闲的分区为第一个
    int ptr = 0, cur = 0, des = 0;
    RDNode* result = &memory[cur];

    //找到适合的空闲分区
    while (ptr != maxSize)
    {
        //首次适应算法
        if (choose == 1)
        {
            if (memory[ptr].flag == 0 && memory[ptr].size >= size)
            {
                cur = ptr;
                des = ptr;
                result = &memory[cur];
            }
        }
        //最佳算法
        else if(choose == 2)
        {
            if (memory[ptr].size > result->size && memory[ptr].size >= size)
            {
                cur = ptr;
                des = ptr;
                result = &memory[cur];
            }
        }
        //最坏算法
        else if (choose == 3)
        {
            if (memory[ptr].size < result->size && memory[ptr].size >= size)
            {
                cur = ptr;
                des = ptr;
                result = &memory[cur];
            }
        }
        //否则输入不合法
        else
        {
            cout << "输入不合法，第三个参数必须为1、2或3！" << endl;
            return false;
        }

        des = ptr;
        ptr = memory[des].nextAdd;

    }

    //如果搜索一圈了都是第一个分区并且第一个分区空间不够，那么返回false
    if (cur == 0 && memory[0].size < size) return false;

    //在这个分区分配空间
    if (result->size == size)
    {//申请的空间恰好等于这块空间
        result->flag = 1;    //表示被占用
        result->name = name;
    }

    else
    {//否则该分区空间大于需要的空间
        //申请的空间分区
        des = cur + result->size - size;
        RDNode newNode(1, name, size, result->nextAdd);
        memory[des] = newNode;
        result->size = result->size - size - 1;
        result->nextAdd = des;
    }
    //cout << "分区地址为" << cur << endl;
    return true;
}

//释放函数
void Partion::release(string name)
{
    bool a = 0, b = 0;    //标记上邻和下邻是否存在
    int des;
    RDNode *pre=nullptr, *current=nullptr, *next=nullptr;
    des = findLocation(name);
    if (des == -1)
    {
        cout << "该区不存在！" << endl;
        return;
    }
    current = &memory[des];                        //需要回收的区
    des = findPreNode(name);
    //上邻存在
    if (des != -1)
    {
        pre = &memory[des];
        a = 1;
    }
    //下邻存在
    des = current->nextAdd;
    if(des != maxSize)
    {
        next = &memory[des];
        b = 1;
    }

    //只有上邻没有下邻时
    if (a == 1 && b == 0)
    {
        //上邻空闲时,把两个区合并
        if (pre->flag==0)
        {
            pre->nextAdd = current->nextAdd;
            pre->size = pre->size + current->size + 1;
        }
        //否则就是已分配,设置为空闲即可
        else
        {
            current->flag = false;
        }
    }

    //上下邻都没有，即这一整块空间都属于一个
    else if (a == 0 && b == 0)
    {
        current->flag = 0;
    }

    //只有下邻没有上邻时
    else if (a == 0 && b == 1)
    {
        //下邻空闲时，把两个区合并
        if (next->flag == 0)
        {
            current->flag = 0;
            current->nextAdd = next->nextAdd;
            current->size = current->size + next->size + 1;
        }
        //否则就是已分配
        else
        {
            current->flag = 0;
        }
    }
    //否则下邻和上邻都存在，有4种情况
    else
    {    //上邻空闲下邻已分配
        if (pre->flag == false && next->flag == true)
        {
            pre->nextAdd = current->nextAdd;
            pre->size = pre->size + current->size + 1;
        }
        //上邻分配下邻空闲
        if (pre->flag == true && next->flag == false)
        {
            current->flag = false;
            current->nextAdd = next->nextAdd;
            current->size = current->size + next->size + 1;
        }
        //上邻空闲下邻空闲
        if (pre->flag == false && next->flag == false)
        {
            pre->nextAdd = next->nextAdd;
            pre->size = pre->size + current->size + next->size + 2;
        }
        //上邻已分配下邻已分配
        if (pre->flag == true && next->flag == true)
        {
            current->flag = false;
        }
    }
}

#endif // !PARTION_H_INCLUDE

main.cpp

#include "partion.h"

int main()
{
    Partion obj;
    int n;
    cout << "请选择放置策略(1代表首次适应算法,2代表最佳算法,3代表最坏算法):";
    cin >> n;
    if (n != 1 && n != 2 && n != 3)
    {
        cout << "输入不合法！" << endl;
    }
    else 
    {
        //cout << "首次适应算法:" << endl;
        //cout << "最佳算法:" << endl;
        //cout << "最坏算法:" << endl;
        obj.request(162, "J1", n);
        obj.request(64, "J2", n);
        obj.request(120, "J3", n);
        obj.request(86, "J4", n);
        obj.release("J1");
        obj.release("J3");
        obj.request(72, "J5", n);
        obj.request(100, "J6", n);
        obj.release("J2");
        obj.request(63, "J7", n);
        obj.request(60, "J8", n);
        obj.release("J4");
        obj.request(110, "J9", n);
        obj.request(42, "J10", n);
        obj.show();
    }
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/04/25/cao-zuo-xi-tong-dong-tai-fen-qu-shi-cun-zhu-qu-guan-li/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 操作系统
赏
评论
 上一篇
[操作系统]请求分页系统中的置换算法 [操作系统]请求分页系统中的置换算法
题目描述（1）通过如下方法产生一指令序列，共320条指令 A.在[1，32k-2]的指令地址之间随机选取一起点M,访问 M； B.顺序访问M+1； C.在[0，M-1]中随机选取M1，访问 M1； D.顺序访问M1+1； E.在[M1+2，
2021-04-28 操作系统
C++ 操作系统
下一篇 
[操作系统]银行家算法 [操作系统]银行家算法
题目描述用程序实现银行家算法，为进程请求资源。 已分配资源数量 资源需求量 A B C A B C P1 2 1 2 3 4 7 P2 4 0 2 1 3 4 P3 3 0 5 0 0 3 P4 2
2021-04-21 操作系统
C++ 操作系统
  目录