On Tue, Jan 5, 2016 at 1:39 AM, Denis Kudriashov <dionisiydk@gmail.com> 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-semaph... [2] http://www.barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore cheers -ben