ORCID Identifier(s)

0000-0002-5754-6894

Graduation Semester and Year

2019

Language

English

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science and Engineering

First Advisor

Ishfaq Ahmad

Abstract

Reducing latency in Inter-Process Communication (IPC) is one of the key challenges in multi-threaded applications in multi-core environments. High latencies can have serious impact on the performance of an application when many threads queue up for memory access. Often lower latencies are achieved by using lock-free algorithms that keep threads spinning but incur high CPU usage as a result. Blocking synchronization primitives such as mutual exclusion locks or semaphores achieve resource efficiency but yield lower performance. In this paper, we take a different approach of combining a lock-free algorithm with resource efficiency of blocking synchronization primitives. We propose a queueing scheme named eLCRQ that uses the lightweight Linux Futex system call to construct a block-when-necessary layer on top of the popular lock-free LCRQ. Owing to the block-when-necessary feature, eLCRQ produces close to lock-free performance when under contention. Under no contention, we use the Futex System call for conditional blocking instead of spinning in a retry loop, which releases the CPU to perform other tasks. When compared with existing IPC mechanisms, eLCRQ yields 2.3 times reduction in CPU usage while lowering the average message latency 1.7 times. When comparing the proposed scheme with industry standard non-blocking lock-free DPDK RTE_RING, the results show a 3.4 times reduction in CPU Usage while maintaining comparable message latency. We also propose a fixed-spinning based variation of the proposed scheme, called eLCRQ-spin, which allows us to make tradeoffs between CPU usage efficiency and message latency.

Keywords

Multi-producer multi-consumer, Futex, Multi-threading, IPC

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS