操作系统：Java模拟磁盘调度算法（先来先服务、最短寻道优先、电梯调度方法）

左手的ㄟ右手 2023-02-14 07:46 28阅读 0赞

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

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

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

/** * @author zsx * @Date: 2020/6/8 * 代码功能：使用先来先服务、最短寻道优先、电梯调度方法进行调度。 * 求出平均移动道数。当前读写头在90号，向磁道号增加的方向移动。 * */
    public class DiskScheduling { 
    
    	public static void main(String args[]) { 
    		// 磁道按访问顺序初始化
    		int diskArr[] = {  30, 50, 100, 180, 20, 90, 150, 70, 80, 10, 160 };
    		String serviceOrder[] = {  "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K" };
    
    		System.out.println("先来先服务算法：");
    		// 调用先来先服务算法
    		FCFS(diskArr, serviceOrder);
    
    		// 使用插入排序算法对distArr和serviceOrder进行排序，以便进行后续算法操作
    		insertSort(diskArr, serviceOrder);
    
    		System.out.println("最短寻道时间优先算法：");
    		// 调用最短寻道时间优先算法
    		SSTF(diskArr, serviceOrder);
    
    		System.out.println("电梯调度算法：");
    		// 调用电梯调度算法
    		SCAN(diskArr, serviceOrder);
    	}
    
    	/** * FCFS功能：先来先服务 * 参数含义： * distArr：存放磁道号的数组 * serviceOrder：存放请求服务的顺序 * */
    	public static void FCFS(int diskArr[], String serviceOrder[]) { 
    		int moveDistance[] = new int[diskArr.length]; // 记录移动距离
    		
    		int readWriteHead = 90; // 读写头在90号开始
    		for (int i = 0; i < diskArr.length; i++) { 
    			if (readWriteHead < diskArr[i]) { 
    				moveDistance[i] = diskArr[i] - readWriteHead;
    				readWriteHead = diskArr[i];
    			} else { 
    				moveDistance[i] = readWriteHead - diskArr[i];
    				readWriteHead = diskArr[i];
    			}
    		}
    		System.out.println("磁盘访问顺序：");
    		outputArr(serviceOrder);
    		calculateAverage(moveDistance);
    	}
    
    	/** * SSTF功能：最短寻道时间优先 * 参数含义： * distArr：存放磁道号的数组 * serviceOrder：存放请求服务的顺序 * */
    	public static void SSTF(int diskArr[], String serviceOrder[]) { 
    		int moveDistance[] = new int[diskArr.length]; // 记录移动距离
    
    		String order[] = new String[diskArr.length];  // 避免原始数组被修改
    
    		int readWriteHead = 90; // 读写头在90号开始
    		int indexL = 0; 		// 用于记录左下标
    		int indexR = 0; 		// 用于记录右下标
    		int numOrder = 0;       // 用于记录order下标
    		int situation = 0;      // 表示两种情况，0为出现相等，1为没出现相等
    		
    		for (int i = 0; i < diskArr.length; i++) { 
    			if (diskArr[i] == readWriteHead) { 
    				// 如果相等，那就直接先访问这个磁道号
    				// 这个磁道号的上下两个位置，必是一大一小
    				moveDistance[0] = 0;
    				order[0] = serviceOrder[i];
    				indexL = i - 1;
    				indexR = i + 1;
    				break;
    			} else if (diskArr[i] > readWriteHead) { 
    				// 如果没相等，那么找到第一个大于读写头的前一个位置和当前位置，必是一大一小
    				indexL = i - 1;
    				indexR = i;
    				situation = 1;
    				break;
    			}
    		}
    		
    		while(true){ 
    			if(situation == 0){ 
    				numOrder = 1;  // order需要从1号位开始记录
    			}
    			while(indexL >= 0 && indexR < diskArr.length){ 
    				if(diskArr[indexR] - readWriteHead > readWriteHead - diskArr[indexL]){ 
    					// 向减小方向移动
    					moveDistance[numOrder] = readWriteHead - diskArr[indexL];
    					order[numOrder] = serviceOrder[indexL];
    					readWriteHead = diskArr[indexL];
    					indexL--;
    					numOrder++;
    				}else{ 
    					// 向增大方向移动
    					moveDistance[numOrder] = diskArr[indexR] - readWriteHead;
    					order[numOrder] = serviceOrder[indexR];
    					readWriteHead = diskArr[indexR];
    					indexR++;
    					numOrder++;
    				}
    			}
    			// 跳出上一个循环，必然证明下一个循环一定是单方向
    			while(indexL >= 0){ 
    				// 如果左侧还有元素
    				moveDistance[numOrder] = readWriteHead - diskArr[indexL];
    				order[numOrder] = serviceOrder[indexL];
    				readWriteHead = diskArr[indexL];
    				indexL--;
    				numOrder++;
    			}
    			while(indexR < diskArr.length){ 
    				// 如果右侧还有元素
    				moveDistance[numOrder] = diskArr[indexR] - readWriteHead;
    				order[numOrder] = serviceOrder[indexR];
    				readWriteHead = diskArr[indexR];
    				indexR++;
    				numOrder++;
    			}
    			// 如果遍历过所有位置就跳出
    			break;
    		}
    		
    		System.out.println("磁盘访问顺序：");
    		outputArr(order);
    		calculateAverage(moveDistance);
    	}
    	
    	/** * SCAN功能：扫描算法（电梯调度算法） * 参数含义： * distArr：存放磁道号的数组 * serviceOrder：存放请求服务的顺序 * */
    	public static void SCAN(int diskArr[], String serviceOrder[]) { 
    		int moveDistance[] = new int[diskArr.length]; // 记录移动距离
    
    		String order[] = new String[diskArr.length]; // 避免原始数组被修改
    
    		int readWriteHead = 90; // 读写头在90号开始
    		int index = 0; 			// 用于记录下标
    		int situation = 0; 		// 用于记录两种情况 0为出现相等 1为没出现相等
    
    		// 题目规定：向磁道号增加的方向移动
    		for (int i = 0; i < diskArr.length; i++) { 
    			if (diskArr[i] == readWriteHead) { 
    				// 如果相等，那就直接先访问这个磁道号
    				// 这个磁道号的上下两个位置，必是一大一小
    				moveDistance[i] = 0;
    				situation = 0;
    				index = i;
    				break;
    			} else if (diskArr[i] > readWriteHead) { 
    				// 如果没相等，那么找到第一个大于读写头的前一个位置和当前位置，必是一大一小
    				situation = 1;
    				index = i;
    				break;
    			}
    		}
    
    		int num = 0; // 用于记录order中下标的位置
    
    		// 情况1
    		if (situation == 0) { 
    			order[num] = serviceOrder[index];
    			num++;
    			// 先向增大方向
    			for (int k = index + 1; k < diskArr.length; k++) { 
    				moveDistance[k] = diskArr[k] - readWriteHead;
    				readWriteHead = diskArr[k];
    				order[num] = serviceOrder[k];
    				num++;
    			}
    			// 再向减小方向
    			for (int j = index - 1; j >= 0; j--) { 
    				moveDistance[j] = readWriteHead - diskArr[j];
    				readWriteHead = diskArr[j];
    				order[num] = serviceOrder[j];
    				num++;
    			}
    		} else { // 情况2
    			// 先向增大方向
    			for (int k = index; k < diskArr.length; k++) { 
    				moveDistance[k] = diskArr[k] - readWriteHead;
    				readWriteHead = diskArr[k];
    				order[num] = serviceOrder[k];
    				num++;
    			}
    			// 再向减小方向
    			for (int j = index - 1; j >= 0; j--) { 
    				moveDistance[j] = readWriteHead - diskArr[j];
    				readWriteHead = diskArr[j];
    				order[num] = serviceOrder[j];
    				num++;
    			}
    		}
    		System.out.println("磁盘访问顺序：");
    		outputArr(order);
    		calculateAverage(moveDistance);
    	}
    
    	/** * calculateAverage功能：计算平均移动道数 参数含义： moveDistance：记录移动距离的数组 * */
    	public static void calculateAverage(int moveDistance[]) { 
    		double sum = 0; // 用于记录距离的总和
    		for (int i = 0; i < moveDistance.length; i++) { 
    			sum += moveDistance[i];
    		}
    		System.out.println("该算法的平均移动道数为：" + (sum / moveDistance.length));
    	}
    
    	/** * insertSort功能：对传进来的数组进行插入排序 * */
    	public static void insertSort(int[] arr, String[] serviceOrder) { 
    		int insertVal = 0;
    		String insertVal2 = "";
    		int insertIndex = 0;
    		for (int i = 1; i < arr.length; i++) { 
    			insertVal = arr[i];
    			insertVal2 = serviceOrder[i];
    			insertIndex = i - 1;
    			while (insertIndex >= 0 && insertVal < arr[insertIndex]) { 
    				arr[insertIndex + 1] = arr[insertIndex];
    				serviceOrder[insertIndex + 1] = serviceOrder[insertIndex];
    				insertIndex--;
    			}
    			if (insertIndex + 1 != i) { 
    				arr[insertIndex + 1] = insertVal;
    				serviceOrder[insertIndex + 1] = insertVal2;
    			}
    		}
    	}
    
    	/** * outputArr功能：输出数组中的内容。 * */
    	public static void outputArr(String arr[]) { 
    		for (int i = 0; i < arr.length; i++) { 
    			System.out.print(arr[i] + " ");
    		}
    		System.out.println(" ");
    	}
    }