【操作系统实验】磁盘管理实验

曾经终败给现在 2022-10-04 15:54 264阅读 0赞

### 磁盘管理实验 ###

*  一、 实验目的
 *  二、 实验内容
 *  三、 实验原理
 *  四、 实验要求

# 一、 实验目的 #

1、 了解磁盘调度的策略和原理；  
2、 理解和掌握磁盘调度算法——先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、电梯扫描算法（SCAN）。

# 二、 实验内容 #

1、 模拟先来先服务法（First-Come, First-Served，FCFS），最短寻道时间优先法（Shortest Seek Time First， SSTF），电梯扫描算法（SCAN）三种磁盘调度算法；  
2、 对三种算法进行对比分析。  
3、 输入为一组请求访问磁道序列，输出为每种调度算法的磁头移动轨迹和移动的总磁道数。

# 三、 实验原理 #

1、先来先服务算法（FCFS）: 按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。

2、最短寻道时间优先算法（SSTF） : 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。

3、扫描算法（SCAN）： SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。

# 四、 实验要求 #

1、 输入为一组请求访问磁道序列，该序列和所选磁道个数要求随机生成，输出为每种调度算法的磁头移动轨迹和移动的总磁道数；  
2、 输入磁道范围 0~1000 ，输入所选磁道个数0~1000；

1.  m = rand() % 1000 ; //m:磁道个数
2.  n = rand() % 1000 ; //n:所选磁道个数

3、 画出主程序流程图；

先来先服务算法（FCFS）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70]

最短寻道算法（SSTF）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70 1]

扫描算法（SCAN）:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70 2]

4、 编写程序并调试；

#include <iostream>
    #include <ctime>
    #include <math.h>
    using namespace std;
    
    int *Sequence;                                                     //序列数组指针
    int start, m, n;                                                   //磁头起始位置 m:磁道个数 n:所选磁道个数
    bool flag;                                                         //flag:磁头转动方向 true:从小到大 false 相反
    void init();                                                       //数据初始化
    void FCFS(int &FCFS_Mobile, int &FCFS_position);                   //先来先服务算法（FCFS）
    void SSTF(int &SSTF_Mobile, int *SSTF_Tracks, int &SSTF_position); //最短寻道时间优先算法（SSTF）
    void SCAN(int &SCAN_Mobile, int *SCAN_Tracks, int &SCAN_position); //扫描算法（SCAN）
    int nextSSTF(int SSTF_position, int *SSTF_Sequence);               //最短寻道
    void buddleSort(int *arr);                                         //冒泡排序，序列数组将从小到大排序
    
    //冒泡排序，序列数组将从小到大排序
    void buddleSort(int *arr)
    { 
        int temp = 0;
        int i, j;
    
        for (i = 0; i < n - 1; i++) //外循环为轮数
        { 
            for (j = 0; j < n - 1 - i; j++) //内循环
            { 
                //相邻元素，若逆序则交换（升序为左大于右，降序反之）
                if (arr[j] > arr[j + 1])
                { 
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    //先来先服务算法（FCFS） FCFS_Mobile:磁道移动数 FCFS_position:磁头位置
    void FCFS(int &FCFS_Mobile, int &FCFS_position)
    { 
        for (int i = 0; i < n; i++)
        { 
            FCFS_Mobile += abs(Sequence[i] - FCFS_position); //移动磁道数
            FCFS_position = Sequence[i];
        }
    }
    
    //最短寻道时间优先算法（SSTF）SSTF_Mobile:磁道移动数 SSTF_Tracks:磁道移动轨迹 SSTF_position:磁头位置
    void SSTF(int &SSTF_Mobile, int *SSTF_Tracks, int &SSTF_position)
    { 
        int temp;
        //备份序列数组
        int *SSTF_Sequence = new int(n);
        for (int i = 0; i < n; i++)
            SSTF_Sequence[i] = Sequence[i];
        for (int i = 0; i < n; i++)
        { 
            temp = nextSSTF(SSTF_position, SSTF_Sequence);           //离磁头最近的磁道的索引位置
            SSTF_Mobile += abs(SSTF_Sequence[temp] - SSTF_position); //移动磁道数
            SSTF_position = SSTF_Sequence[temp];                     //修改磁头位置
            SSTF_Tracks[i] = SSTF_Sequence[temp];                    //记录轨迹
            SSTF_Sequence[temp] = -1;                                //将序列数组中读取过的磁道置为-1
        }
    }
    //返回离磁头最近的磁道的索引位置
    int nextSSTF(int SSTF_position, int *SSTF_Sequence)
    { 
        int Min = 10000, target = 0;
        for (int i = 0; i < n; i++)
            if (SSTF_Sequence[i] != -1 && (Min > abs(SSTF_position - SSTF_Sequence[i])))
            { 
                Min = abs(SSTF_position - SSTF_Sequence[i]);
                target = i;
            }
        return target;
    }
    //扫描算法（SCAN） SCAN_Mobile:磁道移动数 SCAN_Tracks:磁道移动轨迹 SCAN_position:磁头位置
    void SCAN(int &SCAN_Mobile, int *SCAN_Tracks, int &SCAN_position)
    { 
        //将序列从小到大排序
        buddleSort(Sequence);
        //轨迹数组的索引
        int nums = 0;
        //记录一开始的磁道的索引位置
        int temp;
        int i = 0;
        for (; i < n; i++)
            //找到序列中最近磁头位置的下一个磁道
            if (Sequence[i] >= SCAN_position)
            { 
                temp = i;
                break;
            }
        //遍历
        for (int j = 0; j < 2; j++)
        { 
            if (flag)
            {  //磁头从小到大访问
                for (; i < n; i++)
                { 
                    SCAN_Mobile += abs(Sequence[i] - SCAN_position); //移动磁道数
                    SCAN_position = Sequence[i];                     //修改磁头位置
                    SCAN_Tracks[nums++] = Sequence[i];               //记录轨迹
                }
                flag = !flag;
                //恢复到一开始的位置向另一个方向遍历
                i = temp - 1;
            }
            else
            {  //磁头从大到小访问
                for (; i >= 0; i--)
                { 
                    SCAN_Mobile += abs(Sequence[i] - SCAN_position); //移动磁道数
                    SCAN_position = Sequence[i];                     //修改磁头位置
                    SCAN_Tracks[nums++] = Sequence[i];               //记录轨迹
                }
                flag = !flag;
                //恢复到一开始的位置向另一个方向遍历
                i = temp + 1;
            }
        }
    }
    //磁道管理
    void ChannelManagement()
    { 
        int FCFS_Mobile = 0, SSTF_Mobile = 0, SCAN_Mobile = 0;                   //磁道移动数
        int SSTF_Tracks[n] = { -1}, SCAN_Tracks[n] = { -1};                        //磁道移动轨迹
        int FCFS_position = start, SSTF_position = start, SCAN_position = start; //磁头位置
    
        //先来先服务算法（FCFS）
        FCFS(FCFS_Mobile, FCFS_position);
        //输出为每种调度算法的磁头移动轨迹和移动的总磁道数；
        cout << "FCFS算法移动的总磁道数: " << FCFS_Mobile << endl;
        cout << "FCFS磁头移动轨迹:";
        for (int i = 0; i < n; i++)
            cout << Sequence[i] << " ";
        cout << endl;
        //最短寻道时间优先算法（SSTF）
        SSTF(SSTF_Mobile, SSTF_Tracks, SSTF_position);
        cout << "SSTF算法移动的总磁道数: " << SSTF_Mobile << endl;
        cout << "SSTF磁头移动轨迹:";
        for (int i = 0; i < n; i++)
            cout << SSTF_Tracks[i] << " ";
        cout << endl;
        cout << "磁头移动的方向: " << (flag == true ? "往数值大的磁道方向转" : "往数值小的磁道方向转") << endl;
        //扫描算法（SCAN）
        SCAN(SCAN_Mobile, SCAN_Tracks, SCAN_position);
        cout << "SCAN算法移动的总磁道数: " << SCAN_Mobile << endl;
        cout << "SCAN磁头移动轨迹:";
        for (int i = 0; i < n; i++)
            cout << SCAN_Tracks[i] << " ";
        cout << endl;
    }
    //生成测试数据(输入为一组请求访问磁道序列，该序列和所选磁道个数要求随机生成)
    void init()
    { 
        srand((unsigned)time(NULL));
        m = rand() % 1000 + 6;                 //m:磁道个数
        n = rand() % 1000 + 6;                 //n:所选磁道个数
        flag = rand() % 1 == 1 ? true : false; //确定磁头转动方向
        start = rand() % m;                    //磁头起始位置
        cout << "磁道个数:" << m << endl
             << "所选磁道个数:" << n << endl
             << "磁头起始位置:" << start << endl;
        Sequence = new int[n];
        for (int i = 0; i < n; i++) //生成求访问磁道序列
            Sequence[i] = rand() % m;
    }
    //菜单
    void show()
    { 
        cout << "***********菜单**************" << endl;
        cout << "*****************************" << endl;
        cout << "****** 1、清屏 ******" << endl;
        cout << "****** 2、磁道管理 ******" << endl;
        cout << "****** 0、退出 ******" << endl;
        cout << "*****************************" << endl;
        cout << "*****************************" << endl;
    }
    int main()
    { 
        while (true)
        { 
            int select;
            show();
            cout << "请输入命令！" << endl;
            cin >> select;
            switch (select)
            { 
            case 1:
            { 
                system("cls");
                break;
            };
            case 2:
            { 
                init();
                ChannelManagement();
                break;
            };
            case 0:
            { 
                system("pause");
                return 0;
            };
            }
        }
    }

4、 截屏输出实验结果；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70 3]  
**【推荐阅读】**  
[【操作系统实验】内存管理][Link 1]  
[【操作系统实验】文件系统][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70]: /images/20221004/c8813050cb11450c8d209b6d85d95495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70 1]: /images/20221004/c5c760e2bb1841628653cbb222af023b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70 2]: /images/20221004/3b19e2ab5e70482bbc6c4f4564c60eee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70 3]: /images/20221004/06b8378d32fd4f9faa5c7518d18d165c.png
[Link 1]: https://blog.csdn.net/weixin_48557496/article/details/118636137
[Link 2]: https://blog.csdn.net/weixin_48557496/article/details/118653158