求一个既有并行,又有顺序的调度算法

图片说明

如上UML活动图左图,作业既有并行执行,又有顺序执行。
比如:
1->3->5 和2->4这两段任务可以并行执行,6必须在4,5都完成之后开始做。
1->3->5 2->4 两段任务的绝对顺序不变,但两个表可以任意归并,因为他们是并行。

输入3(做完),返回5。
输入5,系统检查4,做完则返回6,否则返回0。
请问有什么经典的调度算法吗?

  • 这不需要什么特定的算法的啊。线程+等待就可以解决了。
  • 1.主线程先开三个线程、线程1执行135,线程2执行24,线程3执行7
  • 2.主线程等待1,2全部完成,然后开第4个线程执行6,
  • 3.主线程等待3,4线程全部完成

如果需要最优的调度,可以采用贪心算法,具体可参考

http://blog.sina.com.cn/s/blog_5b355d6e0100d6v9.html