𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Optimal Multiprocessor Real-Time Scheduling Algorithm

✍ Scribed by Ashok Khemka; R.K. Shyamasundar

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
170 KB
Volume
43
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

An optimal scheduling algorithm is described that feasibly schedules a set of m periodic tasks on n processors before their respective deadlines, if the task set satisfies certain conditions. The complexity of this scheduling algorithm in terms of the number of scheduled tasks and the number of processors and upper bounds on the number of preemptions in a given time interval and for any single task is also derived. The optimal algorithm is shown to be particularly useful when schedules are built from the integral flow values obtained from the corresponding maximum flow network.

πŸ“œ SIMILAR VOLUMES

Scheduling Algorithms with Fault Detecti
Scheduling Algorithms with Fault Detection and Location Capabilities for Real-Time Multiprocessor Systems
✍ K. Mahesh; G. Manimaran; C.Siva Ram Murthy; Arun K. Somani πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 444 KB

Several schemes for detecting and locating faulty processors through self-diagnosis in multiprocessor systems have been discussed in the past. These schemes attempt to start multiple copies (versions) of the tasks on available idle processors simultaneously and compare the results generated by the c

On-line scheduling to minimize max flow
On-line scheduling to minimize max flow time: an optimal preemptive algorithm
✍ Christoph AmbΓΌhl; Monaldo Mastrolilli πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 170 KB

We investigate the maximum flow time minimization problem of on-line scheduling jobs on m identical parallel machines. When preemption is allowed, we derive an optimal algorithm with competitive ratio 2 -1/m. When preemption is not allowed and m = 2, we show that the First In First Out heuristic ach

Optimal Compile-Time Multiprocessor Sche
Optimal Compile-Time Multiprocessor Scheduling Based on the O–1 Linear Programming Algorithm with the Branch and Bound Technique
✍ D.Antony Louis Piriyakumar; C.Siva Ram Murthy πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 238 KB

This paper is organized as follows. We describe the formulation of the problem and the required definitions in Section II. In Section III, the performance improvement over [6] due to processor isomorphism and look ahead pruning in reducing the search space is explained, along with a note on the lowe