679:
24:
303:
A key issue with the performance of concurrent data structures is the level of memory contention: the overhead in traffic to and from memory as a result of multiple threads concurrently attempting to access the same locations in memory. This issue is most acute with blocking implementations in which
279:
On today's machines, the layout of processors and memory, the layout of data in memory, the communication load on the various elements of the multiprocessor architecture all influence performance. Furthermore, there is a tension between correctness and performance: algorithmic enhancements that seek
308:
multiprocessor (one in which processors have local caches that are updated by hardware to keep them consistent with the latest values stored) this results in long waiting times for each attempt to modify the location, and is exacerbated by the additional memory traffic associated with unsuccessful
227:
The safety properties of concurrent data structures must capture their behavior given the many possible interleavings of methods called by different threads. It is quite intuitive to specify how abstract data structures behave in a sequential setting in which there are no interleavings. Therefore,
191:
Concurrent data structures, intended for use in parallel or distributed computing environments, differ from "sequential" data structures, intended for use on a uni-processor machine, in several ways. Most notably, in a sequential environment one specifies the data structure's properties and checks
287:
of the implementation. Speedup is a measure of how effectively the application is using the machine it is running on. On a machine with P processors, the speedup is the ratio of the structures execution time on a single processor to its execution time on P processors. Ideally, we want linear
174:
processors), the term has come to stand mainly for data structures that can be accessed by multiple threads which may actually access the data simultaneously because they run on different processors that communicate with one another. The concurrent data structure (sometimes also called a
275:
The primary source of this additional difficulty is concurrency, exacerbated by the fact that threads must be thought of as being completely asynchronous: they are subject to operating system preemption, page faults, interrupts, and so on.
200:
which an implementation must provide. Safety properties usually state that something bad never happens, while liveness properties state that something good keeps happening. These properties can be expressed, for example, using
247:
as to the results of their simultaneous data access and modification requests. To support such agreement, concurrent data structures are implemented using special primitive synchronization operations (see
220:. Data structures are not restricted to one type or the other, and can allow combinations where some method calls are blocking and others are non-blocking (examples can be found in the
159:/interleaving of the threads' operations on the data by the operating system, even though the processors never issued two operations that accessed the data simultaneously.
460:
454:
500:
385:
588:
41:
240:, and quiescent consistency) specify the structures properties sequentially, and map its concurrent executions to a collection of sequential ones.
550:
386:"More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms"
352:
704:
272:
Concurrent data structures are significantly more difficult to design and to verify as being correct than their sequential counterparts.
88:
583:
573:
493:
249:
243:
To guarantee the safety and liveness properties, concurrent data structures must typically (though not always) allow threads to reach
60:
578:
107:
183:, though this memory may be physically implemented as either a "tightly coupled" or a distributed collection of storage modules.
67:
288:
speedup: we would like to achieve a speedup of P when using P processors. Data structures whose speedup grows with P are called
523:
152:
45:
649:
304:
locks control access to memory. In order to acquire a lock, a thread must repeatedly attempt to modify that location. On a
74:
683:
486:
244:
659:
644:
639:
56:
292:. The extent to which one can scale the performance of a concurrent data structure is captured by a formula known as
180:
280:
to improve performance often make it more difficult to design and verify a correct data structure implementation.
634:
396:
209:
129:
475:– C/C++ and Java libraries and benchmarks of lock-free, lock-based, TM-based and RCU/COW-based data structures.
264:. There is a wide body of theory on the design of concurrent data structures (see bibliographical references).
256:
that allow multiple threads to reach consensus. This consensus can be achieved in a blocking manner by using
664:
34:
261:
237:
217:
538:
202:
81:
509:
228:
many mainstream approaches for arguing the safety properties of a concurrent data structure (such as
213:
528:
148:
133:
425:
and
Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"
367:
324:
167:
393:
Proceedings of the 20th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming
297:
144:
598:
565:
318:
221:
121:
555:
545:
434:
305:
253:
233:
229:
293:
654:
163:
698:
613:
593:
128:
is a particular way of storing and organizing data for access by multiple computing
603:
422:
359:
156:
140:
629:
416:
23:
472:
438:
348:
171:
179:) is usually considered to reside in an abstract storage environment called
428:
257:
208:
The type of liveness requirements tend to define the data structure. The
469:– C++ library of lock-free containers and safe memory reclamation schema
478:
284:
170:
become the dominant computing platform (through the proliferation of
196:. In a concurrent environment, the specification must also describe
463:(Designing concurrent data structures without mutexes) by Arpan Sen
444:
Mattson, Sanders, and
Massingil "Patterns for Parallel Programming"
431:, "Concurrent Programming in Java: Design Principles and Patterns"
366:. Chapman and Hall/CRC Press. pp. 47-14–47-30. Archived from
466:
608:
482:
283:
A key measure for performance is scalability, captured by the
17:
461:
Multithreaded data structures for parallel computing: Part 2
455:
Multithreaded data structures for parallel computing, Part 1
622:
564:
516:
457:(Designing concurrent data structures) by Arpan Sen
48:. Unsourced material may be challenged and removed.
192:that they are implemented correctly, by providing
139:Historically, such data structures were used on
147:that supported multiple computing threads (or
494:
8:
364:Handbook of Data Structures and Applications
501:
487:
479:
441:, "The Art of Multiprocessor Programming"
296:and more refined versions of it such as
108:Learn how and when to remove this message
260:, or without locks, in which case it is
342:
340:
336:
7:
395:. ACM. pp. 1–10. Archived from
166:computer architectures that provide
46:adding citations to reliable sources
14:
678:
677:
22:
33:needs additional citations for
684:Category: Concurrent computing
309:attempts to acquire the lock.
1:
353:"Concurrent Data Structures"
705:Distributed data structures
645:Dining philosophers problem
57:"Concurrent data structure"
721:
534:Concurrent data structures
250:synchronization primitives
673:
650:Producer–consumer problem
635:Cigarette smokers problem
268:Design and implementation
126:concurrent data structure
665:Sleeping barber problem
660:Readers–writers problem
419:"Distributed Computing"
254:multiprocessor machines
539:Concurrent hash tables
252:) available on modern
238:sequential consistency
203:Linear Temporal Logic
177:shared data structure
510:Concurrent computing
384:Gramoli, V. (2015).
42:improve this article
529:Concurrency control
358:. In Dinesh Metha;
224:software library).
198:liveness properties
325:Java ConcurrentMap
692:
691:
402:on 10 April 2015.
194:safety properties
145:operating systems
136:) on a computer.
118:
117:
110:
92:
712:
681:
680:
623:Classic problems
599:Ambient calculus
546:Concurrent users
503:
496:
489:
480:
404:
403:
401:
390:
381:
375:
374:
373:on 1 April 2011.
372:
357:
344:
319:Java concurrency
222:Java concurrency
187:Basic principles
122:computer science
113:
106:
102:
99:
93:
91:
50:
26:
18:
720:
719:
715:
714:
713:
711:
710:
709:
695:
694:
693:
688:
669:
618:
566:Process calculi
560:
556:Linearizability
512:
507:
451:
435:Maurice Herlihy
413:
411:Further reading
408:
407:
399:
388:
383:
382:
378:
370:
355:
346:
345:
338:
333:
315:
298:Gustafson's law
270:
234:linearizability
230:serializability
189:
114:
103:
97:
94:
51:
49:
39:
27:
12:
11:
5:
718:
716:
708:
707:
697:
696:
690:
689:
687:
686:
674:
671:
670:
668:
667:
662:
657:
655:Race condition
652:
647:
642:
637:
632:
626:
624:
620:
619:
617:
616:
611:
606:
601:
596:
591:
586:
581:
576:
570:
568:
562:
561:
559:
558:
553:
548:
543:
542:
541:
531:
526:
520:
518:
514:
513:
508:
506:
505:
498:
491:
483:
477:
476:
470:
464:
458:
450:
449:External links
447:
446:
445:
442:
432:
426:
420:
412:
409:
406:
405:
376:
335:
334:
332:
329:
328:
327:
322:
314:
311:
306:cache-coherent
269:
266:
188:
185:
164:multiprocessor
143:machines with
116:
115:
30:
28:
21:
13:
10:
9:
6:
4:
3:
2:
717:
706:
703:
702:
700:
685:
676:
675:
672:
666:
663:
661:
658:
656:
653:
651:
648:
646:
643:
641:
638:
636:
633:
631:
628:
627:
625:
621:
615:
614:Join-calculus
612:
610:
607:
605:
602:
600:
597:
595:
592:
590:
587:
585:
582:
580:
577:
575:
572:
571:
569:
567:
563:
557:
554:
552:
551:Indeterminacy
549:
547:
544:
540:
537:
536:
535:
532:
530:
527:
525:
522:
521:
519:
515:
511:
504:
499:
497:
492:
490:
485:
484:
481:
474:
471:
468:
465:
462:
459:
456:
453:
452:
448:
443:
440:
436:
433:
430:
427:
424:
421:
418:
415:
414:
410:
398:
394:
387:
380:
377:
369:
365:
361:
354:
350:
343:
341:
337:
330:
326:
323:
320:
317:
316:
312:
310:
307:
301:
299:
295:
291:
286:
281:
277:
273:
267:
265:
263:
259:
255:
251:
246:
241:
239:
235:
231:
225:
223:
219:
215:
212:calls can be
211:
206:
204:
199:
195:
186:
184:
182:
181:shared memory
178:
173:
169:
165:
160:
158:
155:captured the
154:
150:
146:
142:
137:
135:
131:
127:
123:
112:
109:
101:
98:November 2009
90:
87:
83:
80:
76:
73:
69:
66:
62:
59: –
58:
54:
53:Find sources:
47:
43:
37:
36:
31:This article
29:
25:
20:
19:
16:
604:API-Calculus
533:
473:Synchrobench
423:Hagit Attiya
397:the original
392:
379:
368:the original
363:
360:Sartaj Sahni
302:
294:Amdahl's law
289:
282:
278:
274:
271:
262:non-blocking
242:
226:
218:non-blocking
207:
197:
193:
190:
176:
161:
157:multiplexing
151:). The term
141:uniprocessor
138:
125:
119:
104:
95:
85:
78:
71:
64:
52:
40:Please help
35:verification
32:
15:
630:ABA problem
524:Concurrency
417:Nancy Lynch
347:Mark Moir;
168:parallelism
153:concurrency
594:Ď€-calculus
439:Nir Shavit
349:Nir Shavit
331:References
172:multi-core
162:Today, as
68:newspapers
321:(JSR 166)
245:consensus
149:processes
134:processes
699:Category
640:Deadlock
429:Doug Lea
362:(eds.).
351:(2007).
313:See also
290:scalable
214:blocking
517:General
285:speedup
130:threads
82:scholar
682:
467:libcds
210:method
84:
77:
70:
63:
55:
589:LOTOS
400:(PDF)
389:(PDF)
371:(PDF)
356:(PDF)
258:locks
89:JSTOR
75:books
609:PEPA
437:and
132:(or
124:, a
61:news
584:ACP
579:CCS
574:CSP
216:or
120:In
44:by
701::
391:.
339:^
300:.
236:,
232:,
205:.
502:e
495:t
488:v
111:)
105:(
100:)
96:(
86:·
79:·
72:·
65:·
38:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
