Threads as braided strings in abstract space (1)
Thursday, October 25th, 2007In the past I was trying to find a way to depict running and blocked threads graphically perhaps as strings in some abstract n-dimensional space (manifold), preferably 3-dimensional manifold. If you have never encountered manifolds here is their informal definition:
3-dimensional manifold is a 3-dimensional space that looks like a 3-dimensional Euclidean space locally (in small regions) so we can explore the manifold space like we do in our 3-dimensional spatial world
Example: the surface of a sphere where small regions look like 2-dimensional rectangles (compare Earth surface and a football field on it)
My infrequent attempts were not satisfactory and only recently after reading the book Towards a Philosophy of Real Mathematics
Braids are strings that raise monotonically without reversing their direction. It sounds like an arrow of time during computation. Braid theory is related to knot theory and might be at a good metaphor to explore. To picture thread strings we need to find abstract coordinates for our space. One of axes is obviously time axis and the other is a program counter axis (for example, the value of EIP register).
Here is a thread running through code sequentially without jumps or loops, acquiring and releasing a spinlock on its way:
Here is another thread looping while trying to acquire a spinlock and finally taking ownership of it and then running through the same code sequentially:
Suppose that both threads contend for the same spinlock and there is a 3rd thread doing the same. Let’s overlay them on one single diagram:
To have a perspective we can add a 3rd dimension - thread number or ID (TID):
Instead of TID axis we can use data address axis (the data address accessed by the current instruction) or have it as a 4th dimension. If we want to differentiate between read and write addresses we can add 5th axis. We will try to do it in the next part.
- Dmitry Vostokov @ DumpAnalysis.org -