Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]


Journal of Information Science and Engineering, Vol. 26 No. 2, pp. 347-361 (March 2010)

Task Scheduling for Multiprocessor Systems with Autonomous Performance-Optimizing Control

Department of Electrical and Computer Engineering
The University of Texas at San Antonio
San Antonio, TX 78249-0669 U.S.A.

In all non-blocking non-preemptive (NBNP) scheduling techniques for a multicomputer system for processor allocation, Largest-Job-First (LJF) technique proves to possess a unique characteristic in utilizing as many processors as possible compared to others such as First-Come-First-Serve (FCFS) and Smallest-Job-First (SJF). However, a jobbypass limit that is preset to preclude the starvation problem in an NBNP platform may lead to problems in all techniques. The scheduling becomes "mandatory blocking" whenever a job reaches this bypass limit and thus has to be scheduled for allocation in the next immediate turn. This deprives the scheduling process the flexibility benefit in its non- blocking nature. Such an adverse effect is especially pronounced in LJF compared to the normally used FCFS one. Thus, how to find a balance in real time between employing the LJF and the FCFS in different situations is the main focus of this paper. We first propose an automatic control process which allows automatic adjustment on the algorithm based on the observed performance. This process, unlike the well-known feedback- control process, adjusts the algorithm based on an unbiased approach in order to disengage the dependence of performance on the input. We then propose two different scheduling techniques that simply employ this control process to self-adjust the weights in between using the two different techniques in real time. Performance results observed from our simulation runs show a significant improvement over the plain LJF and FCFS.

Keywords: scheduling, resource sharing, multiprocessor system, supercomputing, autonomous control

Full Text () Retrieve PDF document (201003_02.pdf)

Received September 19, 2008; revised November 11, 2008; accepted December 11, 2008.
Communicated by Tsan-sheng Hsu.