Changes between Initial Version and Version 1 of InternalTricks

Timestamp:

Jun 30, 2006, 3:35:19 PM (18 years ago)

Author:

soujak

Comment:

--

InternalTricks

@@ +1 @@
+= Internal tricks =
+During real and deep developing time, we faced some obstacles seeming hard to
+overcome, but we did. That is because a few tricks helped us.
+
+An early faced obstacle was the process queue tail pointer updating in `pcb.c`
+module, avoiding to use a global-visible variable, but passing a parameter. To
+do this, each involved function receives a pointer to that queue pointer (i.e. a
+double pointer).
+
+We use the same hack on a different situation, writing `st.c` source, where we
+enjoined double advantages. Maintaining a tree after insertion/removal
+operations, means updating a couple of pointers, and so knowing their location.
+Because of the fact that tree is
+[wiki:DataStructures#a3.Semaphorebinarytree single-linked], going back the tree
+becomes impossible, and so, each of such operations must be performed starting
+one level higher in the hierarchy. Here another problem comes up: starting from
+a node, which of its child is the wanted one? As pointed up above, we found just
+one solution for both problem: using a pointer to the father's field
+(`s_leftC`/`s_rightC`), which point to the target node.
+
+But, as you can see, there is another question: which is the ancestor of the
+root element? If it does not exist, the solution just explained gets wrong and
+need a small modification: the insertion of a dummy node, pointed to by
+`semdRoot`, as root node, which makes the whole semaphore descriptors tree the
+dummy's left-progeny.
+
+This change suggests another hack, in order to find a suitable place to store
+the free list. It contains descriptors of each inactive semaphore: we linked it
+as a list, using `s_rightC` field, avoiding memory space wastes.
+
+{{{
+
+ Semaphore Tree structure:
+                ______
+               |      |
+               | HEAD |
+               |______|
+               .'   '.
+           __.'       '.__
+          |__|         |__|
+        __.''.__         '.__
+       |__|  |__|         |__|
+
+      |          |     |      |
+       `--------'       `----'
+          AST          Free List
+
+  Further details can be found directly in source code :)
+
+}}}