工作线程
编程threads的时候,最基本的原则是从线程本地(thread-local)状态中分离出共享状态.共享状态需要同步,本地状态不需要.这也是为什么我放弃了OO的active object设计模式——java Thread对象是其中值得一提的典型实现. active object因为将共享状态和本地状态混合而臭名昭著.因为dispatcher是在我领悟到这一点之前写的,所以它使用了我们的active object库.不能再犯这个错误了!
下面是整个程序怎么工作的:main thread产生一个worker thread,传递给它一个函数和一些数据.新创建的worker thread向函数传递数据并执行.能够传递给worker thread的数据的类型是有限的,一共就下面几种:
1. Value.数据被先复制再传递.简单的例子:integer, 内容为值类型的vector等.重要的是这个数据不是共享的——每个thread工作在他们自己复制来的数据上.准确的说,线程安全的值(thread-safe values)可以安全的包含指向共享的monitor的(浅)指针或者是不变对象.举例: ScriptTicket.
2. Monitors. monitor对象是共享的,它们包含锁来同步它们所有的公共方法.(java和D中,这些方法使用关键字synchronized)举例:下面要讲到的WorkQueue.同时,消息队列一般也是monitor.
3. Immutable对象.它们不需要同步就可以共享,因为没有人可以修改它们.举例: ThreadInfo.
4. Unique(独一无二的)数据,如使用C++ auto_ptr的对象.一个Unique对象保证在同一时刻只能有一个线程能看到它.这个对象的原来的所有者发送这个对象到别处的时候自动丢失对象的访问权.所以Unique对象也不需要同步.
完了!绝大多数的并发问题可以用这写模式(高效的)解决.一些语言,如Erlang,被限制为纯value范围内(内部使用不变性来优化.译者注:Erlang语言所有的元素都是不变的).这种限制的缺点就是在本地处理的时候性能较差(比如Erlang process使用普通线程的时候.译者注:Erlang process是Erlang的执行单元,内部不是使用os的线程实现,可能是使用co-routine或者windows fiber等技术实现的,性能很高.Erlang大量使用值类型的数据,作者假设如果Erlang使用线程来实现process那么性能就会因为值类型的来回传递而变的很差.但是以现在Erlang的实现来说,这样大量的数据传递性能也是比较好的).
回到dispatcher: main thread产生worker thread,附带2个对象:
+ WorkQueue,一个monitor和
+ TransportManager,一个unique对象,主线程将它传递给worker thread之后,它就变成了worker thread的本地对象.
WorkQueue包含了共享数据,这些数据由锁来保护. TransportManager包含的数据都是worker thread的本地数据,所以不需要同步.在重写之前,这些数据都被组合到一个active object里面,从而必须非常小心以防止附带发生的共享.当前的设计中, WorkQueue没有访问TransportManager,所以main thread不可能偶然的碰到worker thread不共享的数据.你无法想象这个分离是怎么简化了线程间交互的论证和编码.
图表 2 WorkQueue在线程间共享, TransportManager是worker thread私有的
Worker thread function对这2个对象都访问.在它的空闲状态,它被阻塞等待main thread发来的消息.消息队列是WorkQueue对象的一部分.当消息到来的时候,worker thread醒来, 从WorkQueue检索出它需要的数据并调用TransportManager里面的方法.当它完成了任务,就回到空闲状态并等待下一个消息.
注意,图2 中,线程没有像active object模式那样关联对象,相反,当对象被共享的时候存在于线程之间,否则就在线程内.
消息传递方式
原则上,所有的线程间通信都可以用消息传递实现.我将解释怎样实现这个特殊的任务并考虑其他选择.
让我们从一个用例开始:100 scripts一个接一个的填入了dispatcher的文件夹里.在简单的方式下,每当main thread接到通知,它就列出文件夹的内容,从磁盘读取每个script文件的文件头,创建script滑动窗口并将它们传递到worker thread .最坏的情况下,会创建并发送5000个大的script tickets,其中4900都是重复的.这是因为每个文件 丢弃操作(file drop,大概就是删除文件之类的吧)都会创建一个单独的包含了完整文件夹列表的提醒(译者注:不要忘了作者写的这个文件是版本控制软件,想想我们的svn一个完整的检出).文件可能丢弃的很快,但是它们的处理时间也可能会任意长.
容易想到的第一种优化就是将这些tickets装进一个数组一起发送而不是每创建一个tickets就发送一次.如果这个数组可以被当做unique东西传递,就可以避免复制了(而且消息队列的锁也只需要对每个数组锁一次).最坏的情况下,时间会涉及100个这样的消息(的处理过程)(每次文件夹修改一个消息).
考虑到我们需要读取并解释5000个文件头,以及磁盘IO很昂贵,这样仍然很浪费.同时当前设计中,dispatcher的main thread执行了很廉价的本地copy到同一台机器的recipients.如果没有多余的检查,每个文件会平均在本地传输50次(这个平均值是幂等的(idempotent),但是也不是不要资源的).考虑到我们已经保存了已经被处理过的script的列表,这样的copy显然太多了,不需要一次又一次的处理它们的.
所以第2种优化就是在做任何昂贵的scripts操作之前先将文件夹进行raw directory list(将文件夹当成还没有版本控制的文件夹,递归列出所有的文件和子文件夹)并和正在处理的列表比较. 正在处理的列表由worker thread维护并放在TransportManager里面.main thread通过消息队列发送一个文件名的vector(同样,使用unique数组技术来避免复制),之后等待包含了修剪过的文件列表的返回消息.main thread之后再处理这个简短很多的列表.
控制翻转
让我来总结算法:
1. 列表整个文件夹
2. 比较这个列表和正在处理的scripts列表.将还没有在进程中的队列的那些保存起来.
3. 进行本地处理并且在本地copy剩下的scripts.
4. 将剩下的东西发送回WorkQueue,并将它们添加进正在处理的队列以进行远程copy.
如果我们使用同步的消息传递,将这个算法转化成串行代码相对容易,这种情况下,发送消息到WorkQueue之后,main thread会等待,收到确认消息之后才会继续执行.问题是worker thread可能会忙于工作,它可能要很久才能空闲下来检查新的消息.这个时间内main thread一直都阻塞从而整个程序失去响应.记住我们的目标是减少延迟!
异步消息传递可以工作的更好,但是它也有自己的问题.首先,漂亮的串行代码需要被划分成几个函数:
1. 文件夹提醒处理器枚举文件夹并发送一个包含了所有文件名的消息给worker thread.返回.
2. 在worker thread,这个消息的专门处理器比较这个列表和它自己的列表,并将裁减过的列表发给main thread.返回
3. 在main thread,返回列表消息的处理器进行本地处理,将剩下的列表发给worker thread.返回.
4. 在worker thread,这个消息的处理器将列表添加到正在处理是队列.返回.
注意这个序列算法只存在于程序员的头脑中(也许也在某些文档里面).仅仅看代码就想重新构造这个序列是非常困难的,因为它被分布在几个处理器中. 众所周知,这种reactive programming非常困难.而导致它更难的地方在于,发送了消息之后,这个调用的上下文就丢失了.返回的消息必须包含足够的信息来恢复这个上下文.有很多高级技术来克服这个问题:Closures, continuations, co-routines等等.但是它们大部分都限制在函数式语言里面而很难应用到OO模型上.
另一个重要的问题是很多语言缺少直接的消息传递支持,包括C++,Java, C#, D等.这些语言都是强类型的,因此限制不安全的转换(cast),程序员必须对每个消息类型创建一个单独的消息队列类型.这不仅是一个很烦恼的事,而且还带来了组合问题:一个线程可能想同时等待几种类型的消息.
考虑在这样的限制下,windows对类型安全检查进行了怎样的折衷.所有的windows消息都必须符合相同的模型: (message ID, WPARAM, and LPARAM).所有的类型信息都丢失了,需要程序员自己来恢复这些信息,当然了,通常的办法就是不作检查的类型转换(cast).
在函数语言里面,消息队列的组合(称作通道(channels)或邮箱(mailboxes))使用pattern matching技术来解决.简单的说,pattern matching就像一个switch语句,每个case就是一个类型.使用同一个语句你可以匹配一个字符串消息或者整数消息,最新的全功能语言,如Scala和F#都拥有对pattern matching的优秀支持.
共享有时候更简单
让我们重新考虑裁减列表的问题:main thread有一个候选者列表, worker thread有正在处理的列表.我们想从候选者列表中移除所有在正在处理的列表中出现的元素.在消息传递方式下,main thread必须发送候选者列表给worker thread并等待结果(在异步条件下,它会一边等待一边做别的事情).就算是worker thread根本没有使用正在处理的列表它也必须等待.worker thread没有办法对main thread说:”我现在正忙,你自己干嘛不做?”.
实际上,如果我们允许线程间共享,那么这个办法就有了.当然了,并发访问共享状态必须被保护,比如被锁保护.在我们现在的实现中, WorkQueue就是一个保护正在处理的列表的monitor. Main thread使用WorkQueue锁定并比较这2个列表.仅仅在worker thread已经获得了这个锁,访问正在处理的列表的时候它才必须等待.实际上,我们的正在处理的列表被分成2个列表:一个包含不变的ScriptInfo对象并且作为WorkQueue的一部分被共享,另一部分包含ScriptTickets并且作为TransportManager的一部分,自然这一部分不是共享的也就不需要锁了.
共享也有它自己的问题:竞争和死锁.如果你虔诚的用monitor保护所有共享的数据,竞争可以被避免;而如果你很少用锁(use locks sparingly),死锁也可以被避免. 你在程序中用monitor越多死锁的概率就越大.相反,用消息越多,数据的复制就越多,而且你的代码被分割的越厉害.
所以我想最好的办法还是明智的组合消息传递和共享.
下一节
综上所述,我描述了对dispatcher的初步的重写(的设计思路).在Reliable Software(译者注:作者的公司名),我们开始一个新特性的实现的时候,我们一般会重写该特性的周边的代码.我认识到这是一个在大多数软件公司都很不常见的实践,但是它为我们公司的产品创造了奇迹. Code Co-op项目经过了14年的持续开发,到现在仍然几乎没有“code rot”(腐烂的代码).这个产品没有哪一部分是”不要动它,否则它就坏了”的.
下一个实现步骤是将实际的复制分布到多个线程上.但是在新写的dispatcher之上构造它会很简单.一旦完成我就会在blog上分享.敬请期待
