操作系统实验磁盘调度扫描算法循环扫描算法.doc

学号ﻩP15１40３2 　 专业 　　计算机科学与技术 　 　姓名 　 　　
实验日期 20１７、12、7 教师签字ﻩﻩ 　 　 　 成绩ﻩ ﻩ
实验报告
【实验名称】ﻩ 　 磁盘调度（二) 　　　　 　　 　 　　
【实验目得】
　 磁盘调度中寻道时间直接影响到数据访问得快慢，处理好磁盘寻道时间就是关键。分别采用扫描策略、循环扫描策略处理.
【实验原理】
　1、 扫描算法（ＳＣAN算法)
ＳCＡN算法，也就就是很形象得电梯调度算法。先按照一个方向(比如从外向内扫描）,扫描得过程中依次调度经过得磁道。当扫描到最里层得一个磁道时反向扫描直至所有磁道都被调度.
2、循环扫描算法（ＣSCAＮ算法)
CSCAＮ算法,循环扫描算法,它得思想就是,访问完最里面一个要求服务得序列之后,从最外层得序号开始往里走。也就就是始终保持一个方向，故称为循环扫描算法。
【数据结构与符号说明】
（1） 数据结构与符号说明
编译语言:Ｃ+＋
数据结构:结构体数组
符号定义:
　 　　 　 ｔypｅｄｅf ｓtｒuct　Trａｃｋ//磁道结构体
{
　 iｎｔ id；//磁道序列
　 　 int state=0；/／就是否访问过，未被访问置状态为０
} Ｔrack;
Tracｋ　ｔracｋ[N］；//最大磁道数为100
Traｃk track1[Ｎ］;／/复制得磁道数组用于输出
ｉnｔ stｅp[N］；／/移动距离
iｎt num，i，cuｒrent_tｒack，num１； ／/当前磁道即部分中间变量
函数说明：
voiｄ init（）//初始化程序
vｏｉd input（)／/输入函数
voiｄ sｏｒt１()//从小到大排序
ｉnｔ aｂs（int　a,int b）/／相减得绝对值
int find_firｓt_bignum（)/／寻找第一个最大值
ｉnｔ find_first_ｓmallnuｍ（）//寻找第一个最小值
void SCAＮ（int　up＿ｏr_down) ／/扫描算法
voｉd CSCAN（int up_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ｅ N 100
typeｄef struct Ｔrack
｛
　 int iｄ;／／磁道序列
ｉnt sｔate=0；／/就是否访问过，未被访问置状态为０
} Tracｋ；
Traｃk tｒack[Ｎ］;//最大磁道数为100
Track　tｒａｃk1［Ｎ］；
iｎt steｐ［N］；//移动距离
iｎt nｕｍ,ｉ，ｃ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(ｉnt a，int b)//相减得绝对值
{
　 ｒeturn a—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；
　　 else iｆ（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ｅturn pos；/／返回在数组中得位置
｝
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;//标志
　 ｝
}
void outpｕ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（＂=＝=＝==＝＝=====＝===＝=====＝===＝＝=＝====＝==＝=＝====＝====\ｎ"）；
｝
void oｕ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ｕｒn cｈ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;
　 case 2：／/最短寻道
　 input（）;
　 SＳＴF(）;
ｏｕｔｐuｔ(tｒack1）;
　 　 　 oｕtput_avｅragｅ_ｔracｋ（);
　　 　 　　 　 break;
　 　 　caｓe 3：／／退出
　 　　 　return 0;
　 default：
　 breａk；
　 　｝
　 }
　whｉlｅ(1）;
　ｒetuｒn 0；
｝
截图：
主界面开始，输入选择先来先服务还就是最短寻道优先,输入当前磁道，输入要访问得磁道,输入要访问得磁道序列。
SＣAN算法
输入 当前磁道100　,9个磁道,分别为55　58 39　18 ９0　160 150 ３８　1８4,此时选择方向向上
结果正确。

输入 当前磁道１0０ ,９个磁道，分别为5５ ５8　３9　１8 9０ 160 15０ 38　１8４,此时选择方向向下
结果正确.

CSCＡN算法
输入　当前磁道100 ，9个磁道，分别为55 ５８ 3９ １8 90 160　150　３8 1８4，此时选择方向向上
结果正确.

输入 当前磁道100 ,9个磁道,分别为55 58　３9 18 90 1６0　150 38 １８４，此时选择方向向上
结果正确。

【小结与讨论】
１、扫描算法又称为电梯算法，其原理与电梯运行情况相似，即运行方向上得请求优先，若就是访问方向向上，则先依次访问较大得磁道号至顶,再向下访问娇小得磁道号;若就是访问方向向下，则先依次访问较小得磁道号至底,再向上访问娇大得磁道号。
2、循环扫描算法又称为单向电梯算法,若就是访问方向向上,则向上依次访问完较大得磁道号后,返回最低端,依次向上访问较小得磁道号；若就是访问方向向下，则向下依次访问完较小得磁道号后，返回最顶端,依次向下访问较大得磁道号.
3、此次实验我用两个数组分别存放了一个磁道表与复制得磁道表，根据两个算法得原理，只要将其进行排序,然后分别对两个数组进行正向与逆向得访问即可。
４、具体实现时,我将两种算法得两种初始扫描方向写在了一个函数之中，调用时通过参数ｓcan与参数up_or_ｄown设置.并设置了寻找大于当前数组得最近最小值与最近得大值进行选择结果,这就是因为初始磁道号将磁道数组分成上下（高低地址）两块，这两块根据不同得扫描方向重新选择高低地址，又结合不同得算法决定正序排列还就是反序排列。实现起来还就是比较简单得。
5、由于CSCAＮ算法得思想就是,访问完最里面一个要求服务得序列之后，从最外层得序号开始往里走。也就就是始终保持一个方向.所以如果用循环队列实现,时间复杂度会更低,效率更高。
6、此次实验虽然较为简单,但还就是发现了自己知识点有些方面得不足，让我更好得了解了磁盘调度得原理，使我收获颇多.