5.3 连续内存分配慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

接下来我们介绍连续内存分配

我们说在分配内存空间的时候

我们首先第一个

在没有其它的技术支持的情况下

分配给一个进程的地址空间必须是连续的

为了提高利用效率

那我希望分的位置有适度的选择

这些动态分配算法

实际上就是你在去选择的做法

而选择完之后

你用每一个进程可能用的时间长短不一样

有的进程先结束

有的进程后结束

这个时候有可能先结束的会留出一些空

后面一个在分配的时候又会再去找

这个过程的执行

就会在中间留下一些碎片

这些碎片对于我们后续的分配是会有影响的

我们就从如何去找你要用的空闲分区

和如何来处理不能利用的这些

小的空闲分区的两个角度来看

连续内存分配算法

连续内存分配是指给进程分配一块

不小于指定大小的

物理连续的一块内存区域

这个地方是一个图示

说我进程不断的分配回收

分配了三个进程二就释放掉了

这个时候是我内存分配时候的状态

每一个进程的地址空间里头

我们可能存放的是代码数据

堆栈这些内容

那在这些中间

我们就会有一些区域没办法利用了

比如说像这里头

这有一块这有一小块

中间如果你要分配四块的话

这小块也没法用了

对于这些没法利用的区域

我们就称之为是碎片

这些碎片它是没办法利用的

这个没办法利用是相对而言的

如果说你要得小块

其中这块还是可以利用的

但是有一些你是无论如何用不起来的

这些碎片我们把它分成两种情况

一个是叫外碎片

外碎片是两块之间的这一块

实际上它也是一个小的空闲块

只是由于它过小

而其它进程申请的区域的大小都大于它

而导致这块没法利用

另一种情况是内碎片

内碎片是分配给进程的区域内部的

一些没法利用的区域

什么情况下会出现这种（情况）呢

如果说我分配的时候

并不是说我可以准确地分配你所指定的大小

比如说你想分配510字节

但是实际上我们在分配的时候

只能是以512字节这种

2的整数幂为单位的大小

那剩下的几个字节你就没办法利用了

像这些我们称之为叫内碎片

对于我这来讲

P1和P3上边剩的这段就是这种情况

那是由于它要取整所导致的

那我们在分配的时候

希望尽可能减少这种碎片的出现

从而使得我在利用的时候

比如说这种情况

我想分配一个六块的

那么这两个在这里头是没办法利用的

如果它两个是在一起的

这个事就是行的

我们来看动态分区分配

动态分区分配实际上是说

我在分配的时候

我可以指定大小

并且这个大小是用户指定的时候可变的

那我们分配出来结果

称之为叫一个分区

也可能叫内存块也可能叫块

分配出来的地址是连续的

对于这边是一个例子

第一个进程分配

第二个进程接着来

刚开始的时候我可以顺序地分配

这事比较容易

在用的过程当中

某些进程就会结束

那结束掉就还回来了

对于这种情况

现在我要想再分配的话

我就必须知道我哪些内存区域

已经分配给了进程

哪些内存区域还是空闲的

实际上在这时候

我们操作系统就要

维护这样两个数据结构

一个是已分配的分区

我们就需要知道

哪些是已经分配出去的

它分配给了谁

第二个是空闲分区

我需要知道空闲分区的位置和大小

对于我不同的找法

这两个数据结构的组织形式

是会有一些变化的

在不同组织形式下

你在找分区或者说把分区释放的时候

放回到分区列表里的时候

它的开销是会不一样的

这是我们在这需要考虑的问题

对于找分区的不同

我们在这就有这样几种

动态分区的分配策略

大家通常想要是说我要分配一块区域

我给你指定大小

这个个时候你去分你去找

你可能会碰到一个我就找一个

这就是我们这里的第一种情况最先匹配

你找着哪一个

碰到哪一个就是那个

我也可以是说我找最佳的

叫最佳匹配

它是什么意思

我把所有这些空闲的我全看一遍

看看这里头哪一个是比我大

但是又是大的最少那个

如果说你是这些空闲分区

你是按地址顺序排的

那你就把整个全部找一遍

如果说我在这里

是按照它的大小排的

那我就是从小往上找

找到第一个就行了

这是你空闲分区排序办法的不同

我找的时候开销是不一样的

还一种是最差匹配

我去找

每次用的时候我用的是最大的

用最大就相当于实际上我是按照由大到小排序

我的第一个肯定就是它了

这是几种基本分区的分配策略

下面我们具体来看

第一种最先匹配策略

在这里它的思路很简单

你要分配多少字节

我就从空闲分区列表里

去找第一个可以找着比它大的

比如说在这里头我是按照地址顺序排的

这个时候我在这我去找

我这个黄颜色是我空闲的

我这给了一个例子

说我想找一个400字节的

我上来看这个地方是1K

OK 它就是比我想要的大

那就是它了

分配完了之后变成什么呢

分配完了之后

一块被你申请的进程所占用

我把它放到已分配分区的列表去

并且注明它是哪一个进程占用的

然后这个时候还剩一点

剩一点我又把它描述成另外一个

小个的空闲分区

接着把它放到空闲分区列表里头去

在这里头如果按照地址排的话

那我就是在哪

这个思路就是这样的

那我们再看你在这里做的时候

它实现办法是什么

我的空闲分区是按照地址顺序排的

然后分配的时候怎么做

分配的时候从前往后找

找第一个所谓的合适

就是大于我指定的大小就可以了

释放的时候我在还回来的时候我放回去

按照地址把它插到里面去了

并且看它前后是否有临近的空闲分区

这个时候我把它合并到一起

这个时候找和合并的开销都是比较小的

但是它在这里头

因为我们每一次都是从头找

这样的话你都在前面能找到的时候

它就不会往后找

所以这样一来

它的另外一个好处是

在高地址的区域里头

它会留下一些比较大块的分区

你在后续要申请大块的时候

我是能找着的

如果我大块都切成了小块

那这你就找不着了

这是它的优点

它的缺点是说我会有外碎片

我每一次切的时候

如果大小不合适我都会切成俩

这个时候就会留下一个小的空闲分区

如果这个小个空闲分区多到一定程度

这时候你在后面往下分配大块的时候

它就得从前往后找

也就相当于前面很长一段你找不到

由于你找不到你就只能往后找

那这个时候往后找的这个过程

开销就会越来越大

也就相当于越往后

你在前面搜索的时间就会越长

这是第一种算法最先匹配

它的好处和缺点

那么第二种方法是最佳匹配

也就是说它找到一个比它大

并且是最小的空闲分区

如果说在这里头

像在这里这个例子

我们要想分配400个字节

那1K 2K 500字节

这三个比较起来

这个是比它大并且是大的最少的

那我们在这来分配

分配完的结果变成什么样子

我前两个不动

第三个把它切成两个

留下一个小的100字节的空闲分区

另外一个作为已分配的

对它做相应的标识

告诉它分配给了哪个进程

那这个事就算搞定了

我们看在这里头

我需要维护的数据结构是什么样子的

首先第一个

空闲分区我怎么来排序

因为我是找比它大最小的一个

我找的时候是从小往大找

所以我的空闲分区

如果是从小往大排序

我开始是比它小的

第一个比它大的

OK这就是我想要找的

如果前面比它小的数目比较少

我很快就能找着

分配的时候我是从前往后找

释放的时候

我就看跟它临近的进行合并

这个时候就有一个问题

临近的话我就是需要去找它地址临近的

并不是大小临近的

正是因为这样一来

按地址排序的你合并的时候

它的算法就会复杂一些

花的时间就会长一些

这种做法它的好处是我可以把较大的块

如果说我分配块的尺度

都是比较小的时候

这个时候它的效果是比较好的

如果说你分配大的

那这个时候它后边剩的就会少了

这个时候它会有什么好处呢

避免大的分区被拆分

因为你找的是比它大的最小的那个

然后它可以减少外碎片的尺寸

也就是说剩下那块

一定是我能找的这一块里

剩下的最小那块

然后相对来说它比较简单

缺点是说你剩的那块边角料是小了

但剩的越小这块边角料它越没法利用

所以它有外碎片

并且是释放分区的时候它会比较复杂

然后剩下那些小碎片基本上也就没用了

这是最佳匹配

然后还有一种做法我们是最差匹配

它的做法我找最大的

有可能是说我找最大

也不满足我的要求

这是找不到了

那这里头我们找了一个最大的

比如说在这里这个例子

我要分配400字节

那这个时候找哪个呢

最大的这是2K

我把它切成两块

在这里这块标记已分配

剩下这一块还有1K多比这块还大

它可以被利用的机会就会更多

这是最差匹配它所带来的好处

具体做法是

这个地方空闲分区排序要怎么排

这个时候由大到小排

我每次找的时候

只要第一个满足要求

那就是我要找的

第一个不满足要求我就没有了

这时候分配的时候就是找最大的一个

也是找第一个找的速度是最快的

然后释放的时候我要去找它临近的

由于我排序不是按地址排的

你找临近就需要去顺序找了

找着临近的然后把它合在一起

放回到空闲分区列表时候

我还要去找放的位置

因为你原来是按大小排序的

现在你仍然需要按照原来大小的去排

要不然下次找的时候就不对了

这个时候它有什么好处

如果说你的中等尺度的分配比较多

这个时候效果是比较好的

因为我用掉那块不是很大

然后剩的那块多的时候还能利用起来

相当于我剩的小块就比较少了

剩的那块我还可以找到用处

实际上这个时候关键是

剩的那块能给它找什么样的用处

它的缺点是释放的过程比较慢

因为释放之后的合并是要进行搜索的

它排序跟我这个合并没有关系

然后也会有外部碎片

如果说你在这头由于我每次都是最大的

你在后边你想分配大分区的时候

这事就变的比较困难了

这是我们在这里说到连续存储分配

它的几种做法

这几种做法主要出发点

就是我那个空闲分区的列表

它是按什么来排

然后我们需要去考虑的是

在分配的时候它的查找开销

和在释放的时候它合并的开销

和把这个合并完的结果

放回到空闲分区列表里的时候

找合适位置的开销

操作系统课程列表：

第零讲在线教学环境准备

-0.1 Piazza讨论区

--piazza访问和使用

--html

-0.2 在线实验平台

-0.2在线实验平台

第一讲操作系统概述

-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.2 系统启动流程

-3.3 中断、异常和系统调用比较

--3.3 中断、异常和系统调用比较

-第三讲启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较

-3.4 系统调用

--3.4 系统调用

-第三讲启动、中断、异常和系统调用--3.4 系统调用

-3.5 系统调用示例

--3.5 系统调用示例

-3.6 ucore+系统调用代码

--3.6 ucore+系统调用代码

第四讲实验一 bootloader启动ucore os

-4.1 启动顺序

-4.2 C函数调用的实现

-4.3 GCC内联汇编

-4.4 x86中断处理过程

-4.5 练习一

-4.6 练习二

-4.7 练习三

-4.8 练习四练习五

-4.9 练习六

第五讲物理内存管理: 连续内存分配

-5.1 计算机体系结构和内存层次

-5.2 地址空间和地址生成

-5.3 连续内存分配

-5.4 碎片整理

-5.5 伙伴系统

-第五讲物理内存管理: 连续内存分配--5.6 练习

第六讲物理内存管理: 非连续内存分配

-6.1 非连续内存分配的需求背景

-6.2 段式存储管理

-6.3 页式存储管理

-6.4 页表概述

-6.5 快表和多级页表

-6.6 反置页表

-6.7 段页式存储管理

-第六讲物理内存管理: 非连续内存分配--6.8 练习

第七讲实验二物理内存管理

-7.1 了解x86保护模式中的特权级

--7.1 了解x86保护模式中的特权级

-第七讲实验二物理内存管理--7.1 了解x86保护模式中的特权级

-7.2 了解特权级切换过程

--7.2 了解特权级切换过程

-第七讲实验二物理内存管理--7.2 了解特权级切换过程

-7.3 了解段/页表

--7.3 了解段/页表

-第七讲实验二物理内存管理--7.3 了解段/页表

-7.4 了解UCORE建立段/页表

--7.4 了解ucore建立段/页表

-第七讲实验二物理内存管理--7.4 了解UCORE建立段/页表

-7.5 演示lab2实验环节

--7.5 演示lab2实验环节

第八讲虚拟存储概念

-8.1 虚拟存储的需求背景

-8.2 覆盖和交换

-8.3 局部性原理

-8.4 虚拟存储概念

-8.5 虚拟页式存储

-8.6 缺页异常

第九讲页面置换算法

-9.1 页面置换算法的概念

--9.1 页面置换算法的概念

-9.2 最优算法、先进先出算法和最近最久未使用算法

--9.2 最优算法、先进先出算法和最近最久未使用算法

-第九讲页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法

-9.3 时钟置换算法和最不常用算法

--9.3 时钟置换算法和最不常用算法

-第九讲页面置换算法--9.3 时钟置换算法和最不常用算法

-9.4 Belady现象和局部置换算法比较

--9.4 Belady现象和局部置换算法比较

-第九讲页面置换算法--9.4 Belady现象和局部置换算法比较

-9.5 工作集置换算法

--9.5 工作集置换算法

-第九讲页面置换算法--9.5 工作集置换算法

-9.6 缺页率置换算法

--9.6 缺页率置换算法

-第九讲页面置换算法--9.6 缺页率置换算法

-9.7 抖动和负载控制

--9.7 抖动和负载控制

第十讲实验三虚拟内存管理

-10.1 实验目标：虚存管理

--10.1 实验目标：虚存管理

-第十讲实验三虚拟内存管理--10.1 实验目标：虚存管理

-10.2 回顾历史和了解当下

-- 10.2 回顾历史和了解当下

-第十讲实验三虚拟内存管理--10.2 回顾历史和了解当下

-10.3 处理流程、关键数据结构和功能

--10.3 处理流程、关键数据结构和功能

-第十讲实验三虚拟内存管理--10.3 处理流程、关键数据结构和功能

-10.4 页访问异常

--10.4 页访问异常

-第十讲实验三虚拟内存管理--10.4 页访问异常

-10.5 页换入换出机制

--10.5 页换入换出机制

-第十讲实验三虚拟内存管理--10.5 页换入换出机制

第十一讲进程和线程

-11.1 进程的概念

--11.1 进程的概念

-第十一讲进程和线程--11.1 进程的概念

-11.2 进程控制块

--11.2 进程控制块

-第十一讲进程和线程--11.2 进程控制块

-11.3 进程状态

--11.3 进程状态

-第十一讲进程和线程--11.3 进程状态

-11.4 三状态进程模型

--11.4 三状态进程模型

-11.5 挂起进程模型

--11.5 挂起进程模型

-第十一讲进程和线程--11.5 挂起进程模型

-11.6 线程的概念

--11.6 线程的概念

-第十一讲进程和线程--11.6 线程的概念

-11.7 用户线程

--11.7 用户线程

-第十一讲进程和线程--11.7 用户线程

-11.8 内核线程

--11.8 内核线程

-第十一讲进程和线程--11.8 内核线程

第十二讲进程控制

-12.1 进程切换

--12.1 进程切换

-第十二讲进程控制--12.1 进程切换

-12.2 进程创建

--12.2 进程创建

-第十二讲进程控制--12.2 进程创建

-12.3 进程加载

--12.3 进程加载

-第十二讲进程控制--12.3 进程加载

-12.4 进程等待与退出

--12.4 进程等待与退出

-第十二讲进程控制--12.4 进程等待与退出

第十三讲实验四内核线程管理

-13.1 总体介绍

-13.2 关键数据结构

-13.3 执行流程

-13.4 实际操作

第十四讲实验五用户进程管理

-14.1 总体介绍

--14.1 总体介绍

-14.2 进程的内存布局

--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.5 进程复制

-14.6 内存管理的copy-on-write机制

--14.6 内存管理的copy-on-write机制

第十五讲处理机调度

-15.1 处理机调度概念

--15.1 处理机调度概念

-第十五讲处理机调度--15.1 处理机调度概念

-15.2 调度准则

--15.2 调度准则

-15.3 先来先服务、短进程优先和最高响应比优先调度算法

--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-第十五讲处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

-第十五讲处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc

-15.5 实时调度和多处理器调度

--15.5 实时调度和多处理器调度

-第十五讲处理机调度--15.5 实时调度和多处理器调度

-15.6 优先级反置

--15.6 优先级反置

-第十五讲处理机调度--15.6 优先级反置

第十六讲实验六调度器

-16.1 总体介绍和调度过程

-16.2 调度算法支撑框架

-16.3 时间片轮转调度算法

-16.4 Stride调度算法

第十七讲同步互斥

-17.1 背景

--17.1 背景

-17.2 现实生活中的同步问题

--17.2 现实生活中的同步问题

-第十七讲同步互斥--17.2 现实生活中的同步问题

-17.3 临界区和禁用硬件中断同步方法

--17.3 临界区和禁用硬件中断同步方法

-第十七讲同步互斥--17.3 临界区和禁用硬件中断同步方法

-17.4 基于软件的同步方法

--17.4 基于软件的同步方法

-第十七讲同步互斥--17.4 基于软件的同步方法

-17.5 高级抽象的同步方法

--17.5 高级抽象的同步方法

-第十七讲同步互斥--17.5 高级抽象的同步方法

第十八讲信号量与管程

-18.1 信号量

--18.1 信号量

-第十八讲信号量与管程--18.1 信号量

-18.2 信号量使用

--18.2 信号量使用

-第十八讲信号量与管程--18.2 信号量使用

-18.3 管程

--18.3 管程

-第十八讲信号量与管程--18.3 管程

-18.4 哲学家就餐问题

--18.4 哲学家就餐问题

-18.5 读者-写者问题

--18.5 读者-写者问题

第十九讲实验七同步互斥

-19.1 总体介绍

--19.1 总体介绍

-19.2 底层支撑

--19.2 底层支撑

-第十九讲实验七同步互斥--19.2 底层支撑

-19.3 信号量设计实现

--19.3 信号量设计实现

-第十九讲实验七同步互斥--19.3 信号量设计实现

-19.4 管程和条件变量设计实现

--19.4 管程和条件变量设计实现

-第十九讲实验七同步互斥--19.4 管程和条件变量设计实现

-19.5 哲学家就餐问题

--19.5 哲学家就餐问题

第二十讲死锁和进程通信

-20.1 死锁概念

--20.1 死锁概念

-第二十讲死锁和进程通信--20.1 死锁概念

-20.2 死锁处理方法

--20.2 死锁处理方法

-第二十讲死锁和进程通信--20.2 死锁处理方法

-20.3 银行家算法

--20.3 银行家算法

-第二十讲死锁和进程通信--20.3 银行家算法

-20.4 死锁检测

--20.4 死锁检测

-第二十讲死锁和进程通信--20.4 死锁检测

-20.5 进程通信概念

--20.5 进程通信概念

-第二十讲死锁和进程通信--20.5 进程通信概念

-20.6 信号和管道

--20.6 信号和管道

-第二十讲死锁和进程通信--20.6 信号和管道

-20.7 消息队列和共享内存

--20.7 消息队列和共享内存

-第二十讲死锁和进程通信--20.7 消息队列和共享内存

第二十一讲文件系统

-21.1 文件系统和文件

--21.1 文件系统和文件

-第二十一讲文件系统--21.1 文件系统和文件

-21.2 文件描述符

--21.2 文件描述符

-第二十一讲文件系统--21.2 文件描述符

-21.3 目录、文件别名和文件系统种类

--21.3 目录、文件别名和文件系统种类

-第二十一讲文件系统--21.3 目录、文件别名和文件系统种类

-21.4 虚拟文件系统

--21.4 虚拟文件系统

-第二十一讲文件系统--21.4 虚拟文件系统

-21.5 文件缓存和打开文件

--21.5 文件缓存和打开文件

-第二十一讲文件系统--21.5 文件缓存和打开文件

-21.6 文件分配

--21.6 文件分配

-第二十一讲文件系统--21.6 文件分配

-21.7 空闲空间管理和冗余磁盘阵列RAID

--21.7 空闲空间管理和冗余磁盘阵列RAID

-第二十一讲文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID

第二十二讲实验八文件系统

-22.1 总体介绍

--22.1 总体介绍

-第二十二讲实验八文件系统--22.1 总体介绍

-22.2 ucore 文件系统架构

--22.2 ucore 文件系统架构

-第二十二讲实验八文件系统--22.2 ucore 文件系统架构

-22.3 Simple File System分析

--22.3 Simple File System分析

-第二十二讲实验八文件系统--22.3 Simple File System分析

-22.4 Virtual File System分析

--22.4 Virtual File System分析

-第二十二讲实验八文件系统--22.4 Virtual File System分

-22.5 I/O设备接口分析

--22.5 I/O设备接口分析

-第二十二讲实验八文件系统--22.5 I/O设备接口分析

-22.6 执行流程分析

--22.6 执行流程分析

第二十三讲 I/O子系统

-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

--html

5.3 连续内存分配在线视频