Turing Tumble Community

Race condition in multithreading

I was just fiddling around with an output of 4 blue, then 1 red and again 4 blue etcetera and instead of launching one ball, I launched another one quickly after the first and then another.
Among other things this shows concurrency AND that this also means you get the answer faster. See yourself, the human with the trigger finger as a thread and the interval between two launches as a random time between threads starting.
This also shows thread race conditions, so that the output is incorrect. I even had a deadlock situation where a red and blue wanted to go through a gate at the same time and the gates locked up.
I thought this was awesome as it shows multithreading and the problems you can have very clearly and it is a difficult concept to grasp normally :grinning:

@kupfeli This is great. I don’t have a programming background, so multithreading was a new term for me. When I teaches classes of kids Turing Tumble, I usually have to be pretty clear to just hit the start lever once. Now I can tell them it is because of multithreading. Here’s info on it for others who are new to the concept: https://www.techopedia.com/definition/24297/multithreading-computer-architecture

1 Like

I love this idea. I ran into this problem in a construction on the simulator I did where I wanted pipelined computation, but had to be careful that there was enough delay between the balls so that a race condition didn’t occur due to some upward-gear chaining. A solution is to ahve the computation start with a long time-wasting ramp, then a trigger for the next ball, then the computation, so each next ball triggered was behind the previous one by enough that there is no interaction.

It would be nice to design a lesson specifically to demonstrate successful multi-threading, pipelining, and race-conditions. For example, consider implementing ball counters in the following ways:

Construction 1 : create a separate blue and red ball counter. This would involve two side-by-side computations, one with blue marbles, the other with red, and no interaction possible. Push both levers at the same time and you’ve got a good example of independent non-interfering processes. You add the two results at the end to get the total number of balls released.

Construction 2: have a single ball-counter, which counts both blue and red balls. If you wait for each ball to be counted and caught at the interceptor, then you’ve got normal serial computation. If you hit both red and blue levers at the same time, you’ll likely get a race condition (and a jam) when both balls try to feed in to the top of the counter. If you hit the blue lever, wait a little, then hit the red lever, then wait, then back to blue, etc., you can probably get multiple balls going at once in a pipelined fashion and having them all counted if the separation is enough. If you don’t wait long enough, you’ll get the race condition, where either a jam occurs, or an incorrect bit-flip happens, or something. Kids can have time trials where the goal is to correctly count all of the red and blue balls without jamming… so the goal would be to pipeline as quickly as possible without one ball interfering with the previous one.

1 Like

Very nice ideas Lenny!
By the way, using these principles you can also show the kids that using pipelining the result is there much faster and they also get to think about when pipelining is possible and when its not, though that is quite advanced. But just having them flip the lever multiple times and waiting a bit already makes them aware of parallelism in a natural way.
This also makes me think about thread synchronization, for instance we could also design a “mutex” component for instance. If a ball wants to take hold of a “resource”, which could be a ramp, a bit or a gear for instance it must first acquire a lock on the mutex and afterwards unlock it so another ball may lock it. This mutex could be maybe created using a bit and some gear parts, but I am not sure, otherwise I could maybe design a component for that.
But the idea of having a separate area on the board only accessible by one ball at a time (or two maybe even) is interesting I think. We could create something that a blue ball locks the mutex for instance and the red one unlocks it. For that we could create a specific kind of bit that when switched from the left by a blue ball, it transfers the ball through it and it can only be pushed back from the right using a red ball. When another blue ball comes and wants to acquire the lock, the bit cant let it go through and the system is blocked (the thread is blocking), whenever the red ball pushes it back, the blocked blue ball can pass again and has acquired the lock etcetera.

1 Like

Now I have it, a working mutex example, with existing parts!
See the attached screenshot :grinning:
How it works is that the gears together form the mutex. If it is turned to the left, the mutex is “unlocked” and thus the blue ball may execute the ball counter mechanism on the right side and because of the gear setup it locks the mutex. When the counter is finished, the red ball is triggered and unlocks the mutex again, so a blue ball may count again (go to the right side).
What you can demonstrate here is that if the mutex is “locked” the blue balls cant go through the counter (try it out, that works because of the mechanism of the gear setup). Just launch a blue ball while the counter “code” is executing and the blue ball goes to the left, so to say it is simply ignored. This also demonstrates a queue mechanism where a clerc needs to fill in a form for a customer (the counter code to the right) and only when it is finished, a new customer can be accepted (red ball unlocking the mutex).
Btw, the catcher is there to halt the computer if you are trying to unlock the mutex when it is already locked. I decided to handle this as a “fatal exception”. Ask students why there is no catcher on the left.

To create a class case for this, you could use the example of a student counting balls which other students hand to him. Only if a ball is counted, the student has time to take another ball. Already set the ball counter mechanism up and state that the student must create a mechanism where the counting may only start when a previous count was finished. Obviously also tell them this must work no matter how often the blue trigger is pushed during counting. Of course dont push the trigger too fast, otherwise the blue balls jam something up.
Also setup the left part of the gears and the student must fill in the rest.
Hope this is useful :grinning:image

1 Like

The idea of making a mutex is really cool!
We (by which I usually mean “somebody” :slight_smile: should definitely make a lesson about parallelism.

Here’s another version of locking/unlocking a resource, where the process controlling the resource is responsible for unlocking. Here, we’ve just got one ball-hopper to feed a counter (though there is no reason why there couldn’t be more). I accidentally left the counter to start at “1” - please ignore that.

The counter is available if the gear bit at the top is set to 0. Before entering the counter, the ball locks the resource by setting the gear bit to 1. Any additional trigger hits will have balls diverted to the left interceptor. That is, until the counter is unlocked by the counted ball via a gear chain that resets the top gear bit to 0.

Note that the “reset” command, that is, the lower gear bit, could actually be placed higher up to allow pipelining, as long as it wasn’t so high that a new upper ball would interfere with the lower ball.

counter lock-unlock

Oops - just noticed that the lower right gear bit will never be used, and is not necessary at all.

1 Like

Ah yes, I get it, also nice!
That is also what I mean with “we”, that “somebody” could do that, somewhere in time, or someone who is not as lazy as I am :grinning:
This way indeed the driving ball does the lock and unlock.
That last gear which is unused is just an example of “unused code”, which could potentially even polute the correct code, if it breaks for some reason. Happens in actual software as well :joy:
Using the simulator is also nice!

1 Like