the-bits-of-channel-state.md

The bits of channel state

Definitions

The most pertinent aspects of a Channel’s state can be described in terms of five bits:

CLOSED = 0x10
EMPTY  = 0x08
FULL   = 0x04
PUSHED = 0x02
PULLED = 0x01

where:

• A channel is closed permanently at its inlet, such that no further send operations are allowed. Any values remaining in the buffer may still be received.

• A channel is empty if it is unbuffered or if its buffer is empty.

• A channel is full if it is unbuffered or if it has a fixed buffer which is at or over capacity. A channel with a sliding buffer or dropping buffer can never be full.

  It may be helpful to think of full not strictly in terms of capacity, but rather as meaning, “would detain a process if that process were to perform a send operation now”.

• A channel is pushed when it is subjected to a “compression force” at its inlet, caused by a queue of detained senders waiting to “push” a value into the channel.

• A channel is pulled when it is subjected to a “tension force” at its outlet, caused by a queue of detained receivers waiting to “pull” a value from the channel.

Implications

Channel semantics suggest certain logical implications and restrictions:

• A channel can never be simultaneously pushed and pulled, as this suggests a deadlock. At all observable times, all processes detained by a channel at one of its ends will already have been dispatched before the channel would ever need to detain a process at its other end.

• A channel that has closed can no longer be pushed or pulled, as any awaiting processes must have been dispatched upon closing, and any further channel operations will dispatch the calling process immediately.

• The condition pulled implies empty, and pushed implies full. Likewise, receive on empty causes pulled, and send on full causes pushed.

• A channel that is neither empty nor full (i.e., a partially filled buffered channel) cannot be pushed or pulled, since processes may act on either end of the channel without being blocked.

Configurations

          1E  1C  1A  18  16  14  12  10  0E  0C  0A  08  06  04  02  00 
        1F  1D  1B  19  17  15  13  11  0F  0D  0B  09  07  05  03  01   
—————————————————————————————————————————————————————————————————————————
CLOSED   @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ · · · · · · · · · · · · · · · · 
EMPTY    @ @ @ @ @ @ @ @ · · · · · · · · @ @ @ @ @ @ @ @ · · · · · · · · 
FULL     @ @ @ @ · · · · @ @ @ @ · · · · @ @ @ @ · · · · @ @ @ @ · · · · 
PUSHED   @ @ · · @ @ · · @ @ · · @ @ · · @ @ · · @ @ · · @ @ · · @ @ · · 
PULLED   @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · @ · 
—————————————————————————————————————————————————————————————————————————
valid?   · · · @ · · · @ · · · @ · · · @ · @ @ @ · · @ @ · @ · @ · · · @ 
receive? · · · · · · · · · · · @ · · · @ · @ · · · · · · · @ · @ · · · @ 
send?    · · · · · · · · · · · · · · · · · · @ · · · @ @ · · · · · · · @ 

Validation

With respect to the semantics of a channel, only a subset of the thirty-two possible state configurations are ever valid at any time:

valid?   · · · @ · · · @ · · · @ · · · @ · @ @ @ · · @ @ · @ · @ · · · @ 
         \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ 
    0x      1       1       1       1       7       3       5       1    

It follows then that channel state represented this way can be generally validated by a very fast operation, which takes the five bits of channel state, and performs a left shift and a mask against the integer 0x11117351:

isValid = flags => !!( 1 << flags & 0x11117351 )

Notes

• A total of just two configurations are valid for pushed (0x06, 0x0E), and likewise for pulled (0x09, 0x0D).

Selection

Given its current state, a channel can foretell whether a hypothetical channel operation (receive|send) called by a process would either be immediately serviced (true), or cause the channel to detain the calling process (false). This query is integral to the select operation, which must determine which one channel operation from among multiple candidates can be performed first.

Here again, particular subsets of state configurations can be expressed in integer form, to represent the exact conditions under which:

• a channel may service a receive operation without blocking the receiver:

receive? · · · · · · · · · · · @ · · · @ · @ · · · · · · · @ · @ · · · @ 
         \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ 
    0x      0       0       1       1       4       0       5       1    

canProcessReceive = x => !!( 1 << x & 0x00114051 )

• a channel may service a send operation without blocking the sender:

send?    · · · · · · · · · · · · · · · · · · @ · · · @ @ · · · · · · · @ 
         \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ \__ __/ 
    0x      0       0       0       0       2       3       0       1    

canProcessSend = x => !!( 1 << x & 0x00002301 )