Slotted wiDom: schedulability analysis and its experimental validation

WiDom is a wireless prioritized medium access control protocol which offers a very large number of priority levels. Hence, it brings the potential to employ non-preemptive static-priority scheduling and schedulability analysis for a wireless channel assuming that the overhead of WiDom is modeled properly. One schedulability analysis for WiDom has already been proposed but recent research has created a new version of WiDom (we call it: Slotted WiDom) with lower overhead and for this version of WiDom no schedulability analysis exists. In this paper we propose a new schedulability analysis for slotted WiDom and extend it to work also for message streams with release jitter. We have performed experiments with an implementation of slotted WiDom on a real-world platform (MicaZ). We find that for each message stream, the maximum observed response time never exceeds the calculated response time and hence this corroborates our belief that our new scheduling theory is applicable in practice.

New schedulability analysis for WiDom

WiDom is a wireless prioritized medium access control (MAC) protocol which offers a very large number of priority levels. Hence, it brings the potential for employing non-preemptive static-priority scheduling and schedulability analysis for a wireless channel assuming that the overhead of WiDom is modeled properly. One schedulability analysis for WiDom has already been proposed but recent research has created a new version of WiDom with lower overhead (we call it: WiDom with a master node) and for this version of WiDom no schedulability analysis exists. Also, common to the previously proposed schedulability analyses for WiDom is that they cannot analyze message streams with release jitter. Therefore, in this paper we propose a new schedulability analysis for WiDom (with a master node). We also extend the WiDom analyses (with and without master node) to work also for message streams with release jitter.

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.

Adapting mode switches into the hierarchical scheduling

Mode switches are used to partition the system’s behavior into different modes to reduce the complexity of large embedded systems. Such systems operate in multiple modes in which each one corresponds to a specific application scenario; these are called Multi-Mode Systems (MMS). A different piece of software is normally executed for each mode. At any given time, the system can be in one of the predefined modes and then be switched to another as a result of a certain condition. A mode switch mechanism (or mode change protocol) is used to shift the system from one mode to another at run-time. In this thesis we have used a hierarchical scheduling framework to implement a multi-mode system called Multi-Mode Hierarchical Scheduling Framework (MMHSF). A two-level Hierarchical Scheduling Framework (HSF) has already been implemented in an open source real-time operating system, FreeRTOS, to support temporal isolation among real-time components. The main contribution of this thesis is the extension of the HSF featuring a multimode feature with an emphasis on making minimal changes in the underlying operating system (FreeRTOS) and its HSF implementation. Our implementation uses fixed-priority preemptive scheduling at both local and global scheduling levels and idling periodic servers. It also now supports different modes of the system which can be switched at run-time. Each subsystem and task exhibit different timing attributes according to mode, and upon a Mode Change Request (MCR) the task-set and timing interfaces of the entire system (including subsystems and tasks) undergo a change. A Mode Change Protocol specifies precisely how the system-mode will be changed. However, an application may not only need to change a mode but also a different mode change protocol semantic. For example, the mode change from normal to shutdown can allow all the tasks to be completed before the mode itself is changed, while changing a mode from normal to emergency may require aborting all tasks instantly. In our work, both the system mode and the mode change protocol can be changed at run-time. We have implemented three different mode change protocols to switch from one mode to another: the Suspend/resume protocol, the Abort protocol, and the Complete protocol. These protocols increase the flexibility of the system, allowing users to select the way they want to switch to a new mode. The implementation of MMHSF is tested and evaluated on an AVR-based 32 bit board EVK1100 with an AVR32UC3A0512 micro-controller. We have tested the behavior of each system mode and for each mode change protocol. We also provide the results for the performance measures of all mode change protocols in the thesis. RESUMEN Los conmutadores de modo son usados para particionar el comportamiento del sistema en diferentes modos, reduciendo así la complejidad de grandes sistemas empotrados. Estos sistemas tienen multiples modos de operación, cada uno de ellos correspondiente a distintos escenarios y para distintas aplicaciones; son llamados Sistemas Multimodales (o en inglés “Multi-Mode Systems” o MMS). Normalmente cada modo ejecuta una parte de código distinto. En un momento dado el sistema, que está en un modo concreto, puede ser cambiado a otro modo distinto como resultado de alguna condicion impuesta previamente. Los mecanismos de cambio de modo (o protocolos de cambio de modo) son usados para mover el sistema de un modo a otro durante el tiempo de ejecución. En este trabajo se ha usado un modelo de sistema operativo para implementar un sistema multimodo llamado MMHSF, siglas en inglés correspondientes a (Multi-Mode Hierarchical Scheduling Framework). Este sistema está basado en el HSF (Hierarchical Scheduling Framework), un modelo de sistema operativo con jerarquía de dos niveles, implementado en un sistema operativo en tiempo real de libre distribución llamado FreeRTOS, capaz de permitir el aislamiento temporal entre componentes. La principal contribución de este trabajo es la ampliación del HSF convirtiendolo en un sistema multimodo realizando los cambios mínimos necesarios sobre el sistema operativo FreeRTOS y la implementación ya existente del HSF. Esta implementación usa un sistema de planificación de prioridad fija para ambos niveles de jerarquía, ocupando el tiempo entre tareas con un “modo reposo”. Además el sistema es capaz de cambiar de un modo a otro en tiempo de ejecución. Cada subsistema y tarea son capaces de tener distintos atributos de tiempo (prioridad, periodo y tiempo de ejecución) en función del modo. Bajo una demanda de cambio de modo (Mode Change Request MCR) se puede variar el set de tareas en ejecución, así como los atributos de los servidores y las tareas. Un protocolo de cambio de modo espeficica precisamente cómo será cambiado el sistema de un modo a otro. Sin embargo una aplicación puede requerir no solo un cambio de modo, sino que lo haga de una forma especifica. Por ejemplo, el cambio de modo de “normal” a “apagado” puede permitir a las tareas en ejecución ser finalizadas antes de que se complete la transición, pero sin embargo el cambio de “normal” a “emergencia” puede requerir abortar todas las tareas instantaneamente. En este trabajo ambas características, tanto el modo como el protocolo de cambio, pueden ser cambiadas en tiempo de ejecución, pero deben ser previamente definidas por el desarrollador. Han sido definidos tres protocolos de cambios: el protocolo “suspender/continuar”, protocolo “abortar” y el protocolo “completar”. Estos protocolos incrementan la flexibilidad del sistema, permitiendo al usuario seleccionar de que forma quieren cambiar hacia el nuevo modo. La implementación del MMHSF ha sido testada y evaluada en una placa AVR EVK1100, con un micro-controlador AVR32UC3A0. Se ha comprobado el comportamiento de los distintos modos para los distintos protocolos, definidos previamente. Como resultado se proporcionan las medidades de rendimiento de los distintos protocolos de cambio de modo.

Realization of an Optimal Schedule for the Two-machine Flow-Shop with Interval Job Processing Times

Non-preemptive two-machine flow-shop scheduling problem with uncertain processing times of n jobs is studied. In an uncertain version of a scheduling problem, there may not exist a unique schedule that remains optimal for all possible realizations of the job processing times. We find necessary and sufficient conditions (Theorem 1) when there exists a dominant permutation that is optimal for all possible realizations of the job processing times. Our computational studies show the percentage of the problems solvable under these conditions for the cases of randomly generated instances with n ≤ 100 . We also show how to use additional information about the processing times of the completed jobs during optimal realization of a schedule (Theorems 2 – 4). Computational studies for randomly generated instances with n ≤ 50 show the percentage of the two- machine flow-shop scheduling problems solvable under the sufficient conditions given in Theorems 2 – 4.

Laxity dynamics and LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with a smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, little work has been made to illuminate its characteristics upon multiprocessor platforms. In this paper, we identify the dynamics of laxity from the system’s viewpoint and translate the dynamics into LLF multiprocessor schedulability analysis. More specifically, we first characterize laxity properties under LLF scheduling, focusing on laxity dynamics associated with a deadline miss. These laxity dynamics describe a lower bound, which leads to the deadline miss, on the number of tasks of certain laxity values at certain time instants. This lower bound is significant because it represents invariants for highly dynamic system parameters (laxity values). Since the laxity of a task is dependent of the amount of interference of higher-priority tasks, we can then derive a set of conditions to check whether a given task system can go into the laxity dynamics towards a deadline miss. This way, to the author’s best knowledge, we propose the first LLF multiprocessor schedulability test based on its own laxity properties. We also develop an improved schedulability test that exploits slack values. We mathematically prove that the proposed LLF tests dominate the state-of-the-art EDZL tests. We also present simulation results to evaluate schedulability performance of both the original and improved LLF tests in a quantitative manner.

LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.

Queues with Customer Induced Interruption

In this thesis we have introduced and studied the notion of self interruption of service by customers. Service interruption in queueing systems have been extensively discussed in literature (see, Krishnamoorthy, Pramod and Chakravarthy [38]) for the most recent survey. So far all work reported deal with cases in which service interruptions are generated by sources other than customers. However, there are situations where interruptions are due to the customers rather than the system. Such situations are especially arise at doctors clinic, banks, reservation counter etc. Our attempt is to quantify a few of such problems. Systematically we have proceed from single server queue (in Chapter 2) to multi-server queues (Chapter 3). In Chapte 4, we have studied a very general multiserver queueing model with service interruption and protection of service phases. We also introduced customer interruption in a retrial setup (in Chapter 5). All models (from Chapter 2 to Chapter 4) that were analyzed involve 'non-preemptive priority' for interrupted customers where as in the model discussed in Chapter 5 interruption of service by customers is not encouraged. So the interrupted customers cannot access the server as long as there are primary customers in the system. In Chapter 5 we have obtained an explicit expression for the stability condition of the system. In all models analyzed in this thesis, we have assumed that no more than one interruption is allowed for a customer while in service. Since the models are not analytically tractable, a large number of numerical illustrations were given in each chapter it illustrate the working of the systems. We can extend the models discussed in this thesis to several directions. For example some of the models can be analyzed with both server induced and customer induced interruptions the results for which are not available till date. Another possible extension of work is to the case where there is no bound on the number of interruptions a customer is permitted to have before service completion. More complex is the case where a customer is permitted to have a nite number (K ≥ 2) of We can extend the models discussed in this thesis to several directions.

QoS management in smart grids: a Markovian approach

In Smart Grids, a variety of new applications are available to users of the electrical system (from consumers to the electric system operators and market operators). Some applications such as the SCADA systems, which control generators or substations, have consequences, for example, with a communication delay. The result of a failure to deliver a control message due to noncompliance of the time constraint can be catastrophic. On the other hand, applications such as smart metering of consumption have fewer restrictions. Since each type of application has different quality of service requirements (importance, delay, and amount of data to transmit) to transmit its messages, the policy to control and share the resources of the data communication network must consider them. In this paper Markov Decision Process Theory is employed to determine optimal policies to explore as much as possible the availability of throughput in order to transmit all kinds of messages, considering the quality of service requirements defined to each kind of message. First a non-preemptive model is formulated and after that a preemptive model is derived. Numerical results are used to compare FIFO, non-preemptive and preemptive policies.

Operating System Contribution to Composable Timing Behaviour in High-Integrity Real-Time Systems

The development of High-Integrity Real-Time Systems has a high footprint in terms of human, material and schedule costs. Factoring functional, reusable logic in the application favors incremental development and contains costs. Yet, achieving incrementality in the timing behavior is a much harder problem. Complex features at all levels of the execution stack, aimed to boost average-case performance, exhibit timing behavior highly dependent on execution history, which wrecks time composability and incrementaility with it. Our goal here is to restitute time composability to the execution stack, working bottom up across it. We first characterize time composability without making assumptions on the system architecture or the software deployment to it. Later, we focus on the role played by the real-time operating system in our pursuit. Initially we consider single-core processors and, becoming less permissive on the admissible hardware features, we devise solutions that restore a convincing degree of time composability. To show what can be done for real, we developed TiCOS, an ARINC-compliant kernel, and re-designed ORK+, a kernel for Ada Ravenscar runtimes. In that work, we added support for limited-preemption to ORK+, an absolute premiere in the landscape of real-word kernels. Our implementation allows resource sharing to co-exist with limited-preemptive scheduling, which extends state of the art. We then turn our attention to multicore architectures, first considering partitioned systems, for which we achieve results close to those obtained for single-core processors. Subsequently, we shy away from the over-provision of those systems and consider less restrictive uses of homogeneous multiprocessors, where the scheduling algorithm is key to high schedulable utilization. To that end we single out RUN, a promising baseline, and extend it to SPRINT, which supports sporadic task sets, hence matches real-world industrial needs better. To corroborate our results we present findings from real-world case studies from avionic industry.

Randomized Push-Out Mechanisms in Priority Queuing and their Probability Characteristics

2002 Mathematics Subject Classification: 60K25.

'Enhanced Direct and Indirect Genetic Algorithm Approaches for a Mall Layout and Tenant Selection Problem'

During our earlier research, it was recognised that in order to be successful with an indirect genetic algorithm approach using a decoder, the decoder has to strike a balance between being an optimiser in its own right and finding feasible solutions. Previously this balance was achieved manually. Here we extend this by presenting an automated approach where the genetic algorithm itself, simultaneously to solving the problem, sets weights to balance the components out. Subsequently we were able to solve a complex and non-linear scheduling problem better than with a standard direct genetic algorithm implementation.

Enhanced Direct and Indirect Genetic Algorithm Approaches for a Mall Layout and Tenant Selection Problem

During our earlier research, it was recognised that in order to be successful with an indirect genetic algorithm approach using a decoder, the decoder has to strike a balance between being an optimiser in its own right and finding feasible solutions. Previously this balance was achieved manually. Here we extend this by presenting an automated approach where the genetic algorithm itself, simultaneously to solving the problem, sets weights to balance the components out. Subsequently we were able to solve a complex and non-linear scheduling problem better than with a standard direct genetic algorithm implementation.

'Enhanced Direct and Indirect Genetic Algorithm Approaches for a Mall Layout and Tenant Selection Problem'

During our earlier research, it was recognised that in order to be successful with an indirect genetic algorithm approach using a decoder, the decoder has to strike a balance between being an optimiser in its own right and finding feasible solutions. Previously this balance was achieved manually. Here we extend this by presenting an automated approach where the genetic algorithm itself, simultaneously to solving the problem, sets weights to balance the components out. Subsequently we were able to solve a complex and non-linear scheduling problem better than with a standard direct genetic algorithm implementation.

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.