Fast user-level inter-thread communication, synchronisation and streaming

Abstract

Since 2000, the fast user-level thread scheduler SMASH has been actively developed at the University of Malta. This project's objective is to design and implement several user-level inter-thread communication constructs for SMASH. Since communication and synchronization among threads in a process is heavily used in most multi-threading programs, the efficiency of interthread communications affects the efficiency of the whole program. In the past, those communication and synchronization constructs were built with locks, but this lock-based approach has some problems such as potential deadlock(or livelock), starvation and priority inversion. In order to solve these problems, lock-free algorithms were invented. A concurrent algorithm is lock-free, if after a finite step of execution, at least one of the participating threads is guaranteed to progress. Recently there is a lot of interest in lockfree algorithms in the research community. In this project, all the inter-thread communication constructs considered have two implementations: the lockbased implementation and the lock-free implementation. The performance of concurrent programs using these user-level constructs is measured and compared with the performance of programs using kernel-level inter-thread communication constructs. Besides, the differences between the lock-based implementations and lock-free implementations are also analyzed.