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

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