[Pharo-dev] Lock-free Atomic Counter ?

Eliot Miranda eliot.miranda at gmail.com
Wed Apr 2 19:33:09 EDT 2014


Hi Sven,

On Wed, Apr 2, 2014 at 3:11 PM, Sven Van Caekenberghe <sven at stfx.eu> wrote:

> Hi,
>
> Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
>
> nextId
>   ^ idCounter := idCounter + 1
>
> Or is it still possible that two process entering this code can mess
> things up ?
>

OK, but it's a real hack ;-).

In the current Interpreter, Stack and Cog VMs this will work fine up to
63-bits because non-failing primitives are not suspension points in the VM
/except/ for the Semaphore primitives.

If the counter is initialized to 0, at first, there won't even be a send
since either the interpreter will evaluate special selector #+ on
SmallInteger without performing a send, or machine code will evaluate the
inlined code for SmallInteger #+ without doing a send.

Once the counter overflows into LargePositveInteger but is within 63-bits,
there will be sends but these will always be of primitive 21
(LargePositiveInteger>>#+ uses primitive 21, which does 64-bit /signed/
arithmetic but nothing larger, hence works up to 63-bit
LargePositiveIntegers).

Once beyond 63 bits the primitive will fail and there will be a suspension
point in LargePositiveInteger>>#+ before it calls Integer>>#+, which will
call digitAdd:.

You should be able to test this.  Try evaluating this one:

| counter proc |
counter := 0.
proc := [[counter := counter + 1. true] whileTrue] newProcess.
proc priority: Processor activePriority - 1.
proc resume.
[(Delay forSeconds: 1) wait.
 proc suspendedContext method ~~ thisContext method ifTrue: [proc suspend.
self halt]] repeat


Now try and evaluate this one:
| counter proc |
counter := 1 bitShift: 64.
proc := [[counter := counter + 1. true] whileTrue] newProcess.
proc priority: Processor activePriority - 1.
proc resume.
[(Delay forSeconds: 1) wait.
 proc suspendedContext method ~~ thisContext method ifTrue: [proc suspend.
self halt]] repeat

The second one halts almost immediately.  You can fix this by changing
LargePositiveInteger>>#+ to use the primitive frm the large integer
arithmetic plugin, which will not fail until it runs out of memory.

So if you really /must/ go this route you /can/ get away with it.  But on
your own head be it ;-)


> I vaguely remember a discussion about that long ago...
>
> TIA,
>
> Sven
>



-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-dev_lists.pharo.org/attachments/20140402/223e44ac/attachment-0002.html>


More information about the Pharo-dev mailing list