> > PS. As for tryTakeMVar or locks on MVars, what is wrong
> > with using MMVar a = (MVar (MayBe a)) and a suitable
> > access protocol?
> >
> > MVar empty --> MMVar is locked
> > MVar Nothing --> MMVar is empty, not locked
> > MVar (Just v) --> MMVar holds value v, not locked
>
> That it's impossible to implement the equivalent of takeMVar
> (block until it is full).
In the simple design I had in mind, it would indeed be the writer that
chooses whether reading is blocking or not. In addition, you want the
reader to be able to choose (if the writer permits).
Let's see: for the reader to have a choice, the writer has to operate
the channel in two modes (for blocking and for non-blocking reading),
so a naive modification would be:
MVar (Bool,MVar a)
with states:
MVar empty
MVar (False,MVar empty)
MVar (True,Mvar v)
Hmm, almost. The problem is that the first reader to block on the
inner MVar is likely to get the data, even if a non-blocking reader just
happens to be looking at the True flag..
So we need to be slightly more systematic: readers now come in two
variants, depending on which operation they use to access the channel.
We don't want blocking readers (brs) to be presented with no input when
they wake up, right? And we cannot enter non-blocking readers (nbrs) into
the waiting list because they are not prepared to wait. Then an nbr could
temporarily occupy the front of the queue (and leave it immediately either
with an item of data or knowing that there is nothing on offer) or we have
to make sure that, as long as a br blocks on the channel, no nbr can beat
it to the data. Again, there are some options here: nbrs could observe
empty/full, but not the data items themselves; nbrs could have access to
a copy of the last item that has been written to the blocking channel.
In any case, there is an interaction between nbrs and the queue of brs,
so we need to know whether the queue is empty or not. For such cases,
the CH paper suggests (in 4, control over scheduling) to maintain a list
of blocked processes.
Here is one option for our problem, giving brs priority over nbrs: brs don't
all block on one MVar, but create a private MVar each to block on and
add their private MVars to a queue. Our channel type is modified to:
MVar (Either (MayBe a) [MVar a])
with states:
MVar empty
MVar (Left Nothing)
MVar (Left (Just v))
MVar (Right queue) -- not.null queue
The writer checks whether any brs are queued, and if so, passes the
item to the first br in the queue (replacing the Right-tagged queue with
a Left-tagged Nothing, if the queue becomes empty). If not, it announces
the item as free for all (Left (Just v)). This part is similar to the
quantity
semaphores example.
nbrs operate on Left-tagged information, Right-tagged information is
none of their business (they could return with Nothing, as there is no data
for them to collect before the queue gets empty again). If there is a
Left-tagged item, they can take it or make a copy.
brs operate on both tags, either consuming a Left-tagged item or
adding their private MVar to a new or existing Right-tagged queue.
I don't see how to give nbrs priority over brs. Using a pair type instead
of Either, the writer could temporarily put each item into the free for all
section, then check back to give it to the next br if it hasn't been taken,
but this doesn't feel right..
Perhaps tryTakeMVar should not be required to return immediately,
but be given a timeout parameter instead. That might simplify the
implementation.
What have I missed this time?
Claus
