共享设备的典型代表为磁盘,磁盘物理块的地址由柱面号、磁头号、扇区号来指定,完成磁盘某一个物理块的访问要经过三个阶段:寻道时间Ts、旋转延迟时间Tw和读写时间Trw。现要算出各板块调度时间。
实验思路(1) 最短寻道时间优先算法(SSTF)
该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的,因而导致响应时间的变化幅度很大。在服务请求很多的情况下,对内外边缘磁道的请求将会无限期的被延迟,有些请求的响应时间将不可预期。
(2) 扫描算法(SCAN)电梯调度
扫描算法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。例如,当磁头正在自里向外移动时,扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样自里向外地访问,直到再无更外的磁道需要访问才将磁臂换向,自外向里移动。这时,同样也是每次选择这样的进程来调度,即其要访问的磁道,在当前磁道之内,从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行,故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点,而具有最短寻道时间优先算法的优点即吞吐量较大,平均响应时间较小,但由于是摆动式的扫描方法,两侧磁道被访问的频率仍低于中间磁道。
(3) 循环扫描算法(C-SCAN)
在扫描算法的基础上规定磁头单向移动来提供服务,回返时直接快速移动至起始端而不服务任何请求。
流程图 实验代码SSTF
package com.zjh.extra;
import java.util.*;
public class SSTF {
private static Scanner scanner = new Scanner(System.in);
private static Set diskSet = new HashSet<>(); //磁道序列
private static int beginIndex; //起始位置
private static int cur; //当前位置
private static Queue visitQueue = new LinkedList<>(); //访问序列
private static int totalVisitNum = 0; //总共经过的磁道数
public void show(){
System.out.print("访问序列:");
for (Integer integer : visitQueue) {
System.out.print(integer+" ");
}
System.out.println();
System.out.println("经过的磁道总数:" + totalVisitNum);
System.out.println("平均寻道长度:" + totalVisitNum * 1.0 / visitQueue.size());
}
public void run(){
while (diskSet.size() > 0){
//从当前位置开始 寻找其他距离最近的磁道进行访问
if(diskSet.size() == 0){
return;
}
int next = 0;
int length = Integer.MAX_VALUE;
//遍历set中元素,找到最近的
for (Integer disk : diskSet) {
if(Math.abs(disk - cur) < length){
next = disk;
length = Math.abs(disk - cur);
}
}
cur = next;
diskSet.remove(cur);
visitQueue.offer(cur);
totalVisitNum += length;
}
}
public void input(){
System.out.println("请输入磁盘请求序列长度:");
int num = scanner.nextInt();
System.out.println("请依次输入磁盘请求序列(空格分开):");
for(int i = 0;i < num; i++){
diskSet.add(scanner.nextInt());
}
System.out.println("请输入读写头起始位置:");
beginIndex = scanner.nextInt();
cur = beginIndex;
}
public static void main(String[] args) {
SSTF sstf = new SSTF();
sstf.input();
sstf.run();
sstf.show();
}
}
SCAN
package com.zjh.extra;
import java.util.*;
public class SCAN {
private static Scanner scanner = new Scanner(System.in);
private static Set diskSet = new HashSet<>(); //磁道序列
private static int beginIndex; //起始位置
private static int cur; //当前位置
private static Queue visitQueue = new LinkedList<>(); //访问序列
private static int totalVisitNum = 0; //总共经过的磁道数
private static int direction; //访问方向 1往磁道号增加方向 0往磁道数减少方向
public void show(){
System.out.print("访问序列:");
for (Integer integer : visitQueue) {
System.out.print(integer+" ");
}
System.out.println();
System.out.println("经过的磁道总数:" + totalVisitNum);
System.out.println("平均寻道长度:" + totalVisitNum * 1.0 / visitQueue.size());
}
public void run(){
while (diskSet.size() > 0){
//从当前位置开始 寻找其他距离最近的磁道进行访问
if(diskSet.size() == 0){
return;
}
int next = -1;
int length = Integer.MAX_VALUE;
//遍历set中元素,找到该方向最近的
if(direction == 1){
for (Integer disk : diskSet) {
if(disk > cur){ //增加方向
if(Math.abs(disk - cur) < length){
next = disk;
length = Math.abs(disk - cur);
}
}
}
if(next == -1){
//该方向没有了
direction = 0;
continue;
}
}
if(direction == 0){
for (Integer disk : diskSet) {
if(disk < cur){ //减少方向
if(Math.abs(disk - cur) < length){
next = disk;
length = Math.abs(disk - cur);
}
}
}
if(next == -1){
//该方向没有了
direction = 1;
continue;
}
}
cur = next;
diskSet.remove(cur);
visitQueue.offer(cur);
totalVisitNum += length;
}
}
public void input(){
System.out.println("请输入磁盘请求序列长度:");
int num = scanner.nextInt();
System.out.println("请依次输入磁盘请求序列(空格分开):");
for(int i = 0;i < num; i++){
diskSet.add(scanner.nextInt());
}
System.out.println("请输入读写头起始位置:");
beginIndex = scanner.nextInt();
cur = beginIndex;
System.out.println("请输入访问方向(1往磁道号增加方向 0往磁道数减少方向):");
direction = scanner.nextInt();
}
public static void main(String[] args) {
SCAN scan = new SCAN();
scan.input();
scan.run();
scan.show();
}
}
CSCAN
package com.zjh.extra;
import java.util.*;
public class CSCAN {
private static Scanner scanner = new Scanner(System.in);
private static Set diskSet = new HashSet<>(); //磁道序列
private static int beginIndex; //起始位置
private static int cur; //当前位置
private static Queue visitQueue = new LinkedList<>(); //访问序列
private static int totalVisitNum = 0; //总共经过的磁道数
private static int direction; //访问方向 1往磁道号增加方向 0往磁道数减少方向
public void show(){
System.out.print("访问序列:");
for (Integer integer : visitQueue) {
System.out.print(integer+" ");
}
System.out.println();
System.out.println("经过的磁道总数:" + totalVisitNum);
System.out.println("平均寻道长度:" + totalVisitNum * 1.0 / visitQueue.size());
}
public void run(){
boolean flag = false;
while (diskSet.size() > 0){
//从当前位置开始 寻找其他距离最近的磁道进行访问
if(diskSet.size() == 0){
return;
}
int next = -1;
int length = Integer.MAX_VALUE;
if(flag){
//该方向剩余没有了 循环
//找距离最远的
int max_length = 0;
int max_index = 0;
for (Integer disk : diskSet) {
if(Math.abs(disk - cur) > max_length){
max_index = disk;
max_length = Math.abs(disk - cur);
}
}
cur = max_index;
diskSet.remove(cur);
visitQueue.offer(cur);
totalVisitNum += max_length;
flag = false;
continue;
}
//遍历set中元素,找到该方向最近的
if(direction == 1 && !flag){
for (Integer disk : diskSet) {
if(disk > cur){ //增加方向
if(Math.abs(disk - cur) < length){
next = disk;
length = Math.abs(disk - cur);
}
}
}
if(next == -1){
flag = true;
continue;
}
}
if(direction == 0 && !flag){
for (Integer disk : diskSet) {
if(disk < cur){ //减少方向
if(Math.abs(disk - cur) < length){
next = disk;
length = Math.abs(disk - cur);
}
}
}
if(next == -1){
flag = true;
continue;
}
}
cur = next;
diskSet.remove(cur);
visitQueue.offer(cur);
totalVisitNum += length;
}
}
public void input(){
System.out.println("请输入磁盘请求序列长度:");
int num = scanner.nextInt();
System.out.println("请依次输入磁盘请求序列(空格分开):");
for(int i = 0;i < num; i++){
diskSet.add(scanner.nextInt());
}
System.out.println("请输入读写头起始位置:");
beginIndex = scanner.nextInt();
cur = beginIndex;
System.out.println("请输入访问方向(1往磁道号增加方向 0往磁道数减少方向):");
direction = scanner.nextInt();
}
public static void main(String[] args) {
CSCAN cscan = new CSCAN();
cscan.input();
cscan.run();
cscan.show();
}
}
运行结果



