From: Matthew D Swank
Subject: OT:Lock based concurrency
Date: 
Message-ID: <PakRk.1428$vD2.645@newsfe01.iad>
Concurrency Models tend to excite the passions.  STM's are all the rage 
these days, but recently the systems guys gave a one-two punch against 
STM: 

http://portal.acm.org/citation.cfm?id=1400228 
(STM's are toys)

and 

http://portal.acm.org/citation.cfm?id=1454462 
(We've been writing composable, lock based systems for years-- they're 
called operating systems!)

I'm a bit agnostic, but I also haven't done much traditional lock based 
work (usually just enough to implement a channel, then back to CSP or 
actors).

Can anyone recommend could resources on the classics (mutexes, 
semaphores, monitors, etc)

Also, do I only have to worry about the memory-model/instruction-
reordering when using lock free primitives?

Thanks,

Matt
-- 
Go to a movie tonight.  Darkness becomes you.
From: Paul Tarvydas
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <gf4m8u$92t$1@aioe.org>
Matthew D Swank wrote:

> Can anyone recommend could resources on the classics (mutexes, 
> semaphores, monitors, etc)

Ric Holt's books (unbreak the lines):

http://www.amazon.com/Concurrent-Euclid-Addison-Wesley-computer-science/dp/0201106949/ref=sr_1_9?ie=UTF8&s=books&qid=1226169111&sr=8-9

http://www.amazon.com/Structured-Concurrent-Programming-Applications-Addison-Wesley/dp/0201029375/ref=sr_1_13?ie=UTF8&s=books&qid=1226169111&sr=8-13

pt
From: Matthew D Swank
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <2bqRk.543$2l5.78@newsfe01.iad>
On Sat, 08 Nov 2008 13:37:19 -0500, Paul Tarvydas wrote:

> Matthew D Swank wrote:
> 
>> Can anyone recommend could resources on the classics (mutexes,
>> semaphores, monitors, etc)
> 
> Ric Holt's books (unbreak the lines):
> 
> http://www.amazon.com/Concurrent-Euclid-Addison-Wesley-computer-science/
dp/0201106949/ref=sr_1_9?ie=UTF8&s=books&qid=1226169111&sr=8-9
> 
> http://www.amazon.com/Structured-Concurrent-Programming-Applications-
Addison-Wesley/dp/0201029375/ref=sr_1_13?
ie=UTF8&s=books&qid=1226169111&sr=8-13
> 
> pt

Thanks, I like cheap and used!

The first one, I assume, covers monitors and condition variables since 
that's how Concurrent Euclid does synchronization.  Does the second title 
cover more primitive, well primitives?

Matt

-- 
After your lover has gone you will still have PEANUT BUTTER!
From: Brian Adkins
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <m2zlk8d98r.fsf@gmail.com>
Matthew D Swank <··················@gmail.com> writes:

> Concurrency Models tend to excite the passions.  STM's are all the rage 
> these days, but recently the systems guys gave a one-two punch against 
> STM: 
>
> http://portal.acm.org/citation.cfm?id=1400228 
> (STM's are toys)
>
> and 
>
> http://portal.acm.org/citation.cfm?id=1454462 
> (We've been writing composable, lock based systems for years-- they're 
> called operating systems!)

Interesting. I'm curious about what the Clojure folks would say given
the fact that they seem pleased with their STM.
From: Matthew D Swank
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <fOJRk.968$M5.340@newsfe01.iad>
On Sun, 09 Nov 2008 13:50:28 -0500, Brian Adkins wrote:

> Matthew D Swank <··················@gmail.com> writes:
> 
>> Concurrency Models tend to excite the passions.  STM's are all the rage
>> these days, but recently the systems guys gave a one-two punch against
>> STM:
>>
...
> 
> Interesting. I'm curious about what the Clojure folks would say given
> the fact that they seem pleased with their STM.


Well Clojure's real stab at maintainable concurrency is default 
immutablity. The STM is meant to make correct, concurrent sharing 
easier.  If you have to share, transactions should be more maintainable.

I think the systems guys are skeptical that STMs can be efficient, and 
that the semantics of transactions are unnecessarily complicated for the 
problems they purport to solve.

I can't judge either way.  I do think it is interesting that the 
assumption of the second article, "Real-world Concurrency", is that the 
goal of concurrency is performance.  This seems to be a (understandably I 
suppose) low-level point of view.  However, some problem domains 
encourage decomposition into concurrent computation units regardless of 
the availability parallel execution.


Matt

-- 
You will overcome the attacks of jealous associates.
From: Pascal Costanza
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <6npgkkF4e8tU1@mid.individual.net>
Matthew D Swank wrote:
> On Sun, 09 Nov 2008 13:50:28 -0500, Brian Adkins wrote:
> 
>> Matthew D Swank <··················@gmail.com> writes:
>>
>>> Concurrency Models tend to excite the passions.  STM's are all the rage
>>> these days, but recently the systems guys gave a one-two punch against
>>> STM:
>>>
> ...
>> Interesting. I'm curious about what the Clojure folks would say given
>> the fact that they seem pleased with their STM.
> 
> 
> Well Clojure's real stab at maintainable concurrency is default 
> immutablity. The STM is meant to make correct, concurrent sharing 
> easier.  If you have to share, transactions should be more maintainable.
> 
> I think the systems guys are skeptical that STMs can be efficient, and 
> that the semantics of transactions are unnecessarily complicated for the 
> problems they purport to solve.

I think it's too early to tell one way or the other. We may just be at a 
stage as with garbage collection a couple of decades ago, when it was 
deemed to be too expensive. Over time, better garbage collection 
algorithms were found, and now it's common place.

The same could be true for STM in the long run. I think STM is very 
promising...


Pascal

-- 
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Jon Harrop
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <KcSdnReuvvNx9IXUnZ2dnUVZ8vWdnZ2d@posted.plusnet>
Matthew D Swank wrote:
> I can't judge either way.  I do think it is interesting that the
> assumption of the second article, "Real-world Concurrency", is that the
> goal of concurrency is performance.  This seems to be a (understandably I
> suppose) low-level point of view.  However, some problem domains
> encourage decomposition into concurrent computation units regardless of
> the availability parallel execution.

Improved latency is usually the motivation (even without parallelism, of
course). I'd put that under the performance bracket.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
From: Jon Harrop
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <t62dnfDU_eF-sYrUnZ2dnUVZ8tHinZ2d@posted.plusnet>
Matthew D Swank wrote:
> Concurrency Models tend to excite the passions.  STM's are all the rage
> these days, but recently the systems guys gave a one-two punch against
> STM:
> 
> http://portal.acm.org/citation.cfm?id=1400228
> (STM's are toys)
> 
> and
> 
> http://portal.acm.org/citation.cfm?id=1454462
> (We've been writing composable, lock based systems for years-- they're
> called operating systems!)

AFAICT, STM addresses a very specific problem that I have never personally
encountered outside academic examples from the Haskell community.

> I'm a bit agnostic, but I also haven't done much traditional lock based
> work (usually just enough to implement a channel, then back to CSP or
> actors).
> 
> Can anyone recommend could resources on the classics (mutexes,
> semaphores, monitors, etc)

I found this free Albahari e-book good:

  http://www.albahari.com/threading/

> Also, do I only have to worry about the memory-model/instruction-
> reordering when using lock free primitives?

No, a lock implies fences so you just use a lock and you're fine.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
From: Lars Rune Nøstdal
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <1226258303.9407.19.camel@blackbox.nostdal.org>
On Sat, 2008-11-08 at 17:41 +0000, Matthew D Swank wrote:
> 
> Can anyone recommend could resources on the classics (mutexes, 
> semaphores, monitors, etc)

I think any generic tutorial (wikipedia, even) out there about these
concepts will do in combination with whatever your Lisp-implementation
provides.

For SBCL:

  http://www.sbcl.org/manual/Threading.html


Timers and dealing with timeout etc. sometimes show up when doing
threading:

  http://www.sbcl.org/manual/Timers.html


..and (describe 'sb-ext:with-timeout).


Playing with threads:


        (defmacro with-thread ((name &rest forward-dynamic-bindings) &body body)
          "Defines a thread that executes `body'. Returns the thread-instance."
          (if (null forward-dynamic-bindings)
              `(sb-thread:make-thread (lambda () ,@body) :name ,name)
              (let ((temp-names (loop :repeat (length forward-dynamic-bindings) :collect (gensym))))
                `(let (,@(mapcar (lambda (x y)
                                   (list x y))
                                 temp-names
                                 forward-dynamic-bindings))
                   (make-thread (lambda ()
                                  (let (,@(mapcar (lambda (x y)
                                                    (list x y))
                                                  forward-dynamic-bindings
                                                  temp-names))
                                    ,@body))
                                :name ,name)))))
        
        
        (defmacro while (pred &body body)
          `(loop :while ,pred :do ,@body))
        
        
        
        (let ((quit-p nil)
              (thread-a nil)
              (thread-b nil))
        
          (defun start ()
            (setf quit-p nil)
            (let ((shared-data nil)
                  (shared-data-mutex (sb-thread:make-mutex)))
              
              ;; Set `thread-a' and `thread-b' to "contain" our threads.
              (setf thread-a
                    (with-thread ("thread-a")
                      (while (not quit-p)
                        (sleep (random 4))
                        (sb-thread:with-mutex (shared-data-mutex)
                          (let ((new-value (random 10)))
                            (format t "~A <--(push ~A)-- ~A~%"
                                    (push new-value shared-data)
                                    new-value
                                    (nthcdr 1 shared-data))
                            (finish-output)))))
                            
                    thread-b
                    (with-thread ("thread-b")
                      (while (not quit-p)
                        (sleep (random 4))
                        (sb-thread:with-mutex (shared-data-mutex)
                          (format t "~A <--(pop)-- ~A~%"
                                  (nthcdr 1 shared-data)
                                  shared-data)
                          (pop shared-data)
                          (finish-output)))))))
        
        
          (defun stop ()
            (setf quit-p t)
            (sb-thread:join-thread thread-a)
            (sb-thread:join-thread thread-b)))
        
        
        
        CL-USER> (start)
        #<SB-THREAD:THREAD "thread-b" RUNNING {AC92C19}>
        (5) <--(push 5)-- NIL
        (2 5) <--(push 2)-- (5)
        (0 2 5) <--(push 0)-- (2 5)
        (8 0 2 5) <--(push 8)-- (0 2 5)
        (9 8 0 2 5) <--(push 9)-- (8 0 2 5)
        (5 9 8 0 2 5) <--(push 5)-- (9 8 0 2 5)
        (9 8 0 2 5) <--(pop)-- (5 9 8 0 2 5)
        (8 0 2 5) <--(pop)-- (9 8 0 2 5)
        (0 2 5) <--(pop)-- (8 0 2 5)
        (3 0 2 5) <--(push 3)-- (0 2 5)
        (8 3 0 2 5) <--(push 8)-- (3 0 2 5)
        (3 8 3 0 2 5) <--(push 3)-- (8 3 0 2 5)
        (9 3 8 3 0 2 5) <--(push 9)-- (3 8 3 0 2 5)
        (3 8 3 0 2 5) <--(pop)-- (9 3 8 3 0 2 5)
        (8 3 0 2 5) <--(pop)-- (3 8 3 0 2 5)
        (2 8 3 0 2 5) <--(push 2)-- (8 3 0 2 5)
        (8 3 0 2 5) <--(pop)-- (2 8 3 0 2 5)
        (5 8 3 0 2 5) <--(push 5)-- (8 3 0 2 5)
        (1 5 8 3 0 2 5) <--(push 1)-- (5 8 3 0 2 5)
        (0 1 5 8 3 0 2 5) <--(push 0)-- (1 5 8 3 0 2 5)
        (0 0 1 5 8 3 0 2 5) <--(push 0)-- (0 1 5 8 3 0 2 5)
        (0 1 5 8 3 0 2 5) <--(pop)-- (0 0 1 5 8 3 0 2 5)
        (1 5 8 3 0 2 5) <--(pop)-- (0 1 5 8 3 0 2 5)
        (1 1 5 8 3 0 2 5) <--(push 1)-- (1 5 8 3 0 2 5)
        (1 5 8 3 0 2 5) <--(pop)-- (1 1 5 8 3 0 2 5)
        (5 8 3 0 2 5) <--(pop)-- (1 5 8 3 0 2 5)
        (5 5 8 3 0 2 5) <--(push 5)-- (5 8 3 0 2 5)
        (5 8 3 0 2 5) <--(pop)-- (5 5 8 3 0 2 5)
        (8 5 8 3 0 2 5) <--(push 8)-- (5 8 3 0 2 5)
        (5 8 3 0 2 5) <--(pop)-- (8 5 8 3 0 2 5)
        (3 5 8 3 0 2 5) <--(push 3)-- (5 8 3 0 2 5)
        (0 3 5 8 3 0 2 5) <--(push 0)-- (3 5 8 3 0 2 5)
        (6 0 3 5 8 3 0 2 5) <--(push 6)-- (0 3 5 8 3 0 2 5)
        (2 6 0 3 5 8 3 0 2 5) <--(push 2)-- (6 0 3 5 8 3 0 2 5)
        (6 0 3 5 8 3 0 2 5) <--(pop)-- (2 6 0 3 5 8 3 0 2 5)
        (0 3 5 8 3 0 2 5) <--(pop)-- (6 0 3 5 8 3 0 2 5)
        (6 0 3 5 8 3 0 2 5) <--(push 6)-- (0 3 5 8 3 0 2 5)
        (9 6 0 3 5 8 3 0 2 5) <--(push 9)-- (6 0 3 5 8 3 0 2 5)
        (6 0 3 5 8 3 0 2 5) <--(pop)-- (9 6 0 3 5 8 3 0 2 5)
        (0 3 5 8 3 0 2 5) <--(pop)-- (6 0 3 5 8 3 0 2 5)
        CL-USER> (stop)
        (1 0 3 5 8 3 0 2 5) <--(push 1)-- (0 3 5 8 3 0 2 5)
        (0 3 5 8 3 0 2 5) <--(pop)-- (1 0 3 5 8 3 0 2 5)
        NIL
        CL-USER> 



I have (setf swank:*globally-redirect-io* t) in ~/.swank.lisp .. see the
Slime manual for info; I'm not sure if it is needed anymore.
From: Matthew D Swank
Subject: Re: OT:Lock based concurrency
Date: 
Message-ID: <G4LRk.8425$Qb1.2460@newsfe19.iad>
On Sun, 09 Nov 2008 20:18:23 +0100, Lars Rune Nøstdal wrote:

> On Sat, 2008-11-08 at 17:41 +0000, Matthew D Swank wrote:
>> 
>> Can anyone recommend could resources on the classics (mutexes,
>> semaphores, monitors, etc)
> 
> I think any generic tutorial (wikipedia, even) out there about these
> concepts will do in combination with whatever your Lisp-implementation
> provides.

How dare you try to put this thread back on topic!

Matt
-- 
How apt the poor are to be proud.
		-- William Shakespeare, "Twelfth-Night"
comp.lang.lisp / 2008 / nov