• lock-free queue
• networking
• producer-consumer
• virtualization

Cloud Computing has radically changed the way we look at computing hardware
resources, with server machines hosting tens to thousands of possibly unrelated
applications belonging to different customers. Virtualization technologies provide those isolation guarantees that are necessary for untrusted applications to coexist
within the same physical machine. Although hardware support for virtualization is
essential to achieve acceptable performance, the success of Cloud Computing is still largely attributable to a wide range of software products, frameworks and libraries that complete and enhance the virtualization capabilities directly provided by the hardware.
In particular, Cloud hosts often need to process in software huge amounts of network traffic on behalf of Virtual Machines and application containers, typically attached to a common virtual switch. Even with the many CPUs available on modern machines (100 and beyond), software packet processing at very high speeds (i.e., 1-100 Mpps) may be challenging because of the communication overhead incurred by the processing pipeline when using basic mechanisms such as inter-process notifications, sleeps, or lock-free queues. The current literature lacks of models to analyze these low level mechanisms in depth and identify suitable guidelines for the design of high-speed processing systems. This thesis presents a thorough discussion of the impact that queues and synchronization mechanisms have on the performance of I/O processing pipelines, for all the possible operating regimes, and with a particular focus on networking and virtualization. Models for throughput, latency and energy efficiency of producer-consumer systems are introduced and validated experimentally to verify that they are appropriate to represent real systems. Several fast Single Producer Single Consumer queues are discussed and characterized in terms of interactions with the cache coherence system, with two of them being original contributions of this thesis. As an application of how these basic mechanisms can be used in practice, a novel high-performance packet scheduling architecture, suitable for Data Centers, is presented and experimentally validated, showing a better throughput, latency and isolation than current solutions. Overall, the analysis presented in this thesis provides suggestions and guidelines to design efficient software datapath components for virtual network switches, hypervisor backends for device emulation, and other I/O processing components relevant to Cloud Computing environments.