Control based design of OS components

This thesis is part of a long-term research, the ultimate goal of which is the introduction and exploitation of control based methods and tools in the design of computing system components. The major claim of this work is to support -by means of experimental evidence gathered on real hardware and software- that the proposed approach is indeed a step forward from the design viewpoint. To support that claim, the typical control design procedure was applied to a software problem: preemptive task scheduling, by - first modeling the problem in system-theoretical terms, - then designing a solution in the so chosen modeling formalism, - and only in the end implementing the solution as an algorithm in some programming language. Such an approach is applied in this thesis, in all of its phases. The result is the design of a "control theoretical" scheduler named I+PI for reasons that will become clear later on. In fact, the adoption of control theoretical methods not only generally leads to improved performance and increased robustness to unpredicted runtime situations, but also yields the ability to formally prove the properties of interest for the control system. The thesis is organized as follows. Chapter one provides an introduction to the problem and a minimal literature review. Chapter two presents in detail the I+PI scheduler. In chapter three the Miosix kernel is introduced, detailing its innovative features with particular emphasis put on its suitability for the benchmarking of schedulers. Chapter four is dedicated to the performed benchmarks, and chapter five draws conclusions regarding the presented work, and outlines future directions. The obtained results can be summarized as the successful implementation of a control theoretical scheduling policy on a real architecture. This proves that previous results -more "theoretical" than those of this work- can be applied provided that the underlying engineering aspects are dealt with correctly. All of this allows to hope that the research path followed herein will further provide good results.

Questa tesi fa parte di un lavoro di ricerca a lungo termine, il cui fine è l'introduzione dei metodi della teoria del controllo nella progettazione di componenti software. Il principale contenuto innovativo di questa tesi è quello di dimostrare -attraverso prove sperimentali- che l'approccio proposto è effettivamente un passo avanti rispetto alle usuali tecniche di design. A sostegno di tale affermazione, la tipica procedura di progettazione dei sistemi di controllo è stata applicata ad un problema software: lo scheduling dei task in un sistema operativo, - modellando prima il problema in dal punto di vista teorico, - poi progettando una soluzione nel formalismo scelto, - e solo alla fine, implementando la soluzione attraverso un algoritmo in un linguaggio di programmazione. Tale approccio è stato applicato in questa tesi in tutte le sue fasi. Il risultato è la realizzazione di un "controllore-scheduler" chiamato I+PI per ragioni che verranno esplicitate in seguito. Infatti, l'adozione della teoria del controllo non solo porta al miglioramento delle prestazioni e della robustezza a situazioni impreviste, ma consente anche di provare formalmente proprietà di interesse per il sistema di controllo. La tesi è organizzata come segue. Il primo capitolo fornisce un'introduzione al problema e una revisione della letteratura scientifica. Il capitolo due presenta in dettaglio lo scheduler I+PI. Nel terzo capitolo viene introdotto il kernel Miosix, presentando le sue caratteristiche innovative, con particolare attenzione alla sua idoneità per il benchmarking degli scheduler. Il quarto capitolo è dedicato ai benchmark eseguiti, infine il quinto capitolo trae le conclusioni del lavoro svolto. I risultati ottenuti possono essere riassunti come l'effettiva implementazione di uno scheduler basato sulla teoria del controllo in un kernel. Ciò dimostra che i risultati precedentemente ottenuti -più "teorici" rispetto a quelli di questo lavoro- possono essere effettivamente applicati in pratica. Tutto questo permette di sperare che l'argomento di ricerca qui presentato possa fornire ulteriori buoni risultati.