This project has retired. For details please refer to its Attic page.
BrachaTouegDeadlockVertexValue xref
View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.giraph.examples.utils;
20  
21  import java.io.DataInput;
22  import java.io.DataOutput;
23  import java.io.IOException;
24  import java.util.ArrayList;
25  import java.util.HashMap;
26  import java.util.Map;
27  
28  import org.apache.hadoop.io.LongWritable;
29  import org.apache.hadoop.io.Writable;
30  
31  /**
32   * Vertex value used for the Bracha-Toueg Dealock algorithm
33   */
34  public class BrachaTouegDeadlockVertexValue implements Writable {
35    /** Invalid ID */
36    public static final Long INVALID_ID = Long.valueOf(-1);
37  
38    /** Vertex is free from deadlock */
39    private boolean isFree;
40    /** Vertex was notified */
41    private boolean isNotified;
42    /**
43     * Active requests which need to be satisfied to free the node.
44     * Tha hash map is needed to handle the N-out-of-M semantics. The first
45     * parameter identifies the TAG of the request, the second identifies the
46     * vertex id to which an edge with points. All the eequests (edges) with the
47     * same TAG need to be satisfied to consider the vertex free.
48     */
49    private HashMap<Long, ArrayList<Long>> requests;
50    /**
51     * Structure containing the messages awaited from the other vertices.
52     * The algorithm guarantees that the vertex will not wait for two different
53     * messages from the same vertex.
54     */
55    private HashMap<Long, Long> waitingList;
56    /** IDs of the parents of this vertex */
57    private ArrayList<Long> parents;
58    /** id to which the ACK message needs to be sent for the first GRANT message
59        that releases the node; -1 identifies an empty ackId */
60    private Long idWithInHoldAck;
61    /**
62     * id to which the DONE message needs to be sent for the first NOTICE
63     * message received; -1 identifies an empty ackId
64     */
65    private Long idWithInHoldDone;
66  
67    /**
68     * Default constructor
69     */
70    public BrachaTouegDeadlockVertexValue() {
71      this(new HashMap<Long, ArrayList<Long>>());
72    }
73  
74    /**
75     * Parametrized constructor
76     *
77     * @param requests number of requests needed to consider the node free
78     */
79    public BrachaTouegDeadlockVertexValue(
80      HashMap<Long, ArrayList<Long>> requests) {
81  
82      this.isFree = false;
83      this.isNotified = false;
84      this.requests = requests;
85      this.waitingList = new HashMap<Long, Long>();
86      this.parents = new ArrayList<Long>();
87      this.idWithInHoldAck = INVALID_ID;
88      this.idWithInHoldDone = INVALID_ID;
89    }
90  
91    // Serialization functions -----------------------------------------------
92  
93    @Override
94    public void readFields(DataInput input) throws IOException {
95      int sz;
96  
97      this.isFree = input.readBoolean();
98      this.isNotified = input.readBoolean();
99  
100     sz = input.readInt();
101     for (int i = 0; i < sz; ++i) {
102       ArrayList<Long> targets = new ArrayList<Long>();
103       Long tag = input.readLong();
104       int sw = input.readInt();
105 
106       for (int j = 0; j < sw; ++j) {
107         Long target = input.readLong();
108 
109         targets.add(target);
110       }
111 
112       this.requests.put(tag, targets);
113     }
114 
115     sz = input.readInt();
116     for (int i = 0; i < sz; ++i) {
117       Long key = input.readLong();
118       Long value = input.readLong();
119 
120       this.waitingList.put(key, value);
121     }
122 
123     sz = input.readInt();
124     for (int i = 0; i < sz; ++i) {
125       this.parents.add(Long.valueOf(input.readLong()));
126     }
127 
128     this.idWithInHoldAck  = input.readLong();
129     this.idWithInHoldDone = input.readLong();
130   }
131 
132   @Override
133   public void write(DataOutput output) throws IOException {
134     int sz;
135 
136     output.writeBoolean(this.isFree);
137     output.writeBoolean(this.isNotified);
138 
139     sz = this.requests.size();
140     output.writeInt(sz);
141     for (Map.Entry<Long, ArrayList<Long>> entry : this.requests.entrySet()) {
142       ArrayList<Long> targets;
143 
144       output.writeLong(entry.getKey());
145       targets = entry.getValue();
146       sz = targets.size();
147       output.writeInt(sz);
148       for (Long target : targets) {
149         output.writeLong(target);
150       }
151     }
152 
153     sz = this.waitingList.size();
154     output.writeInt(sz);
155     for (Map.Entry<Long, Long> entry : this.waitingList.entrySet()) {
156       output.writeLong(entry.getKey());
157       output.writeLong(entry.getValue());
158     }
159 
160     sz = this.parents.size();
161     output.writeInt(sz);
162     for (int i = 0; i < sz; ++i) {
163       output.writeLong(this.parents.get(i));
164     }
165 
166     output.writeLong(this.idWithInHoldAck);
167     output.writeLong(this.idWithInHoldDone);
168   }
169 
170   // Accessors -------------------------------------------------------------
171 
172   /**
173    * @return true if free, false otherwise
174    */
175   public boolean isFree() {
176     return this.isFree;
177   }
178 
179   /**
180    * the vertex is free from deadlocks
181    */
182   public void setFree() {
183     this.isFree = true;
184   }
185 
186   /**
187    * @return true if the vertex was notified, false otherwise
188    */
189   public boolean isNotified() {
190     return this.isNotified;
191   }
192 
193   /**
194    * the vertex got a notification
195    */
196   public void setNotified() {
197     this.isNotified = true;
198   }
199 
200   /**
201    * @return false if no pending requests have to be still processed to
202    *         continue the computation
203    */
204   public boolean hasPendingRequests() {
205     boolean withPendingRequests = true;
206 
207     if (this.requests.isEmpty()) {
208       withPendingRequests = false;
209     }
210 
211     for (Map.Entry<Long, ArrayList<Long>> request : this.requests.entrySet()) {
212       ArrayList<Long> targets = request.getValue();
213 
214       if (targets.size() == 0) {
215         withPendingRequests = false;
216       }
217     }
218     return withPendingRequests;
219   }
220 
221   /**
222    * remove the expected request from the edge on which the message arrived
223    *
224    * @param tag       tag of the edge
225    * @param targetId  target Id to which the edge points
226    */
227   public void removeRequest(LongWritable tag, LongWritable targetId) {
228     Long l = Long.valueOf(tag.get());
229     ArrayList<Long> targets = this.requests.get(l);
230 
231     if (targets.contains(targetId.get())) {
232       targets.remove(Long.valueOf(targetId.get()));
233     }
234   }
235 
236   /**
237    * This function retrieves the number of pending requests for the specified
238    * tag. Because of the N-out-of-M semantic, each time a GRANT is received
239    * on an edge, the number of requests is reduced for the tag which the edge
240    * is part of.
241    *
242    * @param tag   tag related to the requests to be verified
243    * @return number of requests pending for the tag provided
244    */
245   public int getNumOfRequests(LongWritable tag) {
246     Long l = Long.valueOf(tag.get());
247     ArrayList<Long> targets = this.requests.get(l);
248 
249     return targets.size();
250   }
251 
252   /**
253    * Add a new message that must be expected by the node
254    *
255    * @param  id        ID of the node from which the messages is expected
256    * @param  type      type of message that is awaited
257    */
258   public void waitForMessage(Long id, Long type) {
259     // waiting list should not contain two messages for the same node
260     assert waitingList.get(id) == null;
261     waitingList.put(id, type);
262   }
263 
264   /**
265    * Each time a message is received, it has to be removed from the queue
266    * that keeps track of the waited messages.
267    *
268    * @param  id        ID of the node from which the messages is expected
269    * @param  type      type of message that is awaited
270    */
271   public void receivedMessage(Long id, Long type) {
272     long typel;
273 
274     assert waitingList.get(id) != null;
275     typel = waitingList.get(id).longValue();
276     assert typel > 0;
277     waitingList.remove(id);
278   }
279 
280   /**
281    * @param  type       type of message to check
282    * @return boolean    true if waiting the message type, false otherwise
283    */
284   public boolean isWaitingForMessage(Long type) {
285     for (Map.Entry<Long, Long> entry : waitingList.entrySet()) {
286       long typel = entry.getValue().longValue();
287       if ((typel & type) > 0) {
288         return true;
289       }
290     }
291 
292     return false;
293   }
294 
295   /**
296    * add a parent id into the list of parents kept at the vertex side
297    * @param parentId    vertex id of the parent
298    */
299   public void addParent(Long parentId) {
300     this.parents.add(parentId);
301   }
302 
303   /**
304    * @return list of parent IDs collected
305    */
306   public ArrayList<Long> getParents() {
307     return this.parents;
308   }
309 
310   /**
311    * @return the id waiting for an ACK message
312    */
313   public Long getIdWithInHoldAck() {
314     return this.idWithInHoldAck;
315   }
316 
317   /**
318    * @param id the id to set
319    */
320   public void setIdWithInHoldAck(Long id) {
321     this.idWithInHoldAck = id;
322   }
323 
324   /**
325    * @return the id waiting for an DONE message
326    */
327   public Long getIdWithInHoldDone() {
328     return idWithInHoldDone;
329   }
330 
331   /**
332    * @param doneId the id to set
333    */
334   public void setIdWithInHoldDone(Long doneId) {
335     this.idWithInHoldDone = doneId;
336   }
337 
338   @Override
339   public String toString() {
340     return "isFree=" + Boolean.toString(isFree);
341   }
342 }