Mysterious combination

Question

I decided to learn concurrency and wanted to find out in how many ways instructions from two different processes could overlap. The code for both processes is just a 10 iteration loop with 3 instructions performed in each iteration. I figured out the problem consisted of leaving X instructions fixed at a point and then fit the other X instructions from the other process between the spaces taking into account that they must be ordered (instruction 4 of process B must always come before instruction 20).

I wrote a program to count this number, looking at the results I found out that the solution is n Combination k, where k is the number of instructions executed throughout the whole loop of one process, so for 10 iterations it would be 30, and n is k*2 (2 processes). In other words, n number of objects with n/2 fixed and having to fit n/2 among the spaces without the latter n/2 losing their order.

Ok problem solved. No, not really. I have no idea why this is, I understand that the definition of a combination is, in how many ways can you take k elements from a group of n such that all the groups are different but the order in which you take the elements doesn't matter. In this case we have n elements and we are actually taking them all, because all the instructions are executed ( n C n).

If one explains it by saying that there are 2k blue (A) and red (B) objects in a bag and you take k objects from the bag, you are still only taking k instructions when 2k instructions are actually executed. Can you please shed some light into this?

Thanks in advance.

Answer 1

FWIW it can be viewed like this: you have a bag with k blue and k red balls. Balls of same color are indistinguishable (in analogy with the restriction that the order of instructions within the same process/thread is fixed - which is not true in modern processors btw, but let's keep it simple for now). How many different ways can you pull all the balls from the bag?

My combinatorial skills are quite rusty, but my first guess is

(2k!)
-----
2*k!

which, according to Wikipedia, indeed equals

(2k)
(k )

(sorry, I have no better idea how to show this).

For n processes, it can be generalized by having balls of n different color in the bag.

Update: Note that in the strict sense, this models only the situation when different processes are executed on a single processor, so all instructions from all processes must be ordered linearly on the processor level. In a multiprocessor environment, several instructions can be executed literally at the same time.

Answer 2

Péter's answer is fine enough, but that doesn't explain just why concurrency is difficult. That's because more and more often nowadays you've got multiple execution units available (be they cores, CPUs, nodes, computers, whatever). That in turn means that the possibilities for overlapping between instructions is increased still further; there's no guarantee that what happens can be modeled correctly with any conventional interleaving.

This is why it is important to think in terms of using semaphores/mutexes correctly, and why memory barriers matter. That's because all of these things end up turning the true nasty picture into something that is far easier to understand. But because mutexes reduce the number of possible executions, they are reducing the overall performance and potential efficiency. It's definitely tricky, and that in turn is why it is far better if you can work in terms of message passing between threads of activity that do not otherwise interact; it's easier to understand and having fewer synchronizations is better.

Answer 3

Generally, I agree with Péter's answer, but since it does not seem to have fully clicked for the OP, here's my shot at it (purely from a mathematical/combinatorial standpoint).

You have 2 sets of 30 (k) instructions that you're putting together, for a total of 60 (n) instructions. Since each set of 30 must be kept in order, we don't need to track which instruction within each set, just which set an instruction is from. So, we have 60 "slots" in which to place 30 instructions from one set (say, red) and 30 instructions from the other set (say, blue).

Let's start by placing the 30 red instructions into the 60 slots. There are (60 choose 30) = 60!/(30!30!) ways to do this (we're choosing which 30 slots of the 60 are filled by red instructions). Now, we still have the 30 blue instructions, but we only have 30 open slots left. There is (30 choose 30) = 30!/(30!0!) = 1 way to place the blue instructions in the remaining slots. So, in total, there are (60 choose 30) * (30 choose 30) = (60 choose 30) * 1 = (60 choose 30) ways to do it.

Now, let's suppose that instead of 2 sets of 30, you have 3 sets (red, green, blue) of k instructions. You have a total of 3k slots to fill. First, place the red ones: (3k choose k) = (3k)!/(k!(3k-k)!) = (3k)!/(k!(2k)!). Now, place the green ones into the remaining 2k slots: (2k choose k) = (2k)!/(k!k!). Finally, place the blue ones into the last k slots: (k choose k) = k!/(k!0!) = 1. In total: (3k choose k) * (2k choose k) * (k choose k) = ( (3k)! * (2k)! * k! ) / ( k!(2k)! * k!k! * k!0! ) = (3k)!/(k!k!k!).

As further extensions (though I'm not going to provide a full explanation):

• if you have 3 sets of instructions with length a, b, and c, the number of possibilities is (a+b+c)!/(a!b!c!).
• if you have n sets of instructions where the ith set has ki instructions, the number of possibilities is (k1+k2+...+kn)!/(k1!k2!...kn!).