Supporting real-time parallel task models with work-stealing

Dynamic parallel scheduling using work-stealing has gained popularity in academia and industry for its good performance, ease of implementation and theoretical bounds on space and time. Cores treat their own double-ended queues (deques) as a stack, pushing and popping threads from the bottom, but treat the deque of another randomly selected busy core as a queue, stealing threads only from the top, whenever they are idle. However, this standard approach cannot be directly applied to real-time systems, where the importance of parallelising tasks is increasing due to the limitations of multiprocessor scheduling theory regarding parallelism. Using one deque per core is obviously a source of priority inversion since high priority tasks may eventually be enqueued after lower priority tasks, possibly leading to deadline misses as in this case the lower priority tasks are the candidates when a stealing operation occurs. Our proposal is to replace the single non-priority deque of work-stealing with ordered per-processor priority deques of ready threads. The scheduling algorithm starts with a single deque per-core, but unlike traditional work-stealing, the total number of deques in the system may now exceed the number of processors. Instead of stealing randomly, cores steal from the highest priority deque.

Parallel real-time support for distributed adaptive embedded applications

Real-time embedded applications require to process large amounts of data within small time windows. Parallelize and distribute workloads adaptively is suitable solution for computational demanding applications. The purpose of the Parallel Real-Time Framework for distributed adaptive embedded systems is to guarantee local and distributed processing of real-time applications. This work identifies some promising research directions for parallel/distributed real-time embedded applications.

Device power management for real-time embedded systems

A large part of power dissipation in a system is generated by I/O devices. Increasingly these devices provide power saving mechanisms to inter alia enhance battery life. While I/O device scheduling has been studied in the past for realtime systems, the use of energy resources by these scheduling algorithms may be improved. These approaches are crafted considering a huge overhead of device transition. The technology enhancement has allowed the hardware vendors to reduce the device transition overhead and energy consumption. We propose an intra-task device scheduling algorithm for real time systems that allows to shut-down devices while ensuring the system schedulability. Our results show an energy gain of up to 90% in the best case when compared to the state-of-the-art.

A framework for the development of parallel and distributed real-time embedded systems

Embedded real-time applications increasingly present high computation requirements, which need to be completed within specific deadlines, but that present highly variable patterns, depending on the set of data available in a determined instant. The current trend to provide parallel processing in the embedded domain allows providing higher processing power; however, it does not address the variability in the processing pattern. Dimensioning each device for its worst-case scenario implies lower average utilization, and increased available, but unusable, processing in the overall system. A solution for this problem is to extend the parallel execution of the applications, allowing networked nodes to distribute the workload, on peak situations, to neighbour nodes. In this context, this report proposes a framework to develop parallel and distributed real-time embedded applications, transparently using OpenMP and Message Passing Interface (MPI), within a programming model based on OpenMP. The technical report also devises an integrated timing model, which enables the structured reasoning on the timing behaviour of these hybrid architectures.

Dynamic global scheduling of parallel real-time tasks

High-level parallel languages offer a simple way for application programmers to specify parallelism in a form that easily scales with problem size, leaving the scheduling of the tasks onto processors to be performed at runtime. Therefore, if the underlying system cannot efficiently execute those applications on the available cores, the benefits will be lost. In this paper, we consider how to schedule highly heterogenous parallel applications that require real-time performance guarantees on multicore processors. The paper proposes a novel scheduling approach that combines the global Earliest Deadline First (EDF) scheduler with a priority-aware work-stealing load balancing scheme, which enables parallel realtime tasks to be executed on more than one processor at a given time instant. Experimental results demonstrate the better scalability and lower scheduling overhead of the proposed approach comparatively to an existing real-time deadline-oriented scheduling class for the Linux kernel.

Online intra-task device scheduling for hard real-time systems

A large part of power dissipation in a system is generated by I/O devices. Increasingly these devices provide power saving mechanisms, inter alia to enhance battery life. While I/O device scheduling has been studied in the past for realtime systems, the use of energy resources by these scheduling algorithms may be improved. These approaches are crafted considering a very large overhead of device transitions. Technology enhancements have allowed the hardware vendors to reduce the device transition overhead and energy consumption. We propose an intra-task device scheduling algorithm for real time systems that allows to shut-down devices while ensuring system schedulability. Our results show an energy gain of up to 90% when compared to the techniques proposed in the state-of-the-art.

Service offloading in adaptive real-time systems

Smartphones and other internet enabled devices are now common on our everyday life, thus unsurprisingly a current trend is to adapt desktop PC applications to execute on them. However, since most of these applications have quality of service (QoS) requirements, their execution on resource-constrained mobile devices presents several challenges. One solution to support more stringent applications is to offload some of the applications’ services to surrogate devices nearby. Therefore, in this paper, we propose an adaptable offloading mechanism which takes into account the QoS requirements of the application being executed (particularly its real-time requirements), whilst allowing offloading services to several surrogate nodes. We also present how the proposed computing model can be implemented in an Android environment

Real-time scheduling with resource sharing on uniform multiprocessors

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a uniform multiprocessor platform where each task may access at most one of |R| shared resources and at most once by each job of that task. The resources have to be accessed in a mutually exclusive manner. We propose an algorithm, GIS-vpr, which offers the guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that allows a task to migrate only when it accesses or releases a resource, then our algorithm also meets the deadlines with the same restriction on the task migration, if given processors 4 + 6|R| times as fast. The proposed algorithm, by design, limits the number of migrations per job to at most two. To the best of our knowledge, this is the first result for resource sharing on uniform multiprocessors with proven performance guarantee.

Server-based scheduling of parallel real-time tasks

Multicore platforms have transformed parallelism into a main concern. Parallel programming models are being put forward to provide a better approach for application programmers to expose the opportunities for parallelism by pointing out potentially parallel regions within tasks, leaving the actual and dynamic scheduling of these regions onto processors to be performed at runtime, exploiting the maximum amount of parallelism. It is in this context that this paper proposes a scheduling approach that combines the constant-bandwidth server abstraction with a priority-aware work-stealing load balancing scheme which, while ensuring isolation among tasks, enables parallel tasks to be executed on more than one processor at a given time instant.

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].

A framework for offloading real-time applications in a distributed environment

This work focuses on highly dynamic distributed systems with Quality of Service (QoS) constraints (most importantly real-time constraints). To that purpose, real-time applications may benefit from code offloading techniques, so that parts of the application can be offloaded and executed, as services, by neighbour nodes, which are willing to cooperate in such computations. These applications explicitly state their QoS requirements, which are translated into resource requirements, in order to evaluate the feasibility of accepting other applications in the system.

Estudo do trabalho e do trabalhar no Núcleo de Apoio à Saúde da Família

OBJETIVO Compreender características da organização, das condições de trabalho e das vivências subjetivas relacionadas ao trabalhar de dois núcleos de apoio à saúde da família. MÉTODOS Estudo de caso realizado entre 2011 e 2012 em dois núcleos de apoio à saúde da família de São Paulo, SP. Para coleta e análise dos dados, utilizaram-se referenciais teórico-metodológicos da ergonomia e da psicodinâmica do trabalho pautados, respectivamente, na análise ergonômica do trabalho, desenvolvida a partir de observações abertas de diversas tarefas e de entrevistas e na ação em Psicodinâmica do Trabalho, realizada por meio de grupos de reflexão sobre o trabalho. RESULTADOS O trabalho dos Núcleos de Apoio à Saúde da Família estudados era constituído a partir de ações diversificadas e complexas devendo ser compartilhado entre profissionais e equipes envolvidas. Eram utilizadas ferramentas tecnológicas inovadoras, pouco adotadas pelos profissionais da atenção primária em saúde, e os parâmetros e instrumentos de produtividade não davam conta da especificidade e complexidade do trabalho realizado. Tais situações exigiam rearranjos organizacionais constantes, sobretudo entre os Núcleos de Apoio e as Equipes de Saúde da Família, provocando dificuldades na realização do trabalho e na própria constituição identitária dos profissionais estudados. CONCLUSÕES Procurou-se dar maior visibilidade aos processos de trabalho do Núcleo de Apoio à Saúde da Família de forma a contribuir para avanços da política pública de atenção primária à saúde. A introdução de mudanças no trabalho é antes de tudo um compromisso que deve ser permanente e contemplar todos os atores envolvidos.

Iniquidades em saúde bucal: escolares beneficiários do Bolsa Família são mais vulneráveis?

OBJETIVO : Analisar a associação entre ser beneficiário do Programa Bolsa Família e condições de saúde bucal entre escolares. MÉTODOS : Estudo transversal com 1.107 escolares entre oito e 12 anos de idade, provenientes de 20 escolas públicas e particulares da cidade de Pelotas, RS, em 2010. Os beneficiários do Programa Bolsa Família foram verificados por meio de lista fornecida pelas escolas participantes do estudo. Informações demográficas, socioeconômicas, de uso de serviço odontológico e de higiene bucal foram obtidas por meio de questionários respondidos pelos escolares e por seus pais. O exame clínico avaliou a presença de placa dental e experiência de cárie. Os dados foram analisados por meio dos testes do Qui-quadrado e Qui-quadrado de tendência linear e por regressão de Poisson (razão de prevalência; intervalo de confiança de 95%). RESULTADOS : Crianças de família não nuclear, que apresentavam CPOD ≥ 1 e que nunca haviam feito uso de serviço odontológico na vida estiveram associadas ao recebimento do Programa Bolsa Família. O modelo final mostrou que a prevalência de cárie foi duas vezes maior (RP 2,00; IC95% 1,47;2,69) em alunos beneficiários do Programa que também apresentaram maior severidade da doença, quando comparados aos alunos de escolas particulares (RM 1,53; IC95% 1,18;2,00). A prevalência de escolares que nunca haviam ido ao dentista foi mais de seis vezes maior em beneficiários do Programa Bolsa Família (RP 6,18; IC95% 3,07;12,45), em comparação com aqueles das escolas privadas, após ajustes. CONCLUSÕES : Escolares beneficiários do Programa Bolsa Família possuem maior carga de cárie e são os que menos acessam os serviços odontológicos. Esses achados sugerem a necessidade de incorporação da saúde bucal nas condicionalidades do Programa Bolsa Família.

A review of power laws in real life phenomena

Power law distributions, also known as heavy tail distributions, model distinct real life phenomena in the areas of biology, demography, computer science, economics, information theory, language, and astronomy, amongst others. In this paper, it is presented a review of the literature having in mind applications and possible explanations for the use of power laws in real phenomena. We also unravel some controversies around power laws.