nextfit.java

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

import java.awt.*;

import javax.swing.*;

import java.awt.event.*;

/*
 * 
 * 循环首次适应算法
 * 算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区开始查找
 * 实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位置
 *
 */

public class NextFit extends JFrame implements MouseListener {
	JTextPane t = new JTextPane();

	public NextFit(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];
		}
		add.printJ(a, t);
		add.insert2(" 内存分区初始状态：" + "\n", t);
		Test.print(b, t);

		mem[] f = mem.lian1(b);
		add.printF(f, t);
		int freeLength = f.length;

		// 以下为界面代码
		JPanel p = new JPanel();
		JScrollPane sp = new JScrollPane(t);
		p.setLayout(new GridLayout(1, 1));
		p.add(sp);
		t.addMouseListener(this);
		t.setBackground(Color.yellow);
		add(p);
		setSize(350, 250);
		setVisible(true);
		setLocation(40, 30);
		setTitle("循环首次适应算法");

		// 从这里开始是算法的主要代码
		/*
		 * notIndex用于记录无法找到匹配分区的作业数，数组sav的长度与a相同，用于存储无法分配的作业
		 * fitIndex用于记录匹配的空闲分区位置，作用是指示下一次比较开始的位置
		 * forIndex指示循环进行的次数，仅于鉴别是否为第一次作循环时起作用
		 */
		int notIndex = 0, fitIndex = 0, forIndex = 0;
		int[] sav = new int[a.length];

		if (freeLength == 0) {// 若无空闲分区则不进行后面的运算
			add.insert("内存中无空闲分区" + "\n", t);
		} else {
			// 下面开始做循环比较，比较方法与首次适应算法基本相同
			for (int i = 0; i < a.length; i++) {
				add.insert("\n", t);
				// 定义n用于记录不符合的次数
				int n = 0;
				add.insert(" - - - - - - - - - - - - - - - - - - - - - - - - -"
						+ "\n", t);
				// 假如是第一次循环或者上一次的匹配分区位于空闲分区表最后，则从第一位开始比较
				if ((forIndex == 0) || (fitIndex == (b.length - 1))) {
					for (int j = 0; j < b.length; j++) {
						if (b[j].m4 != 1) {
							add.insert(" [" + a[i] + "] 与分区号为" + b[j].m1
									+ "的空闲分区 [" + b[j].m2 + "] 比较，", t);
							if (a[i] <= b[j].m2) {// 假如作业小于空闲分区，则可分配
								add.insert("符合，分配" + "\n", t);
								// 数组对应元素减去作业大小，即表示分配后的大小

								mem[] nb = new mem[b.length + 1];
								for (int k = 0; k < j; k++) {
									nb[k] = b[k];
								}
								int size = b[j].m2 - a[i];
								nb[j] = b[j];
								nb[j].m2 = a[i];
								nb[j].m4 = 1;
								nb[j + 1] = new mem(nb[j].m1 + 1, size,
										nb[j].m2 + nb[j].m3, 0);
								for (int k = j + 2; k < nb.length; k++) {
									nb[k] = b[k - 1];
									nb[k].m1 += 1;
								}
								b = new mem[nb.length];
								for (int k = 0; k < nb.length; k++) {
									b[k] = nb[k];
								}

								Test.print(b, t);
								fitIndex = j;
								// 得到分配，结束此作业比较循环
								break;
							} else {
								n++;// 每不符一次把n加1
								add.insert("不符，往下找" + "\n", t);
							}
						}
					}

				} else {
					int x = fitIndex + 1;// 令x指向上次找到空闲分区的下一个空闲分区
					// 比较方法与首次适应算法相比，仅在此改为用x指示空闲分区在数组中的位置
					while (x < b.length) {
						if (b[x].m4 != 1) {
							add.insert(" [" + a[i] + "] 与分区号为" + b[x].m1
									+ "的空闲分区 [" + b[x].m2 + "] 比较，", t);
							if (a[i] <= b[x].m2) {// 假如作业小于空闲分区，则可分配
								add.insert("符合，分配" + "\n", t);
								// 数组对应元素减去作业大小，即表示分配后的大小

								mem[] nb = new mem[b.length + 1];
								for (int k = 0; k < x; k++) {
									nb[k] = b[k];
								}
								int size = b[x].m2 - a[i];
								nb[x] = b[x];
								nb[x].m2 = a[i];
								nb[x].m4 = 1;
								nb[x + 1] = new mem(nb[x].m1 + 1, size,
										nb[x].m2 + nb[x].m3, 0);
								for (int k = x + 2; k < nb.length; k++) {
									nb[k] = b[k - 1];
									nb[k].m1 += 1;
								}
								b = new mem[nb.length];
								for (int k = 0; k < nb.length; k++) {
									b[k] = nb[k];
								}
								fitIndex = x;
								Test.print(b, t);

								// 得到分配，结束此作业比较循环
								break;
							} else {
								n++;// 每不符一次把n加1
								add.insert("不符，往下找" + "\n", t);
							}

						}
						// 利用x++将元素指向下一位
						x++;

					}
					if (x >= b.length) {
						x = 0;
						while (x <= fitIndex) {
							if (b[x].m4 != 1) {
								// 转为从首位开始查找后只比较到上一次找到的匹配分区，以保证循环可结束
								add.insert(" [" + a[i] + "] 与分区号为" + b[x].m1
										+ "的空闲分区 [" + b[x].m2 + "] 比较，", t);
								if (a[i] <= b[x].m2) {// 假如作业小于空闲分区，则可分配
									add.insert("符合，分配" + "\n", t);
									// 数组对应元素减去作业大小，即表示分配后的大小

									mem[] nb = new mem[b.length + 1];
									for (int k = 0; k < x; k++) {
										nb[k] = b[k];
									}
									int size = b[x].m2 - a[i];
									nb[x] = b[x];
									nb[x].m2 = a[i];
									nb[x].m4 = 1;
									nb[x + 1] = new mem(nb[x].m1 + 1, size,
											nb[x].m2 + nb[x].m3, 0);
									for (int k = x + 2; k < nb.length; k++) {
										nb[k] = b[k - 1];
										nb[k].m1 += 1;
									}
									b = new mem[nb.length];
									for (int k = 0; k < nb.length; k++) {
										b[k] = nb[k];
									}
									fitIndex = x;
									Test.print(b, t);

									f = mem.lian1(b);
									add.printF(f, t);
									freeLength = f.length;

									// 得到分配，结束此作业比较循环
									break;
								} else {
									n++;// 每不符一次把n加1
									add.insert("不符，往下找" + "\n", t);
								}

							}
							// 利用x++将元素指向下一位
							x++;

						}
					}
				}

				if (n == freeLength) {// 假如n等于空闲数组的长度，则说明找遍空闲分区都无符合项
					add.insert("\n", t);
					add.insert2(" 未找到符合的空闲分区" + "\n", t);
					add.insert("\n", t);
					if ((i + 1) < a.length) {// i+1<a.length表示以下信息不会出现在最后一次查找后
						add.insert(" 剩下的待分配作业大小为" + "\n", t);
						// 将a数组剩下的元素输出，即待分配的作业
						for (int j = (i + 1); j < a.length; j++) {
							add.insert(" [" + a[j] + "]", t);
						}
						add.insert("\n", t);
					}
					sav[notIndex] = a[i];
					notIndex++;

				} else {// 假如n不等于空闲数组的长度，则说明该次循环找到了可分配空间，于是输出两数组分配后的情况
					// ////////

					add.insert("\n", t);
					// 若不是最后一次分配，则显示剩下的待分配作业
					if ((i + 1) < a.length) {
						add.insert(" 剩下的待分配作业大小为" + "\n", t);
						for (int j = (i + 1); j < a.length; j++) {
							add.insert(" [" + a[j] + "]", t);
						}
						add.insert("\n", t);
					}
					// ////////
				}
				forIndex++;
				// 整个大循环每进行一次forIndex++
				add.insert(" - - - - - - - - - - - - - - - - - - - - - - - - -"
						+ "\n", t);
			}
		}

		// 输出未得到分配的作业
		if (notIndex != 0) {
			add.insert("\n", t);
			add.insert2(" 有以下大小的作业未得到分配:" + "\n", t);
			for (int i = 0; i < notIndex; i++) {
				add.insert(" [" + sav[i] + "]", t);
			}
			add.insert("\n", t);
			// 最后输出空闲分区链在完成所有操作后的情况
			add.insert2(" 内存分区状态：" + "\n", t);
			Test.print(b, t);
		} else {// 若notIndex为零，说明所有作业都得到分配
			add.insert2(" 所有作业分配完成", 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 自动生成方法存根

	}

}