多核系统上可伸缩的读写同步

发布时间：2018-03-13 12:09

本文选题：多核系统　切入点：性能　出处：《复旦大学》2014年硕士论文　论文类型：学位论文

【摘要】：随着计算机硬件技术的飞速发展,单个处理器性能的增长已经遇到了瓶颈,处理器个数的增长成为了提高单个计算机性能的主要发展方向。处理器个数的增长给应用程序的性能提升带来了新的机遇,也带来了性能和正确性上的挑战。为了充分的利用这些处理器资源,操作系统和计算密集型的应用正在向并行化的模型演进。在一个并行的系统中,多个任务之间往往需要共享一些信息以进行协同工作。为了使得多个任务可以正确有序的访问这些共享信息,并行程序采用同步的方法对不同任务的访问进行控制和限制,使得对每一个单独的任务来说,这些共享信息都维持着某种一致性。错误的使用同步可能会导致并行程序的错误或者影响其执行的性能,设计一个易于正确使用,而又具有良好性能的同步原语是一个十分重要的问题。一个理想的同步原语应该具有定义清晰的较强的语义保证,同时又尽量不影响应用在多核系统上的可伸缩性。读写锁是一种在语义上非常清晰的同步机制,它将对共享状态的访问者分为读者和写者两个类别,在同一时刻,仅允许一个写者进入临界区更新共享状态,或允许多个读者同时进入临界区读取共享状态。因为其易于理解的语义,读写锁在操作系统内核以及并行应用程序中得到了广泛的应用。理论上说,因为读写锁中的不同的读者并没有逻辑上的依赖,多个读者在没有写者的情况下应该可以快速的进入和离开临界区,并且不需要相互通信。事实上,现有的读写锁设计中,往往读者获取锁时要产生相互通信,或者使用昂贵的内存屏障指令确保同步的正确性。这些设计限制了使用读写锁的并行系统中读者的可伸缩性和吞吐量。针对读写锁的潜在性能问题,我们设计了一个高可伸缩的读写锁算法PRWLock,这一算法巧妙利用了现代多核系统较短的内存写可见时间以及较小的核间中断开销,在满足TSO内存一致性模型的系统上实现了不需要共享信息以及内存屏障的读者锁,同时保证了写者锁可接受的性能。我们进一步发现,在现代主流操作系统中的睡眠,唤醒机制会对同步机制的可伸缩性造成限制。当多个因为某一条件而进入睡眠的任务的唤醒条件达到时,唤醒操作是由单一任务串行完成的。针对这一问题,我们设计了操作系统中可以并发的唤醒睡眠任务的机制PWake,并将其与PRWLock相结合实现了可伸缩性更好的读写同步机制。为了验证这两种机制的有效性,我们在Linux的内核和用户态分别实现了PRWLock,并结合了PWake唤醒机制。我们将PRWLock应用在了Linux内核的地址空间管理机制上和一个用户态的内存数据库中,多项实验表明PRWLock具有同前人研究成果相似或更好的性能特性,并且更加易于部署到现有并行系统中。
[Abstract]:With the rapid development of computer hardware technology, the performance of a single processor has met with a bottleneck. The increase in the number of processors has become the main development direction for improving the performance of a single computer, and the increase in the number of processors has brought new opportunities for improving the performance of applications. It also presents performance and correctness challenges. In order to take full advantage of these processor resources, operating systems and computationally intensive applications are evolving to parallel models. In order to enable multiple tasks to access the shared information correctly and orderly, parallel programs use synchronous methods to control and restrict access to different tasks. For each individual task, this shared information maintains some consistency. The wrong use of synchronization can lead to errors in parallel programs or affect their performance, and design a design that is easy to use correctly. The synchronization primitive with good performance is a very important problem. An ideal synchronization primitive should have clear definition and strong semantic guarantee. Read and write locks are a semantically clear synchronization mechanism that classifies shared state visitors into two categories, reader and writer, at the same time. Only one writer is allowed to enter the critical area to update the shared state, or multiple readers are allowed to enter the critical section at the same time to read the shared state. Read-write locks are widely used in operating system kernels and parallel applications. In theory, because different readers in read-write locks do not have logical dependencies, Multiple readers should be able to quickly enter and leave the critical area without a writer and do not need to communicate with each other. Or use expensive memory barrier instructions to ensure the correctness of synchronization. These designs limit reader scalability and throughput in parallel systems using read-write locks. We design a highly scalable read-write lock algorithm, PRWLock. this algorithm makes good use of the shorter memory write visible time and the lower inter-core interrupt cost of modern multi-core system. Reader locks that do not require a shared information and memory barrier are implemented on systems that satisfy the TSO memory consistency model, while ensuring the acceptable performance of the writer lock. The wake-up mechanism limits the scalability of the synchronization mechanism. When the wake-up conditions for multiple tasks entering sleep due to a given condition are met, the wakeup operation is done serially by a single task. In order to verify the effectiveness of the two mechanisms, we have designed a mechanism for concurrent wake-up of sleep tasks in the operating system, PWake. and combined it with PRWLock to achieve a more scalable read / write synchronization mechanism. We have implemented PRW locklock in Linux kernel and user state, and combined with PWake wake-up mechanism. We have applied PRWLock to address space management mechanism of Linux kernel and a memory database in user state. Many experiments show that PRWLock has similar or better performance characteristics than previous studies, and it is easier to deploy to existing parallel systems.
【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP332

【相似文献】