CSCAN磁盤調(diào)度算法 操作系統(tǒng)課程設(shè)計(jì)報(bào)告

《CSCAN磁盤調(diào)度算法 操作系統(tǒng)課程設(shè)計(jì)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《CSCAN磁盤調(diào)度算法 操作系統(tǒng)課程設(shè)計(jì)報(bào)告（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、哈爾濱理工大學(xué)課程設(shè)計(jì)（計(jì)算機(jī)操作系統(tǒng)）題目： CSCAN磁盤調(diào)度算法 班級(jí)： 姓名：指導(dǎo)教師：系主任： 2014年03月01日 目 錄1CSCAN磁盤調(diào)度算法問題課程設(shè)計(jì)11.1 題目分析11.2 數(shù)據(jù)結(jié)構(gòu)11.3 流程圖11.4 實(shí)現(xiàn)技術(shù)21.5 設(shè)計(jì)結(jié)論和心得22 Linux代碼分析42.1 功能說明42.2 接口說明42.3 局部數(shù)據(jù)結(jié)構(gòu)42.4 流程圖42.5 以實(shí)例說明運(yùn)行過程5第1章- 15-哈爾濱理工大學(xué)課程設(shè)計(jì)報(bào)告1CSCAN磁盤調(diào)度算法問題課程設(shè)計(jì)1.1 分析題目 將queuen進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queuen的位置，然后在此位置按給

2、定的方向遍歷queuen，當(dāng)?shù)蓝它c(diǎn)（queue0或queuen-1）時(shí)，反向到另一端點(diǎn)再以此方向進(jìn)行遍歷，直到queuen中所有都調(diào)度完。當(dāng)調(diào)度磁道不在queue端點(diǎn)時(shí)，總的尋道長(zhǎng)度為為前一個(gè)磁道與后一個(gè)磁道差值的累加，當(dāng)?shù)竭_(dá)端點(diǎn)且queuen未全調(diào)度時(shí)，總尋道長(zhǎng)度加上端點(diǎn)值再加上磁盤磁道總長(zhǎng)度，再加上下一個(gè)調(diào)度磁道的值，再按前面的算法進(jìn)行，直到磁道全部都調(diào)度完畢，得到總的尋道長(zhǎng)度，除以n得到平均尋道長(zhǎng)度。1.2 數(shù)據(jù)結(jié)構(gòu)Hand:當(dāng)前磁道號(hào); DiscLine10:隨機(jī)生成的磁道號(hào); void SetDI(int DiscL)生成隨機(jī)磁道號(hào)算法; void CopyL(int Sour,in

3、t Dist ,int x) 數(shù)組Sour復(fù)制到數(shù)組Dist復(fù)制到x個(gè)數(shù)四詳細(xì)設(shè)計(jì); void DelInq(int Sour,int x,int y) 數(shù)組Sour把x位置的數(shù)刪除,x后的數(shù)組元素向前挪一位. void PaiXu()尋道長(zhǎng)度由低到高排序void CSCAN(int Han,int DiscL)循環(huán)掃描算法(CSCAN)1.3流程圖1.4實(shí)現(xiàn)技術(shù)為實(shí)現(xiàn)上述設(shè)計(jì)，采用C+語(yǔ)言，VS2008開發(fā)環(huán)境。具體采用的技術(shù)如下：循環(huán)掃描算法實(shí)現(xiàn)步驟如下：輸入總磁道數(shù)（你可以輸入200），點(diǎn)確定，進(jìn)入第二個(gè)界面，再輸入磁盤調(diào)度序列個(gè)數(shù)（你可以輸入5），然后點(diǎn)確定。依次輸入5個(gè)值，再輸入正在

4、調(diào)入的磁道，選擇磁盤調(diào)度算法1 2 中的任意一個(gè)，若選擇1后確認(rèn)，選擇磁道走向1.2若選擇1，點(diǎn)確定，先輸出排序后的磁盤序列：（13 20 89 113 189 ），再輸出調(diào)度序列為：（89 20 13 189 113 89）并且求出了總尋道長(zhǎng)度為352，平均尋道長(zhǎng)度為70.4。運(yùn)行結(jié)果如下：1.5設(shè)計(jì)結(jié)論和心得通過課程設(shè)計(jì)得到如下結(jié)論：本次實(shí)驗(yàn)首先要了解磁盤調(diào)度方法的工作原理。在課程設(shè)計(jì)前的準(zhǔn)備工作時(shí)，先把這部分工作做完了。在設(shè)計(jì)總的程序框架的時(shí)候，要注意各功能模塊的位置，盡量做到簡(jiǎn)潔、有序；各功能模塊與主程序要正確銜接。 有如下幾點(diǎn)心得體會(huì)：至此，計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)算法已經(jīng)完成。此次設(shè)

5、計(jì)基本完成了所規(guī)定的功能，但由于這次設(shè)計(jì)的時(shí)間比較倉(cāng)促，其中不免會(huì)有些紕漏，比如在程序的實(shí)現(xiàn)上還不夠嚴(yán)謹(jǐn)，出錯(cuò)處理不夠完善等多方面問題，這些都有進(jìn)一步改善。由于平時(shí)上課不是很認(rèn)真許多概念沒有理解清楚，導(dǎo)致在做設(shè)計(jì)時(shí)有點(diǎn)無從下手的感覺，只好邊實(shí)驗(yàn)邊看書直到弄懂概念后才開始做設(shè)計(jì)導(dǎo)致時(shí)間有點(diǎn)緊張，最終在同學(xué)和老師的指導(dǎo)下我完成了設(shè)計(jì)，此設(shè)計(jì)基本能夠?qū)崿F(xiàn)規(guī)定的要求但是還是不夠完善，很多東西做的不夠好，程序不夠完善和嚴(yán)謹(jǐn)。此次課程設(shè)計(jì)中我學(xué)到了很多東西，無論在理論上還是實(shí)踐中，都得到不少的提高，這對(duì)于我以后的工作和學(xué)習(xí)都有一種巨大的幫助。#include#include#includeusing na

6、mespace std;void menu() cout*菜單*endl;cout*1、循環(huán)掃描算法 (CSCAN) *endl; cout*2、退出 *endl; cout*endl;/*=初始化序列=*/void init(int queue,int queue_copy,int n) int i; for(i=0;in;+i) queuei=queue_copyi;/對(duì)當(dāng)前正在執(zhí)行的磁道號(hào)進(jìn)行定位，返回磁道號(hào)小于當(dāng)前磁道中最大的一個(gè)int fix ( int queue, int n, int headstarts) int i =0; while ( iqueuei ) i+; if

7、( in-1 ) return n-1; /當(dāng)前磁道號(hào)大于磁盤請(qǐng)求序列中的所有磁道 if ( i=0 ) return -1; /當(dāng)前磁道號(hào)小于磁盤請(qǐng)求序列中的所有磁道 else return i-1; /返回小于當(dāng)前磁道號(hào)中最大的一個(gè)/*=使用冒泡算法從小到大排序=*/int *bubble(int queue,int m) int i,j;int temp;for( i=0; im;i+)for(j=i+1;j queuej) temp=queuei; queuei=queuej; queuej=temp; cout排序后的磁盤序列為：; for( i=0;im;i+) /輸出排序結(jié)果 c

8、outqueuei ; coutendl; return queue;/n表示調(diào)度磁盤請(qǐng)求序列queue的長(zhǎng)度，diskrode表示磁盤磁道的個(gè)數(shù)，headstarts表示目前正在調(diào)度的磁道； void CSCAN(int queue,int n,int diskrode,int headstarts) int direction,i,fixi; cout*以下是CSCAN調(diào)度算法*endl; cout請(qǐng)輸入磁頭的走向：1.由內(nèi)向外 2.由外向內(nèi)endl; coutdirection; int count=0; /count表示磁道移動(dòng)的長(zhǎng)度 *bubble(queue,n); fixi=fi

9、x(queue,n,headstarts); cout調(diào)度序列為: headstarts ; if(fixi=-1) /headstarts比請(qǐng)求調(diào)度序列都小 if(direction=1) /從大到小 count +=queuefixi+1-queue0; /反向再反向 headstarts =queuen-1; coutheadstarts-1;-i) coutqueuei ; count +=headstarts-queuei; headstarts=queuei; if(direction=2) /從小到大 for(i=0;in;+i) coutqueuei-1;-i) coutque

10、uei ; count +=headstarts-queuei; headstarts=queuei; if( direction=2) /從小到大 coutqueue0 ; for(i=1;in;+i) coutqueuei-1;i-) coutqueuei ; count +=headstarts-queuei; headstarts=queuei; count = count+(queuen-1-queue0); /磁頭走到0時(shí)再反向. headstarts=queuen-1; coutheadstartsfixi;i-) coutqueuei ; count +=headstarts-

11、queuei; headstarts =queuei; if(direction=2) /從小到大 for( i=fixi+1;in;i+) if (direction=2) /從小到大 coutqueuei ; count +=queuei-headstarts; headstarts =queuei; count +=queuen-1-queue0; /磁頭走到n-1再反向走. headstarts =queue0; coutheadstarts ; for(i=1;ifixi+1;i+) coutqueuei ; count +=queuei-headstarts; headstarts

12、=queuei; coutendl; cout總的尋道長(zhǎng)度為: countendl; cout平均尋道長(zhǎng)度為: float(count)/nendl;int main() int n, i, diskrode, headstarts; /n表示調(diào)度磁盤請(qǐng)求序列queue的長(zhǎng)度，diskrode表示磁盤磁道的個(gè)數(shù)，headstarts表示目前正在調(diào)度的磁道； cout請(qǐng)輸入磁盤的總磁道數(shù): diskrode; cout請(qǐng)輸入磁盤調(diào)度請(qǐng)求序列個(gè)數(shù):n; int *queue; queue =(int*)malloc(n*sizeof(int); /給queue數(shù)組分配空間. int *queue_

13、copy; queue_copy =(int*)malloc(n*sizeof(int); cout請(qǐng)依次輸入該序列的值:endl; for ( i=0;iqueuei; for ( i=0;in;i+) queue_copyi =queuei; coutheadstarts; int menux; menu(); coutmenux; while (menux !=0) if (menux =1) CSCAN(queue,n,diskrode,headstarts); if (menux =2) cout程序結(jié)束,謝謝使用！endl; coutendl; init(queue,queue_c

14、opy,n); menu(); coutmenux; coutendl; 2 Linux代碼分析為了進(jìn)一步了解操作系統(tǒng)內(nèi)核，學(xué)習(xí)了Linux操作系統(tǒng)的段頁(yè)式存儲(chǔ)管理程序虛擬內(nèi)存映射管理部分，部分源代碼如下：struct vm_structunsigned long flags; void *addr; /*虛擬內(nèi)存塊的其始地址 */unsigned long size; /*虛擬內(nèi)存塊的長(zhǎng)度*/struct vm_struct *next; /*下一個(gè)虛擬內(nèi)存塊*/struct vm_area_struct struct mm_struct * vm_mm; /*指向該虛存段所屬進(jìn)程的mm_s

15、truct */ unsigned long vm_start; /*虛擬內(nèi)存開始地址 */ unsigned long vm_end; /*虛擬內(nèi)存結(jié)束地址*/ struct vm_area_struct vm_next; unsigned short vm_flags; /*本vma塊的屬性標(biāo)志位*/ short vm_avl_height; struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三項(xiàng)用于對(duì)AVL樹操作*/ struct vm_operations_struct * vm

16、_ops; /*指向?qū)ma塊操作的結(jié)構(gòu)體指針*/ unsigned long vm_offset; struct file * vm_file; /*指向文件的inode結(jié)構(gòu)體或NULL */ unsigned long vm_pte;static inline unsigned long do_mmap （struct file *file, unsigned long addr,unsigned long len, unsigned long prot,unsigned long flag, unsigned long offset） unsigned long ret = -EINVA

17、L; if (offset + PAGE_ALIGN(len) PAGE_SHIFT）; out: return ret; 2.1 功能說明這一段程序的主要功能為：（1）進(jìn)程對(duì)內(nèi)存區(qū)域的分配最終多會(huì)歸結(jié)到do_mmap（）函數(shù)上來，同樣釋放一個(gè)內(nèi)存區(qū)域使用函數(shù)do_ummap（）,它會(huì)銷毀對(duì)應(yīng)的內(nèi)存區(qū)域。（這里do_ummap暫不做說明）（2）Linux使用內(nèi)核函數(shù)do_mmap（）完成可執(zhí)行映像等向虛擬區(qū)域的映射，由它建立有關(guān)的虛存區(qū)域，并指定虛存區(qū)域的開始地址、虛存大小以及屬性等。2.2 接口說明本程序的輸入?yún)?shù)為：file：表示要映射的文件。offset：文件內(nèi)的偏移量，因?yàn)槲覀儾⒉皇窍?/p>

18、子全部映射一個(gè)文件，可能只是映射文件的一部分，offset就表示那部分的起始位置。len：要映射的文件部分的長(zhǎng)度。addr：虛擬空間的一個(gè)地址，表示從這個(gè)地址開始查找一個(gè)空閑的虛擬區(qū)。prot：指定對(duì)這個(gè)虛擬區(qū)的存取權(quán)限。輸出結(jié)果為：該段程序返回的應(yīng)為long類型的數(shù)據(jù)，為經(jīng)過do_mmap()映射處理后的虛存區(qū)域的起始地址。否則則返回MAP_FAILED(1)。2.3 局部數(shù)據(jù)結(jié)構(gòu)本程序共有4個(gè)局部變量及數(shù)據(jù)結(jié)構(gòu)，其類型定義及語(yǔ)義如下：struct mm_struct/mm_struct結(jié)構(gòu)包含了用戶進(jìn)程與存儲(chǔ)有關(guān)的信息struct vm_area_struct mmap; /*指向虛擬內(nèi)存

19、段雙向鏈表指針 */struct vm_area_struct *mmap_avl;/*指向虛擬內(nèi)存段AVL樹指針 */pgd_t *pgd; /*進(jìn)程頁(yè)目錄起始地址*/int map_count; /*此進(jìn)程所用虛擬內(nèi)存的塊數(shù)*/unsigned long start_code,end_code; /*進(jìn)程代碼段起始地址和結(jié)束地址*/unsigned long start_data,end_data;/*進(jìn)程數(shù)據(jù)段起始地址和結(jié)束地址*/unsigned long start_stack; /*進(jìn)程堆棧段起始地址*/unsigned long rss; /*進(jìn)程駐留在物理內(nèi)存的頁(yè)面總數(shù)*/st

20、ruct vm_struct/為虛擬內(nèi)存結(jié)構(gòu)體unsigned long flags; void *addr; /*虛擬內(nèi)存塊的其始地址 */unsigned long size; /*虛擬內(nèi)存塊的長(zhǎng)度*/struct vm_struct *next; /*下一個(gè)虛擬內(nèi)存塊*/struct vm_area_struct /虛擬內(nèi)存塊存儲(chǔ)結(jié)構(gòu)體 struct mm_struct * vm_mm; /*指向該虛存段所屬進(jìn)程的mm_struct */ unsigned long vm_start; /*虛擬內(nèi)存開始地址*/ unsigned long vm_end; /*虛擬內(nèi)存結(jié)束地址*/ str

21、uct vm_area_struct vm_next; unsigned short vm_flags; /*本vma塊的屬性標(biāo)志位*/ short vm_avl_height; struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三項(xiàng)用于對(duì)AVL樹操作 */struct vm_operations_struct * vm_ops; /*指向?qū)ma塊操作的結(jié)構(gòu)體指針 */ unsigned long vm_offset; struct file * vm_file; /*指向文件的ino

22、de結(jié)構(gòu)體或NULL */ unsigned long vm_pte;typedef struct page/頁(yè)存儲(chǔ)結(jié)構(gòu)struct list_head list; /*該頁(yè)根據(jù)不同用途掛到不同鏈表中 */struct page *next, *prev; /*前一個(gè)和下一個(gè)頁(yè) */unsigned long index; /*頁(yè)存放代碼或數(shù)據(jù)所屬文件的位移 */ struct inode *inode; /*該頁(yè)所屬文件的位移 */ atomic count; /*使用該頁(yè)的進(jìn)程數(shù)，0表示空閑 */ unsigned long age; /*頁(yè)年齡 */ 2.4 流程圖本程序的流程圖如圖2所示圖2程序流程圖2.5 以實(shí)例說明運(yùn)行過程當(dāng)有進(jìn)程到達(dá)時(shí)所用數(shù)據(jù)與指令存在于內(nèi)存中時(shí)，根據(jù)分析，將不進(jìn)行缺頁(yè)中斷，將建立虛存區(qū)域，并執(zhí)行do_mmap()，并返回起始地址。實(shí)際運(yùn)行結(jié)果如下：