操作系统实验——存储器的分配与回收算法实现

标签：std 操作系统 processSize int 存储器算法 memory allocated size

1.实验内容：

Exercise 1: 本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。

Exercise 2: 采用最先适应法、最佳适应法、最坏适应法分配主存空间。

Exercise 3: 当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。

Exercise 4: 当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。

Exercise 5: 设计的模拟系统中，进程数不小于5，进程调度方式可以采用实验一中的任何一种。

Exercise 6: 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。

1.头文件

#include <iostream>
#include <vector>
#include <algorithm>

#include < vector>
这个头文件提供了std::vector模板类的定义。std::vector是一个序列容器，能够存储具有相同类型的元素的动态数组。与普通的C数组不同，std::vector能够在运行时自动管理存储空间的分配和释放，支持动态地增加或减少元素的数量，并且能够自动处理元素的内存分配。

#include < algorithm>
这个头文件包含了各种算法函数，如排序、搜索、比较、复制、填充、变换等。这些算法可以对容器（如std::vector）中的元素进行操作，但算法本身并不管理容器的内存。算法通常接受迭代器作为参数，允许它们操作不同种类的容器。

2.定义一个结构体，用于表示各个空间（占用区/空闲区）

struct MemoryBlock {
    int startAddress;
    int size;
    bool allocated;

    MemoryBlock(int start, int sz, bool alloc) : startAddress(start), size(sz), allocated(alloc) {}
};

这个结构体MemoryBlock中包含了三个部分：首地址（startAddress），空间大小（size），bool数（allocated，用于判断该空间是否被分配）。
然后定义了一个构造函数名为 MemoryBlock，后续可使用此函数直接定义一个 MemoryBlock结构体，如：
MemoryBlock(0, 100, false)；
表示定义了一个首地址为0，大小为100，未被分配的空间。

3.定义一个结构体，用于表示被插入的进程

struct Process {
    std::string name;
    int size;
    int priority;
    Process(std::string n, int p ,int s) : name(n), size(p) ,priority(s) {}
};

这个结构体Process中包含了三个部分：进程名（name），运行所占空间（size），优先数（priority）。
然后定义了一个构造函数名为Process，后续可使用此函数直接定义一个Process结构体，如：
Process p1(“Process1”, 100, 1);
定义了一个结构体名为p1，进程名为Process1，运行所占空间为100，优先数为1，的结构体，在此用为表示一个进程。

4.定义一个bool函数用于后续配合main函数中的sort函数对空间首地址进行升序排序

bool sortByStartAddress(const MemoryBlock& a, const MemoryBlock& b) {
    return a.startAddress < b.startAddress;
}

5.定义一个类Fit，包含了需要使用的方法

（1）最先适应法

void firstFit(std::vector<MemoryBlock>& memory, std::string name, int processSize) {
        bool allocated = false;
        for (size_t i = 0; i < memory.size(); ++i) {
            if (!memory[i].allocated && memory[i].size >= processSize) {
                std::cout << "将进程 " << name << " 分配到内存块 [" << memory[i].startAddress
                    << ", " << memory[i].startAddress + memory[i].size << "]" << std::endl;
                int remainingSize = memory[i].size - processSize;
                if (remainingSize > 0) {
                    MemoryBlock allocatedBlock = { memory[i].startAddress, processSize, true };
                    MemoryBlock freeBlock = { memory[i].startAddress + processSize, remainingSize, false };

                    memory.erase(memory.begin() + i);
                    memory.insert(memory.begin() + i, allocatedBlock);
                    memory.insert(memory.begin() + i + 1, freeBlock);
                }
                else {
                    memory[i].allocated = true;
                }
                allocated = true;
                break;
            }
        }
        if (!allocated) {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }
    }

首先定义一个bool类型的变量allocated为false用于判断能否为进程分配内存

然后写一个for循环，用于遍历自己定义的主存空间的每一块内存
在for循环中用if (!memory[i].allocated && memory[i].size >= processSize)判断如果这块内存尚未被分配，且大小大于进程大小，则将进程分配给这块内存。定义一个整型变量remainingSize=内存空间与进程大小的差。

如差值大于0，则代表内存并未被完全分配，需要将没被分配的空间重新独立成一新的空闲区。

if (remainingSize > 0) {
                    MemoryBlock allocatedBlock = { memory[i].startAddress, processSize, true };
                    MemoryBlock freeBlock = { memory[i].startAddress + processSize, remainingSize, false };
                    memory.erase(memory.begin() + i);
                    memory.insert(memory.begin() + i, allocatedBlock);
                    memory.insert(memory.begin() + i + 1, freeBlock);
                }

定义一个新的空间allocatedBlock，首地址为原首地址，大小为进程大小，bool值为true用于表示占用区。
定义一个freeBlock，首地址为原首地址加进程大小，大小为内存空间与进程大小的差，bool值为false用于表示空闲区
最后使用erase与insert将原空间删除并将新的两个空间插入

如差值=0，则代表这块内存被完全利用，直接将其bool值改为true表示此内存已被分配。

最后将allocated = true，表示进程已被分配。

如for循环后allocated = false，则会进入此段代码

if (!allocated) {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }

表示进程太大，无合适空闲区。

（2）最佳适应法

void bestFit(std::vector<MemoryBlock>& memory, std::string name, int processSize) {
        int bestFitIndex = -1;
        int minRemainingSize = std::numeric_limits<int>::max();

        for (size_t i = 0; i < memory.size(); ++i) {
            if (!memory[i].allocated && memory[i].size >= processSize) {
                int remainingSize = memory[i].size - processSize;
                if (remainingSize < minRemainingSize) {
                    minRemainingSize = remainingSize;
                    bestFitIndex = i;
                }
            }
        }

        if (bestFitIndex != -1) {
            std::cout << "将进程 " << name << " 分配到内存块 [" << memory[bestFitIndex].startAddress
                << ", " << memory[bestFitIndex].startAddress + memory[bestFitIndex].size << "]" << std::endl;

            int remainingSize = memory[bestFitIndex].size - processSize;
            if (remainingSize > 0) {
                MemoryBlock allocatedBlock = { memory[bestFitIndex].startAddress, processSize, true };
                MemoryBlock freeBlock = { memory[bestFitIndex].startAddress + processSize, remainingSize, false };

                memory.erase(memory.begin() + bestFitIndex);
                memory.insert(memory.begin() + bestFitIndex, allocatedBlock);
                memory.insert(memory.begin() + bestFitIndex + 1, freeBlock);
            }
            else {
                memory[bestFitIndex].allocated = true;
            }
        }
        else {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }
    }

先定义一个整型变量 bestFitIndex = -1，用于存储找到的最佳空间在容器 memory中的编号。
然后定义一个足够大的数minRemainingSize，用于对比空间大小以找到可以插入的最小空间作为最合适的最佳空间。
得到最佳空间后执行与（1）类似插入操作将进程插入即可。

（3）最坏适应法

 void worstFit(std::vector<MemoryBlock>& memory, std::string name, int processSize) {
        int worstFitIndex = -1;
        int maxRemainingSize = -1;

        for (size_t i = 0; i < memory.size(); ++i) {
            if (!memory[i].allocated && memory[i].size >= processSize) {
                int remainingSize = memory[i].size - processSize;
                if (remainingSize > maxRemainingSize) {
                    maxRemainingSize = remainingSize;
                    worstFitIndex = i;
                }
            }
        }

        if (worstFitIndex != -1) {
            std::cout << "将进程 " << name << " 分配到内存块 [" << memory[worstFitIndex].startAddress
                << ", " << memory[worstFitIndex].startAddress + memory[worstFitIndex].size << "]" << std::endl;

            int remainingSize = memory[worstFitIndex].size - processSize;
            if (remainingSize > 0) {
                MemoryBlock allocatedBlock = { memory[worstFitIndex].startAddress, processSize, true };
                MemoryBlock freeBlock = { memory[worstFitIndex].startAddress + processSize, remainingSize, false };

                memory.erase(memory.begin() + worstFitIndex);
                memory.insert(memory.begin() + worstFitIndex, allocatedBlock);
                memory.insert(memory.begin() + worstFitIndex + 1, freeBlock);
            }
            else {
                memory[worstFitIndex].allocated = true;
            }
        }
        else {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }
    }

与（2）最佳适应法相似，区别在于定义的用于寻找空间的整型maxRemainingSize需要足够小，则为-1，且寻找插入空间时需要寻找可以插入的最大空间。

（4）打印函数（用于打印内存状态）

void printMemoryStatus(const std::vector<MemoryBlock>& memory) {
        std::cout << "内存状态：" << std::endl;
        for (const auto& block : memory) {
            std::cout << "[" << block.startAddress << " - " << block.startAddress + block.size - 1 << "] "
                << (block.allocated ? "已分配" : "空闲") << std::endl;
        }
    }

使用一个范围-based for 循环遍历容器
范围-based for 循环的讲解

（5）删除函数（用于删除被插入的进程，并释放其空间）

 void deleteMemory(std::vector<MemoryBlock>& memory, size_t i) {
        if (memory[i].allocated == true) {
            if (memory[i + 1].allocated == false) {
                MemoryBlock new_memory = { memory[i].startAddress,memory[i].size + memory[i + 1].size , false };
                memory.erase(memory.begin() + i + 1);
                memory.erase(memory.begin() + i);
                memory.insert(memory.begin() + i, new_memory);
            }
            else {
                memory[i].allocated = false;
            }
        }
        else {
            std::cout << "无法删除因此为空闲区" << std::endl;
        }
    }

首先判断选定的位置是否为占用区。若此为占用区，则判断此区域的下一个空间是否为空闲区。
如下一空间为空闲区，则需合并空闲区。定义一个新的空闲区，首地址为选定位置首地址，大小为两空间之和，bool值为false。再将原本的两个空间删除，将新的空间插入即可。
如下一空间为占用区，则不需合并空闲区，直接将此空间bool值改为false即可。

6.main函数

int main() {
    Fit fit;
    std::vector<MemoryBlock> memory = { {0, 100, false}, {100, 500, false}, {600, 400, false}, {1000, 300, false} };
    std::sort(memory.begin(), memory.end(), sortByStartAddress);

    std::vector<Process> processes;
    for (int i = 0; i < 5; i++) {
        std::string processName;
        int processSize;
        int processpriority;
        std::cout << "请输入第 " << i + 1 << " 个进程的名称：";
        std::cin >> processName;
        std::cout << "请输入第 " << i + 1 << " 个进程的大小：";
        std::cin >> processSize;
        std::cout << "请输入第 " << i + 1 << " 个进程的优先数：";
        std::cin >> processpriority;
        processes.emplace_back(processName, processSize, processpriority);
    }

    std::sort(processes.begin(), processes.end(), [](const Process& a, const Process& b) {
        return a.priority > b.priority; 
        });

    int x = 0;
    std::cout << "选择动态分区算法：1.最先适应法  2.最佳适应法  3.最坏适应法";
    std::cin >> x;
    switch (x) {
    case 1:
        for (const auto& process : processes) {
            fit.firstFit(memory, process.name, process.size);
        }
        break;
    case 2:
        for (const auto& process : processes) {
            fit.bestFit(memory, process.name, process.size);
        }
        break;
    case 3:
        for (const auto& process : processes) {
            fit.worstFit(memory, process.name, process.size);
        }
        break;
    default:
        std::cout << "请输入正确的数";
    }
    fit.printMemoryStatus(memory);
    int i;
    std::cout << "选择需要删除的被分配区";
    std::cin >> i;
    fit.deleteMemory(memory, i-1);
    std::cout << "删除后的情况";
    fit.printMemoryStatus(memory);
    return 0;
}

定义了4块空闲区，使用

std::sort(memory.begin(), memory.end(), sortByStartAddress);

进行首地址升序排序。

然后用for循环使用户可自主定义5个进程，使用

 std::sort(processes.begin(), processes.end(), [](const Process& a, const Process& b) {
        return a.priority > b.priority; 
        });

进行优先数排序。
使用一个switch (x)，用

for (const auto& process : processes) {
            fit.firstFit(memory, process.name, process.size);
        }

对各进程实现遍历插入。
最后还可以使用deleteMemory函数实现进程删除。
用printMemoryStatus内存分配情况打印出来。

7.完整代码

#include <iostream>
#include <vector>
#include <algorithm>

struct MemoryBlock {
    int startAddress;
    int size;
    bool allocated;

    MemoryBlock(int start, int sz, bool alloc) : startAddress(start), size(sz), allocated(alloc) {}
};

struct Process {
    std::string name;
    int size;
    int priority;
    Process(std::string n, int p ,int s) : name(n), size(p) ,priority(s) {}
};

bool sortByStartAddress(const MemoryBlock& a, const MemoryBlock& b) {
    return a.startAddress < b.startAddress;
}

class Fit {
public:
    

    void firstFit(std::vector<MemoryBlock>& memory, std::string name, int processSize) {
        bool allocated = false;

        for (size_t i = 0; i < memory.size(); ++i) {


            if (!memory[i].allocated && memory[i].size >= processSize) {


                std::cout << "将进程 " << name << " 分配到内存块 [" << memory[i].startAddress
                    << ", " << memory[i].startAddress + memory[i].size << "]" << std::endl;

                int remainingSize = memory[i].size - processSize;
                if (remainingSize > 0) {
                    MemoryBlock allocatedBlock = { memory[i].startAddress, processSize, true };
                    MemoryBlock freeBlock = { memory[i].startAddress + processSize, remainingSize, false };

                    memory.erase(memory.begin() + i);
                    memory.insert(memory.begin() + i, allocatedBlock);
                    memory.insert(memory.begin() + i + 1, freeBlock);
                }
                else {
                    memory[i].allocated = true;
                }
                allocated = true;
                break;
            }
        }
        if (!allocated) {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }
    }

    void bestFit(std::vector<MemoryBlock>& memory, std::string name, int processSize) {
        int bestFitIndex = -1;
        int minRemainingSize = std::numeric_limits<int>::max();

        for (size_t i = 0; i < memory.size(); ++i) {
            if (!memory[i].allocated && memory[i].size >= processSize) {
                int remainingSize = memory[i].size - processSize;
                if (remainingSize < minRemainingSize) {
                    minRemainingSize = remainingSize;
                    bestFitIndex = i;
                }
            }
        }

        if (bestFitIndex != -1) {
            std::cout << "将进程 " << name << " 分配到内存块 [" << memory[bestFitIndex].startAddress
                << ", " << memory[bestFitIndex].startAddress + memory[bestFitIndex].size << "]" << std::endl;

            int remainingSize = memory[bestFitIndex].size - processSize;
            if (remainingSize > 0) {
                MemoryBlock allocatedBlock = { memory[bestFitIndex].startAddress, processSize, true };
                MemoryBlock freeBlock = { memory[bestFitIndex].startAddress + processSize, remainingSize, false };

                memory.erase(memory.begin() + bestFitIndex);
                memory.insert(memory.begin() + bestFitIndex, allocatedBlock);
                memory.insert(memory.begin() + bestFitIndex + 1, freeBlock);
            }
            else {
                memory[bestFitIndex].allocated = true;
            }
        }
        else {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }
    }

    void worstFit(std::vector<MemoryBlock>& memory, std::string name, int processSize) {
        int worstFitIndex = -1;
        int maxRemainingSize = -1;

        for (size_t i = 0; i < memory.size(); ++i) {
            if (!memory[i].allocated && memory[i].size >= processSize) {
                int remainingSize = memory[i].size - processSize;
                if (remainingSize > maxRemainingSize) {
                    maxRemainingSize = remainingSize;
                    worstFitIndex = i;
                }
            }
        }

        if (worstFitIndex != -1) {
            std::cout << "将进程 " << name << " 分配到内存块 [" << memory[worstFitIndex].startAddress
                << ", " << memory[worstFitIndex].startAddress + memory[worstFitIndex].size << "]" << std::endl;

            int remainingSize = memory[worstFitIndex].size - processSize;
            if (remainingSize > 0) {
                MemoryBlock allocatedBlock = { memory[worstFitIndex].startAddress, processSize, true };
                MemoryBlock freeBlock = { memory[worstFitIndex].startAddress + processSize, remainingSize, false };

                memory.erase(memory.begin() + worstFitIndex);
                memory.insert(memory.begin() + worstFitIndex, allocatedBlock);
                memory.insert(memory.begin() + worstFitIndex + 1, freeBlock);
            }
            else {
                memory[worstFitIndex].allocated = true;
            }
        }
        else {
            std::cout << "无法为进程 " << name << " 分配内存" << std::endl;
        }
    }

    void printMemoryStatus(const std::vector<MemoryBlock>& memory) {
        std::cout << "内存状态：" << std::endl;
        for (const auto& block : memory) {
            std::cout << "[" << block.startAddress << " - " << block.startAddress + block.size - 1 << "] "
                << (block.allocated ? "已分配" : "空闲") << std::endl;
        }
    }

    void deleteMemory(std::vector<MemoryBlock>& memory, size_t i) {


        if (memory[i].allocated == true) {
            if (memory[i + 1].allocated == false) {
                MemoryBlock new_memory = { memory[i].startAddress,memory[i].size + memory[i + 1].size , false };
                memory.erase(memory.begin() + i + 1);
                memory.erase(memory.begin() + i);
                memory.insert(memory.begin() + i, new_memory);
            }
            else {
                memory[i].allocated = false;
            }
        }
        else {

            std::cout << "无法删除因此为空闲区" << std::endl;
        }




    }
};
int main() {
    Fit fit;
    std::vector<MemoryBlock> memory = { {0, 100, false}, {100, 500, false}, {600, 400, false}, {1000, 300, false} };
    std::sort(memory.begin(), memory.end(), sortByStartAddress);

    std::vector<Process> processes;
    for (int i = 0; i < 5; i++) {
        std::string processName;
        int processSize;
        int processpriority;
        std::cout << "请输入第 " << i + 1 << " 个进程的名称：";
        std::cin >> processName;
        std::cout << "请输入第 " << i + 1 << " 个进程的大小：";
        std::cin >> processSize;
        std::cout << "请输入第 " << i + 1 << " 个进程的优先数：";
        std::cin >> processpriority;
        processes.emplace_back(processName, processSize, processpriority);
    }

    std::sort(processes.begin(), processes.end(), [](const Process& a, const Process& b) {
        return a.priority > b.priority; 
        });

    int x = 0;
    std::cout << "选择动态分区算法：1.最先适应法  2.最佳适应法  3.最坏适应法";
    std::cin >> x;
    switch (x) {
    case 1:
        for (const auto& process : processes) {
            fit.firstFit(memory, process.name, process.size);
        }
        break;
    case 2:
        for (const auto& process : processes) {
            fit.bestFit(memory, process.name, process.size);
        }
        break;
    case 3:
        for (const auto& process : processes) {
            fit.worstFit(memory, process.name, process.size);
        }
        break;
    default:
        std::cout << "请输入正确的数";
    }
    fit.printMemoryStatus(memory);
    int i;
    std::cout << "选择需要删除的被分配区";
    std::cin >> i;
    fit.deleteMemory(memory, i-1);
    std::cout << "删除后的情况";
    fit.printMemoryStatus(memory);
    return 0;
}

8.运行结果

在这里插入图片描述

标签：std,操作系统,processSize,int,存储器,算法,memory,allocated,size
From： https://blog.csdn.net/xxxxxxxxxxlllll/article/details/141994083