操作系统-用Java实现动态内存分配（首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法FF,NF,BF,WF）

1
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
package neicunfenpei;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Memory my = new Memory();
Scanner sc = new Scanner(System.in);
while(true) {
System.out.println("请输入要分配内存还是要释放内存");
System.out.println("1 分配内存 2 释放内存");
int n =sc.nextInt();
switch(n) {
case 1:{
System.out.println("请输入要分配的内存大小");
int size = sc.nextInt();
my.allocation(size);
my.showZones();
break;
}
case 2:{
System.out.println("输入想要释放内存的分区号");
int id = sc.nextInt();
my.collection(id);
break;
}
}
}
}
}

1
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
package neicunfenpei;
import java.util.LinkedList;
import java.util.Scanner;
public class Memory{
//内存大小
private int size;
//最小剩余分区大小
private static final int MIN_SIZE = 2;
//内存分区
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;
}
}
//默认内存大小512K
public Memory(){
this.size = 512;
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));
}
//内存分配
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 xuanze = in.nextInt();
switch (xuanze){
case 1:
fristFit(size);break;
case 2:
nextFit(size);break;
case 3:
bestFit(size);break;
case 4:
worstFit(size);break;
default:
System.out.println("请重新选择!");
}
}
// FF
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("无可用内存空间!");
}
//NF
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("无可用内存空间!");
}
//BF
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));
}
}
//WF
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));
}
}
//开始分配
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 内存!");
}
//内存回收
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("分区编号t
分区始址t
分区大小t 空闲状态t");
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);
}
}
}