From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Re: Concurrent MVars for Guile Date: Fri, 17 Jan 2014 14:31:29 -0500 Message-ID: <878uuequb2.fsf@netris.org> References: <87fvtn1wv8.fsf@tines.lan> <52D8CEC6.9080800@fuuzetsu.co.uk> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1389987263 6695 80.91.229.3 (17 Jan 2014 19:34:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 17 Jan 2014 19:34:23 +0000 (UTC) Cc: guile-devel@gnu.org To: Mateusz Kowalczyk Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Jan 17 20:34:28 2014 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1W4FBT-00023L-01 for guile-devel@m.gmane.org; Fri, 17 Jan 2014 20:34:27 +0100 Original-Received: from localhost ([::1]:39797 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4FBS-0001IY-LJ for guile-devel@m.gmane.org; Fri, 17 Jan 2014 14:34:26 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:55312) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4FBJ-0001GS-D7 for guile-devel@gnu.org; Fri, 17 Jan 2014 14:34:23 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1W4FBD-0006x4-D1 for guile-devel@gnu.org; Fri, 17 Jan 2014 14:34:17 -0500 Original-Received: from world.peace.net ([96.39.62.75]:52656) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4FBD-0006vS-8P for guile-devel@gnu.org; Fri, 17 Jan 2014 14:34:11 -0500 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=yeeloong) by world.peace.net with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1W4FAs-0003Gb-Nb; Fri, 17 Jan 2014 14:33:51 -0500 In-Reply-To: <52D8CEC6.9080800@fuuzetsu.co.uk> (Mateusz Kowalczyk's message of "Fri, 17 Jan 2014 06:33:42 +0000") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 96.39.62.75 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16812 Archived-At: Hi, Mateusz Kowalczyk 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: > > =E2=80=9CNo thread can be blocked indefinitely on an MVar unless another = thread > holds that MVar indefinitely=E2=80=9D.[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 =3D (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)>=20 > Further down we find out the consequences of this guarantee: =E2=80=9CA > 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=E2=80=9D. 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 =E2=80=98yes, we do this= =E2=80=99 or > =E2=80=98no, we don't do this=E2=80=99 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