quickfit.java

操作系统-动态分区分配算法 操作系统-动态分区分配算法

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);
		}
		add.insert2("\n" + " 内存最终状态：" + "\n", t);
		Test.print(b, t);
	}

	public void mouseClicked(MouseEvent arg0) {
		// TODO 自动生成方法存根

	}

	public void mouseEntered(MouseEvent arg0) {
		// TODO 自动生成方法存根
		t.setBackground(Color.white);
	}

	public void mouseExited(MouseEvent arg0) {
		// TODO 自动生成方法存根

	}

	public void mousePressed(MouseEvent arg0) {
		// TODO 自动生成方法存根

	}

	public void mouseReleased(MouseEvent arg0) {
		// TODO 自动生成方法存根

	}

}