Thread Safe Linked List
-
I have a Linked list with the following functions: Add, Get, Delete. For thread safe implementation I use a CRITICAL_SECTION handle in each function and everything work well. The question is: How I can avoid use of CRITICAL_SECTION on Get function? Because Get function is called on many threads the performance is low, each thread wait the previous thread to finish Get. Add and Delete are called rarely. Thanks!
-
I have a Linked list with the following functions: Add, Get, Delete. For thread safe implementation I use a CRITICAL_SECTION handle in each function and everything work well. The question is: How I can avoid use of CRITICAL_SECTION on Get function? Because Get function is called on many threads the performance is low, each thread wait the previous thread to finish Get. Add and Delete are called rarely. Thanks!
yes you can :) I've already thought about this problem, too, and I found a very fast solution. Lock the list by using interlocked functions, which use a LONG member variable of the class (I assume you use a list class) to synchronize access. Don't try it, just do it! ;-)
-
I have a Linked list with the following functions: Add, Get, Delete. For thread safe implementation I use a CRITICAL_SECTION handle in each function and everything work well. The question is: How I can avoid use of CRITICAL_SECTION on Get function? Because Get function is called on many threads the performance is low, each thread wait the previous thread to finish Get. Add and Delete are called rarely. Thanks!
You can safely eliminate the
CRITICAL_SECTIONin yourGetfunction if you make sure that your program is playing by the rules: as many threads can have read-only access to the list as long as none of them does an insertion or deletion. This usually involves some other synchronization mechanisms, although at a higher level than on the linked list itself, which presumably will yield better performance. If you cannot guarantee this behavior in your program, another possibility is to protect access by means of a read/write lock. Such a lock allows multiple threads to enter for read access, except if some thread has reclaimed write access. A web search gives the following article[^] by Ivan Krivyakov on implementing read/write locks in Windows. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo -
You can safely eliminate the
CRITICAL_SECTIONin yourGetfunction if you make sure that your program is playing by the rules: as many threads can have read-only access to the list as long as none of them does an insertion or deletion. This usually involves some other synchronization mechanisms, although at a higher level than on the linked list itself, which presumably will yield better performance. If you cannot guarantee this behavior in your program, another possibility is to protect access by means of a read/write lock. Such a lock allows multiple threads to enter for read access, except if some thread has reclaimed write access. A web search gives the following article[^] by Ivan Krivyakov on implementing read/write locks in Windows. Joaquín M López Muñoz Telefónica, Investigación y DesarrolloHi. A fast way to ensure synchronised access and update, is to use a simple 'mutex' that all three access/update methods conform to, ( as long as it is not a multi processor platform ). If you do not care about the specific order in which access and/or update is performed, ie) its a free for all, then a simple WaitForSingleObject() on the mutex should provide a simple and fast mechanism. James.
-
Hi. A fast way to ensure synchronised access and update, is to use a simple 'mutex' that all three access/update methods conform to, ( as long as it is not a multi processor platform ). If you do not care about the specific order in which access and/or update is performed, ie) its a free for all, then a simple WaitForSingleObject() on the mutex should provide a simple and fast mechanism. James.
I'm afraid I'm not getting your point. If you protect every function of the list (
Get,AddandDelete), with a mutex, you'll get esentially what the original poster has already done with aCRITICAL_SECTION, with the added penalty that mutexes are heavier. My hunch is that the original poster asks for a way to allow many concurrent threads to be granted read access at a time, and not in a strictly one-by-one basis. Do you think this can be done with mutexes? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo -
I'm afraid I'm not getting your point. If you protect every function of the list (
Get,AddandDelete), with a mutex, you'll get esentially what the original poster has already done with aCRITICAL_SECTION, with the added penalty that mutexes are heavier. My hunch is that the original poster asks for a way to allow many concurrent threads to be granted read access at a time, and not in a strictly one-by-one basis. Do you think this can be done with mutexes? Joaquín M López Muñoz Telefónica, Investigación y DesarrolloHi. By using a simple mutex, access and update can be synchonised very easily. When the list needs to be updated, the mutex is 'set', the update is performed, this excludes all access's, the update is complete and the mutex is 'released'. Since the majority of the operations, as per the 'poster' are accesses, waiting for the mutex is infrequent. Since for the majority of the time, the mutex is 'released' the wait for reads' is satisfied 'immediately' James.
-
Hi. By using a simple mutex, access and update can be synchonised very easily. When the list needs to be updated, the mutex is 'set', the update is performed, this excludes all access's, the update is complete and the mutex is 'released'. Since the majority of the operations, as per the 'poster' are accesses, waiting for the mutex is infrequent. Since for the majority of the time, the mutex is 'released' the wait for reads' is satisfied 'immediately' James.
I'm still not getting you. AFAIK the only way to set a Win32 mutex is by waiting on it; releasing is done via
ReleaseMutex. So your proposal is that the update function properly waits for the mutex and releases it after updating is completed, right? So, what should the access (i.e. read-only) function do?- if the access function also waits for the object, then there cannot be more than one thread either updating or reading at a time, exactly the same way as it happens with using a
CRITICAL_SECTION. - if the access function does not wait for the mutex, the list is not thread safe, as when the update method enters there could be other threads performing read-only acess at that time, and corruption of the data structure can hence ensue.
Maybe I am not getting your proposal right :confused: Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
- if the access function also waits for the object, then there cannot be more than one thread either updating or reading at a time, exactly the same way as it happens with using a
-
I'm still not getting you. AFAIK the only way to set a Win32 mutex is by waiting on it; releasing is done via
ReleaseMutex. So your proposal is that the update function properly waits for the mutex and releases it after updating is completed, right? So, what should the access (i.e. read-only) function do?- if the access function also waits for the object, then there cannot be more than one thread either updating or reading at a time, exactly the same way as it happens with using a
CRITICAL_SECTION. - if the access function does not wait for the mutex, the list is not thread safe, as when the update method enters there could be other threads performing read-only acess at that time, and corruption of the data structure can hence ensue.
Maybe I am not getting your proposal right :confused: Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hi. Sorry, I assumed that there were multiple threads waiting on 'access and/or update', otherwise the question is void. There can be as many threads waiting on the mutex as there is. The idea is that only an update 'locks' the mutex, 'reads', 'fall through'. Otherwise we might be talking about a DOS program. James.
- if the access function also waits for the object, then there cannot be more than one thread either updating or reading at a time, exactly the same way as it happens with using a
-
yes you can :) I've already thought about this problem, too, and I found a very fast solution. Lock the list by using interlocked functions, which use a LONG member variable of the class (I assume you use a list class) to synchronize access. Don't try it, just do it! ;-)
I have used 2 interlocked vars and a semaphore. Below is a schematic of the code. In this case the Get Thread has a very high access on the resource at 2 - 3 mil. of gets/sec towards 20 - 50 of add and del /sec If you have a better idea please tell me. Thank you. Get() { InterlockedIncrement(&_read); while(_write > 0) Sleep(0); CList::Get(); InterlockedDecrement(&_read); } Add() { while(_read > 0) Sleep(0); InterlockedIncrement(&_write); WaitForSingleObject(_sem,INFINITE); CList::Add(); ReleaseSemaphore(_sem,1,NULL); InterlockedDecrement(&_write); } Delete() { while(_read > 0) Sleep(0); InterlockedIncrement(&_write); WaitForSingleObject(_sem,INFINITE); CList::Add(); ReleaseSemaphore(_sem,1,NULL); InterlockedDecrement(&_write); }