Woelfel, PhilippHigham, LisaAghazadeh, Zahra2018-04-272018-04-272018-04-26Aghazadeh, Z. (2018). Efficient Shared Memory Algorithms for Bounding Space (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/31853http://hdl.handle.net/1880/106567It is the state of the art that computer systems use multi-core architectures. In order to exploit the benefits of parallelism, multiple processors have to cooperate and concurrently communicate by executing operations on shared objects. It is challenging in shared memory algorithms to deal with the inherent asynchrony of processes. To overcome this difficulty and to achieve high efficiency, algorithm designers often assume unbounded space. This work focuses on designing time-efficient shared memory algorithms while avoiding unbounded space. One example is that of making shared objects writable: Many standard primitives (for instance, compare-and-swap or fetch-and-add) do not provide a Write() operation that unconditionally changes the object's state to the one provided as a parameter. Adding Write() operations without sacrificing efficiency is challenging if space is limited. We provide a space-efficient solution for making synchronization primitives writable with optimal step complexity. A special case of making an object writable is to augment non-resettable objects with Reset() operations. We show how our general transformation can be improved to achieve optimal space implementations of long-lived test-and-set objects with time-efficient Reset() operations. Another example concerns the ABA problem: Even though a process retrieves the same value twice in a row from a shared object, it is still possible that the value of the object has changed multiple times. We investigate the time and space complexity of detecting ABAs in shared memory algorithms for systems with bounded base objects. To that end, we propose a new primitive called an ABA-detecting register, and we give an efficient implementation of this type using asymptotically optimal number of bounded registers. Finally we deal with a more general unbounded space problem: Many applications employ the tagging technique, where shared objects get augmented with additional values, called tags. Unbounded tags are mainly used in those applications, because bounding them is too complicated and error prone. We introduce a new primitive that provides an abstraction for avoiding unbounded tags. Also, we propose optimally time-efficient implementations of this primitive from bounded objects. In addition to straightforward applications that use tags directly, our implementations can also often be used for memory reclamation.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Distributed ComputingShared MemoryMemory ManagementBounded SpaceWritable ObjectsLong-Lived Test-And-SetTaggingABA ProblemDistributed SystemsMulti-coreMulti-ThreadComputer Sciencedoctoral thesis10.11575/PRISM/31853