> Has anyone ever seen a shared circular queue used in multi-tasking?
Yes. I work on a vendor product that uses a circular queue where
multiple address spaces are adding to the queue and another address
space reads from the queue.
There is a 'next free slot' index in the header.
There is a 'next to be processed' index in the header.
The logic that adds the queue element checks the 'next to be processed'
so it does not overrun the tasks that are adding to the queue.
All queue elements are cleared by the reader processor. The last item
updated in the queue element when it is being built is an ecb field.
The reader reads until the 'next to be processed' matches the 'next free
slot'. It always checks and maybe waits for the ecb in the item slot
before it reads the slot.
There is special logic during the add process to handle a "queue full"
condition. (And, yes, I have seen it triggered.)
The vendor product has worked fine on p390s and later.
Tony Thigpen
Jon Perryman wrote on 8/1/19 12:30 AM:
Repeating what I said earlier, use a chained queue because this circular
queue will only work in 1 specific situation and chains are easy to implement
and maintain.
Everyone seems to think CS is the hard part. The important clue is
multi-tasking (assumed because of CS instruction). Multi-tasking is considered
a random pattern. Using this circular queue cannot be random (e.g. 1 must be
freed before 2).
Has anyone ever seen a shared circular queue used in multi-tasking? It's not in
any of the products I've worked on. It simply does not make sense to use for a
multi-task queue.
Is it better to test/reset this Index number before or after adding the last
entry in the queue?
Should there be a second Compare and Swap?
Resetting the index before or after depends upon Paul's choice of
implementation. Considering a second CS probably means there is a timing issue
that is not mentioned.
It's not the simple case of a sender task and receiver task because that does
not need CS, CSD, PLO or any other type of serialization.
It's not where tasks get an entry, use it then free it because the free would
be considered random (e.g. 7 freed before 6 is freed thus causing a logic
problem).
It's not where various tasks are building data in different buffers and then
sending to a processing task because the receiving task would need to wait for
the next in sequence.
Forcing wait's does not make sense because the logic could get complicated.
I'm curious about why a circular queue was chosen instead of chained queue
(most common implementation).
Jon.
On Tuesday, July 30, 2019, 11:55:15 AM PDT, Peter Relson
<[email protected]> wrote:
Perhaps I am missing something, but I don't see discussion of how an
element is freed and how that interacts with the "index".
This might be thought not to be a "queue" in that elements are not linked
together, but that is OK since the definition of a queue does not require
that, only that access be first in first out.
Your starting point: the "memory chunk" contains n entries, each
(supposedly) associated with an "index" (0 to n-1).
I don't know just when the "index" is incremented, and it is not clear
what "appends" means within "it always appends to the next entry by
incrementing the ordinal number using compare and swap"
means.
Perhaps elements are never freed but it is safe to reuse them?
Without seeing the exact protocol you are proposing, it is unlikely that
one could answer your question with confidence.
It might be necessary to use a lock or ENQ, it might be OK to use
transactional execution, it might be OK to use CDS (if this is a true
"free queue" then CDS logic with a sequence number is usually needed), it
might be OK to use CS.
If elements can be freed at random times, it won't be the case that a free
element is locatable based on the value of the "index".
Peter Relson
z/OS Core Technology Design
