-
2021-03-06 02:11:32
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("------------------------------------");
}
}
更多相关内容 -
操作系统-动态分区分配算法-JAVA版
2020-01-08 15:44:21操作系统实验的动态分区分配算法java版本的，功能实现。包括分配回收机制，和判断空间是否够，然后再分配，回收利用的情况。 -
存储管理——动态分区分配算法
2020-12-13 23:00:26操作系统课设做的动态分区分配算法。第一次上传资源，做的有些乱，献丑了，其中循环首次循环和最佳、最坏分配算法其实只是从首次适应算法改了一点东西。 补充几句，是JAVA做的，分配和回收算法都有，使用数组实现 -
操作系统动态分区分配算法java版.pdf
2021-10-07 13:30:09操作系统动态分区分配算法java版.pdf -
操作系统之动态分区分配算法 （java）
2021-11-25 22:45:42通过实验加强对基于顺序搜索的动态分区分配算法的理解和掌握。 加深理解有关存储结构的概念。 主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间...展开全文（实验目的、实验原理、实验步骤、内容、程序代码、实验数据、结论等）
1.实验目的
详细了解系统之中是如何存储进程的。 通过实验加强对基于顺序搜索的动态分区分配算法的理解和掌握。 加深理解有关存储结构的概念。 主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
2.实验要求
代码实现四种算法
撰写课程设计报告 报告要有设计、实现、测试等过程。
3.实验过程描述
原理（思路）
态分区分配是根据进程的实际需要，动态地址为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。 在本实验中运用了四种分配算法，分别是首次适应算法，循环首次适应算法，最坏适应算法，最佳适应算法。4.实验代码
package 实验三; import java.util.Arrays; import java.util.Scanner; public class DpAllocation { static process[] processS = {new process(0, 2, 20), new process(3, 7, 10), new process(6, 8, 15), new process(9, 4, 15), new process(12, 4, 15), new process(15, 1, 10)}; static int Can_space = 0;//可用空间 static int[][] Current = new int[0][0];//当前空间内元素 public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("请输入可用空间数"); Can_space = in.nextInt(); int n = -1; System.out.println("请输入选择 1: 首次适应 2：循环首次适应 3：最坏适应算法 4：最佳适应算法"); n = in.nextInt(); switch (n) { case 0: break; case 1: First_Fit(); break; case 2: Next_Fit(); break; case 3: Worst_Fit(); break; case 4: Best_Fit(); break; default: System.out.println("无效输入"); } } private static void First_Fit() { int Current_time = 0; for (int i = 0; i < processS.length; i++) {//开始输入所有进程 Current_time = processS[i].inputTime;//获取当前时间 for (int j = Current.length - 1; j >= 0; j--) {//时间之前的全部消失 if (Current[j][3] + processS[Current[j][2]].runTime <= Current_time) { Current = Delete(j); } } if (Current.length == 0) { if (Can_space >= processS[i].space) Current = add(0, processS[i].space, i, processS[i].inputTime, 0); printprocess(Current_time); } else { int Begin = 0;//开始空间 int space = 0;//可用空间 for (int j = 0; j <= Current.length; j++) {//开始空间 结束空间 占用进程 输入时间 if (j == Current.length) { space = Can_space - Current[j - 1][1]; } else { space = Current[j][0] - Begin; } if (space >= processS[i].space) { Current = add(Begin, Begin + processS[i].space, i, Current_time, j); printprocess(Current_time); break; } if (j != Current.length) { Begin = Current[j][1]; } } } } } private static void Next_Fit() { int Current_time = 0; for (int i = 0; i < processS.length; i++) {//开始输入所有进程 Current_time = processS[i].inputTime;//获取当前时间 for (int j = Current.length - 1; j >= 0; j--) {//时间之前的全部消失 if (Current[j][3] + processS[Current[j][2]].runTime <= Current_time) { Current = Delete(j); } } if (Current.length == 0) { if (Can_space >= processS[i].space) Current = add(0, processS[i].space, i, processS[i].inputTime, 0); printprocess(Current_time); } else { int Begin = Current[Current.length - 1][1];//开始空间 int space = 0;//可用空间 boolean be = true; for (int j = Current.length; j <= Current.length; j++) {//开始空间 结束空间 占用进程 输入时间 if (j == Current.length) { space = Can_space - Current[j - 1][1]; } else { space = Current[j][0] - Begin; } if (space >= processS[i].space) { Current = add(Begin, Begin + processS[i].space, i, Current_time, j); printprocess(Current_time); break; } if (j != Current.length) { Begin = Current[j][1]; } if (j == Current.length && be) { be = false; Begin = 0; j = -1; } } } } } private static void Worst_Fit() { int Current_time = 0; for (int i = 0; i < processS.length; i++) {//开始输入所有进程 Current_time = processS[i].inputTime;//获取当前时间 for (int j = Current.length - 1; j >= 0; j--) {//时间之前的全部消失 if (Current[j][3] + processS[Current[j][2]].runTime <= Current_time) { Current = Delete(j); } } if (Current.length == 0) { if (Can_space >= processS[i].space) Current = add(0, processS[i].space, i, processS[i].inputTime, 0); printprocess(Current_time); } else { int danqiangBegin = 0;//开始空间 int danqiangspace = 0;//当前空间 int index = -1; int Begin = 0;//开始空间 int space = 0;//可用空间 for (int j = 0; j <= Current.length; j++) {//开始空间 结束空间 占用进程 输入时间 if (j == Current.length) { space = Can_space - Current[j - 1][1]; } else { space = Current[j][0] - Begin; } if (space >= processS[i].space && space > danqiangspace) { index = j; danqiangspace = space; danqiangBegin = Begin; } if (j != Current.length) { Begin = Current[j][1]; } } if (index != -1) { Current = add(danqiangBegin, danqiangBegin + processS[i].space, i, Current_time, index); printprocess(Current_time); } } } } private static void Best_Fit() { int Current_time = 0; for (int i = 0; i < processS.length; i++) {//开始输入所有进程 Current_time = processS[i].inputTime;//获取当前时间 for (int j = Current.length - 1; j >= 0; j--) {//时间之前的全部消失 if (Current[j][3] + processS[Current[j][2]].runTime <= Current_time) { Current = Delete(j); } } if (Current.length == 0) { if (Can_space >= processS[i].space) Current = add(0, processS[i].space, i, processS[i].inputTime, 0); printprocess(Current_time); } else { int danqiangBegin = 0;//开始空间 int danqiangspace = -1;//当前空间 int index = -1; int Begin = 0;//开始空间 int space = 0;//可用空间 for (int j = 0; j <= Current.length; j++) {//开始空间 结束空间 占用进程 输入时间 if (j == Current.length) { space = Can_space - Current[j - 1][1]; } else { space = Current[j][0] - Begin; } if (space >= processS[i].space && (danqiangspace == -1 || space < danqiangspace)) { index = j; danqiangspace = space; danqiangBegin = Begin; } if (j != Current.length) { Begin = Current[j][1]; } } if (index != -1) { Current = add(danqiangBegin, danqiangBegin + processS[i].space, i, Current_time, index); printprocess(Current_time); } } } } private static int[][] add(int begin, int end, int j, int run, int index0) { int[][] copy = new int[Current.length + 1][]; int index = 0; if (0 == index0) { copy[index++] = new int[]{begin, end, j, run}; for (int i = 0; i < Current.length; i++) { copy[index++] = Current[i]; } return copy; } index = 0; for (int i = 0; i < Current.length; ) { copy[index++] = Current[i]; i++; if (i == index0) { copy[index++] = new int[]{begin, end, j, run}; } } return copy; } private static int[][] Delete(int j) { int[][] copy = new int[Current.length - 1][]; int index = 0; for (int i = 0; i < Current.length; i++) { if (i != j) { copy[index++] = Current[i]; } } return copy; } private static void printprocess(int time) { System.out.println("当前时间为" + time); System.out.println("开始空间 结束空间 占用进程 输入时间"); for (int[] i : Current) { System.out.println(" " + i[0] + " " + i[1] + " " + processS[i[2]].processname + " " + i[3]); } } }辅助类
package 实验三; public class process { int inputTime ;//输入时间 int runTime;//运行时间 int space;//空间 static int name=0; String processname; boolean bool=false; public process(int inputTime, int runTime, int space) { this.inputTime = inputTime; this.runTime = runTime; this.space = space; processname="进程"+name++; } }5.实验结果
上一个操作系统之 银行家算法（java）
下一个操作系统之LRU算法（java）如果本文章对你有用 记得点赞哦 (￣∇￣)
-
操作系统——实验五 动态分区分配算法的模拟
2020-08-05 10:41:39用C/C++实现一个完整的（可变）动态分区管理器，包括分配，回收，分区碎片整理等。希望同学们实现如下功能： 初始化功能：内存状态设置为初始状态。 分配功能：要求至少使用两种算法，用户可以选择使用。 回收... -
存储管理——动态分区分配算法的模拟
2018-09-14 16:14:26存储管理——动态分区分配算法的模拟 要求设计主界面以灵活选择某算法，以下算法都要实现： a、首次适应算法 b、循环首次适应算法 c、最佳适应算法 d、最坏适应算法 e、快速适应算法 具体要求： 1）首先由... -
动态重定位分区分配算法设计实现论文.pdf
2020-07-03 22:34:34移动某些已分配区的内容，使所有进程的分区紧凑在一起，而把空闲分区留在另一端。这种技术称为紧凑（或拼接）。采用紧凑技术的可变分区法称为动态可重定位分区法。该论文为学校学期期末小论文，格式并非标准论文格式... -
Java实现操作系统中四种动态内存分配算法：BF+NF+WF+FF
2021-03-04 07:05:482 四种分配方式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 源码
如果觉得文章好看，欢迎点赞。
同时欢迎关注微信公众号：氷泠之路。
-
动态分区分配--最先适应分配算法
2021-03-06 13:31:07可变分区调度算法有:最先适应分配算法,最优适应分配算法,最坏适应算法。用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序...展开全文可变分区调度算法有:
最先适应分配算法,最优适应分配算法,最坏适应算法。
用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。
每当一个进程被创建时，内存分配程序首先要查找空闲内存分区表(链)，从中寻找一个合适的空闲块进行划分，并修改空闲内存分区表(链)。当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区表(链)中找到相应的插入点，此时出现如下四种情况：
1) 回收区与插入点的前一个空闲分区F1相邻接，此时可将回收区直接与F1合并，并修改F1的大小；
2) 回收区与插入点的后一个空闲分区F2相邻接，此时可将回收区直接与F2合并，并用回收区的首址最为新空闲区的首址，大小为二者之和；
3) 回收区同时与插入点的前、后两个空闲分区邻接，此时需将三者合并；
4) 回收区不与任何一个空闲区邻接，此时应建一新的表项。
首先我们的构建一个分区表，及其相关操作，代码如下:
package 动态分区分配;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
public class Partition implements Comparable{
private int PartitionSize; //分区大小
private int StartLocation; //分区起始地址
private boolean IsBusy; //状态
public Partition(int partitionSize, int startLocation, boolean isBusy) {
super();
PartitionSize = partitionSize;
StartLocation = startLocation;
IsBusy = isBusy;
}
public int getPartitionSize() {
return PartitionSize;
}
public void setPartitionSize(int partitionSize) {
PartitionSize = partitionSize;
}
public boolean isIsBusy() {
return IsBusy;
}
public void setIsBusy(boolean isBusy) {
IsBusy = isBusy;
}
public int getStartLocation() {
return StartLocation;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + StartLocation;
return result;
}
@Override
public int compareTo(Partition arg0) {
// TODO Auto-generated method stub
if ( this.StartLocation < arg0.StartLocation)
return -1;
else if ( this.StartLocation > arg0.StartLocation)
return 1;
return 0;
}
public void setStartLocation(int startLocation) {
StartLocation = startLocation;
}
public void Print(){
System.out.print(this.PartitionSize+" "+this.StartLocation+" ");
if (this.isIsBusy()){
System.out.println("忙碌");
}else{
System.out.println("空闲");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("请初始化空闲分区表[分区大小(KB)和分区起始地址(K)]:");
TreeSet partition = new TreeSet();
for ( int i = 0 ; i < 5 ; i++){
int partitionSize = in.nextInt();
int startLocation = in.nextInt();
partition.add(new Partition(partitionSize, startLocation, false));
}
Iterator it = partition.iterator();
int cnt = 1; //分区号
System.out.println("分区号"+" "+"分区大小(KB)"+" "+"分区起始地址(K)"+" "+"状态");
while ( it.hasNext()){
Partition p = it.next();
System.out.print(cnt+" ");
p.Print();
cnt++;
}
in.close();
}
}
之后开始设计最先适应分配算法,代码如下:
package 动态分区分配;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
public class FirstFit {
private ArrayList partition = new ArrayList();
public FirstFit(TreeSet partition) { //构造方法
Iterator it = partition.iterator();
while(it.hasNext()){
Partition p = it.next();
this.partition.add(p);
}
}
public ArrayList getPartition() {
return partition;
}
public void CarryOut_FirstFit(int[] process){ //执行最先适应算法
int index = 0;
int cnt = 0;
while( cnt < process.length){
Partition p = this.getPartition().get(index);
if ( p.getPartitionSize() >= process[cnt]){
p.setIsBusy(true);
int restsize = p.getPartitionSize() - process[cnt];
p.setPartitionSize(process[cnt]);
if ( index == 0){
Partition after = this.getPartition().get(index+1);
if ( after.isIsBusy() == false ){
after.setPartitionSize(after.getPartitionSize()+restsize);
after.setStartLocation(p.getStartLocation()+p.getPartitionSize()+1);
cnt++;
index++;
}
}else if ( index == this.getPartition().size() - 1){
Partition before = this.getPartition().get(index-1);
if ( before.isIsBusy() == false){
before.setPartitionSize(before.getPartitionSize()+restsize);
before.setStartLocation(p.getStartLocation()+p.getPartitionSize()+1);
cnt++;
index++;
}
}else{
Partition after = this.getPartition().get(index+1);
Partition before1 = this.getPartition().get(index-1);
if ( before1.isIsBusy() == false){
before1.setPartitionSize(before1.getPartitionSize()+restsize);
before1.setStartLocation(p.getStartLocation()+p.getPartitionSize()+1);
cnt++;
index++;
continue;
}else if ( after.isIsBusy() == false ){
after.setPartitionSize(after.getPartitionSize()+restsize);
after.setStartLocation(p.getStartLocation()+p.getPartitionSize()+1);
cnt++;
index++;
continue;
}
}
}else{
continue;
}
}
}
public void Print(){ //打印
System.out.println("分区号"+" "+"分区大小(KB)"+" "+"分区起始地址(K)"+" "+"状态");
Iterator it = this.getPartition().iterator();
int cnt = 1;
while ( it.hasNext()){
Partition tmp = it.next();
System.out.print(cnt+" ");
tmp.Print();
cnt++;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("请输入分区数:");
int cnt = in.nextInt();
TreeSet p = new TreeSet();
System.out.println("开始初始化分区表:");
for ( int i = 0 ; i < cnt ; i++){
int partitionSize = in.nextInt();
int startLocation = in.nextInt();
p.add(new Partition(partitionSize, startLocation, false));
}
FirstFit firstfit = new FirstFit(p);
int[] process = new int[2];
System.out.println(" 开始执行最先适应算法");
System.out.println("请输入进程需分配的内存空间:");
for ( int i = 0 ; i < 2 ; i++){
process[i] = in.nextInt();
}
System.out.println("进行动态分配前空闲分区表为:");
firstfit.Print();
firstfit.CarryOut_FirstFit(process);
System.out.println("进行动态分配后空闲分区表为:");
firstfit.Print();
in.close();
}
}
本文分享 CSDN - 追梦者_AIer。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
-
操作系统 动态分区分配 Java 实现
2021-11-14 21:20:49操作系统 动态分区分配 Java 实现 1. 分配算法原理 操作系统 动态分区分配 2. 代码实现 package dynamicMemoAlloc; class Block{ private int id; // id == -1 表示空闲分区 private int begin; private int ... -
操作系统-（动态分区算法java实现）
2021-05-07 16:09:381、 分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。 2、 分区的初始化——可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始... -
操作系统动态分区分配算法课程设计java版解析.doc
2021-03-10 07:30:42湖 南 文 理 学 院 实 验 报 告课程名称 操作系统课程设计实验名称 存储管理——动态分区分配算法的模拟成绩学生姓名 曹乐 专业 计算机班级、学号 13101 18同组者姓名实验日期 12.21实验目的通过这次实验，加深对... -
操作系统 动态分区分配算法课程设计 java版.pdf
2021-03-06 13:31:22操作系统 动态分区分配算法课程设计 java版湖 南 文 理 学 院 实 验 报 告课程名称 操作系统课程设计实验名称 存储管理——动态分区分配算法的模拟成绩学生姓名 曹乐 专业 计算机班级、学号 13101 18同组者姓名实验... -
操作系统：动态分区分配方式的模拟（Java实现）
2020-06-02 16:21:15分析操作系统的核心功能模块，理解相关功能模块实现的数据结构和算法， 并加以实现，加深对操作系统原理和实现过程的理解。 二、实验内容： 多级反馈队列调度的模拟。 本算法设置了三个优先级从高到低的队列，... -
基于索引搜索的动态分区分配算法
2018-09-11 09:35:50为了提高搜索空间的分区的速度，在中大型系统中往往会采用基于索引搜索的动态分区分配算法，比如我们所熟知的哈希算法、快速适应算法以及伙伴系统。 1）哈希算法 由于分类搜索算法和伙伴系统算法中，都是将空闲... -
基于顺序搜索的动态分区分配算法
2017-11-17 21:20:49从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分... -
动态分区分配(java) 操作系统实验
2021-11-15 13:47:16四种方法就不多介绍了，别的可以看，只是学生作品记录，做的地方还有许多不足 1.比如说当剩余空间Space的start = end相等时...import java.util.*; public class Memory { public static void main(String[] args) { -
操作系统课程设计之存储管理—动态分区分配算法的模拟
2011-07-09 22:28:37课题八:存储管理---动态分区分配算法的模拟： 要求设计主界面以灵活选择某算法，且以下算法都要实现：首次适应算法、循环首次适应算法、最佳适应算法； -
操作系统_动态分区分配算法课程设计_java版
2021-04-17 09:19:08《操作系统_动态分区分配算法课程设计_java版》由会员分享，可在线阅读，更多相关《操作系统_动态分区分配算法课程设计_java版(13页珍藏版)》请在人人文库网上搜索。1、湖 南 文 理 学 院 实 验 报 告课程名称 操作... -
基于顺序搜索的动态分区分配算法模拟内存动态分配--最佳适应算法（best fit,BF）
2018-06-27 05:29:32分别是数据结构、分区分配算法、分区的分配与回收操作。 首数据结构 这里我们使用的是空闲分区链，采用双向链表表示空闲分区。 具体实现如下： typedef struct LNode{ int order; //表示内存块的顺序 int ... -
操作系统动态分区存储器管理 java实现
2020-12-21 13:04:38➢分配(输入一个进程名和所需内存大小，按某种分配算法进行分配，输出分配情况;如不能分配，说明原因)➢回收(输入一个进程名，回收其占用的存储空间) ➢输出内存分配情况( 输出内存分配表) ➢退出 -
存储器管理——基于顺序搜索的动态分区分配算法
2020-06-23 17:03:46基于顺序搜索的动态的分区分配算法有如下四种：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法。 1.首次造应(first fif. FF)算法 我们以空闲分区链为例来说明采取FF算法时的分配情况。FF算法要求空闲... -
java模拟操作系统的动态分区首次适应分配和回收算法
2021-12-17 18:04:34java模拟操作系统的动态分区首次适应分配和回收算法 -
[操作系统]内存动态分区分配算法
2020-12-30 19:27:00首次适应算法每次从低地址开始查找,找到第一个能满足大小的空闲分区,顺序查找空闲分区链或者空闲分区表 最佳适应算法(最小分配)按照容量递增从小到大的顺序查找,每次分配内存按前面顺序查找,找到第一个合适的,会留下...
java
订阅