成都工业学院2021级操作系统专周课程设计FCFS，SSTF，SCAN，LOOK算法的实现

运行环境

操作系统：Windows 11 家庭版

运行软件：CLion 2023.2.2

源代码文件

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;

// 生成随机数
int generateRandomNumber(int min, int max) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(min, max);
    return dis(gen);
}

// 计算引臂移动量
int calculateArmMovement(const vector<int>& movementSequence) {
    int movement = 0;
    for (int i = 1; i < movementSequence.size(); ++i) {
        movement += abs(movementSequence[i] - movementSequence[i-1]);
    }
    return movement;
}

// 计算寻道时间
int calculateSeekTime(int armMovement, int timePerTrack) {
    return armMovement * timePerTrack;
}

// 计算平均旋转延迟时间
int calculateRotationDelay(int armMovement, int diskSpeed) {
    return (armMovement * 60000) / diskSpeed; // 因转速为转/分钟，转成毫秒需要乘以60000
}

// 计算传输时间
int calculateTransferTime(int numRequests, int sectorsPerTrack, int sectorSize, int diskSpeed) {
    int transferTime = (numRequests * sectorsPerTrack * sectorSize * 1000) / diskSpeed; // 字节数除以转速得到毫秒数
    return transferTime;
}

// 计算总处理时间
int calculateTotalProcessingTime(int seekTime, int rotationDelay, int transferTime) {
    return seekTime + rotationDelay + transferTime;
}

// 显示引臂移动序列
void displayArmMovementSequence(const vector<int>& movementSequence) {
    for (int i = 0; i < movementSequence.size(); ++i) {
        cout << movementSequence[i] << " ";
    }
    cout << endl;
}

// SSTF算法
void sstfAlgorithm(vector<int>& ioRequests, int currentTrack, int timePerTrack, int diskSpeed, int sectorsPerTrack, int sectorSize) {
    cout << "SSTF算法：" << endl;
    vector<int> armMovementSequence;
    armMovementSequence.push_back(currentTrack); // 先添加当前磁道到移动序列

    while (!ioRequests.empty()) {
        int minDistance = INT_MAX;
        int nextTrack = -1;

        for (int i = 0; i < ioRequests.size(); ++i) {
            int distance = abs(currentTrack - ioRequests[i]);
            if (distance < minDistance) {
                minDistance = distance;
                nextTrack = ioRequests[i];
            }
        }

        armMovementSequence.push_back(nextTrack);
        currentTrack = nextTrack;
        ioRequests.erase(find(ioRequests.begin(), ioRequests.end(), nextTrack));
    }

    displayArmMovementSequence(armMovementSequence);
    int armMovement = calculateArmMovement(armMovementSequence);
    int seekTime = calculateSeekTime(armMovement, timePerTrack);
    int rotationDelay = calculateRotationDelay(armMovement, diskSpeed);
    int numRequests = ioRequests.size();
    int transferTime = calculateTransferTime(numRequests, sectorsPerTrack, sectorSize, diskSpeed);
    int totalProcessingTime = calculateTotalProcessingTime(seekTime, rotationDelay, transferTime);

    cout << "引臂移动量: " << armMovement << endl;
    cout << "寻道时间: " << seekTime << " 毫秒" << endl;
    cout << "平均旋转延迟时间: " << rotationDelay << " 毫秒" << endl;
    cout << "传输时间: " << transferTime << " 毫秒" << endl;
    cout << "所有访问处理时间: " << totalProcessingTime << " 毫秒" << endl;
}

//SCAN算法
void scanAlgorithm(vector<int>& ioRequests, int currentTrack, int timePerTrack, int diskSpeed, int sectorsPerTrack, int sectorSize) {
    cout << "SCAN算法：" << endl;
    vector<int> scanArmMovementSequence;
    int maxTrack = *max_element(ioRequests.begin(), ioRequests.end());
    int minTrack = *min_element(ioRequests.begin(), ioRequests.end());
    scanArmMovementSequence.push_back(currentTrack);

    vector<int> tempStack;
    vector<bool> visitedTracks(200, false); // 初始化标记数组，200是磁道的数量

    if (currentTrack >= maxTrack) {
        // 先向内扫描
        tempStack.push_back(0); // 添加0进入栈
        visitedTracks[0] = true;

        for (int track = currentTrack - 1; track >= minTrack; --track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end() && !visitedTracks[track]) {
                tempStack.push_back(track);
                visitedTracks[track] = true;
            }
        }

        sort(tempStack.begin(), tempStack.end()); // 对栈进行排序

        // 将栈中的磁道添加到移动序列
        for (int track : tempStack) {
            scanArmMovementSequence.push_back(track);
        }

        // 到达最小磁道号后折返，向外扫描
        for (int track = minTrack + 1; track <= maxTrack; ++track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end() && !visitedTracks[track]) {
                scanArmMovementSequence.push_back(track);
                visitedTracks[track] = true;
            }
        }
    } else {
        // 先向外扫描
        tempStack.push_back(199); // 添加199进入栈
        visitedTracks[199] = true;

        for (int track = currentTrack + 1; track <= maxTrack; ++track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end() && !visitedTracks[track]) {
                tempStack.push_back(track);
                visitedTracks[track] = true;
            }
        }

        sort(tempStack.begin(), tempStack.end()); // 对栈进行排序

        // 将栈中的磁道添加到移动序列
        for (int track : tempStack) {
            scanArmMovementSequence.push_back(track);
        }

        // 到达最大磁道号后折返，向内扫描
        for (int track = maxTrack - 1; track >= minTrack; --track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end() && !visitedTracks[track]) {
                scanArmMovementSequence.push_back(track);
                visitedTracks[track] = true;
            }
        }
    }

    displayArmMovementSequence(scanArmMovementSequence);
    int scanArmMovement = calculateArmMovement(scanArmMovementSequence);
    int scanSeekTime = calculateSeekTime(scanArmMovement, timePerTrack);
    int scanRotationDelay = calculateRotationDelay(scanArmMovement, diskSpeed);
    int scanNumRequests = ioRequests.size();
    int scanTransferTime = calculateTransferTime(scanNumRequests, sectorsPerTrack, sectorSize, diskSpeed);
    int scanTotalProcessingTime = calculateTotalProcessingTime(scanSeekTime, scanRotationDelay, scanTransferTime);

    cout << "引臂移动量: " << scanArmMovement << endl;
    cout << "寻道时间: " << scanSeekTime << " 毫秒" << endl;
    cout << "平均旋转延迟时间: " << scanRotationDelay << " 毫秒" << endl;
    cout << "传输时间: " << scanTransferTime << " 毫秒" << endl;
    cout << "所有访问处理时间: " << scanTotalProcessingTime << " 毫秒" << endl;
    // 在最后释放visitedTracks的空间
    visitedTracks.clear();
    displayArmMovementSequence(scanArmMovementSequence);
}

// LOOK算法
void lookAlgorithm(vector<int>& ioRequests, int currentTrack, string direction, int timePerTrack, int diskSpeed, int sectorsPerTrack, int sectorSize) {
    cout << "LOOK算法：" << endl;
    vector<int> armMovementSequence;
    int maxTrack = *max_element(ioRequests.begin(), ioRequests.end());
    int minTrack = *min_element(ioRequests.begin(), ioRequests.end());
    armMovementSequence.push_back(currentTrack); // 先添加当前磁道到移动序列

    if (direction == "outward") {
        // 向外扫描
        for (int track =  currentTrack + 1; track <= maxTrack; ++track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end()) {
                armMovementSequence.push_back(track);
            }
        }
        // 向内扫描
        for (int track = currentTrack - 1; track >= minTrack; --track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end()) {
                armMovementSequence.push_back(track);
            }
        }
    } else {
        // 向内扫描
        for (int track = currentTrack - 1; track >= minTrack; --track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end()) {
                armMovementSequence.push_back(track);
            }
        }
        // 向外扫描
        for (int track = currentTrack + 1; track <= maxTrack; ++track) {
            if (find(ioRequests.begin(), ioRequests.end(), track) != ioRequests.end()) {
                armMovementSequence.push_back(track);
            }
        }
    }

    displayArmMovementSequence(armMovementSequence);
    int armMovement = calculateArmMovement(armMovementSequence);
    int seekTime = calculateSeekTime(armMovement, timePerTrack);
    int rotationDelay = calculateRotationDelay(armMovement, diskSpeed);
    int numRequests = ioRequests.size();
    int transferTime = calculateTransferTime(numRequests, sectorsPerTrack, sectorSize, diskSpeed);
    int totalProcessingTime = calculateTotalProcessingTime(seekTime, rotationDelay, transferTime);

    cout << "引臂移动量: " << armMovement << endl;
    cout << "寻道时间: " << seekTime << " 毫秒" << endl;
    cout << "平均旋转延迟时间: " << rotationDelay << " 毫秒" << endl;
    cout << "传输时间: " << transferTime << " 毫秒" << endl;
    cout << "所有访问处理时间: " << totalProcessingTime << " 毫秒" << endl;
}

// 根据选择的调度算法进行处理
void processAlgorithm(vector<int>& ioRequests, int currentTrack, int timePerTrack, int startupTime, int diskSpeed, int sectorsPerTrack, int sectorSize, const string& algorithmName) {
    vector<int> armMovementSequence;
    if (algorithmName == "FCFS") {
        armMovementSequence = ioRequests;  // 直接按照顺序处理请求
    } else if (algorithmName == "SSTF") {
        sstfAlgorithm(ioRequests, currentTrack, timePerTrack, diskSpeed, sectorsPerTrack, sectorSize);
        return;
    } else if (algorithmName == "SCAN") {
        scanAlgorithm(ioRequests, currentTrack, timePerTrack, diskSpeed, sectorsPerTrack, sectorSize);
        return;
    } else if (algorithmName == "LOOK") {
        lookAlgorithm(ioRequests, currentTrack, "outward", timePerTrack, diskSpeed, sectorsPerTrack, sectorSize);
        return;
    } else {
        cout << "未知的调度算法：" << algorithmName << endl;
        return;
    }

    armMovementSequence.insert(armMovementSequence.begin(), currentTrack);  // 加入初始位置
    displayArmMovementSequence(armMovementSequence);

    int armMovement = calculateArmMovement(armMovementSequence);
    int seekTime = calculateSeekTime(armMovement, timePerTrack);
    int rotationDelay = calculateRotationDelay(armMovement, diskSpeed);
    int numRequests = ioRequests.size();
    int transferTime = calculateTransferTime(numRequests, sectorsPerTrack, sectorSize, diskSpeed);
    int totalProcessingTime = calculateTotalProcessingTime(seekTime, rotationDelay, transferTime);

    cout << "引臂移动量: " << armMovement << endl;
    cout << "寻道时间: " << seekTime << " 毫秒" << endl;
    cout << "平均旋转延迟时间: " << rotationDelay << " 毫秒" << endl;
    cout << "传输时间: " << transferTime << " 毫秒" << endl;
    cout << "所有访问处理时间: " << totalProcessingTime << " 毫秒" << endl;
}

int main() {
    int initialTrack; // 磁头初始位置
    cout << "请输入磁头初始位置：";
    cin >> initialTrack;
    int timePerTrack;  // 跨越1个磁道所用时间（毫秒）
    int startupTime;   // 启动时间（毫秒）
    int diskSpeed;     // 磁盘转速（转/分钟）
    int sectorsPerTrack;  // 每磁道扇区数
    int sectorSize;    // 每扇区字节数

    cout << "请输入跨越1个磁道所用时间（毫秒）：";
    cin >> timePerTrack;
    cout << "请输入启动时间（毫秒）：";
    cin >> startupTime;
    cout << "请输入磁盘转速（转/分钟）：";
    cin >> diskSpeed;
    cout << "请输入每磁道扇区数：";
    cin >> sectorsPerTrack;
    cout << "请输入每扇区字节数：";
    cin >> sectorSize;

    vector<int> ioRequests;
    vector<int> diskTrackNumbers;
    for(int i=1; i<201; i++){
        diskTrackNumbers.push_back(i);
    } // 磁道号固定为0到10
    int currentTrack = initialTrack; // 修改为用户输入的初始位置
    string direction = (generateRandomNumber(0, 1) == 0) ? "outward" : "inward"; // 添加这一行以初始化方向

    // 生成随机磁道I/O请求序列
    cout << "生成的随机磁道I/O请求序列：" << endl;
    for (int i = 0; i < 6; ++i) {
        int track = generateRandomNumber(0, diskTrackNumbers.size() - 1);
        ioRequests.push_back(diskTrackNumbers[track]);
        cout << ioRequests[i] << " ";
    }
    cout << endl;

    // 选择调度算法
    string algorithmName;
    cout << "请选择调度算法（FCFS、SSTF、SCAN、LOOK）：";
    cin >> algorithmName;

    // 处理IO请求
    processAlgorithm(ioRequests, currentTrack, timePerTrack, startupTime, diskSpeed, sectorsPerTrack, sectorSize, algorithmName);

    return 0;
}

?源代码示例

?运行结果截图

FCFS算法

SSTF算法

?SCAN算法

LOOK算法

?注意事项

1、算法可能有点问题，大多数情况下是没有问题的

2、由于不同编译器可能不兼容，所以本人把代码都写在一起，避免了分文件造成的错误