Java > Open Source Codes > org > objectweb > perseus > concurrency > distributed > globallock > TestGlobalLock


1 /**
2  * Copyright (C) 2003-2004
3  * - France Telecom R&D
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR AE PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  *
19  * Release: 1.0
20  *
21  * Authors: Olivier Lobry (olivier.lobry@rd.francetelecom.com)
22  *
23  */
24
25 package org.objectweb.perseus.concurrency.distributed.globallock;
26
27
28 import junit.framework.TestCase;
29 import org.objectweb.perseus.concurrency.lib.RWLockValue;
30 import org.objectweb.perseus.concurrency.distributed.globallock.api.GlobalLockManager;
31 import org.objectweb.perseus.concurrency.distributed.globallock.lib.GlobalLockCoordinatorFactory;
32 import org.objectweb.perseus.concurrency.distributed.globallock.lib.BasicGlobalLockManager;
33 import org.objectweb.perseus.distribution.api.DistResControllerService;
34 import org.objectweb.perseus.distribution.api.DistResServiceManager;
35 import org.objectweb.perseus.distribution.api.DistResUserService;
36 import org.objectweb.perseus.distribution.jgroups.JGroupsServiceManager;
37 import org.objectweb.perseus.distribution.lib.BasicSerializer;
38 import org.objectweb.perseus.concurrency.distributed.util.RelativeTime;
39 import org.objectweb.perseus.concurrency.distributed.util.CoordInterceptorFactory;
40 import org.objectweb.perseus.concurrency.distributed.util.ServiceManagerInterceptor;
41 import org.objectweb.perseus.concurrency.distributed.util.MessageObserver;
42 import org.objectweb.perseus.concurrency.distributed.util.MessageEventListenerRegistry;
43 import org.objectweb.perseus.concurrency.distributed.util.action.Action;
44 import org.objectweb.perseus.concurrency.distributed.util.action.MoveCoord;
45 import org.objectweb.perseus.concurrency.distributed.util.action.RunnableActions;
46 import org.objectweb.perseus.concurrency.distributed.util.action.ThrownException;
47 import org.objectweb.perseus.concurrency.distributed.util.action.AbstractBlockingAction;
48 import org.objectweb.perseus.concurrency.distributed.util.event.EventManager;
49 import org.jgroups.log.Trace;
50
51 import java.util.LinkedList ;
52 import java.util.List ;
53 import java.util.Random ;
54
55
56 public class TestGlobalLock extends TestCase {
57
58     // number of nodes required and sufficient to run the tests
59 static final byte nbNodes = 4;
60     // WTU = wait time unit (in milli sec): should be equal to the average
61 // time to get a lock without competition. It is used to sequentialized
62 // blocking actions and may need to be re-adjusted if the communication
63 // latency is too high (in which case, an action could be treated before
64 // its preedeceding action)
65 // static final long WTU = 400; // 200 seems ok w/ JGroups (400 w/ move coord)
66 // static final long standardRunTime = 0 * WTU;
67 // static final long deadlockTimeout = 0 * WTU; // 0 = no timeout
68 static final long standardRunTime = 0; // 0 = no timeout
69 static final long deadlockTimeout = 0; // 0 = no timeout
70 static final int nbIterations = 10;
71
72     GlobalLockInterceptor[] h = new GlobalLockInterceptor[nbNodes];
73     GlobalLockManagerInterceptor[] glm = new GlobalLockManagerInterceptor[nbNodes];
74     String r1 = "r1";
75     EventManager em;
76     MessageObserver msgObs;
77     MessageEventListenerRegistry reg;
78     ThrownException te;
79     Object [] node = new Object [nbNodes];
80
81     DistResUserService[] drus = new DistResUserService[nbNodes];
82     DistResServiceManager drsm;
83     CoordInterceptorFactory glcf;
84
85     // moveCoordPeriod values: 0 -> do not move coord, -1 move coord as
86 // soon as possible, x>0 -> move coord every x milliseconds
87 static final long moveCoordPeriod = 0;
88     static final int moveCoordPrintPeriod = 1;
89     boolean stopMoveCoord = false;
90     Object moveCoordMutex = new Object ();
91     Thread moveCoordThread;
92
93     List performers;
94
95
96     // shortcuts
97 static final byte P = AbstractBlockingAction.PARALLEL;
98     static final byte S = AbstractBlockingAction.SEQUENTIAL;
99     static final byte UG = AbstractBlockingAction.GRANTED_BYUSER;
100     static final byte CG = AbstractBlockingAction.GRANTED_BYCOORD;
101     static final byte UQ = AbstractBlockingAction.QUEUED_BYUSER;
102     static final byte CQ = AbstractBlockingAction.QUEUED_BYCOORD;
103
104     static final byte R = RWLockValue.READ;
105     static final byte W = RWLockValue.WRITE;
106     static final byte N = RWLockValue.NOLOCK;
107     static GlobalLockInterceptor GL1, GL2, GL3, GL4;
108     static Object N1, N2, N3, N4;
109
110     public TestGlobalLock(String s) throws Exception {
111         super(s);
112     }
113
114     protected void setUp() throws Exception {
115         trace("setting Up:");
116         // initialize jgroups traces
117 Trace.init();
118         msgObs = new MessageObserver();
119         reg = new MessageEventListenerRegistry();
120
121         glcf = new CoordInterceptorFactory(
122                 new GlobalLockCoordinatorFactory(new RWLockValue()),
123                 msgObs);
124
125         drsm = new ServiceManagerInterceptor(new JGroupsServiceManager(),
126                 msgObs, reg);
127
128         drsm.setSerializer(new BasicSerializer());
129
130         // Create nodes in reverse order so that the last one is the coordinator
131 for (int cpt = nbNodes -1; cpt >= 0; cpt--) {
132             trace("Creating node :" + cpt);
133             glm[cpt] = new GlobalLockManagerInterceptor(drsm, glcf, reg);
134             node[cpt] = glm[cpt].getNodeId();
135             drus[cpt] = drsm.getUserService(node[cpt]);
136             h[cpt] = (GlobalLockInterceptor) glm[cpt].getGlobalLock(r1, true);
137             h[cpt].setName("" + (cpt +1));
138         }
139         N1 = node[0]; N2 = node[1]; N3 = node[2]; N4 = node[3];
140         GL1 = h[0]; GL2 = h[1]; GL3 = h[2]; GL4 = h[3];
141
142         performers = new LinkedList ();
143         //RelativeTime.wakeUpSkew = (int) WTU / 2; // wake up skew of 50 % of WTU
144 em = new EventManager();
145         te = new ThrownException();
146         AbstractBlockingAction.init(em, te, reg);
147     }
148
149
150     protected void cleanUp() {
151         trace("Cleaning up:");
152         if (moveCoordPeriod != 0) {
153             trace("Stopping move coord");
154             stopMoveCoord = true;
155             try {
156                 moveCoordThread.join(4000);
157             } catch (InterruptedException e) {
158                 moveCoordThread.interrupt();
159             }
160             trace("Stopping move coord done");
161         }
162
163         //TODO: should be merged
164 for (int cpt = 0; cpt < nbNodes; cpt++) {
165             trace("Stopping node " + cpt);
166             ((JGroupsServiceManager)
167                     ((ServiceManagerInterceptor) drsm).getIntercepted())
168                     .stopLocalNode(node[cpt]);
169         }
170         for (int cpt = 0; cpt < nbNodes; cpt++) {
171             trace("Removing node " + cpt);
172             drsm.removeLocalNode(node[cpt]);
173         }
174     }
175
176     private void trace(String s) {
177         System.out.println(s);
178     }
179     private void go() throws Exception {
180         go(standardRunTime, nbIterations);
181     }
182     private void go(long maxTime, int nbIterations) throws Exception {
183
184         em.start();
185         te.clearExceptions();
186
187         if (moveCoordPeriod != 0) moveCoordThread = startMoveCoordThread();
188         // Thread.sleep(1000);
189
190         try {
191             for (int cpt = 0; cpt < nbIterations; cpt++) {
192
193                 trace("TEST #" + cpt);
194
195                 List threads = new LinkedList ();
196                 trace("\nExpected:\n" + em.printSchedule(em.expected));
197
198                 RelativeTime.startTime(0);
199 // Thread.sleep(1000);
200
201                 for (int i=0; i < performers.size(); i++) {
202                     Thread t = new Thread ((Runnable ) performers.get(i),
203                             "___ THREAD " + i);
204                     trace("Start :" + performers.get(i));
205                     threads.add(t);
206                     t.start();
207                 }
208
209                 try {
210                     for (int i=0; i < threads.size(); i++) {
211
212                         trace("Wait for thread " + i);
213                         ((Thread ) threads.get(i)).join(maxTime);
214
215                         if (te.hasExceptions()) {
216                             trace("Some exceptions have been thrown: " + te);
217                             throw te;
218                         }
219
220                         if (((Thread ) threads.get(i)).isAlive()) {
221                             trace("Thread " + i + " is blocked");
222                             // cleanUp();
223 em.expected.resetElements();
224                             trace("\nExpected:\n" + em.printSchedule(em.expected));
225                             trace("Observed:\n" + em.printSchedule(em.observed));
226                             fail("There are blocked threads");
227                         }
228
229                     }
230
231                     trace("Observed:\n" + em.printSchedule(em.observed));
232                     trace("END");
233                 } catch (InterruptedException e) {
234                     e.printStackTrace();
235                 }
236                 msgObs.waitEmpty();
237                 em.reset();
238                 // uncache locks to have same context at each run
239 for (int n = 0; n < nbNodes; n++)
240                     h[n].uncache();
241             //Thread.sleep(1000);
242 }
243         } finally {
244             cleanUp();
245         }
246     }
247
248     private Thread startMoveCoordThread() {
249         Thread t = new Thread (new Runnable () {
250             public void run() {
251                 DistResControllerService drcs0 = drsm.getControllerService(node[0]);
252                 try {
253 // Thread.sleep(1000);
254 int numMove = 0;
255                     Random rand = new Random ();
256                     stopMoveCoord = false;
257                     while(true) synchronized (moveCoordMutex) {
258                         if (stopMoveCoord) break;
259                         int dest;
260                         do {
261                             dest = rand.nextInt(nbNodes);
262                         } while (drcs0.getCoordinators(r1).contains(node[dest]));
263
264                         DistResControllerService drcs =
265                                 drsm.getControllerService(node[dest]);
266                         Action a = new MoveCoord(drcs, r1, em);
267                         if (numMove % moveCoordPrintPeriod == 0)
268                             trace("===MOVE=== (" + numMove + ")");
269                         a.perform();
270                         if (numMove % moveCoordPrintPeriod == 0)
271                             trace("===MOVE DONE=== (" + numMove + ")");
272                         if (moveCoordPeriod > 0) Thread.sleep(moveCoordPeriod);
273                         numMove++;
274                     }
275                     Thread.sleep(1000);
276                 } catch (Exception e) {
277                     e.printStackTrace();
278                 }
279             }
280         }, "___MoveCoord");
281         t.start();
282         return t;
283     }
284
285     /**
286      * Test write is not granted while there are conflicts w/ reads
287      * UR1: upgrade to R on node 1 (granted)
288      * UR2: upgrade to R on node 2 (granted)
289      * UR3: upgrade to R on node 3 (granted)
290      * UW4: upgrade to W on node 4 (queued by coord)
291      * DN1: downgrade to N on node 1
292      * DN2: downgrade to N on node 2
293      * DN3: downgrade to N on node 3 (UW4 granted)
294      * DN4: downgrade to N on node 4
295      * GL1 (t1) UR1 -->DN1
296      * GL2 (t2) UR2 | DN2
297      * GL3 (t3) UR3 | -->DN3
298      * GL4 (t4) -->UW4..........^-->DN4
299      */
300
301
302     public void testMultipleRBlockOneW() throws Exception {
303         trace("testMultipleRBlockOneW");
304
305         Action UR1 = new Upgrade(GL1, CG, S, R, false);
306         Action UR2 = new Upgrade(GL2, CG, P, R, false);
307         Action UR3 = new Upgrade(GL3, CG, P, R, false);
308         Action UW4 = new Upgrade(GL4, CQ, S, W, false);// UW4 QUEUED
309 Action DN1 = new Downgrade(GL1, S, N);
310         Action DN2 = new Downgrade(GL2, P, N);
311         Action DN3 = new Downgrade(GL3, S, N);
312         em.addExpectedEvent(UW4.endEvent(), true); // UW4 UNQUEUED
313 Action DN4 = new Downgrade(GL4, S, N);
314
315         List a1 = new LinkedList (); a1.add(UR1); a1.add(DN1);
316         List a2 = new LinkedList (); a2.add(UR2); a2.add(DN2);
317         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
318         List a4 = new LinkedList (); a4.add(UW4); a4.add(DN4);
319
320         performers.add(new RunnableActions("GL1(t1)", a1, te));
321         performers.add(new RunnableActions("GL2(t2)", a2, te));
322         performers.add(new RunnableActions("GL3(t3)", a3, te));
323         performers.add(new RunnableActions("GL4(t4)", a4, te));
324         go();
325
326     }
327
328     /**
329      * Test reads are not granted while there are conflicts w/ one write
330      * UW1: upgrade to W on node 1 (granted)
331      * UR2: upgrade to R on node 2 (queued by coord)
332      * UR3: upgrade to R on node 3 (queued by coord)
333      * UR4: upgrade to R on node 4 (queued by coord)
334      * DR1: downgrade to R on node 1 (UR2, UR3, UR4 unqueued)
335      * DN1: downgrade to N on node 1
336      * DN2: downgrade to N on node 2
337      * DN3: downgrade to N on node 3
338      * DN4: downgrade to N on node 4
339      * GL1 (t1) UW1 -->DR1-->DN1
340      * GL2 (t2) -->UR2...! DN2
341      * GL3 (t3) UR3...! DN3
342      * GL4 (t4) UR4...! DN4
343      */
344
345     public void testOneWBlocksMultipleR_R() throws Exception {
346         trace("testOneWBlocksMultipleR_R");
347
348         Action UW1 = new Upgrade(GL1, CG, S, W, false);
349         Action UR2 = new Upgrade(GL2, CQ, S, R, false);// QUEUED
350 Action UR3 = new Upgrade(GL3, CQ, P, R, false);// QUEUED
351 Action UR4 = new Upgrade(GL4, CQ, P, R, false);// QUEUED
352 Action DR1 = new Downgrade(GL1, S, R);
353         em.addExpectedEvent(UR2.endEvent(), true); // UR2 UNQUEUED
354 em.addExpectedEvent(UR3.endEvent(), true); // UR3 UNQUEUED
355 em.addExpectedEvent(UR4.endEvent(), true); // UR4 UNQUEUED
356 Action DN1 = new Downgrade(GL1, S, N);
357         Action DN2 = new Downgrade(GL2, P, N);
358         Action DN3 = new Downgrade(GL3, P, N);
359         Action DN4 = new Downgrade(GL4, P, N);
360
361         List a1 = new LinkedList (); a1.add(UW1); a1.add(DR1); a1.add(DN1);
362         List a2 = new LinkedList (); a2.add(UR2); a2.add(DN2);
363         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
364         List a4 = new LinkedList (); a4.add(UR4); a4.add(DN4);
365
366         performers.add(new RunnableActions("GL1(t1)", a1, te));
367         performers.add(new RunnableActions("GL2(t2)", a2, te));
368         performers.add(new RunnableActions("GL3(t3)", a3, te));
369         performers.add(new RunnableActions("GL4(t4)", a4, te));
370         go();
371
372
373     }
374     /**
375      * Test reads are not granted while there are conflicts w/ one write
376      * Same as before exept that write is downgraded directly to N
377      * UW1: upgrade to W on node 1 (granted)
378      * UR2: upgrade to R on node 2 (queued by coord)
379      * UR3: upgrade to R on node 3 (queued by coord)
380      * UR4: upgrade to R on node 4 (queued by coord)
381      * DR1: downgrade to N on node 1 (UR2, UR3, UR4 unqueued)
382      * DN2: downgrade to N on node 2
383      * DN3: downgrade to N on node 3
384      * DN4: downgrade to N on node 4
385      * GL1 (t1) UW1 -->DRN-->DN1
386      * GL2 (t2) -->UR2...! DN2
387      * GL3 (t3) UR3...! DN3
388      * GL4 (t4) UR4...! DN4
389      */
390
391     public void testOneWBlocksMultipleR_N() throws Exception {
392         trace("testOneWBlocksMultipleR_N");
393
394         Action UW1 = new Upgrade(GL1, CG, S, W, false);
395         Action UR2 = new Upgrade(GL2, CQ, S, R, false);// QUEUED
396 Action UR3 = new Upgrade(GL3, CQ, P, R, false);// QUEUED
397 Action UR4 = new Upgrade(GL4, CQ, P, R, false);// QUEUED
398 Action DN1 = new Downgrade(GL1, S, N);
399         em.addExpectedEvent(UR2.endEvent(), true); // UR2 UNQUEUED
400 em.addExpectedEvent(UR3.endEvent(), true); // UR3 UNQUEUED
401 em.addExpectedEvent(UR4.endEvent(), true); // UR4 UNQUEUED
402 Action DN2 = new Downgrade(GL2, S, N);
403         Action DN3 = new Downgrade(GL3, P, N);
404         Action DN4 = new Downgrade(GL4, P, N);
405
406         List a1 = new LinkedList (); a1.add(UW1); a1.add(DN1);
407         List a2 = new LinkedList (); a2.add(UR2); a2.add(DN2);
408         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
409         List a4 = new LinkedList (); a4.add(UR4); a4.add(DN4);
410
411         performers.add(new RunnableActions("GL1(t1)", a1, te));
412         performers.add(new RunnableActions("GL2(t2)", a2, te));
413         performers.add(new RunnableActions("GL3(t3)", a3, te));
414         performers.add(new RunnableActions("GL4(t4)", a4, te));
415         go();
416
417
418
419     }
420     /**
421      * checks that any W will blocked until current W is downgraded to N
422      * UW1: upgrade to W on node 1 (granted)
423      * UW2: upgrade to W on node 2 (queued by coord)
424      * UW3: upgrade to W on node 3 (queued by coord)
425      * UW4: upgrade to W on node 4 (queued by coord)
426      * DN1: downgrade to N on node 1 (UW2 unqueued)
427      * DN2: downgrade to N on node 2 (UW3 unqueued)
428      * DN3: downgrade to N on node 3 (UW4 unqueued)
429      * GL1 (t1) UW1 -->DN1
430      * GL2 (t2) -->UW2......|.....!-->DN2
431      * GL3 (t3) -->UW3..|...........!-->DN3
432      * GL4 (t4) -->UW4................!-->DN4
433      */
434     public void testOneWBlocksMultipleW() throws Exception {
435         trace("testOneWBlocksMultipleW");
436
437         Action UW1 = new Upgrade(GL1, CG, S, W, false);
438         Action UW2 = new Upgrade(GL2, CQ, S, W, false); // QUEUED
439 Action UW3 = new Upgrade(GL3, CQ, S, W, false); // QUEUED
440 Action UW4 = new Upgrade(GL4, CQ, S, W, false); // QUEUED
441 Action DN1 = new Downgrade(GL1, S, N);
442         em.addExpectedEvent(UW2.endEvent(), true); // UW2 UNQUEUED
443 Action DN2 = new Downgrade(GL2, S, N);
444         em.addExpectedEvent(UW3.endEvent(), true); // UW3 UNQUEUED
445 Action DN3 = new Downgrade(GL3, S, N);
446         em.addExpectedEvent(UW4.endEvent(), true); // UW4 UNQUEUED
447 Action DN4 = new Downgrade(GL4, S, N);
448
449         List a1 = new LinkedList (); a1.add(UW1); a1.add(DN1);
450         List a2 = new LinkedList (); a2.add(UW2); a2.add(DN2);
451         List a3 = new LinkedList (); a3.add(UW3); a3.add(DN3);
452         List a4 = new LinkedList (); a4.add(UW4); a4.add(DN4);
453
454         performers.add(new RunnableActions("GL1(t1)", a1, te));
455         performers.add(new RunnableActions("GL2(t2)", a2, te));
456         performers.add(new RunnableActions("GL3(t3)", a3, te));
457         performers.add(new RunnableActions("GL4(t4)", a4, te));
458         go();
459
460
461     }
462     /**
463      * checks that upgrade to R are blocked if there is already an
464      * pending upgrade to W even though the lock is currently granted in R
465      * UR1: upgrade to R on node 1 (granted)
466      * UW2: upgrade to W on node 2 (queued by coord)
467      * UR3: upgrade to R on node 3 (queued by coord)
468      * UR4: upgrade to R on node 4 (queued by coord)
469      * DN1: downgrade to N on node 1 (UW2 unqueued)
470      * DN2: downgrade to N on node 2 (UR3, UR4 unqueued)
471      * DN3: downgrade to N on node 3
472      * DN4: downgrade to N on node 4
473      * GL1 (t1) UR1 -->DN1
474      * GL2 (t2) -->UW2..|.....!-->DN2
475      * GL3 (t3) -->UR3..........!-->DN3
476      * GL4 (t4) UR4..........! DN4
477      */
478     public void test_FIFO_Nodes_R1W2R3R4() throws Exception {
479         trace("test_FIFO_Nodes_R1W2R3R4");
480
481         Action UR1 = new Upgrade(GL1, CG, S, R, false);
482         Action UW2 = new Upgrade(GL2, CQ, S, W, false); // QUEUED
483 Action UR3 = new Upgrade(GL3, CQ, S, R, false); // QUEUED
484 Action UR4 = new Upgrade(GL4, CQ, P, R, false); // QUEUED
485 Action DN1 = new Downgrade(GL1, S, N);
486         em.addExpectedEvent(UW2.endEvent(), true); // UW2 UNQUEUED
487 Action DN2 = new Downgrade(GL2, S, N);
488         em.addExpectedEvent(UR3.endEvent(), true); // UR3 UNQUEUED
489 em.addExpectedEvent(UR4.endEvent(), true); // UR4 UNQUEUED
490 // then, in parallel
491 Action DN3 = new Downgrade(GL3, S, N);
492         Action DN4 = new Downgrade(GL4, P, N);
493
494         List a1 = new LinkedList (); a1.add(UR1); a1.add(DN1);
495         List a2 = new LinkedList (); a2.add(UW2); a2.add(DN2);
496         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
497         List a4 = new LinkedList (); a4.add(UR4); a4.add(DN4);
498
499         performers.add(new RunnableActions("GL1(t1)", a1, te));
500         performers.add(new RunnableActions("GL2(t2)", a2, te));
501         performers.add(new RunnableActions("GL3(t3)", a3, te));
502         performers.add(new RunnableActions("GL4(t4)", a4, te));
503         go();
504     }
505
506
507
508     /**
509      * checks that an upgrade to W is blocked if there is already a
510      * pending upgrade to R and is granted only when all R are downgraded to N
511      * UW1: upgrade to W on node 1 (granted)
512      * UR2: upgrade to R on node 2 (queued by coord)
513      * UR3: upgrade to R on node 3 (queued by coord)
514      * UW4: upgrade to W on node 4 (queued by coord)
515      * DN1: downgrade to N on node 1 (UR2, UR3 unqueued)
516      * DN2: downgrade to N on node 2
517      * DN3: downgrade to N on node 3 (UW4 UNQUEUED)
518      * DN4: downgrade to N on node 4
519      * GL1 (t1) UW1 -->DN1
520      * GL2 (t2) -->UR2...|.....!-->DN2
521      * GL3 (t3) UR3...|.....! -->DN3
522      * GL4 (t4) -->UW4................!-->DN4
523      */
524
525     public void test_FIFO_Nodes_W1R2R3W4() throws Exception {
526         trace("test_FIFO_Nodes_W1R2R3W4");
527         Action UW1 = new Upgrade(GL1, CG, S, W, false);
528         Action UR2 = new Upgrade(GL2, CQ, S, R, false); // QUEUED
529 Action UR3 = new Upgrade(GL3, CQ, P, R, false); // QUEUED
530 Action UW4 = new Upgrade(GL4, CQ, S, W, false); // QUEUED
531 Action DN1 = new Downgrade(GL1, S, N);
532         em.addExpectedEvent(UR2.endEvent(), true); // UR2 UNQUEUED
533 em.addExpectedEvent(UR3.endEvent(), true); // UR3 UNQUEUED
534 Action DN2 = new Downgrade(GL2, S, N);
535         Action DN3 = new Downgrade(GL3, S, N);
536         em.addExpectedEvent(UW4.endEvent(), true); // UW4 UNQUEUED
537 Action DN4 = new Downgrade(GL4, S, N);
538
539         List a1 = new LinkedList (); a1.add(UW1); a1.add(DN1);
540         List a2 = new LinkedList (); a2.add(UR2); a2.add(DN2);
541         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
542         List a4 = new LinkedList (); a4.add(UW4); a4.add(DN4);
543
544         performers.add(new RunnableActions("GL1(t1)", a1, te));
545         performers.add(new RunnableActions("GL2(t2)", a2, te));
546         performers.add(new RunnableActions("GL3(t3)", a3, te));
547         performers.add(new RunnableActions("GL4(t4)", a4, te));
548         go();
549     }
550
551     /**
552      * checks that an upgrade to W is blocked if there is already a
553      * pending upgrade to R and is granted only when all R are downgraded to N
554      * UW1: upgrade to W on node 1 (granted)
555      * UR2: upgrade to R on node 2 (queued by coord)
556      * UR3: upgrade to R on node 3 (queued by coord)
557      * UW4: upgrade to W on node 4 (queued by coord)
558      * DN1: downgrade to N on node 1 (UR2, UR3 unqueued)
559      * DN2: downgrade to N on node 2
560      * DN3: downgrade to N on node 3 (UW4 UNQUEUED)
561      * DN4: downgrade to N on node 4
562      * GL1 (t1) UW1 -->DR1 -->DN1
563      * GL2 (t2) -->UR2...|.....!-->DN2 |
564      * GL3 (t3) UR3...|.....! -->DN3 |
565      * GL4 (t4) -->UW4................!-->DN4
566      */
567
568     public void test_FIFO_Nodes_W1R2R3W4_2() throws Exception {
569         trace("test_FIFO_Nodes_W1R2R3W4_2");
570         Action UW1 = new Upgrade(GL1, CG, S, W, false);
571         Action UR2 = new Upgrade(GL2, CQ, S, R, false); // QUEUED
572 Action UR3 = new Upgrade(GL3, CQ, P, R, false); // QUEUED
573 Action UW4 = new Upgrade(GL4, CQ, S, W, false); // QUEUED
574 Action DR1 = new Downgrade(GL1, S, R);
575         em.addExpectedEvent(UR2.endEvent(), true); // UR2 UNQUEUED
576 em.addExpectedEvent(UR3.endEvent(), true); // UR3 UNQUEUED
577 Action DN2 = new Downgrade(GL2, S, N);
578         Action DN3 = new Downgrade(GL3, S, N);
579         Action DN1 = new Downgrade(GL1, S, N);
580         em.addExpectedEvent(UW4.endEvent(), true); // UW4 UNQUEUED
581 Action DN4 = new Downgrade(GL4, S, N);
582
583         List a1 = new LinkedList (); a1.add(UW1); a1.add(DR1); a1.add(DN1);
584         List a2 = new LinkedList (); a2.add(UR2); a2.add(DN2);
585         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
586         List a4 = new LinkedList (); a4.add(UW4); a4.add(DN4);
587
588         performers.add(new RunnableActions("GL1(t1)", a1, te));
589         performers.add(new RunnableActions("GL2(t2)", a2, te));
590         performers.add(new RunnableActions("GL3(t3)", a3, te));
591         performers.add(new RunnableActions("GL4(t4)", a4, te));
592         go();
593     }
594
595     /**
596      * cheks that W upgrade requests are served in FIFO order and are
597      * not granted until all other nodes have downgraded to N. Also check
598      * that a new arriving R upgrade request will be served after waiting W
599      * UW1: upgrade to W on node 1 (granted)
600      * UW2: upgrade to W on node 2 (queued by coord)
601      * UW3: upgrade to W on node 3 (queued by coord)
602      * UW4: upgrade to W on node 4 (queued by coord)
603      * DR1: downgrade to R on node 1
604      * DN1: downgrade to R on node 1 (UW2 unqueued)
605      * UR1: upgrade to R on node 1 (queued)
606      * DR2: downgrade to R on node 2
607      * DN2: downgrade to N on node 2 (UW3 UNQUEUED)
608      * DR3: downgrade to R on node 3
609      * DN3: downgrade to N on node 3 (UW4 UNQUEUED)
610      * DR4: downgrade to R on node 4 (UR1 UNQUEUED)
611      * DN1b: downgrade to N on node 1
612      * DN4: downgrade to N on node 4
613      * GL1 (t1) UW1 -->DR1-->DN1-->UR1.......................!-->DN1b
614      * GL2 (t2) -->UW2......|...........! DR1-->DN1 | |
615      * GL3 (t3) -->UW3..|.......................!-->DR3-->DN3 | |
616      * GL4 (t4) -->UW4..................................!-->DR4 DN4
617      */
618
619     public void test_FIFO_Nodes_W1W2W3W4R1() throws Exception {
620         trace("test_FIFO_Nodes_W1W2W3W4R1");
621
622         Action UW1 = new Upgrade(GL1, CG, S, W, false);
623         Action UW2 = new Upgrade(GL2, CQ, S, W, false); // QUEUED
624 Action UW3 = new Upgrade(GL3, CQ, S, W, false); // QUEUED
625 Action UW4 = new Upgrade(GL4, CQ, S, W, false); // QUEUED
626 Action DR1 = new Downgrade(GL1, S, R);
627         Action DN1 = new Downgrade(GL1, S, N);
628         em.addExpectedEvent(UW2.endEvent(), true); // UW2 UNQUEUED
629 Action UR1 = new Upgrade(GL1, CQ, S, R, true); // QUEUED
630 Action DR2 = new Downgrade(GL2, P, R);
631         Action DN2 = new Downgrade(GL2, S, N);
632         em.addExpectedEvent(UW3.endEvent(), true); // UW3 UNQUEUED
633 Action DR3 = new Downgrade(GL3, S, R);
634         Action DN3 = new Downgrade(GL3, S, N);
635         em.addExpectedEvent(UW4.endEvent(), true); // UW4 UNQUEUED
636 Action DR4 = new Downgrade(GL4, S, R);
637         em.addExpectedEvent(UR1.endEvent(), true); // UR1 UNQUEUED
638
639         Action DN1b = new Downgrade(GL1, S, N);
640         Action DN4 = new Downgrade(GL4, P, N);
641
642         List a1 = new LinkedList (); a1.add(UW1); a1.add(DR1); a1.add(DN1);
643                                     a1.add(UR1); a1.add(DN1b);
644         List a2 = new LinkedList (); a2.add(UW2); a2.add(DR2); a2.add(DN2);
645         List a3 = new LinkedList (); a3.add(UW3); a2.add(DR3); a3.add(DN3);
646         List a4 = new LinkedList (); a4.add(UW4); a2.add(DR4); a4.add(DN4);
647
648         performers.add(new RunnableActions("GL1(t1)", a1, te));
649         performers.add(new RunnableActions("GL2(t2)", a2, te));
650         performers.add(new RunnableActions("GL3(t3)", a3, te));
651         performers.add(new RunnableActions("GL4(t4)", a4, te));
652         go();
653     }
654
655
656     /* FIFO between threads on 2 different nodes (GL1 & GL2)
657      * Actually, THIS IS NOT REAL FIFO, since R2 will pass while R2 must
658      * wait for W1 to be downgraded what has been called back
659      * Note however that this does not lead to starvation because it will
660      * not prevent R2 from being unblocked
661      *
662      * UR1a: upgrade to R on node 1 (granted)
663      * UW2a: upgrade to W on node 2 (queued because of UR1a)
664      * UR1b: upgrade to R on node 1 (queued after UW2a)
665      * UR2b: upgrade to R on node 2 (queued after UW2a but before UR1b)
666      * DR1a: downgrade to R on node 1
667      * DN1a: downgrade to N on node 1 (UW2a & UR2b unqueued)
668      * DR2: downgrade to R on node 2 (UR1b unqueued)
669      * DN1b: downgrade to N on node 1
670      * DN2b: downgrade to N on node 2
671      *
672      * GL1 (t1) UR1a -->DR1a-->DN1a
673      * GL1 (t2) | -->UR1b.|.............|.......!-->DN1b
674      * GL2 (t3) -->UW2a.|...|.............!-->DR2a |
675      * GL2 (t4) -->UR2b...........! DN2b
676      *
677      */
678
679     public void test_FIFO_Threads_R1W2R1R2() throws Exception {
680         trace("test_FIFO_Threads_R1W2R1R2");
681         Action UR1a = new Upgrade(GL1, CG, S, R, false);
682         Action UW2a = new Upgrade(GL2, CQ, S, W, false);
683         Action UR1b = new Upgrade(GL1, CQ, S, R, true); // must wait Call Back
684 Action UR2b = new Upgrade(GL2, UQ, S, R, false);
685         Action DR1a = new Downgrade(GL1, S, R);
686         Action DN1a = new Downgrade(GL1, S, N);
687         em.addExpectedEvent(UW2a.endEvent(), true);
688         em.addExpectedEvent(UR2b.endEvent(), true);
689         Action DR2a = new Downgrade(GL2, S, R);
690         em.addExpectedEvent(UR1b.endEvent(), true);
691         Action DN1b = new Downgrade(GL1, S, N);
692         Action DN2b = new Downgrade(GL2, P, N);
693
694         List a1 = new LinkedList (); a1.add(UR1a); a1.add(DR1a); a1.add(DN1a);
695         List a2 = new LinkedList (); a2.add(UR1b); a2.add(DN1b);
696         List a3 = new LinkedList (); a3.add(UW2a); a3.add(DR2a);
697         List a4 = new LinkedList (); a4.add(UR2b); a4.add(DN2b);
698
699         performers.add(new RunnableActions("GL1(t1)", a1, te));
700         performers.add(new RunnableActions("GL1(t2)", a2, te));
701         performers.add(new RunnableActions("GL2(t3)", a3, te));
702         performers.add(new RunnableActions("GL2(t4)", a4, te));
703         go();
704
705
706     }
707
708     /* FIFO between threads on 2 different nodes (GL1 & GL2)
709      * Actually, THIS IS NOT REAL FIFO, since UR2 will be queued before UR1
710      * Note however that this does not lead to starvation because
711      * UR2 will eventually be unqueued
712      *
713      * UW1a: upgrade to W on node 1 (granted)
714      * UW2a: upgrade to W on node 2 (queued because of UW1a)
715      * UR1b: upgrade to R on node 1 (queued after UW2a)
716      * UR2b: upgrade to R on node 2 (queued after UW2a but before UR1b)
717      * DR1a: downgrade to R on node 1
718      * DN1a: downgrade to N on node 1 (UW2a & UR2b unqueued)
719      * DR2a: downgrade to R on node 1 (UR1b unqueued)
720      *
721      * GL1 (t1) UW1a -->DR1a-->DN1a
722      * GL1 (t2) | -->UR1b.|.............|.......!-->DN1b
723      * GL2 (t3) -->UW2a.|...|.............!-->DR2a |
724      * GL2 (t4) -->UR2b...........! DN2b
725      *
726      */
727     public void test_FIFO_Threads_W1W2R1R2() throws Exception {
728         trace("test_FIFO_Threads_W1W2R1R2");
729
730         Action UW1a = new Upgrade(GL1, CG, S, W, false);
731         Action UW2a = new Upgrade(GL2, CQ, S, W, false);
732         Action UR1b = new Upgrade(GL1, CQ, S, R, true); // must wait Call Back
733 Action UR2b = new Upgrade(GL2, UQ, S, R, false);
734         Action DR1a = new Downgrade(GL1, S, R);
735         Action DN1a = new Downgrade(GL1, S, N);
736         em.addExpectedEvent(UW2a.endEvent(), true);
737         em.addExpectedEvent(UR2b.endEvent(), true);
738         Action DR2a = new Downgrade(GL2, S, R);
739         em.addExpectedEvent(UR1b.endEvent(), true);
740         Action DN1b = new Downgrade(GL1, S, N);
741         Action DN2b = new Downgrade(GL2, P, N);
742
743         List a1 = new LinkedList (); a1.add(UW1a); a1.add(DR1a); a1.add(DN1a);
744         List a2 = new LinkedList (); a2.add(UR1b); a2.add(DN1b);
745         List a3 = new LinkedList (); a3.add(UW2a); a3.add(DR2a);
746         List a4 = new LinkedList (); a4.add(UR2b); a4.add(DN2b);
747
748         performers.add(new RunnableActions("GL1(t1)", a1, te));
749         performers.add(new RunnableActions("GL1(t2)", a2, te));
750         performers.add(new RunnableActions("GL2(t3)", a3, te));
751         performers.add(new RunnableActions("GL2(t4)", a4, te));
752         go();
753
754
755
756     }
757
758     /* FIFO between threads on 2 different nodes (GL1 & GL2)
759      *
760      * UR1a: upgrade to R on node 1 (granted)
761      * UW2a: upgrade to W on node 2 (queued because of UW1a)
762      * UW1b: upgrade to W on node 1 (queued after UW2a)
763      * UR2b: upgrade to R on node 2 (queued after UW2a but before UW1b)
764      * DN1a: downgrade to N on node 1 (UW2a & UR2b unqueued)
765      * DR2a: downgrade to R on node 1
766      * DN2b: downgrade to N on node 1 (UW1b unqueued)
767      * DR1b: downgrade to N on node 1
768      *
769      * GL1 (t1) UR1a -->DN1a
770      * GL1 (t2) | -->UW1b.|......|...........!-->DN1b
771      * GL2 (t3) -->UW2a.|...|......!-->DR2a |
772      * GL2 (t4) -->UR2b....! -->DN2b
773      *
774      */
775     public void test_FIFO_Threads_R1W2W1R2() throws Exception {
776         trace("test_FIFO_Threads_R1W2W1R2");
777
778         Action UR1a = new Upgrade(GL1, CG, S, R, false);
779         Action UW2a = new Upgrade(GL2, CQ, S, W, false);
780         Action UR1b = new Upgrade(GL1, CQ, S, R, true); // must wait call back
781 Action UR2b = new Upgrade(GL2, UQ, S, R, false);
782         Action DN1a = new Downgrade(GL1, S, N);
783         em.addExpectedEvent(UW2a.endEvent(), true);
784         em.addExpectedEvent(UR2b.endEvent(), true);
785         Action DR2a = new Downgrade(GL2, S, R);
786         Action DN2b = new Downgrade(GL2, S, N);
787         em.addExpectedEvent(UR1b.endEvent(), true);
788         Action DN1b = new Downgrade(GL1, S, N);
789
790         List a1 = new LinkedList (); a1.add(UR1a); a1.add(DN1a);
791         List a2 = new LinkedList (); a2.add(UR1b); a2.add(DN1b);
792         List a3 = new LinkedList (); a3.add(UW2a); a3.add(DR2a);
793         List a4 = new LinkedList (); a4.add(UR2b); a4.add(DN2b);
794
795         performers.add(new RunnableActions("GL1(t1)", a1, te));
796         performers.add(new RunnableActions("GL2(t2)", a2, te));
797         performers.add(new RunnableActions("GL1(t3)", a3, te));
798         performers.add(new RunnableActions("GL2(t4)", a4, te));
799         go();
800
801
802     }
803
804     /**
805      * Make sure coord failure does not impact lock management
806      * Actually it may impact granting order
807      * UW1: upgrade to W on node 1 (granted)
808      * UW2: upgrade to R on node 2 (queued)
809      * UW3: upgrade to R on node 3 (queued)
810      * KN4 : kill coordinator
811      * DN1: downgrade to N on node 1 (UR2, UR3 unqueued)
812      * DN2: downgrade to N on node 2
813      * DN3: downgrade to N on node 3
814      *
815      * GL1 (t1) UW1 -->DN1
816      * GL2 (t2) -->UR2....|.....!-->DN2
817      * GL3 (t3) UR3....|.....! DN3
818      * GL4 (t4) -->KN4
819      *
820      */
821     public void test_Failure1() throws Exception {
822         trace("test_Failure1");
823         Action UW1 = new Upgrade(GL1, CG, S, W, false);
824         Action UR2 = new Upgrade(GL2, CQ, S, R, false);
825         Action UR3 = new Upgrade(GL3, CQ, P, R, false);
826         Action KN4 = new KillNodeAndWait("KN4", drsm, N4, r1);
827         Action DN1 = new Downgrade(GL1, S, N);
828         em.addExpectedEvent(UR2.endEvent(), true);
829         em.addExpectedEvent(UR3.endEvent(), true);
830         Action DN2 = new Downgrade(GL2, S, N);
831         Action DN3 = new Downgrade(GL3, P, N);
832
833         List a1 = new LinkedList (); a1.add(UW1); a1.add(DN1);
834         List a2 = new LinkedList (); a2.add(UR2); a2.add(DN2);
835         List a3 = new LinkedList (); a3.add(UR3); a3.add(DN3);
836         List a4 = new LinkedList (); a4.add(KN4);
837
838         performers.add(new RunnableActions("GL1(t1)", a1, te));
839         performers.add(new RunnableActions("GL2(t2)", a2, te));
840         performers.add(new RunnableActions("GL3(t3)", a3, te));
841         performers.add(new RunnableActions("GL4(t4)", a4, te));
842         go(standardRunTime, 1);
843
844     }
845
846 }
847
848
849

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags