POLISH ACADEMY of SCIENCES
TECHNICAL SCIENCES
Disasters, micro and nanomechanics
| BULLETIN
of the
POLISH ACADEMY of SCIENCES TECHNICAL SCIENCES |
|
|||
|---|---|---|---|---|
| Volume
57, Issue 1, March 2009
Disasters, micro and nanomechanics |
||||
| Issue Index | Authors Index | Scope Index | Web Info | |
|
|
||||
| Aims&Scope, Subscription | Editors | Authors' guide | to read PDF files | mirror: http://fluid.ippt.gov.pl/~bulletin/ |
| pp 71 - 77 |
|---|
|
The Knapsack-Lightening problem and its application to scheduling HRT tasks |
|---|
| J.R. NAWROCKI, W. COMPLAK, J. BLAZEWICZ, S. KOPCZYNSKA, and M. MACKOWIAK |
| In hard real-time systems timeliness is as important as functional correctness. Such systems contain so called hard real-time tasks (HRT tasks) which must be finished by a given deadline. One of the methods of scheduling of HRT tasks is periodic loading introduced by Schweitzer, Dror, and Trudeau. The paper presents an extension to that method which allows for deterministic utilization of cache memory in hard real-time systems. It is based on a new version of the Knapsack problem named Knapsack-Lightening. In the paper the Knapsack- Lightening problem is defined, its complexity is analyzed, and an exact algorithm along with two heuristics are presented. Moreover the application of the Knapsack-Lightening problem to scheduling HRT tasks is described. |
| Key words: |
|
algorithms, computational complexity, knapsack problem, greedy algorithms, branch and bound scheduling, real-time systems, cache memory, periodic loading. |
|
|
| Issue Index | Authors Index | Scope Index | Web Info |
|---|---|---|---|
|
|
|||
| Aims&Scope, Subscription | Editors | Authors' guide | to read PDF files |
| Copyright
® Bulletin of the Polish Academy of Sciences: Technical Sciences
12 March 2009 |
|---|