天津理工大学-操作系统实验3：磁盘调度算法的实现.doc

实验报告
学院(系)名称:计算机与通信工程学院
姓名
王远志
学号

专业
计算机科学与技术
班级
2013级３班
实验项目
实验二:磁盘调度算法得实现
课程名称
操作系统
课程代码

实验时间
2０1５ 年12月 1１ 日 第5-８节
实验地点
软件实验室7-2１9
批改意见
成绩

教师签字：　　 　　　
实验内容:
1． 本实验就是模拟操作系统得磁盘寻道方式，运用磁盘访问顺序得不同来设计磁盘得调度算法。
2． 实现得磁盘调度算法有FＣFS,SSTF，SCAＮ,CＳCAN与 NＳｔepSCAN算法。
3． 设定开始磁道号寻道范围,依据起始扫描磁道号与最大磁道号数，随机产生要进行寻道得磁道号序列。
4． 选择磁盘调度算法,显示该算法得磁道访问顺序，计算出移动得磁道总数与平均寻道总数。
5． 按算法得寻道效率进行排序,并对各算法得性能进行分析比较。
实验要求:
1.详细描述实验设计思想、程序结构及各模块设计思路;
2． 详细描述程序所用数据结构及算法;
3． 明确给出测试用例与实验结果；
4． 为增加程序可读性，在程序中进行适当注释说明;
5． 认真进行实验总结,包括:设计中遇到得问题、解决方法与收获等;
6． 实验报告撰写要求结构清晰、描述准确逻辑性强；
7． 实验过程中,同学之间可以进行讨论互相提高,但绝对禁止抄袭。
【实验过程记录(源程序、测试用例、测试结果及心得体会等）】
#include<iｏsｔrｅaｍ＞
#inｃｌude<iomａｎip＞
＃incluｄe<maｔh、h＞
using ｎamespａｃe stｄ;
conｓt int ＭaxＮumber=100;
iｎｔ　 TrackＯrdeｒ[MａxNumber]；
ｉｎｔ　 MovｅＤｉsｔanｃe[MaxNuｍｂer]；　 //－---移动距离;
int 　FindOrｄeｒ［MaxNumber］; 　 　//－----寻好序列。
ｄoｕblｅ 　ＡveｒageDiｓｔaｎｃe; 　 　 /／－---－平均寻道长度
bｏol dｉrectiｏn; 　　 　　 　 　//－-－－-方向 true时为向外,faｌｓe为向里
int　ＢeginＮｕm;　 　 　/／----开始磁道号。
ｉnｔ M; 　 　 　　 //－－－-磁道数。
ｉｎt N;　 　　 　 　　　 　 //--－--提出磁盘I/Ｏ申请得进程数
inｔ SortOrdｅr［MaxNumｂｅｒ］;　 ／/--－-排序后得序列
bool Finished[MaｘＮuｍber];
void Ｉnith(）
{
couｔ<<"请输入磁道数:";
cin＞>M;
cout<＜＂请输入提出磁盘I/O申请得进程数:＂;
ｃiｎ>＞N;
ﻩcout<＜＂请依次输入要访问得磁道号:＂;
foｒ(int i=０;i<N;i＋+)
cin>>TrackOrdeｒ[i]；
ﻩfｏｒ(ｉnt　ｊ=0；ｊ＜N;j++）
ﻩ MoveDistancｅ[j]=0;
ﻩﻩｃout<＜"请输入开始磁道号:";
ﻩ ｃｉn＞>BegiｎNum;
ﻩｆor(ｉｎt ｋ=０;k＜N;ｋ++)
ﻩ Finｉｓｈｅd［k]=fａlse；
for（iｎt　l=0;l＜Ｎ;l＋+)
ﻩSortOrdeｒ[ｌ]=TracｋOrｄer[l］;
｝
/／===＝===＝＝＝=====＝=====排序函数,将各进程申请得磁道按从小到大排列====＝===＝＝=＝=====
vｏｉd Sort(）
｛ 　　 　　 //--－--－冒泡排序
ﻩ 　 ｉnｔ tｅmp;
　　　 　for(iｎｔ ｉ=N-1;i>=0;i－－）
ﻩﻩfoｒ（ｉnt ｊ＝0；j<ｉ;j＋+)
ﻩ{
ﻩ ﻩｉf(SortOrder[j]＞SortOrder[j+1])
ﻩﻩ {
ﻩﻩ　　 tｅｍp=ＳortOrdｅr[j];
ﻩ 　 SｏrｔOrdeｒ［j]＝SortOｒder[j＋1］；
ﻩﻩﻩﻩ　 SｏrtＯrdeｒ［j+1]=tｅmp;
ﻩ ﻩ}
ﻩ }
}
//===＝＝＝=＝====FCFS,先来先服务=＝=＝===============＝==========＝==
vｏiｄ FCFS(）
{
ﻩint　ｔemp；
ｔeｍp=BegｉｎNum; 　 　　 　 //-－---－－－将ＢeginNum赋给teｍｐ作为寻道时得当前所在磁道号
for（iｎｔ ｉ=0;i<N;i＋+)
｛
MoveＤistanｃe[ｉ］=aｂｓ(ＴrackＯrder[i]-tｅmp)； 　//-------计算移动磁道数
ﻩ teｍp＝TｒaｃｋOrder[i]; 　 　　 　　 　　 　 　 ／/-－－--－-寻到后，将此道作为当前所在磁道号,赋给temp
FindOrｄer[ｉ]＝TrackOrder［i];　 　　 　　 //-－---寻好得赋给寻好序列
｝
}
//＝==＝==＝=SSTＦ,最短寻道法＝=＝=＝=========＝=＝====＝＝==＝=＝=
ｖoiｄ　SＳTF（)
{
inｔ tｅmp,n;
ｉnt A＝M；
ﻩtemｐ=BｅginNum；　 　　 　 　/／－--－－－--将ＢeginNｕｍ赋给ｔemｐ作为寻道时得当前所在磁道号
ﻩfｏr(ｉｎｔ i＝0;i＜Ｎ;i++)
ﻩ{
ﻩﻩfor（ｉnｔ j=0;ｊ<N;j＋+) 　　 　 　 　 　 　//－－－－---寻找最短得寻道长度
{
ﻩ if(abs（TrackOｒｄｅr[j]－teｍp)<A&&Fｉｎished［ｊ]==ｆalsｅ）
ﻩ ﻩ{
ﻩA=abｓ(TrａckOｒdｅr[j]-temｐ);
ﻩﻩ n=j;
ﻩﻩ｝
ﻩﻩﻩｅlse coｎtinue;
ﻩﻩ}
ﻩ Fｉnｉsheｄ[n]=ｔｒuｅ；　 　 　 　 //-－---－-将已经寻找到得Ｆinisheｄ赋值为tｒue
MoｖｅDistancｅ[ｉ]=Ａ;　　 /／-------寻道长度
ｔemp＝ＴrａckOrdｅｒ[n]；　　　　 　//-------当前寻道号。
ﻩＡ=M; 　 　//-－-－－重置A值
ﻩＦiｎdOｒdｅｒ[ｉ］=TrackOrder[ｎ]; ／/-－-－寻好得赋给寻好序列
}
}
／/＝＝==＝＝======＝==＝===＝=SCＡN，扫描算法=＝==＝＝===＝=＝===＝＝===＝==＝==
void　SCAＮ()
{
ﻩint m,n，temp;
ｔemｐ=BeginNum;
Sort(); 　 　 　　　 　 　 　　 //－－－---排序
coｕｔ<<"请选择开始方向:1--向外;０－--向里"；　 //-－----选择扫描方向
ﻩcｉn>>ｍ;
if(ｍ==1)
dｉrecｔion=tｒｕe;
ﻩeｌse iｆ(ｍ＝=０)
direｃtｉon=false;
ﻩelse
ﻩ cｏｕt<<"输入错误＂；
ﻩfｏr(inｔ i=０;i＜N；ｉ++)
ﻩ{
ﻩﻩｉｆ（SortOrder[i]<ＢeｇinＮｕm)
ﻩ ﻩcontiｎue；
else
ﻩﻩ{
ﻩ ﻩn=i；
ﻩ ｂrｅak;
}
ﻩ}
if(diｒｅcｔion==trｕe) 　 　 　 ／/------选择向外
｛
ｆor(ｉnt　i＝ｎ;i<Ｎ;i++）
｛
MｏveＤｉstａｎｃe[i-n]＝abs（SortOrｄer[ｉ]-ｔｅmｐ);
ﻩ ﻩtemp=SortOrdeｒ[i]；
ﻩ ﻩ ＦinｄＯrder[i-ｎ］=SｏrtＯrder［i];
}
ﻩﻩfor(inｔ j=n-1;j＞=0；j--)
ﻩﻩ{
ﻩﻩ MoｖeDｉstance[Ｎ－1-j]＝abs(SｏrtOrder[j]－temp);
ﻩﻩﻩﻩｔemp＝SortOrｄer［j];
ﻩﻩﻩﻩＦindOrdeｒ[N-1－ｊ］=SｏrｔOｒdeｒ［j];
ﻩ }
｝
else 　 　　　 　 　 　　 //--－-－－-选择向里
{
ﻩfor(int　i=n-1;i>=0;i－-）
ﻩ{
ﻩﻩMoveＤistanｃｅ[N-i-4］=ａｂs(ＳortＯrｄer[i]-tｅｍp);
ﻩﻩﻩtemp=SoｒtOｒdｅr[ｉ];
ﻩﻩ FindOrder[Ｎ-i-４］＝SｏｒｔOrｄer［i];
ﻩ｝
fｏr(int ｊ＝n;ｊ<Ｎ;ｊ+＋)
{
ﻩﻩ ﻩMoｖeＤiｓtａｎce［j］=abs（SortOrder[j］-ｔｅmp)；
ﻩ tｅmp=TrackＯrdeｒ［j］;
ﻩ ＦindOrdｅｒ[j]=ＳoｒｔOrｄer[ｊ];
｝
｝
｝
//=＝========＝==＝＝=＝CSCAN，循环扫描算法＝＝=======＝＝==＝====＝=＝=＝
void CSCAN()
{
int m,n,ｔeｍp;
ﻩｔemp=BｅｇinNｕｍ;
Sort();
ﻩcout<<"请选择开始方向：1-－向外；0-－-向里";
cin>＞m；
if（m==１)
dirｅｃｔion=true；
ﻩeｌse　if(m＝=0)
ﻩﻩdireｃtｉon=false；
eｌｓｅ
ﻩcoｕｔ<＜"输入错误＂;
for(inｔ i=0;i＜Ｎ；ｉ＋+)
ﻩ｛
if(SortOrdeｒ［i]<BｅginNum)
ﻩﻩcontinｕｅ;
ﻩelｓｅ
ﻩ{
ﻩﻩ ｎ=i；
ﻩﻩﻩbreak;
ﻩ }
ﻩ｝
if(dirｅctioｎ==tｒue)
ﻩ{
ﻩﻩｆor（int i＝n;i＜N；i++)
{
ﻩﻩﻩMovｅDistance[i-ｎ]=abｓ(SortOrder[i]-tｅmp）;
ﻩﻩﻩﻩtemp＝SortOrdｅr［i];
ﻩ ﻩ ＦｉｎｄＯrdｅr[ｉ－ｎ]＝SｏrtOrder［i］;
ﻩﻩ}
for(int j=０;j＜n；ｊ++)
ﻩ {
MｏｖeDistance[N-n+ｊ]=ａbs（ＳortＯｒder[ｊ］-tｅmp)；
ﻩﻩ ﻩtｅmp=SoｒｔOrｄer[j];
ﻩﻩﻩ FｉndOrｄer[Ｎ-ｎ+ｊ]=ＳortＯｒder[j];
ﻩ｝
ﻩ}
ﻩelｓe
｛
ﻩﻩｆor(iｎt i=n－1；i>=0;i--)
ﻩ {
ﻩﻩ ＭoveDiｓtaｎce[n-1-i]=ａbs(SｏrtＯrｄer[i]-tｅmp)；
ﻩ temp=ＳoｒtOrｄer［i];
ﻩ FindOrdeｒ[n-1-i]＝SortＯrｄer[ｉ];
ﻩ｝
ｆoｒ（ｉｎt j=N-1;ｊ>=n;ｊ--)
ﻩ{
ＭovｅＤistaｎce[N-ｊ+n-1]=ａbs(ＳortOrｄer[j]-tｅmｐ）;
ﻩﻩﻩﻩtemp=SｏrtOrder[j];
ﻩFｉndOrdｅr［N-j＋n－１]=ＳoｒｔOｒdeｒ[j];
ﻩ｝
ﻩ}
}
//=＝===＝＝=计算平均寻道时间===＝＝=＝====＝==
ｖｏid Counｔ()
{
int Ｔotａｌ=0；
ｆor（int i＝０;i<Ｎ;i++)
{
ﻩ Tｏtal+＝MoveＤiｓtancｅ[ｉ］;
ﻩ}
AvｅragｅDｉｓtaｎce＝（(ｄｏuble)Total)/((ｄoｕble)N）;
｝
voiｄ Shｏw(）
｛
ﻩｃouｔ<<"=＝===＝＝=＝=＝=＝===从"<<ＢegiｎNum＜<"号磁道开始＝=＝==＝=====＝====＝===="＜<eｎdl;
ﻩcoｕt<＜ｓetｗ（２0)<<"被访问得下一个磁道号＂<＜ｓｅtw(20)<<"移动距离(磁道数)"<<endl；
ﻩfor(int ｉ＝0;i<N；i++)
ﻩ{
ﻩﻩcoｕt＜＜ｓetw（15）<<FindOrder［i］<<ｓetｗ（15）＜＜MｏveDiｓtanｃe［i］<<eｎdl;
}
ｃｏuｔ＜<setw（20）<＜"平均寻道长度："＜＜AveｒaｇeDiｓtaｎｃe＜<endｌ;
ｃout<<enｄl;
}
int ｍain()
{
ﻩint y=１；
iｎt ｓ；
ﻩＩniｔｈ();
while(y)
ﻩ｛
cout<<"请选择寻道方式:1--ＦＣＦS; ２－-SＳTF; 3--SCAN；4--ＣSＣSN;";
ﻩcin>>s;
switch(s)
ﻩ {
ﻩﻩ 　 cａse １:FCFS()；Cｏuｎt();Show（）;break；
ﻩ case 2:ＳＳTF（)；Count();Sｈｏw（);break;
ﻩﻩﻩcaｓe ３:ＳCAＮ()；Count();Show();break;
ﻩ caｓe　4:ＣSCAＮ();Count();Shoｗ()；bｒｅaｋ;
ﻩﻩ}
cout<<"就是否继续选择寻道算法?1-－就是；2－-否＂;
ﻩｉnt　p;
ﻩ cin＞>p；
ﻩ y=p；
｝
ﻩreturn 0;
}
实验结果:
FCFS方式：

Sstf方式:

SCAN方式:

4、CSCSＮ