-
2021-02-06 12:20:34
动态分区分配是根据进程的实际需要,动态地址为之分配内存空间,在分配时按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业
-
1.首次适应算法(FF):将所有空闲分区按照地址递增的次序链接,在申请内存分配时,从链首开始查找,将满足需求的第一个空闲分区分配给作业。
-
2.循环首次适应算法(NF):将所有空闲分区按照地址递增的次序链接,在申请内存分配时,总是从上次找到的空闲分区的下一个空闲分区开始查找,将满足需求的第一个空闲分区分配给作业
-
3.最坏适应算法(WF):将所有的空闲分区按照从大到小的顺序形成空闲分区链,在申请内存分配时,总是把满足需求的、最大的空闲分区分配给作业。
-
4.最佳适应算法(BF): 将所有空闲分区按照从小到大的顺序形成空闲分区链,在申请内存分配时,总是把满足需求的、最小的空闲分区分配给作业。
源码
#include <iostream> #include <fstream> #include <iomanip> using namespace std; #define MAXNUMBER 100 static int PartitionNum; //内存中空闲分区的个数 static int ProcessNum; //需要分配的进程个数 static int FreePartition[MAXNUMBER]; //空闲分区对应的内存 static int ProcessNeed[MAXNUMBER]; //需要分配的进程大小 static int LeftFreePartition[MAXNUMBER]; static int LeftProcessNeed[MAXNUMBER]; static char ProcessName[MAXNUMBER]; static char NameProcessToPartition[MAXNUMBER][MAXNUMBER]; typedef struct { int partitionSize; int id; }sortNeed; void readDataFunction(); void input(); void display(); void FirstFit(); void NextFit(); void BestFit(); void WorstFit(); void selectAlgorithm(int chooceAlgorithm); void display(); void readDataFunction() { cout<<"请输入空闲分区数"<<endl; cin >> PartitionNum; cout << "请输入空闲分区大小" << endl; for (int i = 0; i<PartitionNum; i++) { cin >> FreePartition[i]; } cout<<"请输入进程个数"<<endl; cin >> ProcessNum; cout<<"请输入进程名称"<<endl; for (int i = 0; i<ProcessNum; i++) { cin >> ProcessName[i]; } cout<<"请输入进程需要分配大小"<<endl; for (int i = 0; i<ProcessNum; i++) { cin >> ProcessNeed[i]; } } void input() { int chooseAlgorithm = 5; do { //readDataFunction(); cout << "请选择实现的算法:" << endl; cout << "***** 1 - 首次适应算法 *****" << endl; cout << "***** 2 - 循环首次适应算法 *****" << endl; cout << "***** 3 - 最佳适应算法 *****" << endl; cout << "***** 4 - 最坏适应算法 *****" << endl; cout << "***** 0 - 结束 *****" << endl; cout << "chooseAlgorithm = "; cin >> chooseAlgorithm; selectAlgorithm(chooseAlgorithm); //display(); } while (chooseAlgorithm); } void initial() { readDataFunction(); //读取原始数据 for (int i = 0; i<PartitionNum; i++) { LeftFreePartition[i] = FreePartition[i]; for (int j = 0; j<ProcessNum; j++) { NameProcessToPartition[i][j] = NULL; } } for (int i = 0; i<ProcessNum; i++) { LeftProcessNeed[i] = ProcessNeed[i]; } } void FirstFit() { cout << "***********首次适应算法***********" << endl; initial(); int i, j; for (i = 0; i<ProcessNum; i++) //逐个遍历每个进程 { for (j = 0; j<PartitionNum; j++) { if (LeftProcessNeed[i] <= LeftFreePartition[j] && LeftFreePartition != 0) //当系统内存分区足够大的时候,即分配给进程资源 { LeftFreePartition[j] -= LeftProcessNeed[i]; //扣除分配给进程的资源 LeftProcessNeed[i] = 0; //当且仅当系统内存分区足够时才执行,即当前进程大小置0 NameProcessToPartition[i][j] = ProcessName[i]; //存储各个进程所在的分区位置 break; //!!!很重要,一个进程分区完后,应该立即break,进行下一个进程的判断 } } } display(); } void NextFit() { cout << "***********循环首次适应算法***********" << endl; initial(); int i, nextPoint = 0; bool isWhile; for (i = 0; i<ProcessNum; i++) { isWhile = true; while (isWhile) { if (LeftFreePartition[nextPoint] >= LeftProcessNeed[i]) { LeftFreePartition[nextPoint] -= LeftProcessNeed[i]; LeftProcessNeed[i] = 0; NameProcessToPartition[i][nextPoint] = ProcessName[i]; nextPoint++; if (nextPoint > PartitionNum - 1) { nextPoint = 0; //当j遍历到分区末尾的时候,返回首位置 } isWhile = false; } else nextPoint++; } } display(); } void BestFit() { //思想:利用冒泡排序对分区大小进行排序,但不改变原分区的位置 //创建一个结构体,包括分区大小和所对应的id,排序过程中,每改变顺序一次,id随着改变 //关键:每次分配完一个进程的内存大小后,都要重新排序 cout << "***********最佳适应算法***********" << endl; initial(); int i, j, temp, tempID; sortNeed best[MAXNUMBER]; for (i = 0; i<PartitionNum; i++) { //初始化结构体 best[i].partitionSize = FreePartition[i]; best[i].id = i; } for (i = 0; i<ProcessNum; i++) { for (int s = PartitionNum - 1; s > 0; s--) //冒泡排序(每次分配完一个进程后,都需要重新排序) { for (int t = 0; t < s; t++) { if (best[s].partitionSize < best[t].partitionSize) { temp = best[s].partitionSize; best[s].partitionSize = best[t].partitionSize; best[t].partitionSize = temp; tempID = best[s].id; best[s].id = best[t].id; best[t].id = tempID; } } } for (j = 0; j<PartitionNum; j++) { if (LeftProcessNeed[i] <= best[j].partitionSize) { best[j].partitionSize -= LeftProcessNeed[i]; LeftProcessNeed[i] = 0; NameProcessToPartition[i][best[j].id] = ProcessName[i]; break; } } LeftFreePartition[best[j].id] = best[j].partitionSize; } display(); } void WorstFit() { cout << "***********最坏适应算法***********" << endl; initial(); int i, j, s, t, tempSize, tempID; sortNeed Worst[MAXNUMBER]; for (i = 0; i<PartitionNum; i++) { Worst[i].partitionSize = FreePartition[i]; Worst[i].id = i; } for (i = 0; i<ProcessNum; i++) { for (s = PartitionNum - 1; s>0; s--) { for (t = 0; t<s; t++) { if (Worst[s].partitionSize > Worst[t].partitionSize) { tempSize = Worst[s].partitionSize; Worst[s].partitionSize = Worst[t].partitionSize; Worst[t].partitionSize = tempSize; tempID = Worst[s].id; Worst[s].id = Worst[t].id; Worst[t].id = tempID; } } } for (j = 0; j<PartitionNum; j++) { if (LeftProcessNeed[i] <= Worst[j].partitionSize) { Worst[j].partitionSize -= LeftProcessNeed[i]; LeftProcessNeed[j] = 0; NameProcessToPartition[i][Worst[j].id] = ProcessName[i]; break; } } LeftFreePartition[Worst[j].id] = Worst[j].partitionSize; } display(); } void selectAlgorithm(int chooseAlgorithm) { switch (chooseAlgorithm) { case 0:break; case 1:FirstFit(); break; case 2:NextFit(); break; case 3:BestFit(); break; case 4:WorstFit(); break; default:cout << "请输入正确的序号:" << endl; } } void display() { int i; cout << "需要分配内存的进程名:" << setw(10); for (i = 0; i<ProcessNum; i++) { cout << ProcessName[i] << setw(6); } cout << endl; cout << "需要分配内存的进程分区大小:" << setw(4); for (i = 0; i<ProcessNum; i++) { cout << ProcessNeed[i] << setw(6); } cout << endl; cout << "分配结果:" << endl; cout << "分区序号:"; for (i = 0; i<PartitionNum; i++) { cout << "分区" << i + 1 << " "; } cout << endl << "分区大小:"; for (i = 0; i<PartitionNum; i++) { cout << FreePartition[i] << " "; } cout << endl << "剩余大小: "; for (i = 0; i<PartitionNum; i++) { cout << LeftFreePartition[i] << " "; } cout << endl << "分配进程情况:" << endl; for (i = 0; i<PartitionNum; i++) { for (int j = 0; j<ProcessNum; j++) { if (NameProcessToPartition[j][i] != NULL) { cout << NameProcessToPartition[j][i] << ": (分区" << i + 1 << ")" << endl; } } //cout<<" "; } cout << endl << "********结束**********" << endl; } int main() { input(); return 0; }
更多相关内容 -
-
嵌入式动态内存分配算法tlsf
2019-09-09 15:58:28TLSF是一种动态内存分配算法,本资源是C语言的编写的,包含例程。 -
动态内存分配算法实验报告.doc
2020-11-04 20:30:39动 态 内 存 分 配 算 法 实 验 报 告 院系:计算机与通信工程学院 班级:计科08-1班 姓名:胡太祥 学号:200807010112 一实验题目动态内存分配算法 二实验目的 深入了解动态分区存储管理方式内存分配与回收的实现 三... -
TLSF动态内存分配算法的研究与应用
2020-07-25 02:26:42详细介绍了TLSF(Two Level Segregated Fit)动态内存分配算法的实现过程,包括内存池的创建初始化、动态内存的分配与释放。把TLSF移植到μC/OSII实时操作系统上,移植后的系统在基于CortexM3内核的LPC1768处理器上... -
动态内存分配算法(详解加代码)
2019-12-12 17:28:22动态内存分配主要有四种算法: (1) 首次适应算法:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。 (2) 循环首次适应算法:首次适应算法每次要从头找,增加了查找的开销,也可能在低地 址上产生难以利用...动态内存分配主要有四种算法:
(1) 首次适应算法:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。
(2) 循环首次适应算法:首次适应算法每次要从头找,增加了查找的开销,也可能在低地
址上产生难以利用的小碎片。循环首次适应算法从上一次结束的位置开始查找。
(3) 最佳适应算法:为了保证当“大进程”到来时能有连续的大片空间,可以尽可能的多
留下大片空闲区,即,优先使用更小的空闲区。
(4) 最坏适应算法:为了解决最佳适应算法的问题——留下太多难以利用的小碎片。可以优先使用最大的连续空闲区。各自的优缺点:
(1) 首次适应算法:综合看性能最好。算法开销小,回收分区后一般不需要对空闲分区队列重新排序。
(2) 循环首次适应算法:不用每次都从低地址的小分区开始检索。算法开销小,但会使高地址的大分区也被用完。
(3) 最佳适应算法:会有更多的大分区被保留下来,更能满足大进程的需求。但会产生很多太小的、难以利用的碎片;算法开销大,回收分区后可能需要对空闲分区队列重新排序。
(4) 最坏适应算法:可以减少难以利用的小碎片。但大分区容易被利用完,不利于大进程,算法开销大。这里我们说说代码的构造:
你要有一个分区块的类,用来保存分区块的起始地址,大小,和状态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; } }
之外嵌套我们的主类:
private int size; //总内存大小 private LinkedList<Zone> zones; //保存内存分区 private int pointer; //上次分配的空闲区位置
代码逻辑图:
1、我们先初始化内存的大小
2、进入主界面- 输入作业
- 回收内存
- 显示分区
3、输入作业后,先输入大小,然后选择分配的算法
- 首次适应算法
- 循环首次算法
- 最佳适应算法
- 最坏适应算法
下面是源码阶段:
package Experiment; import java.util.LinkedList; import java.util.Scanner; public class Test2{ private int size; //内存大小 private LinkedList<Zone> 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; } } public Test2(){ this.size = 400; this.pointer = 0; this.zones = new LinkedList<>(); zones.add(new Zone(0, size)); } public Test2(int size) { this.size = size; this.pointer = 0; this.zones = new LinkedList<>(); zones.add(new Zone(0, size)); } private void doAlloc(int size, int location, Zone tmp) { //size 作业大小 location 内存位置 tmp可用空闲区 Zone newHome = new Zone(tmp.head + size, tmp.size - size); //产生一个新空闲区; zones.add(location + 1, newHome);//插入新节点 tmp.size = size; tmp.isFree = false; System.out.println("成功分配 " + size + "KB 内存!"); } public void FirstFit(int size){ //将point赋值为零 从头开始找 for (pointer = 0; pointer < zones.size(); pointer++){ Zone tmp = zones.get(pointer); //找到可用分区(空闲且大小足够) if (tmp.isFree && (tmp.size > size)){ doAlloc(size, pointer, tmp); return; } } //遍历结束后未找到可用分区, 则内存分配失败 System.out.println("无可用内存空间!"); } public void NextFit(int size){ //直接获得上次point位置,开始遍历分区链表 Zone tmp = zones.get(pointer); if (tmp.isFree && (tmp.size > size)){ doAlloc(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)){ doAlloc(size, i, tmp); return; } } //遍历结束后未找到可用分区, 则内存分配失败 System.out.println("无可用内存空间!"); } public 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 { doAlloc(size, flag, zones.get(flag)); } } public 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 { doAlloc(size, flag, zones.get(flag)); } } public void collection(int id){//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 > 0 && zones.get(id - 1).isFree){ Zone fronKuer = zones.get(id - 1); fronKuer.size += tmp.size; zones.remove(id); id--; } //检查后面是否空闲,是则合并 if (id < zones.size() - 1 && zones.get(id + 1).isFree){ Zone nextKuer = zones.get(id + 1);//取到下一个区块 tmp.size += nextKuer.size; zones.remove(nextKuer); } zones.get(id).isFree = true; System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!"); } public void showZones(){//展示内存分区状况 System.out.println("***************************************"); System.out.println("*分区编号 分区始址 分区大小 空闲状态 *"); for (int i = 0; i < zones.size(); i++){ Zone tmp = zones.get(i); System.out.println("* "+i + " " + tmp.head + " " + tmp.size + " " + tmp.isFree+" *"); } System.out.println("****************************************"); } }
这是我们算法的类,下面是调用的类
package Experiment; import java.util.Scanner; public class Main { public static Test2 user; //声明一个用户; public static void Init(){ //初始化内存大小 System.out.println("请输入内存大小(如果输入0,则按默认400分配)"); Scanner scanner=new Scanner(System.in); int choose=scanner.nextInt(); if(choose==0){ user=new Test2(); }else { user=new Test2(choose); } } public static void mainMenu(){ System.out.println("***********************"); System.out.println("* 1.输入作业 *"); System.out.println("* 2.回收内存块 *"); System.out.println("* 3.展示分区情况 *"); System.out.println("* 4.退出系统 *"); System.out.println("***********************"); System.out.println("请输入你要进行的操作:"); } public static void algorithmMenu(int size){ System.out.println("请选择分配算法:"); System.out.println("1.首次适应算法"); System.out.println("2.循环首次算法"); System.out.println("3.最佳适应算法"); System.out.println("4.最坏适应算法"); Scanner in = new Scanner(System.in); int choose = in.nextInt(); switch (choose){ case 1: user.FirstFit(size);break; case 2: user.NextFit(size);break; case 3: user.BestFit(size);break; case 4: user.WorstFit(size);break; default: System.out.println("请重新选择!"); } } public static void main(String[] args) { Init(); //初始化内存条大小 Scanner sc=new Scanner(System.in); while(true){ mainMenu(); //主菜单 int choice=sc.nextInt(); if(choice == 4){ return; }else if(choice == 1){ System.out.println("请输入你要插入的内存块大小"); int length=sc.nextInt(); algorithmMenu(length); }else if(choice==2){ System.out.println("请输入你要回收的分区号码"); int ID=sc.nextInt(); user.collection(ID); }else if(choice == 3){ user.showZones(); }else{ System.out.println("输入错误,请检查"); } } } }
注释写得很清楚,有什么不懂可以私信。
-
Java实现操作系统中四种动态内存分配算法:BF+NF+WF+FF
2020-11-21 17:42:39本文是利用Java实现操作系统中的四种动态内存分配方式 ,分别是: BF NF WF FF 分两部分,第一部分是介绍四种分配方式的概念以及例子,第二部分是代码实现以及讲解。 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<Table> list = new ArrayList<>(); 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 源码
-
动态内存分配(在本实验中运用了四种分配算法)
2022-02-11 10:32:08动态分区分配是根据进程的实际需要,动态地为之分配内存空间,而在分配时,须按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法,分别是1.首次适应算法,2.循环... -
基于μCOS-II的TLSF动态内存分配算法的应用与仿真
2020-10-17 23:05:30以嵌入式实时系统为背景,深入研究了TLSF动态内存分配算法原理及实现过程,并将TLSF移植到μCOS-II中,进行了基于x86平台的仿真测试,取得了很好的效果,为以后学习和应用TLSF算法提供了一种新的方式。 -
操作系统-动态内存分配算法
2019-07-04 20:05:54要求采用一些常用的存储器分配算法,设计一个存储器管理模拟系统并调试运行。 1.2设计要求 用C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中,空闲分区通过空闲...成 绩:
***大学计算机学院
课 程 设 计课 程 操作系统Ⅰ
题 目 存储器管理模拟
学 院 计算机学院
专 业 软件工程
班 级
姓 名
学 号
指导教师 ***2019 年 6 月 16 日
目 录
1.设计目的与要求
1.1设计目的
1.2设计要求
2.设计思想及系统平台
2.1设计思想
2.2系统平台及使用语言
3.详细算法描述
4.源程序清单
5.运行结果与运行情况
6.总结1.设计目的与要求
1.1设计目的
本设计的目的是使学生熟悉存储器管理系统的设计方法;加深对所学各种存储器管理方案的了解;要求采用一些常用的存储器分配算法,设计一个存储器管理模拟系统并调试运行。
1.2设计要求
用C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中,空闲分区通过空闲分区链来管理;首次适应算法在进行内存分配时,系统优先使用空闲区低端的空间。回收时应注意相邻空闲分区的合并。
2.设计思想及系统平台
2.1设计思想
在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间,实现分区存储管理的内存分配功能,选择适应算法(首次适应算法,最佳适应算法),实现分区存储管理的内存回收算法,在这些存储管理中间必然会有碎片的产生,当碎片产生时,进行碎片的拼接。
2.2系统平台及使用语言
平台:Window10,codeblocks17.12
语言:c++3.详细算法描述
在写这个内存的动态分区模拟算法时,我是用c++中的可变数组来模拟的。分别用一个可变数组表示空闲分区链,和已分配的内存分区链,在收到为进程分配内存请求时,在空闲链找看有没有符合条件的。首次适应算法是先分配低地址段的内存,所以在分配时,先对空闲分区链按首地址排序;最佳适应算法是为进程分配能可以满足的最小分区,所以在分配时,先对空闲分区链按分区的大小排序。相邻空闲分区合并,先按首地址排序,对整个空闲链遍历一遍,如果加上分区大小与后下一个地址相同,就合并。具体请看代码实现。
4.源程序清单
#include<bits/stdc++.h> #include<iostream> using namespace std; struct ready_node{//就绪的进程 int id;//进程编号 int flag;//表是进程的状态,1:表示进入内存,0:表示从内存撤出 int size;//进程长度 }; struct free_node{//空闲区域表的结构体,首地址和长度 int id;//保存在该区域的进行号 int start;//首地址 int len;//长度 int state=0;//状态(0-空闲,1-已分配) }; vector<free_node> free_list;//保存空闲区域表的内容,分别是区域首址和区域长度 vector<free_node> used_list;//保存已占用区域表的内容,分别是区域首址和区域长度 queue<ready_node> wait_list;//等待的进程队列 int flag;//选择的算法(1-首次适应算法 2-最佳适应算法) //函数定义 int cmp1(free_node a,free_node b);//按开始地址从小到大排序 int cmp2(free_node a,free_node b);//按分区大小从小到大排序 void Show();//显示空闲区域表和已占用表的信息 void solve();//解决方案 void Alloc(ready_node node);//动态分区分配函数 void Free(ready_node node);//回收过程函数 void Oper_FIRO();//操作函数 int main() { solve(); return 0; } int cmp1(free_node a,free_node b){ return a.start<b.start;//按开始地址从小到大排序 } int cmp2(free_node a,free_node b){ return a.len<b.len;//按分区大小从小到大排序 } void Show(){//显示空闲区域表和已占用表的信息 vector<free_node> qlist; for(int i=0;i<free_list.size();i++){ qlist.push_back(free_list[i]); } for(int i=0;i<used_list.size();i++){ qlist.push_back(used_list[i]); } sort(qlist.begin(),qlist.end(),cmp1);//操作之前首先按首地址从小到大排序 printf("----------------------------------------------\n"); printf("| 内存分区的情况: |\n"); printf("----------------------------------------------\n"); printf("----------------------------------------------\n"); for(int i=0; i<qlist.size(); i++){ printf("| 分区号 | 首址 | 分区大小 | 状态 | 进程号 |\n"); printf("| %3d | %3d | %3d ",i+1,qlist[i].start,qlist[i].len); if(qlist[i].state==0) printf("| 空闲 | ---- |\n"); else printf("| 已分配 | %3d |\n",qlist[i].id); printf("----------------------------------------------\n"); } } void solve(){ free_node fnod; printf("请输入空闲分区初值(Kb):\n"); cin>>fnod.len; fnod.start=0;//初始化空闲表 free_list.push_back(fnod); printf("请输入实现算法:\n"); printf(" 1-首次适应算法\n 2-最佳适应算法\n"); cin>>flag; ready_node node; printf("请输入进程号,内存大小(Kb),执行的操作(1-申请,0-释放)\n"); while(scanf("%d%d%d",&node.id,&node.size,&node.flag)){ wait_list.push(node); Oper_FIRO(); //cout<<node.size<<endl; printf("请输入进程号,内存大小(Kb),执行的操作(1-申请,0-释放)\n"); } } void Alloc(ready_node node){//动态分区分配函数 if(flag==1)//1-首次适应算法 sort(free_list.begin(),free_list.end(),cmp1); else//2-最佳适应算法 sort(free_list.begin(),free_list.end(),cmp2); //cout<<free_list.size()<<endl; free_node fnod; int ok=0;//表示是否匹配成功 vector<free_node>::iterator it;//定义迭代器 for(it=free_list.begin();it!=free_list.end();++it){ //cout<<(*it).start<<endl; if(((*it).len) >= node.size){ //记录已占用空间 fnod.len=node.size; fnod.start=(*it).start; fnod.id=node.id; fnod.state=1; used_list.push_back(fnod);//放入已占用区域表 (*it).start+=node.size; (*it).len-=node.size;//修改空闲区域表的信息 if((*it).len==0){//剩余空闲长度为0,移除这个空闲区域 free_list.erase(it); } ok=1;//已找到匹配 break; } } if(ok==0){//证明当前进程没有匹配成功,则放入就绪队列 //ready_list.push(node); printf(" | 对不起,内存分配失败! |\n"); } printf("进程%d申请进入内存,内存占用大小为%dkb:\n",node.id,node.size); Show(); } void Free(ready_node node){//回收过程函数 //释放内存的过程中,进程正常都会在内存中出现,这里就假设释放的进程全部合法 free_node fnod; //node.state=0; vector<free_node>::iterator it;//定义迭代器 for(it=used_list.begin();it!=used_list.end();++it){ if(((*it).id) == node.id){//找到撤销进程 //回收空闲空间,并放入空闲区域白哦,此时不用记录进程号,因为好没有进程占有空间 fnod.start=(*it).start; fnod.len=node.size; fnod.state=0; free_list.push_back(fnod);//放入空闲区域表 (*it).len-=node.size;//修改占用区域表的信息 if((*it).len==0){//撤销内存后,剩余的占有空间为0,移除这个空闲区域 used_list.erase(it); } break; } } sort(free_list.begin(),free_list.end(),cmp1);//操作之前首先按首地址从小到大排序) vector<free_node>::iterator its;//定义迭代器 its=free_list.begin(); its++; //相邻空闲区合并 for(it=free_list.begin();it!=free_list.end();++it,++its){ if(its!=free_list.end()){//如果与后面的空闲块 int address=it->start+it->len; if(address==its->start){ (it->len) += its->len; free_list.erase(its); its=it; it--; } } } printf("进程%d申请撤销,收回内存大小为%dkb:\n",node.id,node.size); Show(); } void Oper_FIRO(){//操作函数 ready_node node; while(!wait_list.empty()){//操作等待数列,有分配和回收两个过程 node=wait_list.front(); wait_list.pop(); if(node.flag==1){//申请进入内存的进程 Alloc(node); } else{//要撤出内存的进程 Free(node); } } }
5.运行结果与运行情况
分别用首次适应和最佳适应算法演示下列请求序列的完整截图:初始内存空间640kb
作业1申请130kb
作业2申请60kb
作业3申请100kb
作业2释放60kb
作业4申请200kb
作业3释放100kb
作业1释放130kb
作业5申请140kb
作业6申请60kb
作业7申请50kb
作业6申请60kb1-首次适应算法(从上往下,从左往右看)
2-最佳适应算法
6.总结
通过本次的课程设计,使我能够正确运用操作系统课程中所学的基本理论和知识,加深了对进程调度基本概念的理解。在设计过程中,阅读了教材和一些资料,不断的发现问题、提出问题、解决问题,加深自己对这些算法的理解,。在编程和调试的过程中,我们要自己设计用于存储的数据结构,和调试bug来模拟这个过程。通过这样的实验和学习,使我们的知识体系变的更加牢固
-
动态内存分配算法实验报告
2011-06-23 10:01:14动态内存分配算法实验报告包括:实验题目,实验目的,实验要求,实验内容,实验结果,实验总结及后附有详细源代码 实验内容 1,确定定内存空闲分配表和进程内存分配表 2,采用首次适应算法完成内存空间的分配 3,... -
操作系统——实验五 动态分区分配算法的模拟
2020-08-05 10:41:39用C/C++实现一个完整的(可变)动态分区管理器,包括分配,回收,分区碎片整理等。希望同学们实现如下功能: 初始化功能:内存状态设置为初始状态。 分配功能:要求至少使用两种算法,用户可以选择使用。 回收... -
模拟实现动态分区内存分配与回收算法
2021-11-08 15:48:59操作系统课程设计 设计目的:了解动态分区的管理,掌握动态分区的最先适应算法、最佳...设计内容:编程模拟动态分区的最先适应算法、最佳适应算法、循环适应算法的分配过程,同时实现在回收过程中能对相邻区进行合并。 -
操作系统课程设计动态内存分配算法
2009-10-07 14:29:41操作课程设计,动态内存分配算法实现。包括可视化演示,可单步操作和自动执行。 -
常见的动态内存分配算法
2014-04-03 17:30:55首次适配算法很快因为它减少了搜索的次数,只要搜索到就分配。 2,下次适配算法: 它的工作方式和首次适配算法很像,不同点是每次找到合适的内存时都会记录当时的位置,而下次查找时都会从该节点查找,而不会从... -
动态内存分配算法
2013-05-07 15:05:58在实际的环境中,可能会遇到需要反复申请...下面的算法,可以减少无用功,仅在需要更大的内存时,重新申请一次 void getBuffer(char** ppBuf, int uSize) { if (*ppBuf) { if (_msize(*ppBuf) ) { dele -
操作系统 内存管理之动态动态分区分配算法 原理+代码实现
2021-12-07 21:31:27定义另外一个结构体来表达进程的信息,包括进程的id、进程的大小和进程被分配内存的起始位置。分别用一个长度为1000的结构体数组表示所有空闲内存块和进程的信息。 struct Memory_block { int st; int amount; }m... -
操作系统:动态内存分区分配算法实现(C++)
2021-01-09 16:21:32在进行内存分配时,从链首开始顺 序查找,直到找到一块分区的大小可以满足需求时,按照该作业的大小,从该 分区中分配出内存,将剩下的空闲分区仍然链在空闲分区链中。 2.循环首次适应算法 分配内存时不是从链首进行... -
动态内存分配算法(源代码&报告)DynamicAllocate
2009-12-27 19:30:34DynamicAllocate.rar 动态内存分配算法(源代码&报告) -
Dynamic-memory-allocation:计算机操作系统-动态内存分配
2021-05-02 08:34:09计算机操作系统-动态内存分配 1.首次适应算法(first fit,FF) 空闲分区以地址递增的次序链接,分配:从链首开始顺序查找,找到后,按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链... -
存储管理——动态分区分配算法的模拟
2018-09-14 16:14:26存储管理——动态分区分配算法的模拟 要求设计主界面以灵活选择某算法,以下算法都要实现: a、首次适应算法 b、循环首次适应算法 c、最佳适应算法 d、最坏适应算法 e、快速适应算法 具体要求: 1)首先由... -
嵌入式系统的自适应动态内存分配算法
2009-04-15 09:28:48分析了2种常用的动态内存管理算法,基于此提出了一种新的适用与嵌入式系统的动态内存管理方案,在融合了经典算法精髓的同时,通过引入特殊的数据结构,避免了常用算法某些方面的不足,使其更能满足嵌入式系统对内存... -
C++实现基于顺序搜索的动态分区分配算法
2020-12-13 18:58:13在本实验中运用了四种分配算法,分别是首次适应算法,循环首次适应算法,最坏适应算法,最佳适应算法。 首次适应算法 FF算法要求空闲分区链以地址递增的次序链接。在分配内存时,从链首开始顺序查找,直到找到一个... -
操作系统实验四实验报告动态分区分配算法.docx
2020-11-02 00:22:36操作系统实验四 目 分区分配算法 实验学时 4学时 目的 通 次 加深 分区分配算法的理解 一步掌握首次适 算法循 首次适 算法 最佳适 算法和最坏适 算法的 方法 内容及要求 描述 程序模 四种 分区分配算法首次适 算法... -
内存分配方式及分配算法优劣
2020-08-30 09:31:05内部碎片的产生:因为所有的内存分配必须起始于可被 4、8 或 16 整除(视 处理器体系结构而定)的地址或者因为MMU的分页机制的限制,决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 ... -
2016新编操作系统实验四报告-动态分区分配算法.docx
2020-09-11 06:37:052016 新编操作系统实验四报告 - 动态分区分配算法 操作系统实验...实验内容 问题描述 : 设计程序模拟四种动态分区分配算法 : 首次适应算法循环首次适应算法最 佳适应算法和最坏适应算法的工作过程假设内存中空闲分区个 -
操作系统中能够模拟动态内存分配算法来对进程分配内存空间的全部源代码及课设报告
2011-01-15 20:47:47能够模拟动态内存分配算法对进程分配内存空间。该程序具备的基本功能为: (1)能够以空闲分区表的形式显示某一时刻内存空间的使用情况。 (2)能够创建进程即输入进程信息,包括进程名称和进程需要的内存量, 系统... -
操作系统内存动态分区分配算法(Java实现)
2018-01-12 22:55:00内存的作用 内存是计算机的一个重要组成部分,它的主要作用在于配合 CPU 的高速运转,使得计算机的运行速度得到大大地提升 我们应该知道,计算机上的一切都是程序,我们使用计算机其实就是在运行计算机上的各种... -
内存分配算法
2014-03-10 14:35:45内存分配算法 实验目的: 本实验要求利用事先已经编写好的图形包软件模拟内存的分配。 实现动态分区的分配算法。最佳适配算法选择内存空闲块中最适合进程大小的块分配。邻近适配算法从上一次分配的地址开始...