import java.util.LinkedList;
import java.util.Scanner;
import java.text.DecimalFormat;
class Track
{
private int nextTrackNumber;
private int moveDistance;
private boolean Done;
Track(){}
Track(int nextTrackNumber)
{
this.nextTrackNumber=nextTrackNumber;
}
public int getnextTrackNumber() {
return nextTrackNumber;
}
public int getMoveDistance() {
return moveDistance;
}
public boolean isDone() {
return Done;
}
public void setDone(boolean done) {
Done = done;
}
public void setnextTrackNumber(int nextTrackNumber) {
this.nextTrackNumber = nextTrackNumber;
}
public void setMoveDistance(int moveDistance) {
this.moveDistance = moveDistance;
}
public Track[] FCFS(Track[]Track,int startTrackNumber)
{
//先到先服务算法
//求移动距离，移动距离等于|被访问的磁道号-移动距离|
//第一个单独处理：第一个磁道的移动距离=|访问的磁道号-开始的磁道号|
//当前的磁道的移动距离=|当前磁道号-上一个磁道号|
for(int index=0;index<Track.length;index++)
{
if(index==0)
{
Track[0].setMoveDistance(Math.abs(Track[0].getnextTrackNumber()-startTrackNumber));
continue;
}
else
{
Track[index].setMoveDistance(Math.abs(Track[index].getnextTrackNumber()-Track[index-1].getnextTrackNumber()));
}
}
return Track;
}
public int FindMinDistanceTrack(Track[]Track,int startTrackNumber)
{
//寻找距离当前磁道最近的磁道号
//遍历process，如该磁道没有分配完成，判断当前磁道号与开始的磁道号是否为距离最小
//若分配完成，则下一个再继续判断
int MinDistanceTrack=1000;//初始化磁道间最小距离
int NextTrack=0;
for(int i=0;i<Track.length;i++)
{
if(Track[i].isDone()!=true)
{
if( Math.abs(Track[i].getnextTrackNumber()-startTrackNumber )< MinDistanceTrack )
{
MinDistanceTrack=Math.abs(Track[i].getnextTrackNumber()-startTrackNumber );//记录最小移动距离
NextTrack=i;//记录下一个访问的磁道号
}
}
else continue;
}
//遍历完之后得到最小移动距离和下一个访问的磁道号
//这时候返回最小移动距离，并将该磁道号标记为完成
Track[NextTrack].setDone(true);//标记完成
return NextTrack; //返回下一个访问磁道号
}
public Track[] SSTF(Track[]Track,int startTrackNumber)
{
//最短寻道时间优先算法
//求移动距离，移动距离等于|被访问的磁道号-移动距离|
//首先找出第一个距离开始磁道最近的磁道号
Track[] newTrack=new Track[Track.length];//创建新对象数组，用于纪律经筛选后访问的磁道顺序
for(int i=0;i<newTrack.length;i++)
{
int nextTrackNumber=FindMinDistanceTrack(Track,startTrackNumber);//记录下一个访问的磁道号
Track[nextTrackNumber].setMoveDistance( Math.abs(Track[nextTrackNumber].getnextTrackNumber()-startTrackNumber));//记录移动距离
newTrack[i]=Track[nextTrackNumber];//保存访问的磁道记录
startTrackNumber=Track[nextTrackNumber].getnextTrackNumber();//重置下一个磁道开始的位置
}
Track=newTrack;
return Track;
}
public int Sort(LinkedList<Integer> List,Track[]Track,int startTrackNumber)
{
//找到磁道间距离最小的磁道号
int MinDistanceTrack=1000;//初始化磁道间最小距离
int NextTrack=0;
for(int i=0;i<List.size();i++)
{
if(Track[(int) List.get(i)].isDone()!=true)
{
if( Math.abs(Track[(int) List.get(i)].getnextTrackNumber()-startTrackNumber)<MinDistanceTrack)
{
MinDistanceTrack=Math.abs(Track[(int) List.get(i)].getnextTrackNumber()-startTrackNumber);//记录最小移动距离
NextTrack=(int) List.get(i);//记录下一个访问的磁道号
}
}
else continue;
}
Track[NextTrack].setDone(true);
return NextTrack;//返回下一个访问的磁道号
}
public Track[] SCAN(Track[]Track,int startTrackNumber)
{
//扫描算法
//以给定的磁道号为分界线，大的则加入LagerstartTrackNumberList链表，小的则加入SmalltartTrackNumberList链表
LinkedList<Integer> LagerstartTrackNumberList=new LinkedList<Integer>();
LinkedList<Integer> SmalltartTrackNumberList=new LinkedList<Integer>();
for(int i=0;i<Track.length;i++)
{
if(Track[i].getnextTrackNumber()>=startTrackNumber)
LagerstartTrackNumberList.add(i); //加入比开始磁道号大的磁道号
else
SmalltartTrackNumberList.add(i);//加入比开始磁道号小的磁道号
}
Track newTrack[]=new Track[Track.length];
for(int i=0;i<LagerstartTrackNumberList.size();i++)
{
//求比当前磁道大的移动距离
int nextTrackNumber=Sort(LagerstartTrackNumberList,Track,startTrackNumber);//找到距离最近磁道号下标
Track[nextTrackNumber].setMoveDistance(Math.abs(Track[nextTrackNumber].getnextTrackNumber()-startTrackNumber));//设置移动距离
startTrackNumber=Track[nextTrackNumber].getnextTrackNumber();//重置开始磁道号
newTrack[i]=Track[nextTrackNumber];
}
for(int i=LagerstartTrackNumberList.size();i<Track.length;i++)
{
//求比当前磁道小的移动距离
int nextTrackNumber=Sort(SmalltartTrackNumberList,Track,startTrackNumber);//找到距离最近磁道号下标
Track[nextTrackNumber].setMoveDistance(Math.abs(Track[nextTrackNumber].getnextTrackNumber()-startTrackNumber));//设置移动距离
startTrackNumber=Track[nextTrackNumber].getnextTrackNumber();//重置开始磁道号
newTrack[i]=Track[nextTrackNumber];
}
Track=newTrack;
return Track;
}
public int MaxDistanceTrack(LinkedList <Integer>SmalltartTrackNumberList, Track[]Track,int startTrackNumber)
{
int NextTrack=0;
int MaxDistance=0;
for(int i=0;i<SmalltartTrackNumberList.size();i++)
{
//找到距离当前磁道最远的磁道号
for(int j=i+1;j<SmalltartTrackNumberList.size();j++)
{
if(Track[(int) SmalltartTrackNumberList.get(i)].getnextTrackNumber()<Track[(int) SmalltartTrackNumberList.get(j)].getnextTrackNumber())
{
NextTrack=(int) SmalltartTrackNumberList.get(i);//记录下标
MaxDistance=Math.abs(Track[(int) SmalltartTrackNumberList.get(i)].getnextTrackNumber()-startTrackNumber);
}
}
}
return NextTrack;
}
public Track[] CSCAN(Track[]Track,int startTrackNumber)
{
//循环扫描算法
//以给定的磁道号为分界线，大的则加入LagerstartTrackNumberList链表，小的则加入SmalltartTrackNumberList链表
LinkedList<Integer> LagerstartTrackNumberList=new LinkedList<Integer>();
LinkedList<Integer> SmalltartTrackNumberList=new LinkedList<Integer>();
for(int i=0;i<Track.length;i++)
{
if(Track[i].getnextTrackNumber()>=startTrackNumber)
LagerstartTrackNumberList.add(i); //加入比开始磁道号大的磁道号
else
SmalltartTrackNumberList.add(i);//加入比开始磁道号小的磁道号
}
Track newTrack[]=new Track[Track.length];
for(int i=0;i<LagerstartTrackNumberList.size();i++)
{
//求比当前磁道大的移动距离
int nextTrackNumber=Sort(LagerstartTrackNumberList,Track,startTrackNumber);//找到距离最近磁道号下标
Track[nextTrackNumber].setMoveDistance(Math.abs(Track[nextTrackNumber].getnextTrackNumber()-startTrackNumber));//设置移动距离
startTrackNumber=Track[nextTrackNumber].getnextTrackNumber();//重置开始磁道号
newTrack[i]=Track[nextTrackNumber];
}
if(!(LagerstartTrackNumberList.size()==0||SmalltartTrackNumberList.size()==0))
{
//当磁道过大或过小的时候，很可能两个链表中有一个为空，这时候就不需要执行这一部分
//这一部分是用于找到最远磁道
int NextTrack=MaxDistanceTrack(SmalltartTrackNumberList,Track,startTrackNumber);//找到距离最远磁道号下标
Track[NextTrack].setMoveDistance(Math.abs(Track[NextTrack].getnextTrackNumber()-startTrackNumber));//设置移动距离
startTrackNumber=Track[NextTrack].getnextTrackNumber();//重置startTrackNumber
newTrack[LagerstartTrackNumberList.size()]=Track[NextTrack];
SmalltartTrackNumberList.remove(NextTrack);//将已设置过的磁道号移除链表
}
for(int i=LagerstartTrackNumberList.size()+1;i<Track.length;i++)
{
//求比当前磁道小的移动距离
int nextTrackNumber=Sort(SmalltartTrackNumberList,Track,startTrackNumber);//找到距离最近磁道号下标
Track[nextTrackNumber].setMoveDistance(Math.abs(Track[nextTrackNumber].getnextTrackNumber()-startTrackNumber));//设置移动距离
startTrackNumber=Track[nextTrackNumber].getnextTrackNumber();//重置开始磁道号
newTrack[i]=Track[nextTrackNumber];
}
Track=newTrack;
return Track;
}
public void Print(Track[]Track,int startTrackNumber)
{
double sum=0.0;
System.out.println("从"+startTrackNumber+"号磁道开始");
System.out.println("被访问的下一个磁道号"+" "+"移动距离(磁道数):");
for(int i=0;i<Track.length;i++)
{
sum=sum+(double)Track[i].getMoveDistance();
System.out.println(Track[i].getnextTrackNumber()+" \t"+Track[i].getMoveDistance());
}
DecimalFormat a = new DecimalFormat(".##");
System.out.println("平均寻道长度："+Double.parseDouble(a.format(sum/Track.length)));
}
}
public class experiment {
/*
FCFS算法 SSTF算法 SCAN算法 CSCAN算法
被访问的下一个磁道号 移动距离 被访问的下一个磁道号 移动距离 被访问的下一个磁道号 移动距离 被访问的下一个磁道号 移动距离
55 45 90 10 150 50 150 50
58 3 58 32 160 10 160 10
39 19 55 3 184 24 184 24
18 21 39 16 90 94 18 166
90 72 38 1 58 32 38 20
160 70 18 20 55 3 39 1
150 10 150 132 39 16 55 16
38 112 160 10 38 1 58 3
184 146 184 24 18 20 90 32
*/
public static void main(String[] args) {
// Track[]Track=new Track[9];
// Track[0]=new Track(55);
// Track[1]=new Track(58);
// Track[2]=new Track(39);
// Track[3]=new Track(18);
// Track[4]=new Track(90);
// Track[5]=new Track(160);
// Track[6]=new Track(150);
// Track[7]=new Track(38);
// Track[8]=new Track(184);
Scanner Input=new Scanner(System.in);
System.out.println("请输入磁道号：(用逗号隔开)");//55,58,39,18,90,160,150,38,184
String getTrack=Input.nextLine();
System.out.println("请输入开始的磁道号：");
int trackNumber=Input.nextInt();
String[] getTracktoCharAarray=getTrack.split(",");
Track[] Track=new Track[getTracktoCharAarray.length];
for (int i = 0; i < getTracktoCharAarray.length; i++) {
Track[i]=new Track(Integer.parseInt(getTracktoCharAarray[i]));
}
System.out.println("请输入选项来选择算法:0-退出,1-先来先服务算法,2-最短寻道时间算法,3-扫描算法，,4-循环扫描算法");
int option=Input.nextInt();
Input.close();
if(option==0)
return;
if(option==1)
{
System.out.println("FCFS算法如下：————————————————————");
new Track().Print(new Track().FCFS(Track, trackNumber),trackNumber);
}
if(option==2)
{
System.out.println("SSTF算法如下：————————————————————");
new Track().Print(new Track().SSTF(Track, trackNumber), trackNumber);
}
if(option==3)
{
System.out.println("SCAN算法如下：————————————————————");
new Track().Print(new Track().SCAN(Track, trackNumber),trackNumber);
}
if(option==4)
{
System.out.println("CSCAN算法如下：————————————————————");
new Track().Print(new Track().CSCAN(Track, trackNumber),trackNumber);
}
}
}
网友评论