Data structures
A well-designed data structure allows a variety of critical operations to be
performed, using as little resources (both execution time and memory space) as
possible. Moreover, a carefully chosen data structure will allow a more efficient
algorithm to be used; consequently such choice assume a primary importance in
this project.
The two fundamental data structures on which Phase 1 layer is founded are lists
and trees, implemented in various ways, depending on the singular case
evaluations.
Here below we are going to describe the two most significative flavour of them.
1. Linear single linked list
This simple data structure has been choosen for trivial structures implementation. We are talking about lists of non-allocated PCBs or SDs: respectively pcbFree and semdFree.
In fact, because of element insertion and deletion may involve only the first one, a stack with a O(1) computational cost is what we was looking for. And is what we implemented with a linear single linked list, appreciating its simplicity.
2. Circular double linked list
List management operations, such as element insertion and deletion, require
predecessor and successor updating. Because of this, a previous element pointer
(p_prev) is added to the PCB standard structure, performing these operations
scanning the list only once.
Kaya Phase 1 will take advantage of double circularly linked list benefits in every processes queue, which is widely used by operating system.
3. Semaphore binary tree
The importance of the choice of data structure increases directly with the performance relevance and for semaphore descriptors management becomes a primary goal. That is because semaphores queue's phisical address is obfuscated in a higher level view, so Phase 1 layer must encapsulate the association between semaphore address (semAdd) and its queue into the Semaphore descriptors (SDs).
Such association must be searched between them and if they are managed in a sorted structure computational costs decrease, avoiding scanning everyone. For this reason we opted for a data structure that is more complex and difficult to mantain but, on the other hand, is more performant and scalable: a binary search tree.
Let us show in detail a BSTs comparison with sorted list.
The major part of mantainence costs depends on the fact that it is sorted and,
consequently, on the search cost. In fact, while a list search costs O(n), a
binary tree takes only O(log(n)), because of the number of scanned elements
is at most equal to the tree height. By the way, input distribution influences
BST's height in a determining way, deciding tree balance, making O(log(n))
an estimate of the average case cost. In particularly adverse situations BSTs
collapse into a fked list.
Summing up, in order to appreciate BSTs performance improvements and scalability,
input cardinality should be sufficiently large and well-distributed.
Like often happens, performance and memory usage risk to collide and a good
compromise is needed.
Therefore we tried to limit wastes, just single-linking the tree with s_rightC
and s_leftC pointers, increasing module complexity and consequent
implementation and maintainance difficulties.
------------------------------------------------------------------------------
| Semaphore Tree data structure |
------------------------------------------------------------------------------
A ctive _________ Free list
S emaphore | | ._______.
T ree | DUMMY | |
._________. |_________| \|/
| |____|____| V
\|/ .....' `........................
~log(n) V : :
__ _____ _____
| | | | |
| |_____| |_____|
| ........' `............. .'
| : : :
| _____ _____ _____
| | | | | | |
| |_____| |_____| |_____|
| .....' `..... `..... .'
| : : : :
| _____ _____ _____ _____
| | | | | | | | |
| |_____| |_____| |_____| |_____|
: . . . . . .
: . . . . . .
. ..... ..... ..... ..... ..... .....
. : : : : : : : : : : : :
