（计算机应用技术专业论文）linux运行过程可视化中关键状态的描述和数据采集.pdf

山东大学硕士学位论文 摘要 作为开源操作系统的典型代表，“n 慨以其自由开放性和技术先进性跨入教 育科研领域，担当起一个优秀实用的计算机操作系统科研和教学平台，人们越来 越深刻地认识到深入学习和研究l i i l l l ) 【系统内核的必要性，但其源码规模庞大、 异常复杂，尤其是新版内核不断推出、功能逐渐增加，这使得深入内部了解它的 任务异常艰巨。而近年来可视化技术不断发展，它在提高人类认知能力方面发挥 着越来越明显的优势，深入地理、医疗、软件开发、教育等各行业，现在与网络 信息搜索、软件可视化、数据挖掘等方向结合具有更广泛的研究及应用价值，本 文重点在于探索将可视化与l i i l l | ) 【内核执行过程的深入学习相结合的可行性。 目前，将可视化技术引入操作系统教学领域或与l i l l 慨内核研究相结合的工 作已有很多，但存在一些不足。有些演示效果较好的算法可视化软件或工具往往 重在表现算法，与实际运行的操作系统脱离，数据来源不真实，并且多以程序或 算法动画的形式可视化，缺乏与用户的交互：有些以真实操作系统为数据源的可 视化工作，采用静态绑定形式预先定义若干过程或活动，对它们进行可视化模拟， 这种绑定限制了其适用范围；有些可视化以监控和分析系统性能为目的，关注于 可视化系统的整体状态和资源利用率等信息，与源码的数据结构和函数脱节，不 能满足深入学习内核的需要。为了改进目前工作中的不足，本文以内核运行时获 得的真实数据为基础，并以内核函数和数据结构为主体进行可视化，针对系统在 某段时间内相对完整的一个执行过程，直观地可视化出此过程中各种关键操作的 执行细节。 文中首先给出关键过程可视化的工作流程，重点研究以下内容：1 、将可视 化数据源设置为运行中的l i n l d 【操作系统，提取出固定时段内内核的各种关键状 态，定义数据采集点描述不同的内核状态，为采集点分类并规定数据记录格式， 从而确定出一种对关键状态进行描述的方法；2 、通过分析得出数据采集应遵循 的基本原则和有待解决的关键问题，结合这些原则探讨常见内核数据采集方法的 可用性，在此基础上解决相应问题并给出一种现实可行的采集方法。 随后，通过跟踪一个过程实例展示如何在源码中设置数据采集点，解析采集 到的数据记录，以可视方式处理数据从而验证内核状态描述方法的可用性。 山东大学硕士学位论文 从本文最后给出的可视化效果展示可知，结合内核运行时真实数据以关键函 数和数据结构为重点的过程可视化，可以从源码出发实现对所跟踪过程以及相应 数据结构、算法的深层次理解，且可视化结果真实可信，具有进一步研究和开发 的意义。 关键词操作系统；内核；l n u x ；可视化； i i 山东大学硕士学位论文 a b s t r a c t a sa1 y p i c a lr 印r 韶即t a 6 v eo fm eo p e n s o u r c eo p 盯撕n gs y s t 锄，、) l i i t l li t s 丹、 o p n a h 锄da d v 锄c e dt e c h n o l o g y ，l i l l t e dt h ef i d do fe d u c 撕o n a l 嘴e a r c h 锄dh 鹪b e 锄p l 妙i n g 嬲锄o l l t s t a i l d i n g 锄dp r d c a lo p e r a 血g 黟s t e mp l a 仃0 珊i n r 豁e a r c h 锄dt e 洳gp u r p o s e m o 糟锄dm o 坤p e o p l er e a l i z e1 l l e n e c 嚣面妒t o m d e r s t a l l dm el i i i 慨k e m e l ，b u ts o u r d e s m p l e 嫡1 y 趾dh l l g es c a l em a k e 瑚d e r s t 锄d i l l go fi 协i l l t e m a ls 仃u c t i l r ed i 伍c 讪y ，唧i a l l yn e wk 锄e l 哳t l lm o r e f i l c l i o n si s 曲h d d u c e d n t i i l u o 惦l y b mi nr 即ty 髓硌v i s u a l i z a t i o nt e c i l l l o l o 科 d e v e l o p sf 斑趾ds h o 懈1 0 r eo b v i o 懈a d n t a g e si ni l l l p r o v i 】呜m eh 啪锄c o g n i t i v e a b i l i 缸豁i tg o e sd e 印i n t om 锄yv o 谢。他，s u c h 髂g 掣a p h y 、h e a l mc a 糟、f t 哪 d e v e l o p i r 蛐t 、e d i l c a t i 锄d ，“c o m b i i l 豁谢t l lh 1 _ t e r n e ti i l l 白m 雠0 i ls e 砌、 f t w a r ev i s u a l i 蒯、d a t am i i l i n g 锄ds h o w sm o m 窃曲叭s i v er 笛r c h 趾d a p p l i c a t i o nv a l t h em a i np i l r p o o ft l l i sp a p e ri st 0e 冲l o t l l ef 宅豁i b i l i t yt o m b i n ev i 飘l a l i z a l i 澌t l lm e 咖d y k e ye x 训n g p r o c s 韶o f l i n 暇k 锄e 1 p r e s t l 弘al o tw o r kh a v e d o n et oi 1 1 仃o d u c e 啊s u a l i z a t i i i i t 0o p 训n gs y s t e m t e a c h i n gf i e l do rc o m b i n e d 谢t i l “n 畎k e m e lr e s e a r c h ，b i l tt i l e m r e m ed e f i c i c i 嚣， s o m ea l g o r i l l l mv i s u a l i z a t i o nt o o l so rs o f t w a r eh a v ee x c d l e n tv i s u a l 硪b c tb i l tp a y m o r ea 牡锄d o n 幻d e m o n s 仃a l ea l g o r i t h j i li t 1 f ，t l l e y r es 印a r a t e d 舶ma c t u a ln m n i n g s y s t e m ，a n ds ot l i ed a t as o u r c ei su n r e a l 正e a n w m l e1 l l e i ri i l a i n 觚i m 甜i f o 眦i s p r o g r 跏o ra 1 9 0 r i t i l mv i s u a l i z a t i o n t h 锣a r el a c ko fi i l t e r a c t i v e 嘶1 l l 吣盯；s o m e v i s 戚i 刎o nw o r ku n | l t n i n go p e r a l i n g 掣s t e m 髂d a t a 哪，t l i e yp 静d 幽e d s e v e r a lp r o c e 鼹o r 删v i 在嚣b ys t a t i cb i l l d i n 吕血e ns i m u i a t ep c 器sv i s u a l l y n l i s b m d i n gl i i i i i t si 忸s c o p eo fa p p l i c 砒i ；s o m ev i s u a l i 撕。璐a i m 砒锄a l y o rm 咖j t o f 夥s t e m sp 醯脚啪c e ，1 量l e yp a ym o a t t t i 0 i lt o1 l l ei n f o 咖撕d b o l i t1 l l eo v e r a l l s t a l e 锄dt h el n i l i 谢o nr a t eo f 螨o l l r c 嚣，粕dm e ，rd o n tc a k 哪e ld a t as 仉咖酷 a n df 血c t i o n sw t l i c hc 锄tm e e t1 l l en e e dt 01 l l o r o u g hm d e r s t a n dk 锄e l | t bi n 】p v e m ec u 蝴l tw o r k “sp 印e rb 勰e d a c t i l a l 出恤c o l l e c t e d 舶m 棚1 n i n gk e m e l ， i i i 山东大学硕士学位论文 m a i l l l y 、，i s u a l i z ed 砒as 伽l c t u r 豁趾df i l c d o n so fs o l l r c o d e ，a i m sa t 、r i s u a l i z e 删o l i sk e yo p e r a t i o n so far e l 撕v e l yc o 呷i 咖麟e c l n i n gp r o c 器s 蛐gac e f t a i l l p e r i o do f 缸m e t h i sp a p e rf i 陪t 百v 器o l i t 血ew o 棚o w “k e yp r o c e 鼹v i s u a l i 刎o n ，f o c l l so nm e c o n t e i l t sf o l l o 、】v i n g ：1 s e tn 瑚i n gl i n 慨o p e r 缸i 1 1 9 夥s t e m 器d 砒a l l r c e s ，e 姗a c t k e y s t a t e so fk e m e ld u 血gf i x e dp e r i o d s ，d e f i n ek i n d so fd a t ac o l l 在p o i i l 忸，c l 嬲s i 母 t 量l e m 血e ns p e c i 每t h e i rd a t ar e c o r 幽gf o r n l 甜，i nt h i sw 呵g e to n em e t 量l o dt 0d 嚣c 曲e k 锄e ls t a t e s ；2 a n a l y z e1 l l eb a s i cp f i i l d p l 豁s h o m df o l l o w 觚df i h l d a m t a li s s u 器 幽o m d l v e 山| r i i l gd a t a q l l i s i t i o i l d i s c 哪st h el i s a b i l i l yo fc u r r e n tk 锄e ld a t a c o l l 枷0 nm e t l l o d sm d e rt l l e s ep 血c i p l 嚣，s e m ec o n s p l d i n gp r o b i e m sa n d 百v eo u t af b a s i b l en l e t i l o d n ，d e m o 撇h o w 幻i l l r td a _ t ac o l l e c t i o np o i n t si n u f c ec o d eb y 仃a c i n g as p e c i f i cp r o c 铭se x a i r l p l e a i l a l y s e v e r a ld a t a 蚴r 出c o l l e c t 司丘d m 邢1 i l i n g k 唧e la n dd e a lv v i 血血e mv i s i l a lt ov e f i 分m eu s a b i l i l yo fm ed 鼯c r i p t i m 甜l o d d e f i n e db e f o r e f i i l a l l y ，舫ml l l er 嚣l l l t so fv i s u a lp i c t i l r e si m p l e m t e db yp r o 粤狮，w ec a n e c o m b i i l e d 谢t ha c t i i a lk e m e ld a t a 锄dm a i l l l yf o c i l so np r o 缪咖趾dd 砒as 劬蛐鹏 、，i s u a l i 删o n ，k e yp r o c 嚣sv i s u a l i 动矗c 锄h e l pt ou n d e r s t a 】帕1 l l e 铀c 吐t l l e b a s i s o f s o u r c ec o d e 肌d t l l e 、，i s l l a l i 动矗f 豁l d t i s m o r er e a l 锄d 粒c 印t a b l e ，“眦l s t h a v et l l es i g n j f i c a l l c ef o rf i l 】曲e rr 嚣e a r c h 孤dd e v e l o p m e n t k e yw o r d so p e m t i n gs y s t e m ；l e m e i ；l i n u x ；v i s u a l i z a t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：垄赴日期：螋日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：邂导师签名幽日期：五固垒垒弘目 山东大学硕士学位论文 1 1 课题研究背景和意义 第1 章绪论 l i l l 是一个免费和自由传播的操作系统，作为开源系统的代表，它高效、 健壮、安全、功能完备且广泛应用于网络、软件开发、用户平台等多种用途中， 尤其是它公开了从核心到上层所有软件的源码，这为从事计算机科研与教学的人 员提供了操作系统研究和教学平台，我们不仅可以对其中操作系统原理的实现、 算法的设计、数据结构的定义进行深入的学习，还可以方便地提出自己的实验方 案，以验证算法的性能、实现效率和可靠性等问题。这种巨大的潜力表明越来越 多的工程技术人员、大学生、研究生不仅迫切需要学习和使用它，更需要深入了 解其内部构造。 l i n i d 【源代码以其复杂性和规模之大著称，以l i n l d 【2 4 1 8 源码为例，它用 来支持各种体系结构的源代码约含8 7 5 0 个c 语言程序，存放在5 3 0 多个文件的 子目录中，大约包括4 0 0 万行代码，大概占1 “m b 磁盘空剐”。任一个刚刚接 触内核的学习者都会因其庞大的规模、错综复杂的关系感到茫然而无处下手，而 l h u x 的开放性又使得无数个公益团队仍在不断改进现有内核，使得它的系统规 模不断扩大，复杂程度不断提高，这种现况往往使新手望而却步，无法根上内核 发展的步伐。 本文旨在探索如何借助可视化技术解决上述状况。在信息的组织和呈现上， 可视化方法更符合人们的认知心理，其目标就是要帮助人们增强认知能力，通过 将各种抽象数据用有意义好理解的图形图像呈现，化抽象为形象，使信息更容易 被接受。x e r o xp a l oa l t o 研究中心的学者c a r d 等人提出可视化能够从6 个主要 方面增强人们的认知能力：一是通过扩大用户可用的信息存储量和可以处理的资 源量；二是减少用户对信息的搜索；三是通过使用可视化表示可以提高对于模式 的发掘；四是通过调动感知推理操作；五是通过把感知注意于监控：六是通过把 信息编码为可操作的媒介。鉴于可视化在提高人们认知能力方面可以发挥的巨大 潜力，如果能够以数据形式把“n 恹内核运行时的关键状态描述出来，利用可视 化技术，以形象直观的方式重构出内核关键活动真实的执行过程，将成为学习 山东大学硕士学位论文 “n 恹的有效手段。 1 2 相关工作和研究现状 由于操作系统本身特别是l i n l d 【内核研究的重要性和复杂性，人们开辟了各 种学习和研究途径。大量出版的相关书籍是比较传统方法的代表，但即使是经典 的教材【l 棚，对于重要数据结构、算法和过程的阐述都局限在静态图表和文本叙 述的抽象层次上，理解内核的深层机制仍然有一定难度。 网络上存在大量的演示动画用来模拟操作系统的基本原理和算法【删。如 o s c a l ( o p e r a 血gs y s t 咖c o n c e p t 心m a t i o nl i b r a 巧) 1 6 堤一个操作系统概念动 画库，动画演示包括进程调度，磁盘调度、页面置换等机制中常见的算法，其中 涉及的所有过程和活动的数据都是预先构造出来的。这种方式在阐明原理方面比 较直接，但与实际的操作系统脱节，数据来源不真实，只能在形式上单纯介绍原 理不适合深入操作系统内部的机制。 针对上述状况，现有一些仿真结合真实的操作系统进行可视化，k e v i n k l e u n g 设计了一个运行在l i n u x 操作系统上的可视化工具唧，用来模拟l i n u x 进程调度算法，通过该工具提供的图形环境，使用者选取一组预先定义好的具有 特定属性的进程作为输入，各个进程按指定的调度算法执行调度，通过采集一些 内核运行时信息，事后对调度过程进行可视化。这个工具的优点在于数据源的真 实，但是仅局限在对于进程调度算法的模拟：s u a l0 s 是g n 0 g t k 十下的 操作系统教学仿真软件【，需编译安装在l i l l 慨系统上，利用这个软件不需编写 一句代码就能操纵系统运行，允许用户为c p u 、内存和磁盘i o 等每一个子系统 选择不同的算法，并能以图形方式可视化出运行的操作系统，这个软件在内核与 用户之间担当了桥梁功能，在阐明和可视化o s 子系统基本原理和子系统之间的 协作方面很直观，但用户直接接触的是该软件，而不是真正的内核，层次不够深 入。类似的可视化研究工作还有很多【“”，虽然其应用范围、对象、目的、可 视化侧重点各有不同，它们的不足往往集中在通过预先定义若干可处理的系统状 态和活动集合进行可视化模拟，这种静态绑定限制了适用和推广的范围，并且其 可视化与源码的数据结构和函数脱节，而深入理解l i i l l d 【内核机制离不开适当的 源码学习。 2 山东大学硕士学位论文 另外，o p e r 黟s 和l i i l 公司合作研究了“n 的内核跟踪机制l 1 广r ( “n 暇 e1 的l h t ) n q ，这是一个内核性能的分析工具，通过在内核中跟踪某段特 定时间内系统的行为，以图形方式使用户观察系统，了解系统的动态活动，这是 一个从整体上分析监控系统性能的有效工具，但其后期的数据处理和图形可视化 效果偏重性能分析而不适用于深入学习和研究l i l l l d 【内核。 综上，对研究现状的分析表明，若要建立一套基于“n l d ( 操作系统平台，对 其中关键过程进行可视化的科研和教学实验方法，需具备几个特点：1 、紧密结 合真正运行的操作系统，要求数据源真实；2 、方法需具备可扩展性和通用性， 不能局限于预先定义的若干内核关键过程，根据具体可视化的需要应该能够自由 选择过程对象；3 、结合源码中重要的数据结构和函数实现可视化，从源码出发 深层次理解l i n u x 内核中关键过程的实现；4 、可视化效果直观。简言之，本文 将立足于内核运行时的真实数据、结合源码研究内核关键过程的可视化。 1 3 主要工作及章节安排 1 本文的主要工作 为直观地显示“n i | ) 【系统中关键操作的执行过程，本文的创新点在于以真实 数据为基础探索对关键过程的可视化方法。 ( 1 ) 针对l i i l 慨系统在某个特定时间段内的执行过程，从内核源代码出发， 分析出能够表达内核状态的程序特征，提取出关键状态，确定一种通用且合理的 内核状态描述方法，定义相应的数据采集点获取数据描述内核状态，对采集点分 类，定义每一类关键状态的数据描述格式。 ( 2 ) 通过研究软件可视化的基本理论，探讨了操作系统关键过程可视化的 特殊性，从数据量、数据粒度角度分析内核关键状态数据的特征，总结出过程可 视化中数据采集的基本原则，结合基本原则分析常用的内核数据采集方法，在此 基础上设计出一个适合的数据采集方法。 2 本文的章节安排 本文第二章将从可视化的基本理论出发，介绍近年来可视化的发展现状和应 用范围，特别是软件可视化的概念、内涵和关键问题，在此基础上着重探讨操作 系统关键过程可视化不同于普通软件可视化的特殊性，分析要考虑的关键问题， 接着给出过程可视化的总体工作流程，并在这一章重点解决可视化的数据源问 3 山东大学硕士学位论文 题：描述l i n u x 内核关键运行状态、分析数据采集点的种类、定义数据采集点格 式。 随后的章节结合过程可视化中要关注和展示的重点内容，给出数据采集应该 遵循的原则，结合这些原则探讨常用的内核数据采集方法的可用性，分析数据特 征给出本文采用的数据采集方法流程，并且详细介绍了实现的关键技术和实际应 用中应该考虑的问题。 本文第四章在现有实验平台上，跟踪内核的一次缺页异常处理过程，结合源 代码函数详细说明不同种类数据采集点的设置方法，逐步解析采集到的若干数据 记录，通过将数据可视化处理，图形化重构内核的关键状态来验证所定义数据格 式的可用性。这一章最后展示了目前工作中由程序实现的可视化效果示例。 文章最后对当前工作进行了总结，分析不足之处并展望了l i n l l 】【操作系统关 键过程可视化下一步的工作重点和发展前景。 4 山东大学硕士学位论文 第2 章操作系统过程可视化的研究方法和内容 2 1 可视化简介 可视化泛指利用计算机图形学和图像处理技术，将数据转换成图形或图像在 屏幕上显示出来并进行交互处理的理论、方法和技术，这是一个展示数据并获得 对数据更深层次认识的过程。它作为一门新的学科和技术领域出现的标志是 1 9 8 7 年美国科学基金会( n s f ) 组织召开的“科学计算可视化”专题研讨会，以 及大会后m c c o m i c k 等人发表的“科学计算可视化( 鲫a l i 砑l i i l ls c i 铋t i f i c c o n l p 咖吕s c ) ”报告，或简称可视化( 蛐a l i 翻虹0 n ) 。最初的可视化专指科 学计算可视化，它涉及到计算机图形学、图像处理、计算机辅助设计、计算机视 觉及人机交互等多个领域，其实质是运用计算机图形学和图像处理技术，将科学 计算过程中产生的数据及计算结果转化为图像，在屏幕上显示并进行交互处理， 它被广范应用于医学、气象、分子生物学等多种领域i ，多用在对空间数据场 物理数据的可视化处理上。 随着社会信息量的激增和数据的多元化，越来越多的非空间数据出现，需要 强有力地分析工具来对其进行有效的处理和利用，信息可视化( h l f o 衄撕 s u a l i z a 矗o n ，) 应运而生，这成为信息科学的重要研究领域，g r o b e r t s 、 s k c 盯d 与u ) m 卵l c i l l l 研在1 9 8 9 年首次明确提出概念啪l ，c a r d 称它为“计 算机支持的、人机交互的抽象数据图像化方法，从而帮助用户增强识别信息的能 力”。近年来技术迅速发展，深入到医疗、地理、数据挖掘、网络信息搜索、 软件和程序理解等各种应用中，如与数据挖掘1 及与软件可视化吲的结合应用， 特别是软件可视化已成为可视化技术的一个重要分支，也取得了长足进展，下一 节将详细阐述。 2 2 软件可视化 软件可视化( s 曲啪r e s u a l i z a t i o n s ，s v ) 作为可视化技术的一个重要分支， 结合了软件工程、数据挖掘、计算机图形学、信息可视化、编程语言和人机交互 山东大学硕士学位论文 等不同领域的各种技术，其主要目标，一则是实现对软件中复杂程序和算法的理 角翠，二则是帮助程序员管理复杂的现代软件。但不论软件处于开发、研制还是运 行阶段，它都是无形、抽象的，没有明显的物理形体和形态，作为其主体的程序 一旦编写完成装入计算机后，就消失在存储介质上成了一种抽象的逻辑实体。为 了化抽象为形象，使软件在理解、使用、管理以及开发、测试、维护等方面有更 好的发展，软件可视化应运而生。 2 2 1 软件可视化的概念 软件可视化是研究如何利用交互式计算机图形技术以及图形、印刷、颜色、 动画、音频、视频等各种手段，增强软件中算法和程序理解性和使用效率的学科 瞄1 。广义来讲，在程序开发过程中，可视化编程( 如v i s u a ib 嬲i c 、飘| a lc + + 等可视程序设计语言) 和可视化软件开发也在软件可视化的范畴里，因为从普通 意义上来讲基本上近年来的编程活动都是可视的，但本文将讨论范围限制在软件 的执行环节，不涉及开发和管理环节，探讨的可视化目的专门在于提高软件本身 的可理解性。 形式上来讲，软件可视化被定义为一种从程序到图形显示的映射，包括程序 ( p r 0 j 釉m ) 、映射( 删i p p i i l g ) 、图形( g r a l 烛c a lr 印嘲朗t a t i ) 三要素搿。5 1 ，其 关键问题是如何将表明系统状态和行为的程序特征映射至图形或者动画表示，更 详细地讲，主要问题有：如何描述程序的状态和行为特征，相应的数据格式如何 定义；定义何种图形符号用来表示程序执行中涉及到的各种物理和逻辑元素，定 义何种恰当的标准来表征元素的不同状态和行为；如何定义程序特征到图形元素 之间的映射关系等。 2 2 2 软件可视化的内涵 概述软件可视化基本理论的文献较多卿”，从不同角度诠释了它的内涵， 并对现有软件可视化系统进行分类。可视化从总体上包括定义在较低层次的程序 可视化和较高层次的算法可视化两部分，而n 母e 瑙从可视化方面( a s p e c t ) 和显 示模式( d i s p l 妙s l y l e ) 两个角度对可视化系统进行了详细划分嘶1 ，其中可视化 关注的方面包括代码、数据和算法，显示模式分为动态和静态模式，下面在较高 山东大学硕士学位论文 层次上结合这个详细分类说明软件可视化的内涵。 程序可视化( p r 0 掣锄v i s u a l i z a t i o i l ，p v ) 伫6 1 指对程序代码、数据结构的静态 或动态特征进行的可视化。程序代码可视化常见的形式有打印源代码、程序结构 图、调用树等，分为静态代码可视化和动态代码可视化( 又称代码动画) ，前者 通常只是打印出代码或者利用某种软件建立程序映像实现静态观察，而后者则跟 随程序的执行路径着重展示当前代码或动态数据。数据结构可视化常见的形式有 复合的数据结构图、数据流图、调用堆栈的活动视图等，分为静态数据可视化和 动态数据可视化( 又称数据动画) ，前者以静态模式图形化展示数据结构，后者 则以动态模式展示数据结构在执行中的变化。 算法可视化( a 1 9 0 删 1 i n s u a l i z a 五伽，a v ) 陬舢1 l 一般以研究和教学为目的， 针对软件较高层次的算法进行可视化。它将程序的数据、操作和语义提取出来进 行演示，一般分为两类，一类是静态算法可视化，通过一系列静止的图像来展示 算法的执行过程，最简单的例子如流程图、n - s 图等；另一类是动态算法可视化， 将算法的执行过程以动画的形式连续描述出。 事实上程序可视化和算法可视化紧密不可分，都要涉及到代码、控制流程、 数据结构等主要内容的可视化，其最主要的差别来自于可视化系统设计的初衷， 如果系统重点在于研究软件通用的一般算法，则被归类于算法可视化，如果是侧 重于实现某种具体算法，将更加倾向于程序可视化。 2 2 3 软件可视化的关键问题 在设计软件可视化系统时，围绕着程序、映射和图形三个软件可视化的要素， 需要从软件对象本身的特征、待可视化的内容、系统的应用目的等角度出发考虑 一些关键问题。 1 ，可视化的应用范围，它是针对于某个实例还是适用于具有特定类型的任 意程序，是否要受到具体硬件条件、操作系统类型或编程语言种类的限制等。 2 、可视化的内容，指要对程序的哪些方面进行可视化，侧重于程序的可视 化还是算法可视化或者二者兼顾。这里需要考虑的关键问题是根据具体的应用目 的定义哪些需要可视化的程序特征，通常的特征会定义为代码、数据、控制状态、 执行行为等。 7 山东大学硕士学位论文 3 、可视化与被可视化软件之间的连接方法。当对一个软件对象进行可视化 时是否需要对源代码有一定程度的了解，可视化数据采集是否要影响和改动程序 源代码，可视化系统是否实现对于软件的完全自动可视化，可视化系统与被可视 化软件是否具有紧密的耦合性。 4 、数据采集时间和可视化生成的时间。第一，数据采集时间指何时采集可 视化所需要的数据，在编译时进行还是运行时进行，如果是在运行时采集则需考 虑程序运行时间和可视化时间之间的映射方式，这大体分为三种类型。( 1 ) 当程 序执行到某时间点，采集数据重构出程序体此刻的状态，相当于为它生成一个静 态快照；( 2 ) 采集程序在某个时间段内执行的数据序列，重构出程序体在这段时 间内的运行轨迹；( 3 ) 采集程序在某一个执行周期中的数据并生成可视化。第二， 生成可视化结果的时间有实时和非实时两种：运行时采集数据，事后按批作业处 理方式来生成可视化或者采用实时方式边执行程序边生成可视化。 2 。3 操作系统过程可视化 软件本身是不能独立存在和工作的，它依赖于运行环境，包括计算机系统硬 件、通信网络、支撑软件等要素。操作系统作为支撑软件，更是与运行的硬件平 台紧密相关，其规模和复杂性远高于普通软件，其中关键过程的可视化既具有软 件可视化的普遍性，也具有特殊性。下面首先结合2 2 节探讨操作系统可视化的 特殊性和需要考虑的关键问题，并给出操作系统过程可视化的工作流程。 2 3 1 基于开源的l i n u x 本文着眼于从源码出发借助可视化技术提供一种深入学习l j l l 内核的有 效手段，基本思路是通过记录操作系统实际运行过程中所发生的事件及其处理过 程，并以可视化的形式展现出来，让观察者能够观察到操作系统的实际运行过程， 体会操作系统的运行机制和原理，从而达到完整理解操作系统中事件、过程、方 法、机制和原理的目的。下面结合2 2 3 中提出的问题，探讨对l i n 畎操作系统 中关键过程进行可视化时需要考虑的问题。 1 、应用范围：操作系统关键过程可视化同样需要具备程序、映射和图形三 要素，程序要素决定了必须获得源代码，而“n 暖的开源特性满足了此必备条件， 山东大学硕士学位论文 这同时也限制了过程可视化的应用范围，针对u i l i x 、f r e i 出s d 、s 0 l a r i s 等开源系 统的关键过程是可行的，而针对虽使用广泛但不公开源码的w i n d o 懈系列操作 系统则不能实现。从硬件平台来讲，l i i l l d 【操作系统本身可跨平台，支持a l p h a 、 舭n 、i 3 8 6 等多种体系机构，所以本文探讨的过程可视化不受硬件平台的制约， 具体选择了p c 机上较常用的i 3 8 6 平台。 2 、可视化内容：深入理解l i n 内核的某个执行过程，对它可视化时，其 主要内容应包括此过程中各种内核元素的静止状态和动态变化，各种元素既包括 实际存在的计算机系统元素，如c p u 、物理内存、外部设备等实际的物理元素， 也包括进程、进程地址空间、页面、页表等抽象的逻辑元素。然而不论是物理元 素还是逻辑元素，映射到内核代码中，对应的都是定义为不同数据类型的变量， 元素的状态和变化通过变量的值和修改表达，因此本文跟随程序的执行过程着重 对程序代码和数据结构的静态或动态特征进行可视化。代码部分可视化采用函数 调用树，尤其是要展示内核在树上的动态执行路径，数据结构的可视化则集中在 展示执行过程中数据结构的各种状态和变化。 3 、可视化数据源与可视化软件之间的连接方式：这由数据源的真实性决定， 数据采集自运行的系统内核，而试图从内核出发记录系统的运行过程，必然要对 所关注的过程有较深入认识，对源代码有较深了解，还要在不影响内核运行的条 件下改动源代码采集数据。 4 、数据采集和可视化处理时间：真实的数据源决定了数据采集必须实时进 行，基于同样的原因要以事后处理方式进行可视化，这是由于数据处理和数据的 图形图像化要占用大量的系统资源，特别是针对比较复杂的内核执行过程时，数 据量会很大，实时可视化将对内核活动的真实性造成较大影响，因此采用事后可 视化策略。这决定了本文操作系统过程可视化的特色：实时数据采集使得可视化 结果具备真实性，而非实时的事后可视化策略又使其在时间上具有滞后特征。 2 3 2 数据的采集 操作系统过程可视化的真实性使数据采集成为首要问题，l i i l 慨的所有版本 的内核源代码都是网络上的公开资源，而且当前机器上系统内核源码可以在 璐r s r c ，l i n u x 目录下得到，同时其大部分应用软件都是遵循自由软件组织g n u 9 山东大学硕士学位论文 的通用公共许可证( 简称g p l ) ，g n u 组织的目的在于实现一个供大家自由使用 的完整的操作系统，大所数的g n u 程序和超过半数的自由软件都使用g 王 l ，这 意味着源码可以自由获得，通过对源码的了解能够深入理解系统的工作原理，并 量体裁衣定制适合个人需要的系统。源码的开放性为采集内核真实数据创造条 件，本文正是通过在源码中嵌入程序片段来采集数据、记录内核运行情况。由于 内核是操作系统中负责管理进程、内存、设备驱动程序、文件和网络等子模块的 核心，它直接决定着系统的性能和稳定性，为保证可视化的真实性，数据采集时 应尽可能减小对内核的影响。 2 3 3 可视化的工作流程 从前面的讨论可知，操作系统过程可视化对数据真实性要求较高，开源的 l i r i l | ) 【内核及重编译技术为采集这样的数据提供可能，整个可视化工作由数据贯 穿始终，分为内核数据采集和数据可视化两个相互独立的模块。总体工作流程如 图2 1 ，数据源为运行的l i l l u x 操作系统。 图2 1 ：操作系统过程可视化的工作流程 内核数据采集模块：以“n 恹操作系统为运行平台，通过在源码中设置各种 数据采集点记录内核运行时的真实数据，在系统运行时加以采集并转存为磁盘文 件。这个模块的设计和实现是本文将要探讨的重点内容。 数据可视化模块：脱离l i n 畎数据采集运行平台，模块内定义好程序特征到 图形的映射和实现数据解析的数据接口，如2 3 1 所讨论，映射的目标主要集中 在对函数调用树和各种数据结构的可视化，接口用来解析特定格式的数据。可视 化模块由数据采集模块得到的数据驱动，通过对数据进行解析、重构处理，按照 预先建立好的映射进行可视化显示。 两个模块既相互独立又紧密关联：它们在物理上相对独立，两者通过定义好 解析特定数据格式的接口关联，内核数据采集模块输出固定格式的数据文件，可 视化模块以数据文件为驱动，按照双方达成的协议解析并处理数据，实现数据可 山东大学硕士学位论文 视化：最终要可视化的执行过程，决定了采集模块中应该关注哪些程序特征，相 应决定了需要采集哪些数据，数据的内容和特征进而决定了数据采集的基本原则 和方法。 2 4l i n u x 运行过程中关键状态的描述 本小节着重分析内核运行过程中的关键状态，定义能够表征其状态和行为的 数据形式。b s l l i l e i d e m 锄按信息源特征将数据分为以下7 类【3 2 l 。 ( 1 ) 一维信息：简单线性数据类型，如文本文档、数字表格，程序源代码 等都是基于一维线性数据的，其特征是数据按照顺序方式加以组织； ( 2 ) 二维信息：由两种主要属性来描述客观事物，如地理信息系统用二维 平面中x 和y 轴坐标为平面上某点定位，平面中的物体其高和宽可以描述其大小： ( 3 ) 三维信息：描述立体三维空间中物体，真实世界的物体如分子、人体、 建筑物都可以用三维信息描述，最初的可视化应用如科学计算可视化的主要目的 就是表示现实的三维物体，所以将它归类于三维信息可视化： ( 4 ) 多维信息：用来描述有三种以上属性的物体，对大多数关系型数据库 来说，具有n 个属性的记录信息成为n 维空间里的点，这使得操纵数据更为方便； ( 5 ) 时态信息：信息自身具有时间属性，以图形方式显示随着时间不断产 生变化的数据，常见的应用有项目管理、医疗记录等； ( 6 ) 层次信息：满足树形或层次关系的数据集，除根节点之外每个节点都 有一个父结点，如计算机操作系统上的磁盘目录结构和家谱图等； ( 7 ) 网络信息：节点之间存在网状联系的数据集，不存在等级结构，每个 节点可能与其他任意数量的节点有联系，如因特网上成千上万台服务器之间错综 复杂的关联。 针对不同类型的信息，采用的可视化方法不同。其中时态信息指事物本身按 时问序列发生而生成的数据，这种自身具有时间属性的信息被称为时间序列信 息，对其有效的可视化方法是根据时间顺序图形化显示事物。l i i i l d 【在执行中产 生的数据本身具备时间属性，适用于时态数据可视化，所以在可视化模块中，将 借鉴多媒体软件制作中的时间线概念来展示数据的时间属性。针对内核执行中产 生的连续时序信息，通过提取出内核执行中各种关键状态并以数据形式描述这些 山东大学硕士学位论文 状态，解决可视化的数据源问题。 2 4 1 提取关键状态 l i l l u ) 【是单内核的，内部被分为进程、内存、文件、网络等多个基本的功能 管理模块，基本模块间的通讯是通过直接调用其它模块中的函数实现而不是通过 消息机制【1 j ”4 】，以这样的方式合作完成各种内核活动，使得运行中的内核相当 于执行中的大程序体，对于一个程序体，其关键状态就是关键时刻函数及变量的 状态，规定函数和变量是所关注程序的重要特征。这里将关键过程的可视化界定 在程序可视化( 函数调用树和数据结构可视化) ，并于程序可视化中体现重要算 法和内核管理机制。 以l i n l d 【系统完全启动的时刻为时间轴原点，内核在时问轴上正向运行，设 r r s ，1 明( t s 0 ) 为待可视化的运行时段，假定在此区间发生的活动相对独立且完 整。内核的关键状态指t 时刻( t 【强t e l ) 执行哪个函数、以何种方式操作哪 个全局或局部变量。如上所述，( 1 ) 程序的第一个重要特征是函数，其执行信息 在可视化模块中将映射至函数调用树的显示，根据当前执行的函数确定内核在调 用树上的位置，所有函数在【t s ，t e 】内都有被调用的可能，需全局跟踪。( 2 ) 程序 的第二特征是变量，其中不同类型的全局变量在“n l d 【里用来表示各种物理元素 ( c p u 、物理内存等) 或逻辑元素( 进程、内存区、页、页表等) 的状态，若在 【t s ，t e 】内有被访问的可能，都需全局跟踪，在可视化模块中将关注于数据结构的 内容、改变及变量间的组织关系，通过对数据结构的可视化展示内核元素的状态 和变化：局部变量通常用作控制和标志信息，结构简单，不代表抽象的系统资源， 只活动在所属函数执行时段内，局部跟踪即可。 脱离l i l l u x 数据采集模块的平台，在可视化平台上对需要全局跟踪的函数和 全局变量建立对象数据库，并重新建立函数间、全局变量间的关系，即在新的平 台上重构出一个运行的系统整体状态或与某过程相关的部分内核状态。其中，函 数间的关系指其相互间的调用和被调用关系；全局变量之间的关系则根据内核源 码的定义，由其相互间的结构嵌套和指针指向关系决定的，下面详细阐述。 数据库里的对象，无论是函数还是全局变量，需为它们定义关键字作为唯一 标识。( 1 ) 函数在运行内核中名称唯一，规定函数名为函数对象关键字；( 2 ) 内 山东大学硕士学位论文 核使用一个叫做进程描述符p m 的数来标识进程，每个进程具有唯一的p d ，是 分配系统资源的实体，而各种系统资源在源码里映射为全局变量，因此选取进程 为单元划分全局变量集合，而全局变量在进程的地址空间内具有唯一的线性地址 ( 又称虚拟地址) ，是一个3 2 位无符号整数，代表进程4 g 大小的虚拟地址空间， 规定全局变量对象关键字为皿和线性地址组合。 针对函数对象，可视化平台建立对象数据库，通过扫描l i n 慨源代码文件， 从中筛选出所有函数和函数调用关系，分别建立两个表，一个用来记录所有函数， 一个用来记录所有的函数调用关系，函数调用表的所有记录形成了对象问函数调 用树全图。同时，为了获得内核函数的动态执行路径，f r s ，1 e 1 时段内数据采集模 块需全局跟踪内核，在执行路径上采集函数的动态执行信息。综合静态函数调用 树和动态执行路径，就可以可视化出随时间推移内核的函数特征。 针对所有在【t s ，t e 】期间可能被访问到的全局变量对象，在可视化模块的对象 数据库中为所有全局变量对象建立一个表，记录全局变量的相关信息，并在可