Preemption delay analysis for floating non-preemptive region scheduling

In real-time systems, there are two distinct trends for scheduling task sets on unicore systems: non-preemptive and preemptive scheduling. Non-preemptive scheduling is obviously not subject to any preemption delay but its schedulability may be quite poor, whereas fully preemptive scheduling is subject to preemption delay, but benefits from a higher flexibility in the scheduling decisions. The time-delay involved by task preemptions is a major source of pessimism in the analysis of the task Worst-Case Execution Time (WCET) in real-time systems. Preemptive scheduling policies including non-preemptive regions are a hybrid solution between non-preemptive and fully preemptive scheduling paradigms, which enables to conjugate both world's benefits. In this paper, we exploit the connection between the progression of a task in its operations, and the knowledge of the preemption delays as a function of its progression. The pessimism in the preemption delay estimation is then reduced in comparison to state of the art methods, due to the increase in information available in the analysis.

An improved preemption delay upper bound for floating non-preemptive region

In embedded systems, the timing behaviour of the control mechanisms are sometimes of critical importance for the operational safety. These high criticality systems require strict compliance with the offline predicted task execution time. The execution of a task when subject to preemption may vary significantly in comparison to its non-preemptive execution. Hence, when preemptive scheduling is required to operate the workload, preemption delay estimation is of paramount importance. In this paper a preemption delay estimation method for floating non-preemptive scheduling policies is presented. This work builds on [1], extending the model and optimising it considerably. The preemption delay function is subject to a major tightness improvement, considering the WCET analysis context. Moreover more information is provided as well in the form of an extrinsic cache misses function, which enables the method to provide a solution in situations where the non-preemptive regions sizes are small. Finally experimental results from the implementation of the proposed solutions in Heptane are provided for real benchmarks which validate the significance of this work.

Software transactional memory as a building block for parallel embedded realtime systems

The recent trends of chip architectures with higher number of heterogeneous cores, and non-uniform memory/non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as a fundamental building block for developing parallel applications. Nevertheless, although STM promises to ease concurrent and parallel software development, it relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by embedded real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upper-bounded and task sets can be feasibly scheduled. In this paper we assess the use of STM in the development of embedded real-time software, defending that the amount of contention can be reduced if read-only transactions access recent consistent data snapshots, progressing in a wait-free manner. We show how the required number of versions of a shared object can be calculated for a set of tasks. We also outline an algorithm to manage conflicts between update transactions that prevents starvation.

Estudo Estratigráfico e Paleontológico do Jurássico do Algarve Ocidental

Algarve Province, Southern Portugal, corresponds in part to a meso-cenozoic basin running along the coast from Cabo S. Vicente to beyond Spanish border. Structurally it is a big monocline plunging southwards much deformed mainly by two East-West longitudinal flexures. Lithostratigraphical and chronostratigraphical studies dealt specially with Jurassic formations. This and the geological mapping of the post-Hercynian sedimentary formations allow us to define the following units: Triassic-Lower Liassic Arenitos de Silves (Silves sandstones sensu P. Choffat, pro parte) - At their base the Silves sandstones (0-150m) are represented mainly by cross-bedded red sandstones. This unit is Upper Triassic (Keuper) in age, on the evidence of some Brachiopoda. Complexo margo-carbonatado de Silves (Silves marl-limestone complex=Silves sandstones sensu P. Choffat, pro parte) (80-200m) overlies the preceding, it may be reported to the Upper Triassic-Hettangian. It consists of a thick pelite-marl-dolomite-limestone series with many intercalations of greenstones. Since no fossils were found it is not possible to conclude whether it is still Hettangian or if it does correspond, in the whole or in part, already to the Sinemurian. Liassic Dolomitos e calcários dolomíticos de Espiche (Espiche dolomite-rocks and dolomitic-limestones) - The usually massive and finely crystalline or saccharoidal dolomites and dolomitic-limestones are the toughest strata of the Algarve margin giving rise to several hills. Its thickness attains in certain points 60 metres at least. Based on geometry and on lithological similarities with the carbonated complex of the northern basin of Tagus river (Peniche, São Pedro de Muel, Quiaios), this formation can be accepted as Sinemurian in age. As it happens with the carbonated complex, here also the first dolomite beds are non-isochronal throughout the region; upper time-limit of the dolomitic facies is either Lower Carixian, Lower Toarcian or even Lower Dogger. The dolomitization is secondary but not much later than sedimentation. However, between Cabo S. Vicente-Vila do Bispo there is evidence of an even later secondary dolomitization related to the regional fault complex. Calcário dolomítico com nódulos de silex da praia de Belixe (Belixe beach dolomitic-limestone with silex nodules) (50-55m) - Ascribed to Lower or Middle Carixian on the basis of Platypleuroceras sp., Metaderoceras sp. nov. and M. gr. Venarense. Calcário cristalino compacto com Protogrammoceras, Fuciniceras e ? Argutarpites de Belixe (Belixe compact crystalline limestone with Protogrammoceras, Fuciniceras and ? Argutarpites) (30m) - Ascribed to Lower Domerian. Middle and Upper Domerian are indicated but by a single specimen of ? Argutarpites. Calcários margosos e margas com Dactylioceras semicelatum e Harpoceratídeos de Armação Nova (Armação Nova marly limestones and marls with D. semicelatum and Harpoceratidae) (25m) -Ascribed to Lower Toarcian. Middle and Upper Toarcian formations are not known in the Algarve. Dogger Calcários oolíticos, c. corálicos, c. pisolíticos, c. calciclásticos, c. dolomíticos e dolomitos de Almadena (Almadena oolitic-limestones, coral-reef-limestones, pisolite-limestones, limeclastic-limestones, dolomitic-limestones and dolomite-rocks) (more than 50 metres), with lagoonal facies. Ascribed to Aalenian-Bathonian-? Callovian. Margas acinzentadas e calcários detríticos com Zoophycos da praia de Mareta (Mareta beach greyish marls and detritical limestones with Zoophycos) (40m) - Pelagic transreef facies with Upper Bajocian and Bathonian ammonites. Calcários margosos e margas da praia de Mareta (Mareta beach pelagic marly-limestones and marls) (110m) - Ascribed to the Callovian on its ammonites. Malm Near Cabo S. Vicente and Sagres the first Upper Jurassic level consists of a yellowish-brown nodular, compact, locally phosphated and ferruginous, sometimes conglomeratic, marly limestone (0,35-1,50m) containing a rich macrofauna, which includes: 1) Callovian forms unknown at Lower Oxfordian; 2) Upper Callovian forms that still survived in Lower and Middle Oxfordian; 3) Lower Oxfordian forms (Mariae and Cordatum Zones); 4) Lower and Middle Oxfordian forms (Mariae to Plicatilis Zone); 5) Middle Oxfordian forms (plicatilis Zone), and some ones appearing in Middle Oxfordian. This condensed deposit is therefore dated from Middle Oxfordian (Plicatilis Zone). The other Upper Jurassic lithostratigraphical units were also mapped but their detailed study is not presented in this work. Correlations between lithostratigraphical and chronostratigraphical scales from P. Choffat, J. Pratsch, C. Palain and from the author are stated. Further correlations are attempted between zonc scales of Carixian-Lower Toarcian and Upper Bajocian-Middle Oxfordian of France, Spain (Asturias, Iberian and Betic Chains), Argel (Orania) and Portugal (northern Tagus basin and Algarve). The study of pyritous fossil assemblages common in Upper Bathonian-Lower Callovian marly levels of the praia da Mareta seems to suggest that these sediments were deposited in a bay or in an almost closed coastal re-entrance virtually without deep water circulation. Although such conditions may occur at any depth one may suppose that these ones actually correspond to an infralittoral neritic environment. The thaphocoenosis collected there are almost entirely composed of nektonic (ammonites, Belemnites) and planktonic (Bositra) faunas. The sedentary (crinoids, brachiopods) or free (sea-urchins, gastropods) epibenthonic forms are very scarce; endobenthonic forms are not known. The palaeontological study of all Nautiloids and Ammonoids of the Liassic and Dogger is presented (except Kosmoceratidae and Perisphinctaceae). Among the thirty one taxa dealt with, one is new (Metaderoceras sp. nov.) and the great majority of the others has been identified for the first time in Algarve. Some others have never been reported before in Portuguese formations. The evolution, during Jurassic times, of the sedimentary basins of the Portuguese plate margin is described. The absence of Cephalopods in the very extensive marly and dolomitic limestones, partly marine, suggests that, during Lower Liassic, palaeogeography underwent no great changes. Dolomitic-limestone with silex nodules from Cabo S. Vicente contain the first ammonites recorded at the base of the Middle Liassic. This facies, although very common in Tethys, is unknown north of the Tagus. The faunal assemblage has a mediterranean to submediterranean character. Comparisons between faunal assemblage" from Algarve with the ones known north of the Tagus show that communications between Boreal Europe and Tethys, virtually non-existent during Lower and Middle Carixian, became very easy during Lower Domerian. In earlier Pliensbachian times two distinct seas were adjacent to the Iberian plate. One, an epicontinental sea with a tethyan fauna, extended southwards from the Meseta margin. Another, was a boreal sea; during its transgressive episodes boreal faunas attained into the basin north of the Tagus. During Middle Carixian and Lower Domerian, owing to simultaneous transgressions, these two seas joined together allowing faunal exchanges along the epicontinental areas which limited the emerging hercynian chains belts. During Liassic, the Algarve belonged undoubtedly to the tethyan submediterranean province. The area north of the Tagus, on the contrary, was a complex realm where subboreal and tethyan affinities alternatively prevailed. In the Algarve the first Middle Jurassic deposits do frequently show lateral thickness reductions as well as unconformities contemporaneous with other generalized disturbances on the sedimentation processes in other parts of Europe. By this time, near Sagres, a barrier reef developed separating lagoonal or ante-reef facies from the transreef pelagic zone. The presence of tethyan fauna, the abundance of Phylloceratidae and the absence of boreal forms allow us to consider the Algarve basin as a submediterranean province. The presence of Callovian pelagic fossiliferous formations in the Loulé area shows that during Middle Jurassic the marl-limestone transreef sedimentation was not confined to the western Algarve. They would extend eastwards where they only can be seen in the core of some anticlines. This is due to the progressive sinking of the meso-cenozoic formations as we proceed towards the South of the Sagres-Algoz-Querença flexure. In the whole of the Peninsule, and as for the Middle Callovian, an important regression can be clearly recognized on the evidence of an erosion surface which strikes obliquely the Middle and Upper Callovian strata. The geographic boundaries of the different faunal provinces are not changed by the presence of many Kosmoceratidae in the phosphate nodules since they are but a minority in comparison with the tethyan forms. An abstract model can be constructed showing that in Western Europe the Kosmoceratidae may have migrated South and westwards through a channel of the sea that linked Paris basin to Poitou and Aquitaine. By migrating between the Iberian meseta and the Armorican massif this fauna reached northern Tagus basin at the beginning of Upper Callovian (Athleta Zone); this south and southwest bound migration would have proceeded, allowing such forms to reach Algarve basin only in latest Callovian times (Lamberti Zone). This migration means that during Middle Jurassic a widely spread North Atlantic sea would exist, flooding the western part of Portugal up to the Poitou.

The utilization bound of non-preemptive rate-monotonic scheduling in controller area networks is 25%

Consider a distributed computer system comprising many computer nodes, each interconnected with a controller area network (CAN) bus. We prove that if priorities to message streams are assigned using rate-monotonic (RM) and if the requested capacity of the CAN bus does not exceed 25% then all deadlines are met.

Finding an upper bound on the increase in execution time due to contention on the memory bus in COTS-based multicore systems

Contention on the memory bus in COTS based multicore systems is becoming a major determining factor of the execution time of a task. Analyzing this extra execution time is non-trivial because (i) bus arbitration protocols in such systems are often undocumented and (ii) the times when the memory bus is requested to be used are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. We present a method for finding an upper bound on the extra execution time of a task due to contention on the memory bus in COTS based multicore systems. This method makes no assumptions on the bus arbitration protocol (other than assuming that it is work-conserving).

A capacity sharing and stealing strategy for open real-time systems

This paper focuses on the scheduling of tasks with hard and soft real-time constraints in open and dynamic real-time systems. It starts by presenting a capacity sharing and stealing (CSS) strategy that supports the coexistence of guaranteed and non-guaranteed bandwidth servers to efficiently handle soft-tasks’ overloads by making additional capacity available from two sources: (i) reclaiming unused reserved capacity when jobs complete in less than their budgeted execution time and (ii) stealing reserved capacity from inactive non-isolated servers used to schedule best-effort jobs. CSS is then combined with the concept of bandwidth inheritance to efficiently exchange reserved bandwidth among sets of inter-dependent tasks which share resources and exhibit precedence constraints, assuming no previous information on critical sections and computation times is available. The proposed Capacity Exchange Protocol (CXP) has a better performance and a lower overhead when compared against other available solutions and introduces a novel approach to integrate precedence constraints among tasks of open real-time systems.

Managing contention of software transactional memory in real-time systems

The foreseen evolution of chip architectures to higher number of, heterogeneous, cores, with non-uniform memory and non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as an alternative to lock-based synchronisation. However, STM relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upperbounded and task sets can be feasibly scheduled. In this paper we defend the role of the transaction contention manager to reduce the number of transaction retries and to help the real-time scheduler assuring schedulability. For such purpose, the contention management policy should be aware of on-line scheduling information.

Análise de investimento de edifícios arrendados e da sua viabilidade na reabilitação das cidades

Dissertação de Natureza Científica para obtenção do grau de Mestre em Engenharia Civil na Área de Especialização de Edificações

Analyzing TDMA with slot skipping

Distributed real-time systems, such as factory automation systems, require that computer nodes communicate with a known and low bound on the communication delay. This can be achieved with traditional time division multiple access (TDMA). But improved flexibility and simpler upgrades are possible through the use of TDMA with slot-skipping (TDMA/SS), meaning that a slot is skipped whenever it is not used and consequently the slot after the skipped slot starts earlier. We propose a schedulability analysis for TDMA/SS. We assume knowledge of all message streams in the system, and that each node schedules messages in its output queue according to deadline monotonic. Firstly, we present a non-exact (but fast) analysis and then, at the cost of computation time, we also present an algorithm that computes exact queuing times.

Capacity sharing and stealing in dynamic server-based real-time systems

This paper proposes a dynamic scheduler that supports the coexistence of guaranteed and non-guaranteed bandwidth servers to efficiently handle soft-tasks’ overloads by making additional capacity available from two sources: (i) residual capacity allocated but unused when jobs complete in less than their budgeted execution time; (ii) stealing capacity from inactive non-isolated servers used to schedule best-effort jobs. The effectiveness of the proposed approach in reducing the mean tardiness of periodic jobs is demonstrated through extensive simulations. The achieved results become even more significant when tasks’ computation times have a large variance.

A two-competitive approximate schedulability analysis of CAN

Consider the problem of deciding whether a set of n sporadic message streams meet deadlines on a Controller Area Network (CAN) bus for a specified priority assignment. It is assumed that message streams have implicit deadlines and no release jitter. An algorithm to solve this problem is well known but unfortunately it time complexity is non-polynomial. We present an algorithm with polynomial time-complexity for computing an upper bound on the response times. Clearly, if the upper bound on the response time does not exceed the deadline then all deadlines are met. The pessimism of our approach is proven: if the upper bound of the response time exceeds the deadline then the response time exceeds the deadline as well for a CAN network with half the speed.

Current mortars in conservation: an overview

Renders are an important item in historical buildings and the need for their periodical re-application is a basic conservation procedure. In modern times there has been a trend towards the replacement of traditional pure lime mortars by new formulations including Portland cement or hydraulic lime. Apart from those interventions on specific and very important monuments, in which the use oftraditional non-hydraulic mortars can be enforced, in most of the projects involving less than first order magnitude heritage the use of some sort of hydraulic components is becoming the rule rather than the exception. The present paper describes and analyses the results of an experimental study with ten formulations of current mortars - including some that can hardly be considered as adequate conservation procedures - allowing a direct comparison in terms of some of the most relevant characteristics.

Non invasive ventilation during exercise in COPD patients: a systematic review with meta-analysis

COPD is a major cause of morbidity and mortality worldwide, representing a major public health problem due to the high health and economic resource consumption. Pulmonary rehabilitation is a standard care recommendation for these patients, in order to control the symptoms and optimize the functional capacity, reducing health care costs associated with exacerbations and activity limitations and participation. However, in patients with severe COPD exercise performance can be difficult, due to extreme dyspnea, decreased muscle strength and fatigue. In addition, hypoxemia and dyspnea during efforts and daily activities may occur, limiting their quality of life. Thus, NIV have been used as adjunct to exercise, in order to improve exercise capacity in these patients. However, there is no consensus for this technique recommendation. Our objective was to verify whether the use of NIV during exercise is effective than exercise without NIV in dyspnea, walked distance, blood gases and health status in COPD patients, through a systematic review and meta-analysis.

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.