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 the mortuary 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.