Modifier and Accessor Synchornization
Hi,
This is not what you may think -- it is not about getter and setters, allow me to elaborate. I have a data structure that requires a few modifications to the underlying data and many accesses (M threads add/remove, N threads access).
To achieve concurrency, I am adding two minimalistic locks to synchronize between two thread types. One for when the data structure goes under modification phase (modifyingLock) and one for the count of threads currently accessing the data structure (threadCount).
The premise is allow modifying threads to make modification to data when there is no thread accessing (reading) it. Therefore, it must wait until all the accessing threads are done by verifying whether threadCount is zero or not. Ergo, Access threads can be in two states, either in process of accessing the data or just about to begin searching. In case of former, the accessing thread should be allowed to finish it search and at the end decrement threadCount. If the thread of type N haven't begun accessing the data and see modifyingLock set, they should wait until modifications are perform to data and get notified upon completion. The process should work as following:
Modifying threads (M),
- Before making any modification, M must check to see whether modifyingLock as been set which is an indication another M thread is (OR about to) making modification to the data structure and also check whether any thread of type N is accessing it.
- If either condition is not met, threads of type M must wait until either another thread of type M finishes its task of modification and/or accessing threads of type N are flushed and done with their search (threadCount should be zero).
Accessing threads (N),
- If modifyingLock is not set, they can began accessing the data structure safely knowing thread of type M would not begin its task of modification until all the accessing threads are done.
- And any further new access would be blocked and have to wait until thread M's are done with their task.
Sounds logical but when it comes to the actual implementation, I can clearly see that there are many possible thread locks which I cannot seem to figure how to remedy:
// Partial code of add() method
// modifyingLock is a byte[] of size one
// threadAccessCount is an int[] of size one
synchronized (modifyingLock){
while (modifyingLock[0] != 0 &&
threadAccessCount[0] != 0){
try{
modifyingLock.wait();
}catch (InterruptedException ie){
}
}// end of while loop
modifyingLock[0] = (byte) 1;
// Actual modification to the data structure
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();
}// end of synchronized block
// Partial implementation of accessing method
synchronized (modifyingLock){
while (modifyingLock[0] != 0){
try{
modifyingLock.wait();
}catch (InterruptedException ie){
}
}// end of while loop
}// end of synchronized block
synchronized (threadAccessCount){
threadAccessCount[0]++;
}
// Actual search or read task
synchronized (threadAccessCount){
threadAccessCount[0]--;
if (threadAccessCount[0] == 0){
synchronized (modifyingLock){
modifyingLock.notifyAll();
}
}
}
Now my question, can you come up with any scenario where a deadlock or race condition can occur?
Thank You
# 1
I didn't get beyond paragraph two, but all you need is already written in java.util.concurrent.locks.ReadWriteLock and friends.
ejpa at 2007-7-29 17:17:24 >
# 2
I got a little into paragraph three.
Try reading this link: http://www.catb.org/~esr/faqs/smart-questions.html
# 3
Alright, I thought if I go into details, it would have been easier to follow my design -- guess people have better things to do than reading through a spaghetti code. So allow me to ask a question directly from the code:
// Partial code of add() method
// modifyingLock is a byte[] of size one
// threadAccessCount is an int[] of size one
synchronized (modifyingLock) {
while (modifyingLock[0] != 0 &&
threadAccessCount[0] != 0) { /* (1) */
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
modifyingLock[0] = (byte) 1;
// Actual modification to the data structure
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();
} // end of synchronized block
// Partial implementation of accessing method
synchronized (modifyingLock) {
while (modifyingLock[0] != 0) {
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
} // end of synchronized block
synchronized (threadAccessCount) {
threadAccessCount[0]++;
}
// Actual search or read task
synchronized (threadAccessCount) {
threadAccessCount[0]--; /* (2) */
if (threadAccessCount[0] == 0) {
synchronized (modifyingLock) {
modifyingLock.notifyAll();
}
}
}
Could lines (1) and (2) possibly cause a deadlock? If an accessing thread reaches line (2) and context switch to a modifying thread which eventually gets to line (1), it will block because threadAccessCount is synchronized by the accessing thread.
Now, IF, the accessing thread sees the count reaching zero, its attempt to lock modifyingLock would fail and block. Now both threads are in deadlock. Is there a way to avoid such deadlock?
P.S. I will read on ReadAndWriteLock see if it'll fit into my needs.
Thank You
# 4
Hmm... How about wrapping the last synchronized block with modifyingLock: instead of waiting for the counter reaches zero?
synchronized (modifyingLock) {
synchronized (threadAccessCount) {
threadAccessCount[0]--; /* (2) */
if (threadAccessCount[0] == 0) {
modifyingLock.notifyAll();
}
}
}
And I do not believe I should be worrying about this block:
synchronized (threadAccessCount) {
threadAccessCount[0]++; /* (3) */
}
Because it does not depend on modifyingLock and even if the modifying thread gets to line (1), it'll block until accessing thread exit (3). If the thread switch does not occur for the modifying thread and accessing thread continues down the accessing method, at some point it'll reach the last set of synchronized block and would not be able to enter due to the fact that modifyingLock is acquired by the modifying thread.
I know some of you may be shouting at me for not utilizing concurrency API. Frankly, I haven't studied them and it's long over due and I will but I would like to see if I can get this to work. :)
# 5
Another mistake I had done was not to set the modifyingLock once the modifying thread get a hold of the lock:
synchronized (modifyingLock) {
modifyingLock[0] = 1;
while (threadAccessCount[0] != 0) { /* (1) */
And I just realized that all my effort in synchronizing between accessing and modifying threads means absolutely jack squat because the add and remove methods both rely on the search module. So here's how it can go wrong:
add() { if (has it) {return; } otherwise insert }
remove() {if(has it) {return; } otherwise remove }
By the time each of these methods get their result from the search method, another thread can come remove or insert an item into the data structure and by the time they get to the actual insertion and removal, things can be unstable. I have to actually add the contain portion to the synchronized block:
synchronized (modifyingLock) {
modifyingLock[0] = (byte) 1;
while (threadAccessCount[0] != 0) { /* (1) */
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
if (/* contain */) {
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();
return; /* (4) */
}
///// Actual modification to the data structure /////
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();
} // end of synchronized block
Ok, so I guess my question would be, what will happen if I "return" in the middle of synchronized block (line (4))? Does it release the lock for that object?
# 6
Ok, so apparently "return" does release the lock on the object. I made a couple of mistakes on my last post. Let's see if this version holds:
synchronized (modifyingLock) {
while (threadAccessCount[0] != 0) {
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
if (/* contain */) {
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();
return;
}
modifyingLock[0] = (byte) 1;
///// Actual modification to the data structure /////
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();
} // end of synchronized block
And moving the thread count incrementation to modifyingLock synchronize block:
// Partial implementation of accessing method (contain)
synchronized (modifyingLock) {
while (modifyingLock[0] != 0) {
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
synchronized (threadAccessCount) {
threadAccessCount[0]++;
}
} // end of synchronized block
//// Actual search or read task ////
synchronized (threadAccessCount) {
threadAccessCount[0]--;
if (threadAccessCount[0] == 0) {
synchronized (modifyingLock) {
modifyingLock.notifyAll();
}
}
}
# 7
I haven't wasted my time reading any of your posts after my last post since you either did not follow the link I posted or you did not understand it.
To answer your last, last question: Ok, so I guess my question would be, what will happen if I "return" in the middle of synchronized block (line (4))? Does it release the lock for that object?
Yes, return releases the lock.
# 8
cooper6,
First, I would like to thank you for your response. I am trying my best to follow common sense in posting my questions and replies. Your link is well known and frankly, it has some good points and some very refutable ones. It should not be taken as a general rules of thumb but also not to be ignored.
I always try to be as precise and informative as possible about my problem without dumping 100 lines of code. I stated what I want, the design behind it, and finally a snippet of code addressing how I implemented the design. However, the code introduced some issues that I tried to address and seek help in resolving them.
In mean time, I kept realizing I am bumping into new problems which I tried my best to address and present "possible" solutions. Unfortunately, multi-threading is a difficult subject and even when you believe the problem is resolved, new scenarios come along -- especially for people who do not posses a kind of expertise required to tackle such problems. Multi-thread programs usually don't spew out wrong set of results until perhaps a few months down the road, unexpected reveals its gory face.
Ergo, please forgive me if I ask a general question with regard to the code such as, "Can this cause a deadlock?" I know this can be frustrating but I can list all the possible scenarios and again ask the same question. I understand long posts can be deterrent in getting a help you want because this is not "their" problem but rather "yours." People response is a privilege not a right and frankly, I would brush off if the question does not grab my attention in the first two sentence. But some problems cannot be conceived in simple manners.
Anyway, thank you for your consideration.
# 9
aria_kokoschka,
if your question is still "can you come up with any scenario where a deadlock or race condition can occur?", then in your code there are one race (in terms of JLS 3rd, 17.4.5) and one deadlock.
synchronized (modifyingLock) { // <- (1.1)
while (threadAccessCount[0] != 0) { // <- (1.2)
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
if (/* contain */) {
modifyingLock[0] = (byte) 0;
modifyingLock.notifyAll();// <- (1.3)
return;
}
modifyingLock[0] = (byte) 1;// <- (1.4)
///// Actual modification to the data structure /////
modifyingLock[0] = (byte) 0;// <- (1.5)
modifyingLock.notifyAll();// <- (1.6)
} // end of synchronized block
// --
// Partial implementation of accessing method (contain)
synchronized (modifyingLock) { // <- (2.1)
while (modifyingLock[0] != 0) {// <- (2.2)
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
synchronized (threadAccessCount) { // <- (2.3)
threadAccessCount[0]++;
}
} // end of synchronized block
// <- (2.1.1)
//// Actual search or read task ////
synchronized (threadAccessCount) { // <- (2.4)
threadAccessCount[0]--; /// <- (2.5)
if (threadAccessCount[0] == 0) {
synchronized (modifyingLock) {// <- (2.6)
modifyingLock.notifyAll();
}
}
}
Race.
Let last "reader" thread executed statement 2.5, and then writer checks condition 1.2. Readed is synchronized on threadAccessCount and writer - on modifyingLock, so such scenario is possible. In this case "read (1.2)" of threadAccessCount[0] is not in happens-before ordership with "write (2.5)" in threadAccessCount[0], it is only in happens-before ordership whith point 2.1.1, where modifying lock was released. But this is only "race" by definition, it does not allows writer to write, while reader reads the data (if writer see value greater, than zero, it simply waits. If it see value of zero, then all threads decremented that count and there are no readers). But, if we continue possible execution and assume, that 1.2 see zero value, written by 2.5 (it's last reader by assumption), then writer may procede to execute all write procedure. All this time writer will hold lock, acquired at 1.1 and last reader will be waiting acquisition of that lock at line 2.6 and will get that lock only after writer completes it's activity. This "waiting" for the writer is not necessary for reader, which completed reading and trying to "release" the read lock.
Deadlock.
Let's last readed (A) decremented threadAccessCount[0] to zero (2.5). At this point new reader (B) tries to begin read and passed to point 2.2. Now reader A has lock on threadAccessCount and reader B - on modifyingLock. By the assumption, A was the last, and it will try to aquire lock on modifyingLock (point 2.6), which is held by reader B. At that time, reader B will try to aquire lock on threadAccessCount (point 2.3), which is held by reader A. And this is a deadlock. Neither A, nor B can procede and get required lock, because required lock is held by other thread.
Other notes about your code.
Are the assignments 1.4 and 1.5 and check 2.2. necessary? If your worker are not waiting for something on modifyingLock between lines 1.4 and 1.5, then all these checks are not necessary, because they are occurs in secions, synchronized on modifyingLock (2.1), and lock is held by writer (1.1) all the time during actual data change. Whenever any thread acquires lock on modifyingLock, it see value zero in modifyingLock[0].
What is the purpose of notifications at 1.3 and 1.6? They can't notify readers, because there is no readers during write, see previous note. And all other writers in wait queue was already notified by last reader.
P.S. Try to perform both modifyingLock and threadAccessCount updates when synchronized on same (one) value (for example, modifyingLock).
# 10
Maxim_Karvonen,
Thank you for the keen eyes; I really didn't except anyone to read through the whole thing. I can swear I had made changes on my last reply that should reflect many of the issues you pointed out. I don't know why my last post does not reflect these changes. In any case, let me recap what the requirement for my problem is as it'll help explain the situation become more pristine.
We have writer and reader threads which both work on the same set of data structure. Since there is a mutual underlying data involved, I was hoping to come up with a mechanism to basically flush out the "reader" threads as soon as a "writer" thread appears for a modification to such data structure. And by flush, I am not saying to terminate the search in the middle of work but rather allow the "reader" threads to finish their task but any "new" coming "reader" AND "writer" thread must block and wait for the first "writer" thread to perform its duty.
The reason reader and writer threads may go head to head is because the modification methods (i.e. add() and remove()) both take advantage of the accessing method (i.e. contain()) to make sure an entry/node is present in the data structure before proceeding to the actual job. So as you can see, both reader and writer threads call upon contain() method at some point. Therefore, in the design, I have to make sure that all of its content only be available to a single "writer" thread.
Since my last reply, I managed (hopefully) to accomplish this to some extend. But soon after, I realized that my design would continuously only allow the "writer" threads to obtain the locks _IF_ there is a writer thread present in the queue at any given time.
For instance, if I have 50 reader threads in the middle of contain() and 5 writer threads, waiting to be processed, all 50 reader threads must finish their task and exit. Meanwhile any incoming reader (or/and writer thread) must be blocked. Once all 50 reader threads egressed, one of the 5 (or + any incoming writer thread) writer thread is selected and given a way to perform its task.
Now, we can have two scenarios, one being to continue blocking all the incoming reader threads (which can add up to dozens by the time a writer thread finishes) due to the fact that we still have other writer threads. Secondly, allow a contention among reader and writer threads and see who wins. BUT... Due to my design, if a reader wins, then all other readers must be processed and their counter decremented to zero so the writer threads can be given a green flag for operation. And since number of reader threads pretty much dominates throughout the life cycle of the application, it will be a long epoch until any of the writer threads come to life.
So to combat this, I introduced a reader/writer ratio. Every time a writer performs its task, right before it exits, it checks to see whether a threshold has been reached. If not, it gives priority to another writer thread to continue executing until number of reader to writer threads passes such ratio. In that case, the ball would be in reader threads' court. So this is what I came up with so far:
private byte[] modifyingLock; // An indication that a writer thread "wanting" to do some work
private int[] accessThreadCount; // Number of "reader" threads
private short modificationThreadCount; // Number of "writer" threads
private double accessToModifyingThreadRatio; // The ratio of reader to writer (usually 10 to 1)
// add() method
synchorinzed (modifyingLock) {
modificationThreadCount++;
// An indication to all "reader" threads that a "writer" or "writers"
// thread(S) has joined a party and everyone needs to clear out a way
modifyingLock[0] = 1; /* (1.1) */
while (accessThreadCount[0] != 0) {
try {
modifyingLock.wait();
} catch (InterruptedException ie) {
}
} // end of while loop
// We have to reset the lock's value because add() needs to call on
// contain() and if we leave the lock's value on line "1.1", then
// a writer thread that calls contain() would also go on a block
// and create a deadlock
modifyingLock[0] = 0; /* (1.2) */
// If the item is already in the data structure, just return. But before
// doing so, a writer thread needs to do some cleaning and synchronization
if (/* contain() */) {
// As we discussed, if the "current" writing thread leave this lock's value
// unset, this would give the "reader" threads a way to execute without
// giving a chance to "writer" threads.
//
// This is due to the fact that the only way reader threads "know" whether
// a writer thread is about to do some work is to have this lock's value
// set which lets the incoming reader threads know that they should block
// ... for now.
//
// If ratio of reader threads to writer thread exceeds a certain number,
// then the lock's value is left unset so now, "reader" threads can execute
// their task. Otherwise, we let the next possible "writer" thread to take on.
// This is more like a writer thread vouching for another writer thread
// comrade.
if (/* threshold is NOT reached */) {
modifyingLock[0] = 1;
}
modificationThreadCount--;
modifyingLock.notifyAll();
return;
}
/****** Do the actual insertion *******/
// This is the end of the line for the writer thread so it has to perform
// the same set of procedures as I just described above. I could always
// modularize it to avoid code duplication but we leave it like that for now.
if (/* threshold is NOT reached */) {
modifyingLock[0] = 1;
}
modificationThreadCount--;
modifyingLock.notifyAll();
//////////////////////////////////////////////////////////////////////////
// contain() method
synchronized (accessThreadCount) {
accessThreadCount[0]++;
}
// If the modifyingLock is set, this is an indication that a writer
// thread is about to make a modification and all the incoming reader
// threads (those which have not begun accessing the underlying data
// structure) would have to block
//
// A writer thread that gets to this point has already acquired a lock
// so it follows through and also has the modifyingLock reset at line
// 1.2.
//
synchronized (modifyingLock) { /* (2.1) */
while (modifyingLock[0] == 1) {
try {
modifyingLock.wait(); /* (2.x) */
} catch (InterruptedException ie) {
}
} // end of while loop
} end of synchronized block
/******* Do the actual search *******/
// If this is a reader thread, try to acquire a lock on the object,
// decrement the "reader" thread counter. If the counter has reached
// zero, automatically call upon any waiting thread on the lock.
//
// The notification is only good under two conditions:
//
//- Only "reader" threads been performing and a writer(s) is on
//a waiting list.
//- Other reader threads that have been blocked on line 2.1
synchronized (modifyingLock) {
synchronized (accessThreadCount) {
accessThreadCount[0]--;
if (accessThreadCount[0] == 0) { /* (2.4) */
modifyingLock.notifyAll();
}
} // end of synchronized (accessThreadCount)
} // end of synchronized (modifyingLock)
return /* base on the outcome of search method above (2.2) */
///////////////////////////////////////////////////////////////////////////
Ok, so this might not be the most crisp design for such requirements but I think it can hold its own. One concern that I have is that during the work flow of a "writer" thread, when it is about to exit contain(), it "might" call on notifyAll() once here, and another time at the bottom of add(). Would that be a problem? Note that the lock on the modifyingLock is still held by the writer thread up to the end of add().
Another tiny problem that I can think of is when contain() method returns at line (2.2). This is a clear case of unsafe "compound" actions which can result in some reader getting all the way down to line (2.2) and a context switch occurs. As a result, a writer thread begins working (and ultimately exits). In that case, a return value of true may well be "false!" due to alteration done to the data structure. This could leave a client of reader thread very unhappy. Although, this scenario can be very unlikely, it could happen and I do not know how to resolve it.
I still have to think about a few pointers. Maxim_Karvonen, I would like to extend my gratitude for your participation in this discussion. If it wasn't for your reply, I wouldn't have cared to post this latest response. I know this might not be the end so I keep digging.
Thank You
# 11
Nobody is going to read through all that either. As I said before, if you want shared-read locks and write locks they are already done in the JDK. Save yourself all this bother.
ejpa at 2007-7-29 17:17:24 >
