close

Вход

Забыли?

вход по аккаунту

?

Lock-free Skip Lists and Dictionaries

код для вставкиСкачать
Scalable and Lock-Free
Concurrent Dictionaries
HГҐkan Sundell
Philippas Tsigas
Outline
Synchronization Methods
п‚ў Dictionaries
п‚ў Concurrent Dictionaries
п‚ў
Previous results
пЃ¬ New Lock-Free Algorithm
пЃ¬
Experiments
п‚ў Conclusions
п‚ў
2
Synchronization
п‚ў
Shared data structures needs
synchronization
P1
P2
P3
п‚ў
Synchronization using Locks
пЃ¬
Mutually exclusive access to whole or parts
of the data structure
P1
P2
P3
3
Blocking Synchronization
п‚ў
Drawbacks
Blocking
пЃ¬ Priority Inversion
пЃ¬ Risk of deadlock
пЃ¬
п‚ў
Locks: Semaphores, spinning,
disabling interrupts etc.
пЃ¬
4
Reduced efficiency because of
reduced parallelism
Non-blocking Synchronization
п‚ў
Lock-Free Synchronization
пЃ¬
Optimistic approach (i.e. assumes no
interference)
1. The operation is prepared to later take effect
(unless interfered) using hardware atomic
primitives
2. Possible interference is detected via the atomic
primitives, and causes a retry
•
п‚ў
Wait-Free Synchronization
пЃ¬
5
Can cause starvation
Always finishes in a finite number of its
own steps.
Dictionaries (Sets)
Fundamental data structure
п‚ў Works on a set of <key,value> pairs
п‚ў Three basic operations:
п‚ў
пЃ¬
Insert(k,v): Adds a new item
v=FindKey(k): Finds the item <k,v>
пЃ¬ v=DeleteKey(k): Finds and removes
the item <k,v>
пЃ¬
6
Previous Non-blocking
Dictionaries
п‚ў
M. Michael: “High Performance Dynamic
Lock-Free Hash Tables and List-Based
Sets”, SPAA 2002
пЃ¬
Based on Singly-Linked List
• Linear time complexity!
пЃ¬
Fast Lock-Free Memory Management
• Causes retries of concurrent search operations!
пЃ¬
Building-block of Hash Tables
• Assumes each branch is of length <<10.
п‚ў
7
However, Hash Tables might not be
uniformly distributed.
Randomized Algorithm: Skip Lists
п‚ў
William Pugh: ”Skip Lists: A Probabilistic
Alternative to Balanced Trees”, 1990
пЃ¬
Layers of ordered lists with different
densities, achieves a tree-like behavior
Head
Tail
1
2
пЃ¬
8
3
4
5
6
7
Time complexity: O(log2N) – probabilistic!
…
25%
50%
New Lock-Free Concurrent
Skip List
пЃ¬
1
3
2
1
D
Define node state to depend on the
insertion status at lowest level as well
as a deletion flag
2
D
3
D
4
D
5
D
6
D
7
D
пЃ¬
Insert from lowest level going upwards
пЃ¬
Set deletion flag. Delete from
highest level going downwards
p
9
3
2
1
p
D
Overlapping operations on
Insert 2
shared data
2
п‚ў
Example: Insert operation 1
- which of 2 or 3 gets inserted?
п‚ў
Solution: Compare-And-Swap
atomic primitive:
CAS(p:pointer to word, old:word,
new:word):boolean
atomic do
if *p = old then
*p := new;
return true;
else return false;
10
4
3
Insert 3
Concurrent Insert vs. Delete
operations
п‚ў
b)
1
Problem:
2
Delete
3
Insert
- both nodes are deleted!
п‚ў
Solution (Harris et al): Use bit 0 of
pointer to mark deletion status
1
11
4
a)
b)
c)
2 *
a)
3
4
New Lock-Free Dictionary
- Techniques Summary
п‚ў
Based on Skip Lists
пЃ¬
п‚ў
п‚ў
Uses CAS atomic primitive
Lock-Free memory management
пЃ¬
пЃ¬
п‚ў
п‚ў
п‚ў
12
Treated as layers of ordered lists
IBM Freelists
Reference counting (Valois+Michael&Scott)
Helping scheme
Back-Off strategy
All together proved to be linearizable
Experiments
п‚ў
Experiment with 1-30 threads performed on
systems with 2 respective 64 cpu’s.
пЃ¬
пЃ¬
п‚ў
13
п‚ў
Each thread performs 20000 operations,
whereof the first total 50-10000 operations
are Insert’s, remaining are equally randomly
distributed over Insert, FindKey and
DeleteKey’s.
Fixed Skiplist maximum level of 10.
Compare with implementation by Michael,
using same scenarios.
Averaged execution time of 50 experiments.
SGI Origin 2000, 64 cpu’s.
14
Linux Pentium II, 2 cpu’s
15
Conclusions
п‚ў
п‚ў
Our lock-free implementation also includes
the value-oriented operations FindValue
and DeleteValue.
Our lock-free algorithm is suitable for both
pre-emptive as well as systems with full
concurrency
пЃ¬
п‚ў
16
Will be available as part of NOBLE software
library, http://www.noble-library.org
See Technical Report for full details,
http://www.cs.chalmers.se/~phs
Questions?
п‚ў
Contact Information:
пЃ¬
пЃ¬
пЃ¬
17
Address:
HГҐkan Sundell vs. Philippas Tsigas
Computing Science
Chalmers University of Technology
Email:
<phs , tsigas> @ cs.chalmers.se
Web:
http://www.cs.chalmers.se/~phs/warp
Dynamic Memory Management
Problem: System memory allocation
functionality is blocking!
п‚ў Solution (lock-free), IBM freelists:
п‚ў
пЃ¬
Pre-allocate a number of nodes, link
them into a dynamic stack structure,
and allocate/reclaim using CAS
Allocate
Head
Reclaim
18
Mem 1
Used 1
Mem 2
…
Mem n
The ABA problem
п‚ў
Problem: Because of concurrency
(pre-emption in particular), same
pointer value does not always mean
same node (i.e. CAS succeeds)!!!
Step 1:
1
6
7
3
7
4
Step 2:
19
2
4
The ABA problem
п‚ў
Solution: (Valois et al) Add reference
counting to each node, in order to prevent
nodes that are of interest to some thread to
be reclaimed until all threads have left the
node
New Step 2:
1 *
6 *
1
1
CAS Failes!
2
20
?
3
4
1
?
7
?
Helping Scheme
п‚ў
Threads need to traverse safely
2 *
1
4
or
п‚ў
4
Need to remove marked-to-be-deleted
nodes while traversing – Help!
Finds previous node, finish deletion and
continues traversing from previous node
1
21
2 *
?
?
п‚ў
1
2 *
4
Back-Off Strategy
п‚ў
п‚ў
п‚ў
22
For pre-emptive systems, helping is
necessary for efficiency and lock-freeness
For really concurrent systems, overlapping
CAS operations (caused by helping and
others) on the same node can cause
heavy contention
Solution: For every failed CAS attempt,
back-off (i.e. sleep) for a certain duration,
which increases exponentially
Non-blocking Synchronization
п‚ў
Lock-Free Synchronization
Avoids problems with locks
пЃ¬ Simple algorithms
пЃ¬ Fast when having low contention
пЃ¬
п‚ў
Wait-Free Synchronization
пЃ¬
Always finishes in a finite number of
its own steps.
• Complex algorithms
• Memory consuming
• Less efficient in average than lock-free
23
Full SGI
24
Full Linux
25
The algorithm in more detail
п‚ў
Insert:
1.
2.
3.
4.
5.
п‚ў
26
Create node with random height
Search position (Remember drops)
Insert or update on level 1
Insert on level 2 to top (unless
already deleted)
If already deleted then HelpDelete(1)
All of this while keeping track of
references, help deleted nodes etc.
The algorithm in more detail
п‚ў
DeleteKey
1.
2.
3.
4.
5.
п‚ў
27
Search position (Remember drops)
Mark node at level 1 as deleted, otherwise
fail
Mark next pointers on level 1 to top
Delete on level top to 1 while detecting
helping, indicate success
Free node
All of this while keeping track of
references, help deleted nodes etc.
The algorithm in more detail
п‚ў
HelpDelete(level)
1.
2.
3.
4.
п‚ў
28
Mark next pointer at level to top
Find previous node (info in node)
Delete on level unless already
helped, indicate success
Return previous node
All of this while keeping track of
references, help deleted nodes etc.
Correctness
п‚ў
Linearizability (Herlihy 1991)
пЃ¬
29
In order for an implementation to be
linearizable, for every concurrent
execution, there should exist an equal
sequential execution that respects the
partial order of the operations in the
concurrent execution
Correctness
п‚ў
п‚ў
Define precise sequential semantics
Define abstract state and its interpretation
пЃ¬
п‚ў
Define linearizability points
пЃ¬
п‚ў
Show that operations take effect atomically
at these points with respect to sequential
semantics
Creates a total order using the linearizability
points that respects the partial order
пЃ¬
30
Show that state is atomically updated
The algorithm is linearizable
Correctness
п‚ў
Lock-freeness
пЃ¬
п‚ў
At least one operation should always
make progress
There are no cyclic loop depencies,
and all potentially unbounded loops
are ”gate-keeped” by CAS operations
пЃ¬
The CAS operation guarantees that at
least one CAS will always succeed
• The algorithm is lock-free
31
Документ
Категория
Презентации
Просмотров
6
Размер файла
326 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа