This note is a restoration and update of XCHANs: Notes on a New Channel Type.
See the still existing CPA 2012 page.
XCHANs: Notes on a New Channel Type
Øyvind Teig. Autronica Fire and Security (AFS) (A UTC Fire and Security company) – https://www.autronicafire.no
Keys: Channels, synchronous, asynchronous, buffers, overflow, flow control, CSP.
In: Presented at: Communicating Process Architectures 2012 (CPA-2012), at Abertay University in Dundee, Scotland (26-29 Aug. 2012)
Proceedings: Communicating Process Architectures 2012 (CPA-2012). Proceedings of the 34th WoTUG Technical Meeting (pages 155-170). P.H. Welch et al. (Eds.) Open Channel Publishing Ltd., 2012. ISBN 978-0-9565409-5-9 © 2012 The authors and Open Channel Publishing
Ltd (Dissolved company, therefore url from Wayback Engine) – All rights reserved.
This paper proposes a new channel type, XCHAN, for communicating messages between a sender and receiver. Sending on an XCHAN is asynchronous, with the sending process informed as to its success. XCHANs may be buffered, in which case a successful send means the message has got into the buffer. A successful send to an unbuffered XCHAN means the receiving process has the message. In either case, a failed send means the message has been discarded. If sending on an XCHAN fails, a built-in feedback channel (the x-channel, which has conventional channel semantics) will signal to the sender when the channel is ready for input (i.e., the next send will succeed). This x-channel may be used in a select or ALT by the sender side (only input guards are needed), so that the sender may passively wait for this notification whilst servicing other events. When the x-channel signal is taken, the sender should send as soon as possible – but it is free to send something other than the message originally attempted (e.g. some freshly arrived data). The paper compares the use of XCHAN with the use of output guards in select/ALT statements. XCHAN usage should follow a design pattern, which is also described. Since the XCHAN never blocks, its use contributes towards deadlock-avoidance. The XCHAN offers one solution to the problem of overflow handling associated with a fast producer and slow consumer in message passing systems. The claim is that availability of XCHANs for channel based systems gives the designer and programmer another means to simplify and increase quality.
- Paper: CPA2012/paper.pdf (locally) – https://wotug.org/paperdb/ (web)
- Presentation: CPA2012/presentation.pdf
Prologue: This paper had a prologue in a blog note I wrote in the spring of 2012, “034 – Output guard vs. “channel ready” channel.” See, https://oyvteig.blogspot.com/2011/12/034-output-guard-vs-channel-ready.html. The XCHAN suggestion would in practice also encapsulate the semantics of the “knock-come” pattern, as seen in 009 – The “knock-come” deadlock free pattern and also discussed in several other notes here. The internal ChanSched is also shown in the paper.
An added description (for myself 11 years on..): The listening side of an XCHAN waits on the channel just as a standard CHAN, in an ALT/select or in an input statement. The sender side is a user or internal process/task that acts as a “driver” to do the semantics of an overflow. It also just outputs just as on a standard CHAN. However, the sender also needs to listen to an extra channel, the x-channel. The runtime system handles the internal behaviour of the sending channel and also sends on x-channel, since it would know if any process/task in fact has taken the input or not. If none has taken the input, this is called a “failed send” (even if it’s perfectly normal!) and the sender is given a “return” on the x-channel (in the original paper’s semantics). The sender handles this any way it wants to. Alternatively the sender process/task may be part of bundle which is called XCHAN and which would have buffered or unbuffered sender tasks hidden internally, just like in the below model. So XCHAN = x-channel + CHAN + optional hidden handler process/task.
Value-added: once you have read and understood XCHANs, the “Selective choice ‘feathering’ with XCHANs” paper of CPA 2013 might be of interest. There, “this semantics may be used to avoid having to send (and receive) messages that have been seen as uninteresting. We call this scheme feathering, a kind of low level implicit subscriber mechanism.” It is inspired from Tony Hoare‘s lecture from 2003, «Concurrent programs wait faster» (here), which I was lucky enough to attend. See Publications.
An occam Model of XCHANs
Fringe at CPA-2013 (the year after). See the still existing CPA 2013 page.
Observe that the semantics of the internal feedback x-channel is different in this model than in my original paper. See next chapter.
Peter H. WELCH, School of Computing, University of Kent, UK
- Presentation: On occam Model of XCHANs (fringe, PDF, 19 MB, as restored from Wayback Engine)
- Code: xchan_occ.pdf and xchan_occ.txt (the original was called
Names of XCHAN Implementations
See the still existing CPA 2013 page.
Øyvind TEIG, Autronica Fire and Security AS, Trondheim, Norway
Abstract (orig here ). Two names for possible XCHAN implementations are suggested. The original presentation (Teig, CPA-2012) describes the “classic” scheme where the xchan-ready channel is used only if the original sending fails. The occam-pi model (Welch, CPA-2013 fringe) uses the “pre-confirmed” scheme, where a signal on xchan-ready is a necessary precondition to any communication. It is believed that “feathering” (Teig, CPA-2013) seems to be possible only with the classic scheme.
- Presentation: Names of XCHAN Implementations
See search for XCHAN here. In particular: Lecture NTNU: Becoming textual: attempting to model ‘XCHAN’ with CSPm (even if I didn’t succeed).