分别运行两个程序和同时运行两个程序的运行时间

29

我最近在面试中被问到了这个问题,对于前两部分我做得还不错,但是对于第三部分有些困难。以下是问题:

你有两个Linux程序A和B。当单独运行A和B时,在刚重启的系统上每个程序都需要一分钟才能完成。(例如:新系统:重新启动它,登录,获取shell提示符,运行程序)

如果:

a) 当它们同时运行时,需要2分钟 b) 当它们同时运行时,需要1分钟 c) 当它们同时运行时,需要30秒

针对a),如果它们同时运行时需要完全的两倍时间,那么可以推断出它们没有共享任何互斥资源,可能不共享任何高速缓存数据或指令(因此从缓存角度来看对彼此没有帮助),每个程序需要利用全部资源来完成任务,以致操作系统无法并行处理。

针对b),如果它们能够一起快速运行,那么它们可能共享某些空间或时间局部性,并且可能适合以正确的流水线方式操作,即当程序A等待某些操作时,程序B可以在这些阶段之间运行,反之亦然 - 有效地在1分钟内运行它们两个。

针对c),我有些困惑。回顾起来,我可能应该说,程序A和B都在执行共同的任务,两个程序同时运行可以比单独运行更快地完成该任务 - 例如垃圾收集器。但是我能想到的最好答案是:它们也许从硬盘上的相同扇区加载,这帮助它们一起快速运行。

我只是想听听这里一些聪明人提供的意见,该职位需要对硬件/软件和操作系统有很好的理解,以及它们之间的交互,这就是为什么(我认为)这个问题被问到的原因。

我也试图想出一些例子,以便应用到每个部分上,来展示我对问题实际应用的知识,但是当场我无法想出。

3个回答

20

两个程序一起运行需要2分钟才能完成

在这种情况下,我认为每个程序都是完全依赖于CPU的,可以占用机器上可用的100%的CPU。因此,当这些程序同时运行时,每个程序的速度会减慢一半。

也有可能,如果两个程序都可以并且愿意占用除CPU之外的其他资源(例如某个I/O设备),那么观察到的行为就是这样的。但是,由于“实际上通常情况下”I/O设备的性能不会随着所施加的负载线性降低,如果它们被超负荷使用,所以我认为这种情况不太可能发生,并且先考虑CPU-bound。

两个程序一起运行需要1分钟才能完成

这两个程序没有争夺相同的资源,或者系统中有充足的资源来满足两者的需求。因此,它们最终不会互相干扰。

两个程序一起运行需要半分钟才能完成

这两个程序对同一输入进行操作,并且两者都可以判断何时使用完所有的输入,因此每个程序最终会完成其单独运行时间一半的工作量。此外,该系统显然能够提供所需资源的两倍。

由于在这种情况下,运行时间随进程数量线性降低(完美扩展),因此更有可能的是CPU-bound,理由与“2分钟”情况中所述相同。这也很好地符合“共同输入”的假设,因为如果有不同的I/O设备提供输入,则不太可能来自同一源。

因此,在这种情况下的第一个猜测是每个程序都是CPU-bound,并且编写得可以最多占用系统中一半的CPU资源。


1
+1 虽然我们的回答大部分相似,但你对B部分的解析比我的更好。 - corsiKa
我试图想一个例子来说明(c)中它们不会显式地互操作。我能想到的最好的例子是,它们都对某个东西(网页、磁盘上的文件、内存块)进行了不同的工作,如果它们都请求该东西,则可以将其缓存。 - Jack V.
@JackV:任何具有两个消费者的生产者/消费者安排都符合(c)的描述。但是工作也可以事先分配(例如,使用分而治之对大文件进行排序,然后合并结果)。 - Jon

13

对于A,它们是竞争一项互斥资源的程序。

对于B,它们是不互动的独立程序。

对于C,这是你正在努力解决的问题,似乎它们都可以从同样的工作中进行选择。例如,有一个任务队列需要完成,两个程序都有能力执行任务,并且它们知道已经完成了哪些任务。因此,如果它们同时运行(假设使用多核机器,但即使没有也不一定要求,重要的是它们没有资源瓶颈),它们可以在一半的时间内完成工作。


0

查看多线程Java应用程序中的性能,了解为什么当您拥有多个进程时,进程可以运行得更快的另一个可能原因。

尽管我承认可以并发执行的任务队列是解释这种缩短运行时间的一个简单得多的原因。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接