Previous | Next --- Slide 16 of 30
Back to Lecture Thumbnails
shabnam

What is the use of the reclaim pointer? Is it just to maintain a pointer to deleted elements so that they can be deleted later?

LilWaynesFather

Note that in pop the node with the popped value isn't deleted. The head pointer is just moved up one. The reclaim pointer is there so that push can then clean up the unneeded nodes. Both allocation of nodes as well as deallocation of nodes are performed in the same thread (pop) so that we don't have to worry about having to make a thread safe version of alloc and free.

sluck

To further clarify what LilWaynesFather is saying, when we push to the queue, we have to allocate memory for the Node structure that contains the new data, and when we pop from the queue, we then would have to (eventually) free that structure. The act of freeing structures we can separate from the act of popping structures, which we do in the above code by using the reclaim pointer.

According to the man page for malloc, there are mutexes that help avoid corruption in memory management, so if we were to use malloc/free, we wouldn't have to worry about it being thread safe, but I imagine a single thread handling all of the allocations and deallocations would reduce the amount of contention over the mutexes. As a programmer, I imagine it would also make it easier to track our allocations and deallocations and thus reduce the number of memory leaks :)

kayvonf

The above comments focus on keeping allocation/free in the same thread, but you also observe that in this implementation, only the pushing thread touches tail and reclaim, and only the popping thread touches head. As a result, just like in the bounded queue case on the previous slide, the code need not synchronize accesses to these variables.