Skip to main content
Erschienen in: Theory of Computing Systems 4/2013

01.05.2013

Built-in Coloring for Highly-Concurrent Doubly-Linked Lists

verfasst von: Hagit Attiya, Eshcar Hillel

Erschienen in: Theory of Computing Systems | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper presents a novel approach for highly-concurrent nonblocking implementations of doubly-linked lists, based on dynamically maintaining a coloring of the nodes in the list. In these implementations, operations on non-adjacent nodes in the linked-list proceed without interfering with each other. Roughly speaking, the operations are implemented by acquiring nodes in the operation’s data set, in the order of their colors, and then making the changes atomically. The length of waiting chains is restricted, thereby increasing concurrency, because the colors are taken from a small set. Operations carefully update the colors of the nodes they modify, so neighboring nodes in the list have different colors. A helping mechanism ensures progress in small neighborhoods of processes that keep taking steps.
We use this approach in two new algorithms: CAS-Chromo uses an unary conditional primitive, cas, and allows insertions anywhere in the linked list and removals only at the ends, while DCAS-Chromo allows insertions and removals anywhere but uses a stronger primitive, dcas.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
This is similar to the way an operation is invalidated before releasing its nodes in [4].
 
Literatur
1.
Zurück zum Zitat Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 111–120 (1997) Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 111–120 (1997)
2.
Zurück zum Zitat Agesen, O., Detlefs, D.L., Flood, C.H., Garthwaite, A.T., Martin, P.A., Shavit, N., Steele, G.L.: DCAS-based concurrent deques. Theory Comput. Syst. 35(3), 349–386 (2002) MathSciNetMATHCrossRef Agesen, O., Detlefs, D.L., Flood, C.H., Garthwaite, A.T., Martin, P.A., Shavit, N., Steele, G.L.: DCAS-based concurrent deques. Theory Comput. Syst. 35(3), 349–386 (2002) MathSciNetMATHCrossRef
3.
Zurück zum Zitat Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. Theory Comput. Syst. 34(2), 115–144 (2001) MathSciNetMATH Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. Theory Comput. Syst. 34(2), 115–144 (2001) MathSciNetMATH
4.
Zurück zum Zitat Attiya, H., Dagan, E.: Improved implementations of binary universal operations. J. ACM 48(5), 1013–1037 (2001) MathSciNetCrossRef Attiya, H., Dagan, E.: Improved implementations of binary universal operations. J. ACM 48(5), 1013–1037 (2001) MathSciNetCrossRef
5.
6.
Zurück zum Zitat Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, New York (2004) Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, New York (2004)
7.
Zurück zum Zitat Barnes, G.: A method for implementing lock-free shared-data structures. In: Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 261–270 (1993) Barnes, G.: A method for implementing lock-free shared-data structures. In: Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 261–270 (1993)
8.
Zurück zum Zitat Detlefs, D., Flood, C.H., Garthwaite, A., Martin, P., Shavit, N., Steele, G.L. Jr.: Even better DCAS-based concurrent deques. In: Proceedings of the 14th International Conference on Distributed Computing (DISC), pp. 59–73 (2000) Detlefs, D., Flood, C.H., Garthwaite, A., Martin, P., Shavit, N., Steele, G.L. Jr.: Even better DCAS-based concurrent deques. In: Proceedings of the 14th International Conference on Distributed Computing (DISC), pp. 59–73 (2000)
9.
Zurück zum Zitat Doherty, S., Detlefs, D.L., Groves, L., Flood, C.H., Luchangco, V., Martin, P.A., Moir, M., Shavit, N., Steele, G.L. Jr.: DCAS is not a silver bullet for nonblocking algorithm design. In: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 216–224 (2004) Doherty, S., Detlefs, D.L., Groves, L., Flood, C.H., Luchangco, V., Martin, P.A., Moir, M., Shavit, N., Steele, G.L. Jr.: DCAS is not a silver bullet for nonblocking algorithm design. In: Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 216–224 (2004)
10.
Zurück zum Zitat Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free step complexity: Lock-free DCAS as an example. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp. 493–494 (2005) Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free step complexity: Lock-free DCAS as an example. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC), pp. 493–494 (2005)
11.
Zurück zum Zitat Greenwald, M.: Non-blocking synchronization and system design. PhD thesis, Stanford University, August 1999 Greenwald, M.: Non-blocking synchronization and system design. PhD thesis, Stanford University, August 1999
12.
Zurück zum Zitat Greenwald, M.: Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS. In: Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC), pp. 260–269 (2002) Greenwald, M.: Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS. In: Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC), pp. 260–269 (2002)
13.
Zurück zum Zitat Ha, P.H., Tsigas, P., Wattenhofer, M., Wattenhofer, R.: Efficient multi-word locking using randomization. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 249–257 (2005) Ha, P.H., Tsigas, P., Wattenhofer, M., Wattenhofer, R.: Efficient multi-word locking using randomization. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 249–257 (2005)
14.
Zurück zum Zitat Harris, T.L.: A pragmatic implementation of non-blocking linked-lists. In: Proceedings of the 15th International Conference on Distributed Computing (DISC), pp. 300–314 (2001) Harris, T.L.: A pragmatic implementation of non-blocking linked-lists. In: Proceedings of the 15th International Conference on Distributed Computing (DISC), pp. 300–314 (2001)
15.
Zurück zum Zitat Harris, T.L., Fraser, K.: Language support for lightweight transactions. In: Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pp. 388–402 (2003) Harris, T.L., Fraser, K.: Language support for lightweight transactions. In: Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pp. 388–402 (2003)
16.
Zurück zum Zitat Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990) CrossRef Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990) CrossRef
17.
Zurück zum Zitat Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), pp. 522–529 (2003) Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), pp. 522–529 (2003)
18.
Zurück zum Zitat IBM. IBM System/370 Extended Architecture, Principle of Operation. IBM Publication No. SA22-7085 (1983) IBM. IBM System/370 Extended Architecture, Principle of Operation. IBM Publication No. SA22-7085 (1983)
20.
Zurück zum Zitat Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In: Proceedings of the 14th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 73–82 (2002) Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In: Proceedings of the 14th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 73–82 (2002)
21.
Zurück zum Zitat Michael, M.M.: CAS-based lock-free algorithm for shared deques. In: Proceedings of the 9th Euro-Par Conference on Parallel Processing, pp. 651–660 (2003) Michael, M.M.: CAS-based lock-free algorithm for shared deques. In: Proceedings of the 9th Euro-Par Conference on Parallel Processing, pp. 651–660 (2003)
23.
Zurück zum Zitat Schneider, J., Wattenhofer, R.: Bounds on contention management algorithms. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pp. 441–451 (2009) CrossRef Schneider, J., Wattenhofer, R.: Bounds on contention management algorithms. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pp. 441–451 (2009) CrossRef
24.
Zurück zum Zitat Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput. 10(2), 99–116 (1997) CrossRef Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput. 10(2), 99–116 (1997) CrossRef
25.
Zurück zum Zitat Sundell, H.: Efficient and practical non-blocking data structures. PhD thesis, Chalmers University of Technology (2004) Sundell, H.: Efficient and practical non-blocking data structures. PhD thesis, Chalmers University of Technology (2004)
26.
Zurück zum Zitat Sundell, H., Tsigas, P.: Lock-free deques and doubly linked lists. J. Parallel Distrib. Comput. 68(7), 1008–1020 (2008) MATHCrossRef Sundell, H., Tsigas, P.: Lock-free deques and doubly linked lists. J. Parallel Distrib. Comput. 68(7), 1008–1020 (2008) MATHCrossRef
27.
Zurück zum Zitat Turek, J., Shasha, D., Prakash, S.: Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 212–222 (1992) Turek, J., Shasha, D., Prakash, S.: Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 212–222 (1992)
Metadaten
Titel
Built-in Coloring for Highly-Concurrent Doubly-Linked Lists
verfasst von
Hagit Attiya
Eshcar Hillel
Publikationsdatum
01.05.2013
Verlag
Springer-Verlag
Erschienen in
Theory of Computing Systems / Ausgabe 4/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-012-9420-5

Weitere Artikel der Ausgabe 4/2013

Theory of Computing Systems 4/2013 Zur Ausgabe