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

1000.5.CS.OS.1.3-基础-内存管理-堆管理算法-Created: 2024-06-09.Sunday10:41

文章目录

- - 1 内存分配算法概述
  - - 1.1 首次适应（First-Fit）
    - 1.2 最佳适应（Best-Fit）
  - 2 伙伴系统（Buddy System）
- 3 总结
- References

在操作系统和程序设计中，内存管理是一个至关重要的环节。不同的堆分配和管理算法，如首次适应（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;
}