操作系統(tǒng)課程設(shè)計--動態(tài)優(yōu)先權(quán)算法模擬

1、<p><b>　　操作系統(tǒng)課程設(shè)計</b></p><p>　　設(shè)計題目 動態(tài)優(yōu)先權(quán)算法模擬 </p><p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　專業(yè)：計算機科學與技術(shù) 學號： 學生姓名： </p><p><b>

2、　　設(shè)計題目：</b></p><p>　　必做題目：動態(tài)優(yōu)先權(quán)算法模擬</p><p>　　選做題目：Linux內(nèi)核分析</p><p><b>　　一、設(shè)計實驗條件</b></p><p>　　實驗地點：綜合樓808 </p><p><b>　　語言環(huán)境：C語言<

3、/b></p><p><b>　　二、設(shè)計任務(wù)及要求</b></p><p>　　必做：模擬單處理機環(huán)境下的進程調(diào)度模型，調(diào)度采用基于動態(tài)優(yōu)先權(quán)的調(diào)度法。</p><p>　　選做：對Linux操作系統(tǒng)的處理機管理、存儲器管理、文件管理、設(shè)備管理中一個或幾個功能進行較全面系統(tǒng)分析，分析內(nèi)容包括設(shè)計實現(xiàn)原理、典型算法、主要實現(xiàn)函數(shù)，分析內(nèi)

4、容寫入綜述報告，報告內(nèi)容還要包括函數(shù)間調(diào)用關(guān)系圖、功能模塊圖、系統(tǒng)主要流程圖。</p><p><b>　　設(shè)計報告的內(nèi)容</b></p><p><b>　　設(shè)計題目與設(shè)計任務(wù)</b></p><p><b>　　必做題目：</b></p><p>　　設(shè)計題目：動態(tài)優(yōu)先權(quán)算

5、法模擬</p><p>　　設(shè)計任務(wù)：模擬單處理機環(huán)境下的進程調(diào)度模型，調(diào)度采用基于動態(tài)優(yōu)先權(quán)的調(diào)度算法。</p><p><b>　　選做題目：</b></p><p>　　設(shè)計題目：Linux內(nèi)核分析</p><p>　　設(shè)計任務(wù)：對Linux操作系統(tǒng)的處理機管理、存儲器管理、文件管理、設(shè)備管理中一個或幾個功能進行較

6、全面系統(tǒng)分析，分析內(nèi)容包括設(shè)計實現(xiàn)原理、典型算法、主要實現(xiàn)函數(shù)，分析內(nèi)容寫入綜述報告，報告內(nèi)容還要包括函數(shù)間調(diào)用關(guān)系圖、功能模塊圖、系統(tǒng)主要流程圖。</p><p><b>　　前言（緒論）</b></p><p>　　通過小組一起合作進行操作系統(tǒng)課程設(shè)計，讓大家對操作系統(tǒng)的知識學習可以更深入的理解。通過小組討論設(shè)計方案，讓大家學會了團隊合作的重要性，并且通過上機實踐

7、，給提高大家上機編程實踐能力的一個提供一個很好的機會。</p><p>　　在操作系統(tǒng)中調(diào)度算法的實質(zhì)是一種資源的分配，因而調(diào)度算法是指“根據(jù)系統(tǒng)資源分配策略所規(guī)定的資源分配算法”。對于不同的操作系統(tǒng)和系統(tǒng)目標，通常采用不同的調(diào)度算法。為了照顧緊迫作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)先調(diào)度算法。在作為進程調(diào)度算法時，該算法是把處理機分配給就緒隊列優(yōu)先權(quán)最高的進程。這可以分為搶占式優(yōu)先權(quán)算法和非搶

8、占式優(yōu)先權(quán)算法。對于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)還是動態(tài)優(yōu)先權(quán)，以及如何確定進程的優(yōu)先權(quán)。本次課程設(shè)計所實現(xiàn)的算法就是動態(tài)優(yōu)先權(quán)算法的搶占式優(yōu)先權(quán)調(diào)度算法和非搶占式動態(tài)優(yōu)先權(quán)算法。</p><p>　　而在Linux內(nèi)核分析中大家針對操作系統(tǒng)的幾個主要功能分工合作，查閱資料，畫圖整理，進行匯總，使得大家對Linux內(nèi)核都有了全面系統(tǒng)的認識。</p><p>　　3

9、.設(shè)計主體（各部分設(shè)計內(nèi)容、分析、結(jié)論等）</p><p>　　3.1.必做題：動態(tài)優(yōu)先權(quán)算法模擬</p><p><b>　　【設(shè)計內(nèi)容】</b></p><p>　　動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程之初，先賦予其一個優(yōu)先級，然后其隨進程的推進或等待時間的增加而改變，以獲得更好的調(diào)度性能。</p><p>　　非搶占式優(yōu)先權(quán)調(diào)

10、度算法。在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。</p><p>　　搶占式優(yōu)先權(quán)算法。系統(tǒng)同樣把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程的執(zhí)行，重新將進程分配給優(yōu)先權(quán)最高的進程。</

11、p><p><b>　　【算法分析】</b></p><p>　　模擬動態(tài)優(yōu)先權(quán)算法，在主函數(shù)中選擇采用搶占式進程調(diào)度算法還是非搶占式進程調(diào)度算法，進而調(diào)用對應(yīng)的函數(shù)完成模擬。</p><p><b>　　設(shè)置進程結(jié)構(gòu)體，</b></p><p>　　struct PROCESS</p>

12、<p><b>　　{</b></p><p>　　int id; //進程id</p><p>　　double response_rate; //優(yōu)先權(quán)</p><p>　　int cputime; //要求服務(wù)時間</p><p>　　int waittim

13、e; //等待時間</p><p>　　int endtime; //進程完成時間，未完成時標記-1</p><p>　　int STATE; //進程當前狀態(tài)</p><p><b>　　};</b></p><p>　　記錄完成的進程id，使用數(shù)組pro_list[

14、10]</p><p><b>　　功能函數(shù)</b></p><p>　　display() 打印各進程當前狀態(tài)</p><p>　　init() 初始化進程狀態(tài)</p><p>　　change() 搶占式調(diào)度算法進程狀態(tài)更新</p><p>　　no_change

15、() 非搶占式調(diào)度算法進程狀態(tài)更新</p><p>　　函數(shù)調(diào)用順序如圖1：</p><p>　　圖1 函數(shù)調(diào)用順序圖</p><p><b>　　【代碼實現(xiàn)】</b></p><p>　　#include<iostream></p><p>　　#include<cstri

16、ng></p><p>　　#include<stdio.h></p><p>　　#include<cstdlib></p><p>　　using namespace std;</p><p>　　#define num 6</p><p>　　#define RUN 1</p&

17、gt;<p>　　#define READY 0</p><p>　　#define RUNOUT -1</p><p>　　int time=0;</p><p>　　struct PROCESS</p><p><b>　　{</b></p><p><b>　　int

18、 id;</b></p><p>　　double response_rate;</p><p>　　int cputime;</p><p>　　int waittime;</p><p>　　int endtime;</p><p>　　int STATE;</p><p>&l

19、t;b>　　}pro[10];</b></p><p>　　int pro_list[10],q=0;</p><p>　　void display()</p><p><b>　　{</b></p><p>　　cout<<"Time:"<<time<

20、<endl;</p><p>　　cout<<"==========================================="<<endl;</p><p>　　cout<<"ID\t\t0\t1\t2\t3\t4\t5"<<endl;</p><p>　　cou

21、t<<"respone_rate\t";</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　cout<<pro[i].response_rate<<'\t';</p><p

22、><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"cputime\t\t";</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b><

23、/p><p>　　cout<<pro[i].cputime<<'\t';</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"waittime\t";</p>&

24、lt;p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　cout<<pro[i].waittime<<'\t';</p><p><b>　　}</b></p><p>　　cout&

25、lt;<endl;</p><p>　　cout<<"endtime\t\t";</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　cout<<pro[i].endtime<<&

26、#39;\t';</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"STATE\t\t";</p><p>　　for(int i=0;i<num;i++)</p><p>

27、;<b>　　{</b></p><p>　　if(pro[i].STATE==RUN)</p><p>　　cout<<"RUN\t";</p><p>　　else if(pro[i].STATE==READY)</p><p>　　cout<<"READY\t&

28、quot;;</p><p>　　else cout<<"RUNOUT\t";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"the end process<end time&g

29、t;: ";</p><p>　　for(int i=0;i<q;i++)</p><p><b>　　{</b></p><p>　　cout<<"->"<<pro_list[i]<<'<'<<pro[pro_list[i]].en

30、dtime<<'>';</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"==========================================="<<endl;</p

31、><p><b>　　}</b></p><p>　　void init()</p><p><b>　　{</b></p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><

32、;p>　　pro[i].id=i;</p><p>　　pro[i].response_rate=1;</p><p>　　pro[i].waittime=0;</p><p>　　pro[i].endtime=-1;</p><p>　　pro[i].STATE=0;</p><p><b>　　}&

33、lt;/b></p><p>　　pro[0].cputime=5;</p><p>　　pro[1].cputime=3;</p><p>　　pro[2].cputime=1;</p><p>　　pro[3].cputime=2;</p><p>　　pro[4].cputime=4;</p>

34、<p>　　pro[5].cputime=6;</p><p><b>　　}</b></p><p>　　void change()</p><p><b>　　{</b></p><p>　　double runflag=0;</p><p>　　int ru

35、nprocess=0;</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE!=RUNOUT)</p><p><b>　　{</b></p><p>　　pro[i

36、].response_rate=1.0*(pro[i].waittime+pro[i].cputime)/pro[i].cputime;</p><p>　　if(pro[i].response_rate>runflag)</p><p><b>　　{</b></p><p>　　runflag=pro[i].response_rate

37、;</p><p>　　runprocess=i;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(int i=0;i<num;i++)</p

38、><p><b>　　{</b></p><p>　　if(pro[i].STATE==RUN)</p><p><b>　　{</b></p><p>　　pro[i].STATE=READY;</p><p>　　pro[i].waittime=-1;</p>

39、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　pro[runprocess].cputime--;</p><p>　　pro[runprocess].waittime=-1;</p><p>　　pro[runprocess].STATE=R

40、UN;</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　cont

41、inue;</b></p><p><b>　　}</b></p><p>　　pro[i].waittime++;</p><p>　　if(pro[i].cputime==0)</p><p><b>　　{</b></p><p>　　pro[i].endt

42、ime=time;</p><p>　　pro[i].STATE=RUNOUT;</p><p>　　pro[i].response_rate=0;</p><p>　　pro_list[q++]=i;</p><p><b>　　}</b></p><p><b>　　}</b&

43、gt;</p><p><b>　　}</b></p><p>　　void no_change()</p><p><b>　　{</b></p><p>　　int runprocess=0,flag=0;</p><p>　　double runflag=0;</

44、p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;<

45、;/b></p><p><b>　　}</b></p><p>　　pro[i].response_rate=1.0*(pro[i].waittime+pro[i].cputime)/pro[i].cputime;</p><p>　　if(pro[i].response_rate>runflag)</p><

46、p><b>　　{</b></p><p>　　runflag=pro[i].response_rate;</p><p>　　runprocess=i;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

47、t;　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p&

48、gt;<p><b>　　}</b></p><p>　　if(pro[i].STATE==RUN)</p><p><b>　　{</b></p><p><b>　　flag=1;</b></p><p>　　pro[i].cputime--;</p&g

49、t;<p>　　pro[i].waittime=-1;</p><p>　　for(int j=0;j<num;j++)</p><p><b>　　{</b></p><p>　　if(pro[j].STATE==RUNOUT)</p><p><b>　　{</b></

50、p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　pro[j].waittime++;</p><p><b>　　}</b></p><p>　　if(pro[i].cputime==0)<

51、;/p><p><b>　　{</b></p><p>　　pro[i].STATE=RUNOUT;</p><p>　　pro[i].endtime=time;</p><p>　　pro[i].response_rate=0;</p><p>　　pro_list[q++]=i;</p>

52、;<p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(!flag)</b>&

53、lt;/p><p><b>　　{</b></p><p>　　pro[runprocess].cputime--;</p><p>　　pro[runprocess].waittime=-1;</p><p>　　pro[runprocess].STATE=RUN;</p><p>　　for(in

54、t j=0;j<num;j++)</p><p><b>　　{</b></p><p>　　if(pro[j].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p

55、><b>　　}</b></p><p>　　pro[j].waittime++;</p><p><b>　　}</b></p><p>　　if(pro[runprocess].cputime==0)</p><p><b>　　{</b></p>&l

56、t;p>　　pro[runprocess].STATE=RUNOUT;</p><p>　　pro[runprocess].endtime=time;</p><p>　　pro[runprocess].response_rate=0;</p><p>　　pro_list[q++]=runprocess;</p><p><b&

57、gt;　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　int flag=0,type;<

58、;/p><p>　　cout<<"selecet type£¨1.preemptive scheduling 2.non-preemptive scheduling£©£º";</p><p>　　cin>>type;</p><p><b>　　init

59、();</b></p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p><b>　　flag=0;</b></p><p>　　display();</p><p>　　for(int i

60、=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE!=RUNOUT)</p><p><b>　　{</b></p><p><b>　　flag=1;</b></p><p>&

61、lt;b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(!flag) break;</p><p><b>　　time++;</b></p><p>

62、;　　if(type==1)</p><p><b>　　{</b></p><p><b>　　change();</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　

63、no_change();</p><p>　　cout<<endl;</p><p>　　getchar();</p><p><b>　　}</b></p><p>　　cout<<endl<<endl;</p><p>　　cout<<"

64、;All processes have runed out!!"<<endl;</p><p><b>　　}</b></p><p><b>　　【結(jié)果截圖】</b></p><p>　　搶占式優(yōu)先權(quán)調(diào)度算法</p><p>　　非搶占式優(yōu)先調(diào)度算法</p>&

65、lt;p>　　3.2.選做題：Linux內(nèi)核分析</p><p><b>　　Linux內(nèi)核分析</b></p><p>　　【摘要】操作系統(tǒng)是控制其他程序運行、管理系統(tǒng)資源并為用戶提供操作界面的系統(tǒng)軟件的集合。操作系統(tǒng)是一個龐大的管理控制程序，大致包括四個方面的管理功能：進程與處理機管理、存儲管理、設(shè)備管理、文件管理。</p><p>

66、　　【關(guān)鍵詞】Linux操作系統(tǒng)；處理機管理；存儲器管理；文件管理；設(shè)備管理。</p><p>　　操作系統(tǒng)是控制其他程序運行、管理系統(tǒng)資源并為用戶提供操作界面的系統(tǒng)軟件的集合。它是管理計算機硬件和軟件資源的程序，同時也是計算機系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)理論在計算機科學中是歷史悠久而又活躍的分支，而操作系統(tǒng)的設(shè)計與實現(xiàn)則是軟件工業(yè)的基礎(chǔ)與內(nèi)核。操作系統(tǒng)本身負責諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸

67、入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事物。</p><p>　　操作系統(tǒng)能夠使計算機系統(tǒng)的所喲資源最大限度的發(fā)揮作用，為用戶提供方便、有效、友善的服務(wù)界面。操作系統(tǒng)是一個龐大的管理控制程序，大致包括4個方面的管理功能：進程與處理機管理、存儲管理、設(shè)備管理、文件管理。本文主要是對存儲管理進行全面系統(tǒng)的分析。</p><p><b>　　一、處理機管理</b><

68、;/p><p>　　處理機管理主要就是進程管理，進程的管理分為進程的創(chuàng)建，進程的調(diào)度以及進程的終止。</p><p>　　進程的創(chuàng)建過程可以分為兩步，一是創(chuàng)建進程的管理結(jié)構(gòu)，即以task_struct為核心的進程控制塊，二是為進程加載應(yīng)用程序，即為進程創(chuàng)建虛擬地址空間并設(shè)置初始參數(shù)和環(huán)境變量，做好運行前的準備。</p><p>　　進程的調(diào)度：普通類進程采用CFS調(diào)度算

69、法，它所需要的是一個按虛擬計時器由小到大排序的就緒進程隊列。實時進程調(diào)度類實施進程的調(diào)度同行比較簡單，嚴格遵循優(yōu)先級即可，。目前的Linux用結(jié)構(gòu)rt_rq定義實時就緒隊列。空閑進程調(diào)度類每個處理器都有空閑的時候，當處理器空閑時，其上既沒有就緒的實時進程也沒有就緒的普通進程，處理器處于輪空狀態(tài)。</p><p>　　進程的終止：除了一些特殊的守護進程之外，一般進程的運行時間都是有限的，或者在有限的時間內(nèi)完成處理工

70、作，或者被內(nèi)核或其他進程殺死，即進程運行的終點都是終止。終止的進程不會在運行，它所占用的系統(tǒng)資源應(yīng)該被釋放，如內(nèi)存、堆棧、task_struct結(jié)構(gòu)等。</p><p>　　進程的終止一般被分為兩步：</p><p>　?。?）進程自己執(zhí)行退出操作exit，釋放被占用的系統(tǒng)資源，而后向父進程發(fā)送信號，報告自己已經(jīng)退出。</p><p>　?。?）父進程響應(yīng)進程退出信

71、號，執(zhí)行回收操作wait，找到已經(jīng)終止的子進程，回收其中的統(tǒng)計信息，釋放其task_struct結(jié)構(gòu)和系統(tǒng)堆棧，從而徹底將系統(tǒng)注銷。</p><p><b>　　二、存儲器管理</b></p><p>　　Linux是為多用戶多任務(wù)的操作系統(tǒng)，所以存儲資源要被多個進程有效共享，Linux內(nèi)存管理的設(shè)計充分利用了計算機系統(tǒng)所提供的虛擬存儲技術(shù)，真正實現(xiàn)了虛擬存儲器管理。

72、</p><p>　　1、虛擬空間、內(nèi)核空間和用戶空間 </p><p>　　Linux將這4GB的空間分為兩個部分，最高的1GB供內(nèi)核使用，稱為“內(nèi)核空間”，較低的3GB，供各個進程使用，稱為“用戶空間”。因為每個進程可以通過系統(tǒng)調(diào)用進入內(nèi)核，因此，Linux內(nèi)核空間由系統(tǒng)內(nèi)的所有進程共享，于是，從具體的進程角度來看，每個進程可以擁有4GB的虛擬地址空間（也叫虛擬內(nèi)存）

73、 </p><p>　　圖1 進程虛擬地址空間圖</p><p>　　由圖可以看出，每個進程有各自的私有用戶空間（0~3GB），這個空間對系統(tǒng)的其他進程是不可見的。最高的1GB內(nèi)核空間為所有進程及內(nèi)核所共享。</p><p>　　1.1內(nèi)存空間到物理內(nèi)存的映射</p><p>　　內(nèi)核空間內(nèi)所有進程都是共享的，其中存放的是內(nèi)核代碼和數(shù)據(jù)

74、，而進程的用戶空間中存放的是用戶程序的代碼和數(shù)據(jù)。 </p><p>　　圖2 內(nèi)核的虛擬地址空間到物理地址空間的映射圖</p><p>　　3GB在Linux中叫PAGE_OFFSET，對于內(nèi)核空間而言，給定一個虛地址x，其物理地址為x-PAGE_OFFSET,給定一個物理地址x，其虛地址為x+PAGE_OFFSET。</p><p><b>　　1.

75、2內(nèi)核映像</b></p><p>　　內(nèi)核的代碼和數(shù)據(jù)叫內(nèi)核映像。當系統(tǒng)啟動時，Linux內(nèi)核映像裝入在物理地址0x00100000開始的地方，即1MB開始的區(qū)間，這1MB用來存放一些與系統(tǒng)硬件相關(guān)的代碼和數(shù)據(jù)，內(nèi)核只占用從 0x00100000開始到start_men結(jié)束的一段區(qū)域。從start_men到end_men這段區(qū)域叫動態(tài)內(nèi)存，是用戶程序和數(shù)據(jù)使用的內(nèi)存區(qū)。</p><

76、;p>　　0 0x100000 start_men end_men</p><p>　　系統(tǒng)啟動后的物理內(nèi)存布局</p><p>　　由于在鏈接時，所有符號地址都加了PAGE_OFFSET，這樣，內(nèi)核映像在內(nèi)存的起始地址為0xC0100000。</p><p>　　2、 進程的用戶空間管理&

77、lt;/p><p>　　2.1 進程用戶空間的描述</p><p>　　一個進程的用戶地址空間主要由兩個數(shù)據(jù)結(jié)構(gòu)來描述。一個是mm_struct結(jié)構(gòu)，它對進程的整個用戶空間進行描述，簡稱內(nèi)存描述符；另一個是vm_area_structs結(jié)構(gòu)，它對用戶空間的虛存區(qū)進行描述。</p><p>　　圖3 虛存區(qū)的操作函數(shù)圖</p><p>　　2.2

78、進程用戶空間的創(chuàng)建</p><p>　　當創(chuàng)建一個新進程時，拷貝或共享進程的用戶空間，具體地說就是內(nèi)核調(diào)用copy_mm()函數(shù)。該函數(shù)通過建立新進程的所有頁表和mm_struct結(jié)構(gòu)來創(chuàng)建進程的用戶空間，通常每個進程都有自己的用戶空間，但是調(diào)用clone（）函數(shù)創(chuàng)建內(nèi)核線程時共享父進程的用戶空間。進程用戶空間的創(chuàng)建主要依賴于父進程，而且，在創(chuàng)建的過程中所作的工作僅僅是mm_struct結(jié)構(gòu)的建立、vm_area

79、_struct結(jié)構(gòu)的建立以及頁目錄和頁表的建立，并沒有真正復(fù)制一個物理頁面，這是為什么Linux內(nèi)核能迅速地創(chuàng)建進程的原因之一。</p><p><b>　　2.3虛存映射</b></p><p>　　當調(diào)用exec（）系統(tǒng)調(diào)用開始執(zhí)行一個進程時，進程的可執(zhí)行映像（包括代碼段、數(shù)據(jù)段）必須裝入進程的用戶地址空間。如果該進程用到了任何一個共享庫，則共享庫也必須裝入到進程

80、的用戶空間。將映像鏈接到用戶空間的方法被稱為“虛存映射”，也就是把文件從磁盤映射到進程的用戶空間，這樣把對文件的訪問轉(zhuǎn)化為對虛存區(qū)的訪問。有兩種類型的虛存映射：</p><p>　　共享的：有幾個進程共享這一映射，也就是說，如果一個進程對共享的虛存區(qū)進行寫，其他的進程都能感覺到，而且會修改磁盤上的對應(yīng)文件。</p><p>　　私有的：進程創(chuàng)建的這種映射只為了讀文件，而不是寫文件，因此對虛

81、存區(qū)的寫操作不會修改磁盤上的文件，因此，私有映射的效率比共享映射的要高。 </p><p>　　如果映射與文件無關(guān)，叫做匿名映射。</p><p>　　2.4與用戶相關(guān)的系統(tǒng)調(diào)用</p><p>　　表1 與用戶相關(guān)的主要系統(tǒng)調(diào)用表</p><p>　　如何調(diào)用mmap（），其原型為：</p><p>　　Vo

82、id*mmap（void*start，int length，int prot，int flags，int fd，int offset）</p><p>　　其中參數(shù)fd代表一個已打開的文件，offset為文件的起點，而start為映射到用戶空間的起始地址，length為長度（以字節(jié)為單位）。參數(shù)prot表示對映射區(qū)間的 訪問模式，如可寫、可讀、可執(zhí)行等，而flags用于以下控制目的。</p><

83、;p>　　MAP_SHARED:與子進程共享虛存區(qū)。</p><p>　　MAP_PRIVATE:子進程對這個虛存區(qū)是“寫時復(fù)制”。</p><p>　　MAP_LOCKED:鎖定這個虛存區(qū)，不能交換</p><p>　　MAP_ANONYMOUS:匿名區(qū)，與文件無關(guān)</p><p><b>　　請頁機制</b>&

84、lt;/p><p>　　當一個進程運行時，CPU訪問的地址是用戶空間的虛地址。Linux采用請頁機制來節(jié)約物理內(nèi)存，它僅僅把當前要使用的用戶空間的少量頁裝入物理內(nèi)存。</p><p>　　3.1缺頁異常處理程序</p><p>　　當一個進程執(zhí)行時，如果CPU訪問到一個有效的虛地址，但是這個地址對應(yīng)的頁沒有在內(nèi)存中，則CPU產(chǎn)生一個缺頁異常，同時將這個虛地址存入寄存器，

85、然后調(diào)用缺頁異常處理程序do_page_fault（），do_page_fault（）函數(shù)首先讀取引起缺頁的虛地址，如果沒找到，則說明訪問了非法虛地址，Linux會發(fā)送信號終止進程。</p><p>　　缺頁異?？隙ㄒl(fā)生在內(nèi)核態(tài)，如果發(fā)生在用戶態(tài)，則必定是錯誤的，把相關(guān)信息保存在進程的PCB中。如果這個虛存區(qū)的訪問權(quán)限與引起缺頁異常的訪問類型相匹配，則調(diào)用handel_mm_fault函數(shù)，該函數(shù)確定如何給進程

86、分配一個新的物理頁面如下。</p><p>　　如果被訪問的頁不在內(nèi)存，那么，內(nèi)核分配一個新的頁面并適當?shù)爻跏蓟?，這種技術(shù)叫“請求調(diào)頁”。</p><p>　　有兩種原因，被尋址的頁可以不在主存中：進程永遠也沒有訪問到這個頁，內(nèi)核能夠識別這種情況，這是因為頁表相應(yīng)的表項被填充為0.宏pite_none用來判斷這種情況，如果頁表項為空返回1，否則返回0；進程已經(jīng)訪問過這個頁，但是這個頁的內(nèi)容

87、被臨時保存在磁盤上，內(nèi)核能夠識別這種情況，因為相應(yīng)的表項沒有被填充為0。在其他情況下，當頁從未被訪問時調(diào)用do_no_page()函數(shù)。do_no_page()函數(shù)通過檢查虛存區(qū)描述符的nopage域來確定這一點，如果也與文件建立了映射關(guān)系，則nopage域就指向一個函數(shù)，該函數(shù)把所缺的頁表調(diào)入內(nèi)存。當nopage域為NULL，虛存區(qū)沒有映射磁盤文件，它是一個匿名映射，do_no_page()調(diào)用do_anonymous_page()函

88、數(shù)獲一個新的界面，分別處理寫請求和讀請求。當處理寫訪問時，調(diào)用_get_free_page()分配一個新的頁面，并把新頁面填為0。</p><p>　　如果被訪問的頁已在內(nèi)存但標為只讀，內(nèi)核分配一個新的頁面并把舊頁面的數(shù)據(jù)拷貝到新頁面上初始化它，被稱為“寫時復(fù)制”。寫時復(fù)制是一種可以推遲甚至免除拷貝數(shù)據(jù)的技術(shù)。內(nèi)核此時并不復(fù)制整個進程空間，而是讓父進程和子進程共享同一個拷貝。</p><p&g

89、t;　　否 是</p><p>　　是 否</p><p>　　是 否</p><p>　　是 否</p><p>　　否 是

90、否</p><p><b>　　是</b></p><p>　　是 否</p><p>　　是 否 </p><p>　　否 是 </p><p><b>　　是&l

91、t;/b></p><p>　　圖4 缺頁異常處理程序流程圖</p><p>　　物理內(nèi)存的分配與回收</p><p>　　4.1頁描述符和伙伴算法</p><p>　　Struct page結(jié)構(gòu)表示系統(tǒng)的每個物理頁，也叫頁描述符。系統(tǒng)中的每個物理頁面都要分配這樣一個結(jié)構(gòu)體。要管理系統(tǒng)中很多的物理頁面，可以采用最簡單的數(shù)組結(jié)構(gòu)：&l

92、t;/p><p>　　Struct page *men_map; </p><p>　　在內(nèi)核代碼中，men_map是一個全局變量，它描述了系統(tǒng)中的全部物理頁面。</p><p>　　由于頻繁地請求和釋放不同大小一組連續(xù)頁面，會導(dǎo)致外碎片，所以要分配一個大的連續(xù)頁面無法滿足，Linux采用著名的伙伴算法來解決外碎片問題?；锇橄到y(tǒng)中采用的數(shù)據(jù)結(jié)構(gòu)是一個叫做free_ar

93、ea數(shù)組。滿足以下條件的兩個塊成為伙伴即兩個塊的大小相同；兩個塊的物理地址連續(xù)?；锇樗惴ò褲M足以上兩個條件的兩個塊合并為一個塊，該算法是迭代算法，如果合并后的塊還可以跟相鄰的塊進行合并，那么該算法就繼續(xù)合并。</p><p>　　4.2物理頁面的分配</p><p>　　Linux中采用伙伴算法有效地分配和回收物理頁塊，該算法試圖分配一個或多個連接物理頁面組成的內(nèi)存塊，大小為1頁，2頁或4

94、頁等。只要系統(tǒng)有滿足需要的足夠的空閑頁面，就會在free_area數(shù)組中查找滿足需要大小的的一個頁塊。函數(shù)_get_free_pages用于物理頁塊的分配，其定義如下：</p><p>　　Unsigned long_get_free_pages（int gfp_mask，unsigned long order）</p><p><b>　　{ </b></p&

95、gt;<p>　　struct page *page; </p><p>　　VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0); </p><p>　　page = alloc_pages(gfp_mask, order); </p><p>　　if (!page) </p><p>

96、;　　return 0; </p><p>　　return (unsigned long) page_address(page); </p><p><b>　　} </b></p><p>　　Gfp_mask 是分配標志，order是指數(shù)，所請求的頁塊大小為2的order次冪個物理頁面，即塊的索引。</p><p>

97、;　　該函數(shù)所做的工作主要是檢查所請求的頁塊大小是否滿足；檢查系統(tǒng)中空閑物理頁的總數(shù)是否低于允許的下界；正常分配；換頁，通過調(diào)用函數(shù)try_to_free_pages()啟動換頁進程。</p><p>　　4.3物理頁面的回收 </p><p>　　分配頁塊的過程中將大的頁塊分為小的頁塊，會使內(nèi)存更為零散。頁分配與頁回收的過程相反，它會盡可能把小頁塊合并成大的頁塊。</p>

98、<p>　　函數(shù)free_pages用于頁塊的回收，定義如下：</p><p>　　Void free_pages(unsigned long addr,unsigned long order)</p><p>　　{ if (addr != 0) </p><p><b>　　{ </b></p><p>　

99、　VM_BUG_ON(!virt_addr_valid((void *)addr)); </p><p>　　__free_pages(virt_to_page((void *)addr), order); </p><p><b>　　} </b></p><p><b>　　} </b></p><

100、p>　　自此我們知道伙伴算法分配內(nèi)存時，每次至少分配一個頁面，當我們需要的內(nèi)存少于一個頁面時，或者更小的數(shù)據(jù)時，該如何做？Linux引入了slab分配模式。</p><p>　　4.4slab分配模式</p><p>　　slab的主要思想是對內(nèi)核數(shù)據(jù)進行頁面分配時，首先要對數(shù)據(jù)結(jié)構(gòu)進行初始化，用完之后就要回收。對小對象的分配，它們會在系統(tǒng)生命周期內(nèi)進行無數(shù)次分配。slab 緩存分配

101、器通過對類似大小的對象進行緩存而提供這種功能，從而避免了常見的碎片問題。slab 分配器還支持通用對象的初始化，從而避免了為同一目而對一個對象重復(fù)進行初始化。最后，slab 分配器還可以支持硬件緩存對齊和著色，這允許不同緩存中的對象占用相同的緩存行，從而提高緩存的利用率并獲得更好的性能。</p><p>　　緩沖區(qū)的創(chuàng)建通過kmem_cache_create()建立，其原型如下：</p><p

102、>　　struct kmem_cache *kmem_cache_create( const char *name, size_t size, size_t offset,</p><p>　　unsigned long c_flags; void (*ctor)(void*, struct kmem_cache *, unsigned long), void (*dtor)(void*, struct k

103、mem_cache *, unsigned long)); </p><p>　　其中name為緩沖區(qū)的名字，size為對象的大小，offset參數(shù)定義了每個對象必需的對齊。 c_flags 參數(shù)指定了為緩存啟用的選項。其可能取值SLAB_HWCACHE_ALIGN表示與第一個緩沖區(qū)中的緩沖行邊界對齊；SLAB_NO_REAP表示允許系統(tǒng)回收內(nèi)存；SLAB_CACHE_DMA表示使用的是DMA內(nèi)存（DMA是直接存

104、儲器訪問的縮寫，他允許不同速度的硬件裝置來溝通，而不需要依于 CPU 的大量 中斷 負載）；最后兩個函數(shù)分別是構(gòu)造函數(shù)（用于對數(shù)據(jù)初始化）和析構(gòu)函數(shù)（用于對數(shù)據(jù)回收處理）。其中數(shù)據(jù)結(jié)構(gòu)kmem_cache是用來對緩沖區(qū)進行管理的。</p><p>　　緩沖區(qū)的分配與釋放函數(shù)分別如下：</p><p>　　kmem_cache_alloc(struct

105、 kmem_cache *cachep, gfp_t flags);</p><p>　　kmem_cache_free(struct kmem_cache *cachep, void *objp) </p><p>　　內(nèi)核函數(shù) kmem_cache_destroy 用來銷毀緩存。這個調(diào)用是由內(nèi)核模塊在被卸載時執(zhí)行的。在調(diào)用這個函數(shù)時，緩存必須為空。</p><p&g

106、t;　　void kmem_cache_destroy( struct kmem_cache *cachep );</p><p><b>　　通用緩沖區(qū)：</b></p><p>　　通用緩沖區(qū)中分配和釋放緩沖區(qū)的函數(shù)為：</p><p>　　void *kmalloc(size_t,int flags );</p><p

107、>　　void kfree(const void *objp);</p><p>　　當然還有其他函數(shù)來輔助slab完成任務(wù)。kmem_cache_size 函數(shù)會返回這個緩存所管理的對象的大小。您也可以通過調(diào)用 kmem_cache_name 來檢索給定緩存的名稱（在創(chuàng)建緩存時定義）。具體函數(shù)原型如下：</p><p>　　unsigned int kmem_cache_size(

108、 struct kmem_cache *cachep ); const char *kmem_cache_name( struct kmem_cache *cachep );</p><p>　　4.5內(nèi)核空間非連續(xù)內(nèi)存區(qū)分配</p><p>　　非連續(xù)內(nèi)存的線性地址空間是從VMALLOC_START~VMALLOC_END,共128MB大小。當內(nèi)核需要用vmalloc類的函數(shù)進行非連續(xù)內(nèi)

109、存分配時，就會申請一個vm_struct結(jié)構(gòu)來描述對應(yīng)的vmalloc區(qū)，若分配多個vmalloc的內(nèi)存區(qū)，那么相鄰兩個vmalloc區(qū)之間的間隔大小至少為4KB，即至少是一個頁框大小PAGE——SIZE。內(nèi)核中描述非連續(xù)區(qū)的數(shù)據(jù)結(jié)構(gòu)是struct vm_struct：</p><p>　　struct vm_struct {        

110、;    struct vm_struct *next;                 void *addr;              </p><p>　　unsigned lo

111、ng size;            </p><p>　　unsigned long flags;                       struct page **pages; &

112、#160;                 unsigned int nr_pages;               phys_addr_t phys_addr;       

113、;        const void *caller;        };  內(nèi)核中用get_vm_area函數(shù)來創(chuàng)建一個新的非連續(xù)區(qū)結(jié)構(gòu)，在該函數(shù)的實現(xiàn)中又會調(diào)用kmallloc函數(shù)和kfree函數(shù)分別為vm_struct結(jié)構(gòu)分配和釋放所需的內(nèi)存。vmalloc給內(nèi)核分配一個非連續(xù)的內(nèi)存區(qū)，其原型為: 

114、            void *vmalloc(unsigned long size)       函數(shù)首先把size參數(shù)取為頁面的大小(即4KB)的倍數(shù)，然后進行有效性檢查，若有大小適合的可用內(nèi)存，就調(diào)用get_vm_area()獲得一個內(nèi)存區(qū)的結(jié)構(gòu)，最后會調(diào)用vmalloc_area_pages()進行真正的

115、的非連續(xù)內(nèi)存的分配，該函數(shù)實際上建立了非連續(xù)內(nèi)存到物理頁</p><p><b>　　交換機制 </b></p><p>　　當物理內(nèi)存出現(xiàn)不足時 ，Linux內(nèi)存管理子系統(tǒng)需要釋放部分物理內(nèi)存頁面。這一任務(wù)由內(nèi)核的交換守護進程kswapd，該守護進程實際是一個內(nèi)核線程，它在內(nèi)核初始化時啟動，并周期性地運行。在Linux中用于交換的磁盤空間叫做交換文件或交換區(qū)。<

116、;/p><p><b>　　文件管理</b></p><p>　　系統(tǒng)調(diào)用（trap）</p><p><b>　　I/O請求</b></p><p>　　圖5 文件系統(tǒng)的整體結(jié)構(gòu)圖</p><p>　　文件系統(tǒng)是結(jié)構(gòu)化管理塊設(shè)備上的數(shù)據(jù)的機制。它通過文件和目錄等概念，是管理設(shè)

117、備上的數(shù)據(jù)成為可能。Linux文件系統(tǒng)是由兩大模塊構(gòu)成的：(一)VFS虛擬文件系統(tǒng)。(二)具體的文件系統(tǒng)。而文件系統(tǒng)主要有文件系統(tǒng)的建立，文件系統(tǒng)的安裝與卸載，文件的注冊與注銷這幾個部分，基于文件系統(tǒng)的概念又可以把數(shù)據(jù)成分分為數(shù)據(jù)、記錄和文件三級。</p><p>　　文件結(jié)構(gòu)是文件存放磁盤等存儲設(shè)備上的組織方法，只要體現(xiàn)在對文件和目錄的組織上。目錄提供了管理文件的一個方便而有效的途徑。Linux采用的樹形結(jié)構(gòu)。

118、最上層是根目錄，其他所有目錄都是從根目錄出發(fā)而生成的。</p><p><b>　　/（根目錄）</b></p><p>　　Bin dev etc home lib sbin tmp root mnt proc usr var</p><p>　　Linux下主要目錄的功能：</p><p>　

119、　/bin 存放二進制可執(zhí)行文件。</p><p>　　/dev 存放設(shè)備文件。</p><p>　　/etc 存放系統(tǒng)管理和配置文件。</p><p>　　/home 用戶主目錄的幾點，如用戶usr的主目錄就是/usr。</p><p>　　/lib 標準程序設(shè)計庫，又叫動態(tài)鏈接共享庫。</p><p>　

120、　/sbin 系統(tǒng)管理命令目錄，存放的是系統(tǒng)管理員使用的管理程序。</p><p>　　/tmp 公用的臨時文件目錄。</p><p>　　/root 系統(tǒng)管理員的主目錄。</p><p>　　/mnt 用于用戶零食安裝其他文件系統(tǒng)的目錄。</p><p>　　/proc 虛擬的目錄，是系統(tǒng)內(nèi)存的映射?？芍苯釉L問這個目錄來獲取系統(tǒng)信

121、息。</p><p>　　/var 某些大文件的溢出區(qū)，存放例如各種服務(wù)的日志文件。</p><p>　　/usr 最龐大的目錄，會用到的應(yīng)用程序和文件幾乎都在這個目錄下。</p><p><b>　　文件類型</b></p><p>　　·常規(guī)文件 供計算機用戶和曹組系統(tǒng)存放數(shù)據(jù)、程序等信息的文件。<

122、;/p><p>　　·目錄文件 Linux文件系統(tǒng)將文件索引節(jié)點號和文件同時保存在目錄中。</p><p>　　·設(shè)備文件 Linux把所有的外設(shè)都當作文件來處理。</p><p>　　·管道文件 主要用于在進程間傳遞數(shù)據(jù)。</p><p>　　·鏈接文件 提供了共享文件的一種方法。</p>

123、<p><b>　　設(shè)備管理</b></p><p>　　系統(tǒng)中有兩種設(shè)備文件：塊設(shè)備文件和字符設(shè)備文件。第三種設(shè)備類型是網(wǎng)絡(luò)設(shè)備，它是兼有塊設(shè)備屬性和字符設(shè)備屬性的特殊設(shè)備，但并不用文件來表示?；镜耐ㄓ脡K設(shè)備有open、close（或release）和ioct1函數(shù)，以及最重要的request函數(shù)。字符設(shè)備與塊設(shè)備不同，字符設(shè)備用于傳送數(shù)據(jù)流。所有串行設(shè)備都是字符設(shè)備。網(wǎng)絡(luò)設(shè)備

124、兼有塊設(shè)備和字符設(shè)備的一些屬性，通常被認為是一組特殊的設(shè)備。與字符設(shè)備類似，網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)在物理層上串行傳輸。</p><p>　　輸入輸出:Linux內(nèi)核可以運行與一個或多個處理器上。處理器為系統(tǒng)中其余部分提供的接口離不開硬件的支持。在硬件依賴性極強的底層，內(nèi)核使用匯編語言指令與這些設(shè)備“對話”。通過將對頂層虛擬文件系統(tǒng)的操作實現(xiàn)為底層想物理介質(zhì)寫入二進制位，來分析Linux內(nèi)核如何將軟硬件結(jié)合起來。</

125、p><p>　　廣義上說，操作系統(tǒng)包括內(nèi)核和運行在內(nèi)核之上的所有工具軟件，如瀏覽器等。狹義上說，操作系統(tǒng)就是內(nèi)核，其余軟件都是應(yīng)用程序。一個操作系統(tǒng)可以擁有許許多多的應(yīng)用程序，但卻只有一個內(nèi)核。</p><p>　　為了管理資源、提供服務(wù)，在內(nèi)核中需要實現(xiàn)許多程序，如各種中斷的處理程序、各種服務(wù)請求的處理程序、各種資源的管理程序、各種設(shè)備的驅(qū)動程序等。為了實現(xiàn)這些程序，在內(nèi)核中還需要定義多種數(shù)

126、據(jù)結(jié)構(gòu)。由于操作系統(tǒng)內(nèi)核完成的都是核心管理工作，因而內(nèi)核本身必須被嚴格地保護起來，以免被破壞。另外，操作系統(tǒng)內(nèi)核和應(yīng)用程序的能力也應(yīng)該有所區(qū)別，有些工作只能在內(nèi)核中做，不應(yīng)由應(yīng)用程序來實現(xiàn)。</p><p>　　人們在計算機上使用程序，操作系統(tǒng)內(nèi)核的唯一任務(wù)就是幫助這些程序運行。所有操作系統(tǒng)內(nèi)核本身從來沒有主動做任何事，它僅僅是等待應(yīng)用程序請求某些資源或者請求硬盤上的某些文件或者請求程序把它們連接到外部世界等等，

127、然后操作系統(tǒng)內(nèi)核來了，它干預(yù)并且試圖讓人們更容易地運行程序。</p><p><b>　　【結(jié)束語】 </b></p><p>　　此次課程設(shè)計由小組成員一起討論，合作完成。大家結(jié)合課本及平時的實驗知識，討論出算法的可行性、各個變量，函數(shù)使用，結(jié)構(gòu)定義和界面安排等。然后根據(jù)討論結(jié)果確定主要變量、結(jié)構(gòu)體和主要函數(shù)等編寫出程序。通過大家之間的合作與討論，互補不足，解決了很

128、多編程過程中遇到的問題，同時也使我們對動靜態(tài)優(yōu)先權(quán)，搶占式和非搶占式等操作系統(tǒng)知識都有了更深刻的了解。除了課本上的知識，我們更學會了團隊合作的重要性和上機實踐對學習的幫助。 </p><p>　　動態(tài)優(yōu)先權(quán)算法保證了緊急任務(wù)的高優(yōu)先權(quán)先處理，同時彌補了靜態(tài)優(yōu)先權(quán)事先設(shè)置數(shù)值不能完全適合每一個時刻的缺點，動態(tài)賦值，更加的靈活。</p><p>　　在選做題的Linux內(nèi)核分析設(shè)計中，我們小

129、組成員根據(jù)Linux操作系統(tǒng)的幾個重要功能分工合作去圖書館查閱資料，根據(jù)內(nèi)容畫圖整理，最后進行匯總，從而使得小組成員對操作系統(tǒng)的各個功能都有了全面系統(tǒng)的了解，收獲很大。</p><p><b>　　【參考資料】</b></p><p>　　[1]郭玉東，尹青，董衛(wèi)宇．Linux原理與結(jié)構(gòu)[M]．西安：電子科技大學出版社，2012． </p><p&

130、gt;　　[2]陳莉君，康華．Linux操作系統(tǒng)原理與應(yīng)用[M]．北京：清華大學出版社，2012．</p><p>　　[3]何炎祥，李飛，李寧．計算機操作系統(tǒng)[M]．北京:清華大學出版社，2011．</p><p>　　[4]陳莉君，賀炎，劉霞林．Linux內(nèi)核編程[M]．北京：人民郵電大學出版社，2011．</p><p>　　[5]吳小平，羅俊松．操作系統(tǒng)．[