磁盘调度算法

川长思鸟来 2022-02-03 02:49 390阅读 0赞

需求分析

分别实现先到先服务调度(FCFS)磁盘调度算法、最短寻道时间优先算法(SSTF)、“电梯”调度算法（SCAN算法）、C-SCAN算法、LOOK调度算法和C-LOOK调度算法

概要设计

1.先到先服务调度(FCFS)磁盘调度算法

按照磁道的访问顺序依次访问每个磁道。

2.最短寻道时间优先算法(SSTF)

从指定磁道，依次访问距离本磁道最近的磁道。

3.“电梯”调度算法（SCAN算法）

从指定磁道，向指定方向单向移动，依次访问距离本磁道最近的磁道，访问到最终磁道后，转向访问初始磁道另一侧的每个磁道，规则和以上相同。

4.C-SCAN算法

从指定磁道，向指定方向单向移动，依次访问距离本磁道最近的磁道，访问到磁盘最大（最小）容量后，转向访问初始磁道另一侧的每个磁道，到磁盘容量最小（最大），规则和以上相同。

5.LOOK调度算法

从指定磁道，向指定方向单向移动，依次访问距离本磁道最近的磁道，访问完最终磁道后，转向访问据本磁道最远的磁道，按如上规则依次访问至初始磁道。

6.C-LOOK调度算法

从指定磁道，向指定方向单向移动，依次访问距离本磁道最近的磁道，访问至磁盘最大（最小）容量后，转向访问磁盘的最小（最大）容量磁道，按如上规则依次访问至初始磁道。

代码实现

1.先到先服务调度(FCFS)

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. const int maxn=1010;
  6. void run(int track[],int index,int n)
  7. {
  8.     int sum=0;
  9.     for(int i=1;i<=n;i++)
  10.     {
  11.         sum+=abs(index-track[i]);
  12.         index=track[i];
  13.     }
  14.     cout<<"访问磁道顺序为"<<endl;
  15.     for(int i=1;i<=n;i++)
  16.         cout<<track[i]<<" ";
  17.     cout<<endl;
  18.     cout<<"寻道总距离为："<<sum<<endl;
  19.     cout<<"平均寻道距离为："<<sum*1.0/n<<endl;
  20. }
  21. void input(int track[],int n)
  22. {
  23.     cout<<"请依次输入需要访问的磁道号"<<endl;
  24.     for(int i=1;i<=n;i++)
  25.         cin>>track[i];
  27. }
  28. void FCFS_PRO()
  29. {
  30.     cout<<"请输入当前磁道号"<<endl;
  31.     int index;
  32.     cin>>index;
  33.     cout<<"请输入需要访问的磁道数目"<<endl;
  34.     int n;
  35.     cin>>n;
  36.     int track[maxn];
  37.     input(track,n);
  38.     run(track,index,n);
  39. }
  41. int main()
  42. {
  43.     FCFS_PRO();
  44.     return 0;
  45. }

2.最短寻道时间优先算法(SSTF)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1010;
  4. int track[maxn];
  5. priority_queue<int>l;
  6. priority_queue<int, vector<int>, greater<int>>r;
  7. void run(int index,int n)
  8. {
  9.    int sum=0;
  10.    int order[maxn];
  11.    int cur=1;
  12.    while(!l.empty()&&!r.empty())
  13.    {
  14.        if(abs(l.top()-index)<=abs(r.top()-index))
  15.        {
  16.            sum+=abs(l.top()-index);
  17.            index=l.top();
  18.            l.pop();
  19.            order[cur++]=index;
  20.        }
  21.        else
  22.        {
  23.            sum+=abs(r.top()-index);
  24.            index=l.top();
  25.            l.pop();
  26.            order[cur++]=index;
  27.        }
  28.    }
  29.    while(!l.empty())
  30.    {
  31.        sum+=abs(l.top()-index);
  32.            index=l.top();
  33.            l.pop();
  34.            order[cur++]=index;
  35.    }
  36.     while(!r.empty())
  37.    {
  38.        sum+=abs(r.top()-index);
  39.            index=r.top();
  40.            r.pop();
  41.            order[cur++]=index;
  42.    }
  43.    cout<<"访问磁道顺序为"<<endl;
  44.     for(int i=1;i<=n;i++)
  45.         cout<<order[i]<<" ";
  46.     cout<<endl;
  47.     cout<<"寻道总距离为："<<sum<<endl;
  48.     cout<<"平均寻道距离为："<<sum*1.0/n<<endl;
  49. }
  50. void input(int index,int n)
  51. {
  52.     cout<<"请依次输入需要访问的磁道号"<<endl;
  53.     for(int i=1;i<=n;i++)
  54.       {
  55.             cin>>track[i];
  56.             if(track[i]>=index)
  57.                 r.push(track[i]);
  58.             else
  59.                 l.push(track[i]);
  60.       }
  62. }
  63. void SSTF_PRO()
  64. {
  65.     cout<<"请输入当前磁道号"<<endl;
  66.     int index;
  67.     cin>>index;
  68.     cout<<"请输入需要访问的磁道数目"<<endl;
  69.     int n;
  70.     cin>>n;
  71.     input(index,n);
  72.     run(index,n);
  73. }
  75. int main()
  76. {
  77.     SSTF_PRO();
  78.     return 0;
  79. }

3.“电梯”调度算法（SCAN算法）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1010;
  4. int track[maxn];
  5. int maxindex=0;
  6. int minindex=0;
  7. priority_queue<int>l;
  8. priority_queue<int, vector<int>, greater<int>>r;
  9. void run(int index,int n,int capacity)
  10. {
  11.     int sum=0;
  12.     int order[maxn];
  13.     int cur=1;
  14.     while(!r.empty())
  15.     {
  16.         sum+=abs(r.top()-index);
  17.         index=r.top();
  18.         r.pop();
  19.         if(index!=capacity||(index==capacity&&maxindex==1))
  20.             {order[cur++]=index;
  21.             }
  22.     }
  24.     while(!l.empty())
  25.     {
  26.         sum+=abs(l.top()-index);
  27.         index=l.top();
  28.         l.pop();
  29.         if(index!=0||(index==0&&minindex==1))
  30.             order[cur++]=index;
  32.     }
  33.     cout<<"访问磁道顺序为"<<endl;
  34.     for(int i=1; i<=n; i++)
  35.         cout<<order[i]<<" ";
  36.     cout<<endl;
  37.     cout<<"寻道总距离为："<<sum<<endl;
  38.     cout<<"平均寻道距离为："<<sum*1.0/n<<endl;
  39. }
  40. void input(int index,int n,int capacity)
  41. {
  42.     cout<<"请依次输入需要访问的磁道号"<<endl;
  43.     for(int i=1; i<=n; i++)
  44.     {
  45.         cin>>track[i];
  46.         if(track[i]>=index)
  47.         {
  48.             if(track[i]==capacity)
  49.                 maxindex=1;
  50.             r.push(track[i]);
  51.         }
  52.         else
  53.         {
  54.             if(track[i]==0)
  55.                 minindex=1;
  56.             l.push(track[i]);
  57.         }
  58.     }
  59.     if(!maxindex)
  60.     r.push(capacity);
  61.     if(!minindex)
  62.     l.push(0);
  64. }
  65. void SCAN_PRO()
  66. {
  67.     cout<<"请输入当前磁道号"<<endl;
  68.     int index;
  69.     cin>>index;
  70.     cout<<"请输入磁盘容量"<<endl;
  71.     int capacity;
  72.     cin>>capacity;
  73.     cout<<"请输入需要访问的磁道数目"<<endl;
  74.     int n;
  75.     cin>>n;
  76.     input(index,n,capacity);
  77.     run(index,n,capacity);
  78. }
  80. int main()
  81. {
  82.     SCAN_PRO();
  83.     return 0;
  84. }

4.C-SCAN算法

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1010;
  4. int track[maxn];
  5. int maxindex=0;
  6. int minindex=0;
  7. priority_queue<int, vector<int>, greater<int>>l;
  8. priority_queue<int, vector<int>, greater<int>>r;
  9. void run(int index,int n,int capacity)
  10. {
  11.     int sum=0;
  12.     int order[maxn];
  13.     int cur=1;
  14.     while(!r.empty())
  15.     {
  16.         sum+=abs(r.top()-index);
  17.         index=r.top();
  18.         r.pop();
  19.         if(index!=capacity||(index==capacity&&maxindex==1))
  20.             {order[cur++]=index;
  21.             }
  22.     }
  24.     while(!l.empty())
  25.     {
  26.         sum+=abs(l.top()-index);
  27.         index=l.top();
  28.         l.pop();
  29.         if(index!=0||(index==0&&minindex==1))
  30.             order[cur++]=index;
  32.     }
  33.     cout<<"访问磁道顺序为"<<endl;
  34.     for(int i=1; i<=n; i++)
  35.         cout<<order[i]<<" ";
  36.     cout<<endl;
  37.     cout<<"寻道总距离为："<<sum<<endl;
  38.     cout<<"平均寻道距离为："<<sum*1.0/n<<endl;
  39. }
  40. void input(int index,int n,int capacity)
  41. {
  42.     cout<<"请依次输入需要访问的磁道号"<<endl;
  43.     for(int i=1; i<=n; i++)
  44.     {
  45.         cin>>track[i];
  46.         if(track[i]>=index)
  47.         {
  48.             if(track[i]==capacity)
  49.                 maxindex=1;
  50.             r.push(track[i]);
  51.         }
  52.         else
  53.         {
  54.             if(track[i]==0)
  55.                 minindex=1;
  56.             l.push(track[i]);
  57.         }
  58.     }
  59.     if(!maxindex)
  60.     r.push(capacity);
  61.     if(!minindex)
  62.     l.push(0);
  64. }
  65. void SCAN_PRO()
  66. {
  67.     cout<<"请输入当前磁道号"<<endl;
  68.     int index;
  69.     cin>>index;
  70.     cout<<"请输入磁盘容量"<<endl;
  71.     int capacity;
  72.     cin>>capacity;
  73.     cout<<"请输入需要访问的磁道数目"<<endl;
  74.     int n;
  75.     cin>>n;
  76.     input(index,n,capacity);
  77.     run(index,n,capacity);
  78. }
  80. int main()
  81. {
  82.     SCAN_PRO();
  83.     return 0;
  84. }

5.LOOK调度算法

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1010;
  4. int track[maxn];
  5. priority_queue<int>l;
  6. priority_queue<int, vector<int>, greater<int>>r;
  7. void run(int index,int n)
  8. {
  9.    int sum=0;
  10.    int order[maxn];
  11.    int cur=1;
  12.     while(!r.empty())
  13.    {
  14.        sum+=abs(r.top()-index);
  15.            index=r.top();
  16.            r.pop();
  17.            order[cur++]=index;
  18.    }
  20.    while(!l.empty())
  21.    {
  22.        sum+=abs(l.top()-index);
  23.            index=l.top();
  24.            l.pop();
  25.            order[cur++]=index;
  26.    }
  27.    cout<<"访问磁道顺序为"<<endl;
  28.     for(int i=1;i<=n;i++)
  29.         cout<<order[i]<<" ";
  30.     cout<<endl;
  31.     cout<<"寻道总距离为："<<sum<<endl;
  32.     cout<<"平均寻道距离为："<<sum*1.0/n<<endl;
  33. }
  34. void input(int index,int n)
  35. {
  36.     cout<<"请依次输入需要访问的磁道号"<<endl;
  37.     for(int i=1;i<=n;i++)
  38.       {
  39.             cin>>track[i];
  40.             if(track[i]>=index)
  41.                 r.push(track[i]);
  42.             else
  43.                 l.push(track[i]);
  44.       }
  46. }
  47. void LOOK_PRO()
  48. {
  49.     cout<<"请输入当前磁道号"<<endl;
  50.     int index;
  51.     cin>>index;
  52.     cout<<"请输入需要访问的磁道数目"<<endl;
  53.     int n;
  54.     cin>>n;
  55.     input(index,n);
  56.     run(index,n);
  57. }
  59. int main()
  60. {
  61.     LOOK_PRO();
  62.     return 0;
  63. }

6.C-LOOK调度算法

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1010;
  4. int track[maxn];
  5. priority_queue<int, vector<int>, greater<int>>l;
  6. priority_queue<int, vector<int>, greater<int>>r;
  7. void run(int index,int n)
  8. {
  9.    int sum=0;
  10.    int order[maxn];
  11.    int cur=1;
  12.     while(!r.empty())
  13.    {
  14.        sum+=abs(r.top()-index);
  15.            index=r.top();
  16.            r.pop();
  17.            order[cur++]=index;
  18.    }
  20.    while(!l.empty())
  21.    {
  22.        sum+=abs(l.top()-index);
  23.            index=l.top();
  24.            l.pop();
  25.            order[cur++]=index;
  26.    }
  27.    cout<<"访问磁道顺序为"<<endl;
  28.     for(int i=1;i<=n;i++)
  29.         cout<<order[i]<<" ";
  30.     cout<<endl;
  31.     cout<<"寻道总距离为："<<sum<<endl;
  32.     cout<<"平均寻道距离为："<<sum*1.0/n<<endl;
  33. }
  34. void input(int index,int n)
  35. {
  36.     cout<<"请依次输入需要访问的磁道号"<<endl;
  37.     for(int i=1;i<=n;i++)
  38.       {
  39.             cin>>track[i];
  40.             if(track[i]>=index)
  41.                 r.push(track[i]);
  42.             else
  43.                 l.push(track[i]);
  44.       }
  46. }
  47. void CLOOK_PRO()
  48. {
  49.     cout<<"请输入当前磁道号"<<endl;
  50.     int index;
  51.     cin>>index;
  52.     cout<<"请输入需要访问的磁道数目"<<endl;
  53.     int n;
  54.     cin>>n;
  55.     input(index,n);
  56.     run(index,n);
  57. }
  59. int main()
  60. {
  61.     CLOOK_PRO();
  62.     return 0;
  63. }
  64. 55 58 39 18 90 160 150 38 184

运行实例

1.先到先服务调度(FCFS)磁盘调度算法

20190508171252704.png

2.最短寻道时间优先算法(SSTF)

20190508171255543.png

3.“电梯”调度算法（SCAN算法）

20190508171304596.png

4.SCAN算法

201905081713093.png

5.LOOK调度算法

2019050817131715.png

6.CLOOK调度算法

20190508171319187.png

发表评论

表情：
评论列表 （有 0 条评论，390人围观）

还没有评论，来说两句吧...

相关阅读

    相关 磁盘调度算法

    磁盘调度算法是计算机操作系统中用于管理磁盘上的数据访问的重要组成部分。这些算法有助于优化数据的读写操作，以减少磁盘访问时间，提高系统性能。以下是一些常见的磁盘调度算法： 先来

    Bertha 。Bertha 。/ 0 赞/ 117 阅读

    相关 磁盘调度算法

    磁盘调度算法 为了减少对文件的访问时间，应采用一种最佳的磁盘调度算法，以使各进程对磁盘的平均访问时间最少。由于在访问磁盘时主要是寻道时间。因此，磁盘调度的目标是使磁盘的平

    深藏阁楼爱情的钟深藏阁楼爱情的钟/ 0 赞/ 170 阅读

    相关 磁盘调度算法

    磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备

    女爷i女爷i/ 0 赞/ 236 阅读

    相关 磁盘调度算法

    需求分析 分别实现先到先服务调度(FCFS)磁盘调度算法、最短寻道时间优先算法(SSTF)、“电梯”调度算法（SCAN算法）、C-SCAN算法、LOOK调度算法和C-LO

    川长思鸟来川长思鸟来/ 0 赞/ 391 阅读

    相关 磁盘寻道调度算法

    磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读 / 写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘

    红太狼红太狼/ 0 赞/ 365 阅读