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

哈爾濱理工大學(xué)課程設(shè)計（計算機操作系統(tǒng)）題目： CSCAN磁盤調(diào)度算法 班級： 姓名：指導(dǎo)教師：系主任： 2014年03月01日 目 錄1CSCAN磁盤調(diào)度算法問題課程設(shè)計11.1 題目分析11.2 數(shù)據(jù)結(jié)構(gòu)11.3 流程圖11.4 實現(xiàn)技術(shù)21.5 設(shè)計結(jié)論和心得22 Linux代碼分析42.1 功能說明42.2 接口說明42.3 局部數(shù)據(jù)結(jié)構(gòu)42.4 流程圖42.5 以實例說明運行過程5第1章- 15-哈爾濱理工大學(xué)課程設(shè)計報告1CSCAN磁盤調(diào)度算法問題課程設(shè)計1.1 分析題目 將queuen進行由小到大的排序，首先定位當前調(diào)度磁headstarts在queuen的位置，然后在此位置按給定的方向遍歷queuen，當?shù)蓝它c（queue0或queuen-1）時，反向到另一端點再以此方向進行遍歷，直到queuen中所有都調(diào)度完。當調(diào)度磁道不在queue端點時，總的尋道長度為為前一個磁道與后一個磁道差值的累加，當?shù)竭_端點且queuen未全調(diào)度時，總尋道長度加上端點值再加上磁盤磁道總長度，再加上下一個調(diào)度磁道的值，再按前面的算法進行，直到磁道全部都調(diào)度完畢，得到總的尋道長度，除以n得到平均尋道長度。1.2 數(shù)據(jù)結(jié)構(gòu)Hand:當前磁道號; DiscLine10:隨機生成的磁道號; void SetDI(int DiscL)生成隨機磁道號算法; void CopyL(int Sour,int Dist ,int x) 數(shù)組Sour復(fù)制到數(shù)組Dist復(fù)制到x個數(shù)四詳細設(shè)計; void DelInq(int Sour,int x,int y) 數(shù)組Sour把x位置的數(shù)刪除,x后的數(shù)組元素向前挪一位. void PaiXu()尋道長度由低到高排序void CSCAN(int Han,int DiscL)循環(huán)掃描算法(CSCAN)1.3流程圖1.4實現(xiàn)技術(shù)為實現(xiàn)上述設(shè)計，采用C+語言，VS2008開發(fā)環(huán)境。具體采用的技術(shù)如下：循環(huán)掃描算法實現(xiàn)步驟如下：輸入總磁道數(shù)（你可以輸入200），點確定，進入第二個界面，再輸入磁盤調(diào)度序列個數(shù)（你可以輸入5），然后點確定。依次輸入5個值，再輸入正在調(diào)入的磁道，選擇磁盤調(diào)度算法1 2 中的任意一個，若選擇1后確認，選擇磁道走向1.2若選擇1，點確定，先輸出排序后的磁盤序列：（13 20 89 113 189 ），再輸出調(diào)度序列為：（89 20 13 189 113 89）并且求出了總尋道長度為352，平均尋道長度為70.4。運行結(jié)果如下：1.5設(shè)計結(jié)論和心得通過課程設(shè)計得到如下結(jié)論：本次實驗首先要了解磁盤調(diào)度方法的工作原理。在課程設(shè)計前的準備工作時，先把這部分工作做完了。在設(shè)計總的程序框架的時候，要注意各功能模塊的位置，盡量做到簡潔、有序；各功能模塊與主程序要正確銜接。 有如下幾點心得體會：至此，計算機操作系統(tǒng)課程設(shè)計算法已經(jīng)完成。此次設(shè)計基本完成了所規(guī)定的功能，但由于這次設(shè)計的時間比較倉促，其中不免會有些紕漏，比如在程序的實現(xiàn)上還不夠嚴謹，出錯處理不夠完善等多方面問題，這些都有進一步改善。由于平時上課不是很認真許多概念沒有理解清楚，導(dǎo)致在做設(shè)計時有點無從下手的感覺，只好邊實驗邊看書直到弄懂概念后才開始做設(shè)計導(dǎo)致時間有點緊張，最終在同學(xué)和老師的指導(dǎo)下我完成了設(shè)計，此設(shè)計基本能夠?qū)崿F(xiàn)規(guī)定的要求但是還是不夠完善，很多東西做的不夠好，程序不夠完善和嚴謹。此次課程設(shè)計中我學(xué)到了很多東西，無論在理論上還是實踐中，都得到不少的提高，這對于我以后的工作和學(xué)習都有一種巨大的幫助。#include<iostream>#include<stdio.h>#include<stdlib.h>using namespace 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;i<n;+i) queuei=queue_copyi;/對當前正在執(zhí)行的磁道號進行定位，返回磁道號小于當前磁道中最大的一個int fix ( int queue, int n, int headstarts) int i =0; while ( i<n && headstarts>queuei ) i+; if ( i>n-1 ) return n-1; /當前磁道號大于磁盤請求序列中的所有磁道 if ( i=0 ) return -1; /當前磁道號小于磁盤請求序列中的所有磁道 else return i-1; /返回小于當前磁道號中最大的一個/*=使用冒泡算法從小到大排序=*/int *bubble(int queue,int m) int i,j;int temp;for( i=0; i<m;i+)for(j=i+1;j<m;j+) if( queuei > queuej) temp=queuei; queuei=queuej; queuej=temp; cout<<"排序后的磁盤序列為：" for( i=0;i<m;i+) /輸出排序結(jié)果 cout<<queuei<<" " cout<<endl; return queue;/n表示調(diào)度磁盤請求序列queue的長度，diskrode表示磁盤磁道的個數(shù)，headstarts表示目前正在調(diào)度的磁道； void CSCAN(int queue,int n,int diskrode,int headstarts) int direction,i,fixi; cout<<"*以下是CSCAN調(diào)度算法*"<<endl; cout<<"請輸入磁頭的走向：1.由內(nèi)向外 2.由外向內(nèi)"<<endl; cout<<"請輸入磁頭的走向: " cin>>direction; int count=0; /count表示磁道移動的長度 *bubble(queue,n); fixi=fix(queue,n,headstarts); cout<<"調(diào)度序列為: "<<headstarts<<" " if(fixi=-1) /headstarts比請求調(diào)度序列都小 if(direction=1) /從大到小 count +=queuefixi+1-queue0; /反向再反向 headstarts =queuen-1; cout<<headstarts<<" " for ( i=n-2;i>-1;-i) cout<<queuei<<" " count +=headstarts-queuei; headstarts=queuei; if(direction=2) /從小到大 for(i=0;i<n;+i) cout<<queuei<<" " count +=queuei-headstarts; headstarts=queuei; else if(fixi=n-1) /headstarts比請求調(diào)度序列都大 if(direction=1) /從大到小 for(i=n-1;i>-1;-i) cout<<queuei<<" " count +=headstarts-queuei; headstarts=queuei; if( direction=2) /從小到大 cout<<queue0<<" " for(i=1;i<n;+i) cout<<queuei<<" " count =count+(queuei-queuei-1); count +=headstarts-queue0; else if ( direction=1) /從大到小 for ( i=fixi;i>-1;i-) cout<<queuei<<" " count +=headstarts-queuei; headstarts=queuei; count = count+(queuen-1-queue0); /磁頭走到0時再反向. headstarts=queuen-1; cout<<headstarts<<" " for ( i=n-2;i>fixi;i-) cout<<queuei<<" " count +=headstarts-queuei; headstarts =queuei; if(direction=2) /從小到大 for( i=fixi+1;i<n;i+) if (direction=2) /從小到大 cout<<queuei<<" " count +=queuei-headstarts; headstarts =queuei; count +=queuen-1-queue0; /磁頭走到n-1再反向走. headstarts =queue0; cout<<headstarts<<" " for(i=1;i<fixi+1;i+) cout<<queuei<<" " count +=queuei-headstarts; headstarts=queuei; cout<<endl; cout<<"總的尋道長度為: "<<count<<endl; cout<<"平均尋道長度為: "<<float(count)/n<<endl;int main() int n, i, diskrode, headstarts; /n表示調(diào)度磁盤請求序列queue的長度，diskrode表示磁盤磁道的個數(shù)，headstarts表示目前正在調(diào)度的磁道； cout<<"請輸入磁盤的總磁道數(shù):"<<endl; cin>> diskrode; cout<<"請輸入磁盤調(diào)度請求序列個數(shù):"<<endl; cin>>n; int *queue; queue =(int*)malloc(n*sizeof(int); /給queue數(shù)組分配空間. int *queue_copy; queue_copy =(int*)malloc(n*sizeof(int); cout<<"請依次輸入該序列的值:"<<endl; for ( i=0;i<n;i+) cin>>queuei; for ( i=0;i<n;i+) queue_copyi =queuei; cout<<"請輸入正在調(diào)度的磁道: " cin>>headstarts; int menux; menu(); cout<<"請按菜單選擇，輸入相應(yīng)的數(shù)字: " cin>>menux; while (menux !=0) if (menux =1) CSCAN(queue,n,diskrode,headstarts); if (menux =2) cout<<"程序結(jié)束,謝謝使用！"<<endl; cout<<endl; init(queue,queue_copy,n); menu(); cout<<"請按菜單選擇，輸入相應(yīng)的數(shù)字: " cin>>menux; cout<<endl; 2 Linux代碼分析為了進一步了解操作系統(tǒng)內(nèi)核，學(xué)習了Linux操作系統(tǒng)的段頁式存儲管理程序虛擬內(nèi)存映射管理部分，部分源代碼如下：struct vm_structunsigned long flags; void *addr; /*虛擬內(nèi)存塊的其始地址 */unsigned long size; /*虛擬內(nèi)存塊的長度*/struct vm_struct *next; /*下一個虛擬內(nèi)存塊*/struct vm_area_struct struct mm_struct * vm_mm; /*指向該虛存段所屬進程的mm_struct */ unsigned long vm_start; /*虛擬內(nèi)存開始地址 */ unsigned long vm_end; /*虛擬內(nèi)存結(jié)束地址*/ struct vm_area_struct vm_next; unsigned short vm_flags; /*本vma塊的屬性標志位*/ short vm_avl_height; struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三項用于對AVL樹操作*/ struct vm_operations_struct * vm_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 = -EINVAL; if (offset + PAGE_ALIGN(len) < offset) goto out; if (! (offset & PAGE_MASK) ret = do_mmap_pgoff （file, addr, len, prot, flaoffset>>PAGE_SHIFT）; out: return ret; 2.1 功能說明這一段程序的主要功能為：（1）進程對內(nèi)存區(qū)域的分配最終多會歸結(jié)到do_mmap（）函數(shù)上來，同樣釋放一個內(nèi)存區(qū)域使用函數(shù)do_ummap（）,它會銷毀對應(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)的偏移量，因為我們并不是下子全部映射一個文件，可能只是映射文件的一部分，offset就表示那部分的起始位置。len：要映射的文件部分的長度。addr：虛擬空間的一個地址，表示從這個地址開始查找一個空閑的虛擬區(qū)。prot：指定對這個虛擬區(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個局部變量及數(shù)據(jù)結(jié)構(gòu)，其類型定義及語義如下：struct mm_struct/mm_struct結(jié)構(gòu)包含了用戶進程與存儲有關(guān)的信息struct vm_area_struct mmap; /*指向虛擬內(nèi)存段雙向鏈表指針 */struct vm_area_struct *mmap_avl;/*指向虛擬內(nèi)存段AVL樹指針 */pgd_t *pgd; /*進程頁目錄起始地址*/int map_count; /*此進程所用虛擬內(nèi)存的塊數(shù)*/unsigned long start_code,end_code; /*進程代碼段起始地址和結(jié)束地址*/unsigned long start_data,end_data;/*進程數(shù)據(jù)段起始地址和結(jié)束地址*/unsigned long start_stack; /*進程堆棧段起始地址*/unsigned long rss; /*進程駐留在物理內(nèi)存的頁面總數(shù)*/struct vm_struct/為虛擬內(nèi)存結(jié)構(gòu)體unsigned long flags; void *addr; /*虛擬內(nèi)存塊的其始地址 */unsigned long size; /*虛擬內(nèi)存塊的長度*/struct vm_struct *next; /*下一個虛擬內(nèi)存塊*/struct vm_area_struct /虛擬內(nèi)存塊存儲結(jié)構(gòu)體 struct mm_struct * vm_mm; /*指向該虛存段所屬進程的mm_struct */ unsigned long vm_start; /*虛擬內(nèi)存開始地址*/ unsigned long vm_end; /*虛擬內(nèi)存結(jié)束地址*/ struct vm_area_struct vm_next; unsigned short vm_flags; /*本vma塊的屬性標志位*/ short vm_avl_height; struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三項用于對AVL樹操作 */struct vm_operations_struct * vm_ops; /*指向?qū)ma塊操作的結(jié)構(gòu)體指針 */ unsigned long vm_offset; struct file * vm_file; /*指向文件的inode結(jié)構(gòu)體或NULL */ unsigned long vm_pte;typedef struct page/頁存儲結(jié)構(gòu)struct list_head list; /*該頁根據(jù)不同用途掛到不同鏈表中 */struct page *next, *prev; /*前一個和下一個頁 */unsigned long index; /*頁存放代碼或數(shù)據(jù)所屬文件的位移 */ struct inode *inode; /*該頁所屬文件的位移 */ atomic count; /*使用該頁的進程數(shù)，0表示空閑 */ unsigned long age; /*頁年齡 */ 2.4 流程圖本程序的流程圖如圖2所示圖2程序流程圖2.5 以實例說明運行過程當有進程到達時所用數(shù)據(jù)與指令存在于內(nèi)存中時，根據(jù)分析，將不進行缺頁中斷，將建立虛存區(qū)域，并執(zhí)行do_mmap()，并返回起始地址。實際運行結(jié)果如下：