SCAN磁盤調(diào)度算法.doc

哈爾濱理工大學課程設計（操作系統(tǒng)） 題目： SCAN磁盤調(diào)度算法 學 院： 計算機科學與技術學院 班級： 計算機系10-8班 姓名：曾現(xiàn)坤 1004010828 指導教師：高雪瑤 系主任： 林克正 2013年03月01日 目 錄1.SCAN磁盤調(diào)度算法課程設計11.1 題目分析11.2 數(shù)據(jù)結(jié)構(gòu)11.3 流程圖31.4 實現(xiàn)技術31.5 設計結(jié)論和心得3 1.6 源代碼.32 Linux代碼分析122.1 功能說明142.2 接口說明1142.3 局部數(shù)據(jù)結(jié)構(gòu)1142.4 流程圖152.5 以實例說明運行過程16第1章- 16-哈爾濱理工大學課程設計報告1.SCAN磁盤調(diào)度算法課程設計1.1 題目分析本課程設計的目的是通過設計一個磁盤調(diào)度模擬系統(tǒng)，從而使磁盤調(diào)度算法更加形象化，容易使人理解，使磁盤調(diào)度的特點更簡單明了，能使使用者加深對先來先服務算法、最短尋道時間優(yōu)先算法、掃描算法以及循環(huán)掃描算法等磁盤調(diào)度算法的理解。此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。1.2 數(shù)據(jù)結(jié)構(gòu)SCAN磁盤調(diào)度算法問題中涉及的數(shù)據(jù)結(jié)構(gòu)包括手動輸入磁道的信號量、選擇調(diào)度算法的信號量、SCAN調(diào)度算法的信號量、顯示運行結(jié)果的信號量等。用偽代碼表示如下：int scan(Linklist L,int Current)LNode *p,*q,*s;float sum=0;if(L-next!=NULL)p=L-next;while(p-datanext;printf(掃描算法順序是:);for(q=p;q!=NULL;q=q-next)/輸出大于當前磁道號的數(shù)printf(%d ,q-data);sum+=abs(Current-q-data);Current=q-data;for(s=p-prior;s!=NULL;s=s-prior)/磁臂換向，自外向里移動，依次輸出p指針之前的數(shù)據(jù)printf(%d ,s-data);sum+=abs(Current-s-data);Current=s-data;printf(n);printf(平均尋道長度為:%.1fn,sum/i*1.0);return 0;1.3 流程圖開始手動輸入磁道選擇調(diào)度算法SCAN算法顯示運行結(jié)果結(jié)束1.4 實現(xiàn)技術為實現(xiàn)上述設計，采用C+語言，VS2008開發(fā)環(huán)境。具體采用的技術如下：（1） 白盒測試技術白盒測試也稱結(jié)構(gòu)測試或邏輯驅(qū)動測試，它是按照程序內(nèi)部的結(jié)構(gòu)測試程序，通過測試來檢測產(chǎn)品內(nèi)部動作是否按照設計規(guī)格說明書的規(guī)定正常進行，檢驗程序中的每條通路是否都能按預定要求正確工作。 這一方法是把測試對象看作一個打開的盒子，測試人員依據(jù)程序內(nèi)部邏輯結(jié)構(gòu)相關信息，設計或選擇測試用例，對程序所有邏輯路徑進行測試，通過在不同點檢查程序的狀態(tài)，確定實際的狀態(tài)是否與預期的狀態(tài)一致。 （2） 集成測試技術集成測試，也叫組裝測試或聯(lián)合測試。在單元測試的基礎上，將所有模塊按照設計要求（如根據(jù)結(jié)構(gòu)圖組裝成為子系統(tǒng)或系統(tǒng)，進行集成測試。實踐表明，一些模塊雖然能夠單獨地工作，但并不能保證連接起來也能正常的工作。程序在某些局部反映不出來的問題，在全局上很可能暴露出來，影響功能的實現(xiàn)。 實現(xiàn)步驟如下：（1）開始界面 （2） 算法選擇界面 （3） 運行結(jié)果如下： 1.4 設計結(jié)論和心得通過課程設計得到如下結(jié)論：（1）掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。（2）此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。有如下幾點心得體會：（1）軟件結(jié)構(gòu)合理，自需求分析開始，采取自頂向下逐步求精的方法，將問題逐步分解為各個模塊，各模塊間通過指定類型參數(shù)進行數(shù)據(jù)傳遞，保證程序正確，結(jié)構(gòu)清晰。（2）控制變量對比，各磁盤調(diào)度算法均可對同一組隨機磁道進行調(diào)度，但并不會改變隨機磁道的內(nèi)容，保證了平均尋道長度對比的真實性，有效性。1.6 源代碼#include #include #include #include typedef struct LNode /雙鏈表結(jié)點定義int data;struct LNode *next;struct LNode *prior;LNode,*Linklist;int i=0;LNode * CreatList_L(Linklist L) /創(chuàng)建帶頭結(jié)點雙鏈表，滿足用戶從鍵盤輸入數(shù)字LNode *p,*q; /定義尾結(jié)點q，L=(Linklist)malloc(sizeof(LNode);/為結(jié)點L動態(tài)分配內(nèi)存，建立鏈表頭結(jié)點L-next=NULL;int temp;printf(*n);printf( 請輸入磁道數(shù)(以0結(jié)束): n);printf(*n); scanf(%d,&temp);while(temp!=0)q=(Linklist)malloc(sizeof(LNode);q-data=temp;if(L-next=NULL)L-next=q;q-prior=NULL;else /采用尾插法將q插入L尾部并使p指向qp-next=q;q-prior=p;q-next=NULL;p=q;scanf(%d,&temp);/?i+;return L;int scan(Linklist L,int Current)LNode *p,*q,*s;float sum=0;if(L-next!=NULL)p=L-next;while(p-datanext;printf(掃描算法順序是:);for(q=p;q!=NULL;q=q-next)/輸出大于當前磁道號的數(shù)printf(%d ,q-data);sum+=abs(Current-q-data);Current=q-data;for(s=p-prior;s!=NULL;s=s-prior)/磁臂換向，自外向里移動，依次輸出p指針之前的數(shù)據(jù)printf(%d ,s-data);sum+=abs(Current-s-data);Current=s-data;printf(n);printf(平均尋道長度為:%.1fn,sum/i*1.0);return 0;int main()int Current;Linklist L=NULL;LNode *p;printf(請輸入當前的磁道號:);scanf(%d,&Current);p=CreatList_L(L);int temp;printf(*n);printf(1.掃描算法(SCAN)n);printf( 2.退出n);printf(*n);printf(請選擇:);scanf(%d,&temp);while(temp!=2)switch(temp)case 1:scan(p,Current); break;printf(退出函數(shù)，謝謝使用);return 0;2 Linux代碼分析/ 復制進程的頁目錄頁表。int copy_page_tables(unsigned long from,unsigned long to,long size) unsigned long * from_page_table; unsigned long * to_page_table; unsigned long this_page; unsigned long * from_dir, * to_dir; unsigned long nr;/ 源地址和目的地址都需要是4Mb 的倍數(shù)。否則出錯，死機。 if (from&0x3fffff) | (to&0x3fffff) panic(copy_page_tables called with wrong alignment);/ 取得源地址和目的地址的目錄項(from_dir 和to_dir)。 from_dir = (unsigned long *) (from20) & 0xffc); /* _pg_dir = 0 */ to_dir = (unsigned long *) (to20) & 0xffc);/ 計算要復制的內(nèi)存塊占用的頁表數(shù)（也即目錄項數(shù)）。 size = (unsigned) (size+0x3fffff) 22;/ 下面開始對每個占用的頁表依次進行復制操作。 for( ; size-0 ; from_dir+,to_dir+) / 如果目的目錄項指定的頁表已經(jīng)存在(P=1)，則出錯，死機。 if (1 & *to_dir) panic(copy_page_tables: already exist);/ 如果此源目錄項未被使用，則不用復制對應頁表，跳過。 if (!(1 & *from_dir) continue;/ 取當前源目錄項中頁表的地址from_page_table。 from_page_table = (unsigned long *) (0xfffff000 & *from_dir);/ 為目的頁表取一頁空閑內(nèi)存，如果返回是0 則說明沒有申請到空閑內(nèi)存頁面。返回值=-1，退出。 if (!(to_page_table = (unsigned long *) get_free_page() return -1; /* Out of memory, see freeing */ 設置目的目錄項信息。7 是標志信息，表示(Usr, R/W, Present)。 *to_dir = (unsigned long) to_page_table) | 7;/ 針對當前處理的頁表，設置需復制的頁面數(shù)。如果是在內(nèi)核空間，則僅需復制頭160 頁，否則需要/ 復制1 個頁表中的所有1024 頁面。 nr = (from=0)?0xA0:1024;/ 對于當前頁表，開始復制指定數(shù)目nr 個內(nèi)存頁面。 for ( ; nr- 0 ; from_page_table+,to_page_table+) this_page = *from_page_table; / 取源頁表項內(nèi)容。 if (!(1 & this_page) / 如果當前源頁面沒有使用，則不用復制。 continue;/ 復位頁表項中R/W 標志(置0)。(如果U/S 位是0，則R/W 就沒有作用。如果U/S 是1，而R/W 是0，/ 那么運行在用戶層的代碼就只能讀頁面。如果U/S 和R/W 都置位，則就有寫的權(quán)限。) this_page &= 2; *to_page_table = this_page; / 將該頁表項復制到目的頁表中。/ 如果該頁表項所指頁面的地址在1M 以上，則需要設置內(nèi)存頁面映射數(shù)組mem_map，于是計算/ 頁面號，并以它為索引在頁面映射數(shù)組相應項中增加引用次數(shù)。 if (this_page LOW_MEM) *from_page_table = this_page; / 令源頁表項也只讀?。 this_page -= LOW_MEM; this_page = 12; mem_mapthis_page+; invalidate(); / 刷新頁變換高速緩沖。 return 0; 2.1 功能說明復制進程的頁目錄頁表2.2 接口說明本程序的輸入?yún)?shù)為：unsigned long from,unsigned long to,long size輸出結(jié)果為：將進程的頁目錄頁表復制2.3 局部數(shù)據(jù)結(jié)構(gòu)本程序共有5個局部變量及數(shù)據(jù)結(jié)構(gòu)，其類型定義及語義如下：unsign