当前位置：首页 > news >正文

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

news 2025/7/23 22:09:52

运行环境

操作系统：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到10int 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;
}