{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T05:47:54Z","timestamp":1782625674826,"version":"3.54.5"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            Mutual exclusion locks remain the\n            <jats:italic>de facto<\/jats:italic>\n            mechanism for concurrency control on shared-memory data structures. However, their apparent simplicity is deceptive: It is hard to design scalable locking strategies because locks can harbor problems such as priority inversion, deadlock, and convoying. Furthermore, scalable lock-based systems are not readily composable when building compound operations. In looking for solutions to these problems, interest has developed in\n            <jats:italic>nonblocking<\/jats:italic>\n            systems which have promised scalability and robustness by eschewing mutual exclusion while still ensuring safety. However, existing techniques for building nonblocking systems are rarely suitable for practical use, imposing substantial storage overheads, serializing nonconflicting operations, or requiring instructions not readily available on today's CPUs.\n          <\/jats:p>\n          <jats:p>\n            In this article we present three APIs which make it easier to develop nonblocking implementations of arbitrary data structures. The first API is a\n            <jats:italic>multiword compare-and-swap<\/jats:italic>\n            operation (MCAS) which atomically updates a set of memory locations. This can be used to advance a data structure from one consistent state to another. The second API is a\n            <jats:italic>word-based software transactional memory<\/jats:italic>\n            (WSTM) which can allow sequential code to be reused more directly than with MCAS and which provides better scalability when locations are being read rather than being updated. The third API is an\n            <jats:italic>object-based software transactional memory<\/jats:italic>\n            (OSTM). OSTM allows a simpler implementation than WSTM, but at the cost of reengineering the code to use OSTM objects.\n          <\/jats:p>\n          <jats:p>We present practical implementations of all three of these APIs, built from operations available across all of today's major CPU families. We illustrate the use of these APIs by using them to build highly concurrent skip lists and red-black trees. We compare the performance of the resulting implementations against one another and against high-performance lock-based systems. These results demonstrate that it is possible to build useful nonblocking data structures with performance comparable to, or better than, sophisticated lock-based designs.<\/jats:p>","DOI":"10.1145\/1233307.1233309","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"5","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":148,"title":["Concurrent programming without locks"],"prefix":"10.1145","volume":"25","author":[{"given":"Keir","family":"Fraser","sequence":"first","affiliation":[{"name":"University of Cambridge Computer Laboratory, Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Harris","sequence":"additional","affiliation":[{"name":"Microsoft Research Cambridge, Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2005.41"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224985"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259443"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165265"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_14"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571874"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024393.1024395"},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 3rd Workshop on Algorithm Engineering","author":"Hanke S."},{"key":"e_1_2_1_12_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 3rd Italian Conference on Algorithms and Complexity","author":"Hanke S."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/645958.676105"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the PODC Workshop on Synchronization in Java Programs. 46--53. Proceedings published as Memorial University of Newfoundland CS Tech. Rep. 2004-01","author":"Harris T.","year":"2004"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/949305.949340"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065944.1065954"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065944.1065952"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_3"},{"key":"e_1_2_1_19_1","unstructured":"Hennessy J. L. and Patterson D. A. 2003. Computer Architecture---A Quantitative Approach 3rd ed. Morgan Kaufmann San Francisco CA.   Hennessy J. L. and Patterson D. A. 2003. Computer Architecture---A Quantitative Approach 3rd ed. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/161468.161469"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062247.1062249"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE","author":"Herlihy M."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_27_1","volume-title":"Operating Systems Techniques. A.P.I.C. Studies in Data Processing","author":"Hoare C. A. R."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198079"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872078"},{"key":"e_1_2_1_30_1","volume-title":"Garbage Collection: Algorithms for Automatic Dynamic Memory Management","author":"Jones R.","year":"1996"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320619"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066650.1066660"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2005.11"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/103727.103729"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/109625.109637"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571829"},{"key":"e_1_2_1_38_1","volume-title":"Tech. Rep. TR599","author":"Michael M. M.","year":"1995"},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Computer Science","volume-title":"Distributed Algorithms, 11th International Workshop","author":"Moir M."},{"key":"e_1_2_1_40_1","unstructured":"Moir M. 2002. Personal communication.  Moir M. 2002. Personal communication."},{"key":"e_1_2_1_41_1","unstructured":"Moore K. E. Hill M. D. and Wood D. A. 2005. Thread-Level transactional memory. Tech. Rep.: CS-TR-2005-1524 Deptartment of Computer Sciences University of Wisconsin Motorola Inc. Phoenix AZ. 1--11.  Moore K. E. Hill M. D. and Wood D. A. 2005. Thread-Level transactional memory. Tech. Rep.: CS-TR-2005-1524 Deptartment of Computer Sciences University of Wisconsin Motorola Inc. Phoenix AZ. 1--11."},{"key":"e_1_2_1_42_1","unstructured":"Motorola. 1985. MC68020 32-Bit Microprocessor User's Manual.   Motorola. 1985. MC68020 32-Bit Microprocessor User's Manual."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/605432.605399"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.54"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_20"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086365.1086378"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073861"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872049"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224987"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968188"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137873"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the European Conference on Object-Oriented Programming (ECOOP). 519--542","author":"Welc A."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1993.1015"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1233307.1233309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1233307.1233309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:51:51Z","timestamp":1750258311000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1233307.1233309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1233307.1233309"],"URL":"https:\/\/doi.org\/10.1145\/1233307.1233309","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}