Use this resource - and many more! - in *your* textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match *your* way.

**Not an educator**but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

# Static allocation of periodic tasks with precedence constraints in distributed real-time systems

## By: Shin, K.G.; Peng, D.-T.;

1989 / IEEE / 0-8186-1953-8

### Description

This item was taken from the IEEE Periodical ' Static allocation of periodic tasks with precedence constraints in distributed real-time systems ' Using two branch-and-bound (B&B) algorithms, an optimal solution is proposed to the problem of allocating (or assigning with the subsequent scheduling considered) periodic tasks to a set of heterogeneous processing nodes (PNs) of a distributed real-time system. The allocation objective is to minimize the maximum normalized task response time, called the system hazard, subject to precedence constraints among the tasks to be allocated. First, the task system is modeled with a task graph, which describes computation and communication modules as well as the precedence constraints among them. Second, the exact system hazard of a complete assignment is determined so that an optimal assignment can be derived. This exact cost is obtained by optimally scheduling the modules assigned to each PN with a B&B algorithm guided by the dominance relationship between simultaneously schedulable modules. Third, to reduce the amount of computation needed for an optimal assignment, a lower-bound system hazard that is obtainable with a polynomial time algorithm is derived.<

**Related Topics**

Distributed Processing

Polynomial Time Algorithm

Static Allocation

Branch-and-bound Algorithms

Periodic Tasks

Precedence Constraints

Distributed Real-time Systems

Optimal Solution

Scheduling

Heterogeneous Processing Nodes

Pns

Minimize

Maximum Normalized Task Response Time

Precedence Constraints

Task System

Task Graph

Computation

Communication Modules

B&b Algorithm

Dominance Relationship

Real Time Systems

Scheduling Algorithm

Delay

Processor Scheduling

Hazards

Cost Function

Distributed Computing

Laboratories

Polynomials

Time Factors

Computational Complexity

Scheduling

Engineering

System Hazard