{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:18Z","timestamp":1750308438331,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T00:00:00Z","timestamp":1687219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>The MCS lock of Mellor-Crummey and Scott (1991), 23 pages. is a very efficient first-come first-served mutual-exclusion algorithm that uses the atomic hardware primitives fetch-and-store and compare-and-swap. However, it has the disadvantage that the calling thread must provide a pointer to an allocated record. This additional parameter violates the standard locking interface, which has only the lock as a parameter. Hence, it is impossible to switch to MCS without editing and recompiling an application that uses locks.<\/jats:p>\n          <jats:p>\n            This article provides a variation of MCS with the standard interface, which remains FCFS, called MCSH. One key ingredient is to\n            <jats:italic>stack<\/jats:italic>\n            allocate the necessary record in the\n            <jats:italic>acquire<\/jats:italic>\n            procedure of the lock, so its life-time only spans the delay to enter a critical section. A second key ingredient is communicating the allocated record between the\n            <jats:italic>acquire<\/jats:italic>\n            and\n            <jats:italic>release<\/jats:italic>\n            procedures through the lock to maintain the standard locking interface. Both of these practices are known to practitioners, but our solution combines them in a unique way. Furthermore, when these practices are used in prior papers, their correctness is often argued informally. The correctness of MCSH is verified rigorously with the proof assistant PVS, and experiments are run to compare its performance with MCS and similar locks.\n          <\/jats:p>","DOI":"10.1145\/3584696","type":"journal-article","created":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T11:48:02Z","timestamp":1676893682000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["MCSH, a Lock with the Standard Interface"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1413-4320","authenticated-orcid":false,"given":"Wim H.","family":"Hesselink","sequence":"first","affiliation":[{"name":"University of Groningen, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3747-9281","authenticated-orcid":false,"given":"Peter A.","family":"Buhr","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90224-P"},{"key":"e_1_3_4_3_2","unstructured":"M. A. Auslander D. J. Edelsohn O. Y. Krieger B. S. Rosenburg and R. W. Wisniewski. 2003. Enhancement to the MCS lock for increased functionality and improved programmability. U.S. patent application number 20030200457 (abondoned)."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3263."},{"key":"e_1_3_4_5_2","unstructured":"Peter A. Buhr David Dice and Wim H. Hesselink. 2022. Locking Micro-Benchmarks. Retrieved from https:\/\/github.com\/pabuhr\/concurrent-locking."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-67087-0_13"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461805"},{"key":"e_1_3_4_8_2","volume-title":"Cooperating Sequential Processes","author":"Dijkstra Edsger W.","year":"1965","unstructured":"Edsger W. Dijkstra. 1965. Cooperating Sequential Processes. Technical Report. Technological University, Eindhoven, 87 pages. https:\/\/pure.tue.nl\/ws\/files\/4279816\/344354178746665.pdf."},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/365559.365617"},{"key":"e_1_3_4_10_2","volume-title":"A Discipline of Programming","author":"Dijkstra E. W.","year":"1976","unstructured":"E. W. Dijkstra. 1976. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, NJ."},{"key":"e_1_3_4_11_2","unstructured":"Ulrich Drepper. 2022. Futexes Are Tricky Red Hat Inc. 12 pages. Retrieved from https:\/\/cis.temple.edu\/\u223cgiorgio\/cis307\/readings\/futex.pdf."},{"key":"e_1_3_4_12_2","unstructured":"Wim H. Hesselink. 2022. PVS Proof Scripts for Verification of Hardware Locks. Retrieved from http:\/\/wimhesselink.nl\/mechver\/HardwareLocks."},{"key":"e_1_3_4_13_2","article-title":"Trylock, a case for temporal logic and eternity variables","volume":"216","author":"Hesselink Wim H.","year":"2022","unstructured":"Wim H. Hesselink. 2022. Trylock, a case for temporal logic and eternity variables. Sci. Comput. Program. 216, C (April 2022), 12.","journal-title":"Sci. Comput. Program."},{"key":"e_1_3_4_14_2","unstructured":"IBM. 2021. Serially Reusable Programs. Retrieved from https:\/\/www.ibm.com\/docs\/en\/ztpf\/1.1.0.15?topic=structures-serially-reusable-programs."},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/361082.361093"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/7351.7352"},{"key":"e_1_3_4_17_2","unstructured":"Waiman Long. 2013. qspinlock: Introducing a 4-byte Queue Spinlock Implementation. Retrieved from https:\/\/lwn.net\/Articles\/561775."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/645604.662740"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/103727.103729"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_3_4_21_2","volume-title":"PVS Language Reference Version 7.1","author":"Owre S.","year":"2020","unstructured":"S. Owre, N. Shankar, J. M. Rushby, and D. W. J. Stringer-Calvert. 2020. PVS Language Reference Version 7.1. SRI International, Computer Science Laboratory, Menlo Park CA, 113 pages. Retrieved February 7, 2023 from https:\/\/pvs.csl.sri.com\/doc\/pvs-language-reference.pdf."},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/2534458"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851160"},{"key":"e_1_3_4_24_2","unstructured":"WikipediA. 2022. Application Binary Interface.Retrieved February 7 2023 from https:\/\/en.wikipedia.org\/wiki\/Application_binary_interface."},{"key":"e_1_3_4_25_2","unstructured":"WikipediA. 2022. Application Program Interface.Retrieved February 7 2023 from https:\/\/en.wikipedia.org\/wiki\/API."},{"key":"e_1_3_4_26_2","unstructured":"WikipediA. 2022. Thread-local Storage. Retrieved February 7 2023 from https:\/\/en.wikipedia.org\/wiki\/Thread-local_storage."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584696","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:50:00Z","timestamp":1750269000000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,20]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3584696"],"URL":"https:\/\/doi.org\/10.1145\/3584696","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2023,6,20]]},"assertion":[{"value":"2022-06-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}