磁盘调度管理算法

这是操作系统上机实验的最后一次实验，所以得好好收个尾，虽然就没精彩过。

"阔列娃" 题目

实验题
  假定一磁盘有200个柱面，编号为0~199，当前移动臂的位置在143号柱面上，并刚刚完成125号柱面的服务请求，如果请求队列的先后顺序是86，147，91，177，94，150，102，175，130。请按下列算法分别计算为完成上述各次访问总共需要的磁头移动量，并写出磁头的移动顺序。要求通过编写模拟程序实现，开发工具任选。
- 电梯算法；
- 最短寻找时间优先算法(SSTF)。

"阔列娃" 分析

  磁盘的盘面是有磁道的，那么磁道是什么呢？磁道就是一圈一圈的同心圆，一个盘面有200个同心圆。一个磁盘具有多个盘面，那么在立体3D结构上，每个盘面的同一个磁道就构成了一个柱面，就像一个圆柱体。
  那么每一个盘面上都会有一个叫做磁头的东西，系统控制磁头去读写磁盘（磁头的旋转都是同时的），那么磁头总得有个位置，题目给出位置在143号柱面上，即在一个盘面上，她在143号磁道上。那么她刚刚完成125号柱面的服务请求是什么意思呢？就是说这个磁头将要往磁道号大的方向上移动了（即往圆心移动，最外磁道为0，最里面为200）。
  那么现在请求队列的先后顺序是86，147，91，177，94，150，102，175，130，那么对于我们的俩个调度算法怎么实现呢？我们先来学习俩个调度算法的core思想。

• 电梯算法（SCAN Pro）
    电梯算法（SCAN Pro）不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。当磁头正在由里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样由里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向，由外向里移动。这时，同样也是每次选择在当前磁道之内，且距离最近的进程来调度。

• 最短寻找时间优先算法(SSTF)
    SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比FCFS（先来先服务）算法更好的性能。这种算法会产生“饥饿”现象。

  平均寻道 = \frac{moveDisk}{requestDisk}

"阔列娃" 调度管理效果

"阔列娃" 源码

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

vector<unsigned int> reqTrack = {55,58,39,18,90,160,150,38,184};//86,147,91,177,94,150,102,175,130; 55,58,39,18,90,160,150,38,184;
vector<unsigned int> seqTrack;
vector<unsigned int> countTrack;
unsigned int startPos;
unsigned int totalTrack;
bool direction = 0; // 0: to small, 1: to large

void disTrack()
{
        cout<<" --------------------"<<endl;
    for (int i = 0; i < seqTrack.size(); i++)
    {
        cout<<"||"<<setw(6)<<seqTrack[i]<<setw(4)<<"|"<<setw(5)<<countTrack[i]<<setw(5)<<"||"<<endl;
        cout<<" --------------------"<<endl;
    }
}

void initialVector()
{
    seqTrack.clear();
    countTrack.clear();
    vector<unsigned int>().swap(seqTrack);
    vector<unsigned int>().swap(countTrack);
    totalTrack = 0;
}

void scanPro()
{
    initialVector();

    cout<<"Where the Track heading of ELEVATOR to: (For '0' to small, for '1' to large) ";
    cin>>direction;

    vector<unsigned int> small,large;
    unsigned int dis=0;
    int pos = startPos;
    float averageTrack=0.0;

    for (int i = 0; i < reqTrack.size(); i++)
    {
        if (reqTrack[i] == pos)
        {
            seqTrack.push_back(reqTrack[i]);
            countTrack.push_back(0);
        }
        else if (reqTrack[i] < pos)
        {
            small.push_back(reqTrack[i]);
        }
        else if (reqTrack[i] > pos)
        {
            large.push_back(reqTrack[i]);

        }
    }

    sort(large.begin(),large.end());
    sort(small.rbegin(),small.rend());

    // core
    if (direction) // 1: first to large
    {
        for (int i = 0; i < large.size(); i++)
        {
            seqTrack.push_back(large[i]);

            dis = large[i] - pos;
            totalTrack+=dis;
            countTrack.push_back(dis);
            pos = large[i];

        }
        for (int i = 0; i < small.size(); i++)
        {
            seqTrack.push_back(small[i]);

            dis = pos - small[i];
            totalTrack+=dis;
            countTrack.push_back(dis);
            pos = small[i];
        }
    }
    else // 0: first to small
    {
        for (int i = 0; i > small.size(); i++)
        {
            seqTrack.push_back(small[i]);

            dis = pos - small[i];
            totalTrack+=dis;
            countTrack.push_back(dis);
            pos = small[i];
        }
        seqTrack.push_back(0);
        dis = pos - 0;
        totalTrack+=dis;
        countTrack.push_back(dis);
        pos = 0;
        for (int i = 0; i < large.size(); i++)
        {
            seqTrack.push_back(large[i]);

            dis = large[i] - pos;
            totalTrack+=dis;
            countTrack.push_back(dis);
            pos = large[i];
        }
    }

    cout<<"#======Elevator======#"<<endl;
    cout<<"#---Track--|--Dist---#"<<endl;
    disTrack();
    averageTrack = (float) totalTrack/ (float) reqTrack.size();
    cout<<"The Total Track is: "<<totalTrack<<endl;
    cout<<"The Average Track is: "<<averageTrack<<endl;
}

void SSTF()
{
    initialVector();

    vector<unsigned int> small,large;
    unsigned int dis=0;
    int pos = startPos;
    float averageTrack=0.0;

    for (int i = 0; i < reqTrack.size(); i++)
    {
        if (reqTrack[i] == pos)
        {
            seqTrack.push_back(reqTrack[i]);
            countTrack.push_back(0);
        }
        else if (reqTrack[i] < pos)
        {
            small.push_back(reqTrack[i]);
        }
        else if (reqTrack[i] > pos)
        {
            large.push_back(reqTrack[i]);

        }
    }

    sort(large.begin(),large.end());
    sort(small.rbegin(),small.rend());

    // core
    int i=0,j=0;
    while (i < small.size() && j < large.size())
    {
        if (pos - small[i] >= large[j] - pos) // close to the large
        {
            seqTrack.push_back(large[j]);

            dis = large[j] - pos;
            totalTrack+=dis;
            countTrack.push_back(dis);
            pos = large[j];
            j++;
        }
        else  // close to the small
        {
            seqTrack.push_back(small[i]);

            dis = pos - small[i];
            totalTrack+=dis;
            countTrack.push_back(dis);
            pos = small[i];
            i++;
        }
    }

    while (i < small.size())
    {
        seqTrack.push_back(small[i]);

        dis = pos - small[i];
        totalTrack+=dis;
        countTrack.push_back(dis);
        pos = small[i];
        i++;
    }
    while (j < large.size())
    {
        seqTrack.push_back(large[j]);

        dis = large[j] - pos;
        totalTrack+=dis;
        countTrack.push_back(dis);
        pos = large[j];
        j++;
    }

    cout<<"#========SSTF========#"<<endl;
    cout<<"#---Track--|--Dist---#"<<endl;
    disTrack();
    averageTrack = (float) totalTrack/ (float) reqTrack.size();
    cout<<"The Total Track is: "<<totalTrack<<endl;
    cout<<"The Average Track is: "<<averageTrack<<endl;
}

int main()
{
    cout<<"The Request Track is: ";
    for (int i = 0; i < reqTrack.size(); i++)
    {
        cout<<reqTrack[i]<<" ";
    }
    cout<<endl;

    cout<<"The Start Track is: ";
    cin>>startPos;

    scanPro();
    cout<<endl;
    SSTF();
    return 0;
}