{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T08:45:25Z","timestamp":1725871525011},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319495828"},{"type":"electronic","value":"9783319495835"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-49583-5_4","type":"book-chapter","created":{"date-parts":[[2016,11,24]],"date-time":"2016-11-24T08:11:09Z","timestamp":1479975069000},"page":"55-73","source":"Crossref","is-referenced-by-count":5,"title":["A Portable Lock-Free Bounded Queue"],"prefix":"10.1007","author":[{"given":"Peter","family":"Pirkelbauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reed","family":"Milewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan Felipe","family":"Gonzalez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,25]]},"reference":[{"issue":"1","key":"4_CR1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/2480359.2429099","volume":"48","author":"M Batty","year":"2013","unstructured":"Batty, M., Dodds, M., Gotsman, A.: Library abstraction for C\/C++ concurrency. SIGPLAN Not. 48(1), 235\u2013248 (2013)","journal-title":"SIGPLAN Not."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Boehm, H.-J., Adve, S.V.: Foundations of the C++ concurrency memory model. In: PLDI 2008, pp. 68\u201378. ACM (2008)","DOI":"10.1145\/1375581.1375591"},{"issue":"3","key":"4_CR3","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/2835260.2835264","volume":"15","author":"S Feldman","year":"2015","unstructured":"Feldman, S., Dechev, D.: A wait-free multi-producer multi-consumer ring buffer. SIGAPP Appl. Comput. Rev. 15(3), 59\u201371 (2015)","journal-title":"SIGAPP Appl. Comput. Rev."},{"key":"4_CR4","unstructured":"Franke, H., Russell, R., Kirkwood, M.: Fuss, futexes, furwocks: fast user level locking in linux. In: Linux Symposium in Ottawa, pp. 479\u2013491 (2002)"},{"issue":"2","key":"4_CR5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1233307.1233309","volume":"25","author":"K Fraser","year":"2007","unstructured":"Fraser, K., Harris, T.: Concurrent programming without locks. ACM Trans. Comput. Syst. 25(2), 5 (2007)","journal-title":"ACM Trans. Comput. Syst."},{"key":"4_CR6","unstructured":"Frechilla, F.: Yet another implementation of a lock-free circular array queue, April 2011. http:\/\/www.codeproject.com\/Articles\/153898\/Yet-another-implementation-of-a-lock-free-circular . Accessed 3 Mar 2013"},{"key":"4_CR7","volume-title":"Audio Anecdotes II: Tools, Tips, and Techniques for Digital Audio","author":"K Greenebaum","year":"2004","unstructured":"Greenebaum, K., Barzel, R.: Audio Anecdotes II: Tools, Tips, and Techniques for Digital Audio. A K Peters\/CRC Press, Natick (2004)"},{"key":"4_CR8","unstructured":"Hedstr\u00f6m, K.: Lock-free single-producer - single consumer circular queue, December 2012. http:\/\/www.codeproject.com\/Articles\/43510\/Lock-Free-Single-Producer-Single-Consumer-Circular . Accessed 10 Jan 2013"},{"key":"4_CR9","unstructured":"Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming, revised 1st edn. Morgan Kaufmann Publishers Inc., San Francisco (2012)"},{"issue":"3","key":"4_CR10","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"MP Herlihy","year":"1990","unstructured":"Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"4_CR11","unstructured":"ISO\/IEC 14882 International Standard. Programming Language C++. JTC1\/SC22\/WG21 - The C++ Standards Committee (2011)"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Kirsch, C., Lippautz, M., Payer, H.: Fast and scalable k-FIFO queues. Technical report TR2012-04, University of Salzburg (2012)","DOI":"10.1007\/978-3-642-39958-9_18"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Kogan, A., Petrank, E.: Wait-free queues with multiple enqueuers and dequeuers. In: PPoPP 2011, pp. 223\u2013234. ACM, New York (2011)","DOI":"10.1145\/1941553.1941585"},{"issue":"2","key":"4_CR14","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1145\/69624.357207","volume":"5","author":"L Lamport","year":"1983","unstructured":"Lamport, L.: Specifying concurrent program modules. ACM Trans. Program. Lang. Syst. 5(2), 190\u2013222 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Lee, P.P.C., Bu, T., Chandranmenon, G.: A lock-free, cache-efficient shared ring buffer for multi-core architectures. In: ANCS 2009, pp. 78\u201379. ACM, New York (2009)","DOI":"10.1145\/1882486.1882508"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Luchangco, V., Moir, M., Shavit, N.: Nonblocking k-compare-single-swap. In: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2003, pp. 314\u2013323. ACM, New York (2003)","DOI":"10.1145\/777412.777468"},{"key":"4_CR17","unstructured":"McKenney, P.: Memory ordering in modern microprocessors (draft), September 2007. http:\/\/www.rdrop.com\/users\/paulmck\/scalability\/paper\/ordering.2007.09.19a.pdf . Accessed 20 Feb 2013"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Michael, M.M.: Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In: PODC 2002, pp. 21\u201330. ACM, New York (2002)","DOI":"10.1145\/571825.571829"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/978-3-540-45209-6_92","volume-title":"Euro-Par 2003 Parallel Processing","author":"MM Michael","year":"2003","unstructured":"Michael, M.M.: CAS-based lock-free algorithm for shared deques. In: Kosch, H., B\u00f6sz\u00f6rm\u00e9nyi, L., Hellwagner, H. (eds.) Euro-Par 2003. LNCS, vol. 2790, pp. 651\u2013660. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-45209-6_92"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Moir, M., Nussbaum, D., Shalev, O., Shavit, N.: Using elimination to implement scalable and lock-free FIFO queues. In: SPAA 2005, pp. 253\u2013262. ACM, New York (2005)","DOI":"10.1145\/1073970.1074013"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Norris, B., Demsky, B.: CDSchecker: checking concurrent data structures written with C\/C++ atomics. In: OOPSLA 2013, pp. 131\u2013150. ACM, New York (2013)","DOI":"10.1145\/2509136.2509514"},{"key":"4_CR22","unstructured":"Pirkelbauer, P.: Non-blocking programming techniques. University of Innsbruck, Invited Talk (2013)"},{"key":"4_CR23","unstructured":"Pirkelbauer, P.: Portable non-blocking data structures. University of Alabama, Invited Talk (2013)"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Sarkar, S., Memarian, K., Owens, S., Batty, M., Sewell, P., Maranget, L., Alglave, J., Williams, D.: Synchronising C\/C++ and POWER. In: PLDI, PLDI 2012, pp. 311\u2013322. ACM, New York (2012)","DOI":"10.1145\/2345156.2254102"},{"issue":"4","key":"4_CR25","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1145\/265924.265927","volume":"15","author":"S Savage","year":"1997","unstructured":"Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T.: Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15(4), 391\u2013411 (1997)","journal-title":"ACM Trans. Comput. Syst."},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-92295-7_10","volume-title":"Distributed Computing and Networking","author":"N Shafiei","year":"2008","unstructured":"Shafiei, N.: Non-blocking array-based algorithms for stacks and queues. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) ICDCN 2009. LNCS, vol. 5408, pp. 55\u201366. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-92295-7_10"},{"key":"4_CR27","unstructured":"Shann, C.-H., Huang, T.L., Chen, C.: A practical nonblocking queue algorithm using compare-and-swap. In: 7th International Conference on Parallel and Distributed Systems, pp. 470\u2013475 (2000)"},{"key":"4_CR28","unstructured":"Dechev, D., Feldman, S., LaBorde, P.: Tervel (2015). http:\/\/ucf-cs.github.io\/Tervel\/"},{"key":"4_CR29","unstructured":"Stone, J.M.: A nonblocking compare-and-swap algorithm for a shared circular queue. In: Parallel and Distributed Computing in Engineering Systems, pp. 147\u2013152. Elsevier Science B.V. (1992)"},{"key":"4_CR30","volume-title":"The C++ Programming Language","author":"B Stroustrup","year":"2013","unstructured":"Stroustrup, B.: The C++ Programming Language, 4th edn. Addison-Wesley Professional, Salt Lake City (2013)","edition":"4"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Tsigas, P., Zhang, Y.: A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. In: SPAA 2001, pp. 134\u2013143. ACM, New York (2001)","DOI":"10.1145\/378580.378611"},{"key":"4_CR32","unstructured":"Vyukov, D.: Bounded MPMC queue (2013). http:\/\/www.1024cores.net\/home\/lock-free-algorithms\/queues\/bounded-mpmc-queue . Accessed 21 May 2016"},{"key":"4_CR33","volume-title":"C++ Concurrency in Action: Practical Multithreading","author":"A Williams","year":"2012","unstructured":"Williams, A.: C++ Concurrency in Action: Practical Multithreading. Manning Publications, Shelter Island (2012)"},{"key":"4_CR34","doi-asserted-by":"crossref","unstructured":"Yang, C., Mellor-Crummey, J.: A wait-free queue as fast as fast as fetch-and-add. In: PPoPP 2016, pp. 16:1\u201316:13. ACM, New York (2016)","DOI":"10.1145\/2851141.2851168"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Architectures for Parallel Processing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-49583-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T18:58:16Z","timestamp":1657825096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-49583-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319495828","9783319495835"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-49583-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}