磁盘调度-循环扫描（CSCAN）_cscan算法

SCAN算法既能获得较好的寻道性能，又能防止饥饿现象。但是存在这样的问题：当磁头刚从里向外移动而超越了某一磁道时，恰好又有一进程请求访问此磁道，这时该进程必须等待。将磁头继续从里向外，然后再从外向里扫描完处于外面的所有要访问的磁道后，才处理该进程的请求，致使该请求的请求被大大的推迟。

为此，CSCAN算法规定磁头单向移动，如果只是从里向外移动，当磁头移到最外的磁道并访问时，磁头立即返回到最里的欲访问磁道，即将最小磁道号紧接着最大磁道号循环，进行循环扫描。

输入:起始磁道以及要访问的磁道数目，要访问的磁道号，isadd。

输出:被访问的下一个磁道号和移动距离, 最后是平均寻道长度。

运行结果：

数据结构：

//num为进程请求访问的磁道号
int num[maxn];

辅助函数：

//将当前磁头所在的位置s移动到磁道num[i]上
//更新sum，s的值。
void Move(int *num, int i, int &s, double &sum)
{
    printf("%d %d\n", num[i], abs(s-num[i]));
    sum += abs(s-num[i]);
    s = num[i];
}
 

源代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100 + 5;  //要求访问的进程最大数目。
 
//磁盘调度算法
 
 
//将当前磁头所在的位置s移动到磁道num[i]上
//更新sum，s的值。
void Move(int *num, int i, int &s, double &sum)
{
    printf("%d %d\n", num[i], abs(s-num[i]));
    sum += abs(s-num[i]);
    s = num[i];
}
 
/*
循环扫描。
磁头单向移动，例如从里向外移动，当磁头移到最外的磁道并访问时，磁头立即返回
到最里的欲访问磁道，将最小磁道号紧接着最大磁道号循环，进行循环扫描
*/
void CSCAN(int *num, int n, int s, double &sum, int isadd)
{
    int i, j;
 
    sort(num, num+n);
    j = lower_bound(num, num+n, s) - num;
 
    if(isadd)
    {
        for(i = j; i < n; i++)
            Move(num, i, s, sum);
        for(i = 0; i < j; i++)
            Move(num, i, s, sum);
    }
    else
    {
        if(num[j] == s)
            j++;
        for(i = j-1; i >= 0; i--)
            Move(num, i, s, sum);
        for(i = n-1; i >= j; i--)
            Move(num, i, s, sum);
    }
}
 
int main()
{
    int i, s, n, num[maxn], isadd;
    double sum;
 
    while(scanf("%d %d", &s, &n) == 2)
    {
        sum = 0;
        for(i = 0; i < n; i++)
            scanf("%d", &num[i]);
        scanf("%d", &isadd);
        //FCFS(num, n, s, sum);
        //SSTF(num, n, s, sum);
        //SCAN(num, n, s, sum, isadd);
        CSCAN(num, n, s, sum, isadd);
        printf("%lf\n", sum / n);
    }
 
    return 0;
}
/*
100 9
55 58 39 18 90 160 150 38 184
1
53 8
98 183 37 122 14 124 65 67
300 9
55 58 39 18 90 160 150 38 184
184 9
55 58 39 18 90 160 150 38 184
150 9
55 58 39 18 90 160 150 38 184
0 9
55 58 39 18 90 160 150 38 184
18 9
55 58 39 18 90 160 150 38 184
*/