Are we still assuming that there's only one consumer (popping thread) and one producer (pushing thread) like in slide 21? I dont see how old.top could already be freed at the circled section.
kayvonf
@thomasts. No, we are not in the case of the lock-free stack. You should assume there can be arbitrarily many threads accessing the stack.
That assumption was only made for the single reader, single writer queue discussed in slide 21 and slide 22.
rajul
I have one issue with the lock-free stack. If I am using a stack I expect the entries to be LIFO where one would expect this to be determined by the order of push and pop operations.
If I do a
push(1)
push(2)
push(3)
pop()
push(4)
pop()
pop()
pop()
I would expect 3->4->2->1 to be poped. However with a lock free stack if push(1) and push(2) are called simultaneously we cannot provide guarantees of insertion order.
kayvonf
@rajul: but if you state that the pushes are "called simultaneously" you did not in fact "Do a push(1) push(2)".
Really, the order of the pushes is determined by the order in which the threads successfully complete the compare_and_swap, and this is the order in which it is correct to consider the pushes occurring.
maxdecmeridius
Was this issue a concern in the previous implementation of the lock-free stack? I don't see why we didn't worry about it then, or was it there and we just didn't talk about it?
mallocanswer
@maxdecmeridius, in the previous slide, we return a pointer to the poped node directly and let caller manage the memory operation.
Are we still assuming that there's only one consumer (popping thread) and one producer (pushing thread) like in slide 21? I dont see how old.top could already be freed at the circled section.
@thomasts. No, we are not in the case of the lock-free stack. You should assume there can be arbitrarily many threads accessing the stack.
That assumption was only made for the single reader, single writer queue discussed in slide 21 and slide 22.
I have one issue with the lock-free stack. If I am using a stack I expect the entries to be LIFO where one would expect this to be determined by the order of push and pop operations.
If I do a push(1) push(2) push(3) pop() push(4) pop() pop() pop()
I would expect 3->4->2->1 to be poped. However with a lock free stack if push(1) and push(2) are called simultaneously we cannot provide guarantees of insertion order.
@rajul: but if you state that the pushes are "called simultaneously" you did not in fact "Do a push(1) push(2)".
Really, the order of the pushes is determined by the order in which the threads successfully complete the
compare_and_swap, and this is the order in which it is correct to consider the pushes occurring.Was this issue a concern in the previous implementation of the lock-free stack? I don't see why we didn't worry about it then, or was it there and we just didn't talk about it?
@maxdecmeridius, in the previous slide, we return a pointer to the poped node directly and let caller manage the memory operation.