- 实验目的
磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。目前最成用的磁盘调度算法有先来先服务（FCFS），最短寻道时间优先（SSTF），以及扫描算法（SCAN）。通过本实验可以加深理解有关磁盘调度的目标，并体会和了解最短寻道时间优先算法和扫描算法的具体实施办法。
- 实验内容
1 从100#磁道开始，被访问的磁道号分别为：55，58，39，18，90，160，150，38，184。
2 要求用最短寻道时间优先算法的和扫描算法实现磁盘调度。
3 记录下每访问一个磁道磁头移动的磁道数，并计算平均寻道长度（平均移动磁道数）。，，
- 实验要求
分别用两种算法实现磁盘调度。在实验结果分析中，将比较结果以列表的形式表现出来。用数组（或链表）TR[ ]存储待访问磁道号，将每次磁头移动磁道数用数组AR[ ] 存储。输出结果应如下例：（注意空格）
| 150 | 50 |
| 160 | 10 |
| ，184 | 24 |
| 18，， | 166 |
| 38 | 20 |
| 39 | 1 |
| 55 | 16 |
| 58 | 3 |
| 90 | 32 |
| 平均寻道长度：35.8 | |
- 编程工具：
C++语言平台（DevC++开发工具）
五、
(1)问题概述
- 磁盘调度算法的目的是优化磁盘I/O操作，减少磁头移动距离，从而提高磁盘I/O效率。
- 常见的磁盘调度算法包括：先来先服务(FCFS)算法、最短寻道时间优先(SSTF)算法、轮转优先(SCAN)算法、最少最近使用(LRU)算法等。
- FCFS算法按请求到达顺序依次处理请求，简单但效率低下。SSTF算法选择离当前磁头位置最近的请求处理，可以减少磁头移动但难以实现。
- SCAN算法将磁盘划分为多个区，依次扫描每个区处理请求，减少磁头移动但响应时间长。LRU算法优先处理最近最久未使用的磁盘块，需要记录使用信息增加开销。
(2)整体功能及设计
通过构建最短寻道时间优先算法函数、构建扫描算法函数，然后将创作主函数循环调用，并能够输出调度过程以及平均寻道长度。
(3)编程实现（附代码和截图）
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
//55 58 39 18 90 160 150 38 184
void SSTF(int a[], int n) {//最短寻道时间优先调度
int site = 1;//确定开始磁道中间位置
int m, Left, Right;
int i, j, sum = 0;
double Average=0;
int Temp;
sort(a, a + n);//对磁道号进行从小到大排列
printf("排序后磁道数组如下：\n");
for (i = 0; i < n; i++) //输出排序后的磁道号数组
printf("%d ", a[i]);
printf("\n请输入开始的磁道号： ");
scanf("%d", &m);
printf("\nSSTF（最短寻道优先）调度过程如下: \n");
printf("\n被访问的下一个磁道号 移动距离（磁道数）\n");
int mark = m;//用来计算差值或移动距离
if (a[n - 1] <= m)//整个数组里的数都小于开始磁道号的情况
{
for (i = n - 1; i >= 0; i--) { //将数组磁道号就逆序输出
printf("%10d ---------------------- %-3d\n", a[i], mark - a[i]);
mark = a[i];
}
sum = m - a[0];
}
else if (a[0] >= m)//整个数组里的数都大于开始磁道号的情况
{
for (i = 0; i < n; i++) { //将磁道号从小到大顺序输出
printf("%10d ---------------------- %-3d\n", a[i], a[i] - mark);
mark = a[i];
}
sum = a[n - 1] - m;
}
else
{
while (a[site] < m)//找位置
{
site++;
}
Left = site - 1;
Right = site;
//确定开始磁道在已排的序列中的位置
while ((Left >= 0) && (Right < n))
{
if ((m - a[Left]) <= (a[Right] - m))//找最短距离是在左侧还是右侧
{
printf("%10d ---------------------- %-3d\n", a[Left], mark - a[Left]);
mark = a[Left];
sum += m - a[Left];
m = a[Left];
Left = Left - 1;
}
else//在右侧
{
printf("%10d ---------------------- %-3d\n", a[Right], a[Right] - mark);
mark = a[Right];
sum += a[Right] - m;
m = a[Right];
Right = Right + 1;
}
}
if (Left = -1)
{
for (j = Right; j < n; j++)//顺序输出
{
printf("%10d ---------------------- %-3d\n", a[j], a[j] - mark);
mark = a[j];
}
sum += a[n - 1] - a[0];
}
else
{
for (j = Left; j >= 0; j--)//逆序输出
{
printf("%10d ---------------------- %-3d\n", a[j], mark - a[j]);
mark = a[j];
}
sum += a[n - 1] - a[0];
}
}
printf("\n");
Average = (double)sum / n;
printf(" 可见平均寻道的长度为： %.2f \n", Average);
}
void SCAN(int a[], int n) {///扫描算法或电梯调度算法
int i, j, sum = 0;
double Average;
for (i = 0; i < n; i++)
{
sort(a, a + n);//升序排序
}
printf("排序后的磁道数组如下：\n");
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n请输入开始的磁道号： ");
int m;
scanf("%d", &m);
printf("\nSCAN（扫描或电梯）调度过程如下：\n");
printf("\n被访问的下一个磁道号 移动距离（磁道数）\n");
int pointer;
int mark = m;
for (i = 0; i < n; i++)
{
if (a[i] >= m)//找到比开始磁道号大的数
{
pointer = i;
sum += abs(a[i] - m);
break;
}
}
for (i = pointer; i < n; i++)
{
if (i != pointer)//顺着磁头方向顺序输出
sum += abs(a[i] - a[i - 1]);
printf("%10d ---------------------- %-3d\n", a[i], a[i] - mark);
mark = a[i];
}
if (pointer >= 1)
sum += abs(a[n - 1] - a[pointer - 1]);
for (i = pointer - 1; i >= 0; i--)//逆着磁头方向顺序输出
{
if (i)
sum += abs(a[i] - a[i - 1]);
printf("%10d ---------------------- %-3d\n", a[i], mark - a[i]);
mark = a[i];
}
Average = (double)sum / n;
printf("\n 平均寻道的长度为：%.2f\n", Average);
}
int main() {
int track[100];//定义磁道号数组
int select;
int i = 0;
int n;
printf("请先输入磁道数量： \n");
scanf("%d", &n);
printf("请先输入磁道序列： \n");
for (i = 0; i < n; i++)
{
scanf("%d", &track[i]);
}
printf("\n");
while (1)
{
printf("1.最短寻道时间优先算法(SSTF) \n");
printf("2.扫描算法(SCAN)\n");
printf("3.退出\n");
printf("\n");
printf("请选择要使用的调度算法： ");
scanf("%d", &select);
switch (select)//算法选择
{
case 1:
SSTF(track, n);//最短服务时间优先算法
printf("\n");
break;
case 2:
SCAN(track, n);//扫描算法
printf("\n");
break;
case 3:
exit(0);
}
}
return 0;
}
(4)使用说明
输入磁道数量、输入磁道序列、然后回车根据菜单选择相应的调度算法。
(5)结果分析
1. 最短寻道时间优先算法(Shortest Seek Time First, SSTF)
- 优点：能有效减少磁头移动距离，从而减少平均I/O等待时间。
- 缺点：可能导致 starvation,后来请求的I/O等待时间可能很长。
2. 扫描算法(SCAN)
- 优点：能较好避免 starvation 问题，后来请求不会等待过长时间。
- 缺点：磁头移动距离可能较大，平均I/O等待时间较长。
3. 对比分析：
- SSTF算法在减少磁头移动距离上优于SCAN算法，平均I/O等待时间可能较短。
- 但SSTF可能出现一个请求等待时间特别长的情况，不如SCAN在公平性上。
- SSTF更依赖请求分布，如果请求分布不均匀，性能下降明显。
- SCAN算法性能更稳定，不易受请求分布影响。但移动距离较大，平均等待时间较长。
4. 综上，在I/O等待时间优先的场景下，SSTF算法效果较好;在公平性和稳定性要求较高的场景，SCAN算法更适用。
5. 实际使用中，也可以根据负载动态调整两种算法，兼顾等待时间和公平性的优点。
所以两种算法各有优劣，需要根据实际场景具体选择或结合使用，以达到最佳磁盘调度效果。
(6)设计体会
操作系统磁盘调度算法设计和实现给我带来以下几点体会：
1. 磁盘调度算法直接影响系统I/O性能，是操作系统优化的重要一环。不同算法在不同场景下会有很大差异。
2. 算法设计需要考虑公平性、等待时间、移动距离等多方面因素，难度较大。一个好的算法需要兼顾各项指标。
3. 实际系统I/O请求模式复杂，简单的算法在实际中效果可能不如预期。需要结合负载动态调整策略。
4. 算法实现需要考虑多磁盘和多请求并发场景，数据结构和同步机制的设计很重要。
5. 不同算法在不同系统和应用场景下性能也会有差异。需要通过实验对比分析不同参数和场景下的优劣。
7. 算法是一个需要不断优化和更新的模块。需要提供良好的扩展接口支持后期升级。
8. 理解主流算法原理和思路，对设计和优化自己的算法很有帮助。
9. 磁盘调度涉及操作系统、算法和性能优化多个知识点。整个设计过程让我对系统有了更深入的认识。
总体来说，磁盘调度算法设计是一个系统性和实践性很强的学习过程，给我带来很多收获。它也反映了操作系统研发需要考虑的各个方面。
