Common Lisp Package: CALISPEL

README:

FUNCTION

Public

! (CHANNEL VALUE &OPTIONAL TIMEOUT)

Send VALUE on CHANNEL, waiting up to TIMEOUT seconds (a non-negative REAL number; or indefinitely when NIL). Returns a boolean indicating whether the timeout expired before the value could be sent.

? (CHANNEL &OPTIONAL TIMEOUT)

Receive a value from CHANNEL, waiting up to TIMEOUT seconds (a non-negative REAL number; or indefinitely when NIL). Returns the value (or NIL upon timeout) and a boolean indicating whether the timeout expired before a value could be received.

OPERATION-ALTERNATE (TIMEOUT PRIORITY OPS)

Given a list of at least one OPERATION, executes the first one that becomes available within TIMEOUT seconds and returns that OPERATION. If TIMEOUT seconds have elapsed without any of the OPERATIONs becoming available, returns NIL. If TIMEOUT is NIL, waits indefinitely. If one or more of the OPERATIONs can be executed immediately, which one is chosen depends on the value of PRIORITY. When PRIORITY is :FIRST, the first OPERATION listed in OPS that can be executed is chosen. When PRIORITY is :FAIR, one of the OPERATIONs that can be executed immediately is chosen at random.

TEST-CHANNEL (CHANNEL &KEY (MESSAGE-COUNT 2000000) (READER-COUNT 4) (WRITER-COUNT 4) (VERBOSE-P NIL))

Tests CHANNEL by writing MESSAGE-COUNT messages to it. The CHANNEL must not have any buffered messages at the time this function is called, and no other thread may operate on CHANNEL for the duration of this function call. The buffer of CHANNEL, if any, must be exact (it must not drop messages). WRITER-COUNT writer threads are created to write to the channel. READER-COUNT reader threads are created to read from the channel. The CHANNEL is tested under reader-contention, writer-contention, and natural conditions. Under the reader-contention condition, writer threads will intentionally become slow in order to induce multiple readers contending for CHANNEL; the buffer of CHANNEL (if any) should become empty. Under the writer-contention condition, reader threads will intentionally become slow in order to induce multiple writer threads contending for CHANNEL; the buffer of CHANNEL (if any) should become full (or grow indefinately if unbounded). Under the natural condition, no thread will intentionally slow down to induce contention on the other side. The condition which is in effect cycles once every 3 seconds; therefore, a high enough MESSAGE-COUNT should be given so that this function takes at least ~10 seconds to run.

TEST-CONCURRENCY (&REST KW-ARGS &KEY (CHANNEL-COUNT 8) (MAKE-CHANNEL-FN (LAMBDA () (MAKE-INSTANCE 'CHANNEL))) (MESSAGE-COUNT 2000000) (READER-COUNT 4) (WRITER-COUNT 4))

Tests concurrency by creating CHANNEL-COUNT CHANNELs and running TEST-CHANNEL against each, simultaneously. MAKE-CHANNEL-FN is a designator of a function of no arguments that returns a fresh CHANNEL. It is used to produce the test channels. MESSAGE-COUNT, READER-COUNT, and WRITER-COUNT are as in TEST-CHANNEL; note that these values are per-channel-test, not globally.

Private

ALTERNATION-WAIT (TIMEOUT ALTERNATION)

Given an ALTERNATION, waits up to TIMEOUT seconds for another thread to execute one of its OPERATIONs (or indefinitely when TIMEOUT is NIL). The SELECTED slot of ALTERNATION must initially be NIL. Upon return, if another thread executed one of the OPERATIONs of ALTERNATION, that OPERATION will appear in the SELECTED slot of ALTERNATION. Otherwise (if timed-out), that slot will be NIL. Must be called with *LOCK* held.

CONTROL-CHANNEL-VECTOR (COUNT)

Returns a vector of COUNT channels suitable for controlling threads.

DEQUEUE-CHANNEL-FOR-OPERATION (RECEIVING-OP)

Dequeues the oldest object from the the BUFFER of the CHANNEL that RECEIVING-OP is interested in receiving from, storing it in RECEIVING-OP. RECEIVING-OP must be interested in receiving. The CHANNEL must have at least one object in its BUFFER. Must be called with *LOCK* held.

DEQUEUE-OPERATION-WITH-CHANNEL (OP)

Given an OPERATION that will no longer be waiting, dequeues it from the vector of OPERATIONs waiting on CHANNEL (where CHANNEL is the CHANNEL that the OPERATION was interested in). Must be called with *LOCK* held.

DIVIDE-VECTOR (VECTOR COUNT)

Returns a vector of COUNT vectors with elements from VECTOR. The resulting vectors will be roughly the same length (some may be 1 longer than others), and the sum of the lengths will be equal to the length of VECTOR. The order of elements in the returned vectors is not assured.

ENQUEUE-CHANNEL-FOR-OPERATION (SENDING-OP)

Enqueues the object stored in SENDING-OP to the BUFFER of the CHANNEL that SENDING-OP is interested in sending to. SENDING-OP must be interested in sending. The CHANNEL must have room in its BUFFER for at least one object. Must be called with *LOCK* held.

ENQUEUE-OPERATION-WITH-CHANNEL (OP)

Given an OPERATION that is about to wait, enqueues it with the vector of OPERATIONs waiting on CHANNEL (where CHANNEL is the CHANNEL that the OPERATION is interested in). Must be called with *LOCK* held.

ENQUEUE/DEQUEUE-CHANNEL-FROM-OP-TO-OP (SENDING-OP RECEIVING-OP)

Given SENDING-OP (an OPERATION interested in sending to a channel), and RECEIVING-OP (an OPERATION interested in receiving from the same channel), enqueues SENDING-OP's object and dequeues an object for RECEIVING-OP, at the same time. Must be called with *LOCK* held.

EXECUTE-OPERATION (OP)

Executes the given OPERATION. It must be ready (per OPERATION-READY?). Must be called with *LOCK* held.

INVOKE-ACTION (OP)

Invokes the action associated with the given ALT-OPERATION.

OPERATION-QUEUE (CHANNEL DIRECTION)

Returns the queue of all the OPERATIONs waiting to move data in DIRECTION on CHANNEL. When DIRECTION is SEND, the returned OPERATIONs are those waiting until the BUFFER of CHANNEL is no longer full. When RECEIVE, the returned OPERATIONs are those waiting until the BUFFER is no longer empty.

OPERATION-READY? (OP)

Returns a boolean value indicating whether the given OPERATION can be executed. Must be called with *LOCK* held.

OPERATION-TRANSFER (SENDING-OP RECEIVING-OP)

Transfers one object from SENDING-OP to RECEIVING-OP. SENDING-OP must be interested in sending, and RECEIVING-OP in receiving. They must be interested in the same channel, and the channel's BUFFER must be empty. Must be called with *LOCK* held.

Undocumented

ALT-BODY-CODE (OP-CONDITIONS OP-FORMS PRIORITY OTHERWISE-P TIMEOUT-FORM OTHERWISE-FORMS)

ALT-CODE (CLAUSES PRIORITY)

NSORT (SEQUENCE PREDICATE &KEY (KEY NIL KEY-SPEC-P))

NSTABLE-SORT (SEQUENCE PREDICATE &KEY (KEY NIL KEY-SPEC-P))

OP-!-CLAUSE-CONDITION (CLAUSE-OPERANDS)

OP-!-CLAUSE-FORM (CLAUSE-OPERANDS BODY)

OP-?-CLAUSE-CONDITION (CLAUSE-OPERANDS)

OP-?-CLAUSE-FORM (CLAUSE-OPERANDS BODY)

OP-CLAUSE-CONDITION (CLAUSE)

OP-CLAUSE-FORM (CLAUSE)

OPPOSITE-DIRECTION (DIRECTION)

OTHERWISE-CLAUSE? (CLAUSE)

PARSE-OTHERWISE-CLAUSE (CLAUSE)

SORT (SEQUENCE PREDICATE &KEY (KEY NIL KEY-SPEC-P))

STABLE-SORT (SEQUENCE PREDICATE &KEY (KEY NIL KEY-SPEC-P))

MACRO

Public

FAIR-ALT (&BODY CLAUSES)

Performs one of the given channel operations, choosing fairly from the set of operations that first becomes available, then evaluates each of the forms associated with the selected operation. If no operation can immediately be made, waits until an operation is available (optionally up to a given timeout). The result is the result of the final evaluated form (or no values if no clause was executed). clauses ::= operation-clause* [otherwise-clause] operation-clause ::= (operation form*) otherwise-clause ::= ({otherwise | (otherwise [:timeout timeout])} form*) operation ::= (? channel [lambda-list [condition]]) ; receive | (! channel value [condition]) ; send channel: Evaluated to produce a CHANNEL to send to or receive from. The channel forms associated with operations that do not pass the condition are not evaluated. lambda-list: Either a symbol naming a variable to be bound to the value received from the channel, or a destructuring lambda list naming a set of variables to be bound to the destructured value received from the channel. The bindings are visible to the associated forms. If the value cannot be destructured according to the lambda list, an error is signalled. Note that multiple receive clauses for the same channel with different destructuring lambda-lists *cannot* be used for pattern matching. value: An expression whose primary value is used as the message to send to the channel. All value expressions are evaluated before selecting an operation, except for those associated with operations that do not pass the condition. condition: Evaluated to produce a generalized boolean indicating whether the associated operation-clause should receive further consideration. When condition is not given or its resulting value is true, the associated operation is kept for consideration. When the resulting value is false, the operation is removed from consideration (as if its associated channel never becomes ready for sending/receiving). form: Evaluated in sequence when the associated clause is executed. The values of the evaluation of the last form of the effective clause become the result of FAIR-ALT. timeout: Evaluated to produce the duration, as a non-negative REAL number of seconds, to wait for an effective operation to become available before resorting to the otherwise-clause. The result may also be NIL to specify no time out. When an otherwise-clause exists, the default time out is 0, meaning that if none of the channels in the operation-clauses are immediately available, the otherwise-clause forms are executed immediately. When there is no otherwise-clause, the default time out is NIL. It is useful to specify a timeout expression that conditionally evaluates to NIL, in order to disable the time out and inhibit the execution of the otherwise-clause (provided that there are channel operations to wait for that haven't been excluded by a false condition). If there are no effective operations (because all the conditions evaluated to false, or because no operations were specified), then the otherwise-clause (if any) is executed immediately (even if the specified time out is NIL). Stylistically and for future compatibility, avoid side-effects in channel, value, condition, and timeout expressions.

PRI-ALT (&BODY CLAUSES)

Performs one of the given channel operations, choosing the first listed operation that becomes available, then evaluates each of the forms associated with the selected operation. If no operation can immediately be made, waits until an operation is available (optionally up to a given timeout). The result is the result of the final evaluated form (or no values if no clause was executed). The syntax and semantics (other than clause priority) are the same as with FAIR-ALT. PRI-ALT is (currently) more efficient than FAIR-ALT.

SLOT-ACCESSOR

Public

CHANNEL (OBJECT)

The CHANNEL this OPERATION is interested in operating on.

DIRECTION (OBJECT)

Which DIRECTION this OPERATION is trying to move data in. When SEND, the OPERATION is interested in sending the value specified by :VALUE to CHANNEL. When RECEIVE, the OPERATION is interested in receiving a value from CHANNEL.

VALUE (OBJECT)

The value associated with this OPERATION. When sending, this is the value to send. When receiving, this is the received value if the OPERATION has executed, or undefined if it has not.

SETFVALUE (NEW-VALUE OBJECT)

The value associated with this OPERATION. When sending, this is the value to send. When receiving, this is the received value if the OPERATION has executed, or undefined if it has not.

Private

ACTION (OBJECT)

A function to be called when this OPERATION succeeds. When DIRECTION is SEND, the function is called with no arguments. When DIRECTION is RECEIVE, the function is called with the received value. The result of this function is the result of the ALT macro form.

ALTERNATION (OBJECT)

The ALTERNATION (if any) that this OPERATION is a member of.

SETFALTERNATION (NEW-VALUE OBJECT)

The ALTERNATION (if any) that this OPERATION is a member of.

BUFFER (OBJECT)

The QUEUE used to buffer pending objects. The QUEUE must not be holding any objects, and the QUEUE must not be used again unless the CHANNEL owning it is never used again. (Exception: QUEUEs that strictly have no state, such as instances of NULL-QUEUE, may be shared among CHANNELs.)

OPERATIONS (OBJECT)

The set of OPERATIONs waiting to occur (as a list).

RECEIVE-OPERATION-QUEUE (OBJECT)

A queue of all the OPERATIONs waiting to receive from this channel. An OPERATION may be waiting to receive only when BUFFER is empty.

SELECTED (OBJECT)

The OPERATION selected by a thread that took action, or NIL if no OPERATION has yet been executed by another thread. The thread that writes to SELECTED is generally a different thread than that which waits on the ALTERNATION. The OPERATION, when given, must have been executed, and it must appear in the OPERATIONS slot.

SETFSELECTED (NEW-VALUE OBJECT)

The OPERATION selected by a thread that took action, or NIL if no OPERATION has yet been executed by another thread. The thread that writes to SELECTED is generally a different thread than that which waits on the ALTERNATION. The OPERATION, when given, must have been executed, and it must appear in the OPERATIONS slot.

SELECTION-CV (OBJECT)

A condition variable which is notified when an OPERATION has been selected and was written to the SELECTED slot. The thread that waits on SELECTION-CV is generally that which is waiting on the ALTERNATION.

SEND-OPERATION-QUEUE (OBJECT)

A queue of all the OPERATIONs waiting to send to this CHANNEL. An OPERATION may be waiting to send only when BUFFER is full.

VARIABLE

Public

Undocumented

+NULL-QUEUE+

Private

*LOCK*

A lock protecting the global channel state. The lock must be held whenever any data is being accessed (unless it can be proven that no other thread can access that data). Specifically, that means CHANNELs, OPERATIONs, and ALTERNATIONs that other threads can potentially get access to.

CLASS

Public

CHANNEL (OBJECT)

A communication channel.

NULL-QUEUE

The null queue. Used for unbuffered CHANNELs. Think of it as the NULL class, but for queues.

OPERATION

A potential operation (receive or send) to perform on a channel. An OPERATION instance represents an interest to perform the operation; it does not represent an operation that definitely will be or has been carried out.

Private

ALT-OPERATION

An OPERATION with bookkeeping for use by the *-ALT macros.

ALTERNATION (OBJECT)

Represents a waiting alternation of several OPERATIONs. That is, represents the act of waiting for the associated OPERATION that first becomes available.