Starvation Freedom in Multi-Version Transactional Memory Systems

Software Transactional Memory systems (STMs) have garnered significant interest as an elegant alternative for addressing synchronization and concurrency issues with multi-threaded programming in multi-core systems. This work explores the notion of one of the progress property, i.e., starvation-freed...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-08
Main Authors: Chaudhary, Ved Prakash, Juyal, Chirag, Kulkarni, Sandeep, Kumari, Sweta, Sathya Peri
Format: Article
Language:English
Subjects:
Algorithms
Computer memory
Concurrency
Concurrent processing
Synchronism
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Software Transactional Memory systems (STMs) have garnered significant interest as an elegant alternative for addressing synchronization and concurrency issues with multi-threaded programming in multi-core systems. This work explores the notion of one of the progress property, i.e., starvation-freedom, in STMs. An STM system is said to be starvation-free if every thread invoking a transaction gets the opportunity to take a step (due to the presence of a fair scheduler) such that the transaction eventually commits. Multi-version STMs maintain multiple-versions for each transactional object that provides greater concurrency. In this paper, we propose multi-version starvation-free STM, KSFTM, which as the name suggests achieves starvation-freedom while storing K-versions of each t-object. To the best of our knowledge, this is the first multi-version STM system that satisfies starvation-freedom. We implement KSFTM and compare its performance with single-version starvation-free STM system (SV-SFTM) which works on the priority principle. Our experiments show that KSFTM achieves more than two-fold speedup over SV-SFTM for different workloads. KSFTM shows significant performance gain (ranging from 1.3 to 3.3 times) over existing non-starvation-free state-of-the-art STMs (ESTM, NOrec, and MVTO) on various work- loads.
ISSN:2331-8422