操作系統(tǒng)課程設(shè)計報告--磁盤調(diào)度算法

1、<p>　　《操作系統(tǒng)分析與設(shè)計實習》成績單</p><p>　　開設(shè)時間：2015學年第一學期</p><p><b>　　一、需求分析 </b></p><p>　　輸入的形式和輸入值的范圍：</p><p>　　在文本框輸入序列長度，輸入值為int類型</p><p><b

2、>　　輸出的形式：</b></p><p>　　輸出每種磁盤調(diào)度算法的服務(wù)序列；</p><p>　　輸出每種算法的平均尋道長度。</p><p>　　程序所能達到的功能：</p><p>　　模擬實現(xiàn)FCFS、SSTF、SCAN、C-SCAN 算法，并計算及比較磁頭移動道數(shù)。</p><p><

3、;b>　　測試數(shù)據(jù)：</b></p><p>　　包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果：</p><p><b>　　二、概要設(shè)計 </b></p><p><b>　　1）主程序流程圖：</b></p><p>　?。?）各程序模塊之間的調(diào)用關(guān)系</p&g

4、t;<p><b>　　三、詳細設(shè)計 </b></p><p><b>　　1）各操作偽碼算法</b></p><p>　?。?）實現(xiàn)磁頭初始位置的輸入并進行合法性檢查</p><p>　　int printstarter()//磁頭初始位置輸入</p><p><b>　　

5、{</b></p><p>　　輸入：磁頭初始位置;</p><p>　　if輸入小于0或大于1500</p><p><b>　　{</b></p><p>　　輸出："輸入數(shù)據(jù)類型有誤，請重新輸入！" <<endl;</p><p><b>

6、;　　重新輸入</b></p><p><b>　　}</b></p><p>　　Else返回合法的磁頭初始位置</p><p><b>　　}</b></p><p><b>　?。?）冒泡排序算法</b></p><p>　　int

7、*bubble//冒泡排序算法</p><p><b>　　{</b></p><p>　　for 從數(shù)組的第一個元素開始重復(fù)</p><p><b>　　{</b></p><p>　　依次和后續(xù)元素表較大??；</p><p>　　If后面元素大于當前元素</p>

8、;<p><b>　　交換數(shù)值；</b></p><p><b>　　}</b></p><p><b>　　輸出排序后的數(shù)組；</b></p><p><b>　　返回數(shù)組；</b></p><p><b>　　}</b&g

9、t;</p><p>　?。?）int out_to_in//由磁道最外向內(nèi)輸出磁道序列</p><p><b>　　{</b></p><p>　　for 從最外磁道開始</p><p><b>　　{</b></p><p><b>　　依次輸出磁道號;<

10、/b></p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p>　　磁頭初始位置=當前磁道號；</p><p><b>　　}</b></p><p><b>　　返回絕對值之和；</b></p><p><b>　　}</b>

11、</p><p>　?。?）int in_to_out//由磁道最內(nèi)向外輸出磁道序列</p><p><b>　　{</b></p><p>　　for 從最內(nèi)磁道開始</p><p><b>　　{</b></p><p><b>　　依次輸出磁道號;</b

12、></p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p>　　磁頭初始位置=當前磁道號；</p><p><b>　　}</b></p><p><b>　　返回絕對值之和；</b></p><p><b>　　}</b>&l

13、t;/p><p>　?。?）int out_to_in_to_out//先由當前位置向內(nèi)再向外</p><p><b>　　{</b></p><p>　　找到小于等于磁頭初始位置的磁道</p><p><b>　　for由該磁道開始</b></p><p><b>　

14、　{</b></p><p>　　向內(nèi)依次輸出磁道號；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p>　　for由該磁道的外側(cè)磁道開始</p><p><b>　　{</b></p>

15、<p>　　向外依次輸出磁道號；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p><b>　　返回絕對值之和；</b></p><p><b>　　}</b></p><p&g

16、t;　?。?）int in_to_out_to_in//先由當前位置向外再向內(nèi)</p><p><b>　　{</b></p><p>　　找到大于等于磁頭初始位置的磁道</p><p><b>　　for由該磁道開始</b></p><p><b>　　{</b></p

17、><p>　　向外依次輸出磁道號；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p>　　for由該磁道的內(nèi)側(cè)磁道開始</p><p><b>　　{</b></p><p>　　向內(nèi)依次輸

18、出磁道號；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p><b>　　返回絕對值之和；</b></p><p><b>　　}</b></p><p>　?。?）int out_to_

19、in_twice由當前磁道向內(nèi)再從最外向內(nèi)</p><p><b>　　{</b></p><p>　　找到小于等于磁頭初始位置的磁道；</p><p><b>　　for由該磁道開始</b></p><p><b>　　{</b></p><p>　　

20、向內(nèi)依次輸出磁道號；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p>　　for由最外側(cè)磁道開始</p><p><b>　　{</b></p><p>　　向內(nèi)依次輸出磁道號直到小于等于初始位置的磁道的外側(cè)

21、一個磁道；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p><b>　　返回絕對值之和；</b></p><p><b>　　}</b></p><p>　?。?）int in_to_o

22、ut_twice由當前磁道向外再從最內(nèi)向外</p><p><b>　　{</b></p><p>　　找到大于等于磁頭初始位置的磁道</p><p><b>　　for由該磁道開始</b></p><p><b>　　{</b></p><p>　　向

23、內(nèi)依次輸出磁道號；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p>　　for由最內(nèi)側(cè)磁道開始</p><p><b>　　{</b></p><p>　　向外依次輸出磁道號直到小于等于初始位置的磁道的內(nèi)側(cè)一

24、個磁道；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　}</b></p><p><b>　　返回絕對值之和；</b></p><p><b>　　}</b></p><p>　?。?）int nearest_

25、select就近選擇</p><p><b>　　{</b></p><p>　　找到大于磁頭初始位置的磁道；</p><p>　　while初始位置內(nèi)側(cè)差絕對值更小</p><p>　　{ 輸出內(nèi)側(cè)磁道號;</p><p><b>　　絕對值差求和；</b><

26、/p><p>　　初始位置更新為當前磁道號；</p><p><b>　　}</b></p><p>　　while 初始位置外側(cè)絕對值差更小</p><p><b>　　{</b></p><p><b>　　輸出外側(cè)磁道號；</b></p>

27、<p><b>　　絕對值差求和；</b></p><p>　　初始位置更新為當前磁道號；</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　If已到達最內(nèi)側(cè)未到達最外側(cè)</p><p>&l

28、t;b>　　{</b></p><p>　　if內(nèi)側(cè)絕對值差更小</p><p><b>　　{</b></p><p><b>　　輸出最內(nèi)側(cè)磁道號；</b></p><p><b>　　絕對差值求和；</b></p><p><

29、;b>　　初始位置更新；</b></p><p>　　while 向外側(cè)依次輸出磁道號直到到達最外側(cè)</p><p><b>　　{</b></p><p><b>　　絕對差值求和；</b></p><p><b>　　更新初始位置；</b></p&g

30、t;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　else外側(cè)絕對值差更小</p><p><b>　　{</b></p><p>　　While向外側(cè)依次輸出磁道號直到到達最外側(cè)</p><p&g

31、t;<b>　　{</b></p><p><b>　　絕對差值求和；</b></p><p><b>　　更新初始位置；</b></p><p><b>　　}</b></p><p><b>　　輸出最內(nèi)側(cè)磁道號；</b><

32、/p><p><b>　　絕對差值求和；</b></p><p><b>　　更新初始位置；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if 已到達最外側(cè)未到達最內(nèi)側(cè)&l

33、t;/p><p><b>　　{</b></p><p><b>　　If外側(cè)絕對值更小</b></p><p><b>　　{</b></p><p><b>　　輸出最外側(cè)磁道號；</b></p><p><b>　　絕對

34、差值求和；</b></p><p><b>　　更新初始位置；</b></p><p>　　while向內(nèi)依次輸出磁道號</p><p><b>　　{</b></p><p><b>　　絕對差值求和；</b></p><p><b&

35、gt;　　更新初始位置；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　

36、while 向內(nèi)依次輸出磁道號</p><p><b>　　{</b></p><p><b>　　絕對差值求和；</b></p><p><b>　　更新初始位置；</b></p><p><b>　　}</b></p><p>

37、<b>　　輸出最外側(cè)磁道號；</b></p><p><b>　　絕對值差求和；</b></p><p><b>　　更新初始位置；</b></p><p><b>　　}</b></p><p><b>　　}</b></p

38、><p>　　if均到達最內(nèi)側(cè)和最外側(cè)</p><p><b>　　{</b></p><p>　　if 外側(cè)差絕對值更小</p><p><b>　　{</b></p><p>　　輸出最外側(cè)磁道號并絕對值差求和；</p><p>　　輸出最內(nèi)側(cè)磁道號并

39、絕對值差求和；</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　輸出最內(nèi)側(cè)磁道號并絕對值差求和；</p><p>　　輸出最外側(cè)磁道號并絕對值差求和；<

40、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　求總和并返回；</b></p><p><b>　　}</b></p><p>　?。?0）void FCFS算法</p&

41、gt;<p><b>　　{</b></p><p>　　輸出磁盤請求序列為；</p><p>　　按照磁盤請求序列依次輸出磁盤掃描序列；</p><p>　　當前磁道號與磁頭初始未至的絕對值求和；</p><p><b>　　求平均值；</b></p><p>

42、;　　輸出平均尋道長度；}</p><p>　?。?1）void SSTF算法</p><p><b>　　{</b></p><p>　　if序列中最大的磁道號小于磁頭初始位置</p><p><b>　　{</b></p><p>　　調(diào)用out_to_in直接由外向內(nèi);

43、</p><p><b>　　}</b></p><p>　　if 序列中最小的磁道號大于磁頭初始位置</p><p><b>　　{ </b></p><p>　　調(diào)用in_to_out直接由內(nèi)向外;</p><p><b>　　}</b><

44、;/p><p>　　If 磁頭初始位置為中間值</p><p><b>　　{</b></p><p><b>　　調(diào)用就近選擇算法；</b></p><p><b>　　}</b></p><p><b>　　求均值；</b><

45、/p><p><b>　　輸出平均尋道時間；</b></p><p><b>　　}</b></p><p>　?。?2）void SCAN算法</p><p><b>　　{</b></p><p>　　輸入：磁臂移動方向（1：向外，0：向內(nèi)）;</

46、p><p>　　if 序列中最大的磁道號小于磁頭初始位置</p><p><b>　　{</b></p><p>　　調(diào)用out_to_in直接由外向內(nèi)；</p><p><b>　　}</b></p><p>　　if序列中最小的磁道號大于磁頭初始位置</p>&

47、lt;p><b>　　{</b></p><p>　　調(diào)用in_to_out直接由內(nèi)向外；</p><p><b>　　}</b></p><p>　　if 初始磁頭位置為中間值</p><p><b>　　{</b></p><p><b&

48、gt;　　if 磁臂方向向內(nèi)</b></p><p><b>　　{</b></p><p>　　調(diào)用out_to_in_to_out；</p><p><b>　　}</b></p><p><b>　　if 磁臂方向向外</b></p><p

49、><b>　　{</b></p><p>　　調(diào)用n_to_out_to_in；</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　求均值；</b></p><p>　

50、　輸出平均尋道時間；}</p><p>　?。?3）Viod C-SCAN算法</p><p><b>　　{</b></p><p>　　請輸入磁臂移動方向（1：向外，0：向內(nèi)）；</p><p>　　if 序列中最大磁道號小于等于磁頭初始位置</p><p><b>　　{</

51、b></p><p><b>　　if磁臂方向向內(nèi)</b></p><p><b>　　{</b></p><p>　　調(diào)用out_to_in;</p><p><b>　　}</b></p><p>　　if磁臂方向向外</p>

52、<p><b>　　{</b></p><p>　　調(diào)用in_to_out;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if 序列中最大磁道號大于等于磁頭初始位置</p><p>&l

53、t;b>　　{</b></p><p><b>　　if磁臂方向向內(nèi)</b></p><p><b>　　{</b></p><p>　　調(diào)用out_to_in;</p><p><b>　　}</b></p><p>　　if磁臂方向

54、向外</p><p><b>　　{</b></p><p>　　調(diào)用in_to_out;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if初始磁頭位置為中間值</p><p

55、><b>　　{</b></p><p>　　if (磁臂方向向內(nèi)</p><p><b>　　{</b></p><p>　　調(diào)用out_to_in_twice;</p><p><b>　　}</b></p><p><b>　　if

56、 磁臂方向向外</b></p><p><b>　　{</b></p><p>　　調(diào)用in_to_out_twice);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　

57、求均值；</b></p><p><b>　　輸出平均尋道時間；</b></p><p><b>　　}</b></p><p><b>　?。?4）主函數(shù)</b></p><p>　　int main()</p><p><b>

58、　　{</b></p><p>　　隨機生成200個0~499的磁道序列并輸出；</p><p>　　隨機生成100個500~999的磁道序列并輸出；</p><p>　　隨機生成100個1000~1500的磁道序列并輸出；</p><p><b>　　輸出：主菜單；</b></p><p

59、>　　輸入：用戶選擇并進行合法性檢查</p><p>　　switch (用戶選擇)</p><p><b>　　{</b></p><p>　　case 1:調(diào)用FCFS（）;</p><p>　　case 2:調(diào)用SSTF（）</p><p>　　case 3:調(diào)用SCAN（）</

60、p><p>　　case 4:調(diào)用C-SCAN（）</p><p><b>　　case 5:退出</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　2）函數(shù)的調(diào)用關(guān)系圖</p><

61、;p><b>　　四、調(diào)試分析 </b></p><p>　　1）調(diào)試過程中遇到的問題以及對設(shè)計與實現(xiàn)的討論和分析：</p><p>　?。?）隨機生成400個磁道號序列：使用rand()函數(shù)，對于：</p><p>　　50%位于 0～499，</p><p>　　25%分布在 500～999，</p&g

62、t;<p>　　25%分布在 1000～1499，采用如下方法解決：</p><p>　　track[i] = (rand() % 500);</p><p>　　track[i] = (rand() % 500)+500;</p><p>　　track[i] = (rand() % 500)+1000;</p><p>　　

63、（2）通過對每一行的輸出設(shè)置斷點判斷問題出現(xiàn)在哪里，把出問題的地方縮小到一定范圍，然后解決問題，如若解決不出則上網(wǎng)查詢。算法部分SSTF算法實現(xiàn)的比較復(fù)雜，時間復(fù)雜度較高。</p><p>　　2）算法的時間復(fù)雜性(包括基本操作和其他算法的時間復(fù)雜性的分析)和改進設(shè)想：</p><p>　?。?）FCFS算法：時間復(fù)雜度為O（n）,一重循環(huán)，算法比較簡單；</p><p

64、>　?。?）SSTF算法：時間復(fù)雜度為O（n^2），二重循環(huán)，算法較為復(fù)雜；</p><p>　?。?）SCAN算法：時間復(fù)雜度為O（n）；</p><p>　　（4）C-SCAN算法：時間復(fù)雜度為O（n）；</p><p>　　3）設(shè)計過程的經(jīng)驗和體會：</p><p>　　設(shè)計過程必須要按照自頂向下的結(jié)構(gòu)化設(shè)計方法，各個模塊要很清晰

65、的體現(xiàn)，并且要考慮時間復(fù)雜度。整個程序的結(jié)構(gòu)是很清晰的，首先在0~1500的范圍內(nèi)隨機生成400個磁道號序列，接著是主菜單選擇要使用的算法，各個算法的結(jié)構(gòu)通過調(diào)用不同的輸出磁道序列函數(shù)來實現(xiàn)，并進行絕對值的求和以及平均值的計算。</p><p><b>　　五、用戶使用說明 </b></p><p>　　1）按照菜單輸入選擇何種算法在1~5之間；</p>

66、<p>　　2）輸入磁頭初始位置在0~1500之間；</p><p>　　3）輸入磁臂方向，1：向外，0：向內(nèi)；</p><p><b>　　測試與運行結(jié)果 </b></p><p>　　1）初始界面，產(chǎn)生400個隨機序列，選擇算法：</p><p><b>　　FSFC算法：</b>

67、</p><p><b>　　SSTF算法：</b></p><p><b>　　SCAN算法：</b></p><p>　　最小磁道號大于等于初始磁頭位置，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p>　　最大磁道號小于等于磁頭初始位置，測試與運行結(jié)果：輸出請求序列、平均尋道時間：

68、</p><p>　?。?）方向0,磁頭初始位置為中間值，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p>　　（4）方向1,磁頭初始位置為中間值，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p><b>　　C-SCAN算法：</b></p><p>　　方向0，最小磁道號大于等于初始磁頭位置，

69、測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p>　　方向0，最大磁道號小于等于磁頭初始位置，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p>　　方向1，最小磁道號大于等于初始磁頭位置，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p>　　方向1，最大磁道號小于等于磁頭初位置，測試與運行結(jié)果：輸出請求序列、平均尋道時間：<

70、/p><p>　　方向0,磁頭初始位置為中間值，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p>　　方向1,磁頭初始位置為中間值，測試與運行結(jié)果：輸出請求序列、平均尋道時間：</p><p><b>　　總結(jié)感想</b></p><p>　　這次的操作系統(tǒng)課程設(shè)計，讓我對操作系統(tǒng)磁盤調(diào)度策略有了更加深刻的認識，

71、自己動手操作比光看書能更能深刻了解磁盤調(diào)度的策略和原理，同時對磁盤調(diào)度的四種算法——先來先服務(wù)算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF）、SCAN算法，C-SCAN算法有了更深刻的理解和掌握。設(shè)計過程中遇到的困難在老師和同學的幫助下順利解決，我深刻認識到算法的邏輯性和時間復(fù)雜度對程序的重要影響，算法的準確度對程序運行結(jié)果的重要影響，這對我以后在操作系統(tǒng)的學習中有極大幫助。也增強了我寫代碼的能力，尤其是對自頂向下的結(jié)構(gòu)化分析設(shè)計方