firstfit.java

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

import java.awt.*;
import java.awt.event.*;

import javax.swing.*;
import javax.swing.text.*;

/*
 * 
 * 首次适应算法
 * 算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中
 * 实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对应作业的值
 *
 */

public class FirstFit extends JFrame implements MouseListener {
	JTextPane t = new JTextPane();
	JPanel p = new JPanel();

	public FirstFit(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;

		// 以下为界面代码
		JScrollPane sp = new JScrollPane(t);

		p.setLayout(new GridLayout(1, 1));
		p.add(sp);
		t.addMouseListener(this);
		t.setBackground(Color.yellow);
		add(p);
		setLocation(20, 20);
		setSize(350, 250);
		setVisible(true);
		setTitle("首次适应算法");

		// 从这里开始是算法的主要代码
		// notIndex用于记录无法找到匹配分区的作业数，数组sav的长度与a相同，用于存储无法分配的作业
		int notIndex = 0;
		int[] sav = new int[a.length];

		if (freeLength == 0) {// 若无空闲分区则不进行后面的运算
			add.insert("内存中无空闲分区" + "\n", t);
		} else {
			for(int i=0;i<a.length;i++){//以作业数组长度作为循环次数
				int n=0;
				for(int j=0;j<f.length;j++){//与各个空闲分区进行比较
					add.insert(" [" + a[i] + "] 与分区号为" + f[j].m1 + "的空闲分区 ["
							+ f[j].m2 + "] 比较，"+"\n", t);
					if(a[i]<f[j].m2){//分区大于作业
						add.insert("符合，分配" + "\n", t);
						mem[] nb=new mem[b.length+1];
						int ni=f[j].m1;
						if(f[j].m1==1){//如果该空闲分区是内存表头
							nb[0]=new mem(1,a[i],0,1);
							nb[1]=new mem(2,f[j].m2-a[i],a[i],0);
							for(int k=2;k<nb.length;k++){
								nb[k]=new mem(nb[k-1].m1+1,b[k-1].m2,nb[k-1].m2+nb[k-1].m3,b[k-1].m4);
							}
							b=nb;
							Test.print(b, t);
							f = mem.lian1(b);
							add.printF(f, t);
							freeLength = f.length;
						}else{//如果该空闲分区不是内存表头
							for(int k=0;k<ni;k++){
								nb[k]=new mem(b[k].m1,b[k].m2,b[k].m3,b[k].m4);
							}
							nb[ni-1].m2=a[i];
							nb[ni-1].m4=1;
							nb[ni]=new mem(nb[ni-1].m1+1,f[j].m2-a[i],nb[ni-1].m2+nb[ni-1].m3,0);
							for(int k=ni+1;k<nb.length;k++){
								nb[k]=new mem(nb[k-1].m1+1,b[k-1].m2,nb[k-1].m2+nb[k-1].m3,b[k-1].m4);
							}
							b=nb;
							Test.print(b, t);
							f = mem.lian1(b);
							add.printF(f, t);
							freeLength = f.length;
						}
						break;
					}else{
						if(a[i]==f[j].m2){//分区等于作业
							add.insert2(" 符合，分配" + "\n", t);
							b[f[j].m1-1].m4=1;
							Test.print(b, t);
							f = mem.lian1(b);
							add.printF(f, t);
							freeLength = f.length;
							break;
						}else{//分区小于作业，将指示不符合次数的n加一
							n++;
						}
					}
					if(n==f.length){//如果不符合次数为空闲分区数组长度，说明找遍空闲分区都无符合项
						add.insert2(" 无符合分区" + "\n", t);
						sav[notIndex]=a[i];
						notIndex++;
					}
				}
			}
			// 若notIndex不为零，则sav数组中必存储了无法分配的作业，将它们输出
			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 自动生成方法存根

	}

}