Browse Prior Art Database

Preemptive Scheduling of Uniform Processor Systems

IP.com Disclosure Number: IPCOM000128539D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

Teofilo Gonzalez: AUTHOR [+4]

Abstract

An 0(n) time algorithm is presented to obtain an optimal finish time preemptive schedule for n independent tasks on.. m uniform processors. This algorithm assumes that the tasks are initially ordered by task length and that the uniform processors are ordered by processor speed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Preemptive Scheduling of Uniform Processor Systems

by

Teofilo Gonzalez and Sartaj Sahni Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

Technical Report 76-5 May, 1976

Cover design courtesy of Ruth and Jay Leavitt Preemptive Scheduling of Uniform Processor Systems

Teofilo Gonzalez t and Sartaj Sahnifit

Abstract

An 0(n) time algorithm is presented to obtain an optimal finish time preemptive schedule for n independent tasks on.. m uniform processors. This algorithm assumes that the tasks are initially ordered by task length and that the uniform processors are ordered by processor speed.

Keywords and Phrases uniform processors, preemptive schedules, optimal finish time schedules, independent tasks. ,~ This research was supported in part by NSF grant DCR74- 10081

'h Department of Information and Computing Science, University of Oklahoma, Norman, Oklahoma

tt Department of Computer Science, University of Minnesota, Minneapolis, Minnesota

1. Introduction

Let Pl,P2,...,Pm be a system of m uniform processors and let the speed of Pi be si. Without loss of generality we may assume

(Equation Omitted)

be n independent tasks with task lengths (or times)

(Equation Omitted)

. The execution of task Ti on processor Pj requires

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1976

Page 2 of 13

Preemptive Scheduling of Uniform Processor Systems

The finish time of a schedule is the time taken to complete the execution of all the tasks. A preemptive schedule is a schedule in which one may suspend the execution of a task before its completion and resume its execution at a later time :(possibly on a different processor). In a nonpreemptive schedule, the processing of a task on a given processor cannot be suspended until its completion. An optimal finish time (OFT) preemptive (nonpreemptive) schedule is a preemptive (nonpreemptive) schedule with minimum finish time amongst all feasible preemptive (nonpreemptive) schedules for the given independent tasks and uniform processors. The problem of obtaining OFT nonpreemptive schedules for an m uniform processor system with m > 2 is known to be NP-Complete (see Karp [4]). Liu and Liu [5] present worst case bounds on a simple heuristic that obtains approxi-mately optimal OFT schedules. Gonzalez, Ibarra and Sahni
[1] analyse the performance of an LPT (largest processing time first) type heuristic for obtaining near optimal OFT nonpreemptive schedules. Further approximation methods to obtain near optimal schedules for uniform processors are given by Horowitz and Sahni [3]. In this paper we are concerned solely with obtaining OFT preemptive schedules. For this problem Liu and Yang
[6] have obtained the following bound on the length of an OFT schedule. Let w be the length of an OFT preemptive schedule, let

(Equation Omitted)

[6 ] also presents an algorithm that obtains an OF...