BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Joël Goossens

Joël Goossens appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Operating SystemsComputer Science and Game TheoryFormal Languages and Automata TheoryLogic in Computer ScienceOther Computer Science

Catalog footprint

What is connected

14works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2014arXiv

Synthesising Succinct Strategies in Safety Games

Finite turn-based safety games have been used for very different problems such as the synthesis of linear temporal logic (LTL), the synthesis of schedulers for computer systems running on multiprocessor platforms, and also for the determinisation of timed automata. In these contexts, games are implicitly defined, and their size is at least exponential in the size of the input. Nevertheless, there are natural relations between states of arenas of such games. We first formalise the properties that we expect on the relation between states, thanks to the notion of alternating simulation. Then, we show how such simulations can be exploited to (1) improve the running time of the OTFUR algorithm to compute winning strategies and (2) obtain a succinct representation of a winning strategy. We also show that our general theory applies to the three applications mentioned above.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Energy Minimization for Parallel Real-Time Systems with Malleable Jobs and Homogeneous Frequencies

In this work, we investigate the potential utility of parallelization for meeting real-time constraints and minimizing energy. We consider malleable Gang scheduling of implicit-deadline sporadic tasks upon multiprocessors. We first show the non-necessity of dynamic voltage/frequency regarding optimality of our scheduling problem. We adapt the canonical schedule for DVFS multiprocessor platforms and propose a polynomial-time optimal processor/frequency-selection algorithm. We evaluate the performance of our algorithm via simulations using parameters obtained from a hardware testbed implementation. Our algorithm has up to a 60 watt decrease in power consumption over the optimal non-parallel approach.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improving Mixed-Criticality System Consistency and Behavior on Multiprocessor Platforms by Means of Multi-Moded Approaches

Recent research in the domain of real-time scheduling theory has tackled the problem of scheduling mixed-criticality systems upon uniprocessor or multiprocessor platforms, with the main objective being to respect the timeliness of the most critical tasks, at the expense of the requirements of the less critical ones. In particular, the less critical tasks are carelessly discarded when the computation demand of (some of) the high critical tasks increases. This might nevertheless result in system failure, as these less critical tasks could be accessing data, the consistency of which should be preserved. In this paper, we address this problem and propose a method to cautiously handle task suspension. Furthermore, it is usually assumed that the less critical tasks will never be re-enabled once discarded. In this paper, we also address this concern by proposing an approach to re-enable the less critical tasks, without jeopardizing the timeliness of the high critical ones. The suggested approaches apply to systems having two or more criticality levels.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the periodic behavior of real-time schedulers on identical multiprocessor platforms

This paper is proposing a general periodicity result concerning any deterministic and memoryless scheduling algorithm (including non-work-conserving algorithms), for any context, on identical multiprocessor platforms. By context we mean the hardware architecture (uniprocessor, multicore), as well as task constraints like critical sections, precedence constraints, self-suspension, etc. Since the result is based only on the releases and deadlines, it is independent from any other parameter. Note that we do not claim that the given interval is minimal, but it is an upper bound for any cycle of any feasible schedule provided by any deterministic and memoryless scheduler.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Partitioned scheduling of multimode multiprocessor real-time systems with temporal isolation

We consider the partitioned scheduling problem of multimode real-time systems upon identical multiprocessor platforms. During the execution of a multimode system, the system can change from one mode to another such that the current task set is replaced with a new one. In this paper, we consider a synchronous transition protocol in order to take into account mode-independent tasks, i.e., tasks of which the execution pattern must not be jeopardized by the mode changes. We propose two methods for handling mode changes in partitioned scheduling. The first method is offline/optimal and computes a static allocation of tasks schedulable and respecting both tasks and transition deadlines (if any). The second approach is subject to a sufficient condition in order to ensure online First Fit based allocation to satisfy the timing constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A faster exact multiprocessor schedulability test for sporadic tasks

Baker and Cirinei introduced an exact but naive algorithm, based on solving a state reachability problem in a finite automaton, to check whether sets of sporadic hard real-time tasks are schedulable on identical multiprocessor platforms. However, the algorithm suffered from poor performance due to the exponential size of the automaton relative to the size of the task set. In this paper, we successfully apply techniques developed by the formal verification community, specifically antichain algorithms, by defining and proving the correctness of a simulation relation on Baker and Cirinei's automaton. We show our improved algorithm yields dramatically improved performance for the schedulability test and opens for many further improvements.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Global Scheduling of Multi-Mode Real-Time Applications upon Multiprocessor Platforms

Multi-mode real-time systems are those which support applications with different modes of operation, where each mode is characterized by a specific set of tasks. At run-time, such systems can, at any time, be requested to switch from its current operating mode to another mode (called "new mode") by replacing the current set of tasks with that of the new-mode. Thereby, ensuring that all the timing requirements are met not only requires that a schedulability test is performed on the tasks of each mode but also that (i) a protocol for transitioning from one mode to another is specified and (ii) a schedulability test for each transition is performed. We propose two distinct protocols that manage the mode transitions upon uniform and identical multiprocessor platforms at run-time, each specific to distinct task requirements. For each protocol, we formally establish schedulability analyses that indicate beforehand whether all the timing requirements will be met during any mode transition of the system. This is performed assuming both Fixed-Task-Priority and Fixed-Job-Priority schedulers.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Scheduling of Hard Real-Time Multi-Thread Periodic Tasks

In this paper we study the scheduling of parallel and real-time recurrent tasks. Firstly, we propose a new parallel task model which allows recurrent tasks to be composed of several threads, each thread requires a single processor for execution and can be scheduled simultaneously. Secondly, we define several kinds of real-time schedulers that can be applied to our parallel task model. We distinguish between two scheduling classes: hierarchical schedulers and global thread schedulers. We present and prove correct an exact schedulability test for each class. Lastly, we also evaluate the performance of our scheduling paradigm in comparison with Gang scheduling by means of simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sufficient FTP Schedulability Test for the Non-Cyclic Generalized Multiframe Task Model

Our goal is to provide a sufficient schedulability test -ideally polynomial- for the scheduling of Non-Cyclic Generalized Multiframe Task Model using Fixed-Task-Priority schedulers. We report two first results: (i) we present and prove correct the critical instant for the Non-Cyclic Generalized Multiframe Task Model then (ii) we propose an algorithm which provides a sufficient (but pseudo-polynomial) schedulability test.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Exact Schedulability Test for global-EDF Scheduling of Periodic Hard Real-Time Tasks on Identical Multiprocessors

In this paper we consider the scheduling problem of hard real-time systems composed of periodic constrained-deadline tasks upon identical multiprocessor platforms. We assume that tasks are scheduled by using the global-EDF scheduler. We establish an exact schedulability test for this scheduler by exploiting on the one hand its predictability property and by providing on the other hand a feasibility interval so that if it is possible to find a valid schedule for all the jobs contained in this interval, then the whole system will be stamped feasible. In addition, we show by means of a counterexample that the feasibility interval, and thus the schedulability test, proposed by Leung [Leung 1989] is incorrect and we show which arguments are actually incorrect.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Gang FTP scheduling of periodic and parallel rigid real-time tasks

In this paper we consider the scheduling of periodic and parallel rigid tasks. We provide (and prove correct) an exact schedulability test for Fixed Task Priority (FTP) Gang scheduler sub-classes: Parallelism Monotonic, Idling, Limited Gang, and Limited Slack Reclaiming. Additionally, we study the predictability of our schedulers: we show that Gang FJP schedulers are not predictable and we identify several sub-classes which are actually predictable. Moreover, we extend the definition of rigid, moldable and malleable jobs to recurrent tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Multi-Criteria Evaluation of Partitioning Schemes for Real-Time Systems

In this paper we study the partitioning approach for multiprocessor real-time scheduling. This approach seems to be the easiest since, once the partitioning of the task set has been done, the problem reduces to well understood uniprocessor issues. Meanwhile, there is no optimal and polynomial solution to partition tasks on processors. In this paper we analyze partitioning algorithms from several points of view such that for a given task set and specific constraints (processor number, task set type, etc.) we should be able to identify the best heuristic and the best schedulability test. We also analyze the influence of the heuristics on the performance of the uniprocessor tests and the impact of a specific task order on the schedulability. A study on performance difference between Fixed Priority schedulers and EDF in the case of partitioning scheduling is also considered.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Scheduling Multi-Mode Real-Time Systems upon Uniform Multiprocessor Platforms

In this paper, we address the scheduling problem of multi-mode real-time systems upon uniform multiprocessor platforms. We propose two transition protocols, specified together with their schedulability test, and provide the reader with two distinct upper bounds for the length of the transient phases during mode transitions, respectively for the cases where jobs priorities are known and unknown beforehand.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Semi-Partitioned Hard Real-Time Scheduling with Restricted Migrations upon Identical Multiprocessor Platforms

Algorithms based on semi-partitioned scheduling have been proposed as a viable alternative between the two extreme ones based on global and partitioned scheduling. In particular, allowing migration to occur only for few tasks which cannot be assigned to any individual processor, while most tasks are assigned to specific processors, considerably reduces the runtime overhead compared to global scheduling on the one hand, and improve both the schedulability and the system utilization factor compared to partitioned scheduling on the other hand. In this paper, we address the preemptive scheduling problem of hard real-time systems composed of sporadic constrained-deadline tasks upon identical multiprocessor platforms. We propose a new algorithm and a scheduling paradigm based on the concept of semi-partitioned scheduling with restricted migrations in which jobs are not allowed to migrate, but two subsequent jobs of a task can be assigned to different processors by following a periodic strategy.

0 citations0 reviewsNo code linkedOpen access