Control-Based Operating System Design describes the application of system- and control-theoretical methods to the design of computer operating system components. It argues that computer operating system components should not be first 'designed' and then 'endowed with control', but rather when possible conceived from the outset as controllers, synthesised and assessed in the system-theoretical world of dynamic models, and then realised as control algorithms. Doing so is certainly a significant perspective shift with respect to current practices in operating system design, but the payoff is significant too. In some sense, adopting the suggested attitude means viewing computing systems as cyber-physical ones, where the operating system plays the computational role, the physical elements are the managed resources, and the various (control) functionalities to be realised, interact and co-operate as a network. The book includes both a theoretical treatment of the usefulness of the approach, and the description of a complete implementation in the form of Miosix, a microcontroller kernel made available as free software.
Inspec keywords: resource allocation; control system synthesis; scheduling; operating system kernels; predictive control; power aware computing
Other keywords: model identification; control-based solution; control technique; design methodology; power-aware resource management; control-based design attitude; scheduler design; general dynamic model; control theory; Miosix kernel; historical analysis; operating system; resource allocation; cyberphysical system; high-level viewpoint; memory management; task scheduling; model predictive control; systems theory
Subjects: Operating systems; Control system analysis and synthesis methods; General and management topics; Optimal control
In a few words, the operating system takes care of making the hardware available to the application software in an orderly manner. It manages the file system, the memory, the network and the various peripherals, coordinates the execution of the different application programs running in multitasking, guarantees that each of them can access the needed resources by suitably resolving conflicts, and performs numerous other tasks that it would be lengthy and inessential to list in this paper.
This paper provides the barely essential system-theoretical foundations. Basically, its goal is to introduce the notion of dynamic system and one of its simplest specialisations, namely the discrete-time linear time-invariant case. To overcome such a problem, the choice was made to provide just the most important ideas in a manner deliberately abstracted from their utilisation, with just some proof sketches when relevant, and having the sole purpose of maintaining a consistent treatise.
This paper starts giving the considerations expressed in Section 1.2 a mathematical sense. A control system is composed of a controlled system, or plant, and a controller. Most often the latter senses some quantities from the former, and decides what actions to take based on said measurements, and some specification of the desired behaviour. The standard control design procedure is to build a model for P in the form of a dynamic system, then obtain a model in the same form for C and finally turn the latter into control algorithms.
This paper provides knowledge of the basic control-related concepts required in the following. Given a dynamic system, one may want its output to evolve over time in a certain manner. Most frequently this means desiring that a prescribed trajectory be followed, or that the system motion minimise some cost function depending on output and/or state and possibly input, or any combination thereof, although here it shall restrict the scope to cases in which a reference output trajectory needs following. To achieve the desired goal, the system to be controlled must be conveniently coupled to some other system, devoted to suitably determining its input. The former system is termed the controlled system or - for traditional reasons - the plant, the latter the controller, and the compound of the two the control system. The most typical control problem is to determine the controller given the controlled system and the specifications.
This paper presents the development of a model and a control policy for the scheduling problem. To simplify the treatise, as anticipated, in the following only a single-processor case is taken into account; however, the considerations introduced herein hold also in the case of multi-core computing systems. The scheduling problem is entirely treated using the class of discrete-time dynamic systems as the main modelling instrument. The general model obtained can be seen as a switching system; however, simplifying the model and representing only the necessary involved quantities, allows to exploit even simpler modelling frameworks like the one of linear time-invariant systems. This is herein used to develop an entirely new scheduler. The devised scheduler is implemented on a microcontroller kernel, and some benchmark are shown to validate the design approach. Also, the problem is considered of providing the scheduler with a configuration interface that is `friendly' for the typical system administrator, who in general has little (if any) knowledge of the control theory.
Besides CPU time, a very important resource to be managed by an operating system is memory, as for an effective operation it is necessary that each process, and the operating system itself, have the required memory available at any given time. Modern general-purpose operating systems manage memory through a paging mechanism, and reserve a swap space on disk to allow the pool of running processes to collectively access more memory than the available RAM, creating a virtual memory system. Therefore, the general term 'memory' actually refers to two entities, namely physical memory (RAM) and swap space. The memory management activity is generally devoted to a software kernel allocator, that interacts on one side with the running processes, and on the other with a hardware Memory Management Unit (MMU), with the overall goal of satisfying the systems' memory needs by means of RAM and swap space. To support this claim, it is interesting to briefly outline how the typical memory management systems work, and then review some of the milestones of the consolidation of such a design.
This chapter presents more advanced control techniques that will be used in the following. In particular, it presents the main results on Model Predictive Control (MPC). The main concepts related to model identification and adaptive control are presented respectively. The purpose of this paper is to introduce the reader to the basic concepts and terminology related to those control techniques.
The scheduling problem, presented in this paper, can be cast into resource allocation, as the resource to be distributed among the tasks is the CPU time. Keeping this example in mind, the resource allocation problem can be divided into two classes. 1. Resource-resource, where the control action amounts to allocate a resource and the objective is given by some properties of said distribution (e.g., fairness in scheduling) 2. Resource-work, where still the control action is the allocation of a resource, but the issue is how much 'useful work' - whatever is meant for that - the application does with that resource.
After scheduling, memory management and resource allocation, the paper considers another application of the proposed design approach, namely that aimed at realising 'power awareness'. Such a capability is of particular relevance nowadays, since operating systems run on a variety of devices that are not designed for a single purpose, but rather host different applications, each with its own requirements. In this context, an incorrect use of the functionalities made available by the host architecture could easily result in an undue power consumption, or even in the inability of satisfying the applications' needs. In a battery-operated device the relevance of the mentioned problem is apparent, and also larger systems can be affected. In the former case the energies coming into play are small, and the main issue is battery life, in the latter the same energies are instead relevant, and the main concern is their cost. Given also the need for an operating system to scale on differently sized architectures, which is nowadays another important characteristic in a view to application portability and user experience uniformity, a unitary framework to cast the power awareness problem into, is thus highly desirable.
The Miosix kernel is released as free software within the terms of the GNU General Public License version 2 (GPLv2). The motivations for the introduction of a new kernel are presented in this paper. Then, the requirements that led to its design choices are discussed. Some words are subsequently spent illustrating the kernel architecture, and in particular its scheduling API (Application Program Interface).
This paper started out by stating that in the design of operating systems a perspective shift would be beneficial, and that a deeper and more pervasive use of system and control-theoretical concepts can provide the necessary background and modus operandi. The aim is to bridge the gap between the 'parallel lives' of the computer science and the control communities. This is however attempted in a novel way, i.e., by adopting a fully control-theoretical attitude right from the design stage of computing system components. Given that, we think that a few words on future perspectives, thus possible research directions, are now in order.
This appendix contains the programs used to perform some of the simulations presented in this book. They are implemented using Scilab, a high-level programming language oriented towards numerical computation. Interpreters are available as free software, for Linux, Windows and Mac OS X, while an introduction to the language can be found in Reference 94. The readers are encouraged to try these programs, the source code of which can also be found by navigating the authors' homepages, and use them as a starting point to learn about simulation of dynamic systems.