精华内容
下载资源
问答
  • 银行家算法--进程调度算法--内存分配算法java实现
  • 内存分配方式与内存分配算法 http://www.cnblogs.com/hapjin/p/5689049.html 内存分配方式有两种,连续内存分配方式和离散内存分配方式。不同的分配方式又有不同的分配算法。 内存分配算法,其实就是:有一大块...

    内存分配方式与内存分配算法

    http://www.cnblogs.com/hapjin/p/5689049.html

    内存分配方式有两种,连续内存分配方式和离散内存分配方式。不同的分配方式又有不同的分配算法。

    内存分配算法,其实就是:有一大块空闲的资源,如何合理地分配资源?内存分配的思想可以用到很多其他的领域。比如Java虚拟机是如何将内存分配与回收的?再比如文件系统是如何将磁盘块分配与回收的?其本质就是如何把空闲的资源分配出去,分配之后又如何回收?目标就是分配快,回收也快,而且还不浪费。那么,就需要根据资源的特点、以及应用场景做权衡从而选择何种方式进行分配与回收。

     

    ①连续内存分配方式

    1)固定分区分配

    将内存划分成若干个固定大小的块。将程序装入块中即可。内存划分成各个块之后,块大小不再改变。当然,划分块的方式有:所有的块大小相等;划分的块大小不相等。

    这种方式,在实际的内存分配之前,就已经知道了所有的内存块大小了。

     

    2)动态分区分配

    需要一个空闲表 或者 空闲链 来记录目前系统中空间的内存区域。在内存分配时,需要查找空间表或空闲链找到一块内存分配给当前进程。

     

    动态分区分配算法:

    a)首次适应法

    b)循环首次适应法

    c)最佳适应法

    d)最坏适应法

    e)快速适应法

     

    3)可重定位分区分配

    说白了,就是增加了内存移动的功能。由于若干次内存分配与回收之后,各个空闲的内存块不连续了。通过“重定位”,将已经分配的内存“紧凑”在一块(就类似于JVM垃圾回收中的复制算法)从而空出一大块空闲的内存出来。

    ”紧凑“是需要开销的,比如需要重新计算 地址,这也为什么JVM垃圾回收会导致STW的原因。

    而离散分配方式--不管是分页还是分段,都是直接将程序放到各个离散的页中。从而就不存在“紧凑”一说了。

     

    连续内存分配方式涉及两种操作:内存分配操作 和 内存回收操作

     

    ②离散内存分配方式

    内存资源是有限的,程序要运行,必须得加载到内存。如果内存已经满了,而现在又有新的程序要运行,怎么办?---SWAP

    把当前不用的程序(数据)先换出内存,从而就有空间 加载当前需要运行的程序的一部分数据进入内存,这样大大提高了内存的利用率。

    由于牵涉到换入与换出,前面的连续内存分配方式就有点不适用了。因为,最明显的一个问题:对于连续内存分配方式,究竟换出哪部分数据呢?

    而这种只装入部分"数据"就可以使程序运行的机制,就是虚拟存储器的本质。

     

    1)分页存储管理

    将进程的逻辑地址空间分成若干大小相等的页面;同时,也将物理内存分成相等大小的页面(称为块或frame)。在为进程分配内存时,以块为单位将进程的若干页 可以 装入到内存中多个不邻接的物理块中。

    从上可以看出:“离散” 体现在:进程在内存中分配的空间(物理块)是不连续的。而对于连续分配方式,进程在内存的分配的空间是连续的。

    现在考虑32位系统,每个物理块的大小为4KB。如何把逻辑地址 转换成 物理地址?

    对每个进程而言,都有着自己的页表。页表的本质就是逻辑地址到物理地址的映射。

    分页存储中的逻辑地址的结构如下:

    1)由于进程的逻辑页面大小与物理块(页帧)大小相同,故都为4K,因此需要12个位表示4K的大小(2^12=4K),即图中的【0-11】

    2)【12-31】表示的是页号。一共有20个位表示页号,也即:对于一个进程而言,一共可以有1M(2^20=1M)个页。

    3)每个进程的逻辑地址空间范围为0-2^32-1,因为:每个页大小为4K,一共有1M个页。故进程可用的逻辑空间为2^32B

     

    逻辑地址到物理地址的转换需要用到页表。具体细节是有一个“地址变换机构”,它有一个寄存器保存页表在内存的起始地址 以及 页表的长度

    上面提到,一个进程最多可以有1M个页,故页表就有1M个页表项。假设每个页表项只有1B,那页表的大小也有1MB,所以:一般而言,页表也是很大的,不能全放在寄存器中,故页表也是存储在内存中的。(有些机器有“快表”,快表就是一个寄存器,它保存了页表中的部分表项);其次,也可以使用多级页表以解决单个页表太大的问题。

    那现在给定一个逻辑地址,怎么知道其物理地址呢?

    ①将【12-31】位的页号与 页表的长度比较。页号不能大于页表长度,否则越界。

    ②根据页号 找到 该页号所在的页表项,即该页号对应着哪个页表项。因为,页表项里面就存放着物理地址。

    那如何查找页表项呢?将页号乘以页表项的长度(每个页表项,其实就是一个逻辑的页 到 物理页 的映射信息),就知道了该逻辑页对应着哪个页表项(根据页号匹配页表项一般是由硬件完成的)

    然后,正如前面提到,页表也是保存在内存中的,故需要页表的内存始址(这是也为什么地址变换机构 保存 页表在内存的起始地址的原因),将页表始址 与 上面的乘积相加,就得到了该逻辑页对应的页表项的物理地址。读这个页表项的物理地址中的内容,就知道了该逻辑页对应的物理块地址(物理地址)。从而,就完成了逻辑地址到物理地址的转换。

    从上面可以看出,CPU每存取一个数据时,需要两次访问主存。一次是访问页表项的物理地址,得到了数据的物理块地址。第二次拿着物理块地址去取数据。

    在分页存储管理方式下:由于取一个数据,需要二次访存,CPU处理速度降低了一半,正由于这个原因:引入了“快表”(又称TLB(Translation Lookaside Buffer)),快表是个寄存器,用来保存那些当前访问过的页表项。从而,读页表项时,不需要再访存了,而是直接从寄存器中读取。

     

    虚拟存储器

    谈到虚拟存储器,总是说它从逻辑上扩充了内存的容量,why?

    内存是有限的,作业初始时保存在磁盘上的,如果要运行,必须得将相应的程序(数据)加载到内存中。那如果要运行的作业特别多,无法一下子装入内存,怎么办?

    一种方式是加内存条,这是从物理上扩充内存的容量。

    另一种方式是:先把作业的一部分程序(数据)装入内存,先让它运行着,运行过程中发现: 咦,我还需要其他的数据,而这些数据还未装入内存,因此就产生中断(缺页中断)再将数据加载到内存。

    采用这种方式,系统一次就可以将很多作业装入内存运行了。这时,从物理上看,内存还是原来的大小,但是它能运行的作业多了,因此说从逻辑上扩充了内存。

    将虚拟存储器这种思想与分页存储管理结合,一次只将作业的部分页面加载到内存中,形成了一个强大的内存分配与管理系统了。引入了虚拟存储器,同样需要有页表,记录逻辑地址到物理地址的映射,只不过此时的页表更复杂了,因为,有些页可能还在磁盘上。;还需要有缺页中断处理机构,因为毕竟只将一部分数据装入内存,会引起缺页中断嘛,就需要处理中断嘛;还需要地址变换机构,这里的地址变换机构功能更多,因为需要处理中断情况下的地址变换。

     

    2)分段存储管理

    与分页比较相似,不介绍了。

    展开全文
  • 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内存,示意图如下:

    b0feb4b9342d2b7d20263ad1548c905f.png

    现在需要再分配5MB内存。

    若采用FF,因为FF是直接按顺序分配内存,从低地址开始搜索空闲分区,因此便会从第一块空闲分区分配5MB(地址0-5),示意图:

    ba6f5f50db1c609836b345f13230d0cc.png

    若采用NF,NF与FF类似,只不过NF是从上一次找到的空闲分区的下一块开始查找,因为上一次分配的是10MB,因此会从最后一块空闲分区(地址80-100)分配内存:

    dde8a54212ec9768092fa98cdb29c2e3.png

    若采用BF,BF是遍历所有空闲分区并找到一个能满足要求的最小分区,也就会找到一个比5MB大的空闲分区,且该空闲分区是所有空闲分区中最小的,也就是地址为64-70的空闲分区:

    fad224f2583867120489e6ec24ef17ff.png

    若采用WF,WF与BF相反,总是从最大的空闲分区开始分配,因此会从地址为30-60的空闲分区进行分配:

    fee9fd84f4c53c1c34cb455bee146d9b.png

    3 代码实现

    3.1 总览

    代码分成了四个类:

    13ff6b97659f8fd9b8b205b66c2482c1.png

    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();

    }

    }

    }

    主要考虑了六种情况(黄色代表需要释放的空间,橙色是已分配的内存空间):

    fd02643fc123836785d86e04785f15f2.png

    第一种情况就是需要释放首部的分区,此时需要修改后面空闲分区的起始地址和大小,并删除目标分区

    第二种情况是释放尾部的分区,此时需要修改前面空闲分区的大小即可,无需修改起始地址,并删除目标分区

    第三种情况是后面是已分配的分区,前面的空闲分区,需要修改前面空闲分区的大小,并删除目标分区

    第四种情况是前面是已分配的分区,后面是空闲分区,需要修改后面的空闲分区的起始地址以及大小,并删除目标分区

    第五种情况是前后都是已分配的分区,此时只需要修改目标分区的标志为空闲即可,无需额外操作

    第六种情况是前后都是空闲分区,这种情况下需要进行连接操作,具体来说就是先修改前面空闲分区的大小,接着删除目标分区以及后面的空闲分区

    下面回到代码,首先是判断第一种情况:

    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 源码

    如果觉得文章好看,欢迎点赞。

    同时欢迎关注微信公众号:氷泠之路。

    ebe708739090e88a25ec43acae9dd054.gif

    展开全文
  • 一、概述  因为这次os作业对用户在控制台的输入输出有要求... 因为不同内存分配算法,只有对空闲分区表的排序不同,所以可以将FF和BF等内存分配算法一起实现。    如果只关心和算法有关的核心代码的话,只看M...

    一、概述

      因为这次os作业对用户在控制台的输入输出有要求,所以我花了挺多的代码来完善控制台的显示。

      MemoryAlgorithm类里只是和控制台输入输出有关的操作,而对内存的所有逻辑操作都是用Memory类里对应的方法实现的。

      因为不同内存分配算法,只有对空闲分区表的排序不同,所以可以将FF和BF等内存分配算法一起实现。

      

      如果只关心和算法有关的核心代码的话,只看Memory类中add()、del()和sortFreeAreaList()方法即可

      添加和删除操作的逻辑比较绕,后面也有关于添加和删除操作单独的流程图。

     

    二、运行结果

      1. 测试数据:

    (1)系统总内存为256,按下列参数分配内存

    进程

    1

    2

    3

    4

    5

    6

    所需内存

    25

    34

    45

    12

    13

    10

    (2)依次回收进程2,4,3,6

    (3)再次分配进程7,大小40

      2. 测试结果:

      (太长了,我就不截图了。测试的时候注意我的代码是按照请求回收内存的首地址进行回收的就行)

     

    三、流程图

      1. FF算法和BF算法的流程图

      2. 添加进程的流程图

      3. 撤销进程的流程图

     

     

    四、实现代码

      1. MemoryAlgorithm类(主类)

    MemoryAlgorithm类只需要:

      1.在适当的记录用户的输入;

      2.根据用户的输入调用Memory类中对应的方法;

      3.向用户反馈结果

    所以这个类只是个界面。

      1 package xqy.algorithm;
      2 
      3 import java.util.*;
      4 
      5 import xqy.been.*;
      6 
      7 /**
      8  * @author xqy
      9  * @date 2018年12月20日21:36:40
     10  *
     11  */
     12 public class MemoryAlgorithm {
     13     private Memory memory;
     14     private String algType;
     15     private Scanner sc;
     16     
     17     /**
     18      * Each memory algorithm uses this class.<br/><br/>
     19      * Each memory algorithm is different only in free area's sorting. <br/><br/>
     20      * @param algType
     21      *         FF: First fit,
     22      *         BF: Best fit
     23      */
     24     public MemoryAlgorithm(String algType) {
     25         sc = new Scanner(System.in);
     26         this.algType = algType;
     27         
     28         init();
     29         op();
     30     }
     31     
     32     private void init() {
     33         int memorySize;
     34         int fragment;
     35         
     36         System.out.print("<" + algType + "> Please enter the memory size:");
     37         memorySize = sc.nextInt();
     38         
     39         System.out.print("<" + algType + "> Please enter the fragment allocated:");
     40         fragment = sc.nextInt();
     41 
     42         memory = new Memory(memorySize, fragment, algType);        
     43     }
     44 
     45     private void op() {
     46         int key;
     47 
     48         while(true) {
     49             System.out.println("\n    #OPTION#");
     50             System.out.println("1.Add Job   2.Delete Job   3.Show Current Memory   4.Exit");
     51             System.out.print("<" + algType + "> Option:");
     52             key = sc.nextInt();
     53             if (key == 1) {
     54                 add();        
     55             } else if (key == 2) {
     56                 del();
     57             } else if (key == 3) {
     58                 show();
     59             } else if (key == 4) {
     60                 System.out.println("    #EXIT#");
     61                 return;
     62             } else {    
     63                 System.out.println("    #WRONG OPTION#");
     64             }
     65         }
     66     }
     67 
     68     private void add() {
     69         int key;
     70                 
     71         while (true) {
     72             System.out.print("<" + algType + "-add> Please enter the job size (exit: -1):");
     73             key = sc.nextInt();
     74             
     75             if (key == -1) {
     76                 System.out.println("    #EXIT#");
     77                 return;
     78             } else if (key < 0) {
     79                 System.out.println("    #WRONG SIZE#");
     80             } else {
     81                 
     82                 if (memory.add(key)) {
     83                     System.out.println("    #ADD RESULT# complete");
     84                 } else {
     85                     System.out.println("    #ADD RESULT# fail");
     86                 }
     87 
     88             }
     89         }
     90     }
     91     
     92     private void del() {
     93         int key;
     94                 
     95         while (true) {
     96             System.out.print("<" + algType + "-del> Please enter the job first address (exit: -1):");
     97             key = sc.nextInt();
     98             
     99             if (key == -1) {
    100                 System.out.println("    #EXIT#");
    101                 return;
    102             } else if (key < 0 || key >= memory.size()) {
    103                 System.out.println("    #WRONG ADDRESS#");
    104             } else {
    105                 
    106                 if (memory.del(key)) {
    107                     System.out.println("    #DEL RESULT# complete");
    108                 } else {
    109                     System.out.println("    #DEL RESULT# fail");
    110                 }
    111             }
    112         }
    113         
    114     }
    115     
    116     private void show() {
    117         System.out.println("<" + algType + "-current memory>");
    118         System.out.print(memory.toString());
    119     }
    120         
    121     public static void main(String [] args) {
    122         Scanner sc = new Scanner(System.in);
    123         int key;
    124         
    125         
    126         while (true) {
    127             System.out.println("\n    #OPTION#");
    128             System.out.println("1.FF   2.BF   3.Exit");
    129             System.out.print("Option:");
    130             key = sc.nextInt();
    131             
    132             if (key == 1) {
    133                 new MemoryAlgorithm("FF");
    134             } else if (key == 2) {
    135                 new MemoryAlgorithm("BF");
    136             } else if (key == 3) {
    137                 System.out.println("    #EXIT#");
    138                 break;
    139             } else {
    140                 System.out.println("    #WRONG OPTION#");                    
    141             }
    142         }
    143     }
    144 }

      2. Memory类

    Memory类实现了:

      1) 对内存相应属性的封装;

      2) 对内存的操作:

        a) add() --> 添加作业分配内存;

        b) del() --> 撤销作业释放内存;

        c) toString() --> 展示内存的信息;

        d) sortFreeAreaList() --> 根据用户选择的内存分配算法,对“空闲空间表”进行排序(不同算法间,唯一的不同)

      1 package xqy.been;
      2 
      3 import java.util.ArrayList;
      4 import java.util.Collections;
      5 import java.util.Comparator;
      6 
      7 public class Memory {
      8     private int size;
      9     private int fragment;
     10     private String algType;
     11     private ArrayList<Area> freeAreaList;
     12     private ArrayList<Area> usedAreaList;
     13 
     14     public Memory(int size, int fragment, String algType) {
     15         this.size = size;
     16         this.fragment = fragment;
     17         this.algType = algType;
     18         this.freeAreaList = new ArrayList<Area>();
     19         this.usedAreaList = new ArrayList<Area>();
     20 
     21         this.freeAreaList.add(new Area(size, 0, true));
     22     }
     23 
     24     public boolean add(int newJobSize) {
     25         boolean canAdd = false;
     26         Area opFreeArea;
     27 
     28         for (int i = 0; i < freeAreaList.size(); i++) {
     29             opFreeArea = freeAreaList.get(i);
     30 
     31             if (newJobSize > opFreeArea.size()) {
     32                 ;
     33             } else {
     34                 if ((opFreeArea.size() - newJobSize) <= fragment) {
     35                     usedAreaList.add(new Area(opFreeArea.size(), opFreeArea.getAddress(), false));
     36                     freeAreaList.remove(i);
     37                 } else {
     38                     int newAreaSize = opFreeArea.size() - newJobSize;
     39                     int newAreaAddress = opFreeArea.getAddress() + newJobSize;
     40                     Area newFreeArea = new Area(newAreaSize, newAreaAddress, true);
     41 
     42                     usedAreaList.add(new Area(newJobSize, opFreeArea.getAddress(), false));
     43                     freeAreaList.remove(i);
     44                     freeAreaList.add(i, newFreeArea);
     45                 }
     46 
     47                 canAdd = true;
     48                 sortFreeAreaList();
     49                 
     50                 break;
     51             }
     52         }
     53 
     54         return canAdd;
     55     }
     56 
     57     /**
     58      * Delete job according to job`s first address.<br/><br/>
     59      * 
     60      * If the address you entered don`t fit any used area`s first address, can`t delete.<br/><br/>
     61      * 
     62      * If the address you entered is fight:<br/>
     63      * <ul>
     64      *         <li>Case 1: Previous area and next area are both free.</li>
     65      *             <ul>
     66      *                 <li>1.修改状态</li>
     67      *                 <li>2.从used area list中删去,加进free area list</li>
     68      *             </ul>
     69      *         <li>Case 2: Previous area and next area are both used.</li>
     70      *             <ul>
     71      *                 <li>1.修改最前面的分区 更改size(三个区的size之和)</li>
     72      *                 <li>2.从free area list 中将next free area 删除</li>
     73      *                 <li>3.从used area list 中将相应area 删除</li>
     74      *             </ul>
     75      *         <li>Case 3: Previous area is free, and next area is used.</li>
     76      *             <ul>
     77      *                 <li>1.修改前面的分区 更改size(将前面分区的size和要删除分区的size合并)</li>
     78      *                 <li>2.从used area list中将相应area删除</li>
     79      *             </ul>
     80      *         <li>Case 4: Previous are is used, and next area is free.</li>
     81      *             <ul>
     82      *                 <li>1.修改后面的分区 
     83      *                     <ul>
     84      *                         <li>(1)更改size(将要删除的分区的size和后面分区的size合并</li>
     85      *                         <li>(2)更改address-->改成要删除分区的address </li>
     86      *                    </ul>
     87      *                 <li>2.从used area list中将相应area删除</li>
     88      *             </ul>
     89      * </ul>
     90      * @param delJobAddress
     91      * @return
     92      */
     93     public boolean del(int delJobAddress) {
     94         boolean canDel = false;
     95         int delAreaIndex = -1;
     96 
     97         for (int i = 0; i < usedAreaList.size(); i++) {
     98             if (delJobAddress == usedAreaList.get(i).getAddress()) {
     99                 canDel = true;
    100                 delAreaIndex = i;
    101             }
    102         }
    103 
    104         if (canDel == true) {
    105             int previousFreeAreaIndex = calcPreviousFreeAreaIndex(delJobAddress); 
    106             int nextFreeAreaIndex = calcNextFreeAreaIndex(delJobAddress, usedAreaList.get(delAreaIndex).size());
    107             
    108             if ((previousFreeAreaIndex == -1) && (nextFreeAreaIndex == -1)) { // case 1
    109                 Area a = usedAreaList.get(delAreaIndex);
    110                 a.setFree(true);
    111 
    112                 usedAreaList.remove(delAreaIndex);
    113                 freeAreaList.add(a);
    114             } else if ((previousFreeAreaIndex >= 0) && (nextFreeAreaIndex >= 0)) { // case 2
    115                 Area preArea = freeAreaList.get(previousFreeAreaIndex);
    116                 Area needDelArea = usedAreaList.get(delAreaIndex);
    117                 Area nextArea = freeAreaList.get(nextFreeAreaIndex);
    118                 preArea.setSize(preArea.size() + needDelArea.size() + nextArea.size());
    119                 
    120                 freeAreaList.remove(nextFreeAreaIndex);
    121                 usedAreaList.remove(delAreaIndex);
    122             } else if (previousFreeAreaIndex >= 0) { // case 3
    123                 Area area = freeAreaList.get(previousFreeAreaIndex);
    124                 area.setSize(area.size() + usedAreaList.get(delAreaIndex).size());
    125                 usedAreaList.remove(delAreaIndex);
    126             } else if (nextFreeAreaIndex >= 0) { // case 4
    127                 Area area = freeAreaList.get(nextFreeAreaIndex);
    128                 area.setSize(area.size() + usedAreaList.get(delAreaIndex).size());
    129                 area.setAddress(usedAreaList.get(delAreaIndex).getAddress());
    130                 usedAreaList.remove(delAreaIndex);
    131             }
    132 
    133             sortFreeAreaList();
    134         }
    135 
    136         return canDel;
    137     }
    138 
    139     private int calcPreviousFreeAreaIndex(int address) {
    140         int index = -1;
    141 
    142         for (int i = 0; i < freeAreaList.size(); i++) {
    143             if ((freeAreaList.get(i).getAddress() + freeAreaList.get(i).size()) == address) {
    144                 index = i;
    145             }
    146         }
    147 
    148         return index;
    149     }
    150 
    151     private int calcNextFreeAreaIndex(int address, int size) {
    152         int index = -1;
    153 
    154         for (int i = 0; i < freeAreaList.size(); i++) {
    155             if (freeAreaList.get(i).getAddress() == (address + size)) {
    156                 index = i;
    157             }
    158         }
    159 
    160         return index;
    161     }
    162 
    163     private void sortFreeAreaList() {
    164         if (algType.equals("FF")) {
    165             Collections.sort(freeAreaList, new SortByAddress());
    166         } else if (algType.equals("BF")) {
    167             Collections.sort(freeAreaList, new SortBySize());
    168         }
    169     }
    170 
    171     public int size() {
    172         return size;
    173     }
    174 
    175     public ArrayList<Area> getFreeAreaList() {
    176         return freeAreaList;
    177     }
    178 
    179     @SuppressWarnings("unchecked") // 给编译器一条指令,告诉它对被批注的代码元素内部的某些警告保持静默
    180     @Override
    181     public String toString() {
    182         ArrayList<Area> list = new ArrayList<Area>();
    183         list.addAll((ArrayList<Area>)freeAreaList.clone());
    184         list.addAll((ArrayList<Area>)usedAreaList.clone());
    185         Collections.sort(list, new SortByAddress());
    186 
    187         String str = "    Current memory:\n";
    188         for (int i = 0; i < list.size(); i++) {
    189             str += "    [Area] " 
    190                     + "address=" + list.get(i).getAddress() + "-" + (list.get(i).getAddress() + list.get(i).size() - 1)
    191                     + " size=" + list.get(i).size()
    192                     + ((list.get(i).isFree()) ? " free\n" : " used\n");
    193         }
    194         
    195         str += "    Free area List:\n";
    196         if (freeAreaList.size() == 0) {
    197             str += "    null\n";
    198         } else {
    199             for (int i = 0; i < freeAreaList.size(); i++) {
    200                 str += "    [Area] " + "address=" + freeAreaList.get(i).getAddress() + "-"
    201                         + (freeAreaList.get(i).getAddress() + freeAreaList.get(i).size() - 1)
    202                         + " size=" + freeAreaList.get(i).size() + "\n";            
    203             }
    204         }
    205         return str;
    206     }
    207 }
    208 
    209 class SortBySize implements Comparator<Area> {
    210     public int compare(Area a1, Area a2) {
    211         if (a1.size() > a2.size())
    212             return 1;
    213         return -1;
    214     }
    215 }
    216 
    217 class SortByAddress implements Comparator<Area> {
    218     public int compare(Area a1, Area a2) {
    219         if (a1.getAddress() > a2.getAddress())
    220             return 1;
    221         return -1;
    222     }
    223 }

     

    展开全文
  • import java.util.LinkedList;import java.util.Scanner;/*** 内存类* @author [emailprotected]*/public class Memory{/*** 内存大小*/private int size;/*** 最小剩余分区大小*/private static final int...

    package com.dht.memory;

    import java.util.LinkedList;

    import java.util.Scanner;

    /**

    * 内存类

    * @author [email protected]

    */

    public class Memory{

    /**

    * 内存大小

    */

    private int size;

    /**

    * 最小剩余分区大小

    */

    private static final int MIN_SIZE = 5;

    /**

    * 内存分区

    */

    private LinkedList zones;

    /**

    * 上次分配的空闲区位置

    */

    private int pointer;

    /**

    * 分区节点类

    */

    class Zone{

    /**

    * 分区大小

    */

    private int size;

    /**

    * 分区始址

    */

    private int head;

    /**

    * 空闲状态

    */

    private boolean isFree;

    public Zone(int head, int size) {

    this.head = head;

    this.size = size;

    this.isFree = true;

    }

    }

    /**

    * 默认内存大小为 100 KB

    */

    public Memory(){

    this.size = 100;

    this.pointer = 0;

    this.zones = new LinkedList<>();

    zones.add(new Zone(0, size));

    }

    public Memory(int size) {

    this.size = size;

    this.pointer = 0;

    this.zones = new LinkedList<>();

    zones.add(new Zone(0, size));

    }

    /**

    * 内存分配

    * @param size 指定需要分配的大小

    */

    public void allocation(int size){

    System.out.println("1.FirstFit 2.NextFit 3.BestFit 4.WorstFit");

    System.out.print("请选择分配算法:");

    Scanner in = new Scanner(System.in);

    int algorithm = in.nextInt();

    switch (algorithm){

    case 1:

    fristFit(size);break;

    case 2:

    nextFit(size);break;

    case 3:

    bestFit(size);break;

    case 4:

    worstFit(size);break;

    default:

    System.out.println("请重新选择!");

    }

    }

    /**

    * 首次适应算法

    * @param size 指定需要分配的大小

    */

    private void fristFit(int size){

    //遍历分区链表

    for (pointer = 0; pointer < zones.size(); pointer++){

    Zone tmp = zones.get(pointer);

    //找到可用分区(空闲且大小足够)

    if (tmp.isFree && (tmp.size > size)){

    doAllocation(size, pointer, tmp);

    return;

    }

    }

    //遍历结束后未找到可用分区, 则内存分配失败

    System.out.println("无可用内存空间!");

    }

    /**

    * 循环首次适应算法

    * @param size 指定需要分配的大小

    */

    private void nextFit(int size){

    //从上次分配空闲区位置开始遍历分区链表

    Zone tmp = zones.get(pointer);

    if (tmp.isFree && (tmp.size > size)){

    doAllocation(size, pointer, tmp);

    return;

    }

    int len = zones.size();

    int i = (pointer + 1) % len;

    for (; i != pointer; i = (i+1) % len){

    tmp = zones.get(i);

    //找到可用分区(空闲且大小足够)

    if (tmp.isFree && (tmp.size > size)){

    doAllocation(size, i, tmp);

    return;

    }

    }

    //遍历结束后未找到可用分区, 则内存分配失败

    System.out.println("无可用内存空间!");

    }

    /**

    * 最佳适应算法

    * @param size 指定需要分配的大小

    */

    private void bestFit(int size){

    int flag = -1;

    int min = this.size;

    for (pointer = 0; pointer < zones.size(); pointer++){

    Zone tmp = zones.get(pointer);

    if (tmp.isFree && (tmp.size > size)){

    if (min > tmp.size - size){

    min = tmp.size - size;

    flag = pointer;

    }

    }

    }

    if (flag == -1){

    System.out.println("无可用内存空间!");

    }else {

    doAllocation(size, flag, zones.get(flag));

    }

    }

    /**

    * 最坏适应算法

    * @param size 指定需要分配的大小

    */

    private void worstFit(int size){

    int flag = -1;

    int max = 0;

    for (pointer = 0; pointer < zones.size(); pointer++){

    Zone tmp = zones.get(pointer);

    if (tmp.isFree && (tmp.size > size)){

    if (max < tmp.size - size){

    max = tmp.size - size;

    flag = pointer;

    }

    }

    }

    if (flag == -1){

    System.out.println("无可用内存空间!");

    }else {

    doAllocation(size, flag, zones.get(flag));

    }

    }

    /**

    * 执行分配

    * @param size 申请大小

    * @param location 当前可用分区位置

    * @param tmp 可用空闲区

    */

    private void doAllocation(int size, int location, Zone tmp) {

    //如果分割后分区剩余大小过小(MIN_SIZE)则将分区全部分配,否则分割为两个分区

    if (tmp.size - size <= MIN_SIZE){

    tmp.isFree = false;

    } else {

    Zone split = new Zone(tmp.head + size, tmp.size - size);

    zones.add(location + 1, split);

    tmp.size = size;

    tmp.isFree = false;

    }

    System.out.println("成功分配 " + size + "KB 内存!");

    }

    /**

    * 内存回收

    * @param id 指定要回收的分区好号

    */

    public void collection(int id){

    if (id >= zones.size()){

    System.out.println("无此分区编号!");

    return;

    }

    Zone tmp = zones.get(id);

    int size = tmp.size;

    if (tmp.isFree) {

    System.out.println("指定分区未被分配, 无需回收");

    return;

    }

    //如果回收分区不是尾分区且后一个分区为空闲, 则与后一个分区合并

    if (id < zones.size() - 1 && zones.get(id + 1).isFree){

    Zone next = zones.get(id + 1);

    tmp.size += next.size;

    zones.remove(next);

    }

    //如果回收分区不是首分区且前一个分区为空闲, 则与前一个分区合并

    if (id > 0 && zones.get(id - 1).isFree){

    Zone previous = zones.get(id - 1);

    previous.size += tmp.size;

    zones.remove(id);

    id--;

    }

    zones.get(id).isFree = true;

    System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");

    }

    /**

    * 展示内存分区状况

    */

    public void showZones(){

    System.out.println("------------------------------------");

    System.out.println("分区编号t分区始址t分区大小t空闲状态t");

    System.out.println("------------------------------------");

    for (int i = 0; i < zones.size(); i++){

    Zone tmp = zones.get(i);

    System.out.println(i + "tt" + tmp.head + "tt" +

    tmp.size + " t" + tmp.isFree);

    }

    System.out.println("------------------------------------");

    }

    }

    展开全文
  • 1 packagexqy.been;23 importjava.util.ArrayList;4 importjava.util.Collections;5 importjava.util.Comparator;67 public classMemory {8 private intsize;9 private intfragment;10 privateString al...
  • java实现的一个简单的动态分区内存分配算法的实现 本人只是一个学生,写这篇东西纯粹是做完课设留个记录,代码仅供参考,不一定正确。 By Aimer_majiko_sayuri 2019-1-2 实现动态分区内存分配的...
  • import java.util.ArrayList;import java.util.Iterator;import java.util.Scanner;public class OS {ArrayList freeList=new ArrayList();//空闲区链表ArrayList useList=new ArrayList();//使用区链表Iterato...
  • 本文是利用Java实现操作系统中的四种动态内存分配方式 ,分别是: BF NF WF FF 分两部分,第一部分是介绍四种分配方式的概念以及例子,第二部分是代码实现以及讲解。 2 四种分配方式 2.1 概念 操作系统中有一个...
  • fn(离散时间)和时间限制(int),应找到最大输出,即在不同函数之间分配时间以最大化所用函数输出的总和。对于任何函数,任何时候的值表示如果用于所述时间的函数的总输出。 即F(2)=函数的总输出,如果使用2秒。 不是...
  • 操作系统进程调度和内存分配算法可视化模拟,java,idea 支持的算法: 先来先服务,时间片轮转,优先级调度 首次适应,最佳适应,最坏适应
  • 垃圾回收(GarbageCollection,GC)是Java不同于c与c++的重要特性之一。他帮助Java自动清空堆中不再使用的对象。由于不需要手动释放内存,程序员在编程中也可以减少犯错的机会。利用垃圾回收,程序员可以避免一些指针和...
  • 内存的作用 内存是计算机的一个重要组成部分,它的主要作用在于配合 CPU 的高速运转,使得计算机的运行速度得到大大地提升 我们应该知道,计算机上的一切都是程序,我们使用计算机其实就是在运行计算机上的各种...
  • 这篇文章主要讲Java内存分配与回收机制,主要包括Java运行时的数据区域、对象的创建、垃圾收集算法与回收策略一.运行时数据区域下图是Java虚拟机运行时的内存示意图:从图中我们可以看到Java内存总共分为6个部分:...
  • 1 概述 本文是利用Java实现操作系统中的四种动态内存分配方式 ,分别是:BFNFWFFF分两部分,第一部分是介绍四种分配方式的概念以及例子,第二部分是代码实现以及讲解。2 四种分配方式2.1 概念操作系统中有一个动态...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,074
精华内容 1,229
关键字:

内存分配算法java

java 订阅