The dynamic scheduling of the workload of a distributed multiprocessor system was considered in order to identify a scheduling algorithm which was tolerant of variations in the transmission delays between the constituent processing nodes. The workload was considered to comprise a large number of tasks which arrived at random and which had a negative exponential service time distribution.A theoretical comparison was undertaken of a number of alternative, commonly used algorithms, particular emphasis being given to the effect on their performance of increasing inter-processor communications link delay.A complex simulation model was constructed on a direct shared memory multi-processor (CYBA-M) and the performance of various scheduling algorithms was investigated over a range of inter-processor delays and system configurations. The results obtained confirmed and quantified theoretical considerations and enabled a new algorithm to be devoloped.This new algorithm involves two stages of queuing. All tasks are initially transferred to one (or more) first stage, common queue(s). They are then transferred to the second stage queues (one on each processing node) using a batch service algorithm which employs dynamic (run-time) determination of the batch size. The transfer is initiated by a batch request issued by each second stage queue whenever its size falls below a threshold.The algorithm was evaluated for various simulated multi-processor configurations and was shown to be superior to conventional algorithms for a wider range of workloads and inter-processor delays (relative to the expected service time). It was also shown to be relatively insensitive to the values of the parameters used.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:374266 |
| Date | January 1985 |
| Creators | Porteous, J. M. |
| Publisher | University of Cambridge |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0023 seconds