设为首页 收藏本站

运维网

 找回密码
 立即注册
查看: 671|回复: 0

[经验分享] 磁盘调度算法FCFS、SSTF、SCAN、CSCAN详解

[复制链接]
trrtrtrt

尚未签到
发表于 2018-4-10 09:38:50 | 显示全部楼层 |阅读模式
常见的磁盘调度算法有：1.FCFS：先来先服务算法；
2.SSTF：最短寻道时间算法；
3.SCAN：扫描算法（也叫电梯调度算法）；
4.CSCAN：循环扫描算法

   算法的详细介绍：
  • FCFS：算法思想非常简单，就是不论初始磁头在什么位置，都是按照服务队列的先后顺序依次处理进程，可以类比队列的先进先出。优点是进程处理起来非常简单，但缺点显而易见，就是平均寻道长度会很长。
Java实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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<num;i++)
            position=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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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<num;i++){
            position[0] = sc.nextInt();
            position[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<num;i++){
            position1[0] = position[0];
            position1[1] = i+1;
        }
        //寻找磁头访问的序列        
        for(int i=0;i<num;i++){
            for(int j=0;j<num;j++){
                if(position1[j][0]!=-1){
                    if(Math.abs(initPos1 - nearest)>Math.abs(position1[j][0]-initPos1)){
                        nearest = position1[j][0];
                        index = j;
                    }   
                }
            }
            sequenceOfProcess = nearest;
            sequenceOfNumber = index+1;
            position1[index][0] = -1;//-1表示此位置的进程已经放在了访问序列,不在进行查询
            initPos1 = nearest;
            nearest = 10000;        
        }
         
        for(int i=0;i<num;i++){
            System.out.println("进程"+sequenceOfNumber+"在磁道"+sequenceOfProcess+"完成");
        }
    }



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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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<num;i++){
            position1 = sc.nextInt(); //记录进程所在的磁道号
        }
    }
    public void adjust(){
        //按照磁道编号将进程排序,就是一个冒泡排序
        for(int i=0;i<num;i++){
            for(int j=1;j<num-i;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<num-1;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[1]+"At Position"+position[0]+"Completed");
             }
         }
         //磁头开始从初始位置向外扫描
         if(position1[init+1]!=0){
             System.out.println("This Is the Track 0");
             }
             for(int i=start+1;i<num;i++){
                System.out.println("The Second Time Scan:"+"Process"+position[1]+"At Position"+position[0]+"Completed");
             }
         }
     }  
}



  • CSCAN：在磁盘扫描算法的基础上改变磁头的扫描路径：扫描到最内层之后从最外层向内继续扫描，即扫描方向一致。该算法的思路与扫描算法基本一致，也使用二维数组进行进程编号和进程所在磁道号的存储，算法的不同之处在于当磁头扫描到磁盘的最内层时，磁头跳转到磁盘最外层重新向内扫描，这样就可以有效的避免将已经扫描过的磁道重新扫描一次，降低了平均寻到距离。
Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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<num;i++ ){
            position[0] = sc.nextInt();
            position[1] = i+1;
        }
    }
    public void adjust(){//调整数组中进程的记录顺序
        for(int i=0;i<num;i++){
            for(int j=1;j<num-i;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<num-1;init++){
             if(position[init][0]=initPos){
                 break;
             }
         }
         int start = init;
         System.out.println("第一次扫描：");
         for(int i=start;i>=0;i--){      
             System.out.println("第一次扫描："+"进程"+position[1]+"在磁道"+position[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[1]+"在磁道"+position[0]+"完成");
         }
     }   
}



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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=




</num-1;init++){
</num-i;j++){
</num;i++){
</num;i++){
</num-1;init++){
</num-i;j++){
</num;i++){
</num;i++){
</num;i++){
</num;j++){
</num;i++){
</num;i++){
</num;i++){
</num;i++)

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表，该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有，请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意，请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息，一经发现立即删除。若您因此触犯法律，一切后果自负，我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集，我们仅提供一个展示、介绍、观摩学习的平台，我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责，亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏，不得用于商业或者其他用途，否则，一切后果均由您自己承担，我们对此不承担任何法律责任
7、如涉及侵犯版权等问题，请您及时通知我们，我们将立即采取措施予以解决
8、联系人Email：admin@iyunv.com 网址：www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址：https://www.yunweiku.com/thread-448502-1-1.html 上篇帖子： inux系统中管理用户账户和组账户及其权限设置 下篇帖子： Expect实现ssh非交互登录
回复

使用道具 举报

返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群，最新一手资源尽在官方微信交流群！快快加入我们吧...

扫描微信二维码查看详情

客服 E-mail:iyunvcom@gmail.com

本站由青云提供云计算服务

运维网--中国最专业的运维工程师交流社区

豫ICP备20007574号-1 Copyright © 2012-2025

关于我们

发展历程

联系我们

关注我们

广告服务

广告案例

隐私条款

免责声明

用户登录

用户注册

版主守则

申请版主

手机版

金币获取

帮助中心

每日签到

Good Good

Study

Day Day

UP


客服E-mail:kefu@iyunv.com 客服QQ：1061981298


QQ群⑦：运维网交流群⑦ QQ群⑧：运维网交流群⑧ k8s群：运维网kubernetes交流群


提醒：禁止发布任何违反国家法律、法规的言论与图片等内容；本站内容均来自个人观点与网络等信息，非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来，其版权均归原作者及其网站所有，我们尊重他人的合法权益，如有内容侵犯您的合法权益，请及时与我们联系进行核实删除！



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表