報告題目:磁碟排程演算法
小組成員:
指導教師:滕豔萍
2023年6月
磁碟排程演算法
一.設計目的
本課程設計是學習完《計算機作業系統》課程後,進行的一次全面的綜合訓練,通過課程設計,我們更好地掌握作業系統的原理及實現方法,加深對作業系統基礎理論和重要演算法的理解,加強了動手能力。
二.課程設計內容和要求
程式設計序實現下述磁碟排程演算法,並求出每種演算法的平均尋道長度,要求設計主介面以靈活選擇某演算法,且以下演算法都要實現:
1、 先來先服務演算法(fcfs)
2、 最短尋道時間優先演算法(sstf)
3、 掃瞄演算法(scan)
4、 迴圈掃瞄演算法(cscan)
三.演算法及資料結構
3.1演算法的總體思想
裝置的動態分配演算法與程序排程相似,也是基於一定的分配策略的。常用的分配策略有先請求先分配、優先順序高者先分配等策略。在多道程式系統中,低效率通常是由於磁碟類旋轉裝置使用不當造成的。
作業系統中,對磁碟的訪問要求來自多方面,常常需要排隊。這時,對眾多的訪問要求按一定的次序響應,會直接影響磁碟的工作效率,進而影響系統的效能。訪問磁碟的時間因子由3部分構成,它們是查詢(查詢磁軌)時間、等待(旋轉等待扇區)時間和資料傳輸時間,其中查詢時間是決定因素。
因此,磁碟排程演算法先考慮優化查詢策略,需要時再優化旋轉等待策略。
平均尋道長度(l)為所有磁軌所需移動距離之和除以總的所需訪問的磁軌數(n),即:l=(m1+m2++mi++mn)/n
其中mi為所需訪問的磁軌號所需移動的磁軌數。
啟動磁碟執行輸入輸出操作時,要把移動臂移動到指定的柱面,再等待指定扇區的旋轉到磁頭位置下,然後讓指定的磁頭進行讀寫,完成資訊傳送。因此,執行一次輸入輸出所花的時間有:
尋找時間——磁頭在移動臂帶動下移動到指定柱面所花的時間。
延遲時間——指定扇區旋轉到磁頭下所需的時間。
傳送時間——由磁頭程序讀寫完成資訊傳送的時間。
其中傳送資訊所花的時間,是在硬體設計就固定的。而尋找時間和延遲時間是與資訊在磁碟上的位置有關。
為了減少移動臂進行移動花費的時間,每個檔案的資訊不是按盤面上的磁軌順序存放滿乙個盤面後,再放到下乙個盤面上。而是按柱面存放,同一柱面上的各磁軌被放滿資訊後,再放到下乙個柱面上。所以各磁碟的編號按柱面順序(從0號柱面開始),每個柱面按磁軌順序,每個磁軌又按扇區順序進行排序。
3.2演算法實現
1.先來先服務演算法(fcfs)
先來先服務(fcfs)排程:按先來後到次序服務,未作優化。最簡單的移臂排程演算法是「先來先服務」排程演算法,這個演算法實際上不考慮訪問者要求訪問的物理位置,而只是考慮訪問者提出訪問請求的先後次序。
例如,如果現在讀寫磁頭正在100號柱面上執行輸出操作,而等待訪問者依次要訪問的柱面為55,58,39,18,90,160,150,38,184那麼,當100號柱面上的操作結束後,移動臂將按請求的先後次序先移到55號柱面,最後到達184號柱面。
採用先來先服務演算法決定等待訪問者執行輸入輸出操作的次序時,移動臂來回地移動。先來先服務演算法花費的尋找時間較長,所以執行輸入輸出操作的總時間也很長。
void fcfs(int a, int n)
printf("移動的總磁軌數:%d\n", sum);
printf("移動的平均磁軌數:%.2lf\n", 1.0*sum / n);
printf("請再次輸入你想使用的方法:\n");
}2.最短尋道時間優先演算法(sstf)
最短尋找時間優先排程演算法總是從等待訪問者中挑選尋找時間最短的那個請求先執行的,而不管訪問者到來的先後次序。現在仍利用同乙個例子來討論,現在當100號柱面的操作結束後,應該先處理90號柱面的請求,然後到達58號柱面執行操作,隨後處理55號柱面請求,後繼操作的次序應該是39,38,18,150,160,184.採用最短尋找時間優先演算法決定等待訪問者執行操作的次序時,讀寫磁頭總共移動多個柱面的距離,與先來先服務、演算法比較,大幅度地減少了尋找時間,因而縮短了為各訪問者請求服務的平均時間,也就提高了系統效率。
但最短查詢時間優先(sstf)排程,fcfs會引起讀寫頭在盤面上的大範圍移動,sstf查詢距離磁頭最短(也就是查詢時間最短)的請求作為下一次服務的物件。sstf查詢模式有高度區域性化的傾向,會推遲一些請求的服務,甚至引起無限拖延(又稱飢餓)。
void sstf(int a, int n)
printf("%d \t", a[i]);
if (i % 10 == 9)
}printf("\n");
printf("請輸入當前磁軌號:\n");
scanf("%d", &now);
if (a[0] >=now)
sum = a[n - 1] - now;
printf("移動的總磁軌數:%d\n", sum);
}else if (a[n - 1] <= now)
sum = now-a[0];
printf("移動的總磁軌數:%d\n", sum);
}else
j = k-1;
i = 0;
while ((j>=0)&&(ki++;
if (now - a[j] >= a[k] - now)
if (k > n-1)
if (j <0){
for (int t = k; t < n; t++){
i++;
if (t == k){
printf("當前訪問的磁軌:\t%d\n",a[k]);
else{
printf("當前訪問的磁軌:\t%d\n",a[t]);
網路作業系統綜合實訓報告
班級 10計算機網路2班 學號 2010202229 姓名 袁震 日期 2011.06.16 一 綜合實訓專案設計 自己設計乙個網路作業系統使用的例子,如中澳學院校園網,班級網路等 二 虛擬機器和網路作業系統的安裝和配置 1 x安裝配置過程 2 x測試過程 3 x問題處理 三 活動目錄的安裝和配置 ...
作業系統實習報告
主函式 void main 三 資料結構 先來先服務 struct stu 用結構體實現 時間片輪轉法 struct time,struct time time 宣告乙個指向time型別的物件的指標,指標的名字是time,用指標實現該功能 優先數排程 struct pcb2,pcb2裡面包含程序名 ...
外匯操作實訓報告
經濟與管理學院課程設計指導及報告寫作要求 二 課程設計報告寫作要求 一 課程設計報告應包括以下幾方面內容 a封面 b.目錄 c正文。二 字數要求 不少於三 課程設計報告的列印要求 課程設計報告用a4紙列印。大標題統一按四號黑體字,小標題小四號黑體字,正文用宋體小四號字,行間距18磅 版面頁邊距上3c...