【CS.OS】堆管理算法:不同的堆分配和管理算法

1000.5.CS.OS.1.3-基础-内存管理-堆管理算法-Created: 2024-06-09.Sunday10:41
在这里插入图片描述


在操作系统和程序设计中,内存管理是一个至关重要的环节。不同的堆分配和管理算法,如首次适应(first-fit)、最佳适应(best-fit)和伙伴系统(buddy system),在内存分配和管理中发挥着重要作用。这篇文章将深入探讨这些算法,并通过示例代码展示其实现。

1 内存分配算法概述

内存分配算法用于动态地分配和释放内存,以便程序能够高效地使用系统资源。以下是一些常见的堆分配和管理算法:

1.1 首次适应(First-Fit)

首次适应算法是一种简单且快速的内存分配算法。它从头开始扫描内存分区表,找到第一个足够大的空闲块,并分配给请求的进程。

优点:

  • 快速:由于从头开始扫描,通常能迅速找到合适的空闲块。
  • 简单:实现和理解都较为简单。

缺点:

  • 内存碎片:容易产生外部碎片,导致内存利用率下降。

示例代码:

#include <iostream>
#include <vector>

struct Block {
    int size;
    bool free;
    Block(int s) : size(s), free(true) {}
};

class FirstFitAllocator {
public:
    FirstFitAllocator(std::vector<int> blockSizes) {
        for (int size : blockSizes) {
            blocks.push_back(Block(size));
        }
    }

    void* allocate(int requestSize) {
        for (Block& block : blocks) {
            if (block.free && block.size >= requestSize) {
                block.free = false;
                return &block;
            }
        }
        return nullptr; // Allocation failed
    }

    void deallocate(void* ptr) {
        Block* block = static_cast<Block*>(ptr);
        block->free = true;
    }

private:
    std::vector<Block> blocks;
};

int main() {
    FirstFitAllocator allocator({100, 500, 200, 300, 600});
    void* ptr1 = allocator.allocate(150);
    void* ptr2 = allocator.allocate(100);
    allocator.deallocate(ptr1);
    void* ptr3 = allocator.allocate(50);
    return 0;
}

1.2 最佳适应(Best-Fit)

最佳适应算法通过扫描整个内存分区表,找到最接近请求大小的空闲块进行分配。这种方法尽量减少剩余的空闲块,降低外部碎片的产生。

优点:

  • 内存利用率高:通过分配最接近大小的空闲块,减少了外部碎片。
  • 有效:在内存资源紧张的情况下表现较好。

缺点:

  • 扫描时间长:需要扫描整个内存分区表,可能导致分配时间较长。

示例代码:

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

struct Block {
    int size;
    bool free;
    Block(int s) : size(s), free(true) {}
};

class BestFitAllocator {
public:
    BestFitAllocator(std::vector<int> blockSizes) {
        for (int size : blockSizes) {
            blocks.push_back(Block(size));
        }
    }

    void* allocate(int requestSize) {
        int bestFitIndex = -1;
        int minDiff = std::numeric_limits<int>::max();

        for (int i = 0; i < blocks.size(); ++i) {
            if (blocks[i].free && blocks[i].size >= requestSize) {
                int diff = blocks[i].size - requestSize;
                if (diff < minDiff) {
                    minDiff = diff;
                    bestFitIndex = i;
                }
            }
        }

        if (bestFitIndex != -1) {
            blocks[bestFitIndex].free = false;
            return &blocks[bestFitIndex];
        }
        return nullptr; // Allocation failed
    }

    void deallocate(void* ptr) {
        Block* block = static_cast<Block*>(ptr);
        block->free = true;
    }

private:
    std::vector<Block> blocks;
};

int main() {
    BestFitAllocator allocator({100, 500, 200, 300, 600});
    void* ptr1 = allocator.allocate(150);
    void* ptr2 = allocator.allocate(100);
    allocator.deallocate(ptr1);
    void* ptr3 = allocator.allocate(50);
    return 0;
}

2 伙伴系统(Buddy System)

伙伴系统是一种平衡了首次适应和最佳适应优点的内存分配算法。它将内存分割成大小为2的幂次方的块,当需要分配内存时,会找到最小的满足请求的块。如果块大小过大,会将其分割成两个“伙伴”块,并继续分配。

优点:

  • 内存碎片少:由于采用幂次方块,容易合并相邻空闲块,减少碎片。
  • 分配和释放效率高:通过伙伴系统,分配和释放操作较为高效。

缺点:

  • 内存浪费:有时会由于块大小限制,导致内存浪费。

示例代码:

#include <iostream>
#include <vector>
#include <cmath>

class BuddyAllocator {
public:
    BuddyAllocator(int size) {
        int n = std::ceil(std::log2(size));
        maxSize = 1 << n;
        freeBlocks.resize(n + 1);
        freeBlocks[n].push_back(0);
    }

    void* allocate(int size) {
        int n = std::ceil(std::log2(size));
        for (int i = n; i < freeBlocks.size(); ++i) {
            if (!freeBlocks[i].empty()) {
                int block = freeBlocks[i].back();
                freeBlocks[i].pop_back();
                while (i > n) {
                    --i;
                    int buddy = block ^ (1 << i);
                    freeBlocks[i].push_back(buddy);
                }
                return reinterpret_cast<void*>(block * minBlockSize);
            }
        }
        return nullptr; // Allocation failed
    }

    void deallocate(void* ptr) {
        int block = reinterpret_cast<int>(ptr) / minBlockSize;
        int size = 1;
        while (true) {
            int buddy = block ^ size;
            auto it = std::find(freeBlocks[std::log2(size)].begin(), freeBlocks[std::log2(size)].end(), buddy);
            if (it == freeBlocks[std::log2(size)].end()) {
                freeBlocks[std::log2(size)].push_back(block);
                break;
            }
            freeBlocks[std::log2(size)].erase(it);
            block &= ~size;
            size <<= 1;
        }
    }

private:
    int maxSize;
    int minBlockSize = 1;
    std::vector<std::vector<int>> freeBlocks;
};

int main() {
    BuddyAllocator allocator(1024);
    void* ptr1 = allocator.allocate(100);
    void* ptr2 = allocator.allocate(200);
    allocator.deallocate(ptr1);
    void* ptr3 = allocator.allocate(50);
    return 0;
}

3 总结

通过了解不同的内存分配算法,我们可以更好地优化程序的内存使用,提高系统的性能和稳定性。希望这篇文章不仅能为你带来技术上的提升,还能激发你对内存管理的兴趣和热情。

在实际项目中,你使用过哪些内存分配算法?它们在你的项目中表现如何?欢迎在评论区分享你的经验和见解,与其他读者互动,共同探讨内存管理的最佳实践。

References

相关推荐

  1. 掌握:Python算法实践中高效数据管理与优化

    2024-06-11 03:52:02       21 阅读
  2. 算法排序

    2024-06-11 03:52:02       16 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-11 03:52:02       8 阅读
  2. 【Python教程】压缩PDF文件大小

    2024-06-11 03:52:02       9 阅读
  3. 通过文章id递归查询所有评论(xml)

    2024-06-11 03:52:02       10 阅读

热门阅读

  1. ABSD-系统架构师(七)

    2024-06-11 03:52:02       8 阅读
  2. document.queryselector怎么用

    2024-06-11 03:52:02       8 阅读
  3. Centos7.9部署单节点K8S环境

    2024-06-11 03:52:02       5 阅读
  4. leetcode 40. 组合总和 II

    2024-06-11 03:52:02       6 阅读
  5. Cordova WebView重定向到网站

    2024-06-11 03:52:02       5 阅读
  6. 重写setter方法要小心递归调用

    2024-06-11 03:52:02       4 阅读
  7. 代码随想录打卡第一天(补)

    2024-06-11 03:52:02       4 阅读
  8. web3规则改变者:Linea的厉害之处

    2024-06-11 03:52:02       5 阅读
  9. 什么是 prop drilling,如何避免?

    2024-06-11 03:52:02       7 阅读
  10. 【CSP】202312-1 仓库规划

    2024-06-11 03:52:02       6 阅读
  11. testbench仿真文件编写规则

    2024-06-11 03:52:02       6 阅读