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. (NONE, SERIAL, GPS)
  
• 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.

• 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 could be used to indicate requests for 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 user which will be granted will not see the request from the other requester violating the assumption).

The goal in this proposed design is to build this system without the use of ResourceRequested. Rather we use a multimplexed DefaultOwner interface that allows a class of users (that need to camp on the interface) to be given control when more transitory higher priority users are done using the resource. More than one such defaultowner requires an arbritration and sharing mechanism to be used to determine who is the current DefaultOwner and how they share amoung the class.

Modules:

NULL

No serial communications is occuring. A DefaultOwner of USART1.

Serial

Controls the SerialAM stack and access to the underlying UART1 h/w. Implements direct connect communications to a base station. When active is a DefaultOwner of the USART1 resource.

GPS

Implements the GPS stack for communicating with the GPS h/w. Uses UART1 via a serial mux to communicate. DefaultOwner of USART1 when active.

RADIO

Implements control for the CC2420 communications stack. Transitory owner of USART1.

SD

Implements control for the mass storage system. Transitory owner of USART1.

NULL, SERIAL, and GPS are DefaultOwners of USART1. While, RADIO and SD are transitory. Only one DefaultOwner can be active at a time. However, the SERIAL and GPS stacks can be running but only one of them will actively own the USART1 hardware. A mechanism is needed to switch who is the default when both SERIAL and GPS are running. A reasonable approach could make use of simple timers.

• OffMote_Mode: NONE, SERIAL, or RADIO. Controls how the communications stack works. Directs communications packets to the appropriate stack for transmission or on reception. Interacts with default selection.
• SerialDefault: NULL, SERIAL, GPS. Current default owner of the Serial h/w USART1.

Default Owner Classes

A Default Owner Class is a set of resource users that want to use a resource when no other normal users of the resource are active. They must arbitrate to become the active DefaultOwner.

In the above listed modules, NULL, SERIAL, and GPS make up a Default Owner Class. In the prototype implementation these are part of the SerialDemux class which owns the serial h/w. NULL, SERIAL, and GPS are clients of the SerialDemux module.

The existence of more than one Default Owner requires the ResourceDefaultOwner interface to be multiplexed. At any given time for a given multiplex level (for one Default Owner Class implementation) there will be exactly one owner of the DefaultOwner. The members of the class are mutually exclusive. SerialDemux must provide arbritration between its clients for who actively owns the default ownership of the serial h/w.

Originally, the DefaultOwner interface was introduced for default power management. The introduction of multiple DefaultOwners with additional capabilities raises the issue of configuration. Normal resource arbritration provides a well defined configuration mechanism that gets invoked whenever a resource is granted to a particular user. The DefaultOwner interface has no such mechanism which requires each DefaultOwner to handle its own configuration anytime ResourceDefaultOwner.granted is signaled.

When a defaultowner owns the interface a mechanism also must be provided for steering interrupt signals to the appropriate module.

Basic Idea

• One of the default owners (NULL, SERIAL, or GPS) owns the USART1 h/w unless it has been granted to a transient user. SERIAL and GPS will only give the resource up if idle (at message or packet boundary). It is possible that a sequence of transmits and receives can occur that the module will always be busy. Protection can be put into block new transmissions if a request has come in.

• Ownership, Default: A transitory user requesting the resource causes the Default Owner to receive a ResourceDefaultOwner.requested event. The DefaultOwner will release the resource at its next available opportunity (may need to wait for a packet boundary). The requested event causes a state change in the DefaultOwner so it remembers that a request is outstanding.

• Ownership, Transitory User: A different transitory user requests the resource, this request is simply queued. No communication to the current owner occurs. When the current transitory user releases the resource, the next enqueued user will be granted the resource. It is possible that transitory users will starve any defaultowner users.

• When a transitory user releases, the first queued transitory user will be given the resource. If no transitory users (queue is empty), the resource is returned to the DefaultOwner. Note that when the DefaultOwner gets the resource it will have to reconfigure the h/w. Transitory users have a configuration interface that is performed automatically on behalf of the Grantee.

• The three DefaultOwners are multiplexed. One of them is the current DefaultOwner and behaves as listed above. A demux layer is needed on the USART1 resource that then directs the events from the arbiter to the controlling DefaultOwner.

• A mechanism is needed for switching between the different DefaultOwners. I was thinking of defining a ownership window that determines the hold time for a given owner. When the hold time expires then the owner potentially allows a default change to occur. It would be subject to packet boundaries as noted above. For example, say GPS and SERIAL are on. SERIAL is the default. SERIAL has a timer running that when it expires code is called that switches the default to GPS and starts the GPS machine. SERIAL is now shutdown. GPS runs for a while and when its timer expires it switches the default back to SERIAL.

• Given the mutual exclusivity of the defaultOwners it makes sense for this to be controlled by a Resource interface. Seems like a simple Arbiter that uses request, grant, and release would work. The Default owner would be NULL, while SERIAL and GPS would be requesters.