（计算机应用技术专业论文）pass系统的起源信息收集及传播的研究.pdf

祈江大学硕士学位论文 摘要 感知起源的存储系统( r o v c n 蛆c e - a w a r es t o r a g es y s t e mp a s s ) 是自动收集系 统中对象起源信息的存储系统。起源信息是指，一个文件对象的完整历史数据， 包括产生数据时的命令及参数，产生数据时系统的环境参数，操作系统的版本信 息，对象之间的关系等等。p a s s 系统在内核层收集起源信息，p a s s 用户可阻透 明地使用文件系统而不需要关注p a s s 系统的细节。 p a s s 系统在内存中收集起源信息时，首先是用单向链表将内存中的进程对 象和文件对象收集起来，并保持文件与文件，文件与进程的关系。可是当对象之 问的关系比较复杂的时候，会出现环。p a s s 系统采用的是先检测再消除的方法 解决环的问题。算法的时间复杂度为o f n 2 ) ，效率比较低，影响系统的整体性能。 本文采用基于进程粒度上的收集算法来改进原p a s s 的收集算法，可以将算法的 时问复杂度降为o n ) ，有效提高系统的性能。 目前p a s s 系统处在开发初期，现在的版本还没有涉及到p a s s 系统之间传 输文件的问题。也就是说，当p a s s 系统在传输文件时，与文件相对应的起源信 息如何传播的问题还没有提出解决办法。本文对p a s s 系统之间的传输问题提出 初步的设计，通过两个步骤完成文件的传输：第一步是在文件传输后，通过监视 传输进程来获取文件发送方的i p 地址，端口等信息，并将这些信息作为文件的 起源信息存放在数据库中。第二步是由文件的起源信息提供的文件来源向文件发 送方请求原文件的起源信息。 在文章的最后，我们比较了原p a s s 与改进过的p a s s 两者的性能。通过数 据的比较，我们发现在时间的消耗方面，改进过的p a s s 要比原p a s s 减少5 0 左右。在起源信息传播方面，我们的模型能够初步传播文件的起源信息。 关键词：起源信息，感知起源系统，起源收集算法，起源信息传播 浙江大学硕士学位论文 a b s t r a c t p r o v e n a n c e - a w a r es t o r a g es y s t e m ( p a s s ) i sas t o r a g es y s t e mt h a ta u t o m a t i c a l l y c o l l e c t sa n dm a i n t a i n sp r o v e n a n c eo rl i n e a g e ，t h ec o m p l e t eh i s t o r yo ra n c e s t r yo fa n i t e m p r o v e n a n c ei st r a d i t i o n a l l yt h eo w n e r s h i ph i s t o r yo fa no b j e c t p a s sa u t o m a t i c a l l yg e n e r a t e st h ed a gd e s c r i b i n gt h er e l a t i o n s h i pb e t w e e n p r o c e s s e sr u n n i n go ni ta n dt h ef i l e ss t o r e di ni t p a s st r a c k sp r o v e n a n c ea taf i l e g r a n u l a r i t y h o w e v e r , w h e nt h er e l a t i o no f0 b j e c ti sc o m p l e x ，c y c l e sw i l la p p e a ri n d a gp a s sd e a l 、砘t ht h i sp r o b l e mb yd e t e c t i n ga n db r e a k i n gc y c l e s b u tt h et i m e c o m p l e xo f t h ea l g o r i t h mi s0 ( n 2 ) ，t h ew o r ke f f i c i e n c yi sm u c hl o w , a n dt h e ne f f e c t t h ee f f i c i e n c yo fw h o l es y s t e mb a d l y t h ep a p e ri n t r o d u c e sa n o t h e ra l g o r i t h m ，t r a c k p r o v e n a n c ea tap r o c e s sg r a n u l a r i t y , t od e a lw i t l lt h ec y c l ep r o b l e m t h et i m ec o m p l e x o ft h ea l g o r i t h mi s0 ( n ) p a s si sa tt h eb e g i n n i n gp e r i o do fd e v e l o p m e n t ，t h e r ei sn oi d e ao fh o wt od e a l 丽t ht r a n s p o r tp r o b l e m i no t h e rw o r d s ，t h e r ei sn oa n yp r o t o c o lt os e n dp r o v e n a n c e w h e np a s st r a n s p o r t sf i l e s t h ep a p e ri n t r o d u c e sap r e l i m i n a r ym e t h o dt od e a lw i m t h et r a n s p o r tp r o b l e m ，t h ed e s i g ni n c l u d e st w os t e p s ：f i r s ts t e p ，a f t e rt r a n s p o r t i n gt h e f i l et ot h ec l i e n t ，p a s sm o n i t o r st h ep r o c e s s ，t h a tt r a n s p o r tf i l e s ，t oo b t a i nt h es o l v e r s i pa d d r e s sa n dp o r ti n f o r m a t i o n , a n dt h e np a s sc o n v e r t st h e s ei n f o r m a t i o nt ot h e f i l e sp r o v e n a n c ea n ds a v e si nt h ed a t a b a s e s e c o n ds t e p ，p a s sg e t st h er e s o u r c e i n f o r m a t i o no ft h ef i l ef r o mt h ef i l e sp r o v e n a n c ea n du s et h ei n f o r m a t i o nt or e q u e s t s o l v e rf o rt h ef i l e sp r o v e n a n c e i nt h ee n d ，im a k eas e r i e so fe x p e r i m e n tt oc o m p a r et h ep a s sa n dt h em o d i f i e d p a s s a c c o r d i n gt ot h ed a t ao fe x p e r i m e n t ，if i n dt h a tm o d i f i e dp a s si sf a s t e rt h e n p a s sb y5 0 a n di nt h ea s p e c to fp r o v e n a n c ep r o p a g a t i o n ，m o d i f i e dp a s sc a n p r o p a g a t ep r o v e n a n c ew h i l et r a n s p o r t f i l e s k e y w o r d s ：p r o v e n a n c e ，p a s s ，p m v e n a n c ec o l l e c t o ra l g o r i t h m ，p r o v e n a n c ep r o p a g a t i o n 浙江大学硕士学位论文图目录 图目录 图3 1s o r ta b 命令调用的关键系统调用和收集起源信息的步骤1 8 图3 2 进程与文件形成环2 0 图3 3 将形成环的进程合并为一个进程集合2 l 图3 4 新的进程作为两个文件的前驱者2 l 图3 5 滑动窗口示意图。2 3 图3 6 基丁进程粒度上算法来改进p a s s 的收集算法。2 7 图3 7 检测到环2 8 图3 8 消除环。2 9 图3 9 再次检测到环2 9 图3 1 0 消除环3 0 图3 1 l 基于进程粒度上的算法形成的关系3 0 图4 1 起源信息传播的实现框架3 4 图4 2p a s s 起源信息传播的实现3 7 图5 1 进程粒度上收集算法的实现框架4 0 图5 2p a s s 与n e w - p a s s 消耗磁盘的比较4 3 图5 3p a s s 与n e w - p a s s 在时间消耗方面的比较4 3 图5 4e x 9 2 、p a s s 和n e w 二p a s s 在对大文件操作是的时间开销比较4 5 l l i 浙江大学硕士学位论文 表目录 表目录 表2 1s o r ta b 命令的系统调用及描述1 2 表2 2 存放起源信息的数据库1 5 表3 is o r ta b 需要记录的起源信息表项1 7 表5 1 使用小文件进行测试的磁盘开销，单位为k b 一4 1 表5 2 使用小文件进行测试的时间开销，单位为秒4 2 表5 3 使用大文件进行测试的时间开销，单位为秒4 4 i v 浙江大学硕上学位论文所江太掌 i 奸咒生学位论， b 命令为例，收集器的工作相对简单。它为每一个与起源相 关的系统调用都生成起源信息，并将这些起源信息写入合适的数据结构。表2 1 总结了收集器分析的系统调用，产生的起源信息和这些起源信息写入的数据结 构。 表2 1s o r t a b 命令的系统调用及描述 系统调用项目类型 描述存放目标 e x e c v ee n v 环境当前进程 a r g v 命令行参数当前进程 n a m e进程名字当前进程 p d 进程i d当前进程 k e r n e l 内核版本当前进程 m o d u l e s内核中加载的模块 当前进程 i n p u t调用的其他进程当前进程 o p e n o p e n n a m e文件的路径目标文件的i n o d e r e a di n p u t输入文件 当前进程 w r i t ei n p u t 当前进程目标文件的i n o d e 收集器的功能： 功能一：消除重复项。在上面的示例中，如果输入文件相当大的话，s o r t 命 令可能会多次调用r e a d 系统调用。尽管后面的几次记录信息是第次的重复信 息，可是简单的收集器会为每次的r e a d 系统调用都生成一个i n p u t 类型的起源 信息项目。p a s s 收集器试探性地在两个方面消除重复。 1 2 浙江大学硕士学位论文第2 章感知起源系统介绍 收集器产生一条新的记录后，会检查数据结构中是否存在完全相同的记录 项，如果存在则丢弃新的记录项。考虑一个s h e l l 命令( s o r ta ；s o r ta ) b ，这个命 令两次将排序的a 文件写入文件b 。两个s o r t 命令都读a 文件，并将a 记录为进 程的前驱者。当收集器遍历内存中的图为文件b 写起源信息时，也会发现指向a 的两个引用都出现了。因此，收集器在遍历内存中图的过程中也可以消除一些重 复的信息。这种方式是通过消除图中的相同文件来达到目的，可是两个s o r t 进程 拥有两个不同的进程号，起源信息还是会记录有两个s o r t 系统调用被调用。 功能二：新的版本号。假设我们运行命令“s o r ta b ”，但是文件b 是已经存 在的。系统会先将b 中的内容清除掉然后写入新的内容。逻辑上创建了一个新的 文件版本。因为新的文件b 可能和旧的文件b 没有任何关系，所以系统需要生成 一个新的版本号来对应文件b 新的起源信息。生成一个新的起源信息版本需要生 成一个新的p n o d e 号，收集器分析t r u n c a t e 操作并在适当是时间为新的文件产生 新的版本号。 我们不能在文件系统中保存文件b 中以前的数据，但是p a s s 系统需要保存 文件b 以前版本的起源信息，因为以前文件b 可能是一个很重要文件的先驱者， 系统需要保存那个文件的起源信息。 在这个示例中，要确定什么时候创建新的版本号是相对简单的。可是，在一 般的应用中，声明一个新的版本要复杂得多。例如，有一系列的w r i t e 系统调用 被调用，p a s s 需要为每一个w r i t e 系统调用生成一个新的版本吗? 如果进程在每 次写入后都关闭文件，然后再打开写入，系统又该怎么做呢? 如果只是简单的为每一次的写操作都生成一个新的版本，系统中的版本数量 将迅速增加，生成的起源信息也会大幅增加。收集器必须能够将多个写操作合并 为一个写操作，只产生一个新版本。在这个简单的示例中，系统可以在文件关闭 时或者同步时，生成一个新的版本。 功能三：维护对象之间的关系，处理图中的环。理想情况下，系统只为真正 存在的对象产生新的p n o d e 号，收集内存中存在的文件对象，及对象之间的关系， 对象的起源信息等，并将对象之间的关系在内存中建立一个图，图采用单向链表 的数据结构记录对象之间的关系，有两种节点，一种节点记录进程的信息，一种 节点记录文件的信息，进程读文件，文件成为进程的前驱者，进程写文件，文件 浙江大学硕士学位论文第2 章感知起源系统介绍 成为进程的后继者。当需要收集对象之间的关系时，收集器会遍历图。可是随着 工作复杂的增加，收集器在遍历过程中的会遇到一个很有挑战的问题，那就是当 内存中对象之间关系图形成环时，收集器的遍历过程会出现无法停止的状态。例 如，一个程序的执行顺序为： r e a d a w r i t e a 程序读文件a ，在关系上，程序成为文件a 的后续者，然后程序对文件进行 写操作，程序成为文件a 的前驱者。这样就形成了一个环，除非对文件a 的写操 作创建一个新的版本。上面的这个特例是比较简单的情况，下面来考虑一个更复 杂的例子，进程p 和进程q ： 在c l o s e 系统调用被调用前，如果没有为文件生成新的版本号，q 进程的w r i t e 系统调用会形成一个环。进程q 是文件a 的前驱者，文件a 又是进程p 的前驱 者，进程p 是文件b 的前驱者，文件b 又是进程q 的前驱者。如果是更复杂的 例子可能会包含十几个进程和文件。 如果我们希望避免每次w r i t e 操作的时候都建立一个新的版本号，至少有三 个方法可以考虑： ( 1 ) 忽略它的存在，如果内存中的将环保存在数据库中，然后让查询工具处 理环相关的问题。这显然是不可以接受的。 ( 2 ) 修改文件时，只有当改写起源信息是，才生成新的版本号。这种方法会 产生大量的版本号，在文件系统中，太多的版本号会占用很多资源。 ( 2 ) 检测并消除环，这种方法就是p a s s 目前采用的方法。 组成部分二：存储层，存储层由堆栈式文件系统组成，叫做p a s t a 。p a s t a 1 4 浙江大学硕士学位论文 第2 章感知起源系统介绍 使用一个数据库来存储元数据。p a s t a 使用f i s 9 1 8 i t 具包使自己在一般文件系统 层之上。p a s s 使用e x t 2 文件系统作为自己的宿主文件系统。 p a s s 使用b e r k e l e y 1 9 】数据库来存放元数据【2 0 1 。b e r k e l e y 数据库提供快速的 索引查找和存储k e y v a l u e 数据对功能。b e r k e l e y 数据库让应用程序设计它们的 表，定义数据库主索引，次级索引，表之间的关系。数据库的一个表项由一个索 引项和对应的数据值组成。 p a s s 将起源信息存放在5 个数据库中，表2 2 是各个数据库块的信息。 表2 2 存放起源信息的数据库 起源信息的数据库 数据库名称 索引数据 n l a pi n o d e 号 p n o d e 号 p r o v e n a n c e p n o d e 号 起源信息数据 记录项类型 a r g d a i a序列数命令行及参数 a r g r e v e r s e命令行及参数序列数 a r g i n d e xa r g v 中的参数 p n o d e 号 p r o v e n a n c e 数据库是保存起源信息的核心数据库。在p r o v e n a n c e 数据库中记录的项目类型参见表2 2 ；在m a p 数据库中记录着从i n o d e 号到p n o d e 号的映射。文件的p n o d e 号在每次文件被写的时候都需要改变。a r g d a t a 数据 库实现了一个优化，将一个序列号赋值给每一个命令行和环境变量。 a r g r e v e r s e 数据库将命令行或者环境映射到a r g d a t a 提供的序列号。 a r g i n d e x 数据库提供一个二级索引，将命令和环境映射到p n o d e 号。用户为 文件添加的注释存放在p r o v e n a n c e 数据库的a n n o t a t i o n 类型中。 2 3 本章小结 本章介绍了感知起源系统的各种解决方案，包括文件系统和数据库的解决方 案、面向服务的解决方案、采用脚本的解决方案、指定环境的解决方案。在本章 的第二部分，我们介绍了本论文讨论的p a s s 系统，还介绍了p a s s 系统的组成 部分和各部分的相关功能。 1 5 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 第3 章p a s s 自动收集算法的改进 p a s s 的收集器功能很强大，涉及的面也很广，可是作为一个文件系统的辅 助工具系统，它的性能会直接影响整个文件系统，甚至是整个系统的性能。p a s s 收集器采用的是基于文件粒度上的算法来收集系统中对象的起源信息，在内存中 维护一个单向链表，链表记录着文件与文件，文件与进程之间的关系。收集器需 要时刻维护表中的对象信息，当一个新的对象加入环中时，收集器需要调用检测 环的函数，每一次检测环的函数执行，都需要消耗o ( n ) 的c p u 时间，对整个系 统来说，消耗的c p u 时间就是o f n 2 ) 。一个o ( n 2 ) 算法时刻在运行，这将会影响 整个系统的性能。 p a s s 的收集算法是收集记录文件与进程之间的关系、进程与文件之间的关 系、文件与文件之间的关系。当系统中的关系错综复杂时，p a s s 系统维护图的 难度会加大，性能也会降低，并且容易出错。现在的p a s s 版本在运行中有时会 出现错误，错误的根源就是因为系统中的对象之间的关系比较复杂，而在这种复 杂的关系下，调试的难度大大加大了，很难找到问题的出处。而更改这种现象最 根本的原因是改变这种复杂的算法，为了减小系统的复杂度，提高系统的性能， 我们需要为p a s s 系统研发一个新的收集算法。 3 ip a s s 收集器算法 3 1 ip a s s 系统收集器的实现描述 p a s s 系统是在l m u x 2 4 2 9 上实现，为了展示p a s s 模型的实现，我们使用 命令“s o r ta b ”为示例描述p a s s 是怎么收集并存储相关的起源信息。表3 1 是 命令“s o r ta b ”需要记录的起源信息表项。第一列为类型，第二列为值。其中包 括了起源信息对应的文件对象b ，命令参数s o r ta ，产生文件b 的命令b i n s o r t ， b i n c a t ，输入为文件a 的p n o d e 号，打开其它对象为l i b i 6 8 6 l i b c s o 6 ， u s r s h a r e l o c a l e 1 0 c a e a l i a s ，e t e m t a b ，p r o e m e m i n f o ，# p r o v m t a b ，当前的环境为 p w d = p a s su s e r 部o o t ，内核版本l i n u x 2 4 2 9 + a u t o p r o v # 1 7 。将这些信息收 集起来，存入数据库中，以后就可以查看文件b 的来源，并可以通过这些信息重 1 6 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 新产生文件b 。 表3 1s o r ta b 需要记录的起源信息表项 f i l ev a l u e f i l e，b a r g vs o r t n a m e b i n s o r t ，b i n c a t i n p u t ( p n o d e n u m b e ro fa ) o p e n n a m el i b i 6 8 6 l i b c s o 6 u s r s h a r e l o c a l e d c o c a l e a l a i s e t c m t a b ，p r o c m e m i n f o 却r o v m t a b 州 p w d = p a s su s e r - - r o o t k e r n e l l i n u x 2 4 2 9 + a u t o p r o v # 17 m o d u l e p a s t a ，k b d b ，a u t o f s 4 ，3 c 5 9 x ， 图3 1 显示了s o r ta b 命令调用的关键系统调用和收集相关起源信息的步 骤。我们看到，进程在运行中，将创建一个数据结构存放相关的起源信息，起源 信息就是前面描述的那些表项。进程处理完输入数据后，将结果写到输出文件中， 同时将进程收集的起源信息写入数据库中。 1 7 浙江大学硕士学位论文 第3 章p a s s 自动收集算法的改进 4 b t a m a t l 瞧 - 犁帕研t 归晰_ l 图3 1s o r ta b 命令调用的关键系统调用和收集起源信息的步骤 从图中，我们可以看出，s o r t a b 命令需要调用的关键系统调用和p a s s 系 统的相关步骤如下： ( 1 ) 由f o r k 系统调用创建一个新的进程。 ( 2 ) 为新的进程构建t a s ks t u c t 数据结构。 ( 3 ) 打开文件b 作为标准输出。 ( 4 ) 将文件b 的i n o d e 放入i n o d e 缓存中。 ( 5 ) 执行s o r t 系统调用。 ( 6 ) 为进程创建起源信息。 ( 7 ) 装载可运行文件；将文件的i n o d e 放入i n o d e 缓存中。 ( 8 ) 将可运行文件的i n o d e 与运行进程的t a s ks t u c t 关联起来。 ( 9 ) 打开输入文件a 。 ( 1 0 ) 将文件a 的i n o d e 放入i n o d c 缓存。 ( 1 1 ) 读取文件a 的数据。 ( 1 2 ) 将文件a 的起源信息加入当前进程的起源信息。 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 ( 13 ) 将运行结果写入文件b 。 ( 1 4 ) 将当前进程的起源信息传给文件b 。 ( 1 5 ) 关闭文件a 。 ( 1 6 ) 关闭文件b 。 ( 1 7 ) 将起源信息写入数据库中。 3 1 2 对环的处理 收集内存中存在的文件对象，及对象之间的关系，对象的起源信息等，并将 对象之间的关系在内存中建立一个图，图采用单向链表的数据结构记录对象之间 的关系。当需要收集对象之间的关系时，收集器会遍历图。可是随着工作复杂的 增加，内存中对象之间关系图会形成环。p a s s 收集器对环的处理方法是，在向 内存中图添加对象节点之前，收集器会先检测对象关系图中是否有环存在。如果 新加入的对象节点会产生环，收集器会调用环消除算法消除环。 最简单的消除环的方法是，当一个对象的加入会产生环时，就为这个对象产 生一个新的版本号。例如，如果进程读一个文件，而文件又是这个进程的后继者， 这样会产生一个环，如果为进程产生一个新的版本号，可以消除环。如果进程写 一个文件，而文件又是这个进程的前驱者，这时也产生一个环，如果为文件产生 一个新的版本号，也可以消除环。这个解决方法存在的问题是：为文件产生新的 版本号会导致版本号数量大幅增加。 p a s s 使用n o d e - m e r g i n g 算法来解决环的问题。n o d e - m e r g i n g 将形成环的几 个进程对象合并为一个进程对象集合，把他们的起源信息合并为一个起源信息集 合。如果环里包含n 个进程和m 个文件，收集器会将这些进程合并为一个新的 进程。每一个文件都成为这个新版本的后续者。 1 9 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 考虑进程p 和进程q ： 在c l o s e 系统调用被调用前，如果没有为文件生成新的版本号，q 进程的w r i t e 系统调用会形成一个环。进程q 是文件a 的前驱者，文件a 又是进程p 的前驱 者，进程p 是文件b 的前驱者，文件b 又是进程q 的前驱者。如图3 2 进程与文 件形成环。进程p 、q 与文件a 、b 形成了环，如果不去掉环，在收集器遍历图 的过程中，会出现不会停止的问题。 图3 2 进程与文件形成环 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 当收集器检测到图中形成了环，它会将环中的进程合并，如图3 3 所示。系 统将将环中的进程合并为一个进程集合，并将每个被合并进程的起源信息都写入 这个进程集合中。 将进程p ，q 合并为新的进程g 图3 3 将形成环的进程合并为一个进程集合 最后将环中的每个文件都标记为在上个步骤中形成的进程集合的后驱者，如图3 4 所示。 门 一、 ，iaj 、! ，。，一ib ) 、 图3 4 新的进程作为两个文件的前驱者 通过以上三个步骤，我们将链表中的环检测出来并消除。检测单向链表中是 否存在环的算法是采用两个指针来遍历这个单向链表，第一个指针p l ，每次走 一步；第二个指针p 2 ，每次走两步；当p 2 指针追上p 1 的时候，就表明链表当 中有环路了。 2 l 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣 圈。可以证明，p 2 追赶上p l 的时候，p 1 一定还没有走完_ 遍环路，p 2 也不会 跨越p 1 多圈才追上我们可以从p 2 和p 1 的位置差距来证明，p 2 一定会赶上p l 但是不会跳过p 1 的因为p 2 每次走2 步，而p l 走一步，所以他们之间的差距是 一步一步的缩小，4 ，3 ，2 ，1 ，0 到0 的时候就重合了。根据这个方式，可以证 明，p 2 每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环比 如，在环的周长l 是偶数的时候，初始p 2 和p 1 相差奇数的时候，p 2 每次走三 步，就永远和p l 不重合，因为他们之间的差距是：5 ，3 ，1 ，l l ，l 一3 。 对环的维护需要大量的c p u 时间。对环的检测算法的时间复杂度可以做到 o ，一个线性的复杂度，就对环的一次检测需要c p u 时间是不多的，但是， 在系统运行的过程中，会不断有对象加入到链表中，而每次新对象的加入，收集 器都会运行一次检测环的算法，即每次都会消耗o 的c p u 时间。对于整个文 件系统来说，收集器对环的维护工作需要消耗的c p u 时间是。吖) ，当用户运 行大型软件时，对文件的频繁操作可能会使用户感到系统性能的明显下降。下面， 我们探讨一些可能用来作为p a s s 系统收集器的收集算法。 3 2 可能的算法与分析 3 2 1 时间局部性算法 s o u l e s 和g a n g e r 2 1 】开发了一个叫c o n n e c t i o n s 的系统，c o n n e c t i o n s 系统采用 时间局部性( t e m p o r a ll o c a l i t y ) 来获取数据的起源信息：每当写入一个新文件，最 近被读的文件都成为这个新文件的前驱者。采用时间局部性可以获得大部分正确 的文件关系，可是有时候也会获得错误的信息。例如，一个用户正在听音乐，同 时他又在使用w o r d 处理软件写文档，显然，这个音乐文件和用户正在处理的w o r d 文档之间没有什么关系【2 2 】。 局部性算法维护一个滑动窗口，系统在前t 秒内进程存取的文件在这个滑动 窗口中记录。这个窗口中的任何写操作与这个窗口中记录的读操作相关联。如图 3 5 滑动窗口示意酣2 3 】所示，系统中发生的一系列事件。有三个进程a ，b ，c ，同 时运行。进程c 读文件u 和v ，进程a 读文件x 和y ，进程b 读w 并通过一个 剪切板将数据拷贝到a 。最后进程a 写入文件z 。在文件z 被写入时，滑动窗口 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 记录了文件y ，w ，v 被读。局部性算法不区别某个读写操作是属于哪个进程的， 只要是一个用户下的进程，它们的读写操作都被统一对待。这样，算法将返回的 文件之间的关系 y - z ，w - z ，v - z 。 a 曰 c r e a f d 卜一r e a d i 。 以d r e l a t i o nw i n d o w 图3 5 滑动窗口示意图 滑动窗口希望尽可能正确地获取文件之间的关系。但是如果窗口太大，会将 一些无相关的文件关联起来，如果看窗口太小，会丢失一些文件之间的关系。 p a s s 的收集算法可以精确收集文件之间的关系，但是由于时间复杂度比较 复杂，因此当系统中同时运行的进程，打开的文件数量相对比较多时，对性能的 影响会比较大。算法的主要瓶颈主要出现在当系统中同时运行的进程，打开的文 件数量较多时，我们可以通过使用时间局部性这个特性来减少收集器维护图中的 对象个数，减少收集器维护图的负担。 在p a s s 系统中，除了维护内存中的对象关系图，还维护一个滑动窗口，系 统在前t 秒内进程存取的文件在这个滑动窗口中记录着，收集器只维护在滑动窗 口中的文件。每当在环中加入一个新的对象，收集器都需要遍历这个环，检查新 加入的对象是否会形成环，在遍历的同时，收集器将文件与滑动窗口中的文件比 较，如果该文件在滑动窗口中不存在，就把这个文件从图中移除。 采用时间局部性特性结合p a s s 收集算法可以控制在系统中同时出现的文件 数量，使p a s s 收集器在维护图的过程中不会因为图中的节点对象太多而消耗太 多的c p u 时间。但是，时间局部性还是存在一定的问题，那就是性能的不稳定。 假设某个时间段用户启动了很多进程，每个进程都打开很多文件。这时，即使是 采用时间局部性也不能控制图中的文件数量。而某个时段系统中只有很少的进 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 程，进程打开很少的文件，这时p a s s 收集器完全有可能记录所有文件之间的关 系，但采用时间局部性使系统在没有必要的时候丢失了部分对象之间的关系。 3 2 2 最大文件集合算法 在上面叙述的时间局部性算法中，由于系统中运行的进程和文件的数量不是 随时间均匀的，所以使用时间局部性算法不能保证p a s s 系统能收集尽可能多的 对象之间的关系。 我们引进最大文件集合算法来解决这个问题。最大文件集合算法，也就是设 定一个p a s s 系统允许同一时刻在内存中维护的文件对象数量，将打开的文件对 象放在一个集合中，集合中能够存放文件的数量大小有一个最大值，如果某个时 刻，p a s s 系统在内存的图中维护的文件对象数量超过集合的最大值时，p a s s 收集器在添加下一个文件时，就会将最长时间没有被操作的文件从图中去掉，保 证p a s s 维护的图中的对象数量不会超过一定数量，系统的性能不会因为系统中 的文件对象太多而严重下降【2 4 】。 在p a s s 系统中，除了维护内存中的对象关系图，还需要维护一个集合，集 合中记录这系统中的文件、文件个数和每个文件的活动情况，收集器只维护在集 合中的文件。每当要加入一个新的对象，需要先检查集合中的对象数量是否达到 集合限制的最大值。如果新对象的加入是集合的对象数量超过最大值，需要将那 个时刻，集合中最不活跃的文件对象清除集合，也就是将集合中最长时间没有被 操作的文件对象从集合中清除。然后由收集器遍历内存中的图，将被从集合中清 除的文件在图中去掉，在集合中添加新的文件对象，更新集合中文件的活动情况 数据，再在内存中的图中加入新的文件对象：检查新加入的对象是否会形成环， 如果新加入的文件对象形成环【2 卯，收集器调用n o d e - m e r g i n g 算法来消除环。 采用最大文件集合算法可以解决时间局部性算法的缺陷，它可以最大限度的 收集文件对象之间的关系。不过它也带来了一些性能上的损失，集合需要维护集 合中每个文件的活动情况，但一个文件被操作时，集合需要更新集合中相应文件 的活动值，当集合中的文件总数达到最大值时，收集器需要扫描集合中记录的文 件活动值，去掉活动值最小的，收集器再在图中搜索并在图中删除该文件。对文 件活动值的维护，集合中文件总数达到最大值时，对最小活动值文件的搜索，然 后是在图中删除文件。当系统中文件数量相当大时，每次加入新的文件对象都需 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 要执行上述操作一遍，可能会引起性能上的下降。 3 2 3 基于因果关系的算法 基于因果关系来记录文件之间的关系，我们将每个进程看成一个过滤器，输 入数据到进程，然后通过进程的处理在输出数据。因果算法监视数据输入流来创 建文件之间的关系，通过对进程的监视，确定输出文件和输入文件之间的关系。 当写操作被调用时，会形成下面的两种关系： ( 1 ) 在写文件操作之前，这个进程的读文件操作都成为这个被写文件的前驱 者。 ( 2 ) 监视进程问的数据传输和数据接收，如果文件系统有事件通过进程间的 通信传输文件数据，文件之间的关系也会被建立。 也就是说，对于每一个关系a - b ，在图中都存在一条从文件a 到文件b 的路 径，从被读的文件开始到被写的文件，这里没有采用滑动窗口，所以没有局部性 的限制，不会有关系因为局部性而丢失。 进程a 读文件x 和y ，生成文件z ；根据因果关系算法的条件( a ) ，会产生的关 系是： x z ) ， y 抛 ；进程b 没有输出文件，只是读了文件w ，但是它使用拷 贝、粘贴操作通过剪贴板将数据传递给进程a 。根据因果关系的条件( b ) 会产生 的关系是：w - z ；进程c 读文件u ，v ，但是他没有影响文件z ，也没有产生任 何数据，所以，进程c 和文件u ，v 被忽略。 基于因果关系的算法比时间局部性算法产生更少的文件关系，避免了很多伪 关系。使用时间局部性算法，不相关的进程如果同时运行，他们的文件操作很可 能将不相关的文件关联起来，而基于因果关系的算法产生的关系要精确许多。当 一个用户在不相关的任务之间切换时，在时间局部性算法下产生的伪关系也会在 因果关系算法中消失【2 6 】。 一个用户一边编辑他的e x c e l 文档一边听着音乐，如果采用时间局部性算法 来记录文件之间的关系，用户会发现他编辑的e x c e l 文件和音乐文件关联起来了， 采用因果关系的算法则不会出现这样的问题。这些任务是不同的进程，并且他们 没有数据共享。使用时间局部性算法的情况下，假设他切换到他的电子邮件，并 添加一个附件，如果e x c e l 和附件都在滑动窗口中，他的e x c e l 文档可能会成为 附件的前驱者。 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 长时间运行的进程会带来一些麻烦。用户用文档处理程序打开一个文档，编 写了一个下午，然后将文档保存为新的文件名。在时间局部性算法下，以新文件 名命名的文件可能会丢失以前的关系，而因果关系的算法还会保持文件以前的关 系。用户用文档处理程序编辑几个没有关系的文档，如果都是同一个进程在编辑 文档，在因果关系算法下，可能会将这几个没有关系文件关联起来，而在时间局 部性算法下可能不会发生。当数据是通过隐藏的方式传输时，因果关系算法会丢 失真正的上下文关系。例如当用户联系他的记忆力时，将表格里的数据记下来， 然后手动输入到w o r d 文档中，w o r d 文档和表格的关系丢失。 3 3 基于进程粒度上的收集算法 3 3 1 算法描述 p a s s 模型的收集器的采用的自动收集算法可以很精确的收集文件和进程、 文件和文件之间的关系f 2 7 1 。在内存中，p a s s 维护一张图，图中包括了文件与文 件，文件与进程之间的关系，图是采用单向链表的数据结构。在图中，在每加入 一个对象时，收集器都需要检测单向链表中是否有环，这需要o ( n ) 的时间复杂 度，在前面我们叙述过，这o ( n ) 的复杂度对整个系统而言，实际上是o ( n 2 ) 的时 间复杂度，如果存在环，收集器还需要采用n o d e - m e r g i n g 算法来消除图中的环。 p a s s 中的收集器在内存中为文件和进程之间的关系维护着一张图，如果系统中 运行的进程比较多，进程之间读写文件的关系比较复杂的话，这张图可能会很大， 很复杂，很难维护。 采用基于进程粒度上算法来改进p a s s 的收集算法，现在我们对每一个进程 进行跟踪，为每个进程维护两个文件集合，一个集合是被读文件的集合，一个集 合是被写文件的集合，当有文件被写时，我们将被读文件的集合中的文件记录为 被写文件的前驱者。如图3 6 是基于进程粒度上算法来改进p a s s 的收集算法： 浙江大学硕士学位论文第3 章p a s s 自动收集算法的改进 图3 6 基于进程粒度上算法来改进p a s s 的收集算法 进程c 读取文件，a ，b ，c ，写入文件d ，我们得到读取集合 b ，c ) ，和集 合 d ) 。当写入操作产生时，我们产生关系c ：a - d ，c ：b d ，c ：c , - d ，最后我们将 这些关系写入文件d 的起源信息中。这个关系清除的表现了文件与进程之间、文 件与文件之间的关系，即：进程c 读文件a ，b ，c 通过计算，产生了文件d 。而 原p a s s 系统产生的关系将是如b ，c c - d 。通过比较一下原p a s s 系统产生 的关系结果，我们发现，基于进程粒度上的算法产生的关系和原p a s s 系统下产 生的关系是一样的，虽然表现方式不一样，但是从其中我们都可以知道文件d 是进程c 在文件a ，b ，c 中读取数据，经过计算得到的【2 8 】。 3 3 2 算法性能分析 基于进程粒度的收集算法在功能上能够完整收集文件与文件，文件与进程之 间的关系，系统在内存中不需要采用复杂的数据结构，只要有两个集合和进程关 联，就可以跟踪记录对象之间的关系。所以系统的复杂度大幅减小，系统的性能 大幅提高。原p a s s 收集算法是将所有进程，所有文件之间的关系建立成一个图， 图采用单向链表的数据结构。这种方式不但增加了系统的复杂度，使系统在运行 中容易出错、调试困难，在系统运行时的效率也很低。由于系统在每次向图中加 入新对象时都要检测新对象的加入是否会产生环，在有环的情况下需要调用消除 环的方法来消除环，这使得用户在每次文件操作的时候都将带来性能上的损失。 如果在用户启动的进程比较多，对文件的操作比较频繁，性能下降可能会使用户 不能接受。 采用基于进程粒度的收集算法。在每次读文件对像时，只需要将该文件对象 加入对应进程的被读文件集合，每次的写操作时，只需要将文件对象加入对应进 程的被写文件集合，然后将进程的被读集合中的文件作为被写文件的前驱者。容 浙江大学硕士学位论文 第3 章p a s s