Search

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.

Delay-tolerant networks are sparse mobile ad hoc networks in which there is typically no complete path between the source and destination. Although many routing schemes for delay-tolerant networks have been proposed, they do not address fairness issues in terms of the workload/traffic handled at each node and the share of throughput among different destination nodes. In this paper, we propose a socially aware routing strategy that optimizes both fairness and throughput. A relay node is selected based on the multi-hop delivery probability and its queue length. The effect of queue length control is to divert traffic away from highly connected nodes and allows nodes to explore less-congested paths to the destination. This helps balance the network loads, thus achieving workload fairness. Furthermore, to achieve throughput fairness, we sort arriving messages into different destination-based queues. Messages are then scheduled following a two-level forwarding strategy that optimizes throughput fairness using round-robin and delivery ratio using priority scheduling. Extensive real-trace-driven simulation results show that our scheme outperforms existing algorithms in terms of the delivery ratio. Furthermore, our scheme achieves a high throughput fairness, while distributing the network loads more evenly, with the top 10% of network nodes handling only 22% of the forwardings. Copyright © 2016 John Wiley & Sons, Ltd.

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.

The integrated energy system is of great significance to improve the efficiency of social energy utilization, promote the large-scale consumption of renewable energy and the cascade utilization of energy. In view of the uncertainty of cooling, heating and electric load demand of users, this paper proposes a load priority supply model for integrated energy service providers, which considers the user satisfaction and the penalty function of energy supply interruption, and is used to deal with the scheduling optimization of various uncertain energy demand and translatable load. The optimal scheduling mathematical model of community integrated energy system is established. The various optimization objectives and the constraints of different energy demand are considered, the heuristic algorithm is used to solve the optimal scheduling, and the economic of operation mode is analyzed. The model can effectively reflect the impact of energy demand, user satisfaction and system cost on the priority of supply load, and provide the optimal decision to weigh the system cost and user satisfaction. The simulation results show the feasibility and effectiveness of the proposed model.

Many researches have focused on energy management for the processor. However, DPM via I/O device scheduling for real-time periodic tasks with shared resources has drawn little attention. We address the problem of the I/O device energy consumption minimisation for shared resources. Furthermore, we present an energy-aware IO devices fixed-priority scheduling algorithm based on the RM scheduling. It contains two parts: job scheduling and device scheduling. Job scheduling ensures that each task can complete its execution within its deadline. Device scheduling decides to turn off devices to save energy. The experimental results show that it can achieve significant energy savings.

This paper focuses on priority based processing of streaming data. One of the greatest challenges in big data analytics is responding to a bursty input load. The common solutions are to use dynamic resource provisioning techniques, however, these techniques may not respond quickly enough to the change in the load. Another option is to overprovision, but this results in wasted computing resources. This paper describes a technique that can be used in cases where resources are statically provisioned. This technique enables users to prioritize certain input data items so that in cases where the load suddenly increases, the high priority items are given precedence over low priority items. This technique is implemented on the Spark Streaming engine.

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.

Load balancing is one of the major requirements of distributed systems for the effective utilization of resources. Existing dynamic load balancing algorithms take the corrective actions once the system becomes unbalanced. It could be more appropriate to design algorithm which can schedule incoming jobs in such way that system remains in balance state without increasing unnecessary system overhead. In this paper, prediction-based dynamic load balancing algorithm is designed which can balance load between clusters using predicted status of clusters. The designed algorithm is applied on priority scheduling algorithm. Our experimental result shows that the prediction-based load balancing algorithm improves the cluster utilization as compared to existing scheduling algorithm.

The transmission delay of CAN gateway message will affect the real-time performance of the whole CAN network. Firstly, the transmission delay model of CAN gateway message is analyzed in this paper. After two algorithms, ID Priority Scheduling (IDPS) algorithm and Earliest Deadline First (EDF) algorithm, are compared, the Dynamic Feedback based Hybrid Priority Scheduling (DFHPS)algorithm is proposed with implementation algorithm. Finally, Hardware In Loop (HIL) simulation test is conducted. The test results show that this method can effectively reduce the delay of high-priority messages when the network load rate is high, and ensure that low-priority messages can also get good response time.

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.

The success indicator of an institution and company is when the available resources have been used effectively and efficiently. The limited resources available can cause delays in ongoing business processes. The delay in a business process is always closely related to financing. The slower the business process runs, the more the expenses that must be incurred for labor and material costs. Therefore, it is necessary to optimize the cost and time for an organization. It can be minimized by using goal programming. In goal programming, weights are given to make sense of which activities to be watched. In this research using lingo software to calculate goal programming.

We present Sincronia, a near-optimal network design for coflows that can be implemented on top on any transport layer (for flows) that supports priority scheduling. Sincronia achieves this using a key technical result --- we show that given a "right" ordering of coflows, any per-flow rate allocation mechanism achieves average coflow completion time within 4X of the optimal as long as (co)flows are prioritized with respect to the ordering. Sincronia uses a simple greedy mechanism to periodically order all unfinished coflows; each host sets priorities for its flows using corresponding coflow order and offloads the flow scheduling and rate allocation to the underlying priority-enabled transport layer. We evaluate Sincronia over a real testbed comprising 16-servers and commodity switches, and using simulations across a variety of workloads. Evaluation results suggest that Sincronia not only admits a practical, near-optimal design but also improves upon state-of-the-art network designs for coflows (sometimes by as much as 8X).

U ovom radu opisan je problem optimizacije prioritetnog raspoređivanja u okolini nesrodnih strojeva. Opisane su metode strojnog učenja koje se koriste u generiranju rasporeda, genetsko programiranje i neuronska mreža. Opisana je arhitektura grafičkog procesora i tehnologija CUDA. Opisane su tehnike paralelizacije evaluacije rješenja navedenih metoda. Implementirana je programska podrška za izvođenje navedenih metoda na grafičkom procesoru u sklopu programskog okvira ECF. Izmjereni su rezultati ubrzanja i komentirani problemi koji se javljaju. This thesis describes the problem of priority scheduling optimization in the environment of unrelated machines. It also describes the machine learning methods, genetic programing and neural networks used for generating schedules. Furthermore, this thesis describes the architecture of a graphics processor and the CUDA technology, as well as the paralelization techniques that are used for the solution evaluation of these methods. Software support for GPU execution is implemented within the ECF framework. Finally, the thesis reports on speedup measures and comments on the problems that arise.

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.

This paper presents a benchmark development and the analysis of communication times in a CAN (Controller Area Network) bus. Preemptive and fixed priority scheduling is taken as departure point for the initial experiments and analysis. This method would be adapted for programming CAN messages without preemption of the shared communications channel. It is also complemented by a specific priority assignment algorithm, suitable for non-preemptive systems. A real CAN network is used for the experiments, and results are analyzed from the point of view of real-time performance and CAN specification. We have found well known, deterministic, and correct performance communication times. Messages and signals are delivered within deadlines, a fundamental requirement for a real-time system.

Mobile health is a new area of technology that gives the health care system a new face and place in the world. With the support of Body Area Network the m-health application has to make a lot of changes in the area of health support. There are so many research works has been conducted to make the application efficient. As in the case of any network traffic the m-health application also suffers problems. The paper put forward a new idea of scheduling the vital signals from the body with the help of queuing theory. It uses some analytical modeling, by considering the signal packets from sensors are following poisons distribution and the packets are arriving randomly. From the queuing theory uses some equations to find the average waiting time, maximum number of packets waiting for the service, efficiency of the system etc. Here the major issues while incorporating BAN with m-health is the number of nodes and distance from the patients to the receiving station, Number of servers in the receiving station, Priority of the signals etc.

The context of this paper is the two-choice paradigm which is deeply used in balanced online resource allocation, priority scheduling, load balancing and more recently in population protocols. The model governing the evolution of these systems consists in throwing balls one by one and independently of each others into n bins, which represent the number of agents in the system. At each discrete instant, a ball is placed in the least filled bin among two bins randomly chosen among the n ones. A natural question is the evaluation of the difference between the number of balls in the most loaded bin and the one in the least loaded. At time t, this difference is denoted by \(\text {Gap}(t)\). A lot of work has been devoted to the derivation of asymptotic approximations of this gap for large values of n. In this paper we go a step further by showing that for all \(t \ge 0\), \(n \ge 2\) and \(\sigma > 0\), the variable \(\text {Gap}(t)\) is less than \(a(1+\sigma )\ln (n) + b\) with probability greater than \(1-1/n^\sigma \), where the constants a and b, which are independent of t, \(\sigma \) and n, are optimized and given explicitly, which to the best of our knowledge has never been done before.

We study the many-server queue shown in Figure 1(a). Customers from class j ∈ {1, 2} arrive according to renewal processes having rate λj > 0 and request processing. There are N ∈ {1, 2,…} servers, each working at rate one. All servers are fully flexible; that is, every server can serve customers from both classes. Each customer has a randomly distributed patience time that may depend on the class and reneges (abandons the system without receiving service) if service does not begin before the patience time expires. The system incurs the penalty p1 > 0 when a class 1 customer reneges and the penalty p2 > 0 when a class 2 customer reneges. Upon arrival, each class j customer independently samples from the distribution determined by cumulative distribution function (cdf) [Formula: see text] having mean 1/θj < ∞ to find its patience time and from the distribution determined by cdf [Formula: see text] having mean 1/μj < ∞ to determine its service time (that is, the required processing time).

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.

This papercarries out a survey of sufficient schedulability analysis forfixed priority (FP) scheduling. The most common used fixed priority assignment is the rate monotonic (RM) algorithm, according to its policy, the task priorities are ordered based on their activation rates, so that the task with the shortest period is assigned the highest priority. However, when each task’s relative deadline is not equal to its period, the RM algorithm is not suitable to assign the task priorities. When relative deadlines are less than or equal to periods,the deadline monotonic (DM) algorithm can be deployed to schedule the tasks. The utilization based schedulability analysis has the advantage of simple implementation, and manyexisting schedulability analyses on uniprocessor are covered.

Packet scheduling is one of the critical issues in wireless sensor networks. In WSNs most existing scheduling mechanisms use FCFS, non-preemptive or preemptive priority algorithms. However, most of these algorithms incur high processing overhead and high end-to-end transmission delay due to the FCFS concept and starvation of real time and nonreal time data packets in non-preemptive and preemptive priority scheduling algorithms. Also, these packet scheduling algorithms are predetermined and hence cannot change in application requirements of WSNs. Therefore, in this paper, we propose a dynamic multilevel priority (DMP) packet scheduling algorithm to overcome the short comes like starvation of real time data, end-to-end or data transmission delay, and to make the packet scheduling dynamic. It is well known that in DMP scheduling scheme, nodes are organized in hierarchical structure and each node (except those nodes which are located at last level of hierarchical structure) has three level of priority queues in which real time data packets go to highest priority queue and non-real time data packets go to other two queues based on certain threshold levels of their estimated processing time. The DMP scheme proposed in this work was implemented with network simulator (NS2) v.2.32. The results obtained (end-to-end delay, average waiting time, network lifetime, and energy consumption) indicate the proposed DMP scheme is superior to existing first come first serve (FCFS) packet scheduling scheme. General Terms Wireless Sensor Network, FCFS.

The ever increasing size and complexity of large-scale datacenters enhance the difficulty of developing efficient scheduling policies for big data systems, where priority scheduling is often employed to guarantee the allocation of system resources to high priority tasks, at the cost of task preemption and resulting resource waste. A large number of related studies focuses on understanding workloads and their performance impact on such systems; nevertheless, existing works pay little attention on evicted tasks, their characteristics, and the resulting impairment on the system performance. In this paper, we base our analysis on Google cluster traces, where tasks can experience three diffierent types of unsuccessful events, namely eviction, kill and fail. We particularly focus on eviction events, i.e., preemption of task execution due to higher priority tasks, and rigorously quantify their performance drawbacks, in terms of wasted machine time and resources, with particular focus on priority. Motivated by the high dependency of eviction on underlying scheduling policies, we also study its statistical patterns and its dependency on other types of unsuccessful events. Moreover, by considering co-executed tasks and system load, we deepen the knowledge on priority scheduling, showing how priority and machine utilization affect the eviction process and related tasks.

The objective of this paper is to modify Round Robin scheduling for soft real time systems. It introduces a variation of round robin algorithm which can schedule tasks considering their priorities in a round robin fashion. Simple Round Robin scheduling algorithm and Priority scheduling algorithm, both have their own drawbacks. The proposed algorithm removes the drawbacks of Round Robin scheduling and Priority scheduling. The proposed scheduling algorithm calculates different time slices for individual processes considering their priorities. Experimental analysis reveals that the proposed algorithm produces better average turnaround time, average waiting time and less number of context switches than some existing algorithms useful for interactive systems. KeywordsOperating System; Scheduling; Round Robin Algorithm; Context switch; Turnaround time; Average Waiting time __________________________________________________*****_________________________________________________

This paper considers the problem of design optimization for real-time systems scheduled with fixed priority, where task priority assignment is part of the decision variables, and the timing constraints and/or objective function linearly depend on the exact value of task response times (such as end-to-end deadline constraints). The complexity of response time analysis techniques makes it difficult to leverage existing optimization frameworks and scale to large designs. Instead, we propose an efficient optimization framework that is three magnitudes (1,000×) faster than Integer Linear Programming (ILP) while providing solutions with the same quality. The framework centers around three novel ideas: (1) An efficient algorithm that finds a schedulable task priority assignment for minimizing the average worst-case response time; (2) The concept of Maximal Unschedulable Deadline Assignment (MUDA) that abstracts the schedulability conditions, i.e., a set of maximal virtual deadline assignments such that the system is unschedulable; and (3) A new optimization procedure that leverages the concept of MUDA and the efficient algorithm to compute it.

Compared to fixed-priority preemptive scheduling (FPPS), fixedpriorityscheduling with preemption thresholds (FPTS) reduces memoryrequirements, the cost of arbitrary preemptions, and it has beenshown to improve the schedulability ratio of task-sets. FPTS hasbeen viewed as a potential successor to FPPS as a de facto standardin industry, where it is already supported by both OSEK andAUTOSAR compliant operating systems.In this paper, we present and prove a novel exact best-case responsetime analysis for independent real-time periodic tasks witharbitrary deadlines scheduled using FPTS. Moreover, we presentan evaluation of our novel analysis for FPTS with the best-caseresponse time analysis for FPPS when ignoring the tasks that cannotpreempt a task. For the majority of the cases in our evaluation,the best-case response time analysis for FPPS yields a tight lowerbound for the response time of a task scheduled using FPTS.

At present, the safety computer use the first come first served (FCFS) approach to transmit data stream, but this method does not distinguish the data stream types, which may cause safety critical data stream transmission timeout. In order to meet the communication requirements of the future safety computer, by analyzing the characteristics of communication data and the main factors influencing real-time performance in the safety computer, the constrained multilevel priority scheduling strategy is proposed. This strategy consider the constraint relation between data frames under the conditions of meeting the multi-priority when the data to be transmitted. Through the network calculation method, the communication delay of different data stream in the two modes is analyzed. The improved scheduling strategy shortens the maximum delay of emergency safety critical data stream by 22.5% in the current safety computer under the condition of increasing the limited delay of non-safety critical data stream, so the strategy can effectively improve communication real-time performance of emergency safety critical data stream.

Operating system is the core of computer science and task scheduling is the major topic in this domain. Priority base scheduling is always remains hot topic in the domain of operating systems. In Priority base printing always higher priority given to those printings jobs which are processed more quickly rather than the lower priority base printings jobs. In this way low priority jobs are delayed again and again. In this research detail study is conducted regarding the scheduling algorithms in operating system. Priority base printings become bottlenecks who are assigned lowest priority. They may have to wait till their turn may be up to mid night in large departments. Now we are going to discuss a specific algorithm which can solve above issues in a smart way. A new method is proposed to solve the priority scheduling problems. This method is very handy for those users who are assigned a higher priority authority in printing mechanism. It also allows the lowest priority base printing to print data. In this solution we are not going to ignore the highest printing jobs. The highest priority base printing jobs will be continued in the same way. Our main objective is to maintain a balance between the high priority and low priority printing jobs without suffering from continues delay.

Fixed-priority scheduling with preemption thresholds (FPTS) is supported by the AUTOSAR and OSEK standards as a scheduling policy. Since FPTS is a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority nonpreemptive scheduling (FPNS), it aims to improve schedulability. In this paper, we prove, as an intermediate step towards the exact best-case response time analysis for FPTS, that the best-case computation time of a non-preemptive task scheduled under FPTS or FPNS is a tight lower bound for its response time. In addition, we illustrate by means of an example that the best-case response time analysis for FPTS is most likely not a straight forward extension of the current best-case analysis for FPPS.

Aiming at the situation of priority scheduling algorithm of chaos, later redundant processing in the task scheduling on current multi-core heterogeneous processors, this paper proposes a task scheduling algorithm with weighted priority algorithm-- WPTS. It is related to three attribute values of the main reference tasks, which can be obtained by weighted comparison that can overcome the confusion and redundancy of task selection to a certain extent. And it can maintain the priority processing of priority scheduling processor in the processor task allocation process to improve the computational efficiency, reduce idle memory accounted rate. In addition, redundant task processing is introduced in order to achieve a better recovery of the processor’s time period and the effect of time reduction. Compared with the HCPED algorithm and HDEFT algorithm, the WPTS algorithm has a better performance.

Priority scheduling among running transactions is one of the most important issues in the design of mobile distributed real-time database systems (MDRTDBS). In MDRTDBS, to perform correct transaction scheduling, several priority heuristics with different concurrency control methods are used, so that, it could minimize transaction abort rate. Priority heuristic approaches deal with problem of assigning the priorities among transactions so that it could helpful with concurrency control (CC) mechanism to achieve typical time constraint. In recent few years, the performance of CC protocols of distributed real-time database Systems (DRTDBS) have been examined using different priority heuristics methods. However, very few numbers of approaches have been proposed on priority heuristics for wireless environments. Hence, a new priority heuristic method based on deadline computed by considering write only operations has been proposed for wireless environments. It is improved priority heuristic approach which shows better results than earlier priority heuristics. In recent years, researchers have classified the transactions in two types called as Read only transactions (ROT) and Update transaction. This new priority heuristic for mobile environment considers ROT and update transactions separately. Further, a study has also been done to examine the impact of these priority heuristics as compared with number of locks and mixed method approaches.

Scheduling real-time applications on general purpose multicore platforms is a challenging problem from a timing analysis perspective. Such platforms expose uncontrolled sources of interference whenever concurrent accesses to memory are performed. The non-deterministic bus and memory access behavior complicates the estimations of applications' worst-case execution times (WCET). The 3-phase task model seems a good candidate to circumvent the uncontrolled sources of interference by isolating concurrent memory accesses. A task is divided in three successive phases; first, the task loads its instruction and data in a local memory, then it executes non-preemptively using those pre-loaded instructions and data, and finally, the modified data are pushed back to main memory. Following this execution model, tasks never access the bus during their execution phase. Instead, all the bus accesses are performed during the first and third phases. In this paper, we focus on the global fixed-priority scheduling of the 3-phase task model. A new schedulability test is derived by modelling the interference happening on the bus rather than the interference on the cores as in the state-of-the-art techniques. The effectiveness of the test is evaluated by comparing it against the state-of-the-art.

Problem raspoređivanja je vrlo poznat i spada u klasu NP teških problema, što znači da ne postoje efikasni algoritmi koji pronalaze optimalno rješenje unutar razumnih vremenskih ograničenja. Jedna od metoda rješavanja tog problema je prioritetno raspoređivanje gdje se raspored dinamički gradi uz pomoć predefinirane heurističke prioritetne funkcije. U ovom radu opisuje se hiperheuristički model za pronalaženje prioritetnih funkcija temeljen na evolucijskim algoritmima i neurološkim sustavima. U sklopu modela opisuje se kartezijsko genetsko programiranje, gramatička evolucija i neuronske mreže kao tri različita pristupa za evoluciju prioritetnih funkcija. Za svaki pristup se posebno definira struktura, prikaz rješenja i evolucijski operatori križanja i mutacije. Svaki od ta tri pristupa se testira te se analizira njihova efikasnost u usporedbi s postojećim rezultatima drugih metoda. Osim usporedbe kvalitete rezultata, analizira se i vremenska i prostorna složenost različitih pristupa te se daju prijedlozi za moguća poboljšanja. Scheduling is a well known NP-hard optimization problem, which means that an algorithm which can obtain the optimal solution within reasonable time constraints does not exist. One of the methods for solving this problem is priority scheduling where the final schedule is dynamically constructed using a predefined priority function (heuristic). This paper describes a hyper-heuristic model for generating priority functions based on evolutionary algorithms and artificial neural networks. This model describes cartesian genetic programming, grammatical evolution and artifical neural networks as three different methods for evolving priority functions. The structure, solution representation and evolutionary operators are defined for each method. All the methods are tested and their efficiency is analyzed and compared to existing methods. Also, the time and space complexity of the methods is analyzed and possible future improvements are proposed.

Priority scheduling is a fundamental tool to provide service isolation for different jobs in shared clusters. Ideally, the performance of a high-priority job should not be dragged down by another with a lower priority. However, we show in this paper that simply assigning a high priority provides no isolation for jobs with dependent computations. A job, even receiving the highest priority, may give up compute slots to another before proceeding to the downstream computation, which is because of barrier, i.e., that the downstream computation cannot start until all the upstream tasks have completed. Such an interruption of execution inevitably results in a significant delay. In this paper, we propose speculative slot reservation that judiciously reserves slots for downstream computations, so as to retain service isolation for high-priority jobs. To mitigate the utilization loss due to slot reservation, we analyze the trade-off between utilization and isolation, and expose a tunable knob to navigate the trade-off. We also propose a complementary straggler mitigation strategy that uses the reserved slots to run extra copies of slow tasks. We have implemented speculative slot reservation in Spark. Evaluations based on both cluster deployment and trace-driven simulations show that our approach enforces strict service isolation for high-priority jobs, without slowing down the other jobs with a lower priority.