月度归档:2013年03月

给维基百科的捐款

昨天在看到了维基百科的捐款呼吁后,给维基百科捐助了 10 美元,这是我第一次以现金的形式给任何网站捐款。

通过 paypal 给维基百科捐款10美元

 

往年也看到过这样的呼吁,但身为学生,实在囊中羞涩。

维基百科给我带来的价值,远非金钱能够衡量。经常一不小心在 wikipedia 上流连忘返,一下午时光就过去了。维基百科上面条目的严谨性,绝非国内互联网几家“百科”网站所能比。你可以在维基百科上系统的学习新知识,比如中文维基上的历史主题,读完就可以对中国历史有个清晰的脉络了。维基百科绝对是互联网上最伟大的项目之一。

对我影响最大的网站有三个,分别是:google, google reader, wikipedia. google 搜索给 Google 公司带来的巨大的利润,当然不用担心钱的问题。google reader 不能够盈利,加上其他一些原因,被 Google 公司判了死刑。在 google reader 被宣布即将关闭的那天,我几乎不敢相信这是真的,从三年前就开始使用 reader, 订阅了数百个源,几乎每天都至少花上一个小时的时间去阅读。wikipediia 是一个非营利组织,我实在不希望它因钱的问题困扰。

无锁队列

去年在做一个项目时,遇到一个问题:需要处理一些数据,其输入速度是一定的,但输入的数据中只有一部分是实际需要处理,具体比例不一定,但希望能够保证实际处理数据的速度是一定的。所以,在这里用到了队列。首先对数据进行预处理,判断是否需要进行实际处理,如果需要则放入队列。同时还以一定的速率从队列取数据进行处理。这些操作都是在一个进程中,所以用 C 写了一个很简单的队列实现:基于共享内存,保证进程重启队列数据不会丢失;支持当队列满时自动 dump 到文件,使用文件作为存储。

最近又有一个这样的需求:一个进程产生数据放入队列,另一个进程判断队列长度,如果大于某一个值则进行处理,典型的“生产者 – 消费者”模型。这里就要求队列支持多进程,直接把之前写的队列拿来用会有问题,因为读和写队列可能同时进行,当两个进程同时修改某一个计数器时就可能会导致数据不一致。这里简单对队列进行加锁,即读和写是互斥的,就很容易的解决了这个问题。但在高并发时,读写互斥会带来性能上降低。之前公司内部看到有人分享过无锁队列的实现,研究了一下代码发现这个实现并不是真正的无锁队列,读写仍然是互斥的。

在参考了酷壳的文章:无锁队列的实现 之后,根据文章提供的思路,实现了一个无锁队列,它的要求是:

1、支持多进程(线程)同时对队列进行读写。

2、使用共享内存作为存储。

3、能够获取到当前队列的长度。

4 、兼容32位和64位系统

另外前题是:数据单元长度是固定的。

代码在此:https://github.com/haipome/lock_free_queue

大致的思路是:

在初始化时获取一大块内存自己分配,永不释放。将内存划分为控制区和数据区,数据区分成平均的数据块,每个数据块又有一个数据块头。通过数据块头,将队列中的数据组织成为链表。控制区里有两个“指针”分别指向链表的头和尾,这里并不能使用真正的指针,而是数据块的编号,使用 -1 标识链表的结束,为了解决队列在最开始时的初始化问题,所以这里多使用了一个编号为 -1 的数据块。另外,为了解决头尾指针指向同一数据块的问题,当 pop 时,读取的是头指针指向的数据块的下一个数据块,所以这里又多使用了一个数据块。

后记:多进程到处是坑,花了将近两天时间来 DEBUG

参考:

Legacy __sync Built-in Functions for Atomic Memory Access