1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
<!DOCTYPE html
PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- saved from url=(0014)about:internet -->
<html xmlns:MSHelp="http://www.microsoft.com/MSHelp/" lang="en-us" xml:lang="en-us"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="DC.Type" content="topic">
<meta name="DC.Title" content="Reference Counting">
<meta name="DC.subject" content="Reference Counting">
<meta name="keywords" content="Reference Counting">
<meta name="DC.Relation" scheme="URI" content="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="Reference_Counting">
<link rel="stylesheet" type="text/css" href="../../intel_css_styles.css">
<title>Reference Counting</title>
<xml>
<MSHelp:Attr Name="DocSet" Value="Intel"></MSHelp:Attr>
<MSHelp:Attr Name="Locale" Value="kbEnglish"></MSHelp:Attr>
<MSHelp:Attr Name="TopicType" Value="kbReference"></MSHelp:Attr>
</xml>
</head>
<body id="Reference_Counting">
<!-- ==============(Start:NavScript)================= -->
<script src="..\..\NavScript.js" language="JavaScript1.2" type="text/javascript"></script>
<script language="JavaScript1.2" type="text/javascript">WriteNavLink(2);</script>
<!-- ==============(End:NavScript)================= -->
<a name="Reference_Counting"><!-- --></a>
<h1 class="topictitle1">Reference Counting</h1>
<div>
<div class="section"><h2 class="sectiontitle">Problem</h2>
<p>Destroy an object when it will no longer be used.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Context</h2>
<p>Often it is desirable to destroy an object when it is known that it
will not be used in the future. Reference counting is a common serial solution
that extends to parallel programming if done carefully.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Forces</h2>
<ul type="disc">
<li>
<p>If there are cycles of references, basic reference counting is
insufficient unless the cycle is explicitly broken.
</p>
</li>
<li>
<p>Atomic counting is relatively expensive in hardware.
</p>
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Solution</h2>
<p>Thread-safe reference counting is like serial reference counting,
except that the increment/decrement is done atomically, and the decrement and
test "count is zero?" must act as a single atomic operation. The
following example uses
<samp class="codeph">tbb::atomic<int></samp> to achieve this.
</p>
<pre>template<typename T>
class counted {
tbb::atomic<int> my_count;
T value;
public:
// Construct object with a single reference to it.
counted() {my_count=1;}
// Add reference
void add_ref() {++my_count;}
// Remove reference. Return true if it was the last reference.
bool remove_ref() {return ‐‐my_count==0;}
// Get reference to underlying object
T& get() {
assert(my_count>0);
return my_value;
}
};</pre>
<p>It is incorrect to use a separate read for testing if the count is
zero. The following code would be an incorrect implementation of method
<samp class="codeph">remove_ref</samp>() because two threads might both execute
the decrement, and then both read
<samp class="codeph">my_count</samp> as zero. Hence two callers would both be told
incorrectly that they had removed the last reference.
</p>
<pre> ‐‐my_count;
return my_count==0. <span style="color:blue"><strong>// WRONG!</strong></span></pre>
<p>The decrement may need to have a
<em>release</em> fence so that any pending writes complete before the
object is deleted.
</p>
<p>There is no simple way to atomically copy a pointer and increment its
reference count, because there will be a timing hole between the copying and
the increment where the reference count is too low, and thus another thread
might decrement the count to zero and delete the object. Two ways to address
the problem are "hazard pointers" and "pass the buck". See the references below
for details.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Variations</h2>
<p>Atomic increment/decrement can be more than an order of magnitude more
expensive than ordinary increment/decrement. The serial optimization of
eliminating redundant increment/decrement operations becomes more important
with atomic reference counts.
</p>
<p>Weighted reference counting can be used to reduce costs if the
pointers are unshared but the referent is shared. Associate a
<em>weight</em> with each pointer. The reference count is the sum of the
weights. A pointer
<samp class="codeph">x</samp> can be copied as a pointer
<samp class="codeph">x</samp>' without updating the reference count by splitting
the original weight between x and x'. If the weight of x is too low to split,
then first add a constant W to the reference count and weight of x.
</p>
</div>
<div class="section"><h2 class="sectiontitle">References</h2>
<p>D. Bacon and V.T. Rajan, "Concurrent Cycle Collection in Reference
Counted Systems" in
<cite>Proc. European Conf. on Object-Oriented Programming</cite> (June
2001). Describes a garbage collector based on reference counting that does
collect cycles.
</p>
<p>M. Michael, "Hazard Pointers: Safe Memory Reclamation for Lock-Free
Objects" in IEEE Transactions on Parallel and Distributed Systems (June 2004).
Describes the "hazard pointer" technique.
</p>
<p>M. Herlihy, V. Luchangco, and M. Moir, "The Repeat Offender Problem: A
Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures" in
<cite>Proceedings of the 16th International Symposium on Distributed
Computing</cite> (Oct. 2002). Describes the "pass the buck" technique.
</p>
</div>
</div>
<div class="familylinks">
<div class="parentlink"><strong>Parent topic:</strong> <a href="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">Design Patterns</a></div>
</div>
<div></div>
</body>
</html>
|
