Re: A garbage collector for C++

Ok, just to make sure I understand.  You're suggesting associating a
priority with the GC lock and boosting a thread to this priority
whenever the lock is acquired.  And the GC lock priority needs to be
higher than the priority of any mutator thread (or mutator lock if it
also uses this scheme).  And the GC won't be at this priority (have the
lock) longer than 1 microsecond.
 
I think you're also saying that pointer assignment acquires the lock and
therefore boosts the priority of a thread to the GC lock priority.  Have
you measured how long pointer assignment takes to acquire the lock?  I
think this system sounds very interesting because of the goal of minimal
interrupt latency (trading off the expense of pointer assignment).
 
Thanks for the response,
-Brian
 



________________________________

	From: Guo Mingnan [mailto:[email protected]] 
	Sent: Friday, April 28, 2006 5:28 PM
	To: Nettleton, Brian; [email protected]
	Subject: RE: [gclist] A garbage collector for C++
	
	
	Thank you very much for your interest in this system.
	
	This system does not implement priority inversion mechanism
currently. I think, when you get the source code, you would easily add
priority-inversion lock something like Solaris did. Personally, I do not
like priority lending or similar things. Sometime the owner of the lock
is unknown or the blocking chain might be very long. 
	
	Therefore, my solution is to associate priority with resource.
Every lock, which is shared among multiple priority threads and the
programmers wants to keep a strict priority ordering, should have a
fixed priority associated with it. Once a thread acquired the lock, the
thread's priority is boosted to the fixed priority of the lock. So, if a
low-priority thread acquired the lock, it blocks high-priority thread
and middle-priority thread. 
	When the low-priority thread releases the lock, the
high-priority thread gets the control and middle-priority thread keeps
waiting. The latency of high-priority thread is roughly proportion to
the time holding the lock, e.g. the time low-priority thread holding the
lock.
	
	As for this GC system, mutators normally will not acquire any
locks related to GC system. Suppose during the time the collector is
idle, the situation is merely as if no GC system existing. The
low-priority mutator threads may be interrupted by higher priority
threads as usual. I think most (if not all) of conventional locking
mechanism can apply. When a collector is doing object-marking job, other
mutators continue running. During the time, if a mutator explicit
invoking scavenge operation, it will block until the end of existing
scavenge (Future versions might support multiple collectors). Threads
run concurrently with collector, higher priority mutator will not be
affected by the scavenge operation. If the collector holds the lock
(internal of the GC system), which is also coincidental wanted by higher
priority thread doing a pointer assignment, the higher priority thread
has to wait. The worst case of racing condition, the maximum time the
higher priority thread blocked is less than 1 microsecond under current
on-shelf computer hardware. The collector always releases shared lock as
quickly as possible. 
	
	Mingnan G.


	"Nettleton, Brian" <[email protected]> wrote:

		I'm interested in understand more about your collector.
The goals you've set forth are ones I'm interested in, mostly minimal
interrupt latency.
		 
		I do have a concern about priority inversion.  If a
low-priority mutator thread has the GC lock and a high-priority thread
interrupts it and then the high-priority thread needs the lock, it then
has to wait for the low-priority thread to become available again.  It's
really only a problem if there is a middle-priority thread which then
starts running before the low-priority thread, but the effect is that
the high-priority thread has now had it's priority lowered by the GC
design.  Do you have features which handle this situation?
		 
		-Brian Nettleton

	
________________________________

	Win tickets to the 2006 FIFA World Cup Germany with Yahoo!
Messenger.
<http://us.rd.yahoo.com/mail/uk/taglines/default/messenger/fgf/*http://a
dvision.webevents.yahoo.com/fifaworldcup_uk/>