Browse Prior Art Database

Time-Shared Scheduler for Multiple Processors

IP.com Disclosure Number: IPCOM000103842D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 4 page(s) / 117K

Publishing Venue

IBM

Related People

Franaszek, PA: AUTHOR [+2]

Abstract

Disclosed is a method to provide time-shared scheduling for multiple processors by providing system structure algorithms for ensuring that each job is processed in a timely fashion for a suitable processor.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 41% of the total text.

Time-Shared Scheduler for Multiple Processors

      Disclosed is a method to provide time-shared scheduling for
multiple processors by providing system structure algorithms for
ensuring that each job is processed in a timely fashion for a
suitable processor.

      It is assumed that an overall system consists of N processors
Pr sub 1, Pr sub 2, ..., Pr sub n.  Each processor may have some
local storage including a cache.  It is assumed that the system
services jobs [J sub i], i = 1, 2, ..., where each is a member of a
class Q sub j(i).  Members of differing Q sub j are distinguished by
such properties as response time requirements and the data bases that
they access.  The concept described here provides a method for
ensuring that each J sub i is processed in a timely fashion on a
suitable processor.

      In order to process jobs in a timely fashion, the order in
which the jobs should be processed will generally be a function of
the load and the power of the system.  Therefore, for example, if the
processors are fast enough so that each job can be processed with a
negligible delay, the jobs may be processed in arrival order.
However, if there is a possibility of a delay, some jobs may be
considered of a higher priority than others and should receive
preferential treatment.  The differential or the preferential
treatment of the jobs are thereby termed the delay cost.  This delay
cost can be defined as follows:

      If t sub i is the time that J sub i entered the scheduler and
't'' sub i the time at which it completes service in thi stage of
scheduling, then the system is charged a penalty in accordance with
the following algorithm:

      V(t sub i,t sub i') = %%% integral from ti to t' sub i of
'C'sub j(i)(X)dX
where Q sub j(i) is the class of which J sub i is a member C sub
j(i)(X)delX i is the incremental cost for delaying executions of J
sub i by delX.  The objective of the scheduler is ten to minimize the
total delay cost charged to the system.  The functions C sub i(X) can
be designed so that the scheduler will contain a variety of desirable
characteristics.  However, the concept described herein is not to
discuss the particular forms of C sub i(X) but rather to discuss how
the delay cost can serve as a basis for the design of multiprocessor
schedulers.  As a result, for the purpose of the following, it is
sufficient to assume that C sub i(X) = K sub i + S sub iX and it is
understood that other forms of C sub i(X) may at times be
appropriate.

Delay Cost Minimization for a Single Processor

A heuristic for minimizing the delay cost charged to the system in
the case of a single processor, or single dispatch list, is as
described below.  This will be termed the delay cost ratio (DCR)
algorithm.  J sub i is scheduled for the highest value of C sub i(X)
sub i/L sub i, where X sub i is the waiting time for J sub i.  All
quantities are for the current pass through of the scheduler.  L sub
i is an estimate...