Change search
ReferencesLink to record
Permanent link

Direct link
Improving Load Balancing during the Marking Phase of Garbage Collection.
KTH, School of Computer Science and Communication (CSC).
2012 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This master's thesis will experimentally verify that it does not matter from which queue an object is stolen, how often an object is stolen or how many objects are stolen when doing load balancing via work stealing in the context of garbage collection.

As part of this experimental verification is a new way of measuring the balance of work between threads using the variance of the normalized marking times of all threads.

Finally a new load balancing algorithm that uses a private marking stack and a separate stealing queue is presented. Both data structures in the new algorithm are lock-free and the transfer of an object from the marking stack to the stealing is synchronization free.

The work leading up to these results constitutes of two phases: An extensive evaluation of the existing load balancing algorithm that is based on the work by Arora et al. and the design of the new load balancing algorithm. This work is done in the context of the garbage first garbage collector of the Java HotSpot virtual machine.

The recommendation for future research is to focus more on memory centric algorithms for load balancing.

Abstract [sv]

Detta examensarbete har experimentiellt verifierat att det spelar ingen roll från vilken kö man stjäl ett objekt, hur ofta man stjäl ett objekt eller hur många objekt man stjäl när man använder arbetsstjälande för lastbalansering vid skräphantering.

Som en del av denna experimentiella verifiering har ett nytt mått tagits fram för att mäta fördelningen av arbete mellan trådar som baseras på variansen av de olika trådarnas normaliserade markeringstider.

Slutligen har en ny lastbalanseringsalgoritm tagits fram som använder en privat markeringsstack och en separat kö som andra trådar kan stjäla ifrån. Algoritmen använder endast lås-fria datastrukturer och kräver ingen synkronisering för att överföra ett objekt från markeringsstacken till kön.

Arbetet har utförts i två faser: först utvärderades den nuvarande lastbalanseringsalgoritmen som baseras på en algoritm utav Arora et al. och därefter utvecklades en ny lastbalanseringsalgoritm. Detta arbete har utförts i skräpsamlaren "Garbage First" i den virtuella Java maskinen "HotSpot".

Rekommendationen för framtida forskning är att fokusera på lastbalanseringsalgoritmer som även tar åtkomsttider till minnet i beaktning.

Place, publisher, year, edition, pages
Trita-CSC-E, ISSN 1653-5715 ; 2012:092
National Category
Computer Science
URN: urn:nbn:se:kth:diva-130946OAI: diva2:654392
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

Other links
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link