Friday, August 12, 2016

task dispatching system



http://www.1point3acres.com/bbs/thread-124049-1-1.html
设计一个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就失去了存在的意义。不知道我的写法应该怎么改进,求指导。

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts