Complex Arbritration Example

Introduction

Consider a complex mote similar to a TelosB mote that includes the following:

• serial communication for direct connection.
• serial communication for gps.
• serial communication disabled.
• radio communication (SPI based)
• mass storage using a Secure Digital card (SPI based)

• Serial communication utilizes UART1/USART1 with an external multiplexer for switching between the three choices.
  
• Radio communication uses a CC2420 ChipCom radio that uses the SPI bus (SPI1/USART1).
  
• SD Mass Storage uses the SPI (SPI1/USART1).

Off mote serial communications can be in one of three modes:

NONE: no off-mote communication is occuring. USART default owner is NONE and h/w can be shut down.

SERIAL: communications via a direct connect comm cable. Uses SerialAMSender. (Default SERIAL)

RADIO: communications via the CC2420 radio stack. (Default NONE). Uses h/w events doesn't need to sit on h/w.

This determines how the mote will communicate with the outside world. This is different from DefaultOwner of the underlying hardware although they are related. NONE being selected allows USART1 and associated h/w to be powered down. SERIAL being selected configures the serial hardware (including connecting clocks and timers which prevent the CPU from going into a lower power mode). SERIAL will own the h/w unless another module requests it. This ownership allows the serial port to receive packets. The SERIAL driver manages incoming bytes on a packet level and will only release the h/w at a packet boundary.

Types of Access

Default Ownership

Some modules using the USART h/w require long term ownership to function properly. The SERIAL and GPS drivers use the CPU and the serial h/w to collect packets one byte at a time. Interrupting this receive will lose the incoming packet or message.

Transitory/Atomic

A module that obtains the h/w, performs a single well defined operation and then releases the device is a transitory user. Long term dedication of the resource is not needed. The intent is an owning module will not respond to other modules requesting the resource, completing its task quickly and then releasing. The CC2420 radio h/w will do a receive and then generate a h/w event. The CC2420 RADIO driver will see this event, request the h/w, and process the receive data when granted.

Implications of GPS

The addition of GPS creates the potential for multiple serial stacks to be concurrent. Assume that SERIAL is selected when the GPS is turned on. The GPS driver will request the UART1 h/w and will need to keep it while receiving packets from the GPS. But while the GPS is functioning it is desirable to be able to receive control packets from the SERIAL port. The SERIAL module is a default owner so the GPS module obtains the port for some amount of time, releases (at a message boundary), and then requests again after an interval (allowing the SERIAL port to potentially start receiving a packet), the SERIAL port won't release if a packet has started to be received. The SERIAL driver will release when it gets to a packet boundary.

In addition to interacting with the SERIAL driver, the GPS module should be prepared to release (at a message boundary) if another module (such as the SD driver) requests the hardware. If too much time passes other modules can be starved. Serious problems can develop (current code will panic). This argues for the GPS releasing either on request or via timing (kept small enough).

At one point, we toyed with the idea of the GPS being a transient user of the serial hardware. However, the GPS stack functions in a similar fashion to the SERIAL AM stack. Namely, the CPU must be listening to serial hardware in order to receive packets. This argues for the GPS being another DefaultOwner.

Other Considerations

• Forcing the GPS to release/request at message boundaries is expensive due to overhead from the unconfigure/configure at each release/request/grant. It is advantagous to minimize how often the release/request/grant occurs.

• Basing module release purely on time seems rigid. Policy based on requests seems to be more flexible.

• Race conditions need to be explored. If ResourceRequested.requested events are used to cause sharing, then a mechanism is needed for dealing with requests that are "simultaneous" (a request will be granted but hasn't occurred yet, so the current owner is NO_RES, and any new requested events won't be seen by the grantee. This breaks the policy of wait for a request. This only impacts modules that sit on a resource so should only effect DefaultOwners. The behaviour of the code implementing this needs to be examined.

• During normal operation, the GPS module and SERIAL (direct connect) are mutually exclusive. When the mote is plugged in we know where it is and there is no need for the GPS to tell us. When the radio is active, it can receive while being disconnected from the CPU. A h/w event is generated which signals the RADIO driver. In this sense, the RADIO and GPS do not compete with each other. The RADIO driver when presented with the receive event will request, when granted it obtains the SPI bus and handles the receive packet.
  
  This argues for the normal access mechanism being based on request rather than special casing using timers. The GPS releasing/requesting at every message boundary would be expensive and is counter-indicated. An efficient mechanism for switching between different modules could use the ResourceRequested.requested interface. Another possibility is to make GPS a DefaultOwner. Basically any module that needs to sit on the hardware would be a DefaultOwner.

• Implementing GPS and SERIAL coincident is useful for two reasons. For debugging, the mote can be plugged into a base station while the GPS is running. The second reason is to flesh out the implementation and structure for this level of complex arbitration.

• The SD driver is a transient driver that will obtain the USART/SPI1 h/w path, initilize the SD chip, and write one to three buffers. Each buffer can take up to 500 ms. This raises the question of release between buffers. The simplest mechanism and follows the basic idea of Transitory Users would call for a release/request/grant after each buffer. This would allow other users to get in if needed. Only non-default modules would be able to actually obtain control of the resource.

• SERIAL and NONE are selected explicitly. GPS is turned on programatically and at least when debugging SERIAL could be turned on for local communications. This implies a mechanism to control switching between SERIAL and GPS so they can share in some reasonable fashion. Request/Grant/Release via an Arbiter seems the obvious choice.

Proposed Design

The ResourceRequested interface is used to allow modules to indicate a desire to obtain a shared resource from its current owner. This allows more flexibility in release and control strategies than would be ordinarily available. However, in practice, ResourceRequested introduces poor access symantics and its implementation introduces access control race conditions. What happens when we rely on ResourceRequested to inform owning modules to potentially release (state transition) but we have a simultaneous occurance of two requests.

The goal in this proposed design is to build this system without the use of ResourceRequested.