操作系统实验六

Ewdager

发布于 2020-07-14 14:33:11

9630

发布于 2020-07-14 14:33:11

文章被收录于专栏：Gvoidy备份小站

实验内容

本实验通过编程模拟实现几种常见的磁盘调度算法

简直可怕，怎么可能写出来磁盘调度算法啊喂！算法实现倒还好说，就是一个排序算法。但是！访问的柱面就是随机生成的所以还要写iterator？！这里简单描述一下各种磁盘调度算法。

例:假定某磁盘共有200个柱面，编号为0-199，如果在为访问143号柱面的请求者服务后，当前正在为访问125号柱面的请求服务，同时有若干请求者在等待服务，它们每次要访问的柱面号为 86，147，91，177，94，150，102，175，130

1、先来先服务算法（FCFS）First Come First Service 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。先来先服务（125）86.147.91.177.94.150.102.175.130

2、最短寻道时间优先算法（SSTF） Shortest Seek Time First 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。最短寻道时间优先（125）130.147.150.175.177.102.94.91.86

3、扫描算法（SCAN）电梯调度 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。电梯调度（125）102.94.91.86.130.147.150.175.177

4、循环扫描算法（CSCAN） 循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。循环扫描（125）130.147.150.175.177.86.91.94.102

转自枫叶

以下是抄的代码

#include <iostream>  
#include <time.h>  
#include <vector>  
#include <math.h>  
#include <stdlib.h>  
#include <algorithm>  
#include <cstring>  
#include <windows.h>  
#include <fstream>  
using namespace std;  

int position = 0;      //当前磁道位置  
int dis = 0;  
double average_distance = 0;  

void request(vector<int>&m_vec,ofstream &outfile){  
    cout<<"随机生成磁盘序列："<<endl;  
    int n = 0;  
    srand(time(NULL));     //添加随机数种子  
    n = rand() % 20 + 1;  
    int temp = 0;  
    for(int i=0;i<n;i++){  
        temp = rand() % 100;  
        m_vec.push_back(temp);  
        cout<<temp<<" ";  
        outfile<<temp<<endl;  
    }  
    cout<<endl;  
    position = rand() % 100;  
    cout<<"当前磁道："<<position<<endl;  
}  

void compute_dis(vector<int>m_vec,int &dis,double &average_distance){  
    average_distance = (double)dis / (double)m_vec.size();  
}  

void FIFO(vector<int>m_vec,int position){     //先来先服务算法  
    dis = 0;  
    average_distance = 0;  
    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  
        dis += abs(position-*it);  
        Sleep(500);  
        cout<<"->"<<*it;  
        position = *it;  
    }  
    compute_dis(m_vec,dis,average_distance);  
}  

void SSTF(vector<int>m_vec,int position){   //最短寻道时间算法  
    dis = 0;  
    average_distance = 0;  
    sort(m_vec.begin(),m_vec.end());    //从小到大排序  
    int i = 0;  
    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  
        if(position >= *it)  
            i++;  
    }  
    int count = 0;  
    int left = i-1;  
    int right = i;  
    while(count<m_vec.size()){  
        if((left >=0 && abs(m_vec[right]-position) > abs(m_vec[left]-position)) || right>=m_vec.size()){  
            dis += abs(m_vec[left]-position);  
            Sleep(500);  
            cout<<"->"<<m_vec[left];  
            position = m_vec[left];  
            left--;  
        }  
        else{  
            dis += abs(m_vec[right]-position);  
            Sleep(500);  
            cout<<"->"<<m_vec[right];  
            position = m_vec[right];  
            right++;  
        }  
        count++;  
    }  
    compute_dis(m_vec,dis,average_distance);  
}  

void SCAN(vector<int>m_vec,int position){   //电梯调度算法  
    dis = 0;  
    average_distance = 0;  
    sort(m_vec.begin(),m_vec.end());    //从小到大排序  
    int i = 0;  
    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  
        if(position >= *it)  
            i++;      //找到position所在的磁道  
    }  
    int left = i - 1;   //先从外到内扫描  
    int right = i;  
    while(left >= 0){  
        dis += abs(position - m_vec[left]);  
        Sleep(500);  
        cout<<"->"<<m_vec[left];  
        position = m_vec[left];  
        left --;  
    }  
    while(right < m_vec.size()){  
        dis += abs(position - m_vec[right]);  
        Sleep(500);  
        cout<<"->"<<m_vec[right];  
        position = m_vec[right];  
        right ++;  
    }  
    compute_dis(m_vec,dis,average_distance);  
}  

void CSCAN(vector<int>m_vec,int position){   //循环扫描算法  
    dis = 0;  
    average_distance = 0;  
    sort(m_vec.begin(),m_vec.end());    //从小到大排序  
    int i = 0;  
    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  
        if(position >= *it)  
            i++;      //找到position所在的磁道  
    }  
    int left = i - 1;   //先从外到内扫描  
    int right = i;  
    while(left >= 0){  
        dis += abs(position - m_vec[left]);  
        Sleep(500);  
        cout<<"->"<<m_vec[left];  
        position = m_vec[left];  
        left --;  
    }  
    position = 100;     //立即到最外侧的磁道  
    int len = m_vec.size()-1;  
    while(len >= right){  
        dis += abs(position - m_vec[len]);  
        Sleep(500);  
        cout<<"->"<<m_vec[len];  
        position = m_vec[len];  
        len --;  
    }  
    compute_dis(m_vec,dis,average_distance);  
}  

void FSCAN(vector<int>m_vec,int position){   //分步电梯调度算法，。分两个队列  
    dis = 0;  
    average_distance = 0;  
    //SCAN(m_vec,position);  
    sort(m_vec.begin(),m_vec.end());    //从小到大排序  
    int i = 0;  
    for(vector<int>::iterator it=m_vec.begin();it!=m_vec.end();it++){  
        if(position >= *it)  
            i++;      //找到position所在的磁道  
    }  
    int left = i - 1;   //先从外到内扫描  
    int right = i;  
    while(left >= 0){  
        dis += abs(position - m_vec[left]);  
        Sleep(500);  
        cout<<"->"<<m_vec[left];  
        position = m_vec[left];  
        left --;  
    }  
    while(right < m_vec.size()){  
        dis += abs(position - m_vec[right]);  
        Sleep(500);  
        cout<<"->"<<m_vec[right];  
        position = m_vec[right];  
        right ++;  
    }  
    cout<<endl;  
    cout<<"在扫描的过程中新产生的服务序列："<<endl;  
    vector<int>ve;  
    while(!ve.empty())  
        ve.pop_back();  
    int n = 0;  
    n = rand() % 20 + 1;  
    int temp = 0;  
    for(i=0;i<n;i++){  
        temp = rand() % 100;  
        cout<<temp<<"　";  
        ve.push_back(temp);  
    }  
    cout<<endl;  
    cout<<position;  
    SCAN(ve,position);  
    average_distance = (double)dis / (double)(m_vec.size()+ve.size());  
}  

void print(){  
    cout<<endl<<endl;  
    cout<<"经计算，磁头移动的总距离为:"<<dis<<endl;  
    cout<<"磁头平均移动距离:"<<average_distance<<endl;  
    cout<<endl<<endl;  
}  

int choose_algorithm(vector<int>m_vec){  
    cout<<endl<<endl;  
    cout<<"本实验可用的调度算法有以下5种："<<endl;  
    cout<<"1.FIFO  2.SSTF  3.SCAN  4.CSCAN  5.FSCAN  6.结束本序列的调度  7.结束程序"<<endl;  
    int choice = 0;  
    cout<<"选择："<<endl;  
    cin>>choice;  
    cout<<endl;  
    while(choice!=6 && choice!=7){  
        cout<<"磁盘请求的服务状况："<<endl;  
        cout<<position;  
        switch(choice){  
            case 1:  
                FIFO(m_vec,position);break;  
            case 2:  
                SSTF(m_vec,position);break;  
            case 3:  
                SCAN(m_vec,position);break;  
            case 4:  
                CSCAN(m_vec,position);break;  
            case 5:  
                FSCAN(m_vec,position);break;  
            default:  
                cout<<"******非法输入！******"<<endl<<endl;break;   
        }   
        if(choice<=7 && choice>=1)   
            print();  
        cout<<"选择："<<endl;  
        cin>>choice;  
    }  
    if(choice == 7)  
        return 0;  
    else  
        cout<<endl<<endl;  
    return 1;  
}  

int main(){  
    cout<<"---------------磁盘调度算法模拟实验-----------------"<<endl;  
    ofstream outfile;  
    outfile.open("data.txt");  
    while(1){  
        vector<int> vec;  
        while(!vec.empty())  
            vec.pop_back();  
        request(vec,outfile);         //请求服务序列   
        int flag = choose_algorithm(vec);  
        if(flag == 0)  
            break;  
    }   
    outfile.close();  
    return 0;  
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法