1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Multiple Thread Example</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, allocator" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="mt_allocator.html" title="Chapter��19.��The mt_allocator" /><link rel="prev" href="mt_allocator_ex_single.html" title="Single Thread Example" /><link rel="next" href="bitmap_allocator.html" title="Chapter��20.��The bitmap_allocator" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Multiple Thread Example</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="mt_allocator_ex_single.html">Prev</a>��</td><th width="60%" align="center">Chapter��19.��The mt_allocator</th><td width="20%" align="right">��<a accesskey="n" href="bitmap_allocator.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="allocator.mt.example_multi"></a>Multiple Thread Example</h2></div></div></div><p> 3In the ST example we never used the thread_id variable present in each block. 4Let's start by explaining the purpose of this in a MT application. 5</p><p> 6The concept of "ownership" was introduced since many MT applications 7allocate and deallocate memory to shared containers from different 8threads (such as a cache shared amongst all threads). This introduces 9a problem if the allocator only returns memory to the current threads 10freelist (I.e., there might be one thread doing all the allocation and 11thus obtaining ever more memory from the system and another thread 12that is getting a longer and longer freelist - this will in the end 13consume all available memory). 14</p><p> 15Each time a block is moved from the global list (where ownership is 16irrelevant), to a threads freelist (or when a new freelist is built 17from a chunk directly onto a threads freelist or when a deallocation 18occurs on a block which was not allocated by the same thread id as the 19one doing the deallocation) the thread id is set to the current one. 20</p><p> 21What's the use? Well, when a deallocation occurs we can now look at 22the thread id and find out if it was allocated by another thread id 23and decrease the used counter of that thread instead, thus keeping the 24free and used counters correct. And keeping the free and used counters 25corrects is very important since the relationship between these two 26variables decides if memory should be returned to the global pool or 27not when a deallocation occurs. 28</p><p> 29When the application requests memory (calling allocate()) we first 30look at the requested size and if this is >_S_max_bytes we call new() 31directly and return. 32</p><p> 33If the requested size is within limits we start by finding out from which 34bin we should serve this request by looking in _S_binmap. 35</p><p> 36A call to _S_get_thread_id() returns the thread id for the calling thread 37(and if no value has been set in _S_thread_key, a new id is assigned and 38returned). 39</p><p> 40A quick look at _S_bin[ bin ].first[ thread_id ] tells us if there are 41any blocks of this size on the current threads freelist. If this is 42not NULL - fine, just remove the block that _S_bin[ bin ].first[ 43thread_id ] points to from the list, update _S_bin[ bin ].first[ 44thread_id ], update the free and used counters and return a pointer to 45that blocks data. 46</p><p> 47If the freelist is empty (the pointer is NULL) we start by looking at 48the global freelist (0). If there are blocks available on the global 49freelist we lock this bins mutex and move up to block_count (the 50number of blocks of this bins size that will fit into a _S_chunk_size) 51or until end of list - whatever comes first - to the current threads 52freelist and at the same time change the thread_id ownership and 53update the counters and pointers. When the bins mutex has been 54unlocked, we remove the block that _S_bin[ bin ].first[ thread_id ] 55points to from the list, update _S_bin[ bin ].first[ thread_id ], 56update the free and used counters, and return a pointer to that blocks 57data. 58</p><p> 59The reason that the number of blocks moved to the current threads 60freelist is limited to block_count is to minimize the chance that a 61subsequent deallocate() call will return the excess blocks to the 62global freelist (based on the _S_freelist_headroom calculation, see 63below). 64</p><p> 65However if there isn't any memory on the global pool we need to get 66memory from the system - this is done in exactly the same way as in a 67single threaded application with one major difference; the list built 68in the newly allocated memory (of _S_chunk_size size) is added to the 69current threads freelist instead of to the global. 70</p><p> 71The basic process of a deallocation call is simple: always add the 72block to the front of the current threads freelist and update the 73counters and pointers (as described earlier with the specific check of 74ownership that causes the used counter of the thread that originally 75allocated the block to be decreased instead of the current threads 76counter). 77</p><p> 78And here comes the free and used counters to service. Each time a 79deallocation() call is made, the length of the current threads 80freelist is compared to the amount memory in use by this thread. 81</p><p> 82Let's go back to the example of an application that has one thread 83that does all the allocations and one that deallocates. Both these 84threads use say 516 32-byte blocks that was allocated during thread 85creation for example. Their used counters will both say 516 at this 86point. The allocation thread now grabs 1000 32-byte blocks and puts 87them in a shared container. The used counter for this thread is now 881516. 89</p><p> 90The deallocation thread now deallocates 500 of these blocks. For each 91deallocation made the used counter of the allocating thread is 92decreased and the freelist of the deallocation thread gets longer and 93longer. But the calculation made in deallocate() will limit the length 94of the freelist in the deallocation thread to _S_freelist_headroom % 95of it's used counter. In this case, when the freelist (given that the 96_S_freelist_headroom is at it's default value of 10%) exceeds 52 97(516/10) blocks will be returned to the global pool where the 98allocating thread may pick them up and reuse them. 99</p><p> 100In order to reduce lock contention (since this requires this bins 101mutex to be locked) this operation is also made in chunks of blocks 102(just like when chunks of blocks are moved from the global freelist to 103a threads freelist mentioned above). The "formula" used can probably 104be improved to further reduce the risk of blocks being "bounced back 105and forth" between freelists. 106</p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="mt_allocator_ex_single.html">Prev</a>��</td><td width="20%" align="center"><a accesskey="u" href="mt_allocator.html">Up</a></td><td width="40%" align="right">��<a accesskey="n" href="bitmap_allocator.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Single Thread Example��</td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top">��Chapter��20.��The bitmap_allocator</td></tr></table></div></body></html>