A Study On A New Kind Of Synchronization In Linux

In modern computer system, synchronization includes two distinct but related concepts: synchronization of processes, and synchronization of data. However, this thesis will focus on the former. Process synchronization can be classified as blocking and non-blocking. Currently, Linux kernel is one of the most complicated parallel programs. The developers have already introduced many synchronization mechanisms into Linux kernel, which include both blocking and non-blocking algorithms. The key difference between blocking and non-blocking algorithm is whether it will stop the progress of related tasks. The traditional lock belongs to blocking synchronization, such as mutual exclusion and semaphore. With the evolution of computer science and technology, a growing number of flaws have been detected on traditional lock mechanisms. Those problems refer to the performance of the whole system and many applications; they also weaken the RAS features of the operating system. Non-blocking synchronization can be used to overcome those drawbacks for blocking implementation. Non-blocking algorithm is one of the most active research hot points on synchronization. The evolution of non-blocking synchronization in Linux kernel consists of the introductions of lock-free/wait-free mechanisms, refinement and balance of lock granularity, and decrease of chances for lock conflict.PWCS is suggested firstly by Nicholas Me Guire at 13th Real Time Linux Workshop. This synchronization mechanism exploits the inherent randomness of modern multi or many cores computer system. PWCS is one of probabilistic synchronization mechanisms that can be used to solve multiple readers/single-writer problems. And reader is wait-free for PWCS.At present, PWCS prototype has three types of implementation:marker, compression, and CRC. The key difference of those implementations is how to identify the inconsistency of shared data replication. PWCS can provide arbitrary probability of read-success by increasing the number of replications, and the spatial overhead is acceptable. And, since PWCS don’t have to use the atomic read/write operations and memory barriers, it can offer excellent portability. For user-space, we just need to implement PWCS as an application library which doesn’t need the support from kernel. Compared with other synchronization mechanisms that focus on multi readers/single writer problem, PWCS also has excellent performance.PWCS is the start of the research on probabilistic synchronization. In computer system, the source of non-determinism refers to hardware and software, and the randomness is inherent feature of modern operating system. It is necessary for digging the randomness of computer system that can be used for many scenarios, such as a random number generator.The main contributions of this thesis are as follows:(1) discussing the classification of synchronization, (2) analyzing the evolution of lock-free synchronization in Linux, (3) implementing PWCS prototype, and (4) evaluating the efficiency and performance of PWCS.