Browse Prior Art Database

Throughput Scheduling Algorithm in a Multi Programming System

IP.com Disclosure Number: IPCOM000075628D
Original Publication Date: 1971-Oct-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 1 page(s) / 13K

Publishing Venue

IBM

Related People

Edel, TR: AUTHOR

Abstract

A common problem existing in multi-programming environments is the lack of an intelligent selection mechanism by the system, when it comes time to choose a suspended task from a list of ready tasks. Usually it is accomplished by some rigid priority scheme, which says that tasks in partition X always have selection priority over tasks in partition Y. This may be tolerable for a priority oriented system, but is not sufficient in an environment where "throughput" (completed jobs/time interval) is the main criteria. The objective in a "throughput' system is to concurrently keep as many system resources as active as is possible. As long as the CPU I/O (Input/Output) attachments (which function in parallel) remain out of synchronization in relation to its internal processing speed, the need for an intelligent dispatcher exists.

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

Page 1 of 1

Throughput Scheduling Algorithm in a Multi Programming System

A common problem existing in multi-programming environments is the lack of an intelligent selection mechanism by the system, when it comes time to choose a suspended task from a list of ready tasks. Usually it is accomplished by some rigid priority scheme, which says that tasks in partition X always have selection priority over tasks in partition Y. This may be tolerable for a priority oriented system, but is not sufficient in an environment where "throughput" (completed jobs/time interval) is the main criteria. The objective in a "throughput' system is to concurrently keep as many system resources as active as is possible. As long as the CPU I/O (Input/Output) attachments (which function in parallel) remain out of synchronization in relation to its internal processing speed, the need for an intelligent dispatcher exists.

Therefore, in a throughput oriented system, the selection criteria should simply be, "Select that task which has the highest probability of initiating an I/O request in order to maintain parallel activity in a multi-programming system.' A means of determining this probability is to dynamically monitor the past activity of a task as an indication of its future activity. The suggested method is to collect I/O frequency counts on a task basis. Note that CPU overhead must be considered when determining what statistic should be collected in order to determine the selection criteria. Thus, when the time came to select a new task, the system would simply select that task with the highest accumulated total. It should further be recognized, that the executi...