I have this Hashtable of Hashtables, and I'm accessing this object from
multiple threads, now the Hashtable object is thread safe for reading,
but not for writing, so I lock the object every time I need to write to
it, but now it occurred to me that maybe I could just lock one of the
Hashtables inside without locking the entire object, but then I thought
maybe some thread could instruct the outside Hashtable to remove an
inside Hashtable while it was being accessed by some other thread.
So now I'm confused!
Can i just lock an inside Hashtable when i'm trying to write to it, or
do i need to lock the entire object?
I'm no threading expert, but the little experience I have and my read
of the documentation tells me that you can't just lock on writing. You
have to lock on reading, too. Now I know that there are locking schemes
that allow multiple readers but that lock out readers while writing,
but I couldn't hope to tell you what they are.
The problem is that if you try to write to the Hashtable while another
thread is reading it, the reader may be hosed. Hashtables are
implemented as arrays (buckets) of linked lists. If I'm reading the
MSDN doc correctly, simultaneously writing and reading one of those
linked lists is not guaranteed threadsafe, so writers need to lock out
all readers while they're writing.
With regards to your question, well that all depends upon the semantics
you want to impose on your structure. Let's say, for example, that you
have three operations on the whole structure: read, insert, and remove.
Let's also say that if you remove the last entry from a sub-Hashtable
then you remove that sub-Hashtable, too. (If you were to just leave it
lying there, empty, then the following problem goes away....)
So, at the same moment you're inserting and item into a particular
sub-Hashtable, you're coincidentally removing (what was) the last item
from it. Will both operations succeed? Well, that depends upon their
order and it depends upon locking on the main Hashtable. Here are two
possible interleavings of events:
Thread 1: Fetch reference to correct sub-Hashtable
Thread 2: Fetch reference to correct sub-Hashtable
Thread 1: Lock sub-Hashtable for updates
Thread 1: Remove item from sub-Hashtable
Thread 1: Determine that sub-Hashtable is now empty
Thread 1: Remove sub-Hashtable from main Hashtable
Thread 1: Unlock sub-Hashtable
Thread 2: Lock sub-Hashtable for updates
Thread 2: Add item to sub-Hashtable
Thread 2: Unlock sub-Hashtable
or
Thread 1: Fetch reference to correct sub-Hashtable
Thread 2: Fetch reference to correct sub-Hashtable
Thread 2: Lock sub-Hashtable for updates
Thread 2: Add item to sub-Hashtable
Thread 2: Unlock sub-Hashtable for updates
Thread 1: Lock sub-Hashtable for updates
Thread 1: Remove item from sub-Hashtable
Thread 1: Determine that sub-Hashtable is not empty and so should not
be reclaimed
Thread 1: Unlock sub-Hashtable for updates
In the first interleaving, the item is correctly added to the
sub-Hashtable, but the Hashtable is floating in space and will be
reclaimed by the GC. In the second case the item is added to the
sub-Hashtable and it will stay in the structure. Maybe someone else
with better knowledge of thread synchronization can think of a clever
solution, but I don't see any alternative to locking the entire
structure so that multiple updates don't collide.
As for reads, it should be sufficient to lock only the part of the
structure that you're reading from: the main Hashtable long enough to
fetch the correct sub-table, and the sub-table while looking for the
element. This would assume that writes lock both the main table and the
appropraite sub-table during updates.
