Search-insert-delete

Description

The Search-insert-delete example involves a shared data structure that is being accessed concurrently by three types of independent actors. Searchers access the list without changing it. So, any number of concurrent searchers can be accessing the structure safely. Inserters have the ability to add new elements to the end of the structure. Only one inserter can access the structure at any given time, but can work concurrently with any number of searchers. Lastly, Deleters can remove items from any position in the structure. As such, any deleter demands exclusive access to the structure. So, while a deleter has access to the structure neither any other deleter, any inserter, nor any searcher is allowed access.

Highlights

The primary actors are modeled by classes SEARCHER, INSERTER, and DELETER. Additionally, some common features are abstracted into a class ACTOR from which the effective actor classes inherit. Each actor lives only to access the data structure one time. The access looks similar in the different actor classes, and consists of executing a procedure to start the action, then waiting a random time interval, then executing a procedure to end the action.

The shared data structure is modeled by the class SHARED_LIST. Because the point of this example is to demonstrate the different allowable types of concurrent access by the different types of actors, it should be said that features that support that goal are all that you will find in this class. In other words, SHARED_LIST doesn't really maintain a data structure, it only provides the features necessary to coordinate safe concurrent access by searchers, inserters, and deleters.

SHARED_LIST provides features in three feature clauses, each explicitly exported one of the types of accessors. For example, the feature clause exported to clients of type SEARCHER includes the query can_search and the procedures start_search and end_search. The features available to inserters and deleters are nearly identical. Because of the different concurrency requirements of each type of actor though, the implementation for can_search and can_delete are different. Also different are the implementations for starting and ending actions for the various actor types.

SHARED_LIST keeps certain state attributes:

searchers: INTEGER_32 -- How many searchers are there? inserting: BOOLEAN -- Is someone inserting? deleting: BOOLEAN -- Is someone deleting?

These are used in the can_search, can_insert, and can_delete queries, which are in turn used in the preconditions for the corresponding start_xxxx features. For example, start_delete is constrained by a precondition can_delete, which is implemented like this:

can_delete: BOOLEAN -- Can delete? do Result := not deleting and not inserting and searchers = 0 end

For the deleter calling {SHARED_LIST}.start_delete, the precondition clause can_delete is an uncontrolled precondition. This means that the deleter will wait until the can_delete becomes true before feature application of start_delete occurs.