基于ＷＲＫ的進(jìn)程工作集實(shí)驗(yàn)設(shè)計(jì)

王　雷

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

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

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

1引言

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

本文以WRK為實(shí)驗(yàn)平臺(tái),結(jié)合內(nèi)核源代碼和WinDbg調(diào)試工具,以Windows內(nèi)存管理的工作集頁(yè)面替換為分析對(duì)象,分析進(jìn)程工作集的峰值及頁(yè)面替換算法,設(shè)計(jì)了相應(yīng)的實(shí)驗(yàn)修改頁(yè)面替換算法,并給出了實(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)系,對(duì)內(nèi)核調(diào)試、算法修改、內(nèi)核系統(tǒng)調(diào)用的添加都極及有幫助。

2.2工作集代碼分析

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

2.2.1頁(yè)面替換算法分析

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

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

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

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

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

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

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

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

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

2.2.2釋放頁(yè)面過(guò)程分析

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

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

3使用WinDbg查看工作集

WinDbg可以用于Kernel模式調(diào)試和用戶模式調(diào)試。我們編寫(xiě)了一個(gè)應(yīng)用程序,申請(qǐng)100頁(yè)內(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頁(yè),缺頁(yè)次數(shù)0x189頁(yè),工作集最大值0x159頁(yè),最小值0x32頁(yè)。

工作集鏈表結(jié)構(gòu)是_MMWSL可以看出其地址想對(duì)于_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)行工作集頁(yè)面添加的位置

+0x004 FirstDynamic : 4

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

+0x008 LastEntry: 0x23b

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

+0x00c NextSlot : 4

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

……

(3) 查看工作集頁(yè)面項(xiàng)(所有頁(yè)面虛擬地址)的詳細(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)代表一頁(yè)的虛擬地址,地址后面的3位(201)是頁(yè)面的屬性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

① 完成頁(yè)面替換算法的修改。

② 修改完成后重新編譯內(nèi)核,并用新的內(nèi)核映像啟動(dòng)系統(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)證情況記錄下來(lái),作為提交文檔的一部分。

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

本實(shí)驗(yàn)編寫(xiě)應(yīng)用程序能夠輸出當(dāng)前進(jìn)程工作集的狀態(tài)包括當(dāng)前工作集頁(yè)面大小、各頁(yè)面虛擬地址、物理地址等,最終能驗(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)用的方法見(jiàn)文獻(xiàn)[4]的介紹。

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

? 能夠隨時(shí)申請(qǐng)、釋放給定數(shù)目的頁(yè)面;

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

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

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

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

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

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

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

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

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

5結(jié)束語(yǔ)

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