Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Generalized Approach to Ordering and Categorizing Jobs

IP.com Disclosure Number: IPCOM000085585D
Original Publication Date: 1976-Apr-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 50K

Publishing Venue

IBM

Related People

Moeller, JL: AUTHOR [+2]

Abstract

An algorithm for ordering jobs in an operating system and a method of categorizing the jobs dynamically in terms of their rates of receiving resources is described. The jobs comprise N disjoint classes of executable programs and data which place demands upon the resources of the computing system. The resources of the system involved comprise elements of hardware or software which can be measured in terms of consumption by a job.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Generalized Approach to Ordering and Categorizing Jobs

An algorithm for ordering jobs in an operating system and a method of categorizing the jobs dynamically in terms of their rates of receiving resources is described. The jobs comprise N disjoint classes of executable programs and data which place demands upon the resources of the computing system. The resources of the system involved comprise elements of hardware or software which can be measured in terms of consumption by a job.

Necessary requirements for the ordering and categorization are: A job status vector; u = (u(1),..., u(m), u(m+1), ..., u(n)). for each job in the N disjoint classes of jobs where: (a) n is the number of resources to be governed by the operating system. (b) m is the number of elements in a subvector u/1/ of u for which the components of u/1/ are pertinent to a specific ordering algorithm. And; (c) The components u(i) give the rate at which the job is receiving the i/th/ resource.

A minimum resource use specification vector for m resources and N classes is given by: f/(i)/ = (f(i1), ..., f(im)) , i = 1, ..., N.

A maximum resource use specification vector is given by: g/(i)/ = (g(i1), ..., g(im)), i = 1, ..., N. such that f(ij) < g(ij) for every i = 1,..., N and j = 1,..., M and such that f/(i)/ and g/(i) can be compared to a multidimensional subvector u/1/ of the user status vector. The f(ij) and g(ij) represent the minimum and maximum value associated with resource j for users of class i.

A comparison operator < is given such that: v < w is equivalent to; Psi(v) < Psi(w). for m dimensional vector v and w and a suitable function Psi: E/n/ --> R. Selection of a suitable Psi consists of identifying components of u that are to be taken into consideration for a decision, and the relative weights to be given to each component.

The algorithm for ordering the jobs is given in the figure. For the case of more than one class of jobs, Block 11 defines a total ordering of the jobs. Similarly, Blocks 13 and 15 define a total ordering for a single class of jobs. The essential feature of the algorithm is that it transforms a relationship between jobs within a class into a relationship that is class-independent, thereby obtaining a total ordering of all jobs, regardless of the class to which they belong.

The algorithm is entered at Block 1 wherein the first step encountered involves obtaining a subset D of jobs which are to be totally ordered, as shown by Block 3. Thereafter, the algorithm obtains the mapping function Psi to be used as an extension for ordering the jobs in D, as shown by Block 5. A determination is then made as to whether the number of classes represented by jobs in D is equal to 1, as shown by Block 7. If the number of...