磁盘调度管理算法

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

"阔列娃" 题目

实验题
  假定一磁盘有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}

"阔列娃" 调度管理效果

diskDispatch

"阔列娃" 源码

#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;
}

爱狂笑的孩子运气不会差