gc_notes

gc_notes.txt

-Background
	-garbage collection = memory reclaiming = free(), making the memory able to be allocated again.
	-Need a garbage collection algorithm for CONCURRENT, LOCK FREE data structures. 
		-concurrent data structures is harder since readers can still be in a retired node.
		-For lock free scenarios, it's hard to decide when it's a good time to reclaim a node.
	-NOT concurrent garbage collection. (Although it's another interesting topic)


-Automatic Technique: simply killing the pointers will trigger the garbage collection.
	-Reference counts
		-algorithm:
			-increase the reference count if a pointer points to it, and decrease if such a pointer is deleted.
			-If the reference count of a node is 0, deallocate it.
		-Problem:
			-the reference count and the pointer should be changed TOGETHER ATOMICALLY
			-cyclic reference.
		-"Solutions":
			-Using a DCAS, checking and changing two variables in the same time
				-Not so practical
			-In C++ 11, shared_ptr can solve the problem.
				-weak_ptr can dissolve the problem of cyclic reference.
				-for the global pointer, use atomic<shared_ptr>
		-cons:
			-smart pointers might bring overhead: complexity


-Manual Technique: in systems without automatical garbage collection, operations based on the characteristics of the data structures themselves must be done. Namely, explicit retire(). They're basically deferring strategies.

	-Epoch-based garbage collection & Quiescence-based garbage collection
		-algorithm1:
			-set a global epoch, every thread set "active" and update local epoch before an operation.
			-When retiring, add the node to the rlist of last epoch.
			-when garbage collecting, it checkes if every active threads are in current epoch. If so, increase the epoch and deallocate things in the rlist of last epoch.
		-algorithm2:
			-make the local counter updated every time when it finished accessing some data structures.
		-con: Not non-blocking.

	-Hazard Pointer
		-Code:
			-retire(node):
				-rlist <- rlist.pushback(node)
			-protect(node):
				-hp <- requireHP()
				-hp->set(node)
			-access(node):
				-protect(node)
				-if not_deleted(node)
					-do the work
				-else return false
			-Scan(): //when size(rlist) hit R, a "constant"
				-for node in rlist:
					-if node is not in hprec:
						-free(node)
		-Points:
			-A retired node can be reclaimed only if no hazard pointers have been pointing at it continuously.
			-hp: allocate->require->set->access->release->deallocate
			-Writers don't need to worry about if there are readers.
			-wait-free: if a thread holds a hazard pointer and keep running, other threads won't be affected.
		-cons:
			-When scanning, memory fences are introduced


-State-based Read-most data structures
	-making general (graph, tree) data structures into simple ones.