动态内存分配算法

嵌入式动态内存分配算法tlsf
2019-09-09 15:58:28
TLSF是一种动态内存分配算法，本资源是C语言的编写的，包含例程。
收起
动态内存分配算法实验报告.doc
2020-11-04 20:30:39
动态内存分配算法实验报告院系:计算机与通信工程学院班级:计科08-1班姓名:胡太祥学号:200807010112 一实验题目动态内存分配算法 二实验目的深入了解动态分区存储管理方式内存分配与回收的实现三...
收起

动态内存分配算法

千次阅读 2013-05-07 15:05:58

在实际的环境中，可能会遇到需要反复申请...下面的算法，可以减少无用功，仅在需要更大的内存时，重新申请一次 void getBuffer(char** ppBuf, int uSize) { if (*ppBuf) { if (_msize(*ppBuf) ) { dele

在实际的环境中，可能会遇到需要反复申请释放内存空间的情况，而每次申请的内存空间大小又不确定，如果每次都申请，效率肯定会比较低
下面的算法，可以减少无用功，仅在需要更大的内存时，重新申请一次


void getBuffer(char** ppBuf, int uSize)
{
	if (*ppBuf)
	{
		if (_msize(*ppBuf) < uSize)
		{
			delete[] *ppBuf;
			*ppBuf = NULL;
			*ppBuf = new char[uSize];
		}
	}
	else
	{
		*ppBuf = new char[uSize];
	}
}

收起

展开全文

TLSF动态内存分配算法的研究与应用
2020-07-25 02:26:42
详细介绍了TLSF（Two Level Segregated Fit）动态内存分配算法的实现过程，包括内存池的创建初始化、动态内存的分配与释放。把TLSF移植到μC/OSII实时操作系统上，移植后的系统在基于CortexM3内核的LPC1768处理器上...
收起
动态内存分配算法实验报告
2011-06-23 10:01:14
动态内存分配算法实验报告包括：实验题目，实验目的，实验要求，实验内容，实验结果，实验总结及后附有详细源代码实验内容 1，确定定内存空闲分配表和进程内存分配表 2，采用首次适应算法完成内存空间的分配 3，...
收起
基于μCOS-II的TLSF动态内存分配算法的应用与仿真
2020-10-17 23:05:30
以嵌入式实时系统为背景，深入研究了TLSF动态内存分配算法原理及实现过程，并将TLSF移植到μCOS-II中，进行了基于x86平台的仿真测试，取得了很好的效果，为以后学习和应用TLSF算法提供了一种新的方式。
收起
嵌入式操作系统
操作系统课程设计动态内存分配算法
2009-10-07 14:29:41
操作课程设计，动态内存分配算法实现。包括可视化演示，可单步操作和自动执行。
收起
动态内存分配算法（源代码&报告）DynamicAllocate
2009-12-27 19:30:34
DynamicAllocate.rar 动态内存分配算法（源代码&报告）
收起

java动态分区分配算法_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF

2021-03-04 07:05:48

1 概述本文是利用Java实现操作系统中的四种动态内存分配方式，分别是：BFNFWFFF分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。2 四种分配方式2.1 概念操作系统中有一个动态...

1 概述
本文是利用Java实现操作系统中的四种动态内存分配方式 ，分别是：
BF
NF
WF
FF
分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。
2 四种分配方式
2.1 概念
操作系统中有一个动态分区分配的概念，内存在初始化的时候不会划分区域，而是在进程装入的时候，根据所要装入的进程动态地对内存空间进行划分，以提高内存空间的利用率，降低碎片的大小，主要的方法有一下四种：
首次适应算法(First Fit)：从空闲分区链首开始查找，直到找到一个满足其大小要求的空闲分区为止
循环首次适应算法(Next Fit)：从上次找到的空闲分区的下一个开始查找
最佳适应算法(Best Fit)：把空闲分区按大小递增的方式形成分区链，找到第一个能满足要求的空闲分区就进行分配
最坏适应算法(Worst Fit)：与最佳适应算法相反，把空闲分区按大小递减的方式形成分区链，找到第一个能满足要求的空闲分区就进行分配
2.2 例子
假设现在有100MB的内存空间，某一时刻先后分配了20MB、4MB、10MB内存，示意图如下：
现在需要再分配5MB内存。
若采用FF，因为FF是直接按顺序分配内存，从低地址开始搜索空闲分区，因此便会从第一块空闲分区分配5MB(地址0-5)，示意图：
若采用NF，NF与FF类似，只不过NF是从上一次找到的空闲分区的下一块开始查找，因为上一次分配的是10MB，因此会从最后一块空闲分区(地址80-100)分配内存：
若采用BF，BF是遍历所有空闲分区并找到一个能满足要求的最小分区，也就会找到一个比5MB大的空闲分区，且该空闲分区是所有空闲分区中最小的，也就是地址为64-70的空闲分区：
若采用WF，WF与BF相反，总是从最大的空闲分区开始分配，因此会从地址为30-60的空闲分区进行分配：
3 代码实现
3.1 总览
代码分成了四个类：
Main：测试
Print：输出打印
Table：表示每一个分区
TableList：对分区进行控制，包括初始化，分配，回收等
3.2 Main
Main是测试类，代码如下：
public class Main {
private final static TableList list = new TableList(64);
public static void main(String[] args) {
list.useWF();
//        list.useBF();
//        list.useNF();
//        list.useFF();
list.allocate(10);
list.allocate(20);
list.free(10);
list.show();
list.allocate(8);
list.show();
list.allocate(13);
list.allocate(1);
list.show();
list.free(1);
list.allocate(9);
list.free(13);
list.show();
list.allocate(18);
list.show();
list.allocate(3);
list.allocate(4);
list.free(20);
list.free(8);
list.show();
list.allocate(8);
list.free(9);
list.show();
list.clear();
list.show();
}
}
通过TableList对内存进行分配以及释放，初始化分配64MB大小内存，切换分配算法时使用前四行的其中一行即可。
3.3 Table
Table类表示每一个分区，无论是空闲的还是已分配的，成员变量有四个，分别是：
起始地址
大小
是否空闲(只有两种状态，空闲或分配)
是否是上一次分配(NF专用)
代码如下：
@AllArgsConstructor
public class Table {
@Getter
@Setter
private int address;
@Setter
@Getter
private int size;
private boolean free;
@Getter
@Setter
private boolean lastAllocated;
public static Table freeTable(int address,int size)
{
return new Table(address,size,true,false);
}
public static Table allocatedTable(int address,int size)
{
return new Table(address,size,false,false);
}
public boolean isFree()
{
return free;
}
public boolean isAllocated()
{
return !isFree();
}
public void setFree()
{
free = true;
}
}
只有一些Getter和Setter，为了方便提供了一个创建空闲分区或已分配分区的静态方法，指定起始地址和大小即可。
3.4 TableList
TableList是整个算法的核心类，成员变量如下：
private final List
private final int totalSize;
private boolean ff = false;
private boolean nf = false;
private boolean bf = false;
private boolean wf = false;
private boolean first = true;
private final static Print print = new Print();
list就是所有的空闲分区与已分配分区组成的数组，totalSize是总大小，接着是四个控制算法的布尔变量，first表示是否是第一次分配内存，因为第一次的话四种算法都是固定的从地址为0处开始分配。
接下来就是内存分配算法以及释放算法。
3.4.1 FF
if (ff)
{
for (int i = 0; i < list.size(); i++) {
Table table = list.get(i);
if(table.isFree() && table.getSize() >= size)
{
int address = table.getAddress();
Table allocated = Table.allocatedTable(address,size);
table.setAddress(address+size);
table.setSize(table.getSize()-size);
list.add(i,allocated);
return;
}
}
}
FF的实现还是比较简单的，直接遍历列表，如果是空闲分区并满足大小要求，直接进行分配，修改空闲分区的起始地址和大小并插入一个新的已分配分区到列表中即可。
3.4.2 NF
else if (nf)
{
int lastNFIndex = findLastAllocated();
int i = lastNFIndex;
do
{
if(i == list.size())
i = 0;
Table table = list.get(i);
if(table.isFree() && table.getSize() >= size)
{
int address = table.getAddress();
Table allocated = Table.allocatedTable(address,size);
table.setAddress(address+size);
table.setSize(table.getSize()-size);
list.get(lastNFIndex).setLastAllocated(false);
table.setLastAllocated(true);
list.add(i,allocated);
return;
}
++i;
}
while (i != lastNFIndex);
}
NF的话需要提前记录上一次分配的位置，通过Table中的lastAllocated确定上一次分配的位置，找到后从该位置开始遍历列表，注意需要进行绕回处理，因为到末尾位置后有可能还没有能满足的空闲分区，此时需要将下标绕回到0并再次遍历直到到达上一次分配的位置。
3.4.3 BF+WF
由于BF与WF都需要遍历所有的空闲分区，只是前者是选择最小满足要求的，后者是选择最大满足要求的，因此两者的实现差别在于一个判断大小的符号，代码如下：
else
{
int i;
int target = -1;
for (i = 0; i < list.size(); i++) {
Table table = list.get(i);
if(table.isFree())
{
if(table.getSize() >= size)
{
if(target == -1)
target = i;
else
{
if(bf)
{
if(list.get(target).getSize() > table.getSize())
target = i;
}
else
{
if(list.get(target).getSize() < table.getSize())
target = i;
}
}
}
}
}
if(target != -1)
{
Table table = list.get(target);
int address = table.getAddress();
table.setAddress(address+size);
table.setSize(table.getSize()-size);
list.add(target,Table.allocatedTable(address,size));
return;
}
}
首先遍历找到符合条件的空闲分区的下标，接着通过判断target，也就是目标空闲分区的下标，如果为-1表示没有找到符合条件的空闲分区，如果不为-1直接分配空间。
3.4.4 释放算法
释放算法的设计是比较复杂的，代码如下：
public void free(int size)
{
int index = 0;
while(index < list.size())
{
if(list.get(index).isAllocated() && list.get(index).getSize() == size)
break;
++index;
}
if(index >= list.size())
{
print.freeFailed(size);
return;
}
int address = list.get(index).getAddress();
if(index == 0)
{
list.get(0).setFree();
if(index+1 < list.size())
{
Table nextTable = list.get(index+1);
if(nextTable.isFree())
{
list.get(0).setSize(nextTable.getSize()+size);
list.remove(index+1);
}
}
}
else if(index == list.size()-1)
{
list.get(index).setFree();
Table lastTable = list.get(index-1);
if(lastTable.isFree())
{
lastTable.setSize(lastTable.getSize()+size);
list.remove(index);
}
}
else
{
Table before = list.get(index-1);
Table after = list.get(index+1);
if(before.isFree() && after.isFree())
{
before.setSize(before.getSize()+size+after.getSize());
list.remove(index+1);
list.remove(index);
}
else if(before.isFree() && after.isAllocated())
{
before.setSize(before.getSize()+size);
list.remove(index);
}
else if(before.isAllocated() && after.isFree())
{
after.setSize(after.getSize()+size);
after.setAddress(address);
list.remove(index);
}
else
{
list.get(index).setFree();
}
}
}
主要考虑了六种情况(黄色代表需要释放的空间，橙色是已分配的内存空间)：
第一种情况就是需要释放首部的分区，此时需要修改后面空闲分区的起始地址和大小，并删除目标分区
第二种情况是释放尾部的分区，此时需要修改前面空闲分区的大小即可，无需修改起始地址，并删除目标分区
第三种情况是后面是已分配的分区，前面的空闲分区，需要修改前面空闲分区的大小，并删除目标分区
第四种情况是前面是已分配的分区，后面是空闲分区，需要修改后面的空闲分区的起始地址以及大小，并删除目标分区
第五种情况是前后都是已分配的分区，此时只需要修改目标分区的标志为空闲即可，无需额外操作
第六种情况是前后都是空闲分区，这种情况下需要进行连接操作，具体来说就是先修改前面空闲分区的大小，接着删除目标分区以及后面的空闲分区
下面回到代码，首先是判断第一种情况：
if(index == 0)
{
list.get(0).setFree();
if(index+1 < list.size())
{
Table nextTable = list.get(index+1);
if(nextTable.isFree())
{
list.get(0).setSize(nextTable.getSize()+size);
list.remove(index+1);
}
}
}
也就是需要释放首部的分区，通过setFree()设置标志位表示空闲状态，接着判断是否需要修改后面空闲分区的大小，因为有可能后面是一个已分配的分区而不是空闲分区。
else if(index == list.size()-1)
{
list.get(index).setFree();
Table lastTable = list.get(index-1);
if(lastTable.isFree())
{
lastTable.setSize(lastTable.getSize()+size);
list.remove(index);
}
}
这里是判断第二种情况，也就是释放尾部的分区，同样需要判断前一个分区是已分配的分区还是空闲的分区，是空闲分区的话修改大小并移除目标分区。
else
{
Table before = list.get(index-1);
Table after = list.get(index+1);
if(before.isFree() && after.isFree())
{
before.setSize(before.getSize()+size+after.getSize());
list.remove(index+1);
list.remove(index);
}
else if(before.isFree() && after.isAllocated())
{
before.setSize(before.getSize()+size);
list.remove(index);
}
else if(before.isAllocated() && after.isFree())
{
after.setSize(after.getSize()+size);
after.setAddress(address);
list.remove(index);
}
else
{
list.get(index).setFree();
}
}
接下来是最后四种情况的判断，首先获取前一个以及后一个分区，接着按上面算法的思路进行判断即可。
4 测试
以WF为例，默认大小64MB，测试顺序如下：
分配10MB
分配20MB
释放10MB
打印结果
分配8MB
打印结果
分配13MB
分配1MB
打印结果
释放1MB
分配9MB
释放13MB
打印结果
分配18MB
打印结果
分配3MB
分配4MB
释放20MB
释放8MB
打印结果
分配8MB
释放9MB
打印结果
清空
打印结果
输出：
Free           :      0-10MB
Allocated      :      10-30MB
Free           :      30-64MB
----------------------------------------------------------------
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-64MB
----------------------------------------------------------------
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Allocated      :      38-51MB
Allocated      :      51-52MB
Free           :      52-64MB
----------------------------------------------------------------
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-51MB
Allocated      :      51-60MB
Free           :      60-64MB
----------------------------------------------------------------
Do nothing.
Allocated failed, out of memory
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-51MB
Allocated      :      51-60MB
Free           :      60-64MB
----------------------------------------------------------------
Allocated      :      0-4MB
Free           :      4-38MB
Allocated      :      38-41MB
Free           :      41-51MB
Allocated      :      51-60MB
Free           :      60-64MB
----------------------------------------------------------------
Allocated      :      0-4MB
Allocated      :      4-12MB
Free           :      12-38MB
Allocated      :      38-41MB
Free           :      41-64MB
----------------------------------------------------------------
Free           :      0-64MB
----------------------------------------------------------------
读者可以自行画图验证。
5 源码
如果觉得文章好看，欢迎点赞。
同时欢迎关注微信公众号：氷泠之路。

收起

展开全文

操作系统-动态内存分配算法

千次阅读 2017-12-02 14:46:55

内存分配算法 1、首次适应算法(FF) 2、循环首次适应算法(NF) 3、最佳适应算法(BF) 4、最坏适应算法(WF) 本程序使用前端技术实现（html+css+JavaScript）新建以下文件在同一目录:index.html、index.css、index....

内存分配算法 

1、首次适应算法(FF) 

2、循环首次适应算法(NF) 

3、最佳适应算法(BF) 

4、最坏适应算法(WF)



本程序使用前端技术实现（html+css+JavaScript）

新建以下文件在同一目录:index.html、index.css、index.js

index.css

 *{
    margin: 0;
    padding: 0;
}

li{
    list-style:none;
}

div{
    width: 24%;
}


#text{
    width:150px;
    height: 50px;
    font-size: +2em;    
}

.btn{
    height:50px;
    width:40px;
}

#Table{
    border: 2px;
    border-bottom:  2px solid black;
    border-collapse: collapse;

}



.busy{
    width:30px;
    background:#5BC0DE;
    /*#00BFFF;*/

}

.aa{
    margin:0 auto;
}


#container{
    width: 100%;
    height:100%;
}

#div1{
    /*background:#ffff00;*/
    display:inline-block;
    position:relative;
    top:100;
}
#div2{
    /*background:#ff0000;*/
    display:inline-block;
     position:relative;
     top:100;
}
#div3{
    /*background:#f00fff;*/
    display:inline-block;
     position:relative;
     top:100;
}
#div4{
    /*background:#0000ff;*/
    display:inline-block;
     position:relative;
     top:100;
}

h2
{
    text-align: center;
}
.heihei{
    margin:0 5px;
}
.haha{
    position:absolute;
    top:50;
    right:5px;
}

index.html



<html>
<title>动态内存分配</title>
<meta charset="UTF-8">
<script type="text/javascript" src="index.js"></script>
<link href="index.css" rel="stylesheet" type="text/css"/>
<body onload="onload()">

    <div class="aa">
    <input type="text" id="text">
    <input type="button" value="分配" class="btn" onclick="main();"/>
    <input type="button" value="回收" class='btn' onclick="recycle();"/>
    </div>
    <div id="container">

        <div id="div1">
            <h2>首次适应算法</h2>
            <div class="heihei"><ul id="ul00"><li></li></ul></div>
            <div class="haha"><ul id="ul01"><li></li></ul></div>
        </div> 

        <div id="div2">
            <h2>循环首次适应算法</h2>
            <div class="heihei"><ul id="ul11"><li></li></ul></div>
            <div class="haha"><ul id="ul12"><li></li></ul></div>
        </div> 


        <div id="div3">
            <h2>最佳适应算法</h2>
            <div class="heihei"><ul id="ul22"><li></li></ul></div>
            <div class="haha"><ul id="ul23"><li></li></ul></div>
        </div> 


        <div id="div4">
            <h2>最坏适应算法</h2>
            <div class="heihei"><ul id="ul33"><li></li></ul></div>
            <div class="haha"><ul id="ul34"><li></li></ul></div>
        </div> 



    </div>   
</body>
</html>




index.js



var size = 10;//size为最小不可再分阈值

var MAX = 1024;//内存大小为1024K
var flag = 0;//标记


// 三维
var freeTable = new Array();
freeTable[0] = new Array();
freeTable[0][0] = new Array(1,0,200,1);
freeTable[0][1] = new Array(2,200,10,0);
freeTable[0][2] = new Array(3,210,90,1);
freeTable[0][3] = new Array(4,300,100,1);
freeTable[0][4] = new Array(5,400,60,1);
freeTable[0][5] = new Array(6,460,770,0);


freeTable[1] = new Array();
freeTable[1][0] = new Array(1,0,200,1);
freeTable[1][1] = new Array(2,200,10,0);
freeTable[1][2] = new Array(3,210,90,1);
freeTable[1][3] = new Array(4,300,100,1);
freeTable[1][4] = new Array(5,400,60,1);
freeTable[1][5] = new Array(6,460,770,0);


freeTable[2] = new Array();
freeTable[2][0] = new Array(1,0,200,1);
freeTable[2][1] = new Array(2,200,10,0);
freeTable[2][2] = new Array(3,210,90,1);
freeTable[2][3] = new Array(4,300,100,1);
freeTable[2][4] = new Array(5,400,60,1);
freeTable[2][5] = new Array(6,460,770,0);



freeTable[3] = new Array();
freeTable[3][0] = new Array(1,0,200,1);
freeTable[3][1] = new Array(2,200,10,0);
freeTable[3][2] = new Array(3,210,90,1);
freeTable[3][3] = new Array(4,300,100,1);
freeTable[3][4] = new Array(5,400,60,1);
freeTable[3][5] = new Array(6,460,770,0);


function recycle()
{
    var value = document.getElementById("text").value;//要回收的分区号
    if(value == '')
    {
        alert('请输入正确的数据!');
        return false;
    }
    for(var num = 0;num<4;num++){
        for(var i = 0;i< freeTable[num].length;i++)
        {//0分区号 1起始地址 2大小 3状态

            if (freeTable[num][i][3] &&freeTable[num][i][0] == value )
            {
                if(i==0)
                {
                    if(freeTable[num][i+1][3])
                    {
                        freeTable[num][i][3] = 0;
                        //alert('12');
                        break;
                    }
                    else
                    {
                        freeTable[num][i][2] +=  freeTable[num][i+1][2];
                        freeTable[num][i][3] = 0;
                        freeTable[num].splice(i+1,1);//删除i
                        //alert('22');
                        break;
                    }
                }

                if(i == freeTable[num].length -1 )//最后
                {
                    if(!freeTable[num][i-1][3])//且倒数第二空闲
                    {
                        freeTable[num][i-1][2] = freeTable[num][i-1][2] + freeTable[num][i][2];
                        freeTable[num].splice(i,1);//删除i

                        //alert('42');
                        break;  
                    }
                    else
                    {
                        freeTable[num][i][3] = 0;
                        //alert('32');

                        break;              
                    }
                }


                if(!freeTable[num][i-1][3] && !freeTable[num][i+1][3])//前后均空闲
                {
                    freeTable[num][i-1][2] = freeTable[num][i-1][2] + freeTable[num][i][2]+freeTable[num][i+1][2];
                    //alert('52');
                    freeTable[num].splice(i,1);//删除i
                    freeTable[num].splice(i,1);//删除i+1
                    //freeTable[num].splice(i+2,1);//删除i+1
                    break;
                }
                else if (!freeTable[num][i-1][3]){//前空闲
                    //alert('62');
                    freeTable[num][i-1][2] = freeTable[num][i-1][2] + freeTable[num][i][2];
                    freeTable[num].splice(i,1);//删除i
                    break;
                }
                 else if (!freeTable[num][i+1][3]) {//后空闲
                    freeTable[num][i][2] = freeTable[num][i][2] +  freeTable[num][i+1][2];
                    freeTable[num][i][3] = 0;
                    //alert('72');
                    freeTable[num].splice(i+1,1); //删除i+1
                    break;
                }
                else{//前后均占用, 加一条记录
                    //alert('82');
                    freeTable[num][i][3] = 0;
                    break;
                }
            }


        }
    }
    onload();

}

//计算剩余空间
function leftMemory(num)
{
    var length =  freeTable[num].length;
    var free  = MAX;
    for (var i = 0; i < freeTable[num].length; i++){
        free = free - freeTable[num][i][2];
    }
    return free;
}



function firstFit(id,request)//首次适应
{
    var num =0;
    for(var i = 0; i < freeTable[num].length ; i++ )
        {
            if(!freeTable[num][i][3] && request<freeTable[num][i][2])
                {
                    if(freeTable[num][i][2] - request > size)//从i分区画出request大小的空间
                    {
                        freeTable[num][i][2] = freeTable[num][i][2]- request ;//修改分区大小
                        newrow = new Array(id,freeTable[num][i][1]+freeTable[num][i][2],request,1);
                        freeTable[num].splice(i+1,0,newrow);
                        return true;
                    }
                    else
                        {
                            freeTable[num][i][0] = id;//修改分区号
                            freeTable[num][i][3] = 1;//修改状态为已分配
                            return true;
                        }
                }
        }
        alert("首次适应算法内存空间不足，无法分配!");
        return false;
}




function netxFit(id,request)//循环首次
{
    var num = 1;
    if(flag==-1)//表示第一次，flag无标记,从头开始扫描
        flag = 0;
    for(var i = flag; i < freeTable[num].length ; i++ )
        {
            if(request <freeTable[num][i][2] && !freeTable[num][i][3])
                {
                    if(freeTable[num][i][2] - request > size)//从i分区画出request大小的空间
                    {
                        flag = i+1;
                        freeTable[num][i][2] = freeTable[num][i][2]- request ;//修改分区大小
                        newrow = new Array(id,freeTable[num][i][1]+freeTable[num][i][2],request,1);
                        freeTable[num].splice(i+1,0,newrow);
                        return true;
                    }
                    else{
                        flag = i+1;
                        freeTable[num][i][0] = id;//修改分区号
                        freeTable[num][i][3] = 1;//修改状态为已分配
                        return true;
                    }
                }
        }

    for(var i = 0; i < flag ; i++ )
        {
            if(request <freeTable[num][i][2] && !freeTable[num][i][3])
                {
                    if(freeTable[num][i][2] - request > size)//从i分区画出request大小的空间
                    {
                        flag = i+1;
                        freeTable[num][i][2] = freeTable[num][i][2]- request ;//修改分区大小
                        newrow = new Array(id,freeTable[num][i][1]+freeTable[num][i][2],request,1);
                        freeTable[num].splice(i+1,0,newrow);
                        return true;
                    }
                    else{
                        flag = i+1;
                        freeTable[num][i][0] = id;//修改分区号
                        freeTable[num][i][3] = 1;//修改状态为已分配
                        return true;
                    }
                }
        }


    alert("循环适应算法内存空间不足，无法分配!");
    return false;

}

function bestFit(id,request)//差值最小
{
    var num = 2;

    var Min = 1024;//记录差值最小
    var j = -1;//记录差值最小的分区位置
    for(var i = 0; i < freeTable[num].length ; i++ )
    {
        if( !freeTable[num][i][3] && freeTable[num][i][2] > request)//空闲且空间足够大
            {
                if(freeTable[num][i][2] - request < Min)
                    {
                        Min = freeTable[num][i][2] - request;
                        j = i;//更新j
                    }
            }
    }


    if(freeTable[num][j][2]-request > size)//从j分区画出request大小的空间
        {
            freeTable[num][j][2] = freeTable[num][j][2]- request ;//修改分区大小
            newrow = new Array(id,freeTable[num][j][1]+freeTable[num][j][2],request,1);
            freeTable[num].splice(j+1,0,newrow);
            //show();
            return true;
        }
    else
        {
            //alert(freeTable3[j][0]);
            freeTable[num][j][0] = id;//修改分区号
            freeTable[num][j][3] = 1;//修改状态为已分配
            //show();
            return true;
        }

    alert("最佳适应算法内存空间不足，无法分配!");
    return false;

}


function worstFit(id,request)//最坏匹配
{
    var num =3;
    var Max = 0;//记录差值最大
    var j = -1;
    //选择法找出最大的分区号
    for(var i = 0; i < freeTable[num].length ; i++ )
        {
            if( !freeTable[num][i][3] && freeTable[num][i][2] > request)//空闲且空间足够大
                {
                    if(freeTable[num][i][2] - request > Max)
                        {
                            Max = freeTable[num][i][2] - request;
                            j = i;//更新j
                        }
                }
        }


    if(freeTable[num][j][2] - request > size)//从i分区画出request大小的空间
    {
        freeTable[num][j][2] = freeTable[num][j][2]- request ;//修改分区大小
        newrow = new Array(id,freeTable[num][j][1]+freeTable[num][j][2],request,1);
        freeTable[num].splice(j+1,0,newrow);
        //show();
        return true;
    }
    else
        {
            //alert(freeTable4[j][0]);
            freeTable[num][j][0] = id;//修改分区号
            freeTable[num][j][3] = 1;//修改状态为已分配
            //show();
            return true;
        }


    alert("最坏适应算法内存空间不足，无法分配!");
    return false;
}




//生成表格数据
function content(num)
{

    var head ="";
    head += "<table cellspacing='0px' padding='0px'   border='1px'><tr><td nowrap='nowrap'>\
        分区号</td><td nowrap='nowrap'>分区始址</td><td nowrap='nowrap' >大小</td><td nowrap='nowrap'>状态</td></tr>";
    var body="";
    //alert(freeTable[num][1][2]);
    for(var i=0;i<freeTable[num].length;i++)
    {
        body +="<tr>";
        for(var j=0;j<freeTable[num][i].length-1;j++)
        {
                body +="<td>" + freeTable[num][i][j];

        }
        body +="K</td><td>"+(freeTable[num][i][3]==1?"占用":"空闲")+"</td></tr>";
    }

    body +="</table>";

    return head+body;
}


//生成图的数据
var a=0;
function show(num)
{
    //var num =0;
    var head ="";
    var body="";
    var height = 500;
    head+="<table id='Table' style='border:2px solid;height:"+height+'px;\'>';
    console.log(freeTable[num].length);
    console.log(freeTable[num][0][0]);

    for(var i=0;i<freeTable[num].length;i++)
    {
         body+="<tr>";
         if(!freeTable[num][i][3])//表示空闲
             body+="<td id='Table' style='height:"+freeTable[num][i][2]/1024*height+"px;\'>"+freeTable[num][i][2]+"K</td></tr>";
        else
             body+="<td  id='Table' class='busy' style='height:"+freeTable[num][i][2]/1024*height+"px;\'>"+freeTable[num][i][2]+"K</td></tr>";
    }


    var oUl = document.getElementById("ul"+num+num);
    oUl.removeChild(document.getElementsByTagName("li")[a++]);

    var OLi = document.createElement("li");
    OLi.innerHTML = content(num);
    console.log(OLi.innerHTML);
    oUl.appendChild(OLi);

    var oUl2 = document.getElementById("ul"+num+(num+1));
    oUl2.removeChild(document.getElementsByTagName("li")[a++]);
    var OLi1 = document.createElement("li");
    OLi1.innerHTML = head+body;
    oUl2.appendChild(OLi1);
    if(a>7)
        a  = 0;

}

function onload()
{
    for(var i = 0;i<4;i++)
        show(i);
}

function main()
{
    var value = document.getElementById("text").value;
    var id = value.split(',')[0],request = value.split(',')[1];
    if(value==''|| !request)//捕捉异常，不输入数据时点击分配按钮给出提示
    {
        alert('请输入正确的数据!');
        return false;
    }

    firstFit(id,request);
    netxFit(id,request);
    bestFit(id,request);
    worstFit(id,request);
    onload();


}

收起

展开全文

操作系统

操作系统中能够模拟动态内存分配算法来对进程分配内存空间的全部源代码及课设报告
热门讨论 2011-01-15 20:47:47
能够模拟动态内存分配算法对进程分配内存空间。该程序具备的基本功能为：（1）能够以空闲分区表的形式显示某一时刻内存空间的使用情况。（2）能够创建进程即输入进程信息，包括进程名称和进程需要的内存量，系统...
收起

java最适内存分配算法代码,Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF...

2021-04-24 11:31:13

1 概述
本文是利用Java实现操作系统中的四种动态内存分配方式 ，分别是：
BF
NF
WF
FF
分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。
2 四种分配方式
2.1 概念
操作系统中有一个动态分区分配的概念，内存在初始化的时候不会划分区域，而是在进程装入的时候，根据所要装入的进程动态地对内存空间进行划分，以提高内存空间的利用率，降低碎片的大小，主要的方法有一下四种：
首次适应算法(First Fit)：从空闲分区链首开始查找，直到找到一个满足其大小要求的空闲分区为止
循环首次适应算法(Next Fit)：从上次找到的空闲分区的下一个开始查找
最佳适应算法(Best Fit)：把空闲分区按大小递增的方式形成分区链，找到第一个能满足要求的空闲分区就进行分配
最坏适应算法(Worst Fit)：与最佳适应算法相反，把空闲分区按大小递减的方式形成分区链，找到第一个能满足要求的空闲分区就进行分配
2.2 例子
假设现在有100MB的内存空间，某一时刻先后分配了20MB、4MB、10MB内存，示意图如下：
在这里插入图片描述
现在需要再分配5MB内存。
若采用FF，因为FF是直接按顺序分配内存，从低地址开始搜索空闲分区，因此便会从第一块空闲分区分配5MB(地址0-5)，示意图：
在这里插入图片描述
若采用NF，NF与FF类似，只不过NF是从上一次找到的空闲分区的下一块开始查找，因为上一次分配的是10MB，因此会从最后一块空闲分区(地址80-100)分配内存：
在这里插入图片描述
若采用BF，BF是遍历所有空闲分区并找到一个能满足要求的最小分区，也就会找到一个比5MB大的空闲分区，且该空闲分区是所有空闲分区中最小的，也就是地址为64-70的空闲分区：
在这里插入图片描述
若采用WF，WF与BF相反，总是从最大的空闲分区开始分配，因此会从地址为30-60的空闲分区进行分配：
在这里插入图片描述
3 代码实现
3.1 总览
代码分成了四个类：
在这里插入图片描述
Main：测试
Print：输出打印
Table：表示每一个分区
TableList：对分区进行控制，包括初始化，分配，回收等
3.2 Main
Main是测试类，代码如下：
public class Main {
private final static TableList list = new TableList(64);
public static void main(String[] args) {
list.useWF();
//        list.useBF();
//        list.useNF();
//        list.useFF();
list.allocate(10);
list.allocate(20);
list.free(10);
list.show();
list.allocate(8);
list.show();
list.allocate(13);
list.allocate(1);
list.show();
list.free(1);
list.allocate(9);
list.free(13);
list.show();
list.allocate(18);
list.show();
list.allocate(3);
list.allocate(4);
list.free(20);
list.free(8);
list.show();
list.allocate(8);
list.free(9);
list.show();
list.clear();
list.show();
}
}
通过TableList对内存进行分配以及释放，初始化分配64MB大小内存，切换分配算法时使用前四行的其中一行即可。
3.3 Table
Table类表示每一个分区，无论是空闲的还是已分配的，成员变量有四个，分别是：
起始地址
大小
是否空闲(只有两种状态，空闲或分配)
是否是上一次分配(NF专用)
代码如下：
@AllArgsConstructor
public class Table {
@Getter
@Setter
private int address;
@Setter
@Getter
private int size;
private boolean free;
@Getter
@Setter
private boolean lastAllocated;
public static Table freeTable(int address,int size)
{
return new Table(address,size,true,false);
}
public static Table allocatedTable(int address,int size)
{
return new Table(address,size,false,false);
}
public boolean isFree()
{
return free;
}
public boolean isAllocated()
{
return !isFree();
}
public void setFree()
{
free = true;
}
}
只有一些Getter和Setter，为了方便提供了一个创建空闲分区或已分配分区的静态方法，指定起始地址和大小即可。
3.4 TableList
TableList是整个算法的核心类，成员变量如下：
private final List
private final int totalSize;
private boolean ff = false;
private boolean nf = false;
private boolean bf = false;
private boolean wf = false;
private boolean first = true;
private final static Print print = new Print();
list就是所有的空闲分区与已分配分区组成的数组，totalSize是总大小，接着是四个控制算法的布尔变量，first表示是否是第一次分配内存，因为第一次的话四种算法都是固定的从地址为0处开始分配。
接下来就是内存分配算法以及释放算法。
3.4.1 FF
if (ff)
{
for (int i = 0; i < list.size(); i++) {
Table table = list.get(i);
if(table.isFree() && table.getSize() >= size)
{
int address = table.getAddress();
Table allocated = Table.allocatedTable(address,size);
table.setAddress(address+size);
table.setSize(table.getSize()-size);
list.add(i,allocated);
return;
}
}
}
FF的实现还是比较简单的，直接遍历列表，如果是空闲分区并满足大小要求，直接进行分配，修改空闲分区的起始地址和大小并插入一个新的已分配分区到列表中即可。
3.4.2 NF
else if (nf)
{
int lastNFIndex = findLastAllocated();
int i = lastNFIndex;
do
{
if(i == list.size())
i = 0;
Table table = list.get(i);
if(table.isFree() && table.getSize() >= size)
{
int address = table.getAddress();
Table allocated = Table.allocatedTable(address,size);
table.setAddress(address+size);
table.setSize(table.getSize()-size);
list.get(lastNFIndex).setLastAllocated(false);
table.setLastAllocated(true);
list.add(i,allocated);
return;
}
++i;
}
while (i != lastNFIndex);
}
NF的话需要提前记录上一次分配的位置，通过Table中的lastAllocated确定上一次分配的位置，找到后从该位置开始遍历列表，注意需要进行绕回处理，因为到末尾位置后有可能还没有能满足的空闲分区，此时需要将下标绕回到0并再次遍历直到到达上一次分配的位置。
3.4.3 BF+WF
由于BF与WF都需要遍历所有的空闲分区，只是前者是选择最小满足要求的，后者是选择最大满足要求的，因此两者的实现差别在于一个判断大小的符号，代码如下：
else
{
int i;
int target = -1;
for (i = 0; i < list.size(); i++) {
Table table = list.get(i);
if(table.isFree())
{
if(table.getSize() >= size)
{
if(target == -1)
target = i;
else
{
if(bf)
{
if(list.get(target).getSize() > table.getSize())
target = i;
}
else
{
if(list.get(target).getSize() < table.getSize())
target = i;
}
}
}
}
}
if(target != -1)
{
Table table = list.get(target);
int address = table.getAddress();
table.setAddress(address+size);
table.setSize(table.getSize()-size);
list.add(target,Table.allocatedTable(address,size));
return;
}
}
首先遍历找到符合条件的空闲分区的下标，接着通过判断target，也就是目标空闲分区的下标，如果为-1表示没有找到符合条件的空闲分区，如果不为-1直接分配空间。
3.4.4 释放算法
释放算法的设计是比较复杂的，代码如下：
public void free(int size)
{
int index = 0;
while(index < list.size())
{
if(list.get(index).isAllocated() && list.get(index).getSize() == size)
break;
++index;
}
if(index >= list.size())
{
print.freeFailed(size);
return;
}
int address = list.get(index).getAddress();
if(index == 0)
{
list.get(0).setFree();
if(index+1 < list.size())
{
Table nextTable = list.get(index+1);
if(nextTable.isFree())
{
list.get(0).setSize(nextTable.getSize()+size);
list.remove(index+1);
}
}
}
else if(index == list.size()-1)
{
list.get(index).setFree();
Table lastTable = list.get(index-1);
if(lastTable.isFree())
{
lastTable.setSize(lastTable.getSize()+size);
list.remove(index);
}
}
else
{
Table before = list.get(index-1);
Table after = list.get(index+1);
if(before.isFree() && after.isFree())
{
before.setSize(before.getSize()+size+after.getSize());
list.remove(index+1);
list.remove(index);
}
else if(before.isFree() && after.isAllocated())
{
before.setSize(before.getSize()+size);
list.remove(index);
}
else if(before.isAllocated() && after.isFree())
{
after.setSize(after.getSize()+size);
after.setAddress(address);
list.remove(index);
}
else
{
list.get(index).setFree();
}
}
}
主要考虑了六种情况(黄色代表需要释放的空间，橙色是已分配的内存空间)：
在这里插入图片描述
第一种情况就是需要释放首部的分区，此时需要修改后面空闲分区的起始地址和大小，并删除目标分区
第二种情况是释放尾部的分区，此时需要修改前面空闲分区的大小即可，无需修改起始地址，并删除目标分区
第三种情况是后面是已分配的分区，前面的空闲分区，需要修改前面空闲分区的大小，并删除目标分区
第四种情况是前面是已分配的分区，后面是空闲分区，需要修改后面的空闲分区的起始地址以及大小，并删除目标分区
第五种情况是前后都是已分配的分区，此时只需要修改目标分区的标志为空闲即可，无需额外操作
第六种情况是前后都是空闲分区，这种情况下需要进行连接操作，具体来说就是先修改前面空闲分区的大小，接着删除目标分区以及后面的空闲分区
下面回到代码，首先是判断第一种情况：
if(index == 0)
{
list.get(0).setFree();
if(index+1 < list.size())
{
Table nextTable = list.get(index+1);
if(nextTable.isFree())
{
list.get(0).setSize(nextTable.getSize()+size);
list.remove(index+1);
}
}
}
也就是需要释放首部的分区，通过setFree()设置标志位表示空闲状态，接着判断是否需要修改后面空闲分区的大小，因为有可能后面是一个已分配的分区而不是空闲分区。
else if(index == list.size()-1)
{
list.get(index).setFree();
Table lastTable = list.get(index-1);
if(lastTable.isFree())
{
lastTable.setSize(lastTable.getSize()+size);
list.remove(index);
}
}
这里是判断第二种情况，也就是释放尾部的分区，同样需要判断前一个分区是已分配的分区还是空闲的分区，是空闲分区的话修改大小并移除目标分区。
else
{
Table before = list.get(index-1);
Table after = list.get(index+1);
if(before.isFree() && after.isFree())
{
before.setSize(before.getSize()+size+after.getSize());
list.remove(index+1);
list.remove(index);
}
else if(before.isFree() && after.isAllocated())
{
before.setSize(before.getSize()+size);
list.remove(index);
}
else if(before.isAllocated() && after.isFree())
{
after.setSize(after.getSize()+size);
after.setAddress(address);
list.remove(index);
}
else
{
list.get(index).setFree();
}
}
接下来是最后四种情况的判断，首先获取前一个以及后一个分区，接着按上面算法的思路进行判断即可。
4 测试
以WF为例，默认大小64MB，测试顺序如下：
分配10MB
分配20MB
释放10MB
打印结果
分配8MB
打印结果
分配13MB
分配1MB
打印结果
释放1MB
分配9MB
释放13MB
打印结果
分配18MB
打印结果
分配3MB
分配4MB
释放20MB
释放8MB
打印结果
分配8MB
释放9MB
打印结果
清空
打印结果
输出：
Free           :      0-10MB
Allocated      :      10-30MB
Free           :      30-64MB
----------------------------------------------------------------
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-64MB
----------------------------------------------------------------
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Allocated      :      38-51MB
Allocated      :      51-52MB
Free           :      52-64MB
----------------------------------------------------------------
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-51MB
Allocated      :      51-60MB
Free           :      60-64MB
----------------------------------------------------------------
Do nothing.
Allocated failed, out of memory
Free           :      0-10MB
Allocated      :      10-30MB
Allocated      :      30-38MB
Free           :      38-51MB
Allocated      :      51-60MB
Free           :      60-64MB
----------------------------------------------------------------
Allocated      :      0-4MB
Free           :      4-38MB
Allocated      :      38-41MB
Free           :      41-51MB
Allocated      :      51-60MB
Free           :      60-64MB
----------------------------------------------------------------
Allocated      :      0-4MB
Allocated      :      4-12MB
Free           :      12-38MB
Allocated      :      38-41MB
Free           :      41-64MB
----------------------------------------------------------------
Free           :      0-64MB
----------------------------------------------------------------
读者可以自行画图验证。
5 源码

收起

展开全文

动态内存分配算法（详解加代码）
千次阅读 2019-12-12 17:28:22
动态内存分配主要有四种算法： (1) 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。 (2) 循环首次适应算法：首次适应算法每次要从头找，增加了查找的开销，也可能在低地址上产生难以利用...
收起
一种快速的动态内存分配算法
2019-10-17 10:09:16
算法步骤： 1.对每个内存缓冲池进行划分，分为位图和内存块。例如一个2K的内存池，按照16字节一个block单位来划分，首先拿出16字节（=2*1024/16/8）当做位图来标记每个block...2.内存分配，针对需要多个块的情况，例...
收起
动态内存分配算法：首次适应算法，循环首次适应算法，最坏适应算法，最佳适应算法实现
2021-02-06 12:20:34
动态分区分配是根据进程的实际需要，动态地址为之分配内存空间，在分配时按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业 1.首次适应算法(FF):将所有空闲分区按照地址递增的次序链接，在...
收起
操作系统
嵌入式系统的自适应动态内存分配算法
2009-04-15 09:28:48
分析了2种常用的动态内存管理算法，基于此提出了一种新的适用与嵌入式系统的动态内存管理方案，在融合了经典算法精髓的同时，通过引入特殊的数据结构，避免了常用算法某些方面的不足，使其更能满足嵌入式系统对内存...
收起
常见的动态内存分配算法
千次阅读 2014-04-03 17:30:55
首次适配算法很快因为它减少了搜索的次数，只要搜索到就分配。 2,下次适配算法：它的工作方式和首次适配算法很像，不同点是每次找到合适的内存时都会记录当时的位置，而下次查找时都会从该节点查找，而不会从...
收起
各种存储分配算法java代码实现_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF...
2021-03-16 17:22:44
1 概述本文是利用Java实现操作系统中的四种动态内存分配方式，分别是：BFNFWFFF分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。2 四种分配方式2.1 概念操作系统中有一个动态...
收起
Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF
2020-11-21 17:42:39
本文是利用Java实现操作系统中的四种动态内存分配方式，分别是： BF NF WF FF 分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。 2 四种分配方式 2.1 概念操作系统中有一个...
收起
指定动态分区_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF
2021-01-15 02:17:44
1 概述本文是利用Java实现操作系统中的四种动态内存分配方式，分别是：BFNFWFFF分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。2 四种分配方式2.1 概念操作系统中有一个动态...
收起
动态内存分配算法(最简单实现)
2013-10-08 10:38:05
2）实现最简单的动态内存分配算法，不考虑效率，不考虑内存碎片； 3）只要实现malloc和free就行，如果有内存碎片，malloc失败返回空指针即可；网上搜了几种算法，感觉太过复杂，大都追求性能，不适用我面对的需求...
收起
java 判断是否是list_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF
2020-12-02 03:53:23
1 概述本文是利用Java实现操作系统中的四种动态内存分配方式，分别是：BFNFWFFF分两部分，第一部分是介绍四种分配方式的概念以及例子，第二部分是代码实现以及讲解。2 四种分配方式2.1 概念操作系统中有一个动态...
收起
循环首次适应算法

嵌入式动态内存分配算法tlsf

动态内存分配算法实验报告.doc

动态内存分配算法

TLSF动态内存分配算法的研究与应用

动态内存分配算法实验报告

基于μCOS-II的TLSF动态内存分配算法的应用与仿真

操作系统课程设计动态内存分配算法

动态内存分配算法（源代码&报告）DynamicAllocate

java动态分区分配算法_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF

操作系统-动态内存分配算法

操作系统中能够模拟动态内存分配算法来对进程分配内存空间的全部源代码及课设报告

java最适内存分配算法代码,Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF...

动态内存分配算法（详解加代码）

一种快速的动态内存分配算法

动态内存分配算法：首次适应算法，循环首次适应算法，最坏适应算法，最佳适应算法实现

嵌入式系统的自适应动态内存分配算法

常见的动态内存分配算法

各种存储分配算法java代码实现_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF...

Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF

指定动态分区_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF

动态内存分配算法(最简单实现)

java 判断是否是list_Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF

动态内存分配算法