An official website of the United States government
Fixed-priority multicore schedulers are often preferable to dynamic-priority ones because they entail less overhead, are easier to im-plement, and enable certain tasks to be favored over others. Underglobal fixed-priority (G-FP) scheduling, as applied to the standardsporadic task model, response times for low-priority tasks may beunbounded, even if total task-system utilization is low. In this paper,it is shown that this negative result can be circumvented if differentjobs of the same task are allowed to execute in parallel. In particu-lar, a response-time bound is presented for task systems that allowintra-task parallelism. This bound merely requires that total utiliza-tion does not exceed the overall processing capacity—individualtask utilizations need not be further restricted. This result impliesthat G-FP is optimal for scheduling soft real-time tasks that requirebounded tardiness, if intra-task parallelism is allowed
more »
« less
This content will become publicly available on May 15, 2026
Optimal Admission Policy in a Cloud Data Center with Priority and Non-Priority Tasks
This paper studies a cloud datacenter (DC) consisting of two types of tasks with different priority levels. While non-priority tasks generally request the use of a single virtual machine (VM), priority tasks may utilize multiple available VMs to accelerate processing. We focus on determining whether to accept or reject non-priority tasks to maximize overall system benefits. By formulating the problem as a stochastic dynamic program, it is verified that the best approach for handling nonpriority tasks adheres to a control-limit framework. Both experimental outcomes and numerical evaluations highlight the efficacy of the proposed method, leading to the identification of the optimal threshold. The key contribution of this paper is the development of a stochastic dynamic program for DC resource management and the explicit derivation of an optimal control-limit policy. Both value iteration and linear programming methods are utilized to solve optimization problems. These results offer essential understanding for assessing the performance of various DC models, optimizing both rewards and resources efficiently.
more »
« less
- Award ID(s):
- 2318662
- PAR ID:
- 10638577
- Publisher / Repository:
- Springer Nature Switzerland AG 2025
- Date Published:
- Subject(s) / Keyword(s):
- Cloud data center Resource utilization Optimal policy Cost and Reward Stochastic dynamic program.
- Format(s):
- Medium: X
- Location:
- London, UK
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Emerging Edge Computing (EC) technology has shown promise for many delay-sensitive Deep Learning (DL) based applications of smart cities in terms of improved Quality-of-Service (QoS). EC requires judicious decisions which jointly consider the limited capacity of the edge servers and provided QoS of DL-dependent services. In a smart city environment, tasks may have varying priorities in terms of when and how to serve them; thus, priorities of the tasks have to be considered when making resource management decisions. In this paper, we focus on finding optimal offloading decisions in a three-tier user-edge-cloud architecture while considering different priority classes for the DL-based services and making a trade-off between a task’s completion time and the provided accuracy by the DL-based service. We cast the optimization problem as an Integer Linear Program (ILP) where the objective is to maximize a function called gain of system (GoS) defined based on provided QoS and priority of the tasks. We prove the problem is NP-hard. We then propose an efficient offloading algorithm, called PGUS, that is shown to achieve near-optimal results in terms of the provided GoS. Finally, we compare our proposed algorithm, PGUS, with heuristics and a state-of-the-art algorithm, called GUS, using both numerical analysis and real-world implementation. Our results show that PGUS outperforms GUS by a factor of 45% in average in terms of serving the top 25% higher priority classes of the tasks while still keeping the overall percentage of the dropped tasks minimal and the overall gain of system maximized.more » « less
-
Real-time data stream processing at the edge is crucial for time-sensitive tasks within large-scale IoT systems. Task scheduling plays a key role in managing the Quality of Service (QoS), necessitating a prioritization system to distinguish between high and low-priority tasks, thus ensuring efficient data processing on edge nodes. Existing scheduling algorithms rigidly prioritize tasks deemed as high-priority, often at the expense of fairness and overall system efficiency. In this paper, we propose a Priority-aware Fair Task Scheduling (FTS-Hybrid) algorithm that addresses these challenges by managing priority based task execution in a controlled manner. Our task scheduling algorithm streamlines resource utilization and enhances system responsiveness, contributing to low latency and high throughput, outperforming competing techniques including First-Come-FirstServe (FCFS), Round Robin (RR), and Priority Scheduling (PS). We implemented FTS-Hybrid on Apache Storm and evaluated its performance using an open-source real-time IoT benchmark (RIoTBench). Experimental results show that the FTS-Hybrid algorithm reduces task execution latency by 24%, 31%, and 26% compared with FCFS, RR, and PS, respectively, by strategically mitigating queuing delays under dynamic workload conditions.more » « less
-
We study the optimal control problem in stochastic queueing networks with a set of job dispatchers connected to a set of parallel servers with queues. Jobs arrive at the dispatchers and get routed to the servers following some routing policy. The arrival processes of jobs and the service processes of servers are stochastic with unknown arrival rates and service rates. Upon the completion of each job from dispatcherunat serversm, a random utility whose mean is unknown is obtained. We seek to design a control policy that makes routing decisions at the dispatchers and scheduling decisions at the servers to maximize the total utility obtained by the end of a finite time horizonT. The performance of policies is measured by regret, which is defined as the difference in total expected utility with respect to the optimal dynamic policy that has access to arrival rates, service rates and underlying utilities. We first show that the expected utility of the optimal dynamic policy is upper bounded byTtimes the solution to a static linear program, where the optimization variables correspond to rates of jobs from dispatchers to servers and the feasibility region is parameterized by arrival rates and service rates. We next propose a policy for the optimal control problem that is an integration of a learning algorithm and a control policy. The learning algorithm seeks to learn the optimal extreme point solution to the static linear program based on the information available in the optimal control problem. The control policy, a mixture of priority-based and Joint-the-Shortest-Queue routing at the dispatchers and priority-based scheduling at the servers, makes decisions based on the graphical structure induced by the extreme point solutions provided by the learning algorithm. We prove that our policy achieves logarithmic regret whereas application of existing techniques to the optimal control problem would lead to Ω(√T)-regret. The theoretical analysis is further complemented with simulations to evaluate the empirical performance of our policy.more » « less
-
Safe control designs for robotic systems remain challenging because of the difficulties of explicitly solving optimal control with nonlinear dynamics perturbed by stochastic noise. However, recent technological advances in computing devices enable online optimization or sampling-based methods to solve control problems. For example, Control Barrier Functions (CBFs) have been proposed to numerically solve convex optimization problems that ensure the control input to stay in the safe set. Model Predictive Path Integral (MPPI) control uses forward sampling of stochastic differential equations to solve optimal control problems online. Both control algorithms are widely used for nonlinear systems because they avoid calculating the derivatives of the nonlinear dynamic functions. In this paper, we use Stochastic Control Barrier Functions (SCBFs) constraints to limit sample regions in the samplingbased algorithm, ensuring safety in a probabilistic sense and improving sample efficiency with a stochastic differential equation. We also show that our algorithm needs fewer samples than the original MPPI algorithm does by providing a sampling complexity analysis.more » « less
