Optimal scheduling of homogeneous job systems |
| |
Authors: | Clarence A Ellis |
| |
Affiliation: | Project MAC and Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139 USA |
| |
Abstract: | Homogeneous job systems are systems in which all of a finite set of jobs to be processed by the system have exactly the same processing requirements. This paper assumes that each job first executes an input task requiring an input unit (channel or controller) for some amount of time Tc along with a memory unit. Then it executes a computational task requiring a processing unit and the memory for some amount of time Tp. Under these assumptions, it is possible to derive some inequalities concerning the relative number of memory, input, and processor units which can be efficiently used by the system as a function of Tc and Tp. The scheduling problem is to order tasks and assign resources to them in such a way as to minimize some cost function. The cost functions considered in this paper are job set finishing time and dwell time. Some theorems are stated and proved which yield closed form expressions for the minimum finishing time in batch and in time-shared systems as a function of the number of jobs, memories, processors, input units, and Tc and Tp. The purpose of this study is to derive some general results which aid in the efficient utilization of multiprocessor computer systems. Although this study is directed toward a specific type of homogeneous system, it is shown that the results are applicable to other systems (e.g., systems with output). |
| |
Keywords: | Multiprocessors scheduling batch processing timesharing multiprogramming I/O bound systems compute bound systems job shop problem flow shop problem |
本文献已被 ScienceDirect 等数据库收录! |
|