title: running time of two programs run separately and then together
body: <p>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:</p>
  
  <p>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.]</p>
  
  <p>What can you tell me about the programs if:</p>
  
  <p>a) when run together, they take 2 minutes
  b) when run together, they take 1 minute
  c) when run together, they take 30 seconds</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>