FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 | 2 || 4 |

«Cambridge CB3 0FD, U.K. IBM T.J. Watson Research Center P.O. Box 704, Yorktown Heights, NY 10598, U.S.A. Abstract. There are many algorithms for ...»

-- [ Page 3 ] --

In the abstract algorithm, all memory is reached from a single root. Thus stacks and global variables are treated as objects like any other. Such an approach is actually used in some implementations of functional programming languages [12]. However, in systems with a significant level of optimization, the cost of such an approach is prohibitive because the mutation rate of the stack is generally extremely high and every stack mutation must include a write barrier.

Therefore, we can transform an abstract algorithm with a uniform treatment of memory into an algorithm which partitions memory into two regions: the roots and the heap. The roots generally include the stack and may also contain the static variables and other distinguished pointer data.

In common parlance the static variables are generally considered to be roots, but if they are barriered then they are in effect treated as fields of the “global variable object”, and only the pointer to that “object” is a true root. From the point of view of the root transformation, the only issue is that the memory is partitioned into two sets, the roots and the heap, such that there are no pointers from the heap into the roots.

In the abstract collector, there is a single root pointer. Therefore, examining the root is an inherently atomic operation. With the addition of multiple roots, they must either be processed atomically or a further transformation must be applied to incrementalize root processing [15]. In this work we restrict ourselves to algorithms with atomic root processing.

In particular, at the beginning of every collection, we stop the mutators and mark all heap objects directly reachable from roots, placing them on the work queue (mark stack). Subsequently, when the roots are mutated, no write barrier is executed.

Since the roots are processed atomically at the beginning of collection, they are in effect a scanned object. However, since we no longer perform a barrier on mutation, the SRC field of objects referenced by mutated roots is no longer guaranteed to be correct and they will not have been placed in the barrier buffer. Therefore, the algorithm must be adjusted to correct or accommodate this imprecision.

The imprecision can be corrected by atomically re-scanning the roots before barrier processing. Consider a sequence of stores into a particular root pointer. These stores must be treated like stores into a scanned portion of the heap, so that the SRC of the installed and overwritten pointers must be incremented and decremented, respectively. If we rescan the roots, then any pointers which were scanned previously will have already been marked, and the SRC will be unaffected.

When a pointer to an unscanned object is stored into a root for the first time, the pointer that is being overwritten must point to a marked object, since all direct referents of roots are marked atomically at the start of collection. Thus the SRC of the overwritten pointer would not have changed if the write had been barriered. However, the SRC of the newly installed pointer would have been incremented, but if the roots are rescanned this pointer will be discovered and since it points to an unmarked object it is known to be a new pointer, and the SRC is incremented. Thus in the case of a single store to a root, the SRC is correct.

Inductively, if there are multiple stores to a root, then each subsequent store will cause the SRC of the overwritten pointer to be decremented and the SRC of the installed pointer to be incremented. The decrement will cancel the increment that was performed on the same pointer when it was previously installed. Therefore, a sequence of stores to a particular root pointer will result in the SRC of all objects except the last one to remain unchanged. 1 Since that object is found by rescanning, rescanning will compute an accurate SRC, and the transformation that separates the memory into roots and heap leaves the precision of the algorithm unchanged.

3.2 Root Rescan Elimination

As we have just shown, the special treatment of roots does not affect the precision of the collector if root re-scanning is used to correct the SRC. However, re-scanning is undesirable because it increases the running time of the algorithm.

If root re-scanning is eliminated, then the SRC values may be under-approximations (because the increment of the final pointer stored in a root will have been missed). Since increments may keep objects live that would otherwise have been collected, this means This is the same reasoning that was applied by Barth to eliminate redundant reference count updates at compile time [8], and by Levanoni and Petrank to remove redundant reference count updates between epochs in a concurrent reference counting collector [22].

that any reclamation of an object based on its SRC being 0 is unsafe. Therefore, the algorithm must be conservative in such cases and precision will be sacrificed.

Furthermore, when an installation barrier is used the installation of pointers into the scanned portion of the heap is what causes them to be remembered in the barrier buffer for further tracing during barrier processing. This means that regardless of the imprecision of the SRC, objects that would have had a non-zero SRC must be seen during barrier processing. In effect, this means re-scanning can not be eliminated for algorithms that use the installation barrier.

For algorithms that use the deletion barrier, the only pointers to new objects that are remembered in the write barrier are the newly allocated objects. Therefore, as long as those objects are placed in the barrier buffer by the allocator, and the SRC-based computation in the barrier processing is eliminated, then the root re-scanning can be safely eliminated.

Since no collector decisions are based on the value of the SRC, it is redundant and can be eliminated. The result is an algorithm with more floating garbage (in particular, all newly allocated objects are considered live), of which Yuasa’s algorithm is an example.

3.3 Shade Compression

The shade of an object represents the progress of the collector as it processes the individual pointers in the object. The precision of the shade can always safely be reduced as long as the processing of the pointers in the object in the write barrier treats the imprecise shade conservatively.

In particular, since many objects have a small number of pointers N, it is efficient to treat the shade which originally had the range [0, N ] as the set {0, [1... N − 1], N }.

These three values represent an object for which collector processing has not yet begun, is in progress, or has been completed. This is the standard tri-color abstraction introduced by Dijkstra, where the three values are called white, grey, and black, respectively.

When N is small, the chance is low that the mutator will store a pointer into the object currently being processed by the collector, so the reduction in precision is likely to be low. However, with large objects (such as pointer arrays) the reduction in precision can be more noticeable. Some collectors therefore treat sections of the array independently, in effect mapping equal-sized subsections of the array into different shades.

3.4 Scanned Reference Count Compression

The scanned reference count (SRC) can range from 0 to the number of pointers in the system. However, the number of references to an object is usually small, and the SRC will be even lower (since it only counts references from the scanned portion of the heap to unmarked objects). Therefore, the SRC can be compressed and the loss of precision is likely to be low.

However, the compression must be conservative to ensure that live objects are not collected. This is accomplished by making the SRC into a “sticky” count [26]: once it reaches its maximum value, it is never decremented. As a result, the SRC is an overapproximation, which is always safe since it will only cause additional objects to be treated as live.

An important special case for collectors that use an installation barrier is a one-bit SRC, since in this case the SRC becomes equivalent to the Recorded flag, allowing those two fields to be collapsed.

3.5 Conflation of Shade and Scanned Reference Count In a collector using an installation barrier with a one-bit sticky SRC and tri-color shade, an object with a stuck SRC must be scanned by the collector. Similarly, a grey object must be scanned by the collector. Thus the meaning of these two states can be collapsed and the grey color can be used to indicate a non-zero (stuck) SRC, which also represents the Recorded flag.

This is in fact the representation used by most collectors that have been implemented. In effect, they have collapsed numerous independent invariants into a small number of states. This helps to understand why such algorithms are bug-prone: collapsing the states corresponding to algorithmic invariants relies on subtle transformations and simultaneously reduces redundancy in the representation.

4 Using Transformations to Derive Practical Collectors In this section, we derive various practical algorithms by applying the previously discussed transformations to the abstract collector algorithm. Some of the schemes are well-known concurrent algorithms such as Dijkstra and Yuasa, while others are new derivations.

4.1 Derivation of a Dijkstra Algorithm The Dijkstra algorithm is an instance of an abstract installation collector and to derive

it we apply the following transformations:

1. Root Sets transformation

2. Shade compression to tri-color

3. SRC compression to a single sticky bit

4. Conflation of Shade and SRC Although at the end of the transformation steps, we arrive at a practical Dijkstra algorithm, the intermediate steps also represent valid algorithms with different precision.

The compressions of SRC and Shade can lead to floating garbage. However, unlike Shade and SRC compressions, the Conflation transformation does not lead to increased floating garbage. On the other side, it reduces, both, space consumption in the header of the object, and, complexity of the write barrier.

The Root Sets transformation also preserves the treatment of allocated objects.

When a new object is allocated and stored into the roots, the mutator will not nominate the pointer because the store will occur into a scanned partition (roots) and the MarkRoots() while (! roots.end()) Obj = roots.get();


–  –  –

Fig. 5. Pseudo Code For The Hybrid Collector write barrier is not active on the roots. If the pointer to the allocated object gets stored in the heap, then it will be processed in the mutator write barrier, similarly to all other objects existing at collection startup. If the allocated object dies before the roots are rescanned, the collector will not mark that object as live.

A Steele-like collector is similar to a Dijkstra collector except that its transformation covers a wider range of rescanning. A Steele algorithm is not limited to rescanning only the roots, but can also rescan heap partitions. However, the barrier processing phase and the selection criteria are exactly the same as in the Dijkstra collector.

4.2 Derivation of a Yuasa Algorithm Our second derived collector is a Yuasa snapshot algorithm. The Yuasa algorithm is an instance of a deletion collector. The algorithm can be derived by applying the following

transformations to the abstract collector:

1. Root Sets transformation

2. Shade compression to tri-color

3. Root Rescan Elimination During barrier processing, deletion collectors can skip objects whose SRC is 0 and are leafs. However, since Root Rescan elimination prevents the roots rescanning process, an accurate SRC cannot be computed, and subsequently the collector selection criteria cannot be applied. Therefore, in order to preserve the safety property of the abstract collector, the collector must mark all overwritten pointers and rescan from them.

The SRC is removed since it cannot serve its primary purpose: a guide for the collector selection criteria.

The Yuasa collector is the most conservative approach to floating garbage. It does not allow any destruction in the connectivity graph once the collector has started and it effectively allocates only reachable object (black).

One fundamental difference between Yuasa and Dijkstra algorithms is that in the presence of a Root Sets transformation, installation collectors must never use the Root Rescan elimination, while deletion collectors have no requirement to apply it. The rescanning in deletion collectors is done mostly to eliminate floating garbage, albeit, at the expense of triggering work to rescan the roots.

Also, although at the end of our derivation, we arrived at a Yuasa algorithm, the result of every intermediate step is a valid deletion collector.

4.3 Derivation Of a Hybrid Algorithm The third derived practical algorithm is the Hybrid collector. The Hybrid algorithm is an instance of an abstract deletion collector. The Hybrid algorithm can be derived by

applying the following transformations:

1. Root Sets transformation

2. Shade compression to tri-color

3. SRC compression to a single sticky bit

4. Conflation of Shade and SRC

5. Root Rescan elimination for existing objects

6. Over approximate Shade The first two transformation steps are the same as for the Yuasa algorithm. However, in the Hybrid algorithm, we utilize the rescanning of roots only for newly allocated objects. The roots rescan transformation is parameterized to be active only for existing objects. The idea is to obtain a deletion Yuasa algorithm for the existing heap graph while maintaining a less restricted policy for newly allocated objects, similarly to the Dijkstra collector. By eliminating rescanning for existing objects, we can remove the SRC for those objects. Whenever the collector encounters an existing object during its barrier processing phase it will always mark the object, without applying any selection criteria.

Pages:     | 1 | 2 || 4 |

Similar works:

«Cthulhu Vice Neon Nightmares in a Neo-Noir Pastel Paradise Version 1.0 Collin Terrell Collin Terrell 2009 Page 1 This game references the Savage Worlds game system, available from Pinnacle Entertainment Group at www.peginc.com. Savage Worlds and all associated logos and trademarks are copyrights of Pinnacle Entertainment Group. Used with permission. Pinnacle makes no representation or warranty as to the quality, viability, or suitability for purpose of this product. Acknowledgements: Thanks to...»

«Stacy Alaimo Department of English 3454 S. Franklin Box 19035 Dallas, TX 75233 University of Texas at Arlington alaimo@uta.edu Arlington, TX 76019 http://www.uta.edu/english/alaimo Education: Ph.D. University of Illinois, Department of English, May 1994. Certificate. The Unit for Criticism and Interpretive Theory, University of Ilinois, 1993. M.A. University of Wisconsin, Madison, Department of English, 1986. B.A. Gustavus Adolphus College, St. Peter, Minnesota. Magna Cum Laude, 1985. Academic...»

«PROGRAMM FRÜHJAHRSSEMESTER 2015 PROGRAMM FRÜHJAHRSSEMESTER 2015 23.02. 31.07.2015 Anmeldung ab sofort möglich. Sommer-VHS Spezielle Angebote für Spezielle Angebote 11.07. 31.07.2015 Schüler und Jugendliche für Familienlkshochschule bleibt zum Jahreswechsel vom 22.12.2013 bis 02.01.2014 geschlossen. ANSCHRIFT Volkshochschule Leipzig Internet: www.vhs-leipzig.de Löhrstraße 3 7, 04105 Leipzig E-Mail: vhs@leipzig.de Service / Telefonische Anmeldung 0341 123-6000 (Mo. Fr. 8 18 Uhr / April...»

«Cluster Analysis: Tutorial with R Jari Oksanen January 27, 2014 Contents 1 Introduction 1 2 Hierarchic Clustering 1 2.1 Description of Classes........................ 4 2.2 Numbers of Classes.......................... 5 2.3 Clustering and Ordination...................... 6 2.4 Reordering a Dendrogram...................... 7 2.5 Minimum Spanning Tree....................... 9 2.6...»

«Computer Science Courses-1 CSC 099/Orientation to Computer Science 0 course units (fall) An introduction to the computer science program with a focus on the discipline, including an investigation of computing ethics. Students familiarize themselves with departmental procedures, standards, staff and faculty. An introduction to mentored research and internship experiences engages the first-year student in the culture and expectations of the department and of the discipline. Students develop an...»

«AN INVESTIGATION OF STEREOTYPE THREAT IN CALIFORNIA’S CHILD WELFARE COMMON CORE James Coloma, MSW, Cynthia Parry, Ph.D., & Leslie Zeitler, LCSW ABSTRACT In California’s Child Welfare Common Core Training Program, Caucasian trainees have often scored higher on posttests, and occasionally have increased their scores more from pre to posttest than trainees in one or more other racial/ethnic groups. However, previous analyses in which items showing differential functioning by race were...»

«1    Writing Abstracts for Bachelor’s and Master’s Theses Author: Greg Bond, February 2009 With thanks to Kaija Tuomainen from North Karelia University, Finland Contents: What Is an Abstract? p. 2 Why Are Abstracts Used? p. 2 What Is Usually Included in an Abstract p. 2 Qualities of a Good Abstract p. 2 Steps for Writing Effective Abstracts p. 3 Types of Thesis – How to Say Them in English p. 3 Length of Abstracts p. 3 A Simple Abstract Structure p. 3 Abstract and Thesis Titles and...»

«487 MEMOIR OF EDWARD WALLER CLAYPOLE Treasurer : I. C. W h it e, Morgantown, W. Va.Editor : J. S t a n l e y -B row n, Washington, D. C.Librarian : H. P. Cushing, Cleveland, 0.Councillors : C. W. H a y e s, Washington, D. C. J. P. I dd ing s, Chicago, 111. E L E C T I O N OF F E L L O W S The result of the balloting for Fellows, as canvassed by the Council, was announced, and the following persons were declared elected Fellows of the Society: C o w lb s C a se, A. B., A. M. (Kansas State...»

«IOSR Journal of Computer Engineering (IOSR-JCE) e-ISSN: 2278-0661,p-ISSN: 2278-8727, Volume 17, Issue 2, Ver. 1 (Mar – Apr. 2015), PP 61-64 www.iosrjournals.org Analysis of Spending Pattern on Credit Card Fraud Detection Capt. Dr. S Santhosh Baboo1, N Preetha 2 Associate Professor, 2 Research Scholar 1,2 Department of Computer Science and Applications D.G.Vaishnav College, Arumbakkam, Chennai, PhD Research Scholar SCSVMV University, Enathur, Kancheepuram Abstract: Credit card is one of the...»

«Publish detail Ruf Der Sehnsucht books document, also Download PDF Ruf Der Sehnsucht digital file RUF DER SEHNSUCHT PDF Download: RUF DER SEHNSUCHT PDF RUF DER SEHNSUCHT PDF Read story ruf der sehnsucht PDF? You will be glad to know that right now ruf der sehnsucht PDF is available on our online library. With our online resources, you can find ruf der sehnsucht or just about any type of ebooks, for any type of product. Index files are entirely free to find, use and download, so there is no cost...»

«'Muster ohne Wert' Zur Funktionalisierung und Marginalisierung des Musters Dissertation zur Erlangung des akademischen Grades Doktor der Philologie im Fachbereich 16 der Universität Dortmund vorgelegt von Kerstin Kraft Bochum 2001 Inhaltsverzeichnis Das Mustern des Musters 5 Das Muster als Suchkategorie 6 Die Holzwege der Etymologie 6 Die Muster der Natur 8 ‘Was, wenn überhaupt etwas, ist ein Muster?’ 9 Limitrophie – Vom methodischen Umgang mit Mustern 10 Musterbildungsprozesse als...»

«On Complexity and Emergence arXiv:nlin/0101006v1 [nlin.AO] 2 Jan 2001 Russell K. Standish High Performance Computing Support Unit University of New South Wales http://parallel.hpc.unsw.edu.au/rks February 3, 2008 Abstract Numerous definitions for complexity have been proposed over the last half century, with little consensus achieved on how to use the term. A definition of complexity is supplied here that is closely related to the Kolmogorov Complexity and Shannon Entropy measures widely used...»

<<  HOME   |    CONTACTS
2016 www.book.xlibx.info - Free e-library - Books, abstracts, thesis

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.