Scheduling periodic tasks among multiple processors.
Item
-
Title
-
Scheduling periodic tasks among multiple processors.
-
Identifier
-
AAI9315467
-
identifier
-
9315467
-
Creator
-
Hsu, Jane Chien Yueh.
-
Contributor
-
Adviser: Eralp A. Akkoyunlu
-
Date
-
1993
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
This dissertation addresses the problem of scheduling periodic tasks on a multiple processor system. Individual requests of each of N task types arrive periodically with known fixed period and service requirement, and each request of a given task type must be completed before the next arrival of a request of its type. The tasks are processed on a system of M equivalent processors, {dollar}M\ge 2{dollar}. Though a task may be scheduled on more than one processor, it may run on only one processor at a time. For systems in which the total processing demand does not exceed that available ("feasible systems"), algorithms are presented that always produce a viable schedule. These algorithms are of two types. The "Queue-Based" Algorithms partition tasks into queues and assign queues to processors for servicing. The "Flat" Algorithms implement a modified deadline algorithm augmented with auxiliary deadline-type constraints that serve to prevent the typical failure modes of the standard deadline algorithm in the multiple processor setting. The Queue-Based Algorithms typically require tasks to be shared by and switched between processors, while the Flat Algorithms require additional preemptions of active tasks. For both classes of algorithms, the amount of switching required by the schedules produced is quantified and modifications which result in reduced processor switching are given.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
