A framework for the response time analysis of fixed-priority tasks with stochastic inter-arrival times

Real-time scheduling usually considers worst-case values for the parameters of task (or message stream) sets, in order to provide safe schedulability tests for hard real-time systems. However, worst-case conditions introduce a level of pessimism that is often inadequate for a certain class of (soft) real-time systems. In this paper we provide an approach for computing the stochastic response time of tasks where tasks have inter-arrival times described by discrete probabilistic distribution functions, instead of minimum inter-arrival (MIT) values.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Job phasing aware preemption deferral

Preemptions account for a non-negligible overhead during system execution. There has been substantial amount of research on estimating the delay incurred due to the loss of working sets in the processor state (caches, registers, TLBs) and some on avoiding preemptions, or limiting the preemption cost. We present an algorithm to reduce preemptions by further delaying the start of execution of high priority tasks in fixed priority scheduling. Our approaches take advantage of the floating non-preemptive regions model and exploit the fact that, during the schedule, the relative task phasing will differ from the worst-case scenario in terms of admissible preemption deferral. Furthermore, approximations to reduce the complexity of the proposed approach are presented. Substantial set of experiments demonstrate that the approach and approximations improve over existing work, in particular for the case of high utilisation systems, where savings of up to 22% on the number of preemption are attained.

Response Time Analysis of Slotted WiDOM in Noisy Wireless Channels

International Conference on Emerging Technologies and Factory Automation (ETFA 2015), Industrial Communication Technologies and Systems, Luxembourg, Luxembourg.

Evolutionary computing in search-based software engineering

This master’s thesis aims to study and represent from literature how evolutionary algorithms are used to solve different search and optimisation problems in the area of software engineering. Evolutionary algorithms are methods, which imitate the natural evolution process. An artificial evolution process evaluates fitness of each individual, which are solution candidates. The next population of candidate solutions is formed by using the good properties of the current population by applying different mutation and crossover operations. Different kinds of evolutionary algorithm applications related to software engineering were searched in the literature. Applications were classified and represented. Also the necessary basics about evolutionary algorithms were presented. It was concluded, that majority of evolutionary algorithm applications related to software engineering were about software design or testing. For example, there were applications about classifying software production data, project scheduling, static task scheduling related to parallel computing, allocating modules to subsystems, N-version programming, test data generation and generating an integration test order. Many applications were experimental testing rather than ready for real production use. There were also some Computer Aided Software Engineering tools based on evolutionary algorithms.

Modeling and Analysis of Two-Part Type Manufacturing Systems

This paper presents a model and analysis of a synchronous tandem flow line that produces different part types on unreliable machines. The machines operate according to a static priority rule, operating on the highest priority part whenever possible, and operating on lower priority parts only when unable to produce those with higher priorities. We develop a new decomposition method to analyze the behavior of the manufacturing system by decomposing the long production line into small analytically tractable components. As a first step in modeling a production line with more than one part type, we restrict ourselves to the case where there are two part types. Detailed modeling and derivations are presented with a small two-part-type production line that consists of two processing machines and two demand machines. Then, a generalized longer flow line is analyzed. Furthermore, estimates for performance measures, such as average buffer levels and production rates, are presented and compared to extensive discrete event simulation. The quantitative behavior of the two-part type processing line under different demand scenarios is also provided.

Extensiones a los métodos de planificación de sistemas de tiempo real críticos basados en prioridades

Los sistemas de tiempo real tienen un papel cada vez más importante en nuestra sociedad. Constituyen un componente fundamental de los sistemas de control, que a su vez forman parte de diversos sistemas de ingeniería básicos en actividades industriales, militares, de comunicaciones, espaciales y médicas. La planificación de recursos es un problema fundamental en la realización de sistemas de tiempo real. Su objetivo es asignar los recursos disponibles a las tareas de forma que éstas cumplan sus restricciones temporales. Durante bastante tiempo, el estado de la técnica en relación con los métodos de planificación ha sido rudimentario. En la actualidad, los métodos de planificación basados en prioridades han alcanzado un nivel de madurez suficiente para su aplicación en entornos industriales. Sin embargo, hay cuestiones abiertas que pueden dificultar su utilización. El objetivo principal de esta tesis es estudiar los métodos de planificación basados en prioridades, detectar las cuestiones abiertas y desarrollar protocolos, directrices y esquemas de realización práctica que faciliten su empleo en sistemas industriales. Una cuestión abierta es la carencia de esquemas de realización de algunos protocolos con núcleos normalizados. El resultado ha sido el desarrollo de esquemas de realización de tareas periódicas y esporádicas de tiempo real, con detección de fallos de temporización, comunicación entre tareas, cambio de modo de ejecución del sistema y tratamiento de fallos mediante grupos de recuperación. Los esquemas se han codificado en Ada 9X y se proporcionan directrices para analizar la planificabilidad de un sistema desarrollado con esta base. Un resultado adicional ha sido la identificación de la funcionalidad mínima necesaria para desarrollar sistemas de tiempo real con las características enumeradas. La capacidad de adaptación a los cambios del entorno es una característica deseable de los sistemas de tiempo real. Si estos cambios no estaban previstos en la fase de diseño o si hay módulos erróneos, es necesario modificar o incluir algunas tareas. La actualización del sistema se suele realizar estáticamente y su instalación se lleva a cabo después de parar su ejecución. Sin embargo, hay sistemas cuyo funcionamiento no se puede detener sin producir daños materiales o económicos. Una alternativa es diseñar el sistema como un conjunto de unidades que se pueden reemplazar, sin interferir con la ejecución de otras unidades. Para tal fin, se ha desarrollado un protocolo de reemplazamiento dinámico para sistemas de tiempo real crítico y se ha comprobado su compatibilidad con los métodos de planificación basados en prioridades. Finalmente se ha desarrollado un esquema de realización práctica del protocolo.---ABSTRACT---Real-time systems are very important now a days. They have become a relevant issue in the design of control systems, which are a basic component of several engineering systems in industrial, telecommunications, military, spatial and medical applications. Resource scheduling is a central issue in the development of real-time systems. Its purpose is to assign the available resources to the tasks, in such a way that their deadlines are met. Historically, hand-crafted techniques were used to develop real-time systems. Recently, the priority-based scheduling methods have reached a sufficient maturity level to be feasible its extensive use in industrial applications. However, there are some open questions that may decrease its potential usefulness. The main goal of this thesis is to study the priority-based scheduling methods, to identify the remaining open questions and to develop protocols, implementation templates and guidelines that will make more feasible its use in industrial applications. One open question is the lack of implementation schemes, based on commercial realtime kernels, of some of the protocols. POSIX and Ada 9X has served to identify the services usually available. A set of implementation templates for periodic and sporadic tasks have been developed with provisión for timing failure detection, intertask coraraunication, change of the execution mode and failure handling based on recovery groups. Those templates have been coded in Ada 9X. A set of guidelines for checking the schedulability of a system based on them are also provided. An additional result of this work is the identification of the minimal functionality required to develop real-time systems based on priority scheduling methods, with the above characteristics. A desirable feature of real-time systems is their capacity to adapt to changes in the environment, that cannot be entirely predicted during the design, or to misbehaving software modules. The traditional maintenance techniques are performed by stopping the whole system, installing the new application and finally resuming the system execution. However this approach cannot be applied to non-stop systems. An alternative is to design the system as a set of software units that can be dynamically replaced within its operative environment. With this goal in mind, a dynamic replacement protocol for hard real-time systems has been defined. Its compatibility with priority-based scheduling methods has been proved. Finally, a execution témplate of the protocol has been implemented.

Resource sharing in global fixed-priority preemptive multiprocessor scheduling

In this paper we consider global fixed-priority preemptive multiprocessor scheduling of constrained-deadline sporadic tasks that share resources in a non-nested manner. We develop a novel resource-sharing protocol and a corresponding schedulability test for this system. We also develop the first schedulability analysis of priority inheritance protocol for the aforementioned system. Finally, we show that these protocols are efficient (based on the developed schedulability tests) for a class of priority-assignments called reasonable priority-assignments.

Conjecture about global fixed-priority preemptive multiprocessor scheduling of implicit-deadline sporadic tasks: the utilization bound of SM-US(sqrt(2)-1) is sqrt(2)-1

Consider global fixed-priority preemptive multiprocessor scheduling of implicit-deadline sporadic tasks. I conjecture that the utilization bound of SM-US(√2−1) is √2-1.