running time of two programs run separately and then together

Question

I was recently asked this question in an interview, and while I did alright on the first two parts [I am assuming] I struggled a bit on the third. Here's the question:

You have two Linux programs, A and B. When run separately, A and B each take one minute to complete on a system that has just been restarted. [ie: fresh system: you reboot it, log in, get a shell prompt, run the program.]

What can you tell me about the programs if:

a) when run together, they take 2 minutes b) when run together, they take 1 minute c) when run together, they take 30 seconds

I said for a) that if they take exactly double the time when run together, they share no mutual exclusion and are vying for all the same resources, probably don't share any sort of cache data or instructions [and thus don't help each other out from a cache perspective] and each program needs the full utilization of said resource to complete such that the OS cannot parallelize them.

For b), I said that if they can run just as fast together, they probably share some spacial/temporal locality in the cash, and may lend themselves to being properly pipelined in such a way that while program A is waiting on something, program B can run in between those stages, and vice versa-- effectively running them both in 1 minute.

For c), I was a bit stuck. In retrospect, I probably should have said that perhaps program A and B were both doing a common task, where two of them running at once could complete said task faster than one running alone-- such as a garbage collector. But the best that I could come up with was that perhaps they loaded out of the same sector on the hard disk, and that helped them both together run quickly.

I am just looking for some input from some of the smarties here on things I probably missed. The position was for a platforms/systems position that require a good understanding of hardware/software and operating systems, and namely interactions between them which is why [I'm assuming] the question was asked.

I was also trying to think of examples that I could apply to each part to help show my knowledge of the questions real life applications, but on the spot I was coming up short.

Answer 1

Together they take 2 minutes to complete

In this case, I think that each program is fully CPU-bound and can saturate 100% of the CPUs available on the machine. Therefore when the programs run together, each runs at half speed.

It's also possible that this would be the observed behavior if both programs were able and willing to saturate some other resource apart from the CPU, for example some I/O device. However, since in practice, usually the performance of I/O devices does not decrease linearly with the load applied to them if they are oversaturated, I would consider that a less likely scenario and go with CPU-bound as a first guess.

Together they take 1 minute to complete

The two programs do not contest the same resources, or there are ample resources in the system to satisfy the demands of both. Therefore, they end up not interfering with each other.

Together they take half a minute to complete

The programs operate on the same input, and both can tell when all input is used up, so each ends up doing half the work it would do if launched alone at half the running time. Also, the system obviously has the capacity to supply double the amount of whatever resource these programs are constrained by.

Since in this case the running time decreases linearly with the amount of processes (perfect scaling), it seems more likely that the resource constraining the programs is CPU for the same reasons explained in the "2 minutes" scenario. This also fits in well with the "common input" assumption, as the input would not be very likely to be coming from one source if there were e.g. different I/O devices supplying it.

Therefore, the first guess in this case is that each program is CPU-bound and written such that it consumes at most half the CPU resources in the system.

Answer 2

For A, They're programs that are in competition for a mutually exclusive resource.

For B, They're independent programs that don't really interact.

For C, which is the one you're struggling with, it seems they both have the same work to pick from. For example, there's a queue of tasks to do, both programs are capable of doing the tasks, and they know what tasks have been done. So if they both run at the same time (assuming multi core machine, but even then not necessarily, all that's important is that they don't have a resource bottleneck) they get the work done in half the time.