You are here: Home / RTLWS 1999-2017 / RTLWS Submitted Papers / 
2022-07-04 - 05:23

Dates and Events:

OSADL Articles:

2022-01-13 12:00

Phase #3 of OSADL project on OPC UA PubSub over TSN successfully completed

Another important milestone on the way to interoperable Open Source real-time Ethernet has been reached


2021-02-09 12:00

Open Source OPC UA PubSub over TSN project phase #3 launched

Letter of Intent with call for participation is now available


2016-11-12 12:00

Raspberry Pi and real-time Linux

Let's have a look at the OSADL QA Farm data


2016-09-17 12:00

Preemption latency of real-time Linux systems

How to measure it – and how to fix it, if it's too high?



Real Time Linux Workshops

1999 - 2000 - 2001 - 2002 - 2003 - 2004 - 2005 - 2006 - 2007 - 2008 - 2009 - 2010 - 2011 - 2012 - 2013 - 2014 - 2015 - 2017

17th Real Time Linux Workshop, October 21 to 22, 2015 at the Virtual Vehicle Research Center, Graz, Austria

Announcement - Call for participation (ASCII) - Hotels - Directions - Agenda - Paper Abstracts - Presentations - Registration - Abstract Submission - Exhibitors and Sponsors - Gallery

seq: Buffer swapping sequence locks

Nicholas Mc Guire, OpenTech EDV Research GmbH
Peter Okech, Department of Physics University of Nairobi Nairobi

Sequence locks are a concurrency primitive that allows multiple readers to coexist anonymously as well as new readers to enter any time. The single writer may enter the critical section at any point in time resulting in a read-side detectable data inconsistency and following this detection a retry of the read operation. If readers and writers were non-preemptible, then this would be a well-bounded operation on both sides - unfortunately this cannot be assured, and under rare circumstances a writer may delay multiple - spinning - readers more or less arbitrarily long. Due to the reader anonymity, boosting (PI) is not doable.

In this paper, we introduce a slight modification of sequence locks that employs a replication strategy, allowing to switch between buffers and so ensuring that at any given time a non-preempted reader will be able to retrieve a consistent copy of data without unbounded delays. Different strategies of buffer selection (sequential vs. random) as well as different numbers of buffers and execution conditions are compared.

Buffer swapping sequence locks not only may be an improvement for general purpose operating systems but particularly are of interest to real-time operating systems as they can give bounds guarantees for readers that sequence locks can not give.

Further, we briefly introduced the use of inherent non-determinism to extract random bits on demand for low-level algorithms in complex hardware software systems, allowing to implement symmetry-breaking in the theoretically unbounded nature of retries in deterministic sequence lock algorithms.

Preliminary results for a simplified user-space proof-of-concept are presented as well as the current state of experimental kernel level work.