A shared-memory multiprocessor scheduling algorithm

Abstract

This paper presents an extension of the Latency Time (LT) scheduling algorithm for assigning tasks with arbitrary execution times on a multiprocessor with shared memory. The Extended Latency Time (ELT) algorithm adds to the priority function synchronization associated with access to the shared memory. The assignment is carried out associating with each task a time window of the same size as its duration, which decreases with the Insertion Scheduling Heuristic (ISH). Analysis of the results established that ELT has better performance with fine granularity tasks (computing time comparable to synchronization time), and also, when the number of processors available to carry out the assignment increases