Browse Prior Art Database

Spatial Placement Algorithm for a Memory Scheduling Problem

IP.com Disclosure Number: IPCOM000078664D
Original Publication Date: 1973-Feb-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Johnson, EL: AUTHOR [+2]

Abstract

A method is presented for scheduling the memory requirements of jobs in high-speed memory of a computer, where the job must be placed in a contiguous area and cannot be moved once it is placed. Each job (or step of a job) has associated with it a time and a space. The jobs must be fitted into core, which is conceptually a linear string of memory, so that they do not overlap. Thus, looking at memory as a function of time gives a picture such as in Fig. 1. Even if the start and finish time of each job are fixed so that the total memory requirement is within the available limits, there may be no way to physically place the jobs.

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 58% of the total text.

Page 1 of 2

Spatial Placement Algorithm for a Memory Scheduling Problem

A method is presented for scheduling the memory requirements of jobs in high-speed memory of a computer, where the job must be placed in a contiguous area and cannot be moved once it is placed. Each job (or step of a job) has associated with it a time and a space. The jobs must be fitted into core, which is conceptually a linear string of memory, so that they do not overlap. Thus, looking at memory as a function of time gives a picture such as in Fig. 1. Even if the start and finish time of each job are fixed so that the total memory requirement is within the available limits, there may be no way to physically place the jobs.

An example is shown in Figs. 2 and 3, where the cross hatched area represents unused areas and the area bounded by dotted lines represents overlap. Although the total length at any time never exceeds 6, there is no way to place the jobs so that there is no overlap.

Further implementing the method in APL language running with the IBM 360/OS operating system, the following are required as input variables: T(I), the time required for Job I;

IMDP, the jobs arranged in order of increasing finish time;

TRYFT, the finish times in increasing order;

TFL, the total length available.

The program begins at the end of the time interval and works toward the beginning. The variable SLICE represents the jobs which are being worked on at any time. For a given job S in SLICE, the number PUP(S) is the...