Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Highly-Concurrent Multi-word Synchronization

(Extended Abstract)

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4904))

Included in the following conference series:

Abstract

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modifyk arbitrary locations, such ask-read-modify-write (kRMW). Aiming to increase concurrency in order to exploit the parallelism offered by today’s multi-core and multiprocessing architectures, we propose a software implementation ofkRMW that efficiently breaks apart delay chains. Our algorithm ensures that two operations delay each other only if they are within distanceO(k) in theconflict graph, dynamically induced by the operations’ data items.

The algorithm usesdouble compare-and-swap (DCAS). WhenDCAS is not supported by the architecture, the algorithm of Attiya and Dagan [3] can be used to replaceDCAS with (unary)CAS, with only a slight increase in the interference among operations.

Supported by theIsrael Science Foundation (grant number 953/06). The full version of this paper is available fromhttp://www.cs.technion.ac.il/ hagit/publications/

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations. In: PODC 1997, pp. 111–120 (1997)

    Google Scholar 

  2. Anderson, J.H., Moir, M.: Universal constructions for multi-object operations. In: PODC 1995, pp. 184–193 (1995)

    Google Scholar 

  3. Attiya, H., Dagan, E.: Improved implementations of binary universal operations. J. ACM 48(5), 1013–1037 (2001)

    Article MathSciNet  Google Scholar 

  4. Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. John Wiley & Sons, West Sussex (2004)

    Google Scholar 

  5. Barnes, G.: A method for implementing lock-free shared-data structures. In: SPAA 1993, pp. 261–270 (1993)

    Google Scholar 

  6. Choy, M., Singh, A.K.: Efficient fault-tolerant algorithms for distributed resource allocation. ACM Trans. Program. Lang. Syst. 17(3), 535–559 (1995)

    Article  Google Scholar 

  7. Ha, P.H., Tsigas, P., Wattenhofer, M., Wattenhofer, R.: Efficient multi-word locking using randomization. In: PODC 2005, pp. 249–257 (2005)

    Google Scholar 

  8. Harris, T.L., Fraser, K., Pratt, I.A.: A practical multi-word compare-and-swap operation. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 265–279. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  9. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)

    Article  Google Scholar 

  10. Herlihy, M., Moss, J.E.B.: Transactional memory: Architectural support for lock-free data structures. In: ISCA 1993, pp. 289–300 (1993)

    Google Scholar 

  11. Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)

    Article  Google Scholar 

  12. Israeli, A., Rappoport, L.: Disjoint-access-parallel implementations of strong shared memory primitives. In: PODC 1994, pp. 151–160 (1994)

    Google Scholar 

  13. Rajwar, R., Goodman, J.R.: Transactional lock-free execution of lock-based programs. In: ASPLOS 2002, pp. 5–17 (2002)

    Google Scholar 

  14. Shavit, N., Touitou, D.: Software transactional memory. Dist. Comp. 10(2), 99–116 (1997)

    Article  Google Scholar 

  15. Turek, J., Shasha, D., Prakash, S.: Locking without blocking: Making lock based concurrent data structure algorithms nonblocking. In: PODS 1992, pp. 212–222 (1992)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Technion,  

    Hagit Attiya & Eshcar Hillel

Authors
  1. Hagit Attiya

    You can also search for this author inPubMed Google Scholar

  2. Eshcar Hillel

    You can also search for this author inPubMed Google Scholar

Editor information

Shrisha Rao Mainak Chatterjee Prasad Jayanti C. Siva Ram Murthy Sanjoy Kumar Saha

Rights and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Attiya, H., Hillel, E. (2007). Highly-Concurrent Multi-word Synchronization. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds) Distributed Computing and Networking. ICDCN 2008. Lecture Notes in Computer Science, vol 4904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77444-0_9

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp