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