当前位置：首页> 操作系统课程设计实验报告1- 副本

操作系统课程设计实验报告1- 副本

时间：2011-09-14 16:35:27 下载该word文档

操作系统实验报告

--基于WRK的进程工作集实验

姓名：陈云卿

学号：09008323

完成日期：2011.9.10

1.实验目的

1 掌握虚拟机和调试工具等的使用。

2 阅读Windows源码中工作集管理相关部分。

3 修改Windows内核中页面置换算法，深入理解工作集和页面置换算法如何在一个完整的操作系统中实现。

2.实验内容

1.配置实验环境

主要是关于WRK的编译方法以及windbg的安装和调试（简要叙述）

（1）WRK平台安装配置

1）首先把实验需要的文件下载到本地d:\ WRK-CRK目录下。

2）在cmd命令行中输入：

a. mkdir c:\wrk（建立一个新目录）

b. set wrk=c:\wrk（上面建立的目录）

c. xcopy /crehkdq d:\ WRK-CRK\WRK-v1.2 %wrk%（把WRK内核代码和工具拷到新建立的目录下）

d. set arch=x86[amd64]（设置机器的CPU架构，x86还是amd64）指定编译目标结构

e. set path=%wrk%\tools\%arch%;%path%（设置WRK平台编译工具路径）

f. cd %wrk%\base\ntos（进入编译工具目录）

g. nmake –nologo %arch%=（编译WRK内核）

3）如果编译成功的话，%wrk%\base\ntos\build\exe目录下会生成两个文件，wrkx86.exe和wrkx86.pdb。

这里需要注意的是在将指令拷贝到cmd指令框时要注意字体的问题尤其是‘-’需要时英文半角字符。否则会出现指令不识别的情况。

（2）WRK平台安装的联机调试

（1）主要是图形界面操作没什么需要特别注意的，只是在设置shared folders是一般的情况是出现的盘符后面会有*号，这是因为在设置时没有勾选shared everytime选项勾选一下就好了。其次是在启动windbg时可能会有symbol file error只是windbg的file中的symbolfile之下的文件路径设置一下就好。在虚拟机cmd窗口中输入：(重新编译之后要重做)

xcopy z:\base\ntos\build\exe\wrkx86.exe c:\windows\system32

xcopy z:\WS03SP1HALS\x86\halacpim\halacpim.dll c:\windows\system32

2. 了解Windows系统中的工作集

一个进程当前正在使用的页面的集合成为它的工作集（working set）。

Windows系统通常将工作集分为进程工作集与系统工作集，分别用于跟踪各个进程与系统的物理内存使用情况。

Windows内核对工作集页面的操作分工作集管理器（系统级）的页面修剪算法和进程自己的页面替换算法两种，前者主要是定时扫描系统的内存利用情况，同时对某些进程进行页面修剪，比如选定优先级低的进程，应用最近最久未使用算法（LRU）选定要删除的页面进行删除；而后者主要是在进程内部，当进程申请页面超过一定峰值再申请页面时，工作集大小不再增加，而是以一定的策略替换已有页面。

3. 工作集相关数据结构

EPROCESS是描述进程的结构，与工作集相关的数据结构主要有MMSUPPORT、MMWSL、MMWSLE MMWSLENTRY、MMPTE、PMMWSLE_HASH，其主要关系如下图：

4工作集代码分析

4.1 页面替换算法分析

首先调用 MiAddWorkingSetPage()向工作集中添加页面失败时，调用中 MiDoReplacement()函数对工作集进行替换，同时修改 MiReplacing //标志发生了页置换为 True，说明当前系统页面已经紧张，以便在启动工作集管理器时，根据MiReplacing的值执行修剪操作。其中 MiDoReplacement()主要调用了MiReplaceWorkingSetEntry()进行页面替换。

(1) 修剪时刻//替换时刻。根据如下三个条件：

① 当前可用页面数Avai lable少于当前需要的页面数； //超过当前的可用峰值

② 本工作集中已经有被替换页面的记录，MiReplacing == TRUE；

③ 有超过可用页面数 1/4 的页面被循环用作后备页面；

以上条件满足一个则立即进行修剪操作，其中设置Criteria 标准的相应变量。

(2) 老化时刻。当修剪条件全不成立时，当前可用页面 Avai lable 小于限值 20000，则进行老化操作。？？

(3) 不操作。在 1，2 均不成立条件下，说明当前系统中还有大量内存可用，OutFlags=0，作为返回值，不进行任何操作。

此时确定的工作集处理标准，保存在 WorkingSetRequest Flags(OutFlags=0)和 TrimCriteria 中,如果 WorkingSetRequest Flags 非零，即需要进行修剪或者老化操作，具体调用 Mi ProcessWorkingSets (WorkingSetRequestFlags, &TrimCriteria)做具体处理。如果 WorkingSetRequestFlags 为零，则不做操作。接下来查看修改页面链表的计数器 MmModified

PageListHead.Total 是否超过限制 MmModified PageMaximum，若超过则激活修改页面写回器工作。

4.2 释放页面过程分析

MiTrimWorkingSet()根据传入的修剪标准，确定需要进行移除的工作集页面的索引号和释放的页面数，并将其封装在 WsleFlushList 结构中，作为参数传给MiFreeWsleList，具体页面释放操作由 MiFreeWsleList 来完成。 Windows 操作系统是一个多任务系统，虽然已经确定了要释放的页面的索引号，但是在确定索引号到调用本函数真正释放页面，期间所确定的页面可能又被其他进程共享，这种情况仅需要调用 MiDecrementShareCount()函数使共享计数器减一，再或是此页面是一原型页表项，所以要进行第一次循环，将所有这些情况的 FlushIndex()置零，然后在接下来的循环中调用 MiRemoveWsle()移除页面。

4.3 置换算法源码分析

代码分析：base\ntos\mm\wslist.c : 591 : MiReplaceWorkingSetEntry()

函数原型：

VOID MiReplaceWorkingSetEntry (

IN PMMSUPPORT WsInfo,

IN WSLE_ALLOCATION_TYPE Flags

)

参数说明：

WsInfo – 指向工作集信息的指针

Flags – 为0表示不需要页面替换

为1 标识需要进行页面替换

功能概述：

此函数查找一个符合条件的工作集页面用来替换。

变量说明：

3.源代码及注释

VOID

MiReplaceWorkingSetEntry (

IN PMMSUPPORT WsInfo,// 指向工作集信息的指针

IN WSLE_ALLOCATION_TYPE Flags//为0表示不需要页面替换，为1 标识需要进行页面替换

)

{

WSLE_NUMBER WorkingSetIndex;

WSLE_NUMBER FirstDynamic;

WSLE_NUMBER LastEntry;

PMMWSL WorkingSetList;

PMMWSLE Wsle;

ULONG NumberOfCandidates;

PMMPTE PointerPte;

WSLE_NUMBER TheNextSlot;

WSLE_NUMBER OldestWorkingSetIndex;

LONG OldestAge;

WorkingSetList = WsInfo->VmWorkingSetList;

Wsle = WorkingSetList->Wsle;

// Toss a page out of the working set.

LastEntry = WorkingSetList->LastEntry;

FirstDynamic = WorkingSetList->FirstDynamic;

WorkingSetIndex = WorkingSetList->NextSlot;//下一个要修剪的页面下标

if (WorkingSetIndex > LastEntry || WorkingSetIndex < FirstDynamic) {

WorkingSetIndex = FirstDynamic;

}//初始化workingsetindex指针的位置

TheNextSlot = WorkingSetIndex;

NumberOfCandidates = 0;

OldestWorkingSetIndex = WSLE_NULL_INDEX;//最老页面指针为空

OldestAge = -1;

while (TRUE) {

// Keep track of the oldest page along the way in case we

// don't find one that's >= MI_IMMEDIATE_REPLACEMENT_AGE

// before we've looked at MM_WORKING_SET_LIST_SEARCH

// entries.

while (Wsle[WorkingSetIndex].u1.e1.Valid == 0) {

WorkingSetIndex += 1;

if (WorkingSetIndex > LastEntry) {

WorkingSetIndex = FirstDynamic;

}

if (WorkingSetIndex == TheNextSlot) {//扫描了一圈了

if (Flags == WsleAllocationAny) {

// Entire working set list has been searched, increase

// the working set size. Note this may result in exceeding

// a hard maximum limit on the system cache (only)

// in the case where all the other entries (paged pool)

// have been locked (so there isn't one to replace).

WsInfo->GrowthSinceLastEstimate += 1;//这个变量一直不清楚具体含义想提问一下

}

return;

}

if (OldestWorkingSetIndex == WSLE_NULL_INDEX) {

// First time through, so initialize the OldestWorkingSetIndex

// to the first valid WSLE. As we go along, this will be re-pointed

// at the oldest candidate we come across.

OldestWorkingSetIndex = WorkingSetIndex;//最老页面为当前所指页面

OldestAge = -1;

}

PointerPte = MiGetPteAddress(Wsle[WorkingSetIndex].u1.VirtualAddress);

if ((Flags == WsleAllocationReplace) ||

((MI_GET_ACCESSED_IN_PTE(PointerPte) == 0) &&

(OldestAge < (LONG) MI_GET_WSLE_AGE(PointerPte, &Wsle[WorkingSetIndex])))) {

// This one is not used and it's older.

OldestAge = MI_GET_WSLE_AGE(PointerPte, &Wsle[WorkingSetIndex]);

OldestWorkingSetIndex = WorkingSetIndex;

}

// If it's old enough or we've searched too much then use this entry.

if ((Flags == WsleAllocationReplace) ||

OldestAge >= MI_IMMEDIATE_REPLACEMENT_AGE ||

NumberOfCandidates > MM_WORKING_SET_LIST_SEARCH) {

//替换条件

if (OldestWorkingSetIndex != WorkingSetIndex) {

WorkingSetIndex = OldestWorkingSetIndex;

PointerPte = MiGetPteAddress(Wsle[WorkingSetIndex].u1.VirtualAddress);

}

if (MiFreeWsle (WorkingSetIndex, WsInfo, PointerPte)) {//释放原来的界面

// This entry was removed.

WorkingSetList->NextSlot = WorkingSetIndex + 1;

break;

}

// We failed to remove a page, try the next one.

// Clear the OldestWorkingSetIndex so that

// it gets set to the next valid entry above like the

// first time around.

WorkingSetIndex = OldestWorkingSetIndex + 1;

OldestWorkingSetIndex = WSLE_NULL_INDEX;

}

else {

WorkingSetIndex += 1;

}

if (WorkingSetIndex > LastEntry) {

WorkingSetIndex = FirstDynamic;

}

NumberOfCandidates += 1;

if (WorkingSetIndex == TheNextSlot) {//扫描结束

if (Flags == WsleAllocationAny) {

// Entire working set list has been searched, increase

// the working set size. Note this may result in exceeding

// a hard maximum limit on the system cache (only)

// in the case where all the other entries (paged pool)

// have been locked (so there isn't one to replace).

WsInfo->GrowthSinceLastEstimate += 1;

}

break;

}

return;

}

之上为原来操作系统提供的LRU替换算法主要考虑两个方面：1.页的age 2.已扫描的页个数。修改后的算法没有考虑这些因素采用了一种非常直接的策略：替换找到的第一个可以被替换的页。在代码方面也比原来的代码简单了很多。

主要是去除了一些判断条件。

VOID

MiReplaceWorkingSetEntry (

IN PMMSUPPORT WsInfo,

IN WSLE_ALLOCATION_TYPE Flags

)

{

WSLE_NUMBER WorkingSetIndex;

WSLE_NUMBER FirstDynamic;

WSLE_NUMBER LastEntry;

PMMWSL WorkingSetList;

PMMWSLE Wsle;

PMMPTE PointerPte;

WSLE_NUMBER TheNextSlot;

WorkingSetList = WsInfo->VmWorkingSetList;

Wsle = WorkingSetList->Wsle;

LastEntry = WorkingSetList->LastEntry;

FirstDynamic = WorkingSetList->FirstDynamic;

WorkingSetIndex = WorkingSetList->NextSlot;

if (WorkingSetIndex > LastEntry || WorkingSetIndex < FirstDynamic) {

WorkingSetIndex = FirstDynamic;

}

TheNextSlot = WorkingSetIndex;

while (TRUE) {

while (Wsle[WorkingSetIndex].u1.e1.Valid == 0) {//找到第一个可以被替换的页

WorkingSetIndex += 1;

if (WorkingSetIndex > LastEntry) {

WorkingSetIndex = FirstDynamic;

}

if (WorkingSetIndex == TheNextSlot) {

if (Flags == WsleAllocationAny) {

WsInfo->GrowthSinceLastEstimate += 1;

}

return;

}

PointerPte = MiGetPteAddress(Wsle[WorkingSetIndex].u1.VirtualAddress);

if (MiFreeWsle (WorkingSetIndex, WsInfo, PointerPte)) {//直接替换

WorkingSetList->NextSlot = WorkingSetIndex + 1;

break;

}

WorkingSetIndex += 1;

if (WorkingSetIndex > LastEntry) {

WorkingSetIndex = FirstDynamic;

}

if (WorkingSetIndex == TheNextSlot) {

if (Flags == WsleAllocationAny) {

WsInfo->GrowthSinceLastEstimate += 1;

}

break;

}

return;

}

4.调试截图及说明：

1.查找进程

kd> !process 0 0

2. 据此地址查看EPROCESS信息

kd> dt eprocess 811df020

word/media/image3.gif

3. 查看MMSUPPORT的信息

kd>dt nt!_MMSUPPORT 811df020+0x1e8

word/media/image5.gif

4. 查看MMWSL信息

kd> dt nt!_MMWSL 0xc0502000

word/media/image7.gif

5. 查看MMWSLE的信息，即工作集页面项（所有页面虚拟地址）的详细信息

kd> dd 0xc0502698 l 0x40

关于地址查看是要根据在内核运行过程中替换地址的变化跟进的，一般如果nextslot为2d的话可以在上述指令的最后两位改为2d+2即2f这样可以看到2d及2e的情况。

验证页面置换算法

Local中的相关变量情况

从这个图片中可以看出即将被替换的是0x17这个页面

替换前的情况：

替换后的情况：

这里有一个问题，我发现原来的LRU算法会出现整篇替换的情况也就是会有很多页在一次替换中被改变。我问过助教，得到的答案是因为有很多也都符合替换的标准。但是我觉得是不是应该只替换一个页（即符合替换条件的第一个页）。或许就是因为采用了页式导致连续的页属于不同的进程其他进程也发生了页置换。希望老师解答一下，谢谢。

修改页面置换算法之后的验证：（算法已经在上面写出此处不再赘述）

置换前：（NextSlot为0x4f）

置换后：

可以看出，即使NextSlot指示页年龄为1，之后的页面年龄为3，也替换当前页。即验证我们修改的“碰见有效页即替换”的策略。（不过这种策略比较简单在一般的使用过程中可能造成某些页一直不能得到替换）

关于选做实验：

我按照实验手册完成了选做实验，验收的时候比较简单没有仔细分析其中的数据，但是我在总结的时候发现数据有问题，里面的数据除了MAXWorkSetSize是一个有具体意义的数字之外其他数据均处于未初始化的情况。所以也就没有办法分析两种算法的具体效果的不同之处了。我会在之后的学习中继续注意这件事情。我猜想了一下相关的情况，首先是在进程刚开始运行的时候不存在页置换的情况所以两个算法的页错误率均为0，之后是刚开始替换时LRU算法和直接替换的情况应该是一样的都是从前向后替换所以相差应该不大。之后的情况就是进程运行了相当一段时间,LRU算法会体现出它的优越性在页错误方面会降低。一般会趋于一个比较稳定的数字，而另一种算法的页错误率比较随机因为一直替换第一个有效页所以如果程序要求的数据比较分散，页错误就会很高。以上是我的一些想法也许存在比较多的问题。

5.实验心得及总结

1.首先在这次的实验中我对于操作系统课上所学的页面置换策略有了更深入的了解，但是同时我也觉得理论和代码之间存在着比较大的“代沟”。一开始接触到windows内核的代码时我发现自己很难读懂这些代码，如果没有实验手册我想一个月不一定能够做完这些实验。这说明自己所学的东西还都很肤浅，还有很多事情是自己需要努力去做的。

2.在实验的过程中我发现关于段页式内存的具体实现以及几个进程之间同时进行是的内存置换问题不太理解，就像上面所说的发生很大一段内存在一次置换中全部改变的情况。我有一个想法，希望在之后的这门课中加入几节课专门讲一下相关函数的具体作用以及代码含义虽然这些可以通过自己查资料来完成，但是在原理上引导一下或许对于实验的理解会更加深刻。

3.还有就是我觉得开始的wrk平台配置比较繁琐，我觉得可不可以将这些步骤做成为批处理文件直接运行来的更快。（这个是朱礼智同学教的）

阅读全文