A Study of Software Primitives in the context of Concurrent Data Structures

A Study of Software Primitives in the context of Concurrent Data Structures Estudio de Primitivas en Software en el contexto de Estructuras de Datos Concurrentes UNIVERSIDAD COMPLUTENSE DE MADRID FACULTAD DE INFORMÁTICA Trabajo de Fin de Grado Grado en Ingeniería Informática Mayo 2023 Autor Lidia Casado Noguerales Dirigido por Samir Genaim Abstract A Study of Software Primitives in the context of Concurrent Data Structures The "free ride" towards faster processor speeds at the pace set by Moore’s Law has come to an end. Cramming ever smaller transistors on the same processor has reached a physical limit, and quantum technology is yet too immature to take on the challenge. Multiprocessor architectures have surged to meet the rising demand for computational power that has arisen in recent years. These architectures are capable of outperforming single-core architectures, but they require meticulous and orderly resource management to do so in a cost-efficient manner. This is where Concurrent Data Structures come to play. The new ultimate goal is to provide data structure designs that transparently manage workload balancing through several processors, ensuring correctness as well as versatility in a variety of concurrent settings. In this context, we approach the subject of providing the building blocks for Concurrent Data Structures: software and hardware synchronisation primitives. These are the operations in charge of the most critical functionalities of concurrent programs, those having to do with shared-resource management. Synchronisation primitives have to satisfy specific constraints related to correctness conditions for concurrent executions, and are therefore delicate matters worthy of unhurried study. In particular, we dive into the algorithmic details concerning the Non-blocking KCompare-Single-Swap (KCSS) primitive proposed at (Luchangco et al., 2008), a nonblocking obstruction-free software primitive aimed at meeting the challenges posed by Concurrent Linked Data Structures. We provide a profuse educational guide through every non-trivial design feature of KCSS culminating in the proposal of a fully-functional, efficient and transparent-to-the-user C++ implementation, as well as usage instructions. iii Keywords Concurrent data structures, blocking and non-blocking synchronisation, shared memory, compare and swap. Resumen Estudio de Primitivas en Software en el contexto de Estructuras de Datos Concurrentes El ”viaje gratuito” en el aceleramiento de las velocidades de procesado al ritmo establecido por la Ley de Moore ha llegado a su fin. La integración de transistores cada vez más pequeños en un mismo procesador ha alcanzado un límite físico, y la tecnología cuántica es aún demasiado inmadura para asumir el desafío. Las arquitecturas multiprocesador han surgido para satisfacer la creciente demanda de poder computacional que ha surgido en los últimos años. Estas arquitecturas son capaces de superar a las arquitecturas de un solo núcleo, pero requieren una gestión de recursos meticulosa y ordenada para hacerlo de manera rentable. Aquí es donde entran en juego las Estructuras de Datos Concurrentes. El nuevo objetivo final es proporcionar diseños de estructuras de datos que gestionen de forma transparente el equilibrado de la carga de trabajo entre procesadores, asegurando corrección y versatilidad en distintos escenarios de concurrencia. En este contexto, abordamos el tema de proporcionar los componentes básicos para la construcción de Estructuras de Datos Concurrentes: las primitivas software y hardware de sincronización. Estas son las operaciones encargadas de las funcionalidades críticas de los programas concurrentes, las que tienen que ver con la gestión de recursos compartidos. Las primitivas de sincronización tienen que satisfacer restricciones específicas relacionadas con las condiciones de corrección para ejecuciones concurrentes y, por lo tanto, son asuntos delicados merecedores de un estudio detallado. En particular, profundizamos en los detalles algorítmicos relacionados con la primitiva K-Compare-Single-Swap sin bloqueo (KCSS) propuesta en (Luchangco et al., 2008), una primitivo en software sin bloqueo (non-blocking en inglés) y libre de obstrucciones (obstruction-free) destinada a afrontar los desafíos planteados por las Estructuras de Datos Enlazadas Concurrentes. Aportamos una guía educativa acerca de las decisiones de diseño no triviales de KCSS, que culmina con la propuesta de una implementación en C++ funcional, eficiente y transparente para el usuario, así como sus instrucciones de uso. v Palabras clave Estructuras de datos concurrentes, sincronización de bloqueo y sin bloqueo, compartición de memoria, comparar e intercambiar. Contents 1. Introduction 1 1.1. Motivation................................. 1 1.2. Goals.................................... 2 1.3. WorkPlan................................. 3 1.4. Structure ................................. 3 2. Contextualising Concurrent Data Structures 9 2.1. Definition and Characteristics . . . . . . . . . . . . . . . . . . . . . . 9 2.2. Principles of Concurrency . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.1. Atomicity ............................. 14 2.2.2. Linearizability . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.3. Blocking and Non-Blocking Constructs . . . . . . . . . . . . . 16 3. Linked Data Structures: Implementing a Concurrent Linked List 19 3.1. The Locking Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1. Coarse-Grained Locking . . . . . . . . . . . . . . . . . . . . . 19 3.1.2. Fine-Grained Locking . . . . . . . . . . . . . . . . . . . . . . . 21 3.2. The CAS Primitive ............................ 24 3.3. Non-blocking K-Compare-Single-Swap (KCSS) Operation . . . . . . . 26 4. Non-blocking K-Compare-Single-Swap (KCSS) 31 4.1. SystemModel............................... 31 4.2. FormalSpecification ........................... 31 4.3. Memory Locations and their Values . . . . . . . . . . . . . . . . . . . 32 4.4. Load Linked (LL) and Store Conditional (SC) Operations . . . . . . . 35 vii 4.5. SNAPSHOT Operation ........................... 45 4.6. KCSS Operation.............................. 49 4.7. Limitations of the KCSS Operation.................... 50 4.8. RelatedWork............................... 51 5. K-CSS C++ Implementation 53 5.1. Data Structures and Defined Types . . . . . . . . . . . . . . . . . . . 53 5.2. Threads and their Identifiers . . . . . . . . . . . . . . . . . . . . . . . 61 5.3. Implementation of methods LL and SC ................. 63 5.4. Implementation of SNAPSHOT method .................. 63 5.5. Implementation of KCSS method..................... 65 5.6. KCSS UsageExample ........................... 66 5.7. ConcludingRemarks ........................... 69 6. Conclusions and Future Work 77 Bibliography 81 Chapter 1 Introduction 1.1. Motivation The "free ride" towards faster processor speeds at the pace set by Moore’s Law has come to an end for the computer industry. 20 years ago we reached the conclusion that transistor technology would soon fail to keep up with the demands of this Law. In 2004 Intel released the first processor containing transistors smaller than 100nanometers, only to make a public statement later that year announcing that they were abandoning some single-core on-going projects in favour of a new line of development: dual-core chips. Since the possibility of cramming ever smaller transistors on the same processor was reaching a dead-end – the only hope being the yet immature quantum technology – workload balancing through several processors became the new trend. More processors would allow exploiting the power of distributing tasks among them, avoiding altogether the physical complications that had arisen while trying to speed up processors by search of faster hardware. While many research topics still required time to develop, this new solution was set on the table to allow the computer industry to progress in the meantime. Soon, dual-core architectures would turn into quad-core, octa-core, ... Nowadays we refer to them as multi-core architectures. Multi-core architectures have proven their capability to outperform single-core architectures, but they require meticulous and orderly resource management to do so. The best engineering designs are the result of a balance between efficiency and cost, and in our particular case this translates into a multi-core architecture that cannot afford the cost of having multiple storage units or multiple sets of every resource a processor needs in a computer, but instead has to be designed to be efficient with the sharing of those resources available. In fact, it is true that multicore architectures do not use extra resources so as to not raise the cost of the end-product, but also for efficiency’s sake, since sharing resources implies sharing their state, which implies sharing the information that state holds, which is key to coordinate processors. This explains the proliferation of commercial shared-memory multiprocessors: We are searching for a cost-efficient design that allows resource1 8Chapter 1. Introduction 4. Capítulo 5 estudia nuestra propuesta de código C++ para esta operación, cómo solventa los escenarios descritos en el capítulo anterior y cómo usarlo a través de un ejemplo práctico. 5. Capítulo 6 presenta nuestras conclusiones del trabajo realizado y propuestas de futuras direcciones de investigación y mejora. Chapter 2 Contextualising Concurrent Data Structures 2.1. Definition and Characteristics This work focuses on Concurrent Data Structures for Shared-Memory Multi-Processor Systems, which are data structures intended for these systems where, in contrast to uni-processor systems, multiple threads of execution can execute concurrently. The fact that they are multi-processor systems means their architecture is made up of multiple processors (cores) that can combine their computing power. On the other hand, being shared-memory systems implies that there exists a shared address space between all processors, irregardless of whether each one has other local memory units for their own use. We will refer to processors (cores) as the hardware devices that constitute the Central Processing Unit (CPU) of a computer. Each processor can spawn threads: software constructs that represent the flow of execution of a program. For clarification, different operating systems have different definitions for words thread and process, since they are both units of flow control. In this report we will refer to them as the same software construct because we are only interested in describing their behaviour as units of flow control that could execute concurrently, but we are not interested in particularities of one or another specific operating system or architecture. When we say that threads can execute concurrently we mean that they are capable of executing at the same time (this does not mean they will execute synchronously, as we will now explain). Firstly, for the systems under study (sharedmemory,multi-processor) we assume that concurrent execution of more than one thread is possible because each processor can spawn at least one thread of execution at the same time (concurrently) as the rest, and we are in the context of a system with several cores. The fact that threads do not necessarily execute synchronously is key to the understanding of the execution contexts we will be analyzing throughout the following chapters: we have said that threads will execute "asynchronously" but 9 10 Chapter 2. Contextualising Concurrent Data Structures 1shared volatile int count ; 2 3fun produce (){ 4while (true){ 5if( count == 0) { 6// Perform some costly operation 7... 8count += 1; 9print (" Produced 1 unit \n"); 10 } 11 } 12 } Figure 2.1: Producer Program at the same time. Executing "asynchronously at the same time" means that threads do not necessarily have the same clock frequencies, so they are not synchronous, but they are running at the same time, at their own pace. This ultimately means that in some situations the behaviour of threads will greatly vary from the sequential counterpart. For example, in the concurrent setting we cannot expect all threads to halt at the same instant upon the occurrence of a certain event that they can all observe. We will later dive deeper into the kind of events that all threads can see. For now we will simply say that every thread can check if specific conditions are observed on the resources it has access to, and most commonly these are related to reads and writes to shared-memory. For our purposes, this means that we will have to be extra careful when reasoning about the behaviour of threads and the correctness of concurrent data structures, which will challenge our intuition. To make all of the previously mentioned ideas clear, let us see an example of a well-known concurrency problem and how it is solved using the fine-grained mechanisms we have been talking about: the Producer-Consumer Problem. Note that this problem is purposefully built so as to study the shortcomings of programs built for uni-processors when used in a concurrent setting, and it can seem somewhat artificially built. Suppose we have a multi-processor system consisting of three cores (which we will refer to as Core1,Core2and Core3, respectively), and the two programs depicted in figures Figure 2.1 (Producer) and Figure 2.2 (Consumer). In this code, we assume that variable count is a shared variable, meaning it is located in a memory region belonging to a shared address space that all processors can access, and therefore so can any threads they create. count is declared as volatile, meaning on every access to it or use of it, its value will be fetched directly from memory, and not cached. We also assume that count initially holds value 0. The context of use of programs such as the Producer and Consumer is one where a costly operation has to be performed every time another particular operation takes place: one would be performed by the produce() code, and the other one by the consume() code. A plausible example of one such operation could be reading/writing data from/to a buffer. In that case, the Producer (Figure 2.1) would be in charge of performing the "costly operation" of reading data from the input source, and the 2.1. Definition and Characteristics 11 1shared volatile int count ; 2 3fun consume (){ 4while (true){ 5if( count != 0) { 6// Perform some costly operation 7... 8count -= 1; 9print (" Consumed 1 unit \n"); 10 } 11 } 12 } Figure 2.2: Consumer Program 1Produced 1 unit 2Consumed 1 unit 3Produced 1 unit 4Consumed 1 unit 5Produced 1 unit 6Consumed 1 unit 7Produced 1 unit 8... Figure 2.3: Possible output obtained by letting three threads execute concurrently, two of which run on the Consumer Program, one on the Producer Program. Consumer (Figure 2.2) of writing it to the corresponding output destination. Variable count is the mechanism that both programs will use to let each other know that the other one has already performed its operation. Now let us suppose Core1and Core2each spawn a thread to execute the Consumer, and Core3another one to execute the Producer. We will refer to these threads as Consumer1,Consumer2and P roducer1, respectively. Consumer1and Consumer2"want" to set the value of count to 0 (because it will mean they have finished their "consumption phase", decrementing count by 1 unit), while P roducer1 wants to set count’s value to 1 (it wants to go through its "production phase", which increments count by a unit). Given that the initial value of count is 0, it is reasonable to assume that once Producer1,Consumer1and Consumer2start running, the sequence of strings depicted on Figure 2.3 will be printed until we stop the execution of all threads. However, in reality we have no guarantees that this will be the case. This particular set of strings is the result of a specific succession of events consisting of: thread Producer1 accessing count’s memory address and seeing a 0 stored in it, then adding 1 to it and printing Produced 1 unit; then one of the consumer threads (Consumer1, or Consumer2) accessing count’s memory address and seeing a 1 stored in it, subtracting 1 from it and printing Consumed 1 unit, which is when the cycle would start again. This is the expected behaviour in a sequential setting. This behaviour can be expected if we picture threads as parallel flows of execution that execute every 12 Chapter 2. Contextualising Concurrent Data Structures 1Consumed 1 unit 2Consumed 1 unit 3Produced 1 unit 4Consumed 1 unit 5Consumed 1 unit 6Consumed 1 unit 7Consumed 1 unit 8Consumed 1 unit 9... Figure 2.4: Possible output obtained by letting three threads execute concurrently, two of which run on the Consumer Program, one on the Producer Program. code statement in synchronization to a single clock. In a concurrent setting such as the one we have described (three threads executing at the same time while sharing a common variable count), the output shown by Figure 2.3 is one possibility among many, due to the non-deterministic component that the interaction between asynchronous core clocks opens the door to. Another possible output of the Producer-Consumer setup we have described could also be the one depicted by Figure 2.4. At a first glance, this does not make sense because in order to print string Consumed 1 unit value count has to be different from 0, and the only way to achieve this is through the execution of one iteration of the Producer by thread Producer1. However, each of these would result in the printing of string Produced 1 unit, and we do not see this string until the third line of output is reached. Moreover, we do not see any more apparitions of string Produced 1 unit at all. In this concurrent setting, the following can happen (see Figure 2.5 for a visual illustration of the situation): Producer1thread reads a 0 in count, and proceeds to increment count by 1 unit. Before Producer1has time to print Produced 1 unit, both Consumer1and Consumer2read a 1 in count, which satisfies the condition of their if-clause. They both proceed to execute the line which modifies count’s value (count is currently -1). Now, Consumer1and Consumer2(each at its own pace, not necessarily at the same time) proceed to printing string Consumed 1 unit. Then they restart the loop. At this moment, Producer1manages to finalise its printing instruction, so the console currently contains two Consumed 1 unit strings followed by one Produced 1 unit string. The problem that we encounter at this instant is that count now holds value -1, and therefore P roducer1’s if-clause will never be satisfied again, since the only 2.1. Definition and Characteristics 13 Line 4 Consumer1 Consumer2 Evolution of count 0 Producer1 Console: Consumer Program Producer Program Line 5 Lines 6,7 1 Line 5Line 4 Line 5 Line 4 Line 5 Line 4 Line 8 Line 5Line 4 Line 5Line 4 Line 5Line 4 Lines 6,7 Line 8 Lines 6,7 Line 8 0 -1 Line 9 Line 9 Line 9 Consumed 1 unit Consumed 1 unit Consumed 1 unit Consumed 1 unit Produced 1 unit -2 -3 Lines 4,5,6,7,8 Lines 4,5,6,7,8 Lines 4,5,6,7,8 Lines 4,... Line 5 count += 1 count -= 1 count -= 1 count -= 1 count -= 1 print print print Figure 2.5: Illustration of a possible execution of the Producer and Consumer Programs in a setting where there are two consumers: Consumer1and Consumer2, and one producer Producer1. Note that the lines of code referred to by the figure correspond to those at the code that each thread is executing (Consumer1and Consumer2execute the Consumer Program, whereas Producer1executes the Producer Program). 14 Chapter 2. Contextualising Concurrent Data Structures executing threads are both "consumers" of this value. Consumer1and Consumer2’s if-clause will be satisfied at every iteration, endlessly decreasing count’s value until their execution is stopped. What the Producer-Consumer Problem illustrates is the fact that concurrent settings introduce non-determinism into executions derived from their asynchronous execution with respect to each other. Threads are complex software constructs that require a fine balance between independence, in order to exploit the power of multicore architectures, and constant inter-communication in order to not impede other threads from progressing or in order not to duplicate work already done by another thread. This is the motivation for doing research on software primitives enabling communication and synchronisation of some sort between threads. 2.2. Principles of Concurrency Throughout this section we will review key concurrency concepts involved in the reasoning to construct correct Concurrent Data Structures. Let us think back to the Producer-Consumer Problem example. How can we make it execute as Figure 2.3 shows? We want methods produce() and consume() to execute the code within their if-clause as an indivisible unit of code, so that threads can observe the result of the actions carried out by these lines of code as a single outcome occurring at an indivisible moment in time. The concurrency concept summarising this property is atomicity. 2.2.1. Atomicity Atomicity (Moir and Shavit, 2004): A code block is guaranteed to be atomic if no thread can observe a state in which the block has been partially executed. Achieving atomicity can be very costly, and therefore it is common practice to aim at concurrent programs that limit their requirements of atomic operations as much as possible while ensuring correctness. There exist software and hardware primitives providing atomic operations for commonly needed actions. One such example are atomic read-modify operations, for which all modern multiprocessors provide one of the following primitives: load linked/store conditional (LL/SC) or compare-and-swap (CAS). Compare-And-Swap (CAS): operation that atomically loads a memory location, compares the value read to an expected value, and stores a new one at the location if the comparison succeeds. See Figure 2.6 for the semantics of this instruction in pseudo-code. 2.2. Principles of Concurrency 15 1bool CAS(L, E, N) { 2atomic{ 3if (*L == E) { 4*L = N; 5return true ; 6}else { 7return false ; 8} 9} 10 } Figure 2.6: The semantics of the CAS operation. The atomic keyword requires the block it labels to be executed atomically. Figure taken from (Moir and Shavit, 2004). Load Linked/Store Conditional (LL/SC): Information taken from (Barreira, 2023). Together, these two operations provide a means to synchronise memory load and store operations. •Load Linked (LL): It reads a memory address α, and stores address αinto a special register called the link register, local to each processor. This register’s content are deleted in the rest of processors whenever another thread performs an LL operation to the same memory location; or whenever the same thread that performed LL calls SC and it succeeds. •Store Conditional (SC): It stores the content of a register Rin a memory address α, but only if αis the same address as the one stored in the link register. Otherwise, no action is performed. If SC(α,R) was successful it returns true, otherwise it returns false. An LL operation on address α, followed by a successful SC operation on the same address guarantees that α’s content did not change between the call to LL and the call to SC. This behaviour provides a means to know whether LL/SC were executed as if they were atomic (without being interrupted by other threads attempting modifications to α), by analyzing the value returned by SC. If a thread T1calls LL(α), and then SC(α,R): if SC returns true we are guaranteed that thread T1’s link register contained address α, read by the LL operation performed by T1. This means no other LL(α)operation was performed in between T1’s LL/SC calls, because another thread’s call to LL with the same address would have deleted T1’s link register’s content. If SC returns false, we know another thread attempted to modify α’s content, preventing T1from completing its LL/SC operation. 2.2.2. Linearizability Another key concept in concurrency is linearizability of operations. As we have seen, in concurrent settings it is not always straightforward to point out the exact moment when a specific action has taken place. Actions carried out by some threads might be obscured by other concurrently-running threads’ own actions, making their 16 Chapter 2. Contextualising Concurrent Data Structures outcome invisible or confusing for a spectator unaware of the inner workings of the code. To reason about concurrent programs’ correctness, we define linearizability to precisely refer to this moment in time when we can talk about the consequences of the execution of an operation/a set of operations on the system. (Herlihy and Shavit, 2008) An execution is called linearizable if each operation appears to take effect instantaneously at some point between its invocation and its response. This point in time is called its linearization point. 2.2.3. Blocking and Non-Blocking Constructs Concurrency’s main goal is to exploit the parallel computation capabilities of multi-core systems. Ideally, every task being executed would have a disjoint set of independent sub-tasks on which the initial task could be subdivided so that a one-to-one assignment from tasks to cores could be drawn. However, it is often the case that this is not possible, and inter-dependencies between sub-tasks impose limits on the progress that threads can make when they are running concurrently and carrying out related sub-tasks. There exists a classification for the "amount of progress" that threads can make in the situation described: Blocking and Non-Blocking Constructs. Information taken from (Moir and Shavit, 2004). Blocking Constructs: Constructs belonging to this class do not guarantee any progress to be made by threads executing them. Threads could block forever, there are no guarantees that the execution will terminate. One example are constructs employing locks. Non-Blocking Constructs: Constructs belonging to this class guarantee that threads will progress if specific conditions are met. These conditions are called Progress Conditions, and they require that the failure or indefinite delay of a specific thread does not prevent other threads from making progress. Depending on the necessary Progress Conditions, several sub-classes are defined: •Wait-Freedom: A wait-free construct guarantees it will finalise after a thread executing it takes a finite number of its own steps, regardless of the timing behaviour of other threads. •Lock-Freedom: A lock-free construct guarantees that after a thread executing this construct takes a finite number of its own steps, some thread’s execution will finalise (it could either be this one or another thread executing the same construct). •Obstruction-Freedom: An obstruction-free construct guarantees it will finalise if a thread executing it manages to not encounter interference from other threads for a finite number of steps. 2.2. Principles of Concurrency 17 The subject of this study: the KCSS operation, is non-blocking, and in particular obstruction-free, as we will later see. In the concurrent setting, what defines a software construct’s progress guarantees are the synchronization primitives it employs. These are the building blocks in charge of the key actions that can compromise the correctness of the final endproduct. Synchronization primitives are nothing more than operations carrying out specific tasks that are straightforward in the sequential setting but require a redefinition in the concurrent setting because their sequential counterpart does not support concurrent uses. There exist software and hardware synchronisation primitives. The latter are the optimal choice in general, but not all systems provide them due to their dependence on architecture-specific features. One example is the Compare And Swap (CAS) operation, which is nowadays supported by most modern architectures. Software primitives, on the other hand, are malleable and customisable to our needs, in exchange of being higher-level, less efficient operations. There are many examples of software primitives, e.g. there exist variations of the CAS operation providing Double-Location Compare And Swap (CAS2 or DCAS) (Greenwald, 1999), or N-Location Compare And Swap (CASN) (Harris et al., 2002). In the following chapters, we will explore the limits and capabilities of different synchronization primitives, and compare them to the KCSS primitive that is the main subject of this work. 24 Chapter 3. Linked Data Structures: Implementing a Concurrent Linked List 1bool CAS(L, E, N) { 2atomic{ 3if (*L == E) { 4*L = N; 5return true ; 6}else { 7return false ; 8} 9} 10 } Figure 3.6: The semantics of the CAS operation. The atomic keyword requires the block it labels to be executed atomically. Figure taken from (Moir and Shavit, 2004). Nonetheless, locking is a costly mechanism in terms of memory in some programming languages, like C++. In others like Java, the overhead is not so high because every object has an associated Monitor that can be used to lock access to the object, irregardless of whether it is used or not. In any case, our linked list requires one lock per node, and locks are software-supported data structures. We now aim at a more lightweight solution that can run closer to hardware for even better performance. 3.2. The CAS Primitive The first hardware-supported primitive we know of is CAS (Compare And Swap) as described in Figure 3.6. CAS(L, E, N) atomically checks if the content of location Lmatches the expected value E, modifying Lto contain the new value Nif it is the case, and otherwise not performing any operation. We could use the CAS primitive in order to achive a lightweight linked list implementation, because this primitive can be directly implemented as a hardware primitive, in contrast to software-supported locking. It is such a useful tool in concurrency that all modern architectures provide hardware support for it. In contrast to locking, where we were guaranteed freedom of modification in any way we wanted so long as we were holding the lock. CAS introduces a new way of thinking because it forces us to reduce all operations to be performed on a data structure into swaps of memory content. As we will soon see, this is the reason why sometimes CAS needs to be complemented with other synchronisation tools, in order to provide a correct implementation of a concurrent data structure. As an example, imagine we want to delete an element in a linked list like the one in Figure 3.7, initially consisting of three elements: a,band d. Let us suppose we want to delete b. One might think that we can simply use CAS to modify a’s next_pointer field to store d’s memory address, so bis no longer part of the list. The same goes for insertions. If we wanted to insert an element after node b, however, we could simply modify b’s next_pointer field to point to the new element, and the new element to point to d. But what would happen if both calls occurred concurrently? This is what is 3.2. The CAS Primitive 25 ba · · · d c · Problem: node c not inserted Thread T1: delete(b) ... CAS(&a.next, b, d) ... Thread T2: insert(c) ... CAS(&b.next, d, c) ... ba · · d· Initial state of the linked list containing nodes: a, b and d Final state of the linked list after T1's delete(b) and concurrent T2's insert(c) Figure 3.7: Illustration of failed concurrent operations performed by two threads: T1and T2on a linked list initially containing three nodes: a,band d, that uses as only synchronisation tool single-location CAS operations. Figure inspired by those provided in (Luchangco et al., 2008). depicted in Figure 3.7. CAS guarantees atomicity on the check to see if the expected value is still in the provided location, and on the modification towards the new value, if the check was successful. But two calls to CAS on different locations can proceed independently, atomically, having an undesired outcome because they conceptually depend on each other, but CAS is oblivious to it since it just works with single locations. In Figure 3.7 we can see that T1’s deletion of bhas caused a->next_pointer to point to d, but at the same time T2has performed an insertion of cbetween b and d, resulting in b->next_pointer pointing to node c. And so we get a final result that does not correspond to applying either operation to the initial list, nor to applying both to it. The result does not even qualify as a proper linked list. The problems we have encountered are due to not having made sure that the predecessor and successor nodes of the protagonist node in the operation remained immutable while the element was being deleted or inserted. This is the shortfall of CAS: it acts upon a single location. Atomicity is costly because it requires imposing access restrictions to shared resources, so we have to aim towards obtaining an efficient primitive providing some atomicity guarantees but not being limited in applicability. For further illustration of our point, we can take a look at another example over a linked list. Figure 3.8 depicts the failure of two concurrent deletions over a list initially containing four nodes: a,b,cand d. 26 Chapter 3. Linked Data Structures: Implementing a Concurrent Linked List Thread T1: delete(b) ... CAS(&a.next, b, c) ... Thread T2: delete(c) ... CAS(&b.next, c, d) ... Initial state of the linked list containing nodes: a, b, c and d Final state of the linked list after T1's delete(b) and concurrent T2's delete(c) ba · · c·d· ba · · · c d · Problem: node c not deleted Figure 3.8: Illustration of failed concurrent deletions performed by threads T1and T2, over a linked list initially containing four nodes: a,b,cand d. Figure inspired by those provided in (Luchangco et al., 2008). We have just seen that a naïve use of single-location CAS primitives leaves ground for mistakes when designing linked concurrent data structures. We will now see how a smarter combination of synchronisation tools (including CAS), altogether with efficient memory management techniques, can provide a primitive with all the benefits of CAS’s memory-efficiency, while allowing disjoint access parallelism. 3.3. Non-blocking K-Compare-Single-Swap (KCSS) Operation Victor Luchangco, Mark Moir and Nir Shavit (Luchangco et al., 2008) have devised an atomic and obstruction-free software synchronization operation called Klocation-compare single-location-swap (KCSS) that precisely overcomes the difficulties of pointer manipulation in linked data structures with support for concurrency. KCSS allows us to modify a single location in memory while ensuring that Kother locations remain unchanged. As we will later explain, KCSS is a software-supported operation that has the advantage of being more lightweight than general purpose transactionalmemory based solutions, it provides disjoint access parallelism, and it is user-friendly because it can be used transparently, like any other software operation call. This contrasts with the opacity of code solutions that utilize complex synchronisation primitives interspersed in the code and therefore require careful concurrent reasoning to ensure correctness. Finally, KCSS is an interesting operation because it only requires a small constant memory overhead per word involved in the operation (in contrast to other software-supported operations). We will now look at a practical use of KCSS to implement a linked data structure. 3.3. Non-blocking K-Compare-Single-Swap (KCSS) Operation 27 Node { Element elem; Count count; Node* next_pointer; } elem ·count next_pointer Figure 3.9: Illustration of a Node structure in the multiset implementation. a 3 · · e 1 · c1 ·b· 3 4 d Insert node with count = 1 using 2-CSS Figure 3.10: Illustration of an insertion over a KCSS based multiset implementation, when the inserted element was not a member of the multiset before. To demonstrate its potential upon designing concurrent data structures, we will describe its behaviour when applied to a concurrent multiset2implementation based on a linked list. This particular implementation choice will evidence why we have reduced the study of "linked data structures" to general linked lists: because we are implementing a variation of a basic linked list. In this particular case, we design a multiset made up of a linked list of nodes (following the format that can be seen on Figure 3.9), where every node represents one distinct element on the multiset, storing its non-zero multiplicity together with the element value, and a pointer to the next element on the linked list. Because of this, we can already point out the similarities of this multiset to the linked lists we talked about in previous sections: we will encounter similar problems of consistency upon manipulation of the linked list of nodes. The multiset, however, poses the extra challenge of having to manage more fields per node (i.e., the multiplicity field). In particular, to implement a multiset we need 2-CSS (KCSS instance where K = 2) for insertions, and 4-CSS (KCSS instance where K = 4) for deletions, and search operations. The behaviour of these constructs is as follows (see Figures 3.10, 3.11, 3.12 for illustration): search(Element x):This method is an auxiliary procedure that searches whether the multiset contains any appearance of element x. To do this, it has to check whether any node on the linked list making up the multiset stores a key with value x, and non-zero multiplicity. In particular, search(x) returns two adjacent nodes (N1, N2) (i.e. in the list of nodes, the next_pointer field of node N1 points to N2) such that N1’s key is smaller than x, and N2’s key is greater or equal to x. The correctness of this method comes from it guaranteeing to never return a node whose multiplicity is 0. This can be achieved by deleting all nodes found while 2As a clarification, when we talk about "multiset" we refer to the mathematical concept: A generalization of the notion of mathematical set, which allows duplicate values, unlike sets. 28 Chapter 3. Linked Data Structures: Implementing a Concurrent Linked List If count > 0, increment or decrement using 1CSS or CAS ba · · · c 6 · 1 3 3 d Figure 3.11: Illustration of an insertion over a KCSS based multiset implementation, if there was already an appearance of the inserted element on the multiset (count > 1). traversing the list whose multiplicity is 0, making use of 4-CSS. To avoid getting into implementation details at this early stage of introducing the reader to the KCSS software operation, we will not explain how exactly 4-CSS is used in the search operation. insert(Element x):This method inserts a node whose element is x. The first action insert will have to do is to search xin the multiset. In case xwas already present on the multiset, we can simply use 1-CSS or CAS (their behaviour is equivalent, as we will later see) to increment the count field of x’s node on the multiset. On the other hand, in the case where we are adding xto the multiset for the first time, (with multiplicity 1), we have to carefully manipulate the node that will be predecessor to the new node containing element x(we will call this node node_x, and its predecessor predecessor). To insert node_x we have to modify predecessor’s pointer to point to node_x, while ensuring that no other thread is attempting to change the predecessor->next_pointer, nor its multiplicity. This is because if another method attempts to decrement predecessor’s multiplicity to 0, while we are performing insert(x), the predecessor node would be deleted during this call to insert, which is making use of it. Hence the need for 2-CSS on these 2 locations: predecessor->next_pointer,predecessor->multiplicity. 2-CSS will modify the content of predecessor->next_pointer to set it to node_x’s address, guaranteeing in the process that both locations maintain the values they held when the call to 2-CSS was made. delete(Element x):This method decrease the multiplicity of x, if there is a node containing it. delete will initially search for nodes containing element xin the multiset. If one such node is found, and its multiplicity is greater than 1, we can again use 1-CSS or CAS to decrement the count field of x’s node. On the contrary, if a node (let’s call it node_x) is found to contain xand its multiplicity is 1, node_x has to be removed from the multiset (we do not allow non-zero multiplicities). The search operation will have provided us with node_x’s predecessor (predecessor) and successor (successor). The delete(x) operation has to modify predecessor->next_pointer, to point to successor. In the meantime, the following 4 locations have to remain unchanged: predecessor->next_pointer: modifying it is the main purpose of delete(x), and if another thread tries to do so at the same time would cause incorrect behaviour. 3.3. Non-blocking K-Compare-Single-Swap (KCSS) Operation 29 Remove node with count = 0 using 4-CSS c d ba ·· 6 1 3 ·· 0 Figure 3.12: Illustration of a deletion over a KCSS based multiset implementation. This operation occurs when the element’s count field becomes 0. predecessor->multiplicity: it has to remain immutable for the same reason as in insert. Because a concurrent attempt to change it could decrement it to 0, triggering its deletion while this delete(x) operation is using it. node_x->next_pointer and node_x->multiplicity:node_x cannot be modified at all concurrently to this operation, because it is being removed. It should appear unreachable to other threads, and so should its fields. Consequently, we apply 4-CSS on these 4 locations to set the content of of location predecessor->next_pointer to be the pointer to successor – that is, deleting node_x – ensuring all of the above described locations are safe to do so. As we have seen, KCSS precisely overcomes the shortfalls encountered when using locks, because it allows disjoint access parallelism thanks to being a minimal-effect operation acting on very specific memory areas every time it is used. It also generalizes the applicability of single-location CAS, by providing a similar behaviour upon more than one location. Further on, we will also show how it achieves memoryefficiency, which makes it usable on platforms with different capabilities. Chapter 4 Non-blocking K-Compare-Single-Swap (KCSS) Now that we have understood the applicability of the KCSS operation, we will present the tools and requirements necessary to implement it, following what is suggested in (Luchangco et al., 2008). At the end of this section, the reader will have fully understood: the scenarios where KCSS can be used, as well as those where it is most advantageous; the semantics of KCSS and how it can be properly employed. 4.1. System Model We assume a machine architecture with the following characteristics: A 64bit word architecture. Hardware support for the CAS operation on memory words. Some assumptions on the memory model, that we will discuss later on Section 4.7 (they have to do with the effect of storing and reading values on memory, and we prefer to delay this discussion for simplifying the presentation). 4.2. Formal Specification KCSS (with K > 1, a natural number) is a software operation that takes as parameters: The addresses of Kdifferent memory locations a1, ..., ak. The expected values of those Klocations e1, ..., ek. 31 32 Chapter 4. Non-blocking K-Compare-Single-Swap (KCSS) A new value n1that we want to place into the location a1. Therefore, a KCSS call has the following form: KCSS([a1, ..., ak],[e1, ..., ek], n1) and its semantics is as follow: it checks that every location aicontains its expected value ei, for 1≤i≤K. If this is the case, then it also updates location a1with the new value n1, and returns true. Otherwise, it does not modify any memory location and it returns false. We say KCSS either succeeds or fails in each of these cases. KCSS is obstruction-free. As we have already seen in Section 2.2, this means that threads running concurrently are only guaranteed to make progress if they are left to run on their own for enough time. 4.3. Memory Locations and their Values KCSS’s performance largely depends on the format restrictions it imposes on the memory locations involved in it, and the way it manages the values that these locations can contain. In this section, we will not discuss implementation details of the data structures used by KCSS, but rather give only those necessary to explain the big picture of the mechanism behind it. For KCSS, a memory location is a 64bit word in memory, just like it is for the system in which it runs. However, KCSS’ implementation very much relies on identifying the last thread that has accessed a location. In order to do so, we use a mechanism consisting on leaving a timestamp of the thread that last accessed the location, every time it is accessed with the intention of writing to it (note that accessing a location with the intention of writing to it in this case means reading the location’s value, performing some operation with it, and then updating the the location). This timestamp is the thread’s identifier (which we will refer to as threadID from now on), and it is stored in the location itself. This location could have contained a normal value such as the value types we know (integer, floating point, pointer, ...), or it could have already contained the timestamp (threadID) of the previous thread that had attempted to start writing to the location and had not yet finished. These two possibilities allow us to differentiate whether another thread had already accessed this location or not, and it is key to our implementation. In addition, we have a mechanism to restore a location to its original value if a writing operation to it fails before completion. If a thread wants to modify a location α, it first replaces α’s current value with its own threadID (plus other metadata that we will explain later). Then, it saves the value that it had found on αinto a special area of shared memory (an array called SAVED_VAL), so that other threads can refer to it in the future if they find that αcontains the timestamp of a thread that did not manage to finish writing to 4.3. Memory Locations and their Values 33 it, i.e., to be able to reverts α’s content to the original value. Let us now see this mechanism in detail. We distinguish two types of values that memory locations can contain: program values (integer, floating point, pointer, ...), and temporal values (the ones we have been referring to as "timestamps"). For a visual illustration and an example of how locations and their values are organised, see Figure 4.1. Program values: Locations with this value type contain an actual program value (such as an integer, floating point value, a pointer, ...) that has been adapted to fit in 63 bits1, plus a single bit (the least significant bit) set to 0which is reserved to distinguish them from temporal values. Reserving this bit, in practice means that we have to sacrifice 1 bit of precision for normal primitive types. For pointers, however, since we cannot sacrifice precision without changing the pointer’s value, we simply use aligned memory positions on even positions for all of the program’s pointers. This might seem restrictive but in reality, the vast majority of modern systems already use word-aligned memory positions anyway. Temporal values: Locations with this value type contain a pair ⟨threadID, tagnumber⟩ where threadID occupies 15bits, and tagnumber 48bits2. This amounts to a total of 63bits, because once again, the least-significant bit is required to distinguish temporal values from program values. In this case, it will be set to 1. Temporal values represent the information related to the last access to this location: threadID represents the thread that last accessed it, and tagnumber will be used to distinguish different accesses by the same thread to the same location. As we have seen, a memory location α’s program value is temporarily stored in a special location in shared memory that is not the address of α. This special location is SAVED_VAL), an array of program values that stores the last program value that αhas contained. SAVED_VAL is indexed by thread identifiers, which are unique identifiers given to every thread in the system. Now that we have understood some key data structures used by KCSS to represent information, we will move on to explaining the first and most important components 1For now, we will not get into the details of how a "cast" from any program value to a type containing 63bits (instead of 64bits) is possible. The implementation details will be explained in Section 5.1. 2The bit choice for fields threadID and tagnumber is merely a design choice. In this case, 15bits have been allocated for threadID s because we assume this is enough to ensure unique IDs for all virtual threads that could exist. 48bits have been allocated for tagnumber because we assume this provides tags in a range big enough to guarantee no wraparound. 40 Chapter 4. Non-blocking K-Compare-Single-Swap (KCSS) Example 4.4.3 (Motivating the need for tags: without tags) In this example we illustrate the problem that we run into when using only thread identifiers as temporal values, i.e., without the tags. Suppose we have the situation depicted in Figure 4.7, where two threads are attempting LL/SC operations on the same location B, and thread T1is alternating between the execution of two tasks (one executes for some time, then it is interrupted by the other one, which runs in the meantime, and so on). Location Binitially contains a program value oldValue.T1’s T ask1 is running, and performs an LL first, placing into Bits threadID T1. Then comes T2and does the same, so Bwill contain a temporal value made up of T2’s threadID after the first two LL operations. Immediately after its LL,T2performs an SC(B, oldValue + y), which succeeds because no other operation to Btook place between this call and T2’s LL call. Therefore, the current value of location Bat this stage is a program value: integer oldValue + y. Until now everything has worked fine. After some time, T1’s T ask2is allowed to run (interrupting T ask1). T1’s T ask2, oblivious to Task1’s actions, performs a new LL on location B, placing in it a new temporal value with threadID T1. As we can see in the figure, this new temporal value is indistinguishable from the one put into B by T1at the very beginning. Thanks to having put a fresh tag number into Bthrough LL,Task2will be aware that the program value of Bhas changed to oldValue + y, but we cannot say the same for Task1.T ask1wanted to use the last value of B to add a quantity xto it. Because Task1’s LL happened before Thread T2changed B’s value to oldValue + y,T ask1’s execution context thinks that the value in Bis still oldValue. Not only this, but when T ask2gives way to T ask1again, Task1will call SC to commit its operation of modification of oldValue to be oldValue + x. Because T ask2placed Thread T1’s threadID into B,Task1thinks no-one else has accessed Bsince its LL, and therefore it thinks that Bhas contained value oldValue all along, between T ask1’s LL and Task1’s SC. Therefore, T ask1’s SC will succeed, placing an incorrect value on B(incorrect because it ignores Thread T2’s changes to B). Example 4.4.4 (Motivating the need for tags: with tags.) Consider the illustration depicted in Figure 4.8. The same sequence of actions takes place, except that temporal values contain unique tags every time an LL is performed. The use of tags allows Thread T1’s T ask1to know that B’s content correspond to a version of a temporal value that was placed by a call by T1to LL that does not correspond to the one Task1had used to read the value of Band operate with it. Therefore, when Task1attempts to perform an SC, it fails. This is the correct behaviour. Probably, Task1will have to retry LL/SC again in order to see the latest value of Bplaced by Thread T2. The problem we have just described is a well known concurrency issue known as the ABA problem. This is its formal definition: (Luchangco et al., 2008) The ABA problem arises when a thread reads a value A in a location, and later [...] attempts to change the location from A to a new value, with the intention that if any other thread writes to the 4.4. Load Linked (LL) and Store Conditional (SC) Operations 41 LL(location_B) LL(location_B) SC(location_B, oldValue + x) : true (63bits) 0 (1bit) Memory location B (64 bits) Program value integer oldValue Thread T1 (63bits) 0 (1bit) Memory location B (64 bits) Program value integer oldValue + x Task1 Task2 1 (1bit)thread_ID T1 Memory location B (64 bits) Temporal value Initial contents of memory location B Thread T2Task1 LL(location_B) SC(location_B, oldValue + y) : true (63bits) 0 (1bit) Memory location B (64 bits) Program value integer oldValue + y 1 (1bit) thread_ID T2 Memory location B (64 bits) Temporal value 1 (1bit)thread_ID T1 Memory location B (64 bits) Temporal value INCORRECT Figure 4.7: Time diagram illustrating the problem derived from an LL/SC implementation that does not rely on tags to check for different versions of LL operations performed by the same thread. In this case, T1is oblivious to T2’s modifications to a location Bbecause T1is alternating between executing two tasks, T ask1and Task2, so T1performs an SC operation on Bthat succeeds even though it should not. This SC updates the value of Bto be one that has ignored T2’s changes to Bwhile T1’s Task1was not running. If, for example, Bhad stored the value of a counter, there would be some increments performed by T2that would have gotten lost in the process. 42 Chapter 4. Non-blocking K-Compare-Single-Swap (KCSS) LL(location_B) LL(location_B) SC(location_B, oldValue + x) : false (63bits) 0 (1bit) Memory location B (64 bits) Program value integer oldValue Thread T1 Task1 Task2 1 (1bit)tag_number n1 thread_ID T1 Memory location B (64 bits) Temporal value Initial contents of memory location B 1 (1bit)tag_number n2 thread_ID T1 Memory location B (64 bits) Temporal value (Found tag n2, expected tag n1) Thread T2Task1 LL(location_B) SC(location_B, oldValue + y) : true (63bits) 0 (1bit) Memory location B (64 bits) Program value integer oldValue + y 1 (1bit)tag_number m1 thread_ID T2 Memory location B (64 bits) Temporal value Figure 4.8: Time diagram illustrating how using tag numbers solves the problem depicted by Figure 4.7. In this case, T1has a means of checking that a new LL operation has happened between T1T ask1’s LL and its SC. Therefore, its SC fails, which is the expected behaviour. 4.4. Load Linked (LL) and Store Conditional (SC) Operations 43 location between the read and the modification attempt, the modification will fail, leaving the value unchanged. However, in that interval, the value may change from A to some value B and then back to A again, in which case the modification operation will succeed. By using tags which are incremented every time the location is written, threads can avoid the ABA problem, provided the tags have enough bits to avoid wraparound in practice. Thanks to storing simultaneously the threadID and the tagnumber when we perform LL operations, both the same thread and others can exactly know that, if a location’s content is a temporal value, some thread must have an outstanding LL operation on it, and that thread is precisely identified by the threadID at that location. Not only this, but a thread who finds a location’s content storing a temporal value with its own threadID can check whether its current tagnumber matches the one found in that location. If it does match, no ABA problem occurred and it is the only thread with an outstanding LL operation on that location, otherwise, the ABA situation occurred and this thread can be aware and act accordingly. This mechanism for dealing with the ABA problem is a novelty, and it has been proposed by the authors at (Luchangco et al., 2008) for the first time. Let us now go deeper into the details of the READ operation that we mentioned earlier. This operation (see Figure 4.9 for the pseudo-code) allows threads to determine the program value of a location. It works by repeatedly checking whether a location contains a program value or a temporal value, until a program value is found. If a program value is found, it will return it. If a temporal value is found, READ calls an auxiliary operation RESET that will replace the temporal value found with that location’s previous program value, which can be retrieved from array SAVED_VAL (see in lines 1 to 6 for RESET’s pseudo-code, in Figure 4.9). READ then restarts the loop, which will end if no other thread has performed an LL on the same location in between READ’s start of the new iteration and its check of the location’s content. This is the reason why we cannot simply return the content of the location upon performing READ. The call to RESET is necessary to prevents a thread’s outstanding LL operation on it from committing through the corresponding SC, and this will be needed in order to support the SNAPSHOT and KCSS operations that will be presented later. Now that we have described all the pieces that conform the LL/SC mechanism, let us go back to the pseudo-code of LL and SC and explain it in more detail. LL pseudo-code in detail (Figure 4.4): An LL(α)operation is expected to retry until it is capable of returning the program value in α, which is why the first line of code in LL is a while(true) loop (Line 2). LL’s loop repeatedly does the following: it first reads the content of αusing READ.READ will return a program value, irregardless of whether αcontained a program value, or it found a temporal value and RESET had to be called on αto restore it to its previous program value. LL will go on to save the returned program value into its allocated position in array 44 Chapter 4. Non-blocking K-Compare-Single-Swap (KCSS) 1void RESET ( loc_struct * a) { 2uint64_t oldValue = a-> value ; 3if ( is_temporal_value ( oldValue )) { 4CAS (&a-> value , oldValue , SAVED_VAL [ thread_id ( oldValue )]); 5} 6} 7 8uint64_t READ(loc_struct * a) { 9while ( true) { 10 uint64_t val = a -> value ; 11 if (!is_temporal_value(val)) 12 return val; 13 RESET (a); 14 } 15 } Figure 4.9: Pseudo-code of the READ and RESET operations. SAVED_VAL4so that if this LL succeeds, itself and other threads know what the last program value of αwas. Then, it will generate the timestamp necessary for the creation of the temporal value that it will attempt to place in αto finalise its LL operation, using the currently executing thread’s attributes threadID and tagnumber (recently incremented to ensure its uniqueness at Line 3). The placement attempt is done using CAS, to ensure it is an atomic operation. A successful CAS will mean the LL finished correctly and is now an outstanding LL for location α, and so it will return the program value found upon reading α. A failed CAS will mean some other thread managed to change the content of αsomewhere in between the call to READ at Line 4 and Line 7. This is why LL has a while(true) loop. Just like when we saw locking mechanisms that required try-lock() to ensure a failure did not prevent them from progressing, this loop serves the same purpose. SC pseudo-code in detail (Figure 4.5): A call to SC(α, newValue) by a thread Tis a one-time shot at replacing the content of αwith value newValue.SC consists of a CAS operation (Line 4) that checks whether αstill holds the temporal value that Thad placed there during the last LL that thread Tperformed, and replaces the content of αby a new program value newValue if that is the case. Otherwise, it simply fails and return. It does not retry because one failure makes it impossible to succeed in the future, unless the tagnumber is incremented again (which can only happen if a new LL operation is performed by T). 4The reason why we can use array SAVED_VAL to store all of the possible previous program values replaced by threads’ temporal values, is because we can have at most as many outstanding LL operations as threads there are, and because a single thread can have at most one outstanding LL operation in total. 4.5. SNAPSHOT Operation 45 4.5. SNAPSHOT Operation Let us recall the purpose of KCSS: we want to check that Klocations contain their expected values, and if this is the case update the contents of one of them with a new value. Until now, we have focused on the mechanism that enables us to read the content of a location, use it in some intermediate calculations, and then update the location with a new value if it has not been accessed in the meanwhile. All of this is possible using only LL/SC, and READ operations. However, in order to implement KCSS, the first step involved is clear: we have to retrieve the content of Klocations, and then proceed to check if the values match the expected ones, and to update the corresponding location if possible. Therefore, we initially have to carry out KREAD operations. Unfortunately, this step cannot be done by a simple a loop that reads all locations by calling READ(location_X), because every READ operation takes a non-negligible amount of time. This allows for time gaps between one READ(location_X) and another READ(location_Y) where other threads are concurrently executing and can potentially change the contents of location_X by the time READ(location_Y) finishes. This is a problem because what we really wants is to capture the state of Kmemory locations at a single point in time, and the values returned are only correct if we can guarantee that, indeed, they have all coexisted in their corresponding memory locations at some point in time. We illustrate this in the following example. Example 4.5.1 (Motivating the need for the SNAPSHOT operation) Consider the illustration depicted in Figure 4.10. Suppose we have two threads: T1and T2, and two locations Aand B.T1wants to collect the content of both locations, while T2 is concurrently executing. T1goes ahead and performs a READ(A), retrieving value oldAfrom A. Now T2starts executing and performs a successful LL/SC call on A, changing its contents to newA. While T1is still busy with something else, T2keeps executing and manages to also successfully change the contents of Bto newB. Now, T1is ready to perform its second READ operation: READ(B). T1has now captured a value for both Aand B, which we can consider as the "picture" of memory that it will use for future calculations. However, it has captured the contents of Aand Bin a way such that the "picture" they form has never occurred (i.e., both values existed at the same time). We can see that T1thinks that memory location Acontains its old value (oldA) and that Bcontains newB. But if we look at the memory content evolution throughout the execution of both threads, locations Aand Bhave never concurrently contained these two values. At some point, Ahas contained oldAwhile Bcontained oldB; and at some other point in time Bcontained newB, while Acontained its new value (newA). In practice, this means that any computation T1performs with the captured values will be incorrect, simply because there is no point in time where the two values for A and B,oldAand newB, have coexisted. Suppose Aand B’s contents corresponded to two counters. T1has captured their count at different points in time, and therefore these values do not represent a valid state of the counters. Once again, this example illustrates the difficulties of correctly performing an 46 Chapter 4. Non-blocking K-Compare-Single-Swap (KCSS) (63bits) 0 (1bit) Memory location B (64 bits) Program value integer old_B Initial contents of memory locations A and B Thread T2SC(locationA, new_A) : true Thread T1 READ (locationA) READ (locationB) (63bits) Memory location A (64 bits) integer old_A 0 (1bit) In memory Contents of locationA Contents of locationB After READ(locationA)After READ(locationB) integer old_A 0 SC(locationB, new_B) : true LL(locationA) LL(locationB) After LL/SC(locationA) integer new_A 0 integer new_A 0 integer new_A 0 After LL/SC(locationB) integer old_B 0integer old_B 0integer new_B 0 integer new_B 0 As seen by T1 Contents of locationA Contents of locationB After READ(locationA) and READ(locationB) integer old_A 0 integer new_B 0 T1's view of memory locations A and B after performing both READs Figure 4.10: Time diagram illustrating the need for a SNAPSHOT operation, through an example where two threads T1and T2execute concurrent operations over two locations Aand B.T1fails to read both locations in such a way that it retrieves a valid state of memory. It captures a memory state that corresponds to different moments in time per location, and this is invalid. 4.5. SNAPSHOT Operation 47 operation in a concurrent setting when this operation consists on several sub-steps, that have to be coordinated in order to provide an accurate picture of the state of memory. This motivates the introduction of a new operation that precisely answers to this requirement: providing a "picture" (which we will call SNAPSHOT) of K memory locations at once, with guarantees that it accurately represents the state of memory at a specific point in time between the invocation of the operation and its finalisation. The pseudo-code for this operation can be found in Figure 4.11. 1uint64_t[1..k] COLLECT_VALUES(uint64_t k, loc_struct *[1.. k] A) { 2uint64_t[1..k] V; 3for ( uint64_t i = 1; i <= k; i++) { 4V[i] = READ(A[i]); 5} 6return V; 7} 8 9uint64_t[1.. k] COLLECT_SNAPSHOT_TS ( uint64_t k, loc_struct* [1.. k] A ) { 10 uint64_t[1..k] T; 11 for ( uint64_t i = 1; i <= k; i++) { 12 T[i] = A[i]-> snapshot_ts ; 13 } 14 return T; 15 } 16 17 uint64_t[1.. k] SNAPSHOT ( uint64_t k, loc_struct * [1..k] A) { 18 uint64_t[1..k] Timestamps_1 , Timestamps_2 ; 19 uint64_t[1.. k] Values_1 , Values_2 ; 20 while ( true) { 21 Timestamps_1 = COLLECT_SNAPSHOT_TS (k, A); 22 Values_1 = COLLECT_VALUES (k, A); 23 Values_2 = COLLECT_VALUES (k, A); 24 Timestamps_2 = COLLECT_SNAPSHOT_TS (k, A); 25 if ( for all i, ( Timestamps_1 [i] == Timestamps_2 [i]) 26 && ( Values_1 [i] == Values_2 [i ])) 27 { 28 return Values_1; 29 } 30 } 31 } Figure 4.11: Pseudo-code of the SNAPSHOT operation. The SNAPSHOT operation is a well-known non-blocking technique capable of obtaining the content of a number of memory locations in a single point in time. In a few words, it works by repeatedly collecting the content of the locations in a sequential manner (through several READ operations called one after the other by the same thread), and then comparing the retrieved content to the ones read in its previous "collect". Once two "collects" have returned exactly the same values for every one of the locations, we can return these as the SNAPSHOT of memory. The "collection" of values is done by an auxiliary operation COLLECT_VALUES 48 Chapter 4. Non-blocking K-Compare-Single-Swap (KCSS) (see lines 1 to 7 in Figure 4.11), which we will explain later in depth. After two calls to COLLECT_VALUES return the same set of values, we are guaranteed that the collected locations have maintained the same content at a specific moment in time, which us the moment in time is the one the SNAPSHOT represents. The only remaining question is how to determine whether a value has indeed not changed between both COLLECT_VALUES operations. We are already familiar with the ABA problem (See Example 4.4.3), so we can hint at the possibility of it occurring in the course of a SNAPSHOT operation: If a thread T1performs COLLECT_VALUES on a set of locations A[1..K] and retrieves values Values_1[1..K], but then comes another thread T2who changes the contents of A[1..K] to different values Values_2[1..K] and then back again to Values_1[1..K], a subsequent COLLECT_VALUES call by T1would think no one else has changed A[1..K]’s contents in the meantime, and this is not true. To solve the ABA problem once again we apply the timestamp mechanism that LL/SC used. These timestamps, consisting of a tuple ⟨threadID, tagnumber⟩that will be stored together with the values that represent memory locations in loc_struct, as we can see on Figure 4.2, field snapshot_ts. Threads will update snapshot_ts upon every modification of a location structure loc_struct (See Line 9 at Figure 4.4), enabling others and itself to know who has last modified a location (thanks to snapshot_ts’s field threadID), and to differentiate several own modifications (thanks to snapshot_ts’s field tagnumber). Timestamps will be collected together with locations’ content, thanks to being stored as loc_struct structures, by operation COLLECT_SNAPSHOT_TS.SNAPSHOT will then require that both the result of COLLECT_VALUES and COLLECT_SNAPSHOT_TS match from a collection to the other one, in order to provide a correct "picture" of memory. SNAPSHOT pseudo-code in detail (Figure 4.11): A call to SNAPSHOT(K, A[1..K]) by a thread Tconsists of a while(true) loop that repeatedly performs the following: 1. Calls COLLECT_SNAPSHOT_TS(K, A[1..K]) and stores the returned array of timestamps into Timestamps_1. 2. Calla COLLECT_VALUES(K, A[1..K]) to retrieve the values in locations A[1..K], and store the returned array into Values_1. 3. Then it repeats steps 1 and 2, but storing the results into array Timestamps_2 and Values_2. 4. Finally it compares values in arrays Values_1 and Values_2, and timestamps Timestamps_1 and Timestamps_2. If no unmatched value or timestamp is found, SNAPSHOT returns Values_1 as the result. Otherwise, it restarts on Step 1. As we can see at Lines 1 to 15 of Figure 4.11, auxiliary operations COLLECT_VALUES and COLLECT_SNAPSHOT_TS simply loop over location structures and retrieve the content in which they are interested. Note the use of operation READ by COLLECT_VALUES, 4.6. KCSS Operation 49 which is necessary in order to guarantee that COLLECT_VALUES only returns program values. 4.6. KCSS Operation The final step in order to build KCSS, is to put all pieces that we have seen so far together. As we discussed in Section 4.2, a KCSS call: KCSS (Locations[A_1..A_k], ExpectedVals[e_1..e_k], newValue_1) checks that every location A_i contains its expected value e_i. If this is the case, then it updates A_1 with the new value newValue_1. Otherwise, it does not modify any memory location. We now know how to find out a location’s program value even on locations undergoing changes by other threads; we have seen how to successfully modify the content of a location while ensuring that no other thread has accessed it; and we know how to correctly retrieve the value of Klocations at a specific point in time. These are all the pieces we have to put together. 1bool KCSS(uint64_t k, loc_struct * [1..k] A, uint64_t[1.. k] expectedValues , uint64_t newValue ) { 2uint64_t[1.. k] oldValues ; 3while ( true) { 4oldValues [1] = LL(A [1]); 5oldValues [2.. k] = SNAPSHOT (k - 1, A[2.. k]); 6if (for some i, oldValues[i] != expectedValues [i]) { 7SC(A[1] , oldValues [1]) ; // revert A[1] to oldValues [1] 8return false ;// KCSS was unsuccessful 9} 10 // else try to finalise : 11 if ( SC(A[1] , newValue )) { 12 return true ;// KCSS was successful 13 } 14 } 15 } Figure 4.12: Pseudo-code of the KCSS operation. A thread Texecuting a call to KCSS simply does the following (the pseudo-code for this operation can be found on Figure 4.12): 1. At Line 4, Tinitiates an LL/SC on location A_1 by performing LL(A_1), declaring its intentions of modifying this location. 2. At Line 5, before proceeding with the modification of A_1,Thas to make sure that the Klocations it is considering will maintain their content from now until T’s action of "committing" its modifications to A_1. 56 Chapter 5. K-CSS C++ Implementation along, the KCSS code manages uint64_t values which it treats as memory words; and auxiliary methods are employed at times to preserve the format characteristics that this representation carries, transparently to methods like LL,SC,SNAPSHOT, etc. 1// loc_struct_t for uint64_t and int64_t 2template<typename T> 3struct loc_struct_t <T, std :: enable_if_t < std :: is_same_v <T, uint64_t> || std :: is_same_v <T,int64_t>>> : loc_struct_base { 4 5struct t63 { 6Tlocation_type :1; 7Tcontent :63; 8}; 9 10 loc_struct_t() noexcept : 11 loc_struct_base() { 12 } 13 14 loc_struct_t(Tv) noexcept : 15 loc_struct_base( to_value_t (v)) { 16 } 17 18 constexpr inline uint64_t to_value_t (Tv) const noexcept { 19 union { 20 t63 x; 21 uint64_t _x; 22 }; 23 x. location_type = 0; 24 x. content = v; 25 26 return _x; 27 } 28 29 constexpr inline T from_value_t(uint64_t v) const noexcept { 30 union { 31 t63 x; 32 uint64_t _x; 33 }; 34 _x = v; 35 36 return x. content ; 37 } 38 }; Figure 5.3: loc_struct_t<T> C++ code, when Tis either uint64_t or int64_t. Let us now look at two key methods in charge of format-compliance, provided by all loc_struct_t<T> declarations (and in particular by loc_struct_t<uint64_t> and loc_struct_t<int64_t>structures): to_value_t and from_value_t (lines 18 to 37 on Figure 5.3 contain the corresponding C++ code). Method to_value_t(Tv) is used to convert a user-provided value vinto its adequate representation as a uint64_t value (a memory word), just like the pseudo-code method make_ProgramValue did (see Figure 4.5 for the usage of this method). It is 5.1. Data Structures and Defined Types 57 an auxiliary method to "encode" a user-provided value into its KCSS representation, all the while occupying a 64bit-word). This is done employing the C++ union capability, which allows more than one variable, possibly with different type, to be stored the same memory. This means that the value in that memory can be interpreted as one type or another, depending which variable we use to refer to it. In this case, to_value_t exploits this capability to re-interpret the user-defined value v(which is ultimately a 64bit word uint64_t) as a t63 structure. This is done so that we can take advantage of the ease of bit manipulation through bit field assignment to do the following: A t63 structure xis declared in the scope of a union construct, altogether with a uint64_t value _x (Lines 19 to 22 on Figure 5.3), which means that the assignments on Lines 23 and 24 in Figure 5.3 do not only modify x’s bits, but also _x’s. In particular, the last bit (t63->location_type) of both xand _x will contain a 0to indicate that the value contained is a program value; and the remaining 63bits (t63->content) will be filled using the 64bit user-provided value v, which will be automatically truncated to fit into 63bits (this is the real power of bit field assignment). Method from_value_t(uint64_t v) does the oposite of to_value_t. It extracts the content of a KCSS program value vin order to return its user-formatcomplying value. Once again, this is done employing the C++ union capability to re-interpret the uint64_t value vas a t63 structure so that we can easily access the t63 structure’s bit fields. More specifically, we are interested in the content bits of v, which are the 63 least significant ones. Therefore this method returns t63->content, which C++’s union will automatically fit into a uint64_t value _x that will be then re-interpreted as a Ttype upon return. Note that the processing we have described for values of type uint64_t or int64_t varies for other types. Since KCSS has an exhaustive set of templates covering all possible primitive data types, the compiler will choose the appropriate one depending on the data type provided by the user. Pointers are by default aligned on memory addresses that are even that they can be represented without the need to remove 1 precision bit as it happens for integers (because the least significant bit is always zero). This is also the case for types occupying less than 64bits (such as int8_t,int16_t,int32_t and single-precision floating-point numbers): they can be represented without modifying the original value because they fit into 63bits, which is the maximum allocation of bits that values can use. Their corresponding loc_struct_t structure just needs to implement the to_value_t and from_value_t methods so that all loc_struct_t structures share a common interface, and all necessary type conversions can be performed. The C++ code corresponding to the loc_struct_t<T> for the aforementioned cases can be found at Figure 5.4 (code for numeric types occupying less than 64bits) and Figure 5.5 (code for the pointer case). On the other hand, double-precision floating-point numbers (double) pose a new challenge because their bit-wise representation consists of several parts1: sign (1 bit), exponent (11 bits), and mantissa or fraction (52 bits); as we can see on 1https://en.wikipedia.org/wiki/Double-precision_floating-point_format 58 Chapter 5. K-CSS C++ Implementation 1// loc_struct_t for any numeric type of size smaller than 8 bytes 2template<typename T> 3struct loc_struct_t <T, 4std :: enable_if_t < 5(std::is_integral_v <T> || std::is_floating_point_v <T>) 6&& ( sizeof(T) < 8) >> : loc_struct_base { 7 8loc_struct_t() noexcept : 9loc_struct_base() { 10 } 11 12 loc_struct_t(Tv) noexcept : 13 loc_struct_base( to_value_t (v)) { 14 } 15 16 constexpr inline uint64_t to_value_t (Tv) const noexcept { 17 union { 18 struct { 19 uint8_t location_type ; 20 Ta2; 21 } t; 22 uint64_t a1; 23 }; 24 a1 = 0; 25 t.a2 = v; 26 27 return a1; 28 } 29 30 constexpr inline T from_value_t(uint64_t v) const noexcept { 31 union { 32 struct { 33 uint8_t location_type ; 34 Ta2; 35 } t; 36 uint64_t a1; 37 }; 38 a1 = v; 39 40 return t.a2; 41 } 42 }; Figure 5.4: loc_struct_t<T> C++ code, when Tis any any numeric type of size smaller than 8bytes (64bits). 5.1. Data Structures and Defined Types 59 1// loc_struct_t for pointers 2template<typename T> 3struct loc_struct_t <T*> : loc_struct_base { 4 5loc_struct_t() noexcept : 6loc_struct_base() { 7} 8 9explicit loc_struct_t (T*v) noexcept : 10 loc_struct_base( to_value_t (v)) { 11 } 12 13 constexpr inline uint64_t to_value_t (T*v) const noexcept { 14 static_assert ( ( alignof (T) & 1) == 0 ); 15 union { 16 T* v_aux ; 17 uint64_t a; 18 }; 19 v_aux = v; 20 assert ((a & 1) == 0);// pointer must be aligned to even address 21 22 return a; 23 } 24 constexpr inline T* from_value_t(uint64_t v) const noexcept { 25 union { 26 T*a; 27 uint64_t v_aux ; 28 }; 29 v_aux = v; 30 31 return a; 32 } 33 }; Figure 5.5: loc_struct_t<T> C++ code, when Tis a pointer. 60 Chapter 5. K-CSS C++ Implementation Figure 5.6. In this case, "stealing 1 precision bit" is still the mechanism we will use to represent them as loc_struct_t structures, setting to 0the least significant bit of the mantissa. In practice, just like in the case of integer numbers, this means we reduce the range of possible values, but in this case the loss of precision is even more negligible: The maximum relative rounding error will be exactly of 2−53. This is acceptable because 64bit values cover a vast amount of possible numbers, almost inextinguishable for a common-use program. Nevertheless, the user will have to be warned about this limitation, for the sake of correctness. Figure 5.6: Components of a double-precision floating-point number. Figure taken from https://en.wikipedia.org/wiki/Double-precision_floating-point_ format. Figure 5.7 contains the C++ code corresponding to the loc_struct_t<T> structure, when Tis a double-precision floating-point number (double). We can see on Line 18 that the way method to_value_t works in this case is slightly different to the uint64_t and int64_t case. Instead of using an auxiliary structure (like struct t63) and bit field assignment, double values are better manipulated using bit-wise operations. So to_value_t uses the union construct to apply bit-wise operation &(logical AND) to user-provided value double v (that has been assigned to value double a1 and therefore to uint64_t a2 on Line 17 of Figure 5.7), "turning" the least significant bit of the mantissa to 0, which will represent the location_type field in KCSS value format (being 0indicates it is a program value). All in all, we have provided proof that there are mechanisms in place so that users do not have to meddle with the internal representation of memory in KCSS. They will simply call KCSS’s methods using wrappers that KCSS provides so that they can declare which values are going to be susceptible of experiencing a KCSS operation, but without knowing what actions are being carried out at the KCSS class to enable this. When users declare a value of type KCSS::loc_struct_t<T> (Tbeing some type definition of their choice), the C++ compiler will automatically assign it to its corresponding template, whose definition is such that the rest of the methods in KCSS (LL, SC, SNAPSHOT, ...) can use it like any other KCSS::loc_struct_t piece of data. 5.2. Threads and their Identifiers 61 1template<> 2struct loc_struct_t <double > : loc_struct_base { 3 4loc_struct_t() noexcept : 5loc_struct_base() { 6} 7 8loc_struct_t(double v) noexcept : 9loc_struct_base( to_value_t (v)) { 10 } 11 12 constexpr inline uint64_t to_value_t ( double v) const noexcept { 13 union { 14 double a1; 15 uint64_t a2; 16 }; 17 a1 = v; 18 a2 = a2 & 0xfffffffffffffffe; // turn the least significant bit of the mantissa to 0 19 20 return a2; 21 } 22 23 constexpr inline double from_value_t(uint64_t v) const noexcept { 24 union { 25 uint64_t a2; 26 double a1; 27 }; 28 a2 = v; 29 30 return a1; 31 } 32 }; Figure 5.7: loc_struct_t<T> C++ code, when Tis a double-precision floating-point number. 5.2. Threads and their Identifiers Another method worth mentioning, related to compliance with KCSS’s representation format of values, is method (depicted in Figure 5.8): make_TemporalValue(uint16_t thread_ID, uint64_t tag_number) As the name suggests, this method takes as parameters the components necessary to build a temporal value (thread_ID and tag_number) and returns the resulting 64bitcompliant representation (for a reminder of temporal values, refer to Section 4.3). Temporal values are represented via struct TemporalValue, which uses C++’s bit fields to manage the bit-wise manipulation of its three components: location_type (1 bit), thread_ID (15 bits) and tag_number (48 bits), which make up a single 62 Chapter 5. K-CSS C++ Implementation 64bit memory word (uint64_t value). make_TemporalValue simply fills these fields given the parameters it receives, setting location_type to be 1 (which is temporal values’ identifying trait). This last bit is precisely the one checked by auxiliary method is_TemporalValue(uint64_t v), which returns true if the given value v is a temporal value, and false otherwise. 1struct TemporalValue { 2uint64_t location_type :1; 3uint64_t thread_ID :15; 4uint64_t tag_number :48; 5}; 6static_assert ( sizeof(TemporalValue) == 8 ); 7 8constexpr inline bool is_TemporalValue(uint64_t v) const noexcept { 9return (v & 0x0000000000000001) == 1; 10 } 11 12 inline constexpr uint64_t make_TemporalValue(uint16_t thread_ID, 13 uint64_t tag_number) const noexcept { 14 union { 15 TemporalValue vt; 16 uint64_t a; 17 }; 18 19 vt. thread_ID = thread_ID ; 20 vt. tag_number = tag_number ; 21 vt. location_type = 1; 22 23 return a; 24 } Figure 5.8: make_TemporalValue C++ code, together with some auxiliary methods. The way to obtain the currently running thread’s identifier, is through method my_thread_id(). This method (see Figure 5.9) makes use of a thread_local variable my_thread_id that is also static, which stores the increment by one unit of private variable _thread_id. The combination of being thread_local and static means that this variable has a local value for every thread (it is not shared) and that it is only assigned once (the first time the method is called). Therefore, every time method my_thread_id() is called, it will return the result of having incremented private variable _thread_id the first time that it was called. Method thread_id(uint64_t v) (see lines 6 to 13 on Figure 5.9) is an auxiliary method that extracts field thread_ID from a temporal value variable v. It is employed by the RESET operation in order to index the SAVED_VAL array (see Section 4.4 for a reminder of the RESET operation). 5.3. Implementation of methods LL and SC 63 1uint16_t my_thread_id() noexcept { 2thread_local static uint16_t my_thread_id = _thread_id ++; 3return my_thread_id; 4} 5 6constexpr inline uint16_t thread_id ( uint64_t v) const noexcept { 7union { 8TemporalValue tv; 9uint64_t a; 10 }; 11 a = v; 12 13 return tv. thread_ID ; 14 } Figure 5.9: my_thread_id and thread_id C++ code. 5.3. Implementation of methods LL and SC The C++ code for LL and SC operations exactly follows the pseudo-code we explained in Section 4.4. If we retrace our steps back to the pseudo-code for LL (see Figure 4.4), we can compare both figures statement by statement and see they are identical. In the case of SC operations, however, there is a minor difference: our pseudocode implementation (see Figure 4.5) includes a call to make_ProgramValue(a, new_program_val), which is not present on the C++ version of the code. This is because in this case it will actually be called with a program value (i.e., a value whose first bit is 0, and already adapted to fit in 63 bits – see the discussion in the previous section). This is the result of our careful and transparent management of data formats using loc_struct_t<T> structures and their to_value_t and from_value_t methods. All of KCSS’s code manages uint64_t values that already comply to the KCSS format for program and temporal values, so the call to make_ProgramValue (which in C++ has an equivalent method named to_value_t) will have already been done before calling SC. We can see an example of this data format compliance before calling LL and SC on the KCSS operation code, that will be explained in Section 5.5. As for auxiliary operations RESET and READ (their C++ implementation can be found on Figure 5.12), once again their pseudo-code (see Figure 4.9) and their C++ implementation exactly match if we compare every code statement one by one. 5.4. Implementation of SNAPSHOT method The C++ code for the SNAPSHOT operation can be found on Figure 5.13, altogether with the C++ code for its auxiliary operations COLLECT_SNAPSHOT_TS (Figure 5.14) and COLLECT_VALUES (Figure 5.15). The reader is encouraged to look back into Section 4.5 and verify that the pseudo-code provided for these operations (see Figure 4.11) exactly matches the C++ code in Figures 5.13, 5.14 and 5.15, the only difference being that our C++ implementation of auxiliary operations COLLECT_VALUES 64 Chapter 5. K-CSS C++ Implementation 1inline uint64_t ll( loc_struct_base *a) noexcept { 2while ( true) { 3TAG_NUMBERS [ my_thread_id () ]++; 4uint64_t old_val = read(a); 5SAVED_VAL [ my_thread_id ()] = old_val ; 6uint64_t temp_val = make_TemporalValue ( my_thread_id () , 7TAG_NUMBERS [ my_thread_id () ]) ; 8if ( cas (&a-> value , old_val , temp_val )) { 9a-> snapshot_ts = temp_val ; 10 return old_val; 11 } 12 } 13 } Figure 5.10: LL operation C++ code. 1inline bool sc( loc_struct_base *a, uint64_t new_prog_val) noexcept { 2uint64_t temp_val = make_TemporalValue ( my_thread_id () , TAG_NUMBERS [ my_thread_id () ]) ; 3return cas (&a-> value , temp_val , new_prog_val ); 4} Figure 5.11: SC operation C++ code. 1inline void reset ( loc_struct_base *a) noexcept { 2uint64_t old_val = a-> value ; 3if ( is_TemporalValue ( old_val )) { 4cas (&a-> value , old_val , SAVED_VAL [ thread_id (old_val )]); 5} 6} 7 8inline uint64_t read(loc_struct_base *a) noexcept { 9while ( true) { 10 uint64_t val = a -> value ; 11 if (! is_TemporalValue ( val )) 12 return val; 13 reset (a); 14 } 15 } Figure 5.12: reset and read operations C++ code. and COLLECT_SNAPSHOT_TS do not return the array of values or tags, but instead modify an array parameter they receive by value reference. 5.5. Implementation of KCSS method 65 1inline void snapshot ( std :: size_t k, loc_struct_base **a, uint64_t * values_1 ) noexcept { 2uint64_t timestamps_1[k], timestamps_2[k]; 3uint64_t values_2 [k ]; 4 5while ( true) { 6collect_snapshot_ts (k, a, timestamps_1 ); 7collect_values (k, a, values_1 ); 8collect_values (k, a, values_2 ); 9collect_snapshot_ts (k, a, timestamps_2 ); 10 11 unsigned i = 0; 12 while (i < k && timestamps_1 [i] == timestamps_2 [i] && values_1 [i] == values_2 [i ]) 13 ++i; 14 15 if (i == k) 16 return; 17 } 18 19 return; 20 } Figure 5.13: SNAPSHOT operation C++ code. 1inline constexpr void collect_snapshot_ts(const std :: size_t k , 2loc_struct_base **a, uint64_t *t) const noexcept { 3for ( unsigned int i = 0; i < k; ++i) { 4t[i] = a[i]-> snapshot_ts ; 5} 6} Figure 5.14: COLLECT_SNAPSHOT_TS operation C++ code. 1inline void collect_values(const std :: size_t k, loc_struct_base **a, 2uint64_t *v) noexcept { 3for ( unsigned int i = 0; i < k; ++i) { 4v[i] = read(a[i]); 5} 6} Figure 5.15: COLLECT_VALUES operation C++ code. 5.5. Implementation of KCSS method The C++ code for the KCSS operation can be found on Figure 5.16. Note that KCSS is the only operation among the ones we have described (LL,SC,SNAPSHOT, ...) that is public for the user to access. The KCSS C++ implementation slightly varies from the pseudo-code provided in 72 Chapter 5. K-CSS C++ Implementation 1void two_threads() { 2 3// Initial list : a(1) -> c (3) -> d(4) 4node *d = new node (4 , nullptr ); 5node *c = new node (3 , d); 6node *a = new node (1 , c); 7 8std :: cout << " Creating initial list consisting of :\n"; 9print_list (a); 10 11 // We want T1 to delete node d (4) , while T2 inserts b(2). 12 13 auto delete_d = [&]() { // Will make use of KCSS where K = 2. 14 // The first location involved is c->next , and the second one is d->next 15 std :: cout << " Deleting node d(4) ...\ n"; 16 // Apply kcss operation : 17 bool success = kcss_instance .kcss (c->next , d , ( node *) nullptr , KCSS:: mp (d ->next , ( node *) nullptr )); 18 if( success ){ // Now it is safe to delete node e 19 std :: cout << " Deletion operation successful .\ n"; 20 }else{// Failure of kcss 21 std :: cout << " Deletion operation unsuccessful .\ n"; 22 } 23 }; 24 auto insert_b = [&]() { // Will make use of KCSS where K = 1. 25 node *b = new node (2 , c); 26 std :: cout << " Inserting node b(2) ...\ n"; 27 bool success = kcss_instance .kcss (a->next , c , b); 28 if( success ){ // Now it is safe to delete node e 29 std :: cout << " Insertion operation successful .\ n"; 30 }else{// Failure of kcss 31 std :: cout << " Insertion operation unsuccessful .\ n"; 32 } 33 }; 34 35 int num_threads = 2; 36 std :: thread t[ num_threads ]; 37 t [0] = std :: thread ( delete_d ); 38 t [1] = std :: thread ( insert_b ); 39 40 t[0]. join (); 41 t[1]. join (); 42 43 44 std:: cout << " Current list :\n"; 45 print_list (a); 46 47 // Perform the desired actions with the list (...) 48 49 cleanup (a); 50 } Figure 5.21: KCSS operation test using two threads over a linked list, on C++ code. 5.7. Concluding Remarks 73 1void n_threads ( std :: size_t n) { 2 3KCSS:: loc_struct_t <int> v1 (10); 4KCSS:: loc_struct_t <int> v2 (20); 5KCSS:: loc_struct_t <int> v3 (30); 6 7auto f = [&]() { 8while ( true) { 9int x = kcss_instance . get (v1 ); 10 if (x > 100000) 11 break ; 12 kcss_instance .kcss(v1 , x, x + 1, KCSS:: mp (v2 , 20) , KCSS:: mp( v3 , 30)); 13 } 14 }; 15 16 std :: thread t[n]; 17 for (auto i = 0u; i < n; i++) 18 t[i] = std :: thread (f); 19 for (auto i = 0u; i < n; i++) 20 t[i]. join (); 21 22 23 std:: cout << "\ nThe final value of v1 is: " << kcss_instance . get( v1) << std :: endl ; 24 25 } Figure 5.22: KCSS operation test using nthreads concurrently attempting to modify a single location, on C++ code. 1int main (){ 2 3std :: cout << "\ nTest 1\ n"; 4one_thread (); 5 6std :: cout << "\ nTest 2\ n"; 7two_threads(); 8 9std :: cout << "\ nTest 3\ n"; 10 n_threads (6); 11 12 return 0; 13 } Figure 5.23: KCSS operation testing main() method, on C++ code. 74 Chapter 5. K-CSS C++ Implementation 1template< std :: size_t k> 2inline void collect_values_(loc_struct_base **a, uint64_t *v) noexcept { 3collect_values_ <k - 1>(a, v); 4v[k - 1] = read (a[k - 1]) ; 5} 6 7template<> 8inline void collect_values_ <0 >( loc_struct_base**, uint64_t*) noexcept { 9} Figure 5.24: Redefinition of operation COLLECT_VALUES, on C++ code. 1template< std :: size_t k> 2inline constexpr void collect_snapshot_ts_(loc_struct_base **a, 3uint64_t *t) const noexcept { 4collect_snapshot_ts_ <k - 1 >(a, t); 5t[k - 1] = a[k - 1]-> snapshot_ts ; 6} 7 8template<> 9inline constexpr void collect_snapshot_ts_ <0 >( loc_struct_base**, 10 uint64_t*) const noexcept { 11 } Figure 5.25: Redefinition of operation COLLECT_SNAPSHOT_TS, on C++ code. 5.7. Concluding Remarks 75 1// eval_cond_ method for redefined snapshot_ 2template< std :: size_t k> 3inline bool eval_cond_(uint64_t *values_1, uint64_t *values_2 , uint64_t *timestamps_1 , 4uint64_t *timestamps_2) noexcept { 5return eval_cond_ <k - 1>( values_1 , values_2 , timestamps_1 , timestamps_2) 6&& timestamps_1 [k - 1] == timestamps_2[k - 1] 7&& values_1 [k - 1] == values_2 [k - 1]; 8} 9 10 template<> 11 inline bool eval_cond_ <0 >( uint64_t*, uint64_t*, uint64_t*, 12 uint64_t*) noexcept { 13 return true ; 14 } 15 16 // snapshot_ method 17 template< std :: size_t k> 18 inline void snapshot_ ( loc_struct_base **a, uint64_t * values_1 ) noexcept { 19 uint64_t timestamps_1[k], timestamps_2[k]; 20 uint64_t values_2 [k ]; 21 22 while ( true) { 23 collect_snapshot_ts_ <k >(a, timestamps_1 ); 24 collect_values_ <k >(a , values_1 ); 25 collect_values_ <k >(a , values_2 ); 26 collect_snapshot_ts_ <k >(a, timestamps_2 ); 27 28 if ( eval_cond_ <k >( values_1 , values_2 , timestamps_1 , timestamps_2)) 29 return; 30 } 31 32 return; 33 } 34 35 template<> 36 inline void snapshot_ <0>(loc_struct_base**, uint64_t*) noexcept { 37 } Figure 5.26: Redefinition of operation SNAPSHOT, on C++ code. 76 Chapter 5. K-CSS C++ Implementation 1template<typename T0 , typename ...Ts > 2bool kcss_ ( loc_struct_t <T0 > &a0 , T0 a0_expv , T0 a0_newv , Ts &&... args) noexcept { 3 4constexpr std :: size_t k = sizeof...( args ) + 1; 5 6uint64_t old_vals [k ]; 7uint64_t exp_vals [k] = { a0. to_value_t ( a0_expv ) , 8( args . first . to_value_t ( args . second )) ... }; 9loc_struct_base *a[k] = { &a0 , (& args . first )... }; 10 uint64_t new_v = a0 . to_value_t ( a0_newv ); 11 12 while ( true) { 13 old_vals [0] = ll(a [0]); 14 15 snapshot_ <k - 1>(a + 1, old_vals + 1); 16 if ( eval_kcss_cond_ <k >( old_vals , exp_vals )) { 17 sc(a[0] , old_vals [0]) ; 18 return false ; 19 } 20 // The previous code block is equivalent to the following : 21 // snapshot(k - 1, a + 1, old_vals + 1); 22 // for ( unsigned int i = 0; i < k; ++i) { 23 // if ( old_vals [i] != exp_vals [i ]) { 24 // sc(a[0] , old_vals [0]) ; 25 // return false ; 26 // } 27 // } 28 29 if ( sc(a[0] , new_v )) { 30 return true ; 31 } 32 } 33 34 return false ; 35 } Figure 5.27: Redefinition of operation KCSS, on C++ code. 1template< std :: size_t k> 2inline bool eval_kcss_cond_(uint64_t * old_values , uint64_t * exp_values ) noexcept { 3return eval_kcss_cond_ <k - 1>( old_values , exp_values ) 4|| old_values [k - 1] != exp_values [k - 1]; 5} 6 7template<> 8inline bool eval_kcss_cond_ <0 >( uint64_t*, uint64_t*) noexcept { 9return false ; 10 } Figure 5.28: Auxiliary condition evaluation operation for the redefinition of operation KCSS, on C++ code. Chapter 6 Conclusions and Future Work Through this work we have motivated the need for further research on tools that exploit the capabilities of multi-core systems, concurrency being the answer to Moore’s Law standstill. Analysing the challenges that Concurrent-Data-Structure design faces, we have understood the delicate balance between efficient communication and autonomy between concurrently executing threads, and how perfect timing of their actions is key for correctness. The study of fine-grained and coarse-grained software synchronisation mechanisms has allowed us to understand the nature of concurrent settings both from the practical and the theoretical point of view, establishing a knowledge baseline to guide the reader on switching from sequential to concurrent reasoning. Coarsegrained mechanisms provide simple solutions at the cost of efficiency and adaptability. Fine-grained mechanisms tip the balance towards the opposite side, in exchange for higher code complexity that makes the study of these concurrency mechanisms a delicate task. At this point, the KCSS software primitive has been suggested as an adequate commitment between efficiency and adaptability, and code complexity and usability. A profuse explanation of every relevant and non-trivial feature of KCSS has been assembled, to serve as an educational resource easing the understanding of its inner workings. We have explored KCSS’s applicability to the design of Concurrent Data Structures, more specifically Concurrent Linked Data Structures, emphasising its performance with respect to alternative solutions to the synchronisation challenges posed by these Data Structures. To bring to light the real tangible impact of this primitive, a fully-functional, efficient and transparent-to-the-user KCSS implementation has been provided. This task has challenged our initial commitment to make it easy to use, due to the strict memory-location interpretation needs of KCSS and our desire to make it available for all common data types. Nevertheless, C++’s ample capabilities (templates, bit fields, function parameter packs) have allowed us to hide all implementation details from the user while maintaining efficiency and coverage of all common data types. Finally, we have studied how this primitive can be further improved, and how re77 78 Chapter 6. Conclusions and Future Work lated work on multi-location software synchronisation primitives could complement it. In particular, the ideas put forward to design KCSS can be put into practice to develop a transactional model with the same functionality as KCSS but improved efficiency and intuitiveness of the process. The main idea is to have transactional loads in charge of recording the information collected in the first half of the SNAPSHOT operation that our current KCSS implementation performs, and transactional commits doing the second part of this operation: determining if any of the values read has been modified by a concurrent operation since being read by the transactional load. KCSS could also yet undergo further concurrency improvements: it is possible to reduce "collisions" between LL/SC operations at the cost of a more complex SNAPSHOT operation. It is also possible to reuse collected values and timestamps by this operation from one iteration to the other, downgrading readability but improving overall efficiency. Conclusión A través de este trabajo hemos motivado la necesidad de seguir investigando herramientas que exploten las capacidades de los sistemas multinúcleo, siendo la concurrencia la respuesta al estancamiento de la Ley de Moore. Al analizar los desafíos a los que se enfrenta el diseño de Estructuras de Datos Concurrentes, hemos comprendido el delicado equilibrio entre tener comunicación eficiente y autonomía entre hilos ejecutándose simultáneamente, y cómo la sincronización perfecta de sus acciones es clave para la corrección. El estudio de los mecanismos de sincronización de software de granularidad fina y gruesa nos ha permitido comprender la naturaleza de los entornos de ejecución concurrentes tanto desde el punto de vista práctico como teórico, estableciendo una base de conocimiento para guiar al lector en el cambio de razonamiento secuencial a concurrente. Los mecanismos de granularidad gruesa proporcionan soluciones simples a costa de la eficiencia y la adaptabilidad. Los mecanismos de granularidad fina inclinan la balanza hacia el lado opuesto, a cambio de una mayor complejidad del código que hace que el estudio de estos mecanismos de concurrencia sea una tarea delicada. En este punto, la primitiva de software KCSS se ha sugerido como un compromiso adecuado entre eficiencia y adaptabilidad, y complejidad y facilidad de uso del código. Se ha elaborado una explicación detallada de cada característica relevante y no trivial de KCSS, sirviendo como recurso educativo que facilita la comprensión de su funcionamiento interno. Hemos explorado la aplicabilidad de KCSS al diseño de Estructuras de Datos Concurrentes, más específicamente Estructuras de Datos Enlazadas Concurrentes, enfatizando su desempeño con respecto a soluciones alternativas a los desafíos de sincronización planteados por estas Estructuras de Datos. Para sacar a la luz el impacto tangible real de esta primitiva, se ha proporcionado una implementación de KCSS completamente funcional, eficiente y transparente para el usuario. Esta tarea ha desafiado nuestro compromiso inicial de hacerla fácil de usar, debido a las estrictas necesidades de KCSS al interpretar las ubicaciones de memoria y debido a nuestro deseo de que sea compatible con todos los tipos de datos comunes. Gracias a las amplias capacidades de C++ (plantillas, campos de bits, paquetes de parámetros de función) hemos podido ocultar los detalles de im79 80 Chapter 6. Conclusions and Future Work plementación al usuario, manteniendo la eficiencia y cobertura de todos los tipos de datos. Finalmente, hemos estudiado cómo se puede mejorar aún más esta primitiva y cómo el trabajo relacionado con las primitivas de sincronización de software de ubicación múltiple podría complementarla. En particular, las ideas propuestas para diseñar KCSS se pueden poner en práctica para desarrollar un modelo transaccional con la misma funcionalidad que KCSS pero con mayor eficiencia y siendo más intuitivo. La idea principal es tener lecturas transaccionales (transactional loads en inglés) a cargo de registrar la información recopilada en la primera mitad de la operación SNAPSHOT que actualmente realiza nuestra implementación de KCSS, y guardados transaccionales (transactional stores) realizando la segunda parte de esta operación: determinar si alguno de los valores leídos ha sido modificado por una operación concurrente desde que fue leído por la lectura transaccional. KCSS también podría experimentar mejoras de su grado de concurrencia: es posible reducir las ”colisiones” entre operaciones LL/SC a costa de una operación SNAPSHOT más compleja. También es posible reutilizar los valores recopilados y los sellos de tiempos (timestamps) recopilados por esta operación, de una iteración a la otra, lo que reduce la legibilidad pero mejora la eficiencia general. Bibliography Barnes, G. A method for implementing lock-free shared-data structures. In Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures - SPAA '93. ACM Press, 1993. Barreira, J. A. C. Multiprocessors: Coherence and synchronization, computer architecture course slides. 2023. Doherty, S.,Herlihy, M.,Luchangco, V. and Moir, M. Bringing practical lock-free synchronization to 64-bit applications. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. ACM, 2004. Greenwald, M. B. Non-blocking synchronization and system design. 1999. Harris, T. L.,Fraser, K. and Pratt, I. A. A practical multi-word compareand-swap operation. In Lecture Notes in Computer Science, 265–279. Springer Berlin Heidelberg, 2002. Herlihy, M.,Eliot, J. and Moss, B. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture. IEEE Comput. Soc. Press, ???? Herlihy, M.,Luchangco, V.,Moir, M. and Scherer, W. N. Software transactional memory for dynamic-sized data structures. In Proceedings of the twentysecond annual symposium on Principles of distributed computing. ACM, 2003. Herlihy, M. and Shavit, N. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. ISBN 0123705916. Luchangco, V.,Moir, M. and Shavit, N. Nonblocking k-compare-single-swap. Theory of Computing Systems, Vol. 44(1), 39–66, 2008. Moir, M. and Shavit, N. Concurrent data structures. In Handbook of Data Structures and Applications, 47–1–47–30. Chapman and Hall/CRC, 2004. Shavit, N. and Touitou, D. Software transactional memory. Distributed Computing, Vol. 10(2), 99–116, 1997. 81