内存管理-Linux伙伴系统-Java实现

简介: 内存 管理 Linux 伙伴系统 Java 实现

概念

一种经典的内存分配方案。
代码地址: github
https://github.com/fofcn/operation-system/tree/main/%E5%AE%9E%E8%B7%B5/3%20%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86/buddy

主要思想

  1. 将内存按照2的幂进行划分,组成若干个空闲块链表;
  2. 查找该链表找到满足进程需要的最佳匹配块

算法

  1. 首先将真个可用空间看做一块:2^U
  2. 假设进程申请的空间大小为s,如果满足 2^u-1 < s <= 2^u则分配整个块;否则将块划分为两个大小相等的伙伴,大小为2^u-1
  3. 一直划分知道产生大于或等于s的最小块

图例

代码实现

public class BuddySystem {
    /**
     * 申请释放锁
     */
    private Lock lock = new ReentrantLock();
    private LinkedList<MemoryBlock> mmBlockList = new LinkedList<>();
    /**
     * 可用空闲区全部大小
     */
    private final int size;
    /**
     * 空闲区可用大小
     */
    private AtomicInteger idleSize = new AtomicInteger(0);

    /**
     * 内存块数量
     */
    private AtomicInteger blockSize = new AtomicInteger(0);

    /**
     * 是否初始化完成
     */
    private volatile boolean isInitialized = false;

    public BuddySystem(int size) {
        this.size = size;
        this.idleSize.set(size);
    }

    /**
     * 初始化伙伴系统内存链表
     */
    public void initialize() {
        if (isInitialized) {
            return;
        }
        MemoryBlock memoryBlock = new MemoryBlock();
        memoryBlock.setSize(size);
        memoryBlock.setStart(0);
        memoryBlock.setEnd(size - 1);
        mmBlockList.add(memoryBlock);
        blockSize.incrementAndGet();
        isInitialized = true;
    }

    /**
     * 分配内存
     * @param expectSize 待分配的内存大小
     */
    public MemoryBlock alloc(int expectSize) {
        // 参数检查
        if (expectSize > size) {
            throw new IllegalArgumentException("Sorry, I don't have enough memory.");
        }
        
        MemoryBlock best = null;
        
        // 开始查找最适合的块
        if (lock.tryLock()) {
            try {
                // 查看当前空闲块链表,找到小且大于等于申请大小的空闲块
                MemoryBlock smallestFit = findSmallestFitBlock(expectSize);
                if (smallestFit == null) {
                    throw new InternalError("not enough memory");
                }
                // 检查是否满足2^u-1 < expectSize <= 2^u
                // 满足则直接分配
                // 不满足则拆分为两个大于或等于S的小块,然后检查是否满足2^u-1 < size <= 2^u
                if (smallestFit.getSize() != expectSize) {
                    // 检查并等分内存区
                    while (expectSize * 2 <= smallestFit.getSize()) {
                        // 拆分
                        int smallBlockSize = smallestFit.getSize() / 2;
                        int start = smallestFit.getStart();
                        int middle = smallestFit.getStart() + smallBlockSize;
                        int end = smallestFit.getEnd();
                        MemoryBlock left = new MemoryBlock(start, middle, smallBlockSize, false);
                        MemoryBlock right = new MemoryBlock(middle, end, smallBlockSize, false);
                        // 在删除点添加这两块内存
                        mmBlockList.replace(smallestFit, left, right);
                        blockSize.incrementAndGet();
                        smallestFit = left;
                    }
                }

                best = smallestFit;
                best.setUsed(true);
                idleSize.addAndGet(-best.getSize());
            } finally {
                lock.unlock();
            }
        }

        return best;
    }

    private MemoryBlock findSmallestFitBlock(int expectSize) {
        MemoryBlock smallestFit = null;
        for (MemoryBlock memoryBlock : mmBlockList) {
            if (!memoryBlock.isUsed() &&
                    memoryBlock.getSize() >= expectSize) {
                if (smallestFit == null) {
                    smallestFit = memoryBlock;
                } else {
                    if (smallestFit.getSize() > memoryBlock.getSize()) {
                        smallestFit = memoryBlock;
                    }
                }
            }
        }
        return smallestFit;
    }

    public void free(MemoryBlock freeBlock) {
        List<LinkedList.Node<MemoryBlock>> mergeNodes = new ArrayList<>(3);
        // 释放内存需要检查四种相邻场景
        // 如果有相邻,则合并
        if (lock.tryLock()) {
            try {
                freeBlock.setUsed(false);

                LinkedList.Node<MemoryBlock> toFreeNode = mmBlockList.findNode(freeBlock);
                if (toFreeNode == null) {
                    throw new IllegalArgumentException("You accessed memory illegally.");
                }

                // 检查前一个节点
                // 检查查找到的块是否大小相等且地址连续
                LinkedList.Node<MemoryBlock> prev = toFreeNode.prev;
                LinkedList.Node<MemoryBlock> next = toFreeNode.next;
                if (prev != null && !prev.item.isUsed()
                        && prev.item.getSize() == toFreeNode.item.getSize()
                        && prev.item.getEnd() == toFreeNode.item.getStart()) {
                    mergeNodes.add(prev);
                    blockSize.incrementAndGet();
                }

                mergeNodes.add(toFreeNode);

                // 检查下一个节点
                // 检查查找到的块是否大小相等且地址连续
                if (next != null && !next.item.isUsed()
                        && next.item.getSize() == toFreeNode.item.getSize()
                        && next.item.getStart() == toFreeNode.item.getEnd()) {
                    mergeNodes.add(next);
                }

                int start = mergeNodes.get(0).item.getStart();
                int end = mergeNodes.get(mergeNodes.size() - 1).item.getEnd();
                int itemSize = 0;

                for (LinkedList.Node<MemoryBlock> node : mergeNodes) {
                    itemSize += node.item.getSize();
                    blockSize.decrementAndGet();
                }


                // 删除当前节点和下一个节点,然后更新第一个节点大小和连接
                mmBlockList.remove(prev);
                mmBlockList.remove(next);
                toFreeNode.item.setStart(start);
                toFreeNode.item.setEnd(end);
                toFreeNode.item.setSize(itemSize);
            } finally {
                lock.unlock();
            }
        }
    }

    public void printBlocks() {
        int index = 1;
        for (MemoryBlock memoryBlock : mmBlockList) {
            StdOut.println("index: " + index + " " + memoryBlock);
            index++;
        }
    }

    public int getSize() {
        return size;
    }

    public int getIdleSize() {
        return idleSize.get();
    }

    public int getBlockSize() {
        return blockSize.get();
    }
}
AI 代码解读

测试用例

public class BuddySystemTest {

    private BuddySystem buddySystem;
    private static final int MAX_MEM_SIZE = 1024 * 1024 * 1024;

    @Before
    public void before() {
        buddySystem = new BuddySystem(MAX_MEM_SIZE);
    }

    @Test
    public void testInitialize() {
        buddySystem.initialize();
        Assert.assertEquals(MAX_MEM_SIZE, buddySystem.getSize());
        Assert.assertEquals(0, buddySystem.getIdleSize());
    }

    @Test
    public void testAllocAndFree() {
        buddySystem.initialize();

        // 分配100KB
        int size = 100 * 1024 * 1024;
        MemoryBlock block = buddySystem.alloc(size);
        Assert.assertNotNull(block);
        Assert.assertEquals(MAX_MEM_SIZE - block.getSize(), buddySystem.getIdleSize());
        Assert.assertEquals(buddySystem.getBlockSize(), 4);
        buddySystem.printBlocks();
        System.out.println("=================================");
        System.out.println("=================================");

        // 分配240KB
        size = 240 * 1024 * 1024;
        MemoryBlock block2 = buddySystem.alloc(size);
        Assert.assertNotNull(block2);
        Assert.assertEquals(MAX_MEM_SIZE - block.getSize() - block2.getSize(), buddySystem.getIdleSize());
        Assert.assertEquals(buddySystem.getBlockSize(), 4);
        buddySystem.printBlocks();
        System.out.println("=================================");
        System.out.println("=================================");

        // 分配64KB
        size = 64 * 1024 * 1024;
        MemoryBlock block3 = buddySystem.alloc(size);
        Assert.assertNotNull(block3);
        Assert.assertEquals(MAX_MEM_SIZE - block.getSize() - block2.getSize() - block3.getSize(), buddySystem.getIdleSize());
        Assert.assertEquals(buddySystem.getBlockSize(), 5);
        buddySystem.printBlocks();
        System.out.println("=================================");
        System.out.println("=================================");

        // 分配256KB
        size = 256 * 1024 * 1024;
        MemoryBlock block4 = buddySystem.alloc(size);
        Assert.assertNotNull(block3);
        Assert.assertEquals(MAX_MEM_SIZE - block.getSize() - block2.getSize()
                - block3.getSize() - block4.getSize(), buddySystem.getIdleSize());
        Assert.assertEquals(buddySystem.getBlockSize(), 6);
        buddySystem.printBlocks();
        System.out.println("=================================");
        System.out.println("=================================");

        // 释放240KB
        buddySystem.free(block2);
        Assert.assertEquals(buddySystem.getBlockSize(), 5);
    }
}
AI 代码解读

参考

  1. 操作系统原理 陈向群
老冀
+关注
目录
打赏
0
0
0
0
5
分享
相关文章
基于Java+Springboot+Vue开发的鲜花商城管理系统源码+运行
基于Java+Springboot+Vue开发的鲜花商城管理系统(前后端分离),这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Java编程技能,同时锻炼他们的项目设计与开发能力。通过学习基于Java的鲜花商城管理系统项目,大学生可以在实践中学习和提升自己的能力,为以后的职业发展打下坚实基础。技术学习共同进步
100 7
java家政系统实现智能派单?
本项目旨在构建一个基于JAVA的家政系统,通过实时派单满足用户即时需求。系统涵盖用户需求收集、服务人员数据库管理、智能匹配算法(如综合评分、机器学习模型)、实时通信通知、订单状态跟踪及动态调整等功能。同时,优化用户体验,强化安全与隐私保护,并采用微服务架构确保高并发稳定性。通过持续数据分析与算法迭代,实现高效精准的智能派单,提升服务质量和客户满意度。
家政系统源码,java版本
这是一款基于SpringBoot后端框架、MySQL数据库及Uniapp移动端开发的家政预约上门服务系统。
家政系统源码,java版本
在Linux系统中安装JDK、Tomcat、MySQL以及部署J2EE后端接口
校验时,浏览器输入:http://[your_server_IP]:8080/myapp。如果你看到你的应用的欢迎页面,恭喜你,一切都已就绪。
80 17
Java基于SaaS模式多租户ERP系统源码
ERP,全称 Enterprise Resource Planning 即企业资源计划。是一种集成化的管理软件系统,它通过信息技术手段,将企业的各个业务流程和资源管理进行整合,以提高企业的运营效率和管理水平,它是一种先进的企业管理理念和信息化管理系统。 适用于小微企业的 SaaS模式多租户ERP管理系统, 采用最新的技术栈开发, 让企业简单上云。专注于小微企业的应用需求,如企业基本的进销存、询价,报价, 采购、销售、MRP生产制造、品质管理、仓库库存管理、财务应收付款, OA办公单据、CRM等。
96 23
酷阿鲸森林农场:Java 区块链系统中的 P2P 区块同步与节点自动加入机制
本文介绍了基于 Java 的去中心化区块链电商系统设计与实现,重点探讨了 P2P 网络在酷阿鲸森林农场项目中的应用。通过节点自动发现、区块广播同步及链校验功能,系统实现了无需中心服务器的点对点网络架构。文章详细解析了核心代码逻辑,包括 P2P 服务端监听、客户端广播新区块及节点列表自动获取等环节,并提出了消息签名验证、WebSocket 替代 Socket 等优化方向。该系统不仅适用于农业电商,还可扩展至教育、物流等领域,构建可信数据链条。
Linux系统中的cd命令:目录切换技巧
踏过千山,越过万水,人生就是一场不断前行的旅程,总充满了未知与挑战。然而,“cd”命令如同你的旅伴,会带你穿梭在如棋盘一般的文件系统中,探索每一处未知。希望你能从“cd”命令中找到乐趣,像是掌控了一种络新妙的魔法,去向未知进发,开始你的探索之旅。
125 24
|
1月前
|
Linux系统下快速批量创建和删除文件的方法
总的来说,使用shell脚本来批量处理文件是一种非常强大的工具,只要你愿意花时间学习和实践,你会发现它能大大提高你的工作效率。
87 19
Linux系统之su命令的基本使用
Linux系统之su命令的基本使用
109 3
Linux系统之su命令的基本使用
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等