Geek Answers Handbook

Efficient independent synchronized blocks?

I have a scenario where at some points in my program a thread needs to update several common data structures. Each data structure can be safely updated in parallel with any other data structure, but each data structure can only be updated one stream at a time. A simple, naive way that I expressed in my code:

synchronized updateStructure1();
synchronized updateStructure2();
// ...

This seems inefficient because if multiple threads try to update structure 1, but no thread tries to update structure 2, they all block the wait for a lock that protects structure 1, while the lock for structure 2 does not break.

Is there a “standard” way to fix this? In other words, is there a standard thread primitive that tries to update all structures in a cyclic way, blocks only if all locks are taken and returns when all structures are updated?

This is a somewhat linguistic question, but in case it helps, the language I use is D.

+5
source share
6 answers

I do not know if there is a standard way to do this. However, I would do it something like this:

do
{
    if (!updatedA && mutexA.tryLock())
    {
        scope(exit) mutexA.unlock();
        updateA();
        updatedA = true;
    }

    if (!updatedB && mutexB.tryLock())
    {
        scope(exit) mutexB.unlock();
        updateB();
        updatedB = true;
    }
}
while (!(updatedA && updatedB));

Some clever metaprogramming could probably shorten the repetition, but I leave it as an exercise for you.

+1
source

, , , , . . , .

langauges , ( ).

+2

, , , ?

.

public Object lock1 = new Object; // access to resource 1 
public Object lock2 = new Object; // access to resource 2

updateStructure1() {
   synchronized( lock1 ) {
      ...
   }
}

updateStructure2() {
   synchronized( lock2 ) {
     ...
   }
}
+1

, , .

, , , - . , . :

work = unshared list of objects that need updating
while work is not empty:
    found = false
    for each obj in work:
        try locking obj
        if successful:
            remove obj from work
            found = true
            obj.update()
            unlock obj
    if !found:
        // Everything is locked, so we have to wait
        obj = randomly pick an object from work
        remove obj from work
        lock obj
        obj.update()
        unlock obj

, , , , . -, . , , .

, , , try, . , , , , , .

0

"" , . , - ThreadGroup, Swarm, "" , , , , , . , .

: D concurrency, . . ( concurrency.) , , . - , !

import  core.thread,
        core.sync.mutex,
        std.c.stdio,
        std.stdio;

class Swarm{
    ThreadGroup group;
    Mutex mutex;
    auto numThreads = 1;
    void delegate ()[int] jobs;
    this(void delegate()[int] aJobs, int aNumThreads){
        jobs = aJobs;
        numThreads = aNumThreads;
        group = new ThreadGroup;
        mutex = new Mutex();
    }
    void runBlocking(){
        run();
        group.joinAll();
    }
    void run(){
        foreach(c;0..numThreads)
            group.create( &swarmJobs );
    }
    void swarmJobs(){
        void delegate () myJob;
        do{
            myJob = null;
            synchronized(mutex){
                if(jobs.length > 0)
                    foreach(i,job;jobs){
                        myJob = job;
                        jobs.remove(i);
                        break;
                    }
            }
            if(myJob)
                myJob();
        }while(myJob)
    }
}
class Jobs{
    void job1(){
        foreach(c;0..1000){
            foreach(j;0..2_000_000){}
            writef("1");
            fflush(core.stdc.stdio.stdout);
        }
    }
    void job2(){
        foreach(c;0..1000){
            foreach(j;0..1_000_000){}
            writef("2");
            fflush(core.stdc.stdio.stdout);
        }
    }
}
void main(){
    auto jobs = new Jobs();
    void delegate ()[int] jobsList = 
         [1:&jobs.job1,2:&jobs.job2,3:&jobs.job1,4:&jobs.job2];
    int numThreads = 2;
    auto swarm = new Swarm(jobsList,numThreads);
    swarm.runBlocking();
    writefln("end");
}
0

There is no standard solution, but rather a class of standard solutions depending on your needs.

http://en.wikipedia.org/wiki/Scheduling_algorithm

0
source

More articles:


All Articles