High performance thread scheduling on shared memory multiprocessors

Abstract

In this thesis we are concerned with the efficient scheduling of threads on both shared memory multiprocessors and uniprocessor machines. We attempt to efficiently schedule large numbers of threads while reducing overheads commonly associated with thread management. For performance’s sake we attempt to avoid any kernel intervention and in the case of shared memory multiprocessors, we attempt to achieve a high degree of speedup within a single application. We experiment with new and already established scheduling strategies for both uniprocessors and SMPs. We present three distinct uniprocessor schedulers with varying characteristics, one of which is distinguished by very fast context switching, another that provides fast inter-thread communication and a third which highlights the benefits of cache affinity scheduling even on uniprocessors. We implement a series of shared run queue SMP schedulers by decreasing the lock granularity for each subsequent scheduler and present a scheduler which is lock free and in particular non-blocking. Results for shared run queue schedulers demonstrate that although finer grain locks and in particular lock free algorithms are suitable for inter-thread communication and for synchronisation among various internal scheduler data structures, the scheduler’s general performance does not necessarily benefit. Moreover, due the high amount of contention for the run queue, we show how shared run queue schedulers are not suitable for fine grain thread scheduling. On the other hand, per processor run queue schedulers are usually criticised for their weak load balancing. We therefore introduce a series of new migration policies, enabling per processor run queue schedulers to perform better than their shared run queue counterparts. We present two schedulers which use distinct migration policies, the first of which migrates threads in groups we call batches across a shared pool of batches. The second is a completely wait free scheduler since it complements wait free thread synchronisation techniques with a series of wait free migration algorithms.