Calculating execution time for 2-threaded CPUs?

Question

Given 3 programs P0, P1, P2 and two CPUs and each CPU having 2 threads. The running times of the programs take 5, 10 and 20 msecs respectively. How long will it take to execute all 3 programs? Assuming they do not change CPUs and do not block during execution.

My answer is 20 msecs because no matter how we organize the programs on the CPUs they will be completed as fast as the slowest program(P2), therefore 20 msecs. However, the solutions manual gives answers 20, 25 and 30. Can anyone tell me how that answer came to be?

It says

If P0 and P2 are scheduled on same CPU and P1 is scheduled on the other CPU it will take 25 msecs

the question is why though, shouldn't the first CPU take P2 time (20 msecs) and second one P1 and given than P2 takes longer and both CPUs run concurrently shouldn't the answer be 20 msecs as well?

Answer 1

p0 - 5  ms
p1 - 10 ms
p2 - 20 ms

Scenario 1:

| P0  |             |    |
| P1  |             | p2 |  
\_____/             \____/
 CPU0                CPU1

It will take CPU0 15ms to finish both jobs, while CPU1 will run 20ms before p2 is done, they run in parallel, so both jobs will be done in 20ms.

---

Scenario 2:

| P2  |             |    |
| P0  |             | p1 |  
\_____/             \____/
 CPU0                CPU1

It will take CPU0 25ms to finish both jobs, while CPU1 will run 10ms They run in parallel, while CPU1 will go idle after 10ms, it will take CPU0 an extra 15ms to finish. Thus, 25ms.

---

Scenario 3:

| P2  |             |    |
| P1  |             | p0 |  
\_____/             \____/
 CPU0                CPU1

It will take CPU0 30ms to finish both jobs, while CPU1 will run 5ms Again, they run in parallel, so while CPU1 will go idle after 5ms, it will take CPU0 an extra 25ms to finish. Thus, 30ms.

---

Pay attention, jobs remain on the same CPU they were scheduled to run on according to your question. If one job needs 20 ms to run and the other one needs 10 ms to run, it will take 30 ms to finish them both. If your jobs can run on different cores of same CPU then it will be 20 ms anyway (that is the best case), but that is not a granted to be the situation.