操作系统实验三 存储管理

server/2025/1/1 8:49:14/

实验三 存储管理

一、实验目的

通过实验使学生了解可变式分区管理使用的主要数据结构，分配、回收的主要技术，了解最优适应分配、最坏适应分配、最先适应分配和循环适应分配等分配算法。基本能达到下列具体的目标：

  1. 掌握初步进程在内存中的映像所需要的内存需求。
  2. 内存的最先分配算法首先实现，再逐步完成最优和最坏的分配算法。

二、实验内容

  1. 在进程管理的基础上实现内存分配和回收。
  2. 学生了解实验目的，画出流程框图。
  3. 复习单向链操作编程，编写全部程序。能够实现多种分配算法。
  4. 创建和撤消进程时，完成内存的分配和回收操作，必须可以显示空闲内存块队列状态。注意回收内存时，空闲块的合并操作。
  5. 学生要在上一次实验的基础上对队列的删除、插入进一步熟练。
  1. 程序设计（原理、数据结构设计、流程图）

1. 原理

该程序实现了一个简单的内存管理器，支持多种内存分配策略（如首次适应、最佳适应、最坏适应和下一个适应）。内存管理器通过链表结构管理空闲内存块，允许动态分配和释放内存。

2. 数据结构设计

MemoryBlock: 结构体表示一个内存块，包含起始地址、大小和指向下一个内存块的指针。

MemoryManager: 类管理内存块的分配和释放，维护一个空闲内存块的链表。

  1. 流程图

(2)核心函数

// ... existing code ...

int allocate(int size, const std::string& strategy) {

    if (size <= 0) return -1;

    if (strategy == "first_fit") {

        return firstFitAllocate(size);

    }

    else if (strategy == "best_fit") {

        return bestFitAllocate(size);

    }

    else if (strategy == "worst_fit") {

        return worstFitAllocate(size);

    }

    else if (strategy == "next_fit") {

        return nextFitAllocate(size);

    }

    return -1;

}

// ... existing code ...

void deallocate(int start, int size) {

    MemoryBlock* newBlock = new MemoryBlock(start, size);

    MemoryBlock* current = freeList;

    MemoryBlock* prev = nullptr;

    // 找到插入点

    while (current && current->start < start) {

        prev = current;

        current = current->next;

    }

    // 插入新的空闲块

    if (prev) {

        prev->next = newBlock;

    }

    else {

        freeList = newBlock;

    }

    newBlock->next = current;

    // 合并相邻的空闲块

    mergeFreeBlocks();

}

// ... existing code ...

private:

int firstFitAllocate(int size) {

    MemoryBlock* current = freeList;

    while (current) {

        if (current->size >= size) {

            int start = current->start;

            current->start += size;

            current->size -= size;

            if (current->size == 0) {

                // 如果当前块被完全分配，移除它

                if (current == freeList) {

                    freeList = current->next;

                }

                else {

                    MemoryBlock* prev = freeList;

                    while (prev->next != current) {

                        prev = prev->next;

                    }

                    prev->next = current->next;

                }

                delete current;

            }

            return start; // 返回分配的起始地址

        }

        current = current->next;

    }

    return -1; // 分配失败

}

// ... existing code ...

allocate 函数根据用户选择的策略调用相应的分配函数。

deallocate 函数负责释放指定内存块并合并相邻的空闲块。

firstFitAllocate 函数实现了首次适应算法，查找第一个足够大的空闲块进行分配。

(3)测试截图

源码：

#include <iostream>
#include <vector>
#include <limits>

struct MemoryBlock {
    int start; // 内存块的起始地址
    int size;  // 内存块的大小
    MemoryBlock* next; // 指向下一个内存块的指针

    MemoryBlock(int s, int sz) : start(s), size(sz), next(nullptr) {}
};


class MemoryManager {
private:
    MemoryBlock* freeList; // 空闲内存块链表
    int totalSize; // 总内存大小

public:
    MemoryManager(int size) : totalSize(size) {
        freeList = new MemoryBlock(0, size); // 初始化一个大的空闲块
    }

    ~MemoryManager() {
        // 释放内存块
        while (freeList) {
            MemoryBlock* temp = freeList;
            freeList = freeList->next;
            delete temp;
        }
    }

    void printFreeList() {
        std::cout << "Free memory blocks:\n";
        MemoryBlock* current = freeList;
        while (current) {
            std::cout << "Start: " << current->start << ", Size: " << current->size << "\n";
            current = current->next;
        }
    }

    int allocate(int size, const std::string& strategy) {
        if (size <= 0) return -1;

        if (strategy == "first_fit") {
            return firstFitAllocate(size);
        }
        else if (strategy == "best_fit") {
            return bestFitAllocate(size);
        }
        else if (strategy == "worst_fit") {
            return worstFitAllocate(size);
        }
        else if (strategy == "next_fit") {
            return nextFitAllocate(size);
        }
        return -1;
    }

    void deallocate(int start, int size) {
        // 释放内存块并合并空闲块
        MemoryBlock* newBlock = new MemoryBlock(start, size);
        MemoryBlock* current = freeList;
        MemoryBlock* prev = nullptr;

        // 找到插入点
        while (current && current->start < start) {
            prev = current;
            current = current->next;
        }

        // 插入新的空闲块
        if (prev) {
            prev->next = newBlock;
        }
        else {
            freeList = newBlock;
        }
        newBlock->next = current;

        // 合并相邻的空闲块
        mergeFreeBlocks();
    }

private:
    int firstFitAllocate(int size) {
        MemoryBlock* current = freeList;
        while (current) {
            if (current->size >= size) {
                int start = current->start;
                current->start += size;
                current->size -= size;

                if (current->size == 0) {
                    // 如果当前块被完全分配，移除它
                    if (current == freeList) {
                        freeList = current->next;
                    }
                    else {
                        MemoryBlock* prev = freeList;
                        while (prev->next != current) {
                            prev = prev->next;
                        }
                        prev->next = current->next;
                    }
                    delete current;
                }
                return start; // 返回分配的起始地址
            }
            current = current->next;
        }
        return -1; // 分配失败
    }

    int bestFitAllocate(int size) {
        MemoryBlock* current = freeList;
        MemoryBlock* bestFit = nullptr;
        MemoryBlock* bestFitPrev = nullptr;

        // 找到最适合的块
        while (current) {
            if (current->size >= size) {
                if (!bestFit || current->size < bestFit->size) {
                    bestFit = current;
                    bestFitPrev = nullptr;
                }
            }
            current = current->next;
        }

        if (bestFit) {
            int start = bestFit->start;
            bestFit->start += size;
            bestFit->size -= size;

            if (bestFit->size == 0) {
                // 如果当前块被完全分配，移除它
                if (bestFit == freeList) {
                    freeList = bestFit->next;
                }
                else {
                    MemoryBlock* prev = freeList;
                    while (prev->next != bestFit) {
                        prev = prev->next;
                    }
                    prev->next = bestFit->next;
                }
                delete bestFit;
            }
            return start; // 返回分配的起始地址
        }
        return -1; // 分配失败
    }

    int worstFitAllocate(int size) {
        MemoryBlock* current = freeList;
        MemoryBlock* worstFit = nullptr;
        MemoryBlock* worstFitPrev = nullptr;

        // 找到最坏适合的块
        while (current) {
            if (current->size >= size) {
                if (!worstFit || current->size > worstFit->size) {
                    worstFit = current;
                    worstFitPrev = nullptr;
                }
            }
            current = current->next;
        }

        if (worstFit) {
            int start = worstFit->start;
            worstFit->start += size;
            worstFit->size -= size;

            if (worstFit->size == 0) {
                // 如果当前块被完全分配，移除它
                if (worstFit == freeList) {
                    freeList = worstFit->next;
                }
                else {
                    MemoryBlock* prev = freeList;
                    while (prev->next != worstFit) {
                        prev = prev->next;
                    }
                    prev->next = worstFit->next;
                }
                delete worstFit;
            }
            return start; // 返回分配的起始地址
        }
        return -1; // 分配失败
    }

    int nextFitAllocate(int size) {
        static MemoryBlock* lastAllocated = nullptr; // 记录上次分配的位置
        MemoryBlock* current = lastAllocated ? lastAllocated : freeList;

        while (current) {
            if (current->size >= size) {
                int start = current->start;
                current->start += size;
                current->size -= size;

                if (current->size == 0) {
                    // 如果当前块被完全分配，移除它
                    if (current == freeList) {
                        freeList = current->next;
                    }
                    else {
                        MemoryBlock* prev = freeList;
                        while (prev->next != current) {
                            prev = prev->next;
                        }
                        prev->next = current->next;
                    }
                    delete current;
                }
                lastAllocated = current; // 更新上次分配的位置
                return start; // 返回分配的起始地址
            }
            current = current->next;
        }

        // 如果没有找到，继续从头开始搜索
        current = freeList;
        while (current) {
            if (current->size >= size) {
                int start = current->start;
                current->start += size;
                current->size -= size;

                if (current->size == 0) {
                    // 如果当前块被完全分配，移除它
                    if (current == freeList) {
                        freeList = current->next;
                    }
                    else {
                        MemoryBlock* prev = freeList;
                        while (prev->next != current) {
                            prev = prev->next;
                        }
                        prev->next = current->next;
                    }
                    delete current;
                }
                lastAllocated = current; // 更新上次分配的位置
                return start; // 返回分配的起始地址
            }
            current = current->next;
        }

        return -1; // 分配失败
    }

private:
    void mergeFreeBlocks() {
        if (!freeList) return; // 如果空闲列表为空，直接返回

        MemoryBlock* current = freeList;
        MemoryBlock* nextBlock = current->next;

        while (nextBlock) {
            // 情况 1: 前空后不空
            if (current->start + current->size == nextBlock->start) {
                // 合并当前块和下一个块
                current->size += nextBlock->size; // 合并大小
                current->next = nextBlock->next; // 跳过下一个块
                delete nextBlock; // 释放内存
                nextBlock = current->next; // 更新下一个块
            }
            // 情况 2: 前不空后空
            else if (current->start + current->size < nextBlock->start) {
                // 当前块和下一个块不相邻，直接移动到下一个块
                current = nextBlock; // 移动到下一个块
                nextBlock = nextBlock->next; // 更新下一个块
            }
            // 情况 3: 前后都空
            else {
                // 这种情况在当前逻辑中不需要特别处理，因为我们只处理相邻块的合并
                // 继续移动到下一个块
                current = nextBlock; // 移动到下一个块
                nextBlock = nextBlock->next; // 更新下一个块
            }
        }
    }

};

int main() {
    MemoryManager memoryManager(100); // 创建内存管理器，总内存为100

    std::string strategy;
    while (true) {
        std::cout << "输入想要的分配算法 (first_fit, best_fit, worst_fit, next_fit) or 'exit' to quit: ";
        std::cin >> strategy;
        if (strategy == "exit") break;

        int size;
        std::cout << "输入要分配的内存大小 ";
        std::cin >> size;

        int address = memoryManager.allocate(size, strategy);
        if (address != -1) {
            std::cout << "分配的内存位于： " << address << "\n";
        }
        else {
            std::cout << "分配失败！\n";
        }
        memoryManager.printFreeList(); // 打印空闲内存块状态

        std::cout << "输入要取消分配的大小: ";
        std::cin >> size;
        memoryManager.deallocate(address, size); // 释放内存
        memoryManager.printFreeList(); // 打印空闲内存块状态
    }

    return 0;
}


http://www.ppmy.cn/server/154267.html

相关文章

计算机的错误计算（一百九十四）

计算机的错误计算（一百九十四）

摘要 用两个大模型计算 其中&#xff0c;一个大模型通过化简&#xff0c;得出正确结果 0&#xff1b;而另外一个在化简过程中出现错误&#xff0c;得出了错误结果。 例1. 计算 下面是一个大模型的推导化简过程。 以上为一个大模型的回答。 下面是另外一个大模型的回复。 点评…
阅读更多...
Python数据可视化小项目

Python数据可视化小项目

英雄联盟S14世界赛选手数据可视化 由于本学期有一门数据可视化课程&#xff0c;课程结课作业要求完成一个数据可视化的小Demo&#xff0c;于是便有了这个小项目&#xff0c;课程老师要求比较简单&#xff0c;只要求熟练运用可视化工具展示数据&#xff0c;并不要求数据来源&am…
阅读更多...
java protobuf开发简介

java protobuf开发简介

protobuf-demo java protobuf开发简介 protobuf特点 protobuf与xml和json相比 优点&#xff1a;传输效率快&#xff1b;序列化后体积小适合网络传输&#xff1b;支持跨平台多语言。缺点&#xff1a;二进制格式导致可读性差&#xff1b;缺乏自描述。 开发简介 基于参考工程…
阅读更多...
Docker Compose一键部署Spring Boot + Vue项目

Docker Compose一键部署Spring Boot + Vue项目

目录 前提条件 概述 Compose简介 Compose文件 Compose环境 Compose命令 帮助命令 关键命令 Compose部署项目 初始化环境 查看代码文件 sql数据准备 nginx配置文件准备 创建 compose.yaml 一键启动compose多个容器 浏览器访问虚拟机ip:80(可省略默认的80端口) …
阅读更多...
【超级详细】七牛云配置阿里云域名详细过程记录

【超级详细】七牛云配置阿里云域名详细过程记录

0. 准备一个阿里云域名&#xff0c;记得要备案&#xff01;&#xff01;&#xff01;&#xff01; 1. 创建七牛云存储空间 首先&#xff0c;登录七牛云控制台&#xff0c;创建一个新的存储空间&#xff08;Bucket&#xff09;。这个存储空间将用于存放你的文件&#xff0c;并…
阅读更多...
RAGFlow 基于深度文档理解构建的开源 RAG引擎 - 在 Ubuntu 上安装 Docker Engine

RAGFlow 基于深度文档理解构建的开源 RAG引擎 - 在 Ubuntu 上安装 Docker Engine

RAGFlow 基于深度文档理解构建的开源 RAG引擎 - 在 Ubuntu 上安装 Docker Engine flyfish 文本依据的是 https://docs.docker.com/engine/install/ubuntu/防火墙限制 警告 在安装 Docker 之前&#xff0c;请务必考虑以下安全影响和防火墙不兼容性&#xff1a; 如果你使用 u…
阅读更多...
GEE云计算、多源遥感、高光谱遥感技术蓝碳储量估算；红树林植被指数计算及提取

GEE云计算、多源遥感、高光谱遥感技术蓝碳储量估算；红树林植被指数计算及提取

大气温室气体浓度不断增加&#xff0c;导致气候变暖加剧&#xff0c;随之会引发一系列气象、生态和环境灾害。如何降低温室气体浓度和应对气候变化已成为全球关注的焦点。海洋是地球上最大的“碳库”,“蓝碳”即海洋活动以及海洋生物&#xff08;特别是红树林、盐沼和海草&…
阅读更多...
PPT画图——如何设置导致图片为600dpi

PPT画图——如何设置导致图片为600dpi

winr&#xff0c;输入regedit打开注册表 按路径找&#xff0c;HKEY_CURRENT_USER\Software\Microsoft\Office\XX.0\PowerPoint\Options&#xff08;xx为版本号&#xff0c;16.0 or 15.0或则其他&#xff09;。名称命名&#xff1a;ExportBitmapResolution 保存即可&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023