Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-12-23
2002-03-05
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06353844
ABSTRACT:
THE FIELD OF THE INVENTION
The present invention relates generally to computer systems, and in particular to batch job scheduling facilities employed in general purpose multiprocessor computer systems.
BACKGROUND OF THE INVENTION
Multiprocessor computer systems typically run different types of workloads to be executed on the processors such as interactive jobs and batch jobs. Interactive jobs include time-share and real-time jobs and other interactive loads, such as compiling loads and debugging loads. Batch jobs include larger loads such as number-crunching workloads and other workloads requiring large computations. The batch loads typically run for hours and require vast amounts of resources. Typically, a general purpose multiprocessor system handles both interactive and batch jobs in one system, and interactive jobs have tight response time requirements and cannot wait for batch jobs to complete.
In one type of previous general purpose multiprocessor system, static partitioning dedicates a certain number of processors to batch jobs and the rest of the processors to interactive jobs. For example, an eight processor system could have four processors dedicated to interactive jobs and four processors dedicated to batch jobs. In this example, processors run only their type of jobs, regardless of the number of each type of job running in the system. If, for example, no batch jobs are running in the system, the four processors dedicated to batch jobs are idle. Thus, a general purpose multiprocessor system employing static partitioning can have one portion of the machine being heavily overloaded at the same time that the other portion of the machine is idle. With static partitioning, the barrier between batch and interactive jobs is hard and static.
In addition, the static partitioning used in this type of previous general purpose multiprocessor system does not partition memory in the same fashion as processors. Even though a number of processors are dedicated to batch jobs, batch jobs may not make sufficient progress because interactive jobs are using the memory of the system needed by the batch jobs. Alternatively, the interactive response of this type of general purpose multiprocessor system could be slow, even with dedicated interactive processors, as a result of batch jobs using memory in the system.
Because of memory contention, various previous general purpose multiprocessor computer systems employ various types of load-sharing facilities. In this type of system, the load-sharing facility gets allocated some resources, such as processors and/or memory, and the load-sharing facility manages these resources. Jobs are submitted to the load-sharing facility manager and the manager attempts to schedule the batch jobs on the resources allocated to the facility. This type of load-sharing facility solves the resource contention problems, but still results in a significant problem due to static partitioning which results in wasted resources because the resources are dedicated to the load-sharing facility and cannot be used by interactive jobs. In other words, these type of systems allocate more resources than just processors, such as memory, which achieves guaranteed execution times for submitted batch jobs. Nevertheless, if no batch jobs are running in the batch portion of the system, interactive jobs still cannot access the batch portion of the system. Similarly, if no interactive jobs are running in the interactive portion of the system, batch jobs still cannot access the interactive portion of the system.
Therefore, for the reasons stated above, and for other reasons presented in greater detail in the Detailed Description of the Preferred Embodiment section of the present specification, there is a need for an improved batch scheduling facility in a general purpose computer system for scheduling batch jobs with guaranteed completion times in a more efficient manner than currently available with static partitioning of the system. Current load-sharing and batch-queuing user-level service facilities employed in general purpose multiprocessor systems cannot guarantee completion times without statically partitioning the system.
SUMMARY OF THE INVENTION
The present invention provides a method and a general purpose multiprocessor system having a batch scheduling facility for scheduling multiple batch jobs. The general purpose multiprocessor system includes resources and runs interactive and batch jobs. The resources are allocated to each batch job. Completion times are calculated and guaranteed for each batch job based on the resources allocated to each batch job. Batch-critical batch jobs are defined to be those batch jobs which require all their allocated resources to complete by their guaranteed completion time. The batch jobs are scheduled so that batch jobs and interactive jobs compete for the same resources. Batch-critical jobs are permitted to obtain all their allocated resources.
The resources of the multiprocessor system typically include processors and/or memory, and can include other resources.
In one embodiment of the present invention an urgency value is calculated for each batch job substantially equal to the execution time to complete the batch job divided by the time remaining to complete the batch job by the guaranteed completion time minus the maximum processors and/or memory allocated to the job. In this embodiment, a batch-job is defined as batch critical when the calculated urgency value is equal to or greater than zero.
In one embodiment of the present invention, the resources of the multiprocessor system are partitioned into at least one soft system partition. The at least one soft system partition represents a user-level batch queue and is assigned resources. The soft system partition includes soft partition units representing available and unavailable resources over time intervals. The resources are allocated based on the available resources over time intervals.
The soft system partition has many possible implementations. For example, in one embodiment, certain of the multiple batch jobs are allocated multiple segments of the available resources over time intervals. In one embodiment, the multiprocessor system includes multiple soft system partitions. In one embodiment, the at least one soft system partition includes at least one time-varying soft system partition. The time-varying soft system partition is allocated different numbers of processors based on defined time periods.
In one embodiment of the present invention the interactive jobs include normal time-share jobs, weightless time-share jobs, and real-time jobs. The batch-critical jobs are scheduled ahead of the normal time-share jobs and behind the real-time jobs. The batch jobs not defined as batch critical are scheduled behind the normal time-share jobs and ahead of the weightless time-share jobs.
The batch scheduling facility according to the present invention guarantees completion times of batch jobs without using static partitioning like conventional batch scheduling facilities described in the Background of the Invention section. If resources are needed for a batch job to complete on time, the resources are given to the batch job. If the resources are not needed for the batch job to complete on time, the resources are available for use by time-share jobs. If resources are not needed for time share jobs, the resources can be used by batch jobs. Therefore, a general purpose multiprocessor system according to the present invention typically improves response time for time-share jobs and other interactive jobs and also completes the batch jobs faster, because of the more efficient use of the system resources.
REFERENCES:
patent: 3648253 (1972-03-01), Mullery et al.
patent: 5291599 (1994-03-01), Cohen et al.
patent: 5437032 (1995-07-01), Wolf et al.
patent: 5528513 (1996-06-01), Vaitzblit et al.
John A. Stankovic. “The Spring Kernel: A New Paradigm for Real-time Systems”, May 1991.*
R. T. Dimpsey. “Performance Prediction and Tuning on a Multiprocessor”, 1991.*
Sandeep Khanna. “Realtime Scheduling in S
Bitar Nawaf K.
English Robert M.
Banankhah Majid A.
Bullock, Jr. Lewis A.
Schwegman Lundberg Woessner & Kluth P.A.
Silicon Graphics Inc.
LandOfFree
Guaranteeing completion times for batch jobs without static... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Guaranteeing completion times for batch jobs without static..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Guaranteeing completion times for batch jobs without static... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847917