操作系统:动态分区分配方式的模拟(Java实现) |
您所在的位置:网站首页 › java动态分配内存 › 操作系统:动态分区分配方式的模拟(Java实现) |
一、实验目的:
了解动态分区分配方式中的数据结构和分配算法,
并进一步加深对动态分区存储管理方式及其实现过程的理解。
二、实验内容:
用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中,空闲分区通过空闲分区链(表)来管理;在进行内存分配时,系统优先使用空闲区低端的空间。假设初始状态下,可用的内存空间为640KB,并有下列的请求序列: •作业1申请130KB •作业2申请60KB •作业3申请100KB •作业2释放60KB •作业4申请200KB •作业3释放100KB •作业1释放130KB •作业5申请140KB •作业6申请60KB •作业7申请50KB •作业8申请60KB 分别采用首次适应算法和最佳适应算法进行内存的分配和回收,要求每次分配和回收后显示出空闲内存分区链的情况。
三、实现思路:
采用java的ArrayList数据结构存储自定义分区类Block的实例对象分区作为分区链。根据最先适应/最佳适应的思想为作业分配内存(改变内存属性大小、当前作业id、分配始址等),并根据实际情况来释放或合并Block对象的空间属性大小。
四、主要的数据结构:
//ArrayList 分区链
private static List blockList = new ArrayList();
/**
* 自定义Block类,分区
*/
private static class Block {
int address; //分区首地址
int size; //分区大小
int id; //进程id
}
五、程序流程图:
最先适应算法FF: 最佳适应算法BF:
六、算法关键代码:
/** 最先适应算法FF
* 寻找空闲分区并为新作业分配空间
* @param id
* @param size
*/
private static boolean allocation(int id, int size){
//分配成功与否的标志
boolean flag = false;
int blockAddress = 0;
int blockSize = 0;
int blockId = 0;
/*顺序遍历所有分区*/
for(int i = 0; i
blockList.get(i).id = id;
blockList.get(i).size = size;
/*若当前分区重新分配后有剩余内存,
则将其作为新的分区并设置新的address 和 size*/
if (blockSize > size) {
FirstFit.Block newBlock = new Block();
newBlock.id = -1;
newBlock.address = blockAddress + size;
newBlock.size = blockSize - size;
blockList.add(i + 1, newBlock);
}
flag = true;
break;
}
}
//返回分配结果
return flag;
}
/** 最佳适应算法BF
* 寻找空闲分区并为新作业分配空间
* @param id
* @param size
*/
private static boolean allocation(int id, int size){
//分配成功与否的标志
boolean flag = false;
int blockAddress = 0;
int blockSize = 0;
int blockId = 0;
//标记最佳分区的位置
int mark = 0;
int min = 0;
int count = 0;
/*顺序遍历所有分区*/
for(int i = 0; i
count++;
if(count == 1) {
min = blockSize - size;
mark = i;
}else if(count > 1) {
if (min > blockSize - size) {
min = blockSize - size;
mark = i;
}
}
flag = true;
}
}
if(flag) {
blockAddress = blockList.get(mark).address;
blockSize = blockList.get(mark).size;
blockList.get(mark).id = id;
blockList.get(mark).size = size;
/*若当前分区重新分配后有剩余内存,
则将其作为新的分区并设置新的address 和 size*/
if (blockSize > size) {
BestFit.Block newBlock = new BestFit.Block();
newBlock.id = -1;
newBlock.address = blockAddress + size;
newBlock.size = blockSize - size;
blockList.add(mark + 1, newBlock);
}
}
//返回分配结果
return flag;
}
/** FF与BF二者共用的内存释放算法
* 释放内存并合并空闲分区
* @param id
*/
public static boolean release(List block_List, int id) {
//释放成功与否的标志
block_List = blockList;
boolean flag = false;
int blockId = 0;
int blockSize = 0;
for(int i = 0; i
block_List.get(i).id = -1;
/*当分区为第一个时*/
if(i == 0){
//若与之相邻下一个分区空闲
if (block_List.get(i + 1).id == -1) {
/*更新本分区的size并删除下一分区*/
block_List.get(i).size += block_List.get(i + 1).size;
block_List.remove(i + 1);
}
}
/*当分区不是第一个也不是最后一个*/
else if(i
/*更新上一分区的size并删除本分区*/
block_List.get(i - 1).size += block_List.get(i).size;
block_List.remove(i);
}
//若与之相邻下一个分区空闲且上一分区不空闲
else if (block_List.get(i + 1).id == -1 && block_List.get(i - 1).id != -1) {
/*更新本分区的size并删除下一分区*/
block_List.get(i).size += block_List.get(i + 1).size;
block_List.remove(i + 1);
}
//若与之相邻上下分区都空闲
else if (block_List.get(i - 1).id == -1 && block_List.get(i + 1).id == -1) {
/*更新上一分区的size并删除本、下一分区*/
block_List.get(i - 1).size += blockSize;
block_List.get(i - 1).size += block_List.get(i + 1).size;
block_List.remove(i);
block_List.remove(i);
}
}
/*当分区为最后一个分区时*/
else if(i == blockList.size() - 1){
//若与之相邻上一个分区空闲
if (blockList.get(i - 1).id == -1) {
/*更新上一分区的size并删除本分区*/
blockList.get(i - 1).size += blockList.get(i).size;
blockList.remove(i);
}
}
flag = true;
break;
}
}
return flag;
}
七、运行测试:
测试数据: 最先适应算法FF: 可以看出运行结果体现出了“最先适应”的思想,并且正确实现了内存回收和分区合并。 最佳适应算法BF: 可以看出运行结果体现出了“最佳适应”的思想,并且正确实现了内存回收和分区合并。 八、总结:在这次实验中,我经历了多次debug的过程,使得我对于算法的思想策略了解的更加明彻。最终达到想要的效果后,我觉得其实操作系统的一些算法只要理解了就不难实现。这也使我更加喜爱操作系统这门课程。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |