CUTTING-PLANE ALGORITHMS FOR PREEMPTIVE UNIPROCESSOR REAL-TIME SCHEDULING PROBLEMS ABHISHEK SINGH

2025-05-06 0 0 843.21KB 45 页 10玖币

侵权投诉

CUTTING-PLANE ALGORITHMS FOR PREEMPTIVE

UNIPROCESSOR REAL-TIME SCHEDULING PROBLEMS

ABHISHEK SINGH

Abstract. Fixed-point iteration algorithms like RTA (response time analy-

sis) and QPA (quick processor-demand analysis) are arguably the most pop-

ular ways of solving schedulability problems for preemptive uniprocessor FP

(ﬁxed-priority) and EDF (earliest-deadline-ﬁrst) systems. Several IP (integer

program) formulations have also been proposed for these problems, but it is

unclear whether the algorithms for solving these formulations are related to

RTA and QPA. By discovering connections between the problems and the

algorithms, we show that RTA and QPA are, in fact, suboptimal cutting-plane

algorithms for speciﬁc IP formulations of FP and EDF schedulability, where

optimality is deﬁned with respect to convergence rate. We propose optimal

cutting-plane algorithms for these IP formulations. We compare the new algo-

rithms with RTA and QPA on large collections of synthetic systems to gauge

the improvement in convergence rates and running times.

Key words and phrases: hard real-time scheduling, ﬁxed priority, earliest dead-

line ﬁrst, cutting planes, linear programming duality, ﬁxed-point iteration

1. Introduction

FP (ﬁxed-priority) and EDF (earliest-deadline-ﬁrst) are two popular methods of

assigning priorities to preemptible hard real-time tasks in a uniprocessor priority-

driven system. In FP systems, each task is assigned a priority that remains constant

during execution; in contrast, priorities of tasks in EDF systems are variable during

execution, and at any instant a task with the earliest deadline has the highest

priority. From the early work of Liu and Layland (1973), it has been known that

the two systems are quite diﬀerent: for instance, an implicit-deadline FP system

can violate its timing requirements even when processor utilization is as low as

70%, while a comparable EDF system is safe for all processor utilizations up to

100%.1Preemptive uniprocessor systems with FP and EDF priority assignments

are some of the most well-studied systems in hard real-time scheduling theory:

historical perspectives on these systems and other supporting literature may be

found in surveys, handbooks, and textbooks (Audsley et al.,1995;Liu,2000;Sha

et al.,2004;Buttazzo,2011;Levy and Tian,2020); works that study the diﬀerences

between FP and EDF systems are also available (Buttazzo,2005;Rivas et al.,2011;

Perale and Vardanega,2021).

Systems that do not violate their timing requirements are called safe or schedu-

lable; other systems are said to be unschedulable. A schedulable system is often

characterized by a schedulability condition: for instance, a schedulable constrained-

deadline preemptive uniprocessor FP system with ntasks listed in nonincreasing

1Implicit deadlines are deﬁned in Section 2.

arXiv:2210.11185v5 [cs.OS] 18 Aug 2023

2 ABHISHEK SINGH

order of priority is characterized by the existence of a t∈(0, Di] such that rbfi(t)≤t

for all i∈[n], where Diis the relative deadline of the task iand rbfimaps any

tto the maximum amount of work generated by the subsystem [i] in any interval

of length t(Joseph and Pandya,1986;Lehoczky et al.,1989).2An unschedulable

arbitrary-deadline preemptive uniprocessor EDF system with ntasks can also be

characterized by the existence of a t∈(0,lcmj∈[n]Tj] such that dbf(t)> t where Tj

is the period of task jand dbf maps any tto the amount of work generated by the

system in the interval that must be completed in the interval (Baruah et al.,1990b;

Ripoll et al.,1996). We will discuss schedulability conditions, relative deadlines,

constrained deadlines, arbitrary deadlines, rbf, periods and dbf in more detail in

a later section. For now, it suﬃces to know that the schedulability conditions for

both FP and EDF systems are about the existence of a tin a bounded interval

where some function of tis nonnegative; for FP (resp., EDF) systems, the function

is t7→ t−rbfi(t) (resp., t7→ dbf(t)−t−1).

Given a description of a hard real-time system, the problem of deciding whether

the given system satisﬁes its timing requirements is called a schedulability problem.

An algorithm that solves a schedulability problem is called a schedulability test.

Given a system, a schedulability test checks whether the appropriate schedulability

condition holds for the system.

An FP schedulability test attempts to ﬁnd a t∈(0, Di] where rbfi(t)≤t.

There are many algorithmic techniques that can be used to achieve this goal: for

example, we can use ﬁxed-point iteration (Joseph and Pandya,1986;Audsley et al.,

1993), depth-bounded search trees (Manabe and Aoyagi,1998;Bini and Buttazzo,

2004), and continued fractions (Park and Baek,2023). The ﬁxed-point iteration

test is called RTA (response time analysis), and the depth-bounded search tree test

is called HET (hyperplanes exact test). The running times of these tests are, in

general, incomparable: the most signiﬁcant factor in the worst-case running time

of RTA is Dmax/Tmin where Dmax (resp., Tmin) is the largest deadline (resp., the

smallest period) in the system; the most signiﬁcant factor in the worst-case running

time of HET is 2#periods. Thus, for hard problem instances where the number of

periods is small but Dmax/Tmin is large, HET will likely outperform RTA; on the

other hand, for hard problem instances where the number of periods is large and

Dmax/Tmin is small, RTA will likely outperform HET.

Similarly, given a system that is not trivially unschedulable an EDF schedulabil-

ity test attempts to ﬁnd a t∈(0,lcmj∈[n]Tj) such that dbf(t)> t. Many algorith-

mic approaches can be used to search for tincluding ﬁxed-point iteration (Zhang

and Burns,2009b), integer programming in ﬁxed dimension (Baruah et al.,1990a)

(utilizing Lenstra’s algorithm (Lenstra,1983)), and convex-hull computation (Bini,

2019). The ﬁxed-point iteration algorithm is called QPA (quick processor-demand

analysis). As was the case with FP schedulability tests, the running times of EDF

schedulability tests are not comparable, in general: the most signiﬁcant factor in

the worst-case running time of QPA is lcmj∈[n]Tj/Tmin; the most signiﬁcant factor

in the worst-case running time of Lenstra’s algorithm is pO(p)where pis the variety

of the system.3Thus, for hard problem instances where the variety is very small

and lcmj∈[n]Tj/Tmin is large, Lenstra’s algorithm will likely outperform QPA; in

2[n] is shorthand for {1,2,...,n}; we assume that [0] = ∅.

3The variety of a synchronous system is the number of distinct deadline-period pairs in the

system (Baruah et al.,2022). Synchronous and asynchronous systems are deﬁned in Section 2.

CUTTING-PLANE SCHEDULABILITY TESTS 3

contrast, for hard problem instances where the ratio is small and the variety is large,

QPA will likely outperform Lenstra’s algorithm. Diﬀerences in worst-case running

times for various algorithmic approaches for FP and EDF schedulability tests with

respect to the sizes of diﬀerent problem parameters such as the number of periods

in the system, the variety of the system, Dmax/Tmin, and lcmj∈[n]Tj/Tmin have

been studied recently using the framework of parameterized algorithms by Baruah

et al. (2022).

Although applying new algorithmic techniques to create new schedulability tests

with better properties is very important, it is equally important to attempt to

understand the relationships between the schedulability problems and between the

algorithms for the problems. Eﬀorts in the latter direction often yield new structural

and algorithmic insights and result in a coherent uniﬁed theory. We are interested

in studying the connections between the FP schedulability problem and the EDF

schedulability problem in the context of four algorithmic approaches:

RTA: the ﬁxed-point iteration algorithm for FP schedulability (see Section 2.1).

IP-FP: the IP (integer programming) formulation for FP schedulability where the

variables correspond to the integral quantities in rbfi(see Section 4.1).

QPA: the ﬁxed-point iteration algorithm for EDF schedulability (see Section 2.2).

IP-EDF: the IP formulation for EDF schedulability where the variables corre-

spond to the integral quantities in dbf (see Section 4.2).

While RTA and QPA are well-known, IP-FP and IP-EDF are nonstandard names

that we are using to refer to speciﬁc IP formulations of the schedulability problems

described later in the document; moreover, IP-FP and IP-EDF qualify only vaguely

as algorithmic approaches because we have not speciﬁed an algorithm for solving

the IP formulations yet (we will design a new cutting-plane algorithm to solve the

IPs in a uniﬁed manner).

It is natural to try to understand the relationships within the pairs (RTA, IP-

FP) and (QPA, IP-EDF) because they solve the FP schedulability problem and

the EDF schedulability problem respectively. However, we found that studying the

problems separately is a little ineﬃcient because both problems can be reduced in

polynomial time to a common problem called the kernel (see Section 5):

the FP schedulability problem

the kernel

the EDF schedulability problem

poly-time reduction

If the kernel can be solved eﬃciently by some algorithm, then both FP schedu-

lability and EDF schedulability can be solved eﬃciently; thus, the kernel captures

4 ABHISHEK SINGH

the essence of the hardness of the two problems.4We prove the following facts

about the kernel:

•The kernel can be solved by a ﬁxed-point iteration algorithm called FP-

KERN (see Section 5.1). RTA and QPA can be recovered from FP-KERN

by composing it with the above reductions.

•The kernel has an IP formulation called IP-KERN (see Section 5.2). IP-FP

and IP-EDF can be recovered from IP-KERN by composing it with the

above reductions.

Since any relationship between FP-KERN and IP-KERN must also exist for RTA

(resp., QPA) and IP-FP (resp., IP-EDF), we can focus our attention on FP-KERN

and IP-KERN.

Our main result is that IP-KERN can be solved by a family of cutting-plane

algorithms; FP-KERN is a member of the family but it is not the optimal algorithm

in this family with respect to convergence rate, which is deﬁned as the inverse of

the number of iterations required for convergence; and the optimal algorithm in the

family, called CP-KERN, has a better convergence rate than FP-KERN. Viewed

from the FP (resp., EDF) perspective, RTA (resp., QPA) is a suboptimal cutting-

plane algorithm and CP-KERN converges to the solution in fewer iterations. In our

empirical evaluation, we compare the number of iterations required by the ﬁxed-

point iteration algorithms (RTA and QPA) and CP-KERN on synthetic systems;

the results conﬁrm that CP-KERN has a better convergence rate than RTA and

QPA.

1.1. Practical concerns: computational complexity. Faster schedulability al-

gorithms are needed in many applications. In holistic analyses of distributed real-

time systems, schedulability tests are called a great many times till the values

for all parameters in the system stabilize or an unschedulable subsystem is dis-

covered (Tindell and Clark,1994;Spuri,1996b). In partitioned approaches to

multiprocessor scheduling, uniprocessor schedulability tests are used to determine

the feasibility of (usually numerous) partitions. In automatic or interactive design

space explorations to optimize objectives such as energy consumption, schedula-

bility tests are used to determine the feasibility of numerous conﬁgurations. The

speed of a schedulability test is also crucial when it is used as an online test in a

dynamic embedded system.

While the convergence rate of CP-KERN is better than FP-KERN (think, RTA

and QPA), this does not imply that CP-KERN is faster than FP-KERN. Consider,

for instance, the center of gravity method for convex programs (see, for instance,

Bubeck,2015, Sec. 2.1). The center of gravity method has a good convergence

rate, but it requires the center of gravity of a convex body to be computed in each

iteration for which no eﬃcient procedures are known. CP-KERN, unlike the center

of gravity method, is not purely theoretical. In each iteration of CP-KERN we

must solve a linear relaxation of IP-KERN. Since linear programs can be solved

in polynomial time by the ellipsoid method (Khachiyan,1980) and interior point

4Reductions from EDF schedulability to FP schedulability have been used by Ekberg and

Yi (2017) to prove the hardness of FP schedulability using the hardness of EDF schedulability.

Thus, the idea that the two problems are closely related is not new. However, the kernel and the

reductions to it have not been described before, to the best of our knowledge.

CUTTING-PLANE SCHEDULABILITY TESTS 5

methods (Karmarkar,1984), each iteration of CP-KERN has polynomial running

time.5

To solve linear relaxations of IP-KERN in each iteration of CP-KERN even more

eﬃciently, we propose a specialized method that runs in strongly polynomial time.6

Since no strongly polynomial-time algorithms are known for linear programming,

our specialized method is an improvement over using a general algorithm for solv-

ing linear programs. Moreover, we show that if CP-KERN uses this specialized

method then it has the same worst-case running time as FP-KERN. This result,

combined with the optimality with respect to convergence rate, establishes CP-

KERN as a better algorithm than FP-KERN in theory. In practice, FP-KERN

may be faster than CP-KERN for instances where the diﬀerence in convergence

rates of CP-KERN and FP-KERN is negligible because FP-KERN does less work

in each iteration than CP-KERN when we do not ignore constant factors. We

compare the running times on synthetic systems in our empirical evaluation.

1.2. Practical concerns: implementation complexity. Since FP-KERN pro-

ceeds by ﬁxed-point iteration, it is quite easy to implement without depending on

external libraries; thus, it is well-suited to serve as an online schedulability test in

a dynamic embedded system where task and resource constraints are subject to

change over time. Since a cutting-plane algorithm for an IP solves a linear program

in each iteration, an implementation of a cutting-plane algorithm for solving gen-

eral IPs usually depends on linear programming libraries, commercial or otherwise,

making it harder to deploy on dynamic embedded systems.7When CP-KERN uti-

lizes our specialized algorithm to solve relaxations of IP-KERN, it is about 50 lines

in pseudocode, it uses elementary arithmetic operations, and does not depend on

mathematical programming or algebra libraries in function calls. Therefore, CP-

KERN has a small footprint and is well-suited for deployment on dynamic embedded

systems. For software developers writing a schedulability library, our structured ap-

proach promotes code reuse and reduces development eﬀort. Moreover, the smaller

codebase inspires more trust in stakeholders.

2. System Models

In a hard real-time system, a task receives an inﬁnite stream of requests and it

must respond to each request within a ﬁxed amount of time. We consider a system

comprising nindependent preemptible sporadic tasks, labeled 1,2, . . . , n. We refer

to the system simply as [n]; given a system [n], i∈[n] is the i-th task, and [i]⊆[n]

is a subsystem of [n] that contains tasks {1,2, . . . , i}. Each sporadic task i∈[n]

has the following (integral) characteristics:

5The “running time” of an algorithm in a theoretical context refers to the number of elementary

arithmetic operations used by the algorithm.

6An algorithm runs in strongly polynomial time if the algorithm is a polynomial space algorithm

and uses a number of arithmetic operations which is bounded by a polynomial in the number of

input numbers (see Gr¨otschel et al.,1993, pg. 32).

7Projects like CVXGEN attempt to address the problem of deploying convex programming

solvers on embedded systems by generating custom C code for some families of convex pro-

grams (Mattingley and Boyd,2012).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

CUTTING-PLANEALGORITHMSFORPREEMPTIVEUNIPROCESSORREAL-TIMESCHEDULINGPROBLEMSABHISHEKSINGHAbstract.Fixed-pointiterationalgorithmslikeRTA(responsetimeanaly-sis)andQPA(quickprocessor-demandanalysis)arearguablythemostpop-ularwaysofsolvingschedulabilityproblemsforpreemptiveuniprocessorFP(fixed-priority)an...

展开>> 收起<<

CUTTING-PLANE ALGORITHMS FOR PREEMPTIVE UNIPROCESSOR REAL-TIME SCHEDULING PROBLEMS ABHISHEK SINGH.pdf

共45页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

CUTTING-PLANE ALGORITHMS FOR PREEMPTIVE UNIPROCESSOR REAL-TIME SCHEDULING PROBLEMS ABHISHEK SINGH

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: