当前课程知识点：操作系统 > 第五讲 物理内存管理: 连续内存分配 > 5.5 伙伴系统 > 5.5 伙伴系统
好 接下来我们讲一个
连续内存分配的实例 伙伴系统
伙伴系统实际上是一种
我们刚才说的
连续存储分配一种办法
它在这里比较好地折中了
分配和回收过程当中
这种合并和分配块的位置 碎片的问题
具体怎么做的呢
我们在这会分成两部分
一个是对它基本做法有个介绍
第二个是说在我们uCore实验系统里
它的伙伴系统是怎么实现的接口
伙伴系统实际上是
它是把整个你可以分配的分区的大小
约定为必须是2的幂
这样做之后 任何一块要分的时候
只是把它从中间切开
它不会以其它方式来切
只是两个小块合在一起
变成一个更大的
在这里头如果说你在分配的时候
你需要一块它的大小
实际上可用的块
如果它的大小比你需要大小的2倍还大的话
我就把它切一半
然后再跟你来做比较
如果说在这里你比它1/2还大
但是没到当前大小的话
它就直接把这块给你
具体说起来就是
如果说它比你2倍还大
那我就把它切半
切半之后仍然比你2倍还大
那这个时候我在继续切半
一直切到某一个状态
那再切你就比它大了
而当前状态是比你的2倍小
这个时候我把这块就分给你
那这个时候我们形成内碎片
最大可能是多少
最大可能是你这个大小的1/2减1
也就是说你正好需要1/2的时候
我就可以把它分半
你再多一个字节
我有可能就给了你差不多一倍的大小
这是Buddy System它的基本道理
下面我们来看伴侣系统的实现
首先我们来看在伴侣系统当中
我们需要维护的数据结构
在这里头我们空闲块
维护的是一个二维数组
这个二维数组第一维
是空闲块的大小
由小到大我排成第一维
在相同大小这些空闲块里头
我按照它的地址排序排成第二维
这是我们这里的空闲块的二维数组
然后在起头的时候
整个系统里只有一块空闲块
这是整个空闲内存区域
在分配的时候是什么呢
分配的时候我是由小到大去找
比我需要大小更大的空闲块
如果说在初始状态下
我找到整个这是一块
这个时候我就会有第二步
找到之后我会看
如果这块过大
所谓过大是什么意思呢
就是我需要大小的二倍比你给出这块还小
我就把它切成一半
变成2的u-1次幂
然后再看 这个大小跟我需要块的大小
是不是还比它大
是不是比它2倍大
如果比它2倍还大我就继续分
分完之后变成两个空闲块
把它放到空闲块列表里去
二维数组里头
然后这个时候一直到找到
我需要大小是空闲块1/2还大
但是又没它本身大的时候
这个时候我就把这块分给它
这是分配的过程
然后在这 我们通过一组
实际的例子来看分配流程
假定我最开始的时候
它的大小是的1M
然后在这里头我们需要是100K
100K的话1M切成一半512
256 128 切到128的时候
能够满足我的要求
这个时候切完之后的情况
切成一半 再切一半 然后再切一半
128 然后这个时候它的大小
比我需要100K要大
但是比我需要的100K的2倍200K要小
OK那我就把这块分配给它
第二个分配请求是240K
240K那我们从这里看
比它大256K 256K是比它大
但是比它2倍要小
这个我们应该要分配到这
分配下来的结果是这样的
给它分配256K的空间
第三个是给它分配64K
64K我们看比128小
那128的1/2是64正合适
那这个时候我把它分了
把128K分成两半 搁在那里去了
再下一个是说我需要256
那256我们在这里空闲的只有512比它大
切成1/2
这是分配之后的结果
然后再往下我们是释放B
释放完了之后
按照我们原来连续分区的分配
我有一个合并的问题
我们说这块回来之后
它没有办法跟64K合并
因为合完之后的大小
不是我们前面说正好是2倍
也没办法放回到空闲分区的数组里去
这个时候我就变成两个空闲分区
然后我再释放A那128K还回去
它也没有办法跟别人合并
它是单独一个
然后这个时候我申请一个75K
75K仍然可以放到那儿
这个时候换成75K 给了它128K
这个时候我再看
这个时候把C释放掉
这个C释放掉的时候
这个地方一个64
和旁边64它两合起来的时候
正好是原来128
可以把它合在一起
这个时候就变成128了
128和这个能合吗
不能合它不能构成2的幂
即使的能构成2的幂 它也还会有问题
然后这个时候我再释放E
把这几个最后它们三个就会合在一起
最后再还回D 整个过程结束
那么这个时候它把整个合在一起
在这个过程当中
我们已经看到了它分配的时候情况
我找一个比它大的 最小的空闲块
然后看看是不是比它2倍大
如果是 切半
如果不是 OK就是它
这样我们分配的过程就有了
接下来我们把刚才说的
合并的事再明确一下
合并的时候我放到空闲块里头
比如说我在这里分配任何一块
合并的时候需要满足条件
那满足条件是什么样呢
大家看看 我在这里头
如果这块还回去
它可以和哪块合并
和这块能合吗 大小不一样
这是大小一样的 到底它和那块合
我们在这里 第一个条件
就是相邻的两块必须大小是一样的
然后第二个 它必须是相邻的
如果说你隔的话
它是合不到一起的
在这我们也没有移
还有条件吗
还有就是比如这三块
如果这块和这块合那是不行的
原因在于它俩的起始位置搁完之后
这同属于上面两个分支
这种直观意思表达
实际上形式化表达出来就是
相邻的两块 低的地址
必须是2的整数次幂
如果像这个地方
它没办法是它的整数次幂了
这个时候我们第三个条件就是
低地址的空闲块起始地址
必须是块大小的2倍的整数倍
有了这个之后
那我们的伴侣系统就可以
在实际系统当中来进行使用了
目前在我们用到的Linux Unix
都有Buddy System的实现
它是用来做内核里的存储分配
如果有同学想继续去了解它的实现
在这有一些参考信息
网上也有很详细一些实现
大家可以去参考
接下来我们说
在我们用到uCore系统里头
我的内存分配到底怎么做
这个地方 把物理内存的管理
提供了一个标准接口
在这个接口里 实现了一组函数
和相应的一些保存的信息
第一个是管理算法的名字
给了一个字符串做标识
然后有一个初始化
然后有一个检查
这个基本上是辅助性的函数
上来初始化的时候
是我数据结构的起头
检查是我在这个地方
我函数写完了之后是不是好使
我的一些测试就放在这个里头
中间我们关心主要的函数是这两个
是分配和回收
当然在分配和回收分给一个进程之后
我们在用的时候
还得把它映射到进程的地址空间里
所以会有上边这一个函数
和底下这个函数
底下这个函数是告诉你
这个空闲分区里还有多大空间
我们在这里要实现的时候
实际上你就实现这两个函数就行了
在我们uCore已经有Buddy System
实现伴侣系统
在这里实际上我们最后
就把你函数写好之后
只需要往这里一填
把你函数名字填进去
内核里的上层服务就可以
用它来分配自己所需要存储空间了
这个地方我们要填的
从分配和回收的角度来讲
主要填的是这两个函数
具体的内容大家可以下去看代码
好 到这个地方为止
我们就说清楚了
连续存储分配里头 它如何在做
在这里要面临一些什么问题
我们目前有一些什么样的解决方式
这些解决方式都是从什么角度来考虑的
今天的课就上到这里 下课
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
