[操作系统]磁盘调度

C++ 操作系统
操作系统
发布日期:   2021-05-07
文章字数:   2.3k
阅读时长:   10 分
阅读次数:  

题目描述

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

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

2、要求分别采用先来先服务、最短寻道优先以及电梯调度算法进行调度。

3、要求给出每种算法中磁盘访问的顺序，计算出平均移动道数。

4、假定当前读写头在90号，电梯调度算法向磁道号增加的方向移动。

程序功能及设计思路

程序功能：

程序获取一组磁盘访问的信息进行调度，用户可以选择调度的算法，包括先来先服务算法、最短寻道优先算法以及电梯调度算法三个算法，程序用相关算法运行后输出磁盘访问的顺序以及平均的移动道数。

设计思路：

主要是三个算法的设计:

先来先服务算法:直接按顺序访问数组中的每个磁道号即可。

最短寻道算法：每次访问前在未访问的磁道序列中找到距离当前磁头最近的一个磁道号进行访问，访问后从数组中移除，每次都这么寻找下一个磁道号直到全部访问。

电梯调度算法：直接按照初始读写头将数组中的磁道号分为两部分，一部分为大于初始磁道号的磁道集合，另一部分为小于初始磁道号的磁道集合，然后将第一部分按从小到大排序，第二部分按从大到小排序，那么读取顺序就是先把第一部分按顺序输出，再把第二部分按顺序输出。

程序功能及设计思路

数据结构：

//访问的节点
struct Request
{
    string name;        
    int track;            
    int runTrack;        
    Request() {};
    Request(string n, int t) :name(n), track(t), runTrack(0) {};
};

每个磁道访问的节点，一共有3个数据成员，包括请求的名称name，访问的磁道号track以及移动的磁道号runTrack。

//磁道调度
class DiskScheduling
{
private:
    vector<Request> requests;        //所有的请求
    vector<Request> finish;            //完成了的请求
    int curTrack;                    //读写头的位置

    void getData(string fileName);        //将数据读入内存
public:
    DiskScheduling() {};
    DiskScheduling(string fileName);
    void FIFO();                    //先来先服务算法
    void SSTF();                    //最短寻道时间算法
    void SCAN();                    //电梯调度算法
    void print();                   //输出运行结果
};

为主要的数据结构，用一个数组存储所有的请求，一个数组用于存储完成了的请求，用一个int类型的数据放置读写头的位置。以及一些主要的成员函数，例如将数据从文件读入内存，先来先服务算法的实现，最短寻道时间算法的实现，电梯调度算法的实现以及输出最终的运行结果。

算法设计：

//将数据读入内存
void DiskScheduling::getData(string fileName)
{
    fstream outFile;
    string line;
    string a, b;
    outFile.open(fileName, ios::in);        //打开文件
    if (!outFile.is_open())
    {    //判断文件能否打开
        cout << "文件无法打开！" << endl;
        return;
    }

    while (!outFile.eof())
    {
        getline(outFile, line);
        stringstream input(line);
        input >> a >> b;

        Request* temp = new Request(a,stoi(b));

        requests.push_back(*temp);
    }
    outFile.close();
}

算法思想：将数据内容从文件读入内存中，打开文件后，逐行读取，每一行为一个数据节点，每行的第一个元素为请求名，第二个元素为磁道号，字符串切割后转化为一个请求节点存入数组requests中。

//先来先服务算法
void DiskScheduling::FIFO()
{
    curTrack = 90;
    finish.clear();
    for (int i = 0;i < requests.size();i++)
    {
        requests[i].runTrack = abs(requests[i].track - curTrack);
        curTrack = requests[i].track;
        finish.push_back(requests[i]);
    }
}

算法思想：按数组中的顺序逐个访问请求，计算出移动的磁道后将节点移入完成节点中，并且更新磁头的位置为磁道号。

//最短寻道时间算法
void DiskScheduling::SSTF()
{
    curTrack = 90;
    finish.clear();
    vector<Request> jobs(requests);
    Request nowQue;
    int index;
    while (!jobs.empty())
    {
        index = 0;
        nowQue = jobs.front();
        for (int i = 0;i < jobs.size();i++)
        {//找到距离最短的那一个
            if (abs(nowQue.track - curTrack) > abs(jobs[i].track - curTrack))
            {//有更短的就更新
                nowQue = jobs[i];
                index = i;
            }
        }
        nowQue.runTrack = abs(nowQue.track - curTrack);
        curTrack = nowQue.track;
        finish.push_back(nowQue);
        jobs.erase(jobs.begin() + index);
    }
}

算法思想：当请求数组不为空时，就遍历查找到距离当前磁头最短的请求，访问这个最短的请求即可，访问后计算出移动的磁道数，加入到已访问的数组中。并且更新磁头的位置为磁道号。

//电梯调度算法
void DiskScheduling::SCAN()
{
    curTrack = 90;
    finish.clear();
    vector<Request> requests1;
    vector<Request> requests2;
    //将大于等于现在磁道数的放到请求集合1中,小于的放到2
    for (int i = 0;i < requests.size();i++)
    {
        if (requests[i].track >= curTrack)
        {
            requests1.push_back(requests[i]);
        }
        else
        {
            requests2.push_back(requests[i]);
        }
    }
    //requests1从小到大排序，requests2从大到小排序
    sort(requests1.begin(), requests1.end(), cmp1());
    sort(requests2.begin(), requests2.end(), cmp2());
    //先依次访问requests1
    for (int i = 0;i < requests1.size();i++)
    {
        requests1[i].runTrack = abs(requests1[i].track - curTrack);
        curTrack = requests1[i].track;
        finish.push_back(requests1[i]);
    }
    //再依次访问requests1
    for (int i = 0;i < requests2.size();i++)
    {
        requests2[i].runTrack = abs(requests2[i].track - curTrack);
        curTrack = requests2[i].track;
        finish.push_back(requests2[i]);
    }
}

算法思想：遍历一次所有请求，将大于当前磁道号的放入数组1中，小于当前磁道号的放入数组2中，数组1按从大到小排序，数组2按从小到大排序。排序完毕后先依次访问并计算数组1中的请求与磁道号，放入访问过的数组中，再依次访问并计算数组2中的请求与磁道号，放入访问过的数组中即可。每访问一个请求就要更新一次磁道号。

//输出运行结果
void DiskScheduling::print()
{
    int total = 0;
    for (int i = 0;i < finish.size();i++)
    {
        cout << "请求名称为：" << finish[i].name << "\t\t移动的道数为:" << finish[i].runTrack << endl;
        total += finish[i].runTrack;
    }
    cout << "平均移动的道数为：" << float(total) / float(finish.size()) << endl;
}

算法思想：依次访问完成队列中的每一个元素，输出对应的请求名称以及移动的道数，同时计算平均的移动道数并输出。

源代码

data.txt

A    30
B    50
C    100
D    180
E    20
F    90
G    150
H    70
I    80
J    10
K    160
L    120
M    40
N    110

diskScheduling.cpp

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <sstream>
#include <math.h>

using namespace std;
//访问的节点
struct Request
{
    string name;        //请求名称
    int track;            //访问的磁道
    int runTrack;        //移动的道数
    Request() {};
    Request(string n, int t) :name(n), track(t), runTrack(0) {};
};

//按磁道从小到大排序
struct cmp1
{
    bool operator()(Request& a, Request& b) { return a.track < b.track; }
};

//按磁道从大到小排序
struct cmp2
{
    bool operator()(Request& a, Request& b) { return a.track > b.track; }
};

//磁道调度
class DiskScheduling
{
private:
    vector<Request> requests;        //所有的请求
    vector<Request> finish;            //完成了的请求
    int curTrack;                    //读写头的位置

    void getData(string fileName);        //将数据读入内存
public:
    DiskScheduling() {};
    DiskScheduling(string fileName);
    void FIFO();                    //先来先服务算法
    void SSTF();                    //最短寻道时间算法
    void SCAN();                    //电梯调度算法
    void print();                   //输出运行结果
};


DiskScheduling::DiskScheduling(string fileName)
{
    getData(fileName);
}

//将数据读入内存
void DiskScheduling::getData(string fileName)
{
    fstream outFile;
    string line;
    string a, b;
    outFile.open(fileName, ios::in);        //打开文件
    if (!outFile.is_open())
    {    //判断文件能否打开
        cout << "文件无法打开！" << endl;
        return;
    }

    while (!outFile.eof())
    {
        getline(outFile, line);
        stringstream input(line);
        input >> a >> b;

        Request* temp = new Request(a,stoi(b));

        requests.push_back(*temp);
    }
    outFile.close();
}

//先来先服务算法
void DiskScheduling::FIFO()
{
    curTrack = 90;
    finish.clear();
    for (int i = 0;i < requests.size();i++)
    {
        requests[i].runTrack = abs(requests[i].track - curTrack);
        curTrack = requests[i].track;
        finish.push_back(requests[i]);
    }
}

//最短寻道时间算法
void DiskScheduling::SSTF()
{
    curTrack = 90;
    finish.clear();
    vector<Request> jobs(requests);
    Request nowQue;
    int index;
    while (!jobs.empty())
    {
        index = 0;
        nowQue = jobs.front();
        for (int i = 0;i < jobs.size();i++)
        {//找到距离最短的那一个
            if (abs(nowQue.track - curTrack) > abs(jobs[i].track - curTrack))
            {//有更短的就更新
                nowQue = jobs[i];
                index = i;
            }
        }
        nowQue.runTrack = abs(nowQue.track - curTrack);
        curTrack = nowQue.track;
        finish.push_back(nowQue);
        jobs.erase(jobs.begin() + index);
    }

}

//电梯调度算法
void DiskScheduling::SCAN()
{
    curTrack = 90;
    finish.clear();
    vector<Request> requests1;
    vector<Request> requests2;
    //将大于等于现在磁道数的放到请求集合1中,小于的放到2
    for (int i = 0;i < requests.size();i++)
    {
        if (requests[i].track >= curTrack)
        {
            requests1.push_back(requests[i]);
        }
        else
        {
            requests2.push_back(requests[i]);
        }
    }
    //requests1从小到大排序，requests2从大到小排序
    sort(requests1.begin(), requests1.end(), cmp1());
    sort(requests2.begin(), requests2.end(), cmp2());
    //先依次访问requests1
    for (int i = 0;i < requests1.size();i++)
    {
        requests1[i].runTrack = abs(requests1[i].track - curTrack);
        curTrack = requests1[i].track;
        finish.push_back(requests1[i]);
    }
    //再依次访问requests1
    for (int i = 0;i < requests2.size();i++)
    {
        requests2[i].runTrack = abs(requests2[i].track - curTrack);
        curTrack = requests2[i].track;
        finish.push_back(requests2[i]);
    }
}

//输出运行结果
void DiskScheduling::print()
{
    int total = 0;
    for (int i = 0;i < finish.size();i++)
    {
        cout << "请求名称为：" << finish[i].name << "\t\t移动的道数为:" << finish[i].runTrack << endl;
        total += finish[i].runTrack;
    }
    cout << "平均移动的道数为：" << float(total) / float(finish.size()) << endl;
}
int main()
{
    DiskScheduling obj("data.txt");
    cout << "先来先服务算法:" << endl;
    obj.FIFO();
    obj.print();
    cout << "\n最短寻道时间算法:" << endl;
    obj.SSTF();
    obj.print();
    cout << "\n电梯调度算法:" << endl;
    obj.SCAN();
    obj.print();
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/05/07/cao-zuo-xi-tong-ci-pan-diao-du/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 操作系统
赏
评论
 本篇
[操作系统]磁盘调度 [操作系统]磁盘调度
题目描述1、对于如下给定的一组磁盘访问进行调度： 请求服务到达 A B C D E F G H I J K L M N 访问的磁道号 30 50 100 180 20 90 150 70 80 10 160 120 40 110
2021-05-07 操作系统
C++ 操作系统
下一篇 
[操作系统]作业调度 [操作系统]作业调度
题目描述1、假设系统中可同时运行两道作业，给出每道作业的到达时间和运行时间，如下表所示： 作业名 A B C D E F G H I J 到达时间 0 2 5 7 12 15 4 6 8 10 运行时间 7 10 20 30
2021-05-02 操作系统
C++ 操作系统
  目录