操作系统-第六章-磁盘调度算法（使用C++和vector实现）

温馨提示：下面代码我使用的是含有c++的标准模板库(STL)vector的知识，还有文件读取的知识，如果没有学习过相关知识的同学，请先移步搜索相关视频或者帖子学习一下，我知道你的破学校或许不会教这些标准模板库的东西，但是你必须得学会，因为这才是C++的重中之重的知识。

【实验内容】

用高级语言模拟磁盘调度算法中先来先服务算法，最短寻道时间优先算法，电梯调度算法和 CSCAN 算法。要求输入一个磁盘访问请求序列，输出实际处理请求的次序，并且计算输出平均寻道长度。

【实验原理】

先来先服务（FCFS）：按照请求的顺序逐个处理磁道请求，没有优化准则。

最短寻道时间优先（SSTF）：选择当前磁头位置最近的磁道作为下一个访问的磁道，以最小化磁头移动距离。

扫描算法（SCAN）：磁头沿着一个方向移动到达最远的磁道，然后返回到最近的磁道，依此遍历磁道序列。

循环扫描算法（CSCAN）：类似于扫描算法，但是在到达磁道末尾后，磁头直接回到磁道起始位置，形成一个循环。

这里使用计算机操作系统（第四版）汤小丹梁红兵 哲凤屏 汤子瀛 编著第六章6.8节参考数据，结果一样

文件使用文本输入填写

第一行是开始的磁道，上面是100，

第二行开始是按先来先服务填写的磁道访问顺序，其余算法均按这行数据进行

①FCFS（先来先服务）算法：

代码中使用了简单的循环来遍历磁道请求序列，按照请求的顺序依次访问磁道，计算移动距离并输出结果。

②SSTF（最短寻道时间优先）算法：

通过计算当前磁头位置与请求序列中其他磁道的距离，选择最近的磁道作为下一个访问的磁道，以此来减少总的寻道时间。每次选择最近的磁道访问，并更新磁头位置，直至所有请求完成。

③SCAN（扫描）算法：

分为递增和递减两个方向进行模拟。先对请求序列排序，然后从磁头初始位置开始，沿着一个方向移动至最远的磁道号，再返回到最近的磁道并反方向访问，直到全部请求完成。算法根据磁头移动的方向遍历请求序列，并计算移动距离。

④CSCAN（循环扫描）算法：

for (int i = 0; i < totalRequests; i++)
    {
        if (copiedVector[i] > initialHead)
        {
            index = i;
            break;
        }
    }

同样分为递增和递减两个方向。首先对请求序列排序，然后从磁头初始位置开始，一直沿一个方向移动至请求的磁道号末尾，再从磁道的另一端开始继续移动，形成一个循环，直到完成所有请求。算法也根据磁头移动的方向遍历请求序列，并计算移动距离。

在扫描算法（SCAN）和循环扫描算法（CSCAN）中，我是用上面代码找到请求序列中大于初始磁头位置（initialHead）的第一个磁道的索引位置。

具体来说，这个循环迭代请求序列（copiedVector），检查每个磁道的位置是否大于初始磁头位置（initialHead）。一旦找到第一个大于初始磁头位置的磁道，就会将该磁道的索引赋值给变量index，并且立即跳出循环（使用break语句）。这个过程是为了在扫描算法和循环扫描算法中确定磁头移动的起始位置。索引index将被用于确定磁头开始移动的位置，从而执行不同方向的磁道扫描。

还有一点，在sstf最短寻道时间优先算法中，我判断两个磁道之间的距离是暴力判断，一开始没有排序，没有排序，每判断一个数字，记录一下距离，然后通过比较距离找到距离最小的那个输出，并且把它从vector数组中抹除，然后再判断下一个。实际在笔试考试过程中，你应该先把所有给出的磁道先排个序，这样可以方便快速的找到相邻距离最短的磁道。这里我为了偷懒起见就不想搞那么复杂的排序外加判断的算法，毕竟磁道数不多

所有代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream ifs;
int initialHead;
vector<int> requests;
vector<int> copiedVector;

// 计算两个磁道之间的距离
int calculateDistance(int head, int request)
{
    return abs(head - request);
}

// 寻找最短寻道距离的磁道
int findClosestRequest(vector<int>& requests, int head)//逐个判断，不排序了
{
    int minDistance = 999999;
    int closestRequest = -1;

    for (unsigned i = 0; i < requests.size(); ++i)
    {
        int distance = calculateDistance(head, copiedVector[i]);
        if (distance < minDistance)
        {
            minDistance = distance;
            closestRequest = i;
        }
    }

    return closestRequest;
}

// 实现SSTF算法
void SSTF(vector<int>& requests, int head)
{

    // 使用 assign() 进行深度拷贝
    copiedVector.assign(requests.begin(), requests.end());

    int totalRequests = copiedVector.size();
    int totalDistance = 0;

    cout << "SSTF磁盘访问次序: " << endl;

    cout << "被访问的下一个磁道号       移动距离(磁道数)" << endl;

    for (int i = 0; i < totalRequests; ++i)
    {
        int closestIndex = findClosestRequest(copiedVector, head);
        int closestRequest = copiedVector[closestIndex];
        int currentDis = calculateDistance(head, closestRequest);

        totalDistance += currentDis;

        cout << setw(12) << closestRequest << "     " << setw(19) << currentDis << endl;

        head = closestRequest;
        copiedVector.erase(copiedVector.begin() + closestIndex);
    }

    cout << "\n平均寻道长度: " << fixed << setprecision(1) << static_cast<double>(totalDistance) / totalRequests << endl;

    copiedVector.clear();
}


// 实现FCFS算法
void FCFS(vector<int>& requests, int head)
{
    int totalRequests = requests.size();
    int totalDistance = 0;

    cout << "FCFS磁盘访问次序: " << endl;
    cout << "被访问的下一个磁道号       移动距离(磁道数)" << endl;

    for (int i = 0; i < totalRequests; ++i)
    {
        int currentRequest = requests[i];
        int currentDis = calculateDistance(head, currentRequest);

        totalDistance += currentDis;

        cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

        head = currentRequest;
    }

    cout << "\n平均寻道长度: " << fixed << setprecision(1) << static_cast<double>(totalDistance) / totalRequests << endl;
    // cout.unsetf(ios::fixed); // 取消固定小数位数的设置
    copiedVector.clear();
}



// 实现SCAN算法
void SCAN(vector<int>& requests, int head, bool increasing)
{
    // 使用 assign() 进行深度拷贝
    copiedVector.assign(requests.begin(), requests.end());

    sort(copiedVector.begin(), copiedVector.end()); // 对请求排序

    int totalRequests = copiedVector.size();
    int totalDistance = 0;

  
    int index = 0;

    for (int i = 0; i < totalRequests; i++)
    {
        if (copiedVector[i] > initialHead)
        {
            index = i;
            break;
        }
    }

    if (increasing)
    {
        cout << "SCAN磁盘访问次序(递增方向): " << endl;
        cout << "被访问的下一个磁道号       移动距离(磁道数)" << endl;
        for (unsigned i = unsigned(index); i < copiedVector.size(); ++i)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }

        for (int i = index - 1; i >= 0; i--)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }
    }
    else

    {

        cout << "SCAN磁盘访问次序(递减方向): " << endl;
        cout << "被访问的下一个磁道号       移动距离(磁道数)" << endl;

        for (int i = index - 1; i >= 0; i--)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }

        for (unsigned i = index; i < copiedVector.size(); i++)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }
    }

    cout << "\n平均寻道长度: " << fixed << setprecision(1) << static_cast<double>(totalDistance) / totalRequests << endl;

    copiedVector.clear();
}

// 实现CSCAN算法
void CSCAN(vector<int>& requests, int head, bool increasing)
{
    // 使用 assign() 进行深度拷贝
    copiedVector.assign(requests.begin(), requests.end());

    sort(copiedVector.begin(), copiedVector.end()); // 对请求排序

    int totalRequests = copiedVector.size();
    int totalDistance = 0;

   
    int index = 0;

    for (int i = 0; i < totalRequests; i++)
    {
        if (copiedVector[i] > initialHead)
        {
            index = i;
            break;
        }
    }

    if (increasing)

  

    {
        cout << "CSCAN磁盘访问次序(递增方向): " << endl;
        cout << "被访问的下一个磁道号       移动距离(磁道数)" << endl;
        for (unsigned i = index; i < copiedVector.size(); ++i)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }

        for (int i = 0; i < index; ++i)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }
    }

    else
    { // 递减
        cout << "CSCAN磁盘访问次序(递减方向): " << endl;
        cout << "被访问的下一个磁道号       移动距离(磁道数)" << endl;
        for (int i = index-1; i >= 0; --i)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }

        for (unsigned i = index; i < copiedVector.size(); ++i)
        {
            int currentRequest = copiedVector[i];
            int currentDis = calculateDistance(head, currentRequest);

            totalDistance += currentDis;

            cout << setw(12) << currentRequest << "     " << setw(19) << currentDis << endl;

            head = currentRequest;
        }
    }

    cout << "\n平均寻道长度: " << fixed << setprecision(1) << static_cast<double>(totalDistance) / totalRequests << endl;

    copiedVector.clear();
}
// 读取文件input.txt的数值
void read()
{
    ifs >> initialHead;
    int num;
    while (ifs >> num)
    {
        requests.push_back(num);
    }
}
// 遍历打印磁道号的数字
void print(vector<int> a)
{
    for (int num : a)
    {
        cout << num << " ";
    }
    cout << endl;
}

int main()
{

    ifs.open("input.txt", ios::in);
    if (!ifs.is_open())
    {
        cout << "文件打开失败" << endl;
        return 0;
    }

    read();
    print(requests);
    FCFS(requests, initialHead);
    cout << "================================================\n\n" << endl;
    SSTF(requests, initialHead);
    cout << "================================================\n\n"<< endl;
  
    SCAN(requests, initialHead, true);
    cout << "================================================\n\n"<< endl;
    SCAN(requests, initialHead, false);
    cout << "================================================\n\n" << endl;
    CSCAN(requests, initialHead, true);
    cout << "================================================\n\n" << endl;
    CSCAN(requests, initialHead, false);
    cout << "================================================\n\n" << endl;
    return 0;
}