Identification and control techniques for multicore scheduler design

This thesis is part of a long term research line whose purpose is to apply the principles of the systems and control theory to the design of software systems. This research is motivated by the fact that a significant class of computing system problems found in computing systems at large and, more in detail, within operating systems, are, de facto, control problems, even though, traditionally, are solved directly through algorithms or heuristics. A relevant and prominent example is the problem of task scheduling in operating systems, for which a fully control-based scheduler was designed, implemented and profiled. It was shown that such a design approach results in a simpler implementation with respect to many classical ones, and permits to analyze and assess the results formally. This thesis extends the quoted work in a previously unexplored direction, a control-based approach to schedulers designed for multi core architectures. To use control-design principles in a multicore context, first of all, it's necessary to develop the model of the process which will be controlled. So, first part of the thesis is focused on a preliminary analysis about how to model tasks in multi core context. Tasks have been divided into classes, characterized by similar task behaviors from system resources point of view, and then each class has been modeled. Since there are no physical principles available to write models, they have been obtained from data, profiling, for each class, a representative application. Models have to well represent all the tasks belonging to the same class, so they have been developed to represent a family of similar, but different, applications, united by some basic behaviors. In the second part of the work, it's presented a multi core scheduler simulator development. This simulator is useful to have a plain, controlled environment where control structures can be implemented, tested and tuned, without external influences.

Questa tesi fa parte di una linea di ricerca di lungo periodo il cui fine è l'applicazione dei principi della teoria dei sistemi e del controllo alla progettazione dei sistemi software. La ricerca è motivata dal fatto che una vasta gamma di problemi che si incontrano nell'ambito dei sistemi software, e più in particolare, dei sistemi operativi sono in relatà dei problemi di controllo, anche se tradizionalmente risolti direttamente tramite algoritmi o euristiche. Tra questi problemi, un esempio rilevante è quello dello scheduling nei sistemi operativi, per il quale una soluzione interamente basata sulla teoria del controllo è stata progettata, implementata e comparata con soluzioni più tradizionali, dimostrando che un tale approccio progettuale dà come risultato una maggiore semplicità rispetto a molti algoritmi classici e, soprattutto, permette di analizzare e valutare i risultati ottenuti formalmente. In questo lavoro si è proposto di estendere l'approccio basato sulla teoria del controllo a scheduler progettati per architetture multi core. Per utilizzare i principi di progettazione proposti della teoria del controllo in un contesto multi core, prima di tutto è necessario sviluppare il modello del processo che sarà controllato. Così, la prima parte della tesi è focalizzata su un' analisi preliminare su come modellare i task in un contesto con più unità di calcolo indipendenti, ciascuna dotata di una cache locale. I task sono stati suddivisi in classi, caratterizzate da comportamenti (dei task) simili dal punto di vista delle risorse di sistema e, successivamente, ogni classe è stata modellata. Poichè non ci sono principi fisici su cui scrivere i modelli, essi sono stati ottenuti dai dati, profilando, per ogni classe, un'applicazione rappresentativa. I modelli devono rappresentare bene tutti i task che appartengono alla stessa classe, quindi non sono stati sviluppati per fare un buon fitting sulle tracce di esecuzione di uno specifico task, ma devono rappresentare una famiglia di diverse tracce di esecuzione, accomunate da alcuni comportamenti fondamentali. Nella seconda parte del lavoro, è stato sviluppato un simulatore in grado di implementare, testare e mettere a punto algoritmi di scheduling per sistemi multi core, senza interferenze esterne.