New 15Mar2009. Here 22May2026. Updated 04Oct2026 (Moved the AI chapter down and added two paragraphs at the bottom). macOS apps). This is in groups Technology and My XMOS pages. Search for pages with «knock-come» here. The shortlink to this note is https://wp.me/P75eUQ-9QP.
Problem description
If relying on synchronous, unbuffered, blocking channels between tasks, like in native CSP (Wikipedia), is it possible to let two two tasks that directly communicate with each other do this spontaneously on both sides, without this causing a deadlock? The «knock-come» pattern that I coined in 2009 solves this problem by adding a non-blocking data-less signal type «channel» from the one (named slave) to the other task (named master) to «knock» onto the master’s door. The slave can do this «knock» almost any time. When the master has opened the door it shouts «come» on the blocking channel (which would be ready on the slave side) and the master must atomically wait for the data from the slave, which when «come» was received also atomically must (no new «knock» yet) send off its data. At any time (except in the atomic send come/ receive data sequence) the master is allowed to send its data to the slave, which always is able to receive. No figures here, because this is described in more detail below.
This problem may be solved with a number of patterns different from the «knoc-come». Even better, the problem may even turn up not to exist. The «knock-come» may be seen as so natural that it wouldn’t need any name. But it came out of a need, when I was still in work, in some embedded applications which are still (I hope) widely spread.
In 2009 my interest arose in how to verify this pattern with Promela and Spin. 16 years on I took it up and coded it in XMOS xC. The author of the RK0 real-time kernel also did his turn (it was him that spurred my renewed interest). Finally «I» (with the help of AI) implemented the pattern in Rust.
Updates
2009
Also included here is the original 15Mar2009 version of this note (below). The original, which was on my Google Blogspot blog (here) was first picked up by the Internet Archive Wayback Machine in 2016 (here – be patient). I moved it to this location on 22May2026 (also on Wayback Machine (here – be patient, again)). (By the way, the Time Machine Site Map of my pages is here.)
Newest chapter on the top here, but most recent update may be further down:
Code in the Rust language
See https://github.com/Aclassifier/rust_test_knock_come.
My code is running on an iMac (2024) with M4 (16 GB), under macOS Tahoe 26.7.1 (as of 104Oct2026). I also have made three macOS apps, one for each TaskSemantics (more below).
I am using the Tokio asynchronous runtime system [8]. («Tokio is scalable, built on top of the async/await language feature, which itself is scalable«). (Aside: an interesting read is Rob Pike‘s lament, see 256:[Pike’s async/await lament].) The most interesting thing with tokio is that it also supports conditional choice tokio::select! { biased; – where the biased in effect causes it to behave like [[ordered]] select in xC or PRI ALT in occam. Golang (go) does not have prioritised select (here) and (here). Update: But then, knock-come as implemented, in Promela, XC or Rust does not need this.
Aside: I now also understand that the async/await mechanism (which has been hard for me to grasp) Per Johan Vannebo and I did make an almost equivalent to in the ChanSched runtime, using a computed goto based mechanism in C. See Listing 5 and 6 in New ALT for Application Timers and Synchronisation Point Scheduling. When the basic architecture doesn’t supply this (like transputers and XMOS xCORE do), then some tool must be provided for the programmer to support the «task model» in mind, for cooperative multitasking. (From my comment on Tokio GitHub forum first point, 03Oct2026)
I also use channels as delivered by Flume, as flume::bounded. For the Flume crate, instead of Tokio’s native channels, for me it bridges the gap between traditional blocking threads (as in knock-come and XC, occam and go) and «asynchronous tasks» (whatever that term might mean). AI also took me away from sync_channel, even if it allows buffer size 0 (256:[14]).
I use tokio::select! instead of flume::Selector to get strict event priority (PRI ALT / [[ordered]] select). I initially thought that the 2009 solution needed ordered select, but when I looked at it again it does not at all! There is no reason to use it unless slave and master do other things than in my example, where the selected choice in each of them could be prioritised – it shouldn’t hurt the «embedded» knock-come. Another advantage with using Tokio is that its native sleep avoids the overhead of spawning background tasks for timers.
macOS apps
Google AI helped me make a script build_app.sh. I have learnt that using AI still requires some work for me, that I still have to use my year long coding experience to get what I want. Also, all of a sudden AI back where it started, so I have to watch carefully. But I don’t have to, once again, dig into the gritty nitty details of like, regular expressions. The figure shows the three apps running on my iMac M4 with macOS 26.5.2 over some 45 hours. None have deadlocked. Here is the Google AI generated summary (also seen in in the README.md file on GitHub):
Automated build and packaging pipeline
The project includes a robust automation workflow through the build_app.sh script, which treats the Rust source code (rust_test_knock_come.rs) as the single source of truth.
How it works:
- Dynamic extraction: The script parses the Rust file using
grepandsedto automatically extract the active semantic mode, version number, and the exact app bundle name defined inside theCURRENT_APP_NAMEmatch block - Safe configuration injecting: To package the application with context-specific metadata without altering project files permanently, the script creates a temporary backup (
Cargo.toml.bak) and injects the extracted strings into placeholder slots inCargo.toml - Zero-side-effect bundling: It triggers the compilation via
cargo bundle --release. Immediately after compilation—regardless of success or failure—the modified configuration is discarded and the pristine, originalCargo.tomlis fully restored from the backup, ensuring a clean and failure-proof build cycle - The newer
cargo-packagershould in the future perhaps be used instead ofcargo-bundle
Fractally reappearing problem
After 16Jul2026 I have not seen this problem appear, including up to 16Aug2026. But now I am able to test several behaviours, see TaskSemantics below. The deadlock does not seem to appear any more. But I will still let this chapter stay, because I have one ppm doubt. But I have grayed it out.
Observe the try_send in the master, to avoid a deadlock caused by, I think, the tokio runtime. I think that this is where the basic problem that knock-come tries to solve reappears – like a fractal. The outer architectural problem appears intrinsically, almost hidden, in the implementation that tries to solve it (*). Maybe the whole «spontaneouly sending to each other» problem is solved with try_send on one or both sides? In no case is try_send elegant. The data to be sent may become «lost». But we would know it, so it’s «ok». We can resend, which turns it into «busy poll send». Study the initial code and the log on GitHub and watch for «CATCH» (some in the screen inset). But to our rescue, instead of a while ch.try_send(msg).is_err() { } we loop up and send «fresher» data on the next arbitrary timout. Or we could have let the next timeout Duration be zero after this and resent(?) «faster». Oh well..
(*) At least the Rust implementation I present here. I will present this to some forums and see whether this is an inherent problem that simply (for Rust in general or with the tokio or flume on board), or if my implementation is wrong. I’ll take the responsibility myself, I won’t blame AI. I did. See Tokio GitHub forum first point.
Capacity of channels
A common suggestion to solve these kind of problems is to increase the capacity of the channels, from the «difficult» unbuffered channels with capacity:0 to capacity:some-arbitrary-value. First I’d say, that if this were a solution here, the knock-come architecture must have allowed it. It doesn’t. Like Pythagoras’s theorem requires a certain shape of the object, ie. a right triangle, the knock-come solves possible deadlocks between two tasks that are connected like this:
1 [cap:1, knock-on-master: signal or dummy data] 2.1 [cap:0, come-to-slave: signal or dummy data] 2.2 [cap:0, spontaneous-data-from-master: data] 3 [cap:0, data-from-slave: data]
If any of this is altered it is some answer – however, of something else. But I’d love to see the try_send removed! Update: with the three TaskSemantics one of them do try_sende, but even that won’t deadlock:
enum TaskSemantics {
MasterTrySendSlaveSelect, // Retry the same sequence value on a later timer tick if not ready
MasterSendSlaveNestedSelect, // Await delivery; slave waits for Come in a nested receive loop
MasterForceSendSlaveSelect, // Await delivery; slave tracks the handshake in the outer select
} // enum
You can see the correct capacities in main: top figure, lower part.
Having «asynchronous, non-blocking» as some kind of virtue is not for me. I use «asynchronous, buffered and non-blocking» mostly at the edges, connected to the real world where one have to take account for lost data and data becoming too old to care about, perhaps even without knowing it. Then, inside the program structure I strive for synchronous, unbuffered and blocking. (See Not so blocking after all and Timing out design by contract with a stopwatch plus I guess, «difficult»: CSP: arriving at the CHANnel island.) See Tokio GitHub forum, point 1 (below).
Some random sequence properties
Average random values of XC and Rust
As we know there are two tasks, task_slave (which randomly sends to the other) and task_master (which randomly also sends to the other), and a count is incremented in task_master both when it sends and when it receives. Both tasks each have their own random value, in the range causing timeouts of [0..99] ms, 100 numbers (from [1..100] outputs, since 0 cannot be a value in a pseudorandom sequence). On the master counting of «events» side this gives sum [0..99] = (99*100) / 2 = 4950 and average divide by 100 = 49.5s, divide by by two for knock and send in task_master = 24.75s. (v0.0.918)
Average of parts of a random sequence
How fast do we get to the average 3.5 ((1+2+3+4+5+6)/6) on a fair 1-6 dice? Not after 3 throws, probably not after 10. But then, after 100 throws we would be bouncing around 3.5. Over a series of many 100-throws we might get some close below and some close above 3.5. Dice throwing should give truly random numbers. For the the CRC32 cyclic redundancy check (Wikipedia), which the XC code random_get_random_number is based upon (on the XCORE it’s in hardware, it’s a single instruction taking a single cycle) we have a somewhat different picture. If it had had 6 «sides», it will guarantee that all numbers are reached over 6 throws, and then of course only once, but in some strict mathematically CRC-way producing a pseudo random sequence. «Each sequential jump lands on a radically different part of the number range. It does not behave like a physical system that slowly stabilises over time» (Google AI). So with the 32 bits CRC32 we’d have 2^32 = 4,294,967,296 or some 4 billion numbers to get only once per number per giant round. The average would have been the half = 2^31 = 2,147,483,648. So when I in my code say that I shall pick out 1000 of these (and take the values [0..99] with modulo divide 100) then the averages will indeed be close to 49.5. Some above and some below!
Mean always half? A new algorithm?
I have been thinking whether it would be possible to design an algorithm that for any even number of random values I always may get a mean of half of the range? I say «even» here because the algorithm I think I may have invented requires it. The code is at GitHub .. my_random.xc. I have only implemented this in XC so far, here is the function void next_random_number_symmetric code:
Details
The code below may not be the final version, see the GitHub page reference above.
void next_random_number_symmetric (
const use_random_type_e use_random_type,
randoms_t &randoms)
{
if (randoms.use_random_negated) {
// Use negative value of last positive
// This makes it symmetric around zero, seen as signed, however..
// .. seem as unsigned it is symmetric on half the number range
random_signed32_t random_signed32;
random_signed32 = (random_signed32_t) randoms.random_ssgn;
randoms.random_ssgn = (random_unsigned32_t) (-random_signed32);
randoms.use_random_negated = false;
} else { // randoms.use_random_negated false
unsigned max_loop_pos_cnt = 0;
unsigned max_loop_neg_cnt = 0;
// From limits.h plus here
// __INT_MAX__ = 2147483647
//
// UINT_MAX = (INT_MAX * 2U + 1) = (2147483647*2)+1 = 4294967295 = 0xffffffff (-1 signed )
// INT_MAX = __INT_MAX__ = 2147483647 = 0x7fffffff (UINT_MAX/2)
// UINT_MIN = 0 = 0x00000000
// INT_MIN = (-INT_MAX-1) = -2147483647-1 = -2147483648 = 0x80000000
randoms.random_ssgn = randoms.random_ssgn_prev; // Restore previous used in the generator
while (randoms.use_random_negated == false) { // Either it goes to true or the xassert
if (use_random_type == use_lib_random_sw_seed_symmetric) {
random_get_random_number (randoms.random_ssgn); // randoms.random_ssgn old value in and new value out (ignoring return value)
} else if (use_random_type == use_xorshift32_symmetric) {
xorshift32 (randoms); // Updates randoms.random_ssgn
} else {
xassert (false); // One that's not symmetric
}
// Was < (UINT_MAX/2)) { which spelt out to < 0x7fffffff which should have been <=
if ((randoms.random_ssgn bitand INT_MIN) != 0) { // INT_MIN = 0x80000000, ie bit32 set for negative numbers in 2's complement
// Use positive value, but next time, use the negative value of it
randoms.use_random_negated = true; // Use as negative next time in next_symmetric_random_get_random_number
randoms.random_ssgn_prev = randoms.random_ssgn; // But after that, use this here
max_loop_pos_cnt++;
if (max_loop_pos_cnt > randoms.max_loop_pos_cnt) {
randoms.max_loop_pos_cnt = max_loop_pos_cnt;
} else {}
} else {
// Drop negative value
// If like "n" dropped here those calls have been "used up", but since each number
// is reached once, and only once, it will be balanced with "n" calls that
// will return positive values
max_loop_neg_cnt++;
if (max_loop_neg_cnt > randoms.max_loop_neg_cnt) {
randoms.max_loop_neg_cnt = max_loop_neg_cnt; // new max
if (max_loop_neg_cnt > randoms.max_loop_neg_cnt_ever) {
randoms.max_loop_neg_cnt_ever = max_loop_neg_cnt; // new max ever
} else {}
} else {}
xassert (randoms.max_loop_neg_cnt <= DROP_BIT_CNT_MAX);
}
}
}
} // next_symmetric_random_get_random_number
Other random generators
I continue, for I think this is difficult. I’ll try to set myself (and perhaps you) on (an other?) track.
But then, we also have the PRNG (Pseudorandom number generator) functions (Wikipedia). These are different from the CRC polynomials. CRC has the goal of detecting errors in datastreams («checksum», where nothing may internally be lost, kind of) while PRNG has the goal of generating chaotic, random numbers. I found the code below in a Claude dialogue while analysing this blog note (see below, it’s also on the Wikipedia page). I assume it’s to avoid using the rather hidden std::time::Duration library. This one is called Xorshift, and was invented by George Marsaglia in 2003 [9] (which uses this 88172645463325252 seed).
Observe that the shift operators << and >> are «shift out» and forgotten, not circular shifts with wraparound. This is used both for PRNG and CRC, but for CRC the value of the to-be-lost bits are used as triggers for the rest of the math. So these bits have significance also at this stage. And here I was, thinking that CRC (cyclic redundancy check) used circular shifts! And ^= are xor_eq:
#[inline]
fn xorshift64(state: &mut u64) -> u64 {
let mut x = *state;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
*state = x;
x
}
The mean of the 2^64 - 1 numbers generated by Xorshift64 is exactly 2^63. Since 0 never comes out of the generator, excluding it shifts the average of the remaining non-zero values up to precisely the halfway point of the 2^64 total states. (Easy said: sum of [1..99] is 4950. Divide it by 99 and the mean is 50. Almost hard to believe since 100 isn’t in!) Consequently, every single number from 1 to 2^64 - 1 will be seen exactly once before the sequence repeats. This works precisely because the XOR operation preserves information entropy – acting like a conservation law for data energy – meaning it never destroys information; it can never produce a 1 from only zeros, nor will a zero force subsequent values to become zero.
Observe that once we do a modulo division of a range that does not include 0, like [1..99], we will get zeros if the range is larger than the value! Like val % 10 is zero for 10, 20,..90, altogether 9 times, since the remainder after division with [1..9] * 10 are zero 9 times.
For this reasoning it doesn’t really matter whether our SW gets truly random or pseudo random or PRNG. Do «enough» of them and we’d get a good average for truly random. (I think this is in the curriculum of «statistical randomness»). Do the whole range and we’d get the 100% correct values for pseudo random. Do too few and we’re converging, but in a non-smooth way, for both types. Chose either way, but taking a thousand-pick should yield an ok enough average.
Average random of XC
So the theoretical value is 24.75s, but with sw seed I get somewhat lower and with hw seed somewhat higher average values. I get «around» the correct value 24.75s:
#if (USE_RANDOM_HW_SEED==0)
#define RANDOM_CREATE_GENERATOR(seed) random_create_generator_from_seed(seed) // Typical "DT 23.78s", "DT 23.95s"
#elif (USE_RANDOM_HW_SEED==1)
#define RANDOM_CREATE_GENERATOR(not_used) random_create_generator_from_hw_seed() // Typical "DT 26.46s", "DT 26.61s"
#else
#error
#endif
I have queried about two different series of values at xCore Exchange forum, point 3. It put me on track to the good reasoning. This is perfectly correct. See the above chapter.
Average random of Rust
The value I see in the logs of Rust (v0.0.900) basically looks like this like the below. 35s is way off!
REC 505 > SENT 495 (>602= 14 <384) SUM (REC 505 > SENT 495) CATCH 7 DT 35.42s REC 510 > SENT 490 (>558= 29 <413) SUM (REC 1015 > SENT 985) CATCH 7 DT 35.79s REC 515 > SENT 485 (>884= 33 <83) SUM (REC 1530 > SENT 1470) CATCH 5 DT 35.92s REC 475 < SENT 525 (>66= 7 <927) SUM (REC 2005 > SENT 1995) CATCH 1 DT 35.35s REC 489 < SENT 511 (>99= 25 <876) SUM (REC 2494 < SENT 2506) CATCH 1 DT 34.54s REC 504 > SENT 496 (>927= 41 <32) SUM (REC 2998 < SENT 3002) CATCH 4 DT 34.69s
Other timeout abstractions
This whole timeout business rings a bell for me. See 128:[Some timeout abstractions] (specifically [3] there) where Vannebo and I introduced ALTTIMER, EGGTIMER and REPTIMER in a run-time/scheduler (ChanSched) for an embedded processor. We implemented the standard select/ALT timeout and called it ALTTIMER. Then we introduced two timer types that survived other code running in select/ALT cases, ie. events other than timeout did not touch them. There could be events every ms, but EGGTIMER would only time out once after say 5 minutes. Then the REPTIMER would be repeated once it had timed out, like «every hour» with no skew.
Graham’s conjecture and symmetric randomness
There is perhaps thematic parallel between my use of «symmetric» random timeouts and Graham’s rearrangement conjecture, Wikipedia: Erdős–Graham problem, as recently proven for for all sufficiently large primes [10]. Ronald Graham’s puzzle and my «symmetric» random interleaving of task_slave and task_master messages both try to force some wanted behavior for some particular random outputs.
Ronald Graham’s puzzle was about shuffling a sequence so its partial sums never «crash» on the same beat (juggling). The architecture of the «knock-come» pattern guarantees deadlock freedom on its own. However, simply sending spontaneous messages from task_slave and task_master as fast as possible would probably not cause enough «randomness» when it came to maximizing catching a possible Tokio runtime implementation deadlock. It failed to detect any deadlock, but then, non-exhaustive testing won’t prove a thing. Important to say here is that any type of randomness would have sufficed for this use, not only my «symmetric» type. I just happened to get fixed on why I didn’t get an average of half the range, where the «symmetric» recipe solved that. Not important, but rather fun.
The Graham proof in [10], as far as I understand it, says that there exists a set of random «hours» with which to increase a wall clock that wraps around, that are such that after one clock advancement then the next clock advancement would not end up at the same hour. To find the set of these hours to add, if it did end at the same hour, they showed that a strategy existed to rectify it. So I think it’s about a set of random numbers plus a rectify-algorithm. (?)
This is where the alikeness with my «symmetric» sequence come in, for any even number of values (which would then give division by two an integer result) I use «negative» and «positive» her. This is because I treat the32 bits unsigned output from the pseudorandom generator as 32 bits signed since it’ s easier to explain. But then «medium is half of the range» becomes «medium is zero». For any positive value used, then the next to be used is the negative of it. For any negatives that might next appear they would all be thrown away (max 32 in a row for a 32 bits word (*)) until a positive appears. Then repeat. So, If I get a value I don’t want (a negative) I also have a recipe to use another one instead. The result is «no clumping». All the negatives thrown away (half of all values) will sooner or later appear as «new» negatives of the previous positive (also half the range). The positive range flips over to also inclide the negative. Observe that zero (0) never is a value from a pseudorandom generator, so we have to treat [1..100] instead of [0..99] so to say. Ie., higher average for the first. But for my timeouts in XC task_slave and task_master I decrease the values by 1, because I want zero or «immediately» to be a possible delay.
(*) See find_max_consecutive_allbits_xorshift32 in the XC GitHub code.
Knock-come and RK0
Antonio Giacomelli de Oliveira, the author of RK0 (204:[25]) has written an implementation of knock-come that runs under his RK0 («RK0 is a lean yet feature-rich, highly deterministic Real-Time Kernel for deeply embedded systems«). He asked me for some pattern to code, so that I could see how an RK0ish app is different from those built using mainstream kernels. So I proposed knock-come, even if I am aware that this pattern might not necessarily solve any problem in that context. We will come back with an explanation later, since I need to fully understand his implementation. He has let me publish it, see
- The code is at https://www.teigfam.net/oyvind/blog_notes/009/RK0/knockcome.c.
To get it colour coded open it in, like VS Code - The log is at https://www.teigfam.net/oyvind/blog_notes/009/RK0/knockcome_log.txt. The ##### comments have been added by me
Observe that the RK0 RK_CHANNEL, according to Antonio, works more like like a remote procedure call (RPC) type rendezvous or «CALL CHANNEL» than a «CSP channel». (However, RK0 doesn’t have multiprocessor support). The term «channel» has never been formalised. But in my «CSP world» I tend to think of them like the occam or xC chan (*) or golang chan, or maybe even Rust synch_channel (here). (*) Also for XMOS lib_xcore the chanend_t (here). So whenever «channel» is used in a programming context, we’d have to study what it means. Antonio’s RK0 code above certainly shows how RK_CHANNEL works. Also see Wikipedia’s Channel (programming).
Code in XMOS XCORE xC language
I have made a public repository of an implementation of the «knock-come» in XMOS xC. See https://github.com/Aclassifier/xc_test_knock_come. Forums added. GitHub takes care of colour coding.
This shows a scope output from version 0.0.916 09Jun2026:
Fig.3 – 09Jun2026 0.0.916 scope output
The purple curve shows spontaneous sendings from task_master to task_slave. There is a new edge on every sending. Since task_master is «master» it is allowed to send on the chan whenever it wants to. Whenever and as many times as it likes. Independently from this the slave must «knock». This is seen on the blue curve, one knock per edge. After that comes an invisible for the scope «come-data» transaction. The slave too: whenever and as many times as it likes. All initiatives are taken by the master and the slave independently, based on a pseudo random [0..9] µs timer value in each task.
Inside the 12.2 µs window we see two edges (one pulse) of purple. This means that the master has sent two spontaneous messages to the slave. The blue is low during that pulse. At the same time the slave has only done one «knock» and then «come-data». There are two others of the sort.
But we also see that the slave would do two «knock» and «come-data» while the master has not had any value to spontaneously send to the slave. We also see this several times, as a blue pulse inside a constant purple value.
There is no deadlock.
Another Promela example
I have an example of Promela code where two processes spontaneously send to each other over synchronous channels do not deadlock (like occam or XC would have done). See 135:[Promela channel some code]. (It is also on Wikipedia: Promela (Executability) – Aclassifier (me) put it there in 2009.)
Side comment on the use of AI
Aside: This was not my first computer programming AI exercise. I tested Claude in An encounter with AI-powered Cursor text editor and XC. But I think it was the first I hope lead to something.
Thanks to Google AI / Gemini for lowering the threshold for me, sitting alone as retired and not having many others to do pair programming with. When it was finished I asked if it had any idea of how extensive the AI chat had been. It assumed some 15-25 hours of intense work. The effective writing time in the chat had been 3-4 hours. (But I had sat some hours every day for about a week, and saved the AI logs). I have learned a lot!. It concluded:
«For a developer working completely on their own, picking up Rust from scratch, digging through async architecture documentation, and debugging microscopic rendezvous deadlocks against the Tokio scheduler, a project like this could easily have taken between 15 to 25 hours of intense work over several days.»
I’d say, much more! And I would have ended up asking on some forum or Stack Exchange about the subtle deadlock situations.
However…., read the paper «How AI Impacts Skill Formation» [6]:
«Participants who fully delegated coding tasks showed some productivity improvements, but at the cost of learning the library (*). We identify six distinct AI interaction patterns, three of which involve cognitive engagement and preserve learning outcomes even when participants receive AI assistance. Our findings suggest that AI-enhanced productivity is not a shortcut to competence and AI assistance should be carefully adopted into workflows to preserve skill formation — particularly in safety-critical domains.»
The library they used was the Python Trio library for asynchronous programming [7]. (Aside: which again reminds me of the now more than 10 years old 135:[PyCSP] library.)
My takeaway is that I must also study tokio, not just use a tiny part of it. It was obvious that Google AI had been trained on tokio itself, and its semantics. The problem for me though, is that the ratio between what I need to know and what I know is increasing. Despite AI.
Update: Now I have learnt that Google AI / Gemini I am also able to discuss not only Rust and Tokio, but also XC and the XMOS XCORE architecture.
But then, when a larger system is built, like my Beep-BRRR, I would presently not let AI handle it. I think/hope it’s too complex. I have now also learnt (Jul-Sep2026) that AI does as many errors as I do myself, but my own errors I assume/hope would much easier to detect by me/AI. (Bewildering on purpose. who isn’t these days.)
Original unmodified note
Intro and disclaimer
This note is based on a published paper [1]. At the time of publication (2005) I did not think that chapter 10 would describe any more than an interesting case of software engineering. To this date it stays so. However, people have asked me about this pattern. This note therefore describes nothing new, but will add some more discussion.
Disclaimers: 1.) Should anybody claim this pattern as already used, invented or even patented, prior to 2005 – good! It is not known to me (but now I do know that I am not alone, see bullet list below). Please mail me if this is the case – so that I may be able to honour it here – or obsolete – at least the suggested name. 2.) Even if the pattern is deadlock free, there may be errors in this note. 3.) Any usage of this pattern is out of my control and responsibility.
- In Jan.10 I discovered that the «USL Distributed Event Driven Protocol» seems to be similar. See [4].
- In Feb.10 I was made aware that the OpenComRTOS also uses a mechanism in the same street. See [5].
I have named the pattern «knock-come» for a rather obvious reason – the explicit behaviour it must display in order to function properly. The name does not fully describe the behaviour, but it should hold as a reminder.
Rationale
When two software threads or rather, processes, need to talk with each other at the same time, we would get a deadlock if they were communicating over synchronous, blocking channels. This note describes a simple software pattern that removes the possibility of deadlock. It also shows a formal model and verification of the algorithm, written in Promela and evaluated with Spin [2].
The original description, from [1] – of the «knock-come» pattern:
10. Deadlock avoidance
Where two processes spontaneously need to send data to each other, a blocking communication scheme might cause deadlock. This is a state where processes try to communicate – in a circular pattern – blocking for each other to become ready, and therefore unable to proceed. This is pathological and must not happen. All processes run at the same priority, so any priority inversion problem is ruled out in the system.
Fig.1a and 1b – From [1]
The pattern we chose to avoid this was to give the processes clear roles: slave and master. Master may send on the blocking channel any time (solid arrows) when it has something. Slave would never block on any spontaneous message, since the asynchronous “poll me” message (stippled arrow) lets the slave go on and not block, and then instead hang in an INPUT or ALT on the input channel. When the “OK, come on” message arrives from the master, the agreed upon protocol assures no deadly embrace.
Software architecture
Fig.2 – From [3]
We see two processes, the top and bottom P_.. processes. The left dotted lines, downwards are asynchronous non-blocking send channels. One one of them is of interest now. Let's call it the knock channel (Chan_202 in the figure). It carries no data.
The other arrows are one up-going come channel (Chan_201) and the down-going channel (Chan_200). Both are synchronous non buffered and blocking send and receive. Both carry data, together with a tag that describes the contents. They are drawn like a two-way channel, but they are two one-way channels. In addition to the come message, these channels are also used to send the actual data – in both directions.
Message sequence in words
Whenever the bottom process needs to send data, it may do it any time. It is the master.
Whenever the top process, the slave, needs to send data, it may send one only query («knock») any time. For the 1.) data up and the 2.) query – not to deadlock, the query is sent as a no data «interrupt» signal. The slave would send only once per session, so P1_Slave will always proceed (and not block) on this sending.
Whenever the bottom process decides that it has time to handle the query, it sooner or later sends the «ok, come on» up and immediately waits for the slave to respond to that message by sending the data down. Whenever the data has left slave, the sequence with the query may be repeated.
By sooner or later we mean that in the meantime the master may send any number of messages up. As we started with saying, the master may send any time.
The reason why the knock /query / interrupt channel has no data, is really that is simply that it does not need to have any data. Also, in real life, it is simple to implement an async channel with zero buffer.
Formal proof of deadlock freedom
The Promela model code below verifies to no «invalid end state», using spin / xspin. This means that it will not deadlock. Observe that with LEN set to zero it will deadlock. It has been modelled to resemble how the processes are coded with a standard synchronous methodology (language or library) – where only inputs may be ALT’ed over. (Note 010 above gives a very interesting deadlock free alternative.)
The code is my initial iteration on the theme:
Details
mtype =
{
M_KNOCK_DIRDOWN,
M_COME_DIRUP,
M_DATA_DIRUP,
M_DATA_DIRDOWN
};
#define LEN 1 /* Invalid end state (ie deadlock) if this is zero */
chan Chan_knock_down = [LEN] of {mtype}; /* Chan_202 */
chan Chan_data_down = [0] of {mtype}; /* Chan_200 */
chan Chan_data_up = [0] of {mtype}; /* Chan_201 */
proctype P1_Slave (chan Chan_knock_out, Chan_data_in, Chan_data_out)
{
bool Knock_send;
bool Knock_sent = false; /* necessary? */
Run:
if
:: Knock_send = true; /* non-deterministic setting to true.. */
:: Knock_send = false; /* ..or false */
fi;
if
:: (Knock_sent == false) && (Knock_send == true) ->
/* Am slave, but want to get rid of my data now */
Chan_knock_out ! M_KNOCK_DIRDOWN;
Knock_sent = true;
:: else -> skip;
fi;
if
:: Chan_data_in ? M_DATA_DIRUP -> skip;
/* Am slave, always able to receive from master */
:: Chan_data_in ? M_COME_DIRUP ->
/* Got "come" from master, do it */
Chan_data_out ! M_DATA_DIRDOWN;
Knock_sent = false;
fi;
goto Run;
};
proctype P2_Master (chan Chan_knock_in, Chan_data_in, Chan_data_out)
{
bool Knock_received = false;
bool Data_send;
Run:
if
:: Data_send = true; /* non-deterministic setting to true.. */
:: Data_send = false; /* ..or false */
fi;
if
:: (Data_send == true) ->
/* Is master, may always send */
Chan_data_out ! M_DATA_DIRUP;
:: (Knock_received == true) ->
/* Send "come" and get data, according to "contract" */
Knock_received = false;
Chan_data_out ! M_COME_DIRUP;
Chan_data_in ? M_DATA_DIRDOWN;
:: else -> skip;
fi;
if
:: Chan_knock_in ? M_KNOCK_DIRDOWN ->
/* Slave "knocks" */
Knock_received = true;
:: timeout -> skip;
/* global "else" to make "Chan_knock_in" input a poll */
fi;
goto Run;
};
init
{
atomic
{
run P1_Slave (Chan_knock_down, Chan_data_up, Chan_data_down);
run P2_Master (Chan_knock_down, Chan_data_down, Chan_data_up);
}
}
Daisy-chaining this pattern
This pattern scales. You may take a slave’s Chan_data_down and connect to another’s Chan_data_up, and let a new master have one more Chan_knock_down from each new slave. This daisy-chains with loop-back, equal slaves, which must then share via-traffic for the others. I have proven it deadlock free with a slightly modified Promela model.
Forums
Tokio GitHub forum
- «Knock-come» solving a problem but my tokio implementation seems to reintroduce it – started by me 22Jun2026. Long response from MentalOfCrow on 18Jul2026
xCore Exchange forum
Probably requires a user login:
-
- XC and the size of streaming chan buffer – started by me 26May2026
- C/C++ error messages in «Problems» window in VSCode XTC 15.3.1 – started by me 06Jun2026
- Different average random values when hw or sw seed and use of LFSR – started by me 24Jun2026 (A branch from this turned out to become an update of XMOS lib_random)
- XTC CMakeLists.txt and -save-temps – started by me 28Jul2026
References
[1] – [5] are original references
[1] From message queue to ready queue. Øyvind Teig, 2005. Subtitle: Case study of a small, dependable synchronous blocking channels API. «Ship & forget rather than send & forget». Ref chapter «10 – Deadlock avoidance». See https://www.teigfam.net/oyvind/pub/pub_details.html#Ercim05 and read at https://www.teigfam.net/oyvind/pub/ercim05_at_euromicro-2005/paper.pdf. In First ERCIM Workshop on Software-Intensive Dependable Embedded systems. Editors: Amund Skavhaug, Erwin Schoitsch. ISBN 2-912335-15-9, IEEE Computer press
[2] Promela and Spin. See https://spinroot.com/ and https://en.wikipedia.org/wiki/Promela
[3] No Blocking on Yesterday’s Embedded CSP Implementation. Øyvind Teig. Subtitle: The Rubber Band of Getting it Right and Simple. In Communicating Process Architectures 2006, Peter Welch, Jon Kerridge, and Fred Barnes (Eds.) IOS Press, 2006, pages 331-338, ISBN 1-58603-671-8. Read at https://www.teigfam.net/oyvind/pub/pub_details.html#NoBlocking
[4] «USL Distributed Event Driven Protocol«, described in Universal Systems Language: Lessons Learned from Apollo. Margaret H. Hamilton and William R. Hackler, Hamilton Technologies, Inc. In IEEE Computer, Dec. 2008 pp. 34-43
(«USL»). Also see my 007 – Synchronous and asynchronous, where this is discussed thoroughly.
[5] Comment [C.4] of 007 – Synchronous and asynchronous
[6] How AI Impacts Skill Formation, by Judy Hanwen Shen and Alex Tamkin, read at https://arxiv.org/abs/2601.20245 (2026)
[7] Trio: a friendly Python library for async concurrency and I/O. Read at https://trio.readthedocs.io/en/stable/. Especially see Synchronizing and communicating between tasks which has channels and even mentions fairness (which the world I come from is much concerned about, see fairness here). Nathaniel J. Smith seems to be the Trio BDFL
[8] The Tokio asynchronous runtime for the Rust programming language, see https://tokio.rs
[9] Xorshift RNGs by George Marsaglia, (2003). In Journal of Statistical Software, 8(14), 1–6. Read at https://www.jstatsoft.org/article/view/v008i14
[10] Mathematicians Harness Randomness To Crack a 55-Year-Old Conjecture by Halma Wegsman, in Quanta Magazine, 28Sep2026. Read at https://www.quantamagazine.org/mathematicians-harness-randomness-to-crack-a-55-year-old-conjecture-20260928/