一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1252|回复: 5
收起左侧

[编程题] 求问一道关于多线程queue的面试题

[复制链接] |试试Instant~ |关注本帖
Ulu2005 发表于 2015-3-18 04:01:40 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 Ulu2005 于 2015-3-18 07:03 编辑

设计一个task dispatching system,里面有一个task queue和两个function。并且这个queue的所有operation是atomic的。
1. trigger() 这个function运行并清空task queue中所有的tasks。
2. addTask(task) 在trigger之前把task加入task queue,在trigger之后直接运行task。

在mitbbs有一个被说不是最优解的解法,使用了一个全局布尔变量来判断queue是否已经被trigger。
  1. trigger(){
  2.   aquire(mutex_a);   
  3.   a = true;      
  4.   dispatch all tasks in the queue;
  5.   head = null;
  6.   tail = null;
  7.   release(mutex_a);
  8. }
复制代码
  1. addtask(){
  2.      aquire(mutex_a);
  3.      if(a)
  4.           dispatch the task;
  5.      else{
  6.           if(head == null){
  7.                head = task;
  8.                tail = task;
  9.           } else{
  10.                tail.next = task;
  11.                tail = task;
  12.           }
  13.      }
  14.      release(mutex_a);
  15. }
复制代码
我个人觉得queue是否被trigger的区别在于这个queue是否为空,因为queue被trigger后整个queue就空了,没有必要去增加一个全局变量。而且addTask()和trigger()应该是不冲突的,trigger()总是取queue最前面的一个task来run,而新的task总被加到queue的末尾,上面这样加锁system性能会很差。
  1. trigger() {
  2.     while(!queue.isEmpty()) {
  3.         lock(&m);
  4.         get & remove task from queue;
  5.         run task;
  6.         unlock(&m);
  7.     }
  8. }

  9. addTask(task) {
  10.     if (queue.isEmpty()) {
  11.         lock(&m);
  12.         run task;
  13.         unlock(&m);
  14.     } else {
  15.         queue.add(task);
  16.     }
  17. }
复制代码
以上是我的写法,这样加锁可以使queue不为空时,能够同时trigger和addTask。而且可以保证queue里的最后一个task被取出来后,总是能够在addTask(task)的task之前运行。
但是这样写有个bug就是当queue为空,多个addTask(task)被call,task永远没有办法被add进queue,会处于顺序执行状态。持有锁的那个addTask会run task。这样queue就失去了存在的意义。不知道我的写法应该怎么改进,求指导。


Urumic 发表于 2016-6-9 13:49:56 | 显示全部楼层
请问这是一个环形的queue吗。为什么head = task; tail = task;
回复 支持 反对

使用道具 举报

lea82 发表于 2016-6-10 07:56:19 | 显示全部楼层

void register(Callback cb) {
  m.acquire();. 涓
回复 支持 反对

使用道具 举报

Yuao_Liu 发表于 2016-7-22 06:51:59 | 显示全部楼层
感觉还是要加全局变量的, 因为在最开始的时候,queue为空,trigger也没被调用,这个时候仅仅是用queue是否为空来判断就不是很好了。
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-8-8 04:47:23 | 显示全部楼层
mitbbs那个解法是默认trigger仅发生一次的,可是task dispatch system逻辑上应该是个循环吧,应该还有reset操作的
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-8-8 05:17:34 | 显示全部楼层
有两个问题需要clearify下,
1.是否要实现多次trigger,如果只一次那mitbbs那个答案应该是没问题
2.我的理解应该是多次call,本质上就是生产者消费者模型,那么多个addtask的情况是否需要保证公平性?不需要的话,阻赛队列即可;需要的话需要自己加可重入锁
欢迎讨论~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表