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.
Phase 1
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
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 :)
Phase 2
Kaya OS provides a system call which offers to the caller the
possibility to wait until the next pseudo-clock tick. This clock
wakes up sleeping process every 100 milliseconds.
The best way to make this clock accurate is to use the interval
timer, which is therefore used in two different manners. So we
had to distinguish between the pseudo-clock use and the classic
preemption trigger use. Moreover we had to guarantee the
accuracy of length of time-quantum assigned to scheduled
processes. The answer to both issues is a time-credit
system.
Time credits, as you can easily see, solves the problem about
time slices. And the problem about the distinction of
interval-timer uses, too. If there are some credits, it means
that the current process was dispatched for a time lesser than
the quantum that was assigned by the scheduler. The dispatcher
is conscious of time-credit system and restores time losses.
There is another situation where our implementation differs from
the expected one. The classic implementation of
semaphores, need a value adjustment when terminating a
waiting process. Instead of this, we opted to change the value
only if needed, that means the passeren()
subtracts only if
non-blocking and the verhogen()
adds only when no process is
blocked.
There are several little optimization limiting wastes of cpu
time and memory usage. They do not deserve a deep explanation
but they must be mentioned:
- Direct passup: external exception-handlers (loaded by internal ones) returns the control directly to the process which raised the exception.
- Iterative
TERMTHREAD
: process termination means termination of its progeny. Instead of a recursive call, we preferred to first breadth-visit the whole sub-tree and then kill generation after generation.... muahuahuah! Search for themortuary
among the code. - Exception handler functions: An unexpected benefit of modularization avoided exceptions raising after errors or abnormal situations. We opted for a direct function-call strategy, which clearly minimizes the over-head caused by these recursion, reducing the number of context switches.
- Idle: thumbs twiddling it is implemented without waste a whole process control block. A dummy-loop function is more than enough, so we automagically set the interval timer up in order to ring when it is time to pseudo-tick.