how can you avoid nested synchronization

[Wayne John]

in lock() method we need to check records validity, make sure the record is not deleted before locking it.
I found I can't avoid to use nested synchronization, please read following code , how did you implement your lock method? can you avoid nested synchronization? thanks.

lock(recno) throws RecordnotfoundException{
 
synchronize(lockmap){
   while(locked){
       wait()...
   }
   checkvalidity(recno);
   lockmap.put(recno);
}
 
} 
 
checkvalidity(recno){
   synchronize(raf){
     raf.seek(recno);
    ...
    to check deleted record.
  }
}
 

[Andrew Monkhouse]

Hi Wayne,

While you should always try to avoid nested synchronization, sometimes it is not possible to avoid it totally. As long as you always nest in the same order you should be OK.

But some alternatives for you: You could have a local collection containing the list of deleted records which can only be modified while you own the mutex on lockmap. So you could then just check the deleted record in that collection without ever going to the RAF (although this requires you to read the entire RAF at some point).

Alternatively, within your lock method you could add the lock details to the lockmap and release your mutex on it. Then go and check the validity of the record and, if it is not valid, silently unlock the record.

Regards, Andrew

[Wayne John]

But some alternatives for you: You could have a local collection containing
the list of deleted records which can only be modified while you own the mutex on lockmap.
So you could then just check the deleted record in that collection without ever going to the RAF

Hello Andrew :
thank you for your reply.

acutally I had the same idea before, it's similar with your comments.
but, I don't think I can use lockmap as mutex .I write down the code below,
could you read it and give me some suggestion, I'll really appreciate for it!

solution one, I use deletedRecords as mutex
 
ArrayList deletedRecords;
 
int getReusedRecord(){
 synchronize(deletedRecords){
     if( deletedRecords is empty) return -1
     
     search deletedrecords, 
     get  a reused record number
     remove this record from deltedRecords
     
     return this number
 }
 
}
 
 void addDeletedRecords(int recno){
   synchronize(deletedRecords){
  //adding new record to deletedRecords collection
 deletedRecords.add(new Integer(recno));
   }
 }
void RemoveDeletedRecords(int recno){
  synchronize(deletedRecords){
  //remove a record from deletedRecords collection
  deleteRecords.remove(new Integer(recno))
 
 
   }
 
}
void isDeletedRecord(int recno){
 
   synchronize(deletedRecords){
   return deletedReords.contain(recno);
 
   }
 
}
void deleteRecord(int recno) throws Exception{
    synchronize(raf){
    try{
      .........
      delete a record from  dbfile
   
    } catch(IOException){}
      throws Exception
    }
    }
.............
  //even this record was deleted from dbfile already,but thread could slice out in here, 
  //and another thread could  read this record which has already been deleted.
  // is this a big problem???
  addDeletedRecords(recno);
}
 
void created(String[] data){
   int recno=getReusedRecord();
                   
   synchronize(raf){
    try{
      .........
      writing data to dbfile
   
    } catch(IOException){
   
      call AddDeletedRecords(recno)   
      ------->there is a problem , if IOException raised,
      I have to do a rollback operation to restore recno in deletedRecords,   
      but it's a nest synchronization ! so I changed this method as following..
    }
   }
   
}
 
//version two for created method.  
void created(String[] data){
   int recno=getReusedRecord();
  try{                 
   synchronize(raf){
      .........
      writing data to dbfile
   
   }
 } catch(IOException){
   
      call AddDeletedRecords(recno)  
       ------->I put try catch block outside of synchronize(raf)
      so , this could aovid nest synchronization.
                actually,I'm not very confident about this solution, 
   }
}
 

 
second solution, I still use deletedRecords collection, but I  use raf as mutex
 
ArrayList deletedRecords;
 

void isDeletedRecord(int recno){
 
   synchronize(raf){
   return deletedReords.contain(recno);
 
   }
 
}
 
void deleteRecord() throws Exception{
      synchronize(raf){
         delete record from dbfile...
         ...
         deletedRecords.add(recno)//add recno to deletedRecords collection.
      
      }
}
void created(String[] data){
  // you can see all operations of deletedRecords  will be done in     synchronize(raf) block,
   synchronize(raf){
    try{
      search deletedRecord and get a reused record
      .........
      writing data to dbfile
   
      deletedRecords.remove(recno)// remove this record from deletedRecords  collection
   
   } catch(IOException){
   
      throws Exception ;  
   }
   }
   
}
 

solution one  get better performance, because it doesn't use raf as mutex, so other thread can do read , during 
isDeletedRecord() is called. but 
 
I think solution two is more safe . but with bad performance . do you have any comment about above solutions?
 

another question:
in read() method, we also need to check record validity, like following
 
void read( recno) throws Exception{
     //check if record has been deleted;
     if(isDeletedRecord()){
      throw Exception;
     }
    
    ...........> thread could slice out from here, so this record could be deleted by other thread
    then this thread read a deleted record! is this a matter? it's not dirty read, just stale read ,seems many people just 
    ignore this problem.  or we also need to put isDeletedRecord() into synchronize(raf) block?
    
    
    synchronize(raf){
      doing read process
    
    }
 
}

[ December 14, 2005: Message edited by: Wayne John ]

[Mihai Radulescu]

Hi, John


If you choose to combine the lock mechanism with the IO feature you can land easly to the nested block probelm. This is not so nice but if you know the nest order you can avoid a deadlock.
You can also use the same look for both, but this can be a little bit to much.

An othre way to avoid this is to separate the lock mechanism from the IO features - two seperate classes. In this case you can synchronize separate all the read/write operations.

One more remarc to your last statement

thread could slice out from here, so this record could be deleted by other thread then this thread read a deleted record!

IMHO this is not a real problem. You can see it like this, even if your whole method will be atomic and it always retun the right records is still not enought, after you exit them metohd and you try to use the result (let's say to display it) an other thread can perform a delete. The read provides only a "view" from a specific moment(time), in the next moment the system may change.


Regards,
Mihai.
[ December 16, 2005: Message edited by: Mihai Radulescu ]

[Wayne John]

hello Mihai:
thank you for the reply.
maybe I wrote too much in my last post, could you read my following post and give me an answer . thank you.

void deleteRecord(int recno) throws Exception{
synchronize(raf){
try{ ......... delete a record from dbfile
} catch(IOException){
throws Exception
}
}............. //even this record was deleted from dbfile ,but thread could slice out in here, //and another thread could read this record which has already been deleted. // is this a big problem???

addDeletedRecords(recno);//this function will add one deleted record to arraylist.

}


in read() method, we also need to check record validity,
void read( recno) throws Exception{
//check if record has been deleted;
if(isDeletedRecord()){ throw Exception; }
...........> thread could slice out from here, so this record could be deleted by other thread then this thread read a deleted record! is this a matter? it's not dirty read, just stale read ,seems many people just ignore this problem. or we also need to put isDeletedRecord() into synchronize(raf) block?

synchronize(raf){ doing read process }

}

[Mihai Radulescu]

Hi,

I don't realy understand your question.Can you be a little bit more specific.

Here is what I understant.

Your code snipplets are from your IO layer, by io layer I mean the class for read/search/write ?
If the answer is yes why you don't synchronize with same lock(on instance by example) all the IO methods? In this way delete and create are atomic, this can spare you from a lot of problems(one is nested synchronized blocks).

About the read probelm I already explain in my last post("One more remarc to your last statement ........" ).

I hope this hepl.

Regards,
Mihai
[ December 16, 2005: Message edited by: Mihai Radulescu ]

[Wayne John]

Hello Mihai:
thank you for the reply.
yes,the code snipplets is from IO layer. acutally I write one class called "DBFileAccess" for io processing, the Data class need to call this class to finish read , delete ,update operation.

if I put them into same synchronized block,
that means when I write function isDeletedRcord(), I have to use synchronize(raf){}block again . like this:
public void isDeletedRecord(int recno){
synchronize(raf){
return arraylist.contain(new Integer(recno));

}

}
I think it's low performance , because in data class , all read , update method need to call this method . and in lock() method I also need to call this method, so, the lock method will block file io operation.

if I use arraylist as mutex, when I call isDeletedRecord() method it won't block IO operation. I got confused about this.
Maybe I should listen your suggestion, make the things simple.

[Alex Sharkoff]

Andrew said

While you should always try to avoid nested synchronization, sometimes it is not possible to avoid it totally. As long as you always nest in the same order you should be OK.

I guess we need 1) to determine what objects need to be accessed in a multi-thread safe fashion; 2) and then determine how it can be achieved.
That is what I've got so far:

1. For the logical locking (ie record locking) there is a static lockedRecords map that stores key/value pairs where the key is a record number and a value is a client who has locked it

2. For the physical locking (ie file locking) there is a static dbFile object that provides read/write access to the database file (it delegates read/write tasks to the instance of RAF)

3. For the record cache there is static recValidFlags list in which an element position represents a record number and the actual element is a record validity flag (of byte type, either Data.VALID_RECORD or Data. DELETED_RECORD). The actual number of elements in this list represents a total number of records in the file (both deleted and valid).
recValidFlags is initially populated on the start up (when the database file is chosen by the user) and is then maintained by the Data instances.
Collections.synchronizedList(new ArrayList<Byte>()) method is used to create a List instance used for this cache, which makes access to recValidFlags methods multi-thread safe.
The recValidFlags cache is used for a) checking whether the record exist; b) determining in what position to create a new record.
The recValidFlags cache is modified when a) a new record is created ; b) when a record is deleted

Data instances will synchronize on these three static objects ( ie lockedRecords / dbFile / recValidFlags ) in the following manner:

Data#read(int recNo)

VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synchronization in [I]recValidFlags[/I]


GET Monitor on [I]dbFile[/I] // synchronizing on [I]dbFile[/I]

VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synch in [I]recValidFlags[/I] - [B]nested synchr[/B]

READ Record from [I]dbFile[/I]

RELEASE [I]dbFile[/I] Monitor // end of synchronizing block

Data#create(String[] record)

VALIDATE record


GET Monitor on [I]dbFile[/I] // synchronizing on [I]dbFile[/I]

VERIFY Record IS NOT Duplicate (read record by record and compare with given record)

USE [I]recValidFlags[/I] to DETERMINE Record position  // internal synch in [I]recValidFlags[/I] - [B]nested synchr[/B]

WRITE Record into [I]dbFile[/I]

GET Monitor on [I]recValidFlags[/I] // synch on [I]recValidFlags[/I] - [B]nested synchr[/B]

MODIFY [I]recValidFlags[/I] with new Record validity flag // ([I]recValidFlags#remove[/I] and then [I]recValidFlags#add[/I])

RELEASE [I]recValidFlags[/I] Monitor // end of synch block on [I]recValidFlags[/I]

RELEASE [I]dbFile[/I] Monitor // end of synch block [I]dbFile[/I]

Data#lock(int recNo)

VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synchronization in [I]recValidFlags[/I]


GET Monitor on [I]lockedRecords[/I] // synchronizing on [I]lockedRecords[/I]

WHILE Record IS in [I]lockedRecords[/I] -> WAIT

VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synch in [I]recValidFlags[/I] - [B]nested synchr[/B]

PUT Record into [I]lockedRecords[/I]

RELEASE [I]lockedRecords[/I] Monitor // end of synchronizing block

Data#delete(int recNo)

VERIFY Record IS Locked in [I]lockedRecords[/I]  by the client who has called [I]delete[/I]

// no need to perform any further record validation as the record is locked 
// by the client who's called the delete and therefore this record cannot 
// be modified by anyone else until this client unlocks the record 
// (the client will probably do it after the delete operation)

GET Monitor on [I]dbFile[/I] // synchronizing on [I]dbFile[/I]

UPDATE Record with deleted flag in [I]dbFile[/I]

GET Monitor on [I]recValidFlags[/I] // synch on [I]recValidFlags[/I] - [B]nested synchr[/B]

MODIFY [I]recValidFlags[/I] with the Record's deleted flag // ([I]recValidFlags#remove[/I] and then [I]recValidFlags#add[/I])

RELEASE [I]recValidFlags[/I] Monitor // end of synch block on [I]recValidFlags[/I]

RELEASE [I]dbFile[/I] Monitor // end of synch block [I]dbFile[/I]

All comments are welcome.


[ December 19, 2005: Message edited by: Alex Sharkoff ]