基于ＷＲＫ的進程工作集實驗設計

王　雷

Windows操作系統內核、設計操作系統實驗提供了一個很好的基礎。但是由于WRK的代碼量很大,在缺乏指導的情況下學生很難有效地在WRK上完成操作系統原理實驗。本文在分析WRK進程工作集的基礎上,設計了三個針對工作集的實驗,并給出了實驗效果驗證方法。

關鍵詞:操作系統;WRK;工作集

中圖分類號:G642 文獻標識碼:B

1引言

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

本文以WRK為實驗平臺,結合內核源代碼和WinDbg調試工具,以Windows內存管理的工作集頁面替換為分析對象,分析進程工作集的峰值及頁面替換算法,設計了相應的實驗修改頁面替換算法,并給出了實驗應達到的效果。

2工作集分析

2.1工作集數據結構

EPROCESS是描述進程的結構,工作集的相關結構也可以從這里找到,與工作集相關的數據結構主要有MMSUPPORT、MMWSL、MMWSLE MMWSLENTRY、MMPTE、PMMWSLE_HASH,其主要關系如下圖1工作集結構圖,理解工作集結構間的關系,對內核調試、算法修改、內核系統調用的添加都極及有幫助。

2.2工作集代碼分析

工作集相關代碼分布如表1所示。本小節針對前面分析的工作集的結構,選取幾個具有代表性的操作函數進行分析,為后面進行頁面算法的修改打下基礎。

2.2.1頁面替換算法分析

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

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

① 當前可用頁面數Available少于當前需要的頁面數;

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

③ 有超過可用頁面數1/4的頁面被循環用作后備頁面;

以上條件滿足一個則立即進行修剪操作,其中設置Criteria標準的相應變量。

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

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

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

2.2.2釋放頁面過程分析

MiTrimWorkingSet()根據傳入的修剪標準,確定需要進行移除的工作集頁面的索引號和釋放的頁面數,并將其封裝在WsleFlushList結構中,作為參數傳給MiFreeWsleList,具體頁面釋放操作由MiFreeWsleList來完成。

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

3使用WinDbg查看工作集

WinDbg可以用于Kernel模式調試和用戶模式調試。我們編寫了一個應用程序,申請100頁內存。然后在內核設定斷點,讓內核停下查看進程狀態。

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

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結構的類型是_MMSUPPORT,可以看出當前工作集大小是0x18d頁,缺頁次數0x189頁,工作集最大值0x159頁,最小值0x32頁。

工作集鏈表結構是_MMWSL可以看出其地址想對于_MMSUPPORT的偏移是0x028,下面計算_MMWSL的地址:

kd> ?(81de1de0+0x028)

Evaluate expression: -2116149752 = 81de1e08

kd> dd 81de1e08 l 1

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

(2) 用dt命令輸出工作集鏈表結構_MMWSL的詳細信息

kd> dt nt!_MMWSL c0502000

+0x000 FirstFree: 0x18d

//下次進行工作集頁面添加的位置

+0x004 FirstDynamic : 4

//工作集頁面中第一個可用頁面的下標

+0x008 LastEntry: 0x23b

//工作集頁面中最后一個可用頁面的下標

+0x00c NextSlot : 4

//進行頁面修剪算法是據此搜索最優替換頁面

……

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

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

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

通過使用WinDbg,可以對下面的實驗進行驗證。

4實驗設計

通過前面的分析,設計了三個實驗。

4.1實驗項目1:閱讀代碼——頁面替換算法分析

頁面替換算法是操作系統原理算法中重要的算法之一,涉及到進程管理、存儲管理。當進程申請的頁面數目達到工作集的峰值時,若再申請頁面,系統就會根據一定的替換算法替換舊的頁面,本實驗項目可借助WinDbg并結合閱讀WRK源代碼來完成。

(1) 本實驗項目主要以下三方面要求:

① 找到進程工作集頁面的峰值。

② 結合WinDbg在調試過程中內核棧的功能,分析從缺頁中斷到執行替換算法的代碼路徑(函數調用關系),并分析各函數的基本功能。

③ 詳細分析頁面替換算法的過程,這是后面進行頁面替換算法修改的基礎。

(2) 實驗結果驗證要求:

結合WinDbg在算法處設置斷點,單步運行驗證自己對算法分析的正確性,驗證情況記錄下來,作為提交文檔的一部分。

4.2實驗項目2:頁面替換算法的修改

本實驗是在實驗項目1的基礎上修改頁面替換算法,實驗前讀者還應該深刻理解工作集內部的結構,頁面的存放位置等。

(1) 實驗要求:

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

② 修改完成后重新編譯內核,并用新的內核映像啟動系統。

③ 在新的算法處設置斷點觀察,確定內核真正執行了讀者的替換算法。

(2) 實驗結果驗證要求:

結合WinDbg在新算法處設置斷點,單步運行驗證自己新加的算法是否達到預期的目的,驗證情況記錄下來,作為提交文檔的一部分。

4.3實驗項目3:頁面替換算法的驗證

本實驗編寫應用程序能夠輸出當前進程工作集的狀態包括當前工作集頁面大小、各頁面虛擬地址、物理地址等,最終能驗證實驗2的算法。

(1) 實驗要求:

① 需要在內核中添加自己的系統調用,獲取當前工作集的狀態,內核添加系統調用的方法見文獻[4]的介紹。

② 編寫的應用程序調用新增的系統調用,并實現以下功能:

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

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

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

? 顯示指定頁面的內容;

? 申請一定數量頁面后,如果當前工作集已達到峰值,應顯示被替換的頁面位置

(2) 實驗結果驗證要求:

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

輸入6,查看工作集狀態及用戶申請頁面數顯示如圖3所示。

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

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

5結束語

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

參考文獻:

[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.