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

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;
    }
}