[Ann] ReadWriteLock

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
54 messages Options
123
Reply | Threaded
Open this post in threaded view
|

[Ann] ReadWriteLock

Denis Kudriashov
Hi.

I implemented small package ReadWriteLock http://smalltalkhub.com/mc/Pharo/ReadWriteLock/main.

Gofer it 
smalltalkhubUser: 'Pharo' project: 'ReadWriteLock';
configurationOf: 'ReadWriteLock';
loadStable

It is reentral read write lock which described in 

An ReadWriteLock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing.

Public API and Key Messages

- lock := ReadWriteLock new
- lock criticalRead: aBlock
- lock criticalWrite: aBlock

Implementation based on two semaphores and readers counter. 

Main difficulty is carefully handle process termination during execution of critical sections. This problem described in Semaphore>>critical: comment. Same approach is used here. But synchronisation logic around two semaphores for reading and writing complicates things very much. No simple way to decompose logic on multiple methods because information about process interruption become hidden.
From the Semaphore comment:
The main trick is assignment right before we go into the wait primitive (which is not a real send and therefore not interruptable either). So after we can check that waiting is happen or not.

Tests are implemented only for lock scenarios. No tests for described termination process cases. It is not really clear how to write it.  
I will be appreciate if people review code. Maybe you will suggest simplifications. It is always difficult to implement concurrent code. 

Best regards,
Denis
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Max Leske
Hi Denis,

How does your ReadWriteLock compare to Monitor? I was under the impression that what you describe could be done with a Monitor.

Cheers,
Max

 
On 04 Jan 2016, at 18:39, Denis Kudriashov <[hidden email]> wrote:

Hi.

I implemented small package ReadWriteLock http://smalltalkhub.com/mc/Pharo/ReadWriteLock/main.

Gofer it 
smalltalkhubUser: 'Pharo' project: 'ReadWriteLock';
configurationOf: 'ReadWriteLock';
loadStable

It is reentral read write lock which described in 

An ReadWriteLock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing.

Public API and Key Messages

- lock := ReadWriteLock new
- lock criticalRead: aBlock
- lock criticalWrite: aBlock

Implementation based on two semaphores and readers counter. 

Main difficulty is carefully handle process termination during execution of critical sections. This problem described in Semaphore>>critical: comment. Same approach is used here. But synchronisation logic around two semaphores for reading and writing complicates things very much. No simple way to decompose logic on multiple methods because information about process interruption become hidden.
From the Semaphore comment:
The main trick is assignment right before we go into the wait primitive (which is not a real send and therefore not interruptable either). So after we can check that waiting is happen or not.

Tests are implemented only for lock scenarios. No tests for described termination process cases. It is not really clear how to write it.  
I will be appreciate if people review code. Maybe you will suggest simplifications. It is always difficult to implement concurrent code. 

Best regards,
Denis

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Tudor Girba-2
In reply to this post by Denis Kudriashov
Quite elegant! :)

Is this meant to be part of the main distribution?

Doru


> On Jan 4, 2016, at 7:39 PM, Denis Kudriashov <[hidden email]> wrote:
>
> Hi.
>
> I implemented small package ReadWriteLock http://smalltalkhub.com/mc/Pharo/ReadWriteLock/main.
>
> Gofer it
> smalltalkhubUser: 'Pharo' project: 'ReadWriteLock';
> configurationOf: 'ReadWriteLock';
> loadStable
>
> It is reentral read write lock which described in
> https://en.wikipedia.org/wiki/Readers–writer_lock. From the article:
>
> An ReadWriteLock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing.
>
> Public API and Key Messages
>
> - lock := ReadWriteLock new
> - lock criticalRead: aBlock
> - lock criticalWrite: aBlock
>
> Implementation based on two semaphores and readers counter.
>
> Main difficulty is carefully handle process termination during execution of critical sections. This problem described in Semaphore>>critical: comment. Same approach is used here. But synchronisation logic around two semaphores for reading and writing complicates things very much. No simple way to decompose logic on multiple methods because information about process interruption become hidden.
> From the Semaphore comment:
> The main trick is assignment right before we go into the wait primitive (which is not a real send and therefore not interruptable either). So after we can check that waiting is happen or not.
>
> Tests are implemented only for lock scenarios. No tests for described termination process cases. It is not really clear how to write it.  
> I will be appreciate if people review code. Maybe you will suggest simplifications. It is always difficult to implement concurrent code.
>
> Best regards,
> Denis

--
www.tudorgirba.com
www.feenk.com

"What is more important: To be happy, or to make happy?"


Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Tudor Girba-2
In reply to this post by Max Leske
Hi,

If I understand correctly:
- the Monitor only offer one kind of critical section that typically affects everyone equally,
- while with the new ReadWriteLock, the readers will be blocked only if a writer will acquire the writer critical section.

Cheers,
Doru


> On Jan 4, 2016, at 7:55 PM, Max Leske <[hidden email]> wrote:
>
> Hi Denis,
>
> How does your ReadWriteLock compare to Monitor? I was under the impression that what you describe could be done with a Monitor.
>
> Cheers,
> Max
>
>  
>> On 04 Jan 2016, at 18:39, Denis Kudriashov <[hidden email]> wrote:
>>
>> Hi.
>>
>> I implemented small package ReadWriteLock http://smalltalkhub.com/mc/Pharo/ReadWriteLock/main.
>>
>> Gofer it
>> smalltalkhubUser: 'Pharo' project: 'ReadWriteLock';
>> configurationOf: 'ReadWriteLock';
>> loadStable
>>
>> It is reentral read write lock which described in
>> https://en.wikipedia.org/wiki/Readers–writer_lock. From the article:
>>
>> An ReadWriteLock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing.
>>
>> Public API and Key Messages
>>
>> - lock := ReadWriteLock new
>> - lock criticalRead: aBlock
>> - lock criticalWrite: aBlock
>>
>> Implementation based on two semaphores and readers counter.
>>
>> Main difficulty is carefully handle process termination during execution of critical sections. This problem described in Semaphore>>critical: comment. Same approach is used here. But synchronisation logic around two semaphores for reading and writing complicates things very much. No simple way to decompose logic on multiple methods because information about process interruption become hidden.
>> From the Semaphore comment:
>> The main trick is assignment right before we go into the wait primitive (which is not a real send and therefore not interruptable either). So after we can check that waiting is happen or not.
>>
>> Tests are implemented only for lock scenarios. No tests for described termination process cases. It is not really clear how to write it.  
>> I will be appreciate if people review code. Maybe you will suggest simplifications. It is always difficult to implement concurrent code.
>>
>> Best regards,
>> Denis
>

--
www.tudorgirba.com
www.feenk.com

“Live like you mean it."


Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Igor Stasenko
It heavily depends on data structure you using what kind of synchronization mechanism is more efficient than another.
For instance AtomicQueue implementation is one that falls in such category 'many readers, but only single writer'. But it's not using semaphores to synchronise access to it.

On 4 January 2016 at 20:06, Tudor Girba <[hidden email]> wrote:
Hi,

If I understand correctly:
- the Monitor only offer one kind of critical section that typically affects everyone equally,
- while with the new ReadWriteLock, the readers will be blocked only if a writer will acquire the writer critical section.

Cheers,
Doru


> On Jan 4, 2016, at 7:55 PM, Max Leske <[hidden email]> wrote:
>
> Hi Denis,
>
> How does your ReadWriteLock compare to Monitor? I was under the impression that what you describe could be done with a Monitor.
>
> Cheers,
> Max
>
>
>> On 04 Jan 2016, at 18:39, Denis Kudriashov <[hidden email]> wrote:
>>
>> Hi.
>>
>> I implemented small package ReadWriteLock http://smalltalkhub.com/mc/Pharo/ReadWriteLock/main.
>>
>> Gofer it
>>      smalltalkhubUser: 'Pharo' project: 'ReadWriteLock';
>>      configurationOf: 'ReadWriteLock';
>>      loadStable
>>
>> It is reentral read write lock which described in
>> https://en.wikipedia.org/wiki/Readers–writer_lock. From the article:
>>
>> An ReadWriteLock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing.
>>
>> Public API and Key Messages
>>
>> - lock := ReadWriteLock new
>> - lock criticalRead: aBlock
>> - lock criticalWrite: aBlock
>>
>> Implementation based on two semaphores and readers counter.
>>
>> Main difficulty is carefully handle process termination during execution of critical sections. This problem described in Semaphore>>critical: comment. Same approach is used here. But synchronisation logic around two semaphores for reading and writing complicates things very much. No simple way to decompose logic on multiple methods because information about process interruption become hidden.
>> From the Semaphore comment:
>> The main trick is assignment right before we go into the wait primitive (which is not a real send and therefore not interruptable either). So after we can check that waiting is happen or not.
>>
>> Tests are implemented only for lock scenarios. No tests for described termination process cases. It is not really clear how to write it.
>> I will be appreciate if people review code. Maybe you will suggest simplifications. It is always difficult to implement concurrent code.
>>
>> Best regards,
>> Denis
>

--
www.tudorgirba.com
www.feenk.com

“Live like you mean it."





--
Best regards,
Igor Stasenko.
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Max Leske
Hi

2016-01-04 18:55 GMT+01:00 Max Leske <[hidden email]>:
Hi Denis,

How does your ReadWriteLock compare to Monitor? I was under the impression that what you describe could be done with a Monitor.

Monitor is different synchronisation mechanism. It can be used to implement ReadWriteLock. But It looks like more expensive solution. 

After look at Pharo implementation of Monitor I realise that it #critical: method not takes into account issue described in Semaphore>>critical:. I will ask about it on separate thread. 

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Igor Stasenko
Hi.

2016-01-04 19:19 GMT+01:00 Igor Stasenko <[hidden email]>:
It heavily depends on data structure you using what kind of synchronization mechanism is more efficient than another.
For instance AtomicQueue implementation is one that falls in such category 'many readers, but only single writer'. But it's not using semaphores to synchronise access to it.

Can you explain deeply what problem with AtomicQueue in  'many readers, but only single writer'?

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Tudor Girba-2

2016-01-04 18:51 GMT+01:00 Tudor Girba <[hidden email]>:
Is this meant to be part of the main distribution?

I don't know. People should decide it. To me it is normal to get explicit dependency in configuration.
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Ben Coman
In reply to this post by Denis Kudriashov
On Tue, Jan 5, 2016 at 1:39 AM, Denis Kudriashov <[hidden email]> wrote:

> Hi.
>
> I implemented small package ReadWriteLock
> http://smalltalkhub.com/mc/Pharo/ReadWriteLock/main.
>
> Gofer it
> smalltalkhubUser: 'Pharo' project: 'ReadWriteLock';
> configurationOf: 'ReadWriteLock';
> loadStable
>
>
> It is reentral read write lock which described in
> https://en.wikipedia.org/wiki/Readers–writer_lock. From the article:
>
>> An ReadWriteLock allows concurrent access for read-only operations, while
>> write operations require exclusive access. This means that multiple threads
>> can read the data in parallel but an exclusive lock is needed for writing or
>> modifying data. When a writer is writing the data, all other writers or
>> readers will be blocked until the writer is finished writing.
>
>
> Public API and Key Messages
>
> - lock := ReadWriteLock new
> - lock criticalRead: aBlock
> - lock criticalWrite: aBlock
>
> Implementation based on two semaphores and readers counter.
>
> Main difficulty is carefully handle process termination during execution of
> critical sections. This problem described in Semaphore>>critical: comment.
> Same approach is used here. But synchronisation logic around two semaphores
> for reading and writing complicates things very much. No simple way to
> decompose logic on multiple methods because information about process
> interruption become hidden.
> From the Semaphore comment:
>>
>> The main trick is assignment right before we go into the wait primitive
>> (which is not a real send and therefore not interruptable either). So after
>> we can check that waiting is happen or not.
>
>
> Tests are implemented only for lock scenarios. No tests for described
> termination process cases. It is not really clear how to write it.
> I will be appreciate if people review code. Maybe you will suggest
> simplifications. It is always difficult to implement concurrent code.
>
> Best regards,
> Denis



I don't think /writeIsLocked/ is a good variable name in
#criticalWrite: .   Even though its a local var, its semantic "feels"
object wide.  Consider process A enters #criticalWrite and gains the
write lock, then process B enters #criticalWrite: where it does
"writeIsLocked := false" -- but A still has the lock, so the semantic
is confusing.  Perhaps renaming to something like "ensureRelease" is
more intention revealing.

waiting inside the ensure-main-block is interrupted.  If B is
terminated, then the ensure-block executes

Now there is a problem with the logic of #criticalWrite:
Consider a scenario where process p1 is holding the writersSemaphore
for a long time, and processes p2 and p3 are waiting on it.  If p2 is
terminated, then its ensure-block executes, which signals
writersSemaphore  and p3 proceeds prematurely.  By way of example, try
this...

  | lock p1 p2 p3|
  Transcript clear.
  lock := ReadWriteLock new.
  p1 := [ Transcript crShow: '1A'. lock criticalWrite: [ Transcript
crShow: '1B'.  self halt ] ]
                newProcess name: 'LOCK1' .
  p2 := [ Transcript crShow: '2A'. lock criticalWrite: [ Transcript
crShow: '2B' ] ]
                newProcess name: 'LOCK2' .
  p3 := [ Transcript crShow: '3A'. lock criticalWrite: [ Transcript
crShow: '3B' ] ]
                newProcess name: 'LOCK3' .
  p1 resume.
  p2 resume.
  p3 resume.
" (1 second wait).
  p2 terminate.
"

...with the last two lines commented, you get the expected result...
A1
A2
B1
C1
"Correctly pauses until <Proceed> debugger"
B2
C2

..but if you uncomment the last two lines you get...
1A
1B
2A
3A
"whoops, did not pause here until <Proceed> in debugger"
3B

You can observe this further by adding the following logging to the
top of the ensure block...
  ] ensure: [
  Transcript crShow: writersSemaphore excessSignals ; tab ; show:
activeProcess == writeLockOwner ; tab ; show: aBlock.
  ...


So when p2 is terminated, it is no longer waiting on
/writersSemaphore/ and thus will not be consuming a signal, so we
should avoid signalling it when the process it terminated.

One solution might be...
  criticalWrite: aBlock
    | activeProcess ensureRelease blockResult|
    activeProcess := Processor activeProcess.
    activeProcess == writeLockOwner ifTrue:[ ^aBlock value].
    ensureRelease := false.
    blockResult := [
        ensureRelease := true.
        writersSemaphore wait.
        writeLockOwner := activeProcess.
        aBlock value
        ] ensure: [
            "Need to avoid signalling when terminated, since it never
consumed a signal"
            (ensureRelease and:
                [ activeProcess == writeLockOwner ])  ifTrue: [
            writeLockOwner := nil.
            writersSemaphore signal ].
            ].
   ^ blockResult



Now I was curious why Semaphore>>critical: did not exhibit the same
problem, since the following...
  | lock p1 p2 p3|
  Transcript clear.
  lock := Semaphore forMutualExclusion.
  p1 := [ Transcript crShow: '1A'. lock critical: [ Transcript crShow:
'1B'.  self halt ] ]
                newProcess name: 'LOCK1' .
  p2 := [ Transcript crShow: '2A'. lock critical: [ Transcript crShow: '2B' ] ]
                newProcess name: 'LOCK2' .
  p3 := [ Transcript crShow: '3A'. lock critical: [ Transcript crShow: '3B' ] ]
                newProcess name: 'LOCK3' .
  p1 resume.
  p2 resume.
  p3 resume.
  (1 second wait).
  p2 terminate.

which produces...
1A
1B
2A
3A
"Correctly pauses until <Proceed> debugger"
3B


However, if I copy Semaphore to Semaphore2 and do this...
  | lock p1 p2 p3|
  Transcript clear.
  lock := Semaphore2 forMutualExclusion.
  p1 := [ Transcript crShow: '1A'. lock critical: [ Transcript crShow:
'1B'.  self halt ] ]
                newProcess name: 'LOCK1' .
  p2 := [ Transcript crShow: '2A'. lock critical: [ Transcript crShow: '2B' ] ]
                newProcess name: 'LOCK2' .
  p3 := [ Transcript crShow: '3A'. lock critical: [ Transcript crShow: '3B' ] ]
                newProcess name: 'LOCK3' .
  p1 resume.
  p2 resume.
  p3 resume.
  (1 second wait).
  p2 terminate.

it produces...
1A
1B
2A
3A
"whoops, did not pause here until <Proceed> in debugger"
3B

This is really strange!  Why does the copied class Semaphore2 behave
differently to the original class Semaphore? This was in build 50510.


btw I have this growing suspicion that we should eliminate
Semaphore>>critical: and Semaphore>>forMutualExclusion.   Semaphores
on their own should *not* provide a facility for to protect critical
regions since they suffer from accidental release [1] due to
*lack*of*ownership*.   This is the root cause of the problem scenario
above.  Mutex>>critical: which does have a sense of ownership should
be used instead.  Indeed, [2] advises "The correct use of a semaphore
is for *signaling* from one task to another. A mutex is meant to be
taken and released, always in that order, by *[the same]* task that
uses the shared resource it protects." -- But this is a subtle
distinction and having Semaphore>>critical: leads people to incorrect
thinking and exposes them to subtle errors.

Mutex>>critical: cold still be implemented using Semaphore, but rather
than just forwarding to Semaphore>>critical: pull that method's code
out into Mutex>>critical: so it looks like what  Denis did for
#criticalWrite:    Or alternatives, we should consider directly using
the mutex primitives Eliot mentioned some time ago were already in the
VM.

[1] https://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-1-semaphores/
[2] http://www.barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore

cheers -ben

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
Hi

Thank you very much for this analysts.

2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
This is really strange!  Why does the copied class Semaphore2 behave
differently to the original class Semaphore? This was in build 50510.

It is so frustrating.
I add tests for your cases which is red now. And one for Semaphore (inside ReadWriteLockTests) which is green
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Ben Coman

2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
btw I have this growing suspicion that we should eliminate
Semaphore>>critical: and Semaphore>>forMutualExclusion.   Semaphores
on their own should *not* provide a facility for to protect critical
regions since they suffer from accidental release [1] due to
*lack*of*ownership*. 

I have same feeling when analyse problem of critical: implementation. But I not think that Semaphore>>forMutualExclusion is bad. It is common case that semaphore "free" by default. And this name is explicitly said about this.
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Denis Kudriashov

2016-01-05 16:54 GMT+01:00 Denis Kudriashov <[hidden email]>:
2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
This is really strange!  Why does the copied class Semaphore2 behave
differently to the original class Semaphore? This was in build 50510.

It is so frustrating.
I add tests for your cases which is red now. And one for Semaphore (inside ReadWriteLockTests) which is green

It is really crazy. I just try two experiments:
1) I move semaphore critical: logic to Mutex. Our test with mutex become red.
2) I copy Semaphore>>critical: to #critical2:. And with it Semaphore test become red. 

So somebody definitely know about #critical: selector and it receiver
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
I found problem. Look at Process>>terminate. There is special place:

"Figure out if we are terminating the process while waiting in Semaphore>>critical:
In this case, pop the suspendedContext so that we leave the ensure: block inside
Semaphore>>critical: without signaling the semaphore."
(oldList class == Semaphore and: [
self halt.
suspendedContext method == (Semaphore compiledMethodAt: #critical:) ]) ifTrue: [
suspendedContext := suspendedContext home ].

Really crazy. Comment inside #critical: method said that we should signal in any case. But #terminate method said that we should not allow signalling in that case. 
Why it is not implemented inside #critical: method by #ifCurtailed: logic? 


2016-01-05 17:10 GMT+01:00 Denis Kudriashov <[hidden email]>:

2016-01-05 16:54 GMT+01:00 Denis Kudriashov <[hidden email]>:
2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
This is really strange!  Why does the copied class Semaphore2 behave
differently to the original class Semaphore? This was in build 50510.

It is so frustrating.
I add tests for your cases which is red now. And one for Semaphore (inside ReadWriteLockTests) which is green

It is really crazy. I just try two experiments:
1) I move semaphore critical: logic to Mutex. Our test with mutex become red.
2) I copy Semaphore>>critical: to #critical2:. And with it Semaphore test become red. 

So somebody definitely know about #critical: selector and it receiver

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov

2016-01-05 17:25 GMT+01:00 Denis Kudriashov <[hidden email]>:
Comment inside #critical: method said that we should signal in any case.

I think I not correctly understand this point when read it. Process terminating case is not mention in comment.
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Henrik Sperre Johansen
In reply to this post by Denis Kudriashov

On 05 Jan 2016, at 5:10 , Denis Kudriashov <[hidden email]> wrote:


2016-01-05 16:54 GMT+01:00 Denis Kudriashov <[hidden email]>:
2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
This is really strange!  Why does the copied class Semaphore2 behave
differently to the original class Semaphore? This was in build 50510.

It is so frustrating.
I add tests for your cases which is red now. And one for Semaphore (inside ReadWriteLockTests) which is green

It is really crazy. I just try two experiments:
1) I move semaphore critical: logic to Mutex. Our test with mutex become red.
2) I copy Semaphore>>critical: to #critical2:. And with it Semaphore test become red. 

So somebody definitely know about #critical: selector and it receiver

Yes, check Process >> #terminate, there's special code for skipping a context if the suspended process was waiting for Semaphore.

The way I see it, the purpose of the caught variable in Semaphore is to not execute the ensure: if the process was suspended (and then terminated)*in* the ensure: method, before block ever executes and one starts waiting on the semaphore. 

If one has made it to the wait call, caught is already true, and the ensure block would be executed on termination unwind..
That part is, as I said above, handled directly in Process >> #terminate (near the bottom)
AFAICT, both parts would be need to be reflected for Monitor >> #critical: to work correctly under termination.
At which point, it would seem to me a better idea (if possible) if the terminated  context was culled into the ensure block, instead of muddying up Process >> #terminate further, one could then write a few ugly, but localized:
ensure: [:unwoundContext | (caught and: [unwoundContext isWaitContext notl]) ifTrue: [sem signal]]
instead of  having to keep adding special case handling to Process >> #terminate.

Cheers,
Henry

signature.asc (859 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Ben Coman
In reply to this post by Denis Kudriashov
On Tue, Jan 5, 2016 at 11:59 PM, Denis Kudriashov <[hidden email]> wrote:

>
> 2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
>>
>> btw I have this growing suspicion that we should eliminate
>> Semaphore>>critical: and Semaphore>>forMutualExclusion.   Semaphores
>> on their own should *not* provide a facility for to protect critical
>> regions since they suffer from accidental release [1] due to
>> *lack*of*ownership*.
>
>
> I have same feeling when analyse problem of critical: implementation. But I
> not think that Semaphore>>forMutualExclusion is bad.

But Semaphore>>forMutualExclusion *encourages* people to believe
semaphores can be used *on*their*own* for mutual exclusion, when they
*shouldn't*.  You *must* add ownership.  If the mutual exclusion
object doesn’t have ownership then, irrelevant of what it is called,
it is not a mutex!!! [1].

"Strictly speaking [2]...
  -- A mutex is *locking* mechanism used to synchronize access to a
resource. Only one task (can be a thread or process based on OS
abstraction) can acquire the mutex. It means there is *ownership*
associated with mutex, and only the owner can release the lock
(mutex).
  -- A semaphore is *signaling* mechanism (“I am done, you can carry
on” kind of signal). For example, if you are listening songs (assume
it as one task) on your mobile and at the same time your friend calls
you, an interrupt is triggered upon which an interrupt service routine
(ISR) signals the call processing task to wakeup


>It is common case that semaphore "free" by default.

With an implementation like..
    Semaphore>>forMutualExclusion
        ^self new signal

we don't gain a lot, and its a misleading convenience method since its
doesn't provide the proper facility for mutual exclusion (and I do
conflate mutual exclusion == mutex).   Indeed, "Semaphore
forMutualExclusion + roll your ownership management + problems since
you weren't aware you needed to roll your own ownership management" is
not more convenient than "Mutex new"

If you want to keep a convenience method for a pre signalled
Semaphore, then we could provide something like  "Semaphore
newSignalled"

> And this name is explicitly said about this.

Actually no.  It explicitly says it provides mutual exclusion - which
without ownership, it does not. It only implicitly provides a
pre-signalled Semaphore - you have to *know* of look at the source.

[1]  https://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-2-the-mutex/
[2] http://www.geeksforgeeks.org/mutex-vs-semaphore/

cheers -ben

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Ben Coman
In reply to this post by Henrik Sperre Johansen
On Wed, Jan 6, 2016 at 12:30 AM, Henrik Johansen
<[hidden email]> wrote:

>
> On 05 Jan 2016, at 5:10 , Denis Kudriashov <[hidden email]> wrote:
>
>
> 2016-01-05 16:54 GMT+01:00 Denis Kudriashov <[hidden email]>:
>>
>> 2016-01-05 16:06 GMT+01:00 Ben Coman <[hidden email]>:
>>>
>>> This is really strange!  Why does the copied class Semaphore2 behave
>>> differently to the original class Semaphore? This was in build 50510.
>>
>>
>> It is so frustrating.
>> I add tests for your cases which is red now. And one for Semaphore (inside
>> ReadWriteLockTests) which is green
>
>
> It is really crazy. I just try two experiments:
> 1) I move semaphore critical: logic to Mutex. Our test with mutex become
> red.
> 2) I copy Semaphore>>critical: to #critical2:. And with it Semaphore test
> become red.

After Semaphore to Semaphore2 and running my test case above showing
its bad terminate behaviour without the special handling in
Process>>terminate,  I then copied Mutex to Mutex2 and made the
following mod...
  Mutex2>>initiialize
    super initialize.
    semaphore := Semaphore2 forMutualExclusion.

such that my test case with
    lock := Mutex2 new.
also showed the bad terminate behaviour.

But then copying Mutex2 to Mutex3 with the following mod to replace
the call to Semaphore>>critical:...

  Mutex3>>critical: aBlock
    "Evaluate aBlock protected by the receiver."
    | activeProcess ensureRelease blockResult|
    activeProcess := Processor activeProcess.
    activeProcess == owner ifTrue:[^aBlock value].
    ensureRelease := false.
    blockResult := [
      ensureRelease := true.
      semaphore wait.
      owner := activeProcess.
      aBlock value
      ] ensure: [
        (ensureRelease and: [ activeProcess == owner ]) ifTrue: [
          owner := nil.
          semaphore signal ]
        ].
  ^blockResult

and my test case with
      lock := Mutex3 new.
works fine .

So again I push that Semaphore>critical: is *bad*.

>
> So somebody definitely know about #critical: selector and it receiver

#critical: is mutual exclusion, thus a Mutex, not a Semaphore.

>
>
> Yes, check Process >> #terminate, there's special code for skipping a
> context if the suspended process was waiting for Semaphore.

Well spotted.

>
> The way I see it, the purpose of the caught variable in Semaphore is to not
> execute the ensure: if the process was suspended (and then terminated)*in*
> the ensure: method, before block ever executes and one starts waiting on the
> semaphore.
>
> If one has made it to the wait call, caught is already true, and the ensure
> block would be executed on termination unwind..
> That part is, as I said above, handled directly in Process >> #terminate
> (near the bottom)
> AFAICT, both parts would be need to be reflected for Monitor >> #critical:
> to work correctly under termination.
> At which point, it would seem to me a better idea (if possible) if the
> terminated  context was culled into the ensure block, instead of muddying up
> Process >> #terminate further, one could then write a few ugly, but
> localized:
> ensure: [:unwoundContext | (caught and: [unwoundContext isWaitContext notl])
> ifTrue: [sem signal]]
> instead of  having to keep adding special case handling to Process >>
> #terminate.
>
> Cheers,
> Henry

Simply, if we eliminate Semaphore>>critical: then of course no special
processing is required in Process>>terminate.  I suggest that after a
bit of review and testing, all we'll need is  Mutex3>>critical:
described above.

cheers -ben

Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Henrik Sperre Johansen
In reply to this post by Denis Kudriashov

On 05 Jan 2016, at 5:25 , Denis Kudriashov <[hidden email]> wrote:

I found problem. Look at Process>>terminate. There is special place:

"Figure out if we are terminating the process while waiting in Semaphore>>critical:
In this case, pop the suspendedContext so that we leave the ensure: block inside
Semaphore>>critical: without signaling the semaphore."
(oldList class == Semaphore and: [
self halt.
suspendedContext method == (Semaphore compiledMethodAt: #critical:) ]) ifTrue: [
suspendedContext := suspendedContext home ].

Really crazy. Comment inside #critical: method said that we should signal in any case. But #terminate method said that we should not allow signalling in that case. 
Why it is not implemented inside #critical: method by #ifCurtailed: logic? 

ifCurtailed: only unwinds if an error/termination occured, so that would mean not signalling the semaphore when everything goes as planned, and we leave the critical section...

There are only two cases:
- Have I been unblocked by the semaphore? (IE, have I consumed a signal?) Then, signal when exiting section (whether through normal execution, termination, or an unhandled error).
- Has it not? Then, do not signal.
Here, there are two subcases
- I have entered the section that will unwind in the ensure: block, but am not yet waiting for Semaphore. (handled by caught variable)
- I have started waiting for semaphore, but not consumed a signal. (handled by #terminate). 

The last bit is potentially really tricky, if the callback code in suspend is actually used, and is not performed atomically. (Strangely, a haltOnce in the suspend fallback code *did* trigger for me, despite the comment that it is purely for old VM's)
If the terminating process is interrupted on the remove:ifAbsent: call (which could/should be removeLink:ifAbsent:, btw) by a thread signalling its semaphore, and the semaphore selects the process being terminated as the one to resume, but terminating thread is resumed before terminated (which is no longer *really* suspended), the fallback code will happily return the (now no longer really suspended) semaphore it recorded before removeLink:ifAbsent: call. The terminating process then checks that it is indeed a semaphore, and that the terminating threads suspendedContext is still the critical call, and promptly decides to not signal the semaphore as part of termination.

The net result of which, would be an entered critical section without a corresponding exit, and a hung semaphore until someone feeds it a few extra signals, if we're talking input semaphore, say, by wiggling the mouse a bit or something... Sound familiar to anyone?

A possible fix would be changing:
oldList remove: self ifAbsent: [] to
oldList removeLink: self ifAbsent:[oldList := nil]

In other words. if someone (ie, the waiting list ) has removed a thread from the old waiting list before the thread was able to do it, don't just proceed as if nothing has happened, but consider the terminated thread as no longer having on the old waiting list at the time of suspension.
Then, terminate will find a nil oldList (whose class is not Semaphore), and the ensure: block will execute as the semaphore expects.

Combined with the suggesting in preceeding mail, that would mean not doing the checks in terminate, but #cull:'ing the oldList into ensure contexts during unwind.

Cheers,
Henry

Timeline:
[Terminating Thread] Wanting to terminate a victim thread, it tries to suspend it. 
[Terminating Thread] Suspend call records the oldList (semaphore) victim is currently blocked on , then is interrupted at the remove:ifAbsent: call.
[Signalling Tread] Signals the semaphore
[Signalling Tread] Semaphore decides to resume the victim thread. Primitive removes it from list, and readies it for resumption.
[Signalling Tread yields, expecting a signal from victim thread when it is done] 
[Terminating Thread resumed]
[Terminating Tread] Checks oldList and suspendedContext, find them both satisfying its check for whether the victim was waiting for a semaphore, and pops the ensure block







signature.asc (859 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Ben Coman

2016-01-05 18:15 GMT+01:00 Ben Coman <[hidden email]>:
But Semaphore>>forMutualExclusion *encourages* people to believe
semaphores can be used *on*their*own* for mutual exclusion, when they
*shouldn't*.  You *must* add ownership.  If the mutual exclusion
object doesn’t have ownership then, irrelevant of what it is called,
it is not a mutex!!! [1].

"Strictly speaking [2]...
  -- A mutex is *locking* mechanism used to synchronize access to a
resource. Only one task (can be a thread or process based on OS
abstraction) can acquire the mutex. It means there is *ownership*
associated with mutex, and only the owner can release the lock
(mutex).
  -- A semaphore is *signaling* mechanism (“I am done, you can carry
on” kind of signal). For example, if you are listening songs (assume
it as one task) on your mobile and at the same time your friend calls
you, an interrupt is triggered upon which an interrupt service routine
(ISR) signals the call processing task to wakeup


>It is common case that semaphore "free" by default.

With an implementation like..
    Semaphore>>forMutualExclusion
        ^self new signal

we don't gain a lot, and its a misleading convenience method since its
doesn't provide the proper facility for mutual exclusion (and I do
conflate mutual exclusion == mutex).   Indeed, "Semaphore
forMutualExclusion + roll your ownership management + problems since
you weren't aware you needed to roll your own ownership management" is
not more convenient than "Mutex new"

If you want to keep a convenience method for a pre signalled
Semaphore, then we could provide something like  "Semaphore
newSignalled"

> And this name is explicitly said about this.

Actually no.  It explicitly says it provides mutual exclusion - which
without ownership, it does not. It only implicitly provides a
pre-signalled Semaphore - you have to *know* of look at the source.

Ok Ben. I got it.
Thank's for detailed explanation. It makes sense.
I will prepare slice with your proposed changes. We will make Semaphore>>critical: and #forMutualExclusion deprecated (if nobody against it).
Reply | Threaded
Open this post in threaded view
|

Re: [Ann] ReadWriteLock

Denis Kudriashov
In reply to this post by Henrik Sperre Johansen

2016-01-05 18:49 GMT+01:00 Henrik Johansen <[hidden email]>:
ifCurtailed: only unwinds if an error/termination occured, so that would mean not signalling the semaphore when everything goes as planned, and we leave the critical section...

I not suppose to replace #ensure: with #ifCurtailed:. I think about:

signalRequired := false.
[
[signalRequired := true.
self wait] ifCurtailed: [signalRequired := false].
blockValue := mutuallyExcludedBlock value
] ensure: [signalRequired ifTrue: [self signal]].
^blockValue

123