Explore the vast range of titles available.

The Contention-Free (CF) policy has been extensively researched in the realm of real-time multi-processor scheduling due to its wide applicability and the performance enhancement benefits it provides to existing scheduling algorithms. The CF policy improves the feasibility of executing other real-time tasks by assigning the lowest priority to a task at a moment when it is guaranteed not to miss its deadline during the remaining execution time. Despite its effectiveness, existing studies on the CF policy are largely confined to preemptive scheduling, leaving the efficiency and applicability of limited preemption scheduling unexplored. Limited preemption scheduling permits a job to execute to completion with a limited number of preemptions, setting it apart from preemptive scheduling. This type of scheduling is crucial when preemption or migration overheads are either excessively large or unpredictable. In this paper, we introduce SP-CF, a single preemption scheduling approach that incorporates the CF policy. SP-CF allows a preemption only once during each job’s execution, following a priority demotion under the CF policy. We also propose a new schedulability analysis method for SP-CF to determine whether each task is executed in a timely manner and without missing its deadline. Through simulation experiments, we demonstrate that SP-CF can significantly enhance the schedulability of the traditional rate-monotonic algorithm and the earliest deadline first algorithm.

Multi-objective task graph scheduling is a well-known NP-hard problem that plays a significant role in heterogeneous distributed systems. The solution to the problem is expected to optimize all scheduling objectives. Pretty large state-of-the-art algorithms exist in the literature that mostly apply different metaheuristics for solving the problem. This study proposes a new hybrid algorithm comprising an improved multi-objective differential evolution algorithm (DE) and Pareto-front neighborhood search to solve the problem. The novelty of the proposed hybrid method is achieved by improving DE and hybridizing it with the neighborhood search method. The proposed method improves the performance of differential evolution by applying appropriate solution representation as well as effective selection, crossover, and mutation operators. Likewise, the neighborhood search algorithm is applied to improve the extracted Pareto-front and speed up the evolution process. The effectiveness and performance of the developed method are assessed over well-known test problems collected from the related literature. Meanwhile, the values of spacing and hyper-volume metrics are calculated. Moreover, the Wilcoxon signed method is applied to carry out pairwise statistical tests over the obtained results. The obtained results for the makespan, reliability, and flow-time of 50, 18, and 41, respectively, by the proposed hybrid algorithm in the study confirmed that the developed algorithm outperforms all proposed methods considering the performance and quality of objective values.

Multiprocessor task scheduling problem is a pressing problem that affects systems' performance and is still being investigated by the researchers. Finding the optimal schedules is considered to be a computationally hard problem. Recently, researchers have used fuzzy logic in the field of task scheduling to achieve optimal performance, but this area of research is still not well investigated. In addition, there are various scheduling algorithms that used fuzzy logic but most of them are often performed on uniprocessor systems. This article presents a new proposed algorithm in which the priorities of the tasks are derived from the fuzzy logic and bottom level parameter. This approach is designed to find task schedules with optimal or sub‐optimal lengths in order to achieve high performance for a multiprocessor environment. With respect to the proposed algorithm, the precedence constraints between the non‐preemptive tasks and their execution times are known and described by a directed acyclic graph. The number of processors is fixed, the communication costs are negligible and the processors are homogeneous. The suggested technique is tested and compared with the Prototype Standard Task Graph Set.

In the single-processor scheduling problem with time restrictions there is one main processor and B resources that are used to execute the jobs. A perfect schedule has no idle times or gaps on the main processor and the makespan is therefore equal to the sum of the processing times. In general, more resources result in smaller makespans, and as it is in practical applications often more economic not to mobilize resources that will be unnecessary and expensive, we investigate in this paper the problem to find the smallest number B of resources that make a perfect schedule possible. We show that the decision version of this problem is NP-complete, derive new structural properties of perfect schedules, and we describe a Mixed Integer Linear Programming (MIP) formulation to solve the problem. A large number of computational tests show that (for our randomly chosen problem instances) only B=3 or B=4 resources are sufficient for a perfect schedule.

With the development of high‐performance computing, it is possible to solve large‐scale computing problems. However, the irregularity and access characteristics of computing problems bring challenges to the realisation and performance optimisation. Improving the performance of a single core makes it challenging to maintain Moore's law, and multi‐core processors emerge. A chip brings together multiple universal processor cores of equal status and has the same structure supported by an isomorphic multi‐core processor. In high‐performance computing, the granularity of computing tasks leads to the complexity of scheduling strategies. Satisfying high system performance, load balancing and processor fault tolerance at a minimum cost is the key to task scheduling in the high‐performance field, especially in specific multi‐core hardware architecture. In this study, global real‐time task scheduling is implemented in a high‐performance multi‐core system. The system adopts the hybrid scheduling among clusters and the intelligent fitting within clusters to implement the global real‐time task scheduling strategy. In the cluster scheduling policy, tasks are allowed to preempt the core with low priority, and the priority of tasks that access memory is dynamically improved, higher than that of all the tasks without memory access. An intelligent fitting method is also proposed. When the data read by the task is in the cache and the cache access ability value of the task is within a reasonable threshold, the priority of the task is promoted to the highest priority, preempting the core without the access memory task. The results show that the intelligently fitting global scheduling strategy for multi‐core systems has better performance in the nuclear utilisation rate and task schedulability.

The elastic task model enables the adaptation of systems of recurrent real-time tasks under uncertain or potentially overloaded conditions. A range of permissible periods is specified for each task in this model; during run-time a period is selected for each task from the specified range of permissible periods to ensure schedulability in a manner that maximizes the quality of provided service. This model was originally defined for sequential tasks executing upon a preemptive uniprocessor platform; here we consider the implementation of sequential tasks upon multiprocessor platforms. We define algorithms for scheduling sequential elastic tasks under the global and partitioned paradigms of multiprocessor scheduling for both dynamic and static-priority tasks, and we provide an extensive simulation-based comparison of the different approaches.

In this paper we analyze the performance of pull and push strategies in large homogeneous distributed systems where the number of job transfers per time unit is limited. Job transfer strategies which rely on lightly-loaded servers to attract jobs from heavily-loaded servers are known as pull strategies, whereas for push strategies the heavily loaded servers initiate the job transfers to lightly loaded servers. To this end, servers transmit probe messages to discover other servers that are able to take part in a job transfer. Previous work on rate-based pull and push strategies focused on the impact of the probe rate on the mean job response time. In this paper we also limit the overall migration rate and show that any predefined migration rate can be matched by both the rate-based pull and push strategies. We present closed form formulas for the mean response time (as a function of the allowed probe and migration rate) and validate their accuracy by simulation. We also introduce and analyze a new pull strategy and show that under high loads it is superior to the push strategies considered, while the push strategies offer only a very limited gain for medium to low load scenarios.

Test case prioritization techniques schedule test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal. Various goals are possible; one involves rate of fault detection, a measure of how quickly faults are detected within the testing process. An improved rate of fault detection during testing can provide faster feedback on the system under test and let software engineers begin correcting faults earlier than might otherwise be possible. One application of prioritization techniques involves regression testing, the retesting of software following modifications; in this context, prioritization techniques can take advantage of information gathered about the previous execution of test cases to obtain test case orderings. We describe several techniques for using test execution information to prioritize test cases for regression testing, including: 1) techniques that order test cases based on their total coverage of code components; 2) techniques that order test cases based on their coverage of code components not previously covered; and 3) techniques that order test cases based on their estimated ability to reveal faults in the code components that they cover. We report the results of several experiments in which we applied these techniques to various test suites for various programs and measured the rates of fault detection achieved by the prioritized test suites, comparing those rates to the rates achieved by untreated, randomly ordered, and optimally ordered suites.

Devising energy-efficient scheduling strategies for real-time periodic tasks on heterogeneous platforms is a challenging as well as a computationally demanding problem. This study proposes a low-overhead heuristic strategy called, HEALERS, for dynamic voltage and frequency scaling (DVFS)-cum-dynamic power management (DPM) enabled energy-aware scheduling of a set of periodic tasks executing on a heterogeneous multi-core system. The presented strategy first applies deadline-partitioning to acquire a set of distinct time-slices. At any time-slice boundary, the following three-phase operations are applied to obtain a schedule for the next time-slice: first, it computes the fragments of the execution demands of all tasks onto each of the different processing cores in the platform. Next, it generates a schedule for each task on one or more processing cores such that the total execution demand of all tasks is satisfied. Finally, HEALERS applies DVFS and DPM on all processing cores so that energy consumption within the time-slice may be minimized while not jeopardising execution requirements of the scheduled tasks. Experimental results show that the proposed scheme is not only able to achieve appreciable energy savings with respect to state-of-the-art (5–42% on average) but also enables a significant improvement in resource utilisation (as high as 58%).

Taking into consideration the requirements of real-time embedded systems, the processor scheduler must guarantee a constant scheduling frequency, providing determinism and predictability of tasks execution. The purpose of this study is to implement the nMPRA (multi pipeline register architecture) processor into field-programmable gate array, and to integrate the already existing scheduling methods, thus providing a preemptive schedulability analysis of the proposed architecture based on the pipeline assembly line and hardware scheduler. This study describes a hardware implementation of the real-time scheduler named nHSE (hardware scheduler engine for n tasks) and presents the results obtained using the appropriate schedulability methods used in real-time environments. The scheduling and task switch operations are the main source of non-determinism, being successfully dealt with real-time nMPRA concept, in order to improve the system's functionality. Some mechanisms used for synchronisation and inter-task communication are also taken into consideration.