项目总结 (1)

归档: 软件开发 | 标签:

年前开始做这个项目,虽然主要的功能放假前已经完成,但是老板为了体现实验室的主题——并行计算,要求把一个简单的 hash 查找功能弄成复杂的“多线程并行计算”,尽管最后的多线程实现比串行的还慢(通过使用 gprof 分析发现花在同步上的开销超过了多线程带来的并行效益,因为实际的 hash 查找不怎么耗时间)。当然这些我是无力改变的,不过有个好处就是老板虽然不懂具体技术,但是却不会瞎指挥,所以在实现上倒是挺自由的,因此可以随便尝试自己想学的东西,只要最后项目完成就行。

好了,发完牢骚之后总结一下从中学到的东西吧。

生产者-消费者问题

我觉得所有的问题基本都可以归结为生产者-消费者问题:输入是生产者,程序处理是消费者。刚开始写的是串行的代码,使用惯用的套路:

int main(void)
{
    ......

    while ((rec = producer()))
        consumer(rec);

    ......
}

串行程序需要由 main() 函数驱动,主要逻辑由 main() 函数搭建,这样的话如果非要把多线程嵌到这个模型中,看起来会有点奇怪:

void* producer(void)
{
    /* blcok until data arrives */
    return get_resource_from(resource_pool);
}

void consumer(void* rec)
{
    /* assign rec to an idle thread */
}

因此可以在 main() 中只负责创建线程,然后阻塞直到所有线程都退出:

int main(void)
{
    create_threads();
    wait_for_thread_to_exit();

    return 0;
}

void producer(void)
{
    consumer(get_resource_from(resource_pool));
}

void consumer(void* rec)
{
    /* assign rec to an idle thread */
}

这样就不需要经过 main() 函数的调度,而完全由输入来驱动程序的运行了。而且把输入输出和程序逻辑分开,保证只有一个入口和一个出口,以后改起来也方便。另外由于在 c 中内存泄漏和访问越界的普遍现象,习惯把内存分配也封装一下,譬如弄个函数:

inline void* mem_alloc(size_t size, const char* f, int l)
{
    return malloc(size);
}

ptr = mem_alloc(size, __FILE__, __LINE__);

在调试时倒是能减少不少麻烦。

最后我觉得在前期对程序多抽象几层过度设计怎么都不为过,否则后期有一堆 bug 没解决而甲方又一天改 n 遍需求的时候你会有种想捅死他然后自己撞死的冲动。

平均分配

程序逻辑很简单,就是在一个 hash 表中根据一定的规则判断进来的数据是否符合要求,在把数据添加到 hash 表中的同时还要把过期的数据删除。假设 hash 表有 m 个 slot,有 n 个线程在工作,我想到的分配数据的方法有两个:一个是从线程的角度来分,另一个是从 hash 表的角度来分。

先说从线程角度。采用“人人有份”的原则,即把收到的数据分配给线程 pid = (pid + 1) % nr_threads。不过这个方法需要对 hash 的每个 slot 都加一个读写锁,因为可能同时有多个线程对同一个 slot 操作,好处是能够保证每个线程都处于忙碌状态,坏处是除了在 io 入口必须的锁之外每次访问 hash 表都要对 slot 加锁,对于只读操作比较多的情况不太划算。

另一个方法是每个线程负责一部分 slot,准确点说,就是算出收到的数据应该放到哪个 slot 后,把数据分给线程 pid = slot % nr_threads。这样的好处是线程间不会发生冲突,因此 hash 表不需加锁;坏处是虽然整个 hash 表是均匀分布的,但是数据有可能集中到某个线程负责的 slot 中,从而造成一个线程负载过多而另外的线程空闲的情况。

最后考虑到锁的开销占程序时间的比例还是采用了第二种方法。

Qt

真正开始接触 qt 是在去年的一个项目中,主要是因为需要做界面,而正好实验室另一个师兄会 qt,于是就开始了 qt 的旅程。

不得不说 qt 的 signal/slot 方法真的很方便,很容易将逻辑处理和界面改变分开。如果后台在进行大量运算的时候界面可能会没反应,所以界面中的逻辑最好单独一个线程,主线程负责界面元素的改变,两者间通过信号来控制对方,这可能需要对 qt 提供的 slot 进行一下封装。只是 signal/slot 漫天飞,对于我这种不习惯交互编程的人要查起来就比较烦了。而且目前 qt 并没对 connect() 的参数进行编译期检查,我就经常写错参数,导致运行的时候崩溃了才发现是什么原因。qt 有 vs 的插件,还提供了单独的 sdk 和 qtcreator(可以模拟简单的 vi 操作),用起来也挺爽。不过画界面却总是些体力活,还老改来改去的烦死人。

发表于 2012年3月3日
  1. hengyunabc
    2012年3月12日 00:26 | #1

    线程安全的HashMap可以参考java的ConcurrentHashMap的实现。
    里面用到了二级hash,cow实现。

    • ou
      2012年3月12日 08:05 | #2

      对于多线程的认识我还只停留在理论上,并不清楚怎样应用到各种数据结构中……谢谢建议。

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>