Control based tickless scheduling

The use of theoretical methodologies in systems design is highly endorsed in many fields of engineering due to simplicity, flexibility, and uniformity of the solutions as well as the possibility to assess the results even in unpredictable run-time situations. The latter is probably the strongest incentive for exploiting such approaches also in the design of operating system components. This thesis is a part of the aforementioned research trend, as it is devoted to enhance robustness and responsiveness of an existing task scheduler named I+PI which is designed in the light of control theory. This scheduler works by partitioning a run-time modifiable amount of time, called the round time, among all the active tasks, and correcting on-line for any observed discrepancy. The fraction of the round time allotted to each task is also configurable on a per-task basis to best suit the tasks needs. The original scheduler was shown to have a performance closely chasing the EDF scheduler for schedulable task pools, and outperforming it for pools that may become transiently unschedulable. However, a weakness was found in I+PI with pools of periodic tasks having highly asymmetric periods. Scheduling such task pools with I+PI calls for short round times, which increases the scheduling overhead. The contribution of this thesis is to improve I+PI's responsiveness-overhead trade-off by redesigning the control scheme and exploiting the concept of tickless kernels. In such kernels, the time system is designed in an aperiodic fashion that provides other subsystems with dynamic ticks rather than having a periodic interrupt from the system timer. The performance of employing a control theory based task scheduler on top of a tickless kernel is demonstrated in this work through suitable experiments showing that it outperforms the original I+PI scheduler in all the evaluated cases, and tends to be strictly better than EDF in many situations. We will show that the new approach is a highly qualified candidate in real-time applications with or without deadlines and without imposing any particular symmetry on the arrival pattern of tasks.

L'uso di metodologie teoriche nella progettazione dei sistemi è una strada seguita in molti campi dell'ingegneria per via della sua semplicità, flessibilità e uniformità delle soluzioni nonchè per la possibilità di valutare i risultati anche in situazioni imprevedibili di esercizio. Quest'ultimo è probabilmente il più forte incentivo per sfruttare tali approcci anche nella progettazione di componenti di un sistema operativo. Questa tesi è parte di questa linea di ricerca, in quanto è dedicata a migliorare la robustezza e la reattività di uno scheduler esistente denominato I + PI, progettato usando la teoria del controllo. Questo scheduler partiziona un tempo modificabile a run-time, detto tempo di round, tra i task attivi nel sistema, correggendo on-line eventuali discrepanze osservate nel loro comportamento. La frazione del tempo di round assegnata a ogni task è anch'essa configurabile, e può essere diversa per ogni task in modo da meglio adattarsi alle necessità specifiche dei task. Lo scheduler originale ha dimostrato delle prestazioni che si avvicnano allo scheduler EDF nel caso in cui il task pool sia schedulabile, e prestazioni migliori di EDF nel caso in cui il task pool diventi temporanemaente non schedulabile. Tuttavia, lo studio dello scheduler I+PI ha evidenziato un problema nel caso di pool di task periodici con periodi molto diversi tra loro. In queste condizioni è necessario scegliere tempi di round molto bassi, cosa che causa un impatto sull'overhead di scheduling. Il contributo di questa tesi è quello di migliorare le performance di I+PI in queste condizioni, riprogettando lo schema di controllo e traendo vantaggio dalle caratteristiche di un kernel tickless. In questi kernel, il sottosistema temporale è progettato in modo aperiodico, generando interrupt solo quando richiesto invece di avere interrupt ad un periodo fisso. Le performance del nuovo scheduler e del kernel tickless sono state verificate tramite un'opportuna campagna sperimentale. I risultati mostrano come le performance del nuovo scheduler siano strettamente superiori allo scheduler I+PI originale, e migliori di EDF in alcuni casi. Mostreremo che il nuovo approccio è un ottimo candidato in applicazioni real-time con o senza deadline e senza imporre una particolare simmetria sul modello di arrivo dei task.