ORIGINAL

Abstract

Since its first implementation in 1970s, multi-programming system abstraction provided by operating system kernels has been a crucial part of many digital systems. While the first computers had only a handful of almost always cooperative tasks to be scheduled, nowadays kernels in typical household computers schedule 100s and 1000s of processes and need to provide access and safety guarantees to each one regardless of the others' actions. This exponential growth has been possible partly due to the Moor's Law, advances in hardware protection mechanisms and partly due to more advanced scheduling algorithms.

In the growing IoT world the effect of Moor's Law is minimal and hardware protection is often non-existent because of cost and resource constraints while a safe multi-programming environment is still necessary since IoT gadgets are becoming software platforms rather than single purpose devices. Tock and other embedded operating systems address many of the safety and isolation constraints through programming language level protection mechanisms. Currently, however, the Tock trusted codebase includes the scheduling algorithm inside the kernel thereby exposing the whole system to potential vulnerabilities originating from complex scheduling algorithms.

The aim of this project is to explore, propose and evaluate approaches for a safe scheduler interface that will not require the scheduler implementation to be trusted by the applications. The project proposes designs for an abstract scheduler interface in the kernel that provides a safe abstraction with minimal overhead to scheduling algorithm developer. Unlike the PC world, IoT devices are quite heterogeneous thus may have wildly different hardware capabilities and scheduling goals. So the paper also presents a survey of most common scheduling algorithms used in embedded systems and designs the abstract interface to fit most of these schedulers.