QoS Management Through Adaptive Reservations

Reservation based (RB) scheduling is a class of scheduling algorithms that is well-suited for a large class of soft real-time applications. They are based on a bandwidth abstraction, meaning that a task is given the illusion of executing on a dedicated slower processor. In this context, a crucial design issue is deciding the bandwidth that each task should receive. The point we advocate is that, in presence of large fluctuations on the computation requirements of the tasks, it can be a beneficial choice to dynamically adapt the bandwidth based on QoS measurements and on the subsequent application of feedback control (adaptive reservations).In this paper, we present two novel contributions to this research area. First, we propose three new control algorithms inspired to the ideas of stochastic control. Second, we present a flexible and modular software architecture for adaptive reservations. An important feature of this architecture is that it is realised by means of a minimally invasive set of modifications to the Linux kernel.This work has been partially supported by the European OCERA IST-2001-35102 and RECSYS IST-2001-32515 projects.Luca Abeni is a Ph.D. in Computer Engineering at the Scuola Superiore SantAnna of Pisa (Italy). He graduated in Computer Engineering at the University of Pisa in 1998, and received a Ph.D. in Computer Engineering at the Scuola SuperioreS. Anna of Pisa in 2002. During 2000 he was a visiting student at the Carnegie Mellon University (Pittsburgh, PA), working with Prof. Ragunathan Rajkumar on resource reservation algorithms for real-time kernels. During 2001 he was a visiting student a Oregon Graduate Institute (Portland, OR) working with Prof. Jonathan Walpole on the support for time-sensitive applications in the Linux kernel. He has been working in Broadsat S.R.L. since 2003, developing audio/video streaming solutions and IPTV applications.Tommaso Cucinotta got the degree in Computer Engineering at the University of Pisa (Italy) in 2000. He got the Ph.D. inComputer Engineering at the Scuola Superiore SantAnna(SSSA) of Pisa in 2004 with a thesis titled Issues in authentication by means of smart-card devices. He held a course on cryptography in the International Master on Software Engineering organized at SSSA in 2002 and 2004. At the moment, he cooperates in research activities at the Scuola Superiore S. Anna in the areas of computer security and Quality of Service control for soft real-time systems.Giuseppe Lipari graduated in Computer Engineering at the University of Pisa in 1996, and received the Ph.D. degree in Computer Engineering from Scuola Superiore SantAnna in 2000. During 1999, he was avisiting student at University of North Carolina at Chapel Hill, collaborating with professor S.K. Baruah and professor K. Jeffay on real-time scheduling. Currently, he is assistant professor of Operating Systems with Scuola Superiore SantAnna. His main research activities are in real-time scheduling theory and its application to real-time operating systems, soft real-time systems for multimedia applications and component-based real-time systems.Luca Marzario is a Ph.D. student in Computer Engineering at the Scuola Superiore S. Anna of Pisa, Italy. In 2002, he graduated in Computer Engineering at University of Pisa. His main research interest include real-time systems scheduling, aperiodic service mechanism, feedback-scheduling, QoS in multimedia systems, Linux kernel and Real Time Linux executives (RTAI, RTLinux).Luigi Palopoli graduated in Control Engineering at the University of Pisa in 1998 and received his Ph.D. degree in Computer Engineering in 2002 from the Scuola Superiore S. Anna, Pisa. During 2001 he was a visiting scholar at the Department of EECS, University of California at Berkeley, where he worked on design techniques for real-time controllers under the supervision of Professor Alberto Sangiovanni-Vincentelli. He is currently Assistant Professor at the Scuola Superiore S. Anna (Pisa). His main research activities include Quality of Service control, control of systems under communication and computation constraints and design of embedded systems.     

Feasibility Analysis of Real-Time Periodic Tasks with Offsets

The problem of feasibility analysis of asynchronous periodic task sets, where tasks can have an initial offset, is known to be co-NP-complete in the strong sense. A sufficient pseudo-polynomial test has been proposed by Baruah, Howell and Rosier, which consists in analyzing the feasibility of the corresponding synchronous task set (i.e. all offsets are set equal to 0). If the test gives a positive result, then the original asynchronous task set is feasible; else, no definitive answer can be given. In many cases, this sufficient test is too pessimistic, i.e. it gives no response for many feasible task sets.In this paper, we present a new sufficient pseudo-polynomial test for asynchronous periodic task sets. Our test reduces the pessimism by explicitely considering the offsets in deriving a small set of critical arrival patterns. We show, trough a set of extensive simulations, that our test outperforms the previous sufficient test.Rodolfo Pellizzoni received the Laurea degree in Computer Engineering from the Università di Pisa and the Diploma degree from the Scuola Superiore SantAnna, in 2004. He is presently a Ph.D. student in the Department of Computer Science at the University of Illinois at Urbana-Champaign. His main research interests are in real-time operating systems, scheduling theory and resource-allocation in distributed and multiprocessor systems.Giuseppe Lipari graduated in Computer Engineering at the University of Pisa in 1996, and received the Ph.D. degree in Computer Engineering from Scuola Superiore SantAnna in 2000. During 1999, he was a visiting student at University of North Carolina at Chapel Hill, collaborating with professor S.K. Baruah and professor K. Jeffay on real-time scheduling. Currently, he is assistant professor of Operating Systems with Scuola Superiore SantAnna. His main research activities are in real-time scheduling theory and its application to real-time operating systems, soft real-time systems for multimedia applications and component-based real-time systems.     

Algebraic and functional specification of an interactive serializable database interface

Summary A formal functional specification of a serializable interface for an interactive database is given and refined into two different versions with distinct strategies for solving read/write conflicts. The formalization is based on techniques of algebraic specification for defining the basic data structures and functional system specification by streams and stream processing functions for defining the properties concerning interaction. It is especially demonstrated how different specification techniques can be used side by side. Manfred Broy finished his studies with the Diplom in Mathematics and Computer Science at the Technical University of Munich. Till 1983 he was research and teaching assistant at the Institut für Informatik and the Sonderforschungsbereich 49 Programmiertechnik. At the Technical University of Munich he also did his Ph.D. (in February 1980 with the subject: Transformation parallel ablaufender Programme) and qualified as an university lecturer (in 1982 with the subject: A Theory for Nondeterminism, Parallelism, Communication and Concurrency). In April 1983 he became a Full Professor for Computer Science at the Faculty of Mathematics and Computer Science at the University of Passau. Since October 1989 he has been Full Professor for Computer Science at the Technical University of Munich. His fields of interests are: Programming languages, program development, programming methodology and distributed systems.This work was supported by the DFG Project Transformation paralleler Programme and by the Sonderforschungsbereich 342 Werkzeuge und Methoden für die Nutzung paralleler Architekturen     

A Philosophical Approach to the Concept of Data Model: Is a Data Model, in Fact, a Model?

The design of the database is crucial to the process of designing almost any Information System (IS) and involves two clearly identifiable key concepts: schema and data model, the latter allowing us to define the former. Nevertheless, the term model is commonly applied indistinctly to both, the confusion arising from the fact that in Software Engineering (SE), unlike in formal or empirical sciences, the notion of model has a double meaning of which we are not always aware. If we take our idea of model directly from empirical sciences, then the schema of a database would actually be a model, whereas the data model would be a set of tools allowing us to define such a schema.The present paper discusses the meaning of model in the area of Software Engineering from a philosophical point of view, an important topic for the confusion arising directly affects other debates where model is a key concept. We would also suggest that the need for a philosophical discussion on the concept of data model is a further argument in favour of institutionalizing a new area of knowledge, which could be called: Philosophy of Engineering.     

A project for Latin Lexicography: 2. A Latin morphological analyzer

This article describes a second aspect of the Project for Latin Lexicography (see previous article). We here concentrate on two aspects of the project. First, we describe the morphological analyzer, which comprises a base dictionary, a table of suffixes, a table of endings and a table of postfixes. Second, we describe the lemmatization module, which operates by reference to a series of grammatical codes or information given for the base, and reference codes. Giuseppe Cappelli is a program analyst working at the Institute for Computational Linguistics of the National Research Council of Pisa. He has written the software for the morphosyntactic analyzer of the Spanish language. He has also written the software for the morphological analyser of the Latin language in collaboration with the Classics Department of Turin University. At present, Cappelli is involved in the study of child language. His publications include (with M.N. Catarsi, A. Saba and D. Ratti) A Morphosyntactic analyser for Spanish, Computers in Literary and Linguistic Research, Pisa: Giardini Editori, 1982; and (with A. Bozzi) A Latin Morphological Analyser, in Data Base Oriented Source Editions, Kalamazoo, Michigan, 1988. Andrea Bozzi is a researcher at the Institute for Computational Linguistics of the National Research Council of Pisa. She has been involved in the automatic processing of late Latin translations of Hypocratical texts, from a lexicographical point of view. She has also implemented a morphological analyzer of the Latin language. Her publications include Note di lessicografia ippocratica. Il trattato sulle arie, le acque, i luoghi, Roma, 1982, and Il trattamento delle variante nello spoglio elttronico di un testo. Una prova sui Carmina di Claudiano, in MD, 16 (1986),155–79.     

The Professor Doth Protest Too Much, Methinks: Problems with the Foster ”Response“

In Response to Elliott and Valenza, 'And Then There Were None', (1996) Donald Foster has taken strenuous issue with our Shakespeare Clinic's final report, which concluded that none of the testable Shakespeare claimants, and none of the Shakespeare Apocrypha poems and plays – including Funeral Elegy by W.S. – match Shakespeare. Though he seems to accept most of our exclusions – notably excepting those of the Elegy and A Lover's Complaint – he believes that our methodology is nonetheless fatally flawed by worthless figures ... wrong more often than right, rigorous cherry–picking, playing with a stacked deck, and conveniently exil[ing] ... inconvenient data. He describes our tests as foul vapor and methodological madness.We believe that this criticism is seriously overdrawn, and that our tests and conclusions have emerged essentially intact. By our count, he claims to have found 21 errors of consequence in our report. Only five of these claims, all trivial, have any validity at all. If fully proved, they might call for some cautions and slight refinements for five of our 54 tests, but in no case would they come close to invalidating the questioned test. The remaining 49 tests are wholly intact. Total erosion of our findings from the Foster critique could amount, at most, to half of one percent. None of his accusations of cherry–picking, deck–stacking, and evidence–ignoring are substantiated.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Sometime = always + recursion ≡ always on the equivalence of the intermittent and invariant assertions methods for proving inevitability properties of programs

Summary We propose and compare two induction principles called always and sometime for proving inevitability properties of programs. They are respective formalizations and generalizations of Floyd invariant assertions and Burstall intermittent assertions methods for proving total correctness of sequential programs whose methodological advantages or disadvantages have been discussed in a number of previous papers. Both principles are formalized in the abstract setting of arbitrary nondeterministic transition systems and illustrated by appropriate examples. The sometime method is interpreted as a recursive application of the always method. Hence always can be considered as a special case of sometime. These proof methods are strongly equivalent in the sense that a proof by one induction principle can be rewritten into a proof by the other one. The first two theorems of the paper show that an invariant for the always method can be translated into an invariant for the sometime method even if every recursive application of the later is required to be of finite length. The third and main theorem of the paper shows how to translate an invariant for the sometime method into an invariant for the always method. It is emphasized that this translation technique follows the idea of transforming recursive programs into iterative ones. Of course, a general translation technique does not imply that the original sometime invariant and the resulting always invariant are equally understandable. This is illustrated by an example.     

Modelling structures in generic space, a condition for adaptiveness of monitoring cognitive agent

The adaptiveness of agents is one of the basic conditions for the autonomy. This paper describes an approach of adaptiveness forMonitoring Cognitive Agents based on the notion of generic spaces. This notion allows the definition of virtual generic processes so that any particular actual process is then a simple configuration of the generic process, that is to say a set of values of parameters. Consequently, generic domain ontology containing the generic knowledge for solving problems concerning the generic process can be developed. This lead to the design of Generic Monitoring Cognitive Agent, a class of agent in which the whole knowledge corpus is generic. In other words, modeling a process within a generic space becomes configuring a generic process and adaptiveness becomes genericity, that is to say independence regarding technology. In this paper, we present an application of this approach on Sachem, a Generic Monitoring Cognitive Agent designed in order to help the operators in operating a blast furnace. Specifically, the NeuroGaz module of Sachem will be used to present the notion of a generic blast furnace. The adaptiveness of Sachem can then be noted through the low cost of the deployment of a Sachem instance on different blast furnaces and the ability of NeuroGaz in solving problem and learning from various top gas instrumentation.