wiki:Design

Version 5 (modified by soujak, 18 years ago) (diff)

--

Modules design

Complex projects implementation must depend from a good design, which become a cornerstone for development with low-level programming language. A functional approach in phase of designing permits to reduce side-effects and to increase the developers' mastery of the code. What is needed in large-scale programming is a comprehensive view of function relationship, which permits engineering enhancements, such as improvement of function interaction in order to avoid code redundancy.

Phase 1

According to this, we tried from beginning to read project specifications with such wide view, noticing a sort of parallelism between removeing and outing functions. In fact, relationship among them is the same in PCB module as in ST one: out work on a specified element, while remove do the same on an element which is a priori known. Looking deeper, become clearer that they complete the same operation - dequeuing a process. So we decided to let outProcQ carry out the dirty work, reducing replicated code and our workload :). Translating this idea into pcb.c code was trivial, but was not the same for st.c, because outProcQ can be called only after determining the precise semaphore's queue to work on. Because of the fact that both outBloked and removeBlocked have to search that queue, we discarded to make one function calling the other avoiding searching twice. So, we developed captureBlocked: an internal specialized routine called by them, which searches, removes the process using outProcQ and, if the queue becomes empty (and semaphore become inactive) it removes the associated semaphore descriptor from the tree. In the latter case, this function saves the other doing a hard job - binary search tree properties maintenance.

Moreover we found another evident situation where function interaction would have made code more simple and coding funnier. It comes from the whole st.c module, where almost all functions need of looking for a semaphore descriptor. So we created searchSemd, which carries out the majority of scanning-tree iterations load. In the name of code re-usability and non-determinism, we created a function capable to be called by different functions with different targets. It returns a reference to a possible result of the tree search; this output will be interpreted by removal function as the place where "victim" is, while by inserting one as the place where to put in.

Phase 2

Nucleus is all but linear, because of the intrinsic web of calls, passes up and invocations inside the code. A modularized structure eases not only writing and maintaining the code, but also understanding it.

Scheduling

Designing Phase 2, we distinguished between two strictly correlated operations: scheduling and dispatching. In fact we intend the first as the action of analyzing ready processes and then choose one for execution, together with its time-quantum length. On the other hand, dispatching means to put into effect (and guarantee) that decision, that is loading the right processor state.

Therefore we divided them, confining the scheduler in a capsule which obfuscates its real implementation details. This highly increase scheduler adaptability, easing future changes in every scenarios. Moreover our implementation is oriented to run-time changes of scheduling algorithm, in order to provide an operating system that is general-purpose and not generic-purpose. In fact the scheduler's interface consist of a series of pointers to the specific-implementation functions. They are initialized by initSched() according to the configuration chosen in the Makefile. Run-time switch between scheduling algorithms can be easily implemented with a function which performs a trivial update to interface pointers and internal data structure: the ready queue.

Dispatching

We did not spend less time accurately defining interface and duties of dispatcher. In addition to the classic implementation mentioned above, we decided to request it CPU time accounting. It has to measure both direct and indirect use of the CPU. We refer to the direct use when the CPU is busied with tasks of the process; indirect use qualifies the complex of tasks performed for a process by the nucleus. Dispatcher itself could perform direct CPU time measure trivially, so we opted to request it also the indirect time accounting. In fact the two functions added to dispatcher interface, play() and pause(), achieve this purpose. See the diagram right above to deep understand interactions between scheduler, dispatcher and the remaining sections of the nucleus.

 ------------------------------------------------------------------------------
|                      Sequence diagram of CPU usage                           |
 ------------------------------------------------------------------------------

  Dispatcher   Process1    Process2   SyscallH   InterruptH
    ___           .           .         .           .
     |            .           .         .           .      execute(P1);
     | . . . . . ._           .         .           .      play(P1);
     .            |           .         .           .
     .            |           .         .           .
     .            |           .         .           .
     .            |. . . . . . . . . . ._           .      -WAITIO-
     .            .           .         |           .      suspend(P1);
     .            .           .         |           .      
     .            .           .         |           .      
     _ . . . . . . . . . . . . . . . . .|           .      pause(P1); 
     |            .           .         .           .      schedule();
     |. . . . . . . . . . . . _         .           .      play(P2);
     .            .           |         .           .
     .            .           |         .           .
     .            .           |         .           .
     .            .           | . . . . . . . . . . _      pause(P2);
     .            .           .         .           |      play(P1);
     .            .           .         .           |      wakeup(P1)
     .            .           .         .           |      pause(P1);
     .            .           _ . . . . . . . . . . |      play(P2);
     .            .           |         .           .      
     .            .           |         .           .
     .            .           | . . . . . . . . . . _      -INTR-
     . . . . . . . . . . . . . . . . . . . . . . . .|      dispatch()
    _|_           .           .         .           .