精华内容
下载资源
问答
  • 实验六磁盘调度算法1、实验目的通过这次实验,加深对磁盘调度算法的理解,进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。2、试验内容问题描述:设计程序模拟先来先服务FCFS、最短...

    实验六磁盘调度算法

    1、实验目的

    通过这次实验,加深对磁盘调度算法的理解,进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。

    2、试验内容

    问题描述:

    设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列,给定开始磁道号m和磁头移动的方向(正向或者反向),分别利用不同的磁盘调度算法访问磁道序列,给出每一次访问的磁头移动距离,计算每种算法的平均寻道长度。

    3、程序要求:

    1)利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法模拟磁道访问过程。

    2)模拟四种算法的磁道访问过程,给出每个磁道访问的磁头移动距离。

    3)输入:磁道个数n和磁道访问序列,开始磁道号m和磁头移动方向(对SCAN和循环SCAN算法有效),算法选择1-FCFS,2-SSTF,3-SCAN,4-循环SCAN。

    4)输出:每种算法的平均寻道长度。

    4、需求分析

    展开全文
  • 常见的磁盘调度算法有:1.FCFS:先来先服务算法;2.SSTF:最短寻道时间算法;3.SCAN:扫描算法(也叫电梯调度算法);4.CSCAN:循环扫描算法算法的详细介绍:FCFS:算法思想非常简单,就是不论初始磁头在什么位置,都...

    常见的磁盘调度算法有:

    1.FCFS:先来先服务算法;

    2.SSTF:最短寻道时间算法;

    3.SCAN:扫描算法(也叫电梯调度算法);

    4.CSCAN:循环扫描算法

    算法的详细介绍:FCFS:算法思想非常简单,就是不论初始磁头在什么位置,都是按照服务队列的先后顺序依次处理进程,可以类比队列的先进先出。优点是进程处理起来非常简单,但缺点显而易见,就是平均寻道长度会很长。

    Java实现:public class fcfs {

    Scanner x=new Scanner(System.in);

    public int[] position;

    public int num;

    public fcfs()

    {

    System.out.println("Enter the number of process:");

    num=x.nextInt();

    position=new int[num];

    }

    public void input()

    {

    int i=0;

    for(i=0;i

    position[i]=x.nextInt();

    }

    public void algo()

    {

    int i=1;

    for(i=1;i<=num;i++)

    System.out.println("Process Accessed "+i+" at "+position[i-1]);

    }

    }SSTF:最短寻道时间算法,算法本质是贪心,已知磁头的初始位置,则最先被处理就是距离磁头位置最近的进程,处理完成后再处理距离当前磁道最近的进程,直到所有的进程被处理。该算法的优点是平均寻道长度会大大减少,缺点是距离初始磁头较远的服务长期得不到处理,产生“饥饿”现象。具体的思路是:通过循环寻找与初始磁头最近的进程,将进程处理,然后将该进程标记为-1,将初始磁头移动到该进程所在的磁道。然后依次类推,标记为-1的进程不再参与,知道所有的进程都被标记为-1,磁盘调度完成。

    Java实现public class sstfAlg{

    int num;

    int[][] position;

    int size;

    int initPos;

    int[] sequenceOfProcess ;//存储访问序列

    int[] sequenceOfNumber;

    Scanner sc = new Scanner(System.in);

    public sstfAlg(int a,int b,int c){

    //a means the amount of process

    //b means the inital of position

    //c means the size of disk

    num = a;

    position = new int[a][2];

    sequenceOfProcess = new int[a];

    sequenceOfNumber = new int[a];

    initPos = b;

    size = c;

    }

    public void input(){

    System.out.println("input the number of process:");

    for(int i=0;i

    position[i][0] = sc.nextInt();

    position[i][1] = i+1;

    }

    }

    public void myAlg(){

    int nearest = 10000;

    int index = 0 ;

    int initPos1 = initPos;

    //复制一个数组用来寻找访问序列

    int[][] position1 = new int[num][2];

    for(int i=0 ;i

    position1[i][0] = position[i][0];

    position1[i][1] = i+1;

    }

    //寻找磁头访问的序列

    for(int i=0;i

    for(int j=0;j

    if(position1[j][0]!=-1){

    if(Math.abs(initPos1 - nearest)>Math.abs(position1[j][0]-initPos1)){

    nearest = position1[j][0];

    index = j;

    }

    }

    }

    sequenceOfProcess[i] = nearest;

    sequenceOfNumber[i] = index+1;

    position1[index][0] = -1;//-1表示此位置的进程已经放在了访问序列,不在进行查询

    initPos1 = nearest;

    nearest = 10000;

    }

    for(int i=0;i

    System.out.println("进程"+sequenceOfNumber[i]+"在磁道"+sequenceOfProcess[i]+"完成");

    }

    }SCAN:磁头仅沿一个方向进行扫描,在扫描途中完成所有没有完成的请求,直到磁头到达磁盘在这个方向上的最后一个磁道或者这个方向上最后一个请求所在的磁道。利用数组存储进程和磁道编号,依据给定的初始磁头,先找到初始磁头在哪两个进程之间,然后向内扫描。当磁头扫描到磁盘最内层即磁道0且进程还没有全部被处理,磁头开始向外扫描,直到所有的进程都完成。

    Java实现class scanAlgo{

    Scanner sc = new Scanner(System.in);

    int num;   //进程数量

    int[] position1;

    int initPos;  //磁头初始位置

    public scanAlgo(){

    System.out.println("input the amount of process:");

    num = sc.nextInt();

    position1 = new int[num+1];

    System.out.println("input the initial position:");

    initPos = sc.nextInt();

    }

    public void input(){

    System.out.println("input the number of process:");

    for(int i=0;i

    position1[i] = sc.nextInt(); //记录进程所在的磁道号

    }

    }

    public void adjust(){

    //按照磁道编号将进程排序,就是一个冒泡排序

    for(int i=0;i

    for(int j=1;j

    if(position1[j-1] > position1[j]){

    int temp = position1[j];

    position1[j] = position1[j-1];

    position1[j-1] = temp;

    }

    }

    }

    }

    public void algo(){

    //寻找磁头初始位置在哪两个进程之间

    input();

    adjust();

    int init;

    for(init=0;init

    if(position1[init] <= initPos && position1[init+1] > initPos)

    break;

    //此时得到的init值就是磁头初始位置

    }

    int start  = init;

    //磁头先向里扫描

    for(int i=start;i>=0;i--){

    System.out.println("The First Time Scan:"+"Process"+position[i][1]+"At Position"+position[i][0]+"Completed");

    }

    }

    //磁头开始从初始位置向外扫描

    if(position1[init+1]!=0){

    System.out.println("This Is the Track 0");

    }

    for(int i=start+1;i

    System.out.println("The Second Time Scan:"+"Process"+position[i][1]+"At Position"+position[i][0]+"Completed");

    }

    }

    }

    }CSCAN:在磁盘扫描算法的基础上改变磁头的扫描路径:扫描到最内层之后从最外层向内继续扫描,即扫描方向一致。该算法的思路与扫描算法基本一致,也使用二维数组进行进程编号和进程所在磁道号的存储,算法的不同之处在于当磁头扫描到磁盘的最内层时,磁头跳转到磁盘最外层重新向内扫描,这样就可以有效的避免将已经扫描过的磁道重新扫描一次,降低了平均寻到距离。

    Java实现class cscanAlg{

    Scanner sc = new Scanner(System.in);

    int num;

    int[][] position ;

    int initPos;

    int size;

    public cscanAlg (){

    System.out.println("input the amount of process:");

    num = sc.nextInt();

    position = new int[num+1][2];

    System.out.println("input the initial position :");

    initPos = sc.nextInt();

    System.out.println("input the size of Disk:");

    size = sc.nextInt();

    }

    public void input(){

    System.out.println("input the number of process:");

    for(int i = 0;i

    position[i][0] = sc.nextInt();

    position[i][1] = i+1;

    }

    }

    public void adjust(){//调整数组中进程的记录顺序

    for(int i=0;i

    for(int j=1;j

    if(position[j-1][0]>position[j][0]){

    int temp1 = position[j][0];

    int temp2 = position[j][1];

    position[j][0] = position[j-1][0];

    position[j][1] = position[j-1][1];

    position[j-1][0] = temp1;

    position[j-1][1] = temp2;

    }

    }

    }

    }

    public void algo(){

    input();

    adjust();

    int init;

    for(init = 0;init

    if(position[init][0]=initPos){

    break;

    }

    }

    int start = init;

    System.out.println("第一次扫描:");

    for(int i=start;i>=0;i--){

    System.out.println("第一次扫描:"+"进程"+position[i][1]+"在磁道"+position[i][0]+"完成");

    }

    if(position[init+1][0]!=0){

    System.out.println("磁头已经扫描到磁盘最内层:0");

    }

    if(position[num-1][0]!=size){

    System.out.println("磁头已经移到磁盘最外层:"+size);

    }

    System.out.println("第二次扫描:");

    for(int i=num-1;i>start;i--){

    System.out.println("第二次扫描:"+"进程"+position[i][1]+"在磁道"+position[i][0]+"完成");

    }

    }

    }

    为了直观的感受一下各种算法的差别,我选了大概500个进程处理来比较它们的时间和平均寻道长度(现实中肯定不会有这么多的待处理进程,不然炸了,只是为了比较),通过画折线图的方法进程比较,画折线图的实现过程在前面的文章中已经记录过了,所以直接上结果:

    c76c54e89157671f6bfab4a5c8670ea9.png

    a3b783666bfae9463f241f4647b836e4.png

    展开全文
  • Java实现磁盘调度算法

    千次阅读 2017-01-22 18:14:18
    Java实现磁盘调度算法磁盘调度算法有很多种,包括先来先服务(FCFS)、最短寻道优先算法(SSTF)、扫描算法(SCAN)、循环扫描算法等(CSCAN)等等,各种算法的详细介绍在操作系统等书中有详细介绍。这里选取前三种调度算法...

    Java实现磁盘调度算法

    • 磁盘调度算法有很多种,包括先来先服务(FCFS)、最短寻道优先算法(SSTF)、扫描算法(SCAN)、循环扫描算法等(CSCAN)等等,各种算法的详细介绍在操作系统等书中有详细介绍。这里选取前三种调度算法进行实现,语言采用Java。
      三种算法的简介为:

      1、FCFS:按磁盘访问请求的到来顺序进行响应。如若有六个磁盘访问请求依次到来,六个请求所请求访问的磁道号为33,78,55,120,63,70;则根据FCFS,将按请求到来顺序进行调度响应,所以磁盘访问顺序为:33,78,55,120,63,70。

      2、SSTF:此算法优先选取欲访问的磁道距离当前磁头所在位置最近的请求进行调度。假设一组磁盘访问请求如上,并假设磁头初始时在磁道号为60的位置,则磁盘访问顺序为:63,70,78,55,33,120.

      3、SCAN:此算法在SSTF的基础上规定了磁头的运动方向,按磁头初始运动方向,选取此方向上欲访问磁道距离磁头所在位置最近的请求进行调度。切磁头只能继续向该方向行进,直至该方向所有请求均调度完毕。若一组磁道访问请求如上,磁头初始位置仍为60,并假设此时磁头运动方向为磁道号增大方向,则磁盘访问顺序变为:63,70,78,120,55,33.

      在进行编程实现时,磁盘访问请求所要访问的磁道号随机产生,产生的磁盘访问请求数量、磁道号的允许范围、磁头初始运动方向均有用户设定(在SACN算法运行时设定)。

      工程截图如下(IDE用的eclipse,jdk版本为1.8):
      这里写图片描述
      下面贴出代码:

    一、磁盘访问请求的封装。一个磁盘访问请求包括请求号,欲请求的磁道号,是否已被调度的标记。实际上一个请求可以看作是一个进程。

    package com.bean;
    
    public class Request {
    	private int id; //请求号,唯一标识一个请求
    	private int number; //欲访问的磁道号
    	private int flag; //是否已被调度的标记,初始为0,表示为被调度。
    	public Request(){ //空白构造器
    		this.id=0;
    		this.number=0;
    		this.flag=0;
    	}
    	public Request(int id,int num){ //带参构造器
    		this.id=id;
    		this.number=num;
    		this.flag=0;
    	}
    	public void setId(int id){
    		this.id=id;
    	}
    	
    	// 以下是一系列set和get方法
    	public int getId(){
    		return this.id;
    	}
    	
    	public void setNumber(int number){
    		this.number=number;
    	}
    	public int getNumber(){
    		return this.number;
    	}
    	
    	public void setFlag(int flag){
    		this.flag=flag;
    	}
    	public int getFlag(){
    		return this.flag;
    	}
    }
    
    

    二、作业类的封装。即模拟一个作业,其中有一个getRandomRequest()方法,在设定的磁道允许范围内,产生一个磁盘访问序列,也即一个request数组。欲产生的磁盘访问请求数量由用户运行时设定,每个访问请求的磁道号在设定的磁道允许范围内随机产生。

    package com.bean;
    
    import java.util.HashSet;
    import java.util.Random;
    import java.util.Set;
    
    public class Work {
    	private int start; //允许访问的磁道号范围的起始磁道号
    	private int end; //允许访问的磁道号范围的终止磁道号
    	// 即请求可请求访问的磁道号在start与end之间
    	private int num; //所要产生的磁盘访问请求数量
    	public Work(){ //不带参构造器
    		this.start=0;
    		this.end=0;
    		this.num=0;
    	}
    	public Work(int start,int end,int num){ //带参构造器
    		this.start=start;
    		this.end=end;
    		this.num=num;
    	}
    	public int getStart(){
    		return this.start;
    	}
    	public int getEnd(){
    		return this.end;
    	}
    	
    	public Request[] getRandomRequest(){ //产生磁盘访问请求的方法
    		Request req[]=new Request[num]; //数组声明num个请求
    		Random random=new Random();
    		Set<Integer> set=new HashSet<Integer>();
    		while(true){ //为num个请求依次生成要访问的磁道号,放入set集合
    			set.add((int)(random.nextInt(end-start)+start));
    			if(set.size()==num)
    				break;
    		}
    		int i=0;
    		//将set集合中的数取出依次付给各请求。使用set的目的是让num个访问请求要访问的磁道号各不同。
    		for(int temp:set){
    			req[i]=new Request(i+1,temp);
    			i++;
    		}
    		return req;
    	}
    }
    

    三、调度算法的实现。三个方法对应三个调度算法。

    package com.diaodu;
    
    import java.text.DecimalFormat;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.TreeSet;
    
    import com.bean.Request;
    import com.bean.Work;
    
    public class DiaoDu {
    	Work work;
    	Request[] request;
    	int begin;//磁头初始位置
    	DecimalFormat df = new DecimalFormat("0.000");
    	public DiaoDu(Work work){//构造器,接收一个作业
    		this.work=work;
    		request=work.getRandomRequest();
    		//磁头初始位置设为所允许访问磁道号范围的中间值。
    		//如若磁道访问允许范围为100~300,则磁头初始位置在200处。
    		begin=(work.getStart()+work.getEnd())/2;
    	}
    	
    	public void FCFS(){//先来先服务算法
    		begin=(work.getStart()+work.getEnd())/2;
    		Request[] req=request;
    		System.out.println("磁道号区间:"+work.getStart()+"到"+work.getEnd());
    		System.out.println("磁头初始时所在磁道号:"+begin);
    		
    		double sum=0;
    		System.out.println("请求号        被访问的下一个磁道号               移动距离");
    		for(Request r:req){						
    			System.out.println("--"+r.getId()+"----------------"+r.getNumber()+"-----------------"+Math.abs(begin-r.getNumber())+"--");
    			sum+=Math.abs(begin-r.getNumber());
    			begin=r.getNumber();
    		}
    		System.out.println("***********平均寻道长度为:"+df.format(sum/req.length)+"************");
    	}
    	
    	
    	public void SSTF(){//最短寻道优先
    		begin=(work.getStart()+work.getEnd())/2;
    		Request[] req=request;
    		System.out.println("磁道号区间:"+work.getStart()+"到"+work.getEnd());
    		System.out.println("磁头初始时所在磁道号:"+begin);
    		
    		int t=0;
    		double sum=0;
    		System.out.println("请求号        被访问的下一个磁道号               移动距离");
    		for(int i=0;i<req.length;i++){
    			int temp=work.getEnd();
    			for(int j=0;j<req.length;j++){
    				if(Math.abs(req[j].getNumber()-begin)<temp&&req[j].getFlag()==0){
    					temp=Math.abs(req[j].getNumber()-begin);					
    					t=j;
    				}
    			}			
    			System.out.println("--"+req[t].getId()+"----------------"+req[t].getNumber()+"-----------------"+temp+"--");
    			begin=req[t].getNumber();
    			req[t].setFlag(1);
    			sum+=temp;
    		}
    		System.out.println("***********平均寻道长度为:"+df.format(sum/req.length)+"***********");
    	}
    	
    	
    	
    	public void SCAN(){//扫描算法
    		begin=(work.getStart()+work.getEnd())/2;
    		Request[] req=request;
    		int direction;//磁头运动方向方向
    		System.out.println("设定磁头初始化运动方向(1:磁道号增大方向    -1:磁道号减小方向):");
    		direction=new Scanner(System.in).nextInt();
    		System.out.println("磁道号区间:"+work.getStart()+"到"+work.getEnd());
    		System.out.println("磁头初始时所在磁道号:"+begin);
    		if(direction==1)
    			System.out.println("磁头初始运动方向: 磁道号增大方向");
    		else
    			System.out.println("磁头初始运动方向: 磁道号减小方向");
    		
    		Map<Integer,Request> map=new HashMap<Integer,Request>();
    		TreeSet<Integer> ts1=new TreeSet<Integer>();
    		TreeSet<Integer> ts2=new TreeSet<Integer>();
    		for(Request r:req){
    			if(r.getNumber()>=begin){
    				map.put(r.getNumber(), r);
    				ts1.add(r.getNumber());
    			}
    			else{
    				map.put(r.getNumber(), r);
    				ts2.add(r.getNumber());
    			}
    		}		
    		
    		
    		System.out.println("请求号        被访问的下一个磁道号               移动距离");
    		double sum=0;
    		if(direction==1){
    
    			for(int temp:ts1){
    				System.out.println("--"+map.get(temp).getId()+"----------------"+temp+"-----------------"+Math.abs(temp-begin));
    				sum+=Math.abs(temp-begin);
    				begin=temp;
    			}
    			for(int temp:ts2.descendingSet()){
    				System.out.println("--"+map.get(temp).getId()+"----------------"+temp+"-----------------"+Math.abs(temp-begin));
    				sum+=Math.abs(temp-begin);
    				begin=temp;
    			}
    			
    		}
    		
    		else{
    			for(int temp:ts2.descendingSet()){
    				System.out.println("--"+map.get(temp).getId()+"----------------"+temp+"-----------------"+Math.abs(temp-begin));
    				sum+=Math.abs(temp-begin);
    				begin=temp;
    			}
    			for(int temp:ts1){
    				System.out.println("--"+map.get(temp).getId()+"----------------"+temp+"-----------------"+Math.abs(temp-begin));
    				sum+=Math.abs(temp-begin);
    				begin=temp;
    			}
    		}
    		System.out.println("***********平均寻道长度为:"+df.format(sum/req.length)+"***********");
    	}
    }
    
    

    四、场景类测试。在main方法中定义相关对象,进行测试。

    package com.client;
    import java.util.Scanner;
    
    import com.bean.Work;
    import com.diaodu.DiaoDu;
    
    public class Client {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int start,end,num;
    		Scanner in=new Scanner(System.in);
    		System.out.println("设定磁道起止道号:");
    		System.out.print("起始道号:");
    		start=in.nextInt();
    		System.out.print("终止道号:");
    		end=in.nextInt();
    		System.out.print("输入磁盘访问的请求数:");
    		num=in.nextInt();
    		
    		Work work=new Work(start,end,num);
    		DiaoDu diaodu=new DiaoDu(work);
    		
    		System.out.println();
    		System.out.println("*************先来先服务调度法*************");
    		diaodu.FCFS();
    		
    		System.out.println();
    		System.out.println("***********最短寻道时间优先调度法************");
    		diaodu.SSTF();
    		
    		System.out.println();
    		System.out.println("****************扫描调度法*****************");
    		diaodu.SCAN();
    	}
    
    }
    
    

    五、运行实例截图如下:
    这里写图片描述
    这里写图片描述

    展开全文
  • 在操作系统课上的一点小感想,基于JAVA磁盘调度算法,分享出来和大家一起学习。 先来先服务(FCFS)算法。即先来的请求先被响应。FCFS策略为我们建立起一个随机访问机制的模型,但是假如用这个策略反复响应从里...

    在操作系统课上的一点小感想,基于JAVA的磁盘调度算法,分享出来和大家一起学习。

    先来先服务(FCFS)算法。即先来的请求先被响应。FCFS策略为我们建立起一个随机访问机制的模型,但是假如用这个策略反复响应从里到外的请求,那么将会消耗大量的时间。FCFS也被看作是最简单的磁盘调度算法。

    最短寻道时间优先(SSTF)算法。要求访问的磁道,与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。

    扫描调度(SCAN)算法。该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道,既在当前磁道之外,又是距离最近的。这样自里向外的访问,直至再无更外的磁道需要访问时,才将磁道换向自外向里移动。这时,同样也是每次选择这样的进程来调度,也就是要访问的当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现像。

    循环扫描(C-SCAN)算法。当磁头刚从里向外移动而越过了某一磁道时,恰好又有一进程请求访问此磁道,这时,该里程就必须等待,为了减少这种延迟,CSCAN算法规定磁头单向移动,而本实验过程中我们所设计的是磁头从里向外移动,而从外向里移动时只须改方向而已,本实验未实现。但本实验已完全能演示循环扫描的全过程。

    参考博文和源码下载地址:

    https://write-bug.com/article/1362.html

    转载于:https://my.oschina.net/u/4188102/blog/3091776

    展开全文
  • #include#include using namespace std;/*先来先服务调度int i=0,sum=0,x;x=abs(b[i]-num);cout<cout<cout<for(i=1;i{cout<sum+=abs(b[i]-b[i-1]);...}/*电梯调度算法*/void scan(int b[],int n,int nu...
  • 磁盘调度
  • 操作系统,用java实现磁盘调度算法,有swing界面,包括算法fcfs, sstf, scan,cscan。
  • 磁盘调度算法java实现

    热门讨论 2013-05-30 20:54:38
    随机生成磁盘序列 用java实现了FIFO、SSTF、SCAN和C-SCAN算法模拟磁盘调度 有用户界面,有序列结果记录,有计算移动磁道数
  • 实验六 磁盘调度算法 1 实验目的 通过这次实验加深对磁盘调度算法的理解进一步掌握先来先 服务 FCFS最 短寻道时间优先 SSTFSCAN和循环 SCAN算法 的实现方法 2 试验内容 问题描述 设计程序模拟先来先服务 FCFS最短...
  • 页面置换算法 下载地址: 进程调度算法 下载地址: 磁盘调度算法 下载地址

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 133
精华内容 53
关键字:

java磁盘调度算法

java 订阅