《操作系统内核代码热点动态检测技术研究.pdf》由会员分享，可在线阅读，更多相关《操作系统内核代码热点动态检测技术研究.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机及网络技术应用操作系统内核代码热点动态检测技术研究杨!宁!卢显良（电子科技大学!成都!#$%&）摘要：分析了()*+,-&内核中采用的基于蒙特卡罗方法的代码热点检测算法和实现机制，指出了其中的不足，并在此基础上提出了改进措施。关键词：代码热点；蒙特卡罗方法；动态检测中图分类号：./0#!文献标识码：1!文章编号：#2,3&%$（,$）$#3$&3$&!#$%&()*+)$,-&*.&.-)/0&)-12#(3 4%)5 6(78(.#9(.#-):9%$.-)/;+#.,45)6 7()6，*8(5)9(5)6（:)(;(?AB C9D?=A)(D ED()D 5)F.DG)A9A6 A
2、B HG()5!HG)6F*!#$%&）AJ?G?(KJA=?5)?AB?L5=A?G J=BA=K5)D AB ME N=O)5 N B5D?A=?A?G LGA9 DAKJ*?K BB(D()DP.G=BA=)D5=?A F?D?5)F AJ?(OK(Q?G DAF?G5?=*)KA?B=R*)?9，G)D?G DAF 5=D599JA?P.G(J5J 5KK S5F TA)?H5=9A K*F S()*+,-&N=)9?A F?JA?AB?G N=)9F)5K(D599P.G B95L 5)F?G=KF G5;A S)J=)?F G=(%7#：DAFJA?；TA)?H5=9A K?GAF
3、；F)5K(D F?D?()6#!前言操作系统内核是计算机系统中最为重要的系统软件。操作系统内核各个部分的运行性能直接影响着整个系统的性能。因此，对操作系统内核的性能不断地进行优化，是一件非常必要的工作。但是，现代操作系统内核代码非常庞大，所以优化要有针对性地进行。根据程序的时间局部性原理可知，优化的基本原则是，对经常运行的代码或者函数进行优化。我们称被经常运行的那一部分代码为代码热点。如果能有效地找出内核代码实际运行时的代码热点，则优化的针对性就更强，优化后性能的提升就更高。代码热点可以通过阅读代码进行分析和估计，也可以在操作系统实际运行时动态地检测和统计。我们称前者为静态分析的方法，称后者
4、为动态检测的方法。显然，动态检测的方法更能得出真实可靠的结论。()*+,-&内核实现了代码热点的动态检测。本文介绍该技术所依据的蒙特卡罗方法的基本思想，然后对()*+操作系统内核运用该方法实现代码热点检测的算法及其实现进行了分析，并在此基础上对于其中的不足之处提出了改进措施。,!蒙特卡罗方法的基本思想蒙特卡罗方法又叫随机抽样或者统计试验方法，是属于随机模拟的一种方法。()*+,-&内核使用该方法实现了代码热点的检测和统计。当所求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时，它们可以通过某种&C+J=(K)?ED()D U.DG)A9A6!,$年,月第#期!收稿日期,$%3$V 3
5、$V作者简介杨!宁（#V2&），男，硕士研究生，研究方向：操作系统。万方数据“试验”的方法得到这种事件出现的频率，或者这个随机变量的期望值，并用它们作为问题的解。这就是蒙特卡罗方法的基本思想。蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。可以把蒙特卡罗解题归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。这三个步骤的具体描述如下。!#$构造或描述概率过程对于本身就具有随机性质的问题，主要是正确描述和模拟这个概率过程，对于本来
6、不是随机性质的确定性问题，就必须事先构造一个人为的概率过程，它的某些参量正好是所要求问题的解。即要将不具有随机性质的问题转化为随机性质的问题。!$实现从已知概率分布抽样构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。!%$建立各种统计量构造了概率模型并能从中抽样（即实现模拟实验）后，就要确定一个随机变量的统计量，作为所要求的问题的解，称为无偏估计。建立各种统计量，相当于对模拟实验的结果进行考察和登记，从中得到问题的解。总之，蒙特卡罗方法用试
7、验的方法确定事件概率和随机变量的数学期望，以此作为问题的解。%$&()*内核代码热点检测机制%#$采样的时机&()*内核在每次对时钟中断进行处理时，判断中断前系统是否运行于内核状态，如果是，则对中断前+,-寄存器的值进行采样。这个值实际上就是每次时钟中断处理结束后将要执行的第一条指令。基于*./平台的时钟中断频率为#00 12，即每#0 34 采样一次。%!$代码执行的随机性在一次时钟中断前，如果系统运行于内核状态，则中断前保存的+,-的值是不确定的，即中断恢复后执行的第一条指令具有随机性。换句话说，代码热点问题本身就是一个具有随机性的问题，适合用蒙特卡罗方法求解。%$算法及其实现首先，应明确
8、要检测的是某个代码段（函数）是否为代码热点，而不是针对某条指令。然后，将整个内核代码段分为!5!块（称 为伸缩因子）。设离散随机变量#，其可能取值为$（$5 0，#，!6#）。事件#5$的意义为，在一次采样中，+,-值落在了序号为$的代码块内。存在%（0%!6#）使得%5 37*（$），此时序号为%（0%!6#）的代码块为代码热点。由此可见，这里采用的是离散随机变量概率分布模型，统计量就是随机变量本身。问题的关键是求出 37*（$），为此就要通过采样求出随机变量#的概率分布。在算法中，我们使用事件#5$出现的频率数来模拟$。以上为算法的机理，下面描述在&()*中具体实现
9、的过程。%#$初始化过程首先，需要求得整个内核代码段的长度。在整个内核映象中，内核代码段从8 49:*9 开始，到8:9:*9 结束。在内核初始化时，直接求出内核代码段的长度;&:(5 8:9:*9 6 8 49:*9，代码段的块数为!5!，则每块代码的长度为&:(5;&:(3，可见每块代码的长度由伸缩因子)(9:?!，其中=)(9:?$（0%$%!6#）对应序号为$的代码块的计数器。示意图如图#所示。8 49:*9=)(9:?0&:(5;&:(!5!=)(9:?#8:9:*9=)(9:?!6#图#$内核代码段示意图$此外，内核在初始化时，在 A?=文件系统中建立一个 A?BC:节点，允许用户
10、实用程序读取计数数据。%!$采样计数过程如前所述，采样任务在时钟中断处理过程内完DE$!00/年!月第#期$实$验$科$学$与$技$术万方数据成。第一步，判断在中断前系统的运行状态。这是通过检查进入中断处理程序前，被压入堆栈的寄存器!的值中的特权位来实现的。第二步，如果是运行于内核状态，则从堆栈中取出#$%寄存器的值，这是中断恢复后将要执行的第一条指令。为了计算该指令属于哪个代码块，对#$%作如下运算：求得相对于内核代码段起点的位置：&%()#$%*+(,-.,；计算出所属的代码块的序号：!)&%(（)/#）；相应计数器加 0：123,-4 !)123,-4 !50。67 67 68 统计过程
11、统计工作由用户实用程序实现。用户实用程序通过读取9:419:4;32.内 核 编 译 后，生 成 了 一 个 名 为?(,-A7 AB:的符号文件，其中包含了内核中所有函数名（或者过程名）和对应的起始地址，也包括+(,-.,和+-,-.,的值。因此，这个文件可以看作是一个函数，实现了函数地址到函数名的映射，设这个函 数 为：;3BA-)CDD4EFBA-（;BDD4），其 中;BDD4 为函数地址。使用下列!伪代码描述的算法，可以输出每个函数的执行频率。（0）8;3+BDD4)+(,-.,；（/）8 GH=-（;3+BDD4！)+-,-.,）（6）8 8 8,1I()J；（K）8 8 8 3D
12、-.)J；（L）8 8 8 3-.,+;3+BDD4)M-,+3-.,+;231,3+BDD4（）；（N）8 8 8 GH=-（-3）（P）8 8 8 8 8,1I(),1I(5 123,-4 3D-.5 5 ；（Q）888:43,;（“R(R S3”，CDD4EFBA-（;3+BDD4），,-3），所以在算法的（N）、（P）行把包含在这个宽度内的各个代码块的计数累加起来作为该函数的执行频率。K8 问题与改进措施32.操作系统对中断处理是严格串行化的，因此上述机制由于采样时机是在时钟中断内，所以实际上无法采样到各个中断处理代码的数据。然而，在做统计计算时，由于?(,-A7 AB:文件中包含了中
13、断处理函数的地址和函数名的记录，所以有可能会错误地计算出中断处理函数的执行频率。事实上，由于没有中断处理代码的执行计数，所有中断处理函数的执行频率都应该为 J。为了能够取得各个中断处理函数的计数，我们修改采样时机，将采样点改在中断处理程序的总入口函数中，不仅对堆栈中的#$%值进行采样，也对即将执行的中断处理程序的首地址进行采样。中断处理程序的总入口是 D+$&U 函数，D+$&U 函数调用 HB3D=-+$&U+-V-3,函数遍历执行共享同一$&U 信号的中断处理程序。故修改 HB3D=-+$&U+-V-3,函数如下：（0）83,HB3D=-+$&U+-V-3,（23(M3-D3,4W，(,4
14、21,:,+4-M(4-M(，(,421,4WB1,3B1,3）（/）8（6）8 8 8 3,(,B,2(；（K）8 8 8 3,1:2)(A:+:41-(4+D（）；（L）（N）8 8 8 4W+-3,-4（1:2，4W）；（P）（Q）8 8 8(,B,2()0；（T）（0J）8 8 8;（！（B1,3*X;=BM(YC+$FE#&Z%E）（00）8 8 8+(,（）；（0/）（06）8 8 8 D（0K）8 8 8 8(,B,2()B1,3*X;=BM(；（0K*0）D+H,+(:,（23(M3-D3,）B1,3*X HB3D=-4）；（0L）8 8 8 8B1,3*X HB3D=-4（4
15、W，B1,3*X D-V+D，4-M(）；（0N）8 8 8 8 B1,3)B1,3*X 3-.,；（0P）8 8 8GH=-（B1,3）；（0Q）8 8 8#+&CF）（0T）8 8 8 BDD+3,-442:,+4B3DA3-(（4W）；（/J）8 8 8+1=（）；（/0）（/）8 8 8 4W+-.,（1:2，4W）；（下转第 QK 页）NK#.:-4A-3,1-31-Y E-1H3=M?8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8/JJN 年/月第 0 期8万方数据!#$%、视频文件、播放文件等，这些工具为撰写实验报告内容提供了很大的帮助，也是在线完成化学实验报告的
16、基础，给学生撰写化学实验报告提供了很方便的界面（较复杂的分子式、装置图可先用&%()*+,、-%./.$%.0 等软件制作，然后插入合成）。在计算机上完成实验报告后点击提交即上传服务器，完成实验报告的撰写工作。页面如图 1所示。图 12 实验报告撰写页34 12 实验报告的管理模块该模块主要是用户对个人的实验报告进行管理，如对未批改的实验报告进行修改、删除等操作，也可查看教师已批改过的报告内容。页面如图3 所示。52 结束语本系统具有以下优点：（6）学生在完成实验报告的过程当中，可以不受时空限制，并且在数据处理，画实验装置图或结构式时，可以充分利用计算机或本系统提供的工具方便快捷地完成，从而提
17、高了报告写作效率。图 32 实验报告管理页面（1）减少了教师批改实验报告中的收、发、登成绩等许多环节。（3）本系统还方便游客或学生浏览教师批改后的实验报告，可以让更多人看到那些优秀的实验报告，给相互学习提供了一个方便的平台。参 考 文 献62 周洪政，陈文斌 4 78#9:#;8 5 网页制作全新教程5412 易昭湘，聂元铭，杨眉 4 专家门诊?-开发答疑 1 问 4 北京：人民邮电出版社，1A432 周南岳 4 动态页面制作基础与技术5452 风火轮小组 4?-建站编程高手指南34A2 宣小平，但政刚，张文毅 4?-数据库系统开发实例导航34（上接第 5B 页）（13）（15）2 2 2 8
18、/C89$/#/C$；（1A）2（65 D6）行是我们加入的一个采样点。E.F%./F$0./（+0，+0）函数是新写的一个采样函数，其流程如下：求得中断处理程序相对于内核代码段起点的位置：G-.$H+0 D F$/I/；计算出所属的代码块的序号：!HG-.$（H1#）；相应计数器加 6：,.C9/8 !H,.C9/8 !J6；此外对 KL-进行常规采样：求得相对于内核代码段起点的位置：G-.$H KL-D F$/I/；计算出所属的代码块的序号：!HG-.$（H1#）；相应计数器加 6：,.C9/8 !H,.C9/8 !J6。经此改进后，包括中断处理函数在内的所有内核函数的执行频率都能够被正确
19、统计。参 考 文 献62 G.M8/7-，&$#/+4 N9E8$/#9E+9O/%P+9CI Q894 M#R.0.，&?，N4 4?：)SG+T 3412 徐全智，杨晋浩 4 数学建模345UKI08+(9/,+9,V R,%9.OT2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 21B 年 1 月第 6 期2万方数据操作系统内核代码热点动态检测技术研究操作系统内核代码热点动态检测技术研究作者：杨宁，卢显良，Yang Ning，Lu Xianliang作者单位：电子科技大学,成都,610054刊名：实验科学与技术英文刊名：EXPERIMENT SCIENCE&TECHNOLOGY年，卷(期)：2006,4(1)参考文献(2条)参考文献(2条)1.Robert D P;Cesati M Understanding the Linux kernel 20032.徐全智;杨晋浩 数学建模 2003 本文链接：http:/