磁盘调度算法模拟实验

磁盘调度算法模拟实验

实验目的

1. 了解磁盘调度中寻道时间对数据访问速度的影响。
2. 通过模拟实验比较不同磁盘调度算法的效率和优劣。

实验原理

磁盘调度算法的目标是优化磁头寻址路径，减少寻道时间，提高数据访问速度。本实验模拟了四种常见的磁盘调度算法：

1. 先来先服务 (FCFS)：按照请求到达的顺序依次处理，简单易实现，但可能出现饥饿现象。
2. 最短寻道时间优先 (SSTF)：每次选择与当前磁头位置最近的请求进行处理，能减少寻道时间，但可能出现某些请求长期得不到响应。
3. SCAN：磁头从当前位置开始，单向移动到磁盘的边缘，然后反向移动，处理所有请求。能避免饥饿现象，但响应时间可能不均衡。
4. CSCAN：在 SCAN 算法的基础上进行改进，将磁头移动到磁盘边缘后，直接跳到另一端的边缘，继续按原方向处理请求，进一步提高效率和公平性。

数据结构和符号说明

数据结构

• TrackNum: 磁道数量
• StartTrack: 起始磁道号
• Sum: 寻道长度总和
• TrackOrder[MaxNumber]: 磁道序列数组，长度最大为 MaxNumber
• visit[MaxNumber]: 访问顺序数组，长度最大为 MaxNumber
• Move[MaxNumber]: 移动距离数组，长度最大为 MaxNumber
• isvisited[MaxNumber]: 标记每个磁道是否被访问过
• avg: 平均寻道长度

符号说明

• abs(x): 返回 x 的绝对值
• setw(n): 设置输出宽度为 n 个字符
• initial(): 初始化函数，用于将数组清零和标记恢复
• FCFS(): 先来先服务算法函数
• SSTF(): 最短寻道时间优先算法函数
• SCAN(): 扫描算法函数
• CSCAN(): 循环扫描算法函数
• show(): 显示函数，用于输出磁道访问顺序和平均寻道长度

流程图

1. 先来先服务策略处理

2. 采用最短寻道策略处理

3. SCAN策略处理

4. CSCAN策略处理

源程序

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

const int MaxNumber = 100;  // 定义常量MaxNumber为100，用来表示最大磁道访问数
int TrackNum, StartTrack, Sum;  // 磁道数、起始磁道号、总移动距离
int TrackOrder[MaxNumber], visit[MaxNumber], Move[MaxNumber];  // 磁道序列、被访问的磁道、移动距离
bool isvisited[MaxNumber];  // 用于记录每个磁道是否已经被访问
double avg;  // 平均寻道长度

void FCFS(); // 先来先服务(FCFS)算法
void SSTF(); // 最短寻道时间优先(SSTF)算法
void SCAN(); // 扫描(SCAN)算法
void CSCAN(); // 循环扫描(CSCAN)算法
void show(); // 显示信息

void initial() {
    for (int i = 0; i < TrackNum; i++) {
        Move[i] = 0;
        visit[i] = TrackOrder[i];
        isvisited[i] = false;
    }
    Sum = 0; avg = 0;
}

void FCFS() {  // 先来先服务(FCFS)算法
    initial();

    // 计算起始磁道与第一个被访问的磁道之间的移动距离
    Move[0] = abs(TrackOrder[0] - StartTrack);;
    Sum = Move[0];
    visit[0] = TrackOrder[0];

    // 依次计算访问每个磁道时所需要移动的距离，并累加移动距离，记录磁道访问序列
    for (int i = 1; i < TrackNum; i++) {
        Move[i] = abs(TrackOrder[i] - TrackOrder[i - 1]);
        Sum += Move[i];
        visit[i] = TrackOrder[i];
    }

    // 计算平均寻道长度
    avg = Sum * 1.0 / TrackNum;
    show();
}

void SSTF() {
    int posMin, curTrack = StartTrack;
    int disT[MaxNumber];

    initial();

    for (int i = 0; i < TrackNum; i++) { // 对于每个将要访问的磁道
        for (int j = 0; j < TrackNum; j++) { // 遍历所有未访问的磁道
            if (!isvisited[j]) { // 如果该磁道未被访问过
                disT[j] = abs(TrackOrder[j] - curTrack); // 计算该磁道与当前磁头之间的距离
            }
            else {
                disT[j] = 10000; // 如果该磁道已经被访问过，则认为其距离当前磁头的距离为无穷大，不再进行考虑
            }
        }

        // 找到距离当前磁头最近的未访问磁道
        posMin = 0;
        for (int j = 0; j < TrackNum; j++) {
            if (disT[posMin] > disT[j]) {
                posMin = j;
            }
        }

        // 记录访问序列及移动距离，并更新当前磁头位置、被访问的磁道以及已访问标志
        visit[i] = TrackOrder[posMin];
        Move[i] = abs(TrackOrder[posMin] - curTrack);
        Sum += Move[i];
        curTrack = TrackOrder[posMin];
        isvisited[posMin] = true;
    }

    avg = Sum * 1.0 / (TrackNum); // 计算平均寻道长度
    show();
}

void SCAN() {
    int trackIndex[MaxNumber], SortTrack[MaxNumber];
    int t, tIndex;
    int point = 0;
    int count = 0, curTrack = StartTrack;

    initial();

    // 将磁道序列以及对应的索引值存储下来
    for (int i = 0; i < TrackNum; i++) {
        trackIndex[i] = i;
        SortTrack[i] = TrackOrder[i];
    }

    // 对磁道进行排序
    for (int i = TrackNum - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (SortTrack[j] >= SortTrack[j + 1]) {
                t = SortTrack[j]; // 更新排序的磁道号
                SortTrack[j] = SortTrack[j + 1];
                SortTrack[j + 1] = t;

                tIndex = trackIndex[j];  //更新排序的磁道号索引值
                trackIndex[j] = trackIndex[j + 1];
                trackIndex[j + 1] = tIndex;
            }
        }
    }

    // 找到当前磁头所在位置在排序后的磁道序列中的位置
    while (StartTrack >= SortTrack[point]) {
        point++;
    }

    cout << '            向磁道增加的方向访问' << endl;

    // 先访问所有磁道号比当前磁头磁道号大的磁道
    for (int i = point; i < TrackNum; i++) {
        visit[count] = SortTrack[i];
        Move[count] = abs(visit[count] - curTrack);
        curTrack = visit[count];
        count++;
    }

    // 再逆序访问所有剩下的磁道
    for (int i = point - 1; i >= 0; i--) {
        visit[count] = SortTrack[i];
        Move[count] = abs(visit[count] - curTrack);
        curTrack = visit[count];
        count++;
    }

    // 计算总移动距离、平均寻道时间等信息
    for (int i = 0; i < TrackNum; i++) {
        Sum += Move[i];
    }

    avg = (Sum * 1.0) / TrackNum;
    show();
}

void CSCAN() {
    int t, tIndex;
    int trackIndex[MaxNumber], SortTrack[MaxNumber];
    int count = 0, curTrack = StartTrack;
    int point = 0;

    initial();

    // 将磁道序列以及对应的索引值存储下来
    for (int i = 0; i < TrackNum; i++) {
        trackIndex[i] = i;
        SortTrack[i] = TrackOrder[i];
    }

    // 对磁道进行排序
    for (int i = TrackNum - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (SortTrack[j] >= SortTrack[j + 1]) {
                t = SortTrack[j]; // 更新排序的磁道号
                SortTrack[j] = SortTrack[j + 1];
                SortTrack[j + 1] = t;

                tIndex = trackIndex[j];  //更新排序的磁道号索引值
                trackIndex[j] = trackIndex[j + 1];
                trackIndex[j + 1] = tIndex;

            }
        }
    }

    // 找到当前磁头所在位置在排序后的磁道序列中的位置
    while (StartTrack >= SortTrack[point]) {
        point++;
    }

    cout << '            向磁道增加的方向访问' << endl;

    // 先访问所有磁道号比当前磁头磁道号大的磁道
    for (int i = point; i < TrackNum; i++) {
        visit[count] = SortTrack[i];
        Move[count] = abs(visit[count] - curTrack);
        curTrack = visit[count];
        count++;
    }

    // 再从0号磁道开始访问磁道，到当前磁头所在磁道之前的所有磁道
    for (int i = 0; i < point; i++) {
        visit[count] = SortTrack[i];
        Move[count] = abs(visit[count] - curTrack);
        curTrack = visit[count];
        count++;
    }

    // 计算总移动距离、平均寻道时间等信息
    for (int i = 0; i < TrackNum; i++) {
        Sum += Move[i];
    }

    avg = (Sum * 1.0) / TrackNum;
    show();
}

void show() {  //显示信息
    cout << '=============================================' << endl;

    cout <<'              从' << StartTrack << '号磁道开始    ' << endl;
    cout << setw(2) << '被访问的下一个磁道号   ' << setw(6) << '   移到距离（磁道数）' << setw(4) << endl;
    for (int i = 0; i < TrackNum; i++) {
        cout << setw(10) << visit[i] << setw(24) << Move[i] << setw(8) << endl;
    }

    cout << '=============================================' << endl;

    printf('平均寻道长度: %.2f', avg);
}

int main() {
    //输入数据信息
    StartTrack = 100;
    cout << '请先输入磁道数量: ' << endl;
    cin >> TrackNum;
    cout << '请先输入磁道序列: ' << endl;
    for (int i = 0; i < TrackNum; i++) {
        cin >> TrackOrder[i];
    }
    cout << '
磁道访问序列：' << endl;
    for (int i = 0; i < TrackNum; i++)
        cout << TrackOrder[i] << ' ';
    cout << endl << endl;

    //先来先服务(FCFS)
    cout << '1.先来先服务(FCFS)' << endl;
    FCFS();
    cout << endl << endl;

    //最短寻道时间优先(SSTF)
    cout << '2. 最短寻道时间优先(SSTF)' << endl;
    SSTF();
    cout << endl << endl;

    //扫描(SCAN)算法
    cout << '3.扫描(SCAN)算法' << endl;
    SCAN();
    cout << endl << endl;

    //循环扫描(CSCAN)算法
    cout << '4.循环扫描(CSCAN)算法' << endl;
    CSCAN();
    cout << endl << endl;

    return 0;
}

运行截图

1. 先来先服务策略处理

2. 最短寻道策略处理

3. SCAN策略处理

4. CSCAN策略处理

实验小结和心得

本次实验主要研究了磁盘调度中不同的寻道时间策略对数据访问速度的影响。通过编写程序模拟实验，我学习了先来先服务、最短寻道、SCAN 和 CSCAN 这四种策略，并掌握了不同策略的优缺点和运行原理。

• 先来先服务策略 的优点是简单易实现，但由于处理请求的顺序只与请求提交的先后顺序有关，所以可能会出现饥饿现象，即某些请求长时间得不到响应。
• 最短寻道策略 能够减少磁头移动距离和寻道时间，提高数据访问速度，但可能会出现一些磁道长时间无法得到访问的情况，因为磁头可能会一直在其他位置附近徘徊，导致某些距离较远的请求长时间等待。
• SCAN策略 则是将磁头按一个方向运动到最边缘，然后反向运动，依次处理每个方向上的请求。该策略能够平均分配响应时间，避免饥饿现象和不公平现象。
• CSCAN策略 则是在 SCAN 的基础上进行改进，即将磁头移动到磁盘的最边缘后，直接移动到另一个端点，继续按原来的方向处理请求。这种策略能够进一步提高数据访问效率和公平性，因为磁头不再需要回退到原点，而是直接移动到另一端，减少了不必要的移动时间。

在实验过程中，我通过编写程序，模拟实现了不同的磁盘调度策略，并记录了磁头移动距离和平均寻道长度等数据，直观地展示了不同策略的效率差异。实验结果验证了理论分析，并让我对磁盘调度算法有了更深刻的理解。

通过本次实验，我体会到，选择合适的磁盘调度算法对于提高磁盘访问性能至关重要。在实际应用中，需要根据具体情况选择合适的算法，例如，对于需要快速响应的应用，可以选择最短寻道时间优先算法；对于需要保证公平性的应用，可以选择 SCAN 或 CSCAN 算法。

此外，我还认识到程序设计和算法分析的密切关系。程序设计需要根据算法原理进行实现，而算法分析可以帮助我们更好地理解程序的行为和性能。在未来的学习中，我会更加注重理论与实践相结合，不断提升自己的编程能力和算法分析能力。

总结

本次实验让我更加深入地了解了磁盘调度算法的原理和应用，并锻炼了我的编程能力和算法分析能力。相信这些宝贵的经验将对我今后的学习和工作有所帮助。