Enhancing the real-time capabilities of the Linux Kernel

The mainline Linux Kernel is not designed forhard real-time systems; it only fits the requirements of soft realtimesystems. In recent years, a kernel developer communityhas been working on the PREEMPT-RT patch. This patch(that aims to get a fully preemptible kernel) adds some realtimecapabilities to the Linux kernel. However, in terms ofscheduling policies, the real-time scheduling class of Linux islimited to the First-In-First-Out (SCHED_FIFO) and Round-Robin (SCHED_RR) scheduling policies. These scheduling policiesare however quite limited in terms of realtime performance.Therefore, in this paper, we report one importantcontribution for adding more advanced real-time capabilitiesto the Linux Kernel. Specifically, we describe modificationsto the (PREEMPT-RT patched) Linux kernel to supportreal-time slot-based task-splitting scheduling algorithms. Ourpreliminary evaluation shows that our implementation exhibitsa real-time performance that is superior to the schedulingpolicies provided by the current version of PREMPT-RT. Thisis a significant add-on to a widely adopted operating system.

SPARTS: simulator for power aware and real-time systems

Real-time systems demand guaranteed and predictable run-time behaviour in order to ensure that no task has missed its deadline. Over the years we are witnessing an ever increasing demand for functionality enhancements in the embedded real-time systems. Along with the functionalities, the design itself grows more complex. Posed constraints, such as energy consumption, time, and space bounds, also require attention and proper handling. Additionally, efficient scheduling algorithms, as proven through analyses and simulations, often impose requirements that have significant run-time cost, specially in the context of multi-core systems. In order to further investigate the behaviour of such systems to quantify and compare these overheads involved, we have developed the SPARTS, a simulator of a generic embedded real- time device. The tasks in the simulator are described by externally visible parameters (e.g. minimum inter-arrival, sporadicity, WCET, BCET, etc.), rather than the code of the tasks. While our current implementation is primarily focused on our immediate needs in the area of power-aware scheduling, it is designed to be extensible to accommodate different task properties, scheduling algorithms and/or hardware models for the application in wide variety of simulations. The source code of the SPARTS is available for download at [1].

Comparing the schedulers and power saving strategies with SPARTS

We have developed SPARTS, a simulator of a generic embedded real-time device. It is designed to be extensible to accommodate different task properties, scheduling algorithms and/or hardware models for the wide variety of applications. SPARTS was developed to help the community investigate the behaviour of the real-time embedded systems and to quantify the associated constraints/overheads.

Response Time Analysis for Fixed-Priority Tasks with Multiple Probabilistic Parameters

Demo presented in 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015). 8 to 12, Jun, 2015. La Roche-en-Ardenne, Belgium. Extended abstract.

Avaliação dos mecanismos de concorrência na API do Java 8

As plataformas com múltiplos núcleos tornaram a programação paralela/concorrente num tópico de interesse geral. Diversos modelos de programação têm vindo a ser propostos, facilitando aos programadores a identificação de regiões de código potencialmente paralelizáveis, deixando ao sistema operativo a tarefa de as escalonar dinamicamente em tempo de execução, explorando o maior grau possível de paralelismo. O Java não foge a esta tendência, disponibilizando ao programador um número crescente de bibliotecas de mecanismos de sincronização e paralelização de código. Neste contexto, esta tese apresenta e discute um conjunto de resultados obtidos através de testes intensivos à eficiência de algoritmos de ordenação implementados com recurso aos mecanismos de concorrência da API do Java 8 (Threads, Threadpools, ExecutorService, CountdownLach, ExecutorCompletionService e ForkJoinPools) em sistemas com um número de núcleos variável. Para cada um dos mecanismos, são apresentadas conclusões sobre o seu funcionamento e discutidos os cenários em que o seu uso pode ser rentabilizado de modo a serem obtidos melhores tempos de execução.

A physical activity intervention in a workplace setting

Physical inactivity poses a huge burden on Canada's health care system and is detrimental to the health of Canadians (Katzmarzyk & Janssen, 2004). Walking is a viable option for individuals to become physically active on a daily basis and is in fact the most commonly reported leisure time physical activity. It has been associated with many health benefits including weight loss/weight control, reduced risk of coronary artery disease and diabetes, lowered blood pressure, and improved psychological wellbeing (Brisson & Tudor-Locke, 2004). Specifically, individuals' stage of change, selfefficacy and health related quality of life (HRQL) are three psychological constructs that can be greatly improved with increased physical activity (Dishman, 1991; Penedo & Dahn, 2005; Poag & McAuley, 1992). Public health physical activity recommendations exist but many individuals find these difficult to meet due to overly busy lifestyles (Public Health Agency of Canada, 2003). Pedometers are inexpensive devices that can monitor individual bouts of walking so that the incorporation of physical activity into one's daily life is more plausible. They are also excellent tools for motivation, goalsetting, and immediate feedback (Brisson & Tudor-Locke, 2004). Since many people spend a large proportion of their time at their places of employment, workplaces have begun to be a common site for the development of physical activity interventions. These programs have been growing in popUlarity and have shown numerous benefits for both employees and employers (Voit, 2001). The purpose of the current study was to implement and evaluate the use of a pedometer-based physical activity intervention incorporating goal-setting and physical activity logs in a workplace setting, and to examine the relationship between different types of self-efficacy (task, barrier, and scheduling) and different phases of the intervention. Twenty male participants from a local steel manufacturing plant who exhibited health risk factors (e.g. hypertension, diabetes, etc.) were assigned to one of two groups (group A or group B). All participants were asked to wear pedometers on their waists, record their daily steps, set goals that were outlined on a step-tracking sheet (detennined by their baseline number of steps), and keep track of their work days, wakelbed time, sedentary time, and time spent doing other physical activity. Group A began the intervention immediately following the baseline measures, whereas group B continued with their regular routine for 4 weeks before beginning. Physiological measures (height, weight, blood pressure, relative body fat, waist and hip circumference, and body mass index) were taken and a battery of questionnaires that assessed barrier, task and scheduling self-efficacy, HRQL, and stage of change administered at baseline, week 5 (end of intervention for group A), week 9 (end of intervention for group B; follow-up for group A) and week 13 (follow-up for both groups). Results showed that this workplace physical activity intervention was successful at increasing the participants' daily steps, that task self-efficacy is a significant predictor of participants' exercise adherence during the initial stages of participation (intervention phase), and that the participants felt that this intervention was effective. Finally, further exploratory analyses showed that this intervention was effective for all participants, but most valuable for participants most in need of improvement - that is, those who were most sedentary prior to the intervention. This intervention is an inexpensive use of simple and effective tools (e.g. pedometers), has the potential to attract a wide variety of participants and become a pennanent part of any health promotion initiative.

Exploration of RVC applications using an ARM multicore processor = Exploración de aplicaciones RVC empleando un procesador ARM multinúcleo

Single core capabilities have reached their maximum clock speed; new multicore architectures provide an alternative way to tackle this issue instead. The design of decoding applications running on top of these multicore platforms and their optimization to exploit all system computational power is crucial to obtain best results. Since the development at the integration level of printed circuit boards are increasingly difficult to optimize due to physical constraints and the inherent increase in power consumption, development of multiprocessor architectures is becoming the new Holy Grail. In this sense, it is crucial to develop applications that can run on the new multi-core architectures and find out distributions to maximize the potential use of the system. Today most of commercial electronic devices, available in the market, are composed of embedded systems. These devices incorporate recently multi-core processors. Task management onto multiple core/processors is not a trivial issue, and a good task/actor scheduling can yield to significant improvements in terms of efficiency gains and also processor power consumption. Scheduling of data flows between the actors that implement the applications aims to harness multi-core architectures to more types of applications, with an explicit expression of parallelism into the application. On the other hand, the recent development of the MPEG Reconfigurable Video Coding (RVC) standard allows the reconfiguration of the video decoders. RVC is a flexible standard compatible with MPEG developed codecs, making it the ideal tool to integrate into the new multimedia terminals to decode video sequences. With the new versions of the Open RVC-CAL Compiler (Orcc), a static mapping of the actors that implement the functionality of the application can be done once the application executable has been generated. This static mapping must be done for each of the different cores available on the working platform. It has been chosen an embedded system with a processor with two ARMv7 cores. This platform allows us to obtain the desired tests, get as much improvement results from the execution on a single core, and contrast both with a PC-based multiprocessor system. Las posibilidades ofrecidas por el aumento de la velocidad de la frecuencia de reloj de sistemas de un solo procesador están siendo agotadas. Las nuevas arquitecturas multiprocesador proporcionan una vía de desarrollo alternativa en este sentido. El diseño y optimización de aplicaciones de descodificación de video que se ejecuten sobre las nuevas arquitecturas permiten un mejor aprovechamiento y favorecen la obtención de mayores rendimientos. Hoy en día muchos de los dispositivos comerciales que se están lanzando al mercado están integrados por sistemas embebidos, que recientemente están basados en arquitecturas multinúcleo. El manejo de las tareas de ejecución sobre este tipo de arquitecturas no es una tarea trivial, y una buena planificación de los actores que implementan las funcionalidades puede proporcionar importantes mejoras en términos de eficiencia en el uso de la capacidad de los procesadores y, por ende, del consumo de energía. Por otro lado, el reciente desarrollo del estándar de Codificación de Video Reconfigurable (RVC), permite la reconfiguración de los descodificadores de video. RVC es un estándar flexible y compatible con anteriores codecs desarrollados por MPEG. Esto hace de RVC el estándar ideal para ser incorporado en los nuevos terminales multimedia que se están comercializando. Con el desarrollo de las nuevas versiones del compilador específico para el desarrollo de lenguaje RVC-CAL (Orcc), en el que se basa MPEG RVC, el mapeo estático, para entornos basados en multiprocesador, de los actores que integran un descodificador es posible. Se ha elegido un sistema embebido con un procesador con dos núcleos ARMv7. Esta plataforma nos permitirá llevar a cabo las pruebas de verificación y contraste de los conceptos estudiados en este trabajo, en el sentido del desarrollo de descodificadores de video basados en MPEG RVC y del estudio de la planificación y mapeo estático de los mismos.

Partial order and contextual net semantics for atomic and locally atomic CC programs

We present two concurrent semantics (i.e. semantics where concurrency is explicitely represented) for CC programs with atomic tells. One is based on simple partial orders of computation steps, while the other one is based on contextual nets and it is an extensión of a previous one for eventual CC programs. Both such semantics allow us to derive concurrency, dependency, and nondeterminism information for the considered languages. We prove some properties about the relation between the two semantics, and also about the relation between them and the operational semantics. Moreover, we discuss how to use the contextual net semantics in the context of CLP programs. More precisely, by interpreting concurrency as possible parallelism, our semantics can be useful for a safe parallelization of some CLP computation steps. Dually, the dependency information may also be interpreted as necessary sequentialization, thus possibly exploiting it for the task of scheduling CC programs. Moreover, our semantics is also suitable for CC programs with a new kind of atomic tell (called locally atomic tell), which checks for consistency only the constraints it depends on. Such a tell achieves a reasonable trade-off between efficiency and atomicity, since the checked constraints can be stored in a local memory and are thus easily accessible even in a distributed implementation.

A Group-Enhanced Sprint Interval Training Program for Amateur Athletes

Sprint interval training (SIT) can elicit improvements in aerobic and anaerobic capacity. While variations in SIT protocols have been investigated, the influence of social processes cannot be overlooked. As research supports the use of groups to influence individual cognitions and behaviours, the current project assessed the effectiveness of a group-based intervention with participants conducting SIT. Specifically, 53 amateur athletes (age, 21.9 ± 2.9 years; 53% females) took part in a 4-week training program (3 sessions per week, 30-s “all-out” efforts with 4 min active recovery, repeated 4–6 times per session), and were assigned to “true group”, aggregate, or individual conditions. Results indicated no significant differences between groups for the physiological measures. With regards to training improvements from baseline for all participants— regardless of condition — significant main effects for time were identified for maximal oxygen uptake (2.5–2.8 mL·kg−1·min−1, p < 0.001, η2 = 0.03), time-trial performance (14–32 s, p < 0.001, η2 = 0.37), and anaerobic power (1.1–1.7 k·h−1, p < 0.001, η2 = 0.66). With regards to the psychological measures, significant main effects between groups were found for motivation (p = 0.033, η2 = 0.13), task self-efficacy (p = 0.018, η2 = 0.15), and scheduling self-efficacy (p = 0.003, η2 = 0.22). The true group experienced greater improvements in motivation than the individual condition, but the aggregate and individual conditions demonstrated greater increases in task and scheduling self-efficacy. Though the SIT paradigm employed induced training improvements similar to previous work, the group intervention was not able to further these improvements

Fleet Management System for Search and Rescue Operations

Over one million people lost their lives in the last twenty years from natural disasters like wildfires, earthquakes and man-made disasters. In such scenarios the usage of a fleet of robots aims at the parallelization of the workload and thus increasing speed and capabilities to complete time sensitive missions. This work focuses on the development of a dynamic fleet management system, which consists in the management of multiple agents cooperating in order to accomplish tasks. We presented a Mixed Integer Programming problem for the management and planning of mission’s tasks. The problem was solved using both an exact and a heuristic approach. The latter is based on the idea of solving iteratively smaller instances of the complete problem. Alongside, a fast and efficient algorithm for estimation of travel times between tasks is proposed. Experimental results demonstrate that the proposed heuristic approach is able to generate quality solutions, within specific time limits, compared to the exact one.

From task scheduling in single processor environments to message scheduling in a PROFIBUS fieldbus network

In this paper we survey the most relevant results for the prioritybased schedulability analysis of real-time tasks, both for the fixed and dynamic priority assignment schemes. We give emphasis to the worst-case response time analysis in non-preemptive contexts, which is fundamental for the communication schedulability analysis. We define an architecture to support priority-based scheduling of messages at the application process level of a specific fieldbus communication network, the PROFIBUS. The proposed architecture improves the worst-case messages’ response time, overcoming the limitation of the first-come-first-served (FCFS) PROFIBUS queue implementations.

A 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources

We present a 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources.

Implementing multicore real-time scheduling algorithms based on task splitting using ada 2012

Multiprocessors, particularly in the form of multicores, are becoming standard building blocks for executing reliable software. But their use for applications with hard real-time requirements is non-trivial. Well-known realtime scheduling algorithms in the uniprocessor context (Rate-Monotonic [1] or Earliest-Deadline-First [1]) do not perform well on multiprocessors. For this reason the scientific community in the area of real-time systems has produced new algorithms specifically for multiprocessors. In the meanwhile, a proposal [2] exists for extending the Ada language with new basic constructs which can be used for implementing new algorithms for real-time scheduling; the family of task splitting algorithms is one of them which was emphasized in the proposal [2]. Consequently, assessing whether existing task splitting multiprocessor scheduling algorithms can be implemented with these constructs is paramount. In this paper we present a list of state-of-art task-splitting multiprocessor scheduling algorithms and, for each of them, we present detailed Ada code that uses the new constructs.

Scheduling arbitrary-deadline sporadic task systems on multiprocessors

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor platforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach - while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation- based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary- deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.

Scheduling an European basketball competition. An application of graph theory

The object of this project is to schedule a ctitious European basketball competition with many teams situated a long distances. The schedule must be fair, feasible and economical, which means that the total distance trav- eled by every team must be the minimal possible. First, we de ne the sport competition terminology and study di erent competition systems, focusing on the NBA and the Euroleague systems. Then we de ne concepts of graph theory and spherical distance that will be needed. Next we propose a com- petition system, explaining where will be allocated the teams and how will be the scheduling. Then there is a description of the programs that have been implemented, and, nally, the complete schedule is displayed, and some possible improvements are mentioned.