操作系统：Java模拟页面置换算法（最佳置换算法、先进先出算法、最近最久未使用算法）

た入场券 2023-02-12 10:29 11阅读 0赞

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

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

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

import java.util.Scanner;
    
    /** * @author zsx * @Date: 2020/6/8 * 说明：本次算法的编写不算成功，考虑到一个方面后，另一方面就又会出现漏洞。 * 而在这个不断修补的过程中，使得整体算法变得不够合理。 * 希望之后在编写程序时，能够考虑好每个方面。 * 虽然设计的不合理，但是四种页面置换算法也算是实现了。 * */
    public class PageReplace { 
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请问您想为进程分配几个物理块（推荐 3或4）？");
    		int blockNum = sc.nextInt(); // 物理块数
    		int blockArr[] = new int[blockNum]; // 根据物理块数建立物理块数组
    		for (int k = 0; k < blockNum; k++) {  // 初始化物理块数组
    			blockArr[k] = -1; // -1表示当前位置没有页面存放
    		}
    		
    		// 初始化页面号引用串
    		int arr[] = {  1, 2, 5, 7, 5, 7, 1, 4, 3, 5, 6, 4, 3, 2, 1, 5, 2 };
    
    		// 为最近最久未使用算法做准备
    		int time[] = new int[blockNum]; // 用数组来判断每个页面上次被调用的时间（即在物理块中的等待时长）
    		// 初始化得到的结果举例： time{2,1,0} 意味着：
    		// 物理块的 0号位已经过了2次操作未被调用
    		// 1号位已经过了1次操作未被调用
    		// 2号位已经过了0次操作未被调用，即刚被调用
    		// 因此如果之后该位置的页面被替换或者被调用，则将该页面下标位置的元素重置为0
    		// 然后 其他位置元素，自加一
    		// 而每次替换的页面都是这个值最大的位置上的页面
    		int timeIndex = 0; // 用于记录哪个页面被调用
    		
    		// 为最少使用算法做准备
    		int arrNoRepeat[] = new int[arr.length]; // 首先对arr数组去重
    		int arrIndex = 0; // 记录arrNoRepeat中存放数据的个数
    		for(int b = 0; b < arr.length; b++){ 
    			if(arrIndex == 0){  // 只要arrNoRepeat数组为空，那就先把第一个值存入
    				arrNoRepeat[0] = arr[0];
    				arrIndex++;
    				continue;
    			}
    			for(int c = 0; c < arrIndex ; c++){ 
    				if(arr[b] == arrNoRepeat[c]){  // 只要重复，就跳出循环
    					break;
    				}
    				if(c+1 == arrIndex){  // 遍历到arrNoRepeat最后一位仍没有重复，就把这个值存放进来
    					arrNoRepeat[c+1] = arr[b];
    					arrIndex++;
    					break;
    				}
    			}
    		}
    		int time1[] = new int[arrIndex]; // 用来记录每个页面的使用次数，它和arrNoRepeat的页面号一一对应
    		for(int g = 0; g < arrIndex; g++){ 
    			// 初始化time1
    			time1[g] = 0;
    		}
    		
    		System.out.println("物理块初始化过程：");
    		/** * 功能：初始化物理块数组 因为物理块最开始必然是空的，因此必然会根据物理块大小先存放相应个数的页面 * （因为该部分每个算法都要做，放进算法中重复率太高，因此拿出来单独处理） * */
    		int position = blockNum; // 用于判断物理块什么时候第一次存满
    		for (int i = 0; i < arr.length; i++) { 
    			// 如果说物理块中已经没有空位置，就跳出循环，开始算法
    			if (blockArr[blockNum - 1] != -1) { 
    				break;
    			}
    			for (int j = 0; j < blockNum; j++) { 
    				// 只要物理块当前位置没存放页面，就立刻存放新页面
    				if (blockArr[j] == -1) { 
    					blockArr[j] = arr[i];
    					// 记录当前存放位置的下标，time就不自加这个位置，同时这个位置置0
    					timeIndex = j;
    					time[j] = 0;
    					
    					// 判断当前页面在arrNoRepeat中的位置，让其访问次数+1
    					for(int d = 0; d < arrIndex; d++){ 
    						if(arr[i] == arrNoRepeat[d]){  //找到位置
    							time1[d]++;
    							break;
    						}
    					}
    					
    					blockOutput(blockArr);
    					break;
    				}
    				
    				// 如果遇到了相同的页面，跳过当前页面，记录的编号要向后推移
    				if (blockArr[j] == arr[i]) { 
    					// position就是为了这种情况准备的，方便后续算法进行循环处理
    					position++;
    					// 记录当前存放位置的下标，time就不自加这个位置，同时这个位置置0
    					timeIndex = j;
    					time[j] = 0;
    					
    					// 判断当前页面在arrNoRepeat中的位置，让其访问次数+1
    					for(int d = 0; d < arrIndex; d++){ 
    						if(arr[i] == arrNoRepeat[d]){  //找到位置
    							time1[d]++;
    							break;
    						}
    					}
    					
    					System.out.println("物理块无变化");
    					break;
    				}
    			}
    			for (int m = 0; m < blockNum; m++) { 
    				if (m == timeIndex) {  // 当前操作页面不加1
    					continue;
    				}
    				// 其他未操作页面，等待时长自加1
    				time[m]++;
    			}
    		}
    		
    		// 设立这些tranArr是为了避免blockArr数据被修改
    		int tranArr[] = new int[blockNum];
    		for(int a = 0; a < blockNum; a++){ 
    			tranArr[a] = blockArr[a];
    		}
    		System.out.println("");
    		System.out.println("物理块初始化的结果：");
    		blockOutput(blockArr);
    		System.out.println("最佳置换算法：");
    		Optimal(arr, tranArr, blockNum, position);   // 最佳置换算法
    		
    		int tranArr1[] = new int[blockNum];
    		for(int a = 0; a < blockNum; a++){ 
    			tranArr1[a] = blockArr[a];
    		}
    		System.out.println("");
    		System.out.println("物理块初始化的结果：");
    		blockOutput(blockArr);
    		System.out.println("先进先出算法：");
    		FIFO(arr, tranArr1, blockNum, position);      // 先进先出算法
    		
    		int tranArr2[] = new int[blockNum];
    		for(int a = 0; a < blockNum; a++){ 
    			tranArr2[a] = blockArr[a];
    		}
    		System.out.println("");
    		System.out.println("物理块初始化的结果：");
    		blockOutput(blockArr);
    		System.out.println("最近最久未使用算法：");
    		LRU(arr, tranArr2, blockNum, position, time); // 最近最久未使用算法
    		
    		int tranArr3[] = new int[blockNum];
    		for(int a = 0; a < blockNum; a++){ 
    			tranArr3[a] = blockArr[a];
    		}
    		System.out.println("");
    		System.out.println("物理块初始化的结果：");
    		blockOutput(blockArr);
    		System.out.println("最少使用算法：");
    		LFU(arr, tranArr3, blockNum, position, arrNoRepeat, arrIndex, time1); // 最少使用算法
    	}
    
    	/** * 最佳置换算法：所选择的被淘汰页面是以后永不使用或最长时间不再被访问的页面 * 相关参数： * arr：存放页面号的待处理原数组 * blockArr: 物理块中存放页面号的数组 * blockNum: 记录物理块大小 * position: 记录算法中循环的起始位置 * */
    	public static void Optimal(int arr[], int blockArr[], int blockNum, int position) { 
    		int index = 0;     // 用于记录应该被淘汰页面的下标
    		int judge = 0;     // 用于记录页面在以后没被访问的最长时间
    		int pageExist = 0; // 用于判断页面是否存在于物理块数组中
    		
    		// 请求调入页面次数，用于判断缺页率（初始值一定是物理块大小次）
    		int requestReplace = blockNum;
    		
    		for (int i = position; i < arr.length; i++) { 
    			// 拿到新页面，首先判断，它是否是物理块中已经存在的页面
    			for (int j = 0; j < blockNum; j++) { 
    				// 如果当前页面存在于物理块中，就去判断下一个页面
    				if (arr[i] == blockArr[j]) { 
    					System.out.println("物理块无变化");
    					break;
    				}
    				if (judge == arr.length - 1) { 
    					// 如果找到了以后永不使用的页面，就不再判断物理块中其他页面
    					// 因为如果需要淘汰页面，就淘汰这个永不使用的页面即可
    				} else { 
    					// 找出物理块数组中最应该被替换的页面
    					for (int k = i + 1; k < arr.length; k++) { 
    						// 寻找最长时间不被访问的页面
    						if (blockArr[j] == arr[k]) { 
    							if (k > judge) {  //如果当前页面比上一个页面以后未被使用的时间长
    								index = j;   // 暂且认为当前页面是被淘汰页面，记录它的下标
    								judge = k;   // 更改数值，去和下个满足条件的页面判断
    								break;
    							} else {  // 如果当前页面没有上一个页面以后未被使用的时间长，就退出循环
    								break;
    							}
    						}
    						// 如果遍历到原数组的尾部 也没再找到一个和当前页面相同的页面
    						// 那么这个页面肯定是 以后永不使用的页面
    						if (k == arr.length - 1) { 
    							index = j; // 记录它的下标
    							judge = k; // 记录它的最值，且当前这个值一定是arr.length-1
    							break;
    						}
    					}
    				}
    				pageExist++;
    				// 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足最佳置换的页面
    				if (pageExist == blockNum) {  
    					// 通过上面得到的index下标，替换这个需要被淘汰的页面
    					blockArr[index] = arr[i];
    					// 请求调入页面次数加1
    					requestReplace++;
    					
    					blockOutput(blockArr);
    				}
    			}
    			index = 0;     // 归零初始化
    			judge = 0;     // 归零初始化
    			pageExist = 0; // 归零初始化
    		}
    		pageMissingRate(requestReplace, arr); // 计算缺页率
    	}
    
    	/** * 先进先出算法：总是淘汰最先进入内存的页面 * 相关参数： * arr：存放页面号的待处理原数组 * blockArr: 物理块中存放页面号的数组 * blockNum: 记录物理块大小 * position: 记录算法中循环的起始位置 * */
    	public static void FIFO(int arr[], int blockArr[], int blockNum, int position) { 
    		int index = 0;     // 用于记录应该被淘汰页面的下标（相当于指针）
    		int pageExist = 0; // 用于判断页面是否存在于物理块数组中
    		
    		// 请求调入页面次数，用于判断缺页率
    		int requestReplace = blockNum;
    		
    		for (int i = position; i < arr.length; i++) { 
    			// 拿到新页面，首先判断，它是否是物理块中已经存在的页面
    			for (int j = 0; j < blockNum; j++) { 
    				// 如果当前页面存在于物理块中，就去判断下一个页面
    				if (arr[i] == blockArr[j]) { 
    					System.out.println("物理块无变化");
    					break;
    				}
    				pageExist++;
    				// 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足先进先出的页面
    				if (pageExist == blockNum) {  
    					// 通过上面得到的index下标，替换这个需要被淘汰的页面
    					blockArr[index] = arr[i];
    					// 请求调入页面次数加1
    					requestReplace++;
    					// 指针后移
    					index++;
    					
    					blockOutput(blockArr);
    				}
    			}
    			if (index == blockNum) {  // 如果到了物理块尾部，就回到物理块头部
    				index = 0;
    			}
    			pageExist = 0; // 归零初始化
    		}
    		pageMissingRate(requestReplace, arr); // 计算缺页率
    	}
    
    	/** * 最近最久未使用算法：总是淘汰最近最久未使用的页面 * 相关参数： * arr：存放页面号的待处理原数组 * blockArr: 物理块中存放页面号的数组 * blockNum: 记录物理块大小 * position: 记录算法中循环的起始位置 * time: 物理块中各页面距上一次被调用的时长 * */
    	public static void LRU(int arr[], int blockArr[], int blockNum, int position, int time[]) { 
    		int index = 0;     // 用于记录被淘汰页面的下标
    		int pageExist = 0; // 用于判断页面是否存在于物理块数组中
    		int best = 0;      // 用于记录changeArr方法的返回值
    		
    		// 请求调入页面次数，用于判断缺页率
    		int requestReplace = blockNum;
    		
    		for (int i = position; i < arr.length; i++) { 
    			// 拿到新页面，首先判断，它是否是物理块中已经存在的页面
    			for (int j = 0; j < blockNum; j++) { 
    				// 如果当前页面存在于物理块中，就去判断下一个页面
    				if (arr[i] == blockArr[j]) { 
    					// 这个位置的页面被调用过，因此重新置0，同时记录下标index，让除了这个下标的其他位置等待时长加1
    					index = j;
    					time[index] = 0;
    					
    					System.out.println("物理块无变化");
    					break;
    				}
    				pageExist++;
    				// 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足最近最久未使用的页面
    				if (pageExist == blockNum) { 
    					// 拿到物理块数组中，最近最久未被使用的页面的下标（即等待时间最长的）
    					best = changeArr(time);
    					// 将这个页面淘汰
    					blockArr[best] = arr[i];
    					// 记录这个淘汰页面的下标，当前新页面重新置0，其他页面等待时长加1
    					index = best;
    					time[index] = 0;
    					// 请求调入页面次数加1
    					requestReplace++;
    					
    					blockOutput(blockArr);
    				}
    			}
    			for (int m = 0; m < blockNum; m++) { 
    				if (m == index) {  // 当前操作页面不加一
    					continue;
    				}
    				// 其他未操作页面，等待时长自加1
    				time[m]++;
    			}
    			index = 0;     // 归零初始化
    			pageExist = 0; // 归零初始化
    		}
    		pageMissingRate(requestReplace, arr); // 计算缺页率
    	}
    
    	/** * 功能：返回最近最久未使用算法中time数组最近最久未使用页面的下标 * */
    	public static int changeArr(int time[]) { 
    		int index = 0; // 记录返回页面的下标
    		int best = -1; // 记录最大值变化情况
    		for (int i = 0; i < time.length; i++) { 
    			if (time[i] > best) { 
    				best = time[i];
    				index = i;
    			}
    		}
    		return index;
    	}
    
    	/** * 最少使用算法：总是淘汰在最近时期使用最少的页面作为淘汰页 * 相关参数： * arr：存放页面号的待处理原数组 * blockArr: 物理块中存放页面号的数组 * blockNum: 记录物理块大小 * position: 记录算法中循环的起始位置 * arrNoRepeat: 存放每个页面的页面号 * arrIndex: 记录time数组的大小 * time: 记录每个页面的使用次数 * */
    	public static void LFU(int arr[], int blockArr[], int blockNum, int position, int arrNoRepeat[], int arrIndex, int time[]) { 
    		int pageExist = 0;   // 用于判断页面是否存在于物理块数组中
    		int visitLess = 100; // 记录访问次数最小值
    		int index = 0;       // 记录被淘汰页面的下标
    		
    		// 请求调入页面次数，用于判断缺页率
    		int requestReplace = blockNum;
    		
    		for (int i = position; i < arr.length; i++) { 
    			for (int j = 0; j < blockNum; j++) { 
    				// 如果当前页面存在于物理块中，就去判断下一个页面
    				if (arr[i] == blockArr[j]) { 
    					
    					// 判断当前页面在arrNoRepeat中的位置，让其访问次数+1
    					for(int d = 0; d < arrIndex; d++){ 
    						if(arr[i] == arrNoRepeat[d]){  //找到位置
    							time[d]++;
    							break;
    						}
    					}
    					
    					System.out.println("物理块无变化");
    					break;
    				}
    				pageExist++;
    				// 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足最少使用的页面
    				if (pageExist == blockNum) {  
    					
    					// 判断现在存在于物理块中的页面，哪个访问次数最少
    					for(int k = 0; k < blockNum; k++){ 
    						for(int m = 0 ; m < arrIndex; m++){ 
    							if(blockArr[k] == arrNoRepeat[m]){ 
    								// 找到
    								if(time[m] < visitLess){ 
    									index = k;
    									visitLess = time[m];
    									break;
    								}
    							}
    						}
    					}
    					visitLess = 100; // 初始化
    					requestReplace++;
    					// 将这个页面淘汰
    					blockArr[index] = arr[i];
    					
    					// 判断当前页面在arrNoRepeat中的位置，让其访问次数+1
    					for(int d = 0; d < arrIndex; d++){ 
    						if(arr[i] == arrNoRepeat[d]){  //找到位置
    							time[d]++;
    							break;
    						}
    					}
    					
    					blockOutput(blockArr);
    				}
    			}
    			pageExist = 0; // 归零初始化
    		}
    		pageMissingRate(requestReplace, arr); // 计算缺页率
    	}
    	/** * 功能：输出物理块数组情况 * */
    	public static void blockOutput(int blockArr[]) { 
    		System.out.print("当前物理块中的页面号：");
    		for (int i = 0; i < blockArr.length; i++) { 
    			System.out.print(blockArr[i] + " ");
    		}
    		System.out.println("");
    	}
    
    	/** * 功能：缺页率的计算，缺页率 = 请求调入的次数 / 页面总数 * */
    	public static void pageMissingRate(int num, int arr[]) { 
    		System.out.print("该算法总共缺页" + num + "次，缺页率为" + (num / (double) arr.length));
    		System.out.println("");
    	}
    }