Re: Concurrent MVars for Guile

[Mark H Weaver <mhw@netris.org>]

Hi,

Mateusz Kowalczyk <fuuzetsu@fuuzetsu.co.uk> writes:

> First of all, let's quickly outline something that Guilers might not be
> familiar with: MVars are based on an important property of the GHC's
> (GHC is the main Haskell compiler) thread scheduling mechanism, that is
> its fairness policy. GHC uses a round-robin scheduler which means that
> all threads will eventually get to run (although not with equal CPU
> slices). A book by Simon Marlow, the person who has for many many years
> been the main brain behind GHC's RTS says this:
>
> “No thread can be blocked indefinitely on an MVar unless another thread
> holds that MVar indefinitely”.[1]

"Concurrent Haskell" by Simon Peyton Jones, Andrew Gordon, and Sigbjorn
Finne, which introduced MVars, states in section 6.3 (Fairness):

   Assuming that no process holds the MVar indefinitely, it should not
   be possible for any of the competing processes to be denied access
   indefinitely.  One way to avoid such indefinite denial would be to
   specify a FIFO order for processes blocked on an MVar, but that is
   perhaps too strong.  [...]

Since our discussion on IRC, I've looked more closely at the
implementation of Guile's fat mutexes and condition variables, upon
which my MVars implementation is based.  I will not claim to have fully
audited the code for correctness, but both of them use FIFO wait queues.

Here's what experiment shows:

  scheme@(guile-user)> (use-modules (ice-9 mvars))
  scheme@(guile-user)> (define mv (new-empty-mvar))
  scheme@(guile-user)> (define producers
                         (map (lambda (i)
                                (usleep 200000)
                                (call-with-new-thread
                                  (lambda ()
                                    (let loop ()
                                      (put-mvar mv i)
                                      (loop)))))
                              (iota 10)))
  scheme@(guile-user)> (map (lambda (_) (take-mvar mv)) (iota 100))
  $1 = (0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8)

I confess that I do not yet understand why the first thread was able to
put the first two values into the MVar, and I intend to investigate
further.  Nonetheless, it's clear that the producers are being treated
fairly here.

What about competing consumers?

  scheme@(guile-user)> (use-modules (ice-9 mvars) (ice-9 threads))
  scheme@(guile-user)> (define mv (new-empty-mvar))
  scheme@(guile-user)> (define m (make-mutex))
  scheme@(guile-user)> (define consumers
                         (map (lambda (i)
                                (usleep 200000)
                                (call-with-new-thread
                                  (lambda ()
                                    (let loop ()
                                      (let ((x (take-mvar mv)))
                                        (with-mutex m
                                          (format #t "Thread ~a got ~s\n" i x))
                                        (loop))))))
                              (iota 10)))
  scheme@(guile-user)> (for-each (lambda (x) (put-mvar mv x)) (iota 30))
  Thread 0 got 0
  Thread 1 got 1
  Thread 2 got 2
  Thread 3 got 3
  Thread 4 got 4
  Thread 5 got 5
  Thread 6 got 6
  Thread 7 got 7
  Thread 8 got 8
  Thread 9 got 9
  Thread 0 got 10
  Thread 1 got 11
  Thread 2 got 12
  Thread 3 got 13
  Thread 4 got 14
  Thread 5 got 15
  Thread 6 got 16
  Thread 7 got 17
  Thread 8 got 18
  Thread 9 got 19
  Thread 0 got 20
  Thread 1 got 21
  Thread 2 got 22
  Thread 3 got 23
  Thread 4 got 24
  Thread 5 got 25
  Thread 6 got 26
  Thread 7 got 27
  Thread 8 got 28
  Thread 9 got 29
  scheme@(guile-user)> 

> Further down we find out the consequences of this guarantee: “A
> consequence of the fairness implementation is that, when multiple
> threads are blocked in takeMVar and another thread does a putMVar, only
> one of the blocked threads becomes unblocked”.

And indeed, this is the case in this implementation of MVars.  Similarly
when multiple threads are blocked in put-mvar and another thread does a
take-mvar.

My MVars implementation is based on Guile condition variables.  Each
MVar has two condition variables: one that gets signaled when the MVar
becomes full, and another that gets signaled when it becomes empty.
Threads waiting for an MVar wait on the appropriate condition variable
in the MVar.  Each Guile condition variables contains a FIFO queue of
threads waiting for it.  When a condition variable is signaled, one
thread is popped from this queue and woken up.

> What's Guile's scheduling policy? Can we get a single wakeup and this
> kind of fairness guarantee?
>
> Unfortunately, Mark was not able to tell me what's the case. If this is
> to make it into core language as Mark suggests, I think it's important
> that it's first confirmed that the foundation on which MVars are built
> upon is actually present in Guile. I'm posting on this list in an
> attempt to find the person who knows how Guile's scheduler works and can
> answer my questions.

Guile threads are pthreads, so Guile does not implement its own
scheduler.  However, the mutexes and condition variables exposed to
Scheme (and used in this MVars implementation) implement their own FIFO
wait queues.

> Of course tests can be written and it can be eyed whether or not the
> behaviour seems similar but I think a definitive ‘yes, we do this’ or
> ‘no, we don't do this’ is still necessary.

Well, again, I haven't done a full audit of the threads code in Guile,
so I can't provide the definitive statement that you think is necessary.

However, looking over the code, I think it's reasonably clear that there
is a FIFO policy for waiting threads, and I think the experiments above
provide reasonable confirmation of that (modulo the strange case of two
zeroes in a row at the beginning).

I will leave it to others to decide whether this is sufficient.

     Mark