Number of ways a program can execute on a sequentially consistent architecture

Question

I am very poor at understanding and trying to solve this problem, Let's say we have 3 threads with a,b,c instructions each, I need to find how many different ways the program can execute on a sequentially consistent architecture? H How should I approach this problem?

Answer 1

You have 3 threads. Each one processes a sequence of actions a, b, and c. Lets use numbers for threads. The key thing to understand: each thread 1 to 3 ... has to process its actions in their order. Variations can only happen because the threads can do their work in many combinations. Let's also assume that our machine can serve only one thread at any time - and that actions are completed before a thread context switch happens.

You can have:

1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c
1a, 2a, 1b, 1c, 2b, 2c, 3a, 3b, 3c
1a, 2a, 2b, 1b, 1c, 2c, 3a, 3b, 3c
1a, 2a, 2b, 2c, 1b, 1c, 3a, 3b, 3c
1a, 2a, 2b, 2c, 3a, 1b, 1c, 3b, 3c
1a, 2a, 2b, 2c, 3a, 3b, 1b, 1c, 3c
...

Looking at that, one can think up an algorithm to build a tree spawning all combinations. You basically pick a candidate, like "1a", and then you figure which next steps are possible (in this case 1b, 1c, 2a, ... 3c). You can then start building paths:

 1a-1b 
 1a-2a
 ...

and so on. For each path, you remember the elements on it. And in order to add another element, you check out the "remaining" ones. Each remaining object defines another new path. Repeat.

By doing so, you should be able to define an algorithm that computes all possible paths.

This would make up a nice coding kata exercise - and my input should be good enough to get you going. If you need a shortcut, maybe look here. Or there.

Beyond that: obviously, this could also solved as a pure mathematical problem: if you just put all elements 1a, ... 3c into a list, and create all permutations of that list, you would receive 9! so, 362880 possibilities. But of course, this doesn't work, as your problem should exclude permutations such as 1b, 1a (because a, b, c will always be "in order" given your requirements).

So ( number threads + number steps ) ! gives you an upper boundary for the number of valid paths. Maybe someone else comes by and adds a bit more of maths to figure the number of invalid paths.

( btw: that would be another approach for "printing" all possible paths - simply create ALL permutations of the 9 elements, and drop those that are invalid )

Disclaimer: all of the above only makes sense when we assume that the underlying machine has exactly one "real" thread. And that thread execution and context switches happens after an operation has completed. If you drop these assumptions, then you make room for:

1: aaaabbbbcccc
2:  aaaabbbbcccc
3:        aaaabbbbccc

In other words: if you consider the potential paths in a real machine, things become much more complicated.