EvaluationofPartitioningofReal-TimeWorkloadsonLinux.pdf资源-CSDN文库

需积分: 2 70 浏览量 2023-08-05 16:18:42 上传评论收藏 281KB PDF 举报

Evaluation of Partitioning of Real-Time Workloads on Linux.pdf 本文档对 Linux 操作系统上的实时工作负载分区进行了评估。实时系统是指能够在规定的时间范围内完成任务的系统，具有很高的时间效率和可靠性。为了满足实时系统的需求，需要开发高效的实时调度算法和策略。在本文档中，作者提出了一个自适应分区算法，用于实时任务的调度。该算法基于结合分区 EDF 调度和自适应迁移策略，能够在对称多核心系统上实时调度任务。该算法的实现是基于 Linux 内核的 SCHED_DEADLINE 代码库的修改。作者对该算法进行了广泛的实验测试，使用了多个随机生成的合成任务集在真实的多核心平台上进行测试。实验结果表明，该算法在实时工作负载的调度上表现出色，迁移次数大大减少，且能满足实时系统的需求。实时操作系统（RTOS）是指能够在规定的时间范围内完成任务的操作系统，它们广泛应用于航空航天、医疗、交通、金融等领域。为了实现实时操作系统，需要开发高效的实时调度算法和策略。在 Linux 操作系统上，实时调度算法可以分为两类：全局调度算法和分区调度算法。全局调度算法是指对所有处理器上的任务进行调度，而分区调度算法是指将任务分配到不同的处理器上，并对每个处理器上的任务进行调度。在本文档中，作者提出的自适应分区算法就是一种基于分区调度的算法。 EDF（Earliest Deadline First）调度算法是一种常用的实时调度算法，它根据任务的截止日期来调度任务。然而，该算法存在一个缺陷，即它可能会导致任务迁移次数过多，从而影响系统的性能。为了解决这个问题，作者提出了自适应迁移策略，该策略可以根据任务的实际需求来决定是否进行迁移。在实验测试中，作者使用了多个随机生成的合成任务集来测试该算法的性能。实验结果表明，该算法能够在实时工作负载的调度上表现出色，迁移次数大大减少，且能满足实时系统的需求。本文档对 Linux 操作系统上的实时工作负载分区进行了评估，提出了一个自适应分区算法，并进行了广泛的实验测试。该算法能够在实时工作负载的调度上表现出色，且能满足实时系统的需求。知识点： * 实时操作系统（RTOS） * 实时调度算法 * 分区调度算法 * EDF（Earliest Deadline First）调度算法 * 自适应迁移策略 * Linux 操作系统 * SCHED_DEADLINE 代码库 * 多核心处理器 * 实时工作负载 * 任务调度 * 并行计算 * 热门 dissipation 问题 * wielo-core 和 wielo-processor 架构资源链接： * Linux 操作系统 * SCHED_DEADLINE 代码库 * 实时操作系统（RTOS） * EDF（Earliest Deadline First）调度算法 * 分区调度算法 * 自适应迁移策略

资源推荐

资源详情

资源评论

An Evaluation of Adaptive Partitioning of

Real-Time Workloads on Linux

Andrea Stevanato, Tommaso Cucinotta, Luca Abeni

Scuola Superiore Sant’Anna , Pisa, Italy

{a.stevanato,t.cucinotta,l.abeni}@santannapisa.it

Daniel Bristot De Oliveira

Red Hat, Inc., Pisa, Italy

bristot@redhat.com

Abstract—This paper provides an open implementation and

an experimental evaluation of an adaptive partitioning approach

for scheduling real-time tasks on symmetric multicore systems.

The proposed technique is based on combining partitioned EDF

scheduling with an adaptive migration policy that moves tasks

across processors only when strictly needed to respect their tem-

poral constraints. The implementation of the technique within the

Linux kernel, via modiﬁcations to the SCHED

DEADLINE code base,

is presented. An extensive experimentation has been conducted

by applying the technique on a real multi-core platform with

several randomly generated synthetic task sets. The obtained

experimental results highlight that the approach exhibits a

promising performance to schedule real-time workloads on a real

system, with a greatly reduced number of migrations compared

to the original global EDF available in SCHED

DEADLINE.

Index Terms—Real-Time Scheduling, Real-Time Operating

Systems, Linux Kern el

I. INTRODUCTION

Nowa days, proc e ssing platforms stopped evolving towards

higher and higher frequencies, taking a tight turn towards

multi-core and multi-processor a rchitectures. This allowed

manufacturers to keep deploying hardware with consistently

higher and higher computing capabilities, overcoming the

thermal and heat dissipation problems which led to the non-

practicality of releasing microproc essors with frequency be -

yond 5 GHz for the genera l public [1].

Parallel computing platforms are not only taking off

in personal and general-purpose compu ting (beside s high-

performance co mputing, wh e re they have be en th e standard

for decades). They are also becom ing increasingly adopted and

playing a key role in embed ded and real-time systems, where

the growing richness of the required features implies the use of

more and more powerful processing platforms [2], often made

available through multi-core architectures, GPU and FPGA

acceleration [3]. He nce, it is becoming increasingly importa nt

to design efﬁcient and practical scheduling techniques for real-

time applications on multi-core and multi-processor platforms.

However, this is known to be a non-trivial problem [4].

Multi-core real-time sched ulers are gen erally descr ibed [5]

as global or partitioned schedulers. In the former case, tasks

can be migr ated among cores to respect some scheduling

invariant, whilst in the latter one tasks are statically partitioned

This project has received funding from the European Union’s Horizon

2020 research and innovation programme under grant agreement No. 871669

AMPERE – “A Model-driven development framework for highly Parallel and

EneRgy-Efﬁcient computation supporting multi-criteria optimisation”.

among the available CPU cores, a nd a single-processor sched-

uler can be used on each core. A useful trade- off betwee n

these two extremes is the one of clustered schedulers, where

cores ar e partitioned in clusters, tasks are statically assigned

to c lusters and scheduled globally within each cluster.

An interesting new approach that tries to reconcile these

different scheduling a pproaches exploiting their advantages is

represented by adaptive partitioning EDF (apEDF) [6], [7].

This technique consists in combining an EDF-based parti-

tioned r eal-time scheduler, with a policy for dynamic migration

of tasks among cores until a schedulable task partition ing is

reached, if possible. At such point, migrations stop and the

scheduler converges to a partitioned scheduler. This happens

for example if a ﬁrst-ﬁt allocation policy is used, and the task-

set satisﬁes well-known conditions on its tota l utilization [8],

[9], making the technique viable for hard real-time workloads.

Even when said conditions are not veriﬁed, if a schedulable

tasks partitioning doe s not exist, adaptive partitioning falls

back to approximatin g global EDF [6], so that interesting p rop-

erties of such an approach can be preserved, like the bounded

tardiness, making it suitable for soft real-time workloads.

However, although the adaptive partitioning approach seems

to have promising properties, it has not been implem ented

in a real scheduler yet, having only been evaluated through

simulations, to the best of our knowledge.

In this paper, we present the ﬁrst implementation of an

adaptively partitioned EDF scheduler, based on Linux, an

increasingly attractive operating system (OS) for real-tim e

workloads. Currently, Linux supp orts glo bal EDF scheduling

via the SCHED

DEADLINE policy [10]

. Motivated by th e results

found by simulation in [6], [7], where apEDF has been shown

to possess a distinguishe d advantage over a global schedul-

ing approach, we implemented apEDF in Linux modifying

SCHED

DEADLINE, re placing its migration mechanism (which

implements global EDF by default) with a new mechanism

based on ap EDF. The new scheduler, which is made available

as an open-sourc e patch to SCHED

DEADLINE for the commu-

nity, is thoroughly evaluate d by running synthetic randomly

generated task sets, as co mmon in the real-time scheduling

community, in the simplifying scenario of independent (non-

interacting) pe riodic real-time tasks. The obtained results show

that the modiﬁed scheduling policy performs better than the

More information about the SCHED

DEADLINE can be

found in the ofﬁcial Linux kernel documentation at

https://www.kernel.org/doc/Documentation/scheduler/sched-deadline.txt

original one, obtaining a slightly better deadline-miss ratio,

with a greatly reduced number of migrations. Note that this

paper focuses on an exper imental evaluation of the proposed

scheduler. Reader s interested in schedu la bility analysis argu-

ments can refer to prior works as detailed next.

II. RELATED WORK

Several works exist in the literature dealing with scheduling

of hard or soft real-time task sets on multi-processor systems.

In the former case [11]–[15], even a single deadline miss

cannot be tolerated and is co nsidered a system failure. In the

latter case [16], [ 17], a few deadline misses can be acceptable

if their number and frequency can be kept under control.

Approac hes based o n partitioned scheduling ar e known to

have the potential of reusing well-k nown optimal results from

the single-processor real-time scheduling literature, like the

EDF utilization bound [18] for independent periodic tasks,

but they add the burden of having to partition the task set

upfront across the CPUs, which is a NP-h a rd p roblem when

optimality is n eeded. This is normally tackled via integer line ar

programming techniques applied off-line [19], [20].

On the other hand, approaches based on global sche dul-

ing are easier to adopt, but their capability to satura te the

underlying physical resources is generally reduced. Inde ed,

for examp le , simple utilization-based tests for schedulability

analysis on mu lti- processors are charac te rized by poor and

quite pessimistic utilizatio n bounds [21]–[23]. However, in soft

real-time systems one can load the system beyond said limits,

as generally there are techn iques to compute the maximum

tardiness a task can achieve under certain conditions, like the

well-known tardiness bo und for global ED F [16], [24].

Modifying global EDF restricting migrations at job-level

only [25], it is possible to improve its utilization bound,

and prove that it is optim al among ﬁxed-job-priority algo-

rithms [11]. A number of oth e r works exist a bout optimality of

global multiprocessor scheduling algorithms [12]–[15], [26].

However, due to the additional complexity needed in the

realization of the above techniq ues, often requiring higher

implementation overheads, common real-time Operating Sys-

tems focus mostly on simpler scheduling algorithms, either

partitioned or global, and based on e ither ﬁxed-priority or

EDF. Speciﬁcally, partitioned ﬁxed-priority scheduling is the

preferred choice in hard real-time systems. On the other hand,

global EDF-based scheduling is increasingly popular in soft

real-time ones, as witnessed by the SCHED DEADLINE policy

available in the mainlin e Linux kernel today [10], often a pplied

to real-time multimed ia workloads [27]. M oreover, a number

of work s can be found w ith experimental compar iso ns among

the perform a nce of global vs par titioned schedulin g techniques

under various workload conditions [5], [28].

Linux is a popular platform of choice for evaluating the

effectiveness of real-time schedu ling algorithms, often proto-

typed as invasive modiﬁcations to the kernel. Indeed , this is

the case of the Litmu s-RT framework [29], used f or em pirical

compariso ns among a number of RT scheduling algorithms

and resource handling protocols [30]. Albeit interesting, this

platform was not used in the present work, as we tried to adapt

directly the global EDF scheduler in SCHED DEADLINE, so to

obtain a minimally invasive patch to the mainline code base.

In a number of works, on-line partitioning techniques were

investigated , to leverage the advantages of partitioned schedul-

ing, yet being capable of adapting the system conﬁguration

depending on dynamic run -time workload cond itions.

To this pu rpose, co mmon heuristics th at have been in-

vestigated include ﬁrst-ﬁt, worst-ﬁt and next-ﬁt, which have

been studied in depth also in other contexts, such as memory

management [31]–[33]. Useful surveys on the topic can be

found in [34], [35]. Many of these works focus on the concept

of absolute approximation ratio: this is the minimum numbe r

of bins that are nee ded to pack a n umber of items w ith different

weights, when using one of the above me ntioned bin-packing

heuristics, as compared to the numbe r that would have been

sufﬁcient if u sin g an optimal ap proach. Some authors focused

on the asymptotic value of such an approx imation ratio,

achieved as the size of the problem grows to ∞. For example ,

one interesting result in the area is the 12/7 ≅ 1.7143 bo und

for the ﬁrst-ﬁt heuristic [35]. However, many of these works

are not concerned with scheduling of real-time tasks, so they

do not study the effectiveness of the mentione d he uristics on

the pe rformance, in terms of slack and/or tardiness, obtained

when scheduling various real-time task sets.

Note that the present study is strongly motivated by [8],

where heuristic partitioning techniques are applied to real-time

scheduling, a nalyzing the effectiveness of utilization-based

admission tests and demonstrating optim ality of th e ﬁrst-ﬁt

policy, amon g the ones usable in the context.

III. DEFINITIONS AND BACKGROUND

This section provides some d eﬁnitions and a quick overview

of the adaptive partitioning approach.

A. Task Model

The scheduler selects tasks from a (dynamic) set Γ = {τ

}

of real- time tasks τ

and dispatches them on M (identical)

CPU cores. A real-time task τ

is seen as a stream of jobs

i,k

}, each arriving (becom ing ready for execution) at time

i,k

, executing for a time c

i,k

and then ﬁnishing at time f

i,k

Notice that the ﬁnishing time f

i,k

of each job depends on

the schedulin g decisions. Each ta sk is also assoc iate d with a

relative deadline D

and ea ch job J

i,k

must ﬁnish within its

absolute deadline of d

i,k

= r

i,k

+ D

: if f

i,k

≤ d

i,k

, then the

deadline of J

i,k

is respected, otherwise it is missed. Task τ

respects all of its deadlines if ∀k, f

i,k

≤ d

i,k

⇒ ∀k, f

i,k

−

i,k

≤ D

. Finally, the tardiness of job J

i,k

is deﬁned as

max{0, f

i,k

− d

i,k

A real-time task τ

is often periodic with period P

, if

∀k, r

i,k+1

−r

i,k

= P

, or sporadic with minimum inter-arrival

time P

among subsequent jobs, if ∀k, r

i,k+1

− r

i,k

≥ P

;

in this work, we m a ke the simplifying assumption of implicit

deadlines, i.e ., ∀i, D

= P

, and we assume to know a reason-

able estima tion of the Worst-Case Execution Time ( WCET) C

of each real-time task, respecting the condition: C

≥ c

i,k

∀k.

剩余8页未读，继续阅读

评论收藏

内容反馈

程序员徐师兄

粉丝: 1991
资源: 2883

Evaluation of Partitioning of Real-Time Workloads on Linux.pdf

Linux for Embedded and Real-Time Applications.pdf

风河公司取得FSM实验室Hard Real-Time Linux技术 (1).pdf

风河公司取得FSM实验室Hard Real-Time Linux技术.pdf

Real-Time Embedded Components and Systems with Linux and RTOS(2nd) 无水印pdf

论文《Linux for High Performance and Real-Time Computing on SMP system.pdf》

mysql-5.5.27-win32.zip

apache-hive-2.1.0-bin.tar.gz

gparted-live-1.1.0-1-amd64.iso

Real-time.Analytics.with.Storm.and.Cassandra.1784395498

apache-hive-1.1.0-cdh5.7.1-bin.tar.gz

mysql-5.5.57-winx64.zip

hive-1.1.0-cdh5.7.0.tar

mysql-8.0.29-1.el7.x86_64.rpm-bundle

tuned-profiles-cpu-partitioning-2.15.0-2.el8.noarch.rpm

apache-hive-2.0.0-bin.tar

tuned-profiles-cpu-partitioning-2.9.0-1.el7fdp.noarch.rpm

tuned-profiles-cpu-partitioning-2.16.0-0.1.rc1.el8.noarch.rpm

mysql_refman-5.6-en.a4.pdf

apache-hive-3.1.2-bin.tar.zip

mysql-5.5.20-win32.zip

tuned-profiles-cpu-partitioning-2.11.0-10.el7.noarch.rpm

tuned-profiles-cpu-partitioning-2.7.1-5.el7.noarch.rpm

手册-vldb-and-partitioning-guide.pdf(Oracle数据库VLDB和分区指南).pdf

tuned-profiles-cpu-partitioning-2.11.0-5.el7fdp.1.noarch.rpm

黑群晖自动化引导制作工具arpl-1.1-beta2a

软件测试相关论文-英文原文82篇

tuned-profiles-cpu-partitioning-2.16.0-1.el8.noarch.rpm

tuned-profiles-cpu-partitioning-2.11.0-9.el7.noarch.rpm

tuned-profiles-cpu-partitioning-2.8.0-5.el7.noarch.rpm

MySQL-Cluster-test-gpl-7.2.4-1.sles11.x86_64.rar

最新资源