王　雷

Windows操作系統(tǒng)內(nèi)核、設(shè)計(jì)操作系統(tǒng)實(shí)驗(yàn)提供了一個很好的基礎(chǔ)。但是由于WRK的代碼量很大,在缺乏指導(dǎo)的情況下學(xué)生很難有效地在WRK上完成操作系統(tǒng)原理實(shí)驗(yàn)。本文在分析WRK進(jìn)程工作集的基礎(chǔ)上,設(shè)計(jì)了三個針對工作集的實(shí)驗(yàn),并給出了實(shí)驗(yàn)效果驗(yàn)證方法。

關(guān)鍵詞:操作系統(tǒng);WRK;工作集

中圖分類號:G642 文獻(xiàn)標(biāo)識碼:B

1引言

工作集是內(nèi)存管理一個相當(dāng)重要的概念,Windows系統(tǒng)通常將工作集分為進(jìn)程工作集與系統(tǒng)工作集,分別用于跟蹤各個進(jìn)程與系統(tǒng)的物理內(nèi)存使用情況。Windows內(nèi)核中對工作集頁面的操作分工作集管理器(系統(tǒng)級)的頁面修剪算法和進(jìn)程自己的頁面替換算法兩種,前者主要是定時掃描系統(tǒng)的內(nèi)存利用情況,同時對某些進(jìn)程進(jìn)行頁面修剪,比如選定優(yōu)先級低的進(jìn)程,應(yīng)用最近最久未使用算法(LRU)選定要刪除的頁面進(jìn)行刪除;而后者主要是在進(jìn)程內(nèi)部,當(dāng)進(jìn)程申請頁面超過一定峰值再申請頁面時,工作集大小不再增加,而是以一定的策略替換已有頁面。

本文以WRK為實(shí)驗(yàn)平臺,結(jié)合內(nèi)核源代碼和WinDbg調(diào)試工具,以Windows內(nèi)存管理的工作集頁面替換為分析對象,分析進(jìn)程工作集的峰值及頁面替換算法,設(shè)計(jì)了相應(yīng)的實(shí)驗(yàn)修改頁面替換算法,并給出了實(shí)驗(yàn)應(yīng)達(dá)到的效果。

2工作集分析

2.1工作集數(shù)據(jù)結(jié)構(gòu)

EPROCESS是描述進(jìn)程的結(jié)構(gòu),工作集的相關(guān)結(jié)構(gòu)也可以從這里找到,與工作集相關(guān)的數(shù)據(jù)結(jié)構(gòu)主要有MMSUPPORT、MMWSL、MMWSLE MMWSLENTRY、MMPTE、PMMWSLE_HASH,其主要關(guān)系如下圖1工作集結(jié)構(gòu)圖,理解工作集結(jié)構(gòu)間的關(guān)系,對內(nèi)核調(diào)試、算法修改、內(nèi)核系統(tǒng)調(diào)用的添加都極及有幫助。

2.2工作集代碼分析

工作集相關(guān)代碼分布如表1所示。本小節(jié)針對前面分析的工作集的結(jié)構(gòu),選取幾個具有代表性的操作函數(shù)進(jìn)行分析,為后面進(jìn)行頁面算法的修改打下基礎(chǔ)。

2.2.1頁面替換算法分析

首先調(diào)用MiAddWorkingSetPage()向工作集中添加頁面失敗時,調(diào)用中MiDoReplacement()函數(shù)對工作集進(jìn)行替換,同時修改MiReplacing為True,說明當(dāng)前系統(tǒng)頁面已經(jīng)緊張,以便在啟動工作集管理器時,根據(jù)MiReplacing的值執(zhí)行修剪操作。其中MiDoReplacement()主要調(diào)用了MiReplaceWorkingSetEntry()進(jìn)行頁面替換。

(1) 修剪時刻。根據(jù)如下三個條件:

① 當(dāng)前可用頁面數(shù)Available少于當(dāng)前需要的頁面數(shù);

② 本工作集中已經(jīng)有被替換頁面的記錄,MiReplacing == TRUE;

③ 有超過可用頁面數(shù)1/4的頁面被循環(huán)用作后備頁面;

以上條件滿足一個則立即進(jìn)行修剪操作,其中設(shè)置Criteria標(biāo)準(zhǔn)的相應(yīng)變量。

(2) 老化時刻。當(dāng)修剪條件全不成立時,當(dāng)前可用頁面Available小于限值20000,則進(jìn)行老化操作。

(3) 不操作。在1,2均不成立條件下,說明當(dāng)前系統(tǒng)中還有大量內(nèi)存可用,OutFlags=0,作為返回值,不進(jìn)行任何操作。

此時確定的工作集處理標(biāo)準(zhǔn),保存在WorkingSetRequest Flags(OutFlags=0)和TrimCriteria中,如果WorkingSetRequest Flags非零,即需要進(jìn)行修剪或者老化操作,具體調(diào)用Mi ProcessWorkingSets (WorkingSetRequestFlags, &TrimCriteria)做具體處理。如果WorkingSetRequestFlags為零,則不做操作。接下來查看修改頁面鏈表的計(jì)數(shù)器MmModified PageListHead.Total是否超過限制MmModified PageMaximum,若超過則激活修改頁面寫回器工作。

2.2.2釋放頁面過程分析

MiTrimWorkingSet()根據(jù)傳入的修剪標(biāo)準(zhǔn),確定需要進(jìn)行移除的工作集頁面的索引號和釋放的頁面數(shù),并將其封裝在WsleFlushList結(jié)構(gòu)中,作為參數(shù)傳給MiFreeWsleList,具體頁面釋放操作由MiFreeWsleList來完成。

Windows操作系統(tǒng)是一個多任務(wù)系統(tǒng),雖然已經(jīng)確定了要釋放的頁面的索引號,但是在確定索引號到調(diào)用本函數(shù)真正釋放頁面,期間所確定的頁面可能又被其他進(jìn)程共享,這種情況僅需要調(diào)用MiDecrementShareCount()函數(shù)使共享計(jì)數(shù)器減一,再或是此頁面是一原型頁表項(xiàng),所以要進(jìn)行第一次循環(huán),將所有這些情況的FlushIndex()置零,然后在接下來的循環(huán)中調(diào)用MiRemoveWsle()移除頁面。

3使用WinDbg查看工作集

WinDbg可以用于Kernel模式調(diào)試和用戶模式調(diào)試。我們編寫了一個應(yīng)用程序,申請100頁內(nèi)存。然后在內(nèi)核設(shè)定斷點(diǎn),讓內(nèi)核停下查看進(jìn)程狀態(tài)。

(1) 用dt命令輸出Vm的詳細(xì)信息

kd> dt nt!_MMSUPPORT 81de1de0

+0x000 WorkingSetExpansionLinks : _LIST_ ENTRY [ 0x808a4bb0 - 0x819ab648 ]

+0x008 LastTrimTime:_LARGE_INTEGER 0x1c7 b881`3b7cd070

+0x010 Flags: _MMSUPPORT_FLAGS

+0x014 PageFaultCount : 0x189

+0x018 PeakWorkingSetSize : 0x18d

+0x01c GrowthSinceLastEstimate : 0x189

+0x020 MinimumWorkingSetSize : 0x32

+0x024 MaximumWorkingSetSize : 0x159

+0x028 VmWorkingSetList : 0xc0502000

……

Vm結(jié)構(gòu)的類型是_MMSUPPORT,可以看出當(dāng)前工作集大小是0x18d頁,缺頁次數(shù)0x189頁,工作集最大值0x159頁,最小值0x32頁。

工作集鏈表結(jié)構(gòu)是_MMWSL可以看出其地址想對于_MMSUPPORT的偏移是0x028,下面計(jì)算_MMWSL的地址:

kd> ?(81de1de0+0x028)

Evaluate expression: -2116149752 = 81de1e08

kd> dd 81de1e08 l 1

顯示81de1e08存放的內(nèi)容是c0502000,這才是_MMWSL真正地址。

(2) 用dt命令輸出工作集鏈表結(jié)構(gòu)_MMWSL的詳細(xì)信息

kd> dt nt!_MMWSL c0502000

+0x000 FirstFree: 0x18d

//下次進(jìn)行工作集頁面添加的位置

+0x004 FirstDynamic : 4

//工作集頁面中第一個可用頁面的下標(biāo)

+0x008 LastEntry: 0x23b

//工作集頁面中最后一個可用頁面的下標(biāo)

+0x00c NextSlot : 4

//進(jìn)行頁面修剪算法是據(jù)此搜索最優(yōu)替換頁面

……

(3) 查看工作集頁面項(xiàng)(所有頁面虛擬地址)的詳細(xì)信息

kd> dd C0502698 l 0x18d

c0502698c0300203 c0301203 c0501203 c0502203

c05026a8c01ff201 7ffc2009 7ffa6009 7ffa5009

c05026b87ffa4009 7ffa3009 7ffd0009 7ffa1009

c05026c87c94d001 0012f201 c01f2201 7c9b7221

……

c0502c9800a40201 00a50201 00a60201 00a70201

c0502ca800a80201 00a90201 00aa0201 00ab0201

c0502cb800ac0201 00ad0201 00ae0201 00af0201

c0502cc800b00201

用斜體表示的第一列是虛擬地址地址,每一行的四項(xiàng)分別是以前面虛擬地址為起始位置的32字節(jié)的數(shù)據(jù),每項(xiàng)代表一頁的虛擬地址,地址后面的3位(201)是頁面的屬性。

通過使用WinDbg,可以對下面的實(shí)驗(yàn)進(jìn)行驗(yàn)證。

4實(shí)驗(yàn)設(shè)計(jì)

通過前面的分析,設(shè)計(jì)了三個實(shí)驗(yàn)。

4.1實(shí)驗(yàn)項(xiàng)目1:閱讀代碼——頁面替換算法分析

頁面替換算法是操作系統(tǒng)原理算法中重要的算法之一,涉及到進(jìn)程管理、存儲管理。當(dāng)進(jìn)程申請的頁面數(shù)目達(dá)到工作集的峰值時,若再申請頁面,系統(tǒng)就會根據(jù)一定的替換算法替換舊的頁面,本實(shí)驗(yàn)項(xiàng)目可借助WinDbg并結(jié)合閱讀WRK源代碼來完成。

(1) 本實(shí)驗(yàn)項(xiàng)目主要以下三方面要求:

① 找到進(jìn)程工作集頁面的峰值。

② 結(jié)合WinDbg在調(diào)試過程中內(nèi)核棧的功能,分析從缺頁中斷到執(zhí)行替換算法的代碼路徑(函數(shù)調(diào)用關(guān)系),并分析各函數(shù)的基本功能。

③ 詳細(xì)分析頁面替換算法的過程,這是后面進(jìn)行頁面替換算法修改的基礎(chǔ)。

(2) 實(shí)驗(yàn)結(jié)果驗(yàn)證要求:

結(jié)合WinDbg在算法處設(shè)置斷點(diǎn),單步運(yùn)行驗(yàn)證自己對算法分析的正確性,驗(yàn)證情況記錄下來,作為提交文檔的一部分。

4.2實(shí)驗(yàn)項(xiàng)目2:頁面替換算法的修改

本實(shí)驗(yàn)是在實(shí)驗(yàn)項(xiàng)目1的基礎(chǔ)上修改頁面替換算法,實(shí)驗(yàn)前讀者還應(yīng)該深刻理解工作集內(nèi)部的結(jié)構(gòu),頁面的存放位置等。

(1) 實(shí)驗(yàn)要求:

① 完成頁面替換算法的修改。

② 修改完成后重新編譯內(nèi)核,并用新的內(nèi)核映像啟動系統(tǒng)。

③ 在新的算法處設(shè)置斷點(diǎn)觀察,確定內(nèi)核真正執(zhí)行了讀者的替換算法。

(2) 實(shí)驗(yàn)結(jié)果驗(yàn)證要求:

結(jié)合WinDbg在新算法處設(shè)置斷點(diǎn),單步運(yùn)行驗(yàn)證自己新加的算法是否達(dá)到預(yù)期的目的,驗(yàn)證情況記錄下來,作為提交文檔的一部分。

4.3實(shí)驗(yàn)項(xiàng)目3:頁面替換算法的驗(yàn)證

本實(shí)驗(yàn)編寫應(yīng)用程序能夠輸出當(dāng)前進(jìn)程工作集的狀態(tài)包括當(dāng)前工作集頁面大小、各頁面虛擬地址、物理地址等,最終能驗(yàn)證實(shí)驗(yàn)2的算法。

(1) 實(shí)驗(yàn)要求:

① 需要在內(nèi)核中添加自己的系統(tǒng)調(diào)用,獲取當(dāng)前工作集的狀態(tài),內(nèi)核添加系統(tǒng)調(diào)用的方法見文獻(xiàn)[4]的介紹。

② 編寫的應(yīng)用程序調(diào)用新增的系統(tǒng)調(diào)用,并實(shí)現(xiàn)以下功能:

? 能夠隨時申請、釋放給定數(shù)目的頁面;

? 能夠隨時查看當(dāng)前進(jìn)程工作集的情況,包括工作集大小,工作集頁面的物理地址、虛擬地址等;

? 訪問指定位置的頁面,比如偶數(shù)頁面;

? 顯示指定頁面的內(nèi)容;

? 申請一定數(shù)量頁面后,如果當(dāng)前工作集已達(dá)到峰值,應(yīng)顯示被替換的頁面位置

(2) 實(shí)驗(yàn)結(jié)果驗(yàn)證要求:

我們在實(shí)驗(yàn)2中將頁面替換算法改為“先進(jìn)先出”算法,并編寫了一個小測試程序供學(xué)生參考。首先一個簡單的主菜單如圖2所示。

輸入6,查看工作集狀態(tài)及用戶申請頁面數(shù)顯示如圖3所示。

通過反復(fù)選擇1申請頁面,使工作集達(dá)到最大值。接著再申請5頁,輸入命令:7查看我們剛才申請的5頁內(nèi)存替換了那些頁面(如圖4所示)。這時替換的頁面不是應(yīng)用程序申請的頁面。

在申請大約13頁后,從圖5可以看出系統(tǒng)開始按照“先進(jìn)先出”算法開始替換我們申請的第一頁、第二頁……

5結(jié)束語

通過本次對Windows工作集管理的分析,特別是對工作集中頁面替換算法的分析與修改,可以使學(xué)生深入理解了操作系統(tǒng)原理介紹的工作集如何在一個完整操作系統(tǒng)上實(shí)現(xiàn),特別是商業(yè)性質(zhì)的操作系統(tǒng)。更詳細(xì)的實(shí)驗(yàn)介紹參見文獻(xiàn)[4]。

參考文獻(xiàn):

[1] Mark E. Russinovich, David A. Solomon. Microsoft Windows Internals[M].4th ed. Washington USA:Microsoft Press, 2005.

[2] Microsoft. Windows Research Kernel v1.2[CP/OL]. http://www.microsoft.com/resources /sharedsource/windowsacademic/ researchkernelkit.mspx.

[3] Microsoft. Windbg[CP/OL]. http://www.microsoft.com/whdc/ ddk/debugging/default.mspx.

[4] Lei Wang. Analysis Report on Windows Working Set Page Replacement Algorithm[R]. Asian Pacific Windows Core Workshop. Hangzhou, China. March,2008.