Optimal Multiprocessor Scheduling of Periodic Tasks in a Real-Time Environment.

Abstract

This investigation has addressed the problem of constructing a nonpreemptive schedule that requires the minimal number of processors for a given set of periodic tasks. Each periodic task is characterized by an integer period and an execution time. It is assumed that the period between each inititation and termination of a task must not vary once the first is specified. A compatibility relation is defined on the set of tasks such that any pair of tasks may be scheduled on the same processor only if they are compatible. An algorithm is defined which constructs a minimal processor schedule for a given set of tasks. The algorithm determines both upper and lower bounds on the number of processors required.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1979
Accession Number
ADA080521

Entities

People

  • Walter D. Seward

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Ground and Sea Platforms
  • Materials and Manufacturing Processes
  • Sensors
  • Space

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boolean Algebra
  • Command And Control
  • Computations
  • Computer Programming
  • Computers
  • Control Systems
  • Engineering
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Navigation
  • Operating Systems
  • Operations Research
  • Scheduling (Production)
  • Systems Engineering

Fields of Study

  • Computer science
  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.