Treetor: tree visualization tool and JDFR

www.heteroclinic.net

Tree Graph Analysis 1/4

1.Intrudction

We continue the analysis of deadlock problem by studying the features of tree type graph.

2.Tree and its number of edges

We can consider a {\it tree} is a graph that has only one root node. From this root node, we can reach any one of the other nodes and the path is unique (the vertexes/nodes edges sequence is unique). Normally we consider tree is un-directed graph. However, if we consider every edge is bi-directional, it will give us great advantage. In the practice of this article, we use the parent node to sub-node direction to construct the graph, the sub-node to parent node direction to uniquely identify a node.

Corollary 2.1 A tree with $n$ nodes has $n-1$ edges, $n \in \mathbb{N}$.

Tree Graph Analysis 2/4

3.Tree and connected graph

Corollary 3.1 A connected graph with $n$ nodes and $n-1$ edges is a-cyclic $\iff$ it is a tree, $n \in \mathbb{N}$.

4.Conclusion from above sections

From the discussion in the above sections, we can draw some very important conclusions. Here, we leave them to the readers as a brain exercise.\\ We show these conclusions in our coding projects.

5.A tree utility program, BFS and DFS traversal

We attach Java program that can be use to construct a tree. After the tree is constructed, we can use BFS or DFS to print the tree. The readers will also see the program will assist the proper construction of a tree.

6.Treetor a snapshot tool

Treetor is a visualization tool of a tree. We use it to render a tree to jpeg file. Unfortunately, it can not create a file has more than 65,500 pixels. In next phase, we will move to OpenGL, theoretically, we will not have a soft limit as javax.imageio.

7.Discussion

Tree Graph Analysis 3/4
A tree utility program, BFS and DFS traversal

A small utility program Node.java

Tree Graph Analysis 4/4
Treetor a snapshot tool
Treetor is a visualization tool of a tree. We use it to render a tree to jpeg file. Unfortunately, it can not create a file has more than 65500 pixels. In the next phase, we will move to OpenGL, theoretically, we will not have a soft limit as javax.imageio.
treetor.jar
treetorLicesnse.txt

Test.java Case I result

Test.java Case II result
Download, view with a graphics tool like Microsoft paint or GIMP etc. Test.java Case II result

A small test program Test.java

Treetorplus1 and Treetor Functional Requirements 01
Change Graph Orientation
Treetor is a visualization tool of a tree. Now we realease Treetorplus1 treetorplus1.jar,treetorLicesnse.txt

Test Case

Treetoplus1 and Treetor Functional Requirements 02
Build a T-Node Tree

Test Case

Treetorplus1 and Treetor Functional Requirements 03
Build a R-Node Tree

Test Case

Treetorplus1 and Treetor Functional Requirements 04
Build a RT-Node Tree

Test Case

Treetorplus2 and Treetor Functional Requirements 05
Forest Ministry
Treetor now can render simply forest or basic tree operations. We realease Treetorplus2 treetorplus2.jar,treetorLicesnse.txt

Treetoplus2 Forest Ministry Test Case
Test case of rendering a very simple forest:
Visualization of an Imaginary Concurrency Event
We spent much effort to implement functional requirement 05. What is the purpose for doing such? We attach the following program to show an imaginary concurrent event, which is figured out by the author.
If you would give a name of such event, what will it be?
Such event is good or bad?
In coming episodes, we are going to build real concurrent prototypes to demonstrate such behavior. We may or may not.
Have we demostrated a solution for such behavior in our previous coding projects, implicitly or explicitly?

An imaginary concurrency event, good or bad? What are you trying to do?

Visualization Results of XIX
Animation

PNGs:

Figure 01

Figure 02

Figure 03

Figure 04

Figure 05

Figure 06

Figure 07

Figure 08

Figure 09

Figure 10

Figure 11

Figure 12

Treetorplus3 and jdfrbeta01
Prototype no.1 Just Lock and Unlock
Now we realease Treetorplus3 treetorplus3.jar,treetorLicesnse.txt.
We also release jdfrbeta01.jar. 'jdfr' stands for Java Dead-lock Free Runtime. The goal is to design a runtime that will handle general concurrency issues. In the future, we may extend to operating system design/implementation. Or it may not be necessarily to design or implement something new, because we have 'injection' technology. These goals are still far. By now, what are at our hands are four prototypes. So far, we are able to profile basic concurrency events. Please note these prototype will only under the very conditions we pre-set. What works is just what worked! Any above-mentioned goals are huge tasks beyond the limited ability of the author. I spent much time studying java.util.concurrent written by Prof. Doug Lea. It corrects some very critical mis-understandings of mine. Although I am able to build these prototypes using C, C++ etc, without Java, without open source, it won't be so fast. Eclipse Java IDE also provides great help speeding up the work. 'jdfr' is open source. The jar comes with the source code inside.
The first prototype is 'Just Lock and Unlock'.
How to:

You will get the images at the folder specified.

You can also try to modify this file.

Treetorplus3 and jdfrbeta01
Prototype no.2 Simple Blocker and Blockee
How to:

You will get the images at the folder specified.

You can also try to modify this file.

Treetorplus3 and jdfrbeta01
Prototype no.3 A More Complex Blocker and Blockee
How to:

You will get the images at the folder specified.

You can also try to modify this file.

Treetorplus3 and jdfrbeta01
Prototype no.4 A Simple Dead-lock Profiled
How to:

You will get the images at the folder specified.
After the dead-lock is formed, the program will not stop unless a forced ctrl-C. The late tryer caused the dead-lock is painted by 'stop-sign' color.
If you find any errors or you want to leave other comments, please send me email.

You can also try to modify this file.

PNGs:

Figure 01

Figure 02

Figure 03

Figure 04

Figure 05

Figure 06

Figure 07

Figure 08

Figure 09

Figure 10

Here, we present a bad prototye. We also give some reasons to present it even it is bad.
How to:

You would need these two jars: and treetorplus3.jar and jdfrbadprototype01.jar.
You can study the source code inside jdfrbadprototype01.jar. You can also check out the entry point TwoLayersDeadlockImprovisedSolution.java.

Simply, it does not full-fill the purpose of the desgin or the requirement(s). In "Advanced Concurrency Topic: Runtime Deadlock Detection XIX Visualization of an Imaginary Concurrency Event" and "Advanced Concurrency Topic: Runtime Deadlock Detection XX Visualization Results of XIX", I drew a series of diagrams. We tried to conjecture a scheduler that creates a live-lock. Two threads keep yielding each other, but neither of them can acquire all the resources it needs. Neither of them can finish its job.
To build this prototype, we made an assumption. It was also made from the beginning I dived into the dead-lock detection topic. The assumption is that we would be able to read one thread's status from another thread. Thus, we can detect deadlock. Live-lock is construct-able if a thread can know what its peer thread trying to get. If it just gives up one but not all the peer needs, live-lock could happen.
From this prototype, we know this assumption is wrong. If we execute the command line given, it will create either a dead-lock or the starvation of one of the threads. A thread's status is so volatile. A running thread will be blocked, go to sleeping, or perished. A blocked thread can be unblocked just next several CPU ticks. One thing is certain if a thread had finished. We may say two threads are like two particles, can this be called 'entangling', to observe accurately will affect the behavior the object being observed. Or to say, we can describe space/status or time accurately either of them but not both of them at the same time. I am not in physics area, so I stop short here and come back to our topic.
So if we can not read another thread's status from one thread, which is a fundamental mis-understanding, are we completely wrong so we can do nothing( we may also argue that we can lock status, a thread status has read write lock etc-- nightmare of spaghetti)? In our previous discussion, we show a healthy system is a tree-like structure. When a dead-lock is formed, it becomes a cyclic graph. But once the dead-lock is formed, no threads can change their status, suppose we use a no-time-out lock(). What we did in the middle of this topic, help us properly construct the graph. When dead-lock happens, we can detect it. The profiling or detecting mission is accomplished.
An Artificial Livelock
Although our attempt at XXV failed, we can still make a scheduler that follows the digram we drew.
You would need these two jars: and treetorplus3.jar and jdfr1.0.jar.

How to:

You can check out the entry point:

So, you would see the concern is no longer to create a live-lock. At the end of each thread, we did something. I hope this will provide some hint about how to deal with concurrent program that looks bizzare. In general, we should not fear live-lock. As long as the threads are alive, we will have a chance to change the resource access pattern. If a system has no hope, that is the real problem.

More Tested Examples
Multi-tier

How to:

Entry point:

Fast
How to:

Entry point:

Random
How to:

Entry point:

Period
So far, months have been spent upon this topic. The resources are limited, I have to put a period. We may continue on with the same topic or similiar topic.

Today, we release jdfr1.0.jar.
- it fully supports Java ReentrantLock
- it has several proto-types, quick-starts or just say examples -- in the Blog section

It will be a very useful tool to profile concurrent programming. We also have treetor treetorplus3.jar which can render about several thousands nodes of a-cyclic graph or a forest. If I got enough support, we may switch to OpenGL rendering engine and using more advanced IPC.

We corrected some mis-understandings. They are critical but finally not fatal to this project.
I am still not sure about next step. I hope there will be more people download and study what I did. It will be a great pleasure that you can achieve something with these tools. Science and technology does not rely on luck. If you find any bug or errors, please feel free to point them out. This project is done by one person, so it is convenient to control. In real life projects, we have to resolve human conflicts, legacy pacakges etc. Some time you do not even have the source code not mention how to modify them. So we can not simply put a easy or difficult label for a project.
The methods we tried or proposed, may be helpful while extending to profile database system, interprocess concurrent programming, the operating system, or for clustered computing units. Concurrent programming in some sense destroyed the von Neuman architecture, much more effort is needed for understanding or utilizing the nature of concurrency.
More Tested Examples
Multi-tier

How to:

Entry point:

Fast
How to:

Entry point:

Random
How to:

Entry point: