求算法:多线程任务均匀分配问题

C++语言 码拜 4年前 (2017-04-15) 857次浏览
程序设计大致是这样: 开了5个线程,每个线程持有一个数据队列指针 pQueue, 线程处理函数不断的从本人的队列中取数据包处理,
数据包的格式大致是这样:

id;
dataBuffer;

线程函数将处理之后的数据包转存到一组以id为单位的数据对象中。
那么问题来了:
为了避免在处理数据包时线程之间的同步问题, id相同的数据包需要分配到同一个线程的数据队列中。
求这样一个hash函数 :
在保证 id 相同的数据包被插入到同一个线程的pQueue的前提下,尽可能的让收到的数据包在5个线程之间均匀分配。
求各位老湿的指点。
解决方案

30

id是怎么样分配/分布的。

10

去搜 scheduling problem approximation algorithm 吧,这是P time 内无最优解问题

10

开第六个线程,由它调度分配数据包。
数据包分二种情况:
1已经有相同的id被分配,则全部的包都分给原线程
2若还没有相同的id在处理,则找一个最空闲的线程分配包。
用map保存已经加入的id.

10

对于一个新ID, 追加的ID 列表,并返回pos
对于已知id, 返回pos
pos % 5 就可以知道要分配的线程号(0, 1, 2, 3, 4)
id列表更新于查找由调度线程完成,在你的packet中加入一个字段 assigned thread id(0, 1, 2,3, 4)

10

或改成消息传递 /流水线:
把整个流程分成5个子任务: A -> B -> C -> D -> E, 分别有5个线程执行。
这样5个线程的工作量大体平均。在任务较少的时候, 线程之间唤醒开销稍大, 延时会比较高, 一般问题不大。但是在任务爆发的时候, 全部线程都在干活,充分利用计算资源。

10

不要低估操作系统线程调度算法的智商。

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求算法:多线程任务均匀分配问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)