《操作系统原理及应用》课程设计报告
磁盘调度算法
学院（系）：计算机科学与工程学院
班级：37-5 学号
学生姓名：
时间：从2013 年12 月16日到2013 年12月20日
1、课程设计的目的
本课程设计是学生学习完《操作系统原理及应用》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
2、课程设计的内容及要求
编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度：
要求设计主界面以灵活选择某算法，且以下算法都要实现
1、先来先服务算法（FCFS）
2、最短寻道时间优先算法（SSTF）
3、扫描算法（SCAN）
4、循环扫描算法（CSCAN）
3、实现原理
磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先、扫描和循环扫描等算法。
其中，平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N
其中Mi为磁头从上一各磁道到这个磁道所需移动的距离。
4、算法
1.先来先服务算法（FCFS）
这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法只考虑访问者提出访问请求的先后次序，按照先后次序依次访问磁道号。移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。
2.短寻道时间优先算法（SSTF）
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，而不管访问者到来的先后次序。实现时可以先对磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，选择离自己最近的访问，每比较一次，当前磁道号也跟着变化，移动距离等于上一个被访问的
磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，就逆序访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，就正序访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。
3.扫描算法（SCAN）
SCAN 算法又称电梯调度算法。该算法先考虑磁头的移动方向，再考虑距离近的访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再逆向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后逆向访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，两种方向都是逆序对磁道号访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，两种方向都是正序对磁道号访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。
4.循环扫描算法（CSCAN）
CSCAN算法是在SCAN算法的基础上规定磁头单向移动，即扫描时要么向磁道号增加的方向的访问，要么向磁道号减小的方向访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再返回磁道最里面朝增加的方向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后返回到磁道最外层访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当向磁道号增加的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是正序访问；而当向磁道号减小的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是逆序访问；此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。
5、程序中使用的数据结构及使用的变量说明和作用
int[] cidao = new int[1000];//将被访问的磁道号存入cidao数组
int sum = 0;//求移动距离之和
double avg = 0;//求平均寻道时间
string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号
int now = Convert.ToInt32(txtnow.Text);//获取当前的磁道号
for (int i = 0; i < str.Length; i++)
{//将获取的磁道号存入磁道号数组
cidao[i] = Convert.ToInt32(str[i]);
}
private void btnFCFS_Click(object sender, EventArgs e)先来先服务FCFS算法private void btnSSTF_Click(object sender, EventArgs e)最短寻道时间优先SSTF private void btnSCANhigh_Click(object sender, EventArgs e)从里向外扫描
private void btnSCANlow_Click(object sender, EventArgs e)从外向里扫描
private void btnCSCANhigh_Click(object sender, EventArgs e)从里向外循环扫描private void btnCSCANlow_Click(object sender, EventArgs e)从外向里循环扫描private void btnexit_Click(object sender, EventArgs e)退出窗体
private void txtnum_KeyDown(object sender, KeyEventArgs e)快捷键Tab选择输入框
6、关键算法实现流程图
先来先服务FCFS算法：
输入当前磁道
号
输入下一个被访问
的磁道号，各磁道
号之间用逗号隔开
磁道数组求出移动距离之和再除以访问的磁道个数
平均寻道
长度
按按钮输出
最短寻道时间算法：
输入当前磁道
号
输入下一个被访问的磁道号，各磁道号之间用逗号隔开
磁道数组从小到大排序
平均寻道长度
按按钮输出
磁道数组
当前磁道号与磁道
数组比较
数组的最后一个小于当前磁道号，则数组逆序输出，求移动距离之和
数组的第一个数大于当前磁道号，正序输出，求移动距离之和
当前磁道号处于数组最大数与最小数之间，选择离当前磁道号最近的输出，求移动距离之和
平均寻道长度
获取磁道数组
扫描算法：
向磁道号增加的方向：
输入当前磁道
号
输入下一个被访问的磁道号，各磁道号之间用逗号隔开
磁道数组从小到大排序
平均寻道长度
按按钮输出
磁道数组
当前磁道号与磁道
数组比较
数组的最后一个小于当前磁道号，则数组逆序输出，求移动距离之和
数组的第一个数大于当前磁道号，正序输出，求移动距离之和
当前磁道号处于数组最大数与最小数之间，按照增加的方向先输出比当前磁道号大的，接着向减小的方向访问，求移动距离之和
平均寻道长度
获取磁道数组
从磁道号减小的方向：
输入当前磁道
号
输入下一个被访问的磁道号，各磁道号之间用逗号隔开
磁道数组从小到大排序
平均寻道长度
按按钮输出
磁道数组
当前磁道号与磁道数组比较
数组的最后一个小于当前磁道号，则数组逆序输出，求移动距离之和
数组的第一个数大于当前磁道号，正序输出，求移动距离之和
当前磁道号处于数组最大数与最小数之间，按照减小的方向先输出比当前磁道号小的，接着向增加的方向访问，求移动距离之和
平均寻道长度
获取磁道数组
循环扫描算法：
从磁道号增加的方向：
输入当前磁道
号
输入下一个被访问的磁道号，各磁道号之间用逗号隔开
磁道数组从小到大排序
平均寻道长度
按按钮输出
磁道数组
当前磁道号与磁道
数组比较
数组的最后一个数小于当前磁道号或第一个数小于当前磁道号，则数组正序输出，求
移动距离之和
当前磁道号处于数组最大数与最小数之间，按照增加的方向先输出比当前磁道号大的，接着回到最里层，继续向增加的方向访问，求出移
动距离之和
获取磁道数组
从磁道号减小的方向：
输入当前磁道
号
输入下一个被访问的磁道号，各磁道号之间用逗号隔开
磁道数组从小到大排序
平均寻道长度
按按钮输出
磁道数组
当前磁道号与磁道
数组比较
数组的最后一个数小于当前磁道号或第一个数小于当前磁道号，则数组逆序输出，求
移动距离之和
当前磁道号处于数组最大数与最小数之间，按照减小的方向先输出比当前磁道号小的，接着回到最外层，继续向减小的方向访问，求出移
动距离之和
获取磁道数组
7、实现代码
///
///先来先服务FCFS
///
///
///
private void btnFCFS_Click(object sender, EventArgs e)
{
txtresult.Clear();//清除显示
int[] cidao = new int[1000];//被访问的磁道号数组
int sum = 0;//移动距离之和
double avg = 0;//平均寻道时间
string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号
int now = Convert.ToInt32(txtnow.Text);//当前的磁道号
for (int i = 0; i < str.Length; i++)
{
//将获取的磁道号存入磁道号数组
cidao[i] = Convert.ToInt32(str[i]);
}
sum += Math.Abs(now - cidao[0]);//当前的磁道号减去磁道号数组中的第一个值取绝对值
for (int i = 0; i < str.Length; i++)
{
//输出FCFS磁盘调度结果
txtresult.Text = txtresult.Text + cidao[i] + ','; }
for (int i = 0, j = 1; j < str.Length; i++, j++)
{
//累计总的移动距离
sum += Math.Abs(cidao[j] - cidao[i]);
}
avg = (double)sum / str.Length;//平均寻道长度
lblsum.Text = "总移动距离：" + sum.ToString();//在Label中显示总移动距离
lblavg.Text = "平均寻道长度：" + avg.ToString("0.00");//在Label中显示平均寻道时间
}
///
///最短寻道时间优先SSTF
///
///
///
private void btnSSTF_Click(object sender, EventArgs e)
{
txtresult.Clear();//清除显示
int[] cidao = new int[1000];//被访问的磁道号数组
int sum = 0;//移动距离之和
double avg = 0;//平均寻道时间
int temp;//中间变量
int k = 1;
int m, n;
string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号
int now = Convert.ToInt32(txtnow.Text);//当前的磁道号
for (int i = 0; i < str.Length; i++)
{
//将获取的磁道号存入磁道号数组
cidao[i] = Convert.ToInt32(str[i]);
}
//对磁道号进行从小到大排列
for (int i = 0; i < str.Length; i++)
{
for (int j = i + 1; j < str.Length; j++)
{
if (cidao[i] > cidao[j])
{
temp = cidao[i];
cidao[i] = cidao[j];
cidao[j] = temp;
}
}
}
//数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号
if (cidao[str.Length - 1] <= now)
{
for (int i = str.Length - 1; i >= 0; i--)
txtresult.Text = txtresult.Text + cidao[i] + ','; sum = now - cidao[0];//移动距离之和
}
//数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号
else if (cidao[0] >= now)
{
for (int i = 0; i < str.Length; i++)
txtresult.Text = txtresult.Text + cidao[i] + ','; sum = cidao[str.Length - 1] - now;//移动距离之和
}
//当前磁道号的大小介于数组的最大值与最小值之间
{
//k的初始值为，从数组的第二个数开始逐一与当前磁道号比较
while (cidao[k] < now)
{
k++;
}
//k+1比当前磁道号大的时候
m = k - 1;
n = k;
//确定当前磁道在已排的序列中的位置
while ((m >= 0) && (n < str.Length))
{
//当前位置的前一个磁道号离当前磁道号近
if ((now - cidao[m]) <= (cidao[n] - now))
{
txtresult.Text = txtresult.Text + cidao[m] + ',';//输出
sum += now - cidao[m];//移动距离之和
now = cidao[m];//当前磁道号改变
m = m - 1;//与数组的前半部分比较
}
//当前位置的后一个磁道号离当前磁道号近
else
{
txtresult.Text = txtresult.Text + cidao[n] + ','; ;//输出
sum += cidao[n] - now;//移动距离之和
now = cidao[n];//当前磁道号改变
n = n + 1;//与数组的后半部分比较
}
}
//数组的第一个数比当前磁道号大
if (m == -1)
{
for (int j = n; j < str.Length; j++)//输出
{
txtresult.Text = txtresult.Text + cidao[j] + ',';
}
//移动距离之和
sum += cidao[str.Length - 1] - cidao[0];
//数组的最后一个数比当前磁道号小
else
{
for (int j = m; j >= 0; j--)//输出
{
txtresult.Text = txtresult.Text + cidao[j] + ',';
}
sum += cidao[str.Length - 1] - cidao[0];//移动距离之和
}
}
avg = (double)sum / str.Length;//平均寻道长度
lblsum.Text = "总移动距离：" + sum.ToString();//在Label中显示总移动距离
lblavg.Text = "平均寻道长度：" + avg.ToString("0.00");//在Label中显示平均寻道时间
}
///
///磁道号增加的方向扫描
///
///
///
private void btnSCANhigh_Click(object sender, EventArgs e)
{
txtresult.Clear();//清除显示
int[] cidao = new int[1000];//被访问的磁道号数组
int sum = 0;//移动距离之和
double avg = 0;//平均寻道时间
int temp;//中间变量
int k = 1;
int m, n;
string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号
int now = Convert.ToInt32(txtnow.Text);//当前的磁道号
for (int i = 0; i < str.Length; i++)
{
//将获取的磁道号存入磁道号数组
cidao[i] = Convert.ToInt32(str[i]);
}
//对磁道号进行从小到大排列
for (int i = 0; i < str.Length; i++)
{
for (int j = i + 1; j < str.Length; j++)
{
if (cidao[i] > cidao[j])
{
temp = cidao[i];
cidao[i] = cidao[j];
cidao[j] = temp;
}
}
}
//数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号
if (cidao[str.Length - 1] <= now)
{
for (int i = str.Length - 1; i >= 0; i--)
txtresult.Text = txtresult.Text + cidao[i] + ',';
//移动距离之和
sum = now - cidao[0];
}
//数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号
else if (cidao[0] >= now)
{
for (int i = 0; i < str.Length; i++)
txtresult.Text = txtresult.Text + cidao[i] + ',';
sum = cidao[str.Length - 1] - now;//移动距离之和
}
//当前磁道号的大小介于数组的最大值与最小值之间
else
{
//k的初始值为，从数组的第二个数开始逐一与当前磁道号比较
while (cidao[k] < now)
{
k++;
}
//k+1比当前磁道号大的时候
m = k - 1;
n = k;
for (int j = n; j < str.Length; j++)//输出
{
txtresult.Text = txtresult.Text + cidao[j] + ','; }
//sum = cidao[str.Length - 1] - now;
for (int j = m; j >= 0; j--)
{
txtresult.Text = txtresult.Text + cidao[j] + ','; }
//sum = cidao[str.Length - 1] - cidao[0];
sum =2 * cidao[str.Length - 1] - now - cidao[0];
}
avg = (double)sum / str.Length;//平均寻道长度
lblsum.Text = "总移动距离：" + sum.ToString();//在Label中显示总移动距离
lblavg.Text = "平均寻道长度：" + avg.ToString("0.00");//在Label中显示平均寻道时间
}
///
///磁道号减小的方向扫描
///
///
///
private void btnSCANlow_Click(object sender, EventArgs e)
{
txtresult.Clear();//清除显示
int[] cidao = new int[1000];//被访问的磁道号数组
int sum = 0;//移动距离之和
double avg = 0;//平均寻道时间
int temp;//中间变量
int k = 1;
int m, n;
string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号
int now = Convert.ToInt32(txtnow.Text);//当前的磁道号
for (int i = 0; i < str.Length; i++)
{
//将获取的磁道号存入磁道号数组
cidao[i] = Convert.ToInt32(str[i]);
}
//对磁道号进行从小到大排列
for (int i = 0; i < str.Length; i++)
{
for (int j = i + 1; j < str.Length; j++)
{
if (cidao[i] > cidao[j])
{
temp = cidao[i];
cidao[i] = cidao[j];
cidao[j] = temp;
}
}
}
//数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号
if (cidao[str.Length - 1] <= now)
{
for (int i = str.Length - 1; i >= 0; i--)
txtresult.Text = txtresult.Text + cidao[i] + ','; sum = now - cidao[0];//移动距离之和
}
//数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号
else if (cidao[0] >= now)
{
for (int i = 0; i < str.Length; i++)
txtresult.Text = txtresult.Text + cidao[i] + ',';
sum = cidao[str.Length - 1] - now;//移动距离之和
}
//当前磁道号的大小介于数组的最大值与最小值之间
else
{
//k的初始值为，从数组的第二个数开始逐一与当前磁道号比较
while (cidao[k] < now)
{
k++;
}
//k+1比当前磁道号大的时候
m = k - 1;
n = k;
for (int j = m; j >= 0; j--)//比当前磁道号小的磁道数组的左边输出
{
txtresult.Text = txtresult.Text + cidao[j] + ','; }
//sum = now - cidao[0];
for (int j = n; j < str.Length; j++)//比当前磁道号大的磁道数组的右边输出
{
txtresult.Text = txtresult.Text + cidao[j] + ',';
}
//sum = cidao[str.Length - 1] - cidao[0];
sum = now - cidao[0] + cidao[str.Length - 1] - cidao[0]; }
avg = (double)sum / str.Length;//平均寻道长度
lblsum.Text = "总移动距离：" + sum.ToString();//在Label中显示总移动距离
lblavg.Text = "平均寻道长度：" + avg.ToString("0.00");//在Label中显示平均寻道时间
}
///
///磁道号增加的方向循环扫描
///
///
///
private void btnCSCANhigh_Click(object sender, EventArgs e) {
txtresult.Clear();//清除显示
int[] cidao = new int[1000];//被访问的磁道号数组
int sum = 0;//移动距离之和
double avg = 0;//平均寻道时间
int temp;//中间变量
int k = 1;
int m, n;
string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号
int now = Convert.ToInt32(txtnow.Text);//当前的磁道号
for (int i = 0; i < str.Length; i++)
{
//将获取的磁道号存入磁道号数组
cidao[i] = Convert.ToInt32(str[i]);
}
//对磁道号进行从小到大排列
for (int i = 0; i < str.Length; i++)
{
for (int j = i + 1; j < str.Length; j++)
{
if (cidao[i] > cidao[j])
{
temp = cidao[i];
cidao[i] = cidao[j];
cidao[j] = temp;
}
}
//数组的最后一个小于当前磁道号，则数组正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号
if (cidao[str.Length - 1] <= now)
{
for (int i = 0; i < str.Length; i++)
txtresult.Text = txtresult.Text + cidao[i] + ','; sum = now - cidao[0];//移动距离之和
}
//数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号
else if (cidao[0] >= now)
{
for (int i = 0; i < str.Length; i++)
txtresult.Text = txtresult.Text + cidao[i] + ',';
sum = cidao[str.Length - 1] - now;//移动距离之和
}
//当前磁道号的大小介于数组的最大值与最小值之间
else
{
//k的初始值为，从数组的第二个数开始逐一与当前磁道号比较
while (cidao[k] < now)
{
k++;
}
//k+1比当前磁道号大的时候
m = k - 1;
n = k;
for (int j = n; j < str.Length; j++)//输出
{
txtresult.Text = txtresult.Text + cidao[j] + ','; }
//sum = cidao[str.Length - 1] - now;cidao[str.Length - 1] - cidao[0] + cidao[n] - cidao[0];
for (int j = 0; j { txtresult.Text = txtresult.Text + cidao[j] + ','; } //sum = cidao[str.Length - 1] - cidao[0] + cidao[n-1] - cidao[0]; sum = cidao[n-1] + 2 * (cidao[str.Length - 1] - cidao[0]) - now; avg = (double)sum / str.Length;//平均寻道长度 lblsum.Text = "总移动距离：" + sum.ToString();//在Label中显示总移动距离 lblavg.Text = "平均寻道长度：" + avg.ToString("0.00");//在Label中显示平均寻道时间 } /// ///磁道号减小的方向循环扫描 /// /// /// private void btnCSCANlow_Click(object sender, EventArgs e) { txtresult.Clear();//清除显示 int[] cidao = new int[1000];//被访问的磁道号数组 int sum = 0;//移动距离之和 double avg = 0;//平均寻道时间 int temp;//中间变量 int k = 1; int m, n; string[] str = txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);//当前的磁道号 for (int i = 0; i < str.Length; i++) { //将获取的磁道号存入磁道号数组 cidao[i] = Convert.ToInt32(str[i]); } //对磁道号进行从小到大排列 for (int i = 0; i < str.Length; i++) { for (int j = i + 1; j < str.Length; j++) { if (cidao[i] > cidao[j]) { temp = cidao[i]; cidao[i] = cidao[j]; cidao[j] = temp; } } } //数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号 if (cidao[str.Length - 1] <= now) { for (int i = str.Length - 1; i >= 0; i--) txtresult.Text = txtresult.Text + cidao[i] + ','; sum = now - cidao[0];//移动距离之和 } //数组的第一个数大于当前磁道号，逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号 else if (cidao[0] >= now) { for (int i = str.Length - 1; i >= 0; i--) txtresult.Text = txtresult.Text + cidao[i] + ','; sum = cidao[str.Length - 1] - now;//移动距离之和 } //当前磁道号的大小介于数组的最大值与最小值之间 else { //k的初始值为，从数组的第二个数开始逐一与当前磁道号比较 while (cidao[k] < now) { k++; } //k+1比当前磁道号大的时候 m = k - 1; n = k; for (int j = m; j >= 0; j--)//输出 { txtresult.Text = txtresult.Text + cidao[j] + ','; } for (int j = str.Length-1; j >= n; j--) { txtresult.Text = txtresult.Text + cidao[j] + ','; } sum = now - cidao[n] + 2 * (cidao[str.Length - 1] - cidao[0]); } avg = (double)sum / str.Length;//平均寻道长度 lblsum.Text = "总移动距离：" + sum.ToString();//在Label中显示总移动距离 lblavg.Text = "平均寻道长度：" + avg.ToString("0.00");//在Label中显示平均寻道时间 } /// 操作系统实验六磁盘调度算法正确C代码 文档编制序号：[KKIDT-LLE0828-LLETD298-POI08] 《操作系统》实验报告 【实验题目】：磁盘调度算法 【实验目的】 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS，最短寻道时间优先SSTF，SCAN和循环SCAN算法的实现方法。【实验内容】 问题描述： 设计程序模拟先来先服务FCFS，最短寻道时间优先SSTF，SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 程序要求如下： 1）利用先来先服务FCFS，最短寻道时间优先SSTF，SCAN和循环SCAN算法模拟磁道访问过程。 2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。 3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。 4）输出：每种算法的平均寻道长度。 实验要求： 1) 上机前认真复习磁盘调度算法，熟悉FCFS，SSTF，SCAN和循环SCAN算法的过程； 2) 上机时独立编程、调试程序； 3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。 实验代码： #include 磁盘调度算法的模拟实现 学院 专业 学号 学生姓名 指导教师姓名 2014年3月19日 目录 一、课设简介 (2) 1.1 课程设计题目 (2) 1.2 课程设计目的 (2) 1.3 课程设计要求 (2) 二、设计内容 (3) 2.1功能实现 (3) 2.2流程图 (3) 2.3具体内容 (3) 三、测试数据 (4) 3.3 测试用例及运行结果 (4) 四、源代码 (5) 五、总结 (12) 5.1 总结............................................ 一、课设简介 1.1课程设计题目 磁盘调度算法的模拟实现1 1.2程序设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 1）进一步巩固和复习操作系统的基础知识。 2）培养学生结构化程序、模块化程序设计的方法和能力。 3）提高学生调试程序的技巧和软件设计的能力。 4）提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 1.3 设计要求 1）磁头初始磁道号，序列长度，磁道号序列等数据可从键盘输入，也可从文件读入。 2）最好能实现磁道号序列中磁道号的动态增加。 3）磁道访问序列以链表的形式存储 4）给出各磁盘调度算法的调度顺序和平均寻道长度 二、设计内容 2.1 功能实现 设计并实现一个本别利用下列磁盘调度算法进行磁盘调度的模拟 程序。 1） 先来先服务算法FCFS 2） 最短寻道时间优先算法 SSTF 2.2流程图 2.3具体内容 1)先来先服务算法FCFS 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘 的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请 求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情 况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情开始 选择算法 F C F S S S T F 结束 操作系统实验报告实验3 磁盘调度算法 报告日期：2016-6-17 姓名： 学号： 班级： 任课教师： 实验3 磁盘调度算法 一、实验内容 模拟电梯调度算法，实现对磁盘的驱动调度。 二、实验目的 磁盘是一种高速、大量旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，负担着繁重的输入输出任务，在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请示等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求，这就叫驱动调度，使用的算法称驱动调度算法。驱动调度能降低为若干个输入输出请求服务所须的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。 三、实验原理 模拟电梯调度算法，对磁盘调度。 磁盘是要供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求处于等待状态，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。当存取臂仅需移到一个方向最远的所请求的柱面后,如果没有访问请求了,存取臂就改变方向。 假设磁盘有200个磁道，用C语言随机函数随机生成一个磁道请求序列（不少于15个）放入模拟的磁盘请求队列中，假定当前磁头在100号磁道上，并向磁道号增加的方向上移动。请给出按电梯调度算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度。 四、实验过程 1.画出算法流程图。 2．源代码 #include 操作系统 实验报告 哈尔滨工程大学 计算机科学与技术学院 第六讲磁盘调度算法 一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的 （1）通过学习EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机； （2）观察 EOS 实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法； （3）编写 CSCAN和 N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。 3. 实验类型 验证性+设计性实验 4. 实验内容 （1）验证先来先服务（FCFS）磁盘调度算法； （2）验证最短寻道时间优先（SSTF）磁盘调度算法； （3）验证SSTF算法造成的线程“饥饿”现象； （4）验证扫描（SCAN）磁盘调度算法； （5）改写SCAN算法。 二、实验环境 在OS Lab实验环境的基础上，利用EOS操作系统，由汇编语言及C语言编写代码，对需要的项目进行生成、调试、查看和修改，并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。 三、实验过程 1. 设计思路和流程图 （1）改写SCAN算法 在已有 SCAN 算法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求，就可以选中下一个要处理的请求。算法流程图如下图所示。 图 3.1.1 SCAN算法IopDiskSchedule函数流程图（2）编写循环扫描（CSCAN）磁盘调度算法 在已经完成的SCAN算法源代码的基础上进行改写，不再使用全局变量ScanInside 确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。算法流程图如下图所示。 《操作系统原理及应用》课程设计报告 磁盘调度算法 学院（系）：计算机科学与工程学院 班级：37-5 学号 学生姓名： 时间：从2013 年12 月16日到2013 年12月20日 1、课程设计的目的 本课程设计是学生学习完《操作系统原理及应用》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 2、课程设计的内容及要求 编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3、实现原理 磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先、扫描和循环扫描等算法。 其中，平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N 其中Mi为磁头从上一各磁道到这个磁道所需移动的距离。 4、算法 1.先来先服务算法（FCFS） 这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法只考虑访问者提出访问请求的先后次序，按照先后次序依次访问磁道号。移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。 2.短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，而不管访问者到来的先后次序。实现时可以先对磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，选择离自己最近的访问，每比较一次，当前磁道号也跟着变化，移动距离等于上一个被访问的 磁盘调度算法 学生姓名: 学生学号: 专业班级: 指导老师： 2013年6月20日 1、实验目的： 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。 2、问题描述： 设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 3、需求分析 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。 通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方向及访问方式得到访问序列及移动距离和平均移动距离！ (1)输入的形式； int TrackOrder[MaxNumber];//被访问的磁道号序列 int direction;//寻道方向 int Num;//访问的磁道号数目 int start;// (2)输出的形式； int MoveDistance[MaxNumber]={0};//移动距离 double AverageDistance=0;//平均寻道长度 移动的序列！ (3)程序所能达到的功能； 模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 (4)测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。 开始磁道号：100 磁道号方向：内（0）和外（1） 磁道号数目：9 页面序列：55 58 39 18 90 160 150 38 184 4、概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 操作系统磁盘调度算法实 验报告 Last revision on 21 December 2020 目录 1．课程设计目的 编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。 2．课程设计内容 设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 1、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进 程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 2、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 3、扫描算法（SCAN） 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到 题目4 磁盘调度算法的实现 4.1 题目的主要研究内容及预期达到的目标 （1）设计磁盘调度请求队列（请求数≥10） （2）设定单位寻道时间； （3）可动态修改磁盘请求时间和磁道； （4）分别实现四种磁盘调度算法； A、先来先服务算法（FCFS）。 B、最短寻道时间优先算法（SSTF）。 C、扫描算法（SCAN）。 D、循环扫描算法（CSCAN）。 （5）实现动态调度并输出调度序列。 （6）理解磁盘调度相关理论； （7）掌握多种磁盘调度算法。 4.2 题目研究的工作基础或实验条件 （1）硬件环境：装有Linux操作系统（虚拟机）的计算机一台。 （2）软件环境：vim编辑器、Visual C++。 4.3 设计思 （1）磁盘调度 磁盘可供多个进程共享，当有多个进程要求访问磁盘时，应采用一种调度算法，以使各进程对磁盘的平均访问时间最小，由于在访问磁盘的时间中，主要是寻道时间，因此磁盘调度的目标就是使磁盘的平均寻道时间最短。 （2）系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 A、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平 均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。因为每个请求都会按照到达先后顺序得到处理，不会出现某个进程的请求长期得不到处理的情况，算法具有一定的公平性。 B、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。此算法会导致与当前磁道距离较远的访问请求长期等待得不到服务，发生进程“饥饿”现象。 C、扫描算法（SCAN） 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。此算法与自然界中电梯的工作方式极为相像，故也称“电梯调度”算法。 D、循环扫描算法（CSCAN） 循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。 模拟磁盘调度算法操作系 统课程设计 Final approval draft on November 22, 2020 某某大学 课程设计报告课程名称：操作系统 设计题目：模拟磁盘调度算法 系别：计算机系 专业：计算机科学与技术 组别： 学生姓名: 学号: 起止日期: 指导教师: 目录 第一章需求分析 课程设计的简介 这是一个用VC++为工具、C++为编程语言而实现模拟先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）的一个磁盘调度程序。该程序设计系统主界面可以灵活选择某种算法并算出磁头移动的总磁道数以及平均磁道数。 课程设计的目的 本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）等磁盘调度算法的理解。 磁盘调度主要思想 设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。 平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即： L=（M1+M2+……+Mi+……+MN）/N。其中Mi为所需访问的磁道号所需移动的磁道数。 启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有： 寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。 延迟时间——指定扇区旋转到磁头下所需的时间。 传送时间——由磁头进程读写完成信息传送的时间。 实用标准文案 操作系统 实验报告 哈尔滨工程大学计算机科学与技术学院 一、实验概述 1. 实验名称磁盘调度算法 2. 实验目的 (1)通过学习EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机。 (2)观察EOS实现的FCFS、SSTF和SCAN磁盘调度算法，了解常用的磁盘调度算法。 ( 3)编写CSCAN 和N-Step-SCAN 磁盘调度算法，加深对各种扫描算法的理解。 3. 实验类型验证，设计 4. 实验内容 ( 1)准备实验 (2)验证先来先服务(FCFS)磁盘调度算法 (3)验证最短寻道时间优先(SSTF)磁盘调度算法 (4)验证SSTF 算法造成的线程“饥饿”现象 (5.1)验证扫描(SCAN)磁盘调度算法 (5.2)验证SCAN 算法能够解决“饥饿”现象 ( 6 ) 改写SCAN 调度算法 二、实验环境 EOS 操作系统与IDE 环境组成的“操作系统集成实验环境OS Lab ”。 三、实验过程 （一）实验问题及解答 1. 实验指导P176-3.2验证先来先服务（FCFS）磁盘调度算法，要求请给出在“输出”窗口中的结果。 答：输出结果复制如下： 制作软盘镜像... 正在启动Virtual PC... 开始调试... ****** Disk schedule start working ****** Start Cylinder: 10 TID: 31 Cylinder: 8 Offset: 2 - TID: 32 Cylinder: 21 Offset: 13 + TID: 33 Cylinder: 9 Offset: 12 - TID: 34 Cylinder: 78 Offset: 69 + TID: 35 Cylinder: 0 Offset: 78 - TID: 36 Cylinder: 41 Offset: 41 + TID: 37 Cylinder: 10 Offset: 31 - 1.主界面 void display(){ cout<<"\n\n\n\n Operating Systems Curriculum Design\n"; cout<<"\n ╔———————————————————————————————╗"; cout<<"\n ││"; cout<<"\n │名称: 磁盘调度│"; cout<<"\n ││"; cout<<"\n │工具: Visual Studio 2010 │"; cout<<"\n ││"; cout<<"\n │班级:1205 │"; cout<<"\n ││"; cout<<"\n │作者:xxxx │"; cout<<"\n ││"; cout<<"\n │学号：1324256688 │"; cout<<"\n ││"; cout<<"\n ╚———————————————————————————————╝\n"; system("pause"); system("cls"); 2.前言提示用户此程序实现的算法 cout<<"【载入完成】"< 《操作系统》实验报告 【实验题目】：磁盘调度算法 【实验目的】 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS，最短寻道时间优先SSTF，SCAN和循环SCAN算法的实现方法。 【实验内容】 问题描述： 设计程序模拟先来先服务FCFS，最短寻道时间优先SSTF，SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 程序要求如下： 1）利用先来先服务FCFS，最短寻道时间优先SSTF，SCAN和循环SCAN 算法模拟磁道访问过程。 2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。 3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。 4）输出：每种算法的平均寻道长度。 实验要求： 1) 上机前认真复习磁盘调度算法，熟悉FCFS，SSTF，SCAN和循环SCAN 算法的过程； 2) 上机时独立编程、调试程序； 3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。 实验代码： #include 磁盘调度算法 学生: 学生学号: 专业班级: 指导老师： 2013年6月20日 1、实验目的： 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。 2、问题描述： 设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 3、需求分析 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。 通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方向及访问方式得到访问序列及移动距离和平均移动距离！ (1)输入的形式； int TrackOrder[MaxNumber];//被访问的磁道号序列 int direction;//寻道方向 int Num;//访问的磁道号数目 int start;// (2)输出的形式； int MoveDistance[MaxNumber]={0};//移动距离 double AverageDistance=0;//平均寻道长度 移动的序列！ (3)程序所能达到的功能； 模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 (4)测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。 开始磁道号：100 磁道号方向：（0）和外（1） 磁道号数目：9 页面序列：55 58 39 18 90 160 150 38 184 4、概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 操作系统课程设计任务书 题目：磁盘调度算法 院系： 专业： 班级： 姓名： 学号： 指导教师： 设计时间： 2018.1.1-2018.1.5 指导教师评语 目录 1、需求分析 (4) 1.1课题描述 (4) 1.2课题目的 (4) 1.3理论依据 (7) 2、概要设计 (8) 2.1设计方法 (8) 2.2技术 (8) 2.3运行环境 (8) 3、详细设计 (9) 3.1流程图 (11) 3.2程序主要代码 (13) 4、运行结果及分析 (14) 4.1运行结果 (15) 4.2结果详细分析 (16) 5、总结和心得 (16) 6、参考文献 (17) 7、附录：程序源代码 (23) 1、需求分析 1.1课题描述 这次课程设计我研究的题目是：磁盘调度算法。具体包括三种算法分别是：先来先服务算法（FCFS）、最短寻道时间优先算法(SSTF)、扫描算法（电梯调度算法）(SCAN)。 1.2课题目的 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS，最短寻道时间优先SSTF，扫描SCAN算法的实现方法。 1.3理论依据 设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。 平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN） 计算机操作系统课程设计 设计说明书 （题目） 磁盘调度算法的实现与分析 起止日期：2013 年12 月25 日至2013年12 月31 日 学生姓名 班级 学号 成绩 指导教师(签字) 计算机与通信学院 2013年12 月31 日 目录 1 课程设计简介 (3) 1.1 课程设计的目的 (3) 1.2 课程设计内容 (3) 2 数据结构的设计 (4) 2.1 变量和数组的定义 (4) 2.2函数的定义 (4) 3 功能模块（或算法）描述 (4) 3.1模块划分 (4) 3.2 模块调用关系图 (8) 4 程序运行结果..................................... 错误！未定义书签。 5 心得体会 (12) 参考文献 (13) 附源代码 (13) 1 课程设计简介 1.1 课程设计的目的 本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。 1.2 课程设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 1、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 2、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 3、扫描算法（SCAN） 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即 磁盘调度算法实验报告文档 1.依次输入9个磁道数：40 90 170 38 110 20 144 48 59 2.选择调度算法： 先来先服务算法访问顺序和平均寻道长度： 最短寻道时间优先的访问顺序和平均寻道长度： 扫描算法的磁道访问顺序和平均寻道长度：1．移动壁由里向外 2．移动壁由外向里 循环算法的磁道访问顺序和平均寻道长度：1.移动壁由里向外 2.移动壁由外向里 源代码为： #include { int i,j,s,sum=0,p; int a[20]; for(i=0;i 实验四磁盘调度 一、实验目的： 本实验要求学生模拟设计一个磁盘调度程序，观察调度程序的动态运行过程。通过实验让学生理解和掌握磁盘调度的职能。 二、实验内容： 对磁盘进行移臂操作，模拟磁盘调度算法并计算平均寻道时间 三、实验准备： 1.相关理论知识： （1）假设磁盘只有一个盘面，并且磁盘是可移动头磁盘。 （3）磁盘是高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出工作，在现代计算机系统中往往同时会有若干个要求访问磁盘的输入输出要求。系统可采用一种策略，尽可能按最佳次序执行访问磁盘的请求。由于磁盘访问时间主要受寻道时间T的影响，为此需要采用合适的寻道算法，以降低寻道时间。 （2）磁盘是可供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其它想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求而处于等待状态时，可用磁盘调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。 2.测试数据： 磁盘读写请求队列：20，44，40，4，80，12，76 当前磁头位置：50 试问采用FCFS、SSTF、SCAN磁盘调度算法时寻道顺序及平均寻道时间分别为多少？ 四、实验过程： 1.流程图 SCAN算法（扫描算法）流程图： 2. 源代码 #include 磁盘调度算法 操作系统课程设计任务书 学院专业 课程名称题目磁盘调度 完成期限自2014年6月9日至2014年6月22日共2周 一、项目的目的 通过设计一个磁盘调度模拟系统～从而使磁盘调度算法更加形 象化～容易使人理解～使磁盘调度的特点更简单明了～能使使用者 加深对扫描算法以及循环扫描算法等磁盘调度算法的理解。 二、项目任务的主要内容和要求 根据磁盘调度算法的思想～编程实现扫描算法、循环扫描算法～ 并通过数据分析比较各种算法的平均寻道长度。 内 三、项目设计,研究,思路 容 1.扫描算法,SCAN,:将磁道号用冒泡法从小到大排序～输出及 排好序的序列～输入当前磁道号～选择移动臂的移动方向～根据当任前磁道在已排的序列中的位臵～选择扫描的顺序～求出平均寻道长务度～输出移动的平均磁道数。 2.循环扫描算法,CSCAN,:将磁道号用冒泡法从小到大排序～ 输出排好序的序列～输入当前磁道号～规定移动臂单向反复的从内 向外移动～根据当前磁道在已排的序列中的位臵～选择扫描的顺序～ 求出平均寻道长度～输出移动的平均磁道数。 四、具体成果形式和要求 设计一个磁盘调度的程序～按用户不同的选择～用不同的算法 进行不同的模拟。 进起止日期工作内容 度 理解磁盘调度的原理背景、查询相关安 资料设计规划设计总体思路排 编写代码实现各部分的功能 进行测试代码以及对代码进行调试、 修改。最后编写文档 主 [1]汤小丹, 梁红兵.计算机操作系统[M].西安:西安电子科技大学出要版社～2007 参 [2]何钦铭, 颜晖.C语言程序设计[M].北京:高等教育出版社～2008 考 [3]严蔚敏, 吴伟民. 数据结构,C语言版,[M].北京:清华大学出 资版社～2011 料 指导教师 意见 ,签字,: 年月日 系,教研 室,主任意 见 ,签字,: 年月日 磁盘调度课程设计说明书 1.实验题目: 磁盘调度算法。 建立相应的数据结构； 在屏幕上显示磁盘请求的服务状况； 将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支持算法：FIFO、SSTF、SCAN、CSCAN; 2.设计目的: 调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。 3.任务及要求 3.1设计任务 编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度： 1、先来先服务算法（FCFS） 2、最短寻道时间算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3.2设计要求 对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。 4.算法及数据结构 4.1算法的总体思想 queue[n] 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道①先来先服务算法（FCFS） 按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。 ②最短寻道时间优先算法（SSTF） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。 ③扫描算法（SCAN） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁 道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 ④循环扫描算法（CSCAN） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 5、源代码： #include操作系统实验六磁盘调度算法正确C代码
磁盘调度算法的模拟实现
操作系统实验报告—磁盘调度算法
操作系统实验 磁盘调度算法
磁盘调度算法文档
磁盘调度算法实验报告 (2)(推荐文档)
操作系统磁盘调度算法实验报告
磁盘调度算法的实现
模拟磁盘调度算法操作系统课程设计
(第五讲磁盘调度算法)
操作系统磁盘调度算法源代码
操作系统实验六磁盘调度算法正确C代码
磁盘调度算法实验报告材料 (2)
操作系统磁盘调度算法
(完整word版)磁盘调度算法的实现与分析
磁盘调度算法实验报告
操作系统实验四-磁盘调度算法
磁盘调度算法
操作系统课程设计-磁盘调度算法
相关主题
文本预览