Sign in to follow this  

Multithreading problem - Win32

This topic is 3489 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm aware of Mutexes etc but these all allow either only one thread access or a limited number of threads access. The problem is I want to allow an unlimited number of threads to read the data but only allow a thread write access when there are no other threads reading or writing. I also need it so that once a thread has request write access no other read threads are allowed to start (there will be alot more reads than writes so if this doesn't happen it could be some time before the section is actauly clear for write).

Share this post


Link to post
Share on other sites
"Unlimited number of threads" is almost always a bad idea, try having not significantly more threads than cores. One or two extra threads are ok, but 10 or 20 or 50 are very bad for performance.

What you describe is called "readers writer lock". Windows Vista has Slim Reader/Writer (SRW) Locks. If you want to (or rather must) support older versions of Windows, you have to implement your own reader writer lock (can be built on top of other synchronisation objects).

Share this post


Link to post
Share on other sites
Here's a "from scratch" implementation (basically a kind of double spinlock) that Google came up with:
Free Code: Win32 Lightweight Lock.

While it's low fat and fast in the uncongested case, it should be noted that it has serious issues such as a guaranteed deadlock if either the writer or one of the readers crashes or encounters an exception while holding a lock.
The latter can easily be avoided by using Locker objects (which lock in the constructor and unlock in the destructor, stack unwinding will do the rest). The former is a lot harder to avoid.
Also, spinlocks are great for non-congested case (5-50 times faster), but not so good otherwise (burns CPU cycles, starvation, ...).
Other implementations may be more robust, and may run slower or faster, depending on your access patterns.

As always, what's the right thing depends on what you want and what you need, but this is one example of what could be the right thing.

Share this post


Link to post
Share on other sites
There won't be very many threads because I can't see a relibable way to split a game up into a small bits so I'm just planing to have 3 main threads and extra threads for doing heavy lifting in the background, like loading stuff into memory for the next level/upcoming events if theres spare cpu cycles. I just don't want a hardcoded limit in the implementation of the lock.

Most of the time I'm planning to use Mutexes but theres one or two blocks of data that will be read by pretty much everything but only change like once every 10 minutes if that.


-Render Thread - Reads all the data to render the scene
-Local Update Thread - Updates the area the players in at a rapid rate (quite likely 100hz)
-Global update thread - Updates stuff further away in other areas. The player won't actauly "see" these areas and they won't directly effect the player so it can update in larger steps less often (eg 10hz)


The problem now is how to Render the scene without stalling the update threads... The update threads are reading and writing data and the render thread is only reading.

I was thinking of making a copy of all the relvant data (so global data like money, and data for the local area) into a buffer for the render stage to use.

For the two update threads I'm thinking of implementing a few methods of interaction.

1- When an object moves from one area to another it is added to that areas "incoming stack". Object in the incoming stack will be added to the area the next time it's updated.

2- Global items (eg money, messages, etc) will be controlled by mutexes.

Share this post


Link to post
Share on other sites
So is that a reasomable concept? I'd really like to know if having buffers to store data for rendering is really the best approch as that means copying quite alot of data...

Also is there a function to wait untill all other threads have exited? I don't want my main thread to close untill all the other threads have done their shutdown process of freeing memory etc.

Share this post


Link to post
Share on other sites
Quote:
-Render Thread - Reads all the data to render the scene
-Local Update Thread - Updates the area the players in at a rapid rate (quite likely 100hz)
-Global update thread - Updates stuff further away in other areas. The player won't actauly "see" these areas and they won't directly effect the player so
That's the opposite, multiple writers, single reader :)

In this case, I think the best way is indeed to duplicate data akin to double (or better yet, triple) buffering in rendering.
As step N usually depends on step N-1, there is not much useless copying, as the update thread can read from the same buffer as the reader. It must read from somewhere anyway, so the only downside is really using more memory.

Every writer should have its own "buffer set", to keep it simple and to allow them to run at different speeds. The reader (renderer) can read from either one, this doesn't hurt.

Each buffer set needs to have 3 buffers that have reader and writer locks each.

The render thread only reads from the first buffer that's not locked for writing, as does the update thread (both increment the reader count first, of course).
The update thread, after doing its calculations, writes to the next buffer (which it has locked for writing). Once the update thread is done, it decrements the readers count on the first and sets the next block to readers=1, writers = 0. Then it continues reading from that buffer, and writes to the next one (which is free).
Once the renderer thread is done, it decrements the readers count and moves to the next one, checking the writer lock, and possibly waiting for it to drop to zero.
Repeat.

This generally works with only 2 buffers too, but may result in either thread having to wait for the other one regularly (depends on which one is slower, and having 3 threads, it means that all wait for the slowest). Having 3 buffers makes it a bit more complicated, but should avoid most of the stalls.

Share this post


Link to post
Share on other sites


So I can have the update thread with the update buffer so it always has an uptodate copy that nothing else changes.

Then at the end of each update cycle for the local update thread it copies the relevant data from the update buffer into a free local render buffer.

The global gui buffers are updated by the thread responsible for what the players looking at (eg area maps). Gui for the players area (eg radar data for nearby objects) is in the local buffer.

The render thread then uses the most recent local buffer and the most recent global gui buffer to render the scene and gui.



The problem now is how to make the rendering look more smooth eg say this happens
x-cord of object moving at 20 pixels per update
Update 100
Update 120
Render
Update 140
Render
Update 160
Update 180
Render

Sometimes the object will have moved 20 pixels and sometimes 40 pixels on the screen :(

Share this post


Link to post
Share on other sites
Quote:
Then at the end of each update cycle for the local update thread it copies the relevant data from the update buffer into a free local render buffer.

No need for an explicit copy. The render thread reads buffer A. Meanwhile, the update thread generates buffer B. B depends on A, thus to generate buffer B, the update thread needs to know some data. It reads that from buffer A.
When done generating buffer B, the update thread turns to generate C. It needs state for that, and it can read from buffer B (which is now complete).
The render thread, when done rendering A, will release A (so the update thread can recycle it), turn to B, and (if it is not locked for writing) start reading from that. No extra copies necessary.

Quote:
Sometimes the object will have moved 20 pixels and sometimes 40 pixels on the screen
Proper locking should make sure that this can't happen. The reader can't overrun the writer, as it respects the write lock, and the writer can't overrun the reader, as it respects the read lock.

Share this post


Link to post
Share on other sites
But then my update is limited to the render rate...

If the local update is 100hz and I'm getting 75fps then there will oftern be two complete updates between renders.

Share this post


Link to post
Share on other sites
In response to the original question, correct me if I am wrong, but isn't the OP asking about the readers writers problem?

Quote:
Operating System Concepts 7th Edition

A database is to be shared among several concurrent processes. Some of these processes may want only to read the database, whereas others may want to update (that is, to read and write) the database. We distinguish between these two types of processes by referring to the former as readers and to the latter as writers. Obviously, if two readers access the shared data simultaneously, no adverse affects will result. However, if a writer and some other thread ( either a reader or a writer) access the database simultaneously, chaos may ensue.


it goes on to provide a pseudocode solution


semaphore mutex, wrt;
int readcount;


//writer solution
do{
wait(wrt);
...
//writing is performed
...
signal(wrt);
}while(true);

//reader solution
do{
wait(mutex);
readcount++;
if(readcount == 1)
wait(wrt);
signal(mutex);
...
//reading is performed
...
wait(mutex);
readcount--;
if(readcount == 0)
signal(wrt);
signal(mutex);
}while(true);



Do note that this solution can cause starvation for the writers

Share this post


Link to post
Share on other sites

This topic is 3489 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this