Zero-length queues (a.k.a. rendezvous queues)

Kernel
1

Dear all,

I’m facing the following problem in my design: I want to send data from task A to task B, but only if the receiving task B is already waiting for the data. Using a FreeRTOS queue does not work for this use-case because they have require a length greater than zero, meaning 1 data element would be buffered (which I do not want, for reasons of memory usage and latency).

A solution would be if queues were to allow for their maximum number of elements to be zero. A zero-length queue does not buffer any elements, but only transfers data when a send and receive call pair up. This is sometimes referred to as a “rendezvous queue”. Rust’s crossbeam-channel implementation describes this as follows:

A special case is zero-capacity channel, which cannot hold any messages. Instead, send and receive operations must appear at the same time in order to pair up and pass the message over.

In my problem, the receiving task would loop with a blocking call to xQueueReceive(queue, buffer, portMAX_DELAY); when it is done processing the previous data item, the producer A uses xQueueSend(queue, buffer, 0);, that is, non-blocking. This means some data items are not transferred from A to be, which is fine in my use-case.

How are others solving a problem like this? Am I missing something? The work-around we currently use is a queue of length one and before sending something to it the sending task “drains” the queue by calling xQueueReceive(queue, buffer, 0) in a loop till the queue is empty. Then it sends the new image, the receiving task can simply do a blocking receive from the queue. This works, but is somewhat ugly and still consumes twice as much memory as would be needed with a rendezvous queue (at every point in time there are two images im RAM, whereas an optimal solution using a rendezvous queue would require just a single one that the receiver is currently processing).

I already posted a feature suggestion on the GitHub issue tracker (#1323 - sorry, cannot put a link here due to forum policies), where it was suggested to ask here as well.

Best, Michael

2

So you want to send something via a queue only if the receiver is blocked waiting on it ?
One approach could be to use eTaskGetState by sending task to check if the receiving task is blocked on the queue (or sth. else) to send the data or skip it. If I got you right and if it would really match your use case, of course.

3

I would solve that by not using a queue at all, but just a semaphore and a flag. The receiving task sets the flag, and then blocks on the semaphore.

The sending task (I am assuming only one) checks the flag, and if set, clears it and then copies the data itself into the receiving buffer. The flag could be a pointer to the buffer it the sender wouldn’t have access to its address otherwise (which it copies and then nulls).

If multiple tasks might be able to send, replace the flag with another semaphore, that the sender tasks with a 0 timeout to see if it is ready, and then copying the data if it got the semaphore.

(Edit addition)

One other point is that to build your zero length queue would need totally special case code for it as the existing code it totally based on there being a space in the queue to hold the data, for the sending task to copy to, and the receiving task to copy from, and thus does have the memory cost and latency cost you want to avoid. Thus, it needs to be a special case structure anyway.

4

you are misunderstanding the concept of a zero-buffer. it is LOGICALLY zero size. it means no message will be deposited and forgotten, a fully synchronous message exchange.

the send semantics - it WAITS for a confirmation from the receiver.

you do that by creating a 1-item queue
the method for receiving:

  • always blocks if queue is empty
  • signal an ACK, can be a binary semaphore or task notify

the sender:

  • always block if queue is full
  • after successful send, WAIT for an ACK from the receiver

that is how the channel is LOGICALLY zero

the simplest is an 1 item queue plus a binary semaphore.

5

@rko, Which isn’t the structure that the OP (Michael-p) was describing, and is almost the opposite. He wants messages that can’t be immediately delivered to be discarded.

6

@richard-damon
My bad, I only read the rendezvous/zero-buffer. It is definitely not a rendezvous.
Send/recv are not pairing up. Why does the receiver not simply signal a ‘req’, and then wait for the sender?

7

He does pair the send to the receive by just not sending if the receiver isn’t ready yet. He said “Lost” data wasn’t a problem, just that he wanted data sent without delay.

My solution basically is your signal / wait using a flag variable to signal and waiting on a semaphore for data to be sent.

8

My point is that the concept of a zero-buffer channel does not apply in this case. A zero buffer channel is fully synchronous; the sender blocks twice: on a full queue and waiting for an acknowledgement. That is the backbone for remote procedure calls, where the ‘ack’ can be the answer for a client request.

9

A FreeRTOS queue by definition does a value copy. If you only want a single copy of your data in RAM, why don’t you pass a pointer to it in the queue’s payload?

Also, I agree with @rk0 that the title of the thread is somewhat unfortunate. It implies that rendevous queues and zero length queues would be the same thing. I do not think they necessarily are.

10

Thanks everybody for the suggestions, I’ll definitively try out a few of these.

However, I still believe zero-size queues would be a good addition to kernel, as this seems to be a somewhat common use-case, and all the solutions discussed so far are pretty much work-arounds. After all, conceptually this is about passing ownership of some item from a task to another task, which is a queue. Obviously the burden of implementation would then be on the FreeRTOS maintainers, but at least it does not increase the API surface and prevents users from re-inventing the wheel all the time.

Also, I agree with @rk0 that the title of the thread is somewhat unfortunate. It implies that rendevous queues and zero length queues would be the same thing. I do not think they necessarily are.

Zero-size queues/channels are included in the standard libraries of many modern programming languages (with the semantics I described), and are often referred to as “rendezvous channels” in that context, e.g. in Rust (“[…] Note that a bound of 0 is allowed, causing the channel to become a “rendezvous” channel where each sender atomically hands off a message to a receiver.”) or Kotlin (“[…] Unbuffered channels transfer elements when sender and receiver meet each other (aka rendezvous) […]”).

11

Edit: I found this useful AI generated summary of a rendezvous queue’s semantics:

If the sender attempts to send a message and no receiver is waiting, the sender will block. Similarly, if a receiver tries to get a message and none is available, it will wait for a sender to send one.

As mentioned by @rko, these semantics roughly correspond to the “implied ACK” of a synchronous RPC call and can be emulated by nested queues. However, you write that you “do not care if messages are lost,” which is a deviation of the strict coupling of sender and receiver and thus not included in a rendezvous queue. So what feature do you exactly ask to be included? A full fledged rendezvous queue or a “drop box” queue in which the sender never blocks but receives a notification whether the message was accepted? Isn’t the second case covered by FreeRTOS’ xQueueSend(<timeout 0>) as you say you are already implementing as a workaround?

A pseudo code implementation sketch of the first strategy (essentially reiterating elaborations from @rko) is this:

send:

  • create a queue object xAckQueue and pass its handle along with the payload to the receiver using xQueueSend(xOuterQueue)
  • blocking xQueueReceive on xAckQueue
  • delete xAckQueue

receive:

  • blocking wait on xOuterQueue
  • upon success, decode payload and xAckQueue
  • submit an xQueueSend(xAckQueue) call
    • process payload.

What would be missing in this implementation for a full rendezvous queue?

As a side note, may I suggest that you refrain from adding derogatory commands about the forum administration (in particular in the very first post). One may not like it, but there are doubtlessly good reasons for a restriction for newcomers, and if you did follow the forum, you would know that the uploading privilege is normally granted within 24 hours as soon as it becomes clear that you are not a spammer. Thanks!

12

Exactly, there is no such thing as rendezvous message-passing that the sender does not ever block. Synchronous/asynchronous message-passing is somewhat blurry to define, but it often falls to the send semantics.
Going further and a bit pedantically, if the sender blocks on a full queue and the receiver blocks on an empty queue, and this queue is a one-item queue, we already have a rendezvous*.

When the sender also blocks waiting for acknowledgement from the receiver, this is the typical zero-buffer scenario, because a successful send implies a successful receive, and is often regarded as an ‘extended rendezvous’. It means the sender will not just deposit the message on the buffer and proceed; it blocks waiting for the ack, so _logically_ there is no buffering.

* For queues that are more than 1-item, the concept is blurry, but if running at different rates, eventually they will sync to the lowest rate.

13

I have numerous times wanted a feature like this, and every time had to implement it with either some synchronization primitives like you suggest, or sometimes with several synchronization primitives on top of a 1-size queue. And every time, I paid with a little bit of additional complexity, testing, and risk of introducing subtle bugs to achieve this rendezvous behavior.

So even if this is a special case within the kernel implementation, I find that the semantics of a 0-size queue would fit into the current API, and the behavior would also be easily explained from a user perspective. I don’t know how complex this would be to implement, but I know I would have benefited several times from simpler and more robust application code.
And it would be something Zephyr doesn’t have :blush:

14

I would ask you to try to justify why this particular application is so common that it would be worth making every other application a bit bigger and slower. As I mentioned, it would need to be a totally new code path inside the queue code, and thus adding cost to all other users.

Another question to you, since you said you had to do this several times, why didn’t you implement it as a “private library” so you only needed to have done it once, and reused it?

16

I would ask you to try to justify why this particular application is so common…

It is of course difficult to quantify how common of a use-case this is out in the wild. But I think @michael-p makes a compelling case pointing to that it is common enough for both Rust and Kotlin to provide such a concept for inter thread/task message handover.

that it would be worth making every other application a bit bigger and slower.

If the realization in FreeRTOS would require largely a separate code-path, then it is probably also feasible to hide it under a configENABLE_ZERO_ELEMENT_QUEUES or similar?

why didn’t you implement it as a “private library”

I have, but there are still reasons why that might not be as portable as I would like. Different companies for one.

17

it turns out I was reading this paper from (2008) about IPC treats (Minix authors)
look how they classify the send and receive message passing:

The most basic primitives are the synchronous, blocking SEND and RECEIVE. The SENDREC primitive combines these primitives in a single call, doing a synchronous send following by an implicit receive. No buffering is required as the caller is automatically blocked until the message has been copied from the sender to the receiver. The remaining IPC primitives are nonblocking. NBSEND is a nonblocking variant of the synchronous SEND call that returns an error if the other party is not ready at the time of the call.

The NBSEND is what the OP wants, and again, it is not a zero-buffer. I never heard about this one before (except the trivial case, if the buffer is full, producer simply returns, as it is non-blocking). However, a buffer being empty does not imply that the sender is blocked waiting for the message.

18

I will point out that “IPC” isn’t a concept typically discussed with Real-Time systems, but is a topic for larger systems where. memory isolation and its costs, are more prevalent.

Yes, there may be cases where it is useful in a real-time system, but its operation is different enough that using a different API would be reasonable, and quite creatable in “user” code in a library, though using the structures from list.h might make things more efficient (but there is nothing preventing user libraries from using it).

19

No, it is not. The fact is that two concurrent units still communicate (processes or threads), blocking or not, still applies. If it is two threads or two processes, it does not matter from this perspective. If all memory is shared, the queue/message-passing mechanism will provide a way to coordinate this exchange, not because the tasks are not allowed to (as when making a system call and asking for the kernel to pass the message), but for convenience.

20

The issue is that when thinking in the “real-time” domain, the formalism of “IPC” (as opposed to just thinking of synchronism) isn’t normally adopted, as too often the concepts work to opposite goals. Real-Time is about being able to assure meeting deadlines, and avoiding race conditions. “Convenience” isn’t the major concern unless it is in support of that goal.

21

Race conditions are a problem whenever we speak about multitasking. Meeting real-time is one of the reasons we often use shared memory and do not isolate user space from kernel space (even when the MCU has some level of isolation). Using a queue to copy messages when we have shared memory at our disposal is convenience in the sense it organises the message exchange, giving semantics to the operation. The convenience here is exchanging data and synchronising, altogether.