系統(tǒng)軟件開發(fā)實踐實驗報告

中國礦業(yè)大學(xué)計算機學(xué)院2012級本科生實驗報告課程名稱系統(tǒng)軟件開發(fā)實踐報告時間2015/5/1學(xué)生姓名徐竹學(xué)號08123325專業(yè)計算機科學(xué)與技術(shù)任課教師任課教師評語任課教師評語（①對實驗課程基礎(chǔ)理論的掌握；②對實驗課程知識應(yīng)用能力的評價；③對課程報告相關(guān)實驗、作品、軟件等成果的評價；④實驗課學(xué)習(xí)態(tài)度和上課紀(jì)律；⑤實驗課程成果和報告工作量；⑥總體評價和成績；⑦存在問題等）：成績:任課教師簽字:成績:實驗一（第一周）詞法分析器（flex實驗）一、實驗?zāi)康?、通過對flex基本知識的閱讀，了解其工作原理和過程以及其匹配模式和規(guī)則，掌握簡單的lex語法和規(guī)則；2、在上述基礎(chǔ)上能夠自主編寫出簡單且可以運行的詞法分析器，實現(xiàn)簡單的詞法分析功能；3、通過實驗，設(shè)計編制調(diào)試一個具體的詞法分析程序，加深對詞法分析原理的理解，并掌握在對程序設(shè)計語言源程序進行掃描過程中將其分解為各類單詞的詞法分析方法。二、實驗說明本次編制調(diào)試的詞法分析器基本可以實現(xiàn)如下簡單功能：1、可以匹配識別關(guān)鍵字：elseifswitchforintfloatreturnvoidwhile（所有的關(guān)鍵字都是保留字，并且必須是小寫）；2、可以匹配識別專用符號：+-*/<<=>>===!==;,（）[]（}/**/3、標(biāo)識符（ID）和數(shù)字（NU）通過下列正則表達式定義：ID=letterletter*NUM=digitdigit*letter=a|..|z|A|..|Zdigit=0|..|94、可以匹配識別空格（空格由空白、換行符和制表符組成，空格通常被忽略，，除了它必須分開ID、NUM關(guān)鍵字）；5、可以識別簡單的注釋（/*注釋內(nèi)容*/）；三、實驗原理與分析詞法分析的基本任務(wù)是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據(jù)掃描到單詞符號的第一個字符的種類，拼出相應(yīng)的單詞符號。詞法分析階段是編譯過程的第一個階段，是編譯的基礎(chǔ)。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，即對構(gòu)成源程序的字符流進行掃描然后根據(jù)構(gòu)詞規(guī)則識別單詞（也稱單詞符號或符號）。詞法分析是編譯程序的第一個階段且是必要階段；詞法分析的核心任務(wù)是掃描、識別單詞且對識別出的單詞給出定性、定長的處理；實現(xiàn)詞法分析程序的常用途徑：自動生成,手工生成。而本次實驗用的是自動生成工具flex，相對于手動生成可以極大地減少工作量。單詞的描述也就是模式(LexicalPattern),模式一般用正規(guī)表達式進行精確描述。FLEX通過讀取一個有規(guī)定格式的文本文件，輸出一個如下所示的C語言源程序。|輸入文件*.l|>|flex工具|>|輸出文件lex.yy.c|FLEX的輸入文件為LEX源文件，它內(nèi)含正規(guī)表達式和對相應(yīng)模式處理的C語言代碼。FLEX通過對.l源文件的掃描自動生成相應(yīng)的詞法分析函數(shù)intyylex()，并將之輸出到lex.yy.c的文件中。該文件即為LEX的輸出文件或輸出的詞法分析器。LEX的源文件由三個部份組成，每個部分之間用頂行的“%%”分割，其格式如下：定義部份%%規(guī)則部份%%用戶附加C語言部份其中，定義部分由C語言代碼、模式的宏定義、條件模式的開始條件說明三部份組成。C代碼部份由頂行的%｛和｝%引入，LEX掃描源文件時將%(和｝%之間的部分原封不動的拷貝到輸出文件lex.yy.c中。而模式宏定義則是一個正則表達式的定義。正則表達式的匹配如下：解暮X配置單個字母*■匹甑院換行符州之夕卜的任意字符[即]匹斯Q賦或1[abj-oz]匹甄b、哌］全口之間的字母牛習(xí)除大寫字母A-Z之外的其它學(xué)符：八再-召門］院大寫寶母A-W和換行存之夕卜的其它寶符匹配口個或多個「「十匹甄［個或多個「r?匹酉萌個或L個『第二部分規(guī)則部份是LEX源文件的核心部份，它包括一組模式和在生成分析器識別相應(yīng)模式后對相應(yīng)模式進行處理的C語言動作(Action)。LEX對第三部分不作任何處理，僅僅將之直接拷貝到輸出文件lex.yy.c的尾部。在些部份，可定義對模式進行處理的C語言函數(shù)、主函數(shù)和yylex要調(diào)用的函數(shù)yywrap()等。如果用戶在其它C模塊中提供這些函數(shù)，用戶代碼部份可以省略。yylex()函數(shù)被調(diào)用之后，它首先檢查全局文件指針變量yyin是否有定義，如有，則將之設(shè)置為將要掃描的文件指針。如無，則設(shè)置為標(biāo)準(zhǔn)輸入文件stdin。同理，如全局文件指針變量yyout無定義，則將之設(shè)置為標(biāo)準(zhǔn)輸出文件stdout。若有多個模式與被掃描文件中的字符串相匹配，則yylex()執(zhí)行能匹配最長字符串的模式，稱為“最長匹配原則”；若還有多個模式匹配長度相同的字符串，則yylex()選擇在LEX源文件中排列最前面的模式進行匹配，稱為“最先匹配原則”。yylex()常通過超前搜索一個字符來實現(xiàn)這樣的原則，如果使用超前搜索匹配了某一模式，則yylex()在進行下一次分析前，將回退一個字符。另外，LEX提供控制模式在一定狀態(tài)下使用的功能，稱為條件模式。LEX首先在定義部份通過%start來定義條件句。在規(guī)則部份可通過宏BEGIN條件名來激活條件。BEGININITIAL或BEGIN0將休眠所有的條件模式，使分析器回到開始狀態(tài)。四、實驗步驟和過程分析1、lex源代碼編寫通過前期對flex的了解自主編寫了以下簡單的的詞法分析器，該詞法分析器能夠?qū)崿F(xiàn)基本的詞法分析功能如行數(shù)、關(guān)鍵字個數(shù)、單詞個數(shù)以及簡單注釋等的判別。由于功能簡單，所以本次代碼完全是自己一一在記事本里面編寫而成;digit[0-9]NUM[digit][digit]*/*此正則表達式用于對數(shù)字進行匹配*/letter[A-Za-z]ID[letter][letter]*/*此正則表達式是用于對標(biāo)示符進行模式匹配*/else"{num_id++;}"while"{++num_id;}/*這是實現(xiàn)代對關(guān)鍵字進行匹配*/"+"|"-"|"*"|T|"="|"v"|"<="|">"|">="|"=="|"!="|”;"|”,”|”("|")”|"["|”]"|"{"|"}"|"/*"|"\*”{fuhao++;}/*這些代碼可以用于匹配其它符號*/[A\t\n]+{nword++;}/*識別單詞個數(shù)*/\n{hangshu++;}/*對行數(shù)進行識別并統(tǒng)計*//*下面再編寫一個comment函數(shù)用于判斷注釋*/comment(){charc,c1;loop:while((c=input())!='*'&&(c!=0))putchar('\n');if((c1=input())!='/'&&c!=0){unput(c1);gotoloop;}if(c!=0)putchar('\n');}intyywrap(){return1;}最后將這些代碼按照flex語法進行整合得到完整flex源碼。2、通過命令行調(diào)試運行得到lex.yy.exe文件；3、編寫測試文件（命名為123.cpp）并與lex.yy.exe放于同一文件夾內(nèi)；123.cpp：#include<iostream>usingnamespacestd;intmain{inta=33,b=1123;c=12;c=a+b;cout<<"felx123"<<endl;return0;}4、運用命令行的lex.yy.exe<123.cpp運行得到結(jié)果：五、實驗小結(jié)本次實驗通過對flex基本知識的閱讀基本掌握了簡單的lex語法和規(guī)則，也可以自行設(shè)計編制調(diào)試一個具體的詞法分析程序，不僅加深對了詞法分析原理的理解，也初步掌握了在對程序設(shè)計語言源程序進行掃描過程中將其分解為各類單詞的詞法分析方法。實驗二（第二周）語法分析器（bison簡單實驗）一、實驗?zāi)康?、了解語法分析工具bison的用法和自動生成語法分析器的過程和原理；2、學(xué)習(xí)和掌握flex與bison聯(lián)合編譯的思想和方法，能夠通過這種方法編譯實現(xiàn)基本編譯器的構(gòu)造和設(shè)計。二、實驗說明bison是屬于GNU項目的一個語法分析器生成器。Bison把一個關(guān)于“向前查看從左到右最右”(LALR)上下文無關(guān)文法的描述轉(zhuǎn)化成可以分析該文法的C或C++程序。它也可以為二義文法生成“通用的從左到右最右”(GLR)語法分析器。本次試驗主要是學(xué)習(xí)并利用語法分析器生成工具Bison編寫一個語法分析程序，與詞法分析器結(jié)合，能夠根據(jù)語言的上下文無關(guān)文法，識別輸入的單詞序列是否文法的句子，實驗中可以編寫一個測試程序，以給定的測試文件作為輸入，輸出運行結(jié)果到輸出文件中。三、實驗原理與分析Bison是一種通用目的的分析器生成器。它將LALR(1)上下文無關(guān)文法的描述轉(zhuǎn)化成分析該文法的C程序。使用bison的前提是使用flex事先生成相關(guān)詞法分析器°Flex可以識別正則表達式，而bison可以識別語法。Flex把輸入流分解為若干個片段(記號)，而bison則可以將這些記號基于邏輯進行合并。Bison基于我們所給定的語法來生成一個可以識別這個語法中有效語句的語法分析器。而且bison只處理語法，你需要保證其他部分的完整性。語法由一系列規(guī)則組成，語法分析器就是基于這些規(guī)則來識別語法上正確的輸入。Bison的.y文件也是分成三個部分：1、聲明部分：所有詞法單元的定義可以放在此處2、規(guī)則部分：具體的語法和相應(yīng)的動作3、用戶自定義部分。第三部分會被bison原封不動的拷貝進生成的.C文件當(dāng)bison讀入一個終結(jié)符(token)，它會將該終結(jié)符及其語意值一起壓入堆棧。這個堆棧叫做分析器堆棧(parserstack)。把一個token壓入堆棧通常叫做移進(shifting)。但堆棧并不是每讀入一個終結(jié)符就分配一個棧元素給它。當(dāng)已經(jīng)移進的后n個終結(jié)符和組(groupings)與一個文法規(guī)則相匹配時，它們會被根據(jù)那個規(guī)則結(jié)合起來。這叫做歸約(reduction)。棧中的那些終結(jié)符和組會被單個的組(grouping)替換。那個組的符號就是那個規(guī)則的結(jié)果。執(zhí)行該規(guī)則的相應(yīng)的動作(Action)也是歸約處理的一部分，這個動作會計算這個組的語意值。分析器通過移進和歸約嘗試著縮減整個輸入到單個的組。這個組的符號就是文法中的起始符號(start-symbol)。Bison分析器并不總是在后n個終結(jié)符與組匹配某一規(guī)則時立即就進行歸約。這種策略對于大部分語言來說并不合適。相反，當(dāng)可以進行歸約時，分析器有時會“預(yù)讀”(looksahead)下一個終結(jié)符來決定做什么。當(dāng)一個終結(jié)符被讀進來后，并不會立即移進堆棧，而是首先作為一個預(yù)讀終結(jié)符(look-aheadtoken)。此后，分析器開始對棧上的終結(jié)符和組執(zhí)行一個或多個歸約，而預(yù)讀終結(jié)符仍然放在一邊。當(dāng)沒有歸約可做時，這個預(yù)讀終結(jié)符才會被移進堆棧。這并不表示所有可能的歸約都已經(jīng)做了，這要取決于預(yù)讀終結(jié)符的類型，一些規(guī)則可能選擇推遲它們的使用。四、實驗過程詳細(xì)分析和步驟簡單bison與flex聯(lián)合編譯實驗1、window下首先將bison安裝在與flex安裝的相同目錄下，編寫編寫bison文件即.y文件并保存在bison目錄下，然后通過調(diào)用命令行生成.tab.c和.tab.h文件；2、編寫詞法分析文件并將上述的.Tab.h包含在頭文件中，然后后調(diào)用命令行生成.yy.c文件,利用命令行將.yy.c和.tab.c文件生成為可執(zhí)行文件exe文件；3、在命令行里利用生成的exe文件調(diào)用測試文件得到結(jié)果。I.I■版本-I-7Sf?l1版卞匕所有20G9Cooperation.■1￥苴斯五砂用|“P;A拉何：|譚程、示滴叫昨時僅4譯實踐Ibison>bisundHamc.v不是丙都或外部命令,也不是可運行的程序1?：WcnJianIKli果程、系匚玄次霹%]?艮義氣之向海爽\Jbison>cdCnnUinFlcxMiinF：xWenJianX^的照秫、系沆"X歧、操告燧葡\GnuLJinFLex-<bin>biton-dWane一y1?：WcnJion，若IKli果程、系於實霹\|，艮義氣孺海實\JbisonWnuWinl?Lcx\hin>i'Lexbanc.1F=WenJian"隊日勺i果程、系統(tǒng)'：L踐疽艮吉噂M洋次'踐寸M。nXGnuUinFLex<bin>Lex..exe<bison.txthcnj)ao年齡為歲：璀司年齡羽21歲；的課程統(tǒng)實踐峙艮皆譯實踐Mjis□n\GnuWinF1cx\bin>_利用語法分析器生成工具Bison編寫一個語法分析程序，與詞法分析器結(jié)合，能夠根據(jù)語言的上下文無關(guān)文法，識別輸入的單詞序列是否文法的句子。1、編寫代碼并分別編譯flex和bison產(chǎn)生相應(yīng)文件；2、comment函數(shù)調(diào)用yyinput，編譯的時候出現(xiàn)了鏈接錯誤，將lex.yy.c中的yyinput函數(shù)定義拷貝一份到input.lex,重命名為my_yyinput即可解決，另外還要修改生成的cgrammar-new.tab.c文件中的一段代碼并刪去“if（!yyin）yyin=stdin”才可以編譯通過（解析之前，還要設(shè)置yyin為輸入文件指針）；3、在命令行里利用生成的exe文件調(diào)用測試文件得到結(jié)果。五、實驗小結(jié)相對于flex源文件，bison源文件的編寫更為艱難，但通過實驗了解了flex與bison聯(lián)合編譯的思想和方法，并明白了bison將詞法分析階段的規(guī)則進行合并的過程，這些將有助于在接下來的實驗中完成簡單編譯器。實驗三（第三周）簡單桌面計算器一、實驗說明使用flex和bison開發(fā)了一個具有全部功能的桌面計算器，能夠支持變量，過程，循環(huán)和條件表達式，使它成為一個雖然短小但是具有現(xiàn)實意義的編譯器。重點學(xué)習(xí)抽象語法樹的用法，它具有強大而簡單的數(shù)據(jù)結(jié)構(gòu)來表示分析結(jié)果。該計算器具體需要實現(xiàn)的功能包括變量命名、實現(xiàn)賦值功能、實現(xiàn)比較表達式（大于、小于、等于等等）、實現(xiàn)if/then/else和do/while的流程控制、用戶可以自定義函數(shù)；簡單的錯誤恢復(fù)機制。最后編寫測試程序時首先自定義兩個函數(shù)sq和avg，sq函數(shù)使用Newton方法來迭代計算平方根；avg函數(shù)計算兩個數(shù)值的平均值。利用定義好的函數(shù)進行計算，得到計算結(jié)果并顯示出來。二、實驗原理與設(shè)計分析還要分析下，在Bison與Flex聯(lián)用時，Bison只定義標(biāo)記的ID。Flex則需要知道這些詞法標(biāo)記的ID，才能在識別到一個詞法標(biāo)記時返回這個ID給Bison。Bison傳遞這些ID給Flex的方法，就是在調(diào)用bison命令時使用參數(shù)-d。使用這個參數(shù)后，Bison會生成一個獨立的頭文件，該文件的名稱形式為name.tab.h。在Flex的詞法規(guī)則文件中，在定義區(qū)段里包含這個頭文件即可。在編譯器中最強大的數(shù)據(jù)結(jié)構(gòu)之一就是抽象語語法樹。抽象語法樹作為一種通用的中間表示，不僅包含各種語言共有的語法結(jié)構(gòu)，某些特定類型的樹節(jié)點還可以表示一些語言特有的語法結(jié)構(gòu)。抽象語法樹易于轉(zhuǎn)換成寄存器轉(zhuǎn)移語言，而寄存器轉(zhuǎn)移語言適合在不同平臺下進行優(yōu)化,這使得GCC的兩層中間表示具有良好的通用性。作為一種良好的中間表示,抽象語法樹包含了完整的源程序信息。利用抽象語法樹可以實現(xiàn)多種源程序處理工具，比如智能編輯器、源程序瀏覽器等。此外，抽象語法樹的解析器也可以作為程序靜態(tài)分析工具的前端，為其提供一種便于分析的輸入。抽象語法樹結(jié)構(gòu)比較簡單，其對應(yīng)的詞法規(guī)則和語法規(guī)則易于構(gòu)造，使用flex和bison工具生成的解析器能夠有效地對抽象語法樹進行解析。解析器由三部分組成,分別是flex生成的詞法分析器、bison生成的語法分析器和手工編寫的驅(qū)動程序。詞法分析器識別抽象語法樹文件的記號流，提供給語法分析器；語法分析器利用嵌入其中的語義動作識別語法樹節(jié)點，完成解析任務(wù)；驅(qū)動程序負(fù)責(zé)為詞法分析器和語法分析器提供一個調(diào)用接口，并提供解析所需的數(shù)據(jù)結(jié)構(gòu)和函數(shù)的實現(xiàn)。在計算器里，factor僅僅是為了告訴語法分析器各個操作符的相對優(yōu)先級，抽象語法樹可以把分析樹中的不需要關(guān)注的節(jié)點移除。三、實驗步驟和設(shè)計實現(xiàn)過程分析本部分主要說明一下計算器的設(shè)計過程以及在設(shè)計過程中用到的一些重點算法和思想等內(nèi)容。1、首先我們要做開始聲明部分，在.h頭文件中我們可以用以下語句來定義抽象語法樹的structast（intnodetype;structast*l;structast*r;};節(jié)點，且所有節(jié)點都有公共的初始nodetype。而刪除和釋放抽象語法樹可以用語句voidtreefree（structast*）來實現(xiàn)即可。常量使用numval，符號引用使用symref賦值使用symasgn，它有一個指向被賦值符號的指針和使用抽象語法樹表示的值；2、語法分析器的設(shè)計，其中在語法分析器的最后提供了小部分錯誤恢復(fù)機制，這讓我們有可能在錯誤發(fā)生時把語法分析器恢復(fù)到可以繼續(xù)工作的狀態(tài)；3、詞法分析器中設(shè)計六個比較操作符都返回一個帶有字面值以便于區(qū)分的CMP記號，其中這六個關(guān)鍵字和四個內(nèi)置函數(shù)通過文字模式加以識別，它們放在通用模式之前以便于在通用模式之前進行匹配；4、最后還要加一個輔助函數(shù)，正如《flex與bison》中所講的一樣，例程treefree的擴展版本會遞歸的遍歷一顆抽象語法樹并釋放這棵樹的所有節(jié)點。本計算器的核心例程是eval，它用來計算分析器中構(gòu)造的抽象語法樹。我們采用深度優(yōu)先遍歷算法來計算表達式的值；5、完成以上工作后我們就可以在命令行里依次輸入指令得到運行結(jié)果了：函莒醫(yī)員:命令提示符MicrosoftUindovs[版本6.1.7601]版權(quán)所有2009MicrosoftCorporationo保留所有權(quán)制。F:\WenJian、我的課程、系統(tǒng)實踐寸艮告寸6譯實踐Ibison\GnuWin32\bin>jsj.exe<jsj-ttx系統(tǒng)找不到寸差麗文件.F：XWenJianX?的課程、系統(tǒng)實踐寸艮告譯實踐Sbison\GnuWin32\bin>jsj.exe<jsj.txtDefinedsq;Def±nedaug=3_162=15>F=*nJian、我的課程、系統(tǒng)實踐寸艮告祺譯實踐<bison\GnuWin32\bin>四、實驗小結(jié)使用bison和flex工具學(xué)習(xí)編譯原理，遠(yuǎn)比單獨看書然后自己編寫一些程序生動的多。這樣你就不會在那些復(fù)雜的字符處理。但對于初學(xué)者來說，完全編譯出來本次試驗的桌面計算器的編譯器還是挺困難的。因此本次計算器的實現(xiàn)主要還是依靠flex與bison這本書的幫助才得以實現(xiàn)。本計算器雖然短小但卻很具有代表意義。我們添加了命名的變量和賦值、比較表達式、if和then等的流程控制內(nèi)置和用戶自定義函數(shù)以及錯誤恢復(fù)機制等。實驗四（第四周）操作系統(tǒng)實驗（Lab0實驗）一、實驗?zāi)康?、掌握OS基本概念：看在線課程，能理解OS原理與概念；看在線實驗指導(dǎo)書并分析源碼，能理解labcodes_answer的labs運行結(jié)果；2、掌握OS設(shè)計實現(xiàn)：在1的基礎(chǔ)上，能夠通過編程完成labcodes的8個lab實驗中的基本練習(xí)和實驗報告;3、本次lab0實驗主要是讓我們熟悉實驗環(huán)境以便于后續(xù)的實驗操作。二、實驗說明ucore的運行環(huán)境可以是真實的X86計算機，不過考慮到調(diào)試和開發(fā)的方便，我們可采用X86硬件模擬器，比如QEMU、BOCHS、VirtualBox、VMware、Player等。ucore的開發(fā)環(huán)境主要是GCC中的gcc、gas、ld和MAKE等工具，也可采用集成了這些工具的IDE開發(fā)環(huán)境Eclipse-CDT等。在分析源代碼上，可以采用Scitools提供的understand軟件（跨平臺），windows環(huán)境上的source>insight軟件，或者基于emacs+ctags，vim+ctags等，都可以比較方便在在一堆文件中查找變量、函數(shù)定義、調(diào)用訪問關(guān)系等。軟件開發(fā)的版本管理可以采用GIT、SVN等。比較文件和目錄的不同可發(fā)現(xiàn)不同實驗中的差異性和進行文件合并操作，可使用meld、kdiff3、UltraCompare等軟件。調(diào)試（deubg）實驗有助于發(fā)現(xiàn)設(shè)計中的錯誤，可采用gdb（配合qemu）等調(diào)試工具軟件。并可整個實驗的運行環(huán)境和開發(fā)環(huán)境既可以在Linux或Windows中使用。關(guān)于實驗環(huán)境的配置基本是有五種方式（在線實驗--基于"實驗樓"在線平臺、Windows下基于MingW進行實驗、Windows下基于VirtualBoxorVMWare進行實驗、在MACOS下進行實驗和手動在物理PC中安裝環(huán)境），我選擇的是手動在自己的電腦上上安裝ubuntu并在ubuntu系統(tǒng)中安裝實驗環(huán)境相關(guān)軟件在shell（比如gnome-terminal）下可執(zhí)行相關(guān)命令來安裝相關(guān)軟件。以下是在自己的筆記本上安裝實驗環(huán)境成功的截圖：wuyanfeiqwuyanfekX450VC:^/\ab/l>abcodes123/1ab1wuyanfei^wuyanfet-X450VCI-&Iscadtest模板圖片下■載票面examples?desktopnano.save茲共的祝揪文檔音樂wuyanfei@wuyanfei-X450VC:cdlab/labcDdesl23/lablhuyanfet@wuyanfnet-X45OVC：'/lab/l.abcode￡121/l.dbl$nakeqenuCthuxst)osIsloading…Spectalkernelsynbols:entry阪日鴕曲(phys)etext0x00103598(phys)edata0x0010eal6(phys)end(phys)Kernelexecutablenenor^footprint:球Bebp：0xooot>7bzgelp：oxO9ieD9b^rirgs：0K000i9(3940x000103940x00007b0^00100097kern/debug/kdebug.c:20S:printstackframe+21ebp：ex30007b39etp:OxOeH60ca5args7oK00&eO30G0x00006600Ox6e0O7ba8kern/debug/knonitor.c:125:pion_backtrace+lftebp:flxM007bSBeip;0x00100&97a00003330&x00007b8GEffff燦0OKOfl0Q7bB4kerri/trtt/tnlt.c：48：grade_backtracez+13ebp：en^o(&7b79etp：oxo?ioo0ceargstsxee&oooooOKffffeoo?ox曰白日57ba4kern/tntt/tDtt<c：53：gr3de_bdcktracel+38ebp：ex<JOt)&7b9eeip:Ox&aiflD&tlearas:flK6B000300皿包1洶％flKffffBflaaOjcOflaOSSldLinux文件系統(tǒng)被組織成一個有層次的樹形結(jié)構(gòu)。文件系統(tǒng)的最上層是/，或稱為根目錄。在Unix和Linux的設(shè)計理念中，一切皆為文件包括硬盤、分區(qū)和可插拔介質(zhì)。這就意味著所有其它文件和目錄（包括其它硬盤和分區(qū)）都位于根目錄中。例如：/home/jebediah/cheeses.odt給出了正確的完整路徑，它指向cheeses.odt文件，而該文件位于jebediah目錄下，該目錄又位于home目錄，最后，home目錄又位于根（/）目錄下。了解這些對今后更深一步了解操作系統(tǒng)的結(jié)構(gòu)尤為重要。使用命令行并不像您想象的那么困難。使用命令行不需要專門知識，和其它軟件一樣，它也僅僅是一個程序。Linux中絕大部分工作都可以用命令行完成，盡管大部分程序都有相應(yīng)的圖形工具，但有時這些圖形工具會捉襟見肘，不夠用。此時便是命令行大顯身手的時候。終端常常被稱為命令行或者shell。QEMU是一個通用并開放源代碼的模擬器，是一套由FabriceBellard所編寫的以GPL許可證分發(fā)源碼的模擬處理器，在GNU/Linux平臺上使用廣泛。其功能相當(dāng)?shù)膹姶?，例如：可以用QEMU來模擬一個完整的系統(tǒng)，同時，也可以用QEMU來實現(xiàn)系統(tǒng)源碼級的調(diào)試：（了解硬件對ucore帶來影響）和機器指令集。ucore目前支持的硬件環(huán)境是基于Intel80386以上的計算機系統(tǒng)。80386有四種運行模式：實模式、保護模式、SMM模式和虛擬8086模式。這里對涉及ucore的實模式、保護模式做一個簡要介紹。實模式：80386加電啟動后處于實模式運行狀態(tài)，在這種狀態(tài)下軟件可訪問的物理內(nèi)存空間不能超過1MB，且無法發(fā)揮Intel80386以上級別的32位CPU的4GB內(nèi)存管理能力。實模式將整個物理內(nèi)存看成分段的區(qū)域，程序代碼和數(shù)據(jù)位于不同區(qū)域，操作系統(tǒng)和用戶程序并沒有區(qū)別對待，而且每一個指針都是指向?qū)嶋H的物理地址。保護模式：實際上，80386就是通過在實模式下初始化控制寄存器，GDTR，LDTR，IDTR與TR等管理寄存器以及頁表，然后再通過加載CR0使其中的保護模式使能位置位而進入保護模式的。當(dāng)80386工作在保護模式下的時候，其所有的32根地址線都可供尋址，物理尋址空間高達4GB。在保護模式下，支持內(nèi)存分頁機制，提供了對虛擬內(nèi)存的良好支持。保護模式下80386支持多任務(wù)，還支持優(yōu)先級機制，不同的程序可以運行在不同的優(yōu)先級上。優(yōu)先級一共分0?34個級別，操作系統(tǒng)運行在最高的優(yōu)先級0上，應(yīng)用程序則運行在比較低的級別上；配合良好的檢查機制后，既可以在任務(wù)間實現(xiàn)數(shù)據(jù)的安全共享也可以很好地隔離各個任務(wù)。80386是32位的處理器，即可以尋址的物理內(nèi)存地址空間為2”32=4G字節(jié)。在理解操作系統(tǒng)的過程中，需要用到三個地址空間的概念。地址是訪問地址空間的索引。物理內(nèi)存地址空間是處理器提交到總線上用于訪問計算機系統(tǒng)中的內(nèi)存和外設(shè)的最終地址。一個計算機系統(tǒng)中只有一個物理地址空間。線性地址空間是每個運行的應(yīng)用程序看到的地址空間，在操作系統(tǒng)的虛存管理之下，每個運行的應(yīng)用程序都認(rèn)為自己獨享整個計算機系統(tǒng)的地址空間，這樣可讓多個運行的應(yīng)用程序之間相互隔離。處理器負(fù)責(zé)把線性地址轉(zhuǎn)換成物理地址。在UbuntuLinux中的C語言編程主要基于GNUC的語法，通過gcc來編譯并生成最終執(zhí)行文件。GNUmake（簡稱make）是一種代碼維護工具，在大中型項目中，它將根據(jù)程序各個模塊的更新情況，自動的維護和生成目標(biāo)代碼。make命令執(zhí)行時，需要一個makefile（或Makefile）文件，以告訴make命令需要怎么樣的去編譯和鏈接程序。首先，我們用一個示例來說明makefile的書寫規(guī)則。以便給大家一個感興認(rèn)識。這個示例來源于gnu的make使用手冊，在這個示例中，我們的工程有8個c文件，和3個頭文件，我們要寫一個makefile來告訴make命令如何編譯和鏈接這幾個文件。只要我們的makefile寫得夠好，所有的這一切，我們只用一個make命令就可以完成，make命令會自動智能地根據(jù)當(dāng)前的文件修改的情況來確定哪些文件需要重編譯，從而自己編譯所需要的文件和鏈接目標(biāo)程序。三、實驗步驟與分析根據(jù)一個操作系統(tǒng)的設(shè)計實現(xiàn)過程，我們可以有如下的實驗步驟：啟動操作系統(tǒng)的bootloader，用于了解操作系統(tǒng)啟動前的狀態(tài)和要做的準(zhǔn)備工作，了解運行操作系統(tǒng)的硬件支持，操作系統(tǒng)如何加載到內(nèi)存中，理解兩類中斷一“外設(shè)中斷”，“陷阱中斷”等；物理內(nèi)存管理子系統(tǒng)，用于理解x86分段/分頁模式，了解操作系統(tǒng)如何管理物理內(nèi)存；虛擬內(nèi)存管理子系統(tǒng)，通過頁表機制和換入換出（swap）機制，以及中斷-“故障中斷”、缺頁故障處理等，實現(xiàn)基于頁的內(nèi)存替換算法；內(nèi)核線程子系統(tǒng)，用于了解如何創(chuàng)建相對與用戶進程更加簡單的內(nèi)核態(tài)線程，如果對內(nèi)核線程進行動態(tài)管理等；用戶進程管理子系統(tǒng)，用于了解用戶態(tài)進程創(chuàng)建、執(zhí)行、切換和結(jié)束的動態(tài)管理過程，了解在用戶態(tài)通過系統(tǒng)調(diào)用得到內(nèi)核態(tài)的內(nèi)核服務(wù)的過程；處理器調(diào)度子系統(tǒng)，用于理解操作系統(tǒng)的調(diào)度過程和調(diào)度算法；同步互斥與進程間通信子系統(tǒng)，了解進程間如何進行信息交換和共享，并了解同步互斥的具體實現(xiàn)以及對系統(tǒng)性能的影響，研究死鎖產(chǎn)生的原因，以及如何避免死鎖；文件系統(tǒng)，了解文件系統(tǒng)的具體實現(xiàn)，與進程管理等的關(guān)系，了解緩存對操作系統(tǒng)IO訪問的性能改進，了解虛擬文件系統(tǒng)（VFS）、buffer、cache和disk、driver之間的關(guān)系。其中每個開發(fā)步驟都是建立在上一個步驟之上的，一步步完成從理解操作系統(tǒng)原理到實踐操作系統(tǒng)設(shè)計與實現(xiàn)的探索過程。實驗五（第五周）操作系統(tǒng)實驗（Labi實驗）一、實驗?zāi)康耐ㄟ^分析和實現(xiàn)這個bootloader和ucoreOS我們可以了解：1、計算機原理中CPU的編址與尋址、基于分段機制的內(nèi)存管理CPU的中斷機制以及外設(shè)（串口/并口/CGA，時鐘，硬盤）；2、Bootloader軟件中編譯運行bootloader的過程、調(diào)試bootloader的方法、PC啟動bootloader的過程、ELF執(zhí)行文件的格式和加載、外設(shè)訪問：讀硬盤，在CGA上顯示字符串；

3、ucoreOS軟件編譯運行ucoreOS的過程、ucoreOS的啟動過程、調(diào)試ucoreOS的方法、函數(shù)調(diào)用關(guān)系（在匯編級了解函數(shù)調(diào)用棧的結(jié)構(gòu)和處理過程）、中斷管理（軟件相關(guān)的中斷處理）、外設(shè)管理（時鐘）。二、實驗說明ucore的運行環(huán)境可以是真實的X86計算機，不過考慮到調(diào)試和開發(fā)的方便，我們可采用X86硬件模擬器。1|,底統(tǒng)肩用虹「］（E聽問，！I郴如S.CH1k網(wǎng)漁叫沽X虹，頊j=*iAf路理[的％石（E聽問，！I郴如S.CH1k網(wǎng)漁叫沽X虹，頊j=*iAf路理[的％石0?：ir解現(xiàn)*t畢何感花|啡何河凡ij咔心明賣仙I敏cpirtiiiIFr*g啪?耳［gWHWiEW操作系統(tǒng)是一個軟件，也需要通過某種機制加載并運行它。在這里我們將通過另外一個更加簡單的軟件-bootloader來完成這些工作。為此，我們需要完成一個能夠切換到x86的保護模式并顯示字符的bootloader，為啟動操作系統(tǒng)ucore做準(zhǔn)備。labl提供了一個非常小的bootloader和ucoreOS，整個bootloader執(zhí)行代碼小于512個字節(jié)，這樣才能放到硬盤的主引導(dǎo)扇區(qū)中。而labl中包含一個bootloader和一個OS。這個bootloader可以切換到X86保護模式，能夠讀磁盤并加載ELF執(zhí)行文件格式，并顯示字符。而這labl中的OS只是一個可以處理時鐘中斷和顯示字符的簡單的OS。卜boot引導(dǎo)扇區(qū)的代碼卜kern操作系統(tǒng)內(nèi)核代碼Labi代碼樹卜libsJOS的C代碼庫卜tools代碼測試工具和腳本卜Makefile代表整體組裝運行的過程三、OS啟動過程分析PC加電啟動：Bochs模擬硬件，可以通過修改Bochs的配置調(diào)整硬件。BIOS運行，BIOS程序被Bochs加載到0xF0000-0x100000處于實模式下，尋址空間1M檢查和初始化硬件，加載引導(dǎo)扇區(qū)到0000:7c00-0000:7dff；引導(dǎo)扇區(qū)（即BootLoader）執(zhí)行:BIOS的最后一條指令是跳轉(zhuǎn)到0x7c00處，把CPU控制權(quán)交給了BootLoader程序，實模式轉(zhuǎn)換為保護模式，加載內(nèi)核文件；內(nèi)核開始執(zhí)行：初始化內(nèi)核數(shù)據(jù)結(jié)構(gòu)，運行終端。（操作系統(tǒng)啟動流程圖）三、實驗過程與詳細(xì)分析（1）理解通過make生成執(zhí)行文件的過程首先說一下操作系統(tǒng)鏡像文件ucore.img是如何一步一步生成的：linux系統(tǒng)下在命令行中輸入“makeV=”即可看到生成過程，下面我以流程圖的方式分步驟一一說明下操作系統(tǒng)鏡像文件的生成過程：'首先把C語言的源代碼進行編譯成為.o文件，也就是目標(biāo)文件’ld命令將這些目標(biāo)文件轉(zhuǎn)變成可執(zhí)行文件，比如此處的bootblock.outdd命令把bootloder放到ucore.imgcount的虛擬硬盤之中還生成兩個軟件，一個是Bootloader，另一個是kernel分析labl/tools/sign.c中的代碼一個被系統(tǒng)認(rèn)為是符合規(guī)范的硬盤主引導(dǎo)扇區(qū)的特征可以從以下代碼看出，即一個規(guī)范的硬盤引導(dǎo)扇區(qū)的大小為512字節(jié)，硬盤結(jié)束標(biāo)志位55AA。fclose(ifp);buf[510]=0x55;buf[511]=0xAA;FILE*ofp=fopen(argv[2],"wb+");size=fwrite(buf,1,512,ofp);if(size!=512){fprintf(stderr,"write'%s'error,sizeis%d.\n",argv[2],size);return-1;}fclose(ofp);printf("build512bytesbootsector:'%s'success!\n",argv[2]);return0;順便談一下Makefile，它是用于自動編譯和鏈接的，一個工程有很多文件組成，每一個文件的改變都會導(dǎo)致工程的重新鏈接，但是不是所有的文件都需要重新編譯，Makefile中紀(jì)錄有文件的信息，在make時會決定在鏈接的時候需要重新編譯哪些文件。Makefile就是讓編譯器知道要編譯一個文件需要依賴其他的哪些文件。當(dāng)那些依賴文件有了改變，編譯器會自動的發(fā)現(xiàn)最終的生成文件已經(jīng)過時，而重新編譯相應(yīng)的模塊。使用automake，程序開發(fā)人員只需要寫一些簡單的含有預(yù)定義宏的文件，由autoconf根據(jù)一個宏文件生成configure，由automake根據(jù)另一個宏文件生成Makefile.in，再使用configure依據(jù)Makefile.in來生成一個符合慣例的Makefileo主引導(dǎo)扇區(qū)包括硬盤主引導(dǎo)記錄和分區(qū)表DPT。其中主引導(dǎo)記錄的作用就是檢查分區(qū)表是否正確以及確定哪個分區(qū)為引導(dǎo)分區(qū)，并在程序結(jié)束時把該分區(qū)的啟動程序，也就是操作系統(tǒng)引導(dǎo)扇區(qū)調(diào)入內(nèi)存加以執(zhí)行。主引導(dǎo)扇區(qū)記錄硬盤上每一個分區(qū)的數(shù)據(jù)的地方，這個地方不存放實際的數(shù)據(jù)，只保存每一個扇區(qū)的信息。類似圖書館里面的書和圖書館的藏書目錄，主引導(dǎo)扇區(qū)是目錄，每一個扇區(qū)里面存放的是書，如果目錄丟失了，你將無法找到想要的書了，當(dāng)然這個目錄在某種情況下是能用軟件恢復(fù)的的。完成這個操作的方法有兩種，一種是使用系統(tǒng)的格式化程序，我們知道在安裝系統(tǒng)的時候我們最開的的操作就是劃出分區(qū)，格式化硬盤才可以，這個操作就能完成。還有一種就是使用專業(yè)的硬盤操作軟件，在DOS下完成。(2)使用qemu執(zhí)行并調(diào)試labl中的軟件本次練習(xí)主要是了解從CPU加電后執(zhí)行的第一條指令開始，單步跟蹤BIOS的執(zhí)行并在初始化位置0x7c00設(shè)置實地址斷點,測試斷點正常、從0x7c00開始跟蹤代碼運行，將單步跟蹤反匯編得到的代碼與bootasm.S和bootblock.asm進行比較。然后自己找一個bootloader或內(nèi)核中的代碼位置，設(shè)置斷點并進行測試。在初始化位置0x7c00設(shè)置實地址斷點，測試斷點正常，下面是我在linux環(huán)境下運行的一張截圖：在tools/gdbinit結(jié)尾加上setarchitecturei8086b*0x7c00//在0x7c00處設(shè)置斷點。continuex/2i$pc〃顯示當(dāng)前eip處的匯編指令TerminalSxOOOOfffOin??()warning:AhandlerfortheOSABI"GNUJLinux"isnotbuiltintothisconfigurottonofG昭.AttemptingtocontinuewiththedefaultLSO86settings.ThetargetarchitectureisassunedtobeIBOS6Breakpoint1atOx/czOOBreakpointL,0X3OOO7C0Stn??()TOC\o"1-5"\h\z=>Ok7cO0:cltOk7c01:cld(gdB)|我們主要通過硬件模擬器qemu來進行各種實驗。在實驗的過程中我們可能會遇上各種各樣的問題，調(diào)試是必要的。qemu支持使用gdb進行的強大而方便的調(diào)試。所以用好qemu和gdb是完成各種實驗的基本要素。一將執(zhí)行的匯編代碼與bootasm.S和bootblock.asm進行比較可知Notice:在q.log中進入BIOS之后的跳轉(zhuǎn)地址與實際應(yīng)跳轉(zhuǎn)地址不相符，匯編代碼也與bootasm.S和bootblock.asm不相同，這是由于在gdb之中調(diào)試的原因，可以直接輸入makedebug，在生成的qemu虛擬機之中進行調(diào)試可以看到在虛擬機中運行的匯編代碼，之后再與bootasm.S和bootblock.asm進行比較與bootasm.S和bootblock.asm中的代碼相同。分析bootloader進入保護模式的過程本次以注釋和代碼相結(jié)合的方式分析bootloader進入保護模式的過程：globlstartstart:.code16#關(guān)中斷，并清除方向標(biāo)志，即將DF置“0”，這樣(E)SI及(E)DI的修改為增量clicld#清零各數(shù)據(jù)段寄存器:DS、ES、FSxorw%ax,%axmovw%ax,%dsmovw%ax,%esmovw%ax,%ss

#使能A20地址線，這樣80386就可以突破址空間seta20.1:inb$0x64,%al$0x2,%aljnzseta20.1movb$0xd1,%aloutb%al,$0x64#使能A20地址線，這樣80386就可以突破址空間seta20.1:inb$0x64,%al$0x2,%aljnzseta20.1movb$0xd1,%aloutb%al,$0x64seta20.2:inb$0x64,%altestb$0x2,%aljnzseta20.2movb$0xdf,%aloutb%al,$0x60#初始化gdtlgdtgdtdesc#進入保護模式movl%cr0,%eaxorl$CR0_PE_ON,%eaxmovl%eax,%cr0#長跳轉(zhuǎn)ljmp$PROT_MODE_CSEG,$protcseg.code32protcseg:#設(shè)置段寄存器，并建立堆棧movw$PROT_MODE_DSEG,%axmovw%ax,%dsmovw%ax,%esmovw%ax,%fsmovw%ax,%gsmovw%ax,%ss#設(shè)置堆棧movl$0x0,%ebpmovl$start,%esp#棧頂為0x7c00#進入bootmain，不再返回callbootmainspin:jmpspin1MB訪存現(xiàn)在，而可訪問4GB的32位地#等待8042鍵盤控制器不忙testb#等待8042鍵盤控制器不忙#打開A20讀一個扇區(qū)的流程大致如下:首先讀I/O地址0x1f7,等待磁盤準(zhǔn)備好，寫I/O地址0x1f2~0x1f5,0x1f7，發(fā)出讀取第offseet個扇區(qū)處的磁盤數(shù)據(jù)的命令，讀I/O地址0x1f7,等待磁盤準(zhǔn)備好，連續(xù)讀I/O地址0x1f0,然后把磁盤扇區(qū)數(shù)據(jù)讀到指定內(nèi)存。最后在bootmain函數(shù)中完成加載ELF格式os的操作如下：1:讀取ELF的頭部；2:判斷ELF文件是否是合法；3:將描述表的頭地址存在ph；4:按照描述表將ELF文件中數(shù)據(jù)載入內(nèi)存；5:根據(jù)ELF頭部儲存的入口信息，找到內(nèi)核的入口。實現(xiàn)函數(shù)調(diào)用堆棧跟蹤函數(shù)在這個練習(xí)中需要注意ss:ebp指向的堆棧位置儲存著caller的ebp，以此為線索可以得到所有使用堆棧的函數(shù)ebp。ss:ebp+4指向caller調(diào)用時的eip，ss:ebp+8等是參數(shù)。完善中斷初始化和處理1、完善初始化函數(shù)idt_init可以在/lab1/kern/mm/mmu.h中可以找到SETGATE函數(shù)，查找其具體操作。idt_init(void){externuintptr_t__vectors[];inti;for(i=0;i<sizeof(idt)/sizeof(structgatedesc);i++){SETGATE(idt[i],0,GD_KTEXT,__vectors[i],DPL_KERNEL);//設(shè)置IDT}lidt(&idt_pd);//載入IDT表2、完善中斷處理函數(shù)trapcaseIRQ_OFFSET+IRQ_TIMER:ticks++;〃一次中斷累加1if(ticks%TICK_NUM==0){print_ticks();}break;實驗六(第六周選作)物理內(nèi)存管理(lab2實驗)一、實驗?zāi)康?、理解基于段頁式內(nèi)存地址的轉(zhuǎn)換機制；2、理解頁表的建立和使用方法；3、理解物理內(nèi)存的管理方法。二、實驗說明Lab0和labl為必做實驗內(nèi)容，由于時間和精力有限，lab2到lab8的實驗就暫時只能做并分析一下lab2的實驗內(nèi)容了。實驗二主要涉及操作系統(tǒng)的物理內(nèi)存管理。操作系統(tǒng)為了使用內(nèi)存，還需高效地管理內(nèi)存資源。在實驗二中我們會了解并且自己動手完成一個簡單的物理內(nèi)存管理系統(tǒng)。三、實驗原理與分析本次實驗主要完成ucore內(nèi)核對物理內(nèi)存的管理工作。參ucore總控函數(shù)kern_init的代碼，可以清楚地看到在調(diào)用完成物理內(nèi)存初始化的pmm_init函數(shù)之前和之后，是已有l(wèi)abl實驗的工作，好像沒啥修改。其實不是的，ucore有兩個方面的擴展。首先，bootloader的工作有增加，在bootloader中，完成了對物理內(nèi)存資源的探測工作（可進一步參閱附錄A和附錄B），讓ucorekernel在后續(xù)執(zhí)行中能夠基于bootloader探測出的物理內(nèi)存情況進行物理內(nèi)存管理初始化工作。其次，bootloader不像lab1那樣，直接調(diào)用kern_init函數(shù)，而是先調(diào)用位于lab2/kern/init/entry.S中的kern_entry函數(shù)。kern_entry函數(shù)的主要任務(wù)是為執(zhí)行kern_init建立一個良好的C語言運行環(huán)境（設(shè)置堆棧），而且臨時建立了一個段映射關(guān)系，為之后建立分頁機制的過程做一個準(zhǔn)備。完成這些工作后，才調(diào)用kern_init函數(shù)。kern_init函數(shù)在完成一些輸出并對lab1實驗結(jié)果的檢查后，將進入物理內(nèi)存管理初始化的工作，即調(diào)用pmm_init函數(shù)完成物理內(nèi)存的管理，這也是我們lab2的內(nèi)容。接著是執(zhí)行中斷和異常相關(guān)的初始化工作，即調(diào)用pic_init函數(shù)和idt_init函數(shù)等，這些工作與lab1的中斷異常初始化工作的內(nèi)容是相同的。為了完成物理內(nèi)存管理，這里首先需要探測可用的物理內(nèi)存資源；了解到物理內(nèi)存位于什么地方，有多大之后，就以固定頁面大小來劃分整個物理內(nèi)存空間，并準(zhǔn)備以此為最小內(nèi)存分配單位來管理整個物理內(nèi)存，管理在內(nèi)核運行過程中每頁內(nèi)存，設(shè)定其可用狀態(tài)（free的，used的，還是reserved的），這其實就對應(yīng)了我們在課本上講到的連續(xù)內(nèi)存分配概念和原理的具體實現(xiàn)；接ucorekernel就要建立頁表，啟動分頁機制，讓CPU的MMU把預(yù)先建立好的頁表中的頁表項讀入到TLB中，根據(jù)頁表項描述的虛擬頁（Page）與物理頁幀（PageFrame）的對應(yīng)關(guān)系完成CPU對內(nèi)存的讀、寫和執(zhí)行操作。這一部分其實就對應(yīng)了我們在課本上講到內(nèi)存映射、頁表、多級頁表等概念和原理的具體實現(xiàn)。在代碼分析上，我們可以根據(jù)執(zhí)行流程來直接看源代碼，并可采用GDB源碼調(diào)試的手段來動態(tài)地分析ucore的執(zhí)行過程。內(nèi)存管理相關(guān)的總體控制函數(shù)是pmm_init函數(shù)，它完成的王要工作包括：初始化物理內(nèi)存頁管理器框架pmm_manager；建立空閑的page鏈表，這樣就可以分配以頁（4KB）為單位的空閑內(nèi)存了；檢查物理內(nèi)存頁分配算法；為確保切換到分頁機制后，代碼能夠正常執(zhí)行，先建立一個臨時二級頁表；建立一一映射關(guān)系的二級頁表；使能分頁機制；從新設(shè)置全局段描述符表；取消臨時二級頁表；檢查頁表建立是否正確；通過自映射機制完成頁表的打印輸。四、實驗練習(xí)過程與詳細(xì)分析1、實現(xiàn)firstfit連續(xù)物理內(nèi)存分配算法在實現(xiàn)firstfit內(nèi)存分配算法的回收函數(shù)時，要考慮地址連續(xù)的空閑塊之間的合并操作。物理內(nèi)存頁管理器順著雙向鏈表進行搜索空閑內(nèi)存區(qū)域，直到找到一個足夠大的空閑區(qū)域，這是一種速度很快的算法，因為它盡可能少地搜索鏈表。如果空閑區(qū)域的大小和申請分配的大小正好一樣，則把這個空閑區(qū)域分配出去，成功返回；否則將該空閑區(qū)分為兩部分，一部分區(qū)域與申請分配的大小相等，把它分配出去，剩下的一部分區(qū)域形成新的空閑區(qū)。其釋放內(nèi)存的設(shè)計思路很簡單，只需把這塊區(qū)域重新放回雙向鏈表中即可。default_init_memmap()函數(shù)這個函數(shù)是用來初始化空閑頁鏈表的。主要有兩個步驟：初始化每一個空閑頁，計算空閑頁的總數(shù)。staticvoiddefault_init_memmap(structPage*base,size_tn)(assert(n>0);structPage*p=base;for(;p!=base+n;p++)(〃檢查此頁是否是保留頁assert(PageReserved(p));//設(shè)置標(biāo)志位p->flags=0;SetPageProperty(p);//將引用計數(shù)清零p->property=0;set_page_ref(p,0);//使用頭插法將空閑頁插入到鏈表(使用頭插法是因為地址是從低地址向高地址增長)list_add_before(&free_list,&(p->page_link));}nr_free+=n;//本行用于計算空閑頁的總數(shù)base->property=n;}default_alloc_pages()函數(shù)這個函數(shù)是用來分配空閑頁鏈表的。大致可以分為七個步驟：第一步：尋找足夠大的空閑塊第二步：如果找到了，重新設(shè)置標(biāo)志位，從空閑鏈表中刪除此頁第三步：判斷空閑塊大小是否合適第四步：如果不合適，分割頁塊第五步：如果合適則不進行操作第六步：計算剩余空閑頁個數(shù)第七步：返回分配的頁塊地址staticstructPage*default_alloc_pages(size_tn)(assert(n>0);if(n>nr_free)(returnNULL;}list_entry_t*le,*len;le=&free_list;//在空閑頁鏈表中尋找合適大小的頁塊while((le=list_next(le))!=&free_list)(structPage*p=le2page(le,page_link);//找到合適頁塊if(p->property>=n)(inti;for(i=0;i<n;i++){len=list_next(le);structPage*pp=le2page(le,page_link);//設(shè)置每一頁的標(biāo)志位SetPageReserved(pp);ClearPageProperty(pp);//O除此頁的鏈接list_del(le);le=len;}if(p->property>n){//如果找到的頁塊大小合適則分割大頁塊(le2page(le,page_link))->property=p->property-n;}〃如果大小合適則不需要操作了ClearPageProperty(p);SetPageReserved(p);nr_free-=n;returnp;}}returnNULL;}default_free_pages()函數(shù)這個函數(shù)的作用是釋放已經(jīng)使用完的頁，把他們合并到freelist中。這個函數(shù)的基本完成思想和思路為：1、首先在freelist中查找合適的位置以供插入；2、然后改變被釋放頁的標(biāo)志位，以及頭部的計數(shù)器；3、嘗試在freelist中向高地址或低地址合并；staticvoiddefault_free_pages(structPage*base,size_tn){assert(n>0);//本行用來檢測標(biāo)志位是否有錯誤assert(PageReserved(base));list_entry_t*le=&free_list;structPage*p;//查找插入位置while((le=list_next(le))!=&free_list){p=le2page(le,page_link);if(p>base){break;}}〃向插入位置插入多個頁并設(shè)置標(biāo)志位for(p=base;p<base+n;p++){《系統(tǒng)軟件開發(fā)實踐》實驗報告list_add_