操作系统：Java模拟内存管理（循环首次适应算法、回收空间算法）

电玩女神 2023-03-13 05:16 15阅读 0赞

--------------------

***本人是个新手，写下博客用于自我复习、自我总结。  
本人编写算法水平不高，可能会有错误，仅供各位参考。***

--------------------

输出效果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70]

import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.Scanner;
    
    /** * @author zsx * @Date: 2020/5/11 * */
    public class MemoryManage { 
    	public static void main(String args[]) { 
    
    		// 为整段内存划分分区
    		LinkedList areaList = new LinkedList();
    		// 用来记录每段分区是否空闲 0为空闲 1为占用
    		LinkedList isFreeList = new LinkedList();
    		int areaSize = 0; // 用于记录每个分区的大小
    
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请问您想将整个分区分成几段？");
    		int areaNum = sc.nextInt(); // 分区数
    		System.out.println("请问每个分区都占多大？");
    		for (int i = 0; i < areaNum; i++) { 
    			// 为每个分区分配空间
    			areaSize = sc.nextInt();
    			areaList.add(areaSize);
    			isFreeList.add(0);
    		}
    
    		int requestSize = 0; // 用于记录将要请求内存的大小
    		boolean judge = true; // 用于记录什么时候结束
    		int request = 0; // 用于记录是否要请求空间
    		int index = 0; // 用于记录当前链表运行到区间的下标
    		int indexBest = 0; // 用于记录最终需要划分的区间下标
    		int areaListVal = 0; // 用于记录链表中每一个区间的值
    		int isFreeListVal = 0; // 用于记录每一个分区是否被使用
    		int spaceNum = 0; // 用于记录分区号
    		String a = ""; // 用于记录描述性词汇
    		Iterator areaListIt = areaList.iterator(); // 链表1迭代器
    		Iterator isFreeListIt = isFreeList.iterator(); // 链表2迭代器
    		/* * 循环首次适应算法： * 不进行分区排序，每次从上次找到的空闲分区的下一个分区进行查找 */
    		while (judge) { 
    			//每次进入循环都要刷新迭代器
    			areaListIt = areaList.iterator();
    			isFreeListIt = isFreeList.iterator();
    			System.out.println("---内存状态---");
    			System.out.println("分区号 状态 分区大小");
    			//遍历链表，输出当前内存状态
    			while (areaListIt.hasNext()) { 
    				if ((int) isFreeListIt.next() == 0) { 
    					a = "空闲";
    				} else { 
    					a = "占用";
    				}
    				System.out.println(spaceNum + " " + a + " "
    						+ (int) areaListIt.next());
    				spaceNum++;
    			}
    			//遍历链表后，刷新迭代器
    			areaListIt = areaList.iterator();
    			isFreeListIt = isFreeList.iterator();
    			//初始化区间号
    			spaceNum = 0;
    			
    			while (true) { 
    				System.out.println("请问您要请求空间吗？（Y:1/N:2）");
    				request = sc.nextInt();
    				if (request == 1 || request == 2) { 
    					break;
    				} else { 
    					System.out.println("请输入指定数字");
    				}
    			}
    			if (request == 2) { 
    				break;
    			}
    			System.out.println("请问您要占用多大的空间？");
    			requestSize = sc.nextInt();
    
    			//先将迭代器移动到上一次迭代器结束的位置
    			while (indexBest != 0) { 
    				areaListIt.next();
    				isFreeListIt.next();
    				indexBest--;
    			}
    			//循环次数肯定不大于链表大小
    			for (int j = 0; j < areaList.size(); j++) { 
    				//当链表已经循环到了链表尾，就回到起始点
    				if (!areaListIt.hasNext()) { 
    					areaListIt = areaList.iterator();
    					isFreeListIt = isFreeList.iterator();
    				}
    				//获得当前位置上的值
    				isFreeListVal = (int) isFreeListIt.next();
    				areaListVal = (int) areaListIt.next();
    				//只有当前区间空闲，且请求内存值小于目前空闲区的值
    				if (isFreeListVal == 0 && requestSize < areaListVal) { 
    					//只要满足条件，就将找到的第一个空闲区进行分割
    					areaList.set(index, areaListVal - requestSize); // 先覆盖第一个值
    					areaList.add(requestSize); // 然后添加第二个值
    					isFreeList.add(1); //将其设为占用区
    					index++;
    					indexBest = index;
    					//一旦index到达了链表尾，就从头计数
    					if (index == areaList.size()) { 
    						index = 0;
    					}
    					break;
    				}
    				index++;
    				//一旦index到达了链表尾，就从头计数
    				if (index == areaList.size()) { 
    					index = 0;
    				}
    				//如果循环次数即将大于链表大小，就代表着：
    				//对链表循环了一圈，没有找到能够存放请求内存大小的区间
    				if ((j + 1) == areaList.size()) { 
    					request = 3;
    				}
    			}
    			//无法满足条件，就回到循环开始
    			if (request == 3) { 
    				System.out.println("请求占用的空间超过了当前所有内存，请重试");
    			}
    		}
    		
    		judge = true; //以防万一，初始化judge
    		int preAreaVal = 0; // 用于记录上一个空闲区的值
    		int nextAreaVal = 0; // 用于记录下一个空闲区的值
    		System.out.println("回收空间过程如下：");
    		/* * 回收空间算法： * 若回收的分区有上邻空闲分区和（或）下邻空闲分区， * 要求合并为一个空闲分区登记在空闲分区表的一个表项里 */
    		while (judge) { 
    			//每次循环都要刷新迭代器
    			areaListIt = areaList.iterator();
    			isFreeListIt = isFreeList.iterator();
    			index = 0; //初始化下标
    			
    			for (int k = 0; k < areaList.size(); k++) { 
    				//获取当前区域值
    				areaListVal = (int) areaListIt.next();
    				if ((int) isFreeListIt.next() == 1) {  // 找到了第一个占用区
    					// 占用形式分为五种：
    					// （1）0 1 1
    					// （2）0 1 0
    					// （3）1 1 0
    					// （4）1 0 0
    					// （5）0 0 1
    					if (isFreeListIt.hasNext()) {  // 只要当前占用区间，还存在下一个区间
    						if ((int) isFreeListIt.next() == 0) {  // 下一个区间是空闲的
    							if (index == 0) {  // 适用于情况4
    								areaList.set(index + 1, areaListVal + (int) areaListIt.next());
    								areaList.remove(index);
    								isFreeList.remove(index);
    								break;
    							}
    							// 适用于情况2
    							areaList.set(index - 1, areaListVal + (int) areaListIt.next() + preAreaVal);
    							areaList.remove(index + 1);
    							areaList.remove(index);
    							isFreeList.remove(index);
    							isFreeList.remove(index + 1);
    							break;
    						} else {  //下一个区间是被占用的
    							if(index == 0){ //适用于情况3
    								areaList.set(index, areaListVal);
    								isFreeList.set(index, 0);
    								break;
    							}else{  //适用于情况1
    								areaList.set(index - 1, areaListVal + preAreaVal);
    								areaList.remove(index);
    								isFreeList.remove(index);
    								break;
    							}
    						}
    					} else {  // 适用于情况5
    						areaList.set(index - 1, areaListVal + preAreaVal); // 先覆盖第一个值
    						areaList.remove(index);
    						isFreeList.remove(index);
    						break;
    					}
    				}
    				index++;
    				//只要当前区间不是占用区，就把这个值记录下来
    				preAreaVal = areaListVal;
    				//如果遍历了链表，没有再找到占用区，就证明算法结束
    				if ((k + 1) == areaList.size()) { 
    					judge = false;
    				}
    			}
    			if (judge == false) { 
    				break;
    			}
    			//刷新迭代器
    			areaListIt = areaList.iterator();
    			isFreeListIt = isFreeList.iterator();
    			System.out.println("---内存状态---");
    			System.out.println("分区号 状态 分区大小");
    			while (areaListIt.hasNext()) { 
    				if ((int) isFreeListIt.next() == 0) { 
    					a = "空闲";
    				} else { 
    					a = "占用";
    				}
    				System.out.println(spaceNum + " " + a + " "
    						+ (int) areaListIt.next());
    				spaceNum++;
    			}
    			spaceNum = 0;
    			areaListIt = areaList.iterator();
    			isFreeListIt = isFreeList.iterator();
    		}
    		System.out.println("结束");
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70]: /images/20230312/c2699235b2264847b844c6d317b557b9.png