Threads of Execution: How to Look at Them (Fast Detection of a Possible Problem)

[Eus]

Hi Ho!

Is there a better way of looking at more than one threads of execution besides enumerating all of the possible paths so that a person can quickly determine whether there will be a problem or not?

When I face a question of determining whether two threads of execution will have a problem of race condition or deadlock or starvation, I try to work out the most possible scenario of having those kind of problems in my head. For example, in case of two threads, I imagine that Thread A is interrupted after executing a certain atomic instruction and Thread B runs up to a certain atomic instruction and so-and-so until I am sure that there will be a/no problem. The difficult part, I think, is in picking the most possible scenario.

Of course I can always enumerate all of the possible scenarios as follows:

Suppose there are two threads: A and B. Each of them has four atomic instructions:
Thread A:
1) A1
2) A2
3) A3
4) A4

Thread B:
1) B1
2) B2
3) B3
4) B4

So, a given scenario always has to execute eight instructions:

__ __ __ __ __ __ __ __
i1 i2 i3 i4 i5 i6 i7 i8

For the first instruction (i1), there will be two possibilities: A1 or B1.

For i2, there will be two possibilities for each of the previous possibilities:
if i1 is A1, then i2 is either A2 or B1, whereas
if i1 is B1, then i2 is either A1 or B2, which can be illustrated as:

A1 A2
   B1
B1 A1
   B2

For i3, there will also be two possibilites for each of the previous possibilities:

A1 A2 A3
      B1
   B1 A2
      B2
B1 A1 A2
      B2
   B2 A1
      B3

And so on ...

But, it is not a good way to enumerate all of them, isn't it? There are going to be $2^8 = 256$ scenarios!

Besides that, how about if each thread nested their instructions inside an infinite loop? Another complication, right?

Therefore, is there any theorem that can guarantee such-and-such or rule-of-thumb that can point out this-and-that?

Thank you very much.


Eus

 

[jim mcnamara]

Do you know about mutexes, critical sections and so on? One way to prevent thread problems is to use these a mutex for any object or critical section that represents a "single-user" resource - like a global variable. Once a thread gets a mutex it must release it ASAP.

 

[D H]

Therefore, is there any theorem that can guarantee such-and-such

That is akin to the stopping problem -- Can an algorithm be constructed that determines whether a random algorithm will run to completion? The answer is no. OTOH, there are many rules of thumb that do say that an algorithm will run to completion. Straight line code runs to completion, as does a loop of a fixed and finite number of steps around straight line code.

Applied to this problem, there exists no general purpose algorithm (and no such algorithm can exist) to determine whether a general-purpose multithreaded will not run into resource contention problems.

or rule-of-thumb that can point out this-and-that?

This is a different beast. There are many such rules of thumb, number one being know what causes resource contention problems to arise and make sure you don't do those things. Keep mutually exclusive resources to a minimum, make sure your atomic operations are short, make sure they finish (but here's the stopping problem again). Keep the number of atomic operations that require multiple shared resources to an absolute minimum, and check these out thoroughly.

 

[jim mcnamara]

Keep the number of atomic operations that require multiple shared resources to an absolute minimum, and check these out thoroughly.

Good point, but it assumes the only contention for resources will involve only atomic operations. That means the OP will have to understand what every function and operator does precisely in his implmentation. It also limits him/her to just atomic operations. And nobody seemed to mention or care about reentrancy issues. Was it because I missed the fact that this will be limited to atomic operations?

 

[Eus]

Do you know about mutexes, critical sections and so on?

Yes, I know although I am still studying those things.

Once a thread gets a mutex it must release it ASAP.

Sure, it must. But, this does not help to detect a problem in "Strict Alteration".
Because when I knew "Strict Alteration" for the very first time, I could not detect a problem in this algorithm at a glance: a process may be held up indefinitely waiting for its turn, even if no other process is in its critical section.
Actually, I am looking for a way to detect such a problem at a glance.

That is akin to the stopping problem

Oh, I see!
But, how about if we devise a program to enumerate all of the possible scenarios and see whether there will be a problem or not?
Although it may become intractable, but it still has a solution, right?
What do you think?

Applied to this problem, there exists no general purpose algorithm (and no such algorithm can exist) to determine whether a general-purpose multithreaded will not run into resource contention problems.

Thank you for letting me know that there is no magic theorem out there (I was looking for one )

know what causes resource contention problems to arise

Do you mean that resource contention problems are deadlock, starvation, and race-condition? Do I miss other things?

Keep mutually exclusive resources to a minimum

So, we can manage them easily. There is no other reason, right?

make sure your atomic operations are short

What will be happen if they are long enough?
Isn't that the problem will be just that other processes need to block a bit longer?
I know it is annoying to see my mouse pointer stop responding once in two seconds or so, but is there any other problem?

Keep the number of atomic operations that require multiple shared resources to an absolute minimum, and check these out thoroughly.

So, we can manage them easily. Any other reason?

It also limits him/her to just atomic operations.

Is there any other possibility? As far as I know, this is all about atomic operations, right? For example, if a whole big function is atomic, then there will be no problem with that, right?


Eus