 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Craig
Guest
|
 Posted: Mon Jul 19, 2004 5:26 pm Post subject: Threading with STL Containers |
 |
|
Can anyone point me to information on how to use threads to add info to a
container and read other information from the same container at the same
time using separate threads? I guess some form of locking is involved but I
have never tried to write this type of code before.
TIA
Craig
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Maciej Sobczak
Guest
|
| Posted: Mon Jul 19, 2004 9:00 pm Post subject: Re: Threading with STL Containers |
|
|
Hi,
Craig wrote:
| Quote: | Can anyone point me to information on how to use threads to add info to a
container and read other information from the same container at the same
time using separate threads? I guess some form of locking is involved but I
have never tried to write this type of code before.
|
If you want to use a set of threading primitives that are considered to
be a good example of C++ library design, try Boost.Thread:
http://www.boost.org/libs/thread/doc/index.html
The interesting example of mixing threads and STL containers is:
http://www.boost.org/libs/thread/example/condition.cpp
(be sure to understand every line of this code)
You may also find the "Programming with POSIX Threads" by David R.
Butenhof to be really illuminating. It is not about C++ (and STL), but
the general knowledge presented there is just universal and helps a lot
also in development using STL, Boost.Threads and such.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jeff Greif
Guest
|
| Posted: Tue Jul 20, 2004 9:23 pm Post subject: Re: Threading with STL Containers |
|
|
The general principles of synchronizing access as you could find in
Butenhof's book[1] or Kleiman[2] or Schmidt[3], or more theoretically in
Hoare[4] cover most of the issues. Languages that standardize an approach
to threading (such as Java) provide other references about details[5].
(Despite the reservations some experts have about the way it was done in
Java, there are still things to learn.)
There is one difficult issue that is not discussed in most of these works --
the invalidation of iterators. If, while one thread has an iterator on a
container, another thread modifies the container (possibly causing it to be
resized and reallocated, a tree to be rebalanced or hash buckets recomputed)
the easiest thing to do is to have all further uses of the iterator fail
with an exception. In general, it is not possible to "fix up" the iterator
so the usual guarantees about traversal can be met. I think Java builds
into each iterator a cell to hold a modification count gotten at
construction time from the container on which it is based. In each relevant
method on the iterator, the stored modification count on the iterator is
compared to the current one in the container, and an exception thrown on
mismatch Some modifications that occur through the iterator in question
must be treated specially, since that iterator should still be valid (while
others would be invalidated).
Other approaches to handling concurrent access in the presence of iterators
might be found in the CORBA facilities for iterators[6], which have the
additional problem of having potentially distributed collections and remote
iterators or iterator proxies.
[1] Butenhof, David, "Programming with POSIX Threads"
[2] Kleiman, et al., "Programming with Threads"
[3] Schmidt, D., et al., "Pattern-oriented software architectures"
[4] Hoare, Anthony, "Communicating Sequential Processes"
[5] Java API docs for the classes java.lang.Object, java.lang.Thread and the
various container and iterator interfaces and classes in the java.util
package.
[6] OMG specifications for various CORBAservices, including Collection,
Properties, Concurrency, Query.
http://www.omg.org/technology/documents/corbaservices_spec_catalog.htm
Jeff
"Craig" <benbowcSpamNotI (AT) attglobal (DOT) net> wrote
| Quote: | Can anyone point me to information on how to use threads to add info to a
container and read other information from the same container at the same
time using separate threads? I guess some form of locking is involved but
I
have never tried to write this type of code before.
|
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dan McLeran
Guest
|
|
| Back to top |
|
|
Le Chaud Lapin
Guest
|
| Posted: Wed Jul 21, 2004 12:10 pm Post subject: Re: Threading with STL Containers |
|
|
Craig <benbowcSpamNotI (AT) attglobal (DOT) net> wrote
| Quote: | Can anyone point me to information on how to use threads to add info to a
container and read other information from the same container at the same
time using separate threads? I guess some form of locking is involved but I
have never tried to write this type of code before.
TIA
|
A model that works best for me is to wrap the container in a Shared<>
template. Then in each thread, you
1. acquire() // the object that is shared by threads
2. read/write // from/to the object while other threads are locked out
3. release() // the object so that other threads may acquire it
Define your Shared<> template as such:
template <typename Element> struct Shared : public Element, public
Mutex {} ;
Define your global object as such:
Shared<Associative_List foo;
// In a thread requiring temporary exclusivity:
foo.acquire();
foo.suffix ("honey", "bear");
foo.suffix ("sour", "Kraut"); // watch out for thrown exception
foo.release();
This implies that your Mutex class looks something like:
class Mutex
{
unsigned long int handle;
public :
Mutex ();
Mutex (const Mutex &);
Mutex (const String__ &); // for named mutexes
Mutex & operator = (const Mutex &); // assignment
void acquire () const; // waits forever for acquistion
bool acquire (Duration) const; // will not wait forever for
acquistion
void release () const;
~Mutex ();
} ;
Your OS-specific implementation of Mutex should be straightforward.
Use whatever the OS supplies for implementing them. Pay close
attention to the semantics of copying and assigning a Mutex.
Typically, the kernel will get upset if you invoke close() on a stale
mutex handle. On Windows, DuplicateHandle() works nicely for
generating a fresh handle for a kernel-based mutex object so that
regularity in copying and assigning can be maintained without
resorting to tricky reference counting (which would theoretcally
require a mutex on the reference count).
-Chaud Lapin-
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Wed Jul 21, 2004 7:03 pm Post subject: Re: Threading with STL Containers |
|
|
Jeff Greif wrote:
| Quote: | The general principles of synchronizing access as you could find in
Butenhof's book[1] or Kleiman[2] or Schmidt[3], or more theoretically in
Hoare[4] cover most of the issues.
snip
[4] Hoare, Anthony, "Communicating Sequential Processes"
snip |
CSP is about concurrent processes that don't share memory, aside from
section 6.3, which argues that shared memory is too hard to use
correctly! So it's not that relevant to multithreading.
For anyone still interested, there's a free (of charge) electronic
version at <http://www.usingcsp.com/>.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Craig
Guest
|
| Posted: Wed Jul 21, 2004 7:11 pm Post subject: Re: Threading with STL Containers |
|
|
Dan McLeran wrote:
That looks very promising. It should be usable on more than one OS as
well so thats a bonus. I'm a bit surprised the algorithms for this type
of thing are not part of the STL.
Craig
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Le Chaud Lapin
Guest
|
| Posted: Wed Jul 21, 2004 8:11 pm Post subject: Re: Threading with STL Containers |
|
|
[email]unoriginal_username (AT) yahoo (DOT) com[/email] (Le Chaud Lapin) wrote in message news:<fc2e0ade.0407201944.14f4eae8 (AT) posting (DOT) google.com>...
| Quote: | Craig <benbowcSpamNotI (AT) attglobal (DOT) net> wrote
Can anyone point me to information on how to use threads to add info to a
container and read other information from the same container at the same
time using separate threads? I guess some form of locking is involved but > A model that works best for me is to wrap the container in a Shared
template.
|
My first response did not include an implementation for Mutex because
it was OS-specific. However, I should have included it because the
_pattern_ of implementation is the same on all major OS's. After I
hit the ENTER key last night, I was concerned it might be obnoxious to
recomend a solution without actually showing it. Here it is:
// Mutex.cpp
// See parent post for definition of Shared<> template
// Eliminate or implement Duration and String__ to compile.
// Neither of them is necessary for your purpose.
// Good luck. :)
#include <windows.h>
#include <winbase.h>
#include <Mutex.hpp>
Mutex::Mutex ()
{
SECURITY_ATTRIBUTES sa;
SECURITY_DESCRIPTOR sd;
if (!InitializeSecurityDescriptor(&sd,
SECURITY_DESCRIPTOR_REVISION))
throw 0;
if (!SetSecurityDescriptorDacl(&sd, TRUE, NULL, FALSE))
throw 0;
sa.nLength = sizeof(sa);
sa.lpSecurityDescriptor = &sd;
sa.bInheritHandle = FALSE;
handle = (unsigned long int) CreateMutex (&sa, FALSE, NULL);
}
Mutex::Mutex (const Mutex &that)
{
DuplicateHandle(
GetCurrentProcess(),
(HANDLE) that.handle,
GetCurrentProcess(),
(HANDLE *) &this->handle,
NULL,
FALSE,
DUPLICATE_SAME_ACCESS);
}
Mutex::Mutex (const String__ &name)
{
SECURITY_ATTRIBUTES sa;
SECURITY_DESCRIPTOR sd;
if (!InitializeSecurityDescriptor(&sd,
SECURITY_DESCRIPTOR_REVISION))
throw 0;
if (!SetSecurityDescriptorDacl(&sd, TRUE, NULL, FALSE))
throw 0;
sa.nLength = sizeof(sa);
sa.lpSecurityDescriptor = &sd;
sa.bInheritHandle = FALSE;
handle = (unsigned long int) CreateMutexW (&sa, FALSE, name);
}
Mutex & Mutex::operator = (const Mutex &that)
{
if (this != &that)
{
CloseHandle((HANDLE) this->handle);
DuplicateHandle(
GetCurrentProcess(),
(HANDLE) that.handle,
GetCurrentProcess(),
(HANDLE *) &this->handle,
NULL,
FALSE,
DUPLICATE_SAME_ACCESS);
}
return *this;
}
void Mutex::acquire () const
{
WaitForSingleObject ((HANDLE) handle, INFINITE);
}
void Mutex::release () const
{
ReleaseMutex ((HANDLE) handle);
}
Mutex::~Mutex ()
{
CloseHandle ((HANDLE) handle);
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted: Thu Jul 22, 2004 11:12 am Post subject: Re: Threading with STL Containers |
|
|
Craig wrote:
| Quote: |
Dan McLeran wrote:
Try this:
http://www.cuj.com/documents/s=7998/cujcexp1902alexandr/alexandr.htm
It's not exactly what you want, but you can use Andrei's LockingPtr
template to provide thread-safe buffer access.
That looks very promising. It should be usable on more than one OS as
well so thats a bonus. I'm a bit surprised the algorithms for this type
of thing are not part of the STL.
|
Be careful with the automagic wrapper techniques as there are some pitfalls
that can trap the unwary.
You can get deadlock if different threads use multiple autolocked objects
in expressions such that the locks are acquired in different order for
different expressions. Usually you try to have a lock hierarchy and acquire
the locks in a specific order according to the hierarchy to avoid deadlock.
Joe Seigh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Andrei Alexandrescu (See
Guest
|
| Posted: Thu Jul 22, 2004 10:44 pm Post subject: Re: Threading with STL Containers |
|
|
"Joe Seigh" <jseigh_01 (AT) xemaps (DOT) com> wrote
| Quote: | You can get deadlock if different threads use multiple autolocked objects
in expressions such that the locks are acquired in different order for
different expressions. Usually you try to have a lock hierarchy and
acquire
the locks in a specific order according to the hierarchy to avoid
deadlock. |
Indeed. A simple technique that I am sure many people have discovered often
over the time is to always lock in increasing order of addresses. I have an
article on that on www.informit.com.
Andrei
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Michael Karcher
Guest
|
| Posted: Thu Jul 22, 2004 10:54 pm Post subject: Re: Threading with STL Containers |
|
|
Le Chaud Lapin <unoriginal_username (AT) yahoo (DOT) com> wrote:
| Quote: | 1. acquire() // the object that is shared by threads
2. read/write // from/to the object while other threads are locked out
3. release() // the object so that other threads may acquire it
|
Why do you do it this way? As you mention yourself, this leads to exception
safety problems. It also is possible to access the object, while it is not
locked. I would use RAII lock objects, that provide access to the shared
object, while the shared object itself does not permit any access, like
in the appended code.
One point for your variant is that even g++ 3.4 is not able to optimize the
SharedAccessor<> object away, although I expected it would do. But I regard
exception safety as more important than the small performance hit associated
with the extra indirection.
BTW: can anybody explain, why g++ (neither 3.3 nor 3.4) are able to do
direct access to the object in main? Thay should know what the refererence
is bound to.
Michael Karcher
/* Auto-locker implementation */
class NullMutex;
template <typename T, typename Mutex> class SharedAccessor;
template <typename T, typename Mutex = NullMutex>
class Shared {
friend class SharedAccessor<T,Mutex>;
T dataobject;
Mutex m;
public:
typedef SharedAccessor<T,Mutex> accessor;
};
template <typename T, typename Mutex>
class SharedAccessor {
T & dataobject;
typename Mutex::lock lock;
public:
SharedAccessor(Shared<T,Mutex> & sh) : dataobject(sh.dataobject), lock(sh.m) {}
T* operator->() { return &dataobject; }
T& operator&() { return dataobject; }
};
/* Mutex pseudo-implementation */
#include <iostream>
#include <ostream>
// A standard RAII lock object
template <typename Mutex> class standardlock {
Mutex & mymutex;
standardlock(const standardlock&); // noncopyable
public:
standardlock(Mutex& m) : mymutex(m) { mymutex.aquire(); }
~standardlock() { mymutex.release(); }
};
class NullMutex {
public:
typedef standardlock<NullMutex> lock;
private:
friend class standardlock<NullMutex>;
void aquire() { std::cout << "AQUIRE" << std::endl;};
void release() { std::cout << "RELEASE" << std::endl;};
};
/* Test code begins here */
#include
#include <iterator>
#include <algorithm>
#include <stdexcept>
using namespace std;
typedef Shared<vector shvec_t;
void output(shvec_t & shvec)
{
shvec_t::accessor shvecacc(shvec);
cout << "Locked again for output" << endl;
copy(shvecacc->begin(), shvecacc->end(),
ostream_iterator<int>(cout,"n"));
// perfectly safe now
throw runtime_error("Out of bogosity!");
}
int main(void)
{
shvec_t shvec;
cout << "Not locked yet" << endl;
{
// This is the only thing you can do with shvec
shvec_t::accessor shvecacc(shvec);
cout << "Is locked" << endl;
shvecacc->push_back(4);
shvecacc->push_back(111);
}
cout << "No more locked" << endl;
try
{
output(shvec);
}
catch(...)
{
cout << "Oops!" << endl;
}
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Le Chaud Lapin
Guest
|
| Posted: Fri Jul 23, 2004 9:44 am Post subject: Re: Threading with STL Containers |
|
|
[email]Michael.Karcher (AT) writeme (DOT) com[/email] (Michael Karcher) wrote in message news:<2mae95Fla3g3U1 (AT) uni-berlin (DOT) de>...
| Quote: | Le Chaud Lapin <unoriginal_username (AT) yahoo (DOT) com> wrote:
1. acquire() // the object that is shared by threads
2. read/write // from/to the object while other threads are locked out
3. release() // the object so that other threads may acquire it
Why do you do it this way?
|
Simplicity.
| Quote: | As you mention yourself, this leads to exception
safety problems.
|
Easily solved by adding dummy catch (...)/throw; sequence to my
Shared<> destructor. [One day I will get around to it.]
| Quote: | It also is possible to access the object, while it is not
locked.
|
Even though some of my global objects are shared, I need to be able to
access them without locking them for performance reasons. They that
can be mutated/mutilated at will by all threads at once, with no
consequence on my algorithms.
-Chaud Lapin-
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Michael Karcher
Guest
|
| Posted: Fri Jul 23, 2004 3:37 pm Post subject: Re: Threading with STL Containers |
|
|
Le Chaud Lapin <unoriginal_username (AT) yahoo (DOT) com> wrote:
| Quote: | As you mention yourself, this leads to exception safety problems.
Easily solved by adding dummy catch (...)/throw; sequence to my
Shared<> destructor. [One day I will get around to it.]
|
Huh? I don't see how adding something to the Shared<> destructor could
help you. The Shared<> destructor is run if the shared object gets
destructed, which is way after loosing the lock, if the program doesn't
deadlock on the mutex before.
| Quote: | Even though some of my global objects are shared, I need to be able to
access them without locking them for performance reasons.
You can lock it once with my approach and pass references to the |
SharedAccessor around, or even (but loosing the added security) pass the
plain object by *accessor.
Michael Karcher
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Daniel Krügler (ne Spange
Guest
|
| Posted: Mon Jul 26, 2004 1:03 pm Post subject: Re: Threading with STL Containers |
|
|
Hello Michael Karcher,
Michael Karcher schrieb:
| Quote: | Even though some of my global objects are shared, I need to be able to
access them without locking them for performance reasons.
You can lock it once with my approach and pass references to the
SharedAccessor around, or even (but loosing the added security) pass the
plain object by *accessor.
I think there does exist one situation where your ansatz does not help |
(although otherwise its a great
idea. As far as I remember, the boost::thread library also uses a
similar approach):
If you write a higher-order mutex in terms of lower-order mutex types.
In this case the higher-order
mutex type has no direct access to the individual aquire/release
functions, although it needs them probably.
Greetings from Bremen,
Daniel Krügler
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Le Chaud Lapin
Guest
|
| Posted: Tue Jul 27, 2004 11:04 am Post subject: Re: Threading with STL Containers |
|
|
[email]Michael.Karcher (AT) writeme (DOT) com[/email] (Michael Karcher) wrote in message news:<2mcbegFl6pg0U1 (AT) uni-berlin (DOT) de>...
| Quote: | Le Chaud Lapin <unoriginal_username (AT) yahoo (DOT) com> wrote:
As you mention yourself, this leads to exception safety problems.
Easily solved by adding dummy catch (...)/throw; sequence to my
Shared<> destructor. [One day I will get around to it.]
Huh? I don't see how adding something to the Shared<> destructor could
help you. The Shared<> destructor is run if the shared object gets
destructed, which is way after loosing the lock, if the program doesn't
deadlock on the mutex before.
|
Yes. You're right, the objects are global. Don't know what I was
thinking. In all of my code, if there is a possibility of exception,
I trap them by hand and .release and rethrow.
-Chaud Lapin-
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
