Your browser does not support JavaScript! Skip to main content
Free 30-day trial Customer portal Careers DO-178C Handbook
 
Rapita Systems
 

Industry leading verification tools & services

Rapita Verification Suite (RVS)

  RapiTest - Unit/system testing   RapiCover - Structural coverage analysis   RapiTime - Timing analysis (inc. WCET)   RapiTask - Scheduling visualization   RapiCoverZero - Zero footprint coverage analysis   RapiTimeZero - Zero footprint timing analysis   RapiTaskZero - Zero footprint scheduling analysis

Multicore verification

  MACH178   Multicore Timing Solution   RapiDaemons

Services

  V & V Services   Qualification   Training   Tool Integration  Support

Industries

  Aerospace (DO-178C)   Automotive (ISO 26262)   Space

Other

  RTBx   Mx-Suite   Software licensing   Product life cycle policy  RVS development roadmap

Latest from Rapita HQ

Latest news

Danlaw Acquires Maspatechnologies - Expanding Rapita Systems to Spain
Rapita co-authored paper wins ERTS22 Best paper award
A look back on Rapita's Multicore DO-178C training in Huntsville
RVS 3.17 Launched
View News

Latest from the Rapita blog

Why mitigating interference alone isn’t enough to verify timing performance for multicore DO-178C projects
There are how many sources of interference in a multicore system?
Supporting modern development methodologies for verification of safety-critical software
Flexible licensing software fit for modern working
View Blog

Latest discovery pages

do178c DO-178C Guidance: Introduction to RTCA DO-178 certification
matlab_simulink MATLAB® Simulink® MCDC coverage and WCET analysis
code_coverage_ada Code coverage for Ada, C and C++
amc-20-193 AMC 20-193
View Discovery pages

Upcoming events

Aerospace Tech Week Europe 2023
2023-03-29
Certification Together International Conference
2023-05-10
View Events

Technical resources for industry professionals

Latest White papers

DO178C Handbook
Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis
Compliance with the Future Airborne Capability Environment (FACE) standard
View White papers

Latest Videos

Efficient DO-178C verification - WCET analysis
Efficient DO-178C verification - Code coverage
Efficient DO-178C verification - Functional testing
SCADE Test video thumbnail
Complementary DO-178C verification with Ansys(R) SCADE Test(TM) and RVS
View Videos

Latest Case studies

Supporting ISO 26262 ASIL D software verification for EasyMile
RapiCover’s advanced features accelerate the certification of military UAV Engine Control
Front cover of whitepaper collins
Delivering world-class tool support to Collins Aerospace
View Case studies

Other Downloads

 Webinars

 Brochures

 Product briefs

 Technical notes

 Research projects

Discover Rapita

Who we are

The company menu

  • About us
  • Customers
  • Distributors
  • Locations
  • Partners
  • Research projects
  • Contact us

US office

+1 248-957-9801
info@rapitasystems.com
Rapita Systems, Inc.
41131 Vincenti Ct.
Novi
MI 48375
USA

UK office

+44 (0)1904 413945
info@rapitasystems.com
Rapita Systems Ltd.
Atlas House
Osbaldwick Link Road
York, YO10 3JB
UK

Spain office

+34 930 46 42 72
info@rapitasystems.com
Rapita Systems S.L.
Parc UPC, Edificio K2M
c/ Jordi Girona, 1-3, Office 306-307
Barcelona 08034
Spain

Working at Rapita

Careers

Careers menu

  • Current opportunities & application process
  • Working at Rapita
Back to Top

How to set up safe, portable interprocess communication without interrupt locks

Breadcrumb

  1. Home
  2. Blog
  3. How to set up safe, portable interprocess communication without interrupt locks
2010-09-30

The approach described here allows non-blocking interprocess communication to take place on a single CPU, via a FIFO, circular buffer. I originally encountered this method of interprocess communication as part of the MASCOT design methodology, as a way of implementing the channel IDA.

To meet the requirements of providing safe interprocess communication without interrupt locks, the following must be true:

  • Both processes can access common memory
  • Communication is one-way, and occurs from one process/thread to another
  • It is possible to write the in/out indices as an atomic action (i.e. as one machine instruction)
  • It is possible to read the in/out indices as an atomic action
  • Writer never attempts to write to a full buffer
  • Reader never attempts to read from a buffer that doesn't contain valid data
  • Adding data into the buffer does not need to be atomic. That is, it is safe to store records or arrays into the queue

The approach relies upon a circular buffer consists of the following elements:

buffer: array of data with 2^n elements 
in, out: unsigned integers as indices with range 0 to (2^(n+1))-1 

Before reading and writing, it is important to test whether the queue is empty or full, respectively. All queue conditions can be found by looking at the result of the following expression:

 buffer_contents = (in - out) % (2^(n+1)) 

The results of this expression are as follows:

buffer_contents == 0: Queue empty
buffer_contents > 0 && buffer_contents < 2^n: Queue
        contains valid data 
buffer_contents == 2^n: Queue is full 
buffer_contents > 2^n: overrun has occurred 

Writing must only take place when the queue is empty or contains some data (buffer_contents is less than 2^n). If this is the case, the following is done:

buffer[in % (2^n)] = data 
in = (in + 1) % (2^(n+1)) 

Reading must only take place if the queue is full or if it contains valid data (buffer_contents is not 0 and is less than or equal to 2^n). To read, the following actions are performed:

data = buffer[out % (2^n)] 
out = (out + 1) % (2^(n+1)) 

How can we be sure this is safe for interprocess communication?

Writing to a queue

If the writer starts by ensuring that the queue is not full (or overrun), the queue will never overrun after the test, because you are the only one capable of filling up the queue.

If the reader can preempt the writer, there are two possible behaviours:

The reader preempts the writer before the incremented value of 'in' is written

or:

The reader preempts the writer after the incremented value of 'in' is written.

Both of these behaviours are safe (i.e. will not result in the reader attempting to read a partly written value).

Reading from a queue

If the reader starts by ensuring the queue is not empty, the queue will never underrun after the test, because the reader is the only thread capable of emptying the queue.

If the writer can preempt the reader, there are two possible behaviours:

The writer preempts the reader before the incremented value of 'out' is written

or:

The writer preempts the reader after the incremented value of 'out' is written.

Both of these behaviours are safe (i.e. will not result in the writer attempting to overwrite a partly read value). Short C implementation:

#define N 4
#define buffer_contents ((in-out)%(1<<(N+1)))

void * buffer[1<<N];
unsigned int in;
unsigned int out;

void enqueue (void * data)
{
	if (buffer_contents==(1<<N)) return; // full
	buffer[in % (1<<N)] = data;
	in = (in + 1) % (1<<(N+1));
}


void * dequeue (void)
{
	void * data;
	if (buffer_contents==0) return NULL; // empty
	data = buffer[out % (1<<N)];
	out = (out + 1) % (1<<(N+1));
	return data;
}

DO-178C webinars

DO178C webinars

White papers

DO178C Handbook Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis
Compliance with the Future Airborne Capability Environment (FACE) standard
5 key factors to consider when selecting an embedded testing tool
  • Solutions
    • Rapita Verification Suite
    • RapiTest
    • RapiCover
    • RapiTime
    • RapiTask
    • MACH178

    • Verification and Validation Services
    • Qualification
    • Training
    • Integration
  • Latest
  • Latest menu

    • News
    • Blog
    • Events
    • Videos
  • Downloads
  • Downloads menu

    • Brochures
    • Webinars
    • White Papers
    • Case Studies
    • Product briefs
    • Technical notes
    • Software licensing
  • Company
  • Company menu

    • About Rapita
    • Careers
    • Customers
    • Distributors
    • Industries
    • Locations
    • Partners
    • Research projects
    • Contact
  • Discover
    • AMC 20-193
    • What is CAST-32A?
    • Multicore Timing Analysis
    • MC/DC Coverage
    • Code coverage for Ada, C & C++
    • Embedded Software Testing Tools
    • Aerospace Software Testing
    • Automotive Software Testing
    • Certifying eVTOL
    • DO-178C
    • WCET Tools
    • Worst Case Execution Time
    • Timing analysis (WCET) & Code coverage for MATLAB® Simulink®

All materials © Rapita Systems Ltd. 2023 - All rights reserved | Privacy information | Trademark notice Subscribe to our newsletter