Locking pattern to protect a critical List<> with many worker threads
-
My program contains a List<T> object that is extremely critical to the program's function. In normal use, it will be accessed by many ( >10 ) worker threads. I don't need to synchronize worker thread access, because the workers never write to the collection, it's read-only to the worker threads. However, I want to be able to make changes to the list in a single, central class. And I'd like to be able to temporarily shut off worker-thread access to the list while changes are being made by a thread in the central class. I'd like not to require the worker threads to acquire a mutex every time they need access due to performance reasons. So, is there a pattern by which I can make access to the List<T> very fast for the worker threads, but still be able to shut off worker access while the list is being updated by the central class?
The difficult we do right away... ...the impossible takes slightly longer.
-
My program contains a List<T> object that is extremely critical to the program's function. In normal use, it will be accessed by many ( >10 ) worker threads. I don't need to synchronize worker thread access, because the workers never write to the collection, it's read-only to the worker threads. However, I want to be able to make changes to the list in a single, central class. And I'd like to be able to temporarily shut off worker-thread access to the list while changes are being made by a thread in the central class. I'd like not to require the worker threads to acquire a mutex every time they need access due to performance reasons. So, is there a pattern by which I can make access to the List<T> very fast for the worker threads, but still be able to shut off worker access while the list is being updated by the central class?
The difficult we do right away... ...the impossible takes slightly longer.
A Slim Reader/Writer (SRW) Lock[^] might do the job for you.
Mircea
-
A Slim Reader/Writer (SRW) Lock[^] might do the job for you.
Mircea
Yes! That should do the job. I didn't know that they made a primitive exactly for this use case. Thanks!
The difficult we do right away... ...the impossible takes slightly longer.
-
My program contains a List<T> object that is extremely critical to the program's function. In normal use, it will be accessed by many ( >10 ) worker threads. I don't need to synchronize worker thread access, because the workers never write to the collection, it's read-only to the worker threads. However, I want to be able to make changes to the list in a single, central class. And I'd like to be able to temporarily shut off worker-thread access to the list while changes are being made by a thread in the central class. I'd like not to require the worker threads to acquire a mutex every time they need access due to performance reasons. So, is there a pattern by which I can make access to the List<T> very fast for the worker threads, but still be able to shut off worker access while the list is being updated by the central class?
The difficult we do right away... ...the impossible takes slightly longer.
Richard Andrew x64 wrote:
And I'd like to be able to temporarily shut off worker-thread access
If you remove that requirement you can implement a solution with no locks of any sort. Basic idea... For the workers
static ListX realList = ...;
DoWork()
{
ListX temp = realList;// Use temp however you want.
}For the the controller
ManageListX()
{
ListX newList = new ListX();// Populate newList
realList = newList;
} -
Richard Andrew x64 wrote:
And I'd like to be able to temporarily shut off worker-thread access
If you remove that requirement you can implement a solution with no locks of any sort. Basic idea... For the workers
static ListX realList = ...;
DoWork()
{
ListX temp = realList;// Use temp however you want.
}For the the controller
ManageListX()
{
ListX newList = new ListX();// Populate newList
realList = newList;
}Thanks, that's a great idea. I thought of that, but I decided against it because it might lead to some threads seeing the new version of the list while other threads are still working with data from the old version of the list. Also, the worker threads enumerate the list, so that would lead to exceptions caused by changing the list out from under them.
The difficult we do right away... ...the impossible takes slightly longer.
-
Thanks, that's a great idea. I thought of that, but I decided against it because it might lead to some threads seeing the new version of the list while other threads are still working with data from the old version of the list. Also, the worker threads enumerate the list, so that would lead to exceptions caused by changing the list out from under them.
The difficult we do right away... ...the impossible takes slightly longer.
-
My program contains a List<T> object that is extremely critical to the program's function. In normal use, it will be accessed by many ( >10 ) worker threads. I don't need to synchronize worker thread access, because the workers never write to the collection, it's read-only to the worker threads. However, I want to be able to make changes to the list in a single, central class. And I'd like to be able to temporarily shut off worker-thread access to the list while changes are being made by a thread in the central class. I'd like not to require the worker threads to acquire a mutex every time they need access due to performance reasons. So, is there a pattern by which I can make access to the List<T> very fast for the worker threads, but still be able to shut off worker access while the list is being updated by the central class?
The difficult we do right away... ...the impossible takes slightly longer.
Without knowing frequencies, the size of the "work unit", the implications of returning a "busy" signal versus "locking", it's hard to make a thoughtful recommendation.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
-
Without knowing frequencies, the size of the "work unit", the implications of returning a "busy" signal versus "locking", it's hard to make a thoughtful recommendation.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
Appreciate you chiming in anyway. The Slim Reader/Writer lock provides for that by offering methods that acquire locks with timeout values.
The difficult we do right away... ...the impossible takes slightly longer.
-
If you take a local copy (often a good idea anyway) you can avoid the second problem. Then a worker would keep hold of the same list until it's ready for the list to change. Doesn't do anything about the first problem.
When you refer to a local copy of the list, do you mean a copy local to each worker thread, or local to the worker module, (all worker threads can access)? If you mean local to each worker thread, then that becomes expensive creating a deep copy of the list every time a worker needs to reference it. Do I misunderstand?
The difficult we do right away... ...the impossible takes slightly longer.
-
When you refer to a local copy of the list, do you mean a copy local to each worker thread, or local to the worker module, (all worker threads can access)? If you mean local to each worker thread, then that becomes expensive creating a deep copy of the list every time a worker needs to reference it. Do I misunderstand?
The difficult we do right away... ...the impossible takes slightly longer.
A shallow copy does the trick. jschell doesn't want to call this a shallow copy, whatever. What I meant, and what the whole thread has always been about, is assigning the list to a local variable, and never editing its contents, only replacing the whole thing. The list which a reader is iterating over does not change since it has an .. even shallower fucking copy, whatever the fuck you want to call it. Copy of the pointer. They can update that when they're ready for it to change. The list is never modified anyway, only replaced. At least that was the premise of this sub-thread stared by jschell
-
Thanks, that's a great idea. I thought of that, but I decided against it because it might lead to some threads seeing the new version of the list while other threads are still working with data from the old version of the list. Also, the worker threads enumerate the list, so that would lead to exceptions caused by changing the list out from under them.
The difficult we do right away... ...the impossible takes slightly longer.
Richard Andrew x64 wrote:
so that would lead to exceptions caused by changing the list out from under them.
That cannot happen. Per your original description the worker threads do not modify it. The management thread creates a new list. The worker threads never use that list until it is done and the management thread is done with it.
Richard Andrew x64 wrote:
seeing the new version of the list while other threads are still working with data from the old version of the list.
I think that requirement is going to end up requiring additional locking. Say you look up prices in a list. Then an execution flow looks like this
Worker1: Gets price X (v1) from list. Continues work
Management: rebuild list (simple lock)
Worker2: Starts (simple lock gone) and gets price X (v2) from list.
Worker1: Finishes work with v1
Worker2: Finishes work with v2 -
A shallow copy does the trick. jschell doesn't want to call this a shallow copy, whatever. What I meant, and what the whole thread has always been about, is assigning the list to a local variable, and never editing its contents, only replacing the whole thing. The list which a reader is iterating over does not change since it has an .. even shallower fucking copy, whatever the fuck you want to call it. Copy of the pointer. They can update that when they're ready for it to change. The list is never modified anyway, only replaced. At least that was the premise of this sub-thread stared by jschell
-
Threads take a **copy of the reference to the list**. Making a new list builds it brand new. There is no reason for threads to make a deep copy since the list, once made, never changes (only replaced as a whole). E: why are you making me re-explain your own idea back to you anyway? You know how this works, you suggested it.
-
Appreciate you chiming in anyway. The Slim Reader/Writer lock provides for that by offering methods that acquire locks with timeout values.
The difficult we do right away... ...the impossible takes slightly longer.
So far, I see no evidence that the list has to be "protected" at all. If it's "updates"; they should be atomic. If it's inserts, the caller picks it up in the next "list query". If you're not using lists as lists, maybe you should be using a concurrent dictionary. If you don't like dictionaries, wrap it to make it look like a list (keys, values or key value pairs).
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
-
Richard Andrew x64 wrote:
so that would lead to exceptions caused by changing the list out from under them.
That cannot happen. Per your original description the worker threads do not modify it. The management thread creates a new list. The worker threads never use that list until it is done and the management thread is done with it.
Richard Andrew x64 wrote:
seeing the new version of the list while other threads are still working with data from the old version of the list.
I think that requirement is going to end up requiring additional locking. Say you look up prices in a list. Then an execution flow looks like this
Worker1: Gets price X (v1) from list. Continues work
Management: rebuild list (simple lock)
Worker2: Starts (simple lock gone) and gets price X (v2) from list.
Worker1: Finishes work with v1
Worker2: Finishes work with v2jschell wrote:
That cannot happen.
Not even if the worker thread is in the middle of enumerating the list?
The difficult we do right away... ...the impossible takes slightly longer.
-
Threads take a **copy of the reference to the list**. Making a new list builds it brand new. There is no reason for threads to make a deep copy since the list, once made, never changes (only replaced as a whole). E: why are you making me re-explain your own idea back to you anyway? You know how this works, you suggested it.
The term 'shallow copy' means copying entities (objects) while using references to the contents rather than copying them also. It is not a term that applies to a reference/pointer by itself. My code does not copy any entities. It only uses a pointer via a temp variable. There are no entities in that for which a reference could be used. Sources for the definition of shallow copy IBM Documentation[^] Shallow copy - MDN Web Docs Glossary: Definitions of Web-related terms | MDN[^] https://www.techopedia.com/definition/25638/shallow-copy-c[^]
-
jschell wrote:
That cannot happen.
Not even if the worker thread is in the middle of enumerating the list?
The difficult we do right away... ...the impossible takes slightly longer.
Richard Andrew x64 wrote:
enumerating the list?
Correct. The Management thread creates a new list. Completely new. It does not modify nor touch the old list in any way. The worker threads, are using the old list. Because they copied the pointer, the old list is the only one that they can use. The old list is not modified. The pointer copy is the key to this behavior.
-
The term 'shallow copy' means copying entities (objects) while using references to the contents rather than copying them also. It is not a term that applies to a reference/pointer by itself. My code does not copy any entities. It only uses a pointer via a temp variable. There are no entities in that for which a reference could be used. Sources for the definition of shallow copy IBM Documentation[^] Shallow copy - MDN Web Docs Glossary: Definitions of Web-related terms | MDN[^] https://www.techopedia.com/definition/25638/shallow-copy-c[^]
-
Richard Andrew x64 wrote:
enumerating the list?
Correct. The Management thread creates a new list. Completely new. It does not modify nor touch the old list in any way. The worker threads, are using the old list. Because they copied the pointer, the old list is the only one that they can use. The old list is not modified. The pointer copy is the key to this behavior.
Yes, you're right, by George. So that implies that the reference assignment itself is atomic?
The difficult we do right away... ...the impossible takes slightly longer.
-
Yes, you're right, by George. So that implies that the reference assignment itself is atomic?
The difficult we do right away... ...the impossible takes slightly longer.
Richard Andrew x64 wrote:
So that implies that the reference assignment itself is atomic?
Yes that must be the case. For java and C# it is. Best I can tell in C++ the answer is sort of. Apparently it depends on the execution environment. But there is std:atomic. I wondered, when this thread started, if it was possible to have a language that supports threads where assignment was not atomic. (C++ the language does not support threads.)
