操作系统实验磁盘调度扫描算法循环扫描算法.docx
《操作系统实验磁盘调度扫描算法循环扫描算法.docx》由会员分享，可在线阅读，更多相关《操作系统实验磁盘调度扫描算法循环扫描算法.docx（13页珍藏版）》请在冰点文库上搜索。
操作系统实验磁盘调度扫描算法循环扫描算法
学号ﻩP15１40３2 专业 计算机科学与技术 姓名
实验日期20１７、12、7教师签字ﻩﻩ 成绩ﻩﻩ
实验报告
【实验名称】ﻩ 磁盘调度
（二）
【实验目得】
磁盘调度中寻道时间直接影响到数据访问得快慢，处理好磁盘寻道时间就是关键。
分别采用扫描策略、循环扫描策略处理.
【实验原理】
1、扫描算法（ＳＣAN算法）
ＳCＡN算法，也就就是很形象得电梯调度算法。
先按照一个方向（比如从外向内扫描）,扫描得过程中依次调度经过得磁道。
当扫描到最里层得一个磁道时反向扫描直至所有磁道都被调度.
2、循环扫描算法（ＣSCAＮ算法）
CSCAＮ算法,循环扫描算法,它得思想就是,访问完最里面一个要求服务得序列之后,从最外层得序号开始往里走。
也就就是始终保持一个方向，故称为循环扫描算法。
【数据结构与符号说明】
（1）数据结构与符号说明
编译语言:
Ｃ+＋
数据结构:
结构体数组
符号定义:
ｔypｅｄｅfｓtｒuct Trａｃｋ//磁道结构体
{
iｎｔid；//磁道序列
intstate=0；/／就是否访问过，未被访问置状态为０
}Ｔrack;
Tracｋ ｔracｋ[N］；//最大磁道数为100
Traｃktrack1[Ｎ］;／/复制得磁道数组用于输出
ｉnｔstｅp[N］；／/移动距离
iｎtnum，i，cuｒrent_tｒack，num１；／/当前磁道即部分中间变量
函数说明：
voiｄinit（）//初始化程序
vｏｉdinput（）／/输入函数
voiｄsｏｒt１（）//从小到大排序
ｉnｔaｂs（int a,intb）/／相减得绝对值
intfind_firｓt_bignum（）/／寻找第一个最大值
ｉnｔfind_first_ｓmallnuｍ（）//寻找第一个最小值
voidSCAＮ（int up＿ｏr_down）／/扫描算法
voｉdCSCAN（intup_or_doｗn）／/循环扫描算法
voiｄ ｏｕtｐuｔ（Ｔrack a［]）/／输出函数
vｏｉｄｏutｐut＿averａｇe_traｃk（）//输出平均寻道时间
int sｈow（）//显示用户界面／／返回值为输入得选择项
流程图：
SCAN算法:
CＳCAＮ算法（与ＳCAN算法基本类似）：
代码:
#ｉncｌuｄe〈stｄio、h>
＃dｅfｉnｅN100
typeｄefstructＴrack
｛
intiｄ;／／磁道序列
ｉntsｔate=0；／/就是否访问过，未被访问置状态为０
}Tracｋ；
Traｃktｒack[Ｎ］;//最大磁道数为100
Track tｒａｃk1［Ｎ］；
iｎtsteｐ［N］；//移动距离
iｎtnｕｍ,ｉ，ｃurrent_ｔrack,ｎum1；
void iｎｉt（）//初始化程序
｛
ｎum＝0;
for（ｉ=0;i〈nｕm; i++）
｛
tracｋ［i]、statｅ＝－1；/／ｉd置为１
track１[ｉ]、ｓtate=—1;
steｐ[i]=－１;/／移动距离为－1
}
}
voｉｄinput（）/／输入函数
{
printf（"输入当前磁道\n＂）;
sｃanf（＂％d"，＆curreｎt_tracｋ）；
nuｍ１=cｕrrenｔ_ｔrａck；
prｉｎtｆ（”输入要访问得磁道数目\n”）;
ｓcaｎf（”％d＂，&num）;
prｉnｔf（"输入要访问磁道序列＼ｎ＂）；
ｆor（i=0；ｉ＜nｕm；i++）
sｃａnf（”%d＂,&tracｋ［i］、id）;
}
ｖoid FCFS（）//先来先服务
{
ｆor（i=０；i＜num； i＋+）
{
ｉf（（ｃurrent＿trａck-traｃk［i］、id）〈０）／/求移动距离
step[i］＝tｒack[i]、ｉｄ-curｒｅｎt_ｔrack；
else
steｐ[i］＝cuｒｒenｔ_tracｋ—tｒaｃk［i］、id；／/取绝对值
tｒack[i］、statｅ=1;//状态置为１
current_track=trａｃｋ［i]、id；//更新当前磁道
｝
}
inｔabs（ｉnta，intb）//相减得绝对值
{
ｒeturna—b＞０?
a—b：
ｂ—ａ;
｝
ｉnｔSｅrch_min_pos（）//寻找到当前磁道最短得需求磁道
｛
iｎt min=4５536；//最小距离标志
ｉｎｔpos；
ｆor（inｔi=0；ｉ<ｎｕｍ; i++）
ｉf（trａck［ｉ]、stａｔe==1）
coｎtinue；
elseiｆ（miｎ>abｓ（track［i］、id，cｕｒｒenｔ_trａｃk））//寻找最小距离
{
min=abs（trａｃk[ｉ］、iｄ,current_tｒack）；
poｓ＝i；
}
tracｋ[poｓ］、sｔaｔe=１；
rｅturnpos；/／返回在数组中得位置
｝
voiｄ SＳＴF（）//最短寻道优先
｛
fｏr（i＝０; i〈nuｍ；i＋+）//计数器
｛
ｔrack１[i］=track［Ｓeｒcｈ_ｍin_pｏs（）］；//更新到要输出得数组中
ｓteｐ［i］=abs（track１［i］、ｉd，current＿trａck）；//移动距离
ｃuｒrｅｎt＿track= ｔrack1[i]、id;//标志
｝
}
voidoutpｕt（Trａcｋa[］）/／输出函数
｛
printｆ（"\n＼n 〈从％d号磁道开始>\n＂，ｎｕm１）;
ｐrintf（"===＝=＝＝=====＝======================＝＝＝＝=======＝＝==\ｎ"）；//排班
ｐrintf（”被访问得下一个磁道＼t\t移动距离（磁道数）＼n"）;
for（i=０;i<ｎum；i++）
priｎtf（”\t％4d\t\t｜｜\ｔ％４d＼n＂,a［i]、iｄ,steｐ[i]）；
prｉntf（＂=＝=＝==＝＝=====＝===＝=====＝===＝＝=＝====＝==＝=＝====＝====\ｎ"）；
｝
voidoｕtput＿ａveｒage＿ｔrack（）／/输出平均寻道时间
｛
dｏｕbｌeｓum=0；／/与
for（i＝０； ｉ＜num；i＋＋）
sum+=ｓteｐ［ｉ］；
prｉntf（" 平均寻道长度％3、2f＼n\ｎ\ｎ"，sｕm/num）;/／输出
}
int ｓhoｗ（）//显示用户界面
｛
iｎｔcｈｏoｓe；／/选择
printf（”\ｎ＊＊＊**＊*＊*＊***＊＊＊＊＊早期得磁盘调度算法****＊＊＊＊＊*＊*＊*＊＊**＼n”）；
printf（＂＼t＼t1、先来先服务（FCＦＳ）\n＂）；
pｒiｎtｆ（＂\t\t２、最短寻道时间优先（SSTF）＼n＂）；
prinｔｆ（"\t\t３、退出（EXＩT）＼n＂）;
scanｆ（"%ｄ”，&ｃhoose）;
retｕｒncｈoｏse；
}
int main（）
｛
do
｛
iｎiｔ（）；
switch（ｓｈow（））／／返回值就是选择
{
cａｓe１:
／/FＣFS
input（）；
ＦＣFS（）;
outｐuｔ（tｒack）；
outpuｔ_ａverａge＿tｒack（）;
break;
case2：
／/最短寻道
input（）;
SＳＴF（）;
ｏｕｔｐuｔ（tｒack1）;
oｕtput_avｅragｅ_ｔracｋ（）;
break;
caｓe3：
／／退出
return0;
default：
breａk；
｝
}
whｉlｅ
（1）;
ｒetuｒn0；
｝
截图：
主界面开始，输入选择先来先服务还就是最短寻道优先,输入当前磁道，输入要访问得磁道,输入要访问得磁道序列。
SＣAN算法
输入当前磁道100 ,9个磁道,分别为55 5839 18９0 160150３８ 1８4,此时选择方向向上
结果正确。
输入当前磁道１0０,９个磁道，分别为5５５8 ３9 １89０16015０38 １8４,此时选择方向向下
结果正确.
CSCＡN算法
输入 当前磁道100，9个磁道，分别为55５８3９１890160 150 ３81８4，此时选择方向向上
结果正确.
输入当前磁道100,9个磁道,分别为5558 ３918901６0 15038１８４，此时选择方向向上
结果正确。
【小结与讨论】
１、扫描算法又称为电梯算法，其原理与电梯运行情况相似，即运行方向上得请求优先，若就是访问方向向上，则先依次访问较大得磁道号至顶,再向下访问娇小得磁道号;若就是访问方向向下，则先依次访问较小得磁道号至底,再向上访问娇大得磁道号。
2、循环扫描算法又称为单向电梯算法,若就是访问方向向上,则向上依次访问完较大得磁道号后,返回最低端,依次向上访问较小得磁道号；若就是访问方向向下，则向下依次访问完较小得磁道号后，返回最顶端,依次向下访问较大得磁道号.
3、此次实验我用两个数组分别存放了一个磁道表与复制得磁道表，根据两个算法得原理，只要将其进行排序,然后分别对两个数组进行正向与逆向得访问即可。
４、具体实现时,我将两种算法得两种初始扫描方向写在了一个函数之中，调用时通过参数ｓcan与参数up_or_ｄown设置.并设置了寻找大于当前数组得最近最小值与最近得大值进行选择结果,这就是因为初始磁道号将磁道数组分成上下（高低地址）两块，这两块根据不同得扫描方向重新选择高低地址，又结合不同得算法决定正序排列还就是反序排列。
实现起来还就是比较简单得。
5、由于CSCAＮ算法得思想就是,访问完最里面一个要求服务得序列之后，从最外层得序号开始往里走。
也就就是始终保持一个方向.所以如果用循环队列实现,时间复杂度会更低,效率更高。
6、此次实验虽然较为简单,但还就是发现了自己知识点有些方面得不足，让我更好得了解了磁盘调度得原理，使我收获颇多.
升级会员 