Font Size: a A A

Scalable Reader-Writer Synchronization On Multicore Systems

Posted on:2015-03-31Degree:MasterType:Thesis
Country:ChinaCandidate:R LiuFull Text:PDF
GTID:2308330464463456Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
With the rapid development of hardware technology, performance of a single processor is approaching its physical limitation. Instead of optimizing single processor performance, manufactures Increasing the number of processors inside a machine to enhance system performance. This trend brought both opportunities and challenges to application programs.In order to utilize this abundant computing power, operating systems and computation intensive applications are evolving rapidly towards parallel model. In a typical parallel system, different tasks often share some information in order to coordinate together. Synchronization mechanisms are thus used to control and limit the execution of tasks to ensure the consistency of these shared states.As inappropriate use of synchronization mechanism may lead to hard-to-find concurrent bug or performance penalty, designing easy to use synchronization primitives with great performance characteristic is always a hot research topic. An ideal synchronization primitive should define clear and strong semantic guarantee while maintaining performance scalability on multicore platform. Reader-writer locks are such a clear defined synchronization primitive that allows multiple readers or a single writer entering critical section at the same time. As it is very easy to use, reader writer lock is widely adopted in OS kernel and parallel applications.Ideally, as there are no logical dependencies among different readers in a reader writer lock, multiple readers should proceed without interfering with each other if there is no writer pending. But unfortunately, nowadays reader writer lock implementation either requires communication among readers or use expensive memory barrier instruction in reader lock acquisition. These designs eventually limit the scalability or throughput of parallel system using reader writer locks.To tackle this problem, we design a scalable reader writer lock algorithm named PRWLock. This algorithm take advantage of short memory staleness latency and relativity cheap IPI cost on modern multicore platform to achieve a very short reader latency on machine with TSO memory consistency, while maintains acceptable writer performance.Further, we found that the sleep/wakeup mechanism in modern operating systems may limit the scalability of synchronization as multiple tasks waiting a same condition would be wake up serially by a single task when the condition is met. We design a parallel wakeup mechanism for OS kernel to solve this problem. We further integrated it into PRWLock and achieves better scalability.To validate the proposed algorithm, we implemented PRWLock and PWake into Linux kernel and user land. We modify the address space management in kernel and an user level memory database to use PRWLock. Evaluation shows that PRWLock achieves better or similar performance compares to prior effort while being more easily to be deployed in legacy parallel systems.
Keywords/Search Tags:Multicore Platform, Performance, Scalability, Reader-Writer Sychronization
PDF Full Text Request
Related items