如何计算多线程进程的总计算时间

Question

我有一组任务，我们称之为T[]，其中每个任务都T[i]需要一定的时间t(T[i])来处理。任务由线程并行处理X（这并不意味着多个线程在单个任务上协同工作，而是多个线程正在处理多个任务，每个线程执行一个任务，然后执行下一个任务，依此类推） 。

现在我想计算处理所有任务所需的预期总时间。size(T[]) <= X当然只要任务数小于或等于线程数就很容易，在这种情况下总时间等于最慢任务的时间。

但我对这种情况很迷茫X < size(T[])（即我的线程比任务少）。如何以一种优雅的方式计算它？

编辑：正如评论员所问，我们可以假设任务队列按运行时间最长的任务排在前面，运行时间最短的任务排在最后。此外，我们可以假设任务之间没有暂停，我们也可以忽略操作系统调度程序正在做什么。

Answer 1

我假设任务按照提供的顺序进行安排，并且每个任务都转到第一个空闲的线程。如果这些假设正确，则不存在有意义的非确定性——任务可能会转到任何空闲线程（如果有多个线程），但这对总运行时间没有影响。

在这种情况下，我们可以使用大小为 X 的最小堆（其中 X 是线程数）来模拟这一点，堆中的值表示其中一个线程的空闲时间。对于每个任务，我们从堆中弹出最早的空闲线程，然后在完成新任务的时间将其推回。

当我们安排完所有任务后，我们可以取堆中的最大值，这将是所有任务完成的时间。

这是 Python 中相对较少的代码：

import heapq

def compute_time(tasks, X):
    threads = [0] * X
    for t in tasks:
        heapq.heappush(threads, heapq.heappop(threads) + t)
    return max(threads)

print compute_time([3, 2, 1], 2)
print compute_time([5, 4, 3, 3, 2, 1, 1], 3)

或者用Java：

import java.util.*;

class Threads {
    public static void main(String args[]) {
        int totalTime1 = computeTotalTime(Arrays.asList(3, 2, 1), 2);
        System.out.println("totalTime1: " + totalTime1);

        int totalTime2 = computeTotalTime(Arrays.asList(5, 4, 3, 3, 2, 1, 1), 3);
        System.out.println("totalTime2: " + totalTime2);
    }

    static int computeTotalTime(List<Integer> task, int threads) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        for (int i = 0; i < threads; i++) q.add(0);
        for (int t : task) q.add(q.poll() + t);
        int max = 0;
        while(!q.isEmpty()) max = q.poll();
        return max;
    }
}