基于ＷＲＫ的进程工作集实验设计

王　雷

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.