Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract)

Jeff Edmonds y Donald D. Chinn y Tim Brecht y Xiaotie Deng y Department of Computer Science York University North York, ONT M3J 1P3 Abstract A multiprocessor system is unlikely to have access to information about the execution characteristics of the jobs it is to schedule. In this work, we are interested in scheduling algorithms for batch jobs that require no such knowledge (such algorithms are called nonclairvoyant) . Preemptive scheduling (i.e., redistribution of processors) is important to reduce mean response time in multiprocessor systems, especially in the widely available network of workstations. Preemption is a method to adapt to the uncertain and changing nature of jobs and workloads. Unfortunately, preemption may incur large overheads if it is applied frequently. To account for the cost preemptions, we consider a number of simple scheduling algorithms classified by the number of preemptions they are allowed, ranging from none to an infinite number. The Equi-partition..