Publication

Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling

Thomas Rothvoss
2009
Journal Articles

Abstract

This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm. The quantitative metric used in this comparison is the processor speedup factor, equivalent to the factor by which processor speed needs to increase to ensure that any taskset that is schedulable according to an optimal scheduling algorithm can be scheduled using fixed priority pre-emptive scheduling. The maximum value for the processor speedup factor is shown to be 1/Omega = 1.76322 for tasksets where all task deadlines are less than or equal to their periods, and 1/ln(2) = 1.44270 for tasksets where all task deadlines are equal to their periods. The derivation of this latter result provides an alternative proof of the well-know Liu and Layland result.We refer to this factor as the processor speedup factor for fixed priority pre- emptive scheduling. Liu and Layland (1973) considered the pre-emptive scheduling of synchronous1 tasksets comprising independent periodic tasks, with bounded execution times, and deadlines equal to their periods. We refer to such tasksets as implicit-deadline tasksets. Liu and Layland showed that Earliest Deadline First (EDF) can schedule any implicit-deadline taskset with a total utilisation2 less than or equal to 100% ( 1 ≤ U ). Liu and Layland also showed that rate monotonic3 priority assignment is the optimal fixed priority assignment policy for implicit-deadline tasksets, and that using this priority assignment policy, fixed priority pre- emptive scheduling can schedule any implicit-deadline

Official source

https://infoscience.epfl.ch/entities/publication/a6b6707c-7edd-47db-956d-6a4ea6846e8e

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Thomas Rothvoss
2009
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/a6b6707c-7edd-47db-956d-6a4ea6846e8e

About this result

Related concepts (16)

Earliest deadline first scheduling

Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.

Rate-monotonic scheduling

In computer science, rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority. These operating systems are generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application.

Scheduling (computing)

In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows. The scheduling activity is carried out by a process called scheduler. Schedulers are often designed so as to keep all computer resources busy (as in load balancing), allow multiple users to share system resources effectively, or to achieve a target quality-of-service.

Related publications (28)

OASIS: An integrated optimisation framework for activity scheduling

Janody Pougala

Activity-based models offer the potential for a far deeper understanding of daily mobility behaviour than trip-based models. Based on the fundamental assumption that travel demand is derived from the need to do activities, they are flexible tools that aim ...

EPFL2024

Highly Parallel RTL Simulation

Verification and testing of hardware heavily relies on cycle-accurate simulation of RTL. As single-processor performance is growing only slowly, conventional, single-threaded RTL simulation is becoming impractical for increasingly complex chip designs and ...

EPFL2024

Acceleration of graph pattern mining and applications to financial crime

Jovan Blanusa

Various forms of real-world data, such as social, financial, and biological networks, can be represented using graphs. An efficient method of analysing this type of data is to extract subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...

EPFL2023