C++ 内存分配模拟：经典算法实现与代码示例

内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。

经典的内存分配过程是这样进行的：

内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从 0 开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 i 开始的 s 个连续的内存单元称为首地址为 i 长度为 s 的地址片。
运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻 T，需要内存单元数 M 及运行时间 P。在运行时间 P 内（即 T 时刻开始，T+P 时刻结束），这 M 个被占用的内存单元不能再被其他进程使用。
假设在 T 时刻有一个进程申请 M 个单元，且运行时间为 P，则：
- 若 T 时刻内存中存在长度为 M 的空闲地址片，则系统将这 M 个空闲单元分配给该进程。若存在多个长度为 M 个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
- 如果 T 时刻不存在长度为 M 的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为 M 的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

输入格式

第一行是一个数 N，表示总内存单元数（即地址范围从 0 到 N-1）。

从第二行开始每行描述一个进程的三个整数 T、M、P（M <= N）。

最后一行用三个 0 表示结束。

数据已按 T 从小到大排序。

输入文件最多 10000 行，且所有数据都小于 109。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Process {
    int T;  // 申请时刻
    int M;  // 需要内存单元数
    int P;  // 运行时间
};

int main() {
    int N;  // 总内存单元数
    cin >> N;

    vector<Process> processes;
    int T, M, P;
    while (cin >> T >> M >> P && (T != 0 || M != 0 || P != 0)) {
        processes.push_back({T, M, P});
    }

    // 初始化内存状态，所有内存单元均为空闲
    vector<bool> memory(N, true);

    // 等待队列，存储等待分配内存的进程
    queue<Process> waitingQueue;

    // 模拟内存分配过程
    for (const auto& process : processes) {
        // 尝试分配内存
        bool allocated = false;
        for (int i = 0; i < N; ++i) {
            if (memory[i] && memory[i + process.M - 1]) {
                // 找到足够大的空闲地址片
                for (int j = i; j < i + process.M; ++j) {
                    memory[j] = false;
                }
                allocated = true;
                cout << process.T << " " << i << endl;
                break;
            }
        }

        // 如果没有分配成功，则放入等待队列
        if (!allocated) {
            waitingQueue.push(process);
        }

        // 处理等待队列中的进程
        while (!waitingQueue.empty()) {
            Process waitingProcess = waitingQueue.front();
            bool allocated = false;
            for (int i = 0; i < N; ++i) {
                if (memory[i] && memory[i + waitingProcess.M - 1]) {
                    // 找到足够大的空闲地址片
                    for (int j = i; j < i + waitingProcess.M; ++j) {
                        memory[j] = false;
                    }
                    allocated = true;
                    cout << waitingProcess.T << " " << i << endl;
                    waitingQueue.pop();
                    break;
                }
            }
            if (!allocated) {
                break;  // 如果队列头部的进程仍然无法分配，则停止处理队列
            }
        }

        // 释放已运行完成的进程的内存
        for (int i = 0; i < N; ++i) {
            if (memory[i]) {
                continue;
            }
            if (process.T + process.P == processes[processes.size() - 1].T) {
                memory[i] = true;
            }
        }
    }

    return 0;
}

代码说明

使用 vector<bool> memory 表示内存状态，true 表示空闲，false 表示已占用。
使用 queue<Process> waitingQueue 存储等待分配内存的进程。
遍历每个进程，尝试为其分配内存。如果内存充足，则分配并记录分配的起始地址；如果内存不足，则放入等待队列。
遍历等待队列，尝试为等待中的进程分配内存。
当进程运行结束时，释放其占用的内存。

代码示例

假设输入文件内容如下：

则程序输出如下：

注意

本代码使用了简单的内存分配算法，仅供参考。实际应用中，内存分配算法会更加复杂，需要考虑内存碎片、内存泄漏等问题。