操作系统实验报告四
[实验题目]
磁盘调度算法SSTF、SCAN、C-SCAN
[实验目的]
通过设计一个磁盘调度模拟系统,从而使磁盘调度算法更加形象化,容易理解,使磁盘调度的特点更简单明了,能使使用者加深对最短寻道时间优先算法、扫描算法以及循环扫描算法的理解。
[实验内容]
编程实现如下内容:
1. 最短寻道时间优先算法(SSTF);
2. 扫描算法(SCAN)(又叫电梯调度算法);
3. 循环扫描算法(CSCAN)
代码如下:
#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
const int MaxNumber=100;
int TrackOrder[MaxNumber];
int MoveDistance[MaxNumber]; //----移动距离;
int FindOrder[MaxNumber]; //-----寻好序列。
double AverageDistance; //-----平均寻道长度
bool direction; //-----方向 true时为向外,false为向里
int BeginNum; //----开始磁道号。
int M; //----磁道数。
int N; //-----提出磁盘I/O申请的进程数
int SortOrder[MaxNumber]; //----排序后的序列
bool Finished[MaxNumber];
void Inith()
{
cout<<"请输入磁道数:";
cin>>M;
cout<<"请输入提出磁盘I/O申请的进程数:";
cin>>N;
cout<<"请依次输入要访问的磁道号:";
for(int i=0;i<N;i++)
cin>>TrackOrder[i];
for(int j=0;j<N;j++)
MoveDistance[j]=0;
cout<<"请输入开始磁道号:";
cin>>BeginNum;
for(int k=0;k<N;k++)
Finished[k]=false;
for(int l=0;l<N;l++)
SortOrder[l]=TrackOrder[l];
}
//=====================排序函数,将各进程申请的磁道按从小到大排列=================
void Sort()
{ //------冒泡排序
int temp;
for(int i=N-1;i>=0;i--)
for(int j=0;j<i;j++)
{
if(SortOrder[j]>SortOrder[j+1])
{
temp=SortOrder[j];
SortOrder[j]=SortOrder[j+1];
SortOrder[j+1]=temp;
}
}
}
//========SSTF,最短寻道法=============================
void SSTF()
{
int temp,n;
int A=M;
temp=BeginNum; //--------将BeginNum赋给temp作为寻道时的当前所在磁道号
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++) //-------寻找最短的寻道长度
{
if(abs(TrackOrder[j]-temp)<A&&Finished[j]==false)
{
A=abs(TrackOrder[j]-temp);
n=j;
}
else continue;
}
Finished[n]=true; //-------将已经寻找到的Finished赋值为true
MoveDistance[i]=A; //-------寻道长度
temp=TrackOrder[n]; //-------当前寻道号。
A=M; //-----重置A值
FindOrder[i]=TrackOrder[n]; //----寻好的赋给寻好序列
}
}
//=====================SCAN,扫描算法==========================
void SCAN()
{
int m,n,temp;
temp=BeginNum;
Sort(); //------排序
cout<<"请选择开始方向:1--向外;0---向里"; //------选择扫描方向
cin>>m;
if(m==1)
direction=true;
else if(m==0)
direction=false;
else
cout<<"输入错误";
for(int i=0;i<N;i++)
{
if(SortOrder[i]<BeginNum)
continue;
else
{
n=i;
break;
}
}
if(direction==true) //------选择向外
{
for(int i=n;i<N;i++)
{
MoveDistance[i-n]=abs(SortOrder[i]-temp);
temp=SortOrder[i];
FindOrder[i-n]=SortOrder[i];
}
for(int j=n-1;j>=0;j--)
{
MoveDistance[N-1-j]=abs(SortOrder[j]-temp);
temp=SortOrder[j];
FindOrder[N-1-j]=SortOrder[j];
}
}
else //-------选择向里
{
for(int i=n-1;i>=0;i--)
{
MoveDistance[N-i-4]=abs(SortOrder[i]-temp);
temp=SortOrder[i];
FindOrder[N-i-4]=SortOrder[i];
}
for(int j=n;j<N;j++)
{
MoveDistance[j]=abs(SortOrder[j]-temp);
temp=TrackOrder[j];
FindOrder[j]=SortOrder[j];
}
}
}
//=================CSCAN,循环扫描算法=======================
void CSCAN()
{
int m,n,temp;
temp=BeginNum;
Sort();
cout<<"请选择开始方向:1--向外;0---向里";
cin>>m;
if(m==1)
direction=true;
else if(m==0)
direction=false;
else
cout<<"输入错误";
for(int i=0;i<N;i++)
{
if(SortOrder[i]<BeginNum)
continue;
else
{
n=i;
break;
}
}
if(direction==true)
{
for(int i=n;i<N;i++)
{
MoveDistance[i-n]=abs(SortOrder[i]-temp);
temp=SortOrder[i];
FindOrder[i-n]=SortOrder[i];
}
for(int j=0;j<n;j++)
{
MoveDistance[N-n+j]=abs(SortOrder[j]-temp);
temp=SortOrder[j];
FindOrder[N-n+j]=SortOrder[j];
}
}
else
{
for(int i=n-1;i>=0;i--)
{
MoveDistance[n-1-i]=abs(SortOrder[i]-temp);
temp=SortOrder[i];
FindOrder[n-1-i]=SortOrder[i];
}
for(int j=N-1;j>=n;j--)
{
MoveDistance[N-j+n-1]=abs(SortOrder[j]-temp);
temp=SortOrder[j];
FindOrder[N-j+n-1]=SortOrder[j];
}
}
}
//========计算平均寻道时间==============
void Count()
{
int Total=0;
for(int i=0;i<N;i++)
{
Total+=MoveDistance[i];
}
AverageDistance=((double)Total)/((double)N);
}
void Show()
{
cout<<"================从"<<BeginNum<<"号磁道开始====================="<<endl;
cout<<setw(20)<<"被访问的下一个磁道号"<<setw(20)<<"移动距离(磁道数)"<<endl;
for(int i=0;i<N;i++)
{
cout<<setw(15)<<FindOrder[i]<<setw(15)<<MoveDistance[i]<<endl;
}
cout<<setw(20)<<"平均寻道长度:"<<AverageDistance<<endl;
cout<<endl;
}
int main()
{
int y=1;
int s;
Inith();
while(y)
{
cout<<"请选择寻道方式: 1--SSTF; 2--SCAN;3--CSCSN;";
cin>>s;
switch(s)
{
case 1:SSTF();Count();Show();break;
case 2:SCAN();Count();Show();break;
case 3:CSCAN();Count();Show();break;
}
cout<<"是否继续选择寻道算法?1--是;2--否";
int p;
cin>>p;
y=p;
}
return 0;
}
[实验结果]
[心得体会]
通过模拟常见的几种磁盘寻道算法,通过计算平均寻道的长度,我们可以很直观的了解到不同寻道算法的效率,以加深对最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解。而且通过实验操作让我加深了对理论知识掌握。
第二篇:操作系统磁盘调度算法及模拟实验三
江西理工大学软件学院
《计算机操作系统》实验报告
实验名称: 磁盘调度算法及模拟
姓 名:
专 业: 软件开发
学 号:
指导教师:
实验日期: 2012-11-20
江西理工大学软件学院 《计算机网络基础》 实验报告
【实验目的、要求】
(1)设计一个磁盘调度模拟程序,从而使磁盘调度算法更加形象化,容易使人理解,使磁盘调度的特点更简单明了;
(2)加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解;
(3)针对给定的磁盘访问序列,运行各种调度算法得出调度过程
(4)算法所需的各种参数由输入产生(手工输入或者随机数产生) 输出调度过程。
【实验环境】
WindowsXP操作系统平台及C++软件
【实验步骤】
#include<iostream>
#include<cmath>
#include <ctime>
using namespace std;
/*1、FCFS算法*/
void FCFS(int *data,int n,int *order){
}
2 for(int i=0;i<=n;i++){ } order[i]=data[i];
江西理工大学软件学院 《计算机网络基础》 实验报告 /*2、SSTF算法*/
void SSTF(int *data,int n,int *order) {
for(int i=0;i<=n;i++) {
} order[i]=data[i];
for(int j=1;j<=n;j++){
int p=j;
for(int k=j+1;k<=n;k++){
} if(abs(order[k]-order[j-1])<abs(order[p]-order[j-1])) { } p=k;
if(p!=j) {
}
//均向磁道增加方向访问
/*3、SCAN算法*/
void SCAN(int *data,int n,int *order) {
int j=1; int q=n; order[0]=data[0];
for(int i=1;i<=n;i++){
if(data[i]>order[0]) {order[j]=data[i];j++;}
3 } int temp=order[j]; order[j]=order[p]; order[p]=temp; }
江西理工大学软件学院 《计算机网络基础》 实验报告 else{order[q]=data[i];q--;}
}
for(int z=1;z<j;z++) {
int p=z;
for(int k=z+1;k<j;k++){if(order[k]<order[p]) { p=k;} }
if(p!=z){ int temp=order[z]; order[z]=order[p]; order[p]=temp; } }
for(int h=j;h<=n;h++) {
int p=h;
for(int k=h+1;k<=n;k++) { if(order[k]>order[p]) { p=k;} }
if(p!=h) { int temp=order[h]; order[h]=order[p]; order[p]=temp; } }
}
//均向磁道增加方向访问
/*4、CSCAN算法*/
void CSCAN(int *data,int n,int *order) {
int j=1; int q=n; order[0]=data[0];
for(int i=1;i<=n;i++) {
if(data[i]>order[0]) {order[j]=data[i];j++;}
else {order[q]=data[i];q--;}
}
for(int z=1;z<j;z++) {
4
江西理工大学软件学院 《计算机网络基础》 实验报告 int p=z;
for(int k=z+1;k<j;k++) { if(order[k]<order[p]) { p=k;} }
if(p!=z) { int temp=order[z]; order[z]=order[p]; order[p]=temp; } }
for(int h=j;h<=n;h++) {
int p=h;
for(int k=h+1;k<=n;k++) { if(order[k]<order[p]) { p=k;} }
if(p!=h) { int temp=order[h]; order[h]=order[p]; order[p]=temp; } }
}/*5、主函数*/
void main()
{
int data[100]; data[0]=100; int n=0;//要寻访磁道个数
srand((int)time(0)); n=rand()%20+5;
for(int i=1;i<=n;i++) {data[i]=rand()%200+1;}
int order[100]; int length=0;
FCFS(data,n,order); cout<<"FCFS"<<endl;
for(int j=1;j<=n;j++)
{ length+=abs(order[j]-order[j-1]); cout<<order[j]<<" "; } cout<<endl; cout<<"平均寻道长度"<<length*1.0/n<<endl;
SSTF(data,n,order); cout<<"SSTF"<<endl; length=0;
for(int g=1;g<=n;g++)
5
江西理工大学软件学院 《计算机网络基础》
{ length+=abs(order[g]-order[g-1]); cout<<order[g]<<" cout<<endl;
cout<<"平均寻道长度"<<length*1.0/n<<endl;
SCAN(data,n,order); cout<<"SCAN"<<endl; length=0; for(int d=1;d<=n;d++)
{ length+=abs(order[d]-order[d-1]); cout<<order[d]<<" cout<<endl;
cout<<"平均寻道长度"<<length*1.0/n<<endl;
CSCAN(data,n,order); cout<<"CSCAN"<<endl; length=0; for(int k=1;k<=n;k++)
{ length+=abs(order[k]-order[k-1]); cout<<order[k]<<" cout<<endl;
cout<<"平均寻道长度"<<length*1.0/n<<endl;
}
6 实验报告 "; } "; } "; }
江西理工大学软件学院 《计算机网络基础》 实验报告
【实验总结】
先来先服务算法(FCFS)这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。
最短寻道时间优先算法(SSTF)该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却不能保证平均寻道时间最短。
扫描算法(SCAN)扫描算法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。例如,当磁头正在自里向外移动时,扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样自里向外地访问,直到再无更外的磁道需要访问才将磁臂换向,自外向里移动。
循环扫描算法(CSCAN)是对扫描算法的改进。如果对磁道的访问请求是均匀分布的,当磁头到达磁盘的一端,并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理,而磁盘另一端的请求密度相当高,且这些访问请求等待的时间较长,为了解决这种情况,循环扫描算法规定磁头单向移动。
7