分区式存储管理算法
本文主要介绍了OS分区式存储管理的三种算法(FF BF WF)，希望对您有所帮助
一. 实验目的
- 了解可变分区存储管理方式
- 掌握最佳适应，最坏适应，首次适应算法
- 实现三种算法
- 对比不同的方法的优点和缺点
二. 实验内容
- 首次适应算法
- 最佳适应算法
- 最坏适应算法
三. 实验环境
- 实践平台 windows
- 编写环境 java
- 编译器 idea
四. 实验设计原理
首次适应算法
当接到内存申请时，遍历分区表，找到第一个满足长度的空闲区，将其分割并分配，此算法简单，可以快速分配决定，但空间利用率低。
最佳适应算法
当接到内存申请时，遍历分区表，找到第一个能满足长度的最小空闲区，将其分割，此算法节约空间，因为尽量不分割大的空闲区，缺点是形成很多很小的空闲区。
最坏适应算法
当接到内存申请时，遍历分区表，找到第一个能满足长度的最大空闲区，将其分割，该算法可以避免形成碎片，缺点是在分割了大的空闲区后，在遇到较大的申请内存时，无法满足分配。
五. 实验详细实现过程和算法流程
首先适应算法
最佳适应算法
最坏适应算法
六. 实验调试与结果分析
测试数据
空闲块：起始地址 大小
0 120 130 15 150 95 250 70 320 130 560 180
work：80 15 70 130 45
首先适应
最佳适应
最坏适应
七. 源代码
Table类
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public class Table {
public int address;//起始地址
public int size;//大小
public boolean isFree=false;//状态 是否为空闲区
public Table(int address,int size){
this.address = address;
this.size = size;
}
public Table(int address,int size,boolean isFree){
this.address = address;
this.size = size;
this.isFree = isFree;
}
public void outPut(){
System.out.print(" "+this.address+" "+this.size+" ");
if(!isFree){
System.out.println("free");
}else {
System.out.println("busy");
}
}
}TableList类
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56public class TableList {
public List<Table> TL;
int n;
public TableList(int n){
this.n = n;//列表为n
TL = new ArrayList<Table>();
}
//排序
public void sort1() {
Collections.sort(TL, new Comparator() {
@Override
public int compare(Object lhs, Object rhs) {
Table data1 = (Table) lhs;
Table data2 = (Table) rhs;
return data1.address - data2.address;
}
});
}
public void sort2() {
Collections.sort(TL, new Comparator() {
@Override
public int compare(Object lhs, Object rhs) {
Table data1 = (Table) lhs;
Table data2 = (Table) rhs;
return data1.size - data2.size;
}
});
}public void sort3() {
Collections.sort(TL, new Comparator() {
@Override
public int compare(Object lhs, Object rhs) {
Table data1 = (Table) lhs;
Table data2 = (Table) rhs;
return data2.size - data1.size;
}
});
}
//剔除 size 0
public void tichu(){
List<Table> new_TL = new ArrayList<Table>();
for(int i =0 ;i<TL.size();i++){
if(TL.get(i).size!=0){
new_TL.add(TL.get(i));
}
}
TL = new_TL;
}
//输出
public void display(){
System.out.println("index "+"address "+"size "+"status");
for(int i=1;i<=TL.size();i++){
System.out.print(" "+i+" ");
TL.get(i-1).outPut();
}
}
}主类
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入空闲块个数");
int free_tab;
free_tab = scanner.nextInt();
TableList tablist = new TableList(free_tab);
System.out.println("请输入起始地址和大小");
for(int i=0;i<free_tab;i++){
int a = scanner.nextInt();
int b = scanner.nextInt();
Table t = new Table(a,b);
tablist.TL.add(t);
}
System.out.println("请输入work数");
int work_num = scanner.nextInt();
work = new int[work_num];
System.out.println("请输入每个work大小");
for(int i=0;i<work_num;i++){
work[i] = scanner.nextInt();
}
System.out.println("请选择算法(1.首次适应算法 2.最佳适应算法 3.最差适应算法)");
int syn = scanner.nextInt();
if(syn==1)
FF(tablist);
else if(syn==2)
BF(tablist);
else if(syn==3)
WF(tablist);
}主类-FF
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31public static void FF(TableList tablist){
for (int k : work) {
boolean is_suc = false;
tablist.n=tablist.TL.size();
for (int j = 0; j < tablist.n; j++) {
Table table = tablist.TL.get(j);
if (!table.isFree && table.size >= k) {
is_suc = true;
int a = table.address;
int b = k;
Table jia = new Table(a, b, true);
tablist.TL.add(jia);
int c = table.address + k;
table.address = c;
table.size = table.size - k;
break;
}
}
if (!is_suc) {
System.out.println("分配失败");
tablist.tichu();
tablist.sort1();
tablist.display();
return;
}
}
System.out.println("分配成功");
tablist.tichu();
tablist.sort1();
tablist.display();
}主类-BF
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32public static void BF(TableList tablist){
for (int k : work) {
boolean is_suc = false;
tablist.sort2();
tablist.n=tablist.TL.size();
for (int j = 0; j < tablist.n; j++) {
Table table = tablist.TL.get(j);
if (!table.isFree && table.size >= k) {
is_suc = true;
int a = table.address;
int b = k;
Table jia = new Table(a, b, true);
tablist.TL.add(jia);
int c = table.address + k;
table.address = c;
table.size = table.size - k;
break;
}
}
if (!is_suc) {
System.out.println("分配失败");
tablist.tichu();
tablist.sort1();
tablist.display();
return;
}
}
System.out.println("分配成功");
tablist.tichu();
tablist.sort1();
tablist.display();
}主类-WF
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32public static void WF(TableList tablist){
for (int k : work) {
boolean is_suc = false;
tablist.n=tablist.TL.size();
tablist.sort3();
for (int j = 0; j < tablist.n; j++) {
Table table = tablist.TL.get(j);
if (!table.isFree && table.size >= k) {
is_suc = true;
int a = table.address;
int b = k;
Table jia = new Table(a, b, true);
tablist.TL.add(jia);
int c = table.address + k;
table.address = c;
table.size = table.size - k;
break;
}
}
if (!is_suc) {
System.out.println("分配失败");
tablist.tichu();
tablist.sort1();
tablist.display();
return;
}
}
System.out.println("分配成功");
tablist.tichu();
tablist.sort1();
tablist.display();
}
八. 感悟
通过这次实验了解了可变分区的相关知识，可变分区是系统不预先划分固定分区，有很大的灵活性，然后是三种分配策略，首先是首先适应法，这种算法简单，遍历时碰到的第一个满足大小的即可分配，缺点是空间利用率低；最佳适应算法，每次分配时都将块按大小从小到大排序，使其分配时可以分配最佳满足的块，这样利用率最佳，但是会造成很多空闲区，也叫作碎片；最坏适应算法，与最佳的区别是排序方式是从大到小，这样就可以避免最佳适应算法的碎片问题，但是会造成较大块无法分配内存。但是实验还有不完善之处，该实验只是完成了申请内存的过程，没有实现边申请边释放的过程，还有待改进。
分区式存储管理算法
http://kaikai12321.github.io/2022/10/23/分区式存储管理算法/