磁盘调度算法

1、对于如下给定的一组磁盘访问进行调度：

请求服务到达	A	B	C	D	E	F	G	H	I	J	K
访问的磁道号	30	50	100	180	20	90	150	70	80	10	160

2、要求分别采用先来先服务、最短寻道优先以及电梯调度方法进行调度。
3、要求给出每种算法中磁盘访问的顺序，计算出平均移动道数。
4、假定当前读写头在90号，向磁道号增加的方向移动。

算法大致流程：

程序代码:

#include<iostream>
#include<cmath>
using namespace std;
#define maxsize 1000 
int cmp(const void*a, const void*b) {
    return *(int*)a - *(int*)b;
}
void visit(int *a, int pos, int &now, int &sum) {
    cout << a[pos] << " ";
    sum += abs(now - a[pos]);
    now = a[pos];
}
void FIFO(int diskQue[], int m)
{
    int sum = 0, now;
    cout << "当前的读写头位于:";
    cin >> now;
    cout << "\nFIFO 调度顺序: ";
    for (int i = 0; i < m; i++) cout << diskQue[i] << " ";
    sum = abs(now - diskQue[0]);
    for (int j = 1; j < m; j++) sum += abs(diskQue[j] - diskQue[j - 1]);
    cout << "\n移动的总道数:" << sum;
    cout << "\n平均寻道长度:" << (sum*1.0 / m) << endl;
}
void SSTF(int disk[], int m)
{
    int k = 1;
    int left, right;
    int sum = 0;
    int * tempa;
    tempa = new int(m);
    for (int i = 0; i < m; i++) tempa[i] = disk[i];
    qsort(tempa, m, sizeof(int), cmp);
    cout << "当前的读写头位于:";
    int now; cin >> now;
    cout << "\nSSTF 调度顺序: ";
    if (tempa[m - 1] <= now)
    {
        for (int i = m - 1; i >= 0; i--) cout << tempa[i] << " ";
        sum = now - tempa[0];
    }
    else if (tempa[0] >= now)
    {
        for (int i = 0; i < m; i++) cout << tempa[i] << " ";
        sum = tempa[m - 1] - now;
    }
    else
    {
        while (tempa[k] < now) k++;
        left = k - 1;
        right = k;
        while ((left >= 0) && (right < m))
        {
            if ((now - tempa[left]) <= (tempa[right] - now)) 
visit(tempa, left--, now, sum);
            else visit(tempa, right++, now, sum);
        }
        if (left = -1)
        {
            for (int j = right; j < m; j++) cout << tempa[j] << " ";
            sum += tempa[m - 1] - tempa[0];
        }
        else
        {
            for (int j = left; j >= 0; j--) cout << tempa[j] << " ";
            sum += tempa[m - 1] - tempa[0];
        }
    }
    cout << "\n移动的总道数:" << sum;
    cout<< "\n平均寻道长度:" << (sum*1.0 / m) << endl;
}
void SCAN(int disk[], int m)
{
    int * tempa;
    tempa = new int(m);
    for (int i = 0; i < m; i++) tempa[i] = disk[i];
    int sum = 0;
    qsort(tempa, m, sizeof(int), cmp);
    cout << "当前的读写头位于: ";
    int now; cin >> now;
    cout << "\nSCAN 调度顺序:";
    int pos = 0;
    while (tempa[pos] < now) pos++;
    for (int i = pos; i < m; i++) {
        visit(tempa, i, now, sum);
    }
    for (int i = pos; i >= 0; i--) {
        visit(tempa, i, now, sum);
    }
    cout << "\n移动的总道数:" << sum;
    cout << "\n平均寻道长度:" << (sum*1.0 / m) << endl;
}
int main()
{
    char c;
    int diskQue[maxsize];
    int i = 0;
    int b = 0;
    cout << "输入磁道序列(-1结束): ";
    for (i = 0; b != -1; i++) { cin >> b; diskQue[i] = b; }
    cout << "磁道读取结果: ";
    for (i = 0; diskQue[i] != -1; i++) cout << diskQue[i] << " ";
    int count = i;
    while (1)
    {
        cout << "\n1.先进先出算法(FIFO) \n";
        cout << "2.最短服务时间优先算法(SSTF) \n";
        cout << "3.扫描算法(SCAN)\n";
        cout << "4.退出(exit)\n";
        cout << "请选择算法:";
        cin >> c;
        switch (c)
        {
        case '1':FIFO(diskQue, count); break;
        case '2':SSTF(diskQue, count); break;
        case '3':SCAN(diskQue, count); break;
        case '4':return 0;
        default:cout << "输入有误!"; continue;
        }
    }
    return 0;
}

运行结果:

输入磁道序列(-1结束): 30 50 100 180 20 90 150 70 80 10 160 -1
磁道读取结果: 30 50 100 180 20 90 150 70 80 10 160
1.先进先出算法(FIFO)
2.最短服务时间优先算法(SSTF)
3.扫描算法(SCAN)
4.退出(exit)
请选择算法:1
当前的读写头位于:90

FIFO 调度顺序: 30 50 100 180 20 90 150 70 80 10 160
移动的总道数:810
平均寻道长度:73.6364

1.先进先出算法(FIFO)
2.最短服务时间优先算法(SSTF)
3.扫描算法(SCAN)
4.退出(exit)
请选择算法:2
当前的读写头位于:90

SSTF 调度顺序: 90 80 70 50 30 20 10 100 150 160 180
移动的总道数:250
平均寻道长度:22.7273

1.先进先出算法(FIFO)
2.最短服务时间优先算法(SSTF)
3.扫描算法(SCAN)
4.退出(exit)
请选择算法:3
当前的读写头位于: 90

SCAN 调度顺序:90 100 150 160 180 90 80 70 50 30 20 10
移动的总道数:260
平均寻道长度:23.6364

1.先进先出算法(FIFO)
2.最短服务时间优先算法(SSTF)
3.扫描算法(SCAN)
4.退出(exit)
请选择算法:4

---