磁盤調(diào)度報告

PAGE成績課程設(shè)計報告題目磁盤調(diào)度算法設(shè)計課程名稱操作系統(tǒng)課程設(shè)計院部名稱信息技術(shù)學(xué)院專業(yè)11計算機(jī)科學(xué)與技術(shù)班級11計算計科學(xué)與技術(shù)（2）學(xué)生姓名宋雙學(xué)號1105101002課程設(shè)計地點(diǎn)1318課程設(shè)計學(xué)時20指導(dǎo)教師何健金陵科技學(xué)院教務(wù)處制PAGEII目錄TOC\o"1-4"\h\z\u摘要 II1

前言 11.1目的 11.2背景 11.3意義 12正文 22.1課設(shè)要求 22.2課設(shè)設(shè)備、環(huán)境 22.3課設(shè)方法及步驟 22.3.1設(shè)計方法： 22.3.2設(shè)計步驟： 42.4

實(shí)驗(yàn)、調(diào)試及測試結(jié)果與分析。 93

結(jié)論 114

參考文獻(xiàn) 125

附錄 12摘要多道程序設(shè)計中，經(jīng)常是若干個進(jìn)程同時處于就緒狀態(tài)，必須依照某種策略來決定那個進(jìn)程優(yōu)先占有處理機(jī)。因而引起進(jìn)程調(diào)度。本實(shí)驗(yàn)?zāi)M在單處理機(jī)情況下的處理機(jī)調(diào)度問題，加深對進(jìn)程調(diào)度的理解。模擬實(shí)現(xiàn)FCFS、SSTF、SCAN算法，并計算及比較磁頭移動道數(shù)。本實(shí)驗(yàn)設(shè)計的目的是通過設(shè)計一個磁盤調(diào)度模擬系統(tǒng)，以加深對FCFS、最短尋道時間以及電梯等磁盤調(diào)度算法的理解。讓我們更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法,加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)動手能力。本實(shí)驗(yàn)設(shè)計的目的是通過設(shè)計一個磁盤調(diào)度模擬系統(tǒng)，以加深對FCFS、最短尋道時間以及電梯等磁盤調(diào)度算法的理解。讓我們更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法,加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)動手能力。關(guān)鍵字：磁盤調(diào)度fcfssstfscan算法PAGE181

前言1.1目的磁盤是經(jīng)常使用的一種重要的外設(shè)，對磁盤數(shù)據(jù)的尋道時間的長短直接影響機(jī)器的整體運(yùn)行速度，本設(shè)計要求用C語言（或高級語言）編寫程序模擬實(shí)現(xiàn)磁盤調(diào)度的常用算法。以加深對磁盤調(diào)度常用算法的理解和實(shí)現(xiàn)技巧。1.2背景磁盤驅(qū)動調(diào)度對磁盤的效率有重要影響。磁盤驅(qū)動調(diào)度算法的好壞直接影響輔助存儲器的效率，從而影響計算機(jī)系統(tǒng)的整體效率。磁盤調(diào)度在多道程序設(shè)計的計算機(jī)系統(tǒng)中，各個進(jìn)程可能會不斷提出不同的對磁盤進(jìn)行讀/寫操作的請求。由于有時候這些進(jìn)程的發(fā)送請求的速度比磁盤響應(yīng)的還要快，因此我們有必要為每個磁盤設(shè)備建立一個等待隊(duì)列，常用的磁盤調(diào)度算法有以下四種：先來先服務(wù)算法（FCFS），最短尋道時間優(yōu)先算法（SSTF），掃描算法（SCAN），循環(huán)掃描算法（CSCAN）1.3意義在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉(zhuǎn)設(shè)備使用不當(dāng)造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊(duì)。這時，對眾多的訪問要求按一定的次序響應(yīng)，會直接影響磁盤的工作效率，進(jìn)而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構(gòu)成，它們是查找（查找磁道）時間、等待（旋轉(zhuǎn)等待扇區(qū)）時間和數(shù)據(jù)傳輸時間，其中查找時間是決定因素。因此，磁盤調(diào)度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉(zhuǎn)等待策略。2正文2.1課設(shè)要求1）、設(shè)計一個函數(shù)完成先來先服務(wù)的磁盤調(diào)度功能。2）、設(shè)計一個函數(shù)完成最短尋道時間優(yōu)先的磁盤調(diào)度功能。3）、設(shè)計一個函數(shù)完成電梯算法的磁盤調(diào)度功能。2.2課設(shè)設(shè)備、環(huán)境奔騰以上計算機(jī)，裝有TurboC2.0軟件2.3課設(shè)方法及步驟2.3.1設(shè)計方法：本系統(tǒng)應(yīng)該具有功能：設(shè)計一個函數(shù)完成先來先服務(wù)的磁盤調(diào)度功能，設(shè)計一個函數(shù)完成最短尋道時間優(yōu)先的磁盤調(diào)度功能，設(shè)計一個函數(shù)完成電梯算法的磁盤調(diào)度功能，并設(shè)計一個函數(shù)實(shí)現(xiàn)文件保存功能。本系統(tǒng)具有通用性，界面美觀，操作方便考慮到了系統(tǒng)安全問題。相關(guān)信息應(yīng)保存在文件中。本軟件的性能很好：通過磁盤調(diào)度算法的模擬設(shè)計，了解磁盤調(diào)度的特點(diǎn)。磁盤調(diào)度算法是根據(jù)訪問都指定的磁道（柱面）位置來決定執(zhí)行次序的調(diào)度。其目的是盡可能地減少操作中的尋道時間。在磁盤盤面上，0磁道在盤面的外圈；號數(shù)越大，磁道戛靠近盤片的中心。通常采用FCFS（先來先服務(wù)）、SSTF（最短尋道時間）、SCAN（掃描）進(jìn)行不同的磁盤調(diào)度。該磁盤調(diào)度系統(tǒng)流程圖如下：輸入數(shù)據(jù)輸入數(shù)據(jù)選擇算法？調(diào)用FCFS（）算法調(diào)用SSTF（）算法調(diào)用SCAN（）算法輸出退出是否開始圖2.3.1.1系統(tǒng)模塊圖如下：磁盤調(diào)度磁盤調(diào)度登陸界面電梯調(diào)度算法最短尋道時間優(yōu)先算法先來先服務(wù)算法保存文件圖2.3.1.2函數(shù)調(diào)用關(guān)系圖main函數(shù)main函數(shù)FCFS函數(shù)SSTF函數(shù)SCAN函數(shù)FCFS函數(shù)SSTF函數(shù)SCAN函數(shù)輸出輸出圖2.3.1.32.3.2設(shè)計步驟：下面我將詳細(xì)地為你講解本程序的FCFS（先來先服務(wù)）、SSTF（最短尋道時間）、SCAN（掃描）、C-SCAN（單向掃描）。2.3.2.1FCFS（先來先服務(wù)）算法先來先服務(wù)是一種最簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平，簡單，且每個進(jìn)程的請求都能依次地得到處理，不會出現(xiàn)某一進(jìn)程的請求長期得不到滿足的情況。但是，此算法由于未對尋道進(jìn)行優(yōu)化，致使平均尋道時間可能較長。圖2.4.2展示出有10個進(jìn)程先后提出磁盤I/O請求時，按先來先服務(wù)算法進(jìn)行調(diào)度的情況。這里，將進(jìn)程號按他們發(fā)出請求的先后次序排隊(duì)。這樣，平均尋道距離為53.1條磁道，與后面將講到的幾種調(diào)度算法相比，其平均尋道距離較大，故先來先服務(wù)算法僅適用于請求磁盤I/O的進(jìn)程數(shù)目較少的場合。程序設(shè)計流程圖為：輸入各磁道號和當(dāng)前磁道號start輸入各磁道號和當(dāng)前磁道號start磁頭移動距離sum=abss(p[0]-start)磁頭移動總距離sum+=abss(p[i]-start)輸出磁盤調(diào)度序列p目前的位置變?yōu)楫?dāng)前的位置start=p[i]i<num輸出平均尋道長度asum/num圖2.3.2.1我們通過程序for(i=0;i<num;i++){sum+=abss(p[i]-start);start=p[i];}來實(shí)現(xiàn)該算法。2.3.2.2SSTF（最短尋道時間）算法該算法選擇這樣的進(jìn)程，其要求訪問的磁道，與當(dāng)前磁頭所在的磁道距離最近，以使得每次的尋道時間最短，但是這種算法不能保證平均尋道時間最短。圖2.4.3展示出最短尋道時間優(yōu)先算法進(jìn)行調(diào)度時，各進(jìn)程被調(diào)度的次序，每次磁頭移動的距離，以及9次磁頭平均移動距離。比較圖2.4.2和圖2.4.3可以看出，最短尋道時間優(yōu)先算法的平均每次磁頭移動距離，明顯低于先來先服務(wù)的距離，因而最短尋道時間優(yōu)先算法較之先來先服務(wù)有更好的尋道性能，故過去曾一度被廣泛采用。程序設(shè)計流程圖為：輸入各磁道號和當(dāng)前磁道號start輸入各磁道號和當(dāng)前磁道號start設(shè)最短距離設(shè)最短距離min=abss(p[0]-start)min>=abss(p[j]-start)min>=abss(p[j]-start)j++j++當(dāng)前磁道所在位置current=j當(dāng)前磁道所在位置current=j當(dāng)前臨時隊(duì)列temp[len++]=p[current]當(dāng)前臨時隊(duì)列temp[len++]=p[current]磁頭移動總距離磁頭移動總距離sum+=abss(p[current]-start)輸出磁盤調(diào)度序列temp輸出磁盤調(diào)度序列temp輸出平均尋道長度輸出平均尋道長度sum/num圖2.3.2.2我們通過程序for(i=0;i<n;i++) {min=abss(p[0]-start);for(j=0;j<num;j++) {if(min>=abss(p[j]-start)) {min=abss(p[j]-start);current=j; }}temp[len++]=p[current];sum+=fabs(p[current]-start);start=p[current]; for(j=current+1;j<num;j++)p[j-1]=p[j];num--; }來實(shí)現(xiàn)最短尋道時間優(yōu)先算法。2.3.2.3SCAN（電梯調(diào)度）算法該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動方向。例如，當(dāng)磁頭正在自里向外移動時，電梯調(diào)度算法所考慮的下一個訪問對象，應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直至再無更外的磁道需要訪問時，才將磁臂向?yàn)樽酝庀蚶镆苿?。這時，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即要訪問的磁道在當(dāng)前位置內(nèi)距離最近者，這樣，磁頭又逐步地從外向里移動，直至再無更里面的磁道要訪問，從而避免了出現(xiàn)“饑餓”現(xiàn)象。由于在這種算法中磁頭移動的規(guī)律頗似電梯的運(yùn)行，因而又常稱之為電梯調(diào)度算法。我們使用語句printf("請選擇移動臂初始方向(1增加0減小)：");來實(shí)現(xiàn)另一個功能，用戶可以選擇相對當(dāng)前磁道位置增加或者減少的方向移動，其中用1代表向上移動，0代表向下移動。從而使功能更加強(qiáng)大。程序設(shè)計流程圖為：輸入各磁道號和當(dāng)前磁道號start輸入各磁道號和當(dāng)前磁道號startp[i]>=start將比當(dāng)前磁道號大的放入max[max_len++]=p[i]將比當(dāng)前磁道號小的放入min[min_len++]=p[i]移動臂初始方向case1:將磁道號從小到大排序case0:將磁道號從小到大排序?qū)⒈犬?dāng)前磁道號大的磁道按順序賦給臨時序列temp[i]=max[i]將比當(dāng)前磁道號小的磁道接著按順序賦給臨時序列temp[max_len++]=min[i]磁頭移動總距離sum+=abss(temp[i]-start)輸出平均尋道長度sum/num將比當(dāng)前磁道號小的磁道按順序賦給臨時序列temp[i]=min[i]將比當(dāng)前磁道號大的磁道接著按順序賦給臨時序列temp[min_len++]=max[i]圖2.3.2.3我們通過語句for(i=0;i<max_len;i++)temp[i]=max[i];for(i=0;i<min_len;i++)temp[max_len++]=min[i]; for(i=0;i<num;i++){sum+=abss(temp[i]-start); start=temp[i];}來實(shí)現(xiàn)向增加方向移動功能。與此相同我們通過語句for(i=0;i<min_len;i++)temp[i]=min[i]; for(i=0;i<max_len;i++)temp[min_len++]=max[i]; for(i=0;i<num;i++){sum+=fabs(temp[i]-start); start=temp[i];}來實(shí)現(xiàn)向減小方向移動功能。電梯調(diào)度算法既能獲得較好的尋道性能，又能防止“饑餓”現(xiàn)象，故被廣泛用于大，中，小型機(jī)器和網(wǎng)絡(luò)中的磁盤調(diào)度，但是也存在這樣的問題：當(dāng)磁頭剛從里向外移動而越過了某一磁道時，恰好又有一進(jìn)程請求訪問此磁道，這時，該進(jìn)程必須等待，待磁頭繼續(xù)從里向外，然后再從外向里掃描完所有要訪問的磁道后，才處理該進(jìn)程的請求，致使該進(jìn)程的請求被大大地推遲。2.3.2.4保存文件我們通過程序fp=fopen("cidao.txt","a");if(fp==NULL)printf("文件打不開！\n");else{fprintf(fp,"%s\n",p);for(i=0;i<totalnum;i++) {if(i)fprintf(fp,"->");fprintf(fp,"%d",file[i])；｝}來實(shí)現(xiàn)保存功能。我們可以將運(yùn)行的結(jié)果存儲到記事本中，方便快捷。2.4

實(shí)驗(yàn)、調(diào)試及測試結(jié)果與分析。本程序可算是經(jīng)歷了一番周折，最后總算調(diào)試成功。下面我來介紹一下本程序的運(yùn)行方法以及分析運(yùn)行結(jié)果。為了實(shí)現(xiàn)磁盤調(diào)度，我們設(shè)計了3種算法。另外增加了保存文件功能。如圖所示：圖2.4.1我們程序的主菜單，我們可以通過提示選擇我們想要的相關(guān)算法圖2.4.2展示出選擇1先來先服務(wù)算法的執(zhí)行結(jié)果，屏幕展示出最短尋道時間優(yōu)先順序，以及移動的總道數(shù)，平均尋道長度，還有提出詢問，是否保存文件。圖2.4.3展示出選擇2最短尋道時間優(yōu)先算法的執(zhí)行結(jié)果，屏幕展示出最短尋道時間優(yōu)先順序，以及移動的總道數(shù)，平均尋道長度，還有提出詢問，是否保存文件。圖2.4.4展示出選擇3電梯調(diào)度算法的執(zhí)行結(jié)果，程序給出提示，選擇0程序?qū)⑾蛳鄬Ξ?dāng)前磁道位置減少的方向移動，屏幕上顯示出最短尋道時間優(yōu)先順序，以及移動的總道數(shù)，平均尋道長度，還有提出詢問，是否保存文件。圖2.4.5展示出選擇3電梯調(diào)度算法的執(zhí)行結(jié)果，程序給出提示，選擇1程序?qū)⑾蛳鄬Ξ?dāng)前磁道位置增加的方向移動，屏幕上顯示出最短尋道時間優(yōu)先順序，以及移動的總道數(shù)，平均尋道長度，還有提出詢問，是否保存文件。3

結(jié)論這個程序基本完成了磁盤調(diào)度算法設(shè)計的目的與要求。不過其中也有一些不足之處，例如算法有點(diǎn)麻煩，有些句子不是很能理解。但是通過上網(wǎng)查找資料，去圖書館借閱相關(guān)書籍解決了這些不足之處。由于關(guān)于磁盤調(diào)度的那部分，理論內(nèi)容很少，所以，這次課程設(shè)計，我主要將重點(diǎn)放在實(shí)踐中，也就是說，我在本次實(shí)驗(yàn)中，我是實(shí)現(xiàn)了3種磁盤調(diào)度算法。我這么做的原因有三個：一是關(guān)于磁盤調(diào)度的理論性問題很少，如果僅僅模擬一下磁盤調(diào)度，那么實(shí)在是對不起辛辛苦苦教我們一學(xué)期的老師。二是既然我們從課堂上學(xué)到了理論知識，那么就應(yīng)該應(yīng)用于實(shí)踐，如果僅僅演示一下課堂上講的理論或算法，那么實(shí)在是紙上談兵。畢竟，程序員做的程序是給客戶用的，并不是每個客戶都精通計算機(jī)，如何完成客戶要求的程序，并且客戶使用起來方便，那么才可以說是一個比較不錯的程序。三是作為我們這些計算機(jī)專業(yè)的學(xué)生，遲早將面臨著畢業(yè)設(shè)計，到時候我們總不能編寫一些算法來敷衍吧，所以我認(rèn)為在平時的課程設(shè)計中不但要真心真意地去做，更為重要的是程序使用并且使用簡便，對于用戶來說，重要的不是算法，而是程序的結(jié)果。作為一個計算機(jī)專業(yè)的學(xué)生，在課堂上要把基本思想熟練掌握，課后在寫程序的時候要把思想封裝到程序當(dāng)中，充分體現(xiàn)它的應(yīng)用價值。本次課程設(shè)計，我利用調(diào)度算法完成了磁盤的調(diào)度，充分利用了課堂上講的理論知識，完成了本次設(shè)計。至于功能嗎，很單一，只不過是演示了一下3種最基本的磁盤調(diào)度算法，雖然界面不漂亮，尚且不完整，但是通過這次課程設(shè)計使我懂得了如何完成磁盤的調(diào)度。程序最大的不足就是界面不漂亮，，我的設(shè)想是：為程序添加一些圖像，并設(shè)計背景音樂。因?yàn)樵韱栴}已經(jīng)懂了，所以我相信利用管道能夠?qū)崿F(xiàn)更強(qiáng)大功能的軟件。4

參考文獻(xiàn)

[1]張堯?qū)W。計算機(jī)操作系統(tǒng)教程。出版地：清華大學(xué)出版[2]任愛華。操作系統(tǒng)實(shí)用教程。出版地：清華大學(xué)出版[3]周蘇。操作系統(tǒng)原理實(shí)驗(yàn)。出版地：科學(xué)出版社[4]張堯?qū)W、史美林。計算機(jī)操作系統(tǒng)教程（第2版）。出版地：清華大學(xué)出版社[5]曾平、李春葆。操作系統(tǒng)習(xí)題與解析.出版地：清華大學(xué)出版社[6]張堯?qū)W、史美林。操作系統(tǒng)系統(tǒng)教程（第2版）習(xí)題解答與實(shí)驗(yàn)指導(dǎo).出版地：清華大學(xué)出版社5

附錄

#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>#defineM100intfile[M],total,totalnum,xuan;voidprint(int*p,intnum)//輸出優(yōu)先順序{inti;printf("短尋道時間優(yōu)先順序是:"); for(i=0;i<num;i++){ if(i)printf("->");printf("%d",p[i]);file[i]=p[i]; } printf("\n");}intabss(inta)//絕對值函數(shù){ if(a<0)a*=-1;returna;}voidfcfs(int*p,intnum,intstart)//先來先服務(wù)算法FCFS{inti;doublesum=0;for(i=0;i<num;i++) {sum+=abss(p[i]-start);start=p[i]; } print(p,num);total=(int)sum;printf("移動的總道數(shù)：%.0lf\n",sum);printf("平均尋道長度:%lf\n",sum/num);}voidsstf(int*p,intnum,intstart)//最短尋道時間優(yōu)先算法SSTF{ inti,j,min,current,temp[M],n,len=0;doublesum=0;n=num;for(i=0;i<n;i++) {min=abss(p[0]-start);for(j=0;j<num;j++) {if(min>=abss(p[j]-start)) { min=abss(p[j]-start);current=j; } }temp[len++]=p[current];sum+=fabs(p[current]-start);start=p[current]; for(j=current+1;j<num;j++)p[j-1]=p[j];num--; }total=(int)sum;print(temp,n);printf("移動的總道數(shù)：%.0lf\n",sum);printf("平均尋道長度:%lf\n",sum/n);}intcmp1(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}intcmp2(constvoid*a,constvoid*b){return*(int*)b-*(int*)a;}voidscan(int*p,intnum,intstart)//電梯調(diào)度算法(掃描算法SCAN){ inti,temp[M],max[M],min[M],max_len,min_len;doublesum=0;max_len=min_len=0; for(i=0;i<num;i++){ if(p[i]>=start)max[max_len++]=p[i]; elsemin[min_len++]=p[i];} while(1) { printf("請選擇移動臂初始方向(1增加0減小)："); scanf("%d",&xuan); if(xuan==1) { qsort(max,max_len,sizeof(max[0]),cmp1); qsort(min,min_len,sizeof(min[0]),cmp2); for(i=0;i<max_len;i++) temp[i]=max[i]; for(i=0;i<min_len;i++) temp[max_len++]=min[i]; for(i=0;i<num;i++) { sum+=abss(temp[i]-start); start=temp[i]; } total=(int)sum; print(temp,num); printf("移動的總道數(shù)：%.0lf\n",sum); printf("平均尋道長度:%lf\n",sum/num); break; } elseif(xuan==0) { qsort(max,max_len,sizeof(max[0]),cmp1); qsort(min,min_len,sizeof(min[0]),cmp2); for(i=0;i<min_len;i++) temp[i]=min[i]; for(i=0;i<max_len;i++) temp[min_len++]=max[i]; for(i=0;i<num;i++) { sum+=abss(temp[i]-start); start=temp[i]; } total=(int)sum; print(temp,num); printf("移動的總道數(shù)：%.0lf\n",sum);+ printf("平均尋道長度:%lf\n",sum/num); break; } else { printf("選擇錯誤請重新選擇?。?！\n"); continue; } }}voidsave(char*p)//保存文件{FILE*fp;inti;fp=fopen("cidao.txt","a"); if(fp==NULL)printf("文件打不開！\n");else{fprintf(fp,"%s\n",p);for(i=0;i<totalnum;i++) { if(i)fprintf(fp,"->");fprintf(fp,"%d",file[i]); }fprintf(fp,"\n");fprintf(fp,"移動的總道數(shù)：%d\n",total);fprintf(fp,"平均尋道長度：%lf\n\n",total*1.0/totalnum);printf("保存文件成功！\n");}}intmain(){intnode[M],num,i,start,node2[M];charc[M],str[M],choose[M]; printf("/*****************磁盤調(diào)度算法******************/\n");printf("請輸入磁道個數(shù)：");scanf("%d",&num);totalnum=num;printf("請輸入各磁道號："); for(i=0;i<num;i++) {scanf("%d",&node[i]); node2[i]=node[i]; } printf("請輸入當(dāng)前磁道號：");scanf("%d",&start); printf("/*********************菜單**********************/\n");printf("**\n");printf("*1、先來先服務(wù)算法FCFS*\n");printf("*2、最短尋道時間優(yōu)先算法SSTF*\n");printf("*3、電梯調(diào)度算法(掃描算法SCAN)*\n");printf("*0、退出*\n");printf("**\n");printf("/***********************************************/\n"); remove("cidao.txt");//如果文件已經(jīng)存在刪除 while(1){printf("請選擇:");