操作系統———磁盤調度算法模擬

實驗目的

?磁盤是可供多個進程共享的設備，當有多個進程都要求訪問磁盤是，應采用一種最佳調度算法，以使各進程對磁盤的平均訪問時間最小。目前最成用的磁盤調度算法有先來先服務（FCFS），最短尋道時間優先（SSTF），以及掃描算法（SCAN）。通過本實驗可以加深理解有關磁盤調度的目標，并體會和了解最短尋道時間優先算法和掃描算法的具體實施辦法。

實驗內容

1 從100#磁道開始，被訪問的磁道號分別為：55，58，39，18，90，160，150，38，184。

2 要求用最短尋道時間優先算法的和掃描算法實現磁盤調度。

3 記錄下每訪問一個磁道磁頭移動的磁道數，并計算平均尋道長度（平均移動磁道數）。，，

實驗要求

分別用兩種算法實現磁盤調度。在實驗結果分析中，將比較結果以列表的形式表現出來。用數組（或鏈表）TR[ ]存儲待訪問磁道號，將每次磁頭移動磁道數用數組AR[ ] 存儲。輸出結果應如下例：（注意空格）

150	50
160	10
，184	24
18，，	166
38	20
39	1
55	16
58	3
90	32
平均尋道長度：35.8

編程工具：

C++語言平臺（DevC++開發工具）

五、

(1)問題概述

磁盤調度算法的目的是優化磁盤I/O操作，減少磁頭移動距離，從而提高磁盤I/O效率。
常見的磁盤調度算法包括：先來先服務(FCFS)算法、最短尋道時間優先(SSTF)算法、輪轉優先(SCAN)算法、最少最近使用(LRU)算法等。
FCFS算法按請求到達順序依次處理請求，簡單但效率低下。SSTF算法選擇離當前磁頭位置最近的請求處理，可以減少磁頭移動但難以實現。
SCAN算法將磁盤劃分為多個區，依次掃描每個區處理請求，減少磁頭移動但響應時間長。LRU算法優先處理最近最久未使用的磁盤塊，需要記錄使用信息增加開銷。

(2)整體功能及設計

通過構建最短尋道時間優先算法函數、構建掃描算法函數，然后將創作主函數循環調用，并能夠輸出調度過程以及平均尋道長度。

(3)編程實現（附代碼和截圖）

#include<stdio.h> 
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
//55 58 39 18 90 160 150 38 184
void SSTF(int a[], int n) {//最短尋道時間優先調度int site = 1;//確定開始磁道中間位置int m, Left, Right;int i, j, sum = 0;double Average=0;int Temp; sort(a, a + n);//對磁道號進行從小到大排列printf("排序后磁道數組如下：\n");for (i = 0; i < n; i++) //輸出排序后的磁道號數組printf("%d ", a[i]);printf("\n請輸入開始的磁道號： ");scanf("%d", &m);printf("\nSSTF（最短尋道優先）調度過程如下: \n");printf("\n被訪問的下一個磁道號             移動距離（磁道數）\n"); int mark = m;//用來計算差值或移動距離if (a[n - 1] <= m)//整個數組里的數都小于開始磁道號的情況{for (i = n - 1; i >= 0; i--) { //將數組磁道號就逆序輸出printf("%10d ---------------------- %-3d\n", a[i], mark - a[i]);mark = a[i];}sum = m - a[0];}else if (a[0] >= m)//整個數組里的數都大于開始磁道號的情況{for (i = 0; i < n; i++) { //將磁道號從小到大順序輸出printf("%10d ---------------------- %-3d\n", a[i], a[i] - mark);mark = a[i];}sum = a[n - 1] - m;}else{while (a[site] < m)//找位置{site++;}Left = site - 1;Right = site;//確定開始磁道在已排的序列中的位置while ((Left >= 0) && (Right < n)){if ((m - a[Left]) <= (a[Right] - m))//找最短距離是在左側還是右側{printf("%10d ---------------------- %-3d\n", a[Left], mark - a[Left]);mark = a[Left];sum += m - a[Left];m = a[Left];Left = Left - 1;}else//在右側{printf("%10d ---------------------- %-3d\n", a[Right], a[Right] - mark);mark = a[Right];sum += a[Right] - m;m = a[Right];Right = Right + 1;}}if (Left = -1){for (j = Right; j < n; j++)//順序輸出 {printf("%10d ---------------------- %-3d\n", a[j], a[j] - mark);mark = a[j];}sum += a[n - 1] - a[0];}else{for (j = Left; j >= 0; j--)//逆序輸出 {printf("%10d ---------------------- %-3d\n", a[j], mark - a[j]);mark = a[j];}sum += a[n - 1] - a[0];}}printf("\n");Average = (double)sum / n;printf(" 可見平均尋道的長度為： %.2f \n", Average);
}void SCAN(int a[], int n) {///掃描算法或電梯調度算法int i, j, sum = 0;double Average;for (i = 0; i < n; i++){sort(a, a + n);//升序排序}printf("排序后的磁道數組如下：\n");for (i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n請輸入開始的磁道號： ");int m;scanf("%d", &m);printf("\nSCAN（掃描或電梯）調度過程如下：\n");printf("\n被訪問的下一個磁道號             移動距離（磁道數）\n"); int pointer;int mark = m;for (i = 0; i < n; i++){if (a[i] >= m)//找到比開始磁道號大的數 {pointer = i;sum += abs(a[i] - m);break;}}for (i = pointer; i < n; i++){if (i != pointer)//順著磁頭方向順序輸出 sum += abs(a[i] - a[i - 1]);printf("%10d ---------------------- %-3d\n", a[i], a[i] - mark);mark = a[i];}if (pointer >= 1)sum += abs(a[n - 1] - a[pointer - 1]);for (i = pointer - 1; i >= 0; i--)//逆著磁頭方向順序輸出 {if (i)sum += abs(a[i] - a[i - 1]);printf("%10d ---------------------- %-3d\n", a[i], mark - a[i]);mark = a[i];}Average = (double)sum / n;printf("\n 平均尋道的長度為：%.2f\n", Average);
}
int main() {int track[100];//定義磁道號數組int select;int i = 0;int n;printf("請先輸入磁道數量： \n");scanf("%d", &n);printf("請先輸入磁道序列： \n");for (i = 0; i < n; i++){scanf("%d", &track[i]);}printf("\n");while (1){printf("1.最短尋道時間優先算法(SSTF) \n");printf("2.掃描算法(SCAN)\n");printf("3.退出\n");printf("\n");printf("請選擇要使用的調度算法： ");scanf("%d", &select);switch (select)//算法選擇{case 1:SSTF(track, n);//最短服務時間優先算法printf("\n");break;case 2:SCAN(track, n);//掃描算法printf("\n");break;case 3:exit(0);}}return 0;
}