Search

Mission-critical embedded systems simultaneously run multiple graphics-processing-unit (GPU) computing tasks with different criticality and timeliness requirements. Considerable research effort has been dedicated to supporting the preemptive priority scheduling of GPU kernels. However, hardware-supported preemption leads to lengthy scheduling delays and complicated designs, and most software approaches depend on the voluntary yielding of GPU resources from restructured kernels. We propose a preemptive GPU kernel scheduling scheme that harnesses the idempotence property of kernels. The proposed scheme distinguishes idempotent kernels through static source code analysis. If a kernel is not idempotent, then GPU kernels are transactionized at the operating system (OS) level. Both idempotent and transactionized kernels can be aborted at any point during their execution and rolled back to their initial state for reexecution. Therefore, low-priority kernel instances can be preempted for high-priority kernel instances and reexecuted after the GPU becomes available again. Our evaluation using the Rodinia benchmark suite showed that the proposed approach limits the preemption delay to 18 $\mu$ μ s in the 99.9th percentile, with an average delay in execution time of less than 10 percent for high-priority tasks under a heavy load in most cases.

Non-preemptive scheduling is essential to tasks that inherently disallow any preemption and useful for tasks that exhibit extremely large preemption/migration overhead; however, studies of non-preemptive scheduling have not matured for real-time tasks subject to timing constraints. In this letter, we propose an improved schedulability test for non-preemptive fixed-priority scheduling (NP-FP), which offers timing guarantees for a set of real-time tasks executed on a multiprocessor platform. To this end, we first carefully investigate the NP-FP properties, and present an observation why the existing technique is pessimistic in calculating interference from higher-priority tasks. We then develop a new technique that tightly upper bounds the amount of the interference, and show how to incorporate the technique into the existing schedulability test. Via simulations, we demonstrate that our proposed test improves schedulability performance of NP-FP up to 18%, compared with the state-of-the-art existing tests.

Data service scheduling is paramount in realization of Intelligent Transportation System (ITS). ITS services recon upon real-time information sharing among vehicular network components. To provide real time information services in vehicular networks, numerous challenges are imposed due to unique characteristics of such networks. For efficient information dissemination, there is a prime requirement of an adaptive scheduling algorithm for approximate vehicular dynamics information. In this work, a Dedicated Short Range Communication (DSRC) based vehicular communication model has been used for efficient data services in heterogeneous traffic environment. A novel Adaptive Priority data Service scheduling (AdPS) algorithm has been proposed to provide real-time data services, which is based on fuzzy logic request deadline estimation and request prioritization. The prioritized requests has been stored in multilevel queues according to the urgency of requests to provide simultaneous access. The proposed algorithm has been simulated for different traffic scenarios for a real city environment and its performance has been analyzed at different traffic instances. The proposed protocol ensures the real time service scheduling which provides fairness among the users.

During the real production system, the scheduling scheme change is mostly changed by dynamic events or new tasks. Due to the different urgency degrees of dynamic events, the corresponding scheduling methods should be adopted to ensure the production efficiency of enterprises. In this paper, an event-driven dynamic workshop scheduling model is established based on Ant Colony System (ACS), and two scheduling methods are designed to deal with dynamic events, namely parallel scheduling and parallel priority scheduling, respectively. The goal of parallel scheduling is to minimize the total makespan, while that of parallel priority scheduling is to minimize the delivery time of dynamic events. Additionally, a selective scheduling strategy is designed to determine the optimal scheduling method according to the urgency degree of dynamic events. Finally, the feasibility of the selective scheduling strategy in solving the dual-objective dynamic job shop scheduling problem (DJSP) is verified by an example experiment on DJSP as well as a large scale problem test set.

A solution to the patient scheduling problem for a case study animal hospital called Mix+Factor scheduling is proposed in this work. Mix scheduling is based on the weighted sum of patient arrival order, the job type and the priority. The priority is based on the veterinarian opinion on the treatment type. Factor is an additional function based on the psychological acceptability of the patient owners in allowing some later jobs to be moved ahead in the waiting queue. The experimental results are conducted on three synthesis workloads to create a light-load, normal-load and high-load conditions. The synthesis workloads are created according to the mixture of jobs at the case study animal hospital. The results show that the Mix+Factor algorithm provides similar or better average waiting time performance in comparison with the currently used algorithms, namely First-Come-First-Served. In addition, Mix+Factor can also provide a better scheduling in order to reduce the waiting time for specific patients such as violence animals or patients with appointments. A study on potential benefit of opening an extra treatment room shows that an extra treatment room can significantly reduce the waiting time and better serve the specific patients than that of the currently used algorithm.

This letter considers dual-criticality systems having periodic tasks with offsets scheduled by a given fixed-priority scheduler. We are interested to formally derive some feasibility interval for such systems. We prove that such an interval exists and that it is bounded by the size of four hyperperiods plus the largest task offset.

In a mobile system, mobility refers to a change in position of a mobile object with respect to time and its reference point, whereas isolation means the isolation relationship between mobile objects under some scheduling policies. Inspired by event-based formal models and the ambient calculus, we first propose the two types of special events, entering and exiting an ambient, as movement events to model and analyze mobility. Based on mobility, we then introduce the notion of the isolation of mobile objects for ambients. To ensure the isolation, a priority policy needs to be used to schedule the movement of mobile objects. However, traditional scheduling policies focus on task scheduling and depend on the strong hypothesis: The scheduled tasks are independent—that is, the scheduled tasks do not affect each other. In a practical mobile system, mobile objects and ambients interact with each other. It is difficult to separate a mobile system into independent tasks. We finally present an automatic approach for generating a priority scheduling policy without considering the preceding assumption. The approach can guarantee the isolation of the mobile objects for ambients in a mobile system. Experiments demonstrate these results.

Meeting tail latency Service Level Objective (SLO) as well as achieving high resource utilization is important to distributed storage systems. Recent works adopt strict priority scheduling or constant rate limiting to provide SLO guarantee but cause under-utilization resources. To address this issue, we first analyze the relationship between workload burst and latency SLO. Based on burst patterns and latency SLOs, we classify tenants into two categories: Postponement-Tolerable tenant and Postponement-Intolerable tenant. We then explore the opportunity to improve resource utilization by carefully allocating resources to each tenant type. We design Rate-Limiting-Priority scheduling algorithm to limit the impact of high priority tenants on low priority ones. Meanwhile, we propose Postponement-Aware scheduling algorithm which allows Postponement-Intolerable tenants to preempt system capacity from Postponement-Tolerable tenants. This helps to increase resource utilization. We propose a latency SLO guarantee framework Gecko. Gecko guarantees multi-tenant latency SLOs via combining the two proposed scheduling algorithms together with an admission control strategy. We evaluate Gecko with real production traces and the results show that Gecko admits 44% more tenants on average than state-of-the-art techniques meanwhile guaranteeing latency SLO.

In Vitro Diagnosis devices (IVD) are made of hundreds of parts. At present, time-slot scheduling method makes some parts of the device idle when they are working. Therefore, this paper proposes an emergency priority scheduling optimization algorithm. Firstly, a linear programming method is used to obtain the optimal solution with optimization objective of the shortest duration. When emergency samples arrive, rescheduling is used to ensure the effectiveness of the test. Taking a fluorescence immunoassay as an example, the time-slot scheduling method and emergency priority scheduling optimization algorithm are compared. The results show that he latter is 3/min faster than that of the former. When an emergency is added, the latter produces results in time. The proposed method has at least 12 hours MTBF (Mean Time Between Failure). This proves that the proposed method is more effective.

Time-sensitive networking (TSN) is a set of standardised communication protocols developed under the IEEE 802.1 working group. TSN aims to support deterministic communication based on network schedules that are distributively configured. It is widely considered as the future in-vehicle network solution for highly automated driving, where the requirement on timing guarantee is alongside the demand of high communication bandwidth. In this work, we study a setting of periodic control and non-control packets, with implicit and arbitrary deadlines, respectively. As the FIFO (first-in, first-out) queues in the 802.1Qbv switch incur long delay in the worst case, which prevents the control tasks from achieving short sampling periods and thus impedes control performance optimisation, we propose the first fixed-priority scheduling (FPS) approach for TSN by leveraging its gate control features. In this context, we develop a finer-grained frame-level response time analysis, which provides a tighter bound than the conventional packet-level analysis. Building upon FPS and the above analysis, we formulate a co-design optimisation problem to decide the sampling periods and poles of real-time controllers with settling time as the objective to minimise, whilst satisfying the schedulability constraint.

Intelligent transportation system (ITS) extracts efficiently and reliably and ensures security of information exchange between information infrastructures residing whether on roadside or vehicles on road by incorporating with blockchain. Also ITS includes vehicular ad hoc network (VANET), roadside units (RSU), priority scheduling, blockchain and some other vital components, for combining the according to characteristics, provides information exchange upon blockchain technology, and will give the best ITS. Basic requirements can be sent emergency, life-saving and legal information which may have nationwide critical data. To achieve the requirements for the transportation system, priority-based scheduling protocol and algorithm will be merged with efficient and reliable blockchain-based transportation which will reduce the network traffic and will not affect the service ratio and reliability of transmission channel.

International audience; The need to integrate flexible and intelligent mechanisms for energy management becomes a necessity. In this paper, we are considering a microgrid with infrastructures having production capacities and consumption needs. Several data and constraints related to the microgrid consumption have been collected, in addition to data concerning the production of renewable energy from Photovoltaic panels (PV). Data history is used as input to a neural network to predict one day ahead of consumption and production. Then, a prioritized scheduling family of algorithms is presented. First, we introduce a mathematical formulation to our problem. Then, we propose various scenarios that go from an exact solution to heuristic-based use cases, including scheduling of several energy classes with a maximum scheduling time lapse. Results show that prioritized scheduling, including time lapse based on predictions, can give more reliable results than scheduling based on bin packing.

This paper considers a discrete-time single-server infinite-capacity queue with two classes of packet arrivals, either delay-sensitive (class 1) or delay-tolerant (class 2), and a reservation-based priority scheduling mechanism. The objective is to provide a better quality of service to delay-sensitive packets at the cost of allowing higher delays for the best-effort packets. To this end, the scheduling mechanism makes use of an in-queue reserved place intended for future class-1 packet arrivals. A class-1 arrival takes the place of the reservation in the queue, after which a new reservation is created at the tail of the queue. Class-2 arrivals always take place at the tail of the queue. We study the delay characteristics for both packet classes under the assumption of a general independent packet arrival process. The service times of the packets are independent and have a general distribution that depends on the class of the packet. Closed-form expressions are obtained for the probability generating functions of the per-class delays. From this, moments and tail probabilities of the packet delays of both classes are derived. The results are illustrated by some numerical examples.

Hardware/software (HW/SW) partitioning and scheduling are the crucial steps in HW/SW co-design. They have a strong effect on performance, area, power and the system itself. In this paper, a memory-reinforced tabu search algorithm with critical path awareness (MTSP) is proposed for solving the HW/SW partitioning problem. First, the critical path (CP) algorithm can locate the critical task queues and output a reduced task graph. Second, the solution to a heuristic algorithm (HA) is used as the initial solution. Third, by introducing hash technology, adding dual memory tables improves the search strength and effectiveness of the tabu search, and the experiment is completed by priority scheduling. MTSP especially has good performance in large task graphs, while it can greatly improve system performance, especially in the case of generating a large communication penalty. The experimental results show that the average improvement over the latest efficient hybrid algorithm is up to 5%. The improvement in algorithm searching time is 66% in comparison to the popular algorithms cited in this paper.

As the limitation of energy consumption of real-time embedded systems becomes more and more strict, it has been difficult to ignore the time overhead and energy consumption of context switches for fixed-priority tasks with preemption scheduling (FPP) in multitasking environments. In addition, the scheduling for different types of tasks may disrupt each other and affect system reliability. A group-based energy-efficient dual priority scheduling (GEDP) is proposed in this paper. The GEDP isolates different types of tasks to avoid the disruption. Furthermore, it also reduces context switches effectively, thus decreasing system energy consumption. As many studies ignored the context switches&rsquo, overhead in the worst-case response time (WCRT) model, and it will affect the accuracy of WCRT, thereby affecting the system schedulability. Consequently, the WCRT model is improved based on considering context switches&rsquo, overhead. The GEDP is designed and implemented in Linux, and the time overhead and energy consumption of context switches is compared in different situations with GEDP and FPP. The experimental results show that GEDP can reduce context switches by about 1% and decrease energy consumption by about 0.6% for given tasks.

Mobile operators aim to enhance the Quality of Service (QoS) in each new mobile network generation. The upcoming 5G mobile network is expected to make a revolutionary enhancement in the provided service level. Serving diverse requirements from different mobile network users in a flexible and a dynamic way is a key demand. Thus, the 5G network-slicing concept provides an optimal and an efficient way to deal with the diversity of end users requirements and demands. In 5G, three different network slices share the network resources in a virtually isolated slicing manner. These slices will be in different priority classes. Indeed, priority scheduling algorithms are needed to guarantee the service level for each slice among all other lesser priority slices. This paper proposes a priority-based polling scheme with multiple scheduling techniques for the data traffic coming from multiple 5G network slices. Cyclic and random polling with/without priority are analyzed and discussed for multiple 5G use cases. The analytical model of the proposed priority-based polling scheme is presented and the performance measures in terms of the average waiting time and utilization are derived. The results prove that the proposed polling scheme shows a powerful ability to control the 5G virtual base-band units pool and guard the QoS of the 5G slices, which is what 5G networks need.

With the increasing trend towards using multi-core architecture for embedded systems, the study of intra-task parallelism becomes attractive and desirable in the literature. Although several work studying parallel task models has been proposed, the problem of precise scheduling analysis for the multiprocessor case has largely remained open. To this end, this paper concentrates on analyzing the response time for synchronous parallel real-time tasks scheduled on a multiprocessor platform. Specifically, by exploring the feature of each interfering task, we first present an interference analysis method with higher accuracy compared to other existing work. Considering the cost brought by a high complexity of the proposed method, we further introduce techniques to increase the efficiency with an acceptable loss of accuracy which gives more flexibility to the system designers. Finally, we provide a dynamic programming algorithm for analyzing the schedulability of the whole task set based on our proposed interference analysis technique. Experimental evaluation validates the performance and efficiency of the proposed approach by comparing with other methods.

In cloud computing, scheduling plays an eminent role while processing enormous jobs. The paralle jobs utmost need parallel processing capabilities which leads to CPU underutilization mainly due to synchronization and communication among parallel processes. Researchers introduced several algorithms for scheduleing parallel jobs namely, Conservative Migration Consolidation supported Backfilling (CMCBF) and Aggressive Migration Consolidation supported Backfilling (AMCBF). The greatest challenge of a existing scheduling algorithm is to improve the data center utilization without affecting job responsiveness. Hence, this work proposes an Effective Multiphase Scheduling Approach (EMSA) to process the jobs. In EMSA, the jobs are initially preprocessed and batched together to avoid starvation and to mitigate unwanted delay. Later, an Associate Priority Method has been proposed which prioritizes the batch jobs to minimize the number of migrations. Finally, the prioritized jobs are scheduled using Priority Scheduling with BackFilling algorithm to utilize the intermediate idle nodes. Moreover, the virtualization technology partitions the computing capacity of the Virtual Machine (VM) into two-tier VM as foreground VM (FVM) and Background VM (BVM) to improve node utilization. Hence, Priority Scheduling with Consolidation based BackFilling algorithm has been deployed in a two-tier VM that processes the jobs by utilizing the VMs effectively. Experimental results show that the performance of the proposed work performs better than other existing algorithms by increasing the resource utilization by 8%.

An emerging technology of cloud computing has major issue as scheduling the task and resource allocating. To avoid this issue, there are suggestions on different scheduling algorithm and that has its own merits and demerits. The proposed virtual task scheduling in multi cloud environment using three different scheduling algorithms such as equal load balancing (ELB) algorithm, high priority scheduling algorithm and rate based scheduling (RBS) algorithm. These different scheduling algorithms are used based on the number of tasks and number of virtual machine in multi cloud environment architecture. If the number of task is equal to number of virtual machine, ELB scheduling algorithm is used. If the number of tasks is greater than the number of virtual machine, high prioritization scheduling algorithm is used. If the number of tasks are lesser than the number of virtual machines, RBS algorithm is used. By using these three different scheduling algorithms we can improve the makespan, average efficiency of the multi cloud computing. Simulation results have analyzed the overall performance by comparing these three different scheduling algorithms. From these simulation results, proposed virtual task scheduling which increases the makespan and reduces the delay and energy consumption.

Cloud platforms supported by shared clusters are getting increasingly effective. Numerous tasks are submitted into clusters by a variety of users. Cloud platforms usually assign tasks with different priorities based on different Quality of Services (QoS) chosen by users. High-priority tasks can be executed primarily. As a consequence, preemption frequently occurs in almost all the commercial cloud platforms, such as Google and Amazon cluster. Although kill-based preemption is adopted as an optimal solution for high-priority tasks, it severely harms low-priority tasks. Especially, during the peak time, some low-priority tasks may be preempted and restarted repeatedly resulting in consuming much more precious resources including CPU cores, RAM and hard drives. Thanks to the checkpoint technology that provides an efficient solution to addressing the preemption issue. However, using checkpoint blindly will cause more resource waste. To address this issue, in this paper, we propose a concept of hybrid waiting list that holds all unfinished tasks and makes the resumption of tasks regularly. We leverage the checkpoint technology and design a novel approach based on the hybrid waiting list named Chord ( Ch eckp o int with hyb r id sche d uling method) which effectively improves the performance of shared clusters. Specifically, by checking the occupancy of resources periodically and making checkpoints for certain tasks, our approach can effectively reduce unnecessary checkpoints and improve the performance of the whole cluster, especially for low-priority tasks. Extensive simulation experiments injecting tasks from the Google cloud trace logs were conducted to validate the superiority of our approach. Compared with the ordinary priority scheduling methods adopt by several commercial clouds, the improvement of response time gained by our Chord can reach 18.94%.

Recently, the modeling and design of distributed controllers in cyber-physical systems (CPSs), which suffer from messages lost, delay variation, and jitter, has gained lots of research attentions. A special CPS, arbitrated networked control system (ANCS), has been designed for scheduling or arbitrating networks in a control system. In this paper, we propose a novel ANCS with dual communication channels. The proposed ANCS uses a hierarchical flexible time-division multiple access (TDMA)/fixed priority scheduling policy that is based on the event trigger protocol. A flat semi-dormant multicontrollers (FSDMC) model is developed for the proposed ANCS. We then model the FSDMC as an N/(d,c)-M/M/c/K/SMWV queue, and obtain various performance indices. Based on the model, a multiobjective optimization problem is then formulated to minimize the nonlinear energy consumption function and the nominal delay function presented in this study. To resolve the multiobjective optimization problem, a scheduling algorithm based on the multiobjective particle swarm optimization algorithm is proposed to generate the Pareto front and the corresponding nondominated vector sets. An optimal stopping algorithm is also designed to obtain the optimal value of the number of semi-dormant controllers. The optimal values of various parameters of the control system are obtained by using the above nondominated vector sets, and are applied to the proposed ANCS. Extensive numerical results are provided to illustrate the usefulness of the proposed algorithms and the effects of the control system parameters on the optimal policy.

CPU scheduling is an important subject to maximize CPU utilization in the context of operating systems. Multiprogramming operating systems need CPU scheduling for organization of processes to be executed. The order of process execution is determined by a CPU scheduling policy in use. The utilization of CPU depends on the selection of scheduling algorithms. There are several scheduling policies in the literature such as First-Come, First-Served scheduling, Shortest-Job-First scheduling, Last-Come, First-Served scheduling, Priority scheduling. On the other hand, there are some criteria (waiting time, throughput number, turnaround time, response time) to measure the eficiency of these policies. It is important that we choose the scheduling policy which has the minimum waiting time as this is crucial stage of utilizing CPU efficiently. This paper explores an alternative, neural network approach to build a CPU scheduling model to obtain the waiting time measure. In this paper, we will show that neural networks can be used to model scheduling policies and can predict the waiting time of processes. Three learning algorithms and three different neuron numbers in the hidden layer of the network are studied to boost the eficiency of neural network model for waiting time prediction. A comparison between Neural-Network Based Model and First-Come, First-Served scheduling, Shortest-Job-First scheduling, Last-Come, First-Served scheduling are provided. The results reveal the effectiveness of neural networks in predicting waiting times, and thus suggest that it can be useful and practical addition to the framework of operating systems.

The uncertainty due to performance variations of IC chips and resource sharing on multi-core platforms have significantly degraded the predictability of real-time systems. Traditional deterministic approaches based on the worst-case assumptions become extremely pessimistic and thus unpractical. In this article, we address the problem of scheduling a set of fixed-priority periodic real-time tasks on multi-core platforms in a probabilistic manner. Specifically, we consider task execution time as a probabilistic distribution and study how to schedule these tasks on multi-core platforms with guaranteed Quality of Service (QoS) requirements in terms of deadline-missing probabilities. Moreover, it is a well-known fact that the relationship among task periods, if exploited appropriately, can significantly improve the processor utilization. To this end, we present a novel approach to partition real-time tasks that can take both task execution time distributions and their period relationships into consideration. From our extensive experiment results, our proposed methods can greatly improve the schedulability of real-time tasks when compared with existing approaches.

We consider fixed priority sporadic tasks with arbitrary deadlines to be executed upon a uni-processor platform. Efficient schedulability tests for this task model are required for both online task admission in dynamic systems and interactive design of complex embedded real-time systems. The paper derives novel continuous upper bounds on the worst-case response times which runs in linear complexity. These bounds are not comparable to the tightest existing continuous upper bound of Bini et al. (in: Proceedings of the IEEE international conference on real-time systems symposium (RTSS’15), San Antonio, 2015) and strictly tighter under some parameters configurations. Moreover, the proposed approach allows to combine various existing methods to produce the tightest known continuous response time bounds. These results are extended to be applicable to a wide range of processor and network scheduling problems, including: release jitters, blocking times and cache related preemption delay (CRPD). Response time upper bounds are also given for tasks that are scheduled pre-emptively, co-operatively with intervals where pre-emption is deferred, and non-preemptively. Lastly, the quality of the method is analyzed and various recommendations are provided by means of numerical experiments.

In this paper, researching on task scheduling is a way from the perspective of resource allocation and management to improve performance of Hadoop system. In order to save the network bandwidth resources in Hadoop cluster environment and improve the performance of Hadoop system, a ReduceTask scheduling strategy that based on data-locality is improved. In MapReduce stage, there are two main data streams in cluster network, they are slow task migration and remote copies of data. The two overlapping burst data transfer can easily become bottlenecks of the cluster network. To reduce the amount of remote copies of data, combining with data-locality, we establish a minimum network resource consumption model (MNRC). MNRC is used to calculate the network resources consumption of ReduceTask. Based on this model, we design a delay priority scheduling policy for the ReduceTask which is based on the cost of network resource consumption. Finally, MNRC is verified by simulation experiments. Evaluation results show that MNRC outperforms the saving cluster network resource by an average of 7.5% in heterogeneous.

Software defined wide area network (SD-WAN) is a promising technique in scheduling mix-flows with different quality of service (QoS) requirements due to the decoupling of control and data planes, if the flow information, e.g., the flow size, is pre-known. In many cases, it is almost impossible to pre-know the flow size of the mix-flows before the transmission starts. In this context, how to efficiently schedule the information-agnostic mix-flows to provide SD-WAN users with better quality of experience (QoE) is a burning problem. In this paper, we propose an information-agnostic mix-flows scheduling mechanism, called QIMS, to minimize flow completion time (FCT). QIMS leverages a two stage priority scheduling mechanism, which is implemented on both the SD-WAN users and switch side. In the first stage, nondeadline flows are assigned with the highest priority, while each deadline flow is assigned with the lowest priority at its start and its priority is gradually promoted according to its urgency. More specifically, a flow is more urgent if it is closer to its deadline. In the second stage, QIMS keeps the priority of non-deadline flows unchanged, but reverses each deadline flow's priority which is assigned in the first stage to avoid packet reordering. Furthermore, we formulate the relationship between priority and urgency as a nonlinear sum-of-ratios problem with queuing theory, and derive the optimal priority promotion thresholds. The experiment results show that QIMS reduces the average FCT by 18% and improves the system throughput by 8.9%.

This paper introduce a new approach for scheduling algorithms which aim to improve real time operating system CPU performance. This new approach of CPU Scheduling algorithm is based on the combination of round-robin (RR) and Priority based (PB) scheduling algorithms. This solution maintains the advantage of simple round robin scheduling algorithm, which is reducing starvation and integrates the advantage of priority scheduling. The proposed algorithm implements the concept of time quantum and assigning as well priority index to the processes. Existing round robin CPU scheduling algorithm cannot be dedicated to real time operating system due to their large waiting time, large response time, large turnaround time and less throughput. This new algorithm improves all the drawbacks of round robin CPU scheduling algorithm. In addition, this paper presents analysis comparing proposed algorithm with existing round robin scheduling algorithm focusing on average waiting time and average turnaround time.

While the modern graphics processing unit (GPU) offers massive parallel compute power, the ability to influence the scheduling of these immense resources is severely limited. Therefore, the GPU is widely considered to be only suitable as an externally controlled co-processor for homogeneous workloads which greatly restricts the potential applications of GPU computing. To address this issue, we present a new method to achieve fine-grained priority scheduling on the GPU: hierarchical bucket queuing. By carefully distributing the workload among multiple queues and efficiently deciding which queue to draw work from next, we enable a variety of scheduling strategies. These strategies include fair-scheduling, earliest-deadline-first scheduling and user-defined dynamic priority scheduling. In a comparison with a sorting-based approach, we reveal the advantages of hierarchical bucket queuing over previous work. Finally, we demonstrate the benefits of using priority scheduling in real-world applications by example of path tracing and foveated micropolygon rendering.

We present the fairness scheduling policy from a high performance perspective.We present the whole priority scheduling policy from a timing constraint perspective.We present mixed partial priority scheduling policy from both high performance and timing constraint perspectives. As multi-core processors continue to scale, more and more multiple distributed applications with precedence-constrained tasks simultaneously and widely exist in multi-functional embedded systems. Scheduling multiple DAGs-based applications on heterogeneous multi-core processors faces conflicting high-performance and real-time requirements. This study presents a multiple DAGs-based applications scheduling optimization with respect to high performance and timing constraint. We first present the fairness and the whole priority scheduling algorithms from high performance and timing constraint perspectives, respectively. Thereafter, we mix these two algorithms to present the partial priority scheduling algorithm to meet the deadlines of more high-priority applications and reduce the overall makespan of the system. The partial priority scheduling is implemented by preferentially scheduling the partial tasks of high-priority applications, and then fairly scheduling their remaining tasks with all the tasks of low-priority applications. Both example and experimental evaluation demonstrate the significant optimization of the partial priority scheduling algorithm.

Memory is a limited resource in cost-sensitive, resource-constrained embedded applications. Preemption Threshold Scheduling (PTS) is a well-known technique for reducing the system stack size requirement. We consider Global Fixed Priority Scheduling with Preemption Threshold (gFPPT), as integration of PTS with global Fixed-Priority scheduling on a homogeneous multiprocessor platform, and formulate the optimization problem of minimizing the system stack size requirement while guaranteeing schedulability. We present schedulability analysis, optimization algorithms for priority and preemption threshold assignment, and an ILP formulation for computing system stack size requirement. Performance evaluation shows that the system stack size requirement can be reduced significantly with gFPPT compared to preemptive scheduling.

A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, which is preemptive and non-work-conserving in nature to better serve the tasks ASAP and ALAP execution preferences.Runtime techniques are also investigated to further delay (expedite) the executions of ALAP (ASAP) tasks by exploiting system slack at runtime.The proposed PPA scheme, POFP scheduler and runtime techniques are evaluated through extensive simulations with synthetic tasks, which are shown to be very effective to fulfill the tasks ASAP and ALAP execution requirements, when compared to that of the preference- oblivious RMS scheduler. Traditionally, real-time scheduling algorithms prioritize tasks solely based on their timing parameters and cannot effectively handle tasks that have different execution preferences. In this paper, for a set of periodic real-time tasks running on a single processor, where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP), we investigate Preference-Oriented Fixed-Priority (POFP) scheduling techniques. First, based on Audsley's Optimal Priority Assignment (OPA), we study a Preference Priority Assignment (PPA) scheme that attempts to assign ALAP (ASAP) tasks lower (higher) priorities, whenever possible. Then, by considering the non-work-conserving strategy, we exploit the promotion times of ALAP tasks and devise an online dual-queue based POFP scheduling algorithm. Basically, with the objective of fulfilling the execution preferences of all tasks, the POFP scheduler retains ALAP tasks in the delay queue until their promotion times while putting ASAP tasks into the ready queue right after their arrivals. In addition, to further expedite (delay) the executions of ASAP (ALAP) tasks using system slack, runtime techniques based on dummy and wrapper tasks are investigated. The proposed schemes are evaluated through extensive simulations. The results show that, compared to the classical fixed-priority Rate Monotonic Scheduling (RMS) algorithm, the proposed priority assignment scheme and POFP scheduler can achieve significant improvement in terms of fulfilling the execution preferences of both ASAP and ALAP tasks, which can be further enhanced at runtime with the wrapper-task based slack management technique.

We consider a scheduling problem of the sporadic task that shares resources.We present a new scheduling policy based on a fixed-priority scheduling.The energy management problem is considered in a real time system.Two techniques are presented to solve a sporadic task shared resources problem. Dynamic voltage scaling (DVS) and dynamic power management (DPM) are two effective techniques in a real time system. In this paper, we address the problem of the canonical sporadic task scheduling based on a fixed-priority scheduling scheme and take a generalized power model into account. The sporadic tasks share a set serially reusable, single-unit resources. First, we present a rate monotonic with dual priority scheduling policy, called RM/DPP, to solve the sporadic tasks shared resources scheduling problem and discuss the feasibility of the RM/DPP algorithm. Second, a static fixed-priority sporadic tasks scheduling algorithm with shared resources, called SFPSASR, has been put forward, which considers the off-chip workload and assumes that each task executes with its worst case execution time. Third, for energy efficiency, a dynamic fixed-priority sporadic tasks scheduling algorithm with shared resources, called DFPSASR, has been put forward, which considers the speed transition overhead and combines the DVS and the DPM technology. The experimental results show that the proposed SFPSASR algorithm can reduce the energy consumption by 42.14%~51.73% over the RM/DPP algorithm and the DFPSASR algorithm can reduce the energy consumption by 79.37%~82.94% over the SFPSASR algorithm.

The objective of the packet scheduling algorithm is to avoid the delay and drop rate in the wireless network. At the same time, without proper scheduling it may lead to high collision, delay and drop rate. This can be overcome by a proposed Enhanced Delay Sensitive Data Packet scheduling (EDSP) algorithm. This algorithm mainly focus on reduction of the delay and increase in the network lifetime and energy efficiency. This proposed EDSP algorithm follows three rules for proper scheduling such as medium selection, weight calculation and priority scheduling. After assigning the source and destination node, by using the AODV routing protocol shortest path with lesser number of relay nodes will be found. Then the source node data flows will be stored in the queue, when the queue size starts to increase, a particular threshold rate scheduling is required. Scheduling checks the channel medium, based on the busy or idle state, node may be sleep or awake state respectively. If the state is busy, all the data flows will be stored in the buffer. If the state is idle, buffered data will move to queue and then forward based high weighted data as first priority. Simulation results have analyzed the performance of the proposed algorithm in two different stages by varying the queue size of 50 and 100 cm. The proposed algorithm has increased the network lifetime and energy efficiency and decreased the delay and drop rate.

In today's scaled out systems, co-scheduling data analytics work with high priority user workloads is common as it utilizes better the vast hardware availability. User workloads are dominated by periodic patterns, with alternating periods of high and low utilization, creating promising conditions to schedule data analytics work during low activity periods. To this end, we show the effectiveness of machine learning models in accurately predicting user workload intensities, essentially by suggesting the most opportune time to co-schedule data analytics work. Yet, machine learning models cannot predict the effects of performance interference when co-scheduling is employed, as this constitutes a "new" observation. Specifically, in tiered storage systems, their hierarchical design makes performance interference even more complex, thus accurate performance prediction is more challenging. Here, we quantify the unknown performance effects of workload co-scheduling by enhancing machine learning models with queuing theory ones to develop a hybrid approach that can accurately predict performance and guide scheduling decisions in a tiered storage system. Using traces from commercial systems we illustrate that queuing theory and machine learning models can be used in synergy to surpass their respective weaknesses and deliver robust co-scheduling solutions that achieve high performance.

With the increasing trend towards using multi-cores architecture for embedded systems, the study of parallel tasks on the heterogeneous platform becomes attractive and desirable in the literature. Although several work studying parallel task models has been proposed, the problem of precise scheduling analysis for the multiprocessor case has largely remained open. To this end, this paper concentrates on analyzing the response time for typed DAG real-time tasks scheduled on a multiprocessor platform under global fixed priority scheduling. Firstly, we use the state-of-the-art method of the single typed DAG task to bound the intra-interference. Second, we use an efficient but pessimistic way to bound the carry-in interference for a higher priority task. And we also propose a new technique based on the decomposition tree method to bound the carry-out interference. Finally, we use the classic sliding technique to bound the inter-interference of each higher priority task. Experimental evaluation validates the performance and efficiency of the proposed approach by comparing with other methods.

This chapter presents a multiple parallel applications scheduling optimization with respect to high performance and timing constraint. We first present the fairness and the whole priority scheduling algorithms from high performance and timing constraint perspectives, respectively. Thereafter, we mix these two algorithms to present the partial priority scheduling algorithm, which can satisfy the deadlines of more high-priority applications and reduce the overall schedule length of the system. The partial priority scheduling algorithm is implemented by preferentially scheduling the partial tasks of high-priority applications, and then fairly scheduling their remaining tasks with all the tasks of low-priority applications. Further, each application has different criticality levels (e.g., severity), and missing the deadlines of certain high-criticality functions may cause fatal injuries to people. Therefore, we present the multiple heterogeneous earliest finish time (F_MHEFT) algorithm for a multiple parallel applications with the mixed-criticality on heterogeneous distributed embedded systems. Next, we propose a novel algorithm called the deadline-span of multiple heterogeneous earliest finish time (D_MHEFT), which is a scheduling algorithm for multiple mixed-criticality applications. The F_MHEFT algorithm aims at improving the performance of systems, while the D_MHEFT algorithm tries to meet the deadlines of more high-criticality functions by sacrificing a certain performance. At the end of this chapter, different experiments will be presented and their results demonstrate that the partial priority scheduling algorithm achieves the significant optimization, and the D_MHEFT algorithm can significantly reduce the deadline miss ratio (DMR) while keeping satisfactory performance over existing methods.

One of the major sources of pessimism in the response time analysis (RTA) of globally scheduled real-time tasks is the computation of an upper-bound on the inter-task interference. This problem is further exacerbated when intra-task parallelism is permitted because of the complex internal structure of parallel tasks. This paper considers the global fixed-priority (G-FP) scheduling of sporadic real-time tasks when each task is modeled by a directed acyclic graph (DAG) of concurrent subtasks. We present a RTA based on the concept of problem window, a technique that has been extensively used to study the schedulability of sequential task in multiprocessor systems. The problem window approach of RTA usually categorizes interfering jobs in three different groups: carry-in, carry-out and body jobs. In this paper, we propose two novel techniques to derive less pessimistic upper-bounds on the workload produced by the carry-in and carry-out jobs of the interfering tasks. Those new bounds take into account the precedence constraints between subtasks pertaining to the same DAG. We show that with this new characterization of the carry-in and carry-out workload, the proposed schedulability test offers significant improvements on the schedulability of DAG tasks for randomly generated task sets in comparison to state-of-the-art techniques. In fact, we show that, while the state-of-art analysis does not scale with an increasing number of processors when tasks have constrained deadlines, the results of our analysis are barely impacted by the processor count in both the constrained and the arbitrary deadline case.

The study of parallel task models executed with predictable scheduling approaches is a fundamental problem for real-time multiprocessor systems. Nevertheless, to date, limited efforts have been spent in analyzing the combination of partitioned scheduling and non-preemptive execution, which is arguably one of the most predictable schemes that can be envisaged to handle parallel tasks. This paper fills this gap by proposing an analysis for sporadic DAG tasks under partitioned fixed-priority scheduling where the computations corresponding to the nodes of the DAG are non-preemptively executed. The analysis has been achieved by means of segmented self-suspending tasks with nonpreemptable segments, for which a new fine-grained analysis is also proposed. The latter is shown to analytically dominate state-of-the-art approaches. A partitioning algorithm for DAG tasks is finally proposed. By means of experimental results, the proposed analysis has been compared against a previouslyproposed analysis for DAG tasks with non-preemptable nodes managed by global fixed-priority scheduling. The comparison revealed important improvements in terms of schedulability performance.

Unbalanced load is one of the major issues of distributed system which leads to worst utilization of available resources. All existing dynamic load balancing algorithms (DLBA) start balancing activities after the system becomes unbalanced. It is more appropriate to design load balancing algorithm that can plug into scheduling algorithm and helps scheduling algorithm to schedule incoming jobs in such way that system remains in balanced state without increasing unnecessary system overhead. In this paper, we have designed a pluggable to scheduler DLBA which can schedule incoming jobs by considering current load status of clusters. The designed algorithm is plugged with priority scheduling algorithm. The experimental results show that designed algorithm improves cluster utilization over scheduling and predication based algorithms.

The calculation of massive data has always been an significant research topic, and the data calculation job scheduling system is an important platform to deal with this problem. There are many scheduling systems in use, however, their functions are not perfect and cannot meet the needs of users. This paper designs a novel architecture of scheduling system for big data framework. The system has basic scheduling functions, such as algorithm job assignment, job priority scheduling, job result management. It supports three algorithms to schedule jobs: scheduling-in-order algorithm, scheduling-by-priority algorithm, and scheduling-by-resource algorithm, meanwhile implementing dynamic switching of these algorithms. The system has a graphical interface which greatly facilitates interaction between the system and the user.

The rise of technology has revolutionized the way we do almost anything, apart from our education system model which still remains the same. The only difference technology has made to education is that now traditional classroom lectures can be heard at a distant place as well. Other than this, there has been no contribution made to the quality of practical learning in engineering courses. In order to bridge this gap between theoretical and practical learning, we have taken one of the most important areas of Computer Science and Engineering, i.e., CPU scheduling policies in operating systems. Till now, we have just taught students about the working behavior of scheduling policies either diagrammatically or through simulation, but here we are presenting a review on the real-time implementation of scheduling policies by creating various kernels for different types of operating systems which would run first-in, first-out (FIFO), round-robin (RR), and priority scheduling policies, respectively. This helps students to understand and appreciate the behavior of these scheduling policies in a real-time environment and to analyze various parameters practically. The analyzed behavior makes students understand the advantages and drawbacks of each policy on a real-time operating system. This approach is need of the hour in order to enhance our education system.

Consider uniprocessor platforms, the scheduling of synchronous implicit deadline periodic task sets and the dual priority scheme where each task is assigned two fixed priorities. That is, at run time each task starts executing using its primary priority and is promoted if not completed at an intermediate deadline. We present counter-intuitive examples illustrating how difficult this scheduling problem is. We propose a preprocessing approach to remove from the scheduling problem lowest priority viable tasks as defined by Audsley's procedure. We revisit one solution called RM + RM conjectured optimal. We propose a procedure to compute promotion deadlines based on multiple simulations over an hyperperiod called FDMS. That solution has an exponential time complexity but an experimental success ratio of 100%. Then we propose a new sub-optimal solution to assign priorities called 1 /RM + RM along with a very simple promotion deadline assignment scheme called RML for which no simulation are required, the procedure is simple and the success ratio is close to 99.99%. We show that the method is fast and scalable to very large task sets which makes it ideal for practical applications., info:eu-repo/semantics/published

This paper considers Dual Priority (DP) scheduling of constrained deadline sporadic tasks on uniprocessor. The initial fixed priority of each job of a task is promoted to a higher priority (called, promoted priority) after a fixed time interval (called, promotion point) relative to the release time of that job. DP scheduling alters the default preemptive behavior of traditional fixed priority (FP) scheduling to efficiently utilize the processor as close as possible to that of the optimal earliest deadline first (EDF) scheduler. In this paper, we address some of the main challenges of DP scheduling including derivation of a sufficient schedulability test, determination of promotion point of each task1. To the best of our knowledge, this test is the first schedulability test for DP scheduling applicable to constrained deadline sporadic tasks. The test is applicable for any given promotion points of the tasks and has pseudo-polynomial time complexity. We also propose two different heuristics to assign the promotion points, and experimental results show that the proposed test achieves performance very close to that of EDF scheduling.

Real-Time Monotonic algorithm (RMA) is a widely used static priority scheduling algorithm. For application of RMA at various systems, it is essential to determine the system’s feasibility first. The various existing algorithms perform the analysis by reducing the scheduling points in a given task set. In this paper we propose a schedubility test algorithm, which reduces the number of tasks to be analyzed instead of reducing the scheduling points of a given task. This significantly reduces the number of iterations taken to compute feasibility. This algorithm can be used along with the existing algorithms to effectively reduce the high complexities encountered in processing large task sets. We also extend our algorithm to multiprocessor environment and compare number of iterations with different number of processors. This paper then compares the proposed algorithm with existing algorithm. The expected results show that the proposed algorithm performs better than the existing algorithms.

Executing heterogeneous workloads with different priorities, resource demands and performance objectives is one of the key operations for today's data centers to increase resource as well as energy efficiency. In order to meet the performance objectives of diverse workloads, schedulers rely on evictions even resulting in waste of resources due to lost executions of evicted tasks. It is not straightforward to design priority schedulers which capture key aspects of workloads and systems and also to strike a balance between resource (in)efficiency and application performance tradeoff. To explore large space of designing such schedulers, we propose a trace-driven cluster management framework that models a comprehensive set of system configurations and general priority-based scheduling policies. In particular, we focus on the impact of task evictions on resource inefficiency and task response times of multiple priority classes driven by Google production cluster trace. Moreover, we propose a system design as a use case exploiting workload heterogeneity and introducing workload-awareness into the system configuration and task assignment. Trace driven cluster management framework for priority scheduling is proposed.Tradeoff between evictions and response time of priorities is analyzed.Effects of different eviction policies are explored by trace driven simulations.Workload-aware system is proposed to improve response time of heterogeneous workloads.

Scheduling driverless vehicles with different priorities to pass through intersections efficiently and safely has been becoming an important passing-through intersection (PTI) problem in the field of novel intelligent traffic systems (ITS), which is increasingly becoming cyber–physical-fused and social-service-oriented. Considering new emerging features with possible priorities, a novel centralized priority scheduling mechanism is mainly explored in this paper. First, related pivotal aspects of environment and driverless vehicles are modeled by fusing their physical and kinematic characters. Based on these models, PTI-related motions are further abstracted as several reservation-oriented standard states and actions. Then, an event-triggered and state-driven autonomous control procedure is designed. By mapping vehicular relations in spatiotemporal domain into time–distance windows, a universal passing-through principle, rules, and priority-based scheduling mechanisms are proposed and described in detail. Finally, a priority scheduling algorithm sPriorFIFO is proposed and designed. These models and mechanisms are then implemented within an algorithm simulator, through which scheduling performances are verified and evaluated.

Provisioning guaranteed Quality of Service (QoS) in multiservice wireless internet is challenging due to diverse nature of end-user traffic (e.g., voice, streaming video, interactive gaming) passing through heterogeneous interconnected domains with their own policies and procedures. Numerous studies have shown that multimedia traffic carried in wireless internet possesses self-similar and long-range dependent characteristics. Nonetheless, published work on wireless traffic modeling is merely based on traditional Poisson traffic distribution which fails to capture these characteristics and hence yield misleading results. Moreover, existing work related to self-similar traffic modeling is primarily based on conventional queuing and scheduling combinations which are simple approximations.This paper presents a novel analytical framework for G/M/1 queuing system based on realistic internet traffic distribution to provide guaranteed QoS. We analyze the behavior of multiple classes of self-similar traffic based on newly proposed scheduling-cum-polling mechanism (i.e., combination of priority scheduling and limited service polling model). We formulate the Markov chain for G/M/1 queuing system and present closed form expressions for different QoS parameters i.e., packet delay, packet loss rate, bandwidth, jitter and queue length. We develop a customized discrete event simulator to validate the performance of the proposed analytical framework. The proposed framework can help in building comprehensive service level agreements for heterogeneous wireless domains.

With the increase in user mobility the most challenging issues are data scheduling which premises its users high quality of service in the context of the interoperability for microwave access in WiMAX for vehicular ad-hoc network (VANET). There is no complete proof of existing techniques accessible to provide better quality as there is a starvation problem due to the uncertainty in decision process with imprecise data. In VANET for the sake of interest while vehicles started increasing more and more in network traffic this paper devised a two stage Optimized priority scheduling scheme known as Evolving Intuitionistic Fuzzy Priority Classifier with Bio-inspiration Based Scheduling Scheme. This work takes into account the hesitation degree of each factor for priority and the bio-inspiration based classification. Through our simulation, it is shown that the projected proposal can work to acclimatize and make competent to improve the existing VANET approaches in terms of high spectrum effectiveness and low outage probability.

Automotive ECUs have been upgraded with multicore processor implementation. It has the benefits of achieving high computing power without increasing the clock speed. System developers partition the automotive application tasks to have parallelizability and avoid interference between various software modules. Task intensive applications are assigned to multiple CPU cores. To improve the performance of such systems, there has to be an efficient task scheduler. In this regard, the Automotive Open System Architecture (AUTOSAR) suggests partitioned static priority scheduling for parallelized software for the multicore ECUs. In this approach, the difficulty lies with task clustering and partitioning for specific cores. There is no exact criterion to be followed to partition the tasks. Due to which cores are not balanced with loads. Under contingency conditions, there are chances of tasks missing deadlines. This paper addresses this issue by exploring a mixed approach scheduling algorithm which has features of both static and dynamic scheduling and also few adaptations of partitioned and global scheduling. With this algorithm, high load conditions under contingency consequences are tested. This algorithm was run and tested using a scheduling simulator with real time task models of periodic tasks, angle synchronous interrupts and event triggered interrupts. The performance parameters considered here are, the % of core utilization, response time, deadlines missing rate. It has been verified that, this proposed algorithm is able to find a feasible schedule under various contingency scenarios and contributes to improve the safety level of the vehicle.

A hardware scheduler is developed to improve real-time performance of soft-core processor based computing systems. A hardware scheduler typically accelerates system performance at the cost of increased hardware resources, inflexibility and integration difficulty. However, the reprogrammability of FPGA-based systems removes the problems of inflexibility and integration difficulty. This paper introduces a new task-queue architecture to better support practical task controls and maintain good resource scaling. The scheduler can be configured to support various algorithms such as time sliced priority scheduling, Earliest Deadline First and Least Slack Time. The hardware scheduler reduces scheduling overhead by more than 1,000 clock cycles and raises the system utilization bound by a maximum 19.2 percent. Scheduling jitter is reduced from hundreds of clock cycles in software to just two or three cycles for most operations. The additional resource cost is no more than 17 percent of a typical softcore system for a small scale embedded application.