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

Recommended Posts

Hello! I want to creat a linkedlist of all elements to draw with multithreading! For updating the list, the main thread copys the element, overwrites it with the new data and then just sets the pointer of the previous to the new one(so no problem there, because the other is just reading the list) The Problem is now: can it occur(on a dual core) that both threads(cores) access the pointer(the adress stored by the pointer, not the data pointed to) at the same time? so, while one thread is reading it, the other is writing to it! wouldnt the adress then be corrupted? thx for answers

Share on other sites
Yep, this is a general problem for any multi-threaded programming, not just for software running on dual-core CPUs. There's a whole family of such issues known as synchronization problems.

The solution is to lock the list when it is being updated or accessed so that other threads can't screw things up. The simplest method is probably to use a mutex.

Share on other sites
They can access the same pointer at the same time, but since writing only takes one cycle (I think), the data won't be corrupted. You don't have to worry about it.
What you do have to worry about is making sure two threads don't try to write to the same data, causing it to get "out of sync".

Also, your method won't work when you remove elements from the list. What if thread 1 is looking at the last node of the list, and thread 2 then gets scheduled in and deletes the last node? When thread 1 gets scheduled back in, it's looking at invalid memory.

Share on other sites
the deleting is also rather simple! i just have to use a second pointer for the deletelist and a variable "used"! mutex could also work, have to think about that one!

1) my list has an order! which is rather useful to my idea! :)
2) when no longer used the object is added to the deletelist! (also sorted)
3) when deleting, the objects are deleted until the object with "used" variable is set!(from front to back, same direction in which reading occurs)

There should be no problem because the elements before the "used" object are no longer pointed to by the main list, and thus can no longer be read by thread 2! if you want a graphic of the situation...ask, but it looks awful

Share on other sites
Quote:
 I want to creat a linkedlist of all elements to draw with multithreading!

Can you elaborate on this please?
Are you using mutiple threads to render or are there multiple threads updating objects states?

Share on other sites
Quote:
 I want to creat a linkedlist of all elements to draw with multithreading!

Can you elaborate on this please?
Are you using mutiple threads to render or are there multiple threads updating objects states?

Share on other sites
You can do this by having two linked lists.
The rendering thread starts at the head of one list (a pointer to one of your objects) and runs through it rendering every element like you would expect. The other thread works on the other list, and when it is ready, just changes the value of the head pointer that the rendering thread uses to the new list - since this is one op like Evil said, you can do it anytime. In the next rendering pass, the rendering thread will now be using the newly changed list.
You have to make sure that the second thread doesn't work on the list that the rendering thread is currently rendering though. I think I avoided this by having another variable that the rendering thread sets at the beginning of a render so that the other thread will know when the old list is safe to alter. In this way the rendering thread can run at full speed, and the data changing thread will be the only one that has to wait; I wouldn't want to have the rendering thread waiting on a mutex, that will likely cause the frame rate to stutter noticeably.
Hope that all makes sense.

Edit: I should add that there are no mutexes necessary, the data changing thread can just sleep(1) if the rendering thread has not yet started another pass since the list head changed.

Share on other sites
Quote:
 Original post by Evil SteveThey can access the same pointer at the same time, but since writing only takes one cycle (I think), the data won't be corrupted. You don't have to worry about it.

If you only plan to write a single 32-bit value, yes.

And it might still be a problem if you access the pointer more than once, and expect it to still be the same value.

Share on other sites
The most standard method would be to lock the data, so only one thread can modify the state of the list at once.

Ie:
Render thread walks up to the list, locks it, takes the front element off of the list, unlocks the list, and then goes off and renders that element.

The producer, when she wants to add data to the list, locks the list, appends the element, and unlocks the list.

The above operations can involve multiple elements at once for efficiency. (ie, the renderer can lock; take multiple elements; unlock; render them;, and the producer can make multiple elements, lock, add the elements to the list, unlock.)

An alternative is implementing a "lock-free" list or queue. This isn't nearly as easy as you think, unless you have done it before.

Multithreaded programming is quite often much harder than you think it is. It is usually best to stress correctness of your code. One large problem with multithreaded code is that the number of time slices each thread gets is non deterministic (it depends on system load amoung other factors) -- so even if your code works in a test run, it may still have bugs, and it may generate system instability months down the line.

Share on other sites
I don't think this needs either mutexes, or a full-blown lock-free list implementation. Given that there are only two threads accessing the data, and only one of them is writing to it, this is a pretty simple case. It sounds like Zeusel may have already got it sorted out, but fwiw this is what I was trying to describe before:
(written from memory so don't expect anything to compile)
class ListNode {	SomeObject* objectToRender;	ListNode* next;};/////////////////////////////// rendering threadListNode* renderingListHead;ListNode* queuedListHead;void render(){	ListNode* node = renderingListHead = queuedListHead;	while (node) {		renderObject(node->objectToRender);		node = node->next;	}}/////////////////////////////// data altering threadvector<ListNode*>* currentRenderList;vector<ListNode*>* nextRenderList;void updateRenderingList(){	// If the rendering thread loops faster than this thread 	// which is probably the case, this will rarely happen	while (renderingListHead != queuedListHead) Sleep(1);		// ... Put everything you want to render into nextRenderList	// ... If you want to delete objects, do so only if they	// ... are not still present in currentRenderList		// This is why I am using vectors for storage	sort(nextRenderList->begin(), nextRenderList->end(), someSort);		// Set up a linked list from the vector contents	int numElements = nextRenderList->size();	for (int i = 0; i < numElements - 1; i++)		nextRenderList->at(i).next = nextRenderList->at(i+1);	nextRenderList->at(numElements-1).next = NULL;		// Need to have a list of what is being rendered to know	// what is safe to delete during the next update	currentRenderList = nextRenderList;		// this assignment 'flips the switch' to use the new list	queuedListHead = nextRenderList->at(0);}

I used that approach for a google-earth like program where textures were loaded over the network and displayed as they became available, then deleted (oldest first) when the cache limit was exceeded. I feel I should repeat - you really don't want to have your rendering thread waiting for the other thread to unlock something (unless framerate stuttering is not a concern).

Share on other sites
Quote:
 Original post by ApochPiQYep, this is a general problem for any multi-threaded programming, not just for software running on dual-core CPUs. There's a whole family of such issues known as synchronization problems.The solution is to lock the list when it is being updated or accessed so that other threads can't screw things up. The simplest method is probably to use a mutex.

A solution is to use locks. Not the solution. There is a whole class of containers known as lock-free that generally perform much better than those that use synchronization methods such as locks. Of course, they do require a much more intimate knowledge of threading and its issues than lock based programming generally does, but they also more effectively utilize the processor.

Share on other sites
Cool... I consider myself educated [smile]

Thanks!

Share on other sites
Quote:
 Original post by WashuA solution is to use locks. Not the solution. There is a whole class of containers known as lock-free that generally perform much better than those that use synchronization methods such as locks. Of course, they do require a much more intimate knowledge of threading and its issues than lock based programming generally does, but they also more effectively utilize the processor.

Could you give an example of such a library?

Share on other sites
Quote:
Original post by Washu
Quote:
 Original post by ApochPiQYep, this is a general problem for any multi-threaded programming, not just for software running on dual-core CPUs. There's a whole family of such issues known as synchronization problems.The solution is to lock the list when it is being updated or accessed so that other threads can't screw things up. The simplest method is probably to use a mutex.

A solution is to use locks. Not the solution. There is a whole class of containers known as lock-free that generally perform much better than those that use synchronization methods such as locks. Of course, they do require a much more intimate knowledge of threading and its issues than lock based programming generally does, but they also more effectively utilize the processor.

Can you go into more detail about that? I'm heavily involved with multi-threaded programming, and this sounds very interesting.

Share on other sites
I'm going to have to third that request... Wikipedia's information leaves quite a bit to be desired. I gather that there are known lock-free implementations of a handful of structures (sets, LIFO/FILO buffers, queues, red/black trees, blah blah) but my Google-fu is not strong enough to turn up actual descriptions of how those implementations work.

Quote:

Heh, great!!

Share on other sites
Quote:
 The most standard method would be to lock the data, so only one thread can modify the state of the list at once.

standard, yes, but when only 1 thread is altering the data, locking in unnecessary...with my method :)

and in fact my problem is solved(it was the 1-cycle thing)!

Quote:
 You can do this by having two linked lists.

well, as described: i now use two lists! now with really nice graphic: http://webplaza.pt.lu/moos/rng.jpg

If you now ask what happens when rendering and updating affects the same element: nothing happens! "renderthread" just continues rendering the list, thanks to the "renderlist" pointers not being altered when being moved to the deletelist! it renders an(or multiple) object now in deletelist an then switches back to the renderlist, without noticing that it ever rendered an object of the deletelist!

For deleting of objects: because BOTH lists are sorted the same way(ID 1 -> ID 2 -> ...) and rendering starts with (ID 1 -> ID 2 -> ...)! I begin deleting the list in sorted way until a "used" bool is found! i cant delete any further in the list because the "next render pointer" could still point to an element in the "deletelist"(this case happens if element a which is being rendered is being updaten an then, the next element in the list is being updated(the element then existists twice(one in renderlist and one in deletelist) with worstcase scenarion being the "next pointer" pointing to 2 distinct adresses...blablabla))

do you understand? i couldnt test it until now, because i use a server-client model and this was for the client, i have to do it another time for the server! when results are there, i will upload some code! and dont complain about the "really nice graphic"! :)

Share on other sites
On the x86/x64 platform the keystone of the lock-free containers is the InterlockCompareExchange function.

For those intrested Game Programming Gems 6 has an article on lock free designs and one on using OpenMP (infact, its just a damned good book all around, heh).

Share on other sites
Quote:
 Original post by phantomFor those intrested Game Programming Gems 6 has an article on lock free designs and one on using OpenMP (infact, its just a damned good book all around, heh).
Damn, you beat me to it [smile] GPG6 has examples of all sorts of lock-free containers, including free lists and linked lists.

Share on other sites
You can find information on Lock-Free linked lists here (Click the PDF link on the right if you can't stand Post Script [grin]). I should note that there are many other papers on implementing other containers, you just need to look around a bit. I can't verify the validity of the information covered in GPG, so I'm not going to recommend it (that's not saying you shouldn't get it, that's just saying I haven't read it so I can't comment on how good the information is). If I recall correctly, the paper above either contains or references to a formal proof of their algorithm. Lock-free theory really is an advanced subject and not one to be taken up by someone new to threading, or even only mildy experienced with it. The principles and concepts used are typically far more detailed than the two or three word shorthand that is used (Think of polymorphism...now try and properly describe it in a paragraph or less [grin]).

Lock free containers rely on the usage of atomic operations to perform their operations. They are typically highly restricted in what operations are allowed, as being able to guarantee thread safety of a container over all operations is impossible without using locks. On the other hand, for your typical containers that will be concurrently written to by multiple threads, the number of operations you will realistically be performing on it is limited (for a queue, for instance, you will most likely just Enqueue and Dequeue, for a stack its Push/Pop).

Anyways, I've got a heap load of other links, but googling for lock free (container name) should give you other results.

Share on other sites
Am I correct in assuming that the various 'lock free' methods are limited in the allowed manipulation and wont work for some very commonly used operations (as in deleting nodes in the middle of a list (a common operation in game rendering where the display set is constantly changing...).

Also just because a 'lock' isnt involved doesnt man that there isnt a delay (multiple CPUs can mean multiple caches that have to sync up for a particular memory space).

Spin Waits can be used for locks across multiple CPUs (again having to wait for cache/memory sync, etc...) though if threads are mixed (run on differenet CPUs and sometimes on the same CPU) for load scheduling it can be a complication (SpinWaits dont work on a single CPU).

Share on other sites
Quote:
 Original post by Anonymous PosterAm I correct in assuming that the various 'lock free' methods are limited in the allowed manipulation and wont work for some very commonly used operations (as in deleting nodes in the middle of a list (a common operation in game rendering where the display set is constantly changing...).

Not at all, read the paper i linked, it allows for lock free insertion and deletion from the middle of the list, singly linked though, so such operations are easily atomic. I say easily atomic since the operation is no where near as complex as that of say a Red/Black tree...
Quote:
 Also just because a 'lock' isnt involved doesnt man that there isnt a delay (multiple CPUs can mean multiple caches that have to sync up for a particular memory space).

Delays are indeed possible, however they are generally much shorter (unless you've got a really bad implementation) than using critical sections/mutexes (or other forms of locking objects).
Quote:
 for cache/memory sync, etc...) though if threads are mixed (run on differenet CPUs and sometimes on the same CPU) for load scheduling it can be a complication (SpinWaits dont work on a single CPU).

There are many documented and proven methods of performing atomic inserts and deletions from collections that don't care for how many cores you have. See the paper, again.