The compare and swap() instruction can be used to design lock-free data structures such as stacks, queues, and lists. The program example shown in Figure 6.18 presents a possible solution to a...

The compare and swap() instruction can be used to design lock-free data structures such as stacks, queues, and lists. The program example shown in Figure 6.18 presents a possible solution to a lock-free stack using CAS instructions, where the stack is represented as a linked list of Node elements with the top representing the top of the stack. Is this implementation free from race conditions?

Extracted text: typedef struct node { value_t data; struct node *next; } Node; Node *top; // top of stack void push(valu0_t itom) { Node +old_node; Node +new_node; new node = malloc(sizeof (Node)); nev node->data = item; do { old nodo = top; now nodo->noxt = old_nodo; } while (compare and.swap(top, old.node,new.node) != oldnode); } value_t pop() { Node +old node; Node *nev node; do { old node = top; if (old node == NULL) return NULL; new node = old node->next; } while (compare_and_swap(top, old_node, new node) != old_node); return old node->data; } Figure 6.18 Lock-free stack for Exercise 6 15