一、算法思想：

1、首次適應算法：

????????首次適應算法從空閑分區的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在于減少查找時間。

2、最佳適應算法：

從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此算法，空閑分區要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。

二、算法代碼：

1、首次適應算法：

package Package8;import java.util.*;public class FirstFit {static int totalSpace = 0; // 記錄整個內存的空間public static void main(String[] args) {System.out.println("輸入整數執行相應操作：");System.out.println("1、初始化內存；");System.out.println("2、輸入作業；");System.out.println("3、分區回收；");System.out.println("4、內存信息；");System.out.println("其他：結束程序");List<Subregion> subregionList = new ArrayList<>();Scanner scanner = new Scanner(System.in);outside:while (true) {System.out.print("請輸入要執行的操作：");int command = 0;try{command = scanner.nextInt();} catch (Exception e){System.out.println("請輸入整數！");e.printStackTrace();}switch (command){case 1:// 初始化if (totalSpace == 0){// 初始化分區System.out.print("請輸入初始分區的大小：");int size = 0;try{size = scanner.nextInt();totalSpace = size;} catch (Exception e){System.out.println("請輸入整數！");e.printStackTrace();}Subregion subregion = new Subregion(0, size, size, size);subregionList.add(subregion);System.out.println("初始化成功！");} else {System.out.println("分區已經初始化!");}break;case 2:// 輸入作業if (totalSpace != 0){System.out.print("請輸入作業名：");String taskName = scanner.next();System.out.print("請輸入作業大小：");int taskSize = 0;try{taskSize = scanner.nextInt();} catch (Exception e){System.out.println("請輸入整數！");e.printStackTrace();}if (taskSize == 0){System.out.println("作業大小不能為0!");break;}int flag = -1; // 用于標記內存是否可以存入作業// 判斷內存中是否有同名的作業for (Subregion subregion : subregionList) {if (subregion.task.taskName != null && subregion.task.taskName.equals(taskName)) {System.out.println("作業名被占用！");flag = 1;break;}}if (flag != 1) {// 遍歷所有分區for (int i = 0; i < subregionList.size(); i++) {// 判斷分區是否可以存下作業if (subregionList.get(i).freeSpace >= taskSize){// 存入作業Task task = new Task();task.taskName = taskName;task.taskSize = taskSize;subregionList.get(i).task = task;// 修改分區空閑空間subregionList.get(i).freeSpace = subregionList.get(i).freeSpace - taskSize;// 動態分區// 如果剛好存下就不分區，否則剩下的分一個新的分區if (subregionList.get(i).freeSpace != 0){Subregion subregion = new Subregion();subregion.freeSpace = subregionList.get(i).freeSpace;subregion.startAddress = subregionList.get(i).endAddress - subregionList.get(i).freeSpace;subregion.endAddress = subregionList.get(i).endAddress;subregion.partitionSpace = subregionList.get(i).freeSpace;subregionList.add(subregion);// 修改原分區信息subregionList.get(i).endAddress = subregion.startAddress;subregionList.get(i).partitionSpace = subregionList.get(i).partitionSpace - subregionList.get(i).freeSpace;subregionList.get(i).freeSpace = 0;// 將分區按照起始地址排序sortByStartAddress(subregionList);}flag = 0;System.out.println("存入成功！");break;}}}if (flag == -1){System.out.println("內存不足！");}} else {System.out.println("請初始化分區！");}break;case 3:// 回收作業if (totalSpace != 0){System.out.print("請輸入作業名：");String taskName = scanner.next();// 判斷作業是否存在int flag = -1; // 用于標記作業是否存在for (int i = 0; i < subregionList.size(); i++) {if (subregionList.get(i).task.taskName != null && subregionList.get(i).task.taskName.equals(taskName)){// 如果只有一個分區，直接回收if (subregionList.size() == 1){subregionList.get(i).task = new Task();subregionList.get(i).partitionSpace = totalSpace;subregionList.get(i).freeSpace = totalSpace;System.out.println("回收成功！");flag = 1;break;}// 將該作業所在的區域變成空閑分區subregionList.get(i).freeSpace = subregionList.get(i).task.taskSize;subregionList.get(i).task = new Task();sortByStartAddress(subregionList);// 刪除總空間為0的分區deleteSubregion(subregionList);flag = 0;break;}}// 合并分區if (flag == 0){int num = subregionList.size();while (num > 0){for (int i = 0; i < subregionList.size(); i++) {// 該分區為第一個分區if (subregionList.get(i).task.taskName == null && i == 0){// 同時第二個分區也為空，合并if ((i + 1) < subregionList.size() && subregionList.get(i + 1).task.taskName == null){// 將兩個分區大小合并subregionList.get(i).endAddress = subregionList.get(i + 1).endAddress;subregionList.get(i).partitionSpace = subregionList.get(i).endAddress - subregionList.get(i).startAddress;subregionList.get(i).freeSpace = subregionList.get(i).partitionSpace;// 將第二個分區大小變成0subregionList.get(i + 1).startAddress = subregionList.get(i + 1).endAddress;subregionList.get(i + 1).partitionSpace = 0;subregionList.get(i + 1).freeSpace = 0;}}// 該分區不是第一個分區if (subregionList.get(i).task.taskName == null && i != 0){// 如果該分區的前一個分區為空閑分區if (subregionList.get(i - 1).task.taskName == null){// 將該分區合并到前一個分區subregionList.get(i - 1).endAddress = subregionList.get(i).endAddress;subregionList.get(i - 1).partitionSpace = subregionList.get(i - 1).endAddress - subregionList.get(i - 1).startAddress;subregionList.get(i - 1).freeSpace = subregionList.get(i - 1).partitionSpace;// 該分區大小變成0subregionList.get(i).startAddress = subregionList.get(i).endAddress;subregionList.get(i).partitionSpace = 0;subregionList.get(i).freeSpace = 0;}}}// 刪除分區空間為0的分區deleteSubregion(subregionList);num --;}System.out.println("回收成功！");} else if (flag == -1){System.out.println("作業不存在！");}} else {System.out.println("請初始化分區！");}break;case 4:// 內存信息if (totalSpace != 0){System.out.println("總內存空間：" + totalSpace);for (Subregion subregion : subregionList) {System.out.println(subregion);}} else {System.out.println("請初始化分區！");}break;default:break outside; // 退出外層循環}}scanner.close();}/*** 該方法用于將數組按起始地址排序*/public static void sortByStartAddress(List<Subregion> subregionList){for (int i = 0; i < subregionList.size(); i++) {for (int j = 0; j + 1 < subregionList.size() - i; j++) {if (subregionList.get(j).startAddress > subregionList.get(j + 1).startAddress){Collections.swap(subregionList, j, j + 1);}}}}/*** 該方法用于刪除總空間為0的分區*/public static void deleteSubregion(List<Subregion> subregionList){subregionList.removeIf(subregion -> subregion.partitionSpace == 0);}// 分區信息static class Subregion {private int startAddress; // 起始地址private int endAddress; // 結束地址private int partitionSpace; // 該分區的總空間private int freeSpace; // 空閑空間Task task = new Task(); // 作業信息public Subregion(int startAddress, int endAddress, int partitionSpace, int freeSpace) {this.startAddress = startAddress;this.endAddress = endAddress;this.partitionSpace = partitionSpace;this.freeSpace = freeSpace;}public Subregion() {}@Overridepublic String toString() {String taskInfo = "";if (task.taskName != null){taskInfo = " " + "分區中作業信息：\n" + " " + task;}return "分區信息：" +"起始地址：" + startAddress +", 結束地址：" + endAddress +", 分區總空間：" + partitionSpace +", 空閑空間：" + freeSpace + "\n" +taskInfo;}}// 作業信息static class Task{private String taskName; // 作業名private int taskSize; // 作業大小@Overridepublic String toString() {return "作業名：'" + taskName + '\'' +", 作業大小: " + taskSize;}}}

2、最佳適應算法：

package Package8;import java.util.*;public class BestFit {static int totalSpace = 0; // 記錄整個內存的空間public static void main(String[] args) {System.out.println("輸入整數執行相應操作：");System.out.println("1、初始化內存；");System.out.println("2、輸入作業；");System.out.println("3、分區回收；");System.out.println("4、內存信息；");System.out.println("其他：結束程序");List<Subregion2> subregionList = new ArrayList<>();Scanner scanner = new Scanner(System.in);outside:while (true) {System.out.print("請輸入要執行的操作：");int command = 0;try{command = scanner.nextInt();} catch (Exception e){System.out.println("請輸入整數！");e.printStackTrace();}switch (command){case 1:// 初始化if (totalSpace == 0){// 初始化分區System.out.print("請輸入初始分區的大小：");int size = 0;try{size = scanner.nextInt();totalSpace = size;} catch (Exception e){System.out.println("請輸入整數！");e.printStackTrace();}Subregion2 subregion = new Subregion2(0, size, size, size);subregionList.add(subregion);System.out.println("初始化成功！");} else {System.out.println("分區已經初始化!");}break;case 2:// 輸入作業if (totalSpace != 0){System.out.print("請輸入作業名：");String taskName = scanner.next();System.out.print("請輸入作業大小：");int taskSize = 0;try{taskSize = scanner.nextInt();} catch (Exception e){System.out.println("請輸入整數！");e.printStackTrace();}if (taskSize == 0){System.out.println("作業大小不能為0!");break;}int flag = -1; // 用于標記內存是否可以存入作業// 判斷內存中是否有同名的作業for (Subregion2 subregion : subregionList) {if (subregion.task.taskName != null && subregion.task.taskName.equals(taskName)) {System.out.println("作業名被占用！");flag = 1;break;}}if (flag != 1) {// 遍歷所有分區for (int i = 0; i < subregionList.size(); i++) {// 判斷分區是否可以存下作業if (subregionList.get(i).freeSpace >= taskSize){// 存入作業Task2 task = new Task2();task.taskName = taskName;task.taskSize = taskSize;subregionList.get(i).task = task;// 修改分區空閑空間subregionList.get(i).freeSpace = subregionList.get(i).freeSpace - taskSize;// 動態分區// 如果剛好存下就不分區，否則剩下的分一個新的分區if (subregionList.get(i).freeSpace != 0){Subregion2 subregion = new Subregion2();subregion.freeSpace = subregionList.get(i).freeSpace;subregion.startAddress = subregionList.get(i).endAddress - subregionList.get(i).freeSpace;subregion.endAddress = subregionList.get(i).endAddress;subregion.partitionSpace = subregionList.get(i).freeSpace;subregionList.add(subregion);// 修改原分區信息subregionList.get(i).endAddress = subregion.startAddress;subregionList.get(i).partitionSpace = subregionList.get(i).partitionSpace - subregionList.get(i).freeSpace;subregionList.get(i).freeSpace = 0;// 將分區按照起始地址排序// sortByStartAddress(subregionList);// 將空閑分區按空閑空間大小排序sortByFreeSpace(subregionList);}flag = 0;System.out.println("存入成功！");break;}}}if (flag == -1){System.out.println("內存不足！");}} else {System.out.println("請初始化分區！");}break;case 3:// 回收作業if (totalSpace != 0){System.out.print("請輸入作業名：");String taskName = scanner.next();// 判斷作業是否存在int flag = -1; // 用于標記作業是否存在for (int i = 0; i < subregionList.size(); i++) {if (subregionList.get(i).task.taskName != null && subregionList.get(i).task.taskName.equals(taskName)){// 如果只有一個分區，直接回收if (subregionList.size() == 1){subregionList.get(i).task = new Task2();subregionList.get(i).partitionSpace = totalSpace;subregionList.get(i).freeSpace = totalSpace;System.out.println("回收成功！");flag = 1;break;}// 將該作業所在的區域變成空閑分區subregionList.get(i).freeSpace = subregionList.get(i).task.taskSize;subregionList.get(i).task = new Task2();sortByStartAddress(subregionList);// 刪除總空間為0的分區deleteSubregion(subregionList);flag = 0;break;}}// 合并分區if (flag == 0){int num = subregionList.size();while (num > 0){for (int i = 0; i < subregionList.size(); i++) {// 該分區為第一個分區if (subregionList.get(i).task.taskName == null && i == 0){// 同時第二個分區也為空，合并if ((i + 1) < subregionList.size() && subregionList.get(i + 1).task.taskName == null){// 將兩個分區大小合并subregionList.get(i).endAddress = subregionList.get(i + 1).endAddress;subregionList.get(i).partitionSpace = subregionList.get(i).endAddress - subregionList.get(i).startAddress;subregionList.get(i).freeSpace = subregionList.get(i).partitionSpace;// 將第二個分區大小變成0subregionList.get(i + 1).startAddress = subregionList.get(i + 1).endAddress;subregionList.get(i + 1).partitionSpace = 0;subregionList.get(i + 1).freeSpace = 0;}}// 該分區不是第一個分區if (subregionList.get(i).task.taskName == null && i != 0){// 如果該分區的前一個分區為空閑分區if (subregionList.get(i - 1).task.taskName == null){// 將該分區合并到前一個分區subregionList.get(i - 1).endAddress = subregionList.get(i).endAddress;subregionList.get(i - 1).partitionSpace = subregionList.get(i - 1).endAddress - subregionList.get(i - 1).startAddress;subregionList.get(i - 1).freeSpace = subregionList.get(i - 1).partitionSpace;// 該分區大小變成0subregionList.get(i).startAddress = subregionList.get(i).endAddress;subregionList.get(i).partitionSpace = 0;subregionList.get(i).freeSpace = 0;}}}// 刪除分區空間為0的分區deleteSubregion(subregionList);num --;}sortByFreeSpace(subregionList);System.out.println("回收成功！");} else if (flag == -1){System.out.println("作業不存在！");}} else {System.out.println("請初始化分區！");}break;case 4:// 內存信息if (totalSpace != 0){System.out.println("總內存空間：" + totalSpace);for (Subregion2 subregion : subregionList) {System.out.println(subregion);}} else {System.out.println("請初始化分區！");}break;default:break outside; // 退出外層循環}}scanner.close();}/*** 該方法用于將分區按起始地址排序*/public static void sortByStartAddress(List<Subregion2> subregionList){for (int i = 0; i < subregionList.size(); i++) {for (int j = 0; j + 1 < subregionList.size() - i; j++) {if (subregionList.get(j).startAddress > subregionList.get(j + 1).startAddress){Collections.swap(subregionList, j, j + 1);}}}}/*** 該方法用于將空閑分區按空閑空間大小排序* 被占用的分區放到最后*/public static void sortByFreeSpace(List<Subregion2> subregionList){for (int i = 0; i < subregionList.size(); i++) {for (int j = 0; j + 1 < subregionList.size() - i; j++) {if (subregionList.get(j).freeSpace > subregionList.get(j + 1).freeSpace){Collections.swap(subregionList, j, j + 1);}}}List<Subregion2> list = new ArrayList<>();Iterator<Subregion2> iterator = subregionList.iterator();while (iterator.hasNext()){Subregion2 subregion2 = iterator.next();if (subregion2.freeSpace == 0){list.add(subregion2);iterator.remove();}}subregionList.addAll(list);}/*** 該方法用于刪除總空間為0的分區*/public static void deleteSubregion(List<Subregion2> subregionList){subregionList.removeIf(subregion -> subregion.partitionSpace == 0);}// 分區信息static class Subregion2 {private int startAddress; // 起始地址private int endAddress; // 結束地址private int partitionSpace; // 該分區的總空間private int freeSpace; // 空閑空間Task2 task = new Task2(); // 作業信息public Subregion2(int startAddress, int endAddress, int partitionSpace, int freeSpace) {this.startAddress = startAddress;this.endAddress = endAddress;this.partitionSpace = partitionSpace;this.freeSpace = freeSpace;}public Subregion2() {}@Overridepublic String toString() {String taskInfo = "";if (task.taskName != null){taskInfo = " " + "分區中作業信息：\n" + " " + task;}return "分區信息：" +"起始地址：" + startAddress +", 結束地址：" + endAddress +", 分區總空間：" + partitionSpace +", 空閑空間：" + freeSpace + "\n" +taskInfo;}}// 作業信息static class Task2{private String taskName; // 作業名private int taskSize; // 作業大小@Overridepublic String toString() {return "作業名：'" + taskName + '\'' +", 作業大小: " + taskSize;}}}

三、運行結果：

1、首次適應算法：

2、最佳適應算法：?

總結

以上是生活随笔為你收集整理的操作系统：动态分区存储（首次适应算法、最佳适应算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。