2.9 Scheduling Messages

The scheduler queue is a powerful priority queue. The following functions can be used to place messages into the scheduler queue. These messages are treated very much like newly-arrived messages: when they reach the front of the queue, they trigger handler functions, just like messages transmitted with CMI functions. Note that unlike the CMI send functions, these cannot move messages across processors.

Every message inserted into the queue has a priority associated with it. CONVERSE priorities are arbitrary-precision numbers between 0 and 1. Priorities closer to 0 get processed first, priorities closer to 1 get processed last. Arbitrary-precision priorities are very useful in AI search-tree applications. Suppose we have a heuristic suggesting that tree node N1 should be searched before tree node N2. We therefore designate that node N1 and its descendants will use high priorities, and that node N2 and its descendants will use lower priorities. We have effectively split the range of possible priorities in two. If several such heuristics fire in sequence, we can easily split the priority range in two enough times that no significant bits remain, and the search begins to fail for lack of meaningful priorities to assign. The solution is to use arbitrary-precision priorities, aka bitvector priorities.

These arbitrary-precision numbers are represented as bit-strings: for example, the bit-string ``0011000101'' represents the binary number (.0011000101). The format of the bit-string is as follows: the bit-string is represented as an array of unsigned integers. The most significant bit of the first integer contains the first bit of the bitvector. The remaining bits of the first integer contain the next 31 bits of the bitvector. Subsequent integers contain 32 bits each. If the size of the bitvector is not a multiple of 32, then the last integer contains 0 bits for padding in the least-significant bits of the integer.

Some people only want regular integers as priorities. For simplicity's sake, we provide an easy way to convert integer priorities to CONVERSE's built-in representation.

In addition to priorities, you may choose to enqueue a message ``LIFO'' or ``FIFO''. Enqueueing a message ``FIFO'' simply pushes it behind all the other messages of the same priority. Enqueueing a message ``LIFO'' pushes it in front of other messages of the same priority.

Messages sent using the CMI functions take precedence over everything in the scheduler queue, regardless of priority.

A recent addition to CONVERSE scheduling mechanisms is the introduction of node-level scheduling designed to support low-overhead programming for the SMP clusters. These functions have ``Node'' in their names. All processors within the node has access to the node-level scheduler's queue, and thus a message enqueued in a node-level queue may be handled by any processor within that node. When deciding about which message to process next, i.e. from processor's own queue or from the node-level queue, a quick priority check is performed internally, thus a processor views scheduler's queue as a single prioritized queue that includes messages directed at that processor and messages from the node-level queue sorted according to priorities.

void CsdEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)
This call enqueues a message to the processor's scheduler's queue, to be sorted according to its priority and the queueing strategy. The meaning of the priobits and prioptr fields depend on the value of strategy, which are explained below.

void CsdNodeEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)
This call enqueues a message to the node-level scheduler's queue, to be sorted according to its priority and the queueing strategy. The meaning of the priobits and prioptr fields depend on the value of strategy, which can be any of the following:

• CQS_QUEUEING_BFIFO: the priobits and prioptr point to a bit-string representing an arbitrary-precision priority. The message is pushed behind all other message of this priority.

• CQS_QUEUEING_BLIFO: the priobits and prioptr point to a bit-string representing an arbitrary-precision priority. The message is pushed in front all other message of this priority.

• CQS_QUEUEING_IFIFO: the prioptr is a pointer to a signed integer. The integer is converted to a bit-string priority, normalizing so that the integer zero is converted to the bit-string ``1000...'' (the ``middle'' priority). To be more specific, the conversion is performed by adding 0x80000000 to the integer, and then treating the resulting 32-bit quantity as a 32-bit bitvector priority. The message is pushed behind all other messages of this priority.

• CQS_QUEUEING_ILIFO: the prioptr is a pointer to a signed integer. The integer is converted to a bit-string priority, normalizing so that the integer zero is converted to the bit-string ``1000...'' (the ``middle'' priority). To be more specific, the conversion is performed by adding 0x80000000 to the integer, and then treating the resulting 32-bit quantity as a 32-bit bitvector priority. The message is pushed in front of all other messages of this priority.

• CQS_QUEUEING_FIFO: the prioptr and priobits are ignored. The message is enqueued with the middle priority ``1000...'', and is pushed behind all other messages with this priority.

• CQS_QUEUEING_LIFO: the prioptr and priobits are ignored. The message is enqueued with the middle priority ``1000...'', and is pushed in front of all other messages with this priority.

Caution: the priority itself is not copied by the scheduler. Therefore, if you pass a pointer to a priority into the scheduler, you must not overwrite or free that priority until after the message has emerged from the scheduler's queue. It is normal to actually store the priority in the message itself, though it is up to the user to actually arrange storage for the priority.

void CsdEnqueue(void *Message)
This macro is a shorthand for

CsdEnqueueGeneral(Message, CQS_QUEUEING_FIFO,0, NULL)

provided here for backward compatibility.

void CsdNodeEnqueue(void *Message)
This macro is a shorthand for

CsdNodeEnqueueGeneral(Message, CQS_QUEUEING_FIFO,0, NULL)

provided here for backward compatibility.

void CsdEnqueueFifo(void *Message)
This macro is a shorthand for

CsdEnqueueGeneral(Message, CQS_QUEUEING_FIFO,0, NULL)

provided here for backward compatibility.

void CsdNodeEnqueueFifo(void *Message)
This macro is a shorthand for

CsdNodeEnqueueGeneral(Message, CQS_QUEUEING_FIFO,0, NULL)

provided here for backward compatibility.

void CsdEnqueueLifo(void *Message)
This macro is a shorthand for

CsdEnqueueGeneral(Message, CQS_QUEUEING_LIFO,0, NULL)

provided here for backward compatibility.

void CsdNodeEnqueueLifo(void *Message)
This macro is a shorthand for

CsdNodeEnqueueGeneral(Message, CQS_QUEUEING_LIFO,0, NULL)

provided here for backward compatibility.

int CsdEmpty()
This function returns non-zero integer when the scheduler's processor-level queue is empty, zero otherwise.

int CsdNodeEmpty()
This function returns non-zero integer when the scheduler's node-level queue is empty, zero otherwise.