termination-detection-garbage-collection.md (8099B)
1 +++ 2 title = 'Termination detection & garbage collection' 3 +++ 4 5 # Termination detection 6 Termination detection in e.g. diffusing computations, workpools, deadlock detection, self stabilization. 7 8 Basic algorithm terminated if each process is passive (no sends/received), and no basic messages are in transit. 9 10 Control algorithm concerns termination detection and announcement. 11 Termination detection shouldn't influence basic computations. 12 13 ## Dijkstra-Scholten algorithm 14 Centralised basic algorithm, undirected network. 15 16 Tree T is maintained with initiation p₀ as root, and includes all active processes. 17 Initially, T only has p₀. 18 19 cc(p) estimates number of children of process p in T. 20 - when p sends basic message, cc(p) += 1 21 - let this message be received by q 22 - if q not yet in T, it joins T with parent p and cc(q) = 0. 23 - if q already in T, it sends control message to p that isn't a new child of p. Upon receipt of this message, cc(p) -= 1 24 - when noninitiator q is passive and cc(q) == 0, it quits T and informs its parent that it's no longer a child 25 - when initiator p₀ is passive and cc(p) == 0, it calls Announce 26 27 ## Shavit-Francez algorithm 28 Decentralised basic algorithm, undirected network. 29 30 Forest F of disjoint trees maintained, rooted in initiators. 31 32 Initially each initiator of basic algorithm constitutes tree in F 33 - when process p sends basic message, cc(p) += 1 34 - let this message be received by q 35 - if q not yet in a tree in F, it joins F with parent p and cc(q) = 0 36 - if q already in a tree in F, it sends control message to p that it isn't a new child of p. Upon receipt, cc(p) -= 1 37 - when noninitiator q is passive and cc(q) == 0, it informs its parent that it's no longer a child 38 - passive initiator p with cc(p) == 0 starts a wave, tagged with its ID. Processes in a tree refuse to participate, `decide` calls `Announce` 39 40 If a wave doesn't complete, another initiator for which tree not yet disappeared will start a wave. 41 Last tree to disappear will start a wave that completes. 42 43 ## Rana's algorithm 44 Decentralised algorithm, undirected network. 45 46 Each basic message is acknowledged. 47 Lamport's logical clock provides control events with a time stamp. 48 Time stamp of process is highest time stamp of its control events so far (initially 0). 49 50 Let process p at time t become quiet, i.e. p is passive and all basic messages it sent have been acknowledged 51 - p starts a wave of control messages, tagged with t and p 52 - only processes that have been quiet from time ≤ t onwards take part in the wave 53 - if wave completes, p calls Announce 54 55 ## Weight-throwing termination detection 56 Centralised basic algorithm, directed network. 57 58 Initiator has weight 1, noninitiators weight 0. 59 60 - When process sends basic message, it transfers part of its weight to this message. 61 - When a process receives a basic message, it adds the weight of this message to its own weight. 62 - noninitiator that becomes passive returns its weight to the initiator 63 - when initiator becomes passsive, and has regained weight 1, it calls Announce. 64 65 Problem with underflow, weight of process can become too small to be divided further 66 - solution 1: process gives itself extra weight and informs initiator of additional weight in the system (ack from initiator needed before extra weight can be used to avoid race condition) 67 - solution 2: process initiates weight-throwing termination detection sub-call, only returns its weight to initiator when it has become passive and the sub-call has terminated 68 69 ## Safra's algorithm 70 Decentralised basic algorithm and directed network. 71 72 Each process maintaines an integer counter, initially 0. 73 - at each outgoing/incoming basic message, counter is increased/decreased 74 - at any time, sum of all counters in network is ≥ 0, and is exactly 0 iff no basic messages are in transit 75 - at each round trip, token carries sum of counters of the processes it has traversed 76 77 Processes colored white or black, initially white 78 - process receiving basic message becomes black 79 - when p₀ becomes passiv, it sends white token with sum 0 80 - noninitiator only forwards token when it's passive, adding its counter value to sum in the token 81 - when black process forwards the token, the process becomes white and the token black (and will stay black for the rest of the round trip) 82 - eventually token returns to p₀, who waits until it's passive and then adds its counter value to the sum in the token 83 - of token and p₀ are white, and sum of all counters is 0, then p₀ calls Announce 84 - else, p₀ sends white token with counter 0 85 86 # Distributed garbage collection 87 processes provided with memory. 88 objects carry pointers to local objects and references to remote objects 89 90 three operations by processes build or delete a reference 91 - creation: object owner sends pointer to another process 92 - duplication: process that isn't object owner sends reference to another process 93 - deletion: reference deleted at its process 94 95 ## Reference counting 96 Tracks number of references to non-root object 97 - if it drops to zero, and no pointers to it, then object is garbage 98 99 Can be performed at runtime, but can't reclaim cyclic garbage. 100 101 ## Indirect reference counting 102 Tree maintained for each object, with object at root, and references to this object as othe nodes in tree 103 - each object maintains counter how many references to it created 104 - each reference supplied with counter how many times it's been duplicated 105 - references keep track of their parent in tree (where they were created/duplicated from) 106 107 If process receives reference, but already holds reference to or owns this object, it sends back decrement. 108 109 When duplicated/created reference has been deleted, and its counter is zero, decrement is sent to process it was duplicated from (or owner). 110 111 When counter of object becomes zero, and no pointers to it, object can be reclaimed. 112 113 ## Weighted reference counting 114 Each object carries total weight (weights of all references to the object) and a partial weight 115 - when reference created, partial weight of object divided over object and reference 116 - when reference duplicated, weight of reference divided over itself and copy 117 - when reference deleted, object owner is notified, and weight of deleted reference subtracted from total weight of the object 118 119 If total weight of object becomes eequal to its partial weight, and no pointers to the object, it can be reclaimed. 120 121 Underflow problem -- when weight of reference/object becomes too small to be divided further, no more duplicatation/creation possible 122 - solution 1: reference increases its weight and tells object owner to increase its total weight (ack from object owner to reference is needed before additional weight can be used to avoid race conditions) 123 - solution 2: process at which underflow occurs creates artificial object with new total weight, with reference to original object 124 125 duplicated references are then to artificial object, so references to original object become indirect. 126 127 ## Garbage collection to termination detection 128 Garbage collection algorithms can be transformed into termination detection algorithms. 129 130 Given a basic algorithm. 131 Let each process p host one artificial root object O(p). 132 There is special non-root object Z. 133 - initially, only initiators p hold reference from O(p) to Z 134 - when process becomes passive it deletes its Z-refeference 135 - basic algorithm terminated iff Z is garbage 136 137 ## Mark-scan 138 Two phases: 139 - traversal of all acessible objects, which are marked 140 - all unmarked objects are reclaimed 141 142 But in a distributed settings, mark-scan usually needs basic computation to freeze. 143 144 Mark-copy: second phase consists of copying all marked objects to empty memory space. 145 146 Mark-compact: second phase compacts all marked objects without requiring empty space. 147 148 ## Generational garbage collection 149 In practice, most objects either reclaimed shortly after creation, or stay accessible for very long time. 150 151 Garbage collection in Java divides object into two generations 152 - garbage in young generation collected frequently with mark-copy 153 - garbage in old generation collected sporadically with mark-compact