Concurrency Combination

1 points by sahueso 16 years ago · 2 comments · 2 min read

I decided to learn concurrency and wanted to find out in how many ways machine instructions from two different threads/processes could overlap in a theoretical setting where they are executed linearly. The code for both processes is a 10 iteration loop with 3 instructions performed in each iteration. I figured out the problem consisted of leaving X instructions fixed and then fit the other X instructions from the other process between the spaces taking into account that they must be ordered (eg.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 life of one process, so for 10 iterations it would be 30, and n is nº instructions * 2 (2 processes), 60. In other words, the problem is the same as having 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.

I have no idea why n C k works, I understand that the definition of a combination is, in how many ways can you take k elements from a group of n elements 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, so I don't see how it can be a combination where we are taking only k instructions from this set of size n, leaving the other k without being executed.

Could someone please explain to me how it works?

Thanks in advance.