This discussion is archived
1 2 Previous Next 15 Replies Latest reply: Dec 27, 2010 6:05 AM by 803888 RSS

Need help to concurrently swap elements in an array using trylock

803888 Newbie
Currently Being Moderated
Hi all,

First of all this is a college question and I've already posted my assignment I'm just looking for an answer to why I have a problem for my own experience.

I had to write a simple program that allows 2+ threads to swap elements in an array while preventing deadlock, I used the code shown below but I kept getting the following error while the program was executing. I'm guessing from what I've read online that the problem is with one of the threads obtaining a lock when the array index was already locked.
Exception in thread "Thread-1" java.lang.IllegalMonitorStateException
     at java.util.concurrent.locks.ReentrantLock$Sync.tryRelease(Unknown Source)
     at java.util.concurrent.locks.AbstractQueuedSynchronizer.release(Unknown Source)
     at java.util.concurrent.locks.ReentrantLock.unlock(Unknown Source)
     at ShuffleBase.swap(ShuffleBase.java:45)
     at Shuffle.run(Shuffle.java:18)
     at java.lang.Thread.run(Unknown Source)
My submitted code is below can anyone give me some pointers as to where I went wrong.
import java.util.concurrent.locks.*;
class ShuffleBase {

     
     ReentrantLock [] l;
     int [] data;
        int x;
     
     public ShuffleBase(int [] d){
          x=0;
          data=d;
          l = new ReentrantLock[d.length];
          while (x!=data.length)
          {
               l[x]=new ReentrantLock();
               
               x++;
          }
     }
     
     public void swap(int a, int b) {
             // If a and b reference to different indexes swap else ignore
             if(a!=b)
             { 
                  try{           
                      if(l[a].tryLock() && l.tryLock())
                    {
                         int temp=data[a];
                         
                         data[a]=data[b];
                         
                         data[b]=temp;
                    }
                    
               }
          finally{l[a].unlock();
               l[b].unlock();
               }
          }
          
          }
     
     public void display(){
          System.out.println("The array when swapped");
          for(int j=0; j<data.length;j++)
          {
               System.out.print(data[j]+", ");
          }
          
          
     }
          

}

class Shuffle implements Runnable{
     
     ShuffleBase b;
     public Shuffle(ShuffleBase c){
          b=c;
     }
     
     
     public void run(){
          int k=0;
          int z = b.data.length;
          
      while(k!=b.data.length)
          {
               int x = (int)(0+z*Math.random());
               int y =(int)(0+z*Math.random());
                b.swap(x,y);
                k++;
          }
     }

     
}
All help and pointers greatly appreciated.

Edited by: 800885 on Dec 16, 2010 7:55 AM
  • 1. Re: Need help to concurrently swap elements in an array using trylock
    800268 Expert
    Currently Being Moderated
    If tryLock() fails you still unlock it. See the documentation:
    http://download.oracle.com/javase/6/docs/api/java/util/concurrent/locks/ReentrantLock.html
  • 2. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    Hi Walter,

    Pardon my ignorance but are the trylock() not unlocked as show in the code for example.
       try{           
                          if(l[a].tryLock() && l.tryLock())
                        {
                             int temp=data[a];
                             
                             data[a]=data[b];
                             
                             data[b]=temp;
                        }
                   }
              finally{l[a].unlock();
                   l[b].unlock();
                   }


    I can't see where else this can be placed, even from reading the documentation.



    Thanks
  • 3. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    Hi I've changed the method code to the following but I'm not sure if its preventing deadlock.

    I'll have a read of the documentation to see if I can test for this.
         public void swap(int a, int b) {
                 // If a and b reference to different indexes swap else ignore
                 if(a!=b)
                 {            
                      if(l[a].tryLock() && l.tryLock())
                        {
                             try{

                                  int temp=data[a];
                             
                                  data[a]=data[b];
                             
                                  data[b]=temp;
                             }
                             finally{l[a].unlock();
                                       l[b].unlock();
              }
                             

                   }// EOD OF INNER IF
                   
              }
              else{;}
              
              }/


    Thanks for the help
  • 4. Re: Need help to concurrently swap elements in an array using trylock
    800268 Expert
    Currently Being Moderated
    What happens if locks[ a ].tryLock() succeeds but locks[ b ].trylock() fails? For example thread X swaps 0-1 and thread Y swaps 1-0 and both threads succeed in locks[ a ].trylock().
  • 5. Re: Need help to concurrently swap elements in an array using trylock
    804650 Journeyer
    Currently Being Moderated
    else{;}
    ARRRRGGGGH!

    My eyes, they burn.
  • 6. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    else{;}

    Favorite syntax of my lecturer.

    Edited by: 800885 on Dec 16, 2010 1:54 PM
  • 7. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    Hi Walter

    Have to admit I understand the premise of what your saying but I don't know how to enforce this.
  • 8. Re: Need help to concurrently swap elements in an array using trylock
    804650 Journeyer
    Currently Being Moderated
    800885 wrote:
    else{;}

    Favorite syntax of my lecturer.
    Then your lecturer should be spanked severely. Unless he/she would like that.
  • 9. Re: Need help to concurrently swap elements in an array using trylock
    800381 Explorer
    Currently Being Moderated
    800885 wrote:
    Hi I've changed the method code to the following but I'm not sure if its preventing deadlock.

    I'll have a read of the documentation to see if I can test for this.
         public void swap(int a, int b) {
                 // If a and b reference to different indexes swap else ignore
                 if(a!=b)
                 {            
                      if(l[a].tryLock() && l.tryLock())
                        {
                             try{

                                  int temp=data[a];
                             
                                  data[a]=data[b];
                             
                                  data[b]=temp;
                             }
                             finally{l[a].unlock();
                                       l[b].unlock();
              }
                             

                   }// EOD OF INNER IF
                   
              }
              else{;}
              
              }/


    Thanks for the help
    Multiple problems here. 1.  You're unlocking both locks even though you're not guaranteed to actually lock both. 2.  Since you're not returning any status if any of the lock attempts fails, the caller never knows if the swap is done or not. Avoiding deadlocks is easy, because there are only two ways to get a deadlock:  lock escalation (i.e., try to change a read lock to a write lock), and disparate lock order. This is better, although I'm not sure if it will prevent deadlocks if 3 or more threads try to lock three or more of the same elements:
    public void swap( int a, int b )
    {
    int temp;

    if ( a == b ) return;

    // make sure we lock lowest-indexed lock first
    // to avoid deadlocks
    if ( b < a )
    {
    temp = b;
    b = a;
    a = temp;
    }

    // if we're not passing any status back some way,
    // we have to use lock() and not trylock()
    if ( l[ a ].lock() )
    {
    try
    {
    if ( l[ b ].lock() )
    {
    try
    {
    temp = data[ a ];
    data[ a ] = data[ b ];
    data[ b ] = temp;
    }
    finally
    {
    l[ b ].unlock();
    }
    }
    }

    finally
    {
    l[ a ].unlock();
    }
    }

    return;
    }
  • 10. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    Hi thanks for your post sorry for delay in replying my Internet has been down for the last few days thanks to the weather over here.

    I'll have a look at what you've posted and about amending what I've written to test for the trylock status.


    Thanks again
  • 11. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    Hi

    OK this is what I have done so far after looking at some reading material on the web. It works 99% of the time in that only once in ten executions do I get the error mentioned in my first post.
    At times it appears that both threads get a lock on either both elements or one thread gets the lock on both elements and the other thread get a lock on one of the elements, causing the error on trying to unlock.
    import java.util.concurrent.locks.*;
    class ShuffleBase {
    
         
         ReentrantLock [] l;
         int [] data;
        int x;
         ReentrantLock lock1;
         ReentrantLock lock2;
         
         public ShuffleBase(int [] d){
              x=0;
              data=d;
              l = new ReentrantLock[d.length];
              while (x!=data.length)
              {
                   l[x]=new ReentrantLock();
                   
                   x++;
              }
         }
         
         public boolean lockedIndex(int a, int b){
              
                Boolean lockA = false;
                
                Boolean lockB = false;
                
                try{
                     lockA = lock1.tryLock();
                     
                     lockB = lock2.tryLock();
                }finally{
                     
                     if (!(lockA && lockB))
                     {
                          
                          if(lockA){
                                    
                                            lock1.unlock();
                               
                                       }
    
                          if (lockB){
                               
                                             lock2.unlock();
                          }
                          
                          
                     }// end of IF ! lockA & lockB
                }
                
              return lockA && lockB;
              
         }
         
         
         public void swap(int a, int b){
                 
              lock1 = l[a];
               lock2=l;
              if(a!=b)
              {
                   if(lockedIndex(a,b))
                        {
                             try{
                                  int temp=data[a];
                             
                                  data[a]=data[b];
                             
                                  data[b]=temp;
                             
                                  }finally{
                        lock1.unlock();
                        lock2.unlock();
    }
                        }
                   
                   else{System.out.println("Couldn't lock");}     
                   
              }//End of outer if
              
              }//EOF Method
         
         public void display(){
              System.out.println("The array when swapped");
              for(int j=0; j<data.length;j++)
              {
                   System.out.print(data[j]+", ");
              }
              
              
         }
              

    }



     class Shuffle implements Runnable{
         
         ShuffleBase b;
         public Shuffle(ShuffleBase c){
              b=c;
         }
         
         
         public void run(){
              int k=0;
              int z = b.data.length;
              
          while(k!=b.data.length)
              {
                   int x = (int)(0+z*Math.random());
                   int y =(int)(0+z*Math.random());
                   try{
                        Thread.sleep(100);
                   }catch(InterruptedException e){}
                    b.swap(x,y);
                    k++;
              }
         }
    
         
    }
    Thanks for all the help and Happy New Year.

    Edited by: 800885 on Dec 27, 2010 5:05 AM
  • 12. Re: Need help to concurrently swap elements in an array using trylock
    Kayaman Guru
    Currently Being Moderated
    800885 wrote:
    It works 99% of the time in that only once in ten executions do I get the error mentioned in my first post.
    Then it would work 90% of the time.
    At times it appears that both threads get a lock on either both elements or one thread gets the lock on both elements and the other thread get a lock on one of the elements, causing the error on trying to unlock.
    Well, this is a solvable problem. Aren't you going to try to make it work correctly?
  • 13. Re: Need help to concurrently swap elements in an array using trylock
    803888 Newbie
    Currently Being Moderated
    Yep I was hoping that I could get some insight into what could be a solution to the error.

    Thanks for spotting my % typo anyway.
  • 14. Re: Need help to concurrently swap elements in an array using trylock
    Kayaman Guru
    Currently Being Moderated
    One thing that might help is if you try to lock the lower index first.

    So if thread 1 is trying to lock 3 and 7 and thread 2 is trying to lock 7 and 3, both can succeed in the first lock, but fail on the second one.
    If you re-arrange them so the lower index is locked first, that can't happen.
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points