Search

A number of scheduling algorithms have been proposed for real-time parallel tasks modeled as Directed Acyclic Graphs (DAGs). Many of them focus on scheduling DAG tasks with implicit deadlines. Fewer studies have considered DAG tasks with constrained deadlines or arbitrary deadlines. In this study, we propose a scheduling strategy based on fluid scheduling theory and we target DAG tasks with constrained or arbitrary deadlines. We prove that the proposed algorithm has a capacity augmentation bound of $\frac{1}{2}(1+\beta +\sqrt{(1+\beta)^2-\frac{4}{m}})$ 1 2 (1 + β + (1 + β) 2 - 4 m ) when scheduling multiple DAG tasks with constrained deadlines, in which $m$ m is the number of processors and $\beta$ β is the maximum ratio of task period to deadline. This value is lower than the current best result $\beta +2\sqrt{(\beta +1-\frac{1}{m})(1-\frac{1}{m})}$ β + 2 (β + 1 - 1 m) (1 - 1 m) . We also prove that a capacity augmentation bound of $\frac{1}{2}(1+\sqrt{2}+\sqrt{(1+\sqrt{2})^2-\frac{4\sqrt{2}}{m}})$ 1 2 (1 + 2 + (1 + 2) 2 - 4 2 m ) is guaranteed by our algorithm in the case of scheduling multiple DAG tasks with deadlines greater than periods. To the best of our knowledge, this is the first capacity augmentation bound that has been proven for scheduling multiple DAG tasks with deadlines greater than periods. Our experiments show that our algorithm outperforms the state of the art scheduling algorithms in the percentage of schedulable task sets. [ABSTRACT FROM AUTHOR]

In mobile crowdsensing, it is a challenge to assign tasks to appropriate smartphones. Existing task allocation mechanisms mainly aim at optimizing the global system performance, while ignoring the personal preferences of individual crowdsensing tasks and smartphone users. Nevertheless, in an open crowdsensing system, a task assignment is prone to be unstable if smartphone users or tasks have incentives to deviate from the global assignment, and seek for alternative choices to improve their own utilities. Besides that, during task competition, the rational smartphone users might choose to adjust their payments after the first few failures, which however, brings new challenges in achieving the stability. To address these issues, this paper constructs a distributed many-to-many matching model to capture the interaction between crowdsensing tasks and smartphone users, taking into account the budget constraints of tasks. Then, we design a stable matching algorithm to allocate the tasks to the users, and determine their payments. We prove that the proposed algorithm achieves several desirable properties including individual rationality, stability, and convergency. It is also proved that the proposed scheme achieves at least half of the optimal system efficiency when each smartphone provides homogeneous service quality. Finally, simulation results confirm the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

The problem of precisely computing the worst-case blocking time that tasks may experience is one of the fundamental issues of schedulability analysis of real-time applications. While exact methods have been proposed for more sophisticated protocols, the problem is indeed complex in case of the Priority Inheritance Protocol, even restricting the attention to uniprocessor systems, non-nested resource accesses, and non-self-suspending tasks. Besides a very simple method leading in general to loose upper bounds, only one algorithm of exponential complexity has been so far reported in literature to tighten such bounds. In this article, we describe a novel approach which, leveraging an operational research technique for modeling the problem, computes the same tight bounds in polynomial time. We then discuss the scenarios in which, assuming no conditional statements in the tasks’ code, the computed bounds derive from an actually impossible blocking chain, and we refine the initial model to more precisely compute the worst-case blocking times for any task set in any possible operating condition. [ABSTRACT FROM AUTHOR]

Fleets of cooperative drones are a powerful tool in monitoring critical scenarios requiring early anomaly discovery and intervention. Due to limited energy availability and application requirements, drones may visit target points in consecutive trips, with recharging and data offloading in between. To capture timeliness of intervention and prioritize early coverage, we propose the new notion of Weighted Progressive Coverage, which is based on the definition of time dependent weights. Weighted progressive coverage generalizes classic notions of coverage, as well as a new notion of accumulative coverage specifically designed to address trip scheduling. We show that weighted progressive coverage maximization is NP-hard and propose an efficient polynomial algorithm, called Greedy and Prune (GaP), with guaranteed approximation. By means of simulations we show that GaP performs close to the optimal solution and outperforms a previous approach in all the considered performance metrics, including coverage, average inspection delay, energy consumption, and computation time, in a wide range of application scenarios. Through prototype experiments we also confirm the theoretical and simulation analysis, and demonstrate the applicability of our algorithm in real scenarios. [ABSTRACT FROM AUTHOR]

In mobile crowdsensing, finding the best match between tasks and users is crucial to ensure both the quality and effectiveness of a crowdsensing system. Existing works usually assume a centralized task assignment by the crowdsensing platform, without addressing the need of fine-grained personalized task matching. In this paper, we argue that it is essential to match tasks to users based on a careful characterization of both the users’ preference and reliability. To that end, we propose a personalized task recommender system for mobile crowdsensing, which recommends tasks to users based on a recommendation score that jointly takes each user’s preference and reliability into consideration. We first present a hybrid preference metric to characterize users’ preference by exploiting their implicit feedback. Then, to profile users’ reliability levels, we formalize the problem as a semi-supervised learning model, and propose an efficient block coordinate descent algorithm to solve the problem. For some tasks that lack users’ historical information, we further propose a matrix factorization method to infer the users’ reliability levels on those tasks. We conduct extensive experiments to evaluate the performance of our system, and the evaluation results demonstrate that our system can achieve superior performance to the benchmarks in both user profiling and personalized task recommendation. [ABSTRACT FROM AUTHOR]

With the explosive growth in the scale of cloud computing infrastructures, reliability and energy efficiency have become important concerns considering the great complexity of cloud data centers. There is an urgent need for efficient task assignment that can dispatch tasks to appropriate cloud data center servers, which is critical to achieve reliability and energy efficiency in current cloud data centers. Most of the research on task assignment focuses on only one of the objectives of reliability and energy efficiency, while the two objectives are intrinsically conflicting with each other. In this paper, we deal with the problem of task assignment in data centers, with the objective of minimizing the energy consumption while providing failure tolerance to task execution failure. We propose a reliability-aware and energy-efficient task replica assignment algorithm based on running task replicas at a low speed and enabling multiple task replicas to share the same server resources. Each task in a job processed by the cloud computing platform has two instances: main task and task replica (shadow). Each main task runs on an individual server, and the task replica associated with the main task is assigned on a different server. The main tasks run at the full server speed, while the task replicas run at a lower rate than the main tasks. The task replicas can be mapped onto dedicated backup servers or be assigned to the servers on which the main tasks are running. Multiple task replicas can share the same server resources to reduce the number of servers required. We conduct experiments through simulations. Experimental results demonstrate that the proposed algorithm can effectively reduce the energy consumption, while achieving a good balance between the number of servers used and job completion time. [ABSTRACT FROM AUTHOR]

The mixed-criticality system provides multiple real-time applications with different criticalities in a single system. Poor energy-saving performance of the previous studies on mixed-criticality sporadic tasks are mainly due to the fact that the slack time generated from the random arrival of sporadic tasks is not taken into account. In this article, we focus on scheduling energy aware mixed-criticality sporadic tasks and take the random arrival of sporadic tasks into account. We proposed a dynamically frequency updating mixed-criticality algorithm (DFU). DFU based on the earliest deadline first scheme can exploit the slack time generated from high criticality tasks in a low criticality mode to reduce processor frequency. In addition, it also can dynamically update the utilization of sporadic tasks set to further reduce processor frequency. The simulation experiments are conducted to evaluate the performance of DFU and experimental results show that DFU consumes 34.29% less energy than that of the existing algorithms. [ABSTRACT FROM AUTHOR]

Multicore processors have become mainstream computation platforms not only for general and high-performance computers but also for real-time embedded systems. To fully utilize the computation power of multicores, software must be parallelized. Recently, there has been a rapidly increasing interest in real-time scheduling of parallel real-time tasks, but the field is still much less mature than traditional real-time scheduling of sequential tasks. In this article, we study the real-time scheduling and techniques for parallel real-time tasks based on decomposition, where a task graph is transferred to a set of independent sporadic tasks. In particular, we propose new decomposition strategies that better explore the structure feature of each task to improve schedulability. We develop schedulability tests for the global earliest deadline first (EDF) scheduling algorithm based on decomposition and three types of its variants, with their own pros and cons in different aspects. We conduct experiments to evaluate the real-time performance of our proposed scheduling algorithms against the state-of-the-art scheduling and analysis methods of different types. [ABSTRACT FROM AUTHOR]

OpenMP is a promising framework to develop parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by OpenMP specifications. One of the most interesting features in OpenMP is the support for nested parallelism, enjoying benefits in enhancing performance transparency of parallel libraries and promoting reuse of black-box code. Previous researches on DAG task scheduling mainly restrict to only one level of parallelism. The problem whether OpenMP tasks with multiple levels of parallelism are suitable to real-time systems remains open. In this paper, we study the real-time scheduling and analysis of OpenMP task systems supporting nested parallelism. First, we show that under existing scheduling algorithms in OpenMP implementations, nested parallelism indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we propose a new scheduling algorithm and develop two sound response time bounds by considering the trade-off between simplicity and analysis precision. Experiments demonstrate the efficiency of our methods. [ABSTRACT FROM AUTHOR]

In this paper, we consider parallel and sequential task offloading to multiple mobile edge computing servers. The task consists of a set of inter-dependent sub-tasks, which are scheduled to servers to minimize both offloading latency and failure probability. Two algorithms are proposed to solve the scheduling problem, which are based on genetic algorithm and conflict graph models, respectively. Simulation results show that these algorithms provide performance close to the optimal solution, which is obtained through exhaustive search. Furthermore, although parallel offloading uses orthogonal channels, results demonstrate that the sequential offloading yields a reduced offloading failure probability when compared to the parallel offloading. On the other hand, parallel offloading provides less latency. However, as the dependency among sub-tasks increases, the latency gap between parallel and sequential schemes decreases. [ABSTRACT FROM AUTHOR]

With the advent of the Internet of Things (IoT), energy-harvesting nonvolatile processors (NVPs) have become promising platforms due to their durability when running on an intermittent power supply and fast read/write operations. However, the penalties caused by an increasing amount of data to be processed and growing communication demands pose critical challenges in the scheduling of tasks on energy-harvesting NVP platforms with tight energy and latency budgets. Together with the high power switching overhead that is induced under unstable power conditions, an increase in the amount of data to be processed significantly degrades the system performance. To overcome the problems of high communication and switching overheads for energy-harvesting NVP platforms, this article proposes a novel communication-aware task-scheduling technique. The algorithm first selects one or more executable tasks to be performed based on the task benefits and then calls a task partitioning algorithm to dynamically divide the scheduled tasks. We evaluate the performance of our proposed algorithm in comparison with the performance-aware task scheduling (PATH) and greedy iterative (GI) algorithms. Experimental results show that the proposed algorithm can reduce the execution time by 17.08% and 13.72% on average compared with the PATH and GI algorithms, respectively. [ABSTRACT FROM AUTHOR]

Low latency/delay is one of the most critical requirements for the application of vehicular networks. However, frequent real-time information update caused by vehicles high mobility is liable to aggravate the delay. Meanwhile, the task migration between different vehicular edge computing (VEC) servers results in an amount of delay if the computing cannot be completed before the vehicle moves out of the coverage of the current VEC server. In this paper, the problem is concluded as when and to whom to offload the task for VEC, which is formulated as a finite horizon Markov decision process (MDP) to minimize the delay with respect to the communication, computing, handover and migration. Through characterizing the time-space correlation of vehicles mobility, the curse of dimensionality problem in MDP is resolved. Meanwhile, a general expression of the transition probabilities is derived. On this basis, the specific results of highway, 2-D street and real-data scenarios are provided as well. For practical implementation considerations, the transition probabilities are commonly uncertain primarily due to random driver behavior, inaccurate sample data and complex path environment. Under this uncertain environment,a robust time-aware MDP-based task offloading algorithm (RTMDP) is proposed, which has been proved to perform well even under the high uncertain transition probabilities by simulation results. [ABSTRACT FROM AUTHOR]

With the explosive growth of mobile devices, it is convenient for participants to perform mobile crowd sensing (MCS) tasks. It is a useful way to recruit participants to perform location-dependent tasks. We first investigate Min-Max Task Planning (MMTP) problem on time-sensitive MCS systems, considering time-sensitivity and heterogeneity of sensing tasks, and people-variability of the participants. Namely, how to design a cooperation method for the participants so that they spend as little time as possible. To address the MMTP problem, we propose a Memetic based Bidirectional General Variable Neighborhood Search (MB-GVNS) algorithm, in which all tasks are separated into groups and traveling path is planned for each participant. Moreover, we consider the task in both people-invariable and people-variable scenarios. Finally, extensive experiments are conducted to demonstrate the benefits of our method, outperforming other similar state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

With the ubiquitous usage of mobile devices, we are witnessing the emergence of commercial crowdsourcing applications that leverage the power of the crowd (workers) to collect massive data. However, the participation unbalance problem commonly occurs in existing location-dependent mobile crowdsourcing applications as workers tend to select nearby tasks while far away tasks are ignored. In this article, we propose a novel task bundling based incentive mechanism that dynamically bundles tasks with different popularity together to solve the participation unbalance problem. We consider the continuous sensing scenarios and categorize tasks into high-popularity (hot) tasks and low-popularity (cold) tasks at each round according to the real-time participation situation of tasks at the last round. We then formulate the task bundling problem as a multi-objective optimization problem, and propose a dynamic task bundling algorithm that dynamically bundles cold tasks with hot tasks at each round. The experimental results demonstrate that the bundling incentive mechanism has a more balanced participation for location-dependent tasks in mobile crowdsourcing systems. [ABSTRACT FROM AUTHOR]

Resubmission and replication are two fundamental and widely recognized techniques in distributed computing systems for fault tolerance. The resubmission based strategy has an advantage in resource utilization, while the replication based strategy can reduce the task completed time in the context of fault. However, few researches take these two techniques together for fault-tolerant workflow scheduling, especially in Cloud systems. In this paper, we present a novel fault-tolerant workflow scheduling (ICFWS) algorithm for Cloud systems by combining the aforementioned two strategies together to play their respective advantages for fault tolerance while trying to meet the soft deadline of workflow. First, it divides the soft deadline of workflow into multiple sub-deadlines for all tasks. Then, it selects a reasonable fault-tolerant strategy and reserves suitable resource for each task by taking the imbalance sub-deadlines among tasks and on-demand resource provisioning of Cloud systems into consideration. Finally, an online scheduling and reservation adjustment scheme is designed to select a suitable resource for the task with resubmission strategy and adjust the sub-deadlines as well as fault-tolerant strategies of some unexecuted tasks during the task execution process, respectively. The proposed algorithm is evaluated on both real-world and randomly generated workflows. The results demonstrate that the ICFWS outperforms some well-known approaches on corresponding metrics. [ABSTRACT FROM AUTHOR]

This paper models 1-out-of-N standby computing systems with a dynamic checkpointing policy. The system performs a real-time mission task that has to be accomplished within an allowed mission time. During the mission, to facilitate an effective failure recovery the system undergoes checkpointing procedures according to a policy that dynamically determines a checkpointing frequency based on the activated element and remaining work for completing the mission. System elements are heterogeneous; they can follow different, arbitrary types of time-to-failure distributions, have different performance and wait in different standby modes before their activation. A new numerical algorithm based on state space event transitions is first proposed to evaluate mission success probability of the real-time standby systems considered in this work. Additional new contributions are made by formulating and solving optimal dynamic checkpointing policy problems, as well as an integrated optimization problem that finds the optimal combination of checkpointing policy and element activation sequence maximizing mission success probability. Advantages of using the dynamic checkpointing policy over fixed even checkpoints are demonstrated through examples. Examples and results are also provided to illustrate effects of different mission and element parameters on mission success probability as well as on the optimal dynamic checkpointing policy. [ABSTRACT FROM AUTHOR]

This paper addresses task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, i.e., the consensus-based bundle algorithm (CBBA). These algorithms utilize a market-based decision strategy as the mechanism for decentralized task selection and use a consensus routine based on local communication as the conflict resolution mechanism to achieve agreement on the winning bid values. Under reasonable assumptions on the scoring scheme, both of the proposed algorithms are proven to guarantee convergence to a conflict-free assignment, and it is shown that the converged solutions exhibit provable worst-case performance. It is also demonstrated that CBAA and CBBA produce conflict-free feasible solutions that are robust to both inconsistencies in the situational awareness across the fleet and variations in the communication network topology. Numerical experiments confirm superior convergence properties and performance when compared with existing auction-based task-allocation algorithms. [ABSTRACT FROM AUTHOR]