[alg] semafoor en oneindig aantal vergunningen

[Alarmnummer]

Ik heb het volgende probleem. Ik heb een object dat in zich een reader heeft. Iedereen mag deze reader gebruiken (de Reader is thread safe). Maar zo nu en dan moet er een nieuwe reader opgebouwd worden (de ander is verouderd) en hiervoor moet ik eerst ervoor zorgen dat iedereen die reader weer terug geeft. Daarna mag ik die reader pas closen (als ik hem close terwijl hij in gebruik is treden er exceptions op).

Op het moment dat iedereen die reader heeft terug gegeven, ga ik wat herindexatie werk doen.. een nieuwe reader aanmaken... en deze weer vrijgeven.

Ok.. tot zover wat ik wil.

Wat heb ik bedacht?

code:

private Reader reader;
private Semaphore readersAvailableSemaphore = new Semaphore(0);

...init methode waardoor readersAvailableSemaphore wordt gezet. 

Reader acquireReader()throws InterruptedException{
     readersAvailableSemaphore.acquire();
     return reader; 
}

void releaseReader(){
    readersAvailableSemaphore.release();
}

void indexeren(){
     //eis alle vergunningen op
     readersAvailableSemaphore.acquireAll();

      ... voer bewerkingen uit op de reader.

     reader.close();

     reader = new Reader(...);
 
     //maak de reader weer beschikbaar door oneindig 
     //aantal vergunningen klaar te leggen
     readersAvailableSemaphore.release(Integer.MAX_INTEGER)
}

In principe gaat dit goed, maar ik zit een beetje in mijn maag met die oneindig aantal vergunningen. Gewoonlijk heb ik een beperkt aantal vergunningen en dan klopt het wel... maar ik ben niet helemaal blij met deze opzet. En verder zijn de volgende operaties denk ik ook vrij duur (ivm oneindig aantal):
readersAvailableSemaphore .release(Integer.MAX_INTEGER)
en
readersAvailableSemaphore .acquireAll();

Ik kan verder wel een constructie bedenken met meerdere synchronisatie bouwstenen, maar de complexiteit neemt daardoor erg toe (en daar ben ik nooit blij mee). Mijn vraag is of er niet een beter synchronisatie bouwsteen is dan deze semafoor. (Misschien een lazy semafoor)

[ Voor 16% gewijzigd door Alarmnummer op 07-01-2005 10:11 ]

[De Cowboy]

Is een mutex over een getal die bij houdt hoeveel threads gebruik maken, en een bool die bijhoudt of het object nog mag worden gebruikt niet iets ? Het zou weinig geheugen gebruiken, maar of het snel is...

[Alarmnummer]

De Cowboy schreef op vrijdag 07 januari 2005 @ 10:35:
Is een mutex over een getal die bij houdt hoeveel threads gebruik maken, en een bool die bijhoudt of het object nog mag worden gebruikt niet iets ? Het zou weinig geheugen gebruiken, maar of het snel is...

Het probleem van jouw oplossing is de informatie wel thread-safe wordt weggeschreven. Maar dat je niet kan slapen op bv alle-vergunningen-zijn-weer-terug.

[Verwijderd]

Wanneer je toch al een oneindig aantal vergunningen uit wilt kunnen delen, waarom dan niet gewoon een tellertje op 0 zetten en die ophogen bij elke semaphore die aangevraagd wordt? Dan weet je precies hoeveel je er terug moet krijgen van de clients.

[De Cowboy]

Pseudocode:

code:

GetReader()
{
    reader = null;
    While (reader == null)
    {
        lock();
        if (!bIsLocked)
        {
            instanceCount++;
            reader = this;
        }
        unlock();
    }
}



ReleaseReader()
{
    lock();
    instanceCount--;
    unlock();       
}

VerversReader()
{
    lock();
    bIsLocked = true;
    unlock();
    bNoInstances = false;
    while (!bNoInstances)
    {
        lock();
        if (InstanceCount == 0)
        {
            bNoInstances = true;
        }
        unlock();
    }

    //doeiets
    
    lock();
    bIsLocked = false;
    unlock();
}

Volgens mij zijn bij //doeiets alle instances weer ingeleverd, of zie ik nu iets heel doms over het hoofd?

edit: is dus uitwerking wat persoon boven mij perfect uitlegt

[ Voor 6% gewijzigd door De Cowboy op 07-01-2005 12:17 ]

[Alarmnummer]

Volgens mij creeer je door die while lussen een busy wait...

[De Cowboy]

Volgens mij heb je gelijk, zou het met alleen mutexen kunnen ?

code:

GetReader()
{
    lock(ververs);
    lock(count);
    instanceCount++;

    reader = this;

    if (instanceCount == 1)
    {
         lock(inUse);
    }

    unlock(count);
    unlock(ververs);
}

ReleaseReader()
{
    lock(count);

    instanceCount--;
    if instanceCount == 0)
    {
         unlock(inUse);
    }

    unlock(count);        
}

VerversReader()
{
    lock(ververs);
    lock(inUse);
    //doe iets
    unlock(inUse);
    unlock(ververs);
}

[Infinitive]

Ik denk dat je de semaphoor op een verkeerde manier gebruikt. Je gebruikt een semaphoor om een beperkt aantal processen toegang te geven tot een gedeelde resource. Wat jij wilt is iedereen toegang geven en op het moment dat niemand toegang heeft wat operaties uitvoeren.

Voordat ik verder ga: als je resource druk gebruikt wordt kan het heel goed voorkomen dat er altijd wel iemand mee bezig is. Dat komt de situatie nooit voor dat je kan gaan herindexeren. Dat kan je echter oplossen door bij de acquire processen in de wacht te gooien als er al een tijdje geen herindexatie gedaan is. Aan het einde van de herindexatie geef je eventueel wachtende processen weer vrij.

Maar goed, nu jouw echte probleem. Dat kan je volgens mij oplossen met een telletje en een wait/notify mechanisme. Bij elke acquire verhoog je het tellertje. Bij elke release verlaag je deze weer. Zodra de teller 0 is doe je een notify. Het herindexatieproces doet voordat hij begint een wait. Met deze constructie wordt een herindexatie alleen via het wait/notify proces gestart nadat een reader wordt vrijgegeven en er geen readers meer in gebruik zijn. Dat heeft als side effect dat je herindexatie niet continue aan het runnen is als er geen readers in gebruik zijn.

Bovenstaande kan je met standaard monitor support in java implementeren.

[Alarmnummer]

De Cowboy schreef op vrijdag 07 januari 2005 @ 13:15:
Volgens mij heb je gelijk, zou het met alleen mutexen kunnen ?

Vast wel Maar dan krijg je dus meerdere synchronisatie bouwstenen en dat wil ik dus verhinderen. Code wordt dan erg slecht te lezen en ik heb liever 1 bouwsteen waaruit het gedrag in 1 keer af te lezen valt.

UnboundedSemaphore bv.

[Zoijar]

Volgens mij werkt het sowieso niet, omdat aquireAll waarschijnlijk gewoon alle uitstaande permits opeist, en niet alle mogelijke. Stel dus je begint met 100, 3 threads openen een reader, dan staat de semaphore op 97, dan aquireAll je in indexeren(), dan gaat de semaphore naar 0. De volgende thread die een reader wil blocked, maar de andere draaien nog.

Je hebt conditie variabelen nodig, ik weet niet hoe dat zit in java. Dit werkt volgens mij:

code:

semaphore s(1);
conditionvar cv(0);

reader() {
   s.aquire(); // see if we can start, else wait until we can
   cv.increment(); // one more reader active. must be between aquire and release
   s.release(); // allow new readers to be started
}

~reader() {
   cv.decrement();
}

indexeren() {
   s.aquire(); // avoid new readers to be started, let them wait
   cv.WaitForCondition(0);

  // do work

   s.release();
}

Die conditie var (atomic) increment moet tussen de aquire/release staan. Zo niet kan er het volgende gebeuren:

(1e) reader aquired semaphore, released, en wordt dan onderbroken
indexeren aquired semaphore
indexeren ziet dat cv == 0, en gaat processen
reader increment cv en gaat draaien... bad things happen

(oh en die semaphore moet "fair" zijn, zodat bij veel readers, je indexeren() functie ook een kans krijgt)

[ Voor 5% gewijzigd door Zoijar op 07-01-2005 14:00 ]

[Alarmnummer]

Infinitive schreef op vrijdag 07 januari 2005 @ 13:20:
Ik denk dat je de semaphoor op een verkeerde manier gebruikt. Je gebruikt een semaphoor om een beperkt aantal processen toegang te geven tot een gedeelde resource.

Het is idd een iets andere benadering maar als je een semafoor puur ziet als een vergunning verstrekker valt het best mee. Ipv 10 of 40 vergunningen, heb ik er iets meer. De vraag is dus waarom er zo`n groot verschil tussen een normaal en een een 'oneindig' aantal vergunningen zou moeten bestaan. Het concept blijft hetzelfde.

Wat jij wilt is iedereen toegang geven en op het moment dat niemand toegang heeft wat operaties uitvoeren.

Ik wil niet wachten op de gebruikers dat die reader weer terug is gegeven. Want als er veel verkeer is kan het voorkomen dat de situatie zich gewoon niet voortdoet. De indexer moet dus kunnen ingrijpen en zeggen van.. heej pipo`s.. vergunningen inleveren.. perfect.. maar voorlopig gaan er geen vergunningen meer uit te deur. Heb je wel een nodig? Geen probleem.. ga maar wachten.. ik geef je wel een signaal als het zover is.

Voordat ik verder ga: als je resource druk gebruikt wordt kan het heel goed voorkomen dat er altijd wel iemand mee bezig is. Dat komt de situatie nooit voor dat je kan gaan herindexeren.

pcies.

Dat kan je echter oplossen door bij de acquire processen in de wacht te gooien als er al een tijdje geen herindexatie gedaan is. Aan het einde van de herindexatie geef je eventueel wachtende processen weer vrij.

Dit volg ik niet helemaal.

Maar goed, nu jouw echte probleem.

hehe...

Dat kan je volgens mij oplossen met een telletje en een wait/notify mechanisme. Bij elke acquire verhoog je het tellertje. Bij elke release verlaag je deze weer. Zodra de teller 0 is doe je een notify.

Het herindexatieproces doet voordat hij begint een wait. Met deze constructie wordt een herindexatie alleen via het wait/notify proces gestart nadat een reader wordt vrijgegeven en er geen readers meer in gebruik zijn. Dat heeft als side effect dat je herindexatie niet continue aan het runnen is als er geen readers in gebruik zijn.

In deze situatie ga je ervan uit dat de indexer mag gaan runnen als er niemand bezig is. Ik wil dat de indexer er zelf voor zorgt dat er niemand mee bezig gaat.

Bovenstaande kan je met standaard monitor support in java implementeren.

Ik sluit liever dit soort functionaliteit op in 1 object waaruit ook meteen duidelijk is wat de bedoeling is. Anders krijg je van die rommelige classes imho en dat is met concurrency control vaak... minder leuk.

[Alarmnummer]

Zoijar schreef op vrijdag 07 januari 2005 @ 13:58:
Volgens mij werkt het sowieso niet, omdat aquireAll waarschijnlijk gewoon alle uitstaande permits opeist, en niet alle mogelijke.

Yep.. De indexer zou idd het totale aantal vergunningen moeten terug vragen en niet het aantal vergunningen dat nog beschikbaar is. Effectief gezien heeft de foute oplossing als gevolg dat er nog steeds aantalvergunningen-aantalvergunningenuitgeleend = x. X aantal vergunningen gebruikt mogen worden en niet 0.

Stel dus je begint met 100, 3 threads openen een reader, dan staat de semaphore op 97, dan aquireAll je in indexeren(), dan gaat de semaphore naar 0. De volgende thread die een reader wil blocked, maar de andere draaien nog.

Yep... dat was idd een fout..

Je hebt conditie variabelen nodig, ik weet niet hoe dat zit in java. Dit werkt volgens mij:

http://gee.cs.oswego.edu/...l/concurrent/CondVar.html

code:

semaphore s(1);
conditionvar cv(0);

reader() {
   s.aquire(); // see if we can start, else wait until we can
   cv.increment(); // one more reader active. must be between aquire and release
   s.release(); // allow new readers to be started
}

~reader() {
   cv.decrement();
}

indexeren() {
   s.aquire(); // avoid new readers to be started, let them wait
   cv.WaitForCondition(0);

  // do work

   s.release();
}

Die conditie var (atomic) increment moet tussen de aquire/release staan. Zo niet kan er het volgende gebeuren:

(1e) reader aquired semaphore, released, en wordt dan onderbroken
indexeren aquired semaphore
indexeren ziet dat cv == 0, en gaat processen
reader increment cv en gaat draaien... bad things happen

(oh en die semaphore moet "fair" zijn, zodat bij veel readers, je indexeren() functie ook een kans krijgt)

Ik zal er straks eens goed naar kijken. Ik had me gisteren al ff gekeken naar de CondVar van Doug Lea maar de semafoor leek me de meest eenvoudige oplossing. (Afgezien van narigheid)

[Alarmnummer]

Ik heb snel even iets in elkaar gezet. Ik wil namelijk al dit soort gedrag kunnen onderbrengen in 1 object zodat ik in mijn 'core' objecten niets meer terug zie van concurrency... afgezien van een goed concurrency bouwsteen.

code:

class ObjectContainer{
    
    private Lock            _lock = new ReentrantLock();
    
    private Condition       _sharedCond  = lock.newCondition();     
    private int             _shareCount = 0;
        
    private Condition       _availableCond = lock.newCondition(); 
    private boolean         _available;     
        
    private Object _object;
        
    public ObjectContainer(Object o){
        _objectAvailable = true;
        _object = o;
    }
    
    Object acquireObject()throws InterruptedException{      
        lock.lock();
        
        try{
            while(!_available)
                _availableCond.wait();
        
            _shareCount++;
            return _object;
        }finally{
            lock.release();
        }
    }
    
    void returnObject(){
        lock.lock();
        
        try{
            _shareCount--;
            
            if(_shareCount == 0)
                _sharedCond.notify();               
        }finally{
            lock.release();
        }
    }
    
    Object acquireForUpdate(){
        lock.lock();
        
        try
        {
            _available = false;
            _availableCond.notify();
            
            while (_shareCount >0) 
                _sharedCond.await();

                
            return _object; 
        }finally{
            lock.release();
        }
    }
    
    void update(Object newObject){
        lock.lock();
        
        try{
            _object = object;
            _objectAvailable = true;
            _objectAvailableCond.notify();
        }finally{
            lock.release();
        }
    }
}

Moet nog ff betere naam hebben en het object is nog niet save..

[Zoijar]

Ik zie behoorlijk wat potentiele fouten volgens mij... vnl met die lock. Stel bv dat je aquireForUpdate() aanroept, vervolgens wordt er returnObject() aangeroepen, die locked het object en wait op de conditie var. Vervolgens wordt update() aangeroepen, en die hangt in ook in de lock...deadlock. Sowieso zou ik geen Lock gebruiken bij iets dat mogelijk lang kan duren, lock is busy-wait toch?

[Alarmnummer]

Zoijar schreef op vrijdag 07 januari 2005 @ 15:08:
Ik zie behoorlijk wat potentiele fouten volgens mij...

Ojee..

vnl met die lock. Stel bv dat je aquireForUpdate() aanroept, vervolgens wordt er returnObject() aangeroepen,

Ik neem aan dat je bedoelt :return _object?

die locked het object en wait op de conditie var.

Ik neem aan dat je bedoelt:

while (_shareCount >0)
_sharedCond.await();

Vervolgens wordt update() aangeroepen, en die hangt in ook in de lock...deadlock.

Je moet wel van dezelfde thread updaten als je de acquire for update aanroept. En bij java is het niet mogelijk dat je door een herhaalde lock van 1 thread in een deadlock situatie terecht komt.

code:

synchronized void a(){
    b();
}

synchronized b(){
     c();
}

synchronized c(){
    System.out.println("bla");
}

Dit levert in Java geen problemen op. En ook niet als je de monitor (het object waarin die a,b,c zit) wegrefactored naar een ander object.

Sowieso zou ik geen Lock gebruiken bij iets dat mogelijk lang kan duren, lock is busy-wait toch?

Nope:

Condition factors out the Object monitor methods (wait, notify and notifyAll) into distinct objects to give the effect of having multiple wait-sets per object, by combining them with the use of arbitrary Lock implementations. Where a Lock replaces the use of synchronized methods and statements, a Condition replaces the use of the Object monitor methods.

[ Voor 12% gewijzigd door Alarmnummer op 07-01-2005 15:33 ]

[Zoijar]

Die "_lock" is voor alle threads toch? Het ging me om regels 22/23, dat je hangt in een loop (een wait()) terwijl je je lock nog vast hebt.Het stukje code dat die wait() moet notifyen (regels 69) kan nooit draaien, omdat die methode ook dat lock nodig heeft. Dat zijn twee verschillende threads, die hetzelfde lock willen. Dat bedoelde ik.

Maar je kan ook je lock niet vrijgeven voordat je de wait() doet (regel 22), want dan is het mogelijk dat de andere thread draait, en toevallig net available weer op true zet en een notify stuurt. Vervolgens doet de oorsponkelijke thread die wait() (regel 23), en krijgt nooit een notify. Vandaar dat ik een semaphore gebruikte, zodat er geen 'lost wakeup' is.

Ik lees net idd dat Condition dat al voor je regelt, dat wist ik niet, dan is het dus geen probleem In dat geval ziet het er goed uit. Zal nog een keer kijken of ik iets zie, het is zo makkelijk om een subtiel foutje te maken in dit soort code...

Ja ok, lijkt me goed. Net even Condition reference gelezen; dat ding is echt handig Doet eigenlijk alles voor je. Ook dat je na wakeup gegarandeert weer dat lock in handen hebt, en bij sleep het atomisch vrijgegeven wordt en suspended. Zeer nuttig. (en dat waren nou juist precies die potentiele fouten die ik zag...sorry )

[ Voor 18% gewijzigd door Zoijar op 07-01-2005 15:52 ]

[Alarmnummer]

Zoijar schreef op vrijdag 07 januari 2005 @ 15:41:
Die "_lock" is voor alle threads toch? Het ging me om regels 22/23, dat je hangt in een loop (een wait()) terwijl je je lock nog vast hebt.Het stukje code dat die wait() moet notifyen (regels 69) kan nooit draaien, omdat die methode ook dat lock nodig heeft. Dat zijn twee verschillende threads, die hetzelfde lock willen. Dat bedoelde ik.

Daar heb je normaliter gelijk in. Maar bij java is het anders:

void await()
throws InterruptedException
Causes the current thread to wait until it is signalled or interrupted.

The lock associated with this Condition is atomically released and the current thread becomes disabled for thread scheduling purposes and lies dormant until one of four things happens:

Some other thread invokes the signal() method for this Condition and the current thread happens to be chosen as the thread to be awakened; or
Some other thread invokes the signalAll() method for this Condition; or
Some other thread interrupts the current thread, and interruption of thread suspension is supported; or
A "spurious wakeup" occurs
In all cases, before this method can return the current thread must re-acquire the lock associated with this condition. When the thread returns it is guaranteed to hold this lock.

Ik lees net idd dat Condition dat al voor je regelt, dat wist ik niet, dan is het dus geen probleem In dat geval ziet het er goed uit. Zal nog een keer kijken of ik iets zie, het is zo makkelijk om een subtiel foutje te maken in dit soort code...

Ja ok, lijkt me goed. Net even Condition reference gelezen; dat ding is echt handig Doet eigenlijk alles voor je. Ook dat je na wakeup gegarandeert weer dat lock in handen hebt, en bij sleep het atomisch vrijgegeven wordt en suspended. Zeer nuttig.

Ik en ook zeer blij met de concurrency library van Doug Lea (die standaard in jdk 1.5/5.0 zit). Ik probeer me er goed in te verdiepen.. maar ik heb nog regelmatig dat ik 'terug naar start' moet

[Infinitive]

Wat ik me zomaar ineens te binnen schoot: ben je met een single-writer, multiple-reader lock niet gewoon klaar? Of wordt dat niet aangeboden in Doug Lea's library?

... enige seconden denktijd later...

Ja, wat jij aan het implementeren bent is een single-writer, multiple-reader synchronisatie-primitieve. Als dat er nog niet is, dan heb je iig nu de naam ervoor

[ Voor 40% gewijzigd door Infinitive op 07-01-2005 16:12 ]

[Alarmnummer]

Infinitive schreef op vrijdag 07 januari 2005 @ 16:08:
Wat ik me zomaar ineens te binnen schoot: ben je met een single-writer, multiple-reader lock niet gewoon klaar? Of wordt dat niet aangeboden in Doug Lea's library?

Die boef, loopt ie mij na te apen:
http://gee.cs.oswego.edu/...urrent/ReadWriteLock.html

Maar zo`n hoger concurrency bouwsteen is veel beter te begrijpen dan het gepiel met een hele zooi lagere. De oplossing is veel helderer en foutvrijer (als je gebruik kunt maken van herbruikbare bouwstenen)

[ Voor 26% gewijzigd door Alarmnummer op 07-01-2005 16:31 ]