Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Pre-emption

This article introduces schedulability analysis for global fixed priority scheduling with deferred preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of global fixed priority pre-emptive scheduling (gFPPS) and global fixed priority non-pre-emptive scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final non-pre-emptive region lengths, and provide algorithms which optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor.

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.

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound

Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound. A clustered variant of the algorithm, for systems made of multicore chips, eliminates (costly) off-chip task migrations, by dividing processors into disjoint clusters, formed by cores on the same chip (with the cluster size being a parameter). Clusters are independently scheduled (each, using non-clustered NPS-F). The utilisation bound is only moderately affected. We also formulate an important extension (applicable to both clustered and non-clustered NPS-F) which optimises the supply of processing time to executing tasks and makes it more granular. This reduces processing capacity requirements for schedulability without increasing preemptions.

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.

Job phasing aware preemption deferral

Preemptions account for a non-negligible overhead during system execution. There has been substantial amount of research on estimating the delay incurred due to the loss of working sets in the processor state (caches, registers, TLBs) and some on avoiding preemptions, or limiting the preemption cost. We present an algorithm to reduce preemptions by further delaying the start of execution of high priority tasks in fixed priority scheduling. Our approaches take advantage of the floating non-preemptive regions model and exploit the fact that, during the schedule, the relative task phasing will differ from the worst-case scenario in terms of admissible preemption deferral. Furthermore, approximations to reduce the complexity of the proposed approach are presented. Substantial set of experiments demonstrate that the approach and approximations improve over existing work, in particular for the case of high utilisation systems, where savings of up to 22% on the number of preemption are attained.

Deferred effects of nursery school on adolescents' school performance in Spain

This research analysis the long-term effects of nursery school attendance before the age of three in Spain. The effects are measured when the individuals are adolescents and attend secondary school. The article deals with the controversy over the long-term effects of nursery school attendance and its potential effect on reducing inequalities and social exclusion. The results estimate a significant long-term effect of nursery school attendance on improving educational performance, although the beneficial effects are lower among adolescents residing in the lower status households.

Allocation via Deferred-Acceptance under Responsive Priorities

In many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource- monotonicity with two-agent consistent con ict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.

Strategy-proofness makes the difference: deferred-acceptance with responsive priorities

In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments - including the large classes of priority mechanisms and linear programming mechanisms - satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB)procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.

House allocation via deferred-acceptance

We study the simple model of assigning indivisible and heterogenous objects (e.g., houses, jobs, offi ces, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. For this model, known as the house allocation model, we characterize the class of rules satisfying unavailable object invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness: any rule with these properties must allocate objects based on (implicitly induced) objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm.

Object allocation via deferred-acceptance: strategy-proofness and comparative statics

We study the problem of assigning indivisible and heterogenous objects (e.g., houses, jobs, offices, school or university admissions etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We consider mechanisms satisfying a set of basic properties (unavailable-type-invariance, individual-rationality, weak non-wastefulness, or truncation-invariance). In the house allocation problem, where at most one copy of each object is available, deferred-acceptance (DA)-mechanisms allocate objects based on exogenously fixed objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm. For house allocation we show that DA-mechanisms are characterized by our basic properties and (i) strategy-proofness and population-monotonicity or (ii) strategy-proofness and resource-monotonicity. Once we allow for multiple identical copies of objects, on the one hand the first characterization breaks down and there are unstable mechanisms satisfying our basic properties and (i) strategy-proofness and population-monotonicity. On the other hand, our basic properties and (ii) strategy-proofness and resource-monotonicity characterize (the most general) class of DA-mechanisms based on objects' fixed choice functions that are acceptant, monotonic, substitutable, and consistent. These choice functions are used by objects to reject agents in the agent-proposing deferred-acceptance-algorithm. Therefore, in the general model resource-monotonicity is the «stronger» comparative statics requirement because it characterizes (together with our basic requirements and strategy-proofness) choice-based DA-mechanisms whereas population-monotonicity (together with our basic properties and strategy-proofness) does not.

A Dream Deferred

Presentation at the MLK Annual Unity Breakfast, Boston College, January 19, 2005.