存储管理——动态分区分配算法

import java.awt.*; import java.awt.event.*; import javax.swing.*; /* * 快速适应算法 * 算法概述：将空闲分区按容量大小进行分类，为每一类具有相同容量的空闲分区单独设立一个空闲分区链表， * 分配时仅根据线程长度寻找能容纳它的最小空闲分区 * 实现方法：由于元素少，所以很难出现相同的数值，于是改为将数值接近的元素分为一组（以10为单位分类）， * 分配时将大于该作业的一组元素中最小的一个分配出来 * */ public class QuickFit extends JFrame implements MouseListener { JTextPane t = new JTextPane(); JPanel p = new JPanel(); // 定义一个二维数组用于存储分组后的元素，二维数组可实现按元素所在行而分辨出它所在的组 mem[][] aa; // m表示分组后最长组的数组长度，index用于指示未得到分配的作业存入c的位置 int m, index; // c用于存储未得到分配的作业，构造方法中将它的长度设为与作业数组长度相同 int[] c; // 通过count方法统计各个分组的大小，然后以最大的长度作为二维数组aa的列数 public void count(mem[] b) { int i0 = 0, i1 = 0, i2 = 0, i3 = 0, i4 = 0, i5 = 0, i6 = 0, i7 = 0, i8 = 0, i9 = 0; // 通过switch语句把所有空闲分区分组的大小确定 for (int i = 0; i < b.length; i++) { if (b[i].m4 == 0) { switch (b[i].m2 / 10) { case 0: { i0++; break; } case 1: { i1++; break; } case 2: { i2++; break; } case 3: { i3++; break; } case 4: { i4++; break; } case 5: { i5++; break; } case 6: { i6++; break; } case 7: { i7++; break; } case 8: { i8++; break; } default: { i9++; break; } } } } m = Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(Math .max(Math.max(i0, i1), i2), i3), i4), i5), i6), i7), i8), i9); aa = new mem[10][m]; } // 分组存数据，即给二维数组aa的对应位置赋值 // 通过i0~i9几个数起到指针的作用，将各组元素依次存入对应位置 public void create(mem[] b) { int i0 = 0, i1 = 0, i2 = 0, i3 = 0, i4 = 0, i5 = 0, i6 = 0, i7 = 0, i8 = 0, i9 = 0; for (int i = 0; i < b.length; i++) { if (b[i].m4 == 0) { switch (b[i].m2 / 10) { case 0: { aa[0][i0] = b[i]; i0++; break; } case 1: { aa[1][i1] = b[i]; i1++; break; } case 2: { aa[2][i2] = b[i]; i2++; break; } case 3: { aa[3][i3] = b[i]; i3++; break; } case 4: { aa[4][i4] = b[i]; i4++; break; } case 5: { aa[5][i5] = b[i]; i5++; break; } case 6: { aa[6][i6] = b[i]; i6++; break; } case 7: { aa[7][i7] = b[i]; i7++; break; } case 8: { aa[8][i8] = b[i]; i8++; break; } default: { aa[9][i9] = b[i]; i9++; break; } } } } } // 快速适应算法分组的显示方法 public void print(mem[][] a, JTextPane t) { add.insert(" - - - - - - - - - - - - - - - - - - - - - - -" + "\n", t); add.insert(" 空闲分区分组如下所示：", t); // 使用for循环将各组元素依次输出，即输出二维数组中各行的非零元素 add.insert("\n" + " 1~ 9: ", t); if (a[0][0] != null) {// 假如第一位非零，则说明该组元素非空 int i = 0; while (i < m && a[0][i] != null) {// 将在数组长度范围内的非零元素输出 add.insert3(" [" + a[0][i].m2 + "]", t); i++; } } add.insert("\n" + " 10~19: ", t); if (a[1][0] != null) { int i = 0; while (i < m && a[1][i] != null) { add.insert3(" [" + a[1][i].m2 + "]", t); i++; } } add.insert("\n" + " 20~29: ", t); if (a[2][0] != null) { int i = 0; while (i < m && a[2][i] != null) { add.insert3(" [" + a[2][i].m2 + "]", t); i++; } } add.insert("\n" + " 30~39: ", t); if (a[3][0] != null) { int i = 0; while (i < m && a[3][i] != null) { add.insert3(" [" + a[3][i].m2 + "]", t); i++; } } add.insert("\n" + " 40~49: ", t); if (a[4][0] != null) { int i = 0; while (i < m && a[4][i] != null) { add.insert3(" [" + a[4][i].m2 + "]", t); i++; } } add.insert("\n" + " 50~59: ", t); if (a[5][0] != null) { int i = 0; while (i < m && a[5][i] != null) { add.insert3(" [" + a[5][i].m2 + "]", t); i++; } } add.insert("\n" + " 60~69: ", t); if (a[6][0] != null) { int i = 0; while (i < m && a[6][i] != null) { add.insert3(" [" + a[6][i].m2 + "]", t); i++; } } add.insert("\n" + " 70~79: ", t); if (a[7][0] != null) { int i = 0; while (i < m && a[7][i] != null) { add.insert3(" [" + a[7][i].m2 + "]", t); i++; } } add.insert("\n" + " 80~89: ", t); if (a[8][0] != null) { int i = 0; while (i < m && a[8][i] != null) { add.insert3(" [" + a[8][i].m2 + "]", t); i++; } } add.insert("\n" + " 90~99: ", t); if (a[9][0] != null) { int i = 0; while (i < m && a[9][i] != null) { add.insert3(" [" + a[9][i].m2 + "]", t); i++; } } add.insert("\n", t); } // select方法用于确定将哪个空闲分区分配给作业 public void select(int a, mem[] b) { // 将作业大小除以十可知该作业属十组中哪一组，而比该组大的组中的元素肯定可以分配给它，以此作为算法 int n = a / 10; // 由于使用的算法决定了无法分配大于90的作业，所以以下循环中仅比较1～89的值，超过90直接认定为无法分配 for (int i = n; i < 10; i++) { if (n < 9 && i < 9) {// 仅在作业大小小于90以及未比较至最后一组空闲分区的情况下进行 if (aa[i + 1][0] != null) {// 若比该作业大的一组空闲空间数组头位元素存在 add.insert2("\n" + " [" + aa[i + 1][0].m2 + "] 分配给 [" + a + "] " + "\n", t); // 将该数组从第二位开始前移，末位设零，然后结束本次循环 for (int j = 0; j < m - 1; j++) { aa[i + 1][j] = aa[i + 1][j + 1]; } int xx = aa[i + 1][0].m1 - 1; b[xx].m4 = 1; aa[i + 1][m - 1] = null; break; } else {// 假如比该作业大的一组空闲空间数组头位元素不存在，则再往上找 continue; } } else {// 假如作业大于90或者比较到最后(i=9)仍无合适空间，则输出“无法分配”，并将index加一 c[index] = a; add.insert2("\n" + " [" + a + "] 无法分配" + "\n", t); index++; } } } // 构造方法 public QuickFit(int[] ai, mem[] bi) { // 为避免改变传递进来的数组值，影响操作，新建两个相同的数组 int la = ai.length, lb = bi.length; int[] a = new int[la]; mem[] b = new mem[lb]; for (int i = 0; i < la; i++) { a[i] = ai[i]; } for (int i = 0; i < lb; i++) { b[i] = bi[i]; } c = new int[a.length]; // 以下为界面代码 JScrollPane sp = new JScrollPane(t); p.setLayout(new GridLayout(1, 1)); p.add(sp); t.addMouseListener(this); t.setBackground(Color.yellow); t.setEditable(false); add(p); setSize(350, 250); setVisible(true); setLocation(100, 60); setTitle("快速适应算法"); add.printJ(a, t); add.insert2(" 内存分区初始状态：" + "\n", t); Test.print(b, t); // 调用分组的方法生成一个空的二维数组 count(b); // 将二维数组对应位置逐一赋值 create(b); // 调用显示分组结果的方法 print(aa, t); // 使用循环依次将作业按select方法分配 for (int i = 0; i < a.length; i++) { int cc = 0; for (int j = 0; j < 10; j++) { if (aa[j][0] == null) { cc++; } if (cc == 10) { add.insert2(" 内存中已无空闲分区" + "\n", t); break; } } select(a[i], b); add.insert(" - - - - - - - - - - - - - - - - - - - - - - -" + "\n", t); add.insert("\n", t); print(aa, t); } add.insert("\n", t); if (c[0] != 0) {// 若未分配作业数组非空 add.insert2(" 以下作业未得到分配：" + "\n", t); for (int i = 0; i < c.length; i++) { if (c[i] != 0) {// 输出非零元素 add.insert(" [" + c[i] + "]", t); } } } else {// 如果未分配作业数组为空，则输出"所有作业分配完成" add.insert2(" 所有作业分配完成" + "\n", t); } a