Blog:

Bus arbitration done easy

Published on Oct 12, 2018
By Terry / Senior System Engineer

In an embedded system a single bus (for example: SPI or I2C) can be used by multiple attached modules (for instance: a motion sensor or an EEPROM). If these modules would access the bus at the same time, there will be collisions during data transmissions. From a design perspective however, it would be nice to treat the bus as a single resource for each module: never to worry that transmissions would collide. In this article a generic technique for bus arbitration is discussed. This assumes C++11 is used on the embedded device.

Taking the I2C bus as example; assuming there are 2 (or more) slave devices on the bus. From a design perspective we would have 2 classes handling each slave independently. During initialization of the application we pass a reference to the class handling the I2C for data transmissions (here: the I2C peripheral driver). Ideally both classes do not know what the other is doing, which will lead to transmission conflicts: one class might be busy with a transmission while the other (not knowing this is ongoing) can start another transmission.

To prevent such collisions an Arbiter can be used. This class acts as intermediate layer between the 2 classes (here: the users of the I2C bus) and the I2C class (peripheral driver, the one pushing the bits over the wire). Its primary task is to control when requests for transmissions are passed onto the I2C bus and thus prevent these collisions.

The first thing to do is to shield access to the bus by adding an atomic flag indicating if the bus is busy. If so new requests to use the bus will have to wait until the bus is free. To prevent such new request blocking the system, a buffer is used to queue the request. This buffer is a single-consumer, single producer, thread safe variant, to make callbacks from the I2C class possible: transmission completed events.

The Arbiter will re-route the callbacks in the requests to allow control over these requests. In simple form: all requests are queued. Once the bus becomes (or is) free, the next item from buffer is processed. This blocks the bus until the transmission is completed. Once completed, the next item from the queue is processed, until the queue is empty. This allows for an efficient means to use the bus (but no control over the order of transmissions: first in the queue is first to be processed).

Since there is no control over how the 2 classes add requests (this can be from a higher priority interrupt, or main loop context), the addition of requests into the buffer is protected by making the buffer (for additions) a multi-producer variant. To do so, first the interrupts are disabled to prevent a race condition if an addition is done from (a higher priority) interrupt. Then a spinlock is used to make sure an ongoing addition is completed before a possible interruption of a higher priority interrupt accesses the buffer. The time it takes to add a request to buffer is expected to be rather short, which favors the use of a spinlock over a more complex synchronisation construct.

Once a request is handled, the Arbiter will call the configured callback (transmission completed), then processes the next request in the buffer (until the buffer is empty). Internally the Arbiter is the only one accessing the I2C bus (by rerouting the callbacks), the outside world (the using classes) can benefit from this without any modifications.

By having an interface identical to the I2C class, this Arbiter can be added to a project when required. Instead of passing the I2C class to the 2 using classes – the Arbiter is passed, no more functional changes are needed. The result is a flexible, small and fast intermediate Arbiter layer, which takes away the complexity of bus arbitration. It can be used for any bus which allows 2 or more slave devices.

This implementation does rely on a small single-producer, single consumer, thread safe, lock free buffer, in this particular case I selected one from Kjell Hedström (with minor modifications): https://www.codeproject.com/Articles/43510/Lock-Free-Single-Producer-Single-Consumer-Circular

To show this works (and how) I created a demo project which stubs the I2C peripheral driver (in particular the asynchronous DMA handling) and added an Application stub on top – the Arbiter can thus be tested without the use of real embedded hardware. Feel free to have a look and let me know what you think: https://github.com/tlouwers/embedded/tree/master/Arbiter