In response to the increasing ubiquity of multicore processors, applications are usually designed or deployed to make each core busy. Unfortunately, lock contention within operating systems can limit the scalability of multicore systems so severely that an increase in the number of cores can actually lead to reduced performance (i.e., scalability collapse). Existing lock implementations have disadvantages in scalability, power consumption, and energy efficiency. In this paper, we observe that the number of tasks requesting a lock has a significant correlation with the occurrence of scalability collapse. Based on this observation, a lock implementation that allows tasks waiting for a lock to either spin or enter a power-saving state based on the number of requesters is proposed. Our lock protocol is called requester-based lock and is implemented in the Linux kernel to replace its default spin lock. Based on the results of a sensitivity analysis, we find that the best policy, in practice, for a task waiting for a lock to be granted is to enter the power-saving state immediately after noticing the lock cannot be acquired. Our requester-based lock scheme is evaluated using intensive benchmarking on AMD 32-core and Intel 40-core systems. Experimental results suggest that our lock avoids scalability collapse completely for most applications and shows better scalability, power consumption, and energy efficiency than previous work. Besides, the requester-based lock is extensible, which means using together with other kinds of spin locks can provide better scalability and energy efficiency.

Spin lock contention in operating systems can limit scalability on multicore systems so significantly that an increase in the number of cores actually leads to reduced speedup (i.e., scalability collapse). Modeling spin lock contention is an effective way to understand the scalability collapse phenomenon and explore collapse avoidance schemes. However, previous spin lock models have disadvantages in accuracy and efficiency. To overcome these drawbacks, this paper proposes LockSim, an event-driven simulator which models both the sequential execution in lock-protected codes (i.e., critical sections) and shared hardware resource contention caused by the cache coherence protocol. Our simulator is verified against real-world workloads with different degrees of spin lock contention. Experimental results suggest that LockSim can reproduce the scalability collapse phenomenon with better accuracy than previous work. Besides, several metrics are also used to characterize this phenomenon and collapse avoidance methods are investigated.

This paper addresses the resource contention issue caused by the sharing of the last level caches by introducing a novel contention-aware scheduler. To accurately determine a task's resource requirements, i.e. the unique input of our scheduler, we develop a methodology to select the best heuristic metric from five candidates to represent a task's resource requirements. Based on the heuristic of each task acquired by exploiting the performance monitor unit, our scheduler co-schedules tasks with complementary resource requirements by combining scheduling order adjustments with task-to-core reassignments. The proposed scheduler has been implemented in the completely fair scheduler, rotating staircase deadline scheduler and O(1) schedulers. Using eight workloads constructed from nine NASA advanced supercomputing serial benchmarks on an Intel dual-core platform, the execution time of an individual task is reduced by up to 21%, system scalability and performance of a workload are improved by up to 13%, and the full potential of the contention-aware scheduling can be achieved if the time slice length and the period of executing each task once are short enough. In addition, our proposal exhibits benefits in the reduction of the execution time fluctuation of individual tasks due to an enforcement of reasonable usage of shared resources. Finally, we demonstrate an expected performance improvement on an Intel eight-core platform in order to suggest the broad applicability of our protocol.

SUMMARY Multicore processor systems have become mainstream. To release the full potential of multiple cores, applications are programmed to be parallel to keep every core busy. Unfortunately, lock contention within operating systems can limit the scalability so seriously that use of more cores leads to reduced throughput (scalability collapse). To understand and characterize the collapse behavior easily, a discrete‐event simulation model, which considers both the sequential execution of critical sections and the overhead of hardware resource contention, is designed and implemented. By the use of the model, we observe that the percentage of time used to wait for locks and the number of tasks requesting for a lock have a significant correlation with the occurrence of scalability collapse. On the basis of these observations, two new techniques (lock contention aware scheduler and requester‐based adaptive lock) are proposed to remove the scalability collapse on multicores. The proposed methods are implemented in the Linux kernel 2.6.29.4 and evaluated on an AMD 32‐core system to verify their effectiveness. By using micro‐benchmarks and macro‐benchmarks, we find that these methods can remove scalability collapse totally for four of five workloads exhibiting the collapse behavior. For one workload that does not suffer scalability collapse, these proposed methods only introduce negligible overhead. Copyright © 2012 John Wiley & Sons, Ltd.

In response to the increasing ubiquity of multicore processors, there has been widespread development of multithreaded applications that strive to realize their full potential. Unfortunately, lock contention within operating systems can limit the scalability of multicore systems so severely that an increase in the number of cores can actually lead to reduced performance (i.e., scalability collapse). Existing efforts of solving scalability collapse mainly focus on making critical sections of kernel code fine-grained or designing new synchronization primitives. However, these methods have disadvantages in scalability or energy efficiency. In this article, we observe that the percentage of lock-waiting time over the total execution time for a lock intensive task has a significant correlation with the occurrence of scalability collapse. Based on this observation, a lock-contention-aware scheduler is proposed. Specifically, each task in the scheduler monitors its percentage of lock waiting time continuously. If the percentage exceeds a predefined threshold, this task is considered as lock intensive and migrated to a Special Set of Cores (i.e., SSC). In this way, the number of concurrently running lock-intensive tasks is limited to the number of cores in the SSC, and therefore, the degree of lock contention is controlled. A central challenge of using this scheme is how many cores should be allocated in the SSC to handle lock-intensive tasks. In our scheduler, the optimal number of cores is determined online by the model-driven search. The proposed scheduler is implemented in the recent Linux kernel and evaluated using micro- and macrobenchmarks on AMD and Intel 32-core systems. Experimental results suggest that our proposal is able to remove scalability collapse completely and sustains the maximal throughput of the spin-lock-based system for most applications. Furthermore, the percentage of lock-waiting time can be reduced by up to 84%. When compared with scalability collapse reduction methods such as requester-based locking scheme and sleeping-based synchronization primitives, our scheme exhibits significant advantages in scalability, power consumption, and energy efficiency.

In response to the increasing ubiquity of multicore processors, there has been widespread development of multithreaded applications that strive to realize their full potential. Unfortunately, lock contention within operating systems can limit the scalability of multicore systems so severely that an increase in the number of cores can actually lead to reduced performance (i.e. scalability collapse). Existing lock implementations have disadvantages in scalability, resource utilization and energy efficiency. In this work, we observe that the number of tasks requesting a lock has a significant correlation with the occurrence of scalability collapse. Based on this observation, we propose a novel lock implementation that allows tasks blocked on a lock to either spin or maintain a power-saving state according to the number of lock requesters. We call our lock implementation protocol a requester-based lock and implement it in the Linux kernel to replace its default spin lock. Based on the results of an analysis, we find that the best policy for a task waiting for a lock to become free is to enter the power saving state immediately after noticing that the lock cannot be acquired. Our lock-requester based lock scheme is evaluated using micro- and macro-benchmarks on AMD 32-core and Intel 40-core systems. Experimental results indicate our lock scheme removes scalability collapse completely for most applications. Furthermore, our method shows better scalability and energy efficiency than mutex locks and adaptive locks.

Multi-core processor architectures have become ubiquitous in today's computing platforms, especially in parallel computing installations, with their power and cost advantages. While the technology trend continues towards having hundreds of cores on a chip in the foreseeable future, an urgent question posed to system designers as well as application users is whether applications can receive sufficient support on today's operating systems for them to scale to many cores. To this end, people need to understand the strengths and weaknesses on their support on scalability and to identify major bottlenecks limiting the scalability, if any. As open-source operating systems are of particular interests in the research and industry communities, in this paper we choose three operating systems (Linux, Solaris and FreeBSD) to systematically evaluate and compare their scalability by using a set of highly-focused microbenchmarks for broad and detailed understanding their scalability on an AMD 32-core system. We use system profiling tools and analyze kernel source codes to find out the root cause of each observed scalability bottleneck. Our results reveal that there is no single operating system among the three standing out on all system aspects, though some system(s) can prevail on some of the system aspects. For example, Linux outperforms Solaris and FreeBSD significantly for file-descriptor and process-intensive operations. For applications with intensive sockets creation and deletion operations, Solaris leads FreeBSD, which scales better than Linux. With the help of performance tools and source code instrumentation and analysis, we find that synchronization primitives protecting shared data structures in the kernels are the major bottleneck limiting system scalability. Empowered by the knowledge obtained through targeted experiments and analysis on a small-scale system, we are able to project the scalability of an application on any of the investigated operating systems running on a system of a larger number of cores.

Multi-core architectures have become mainstream. Trends suggest that the number of cores integrated on a single chip will increase continuously. However, lock contention in operating systems can limit the parallel scalability on multi-cores so significantly that the speedup decreases with the increasing number of cores (thrashing). Although the phenomenon can be easily reproduced experimentally, most existing lock models are not able to do so. To overcome this challenge, this paper develops a discrete event simulation model which has the capability of capturing both the sequential execution in critical sections and the contention for shared hardware resources. The model is evaluated using a series of typical parameter configurations which can represent different degrees of lock contention. Experimental results suggest that the thrashing phenomenon can be observed when the model parameters are selected properly. To further understand this phenomenon, statistics such as the percentage of time spent waiting for locks and the number of cores waiting for a lock are exploited to characterize the lock thrashing. In addition, the model sensitivity to changes in memory latency and hardware architectures are also examined. Finally, we use this model to compare three methods which are proposed for preventing the lock thrashing.

Multi-core architectures have been adopted in various computing environments. Predictions based on Moore's Law state that thousands of cores can be integrated on a single chip within 10 years. To achieve better performance and scalability on multi-cores, applications should be multi-threaded, and therefore threads assigned on different cores can execute concurrently. However, lock contention in kernels can affect the scalability so significantly that the speedup decreases with the increasing number of cores (thrashing). Existing efforts to address this problem mainly focus on deferring lock thrashing, and therefore these techniques cannot prevent thrashing fundamentally. In this paper, we propose to use lock-aware scheduling to avoid thrashing. Our method detects thrashing on a per-thread basis and migrates contended threads to a smaller set of cores. The optimal number of cores is determined by maximizing the proposed normalized throughput model of migrated threads. The proposed method is implemented in Linux 2.6.29.4 and evaluated on a 32-core system. Experimental results on a series of lock-intensive micro- and macro-benchmarks show the effectiveness: for 3 of 5 workloads exhibiting thrashing behaviour, lock-aware scheduling can detect the speedup decrease accurately and sustain the maximal speedup, for the remaining 2 workloads, the performance can be improved greatly although the maximal speedup is not sustained, for 1 workload which does not suffer thrashing, the method introduces negligible runtime overhead.

Multi-core processor architectures can have significant performance advantage over traditional single core designs, which are limited by power and processor complexity. Predictions based on Moore's Law state that a processor chip may accommodate thousands of cores in 5–10 years. Can software scale with the number of cores and achieve the performance potential?

In this paper, we evaluate and compare the parallel scalability of three commodity operating systems (Linux, Solaris and FreeBSD) on an AMD 32-core platform. Measurements of microbenchmarks and a real-life application reveal that no operating system scales totally better than another for microbenchmarks; for the real-life application, Linux and Solaris are competitive in scalability and perform better than FreeBSD. Related kernel source analysis and performance data suggest that synchronization primitives protecting the shared data structure in kernels are the root cause of the poor scalability on multi-cores.

Multi-core architectures have become mainstream. Trends suggest that the number of cores integrated on a single chip will continue to increase. However, lock contention in applications or kernels can degrade the scalability so significantly that the speedup decreases with the increasing number of cores (thrashing). Although the phenomenon can be easily reproduced on real multi-core platforms, existing lock models are not able to do so. To overcome the disadvantage, this paper proposes an analysis model which has the capability of capturing both the sequential execution of critical sections and the overhead of lock implementation. Numerical results indicate that thrashing can be observed by using the proposed model. Furthermore, this model can also be exploited to compare different mechanisms designed for avoiding the lock thrashing.

Multi-core architecture provides more on-chip parallelism and powerful computational capability. It helps virtualization achieve scalable performance. KVM (kernel based virtual machine) is different from other virtualization solutions which can make use of the Linux kernel components such as completely fair scheduler (CFS). However, CFS treats the KVM threads as normal tasks without considering about their unique features such as thread allocation mechanism and lock inside guest virtual machine, which may harm the KVM virtualization performance. In this paper, we analyze a phenomenon that some guest multi-threaded applications have very low performance when scheduled by CFS. As a solution to this problem, we introduce two kinds of optimizations in CFS: (1) configuration optimizations (2) lock optimizations. Our contributions are: (1) implement 5 original and 2 newest proposed optimizations in the newest Linux kernel. (2) Classify and compare them, a brief analysis is also given. They are all very simple and general to other virtual machine monitors such as Xen and schedulers as O(1). The performance of our CFS optimizations to KVM threads is measured by running some well-known benchmarks in two guest virtual machines on an 8-core server which models the real world applications. The results indicate our scheduling optimizations can improve the overall system performance. This paper can provide useful advices to KVM developers and virtualization data center administrators.

CPU scheduler is a very important subsystem which affects system throughput, interactivity and fairness. The development of Linux kernel is relatively fast-paced. By now, many CPU schedulers have been designed by researchers, hobbyists and kernel hackers. It is necessary to accurately compare and analyze different characteristics among these schedulers, so as to understand and design better CPU schedulers for various applications. However, researchers lack a straight-forward method to compare and analyze these CPU schedulers precisely. In this paper, we systematically analyze and measure fairness, interactivity and multi-processors performance of three schedulers: O(1), RSDL and CFS, by using micro, synthesis and real application benchmarks. They have been ported into one scheduler framework in Linux kernel-2.6.29. Experimental results show that there are notable differences in fairness and interactivity under micro benchmarks, while minor differences in synthesis and real applications. We also analyze the impact of implementations of schedulers on fairness and interactivity of applications, discuss challenges in estimating application resource requirements in different environments, and present some ideas for developing future CPU schedulers.